summaryrefslogtreecommitdiff
path: root/compiler/optimizing/nodes.h
diff options
context:
space:
mode:
Diffstat (limited to 'compiler/optimizing/nodes.h')
-rw-r--r--compiler/optimizing/nodes.h200
1 files changed, 187 insertions, 13 deletions
diff --git a/compiler/optimizing/nodes.h b/compiler/optimizing/nodes.h
index ed6dd939de..be6b355d22 100644
--- a/compiler/optimizing/nodes.h
+++ b/compiler/optimizing/nodes.h
@@ -38,6 +38,7 @@ class LocationSummary;
static const int kDefaultNumberOfBlocks = 8;
static const int kDefaultNumberOfSuccessors = 2;
static const int kDefaultNumberOfPredecessors = 2;
+static const int kDefaultNumberOfDominatedBlocks = 1;
static const int kDefaultNumberOfBackEdges = 1;
enum IfCondition {
@@ -56,6 +57,12 @@ class HInstructionList {
void AddInstruction(HInstruction* instruction);
void RemoveInstruction(HInstruction* instruction);
+ // Return true if `instruction1` is found before `instruction2` in
+ // this instruction list and false otherwise. Abort if none
+ // of these instructions is found.
+ bool FoundBefore(const HInstruction* instruction1,
+ const HInstruction* instruction2) const;
+
private:
HInstruction* first_instruction_;
HInstruction* last_instruction_;
@@ -192,7 +199,8 @@ class HLoopInformation : public ArenaObject {
HLoopInformation(HBasicBlock* header, HGraph* graph)
: header_(header),
back_edges_(graph->GetArena(), kDefaultNumberOfBackEdges),
- blocks_(graph->GetArena(), graph->GetBlocks().Size(), false) {}
+ // Make bit vector growable, as the number of blocks may change.
+ blocks_(graph->GetArena(), graph->GetBlocks().Size(), true) {}
HBasicBlock* GetHeader() const {
return header_;
@@ -265,6 +273,7 @@ class HBasicBlock : public ArenaObject {
successors_(graph->GetArena(), kDefaultNumberOfSuccessors),
loop_information_(nullptr),
dominator_(nullptr),
+ dominated_blocks_(graph->GetArena(), kDefaultNumberOfDominatedBlocks),
block_id_(-1),
lifetime_start_(kNoLifetime),
lifetime_end_(kNoLifetime) {}
@@ -277,6 +286,10 @@ class HBasicBlock : public ArenaObject {
return successors_;
}
+ const GrowableArray<HBasicBlock*>& GetDominatedBlocks() const {
+ return dominated_blocks_;
+ }
+
void AddBackEdge(HBasicBlock* back_edge) {
if (loop_information_ == nullptr) {
loop_information_ = new (graph_->GetArena()) HLoopInformation(this, graph_);
@@ -292,6 +305,7 @@ class HBasicBlock : public ArenaObject {
HBasicBlock* GetDominator() const { return dominator_; }
void SetDominator(HBasicBlock* dominator) { dominator_ = dominator; }
+ void AddDominatedBlock(HBasicBlock* block) { dominated_blocks_.Add(block); }
int NumberOfBackEdges() const {
return loop_information_ == nullptr
@@ -331,6 +345,13 @@ class HBasicBlock : public ArenaObject {
block->successors_.Add(this);
}
+ void SwapPredecessors() {
+ DCHECK_EQ(predecessors_.Size(), 2u);
+ HBasicBlock* temp = predecessors_.Get(0);
+ predecessors_.Put(0, predecessors_.Get(1));
+ predecessors_.Put(1, temp);
+ }
+
size_t GetPredecessorIndexOf(HBasicBlock* predecessor) {
for (size_t i = 0, e = predecessors_.Size(); i < e; ++i) {
if (predecessors_.Get(i) == predecessor) {
@@ -352,6 +373,9 @@ class HBasicBlock : public ArenaObject {
void AddInstruction(HInstruction* instruction);
void RemoveInstruction(HInstruction* instruction);
void InsertInstructionBefore(HInstruction* instruction, HInstruction* cursor);
+ // Replace instruction `initial` with `replacement` within this block.
+ void ReplaceAndRemoveInstructionWith(HInstruction* initial,
+ HInstruction* replacement);
void AddPhi(HPhi* phi);
void RemovePhi(HPhi* phi);
@@ -359,6 +383,12 @@ class HBasicBlock : public ArenaObject {
return (loop_information_ != nullptr) && (loop_information_->GetHeader() == this);
}
+ bool IsLoopPreHeaderFirstPredecessor() const {
+ DCHECK(IsLoopHeader());
+ DCHECK(!GetPredecessors().IsEmpty());
+ return GetPredecessors().Get(0) == GetLoopInformation()->GetPreHeader();
+ }
+
HLoopInformation* GetLoopInformation() const {
return loop_information_;
}
@@ -401,6 +431,7 @@ class HBasicBlock : public ArenaObject {
HInstructionList phis_;
HLoopInformation* loop_information_;
HBasicBlock* dominator_;
+ GrowableArray<HBasicBlock*> dominated_blocks_;
int block_id_;
size_t lifetime_start_;
size_t lifetime_end_;
@@ -422,6 +453,7 @@ class HBasicBlock : public ArenaObject {
M(If) \
M(IntConstant) \
M(InvokeStatic) \
+ M(InvokeVirtual) \
M(LoadLocal) \
M(Local) \
M(LongConstant) \
@@ -447,19 +479,22 @@ class HBasicBlock : public ArenaObject {
#define FOR_EACH_INSTRUCTION(M) \
FOR_EACH_CONCRETE_INSTRUCTION(M) \
- M(Constant)
+ M(Constant) \
+ M(BinaryOperation)
#define FORWARD_DECLARATION(type) class H##type;
FOR_EACH_INSTRUCTION(FORWARD_DECLARATION)
#undef FORWARD_DECLARATION
-#define DECLARE_INSTRUCTION(type) \
- virtual const char* DebugName() const { return #type; } \
- virtual H##type* As##type() { return this; } \
- virtual bool InstructionTypeEquals(HInstruction* other) const { \
- return other->Is##type(); \
- } \
- virtual void Accept(HGraphVisitor* visitor) \
+#define DECLARE_INSTRUCTION(type) \
+ virtual InstructionKind GetKind() const { return k##type; } \
+ virtual const char* DebugName() const { return #type; } \
+ virtual const H##type* As##type() const OVERRIDE { return this; } \
+ virtual H##type* As##type() OVERRIDE { return this; } \
+ virtual bool InstructionTypeEquals(HInstruction* other) const { \
+ return other->Is##type(); \
+ } \
+ virtual void Accept(HGraphVisitor* visitor)
template <typename T>
class HUseListNode : public ArenaObject {
@@ -484,6 +519,8 @@ class HUseListNode : public ArenaObject {
// Represents the side effects an instruction may have.
class SideEffects : public ValueObject {
public:
+ SideEffects() : flags_(0) {}
+
static SideEffects None() {
return SideEffects(0);
}
@@ -501,6 +538,31 @@ class SideEffects : public ValueObject {
return SideEffects(((1 << count) - 1) << kFlagChangesCount);
}
+ SideEffects Union(SideEffects other) const {
+ return SideEffects(flags_ | other.flags_);
+ }
+
+ bool HasSideEffects() const {
+ size_t all_bits_set = (1 << kFlagChangesCount) - 1;
+ return (flags_ & all_bits_set) != 0;
+ }
+
+ bool HasAllSideEffects() const {
+ size_t all_bits_set = (1 << kFlagChangesCount) - 1;
+ return all_bits_set == (flags_ & all_bits_set);
+ }
+
+ bool DependsOn(SideEffects other) const {
+ size_t depends_flags = other.ComputeDependsFlags();
+ return (flags_ & depends_flags) != 0;
+ }
+
+ bool HasDependencies() const {
+ int count = kFlagDependsOnCount - kFlagChangesCount;
+ size_t all_bits_set = (1 << count) - 1;
+ return ((flags_ >> kFlagChangesCount) & all_bits_set) != 0;
+ }
+
private:
static constexpr int kFlagChangesSomething = 0;
static constexpr int kFlagChangesCount = kFlagChangesSomething + 1;
@@ -508,10 +570,13 @@ class SideEffects : public ValueObject {
static constexpr int kFlagDependsOnSomething = kFlagChangesCount;
static constexpr int kFlagDependsOnCount = kFlagDependsOnSomething + 1;
- private:
explicit SideEffects(size_t flags) : flags_(flags) {}
- const size_t flags_;
+ size_t ComputeDependsFlags() const {
+ return flags_ << kFlagChangesCount;
+ }
+
+ size_t flags_;
};
class HInstruction : public ArenaObject {
@@ -532,6 +597,12 @@ class HInstruction : public ArenaObject {
virtual ~HInstruction() {}
+#define DECLARE_KIND(type) k##type,
+ enum InstructionKind {
+ FOR_EACH_INSTRUCTION(DECLARE_KIND)
+ };
+#undef DECLARE_KIND
+
HInstruction* GetNext() const { return next_; }
HInstruction* GetPrevious() const { return previous_; }
@@ -541,7 +612,7 @@ class HInstruction : public ArenaObject {
bool IsInLoop() const { return block_->IsInLoop(); }
bool IsLoopHeaderPhi() { return IsPhi() && block_->IsLoopHeader(); }
- virtual size_t InputCount() const = 0;
+ virtual size_t InputCount() const = 0;
virtual HInstruction* InputAt(size_t i) const = 0;
virtual void Accept(HGraphVisitor* visitor) = 0;
@@ -552,17 +623,20 @@ class HInstruction : public ArenaObject {
virtual bool NeedsEnvironment() const { return false; }
virtual bool IsControlFlow() const { return false; }
+ bool HasSideEffects() const { return side_effects_.HasSideEffects(); }
void AddUseAt(HInstruction* user, size_t index) {
uses_ = new (block_->GetGraph()->GetArena()) HUseListNode<HInstruction>(user, index, uses_);
}
void AddEnvUseAt(HEnvironment* user, size_t index) {
+ DCHECK(user != nullptr);
env_uses_ = new (block_->GetGraph()->GetArena()) HUseListNode<HEnvironment>(
user, index, env_uses_);
}
void RemoveUser(HInstruction* user, size_t index);
+ void RemoveEnvironmentUser(HEnvironment* user, size_t index);
HUseListNode<HInstruction>* GetUses() const { return uses_; }
HUseListNode<HEnvironment>* GetEnvUses() const { return env_uses_; }
@@ -581,6 +655,10 @@ class HInstruction : public ArenaObject {
return result;
}
+ // Does this instruction dominate `other_instruction`? Aborts if
+ // this instruction and `other_instruction` are both phis.
+ bool Dominates(HInstruction* other_instruction) const;
+
int GetId() const { return id_; }
void SetId(int id) { id_ = id; }
@@ -606,7 +684,8 @@ class HInstruction : public ArenaObject {
}
#define INSTRUCTION_TYPE_CHECK(type) \
- bool Is##type() { return (As##type() != nullptr); } \
+ bool Is##type() const { return (As##type() != nullptr); } \
+ virtual const H##type* As##type() const { return nullptr; } \
virtual H##type* As##type() { return nullptr; }
FOR_EACH_INSTRUCTION(INSTRUCTION_TYPE_CHECK)
@@ -628,6 +707,18 @@ class HInstruction : public ArenaObject {
// 2) Their inputs are identical.
bool Equals(HInstruction* other) const;
+ virtual InstructionKind GetKind() const = 0;
+
+ virtual size_t ComputeHashCode() const {
+ size_t result = GetKind();
+ for (size_t i = 0, e = InputCount(); i < e; ++i) {
+ result = (result * 31) + InputAt(i)->GetId();
+ }
+ return result;
+ }
+
+ SideEffects GetSideEffects() const { return side_effects_; }
+
size_t GetLifetimePosition() const { return lifetime_position_; }
void SetLifetimePosition(size_t position) { lifetime_position_ = position; }
LiveInterval* GetLiveInterval() const { return live_interval_; }
@@ -983,6 +1074,17 @@ class HBinaryOperation : public HExpression<2> {
virtual bool CanBeMoved() const { return true; }
virtual bool InstructionDataEquals(HInstruction* other) const { return true; }
+ // Try to statically evaluate `operation` and return an HConstant
+ // containing the result of this evaluation. If `operation` cannot
+ // be evaluated as a constant, return nullptr.
+ HConstant* TryStaticEvaluation(ArenaAllocator* allocator) const;
+
+ // Apply this operation to `x` and `y`.
+ virtual int32_t Evaluate(int32_t x, int32_t y) const = 0;
+ virtual int64_t Evaluate(int64_t x, int64_t y) const = 0;
+
+ DECLARE_INSTRUCTION(BinaryOperation);
+
private:
DISALLOW_COPY_AND_ASSIGN(HBinaryOperation);
};
@@ -993,8 +1095,15 @@ class HCondition : public HBinaryOperation {
: HBinaryOperation(Primitive::kPrimBoolean, first, second) {}
virtual bool IsCommutative() { return true; }
+
+ // For register allocation purposes, returns whether this instruction needs to be
+ // materialized (that is, not just be in the processor flags).
bool NeedsMaterialization() const;
+ // For code generation purposes, returns whether this instruction is just before
+ // `if_`, and disregard moves in between.
+ bool IsBeforeWhenDisregardMoves(HIf* if_) const;
+
DECLARE_INSTRUCTION(Condition);
virtual IfCondition GetCondition() const = 0;
@@ -1009,6 +1118,9 @@ class HEqual : public HCondition {
HEqual(HInstruction* first, HInstruction* second)
: HCondition(first, second) {}
+ virtual int32_t Evaluate(int32_t x, int32_t y) const { return x == y; }
+ virtual int64_t Evaluate(int64_t x, int64_t y) const { return x == y; }
+
DECLARE_INSTRUCTION(Equal);
virtual IfCondition GetCondition() const {
@@ -1024,6 +1136,9 @@ class HNotEqual : public HCondition {
HNotEqual(HInstruction* first, HInstruction* second)
: HCondition(first, second) {}
+ virtual int32_t Evaluate(int32_t x, int32_t y) const { return x != y; }
+ virtual int64_t Evaluate(int64_t x, int64_t y) const { return x != y; }
+
DECLARE_INSTRUCTION(NotEqual);
virtual IfCondition GetCondition() const {
@@ -1039,6 +1154,9 @@ class HLessThan : public HCondition {
HLessThan(HInstruction* first, HInstruction* second)
: HCondition(first, second) {}
+ virtual int32_t Evaluate(int32_t x, int32_t y) const { return x < y; }
+ virtual int64_t Evaluate(int64_t x, int64_t y) const { return x < y; }
+
DECLARE_INSTRUCTION(LessThan);
virtual IfCondition GetCondition() const {
@@ -1054,6 +1172,9 @@ class HLessThanOrEqual : public HCondition {
HLessThanOrEqual(HInstruction* first, HInstruction* second)
: HCondition(first, second) {}
+ virtual int32_t Evaluate(int32_t x, int32_t y) const { return x <= y; }
+ virtual int64_t Evaluate(int64_t x, int64_t y) const { return x <= y; }
+
DECLARE_INSTRUCTION(LessThanOrEqual);
virtual IfCondition GetCondition() const {
@@ -1069,6 +1190,9 @@ class HGreaterThan : public HCondition {
HGreaterThan(HInstruction* first, HInstruction* second)
: HCondition(first, second) {}
+ virtual int32_t Evaluate(int32_t x, int32_t y) const { return x > y; }
+ virtual int64_t Evaluate(int64_t x, int64_t y) const { return x > y; }
+
DECLARE_INSTRUCTION(GreaterThan);
virtual IfCondition GetCondition() const {
@@ -1084,6 +1208,9 @@ class HGreaterThanOrEqual : public HCondition {
HGreaterThanOrEqual(HInstruction* first, HInstruction* second)
: HCondition(first, second) {}
+ virtual int32_t Evaluate(int32_t x, int32_t y) const { return x >= y; }
+ virtual int64_t Evaluate(int64_t x, int64_t y) const { return x >= y; }
+
DECLARE_INSTRUCTION(GreaterThanOrEqual);
virtual IfCondition GetCondition() const {
@@ -1105,6 +1232,19 @@ class HCompare : public HBinaryOperation {
DCHECK_EQ(type, second->GetType());
}
+ virtual int32_t Evaluate(int32_t x, int32_t y) const {
+ return
+ x == y ? 0 :
+ x > y ? 1 :
+ -1;
+ }
+ virtual int64_t Evaluate(int64_t x, int64_t y) const {
+ return
+ x == y ? 0 :
+ x > y ? 1 :
+ -1;
+ }
+
DECLARE_INSTRUCTION(Compare);
private:
@@ -1185,6 +1325,8 @@ class HIntConstant : public HConstant {
return other->AsIntConstant()->value_ == value_;
}
+ virtual size_t ComputeHashCode() const { return GetValue(); }
+
DECLARE_INSTRUCTION(IntConstant);
private:
@@ -1203,6 +1345,8 @@ class HLongConstant : public HConstant {
return other->AsLongConstant()->value_ == value_;
}
+ virtual size_t ComputeHashCode() const { return static_cast<size_t>(GetValue()); }
+
DECLARE_INSTRUCTION(LongConstant);
private:
@@ -1272,6 +1416,26 @@ class HInvokeStatic : public HInvoke {
DISALLOW_COPY_AND_ASSIGN(HInvokeStatic);
};
+class HInvokeVirtual : public HInvoke {
+ public:
+ HInvokeVirtual(ArenaAllocator* arena,
+ uint32_t number_of_arguments,
+ Primitive::Type return_type,
+ uint32_t dex_pc,
+ uint32_t vtable_index)
+ : HInvoke(arena, number_of_arguments, return_type, dex_pc),
+ vtable_index_(vtable_index) {}
+
+ uint32_t GetVTableIndex() const { return vtable_index_; }
+
+ DECLARE_INSTRUCTION(InvokeVirtual);
+
+ private:
+ const uint32_t vtable_index_;
+
+ DISALLOW_COPY_AND_ASSIGN(HInvokeVirtual);
+};
+
class HNewInstance : public HExpression<0> {
public:
HNewInstance(uint32_t dex_pc, uint16_t type_index)
@@ -1301,6 +1465,9 @@ class HAdd : public HBinaryOperation {
virtual bool IsCommutative() { return true; }
+ virtual int32_t Evaluate(int32_t x, int32_t y) const { return x + y; }
+ virtual int64_t Evaluate(int64_t x, int64_t y) const { return x + y; }
+
DECLARE_INSTRUCTION(Add);
private:
@@ -1314,6 +1481,9 @@ class HSub : public HBinaryOperation {
virtual bool IsCommutative() { return false; }
+ virtual int32_t Evaluate(int32_t x, int32_t y) const { return x + y; }
+ virtual int64_t Evaluate(int64_t x, int64_t y) const { return x + y; }
+
DECLARE_INSTRUCTION(Sub);
private:
@@ -1446,6 +1616,10 @@ class HInstanceFieldGet : public HExpression<1> {
return other_offset == GetFieldOffset().SizeValue();
}
+ virtual size_t ComputeHashCode() const {
+ return (HInstruction::ComputeHashCode() << 7) | GetFieldOffset().SizeValue();
+ }
+
MemberOffset GetFieldOffset() const { return field_info_.GetFieldOffset(); }
Primitive::Type GetFieldType() const { return field_info_.GetFieldType(); }
generated by cgit v1.2.3-59-g8ed1b (git 2.39.0) at 2025-10-24 23:18:09 +0000