Add a Transform to SSA phase to the optimizing compiler.

Change-Id: Ia9700756a0396d797a00b529896487d52c989329

1 files changed, 160 insertions, 7 deletions

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 @@ void HGraph::RemoveDeadBlocks(const ArenaBitVector& visited) const {
     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 HGraph::VisitBlockForDominatorTree(HBasicBlock* block,
   }
 }
 
-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,9 +241,51 @@ void HBasicBlock::AddInstruction(HInstruction* instruction) {
     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)                                                    \
@@ -155,7 +305,10 @@ void HGraphVisitor::VisitInsertionOrder() {
 }
 
 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);
   }
 }