Add (simple) side effects flags and equality methods on nodes.
This is in preparation of doing GVN and LICM.
Change-Id: I43050ff846755f9387a62b893d548ecdb54e7e95
diff --git a/compiler/optimizing/nodes.cc b/compiler/optimizing/nodes.cc
index f07029d..207c605 100644
--- a/compiler/optimizing/nodes.cc
+++ b/compiler/optimizing/nodes.cc
@@ -468,4 +468,16 @@
return false;
}
+bool HInstruction::Equals(HInstruction* other) const {
+ if (!InstructionTypeEquals(other)) return false;
+ if (!InstructionDataEquals(other)) return false;
+ if (GetType() != other->GetType()) return false;
+ if (InputCount() != other->InputCount()) return false;
+
+ for (size_t i = 0, e = InputCount(); i < e; ++i) {
+ if (InputAt(i) != other->InputAt(i)) return false;
+ }
+ return true;
+}
+
} // namespace art
diff --git a/compiler/optimizing/nodes.h b/compiler/optimizing/nodes.h
index ea0cacc..9018fee0 100644
--- a/compiler/optimizing/nodes.h
+++ b/compiler/optimizing/nodes.h
@@ -455,6 +455,9 @@
#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) \
template <typename T>
@@ -477,9 +480,42 @@
DISALLOW_COPY_AND_ASSIGN(HUseListNode);
};
+// Represents the side effects an instruction may have.
+class SideEffects : public ValueObject {
+ public:
+ static SideEffects None() {
+ return SideEffects(0);
+ }
+
+ static SideEffects All() {
+ return SideEffects(ChangesSomething().flags_ | DependsOnSomething().flags_);
+ }
+
+ static SideEffects ChangesSomething() {
+ return SideEffects((1 << kFlagChangesCount) - 1);
+ }
+
+ static SideEffects DependsOnSomething() {
+ int count = kFlagDependsOnCount - kFlagChangesCount;
+ return SideEffects(((1 << count) - 1) << kFlagChangesCount);
+ }
+
+ private:
+ static constexpr int kFlagChangesSomething = 0;
+ static constexpr int kFlagChangesCount = kFlagChangesSomething + 1;
+
+ static constexpr int kFlagDependsOnSomething = kFlagChangesCount;
+ static constexpr int kFlagDependsOnCount = kFlagDependsOnSomething + 1;
+
+ private:
+ explicit SideEffects(size_t flags) : flags_(flags) {}
+
+ const size_t flags_;
+};
+
class HInstruction : public ArenaObject {
public:
- HInstruction()
+ explicit HInstruction(SideEffects side_effects)
: previous_(nullptr),
next_(nullptr),
block_(nullptr),
@@ -490,7 +526,8 @@
environment_(nullptr),
locations_(nullptr),
live_interval_(nullptr),
- lifetime_position_(kNoLifetime) {}
+ lifetime_position_(kNoLifetime),
+ side_effects_(side_effects) {}
virtual ~HInstruction() {}
@@ -574,6 +611,22 @@
FOR_EACH_INSTRUCTION(INSTRUCTION_TYPE_CHECK)
#undef INSTRUCTION_TYPE_CHECK
+ // Returns whether the instruction can be moved within the graph.
+ virtual bool CanBeMoved() const { return false; }
+
+ // Returns whether the two instructions are of the same kind.
+ virtual bool InstructionTypeEquals(HInstruction* other) const { return false; }
+
+ // Returns whether any data encoded in the two instructions is equal.
+ // This method does not look at the inputs. Both instructions must be
+ // of the same type, otherwise the method has undefined behavior.
+ virtual bool InstructionDataEquals(HInstruction* other) const { return false; }
+
+ // Returns whether two instructions are equal, that is:
+ // 1) They have the same type and contain the same data,
+ // 2) Their inputs are identical.
+ bool Equals(HInstruction* other) const;
+
size_t GetLifetimePosition() const { return lifetime_position_; }
void SetLifetimePosition(size_t position) { lifetime_position_ = position; }
LiveInterval* GetLiveInterval() const { return live_interval_; }
@@ -613,6 +666,8 @@
// order of blocks where this instruction's live interval start.
size_t lifetime_position_;
+ const SideEffects side_effects_;
+
friend class HBasicBlock;
friend class HInstructionList;
@@ -789,7 +844,8 @@
template<intptr_t N>
class HTemplateInstruction: public HInstruction {
public:
- HTemplateInstruction<N>() : inputs_() {}
+ HTemplateInstruction<N>(SideEffects side_effects)
+ : HInstruction(side_effects), inputs_() {}
virtual ~HTemplateInstruction() {}
virtual size_t InputCount() const { return N; }
@@ -807,9 +863,10 @@
};
template<intptr_t N>
-class HExpression: public HTemplateInstruction<N> {
+class HExpression : public HTemplateInstruction<N> {
public:
- explicit HExpression<N>(Primitive::Type type) : type_(type) {}
+ HExpression<N>(Primitive::Type type, SideEffects side_effects)
+ : HTemplateInstruction<N>(side_effects), type_(type) {}
virtual ~HExpression() {}
virtual Primitive::Type GetType() const { return type_; }
@@ -822,7 +879,7 @@
// instruction that branches to the exit block.
class HReturnVoid : public HTemplateInstruction<0> {
public:
- HReturnVoid() {}
+ HReturnVoid() : HTemplateInstruction(SideEffects::None()) {}
virtual bool IsControlFlow() const { return true; }
@@ -836,7 +893,7 @@
// instruction that branches to the exit block.
class HReturn : public HTemplateInstruction<1> {
public:
- explicit HReturn(HInstruction* value) {
+ explicit HReturn(HInstruction* value) : HTemplateInstruction(SideEffects::None()) {
SetRawInputAt(0, value);
}
@@ -853,7 +910,7 @@
// exit block.
class HExit : public HTemplateInstruction<0> {
public:
- HExit() {}
+ HExit() : HTemplateInstruction(SideEffects::None()) {}
virtual bool IsControlFlow() const { return true; }
@@ -866,14 +923,14 @@
// Jumps from one block to another.
class HGoto : public HTemplateInstruction<0> {
public:
- HGoto() {}
+ HGoto() : HTemplateInstruction(SideEffects::None()) {}
+
+ virtual bool IsControlFlow() const { return true; }
HBasicBlock* GetSuccessor() const {
return GetBlock()->GetSuccessors().Get(0);
}
- virtual bool IsControlFlow() const { return true; }
-
DECLARE_INSTRUCTION(Goto);
private:
@@ -885,10 +942,12 @@
// two successors.
class HIf : public HTemplateInstruction<1> {
public:
- explicit HIf(HInstruction* input) {
+ explicit HIf(HInstruction* input) : HTemplateInstruction(SideEffects::None()) {
SetRawInputAt(0, input);
}
+ virtual bool IsControlFlow() const { return true; }
+
HBasicBlock* IfTrueSuccessor() const {
return GetBlock()->GetSuccessors().Get(0);
}
@@ -897,8 +956,6 @@
return GetBlock()->GetSuccessors().Get(1);
}
- virtual bool IsControlFlow() const { return true; }
-
DECLARE_INSTRUCTION(If);
virtual bool IsIfInstruction() const { return true; }
@@ -911,7 +968,7 @@
public:
HBinaryOperation(Primitive::Type result_type,
HInstruction* left,
- HInstruction* right) : HExpression(result_type) {
+ HInstruction* right) : HExpression(result_type, SideEffects::None()) {
SetRawInputAt(0, left);
SetRawInputAt(1, right);
}
@@ -922,6 +979,9 @@
virtual bool IsCommutative() { return false; }
+ virtual bool CanBeMoved() const { return true; }
+ virtual bool InstructionDataEquals(HInstruction* other) const { return true; }
+
private:
DISALLOW_COPY_AND_ASSIGN(HBinaryOperation);
};
@@ -1053,7 +1113,8 @@
// A local in the graph. Corresponds to a Dex register.
class HLocal : public HTemplateInstruction<0> {
public:
- explicit HLocal(uint16_t reg_number) : reg_number_(reg_number) {}
+ explicit HLocal(uint16_t reg_number)
+ : HTemplateInstruction(SideEffects::None()), reg_number_(reg_number) {}
DECLARE_INSTRUCTION(Local);
@@ -1069,7 +1130,8 @@
// Load a given local. The local is an input of this instruction.
class HLoadLocal : public HExpression<1> {
public:
- explicit HLoadLocal(HLocal* local, Primitive::Type type) : HExpression(type) {
+ explicit HLoadLocal(HLocal* local, Primitive::Type type)
+ : HExpression(type, SideEffects::None()) {
SetRawInputAt(0, local);
}
@@ -1085,7 +1147,7 @@
// and the local.
class HStoreLocal : public HTemplateInstruction<2> {
public:
- HStoreLocal(HLocal* local, HInstruction* value) {
+ HStoreLocal(HLocal* local, HInstruction* value) : HTemplateInstruction(SideEffects::None()) {
SetRawInputAt(0, local);
SetRawInputAt(1, value);
}
@@ -1100,7 +1162,9 @@
class HConstant : public HExpression<0> {
public:
- explicit HConstant(Primitive::Type type) : HExpression(type) {}
+ explicit HConstant(Primitive::Type type) : HExpression(type, SideEffects::None()) {}
+
+ virtual bool CanBeMoved() const { return true; }
DECLARE_INSTRUCTION(Constant);
@@ -1116,6 +1180,10 @@
int32_t GetValue() const { return value_; }
+ virtual bool InstructionDataEquals(HInstruction* other) const {
+ return other->AsIntConstant()->value_ == value_;
+ }
+
DECLARE_INSTRUCTION(IntConstant);
private:
@@ -1130,6 +1198,10 @@
int64_t GetValue() const { return value_; }
+ virtual bool InstructionDataEquals(HInstruction* other) const {
+ return other->AsLongConstant()->value_ == value_;
+ }
+
DECLARE_INSTRUCTION(LongConstant);
private:
@@ -1144,7 +1216,8 @@
uint32_t number_of_arguments,
Primitive::Type return_type,
uint32_t dex_pc)
- : inputs_(arena, number_of_arguments),
+ : HInstruction(SideEffects::All()),
+ inputs_(arena, number_of_arguments),
return_type_(return_type),
dex_pc_(dex_pc) {
inputs_.SetSize(number_of_arguments);
@@ -1200,8 +1273,10 @@
class HNewInstance : public HExpression<0> {
public:
- HNewInstance(uint32_t dex_pc, uint16_t type_index) : HExpression(Primitive::kPrimNot),
- dex_pc_(dex_pc), type_index_(type_index) {}
+ HNewInstance(uint32_t dex_pc, uint16_t type_index)
+ : HExpression(Primitive::kPrimNot, SideEffects::None()),
+ dex_pc_(dex_pc),
+ type_index_(type_index) {}
uint32_t GetDexPc() const { return dex_pc_; }
uint16_t GetTypeIndex() const { return type_index_; }
@@ -1249,7 +1324,7 @@
class HParameterValue : public HExpression<0> {
public:
HParameterValue(uint8_t index, Primitive::Type parameter_type)
- : HExpression(parameter_type), index_(index) {}
+ : HExpression(parameter_type, SideEffects::None()), index_(index) {}
uint8_t GetIndex() const { return index_; }
@@ -1265,10 +1340,13 @@
class HNot : public HExpression<1> {
public:
- explicit HNot(HInstruction* input) : HExpression(Primitive::kPrimBoolean) {
+ explicit HNot(HInstruction* input) : HExpression(Primitive::kPrimBoolean, SideEffects::None()) {
SetRawInputAt(0, input);
}
+ virtual bool CanBeMoved() const { return true; }
+ virtual bool InstructionDataEquals(HInstruction* other) const { return true; }
+
DECLARE_INSTRUCTION(Not);
private:
@@ -1278,7 +1356,8 @@
class HPhi : public HInstruction {
public:
HPhi(ArenaAllocator* arena, uint32_t reg_number, size_t number_of_inputs, Primitive::Type type)
- : inputs_(arena, number_of_inputs),
+ : HInstruction(SideEffects::None()),
+ inputs_(arena, number_of_inputs),
reg_number_(reg_number),
type_(type),
is_live_(false) {
@@ -1318,10 +1397,13 @@
class HNullCheck : public HExpression<1> {
public:
HNullCheck(HInstruction* value, uint32_t dex_pc)
- : HExpression(value->GetType()), dex_pc_(dex_pc) {
+ : HExpression(value->GetType(), SideEffects::None()), dex_pc_(dex_pc) {
SetRawInputAt(0, value);
}
+ virtual bool CanBeMoved() const { return true; }
+ virtual bool InstructionDataEquals(HInstruction* other) const { return true; }
+
virtual bool NeedsEnvironment() const { return true; }
uint32_t GetDexPc() const { return dex_pc_; }
@@ -1352,10 +1434,17 @@
HInstanceFieldGet(HInstruction* value,
Primitive::Type field_type,
MemberOffset field_offset)
- : HExpression(field_type), field_info_(field_offset, field_type) {
+ : HExpression(field_type, SideEffects::DependsOnSomething()),
+ field_info_(field_offset, field_type) {
SetRawInputAt(0, value);
}
+ virtual bool CanBeMoved() const { return true; }
+ virtual bool InstructionDataEquals(HInstruction* other) const {
+ size_t other_offset = other->AsInstanceFieldGet()->GetFieldOffset().SizeValue();
+ return other_offset == GetFieldOffset().SizeValue();
+ }
+
MemberOffset GetFieldOffset() const { return field_info_.GetFieldOffset(); }
Primitive::Type GetFieldType() const { return field_info_.GetFieldType(); }
@@ -1373,7 +1462,8 @@
HInstruction* value,
Primitive::Type field_type,
MemberOffset field_offset)
- : field_info_(field_offset, field_type) {
+ : HTemplateInstruction(SideEffects::ChangesSomething()),
+ field_info_(field_offset, field_type) {
SetRawInputAt(0, object);
SetRawInputAt(1, value);
}
@@ -1392,11 +1482,14 @@
class HArrayGet : public HExpression<2> {
public:
HArrayGet(HInstruction* array, HInstruction* index, Primitive::Type type)
- : HExpression(type) {
+ : HExpression(type, SideEffects::DependsOnSomething()) {
SetRawInputAt(0, array);
SetRawInputAt(1, index);
}
+ virtual bool CanBeMoved() const { return true; }
+ virtual bool InstructionDataEquals(HInstruction* other) const { return true; }
+
DECLARE_INSTRUCTION(ArrayGet);
private:
@@ -1409,7 +1502,10 @@
HInstruction* index,
HInstruction* value,
Primitive::Type component_type,
- uint32_t dex_pc) : dex_pc_(dex_pc), component_type_(component_type) {
+ uint32_t dex_pc)
+ : HTemplateInstruction(SideEffects::ChangesSomething()),
+ dex_pc_(dex_pc),
+ component_type_(component_type) {
SetRawInputAt(0, array);
SetRawInputAt(1, index);
SetRawInputAt(2, value);
@@ -1436,10 +1532,16 @@
class HArrayLength : public HExpression<1> {
public:
- explicit HArrayLength(HInstruction* array) : HExpression(Primitive::kPrimInt) {
+ explicit HArrayLength(HInstruction* array)
+ : HExpression(Primitive::kPrimInt, SideEffects::None()) {
+ // Note that arrays do not change length, so the instruction does not
+ // depend on any write.
SetRawInputAt(0, array);
}
+ virtual bool CanBeMoved() const { return true; }
+ virtual bool InstructionDataEquals(HInstruction* other) const { return true; }
+
DECLARE_INSTRUCTION(ArrayLength);
private:
@@ -1449,12 +1551,15 @@
class HBoundsCheck : public HExpression<2> {
public:
HBoundsCheck(HInstruction* index, HInstruction* length, uint32_t dex_pc)
- : HExpression(index->GetType()), dex_pc_(dex_pc) {
+ : HExpression(index->GetType(), SideEffects::None()), dex_pc_(dex_pc) {
DCHECK(index->GetType() == Primitive::kPrimInt);
SetRawInputAt(0, index);
SetRawInputAt(1, length);
}
+ virtual bool CanBeMoved() const { return true; }
+ virtual bool InstructionDataEquals(HInstruction* other) const { return true; }
+
virtual bool NeedsEnvironment() const { return true; }
uint32_t GetDexPc() const { return dex_pc_; }
@@ -1476,7 +1581,7 @@
*/
class HTemporary : public HTemplateInstruction<0> {
public:
- explicit HTemporary(size_t index) : index_(index) {}
+ explicit HTemporary(size_t index) : HTemplateInstruction(SideEffects::None()), index_(index) {}
size_t GetIndex() const { return index_; }
@@ -1550,7 +1655,8 @@
class HParallelMove : public HTemplateInstruction<0> {
public:
- explicit HParallelMove(ArenaAllocator* arena) : moves_(arena, kDefaultNumberOfMoves) {}
+ explicit HParallelMove(ArenaAllocator* arena)
+ : HTemplateInstruction(SideEffects::None()), moves_(arena, kDefaultNumberOfMoves) {}
void AddMove(MoveOperands* move) {
moves_.Add(move);
