blob: a16b035cd1685c6ce654a1d086b88c9fadf59bcd [file] [log] [blame]
// Copyright (c) 2013, the Dart project authors. Please see the AUTHORS file
// for details. All rights reserved. Use of this source code is governed by a
// BSD-style license that can be found in the LICENSE file.
#ifndef RUNTIME_VM_COMPILER_BACKEND_IL_H_
#define RUNTIME_VM_COMPILER_BACKEND_IL_H_
#include "vm/allocation.h"
#include "vm/code_descriptors.h"
#include "vm/compiler/backend/compile_type.h"
#include "vm/compiler/backend/locations.h"
#include "vm/compiler/backend/slot.h"
#include "vm/compiler/compiler_state.h"
#include "vm/compiler/ffi.h"
#include "vm/compiler/method_recognizer.h"
#include "vm/flags.h"
#include "vm/growable_array.h"
#include "vm/native_entry.h"
#include "vm/object.h"
#include "vm/parser.h"
#include "vm/static_type_exactness_state.h"
#include "vm/token_position.h"
namespace dart {
class BitVector;
class BlockEntryInstr;
class BlockEntryWithInitialDefs;
class BoxIntegerInstr;
class BufferFormatter;
class CallTargets;
class CatchBlockEntryInstr;
class ComparisonInstr;
class Definition;
class Environment;
class FlowGraph;
class FlowGraphCompiler;
class FlowGraphVisitor;
class Instruction;
class LocalVariable;
class LoopInfo;
class ParsedFunction;
class Range;
class RangeAnalysis;
class RangeBoundary;
class UnboxIntegerInstr;
class TypeUsageInfo;
namespace compiler {
class BlockBuilder;
}
class Value : public ZoneAllocated {
public:
// A forward iterator that allows removing the current value from the
// underlying use list during iteration.
class Iterator {
public:
explicit Iterator(Value* head) : next_(head) { Advance(); }
Value* Current() const { return current_; }
bool Done() const { return current_ == NULL; }
void Advance() {
// Pre-fetch next on advance and cache it.
current_ = next_;
if (next_ != NULL) next_ = next_->next_use();
}
private:
Value* current_;
Value* next_;
};
explicit Value(Definition* definition)
: definition_(definition),
previous_use_(NULL),
next_use_(NULL),
instruction_(NULL),
use_index_(-1),
reaching_type_(NULL) {}
Definition* definition() const { return definition_; }
void set_definition(Definition* definition) { definition_ = definition; }
Value* previous_use() const { return previous_use_; }
void set_previous_use(Value* previous) { previous_use_ = previous; }
Value* next_use() const { return next_use_; }
void set_next_use(Value* next) { next_use_ = next; }
bool IsSingleUse() const {
return (next_use_ == NULL) && (previous_use_ == NULL);
}
Instruction* instruction() const { return instruction_; }
void set_instruction(Instruction* instruction) { instruction_ = instruction; }
intptr_t use_index() const { return use_index_; }
void set_use_index(intptr_t index) { use_index_ = index; }
static void AddToList(Value* value, Value** list);
void RemoveFromUseList();
// Change the definition after use lists have been computed.
inline void BindTo(Definition* definition);
inline void BindToEnvironment(Definition* definition);
Value* Copy(Zone* zone) { return new (zone) Value(definition_); }
// CopyWithType() must only be used when the new Value is dominated by
// the original Value.
Value* CopyWithType(Zone* zone) {
Value* copy = new (zone) Value(definition_);
copy->reaching_type_ = reaching_type_;
return copy;
}
Value* CopyWithType() { return CopyWithType(Thread::Current()->zone()); }
CompileType* Type();
void SetReachingType(CompileType* type) { reaching_type_ = type; }
void RefineReachingType(CompileType* type);
void PrintTo(BufferFormatter* f) const;
const char* ToCString() const;
bool IsSmiValue() { return Type()->ToCid() == kSmiCid; }
// Return true if the value represents a constant.
bool BindsToConstant() const;
// Return true if the value represents the constant null.
bool BindsToConstantNull() const;
// Assert if BindsToConstant() is false, otherwise returns the constant value.
const Object& BoundConstant() const;
// Return true if storing the value into a heap object requires applying the
// write barrier.
bool NeedsWriteBarrier();
bool Equals(Value* other) const;
private:
friend class FlowGraphPrinter;
Definition* definition_;
Value* previous_use_;
Value* next_use_;
Instruction* instruction_;
intptr_t use_index_;
CompileType* reaching_type_;
DISALLOW_COPY_AND_ASSIGN(Value);
};
// Represents a range of class-ids for use in class checks and polymorphic
// dispatches. The range includes both ends, i.e. it is [cid_start, cid_end].
struct CidRange : public ZoneAllocated {
CidRange(const CidRange& o)
: ZoneAllocated(), cid_start(o.cid_start), cid_end(o.cid_end) {}
CidRange(intptr_t cid_start_arg, intptr_t cid_end_arg)
: cid_start(cid_start_arg), cid_end(cid_end_arg) {}
CidRange() : cid_start(kIllegalCid), cid_end(kIllegalCid) {}
const CidRange& operator=(const CidRange& other) {
cid_start = other.cid_start;
cid_end = other.cid_end;
return *this;
}
bool IsSingleCid() const { return cid_start == cid_end; }
bool Contains(intptr_t cid) { return cid_start <= cid && cid <= cid_end; }
int32_t Extent() const { return cid_end - cid_start; }
// The number of class ids this range covers.
intptr_t size() const { return cid_end - cid_start + 1; }
bool IsIllegalRange() const {
return cid_start == kIllegalCid && cid_end == kIllegalCid;
}
intptr_t cid_start;
intptr_t cid_end;
};
typedef MallocGrowableArray<CidRange> CidRangeVector;
class HierarchyInfo : public ThreadStackResource {
public:
explicit HierarchyInfo(Thread* thread)
: ThreadStackResource(thread),
cid_subtype_ranges_nullable_(NULL),
cid_subtype_ranges_abstract_nullable_(NULL),
cid_subtype_ranges_nonnullable_(NULL),
cid_subclass_ranges_(NULL) {
thread->set_hierarchy_info(this);
}
~HierarchyInfo() {
thread()->set_hierarchy_info(NULL);
delete[] cid_subtype_ranges_nullable_;
cid_subtype_ranges_nullable_ = NULL;
delete[] cid_subtype_ranges_abstract_nullable_;
cid_subtype_ranges_abstract_nullable_ = NULL;
delete[] cid_subtype_ranges_nonnullable_;
cid_subtype_ranges_nonnullable_ = NULL;
delete[] cid_subclass_ranges_;
cid_subclass_ranges_ = NULL;
}
const CidRangeVector& SubtypeRangesForClass(const Class& klass,
bool include_abstract,
bool exclude_null);
const CidRangeVector& SubclassRangesForClass(const Class& klass);
bool InstanceOfHasClassRange(const AbstractType& type,
intptr_t* lower_limit,
intptr_t* upper_limit);
// Returns `true` if a simple [CidRange]-based subtype-check can be used to
// determine if a given instance's type is a subtype of [type].
//
// This is the case for [type]s without type arguments or where the type
// arguments are all dynamic (known as "rare type").
bool CanUseSubtypeRangeCheckFor(const AbstractType& type);
// Returns `true` if a combination of [CidRange]-based checks can be used to
// determine if a given instance's type is a subtype of [type].
//
// This is the case for [type]s with type arguments where we are able to do a
// [CidRange]-based subclass-check against the class and [CidRange]-based
// subtype-checks against the type arguments.
//
// This method should only be called if [CanUseSubtypeRangecheckFor] returned
// false.
bool CanUseGenericSubtypeRangeCheckFor(const AbstractType& type);
private:
// Does not use any hierarchy information available in the system but computes
// it via O(n) class table traversal. The boolean parameters denote:
// use_subtype_test : if set, IsSubtypeOf() is used to compute inclusion
// include_abstract : if set, include abstract types (don't care otherwise)
// exclude_null : if set, exclude null types (don't care otherwise)
void BuildRangesFor(ClassTable* table,
CidRangeVector* ranges,
const Class& klass,
bool use_subtype_test,
bool include_abstract,
bool exclude_null);
// In JIT mode we use hierarchy information stored in the [RawClass]s
// direct_subclasses_/direct_implementors_ arrays.
void BuildRangesForJIT(ClassTable* table,
CidRangeVector* ranges,
const Class& klass,
bool use_subtype_test,
bool include_abstract,
bool exclude_null);
CidRangeVector* cid_subtype_ranges_nullable_;
CidRangeVector* cid_subtype_ranges_abstract_nullable_;
CidRangeVector* cid_subtype_ranges_nonnullable_;
CidRangeVector* cid_subclass_ranges_;
};
// An embedded container with N elements of type T. Used (with partial
// specialization for N=0) because embedded arrays cannot have size 0.
template <typename T, intptr_t N>
class EmbeddedArray {
public:
EmbeddedArray() : elements_() {}
intptr_t length() const { return N; }
const T& operator[](intptr_t i) const {
ASSERT(i < length());
return elements_[i];
}
T& operator[](intptr_t i) {
ASSERT(i < length());
return elements_[i];
}
const T& At(intptr_t i) const { return (*this)[i]; }
void SetAt(intptr_t i, const T& val) { (*this)[i] = val; }
private:
T elements_[N];
};
template <typename T>
class EmbeddedArray<T, 0> {
public:
intptr_t length() const { return 0; }
const T& operator[](intptr_t i) const {
UNREACHABLE();
static T sentinel = 0;
return sentinel;
}
T& operator[](intptr_t i) {
UNREACHABLE();
static T sentinel = 0;
return sentinel;
}
};
// Instructions.
// M is a two argument macro. It is applied to each concrete instruction type
// name. The concrete instruction classes are the name with Instr concatenated.
struct InstrAttrs {
enum Attributes {
_ = 0, // No special attributes.
//
// The instruction is guaranteed to not trigger GC on a non-exceptional
// path. If the conditions depend on parameters of the instruction, do not
// use this attribute but overload CanTriggerGC() instead.
kNoGC = 1
};
};
#define FOR_EACH_INSTRUCTION(M) \
M(GraphEntry, kNoGC) \
M(JoinEntry, kNoGC) \
M(TargetEntry, kNoGC) \
M(FunctionEntry, kNoGC) \
M(OsrEntry, kNoGC) \
M(IndirectEntry, kNoGC) \
M(CatchBlockEntry, kNoGC) \
M(Phi, kNoGC) \
M(Redefinition, kNoGC) \
M(Parameter, kNoGC) \
M(LoadIndexedUnsafe, kNoGC) \
M(StoreIndexedUnsafe, kNoGC) \
M(TailCall, kNoGC) \
M(ParallelMove, kNoGC) \
M(PushArgument, kNoGC) \
M(Return, kNoGC) \
M(Throw, kNoGC) \
M(ReThrow, kNoGC) \
M(Stop, _) \
M(Goto, kNoGC) \
M(IndirectGoto, kNoGC) \
M(Branch, kNoGC) \
M(AssertAssignable, _) \
M(AssertSubtype, _) \
M(AssertBoolean, _) \
M(SpecialParameter, kNoGC) \
M(ClosureCall, _) \
M(FfiCall, _) \
M(InstanceCall, _) \
M(PolymorphicInstanceCall, _) \
M(StaticCall, _) \
M(LoadLocal, kNoGC) \
M(DropTemps, kNoGC) \
M(MakeTemp, kNoGC) \
M(StoreLocal, kNoGC) \
M(StrictCompare, kNoGC) \
M(EqualityCompare, kNoGC) \
M(RelationalOp, kNoGC) \
M(NativeCall, _) \
M(DebugStepCheck, _) \
M(LoadIndexed, kNoGC) \
M(LoadCodeUnits, kNoGC) \
M(StoreIndexed, kNoGC) \
M(StoreInstanceField, _) \
M(InitStaticField, _) \
M(LoadStaticField, kNoGC) \
M(StoreStaticField, kNoGC) \
M(BooleanNegate, kNoGC) \
M(InstanceOf, _) \
M(CreateArray, _) \
M(AllocateObject, _) \
M(LoadField, kNoGC) \
M(LoadUntagged, kNoGC) \
M(LoadClassId, kNoGC) \
M(InstantiateType, _) \
M(InstantiateTypeArguments, _) \
M(AllocateContext, _) \
M(AllocateUninitializedContext, _) \
M(CloneContext, _) \
M(BinarySmiOp, kNoGC) \
M(CheckedSmiComparison, _) \
M(CheckedSmiOp, _) \
M(BinaryInt32Op, kNoGC) \
M(UnarySmiOp, kNoGC) \
M(UnaryDoubleOp, kNoGC) \
M(CheckStackOverflow, _) \
M(SmiToDouble, kNoGC) \
M(Int32ToDouble, kNoGC) \
M(Int64ToDouble, kNoGC) \
M(DoubleToInteger, _) \
M(DoubleToSmi, kNoGC) \
M(DoubleToDouble, kNoGC) \
M(DoubleToFloat, kNoGC) \
M(FloatToDouble, kNoGC) \
M(CheckClass, kNoGC) \
M(CheckClassId, kNoGC) \
M(CheckSmi, kNoGC) \
M(CheckNull, kNoGC) \
M(CheckCondition, kNoGC) \
M(Constant, kNoGC) \
M(UnboxedConstant, kNoGC) \
M(CheckEitherNonSmi, kNoGC) \
M(BinaryDoubleOp, kNoGC) \
M(DoubleTestOp, kNoGC) \
M(MathUnary, kNoGC) \
M(MathMinMax, kNoGC) \
M(Box, _) \
M(Unbox, kNoGC) \
M(BoxInt64, _) \
M(UnboxInt64, kNoGC) \
M(CaseInsensitiveCompareUC16, _) \
M(BinaryInt64Op, kNoGC) \
M(ShiftInt64Op, kNoGC) \
M(SpeculativeShiftInt64Op, kNoGC) \
M(UnaryInt64Op, kNoGC) \
M(CheckArrayBound, kNoGC) \
M(GenericCheckBound, kNoGC) \
M(Constraint, _) \
M(StringToCharCode, kNoGC) \
M(OneByteStringFromCharCode, kNoGC) \
M(StringInterpolate, _) \
M(InvokeMathCFunction, _) \
M(TruncDivMod, kNoGC) \
/*We could be more precise about when these 2 instructions can trigger GC.*/ \
M(GuardFieldClass, _) \
M(GuardFieldLength, _) \
M(GuardFieldType, _) \
M(IfThenElse, kNoGC) \
M(MaterializeObject, _) \
M(TestSmi, kNoGC) \
M(TestCids, kNoGC) \
M(ExtractNthOutput, kNoGC) \
M(BinaryUint32Op, kNoGC) \
M(ShiftUint32Op, kNoGC) \
M(SpeculativeShiftUint32Op, kNoGC) \
M(UnaryUint32Op, kNoGC) \
M(BoxUint32, _) \
M(UnboxUint32, kNoGC) \
M(BoxInt32, _) \
M(UnboxInt32, kNoGC) \
M(UnboxedIntConverter, _) \
M(Deoptimize, kNoGC) \
M(SimdOp, kNoGC)
#define FOR_EACH_ABSTRACT_INSTRUCTION(M) \
M(BlockEntry, _) \
M(BoxInteger, _) \
M(UnboxInteger, _) \
M(Comparison, _) \
M(UnaryIntegerOp, _) \
M(BinaryIntegerOp, _) \
M(ShiftIntegerOp, _) \
M(Allocation, _)
#define FORWARD_DECLARATION(type, attrs) class type##Instr;
FOR_EACH_INSTRUCTION(FORWARD_DECLARATION)
FOR_EACH_ABSTRACT_INSTRUCTION(FORWARD_DECLARATION)
#undef FORWARD_DECLARATION
#define DEFINE_INSTRUCTION_TYPE_CHECK(type) \
virtual type##Instr* As##type() { return this; } \
virtual const char* DebugName() const { return #type; }
// Functions required in all concrete instruction classes.
#define DECLARE_INSTRUCTION_NO_BACKEND(type) \
virtual Tag tag() const { return k##type; } \
virtual void Accept(FlowGraphVisitor* visitor); \
DEFINE_INSTRUCTION_TYPE_CHECK(type)
#define DECLARE_INSTRUCTION_BACKEND() \
virtual LocationSummary* MakeLocationSummary(Zone* zone, bool optimizing) \
const; \
virtual void EmitNativeCode(FlowGraphCompiler* compiler);
// Functions required in all concrete instruction classes.
#define DECLARE_INSTRUCTION(type) \
DECLARE_INSTRUCTION_NO_BACKEND(type) \
DECLARE_INSTRUCTION_BACKEND()
#if defined(TARGET_ARCH_DBC)
#define DECLARE_COMPARISON_METHODS \
virtual LocationSummary* MakeLocationSummary(Zone* zone, bool optimizing) \
const; \
virtual Condition EmitComparisonCode(FlowGraphCompiler* compiler, \
BranchLabels labels); \
virtual Condition GetNextInstructionCondition(FlowGraphCompiler* compiler, \
BranchLabels labels);
#else
#define DECLARE_COMPARISON_METHODS \
virtual LocationSummary* MakeLocationSummary(Zone* zone, bool optimizing) \
const; \
virtual Condition EmitComparisonCode(FlowGraphCompiler* compiler, \
BranchLabels labels);
#endif
#define DECLARE_COMPARISON_INSTRUCTION(type) \
DECLARE_INSTRUCTION_NO_BACKEND(type) \
DECLARE_COMPARISON_METHODS
#if !defined(PRODUCT) || defined(FORCE_INCLUDE_DISASSEMBLER)
#define PRINT_TO_SUPPORT virtual void PrintTo(BufferFormatter* f) const;
#else
#define PRINT_TO_SUPPORT
#endif // !defined(PRODUCT) || defined(FORCE_INCLUDE_DISASSEMBLER)
#if !defined(PRODUCT) || defined(FORCE_INCLUDE_DISASSEMBLER)
#define PRINT_OPERANDS_TO_SUPPORT \
virtual void PrintOperandsTo(BufferFormatter* f) const;
#else
#define PRINT_OPERANDS_TO_SUPPORT
#endif // !defined(PRODUCT) || defined(FORCE_INCLUDE_DISASSEMBLER)
// Together with CidRange, this represents a mapping from a range of class-ids
// to a method for a given selector (method name). Also can contain an
// indication of how frequently a given method has been called at a call site.
// This information can be harvested from the inline caches (ICs).
struct TargetInfo : public CidRange {
TargetInfo(intptr_t cid_start_arg,
intptr_t cid_end_arg,
const Function* target_arg,
intptr_t count_arg,
StaticTypeExactnessState exactness)
: CidRange(cid_start_arg, cid_end_arg),
target(target_arg),
count(count_arg),
exactness(exactness) {
ASSERT(target->IsZoneHandle());
}
const Function* target;
intptr_t count;
StaticTypeExactnessState exactness;
};
// A set of class-ids, arranged in ranges. Used for the CheckClass
// and PolymorphicInstanceCall instructions.
class Cids : public ZoneAllocated {
public:
explicit Cids(Zone* zone) : zone_(zone) {}
// Creates the off-heap Cids object that reflects the contents
// of the on-VM-heap IC data.
static Cids* Create(Zone* zone, const ICData& ic_data, int argument_number);
static Cids* CreateMonomorphic(Zone* zone, intptr_t cid);
bool Equals(const Cids& other) const;
bool HasClassId(intptr_t cid) const;
void Add(CidRange* target) { cid_ranges_.Add(target); }
CidRange& operator[](intptr_t index) const { return *cid_ranges_[index]; }
CidRange* At(int index) const { return cid_ranges_[index]; }
intptr_t length() const { return cid_ranges_.length(); }
void SetLength(intptr_t len) { cid_ranges_.SetLength(len); }
bool is_empty() const { return cid_ranges_.is_empty(); }
void Sort(int compare(CidRange* const* a, CidRange* const* b)) {
cid_ranges_.Sort(compare);
}
bool IsMonomorphic() const;
intptr_t MonomorphicReceiverCid() const;
intptr_t ComputeLowestCid() const;
intptr_t ComputeHighestCid() const;
protected:
void CreateHelper(Zone* zone,
const ICData& ic_data,
int argument_number,
bool include_targets);
GrowableArray<CidRange*> cid_ranges_;
Zone* zone_;
private:
DISALLOW_IMPLICIT_CONSTRUCTORS(Cids);
};
class CallTargets : public Cids {
public:
explicit CallTargets(Zone* zone) : Cids(zone) {}
// Creates the off-heap CallTargets object that reflects the contents
// of the on-VM-heap IC data.
static CallTargets* Create(Zone* zone, const ICData& ic_data);
// This variant also expands the class-ids to neighbouring classes that
// inherit the same method.
static CallTargets* CreateAndExpand(Zone* zone, const ICData& ic_data);
TargetInfo* TargetAt(int i) const { return static_cast<TargetInfo*>(At(i)); }
intptr_t AggregateCallCount() const;
bool HasSingleTarget() const;
bool HasSingleRecognizedTarget() const;
const Function& FirstTarget() const;
const Function& MostPopularTarget() const;
private:
void MergeIntoRanges();
};
class Instruction : public ZoneAllocated {
public:
#define DECLARE_TAG(type, attrs) k##type,
enum Tag { FOR_EACH_INSTRUCTION(DECLARE_TAG) kNumInstructions };
#undef DECLARE_TAG
static const intptr_t kInstructionAttrs[kNumInstructions];
enum SpeculativeMode {
// Types of inputs should be checked when unboxing for this instruction.
kGuardInputs,
// Each input is guaranteed to have a valid type for the input
// representation and its type should not be checked when unboxing.
kNotSpeculative
};
explicit Instruction(intptr_t deopt_id = DeoptId::kNone)
: deopt_id_(deopt_id),
lifetime_position_(kNoPlaceId),
previous_(NULL),
next_(NULL),
env_(NULL),
locs_(NULL),
inlining_id_(-1) {}
virtual ~Instruction() {}
virtual Tag tag() const = 0;
virtual intptr_t statistics_tag() const { return tag(); }
intptr_t deopt_id() const {
ASSERT(ComputeCanDeoptimize() || CanBecomeDeoptimizationTarget());
return GetDeoptId();
}
const ICData* GetICData(
const ZoneGrowableArray<const ICData*>& ic_data_array) const;
virtual TokenPosition token_pos() const { return TokenPosition::kNoSource; }
virtual intptr_t InputCount() const = 0;
virtual Value* InputAt(intptr_t i) const = 0;
void SetInputAt(intptr_t i, Value* value) {
ASSERT(value != NULL);
value->set_instruction(this);
value->set_use_index(i);
RawSetInputAt(i, value);
}
// Remove all inputs (including in the environment) from their
// definition's use lists.
void UnuseAllInputs();
// Call instructions override this function and return the number of
// pushed arguments.
virtual intptr_t ArgumentCount() const { return 0; }
virtual PushArgumentInstr* PushArgumentAt(intptr_t index) const {
UNREACHABLE();
return NULL;
}
inline Definition* ArgumentAt(intptr_t index) const;
// Returns true, if this instruction can deoptimize with its current inputs.
// This property can change if we add or remove redefinitions that constrain
// the type or the range of input operands during compilation.
virtual bool ComputeCanDeoptimize() const = 0;
// Once we removed the deopt environment, we assume that this
// instruction can't deoptimize.
bool CanDeoptimize() const { return env() != NULL && ComputeCanDeoptimize(); }
// Visiting support.
virtual void Accept(FlowGraphVisitor* visitor) = 0;
Instruction* previous() const { return previous_; }
void set_previous(Instruction* instr) {
ASSERT(!IsBlockEntry());
previous_ = instr;
}
Instruction* next() const { return next_; }
void set_next(Instruction* instr) {
ASSERT(!IsGraphEntry());
ASSERT(!IsReturn());
ASSERT(!IsBranch() || (instr == NULL));
ASSERT(!IsPhi());
ASSERT(instr == NULL || !instr->IsBlockEntry());
// TODO(fschneider): Also add Throw and ReThrow to the list of instructions
// that do not have a successor. Currently, the graph builder will continue
// to append instruction in case of a Throw inside an expression. This
// condition should be handled in the graph builder
next_ = instr;
}
// Link together two instruction.
void LinkTo(Instruction* next) {
ASSERT(this != next);
this->set_next(next);
next->set_previous(this);
}
// Removed this instruction from the graph, after use lists have been
// computed. If the instruction is a definition with uses, those uses are
// unaffected (so the instruction can be reinserted, e.g., hoisting).
Instruction* RemoveFromGraph(bool return_previous = true);
// Normal instructions can have 0 (inside a block) or 1 (last instruction in
// a block) successors. Branch instruction with >1 successors override this
// function.
virtual intptr_t SuccessorCount() const;
virtual BlockEntryInstr* SuccessorAt(intptr_t index) const;
void Goto(JoinEntryInstr* entry);
virtual const char* DebugName() const = 0;
#if defined(DEBUG)
// Checks that the field stored in an instruction has proper form:
// - must be a zone-handle
// - In background compilation, must be cloned.
// Aborts if field is not OK.
void CheckField(const Field& field) const;
#else
void CheckField(const Field& field) const {}
#endif // DEBUG
// Printing support.
const char* ToCString() const;
#if !defined(PRODUCT) || defined(FORCE_INCLUDE_DISASSEMBLER)
virtual void PrintTo(BufferFormatter* f) const;
virtual void PrintOperandsTo(BufferFormatter* f) const;
#endif
#define DECLARE_INSTRUCTION_TYPE_CHECK(Name, Type) \
bool Is##Name() { return (As##Name() != NULL); } \
virtual Type* As##Name() { return NULL; }
#define INSTRUCTION_TYPE_CHECK(Name, Attrs) \
DECLARE_INSTRUCTION_TYPE_CHECK(Name, Name##Instr)
DECLARE_INSTRUCTION_TYPE_CHECK(Definition, Definition)
DECLARE_INSTRUCTION_TYPE_CHECK(BlockEntryWithInitialDefs,
BlockEntryWithInitialDefs)
FOR_EACH_INSTRUCTION(INSTRUCTION_TYPE_CHECK)
FOR_EACH_ABSTRACT_INSTRUCTION(INSTRUCTION_TYPE_CHECK)
#undef INSTRUCTION_TYPE_CHECK
#undef DECLARE_INSTRUCTION_TYPE_CHECK
template <typename T>
T* Cast() {
return static_cast<T*>(this);
}
// Returns structure describing location constraints required
// to emit native code for this instruction.
LocationSummary* locs() {
ASSERT(locs_ != NULL);
return locs_;
}
bool HasLocs() const { return locs_ != NULL; }
virtual LocationSummary* MakeLocationSummary(Zone* zone,
bool is_optimizing) const = 0;
void InitializeLocationSummary(Zone* zone, bool optimizing) {
ASSERT(locs_ == NULL);
locs_ = MakeLocationSummary(zone, optimizing);
}
static LocationSummary* MakeCallSummary(Zone* zone);
virtual void EmitNativeCode(FlowGraphCompiler* compiler) { UNIMPLEMENTED(); }
Environment* env() const { return env_; }
void SetEnvironment(Environment* deopt_env);
void RemoveEnvironment();
intptr_t lifetime_position() const { return lifetime_position_; }
void set_lifetime_position(intptr_t pos) { lifetime_position_ = pos; }
bool HasUnmatchedInputRepresentations() const;
// Returns representation expected for the input operand at the given index.
virtual Representation RequiredInputRepresentation(intptr_t idx) const {
return kTagged;
}
// By default, instructions should check types of inputs when unboxing.
virtual SpeculativeMode speculative_mode() const { return kGuardInputs; }
// Representation of the value produced by this computation.
virtual Representation representation() const { return kTagged; }
bool WasEliminated() const { return next() == NULL; }
// Returns deoptimization id that corresponds to the deoptimization target
// that input operands conversions inserted for this instruction can jump
// to.
virtual intptr_t DeoptimizationTarget() const {
UNREACHABLE();
return DeoptId::kNone;
}
// Returns a replacement for the instruction or NULL if the instruction can
// be eliminated. By default returns the this instruction which means no
// change.
virtual Instruction* Canonicalize(FlowGraph* flow_graph);
// Insert this instruction before 'next' after use lists are computed.
// Instructions cannot be inserted before a block entry or any other
// instruction without a previous instruction.
void InsertBefore(Instruction* next) { InsertAfter(next->previous()); }
// Insert this instruction after 'prev' after use lists are computed.
void InsertAfter(Instruction* prev);
// Append an instruction to the current one and return the tail.
// This function updated def-use chains of the newly appended
// instruction.
Instruction* AppendInstruction(Instruction* tail);
// Returns true if CSE and LICM are allowed for this instruction.
virtual bool AllowsCSE() const { return false; }
// Returns true if this instruction has any side-effects besides storing.
// See StoreInstanceFieldInstr::HasUnknownSideEffects() for rationale.
virtual bool HasUnknownSideEffects() const = 0;
virtual bool CanTriggerGC() const;
// Get the block entry for this instruction.
virtual BlockEntryInstr* GetBlock();
// Place identifiers used by the load optimization pass.
intptr_t place_id() const { return place_id_; }
void set_place_id(intptr_t place_id) { place_id_ = place_id; }
bool HasPlaceId() const { return place_id_ != kNoPlaceId; }
intptr_t inlining_id() const { return inlining_id_; }
void set_inlining_id(intptr_t value) {
ASSERT(value >= 0);
inlining_id_ = value;
}
bool has_inlining_id() const { return inlining_id_ >= 0; }
// Returns a hash code for use with hash maps.
virtual intptr_t Hashcode() const;
// Compares two instructions. Returns true, iff:
// 1. They have the same tag.
// 2. All input operands are Equals.
// 3. They satisfy AttributesEqual.
bool Equals(Instruction* other) const;
// Compare attributes of a instructions (except input operands and tag).
// All instructions that participate in CSE have to override this function.
// This function can assume that the argument has the same type as this.
virtual bool AttributesEqual(Instruction* other) const {
UNREACHABLE();
return false;
}
virtual void InheritDeoptTarget(Zone* zone, Instruction* other);
bool NeedsEnvironment() const {
return ComputeCanDeoptimize() || CanBecomeDeoptimizationTarget();
}
virtual bool CanBecomeDeoptimizationTarget() const { return false; }
void InheritDeoptTargetAfter(FlowGraph* flow_graph,
Definition* call,
Definition* result);
virtual bool MayThrow() const = 0;
bool IsDominatedBy(Instruction* dom);
void ClearEnv() { env_ = NULL; }
void Unsupported(FlowGraphCompiler* compiler);
static bool SlowPathSharingSupported(bool is_optimizing) {
#if defined(TARGET_ARCH_X64) || defined(TARGET_ARCH_ARM) || \
defined(TARGET_ARCH_ARM64)
return FLAG_enable_slow_path_sharing && FLAG_precompiled_mode &&
is_optimizing;
#else
return false;
#endif
}
virtual bool UseSharedSlowPathStub(bool is_optimizing) const { return false; }
protected:
// GetDeoptId and/or CopyDeoptIdFrom.
friend class CallSiteInliner;
friend class LICM;
friend class ComparisonInstr;
friend class Scheduler;
friend class BlockEntryInstr;
friend class CatchBlockEntryInstr; // deopt_id_
friend class DebugStepCheckInstr; // deopt_id_
friend class StrictCompareInstr; // deopt_id_
// Fetch deopt id without checking if this computation can deoptimize.
intptr_t GetDeoptId() const { return deopt_id_; }
void CopyDeoptIdFrom(const Instruction& instr) {
deopt_id_ = instr.deopt_id_;
}
private:
friend class BranchInstr; // For RawSetInputAt.
friend class IfThenElseInstr; // For RawSetInputAt.
friend class CheckConditionInstr; // For RawSetInputAt.
virtual void RawSetInputAt(intptr_t i, Value* value) = 0;
enum { kNoPlaceId = -1 };
intptr_t deopt_id_;
union {
intptr_t lifetime_position_; // Position used by register allocator.
intptr_t place_id_;
};
Instruction* previous_;
Instruction* next_;
Environment* env_;
LocationSummary* locs_;
intptr_t inlining_id_;
DISALLOW_COPY_AND_ASSIGN(Instruction);
};
struct BranchLabels {
Label* true_label;
Label* false_label;
Label* fall_through;
};
class PureInstruction : public Instruction {
public:
explicit PureInstruction(intptr_t deopt_id) : Instruction(deopt_id) {}
virtual bool AllowsCSE() const { return true; }
virtual bool HasUnknownSideEffects() const { return false; }
};
// Types to be used as ThrowsTrait for TemplateInstruction/TemplateDefinition.
struct Throws {
static const bool kCanThrow = true;
};
struct NoThrow {
static const bool kCanThrow = false;
};
// Types to be used as CSETrait for TemplateInstruction/TemplateDefinition.
// Pure instructions are those that allow CSE and have no effects and
// no dependencies.
template <typename DefaultBase, typename PureBase>
struct Pure {
typedef PureBase Base;
};
template <typename DefaultBase, typename PureBase>
struct NoCSE {
typedef DefaultBase Base;
};
template <intptr_t N,
typename ThrowsTrait,
template <typename Default, typename Pure> class CSETrait = NoCSE>
class TemplateInstruction
: public CSETrait<Instruction, PureInstruction>::Base {
public:
explicit TemplateInstruction(intptr_t deopt_id = DeoptId::kNone)
: CSETrait<Instruction, PureInstruction>::Base(deopt_id), inputs_() {}
virtual intptr_t InputCount() const { return N; }
virtual Value* InputAt(intptr_t i) const { return inputs_[i]; }
virtual bool MayThrow() const { return ThrowsTrait::kCanThrow; }
protected:
EmbeddedArray<Value*, N> inputs_;
private:
virtual void RawSetInputAt(intptr_t i, Value* value) { inputs_[i] = value; }
};
class MoveOperands : public ZoneAllocated {
public:
MoveOperands(Location dest, Location src) : dest_(dest), src_(src) {}
Location src() const { return src_; }
Location dest() const { return dest_; }
Location* src_slot() { return &src_; }
Location* dest_slot() { return &dest_; }
void set_src(const Location& value) { src_ = value; }
void set_dest(const Location& value) { dest_ = value; }
// The parallel move resolver marks moves as "in-progress" by clearing the
// destination (but not the source).
Location MarkPending() {
ASSERT(!IsPending());
Location dest = dest_;
dest_ = Location::NoLocation();
return dest;
}
void ClearPending(Location dest) {
ASSERT(IsPending());
dest_ = dest;
}
bool IsPending() const {
ASSERT(!src_.IsInvalid() || dest_.IsInvalid());
return dest_.IsInvalid() && !src_.IsInvalid();
}
// True if this move a move from the given location.
bool Blocks(Location loc) const {
return !IsEliminated() && src_.Equals(loc);
}
// A move is redundant if it's been eliminated, if its source and
// destination are the same, or if its destination is unneeded.
bool IsRedundant() const {
return IsEliminated() || dest_.IsInvalid() || src_.Equals(dest_);
}
// We clear both operands to indicate move that's been eliminated.
void Eliminate() { src_ = dest_ = Location::NoLocation(); }
bool IsEliminated() const {
ASSERT(!src_.IsInvalid() || dest_.IsInvalid());
return src_.IsInvalid();
}
private:
Location dest_;
Location src_;
DISALLOW_COPY_AND_ASSIGN(MoveOperands);
};
class ParallelMoveInstr : public TemplateInstruction<0, NoThrow> {
public:
ParallelMoveInstr() : moves_(4) {}
DECLARE_INSTRUCTION(ParallelMove)
virtual intptr_t ArgumentCount() const { return 0; }
virtual bool ComputeCanDeoptimize() const { return false; }
virtual bool HasUnknownSideEffects() const {
UNREACHABLE(); // This instruction never visited by optimization passes.
return false;
}
MoveOperands* AddMove(Location dest, Location src) {
MoveOperands* move = new MoveOperands(dest, src);
moves_.Add(move);
return move;
}
MoveOperands* MoveOperandsAt(intptr_t index) const { return moves_[index]; }
intptr_t NumMoves() const { return moves_.length(); }
bool IsRedundant() const;
virtual TokenPosition token_pos() const {
return TokenPosition::kParallelMove;
}
PRINT_TO_SUPPORT
private:
GrowableArray<MoveOperands*> moves_; // Elements cannot be null.
DISALLOW_COPY_AND_ASSIGN(ParallelMoveInstr);
};
// Basic block entries are administrative nodes. There is a distinguished
// graph entry with no predecessor. Joins are the only nodes with multiple
// predecessors. Targets are all other basic block entries. The types
// enforce edge-split form---joins are forbidden as the successors of
// branches.
class BlockEntryInstr : public Instruction {
public:
virtual intptr_t PredecessorCount() const = 0;
virtual BlockEntryInstr* PredecessorAt(intptr_t index) const = 0;
intptr_t preorder_number() const { return preorder_number_; }
void set_preorder_number(intptr_t number) { preorder_number_ = number; }
intptr_t postorder_number() const { return postorder_number_; }
void set_postorder_number(intptr_t number) { postorder_number_ = number; }
intptr_t block_id() const { return block_id_; }
// NOTE: These are SSA positions and not token positions. These are used by
// the register allocator.
void set_start_pos(intptr_t pos) { start_pos_ = pos; }
intptr_t start_pos() const { return start_pos_; }
void set_end_pos(intptr_t pos) { end_pos_ = pos; }
intptr_t end_pos() const { return end_pos_; }
BlockEntryInstr* dominator() const { return dominator_; }
BlockEntryInstr* ImmediateDominator() const;
const GrowableArray<BlockEntryInstr*>& dominated_blocks() {
return dominated_blocks_;
}
void AddDominatedBlock(BlockEntryInstr* block) {
ASSERT(!block->IsFunctionEntry() || this->IsGraphEntry());
block->set_dominator(this);
dominated_blocks_.Add(block);
}
void ClearDominatedBlocks() { dominated_blocks_.Clear(); }
bool Dominates(BlockEntryInstr* other) const;
Instruction* last_instruction() const { return last_instruction_; }
void set_last_instruction(Instruction* instr) { last_instruction_ = instr; }
ParallelMoveInstr* parallel_move() const { return parallel_move_; }
bool HasParallelMove() const { return parallel_move_ != NULL; }
bool HasNonRedundantParallelMove() const {
return HasParallelMove() && !parallel_move()->IsRedundant();
}
ParallelMoveInstr* GetParallelMove() {
if (parallel_move_ == NULL) {
parallel_move_ = new ParallelMoveInstr();
}
return parallel_move_;
}
// Discover basic-block structure of the current block. Must be called
// on all graph blocks in preorder to yield valid results. As a side effect,
// the block entry instructions in the graph are assigned preorder numbers.
// The array 'preorder' maps preorder block numbers to the block entry
// instruction with that number. The depth first spanning tree is recorded
// in the array 'parent', which maps preorder block numbers to the preorder
// number of the block's spanning-tree parent. As a side effect of this
// function, the set of basic block predecessors (e.g., block entry
// instructions of predecessor blocks) and also the last instruction in the
// block is recorded in each entry instruction. Returns true when called the
// first time on this particular block within one graph traversal, and false
// on all successive calls.
bool DiscoverBlock(BlockEntryInstr* predecessor,
GrowableArray<BlockEntryInstr*>* preorder,
GrowableArray<intptr_t>* parent);
virtual intptr_t InputCount() const { return 0; }
virtual Value* InputAt(intptr_t i) const {
UNREACHABLE();
return NULL;
}
virtual intptr_t ArgumentCount() const { return 0; }
virtual bool CanBecomeDeoptimizationTarget() const {
// BlockEntry environment is copied to Goto and Branch instructions
// when we insert new blocks targeting this block.
return true;
}
virtual bool ComputeCanDeoptimize() const { return false; }
virtual bool HasUnknownSideEffects() const { return false; }
virtual bool MayThrow() const { return false; }
intptr_t try_index() const { return try_index_; }
void set_try_index(intptr_t index) { try_index_ = index; }
// True for blocks inside a try { } region.
bool InsideTryBlock() const { return try_index_ != kInvalidTryIndex; }
// Loop related methods.
LoopInfo* loop_info() const { return loop_info_; }
void set_loop_info(LoopInfo* loop_info) { loop_info_ = loop_info; }
bool IsLoopHeader() const;
intptr_t NestingDepth() const;
virtual BlockEntryInstr* GetBlock() { return this; }
virtual TokenPosition token_pos() const {
return TokenPosition::kControlFlow;
}
// Helper to mutate the graph during inlining. This block should be
// replaced with new_block as a predecessor of all of this block's
// successors.
void ReplaceAsPredecessorWith(BlockEntryInstr* new_block);
void set_block_id(intptr_t block_id) { block_id_ = block_id; }
intptr_t offset() const { return offset_; }
void set_offset(intptr_t offset) { offset_ = offset; }
// For all instruction in this block: Remove all inputs (including in the
// environment) from their definition's use lists for all instructions.
void ClearAllInstructions();
DEFINE_INSTRUCTION_TYPE_CHECK(BlockEntry)
protected:
BlockEntryInstr(intptr_t block_id, intptr_t try_index, intptr_t deopt_id)
: Instruction(deopt_id),
block_id_(block_id),
try_index_(try_index),
preorder_number_(-1),
postorder_number_(-1),
dominator_(nullptr),
dominated_blocks_(1),
last_instruction_(NULL),
offset_(-1),
parallel_move_(nullptr),
loop_info_(nullptr) {}
// Perform a depth first search to find OSR entry and
// link it to the given graph entry.
bool FindOsrEntryAndRelink(GraphEntryInstr* graph_entry,
Instruction* parent,
BitVector* block_marks);
private:
virtual void RawSetInputAt(intptr_t i, Value* value) { UNREACHABLE(); }
virtual void ClearPredecessors() = 0;
virtual void AddPredecessor(BlockEntryInstr* predecessor) = 0;
void set_dominator(BlockEntryInstr* instr) { dominator_ = instr; }
intptr_t block_id_;
intptr_t try_index_;
intptr_t preorder_number_;
intptr_t postorder_number_;
// Starting and ending lifetime positions for this block. Used by
// the linear scan register allocator.
intptr_t start_pos_;
intptr_t end_pos_;
BlockEntryInstr* dominator_; // Immediate dominator, NULL for graph entry.
// TODO(fschneider): Optimize the case of one child to save space.
GrowableArray<BlockEntryInstr*> dominated_blocks_;
Instruction* last_instruction_;
// Offset of this block from the start of the emitted code.
intptr_t offset_;
// Parallel move that will be used by linear scan register allocator to
// connect live ranges at the start of the block.
ParallelMoveInstr* parallel_move_;
// Closest enveloping loop in loop hierarchy (nullptr at nesting depth 0).
LoopInfo* loop_info_;
DISALLOW_COPY_AND_ASSIGN(BlockEntryInstr);
};
class ForwardInstructionIterator : public ValueObject {
public:
explicit ForwardInstructionIterator(BlockEntryInstr* block_entry)
: current_(block_entry) {
Advance();
}
void Advance() {
ASSERT(!Done());
current_ = current_->next();
}
bool Done() const { return current_ == NULL; }
// Removes 'current_' from graph and sets 'current_' to previous instruction.
void RemoveCurrentFromGraph();
Instruction* Current() const { return current_; }
private:
Instruction* current_;
};
class BackwardInstructionIterator : public ValueObject {
public:
explicit BackwardInstructionIterator(BlockEntryInstr* block_entry)
: block_entry_(block_entry), current_(block_entry->last_instruction()) {
ASSERT(block_entry_->previous() == NULL);
}
void Advance() {
ASSERT(!Done());
current_ = current_->previous();
}
bool Done() const { return current_ == block_entry_; }
void RemoveCurrentFromGraph();
Instruction* Current() const { return current_; }
private:
BlockEntryInstr* block_entry_;
Instruction* current_;
};
// Base class shared by all block entries which define initial definitions.
//
// The initial definitions define parameters, special parameters and constants.
class BlockEntryWithInitialDefs : public BlockEntryInstr {
public:
BlockEntryWithInitialDefs(intptr_t block_id,
intptr_t try_index,
intptr_t deopt_id)
: BlockEntryInstr(block_id, try_index, deopt_id) {}
GrowableArray<Definition*>* initial_definitions() {
return &initial_definitions_;
}
virtual bool IsBlockEntryWithInitialDefs() { return true; }
virtual BlockEntryWithInitialDefs* AsBlockEntryWithInitialDefs() {
return this;
}
protected:
void PrintInitialDefinitionsTo(BufferFormatter* f) const;
private:
GrowableArray<Definition*> initial_definitions_;
DISALLOW_COPY_AND_ASSIGN(BlockEntryWithInitialDefs);
};
class GraphEntryInstr : public BlockEntryWithInitialDefs {
public:
GraphEntryInstr(const ParsedFunction& parsed_function,
intptr_t osr_id);
DECLARE_INSTRUCTION(GraphEntry)
virtual intptr_t PredecessorCount() const { return 0; }
virtual BlockEntryInstr* PredecessorAt(intptr_t index) const {
UNREACHABLE();
return NULL;
}
virtual intptr_t SuccessorCount() const;
virtual BlockEntryInstr* SuccessorAt(intptr_t index) const;
void AddCatchEntry(CatchBlockEntryInstr* entry) { catch_entries_.Add(entry); }
CatchBlockEntryInstr* GetCatchEntry(intptr_t index);
void AddIndirectEntry(IndirectEntryInstr* entry) {
indirect_entries_.Add(entry);
}
ConstantInstr* constant_null();
void RelinkToOsrEntry(Zone* zone, intptr_t max_block_id);
bool IsCompiledForOsr() const;
intptr_t osr_id() const { return osr_id_; }
intptr_t entry_count() const { return entry_count_; }
void set_entry_count(intptr_t count) { entry_count_ = count; }
intptr_t spill_slot_count() const { return spill_slot_count_; }
void set_spill_slot_count(intptr_t count) {
ASSERT(count >= 0);
spill_slot_count_ = count;
}
// Number of stack slots reserved for compiling try-catch. For functions
// without try-catch, this is 0. Otherwise, it is the number of local
// variables.
intptr_t fixed_slot_count() const { return fixed_slot_count_; }
void set_fixed_slot_count(intptr_t count) {
ASSERT(count >= 0);
fixed_slot_count_ = count;
}
FunctionEntryInstr* normal_entry() const { return normal_entry_; }
FunctionEntryInstr* unchecked_entry() const { return unchecked_entry_; }
void set_normal_entry(FunctionEntryInstr* entry) { normal_entry_ = entry; }
void set_unchecked_entry(FunctionEntryInstr* target) {
unchecked_entry_ = target;
}
OsrEntryInstr* osr_entry() const { return osr_entry_; }
void set_osr_entry(OsrEntryInstr* entry) { osr_entry_ = entry; }
const ParsedFunction& parsed_function() const { return parsed_function_; }
const GrowableArray<CatchBlockEntryInstr*>& catch_entries() const {
return catch_entries_;
}
const GrowableArray<IndirectEntryInstr*>& indirect_entries() const {
return indirect_entries_;
}
bool HasSingleEntryPoint() const {
return catch_entries().is_empty() && unchecked_entry() == nullptr;
}
PRINT_TO_SUPPORT
private:
virtual void ClearPredecessors() {}
virtual void AddPredecessor(BlockEntryInstr* predecessor) { UNREACHABLE(); }
const ParsedFunction& parsed_function_;
FunctionEntryInstr* normal_entry_ = nullptr;
FunctionEntryInstr* unchecked_entry_ = nullptr;
OsrEntryInstr* osr_entry_ = nullptr;
GrowableArray<CatchBlockEntryInstr*> catch_entries_;
// Indirect targets are blocks reachable only through indirect gotos.
GrowableArray<IndirectEntryInstr*> indirect_entries_;
const intptr_t osr_id_;
intptr_t entry_count_;
intptr_t spill_slot_count_;
intptr_t fixed_slot_count_; // For try-catch in optimized code.
DISALLOW_COPY_AND_ASSIGN(GraphEntryInstr);
};
class JoinEntryInstr : public BlockEntryInstr {
public:
JoinEntryInstr(intptr_t block_id, intptr_t try_index, intptr_t deopt_id)
: BlockEntryInstr(block_id, try_index, deopt_id),
predecessors_(2), // Two is the assumed to be the common case.
phis_(NULL) {}
DECLARE_INSTRUCTION(JoinEntry)
virtual intptr_t PredecessorCount() const { return predecessors_.length(); }
virtual BlockEntryInstr* PredecessorAt(intptr_t index) const {
return predecessors_[index];
}
// Returns -1 if pred is not in the list.
intptr_t IndexOfPredecessor(BlockEntryInstr* pred) const;
ZoneGrowableArray<PhiInstr*>* phis() const { return phis_; }
PhiInstr* InsertPhi(intptr_t var_index, intptr_t var_count);
void RemoveDeadPhis(Definition* replacement);
void InsertPhi(PhiInstr* phi);
void RemovePhi(PhiInstr* phi);
virtual bool HasUnknownSideEffects() const { return false; }
PRINT_TO_SUPPORT
private:
// Classes that have access to predecessors_ when inlining.
friend class BlockEntryInstr;
friend class InlineExitCollector;
friend class PolymorphicInliner;
friend class IndirectEntryInstr; // Access in il_printer.cc.
// Direct access to phis_ in order to resize it due to phi elimination.
friend class ConstantPropagator;
friend class DeadCodeElimination;
virtual void ClearPredecessors() { predecessors_.Clear(); }
virtual void AddPredecessor(BlockEntryInstr* predecessor);
GrowableArray<BlockEntryInstr*> predecessors_;
ZoneGrowableArray<PhiInstr*>* phis_;
DISALLOW_COPY_AND_ASSIGN(JoinEntryInstr);
};
class PhiIterator : public ValueObject {
public:
explicit PhiIterator(JoinEntryInstr* join) : phis_(join->phis()), index_(0) {}
void Advance() {
ASSERT(!Done());
index_++;
}
bool Done() const { return (phis_ == NULL) || (index_ >= phis_->length()); }
PhiInstr* Current() const { return (*phis_)[index_]; }
private:
ZoneGrowableArray<PhiInstr*>* phis_;
intptr_t index_;
};
class TargetEntryInstr : public BlockEntryInstr {
public:
TargetEntryInstr(intptr_t block_id, intptr_t try_index, intptr_t deopt_id)
: BlockEntryInstr(block_id, try_index, deopt_id),
predecessor_(NULL),
edge_weight_(0.0) {}
DECLARE_INSTRUCTION(TargetEntry)
double edge_weight() const { return edge_weight_; }
void set_edge_weight(double weight) { edge_weight_ = weight; }
void adjust_edge_weight(double scale_factor) { edge_weight_ *= scale_factor; }
virtual intptr_t PredecessorCount() const {
return (predecessor_ == NULL) ? 0 : 1;
}
virtual BlockEntryInstr* PredecessorAt(intptr_t index) const {
ASSERT((index == 0) && (predecessor_ != NULL));
return predecessor_;
}
PRINT_TO_SUPPORT
private:
friend class BlockEntryInstr; // Access to predecessor_ when inlining.
virtual void ClearPredecessors() { predecessor_ = NULL; }
virtual void AddPredecessor(BlockEntryInstr* predecessor) {
ASSERT(predecessor_ == NULL);
predecessor_ = predecessor;
}
BlockEntryInstr* predecessor_;
double edge_weight_;
DISALLOW_COPY_AND_ASSIGN(TargetEntryInstr);
};
// Represents an entrypoint to a function which callers can invoke (i.e. not
// used for OSR entries).
//
// The flow graph builder might decide to create create multiple entrypoints
// (e.g. checked/unchecked entrypoints) and will attach those to the
// [GraphEntryInstr].
//
// Every entrypoint has it's own initial definitions. The SSA renaming
// will insert phi's for parameter instructions if necessary.
class FunctionEntryInstr : public BlockEntryWithInitialDefs {
public:
FunctionEntryInstr(GraphEntryInstr* graph_entry,
intptr_t block_id,
intptr_t try_index,
intptr_t deopt_id)
: BlockEntryWithInitialDefs(block_id, try_index, deopt_id),
graph_entry_(graph_entry) {}
DECLARE_INSTRUCTION(FunctionEntry)
virtual intptr_t PredecessorCount() const {
return (graph_entry_ == nullptr) ? 0 : 1;
}
virtual BlockEntryInstr* PredecessorAt(intptr_t index) const {
ASSERT(index == 0 && graph_entry_ != nullptr);
return graph_entry_;
}
GraphEntryInstr* graph_entry() const { return graph_entry_; }
PRINT_TO_SUPPORT
private:
virtual void ClearPredecessors() { graph_entry_ = nullptr; }
virtual void AddPredecessor(BlockEntryInstr* predecessor) {
ASSERT(graph_entry_ == nullptr && predecessor->IsGraphEntry());
graph_entry_ = predecessor->AsGraphEntry();
}
GraphEntryInstr* graph_entry_;
DISALLOW_COPY_AND_ASSIGN(FunctionEntryInstr);
};
// Represents an OSR entrypoint to a function.
//
// The OSR entry has it's own initial definitions.
class OsrEntryInstr : public BlockEntryWithInitialDefs {
public:
OsrEntryInstr(GraphEntryInstr* graph_entry,
intptr_t block_id,
intptr_t try_index,
intptr_t deopt_id)
: BlockEntryWithInitialDefs(block_id, try_index, deopt_id),
graph_entry_(graph_entry) {}
DECLARE_INSTRUCTION(OsrEntry)
virtual intptr_t PredecessorCount() const {
return (graph_entry_ == nullptr) ? 0 : 1;
}
virtual BlockEntryInstr* PredecessorAt(intptr_t index) const {
ASSERT(index == 0 && graph_entry_ != nullptr);
return graph_entry_;
}
GraphEntryInstr* graph_entry() const { return graph_entry_; }
PRINT_TO_SUPPORT
private:
virtual void ClearPredecessors() { graph_entry_ = nullptr; }
virtual void AddPredecessor(BlockEntryInstr* predecessor) {
ASSERT(graph_entry_ == nullptr && predecessor->IsGraphEntry());
graph_entry_ = predecessor->AsGraphEntry();
}
GraphEntryInstr* graph_entry_;
DISALLOW_COPY_AND_ASSIGN(OsrEntryInstr);
};
class IndirectEntryInstr : public JoinEntryInstr {
public:
IndirectEntryInstr(intptr_t block_id,
intptr_t indirect_id,
intptr_t try_index,
intptr_t deopt_id)
: JoinEntryInstr(block_id, try_index, deopt_id),
indirect_id_(indirect_id) {}
DECLARE_INSTRUCTION(IndirectEntry)
intptr_t indirect_id() const { return indirect_id_; }
PRINT_TO_SUPPORT
private:
const intptr_t indirect_id_;
};
class CatchBlockEntryInstr : public BlockEntryWithInitialDefs {
public:
CatchBlockEntryInstr(TokenPosition handler_token_pos,
bool is_generated,
intptr_t block_id,
intptr_t try_index,
GraphEntryInstr* graph_entry,
const Array& handler_types,
intptr_t catch_try_index,
bool needs_stacktrace,
intptr_t deopt_id,
const LocalVariable* exception_var,
const LocalVariable* stacktrace_var,
const LocalVariable* raw_exception_var,
const LocalVariable* raw_stacktrace_var)
: BlockEntryWithInitialDefs(block_id, try_index, deopt_id),
graph_entry_(graph_entry),
predecessor_(NULL),
catch_handler_types_(Array::ZoneHandle(handler_types.raw())),
catch_try_index_(catch_try_index),
exception_var_(exception_var),
stacktrace_var_(stacktrace_var),
raw_exception_var_(raw_exception_var),
raw_stacktrace_var_(raw_stacktrace_var),
needs_stacktrace_(needs_stacktrace),
handler_token_pos_(handler_token_pos),
is_generated_(is_generated) {}
DECLARE_INSTRUCTION(CatchBlockEntry)
virtual intptr_t PredecessorCount() const {
return (predecessor_ == NULL) ? 0 : 1;
}
virtual BlockEntryInstr* PredecessorAt(intptr_t index) const {
ASSERT((index == 0) && (predecessor_ != NULL));
return predecessor_;
}
GraphEntryInstr* graph_entry() const { return graph_entry_; }
const LocalVariable* exception_var() const { return exception_var_; }
const LocalVariable* stacktrace_var() const { return stacktrace_var_; }
const LocalVariable* raw_exception_var() const { return raw_exception_var_; }
const LocalVariable* raw_stacktrace_var() const {
return raw_stacktrace_var_;
}
bool needs_stacktrace() const { return needs_stacktrace_; }
bool is_generated() const { return is_generated_; }
TokenPosition handler_token_pos() const { return handler_token_pos_; }
// Returns try index for the try block to which this catch handler
// corresponds.
intptr_t catch_try_index() const { return catch_try_index_; }
PRINT_TO_SUPPORT
private:
friend class BlockEntryInstr; // Access to predecessor_ when inlining.
virtual void ClearPredecessors() { predecessor_ = NULL; }
virtual void AddPredecessor(BlockEntryInstr* predecessor) {
ASSERT(predecessor_ == NULL);
predecessor_ = predecessor;
}
GraphEntryInstr* graph_entry_;
BlockEntryInstr* predecessor_;
const Array& catch_handler_types_;
const intptr_t catch_try_index_;
GrowableArray<Definition*> initial_definitions_;
const LocalVariable* exception_var_;
const LocalVariable* stacktrace_var_;
const LocalVariable* raw_exception_var_;
const LocalVariable* raw_stacktrace_var_;
const bool needs_stacktrace_;
TokenPosition handler_token_pos_;
bool is_generated_;
DISALLOW_COPY_AND_ASSIGN(CatchBlockEntryInstr);
};
// If the result of the allocation is not stored into any field, passed
// as an argument or used in a phi then it can't alias with any other
// SSA value.
class AliasIdentity : public ValueObject {
public:
// It is unknown if value has aliases.
static AliasIdentity Unknown() { return AliasIdentity(kUnknown); }
// It is known that value can have aliases.
static AliasIdentity Aliased() { return AliasIdentity(kAliased); }
// It is known that value has no aliases.
static AliasIdentity NotAliased() { return AliasIdentity(kNotAliased); }
// It is known that value has no aliases and it was selected by
// allocation sinking pass as a candidate.
static AliasIdentity AllocationSinkingCandidate() {
return AliasIdentity(kAllocationSinkingCandidate);
}
bool IsUnknown() const { return value_ == kUnknown; }
bool IsAliased() const { return value_ == kAliased; }
bool IsNotAliased() const { return (value_ & kNotAliased) != 0; }
bool IsAllocationSinkingCandidate() const {
return value_ == kAllocationSinkingCandidate;
}
AliasIdentity(const AliasIdentity& other)
: ValueObject(), value_(other.value_) {}
AliasIdentity& operator=(const AliasIdentity& other) {
value_ = other.value_;
return *this;
}
private:
explicit AliasIdentity(intptr_t value) : value_(value) {}
enum {
kUnknown = 0,
kNotAliased = 1,
kAliased = 2,
kAllocationSinkingCandidate = 3,
};
COMPILE_ASSERT((kUnknown & kNotAliased) == 0);
COMPILE_ASSERT((kAliased & kNotAliased) == 0);
COMPILE_ASSERT((kAllocationSinkingCandidate & kNotAliased) != 0);
intptr_t value_;
};
// Abstract super-class of all instructions that define a value (Bind, Phi).
class Definition : public Instruction {
public:
explicit Definition(intptr_t deopt_id = DeoptId::kNone);
// Overridden by definitions that have call counts.
virtual intptr_t CallCount() const {
UNREACHABLE();
return -1;
}
intptr_t temp_index() const { return temp_index_; }
void set_temp_index(intptr_t index) { temp_index_ = index; }
void ClearTempIndex() { temp_index_ = -1; }
bool HasTemp() const { return temp_index_ >= 0; }
intptr_t ssa_temp_index() const { return ssa_temp_index_; }
void set_ssa_temp_index(intptr_t index) {
ASSERT(index >= 0);
ssa_temp_index_ = index;
}
bool HasSSATemp() const { return ssa_temp_index_ >= 0; }
void ClearSSATempIndex() { ssa_temp_index_ = -1; }
bool HasPairRepresentation() const {
#if defined(TARGET_ARCH_X64) || defined(TARGET_ARCH_ARM64)
return representation() == kPairOfTagged;
#else
return (representation() == kPairOfTagged) ||
(representation() == kUnboxedInt64);
#endif
}
// Compile time type of the definition, which may be requested before type
// propagation during graph building.
CompileType* Type() {
if (type_ == NULL) {
type_ = new CompileType(ComputeType());
}
return type_;
}
bool HasType() const { return (type_ != NULL); }
inline bool IsInt64Definition();
bool IsInt32Definition() {
return IsBinaryInt32Op() || IsBoxInt32() || IsUnboxInt32() ||
IsUnboxedIntConverter();
}
// Compute compile type for this definition. It is safe to use this
// approximation even before type propagator was run (e.g. during graph
// building).
virtual CompileType ComputeType() const { return CompileType::Dynamic(); }
// Update CompileType of the definition. Returns true if the type has changed.
virtual bool RecomputeType() { return false; }
PRINT_OPERANDS_TO_SUPPORT
PRINT_TO_SUPPORT
bool UpdateType(CompileType new_type) {
if (type_ == NULL) {
type_ = new CompileType(new_type);
return true;
}
if (type_->IsNone() || !type_->IsEqualTo(&new_type)) {
*type_ = new_type;
return true;
}
return false;
}
bool HasUses() const {
return (input_use_list_ != NULL) || (env_use_list_ != NULL);
}
bool HasOnlyUse(Value* use) const;
bool HasOnlyInputUse(Value* use) const;
Value* input_use_list() const { return input_use_list_; }
void set_input_use_list(Value* head) { input_use_list_ = head; }
Value* env_use_list() const { return env_use_list_; }
void set_env_use_list(Value* head) { env_use_list_ = head; }
void AddInputUse(Value* value) { Value::AddToList(value, &input_use_list_); }
void AddEnvUse(Value* value) { Value::AddToList(value, &env_use_list_); }
// Replace uses of this definition with uses of other definition or value.
// Precondition: use lists must be properly calculated.
// Postcondition: use lists and use values are still valid.
void ReplaceUsesWith(Definition* other);
// Replace this definition with another instruction. Use the provided result
// definition to replace uses of the original definition. If replacing during
// iteration, pass the iterator so that the instruction can be replaced
// without affecting iteration order, otherwise pass a NULL iterator.
void ReplaceWithResult(Instruction* replacement,
Definition* replacement_for_uses,
ForwardInstructionIterator* iterator);
// Replace this definition and all uses with another definition. If
// replacing during iteration, pass the iterator so that the instruction
// can be replaced without affecting iteration order, otherwise pass a
// NULL iterator.
void ReplaceWith(Definition* other, ForwardInstructionIterator* iterator);
// A value in the constant propagation lattice.
// - non-constant sentinel
// - a constant (any non-sentinel value)
// - unknown sentinel
Object& constant_value();
virtual void InferRange(RangeAnalysis* analysis, Range* range);
Range* range() const { return range_; }
void set_range(const Range&);
// Definitions can be canonicalized only into definitions to ensure
// this check statically we override base Canonicalize with a Canonicalize
// returning Definition (return type is covariant).
virtual Definition* Canonicalize(FlowGraph* flow_graph);
static const intptr_t kReplacementMarker = -2;
Definition* Replacement() {
if (ssa_temp_index_ == kReplacementMarker) {
return reinterpret_cast<Definition*>(temp_index_);
}
return this;
}
void SetReplacement(Definition* other) {
ASSERT(ssa_temp_index_ >= 0);
ASSERT(WasEliminated());
ssa_temp_index_ = kReplacementMarker;
temp_index_ = reinterpret_cast<intptr_t>(other);
}
virtual AliasIdentity Identity() const { return AliasIdentity::Unknown(); }
virtual void SetIdentity(AliasIdentity identity) { UNREACHABLE(); }
Definition* OriginalDefinition();
virtual Definition* AsDefinition() { return this; }
protected:
friend class RangeAnalysis;
friend class Value;
Range* range_;
CompileType* type_;
private:
intptr_t temp_index_;
intptr_t ssa_temp_index_;
Value* input_use_list_;
Value* env_use_list_;
Object* constant_value_;
DISALLOW_COPY_AND_ASSIGN(Definition);
};
// Change a value's definition after use lists have been computed.
inline void Value::BindTo(Definition* def) {
RemoveFromUseList();
set_definition(def);
def->AddInputUse(this);
}
inline void Value::BindToEnvironment(Definition* def) {
RemoveFromUseList();
set_definition(def);
def->AddEnvUse(this);
}
class PureDefinition : public Definition {
public:
explicit PureDefinition(intptr_t deopt_id) : Definition(deopt_id) {}
virtual bool AllowsCSE() const { return true; }
virtual bool HasUnknownSideEffects() const { return false; }
};
template <intptr_t N,
typename ThrowsTrait,
template <typename Impure, typename Pure> class CSETrait = NoCSE>
class TemplateDefinition : public CSETrait<Definition, PureDefinition>::Base {
public:
explicit TemplateDefinition(intptr_t deopt_id = DeoptId::kNone)
: CSETrait<Definition, PureDefinition>::Base(deopt_id), inputs_() {}
virtual intptr_t InputCount() const { return N; }
virtual Value* InputAt(intptr_t i) const { return inputs_[i]; }
virtual bool MayThrow() const { return ThrowsTrait::kCanThrow; }
protected:
EmbeddedArray<Value*, N> inputs_;
private:
friend class BranchInstr;
friend class IfThenElseInstr;
virtual void RawSetInputAt(intptr_t i, Value* value) { inputs_[i] = value; }
};
class PhiInstr : public Definition {
public:
PhiInstr(JoinEntryInstr* block, intptr_t num_inputs)
: block_(block),
inputs_(num_inputs),
representation_(kTagged),
reaching_defs_(NULL),
is_alive_(false),
is_receiver_(kUnknownReceiver) {
for (intptr_t i = 0; i < num_inputs; ++i) {
inputs_.Add(NULL);
}
}
// Get the block entry for that instruction.
virtual BlockEntryInstr* GetBlock() { return block(); }
JoinEntryInstr* block() const { return block_; }
virtual CompileType ComputeType() const;
virtual bool RecomputeType();
intptr_t InputCount() const { return inputs_.length(); }
Value* InputAt(intptr_t i) const { return inputs_[i]; }
virtual bool ComputeCanDeoptimize() const { return false; }
virtual bool HasUnknownSideEffects() const { return false; }
// Phi is alive if it reaches a non-environment use.
bool is_alive() const { return is_alive_; }
void mark_alive() { is_alive_ = true; }
void mark_dead() { is_alive_ = false; }
virtual Representation RequiredInputRepresentation(intptr_t i) const {
return representation_;
}
virtual Representation representation() const { return representation_; }
virtual void set_representation(Representation r) { representation_ = r; }
virtual intptr_t Hashcode() const {
UNREACHABLE();
return 0;
}
DECLARE_INSTRUCTION(Phi)
virtual void InferRange(RangeAnalysis* analysis, Range* range);
BitVector* reaching_defs() const { return reaching_defs_; }
void set_reaching_defs(BitVector* reaching_defs) {
reaching_defs_ = reaching_defs;
}
virtual bool MayThrow() const { return false; }
// A phi is redundant if all input operands are the same.
bool IsRedundant() const;
PRINT_TO_SUPPORT
enum ReceiverType { kUnknownReceiver = -1, kNotReceiver = 0, kReceiver = 1 };
ReceiverType is_receiver() const {
return static_cast<ReceiverType>(is_receiver_);
}
void set_is_receiver(ReceiverType is_receiver) { is_receiver_ = is_receiver; }
private:
// Direct access to inputs_ in order to resize it due to unreachable
// predecessors.
friend class ConstantPropagator;
void RawSetInputAt(intptr_t i, Value* value) { inputs_[i] = value; }
JoinEntryInstr* block_;
GrowableArray<Value*> inputs_;
Representation representation_;
BitVector* reaching_defs_;
bool is_alive_;
int8_t is_receiver_;
DISALLOW_COPY_AND_ASSIGN(PhiInstr);
};
class ParameterInstr : public Definition {
public:
ParameterInstr(intptr_t index,
BlockEntryInstr* block,
Register base_reg = FPREG)
: index_(index), base_reg_(base_reg), block_(block) {}
DECLARE_INSTRUCTION(Parameter)
intptr_t index() const { return index_; }
Register base_reg() const { return base_reg_; }
// Get the block entry for that instruction.
virtual BlockEntryInstr* GetBlock() { return block_; }
intptr_t InputCount() const { return 0; }
Value* InputAt(intptr_t i) const {
UNREACHABLE();
return NULL;
}
virtual bool ComputeCanDeoptimize() const { return false; }
virtual bool HasUnknownSideEffects() const { return false; }
virtual intptr_t Hashcode() const {
UNREACHABLE();
return 0;
}
virtual CompileType ComputeType() const;
virtual bool MayThrow() const { return false; }
PRINT_OPERANDS_TO_SUPPORT
private:
virtual void RawSetInputAt(intptr_t i, Value* value) { UNREACHABLE(); }
const intptr_t index_;
const Register base_reg_;
BlockEntryInstr* block_;
DISALLOW_COPY_AND_ASSIGN(ParameterInstr);
};
// Stores a tagged pointer to a slot accessible from a fixed register. It has
// the form:
//
// base_reg[index + #constant] = value
//
// Input 0: A tagged Smi [index]
// Input 1: A tagged pointer [value]
// offset: A signed constant offset which fits into 8 bits
//
// Currently this instruction uses pinpoints the register to be FP.
//
// This low-level instruction is non-inlinable since it makes assumptions about
// the frame. This is asserted via `inliner.cc::CalleeGraphValidator`.
class StoreIndexedUnsafeInstr : public TemplateInstruction<2, NoThrow> {
public:
StoreIndexedUnsafeInstr(Value* index, Value* value, intptr_t offset)
: offset_(offset) {
SetInputAt(kIndexPos, index);
SetInputAt(kValuePos, value);
}
enum { kIndexPos = 0, kValuePos = 1 };
DECLARE_INSTRUCTION(StoreIndexedUnsafe)
virtual Representation RequiredInputRepresentation(intptr_t index) const {
ASSERT(index == kIndexPos || index == kValuePos);
return kTagged;
}
virtual bool ComputeCanDeoptimize() const { return false; }
virtual bool HasUnknownSideEffects() const { return false; }
virtual bool AttributesEqual(Instruction* other) const {
return other->AsStoreIndexedUnsafe()->offset() == offset();
}
Value* index() const { return inputs_[kIndexPos]; }
Value* value() const { return inputs_[kValuePos]; }
Register base_reg() const { return FPREG; }
intptr_t offset() const { return offset_; }
PRINT_OPERANDS_TO_SUPPORT
private:
const intptr_t offset_;
DISALLOW_COPY_AND_ASSIGN(StoreIndexedUnsafeInstr);
};
// Loads a tagged pointer from slot accessable from a fixed register. It has
// the form:
//
// base_reg[index + #constant]
//
// Input 0: A tagged Smi [index]
// offset: A signed constant offset which fits into 8 bits
//
// Currently this instruction uses pinpoints the register to be FP.
//
// This lowlevel instruction is non-inlinable since it makes assumptons about
// the frame. This is asserted via `inliner.cc::CalleeGraphValidator`.
class LoadIndexedUnsafeInstr : public TemplateDefinition<1, NoThrow> {
public:
LoadIndexedUnsafeInstr(Value* index, intptr_t offset) : offset_(offset) {
SetInputAt(0, index);
}
DECLARE_INSTRUCTION(LoadIndexedUnsafe)
virtual Representation RequiredInputRepresentation(intptr_t index) const {
ASSERT(index == 0);
return kTagged;
}
virtual Representation representation() const { return kTagged; }
virtual bool ComputeCanDeoptimize() const { return false; }
virtual bool HasUnknownSideEffects() const { return false; }
virtual bool AttributesEqual(Instruction* other) const {
return other->AsLoadIndexedUnsafe()->offset() == offset();
}
Value* index() const { return InputAt(0); }
Register base_reg() const { return FPREG; }
intptr_t offset() const { return offset_; }
PRINT_OPERANDS_TO_SUPPORT
private:
const intptr_t offset_;
DISALLOW_COPY_AND_ASSIGN(LoadIndexedUnsafeInstr);
};
// Unwinds the current frame and tail calls a target.
//
// The return address saved by the original caller of this frame will be in it's
// usual location (stack or LR). The arguments descriptor supplied by the
// original caller will be put into ARGS_DESC_REG.
//
// This lowlevel instruction is non-inlinable since it makes assumptons about
// the frame. This is asserted via `inliner.cc::CalleeGraphValidator`.
class TailCallInstr : public Instruction {
public:
TailCallInstr(const Code& code, Value* arg_desc)
: code_(code), arg_desc_(NULL) {
SetInputAt(0, arg_desc);
}
DECLARE_INSTRUCTION(TailCall)
const Code& code() const { return code_; }
virtual intptr_t InputCount() const { return 1; }
virtual Value* InputAt(intptr_t i) const {
ASSERT(i == 0);
return arg_desc_;
}
virtual void RawSetInputAt(intptr_t i, Value* value) {
ASSERT(i == 0);
arg_desc_ = value;
}
// Two tailcalls can be canonicalized into one instruction if both have the
// same destination.
virtual bool AllowsCSE() const { return true; }
virtual bool AttributesEqual(Instruction* other) const {
return &other->AsTailCall()->code() == &code();
}
// Since no code after this instruction will be executed, there will be no
// side-effects for the following code.
virtual bool HasUnknownSideEffects() const { return false; }
virtual bool MayThrow() const { return true; }
virtual bool ComputeCanDeoptimize() const { return false; }
PRINT_OPERANDS_TO_SUPPORT
private:
const Code& code_;
Value* arg_desc_;
};
class PushArgumentInstr : public TemplateDefinition<1, NoThrow> {
public:
explicit PushArgumentInstr(Value* value) { SetInputAt(0, value); }
DECLARE_INSTRUCTION(PushArgument)
virtual CompileType ComputeType() const;
Value* value() const { return InputAt(0); }
virtual bool ComputeCanDeoptimize() const { return false; }
virtual bool HasUnknownSideEffects() const { return false; }
virtual TokenPosition token_pos() const {
return TokenPosition::kPushArgument;
}
PRINT_OPERANDS_TO_SUPPORT
private:
DISALLOW_COPY_AND_ASSIGN(PushArgumentInstr);
};
inline Definition* Instruction::ArgumentAt(intptr_t index) const {
return PushArgumentAt(index)->value()->definition();
}
class ReturnInstr : public TemplateInstruction<1, NoThrow> {
public:
ReturnInstr(TokenPosition token_pos, Value* value, intptr_t deopt_id)
: TemplateInstruction(deopt_id), token_pos_(token_pos) {
SetInputAt(0, value);
}
DECLARE_INSTRUCTION(Return)
virtual TokenPosition token_pos() const { return token_pos_; }
Value* value() const { return inputs_[0]; }
virtual bool CanBecomeDeoptimizationTarget() const {
// Return instruction might turn into a Goto instruction after inlining.
// Every Goto must have an environment.
return true;
}
virtual bool ComputeCanDeoptimize() const { return false; }
virtual bool HasUnknownSideEffects() const { return false; }
private:
const TokenPosition token_pos_;
DISALLOW_COPY_AND_ASSIGN(ReturnInstr);
};
class ThrowInstr : public TemplateInstruction<0, Throws> {
public:
explicit ThrowInstr(TokenPosition token_pos, intptr_t deopt_id)
: TemplateInstruction(deopt_id), token_pos_(token_pos) {}
DECLARE_INSTRUCTION(Throw)
virtual intptr_t ArgumentCount() const { return 1; }
virtual TokenPosition token_pos() const { return token_pos_; }
virtual bool ComputeCanDeoptimize() const { return true; }
virtual bool HasUnknownSideEffects() const { return false; }
private:
const TokenPosition token_pos_;
DISALLOW_COPY_AND_ASSIGN(ThrowInstr);
};
class ReThrowInstr : public TemplateInstruction<0, Throws> {
public:
// 'catch_try_index' can be kInvalidTryIndex if the
// rethrow has been artificially generated by the parser.
ReThrowInstr(TokenPosition token_pos,
intptr_t catch_try_index,
intptr_t deopt_id)
: TemplateInstruction(deopt_id),
token_pos_(token_pos),
catch_try_index_(catch_try_index) {}
DECLARE_INSTRUCTION(ReThrow)
virtual intptr_t ArgumentCount() const { return 2; }
virtual TokenPosition token_pos() const { return token_pos_; }
intptr_t catch_try_index() const { return catch_try_index_; }
virtual bool ComputeCanDeoptimize() const { return true; }
virtual bool HasUnknownSideEffects() const { return false; }
private:
const TokenPosition token_pos_;
const intptr_t catch_try_index_;
DISALLOW_COPY_AND_ASSIGN(ReThrowInstr);
};
class StopInstr : public TemplateInstruction<0, NoThrow> {
public:
explicit StopInstr(const char* message) : message_(message) {
ASSERT(message != NULL);
}
const char* message() const { return message_; }
DECLARE_INSTRUCTION(Stop);
virtual intptr_t ArgumentCount() const { return 0; }
virtual bool ComputeCanDeoptimize() const { return false; }
virtual bool HasUnknownSideEffects() const { return false; }
private:
const char* message_;
DISALLOW_COPY_AND_ASSIGN(StopInstr);
};
class GotoInstr : public TemplateInstruction<0, NoThrow> {
public:
explicit GotoInstr(JoinEntryInstr* entry, intptr_t deopt_id)
: TemplateInstruction(deopt_id),
block_(NULL),
successor_(entry),
edge_weight_(0.0),
parallel_move_(NULL) {}
DECLARE_INSTRUCTION(Goto)
BlockEntryInstr* block() const { return block_; }
void set_block(BlockEntryInstr* block) { block_ = block; }
JoinEntryInstr* successor() const { return successor_; }
void set_successor(JoinEntryInstr* successor) { successor_ = successor; }
virtual intptr_t SuccessorCount() const;
virtual BlockEntryInstr* SuccessorAt(intptr_t index) const;
double edge_weight() const { return edge_weight_; }
void set_edge_weight(double weight) { edge_weight_ = weight; }
void adjust_edge_weight(double scale_factor) { edge_weight_ *= scale_factor; }
virtual bool CanBecomeDeoptimizationTarget() const {
// Goto instruction can be used as a deoptimization target when LICM
// hoists instructions out of the loop.
return true;
}
virtual bool ComputeCanDeoptimize() const { return false; }
virtual bool HasUnknownSideEffects() const { return false; }
ParallelMoveInstr* parallel_move() const { return parallel_move_; }
bool HasParallelMove() const { return parallel_move_ != NULL; }
bool HasNonRedundantParallelMove() const {
return HasParallelMove() && !parallel_move()->IsRedundant();
}
ParallelMoveInstr* GetParallelMove() {
if (parallel_move_ == NULL) {
parallel_move_ = new ParallelMoveInstr();
}
return parallel_move_;
}
virtual TokenPosition token_pos() const {
return TokenPosition::kControlFlow;
}
PRINT_TO_SUPPORT
private:
BlockEntryInstr* block_;
JoinEntryInstr* successor_;
double edge_weight_;
// Parallel move that will be used by linear scan register allocator to
// connect live ranges at the end of the block and resolve phis.
ParallelMoveInstr* parallel_move_;
};
// IndirectGotoInstr represents a dynamically computed jump. Only
// IndirectEntryInstr targets are valid targets of an indirect goto. The
// concrete target to jump to is given as a parameter to the indirect goto.
//
// In order to preserve split-edge form, an indirect goto does not itself point
// to its targets. Instead, for each possible target, the successors_ field
// will contain an ordinary goto instruction that jumps to the target.
// TODO(zerny): Implement direct support instead of embedding gotos.
//
// Byte offsets of all possible targets are stored in the offsets_ array. The
// desired offset is looked up while the generated code is executing, and passed
// to IndirectGoto as an input.
class IndirectGotoInstr : public TemplateInstruction<1, NoThrow> {
public:
IndirectGotoInstr(TypedData* offsets, Value* offset_from_start)
: offsets_(*offsets) {
SetInputAt(0, offset_from_start);
}
DECLARE_INSTRUCTION(IndirectGoto)
virtual Representation RequiredInputRepresentation(intptr_t idx) const {
ASSERT(idx == 0);
return kNoRepresentation;
}
virtual intptr_t ArgumentCount() const { return 0; }
void AddSuccessor(TargetEntryInstr* successor) {
ASSERT(successor->next()->IsGoto());
ASSERT(successor->next()->AsGoto()->successor()->IsIndirectEntry());
successors_.Add(successor);
}
virtual intptr_t SuccessorCount() const { return successors_.length(); }
virtual TargetEntryInstr* SuccessorAt(intptr_t index) const {
ASSERT(index < SuccessorCount());
return successors_[index];
}
virtual bool ComputeCanDeoptimize() const { return false; }
virtual bool CanBecomeDeoptimizationTarget() const { return false; }
virtual bool HasUnknownSideEffects() const { return false; }
Value* offset() const { return inputs_[0]; }
void ComputeOffsetTable();
PRINT_TO_SUPPORT
private:
GrowableArray<TargetEntryInstr*> successors_;
TypedData& offsets_;
};
class ComparisonInstr : public Definition {
public:
Value* left() const { return InputAt(0); }
Value* right() const { return InputAt(1); }
virtual TokenPosition token_pos() const { return token_pos_; }
Token::Kind kind() const { return kind_; }
virtual ComparisonInstr* CopyWithNewOperands(Value* left, Value* right) = 0;
// Emits instructions to do the comparison and branch to the true or false
// label depending on the result. This implementation will call
// EmitComparisonCode and then generate the branch instructions afterwards.
virtual void EmitBranchCode(FlowGraphCompiler* compiler, BranchInstr* branch);
// Used by EmitBranchCode and EmitNativeCode depending on whether the boolean
// is to be turned into branches or instantiated. May return a valid
// condition in which case the caller is expected to emit a branch to the
// true label based on that condition (or a branch to the false label on the
// opposite condition). May also branch directly to the labels.
virtual Condition EmitComparisonCode(FlowGraphCompiler* compiler,
BranchLabels labels) = 0;
#if defined(TARGET_ARCH_DBC)
// On the DBC platform EmitNativeCode needs to know ahead of time what
// 'Condition' will be returned by EmitComparisonCode. This call must return
// the same result as EmitComparisonCode, but should not emit any
// instructions.
virtual Condition GetNextInstructionCondition(FlowGraphCompiler* compiler,
BranchLabels labels) = 0;
#endif
// Emits code that generates 'true' or 'false', depending on the comparison.
// This implementation will call EmitComparisonCode. If EmitComparisonCode
// does not use the labels (merely returning a condition) then EmitNativeCode
// may be able to use the condition to avoid a branch.
virtual void EmitNativeCode(FlowGraphCompiler* compiler);
void SetDeoptId(const Instruction& instr) { CopyDeoptIdFrom(instr); }
// Operation class id is computed from collected ICData.
void set_operation_cid(intptr_t value) { operation_cid_ = value; }
intptr_t operation_cid() const { return operation_cid_; }
virtual void NegateComparison() { kind_ = Token::NegateComparison(kind_); }
virtual bool CanBecomeDeoptimizationTarget() const { return true; }
virtual intptr_t DeoptimizationTarget() const { return GetDeoptId(); }
virtual bool AttributesEqual(Instruction* other) const {
ComparisonInstr* other_comparison = other->AsComparison();
return kind() == other_comparison->kind() &&
(operation_cid() == other_comparison->operation_cid());
}
DEFINE_INSTRUCTION_TYPE_CHECK(Comparison)
protected:
ComparisonInstr(TokenPosition token_pos,
Token::Kind kind,
intptr_t deopt_id = DeoptId::kNone)
: Definition(deopt_id),
token_pos_(token_pos),
kind_(kind),
operation_cid_(kIllegalCid) {}
private:
const TokenPosition token_pos_;
Token::Kind kind_;
intptr_t operation_cid_; // Set by optimizer.