Add a Transform to SSA phase to the optimizing compiler.
Change-Id: Ia9700756a0396d797a00b529896487d52c989329
diff --git a/compiler/optimizing/nodes.cc b/compiler/optimizing/nodes.cc
index 498deba..3d6aeb7 100644
--- a/compiler/optimizing/nodes.cc
+++ b/compiler/optimizing/nodes.cc
@@ -15,6 +15,7 @@
*/
#include "nodes.h"
+#include "ssa_builder.h"
#include "utils/growable_array.h"
namespace art {
@@ -34,7 +35,13 @@
if (!visited.IsBitSet(i)) {
HBasicBlock* block = blocks_.Get(i);
for (size_t j = 0; j < block->GetSuccessors()->Size(); j++) {
- block->GetSuccessors()->Get(j)->RemovePredecessor(block);
+ block->GetSuccessors()->Get(j)->RemovePredecessor(block, false);
+ }
+ 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());
}
}
}
@@ -120,11 +127,112 @@
}
}
-void HBasicBlock::AddInstruction(HInstruction* instruction) {
+void HGraph::TransformToSSA() {
+ DCHECK(!dominator_order_.IsEmpty());
+ SimplifyCFG();
+ SsaBuilder ssa_builder(this);
+ ssa_builder.BuildSsa();
+}
+
+void HGraph::SimplifyCFG() {
+ for (size_t i = 0; i < dominator_order_.Size(); i++) {
+ HBasicBlock* current = dominator_order_.Get(i);
+ if (current->IsLoopHeader()) {
+ // Make sure the loop has only one pre header. This simplifies SSA building by having
+ // to just look at the pre header to know which locals are initialized at entry of the
+ // loop.
+ HLoopInformation* info = current->GetLoopInformation();
+ size_t number_of_incomings = current->GetPredecessors()->Size() - info->NumberOfBackEdges();
+ if (number_of_incomings != 1) {
+ HBasicBlock* pre_header = new (arena_) HBasicBlock(this);
+ AddBlock(pre_header);
+ pre_header->AddInstruction(new (arena_) HGoto());
+ pre_header->SetDominator(current->GetDominator());
+ current->SetDominator(pre_header);
+ dominator_order_.InsertAt(i, pre_header);
+ i++;
+
+ ArenaBitVector back_edges(arena_, GetBlocks()->Size(), false);
+ for (size_t pred = 0; pred < info->GetBackEdges()->Size(); pred++) {
+ back_edges.SetBit(info->GetBackEdges()->Get(pred)->GetBlockId());
+ }
+ for (size_t pred = 0; pred < current->GetPredecessors()->Size(); pred++) {
+ HBasicBlock* predecessor = current->GetPredecessors()->Get(pred);
+ if (!back_edges.IsBitSet(predecessor->GetBlockId())) {
+ current->RemovePredecessor(predecessor);
+ pred--;
+ predecessor->AddSuccessor(pre_header);
+ }
+ }
+ pre_header->AddSuccessor(current);
+ }
+ info->SetPreHeader(current->GetDominator());
+ }
+ }
+}
+
+void HLoopInformation::SetPreHeader(HBasicBlock* block) {
+ DCHECK_EQ(header_->GetDominator(), block);
+ pre_header_ = block;
+}
+
+static void Add(HInstructionList* instruction_list,
+ HBasicBlock* block,
+ HInstruction* instruction) {
DCHECK(instruction->GetBlock() == nullptr);
DCHECK_EQ(instruction->GetId(), -1);
- instruction->SetBlock(this);
- instruction->SetId(GetGraph()->GetNextInstructionId());
+ instruction->SetBlock(block);
+ instruction->SetId(block->GetGraph()->GetNextInstructionId());
+ instruction_list->AddInstruction(instruction);
+}
+
+void HBasicBlock::AddInstruction(HInstruction* instruction) {
+ Add(&instructions_, this, instruction);
+}
+
+void HBasicBlock::AddPhi(HPhi* phi) {
+ Add(&phis_, this, phi);
+}
+
+static void Remove(HInstructionList* instruction_list,
+ HBasicBlock* block,
+ HInstruction* instruction) {
+ DCHECK_EQ(block, instruction->GetBlock());
+ DCHECK(instruction->GetUses() == nullptr);
+ DCHECK(instruction->GetEnvUses() == nullptr);
+ instruction->SetBlock(nullptr);
+ instruction_list->RemoveInstruction(instruction);
+
+ for (size_t i = 0; i < instruction->InputCount(); i++) {
+ instruction->InputAt(i)->RemoveUser(instruction, i);
+ }
+}
+
+void HBasicBlock::RemoveInstruction(HInstruction* instruction) {
+ Remove(&instructions_, this, instruction);
+}
+
+void HBasicBlock::RemovePhi(HPhi* phi) {
+ Remove(&phis_, this, phi);
+}
+
+void HInstruction::RemoveUser(HInstruction* user, size_t input_index) {
+ HUseListNode<HInstruction>* previous = nullptr;
+ HUseListNode<HInstruction>* current = uses_;
+ while (current != nullptr) {
+ if (current->GetUser() == user && current->GetIndex() == input_index) {
+ if (previous == NULL) {
+ uses_ = current->GetTail();
+ } else {
+ previous->SetTail(current->GetTail());
+ }
+ }
+ previous = current;
+ current = current->GetTail();
+ }
+}
+
+void HInstructionList::AddInstruction(HInstruction* instruction) {
if (first_instruction_ == nullptr) {
DCHECK(last_instruction_ == nullptr);
first_instruction_ = last_instruction_ = instruction;
@@ -133,11 +241,53 @@
instruction->previous_ = last_instruction_;
last_instruction_ = instruction;
}
- for (int i = 0; i < instruction->InputCount(); i++) {
- instruction->InputAt(i)->AddUse(instruction);
+ for (size_t i = 0; i < instruction->InputCount(); i++) {
+ instruction->InputAt(i)->AddUseAt(instruction, i);
}
}
+void HInstructionList::RemoveInstruction(HInstruction* instruction) {
+ if (instruction->previous_ != nullptr) {
+ instruction->previous_->next_ = instruction->next_;
+ }
+ if (instruction->next_ != nullptr) {
+ instruction->next_->previous_ = instruction->previous_;
+ }
+ if (instruction == first_instruction_) {
+ first_instruction_ = instruction->next_;
+ }
+ if (instruction == last_instruction_) {
+ last_instruction_ = instruction->previous_;
+ }
+}
+
+void HInstruction::ReplaceWith(HInstruction* other) {
+ for (HUseIterator<HInstruction> it(GetUses()); !it.Done(); it.Advance()) {
+ HUseListNode<HInstruction>* current = it.Current();
+ HInstruction* user = current->GetUser();
+ size_t input_index = current->GetIndex();
+ user->SetRawInputAt(input_index, other);
+ other->AddUseAt(user, input_index);
+ }
+
+ for (HUseIterator<HEnvironment> it(GetEnvUses()); !it.Done(); it.Advance()) {
+ HUseListNode<HEnvironment>* current = it.Current();
+ HEnvironment* user = current->GetUser();
+ size_t input_index = current->GetIndex();
+ user->SetRawEnvAt(input_index, other);
+ other->AddEnvUseAt(user, input_index);
+ }
+
+ uses_ = nullptr;
+ env_uses_ = nullptr;
+}
+
+void HPhi::AddInput(HInstruction* input) {
+ DCHECK(input->GetBlock() != nullptr);
+ inputs_.Add(input);
+ input->AddUseAt(this, inputs_.Size() - 1);
+}
+
#define DEFINE_ACCEPT(name) \
void H##name::Accept(HGraphVisitor* visitor) { \
visitor->Visit##name(this); \
@@ -155,7 +305,10 @@
}
void HGraphVisitor::VisitBasicBlock(HBasicBlock* block) {
- for (HInstructionIterator it(block); !it.Done(); it.Advance()) {
+ for (HInstructionIterator it(*block->GetPhis()); !it.Done(); it.Advance()) {
+ it.Current()->Accept(this);
+ }
+ for (HInstructionIterator it(*block->GetInstructions()); !it.Done(); it.Advance()) {
it.Current()->Accept(this);
}
}