Optimizing: Speed up HInstruction use removal
Similarly to a previous commit on HEnvironment use removal, this patch
adds links from instructions to their respective inputs' use lists for
contant-time removal at the cost of doubling the size of input lists
(from one pointer per entry to two). Manual testing shows that this
significantly reduces the time required to transform HGraph to SSA
form for some huge methods.
Change-Id: I8dc3e4b0c48a50ac1481eb55c31093b99f4dc29f
diff --git a/compiler/optimizing/bounds_check_elimination_test.cc b/compiler/optimizing/bounds_check_elimination_test.cc
index 17cb8f3..66c873e 100644
--- a/compiler/optimizing/bounds_check_elimination_test.cc
+++ b/compiler/optimizing/bounds_check_elimination_test.cc
@@ -400,7 +400,6 @@
loop_body->AddSuccessor(loop_header);
HPhi* phi = new (allocator) HPhi(allocator, 0, 0, Primitive::kPrimInt);
- phi->AddInput(constant_initial);
HInstruction* null_check = new (allocator) HNullCheck(parameter, 0);
HInstruction* array_length = new (allocator) HArrayLength(null_check);
HInstruction* cmp = nullptr;
@@ -416,6 +415,7 @@
loop_header->AddInstruction(array_length);
loop_header->AddInstruction(cmp);
loop_header->AddInstruction(if_inst);
+ phi->AddInput(constant_initial);
null_check = new (allocator) HNullCheck(parameter, 0);
array_length = new (allocator) HArrayLength(null_check);
@@ -544,7 +544,6 @@
loop_body->AddSuccessor(loop_header);
HPhi* phi = new (allocator) HPhi(allocator, 0, 0, Primitive::kPrimInt);
- phi->AddInput(array_length);
HInstruction* cmp = nullptr;
if (cond == kCondLE) {
cmp = new (allocator) HLessThanOrEqual(phi, constant_initial);
@@ -556,6 +555,7 @@
loop_header->AddPhi(phi);
loop_header->AddInstruction(cmp);
loop_header->AddInstruction(if_inst);
+ phi->AddInput(array_length);
HInstruction* add = new (allocator) HAdd(Primitive::kPrimInt, phi, constant_minus_1);
null_check = new (allocator) HNullCheck(parameter, 0);
@@ -672,7 +672,6 @@
loop_body->AddSuccessor(loop_header);
HPhi* phi = new (allocator) HPhi(allocator, 0, 0, Primitive::kPrimInt);
- phi->AddInput(constant_initial);
HInstruction* cmp = nullptr;
if (cond == kCondGE) {
cmp = new (allocator) HGreaterThanOrEqual(phi, constant_10);
@@ -684,6 +683,7 @@
loop_header->AddPhi(phi);
loop_header->AddInstruction(cmp);
loop_header->AddInstruction(if_inst);
+ phi->AddInput(constant_initial);
HNullCheck* null_check = new (allocator) HNullCheck(new_array, 0);
HArrayLength* array_length = new (allocator) HArrayLength(null_check);
@@ -785,7 +785,6 @@
loop_body->AddSuccessor(loop_header);
HPhi* phi = new (allocator) HPhi(allocator, 0, 0, Primitive::kPrimInt);
- phi->AddInput(constant_initial);
HInstruction* null_check = new (allocator) HNullCheck(parameter, 0);
HInstruction* array_length = new (allocator) HArrayLength(null_check);
HInstruction* cmp = nullptr;
@@ -800,6 +799,7 @@
loop_header->AddInstruction(array_length);
loop_header->AddInstruction(cmp);
loop_header->AddInstruction(if_inst);
+ phi->AddInput(constant_initial);
null_check = new (allocator) HNullCheck(parameter, 0);
array_length = new (allocator) HArrayLength(null_check);
@@ -904,7 +904,6 @@
HBasicBlock* outer_header = new (&allocator) HBasicBlock(graph);
graph->AddBlock(outer_header);
HPhi* phi_i = new (&allocator) HPhi(&allocator, 0, 0, Primitive::kPrimInt);
- phi_i->AddInput(constant_0);
HNullCheck* null_check = new (&allocator) HNullCheck(parameter, 0);
HArrayLength* array_length = new (&allocator) HArrayLength(null_check);
HAdd* add = new (&allocator) HAdd(Primitive::kPrimInt, array_length, constant_minus_1);
@@ -916,11 +915,11 @@
outer_header->AddInstruction(add);
outer_header->AddInstruction(cmp);
outer_header->AddInstruction(if_inst);
+ phi_i->AddInput(constant_0);
HBasicBlock* inner_header = new (&allocator) HBasicBlock(graph);
graph->AddBlock(inner_header);
HPhi* phi_j = new (&allocator) HPhi(&allocator, 0, 0, Primitive::kPrimInt);
- phi_j->AddInput(constant_0);
null_check = new (&allocator) HNullCheck(parameter, 0);
array_length = new (&allocator) HArrayLength(null_check);
HSub* sub = new (&allocator) HSub(Primitive::kPrimInt, array_length, phi_i);
@@ -934,6 +933,7 @@
inner_header->AddInstruction(add);
inner_header->AddInstruction(cmp);
inner_header->AddInstruction(if_inst);
+ phi_j->AddInput(constant_0);
HBasicBlock* inner_body_compare = new (&allocator) HBasicBlock(graph);
graph->AddBlock(inner_body_compare);
diff --git a/compiler/optimizing/graph_checker.cc b/compiler/optimizing/graph_checker.cc
index ef10428..a7f1f74 100644
--- a/compiler/optimizing/graph_checker.cc
+++ b/compiler/optimizing/graph_checker.cc
@@ -160,6 +160,22 @@
instruction->GetId()));
}
}
+
+ // Ensure 'instruction' has pointers to its inputs' use entries.
+ for (size_t i = 0, e = instruction->InputCount(); i < e; ++i) {
+ HUserRecord<HInstruction*> input_record = instruction->InputRecordAt(i);
+ HInstruction* input = input_record.GetInstruction();
+ HUseListNode<HInstruction*>* use_node = input_record.GetUseNode();
+ if (use_node == nullptr || !input->GetUses().Contains(use_node)) {
+ AddError(StringPrintf("Instruction %s:%d has an invalid pointer to use entry "
+ "at input %u (%s:%d).",
+ instruction->DebugName(),
+ instruction->GetId(),
+ static_cast<unsigned>(i),
+ input->DebugName(),
+ input->GetId()));
+ }
+ }
}
void SSAChecker::VisitBasicBlock(HBasicBlock* block) {
diff --git a/compiler/optimizing/licm.cc b/compiler/optimizing/licm.cc
index 10f24d8..bf9b8e5 100644
--- a/compiler/optimizing/licm.cc
+++ b/compiler/optimizing/licm.cc
@@ -66,8 +66,7 @@
for (size_t i = 0, e = environment->Size(); i < e; ++i) {
HInstruction* input = environment->GetInstructionAt(i);
if (input != nullptr && IsPhiOf(input, info->GetHeader())) {
- HUseListNode<HEnvironment*>* env_use = environment->GetInstructionEnvUseAt(i);
- input->RemoveEnvironmentUser(env_use);
+ environment->RemoveAsUserOfInput(i);
HInstruction* incoming = input->InputAt(0);
environment->SetRawEnvAt(i, incoming);
incoming->AddEnvUseAt(environment, i);
diff --git a/compiler/optimizing/nodes.cc b/compiler/optimizing/nodes.cc
index 7a75d26..93787b8 100644
--- a/compiler/optimizing/nodes.cc
+++ b/compiler/optimizing/nodes.cc
@@ -34,17 +34,14 @@
static void RemoveAsUser(HInstruction* instruction) {
for (size_t i = 0; i < instruction->InputCount(); i++) {
- instruction->InputAt(i)->RemoveUser(instruction, i);
+ instruction->RemoveAsUserOfInput(i);
}
HEnvironment* environment = instruction->GetEnvironment();
if (environment != nullptr) {
for (size_t i = 0, e = environment->Size(); i < e; ++i) {
- HUseListNode<HEnvironment*>* vreg_env_use = environment->GetInstructionEnvUseAt(i);
- if (vreg_env_use != nullptr) {
- HInstruction* vreg = environment->GetInstructionAt(i);
- DCHECK(vreg != nullptr);
- vreg->RemoveEnvironmentUser(vreg_env_use);
+ if (environment->GetInstructionAt(i) != nullptr) {
+ environment->RemoveAsUserOfInput(i);
}
}
}
@@ -64,22 +61,19 @@
}
}
-void HGraph::RemoveBlock(HBasicBlock* block) const {
- for (size_t j = 0; j < block->GetSuccessors().Size(); ++j) {
- block->GetSuccessors().Get(j)->RemovePredecessor(block);
- }
- for (HInstructionIterator it(block->GetPhis()); !it.Done(); it.Advance()) {
- block->RemovePhi(it.Current()->AsPhi());
- }
- for (HInstructionIterator it(block->GetInstructions()); !it.Done(); it.Advance()) {
- block->RemoveInstruction(it.Current());
- }
-}
-
void HGraph::RemoveDeadBlocks(const ArenaBitVector& visited) const {
for (size_t i = 0; i < blocks_.Size(); ++i) {
if (!visited.IsBitSet(i)) {
- RemoveBlock(blocks_.Get(i));
+ HBasicBlock* block = blocks_.Get(i);
+ for (size_t j = 0; j < block->GetSuccessors().Size(); ++j) {
+ block->GetSuccessors().Get(j)->RemovePredecessor(block);
+ }
+ for (HInstructionIterator it(block->GetPhis()); !it.Done(); it.Advance()) {
+ block->RemovePhi(it.Current()->AsPhi(), /*ensure_safety=*/ false);
+ }
+ for (HInstructionIterator it(block->GetInstructions()); !it.Done(); it.Advance()) {
+ block->RemoveInstruction(it.Current(), /*ensure_safety=*/ false);
+ }
}
}
}
@@ -439,22 +433,24 @@
static void Remove(HInstructionList* instruction_list,
HBasicBlock* block,
- HInstruction* instruction) {
+ HInstruction* instruction,
+ bool ensure_safety) {
DCHECK_EQ(block, instruction->GetBlock());
- DCHECK(instruction->GetUses().IsEmpty());
- DCHECK(instruction->GetEnvUses().IsEmpty());
instruction->SetBlock(nullptr);
instruction_list->RemoveInstruction(instruction);
-
- RemoveAsUser(instruction);
+ if (ensure_safety) {
+ DCHECK(instruction->GetUses().IsEmpty());
+ DCHECK(instruction->GetEnvUses().IsEmpty());
+ RemoveAsUser(instruction);
+ }
}
-void HBasicBlock::RemoveInstruction(HInstruction* instruction) {
- Remove(&instructions_, this, instruction);
+void HBasicBlock::RemoveInstruction(HInstruction* instruction, bool ensure_safety) {
+ Remove(&instructions_, this, instruction, ensure_safety);
}
-void HBasicBlock::RemovePhi(HPhi* phi) {
- Remove(&phis_, this, phi);
+void HBasicBlock::RemovePhi(HPhi* phi, bool ensure_safety) {
+ Remove(&phis_, this, phi, ensure_safety);
}
void HEnvironment::CopyFrom(HEnvironment* env) {
@@ -467,15 +463,9 @@
}
}
-template <typename T>
-static void RemoveFromUseList(T user, size_t input_index, HUseList<T>* list) {
- HUseListNode<T>* current;
- for (HUseIterator<HInstruction*> use_it(*list); !use_it.Done(); use_it.Advance()) {
- current = use_it.Current();
- if (current->GetUser() == user && current->GetIndex() == input_index) {
- list->Remove(current);
- }
- }
+void HEnvironment::RemoveAsUserOfInput(size_t index) const {
+ const HUserRecord<HEnvironment*> user_record = vregs_.Get(index);
+ user_record.GetInstruction()->RemoveEnvironmentUser(user_record.GetUseNode());
}
HInstruction* HInstruction::GetNextDisregardingMoves() const {
@@ -494,14 +484,6 @@
return previous;
}
-void HInstruction::RemoveUser(HInstruction* user, size_t input_index) {
- RemoveFromUseList(user, input_index, &uses_);
-}
-
-void HInstruction::RemoveEnvironmentUser(HUseListNode<HEnvironment*>* use) {
- env_uses_.Remove(use);
-}
-
void HInstructionList::AddInstruction(HInstruction* instruction) {
if (first_instruction_ == nullptr) {
DCHECK(last_instruction_ == nullptr);
@@ -612,7 +594,7 @@
}
void HInstruction::ReplaceInput(HInstruction* replacement, size_t index) {
- InputAt(index)->RemoveUser(this, index);
+ RemoveAsUserOfInput(index);
SetRawInputAt(index, replacement);
replacement->AddUseAt(this, index);
}
@@ -623,7 +605,7 @@
void HPhi::AddInput(HInstruction* input) {
DCHECK(input->GetBlock() != nullptr);
- inputs_.Add(input);
+ inputs_.Add(HUserRecord<HInstruction*>(input));
input->AddUseAt(this, inputs_.Size() - 1);
}
diff --git a/compiler/optimizing/nodes.h b/compiler/optimizing/nodes.h
index 352403d..de448cc 100644
--- a/compiler/optimizing/nodes.h
+++ b/compiler/optimizing/nodes.h
@@ -31,6 +31,7 @@
namespace art {
+class GraphChecker;
class HBasicBlock;
class HEnvironment;
class HInstruction;
@@ -211,7 +212,6 @@
ArenaBitVector* visiting);
void RemoveInstructionsAsUsersFromDeadBlocks(const ArenaBitVector& visited) const;
void RemoveDeadBlocks(const ArenaBitVector& visited) const;
- void RemoveBlock(HBasicBlock* block) const;
ArenaAllocator* const arena_;
@@ -490,14 +490,17 @@
void ReplaceWith(HBasicBlock* other);
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 InsertPhiAfter(HPhi* instruction, HPhi* cursor);
- void RemovePhi(HPhi* phi);
+ // RemoveInstruction and RemovePhi delete a given instruction from the respective
+ // instruction list. With 'ensure_safety' set to true, it verifies that the
+ // instruction is not in use and removes it from the use lists of its inputs.
+ void RemoveInstruction(HInstruction* instruction, bool ensure_safety = true);
+ void RemovePhi(HPhi* phi, bool ensure_safety = true);
bool IsLoopHeader() const {
return (loop_information_ != nullptr) && (loop_information_->GetHeader() == this);
@@ -715,6 +718,9 @@
}
void Remove(HUseListNode<T>* node) {
+ DCHECK(node != nullptr);
+ DCHECK(Contains(node));
+
if (node->prev_ != nullptr) {
node->prev_->next_ = node->next_;
}
@@ -726,6 +732,18 @@
}
}
+ bool Contains(const HUseListNode<T>* node) const {
+ if (node == nullptr) {
+ return false;
+ }
+ for (HUseListNode<T>* current = first_; current != nullptr; current = current->GetNext()) {
+ if (current == node) {
+ return true;
+ }
+ }
+ return false;
+ }
+
bool IsEmpty() const {
return first_ == nullptr;
}
@@ -761,6 +779,33 @@
friend class HValue;
};
+// This class is used by HEnvironment and HInstruction classes to record the
+// instructions they use and pointers to the corresponding HUseListNodes kept
+// by the used instructions.
+template <typename T>
+class HUserRecord : public ValueObject {
+ public:
+ HUserRecord() : instruction_(nullptr), use_node_(nullptr) {}
+ explicit HUserRecord(HInstruction* instruction) : instruction_(instruction), use_node_(nullptr) {}
+
+ HUserRecord(const HUserRecord<T>& old_record, HUseListNode<T>* use_node)
+ : instruction_(old_record.instruction_), use_node_(use_node) {
+ DCHECK(instruction_ != nullptr);
+ DCHECK(use_node_ != nullptr);
+ DCHECK(old_record.use_node_ == nullptr);
+ }
+
+ HInstruction* GetInstruction() const { return instruction_; }
+ HUseListNode<T>* GetUseNode() const { return use_node_; }
+
+ private:
+ // Instruction used by the user.
+ HInstruction* instruction_;
+
+ // Corresponding entry in the use list kept by 'instruction_'.
+ HUseListNode<T>* use_node_;
+};
+
// Represents the side effects an instruction may have.
class SideEffects : public ValueObject {
public:
@@ -831,46 +876,36 @@
: vregs_(arena, number_of_vregs) {
vregs_.SetSize(number_of_vregs);
for (size_t i = 0; i < number_of_vregs; i++) {
- vregs_.Put(i, VRegInfo(nullptr, nullptr));
+ vregs_.Put(i, HUserRecord<HEnvironment*>());
}
}
void CopyFrom(HEnvironment* env);
void SetRawEnvAt(size_t index, HInstruction* instruction) {
- vregs_.Put(index, VRegInfo(instruction, nullptr));
- }
-
- // Record instructions' use entries of this environment for constant-time removal.
- void RecordEnvUse(HUseListNode<HEnvironment*>* env_use) {
- DCHECK(env_use->GetUser() == this);
- size_t index = env_use->GetIndex();
- VRegInfo info = vregs_.Get(index);
- DCHECK(info.vreg_ != nullptr);
- DCHECK(info.node_ == nullptr);
- vregs_.Put(index, VRegInfo(info.vreg_, env_use));
+ vregs_.Put(index, HUserRecord<HEnvironment*>(instruction));
}
HInstruction* GetInstructionAt(size_t index) const {
- return vregs_.Get(index).vreg_;
+ return vregs_.Get(index).GetInstruction();
}
- HUseListNode<HEnvironment*>* GetInstructionEnvUseAt(size_t index) const {
- return vregs_.Get(index).node_;
- }
+ void RemoveAsUserOfInput(size_t index) const;
size_t Size() const { return vregs_.Size(); }
private:
- struct VRegInfo {
- HInstruction* vreg_;
- HUseListNode<HEnvironment*>* node_;
+ // Record instructions' use entries of this environment for constant-time removal.
+ // It should only be called by HInstruction when a new environment use is added.
+ void RecordEnvUse(HUseListNode<HEnvironment*>* env_use) {
+ DCHECK(env_use->GetUser() == this);
+ size_t index = env_use->GetIndex();
+ vregs_.Put(index, HUserRecord<HEnvironment*>(vregs_.Get(index), env_use));
+ }
- VRegInfo(HInstruction* instruction, HUseListNode<HEnvironment*>* env_use)
- : vreg_(instruction), node_(env_use) {}
- };
+ GrowableArray<HUserRecord<HEnvironment*> > vregs_;
- GrowableArray<VRegInfo> vregs_;
+ friend HInstruction;
DISALLOW_COPY_AND_ASSIGN(HEnvironment);
};
@@ -989,13 +1024,15 @@
bool IsLoopHeaderPhi() { return IsPhi() && block_->IsLoopHeader(); }
virtual size_t InputCount() const = 0;
- virtual HInstruction* InputAt(size_t i) const = 0;
+ HInstruction* InputAt(size_t i) const { return InputRecordAt(i).GetInstruction(); }
virtual void Accept(HGraphVisitor* visitor) = 0;
virtual const char* DebugName() const = 0;
virtual Primitive::Type GetType() const { return Primitive::kPrimVoid; }
- virtual void SetRawInputAt(size_t index, HInstruction* input) = 0;
+ void SetRawInputAt(size_t index, HInstruction* input) {
+ SetRawInputRecordAt(index, HUserRecord<HInstruction*>(input));
+ }
virtual bool NeedsEnvironment() const { return false; }
virtual bool IsControlFlow() const { return false; }
@@ -1018,7 +1055,10 @@
ReferenceTypeInfo GetReferenceTypeInfo() const { return reference_type_info_; }
void AddUseAt(HInstruction* user, size_t index) {
- uses_.AddUse(user, index, GetBlock()->GetGraph()->GetArena());
+ DCHECK(user != nullptr);
+ HUseListNode<HInstruction*>* use =
+ uses_.AddUse(user, index, GetBlock()->GetGraph()->GetArena());
+ user->SetRawInputRecordAt(index, HUserRecord<HInstruction*>(user->InputRecordAt(index), use));
}
void AddEnvUseAt(HEnvironment* user, size_t index) {
@@ -1028,11 +1068,13 @@
user->RecordEnvUse(env_use);
}
- void RemoveUser(HInstruction* user, size_t index);
- void RemoveEnvironmentUser(HUseListNode<HEnvironment*>* use);
+ void RemoveAsUserOfInput(size_t input) {
+ HUserRecord<HInstruction*> input_use = InputRecordAt(input);
+ input_use.GetInstruction()->uses_.Remove(input_use.GetUseNode());
+ }
- const HUseList<HInstruction*>& GetUses() { return uses_; }
- const HUseList<HEnvironment*>& GetEnvUses() { return env_uses_; }
+ const HUseList<HInstruction*>& GetUses() const { return uses_; }
+ const HUseList<HEnvironment*>& GetEnvUses() const { return env_uses_; }
bool HasUses() const { return !uses_.IsEmpty() || !env_uses_.IsEmpty(); }
bool HasEnvironmentUses() const { return !env_uses_.IsEmpty(); }
@@ -1126,7 +1168,13 @@
return NeedsEnvironment() || IsLoadClass() || IsLoadString();
}
+ protected:
+ virtual const HUserRecord<HInstruction*> InputRecordAt(size_t i) const = 0;
+ virtual void SetRawInputRecordAt(size_t index, const HUserRecord<HInstruction*>& input) = 0;
+
private:
+ void RemoveEnvironmentUser(HUseListNode<HEnvironment*>* use_node) { env_uses_.Remove(use_node); }
+
HInstruction* previous_;
HInstruction* next_;
HBasicBlock* block_;
@@ -1164,7 +1212,9 @@
// TODO: for primitive types this should be marked as invalid.
ReferenceTypeInfo reference_type_info_;
+ friend class GraphChecker;
friend class HBasicBlock;
+ friend class HEnvironment;
friend class HGraph;
friend class HInstructionList;
@@ -1284,15 +1334,16 @@
virtual ~HTemplateInstruction() {}
virtual size_t InputCount() const { return N; }
- virtual HInstruction* InputAt(size_t i) const { return inputs_[i]; }
protected:
- virtual void SetRawInputAt(size_t i, HInstruction* instruction) {
- inputs_[i] = instruction;
+ const HUserRecord<HInstruction*> InputRecordAt(size_t i) const OVERRIDE { return inputs_[i]; }
+
+ void SetRawInputRecordAt(size_t i, const HUserRecord<HInstruction*>& input) OVERRIDE {
+ inputs_[i] = input;
}
private:
- EmbeddedArray<HInstruction*, N> inputs_;
+ EmbeddedArray<HUserRecord<HInstruction*>, N> inputs_;
friend class SsaBuilder;
};
@@ -1848,7 +1899,6 @@
class HInvoke : public HInstruction {
public:
virtual size_t InputCount() const { return inputs_.Size(); }
- virtual HInstruction* InputAt(size_t i) const { return inputs_.Get(i); }
// Runtime needs to walk the stack, so Dex -> Dex calls need to
// know their environment.
@@ -1858,10 +1908,6 @@
SetRawInputAt(index, argument);
}
- virtual void SetRawInputAt(size_t index, HInstruction* input) {
- inputs_.Put(index, input);
- }
-
virtual Primitive::Type GetType() const { return return_type_; }
uint32_t GetDexPc() const { return dex_pc_; }
@@ -1893,7 +1939,12 @@
inputs_.SetSize(number_of_arguments);
}
- GrowableArray<HInstruction*> inputs_;
+ const HUserRecord<HInstruction*> InputRecordAt(size_t i) const OVERRIDE { return inputs_.Get(i); }
+ void SetRawInputRecordAt(size_t index, const HUserRecord<HInstruction*>& input) OVERRIDE {
+ inputs_.Put(index, input);
+ }
+
+ GrowableArray<HUserRecord<HInstruction*> > inputs_;
const Primitive::Type return_type_;
const uint32_t dex_pc_;
const uint32_t dex_method_index_;
@@ -2389,11 +2440,6 @@
}
size_t InputCount() const OVERRIDE { return inputs_.Size(); }
- HInstruction* InputAt(size_t i) const OVERRIDE { return inputs_.Get(i); }
-
- void SetRawInputAt(size_t index, HInstruction* input) OVERRIDE {
- inputs_.Put(index, input);
- }
void AddInput(HInstruction* input);
@@ -2412,8 +2458,15 @@
DECLARE_INSTRUCTION(Phi);
+ protected:
+ const HUserRecord<HInstruction*> InputRecordAt(size_t i) const OVERRIDE { return inputs_.Get(i); }
+
+ void SetRawInputRecordAt(size_t index, const HUserRecord<HInstruction*>& input) OVERRIDE {
+ inputs_.Put(index, input);
+ }
+
private:
- GrowableArray<HInstruction*> inputs_;
+ GrowableArray<HUserRecord<HInstruction*> > inputs_;
const uint32_t reg_number_;
Primitive::Type type_;
bool is_live_;
diff --git a/compiler/optimizing/ssa_phi_elimination.cc b/compiler/optimizing/ssa_phi_elimination.cc
index f66a1c8..2f2e2d1 100644
--- a/compiler/optimizing/ssa_phi_elimination.cc
+++ b/compiler/optimizing/ssa_phi_elimination.cc
@@ -64,31 +64,33 @@
HBasicBlock* block = it.Current();
HInstruction* current = block->GetFirstPhi();
HInstruction* next = nullptr;
+ HPhi* phi;
while (current != nullptr) {
+ phi = current->AsPhi();
next = current->GetNext();
- if (current->AsPhi()->IsDead()) {
- if (current->HasUses()) {
- for (HUseIterator<HInstruction*> use_it(current->GetUses()); !use_it.Done();
+ if (phi->IsDead()) {
+ // Make sure the phi is only used by other dead phis.
+ if (kIsDebugBuild) {
+ for (HUseIterator<HInstruction*> use_it(phi->GetUses()); !use_it.Done();
use_it.Advance()) {
- HUseListNode<HInstruction*>* user_node = use_it.Current();
- HInstruction* user = user_node->GetUser();
+ HInstruction* user = use_it.Current()->GetUser();
DCHECK(user->IsLoopHeaderPhi()) << user->GetId();
DCHECK(user->AsPhi()->IsDead()) << user->GetId();
- // Just put itself as an input. The phi will be removed in this loop anyway.
- user->SetRawInputAt(user_node->GetIndex(), user);
- current->RemoveUser(user, user_node->GetIndex());
}
}
- if (current->HasEnvironmentUses()) {
- for (HUseIterator<HEnvironment*> use_it(current->GetEnvUses()); !use_it.Done();
- use_it.Advance()) {
- HUseListNode<HEnvironment*>* user_node = use_it.Current();
- HEnvironment* user = user_node->GetUser();
- user->SetRawEnvAt(user_node->GetIndex(), nullptr);
- current->RemoveEnvironmentUser(user_node);
- }
+ // Remove the phi from use lists of its inputs.
+ for (size_t i = 0, e = phi->InputCount(); i < e; ++i) {
+ phi->RemoveAsUserOfInput(i);
}
- block->RemovePhi(current->AsPhi());
+ // Remove the phi from environments that use it.
+ for (HUseIterator<HEnvironment*> use_it(phi->GetEnvUses()); !use_it.Done();
+ use_it.Advance()) {
+ HUseListNode<HEnvironment*>* user_node = use_it.Current();
+ HEnvironment* user = user_node->GetUser();
+ user->SetRawEnvAt(user_node->GetIndex(), nullptr);
+ }
+ // Delete it from the instruction list.
+ block->RemovePhi(phi, /*ensure_safety=*/ false);
}
current = next;
}