summaryrefslogtreecommitdiff
path: root/compiler/optimizing
diff options
context:
space:
mode:
Diffstat (limited to 'compiler/optimizing')
-rw-r--r--compiler/optimizing/bounds_check_elimination_test.cc12
-rw-r--r--compiler/optimizing/graph_checker.cc16
-rw-r--r--compiler/optimizing/licm.cc3
-rw-r--r--compiler/optimizing/nodes.cc76
-rw-r--r--compiler/optimizing/nodes.h151
-rw-r--r--compiler/optimizing/register_allocator.cc101
-rw-r--r--compiler/optimizing/register_allocator.h15
-rw-r--r--compiler/optimizing/ssa_phi_elimination.cc36
8 files changed, 264 insertions, 146 deletions
diff --git a/compiler/optimizing/bounds_check_elimination_test.cc b/compiler/optimizing/bounds_check_elimination_test.cc
index 17cb8f35de..66c873e27e 100644
--- a/compiler/optimizing/bounds_check_elimination_test.cc
+++ b/compiler/optimizing/bounds_check_elimination_test.cc
@@ -400,7 +400,6 @@ static HGraph* BuildSSAGraph1(ArenaAllocator* allocator,
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 @@ static HGraph* BuildSSAGraph1(ArenaAllocator* allocator,
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 @@ static HGraph* BuildSSAGraph2(ArenaAllocator* allocator,
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 @@ static HGraph* BuildSSAGraph2(ArenaAllocator* allocator,
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 @@ static HGraph* BuildSSAGraph3(ArenaAllocator* allocator,
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 @@ static HGraph* BuildSSAGraph3(ArenaAllocator* allocator,
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 @@ static HGraph* BuildSSAGraph4(ArenaAllocator* allocator,
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 @@ static HGraph* BuildSSAGraph4(ArenaAllocator* allocator,
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 @@ TEST(BoundsCheckEliminationTest, BubbleSortArrayBoundsElimination) {
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 @@ TEST(BoundsCheckEliminationTest, BubbleSortArrayBoundsElimination) {
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 @@ TEST(BoundsCheckEliminationTest, BubbleSortArrayBoundsElimination) {
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 ef10428c0f..a7f1f74e27 100644
--- a/compiler/optimizing/graph_checker.cc
+++ b/compiler/optimizing/graph_checker.cc
@@ -160,6 +160,22 @@ void GraphChecker::VisitInstruction(HInstruction* instruction) {
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 10f24d8148..bf9b8e59c5 100644
--- a/compiler/optimizing/licm.cc
+++ b/compiler/optimizing/licm.cc
@@ -66,8 +66,7 @@ static void UpdateLoopPhisIn(HEnvironment* environment, HLoopInformation* info)
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 7a75d260fd..93787b8bfd 100644
--- a/compiler/optimizing/nodes.cc
+++ b/compiler/optimizing/nodes.cc
@@ -34,17 +34,14 @@ void HGraph::FindBackEdges(ArenaBitVector* visited) {
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::RemoveInstructionsAsUsersFromDeadBlocks(const ArenaBitVector& visit
}
}
-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 @@ void HBasicBlock::InsertPhiAfter(HPhi* phi, HPhi* cursor) {
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 @@ void HEnvironment::CopyFrom(HEnvironment* env) {
}
}
-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 @@ HInstruction* HInstruction::GetPreviousDisregardingMoves() const {
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::ReplaceWith(HInstruction* other) {
}
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 @@ size_t HInstruction::EnvironmentSize() const {
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 352403d72c..de448cc483 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 @@ class HGraph : public ArenaObject<kArenaAllocMisc> {
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 @@ class HBasicBlock : public ArenaObject<kArenaAllocMisc> {
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 @@ class HUseList : public ValueObject {
}
void Remove(HUseListNode<T>* node) {
+ DCHECK(node != nullptr);
+ DCHECK(Contains(node));
+
if (node->prev_ != nullptr) {
node->prev_->next_ = node->next_;
}
@@ -726,6 +732,18 @@ class HUseList : public ValueObject {
}
}
+ 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 @@ class HUseIterator : public ValueObject {
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 @@ class HEnvironment : public ArenaObject<kArenaAllocMisc> {
: 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 @@ class HInstruction : public ArenaObject<kArenaAllocMisc> {
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 @@ class HInstruction : public ArenaObject<kArenaAllocMisc> {
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 @@ class HInstruction : public ArenaObject<kArenaAllocMisc> {
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 @@ class HInstruction : public ArenaObject<kArenaAllocMisc> {
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 @@ class HInstruction : public ArenaObject<kArenaAllocMisc> {
// 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 @@ class HTemplateInstruction: public HInstruction {
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 @@ std::ostream& operator<<(std::ostream& os, const Intrinsics& intrinsic);
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 @@ class HInvoke : public HInstruction {
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 @@ class HInvoke : public HInstruction {
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 @@ class HPhi : public HInstruction {
}
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 @@ class HPhi : public HInstruction {
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/register_allocator.cc b/compiler/optimizing/register_allocator.cc
index bfbe63f6ce..54e62a5b2c 100644
--- a/compiler/optimizing/register_allocator.cc
+++ b/compiler/optimizing/register_allocator.cc
@@ -48,7 +48,10 @@ RegisterAllocator::RegisterAllocator(ArenaAllocator* allocator,
physical_core_register_intervals_(allocator, codegen->GetNumberOfCoreRegisters()),
physical_fp_register_intervals_(allocator, codegen->GetNumberOfFloatingPointRegisters()),
temp_intervals_(allocator, 4),
- spill_slots_(allocator, kDefaultNumberOfSpillSlots),
+ int_spill_slots_(allocator, kDefaultNumberOfSpillSlots),
+ long_spill_slots_(allocator, kDefaultNumberOfSpillSlots),
+ float_spill_slots_(allocator, kDefaultNumberOfSpillSlots),
+ double_spill_slots_(allocator, kDefaultNumberOfSpillSlots),
safepoints_(allocator, 0),
processing_core_registers_(false),
number_of_registers_(-1),
@@ -438,7 +441,7 @@ bool RegisterAllocator::ValidateInternal(bool log_fatal_on_failure) const {
}
}
- return ValidateIntervals(intervals, spill_slots_.Size(), reserved_out_slots_, *codegen_,
+ return ValidateIntervals(intervals, GetNumberOfSpillSlots(), reserved_out_slots_, *codegen_,
allocator_, processing_core_registers_, log_fatal_on_failure);
}
@@ -1133,41 +1136,62 @@ void RegisterAllocator::AllocateSpillSlotFor(LiveInterval* interval) {
}
size_t end = last_sibling->GetEnd();
+ GrowableArray<size_t>* spill_slots = nullptr;
+ switch (interval->GetType()) {
+ case Primitive::kPrimDouble:
+ spill_slots = &double_spill_slots_;
+ break;
+ case Primitive::kPrimLong:
+ spill_slots = &long_spill_slots_;
+ break;
+ case Primitive::kPrimFloat:
+ spill_slots = &float_spill_slots_;
+ break;
+ case Primitive::kPrimNot:
+ case Primitive::kPrimInt:
+ case Primitive::kPrimChar:
+ case Primitive::kPrimByte:
+ case Primitive::kPrimBoolean:
+ case Primitive::kPrimShort:
+ spill_slots = &int_spill_slots_;
+ break;
+ case Primitive::kPrimVoid:
+ LOG(FATAL) << "Unexpected type for interval " << interval->GetType();
+ }
+
// Find an available spill slot.
size_t slot = 0;
- for (size_t e = spill_slots_.Size(); slot < e; ++slot) {
- // We check if it is less rather than less or equal because the parallel move
- // resolver does not work when a single spill slot needs to be exchanged with
- // a double spill slot. The strict comparison avoids needing to exchange these
- // locations at the same lifetime position.
- if (spill_slots_.Get(slot) < parent->GetStart()
- && (slot == (e - 1) || spill_slots_.Get(slot + 1) < parent->GetStart())) {
+ for (size_t e = spill_slots->Size(); slot < e; ++slot) {
+ if (spill_slots->Get(slot) <= parent->GetStart()
+ && (slot == (e - 1) || spill_slots->Get(slot + 1) <= parent->GetStart())) {
break;
}
}
if (parent->NeedsTwoSpillSlots()) {
- if (slot == spill_slots_.Size()) {
+ if (slot == spill_slots->Size()) {
// We need a new spill slot.
- spill_slots_.Add(end);
- spill_slots_.Add(end);
- } else if (slot == spill_slots_.Size() - 1) {
- spill_slots_.Put(slot, end);
- spill_slots_.Add(end);
+ spill_slots->Add(end);
+ spill_slots->Add(end);
+ } else if (slot == spill_slots->Size() - 1) {
+ spill_slots->Put(slot, end);
+ spill_slots->Add(end);
} else {
- spill_slots_.Put(slot, end);
- spill_slots_.Put(slot + 1, end);
+ spill_slots->Put(slot, end);
+ spill_slots->Put(slot + 1, end);
}
} else {
- if (slot == spill_slots_.Size()) {
+ if (slot == spill_slots->Size()) {
// We need a new spill slot.
- spill_slots_.Add(end);
+ spill_slots->Add(end);
} else {
- spill_slots_.Put(slot, end);
+ spill_slots->Put(slot, end);
}
}
- parent->SetSpillSlot((slot + reserved_out_slots_) * kVRegSize);
+ // Note that the exact spill slot location will be computed when we resolve,
+ // that is when we know the number of spill slots for each type.
+ parent->SetSpillSlot(slot);
}
static bool IsValidDestination(Location destination) {
@@ -1516,7 +1540,7 @@ void RegisterAllocator::ConnectSplitSiblings(LiveInterval* interval,
}
void RegisterAllocator::Resolve() {
- codegen_->InitializeCodeGeneration(spill_slots_.Size(),
+ codegen_->InitializeCodeGeneration(GetNumberOfSpillSlots(),
maximum_number_of_live_core_registers_,
maximum_number_of_live_fp_registers_,
reserved_out_slots_,
@@ -1542,6 +1566,39 @@ void RegisterAllocator::Resolve() {
} else if (current->HasSpillSlot()) {
current->SetSpillSlot(current->GetSpillSlot() + codegen_->GetFrameSize());
}
+ } else if (current->HasSpillSlot()) {
+ // Adjust the stack slot, now that we know the number of them for each type.
+ // The way this implementation lays out the stack is the following:
+ // [parameter slots ]
+ // [double spill slots ]
+ // [long spill slots ]
+ // [float spill slots ]
+ // [int/ref values ]
+ // [maximum out values ] (number of arguments for calls)
+ // [art method ].
+ uint32_t slot = current->GetSpillSlot();
+ switch (current->GetType()) {
+ case Primitive::kPrimDouble:
+ slot += long_spill_slots_.Size();
+ FALLTHROUGH_INTENDED;
+ case Primitive::kPrimLong:
+ slot += float_spill_slots_.Size();
+ FALLTHROUGH_INTENDED;
+ case Primitive::kPrimFloat:
+ slot += int_spill_slots_.Size();
+ FALLTHROUGH_INTENDED;
+ case Primitive::kPrimNot:
+ case Primitive::kPrimInt:
+ case Primitive::kPrimChar:
+ case Primitive::kPrimByte:
+ case Primitive::kPrimBoolean:
+ case Primitive::kPrimShort:
+ slot += reserved_out_slots_;
+ break;
+ case Primitive::kPrimVoid:
+ LOG(FATAL) << "Unexpected type for interval " << current->GetType();
+ }
+ current->SetSpillSlot(slot * kVRegSize);
}
Location source = current->ToLocation();
diff --git a/compiler/optimizing/register_allocator.h b/compiler/optimizing/register_allocator.h
index b8f70bdc18..ff2f106b74 100644
--- a/compiler/optimizing/register_allocator.h
+++ b/compiler/optimizing/register_allocator.h
@@ -75,7 +75,10 @@ class RegisterAllocator {
}
size_t GetNumberOfSpillSlots() const {
- return spill_slots_.Size();
+ return int_spill_slots_.Size()
+ + long_spill_slots_.Size()
+ + float_spill_slots_.Size()
+ + double_spill_slots_.Size();
}
private:
@@ -171,8 +174,14 @@ class RegisterAllocator {
// where an instruction requires a temporary.
GrowableArray<LiveInterval*> temp_intervals_;
- // The spill slots allocated for live intervals.
- GrowableArray<size_t> spill_slots_;
+ // The spill slots allocated for live intervals. We ensure spill slots
+ // are typed to avoid (1) doing moves and swaps between two different kinds
+ // of registers, and (2) swapping between a single stack slot and a double
+ // stack slot. This simplifies the parallel move resolver.
+ GrowableArray<size_t> int_spill_slots_;
+ GrowableArray<size_t> long_spill_slots_;
+ GrowableArray<size_t> float_spill_slots_;
+ GrowableArray<size_t> double_spill_slots_;
// Instructions that need a safepoint.
GrowableArray<HInstruction*> safepoints_;
diff --git a/compiler/optimizing/ssa_phi_elimination.cc b/compiler/optimizing/ssa_phi_elimination.cc
index f66a1c8de2..2f2e2d1fab 100644
--- a/compiler/optimizing/ssa_phi_elimination.cc
+++ b/compiler/optimizing/ssa_phi_elimination.cc
@@ -64,31 +64,33 @@ void SsaDeadPhiElimination::EliminateDeadPhis() {
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);
+ }
+ // 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);
}
- block->RemovePhi(current->AsPhi());
+ // Delete it from the instruction list.
+ block->RemovePhi(phi, /*ensure_safety=*/ false);
}
current = next;
}
generated by cgit v1.2.3-59-g8ed1b (git 2.39.0) at 2025-10-21 19:39:24 +0000