Add conditional branches, and build dominator tree.

Change-Id: I4b151a07b72692961235a1419b54b6b45cf54e63

1 files changed, 94 insertions, 13 deletions

diff --git a/compiler/optimizing/builder.cc b/compiler/optimizing/builder.cc
index 2c1091c..e6db7bc 100644
--- a/compiler/optimizing/builder.cc
+++ b/compiler/optimizing/builder.cc
@@ -22,39 +22,120 @@
 namespace art {
 
 HGraph* HGraphBuilder::BuildGraph(const uint16_t* code_ptr, const uint16_t* code_end) {
+  // Setup the graph with the entry block and exit block.
   graph_ = new (arena_) HGraph(arena_);
-
   entry_block_ = new (arena_) HBasicBlock(graph_);
   graph_->AddBlock(entry_block_);
-
+  entry_block_->AddInstruction(new (arena_) HGoto());
   exit_block_ = new (arena_) HBasicBlock(graph_);
-  // The exit block is added at the end of this method to ensure
-  // its id is the greatest. This is needed for dominator computation.
-
-  entry_block_->AddInstruction(new (arena_) HGoto(entry_block_));
+  exit_block_->AddInstruction(new (arena_) HExit());
 
-  current_block_ = new (arena_) HBasicBlock(graph_);
-  graph_->AddBlock(current_block_);
-  entry_block_->AddSuccessor(current_block_);
+  // To avoid splitting blocks, we compute ahead of time the instructions that
+  // start a new block, and create these blocks.
+  ComputeBranchTargets(code_ptr, code_end);
 
+  size_t dex_offset = 0;
   while (code_ptr < code_end) {
+    // Update the current block if dex_offset starts a new block.
+    MaybeUpdateCurrentBlock(dex_offset);
     const Instruction& instruction = *Instruction::At(code_ptr);
-    if (!AnalyzeDexInstruction(instruction)) return nullptr;
+    if (!AnalyzeDexInstruction(instruction, dex_offset)) return nullptr;
+    dex_offset += instruction.SizeInCodeUnits();
     code_ptr += instruction.SizeInCodeUnits();
   }
 
-  exit_block_->AddInstruction(new (arena_) HExit(exit_block_));
+  // Add the exit block at the end to give it the highest id.
   graph_->AddBlock(exit_block_);
   return graph_;
 }
 
-bool HGraphBuilder::AnalyzeDexInstruction(const Instruction& instruction) {
+void HGraphBuilder::MaybeUpdateCurrentBlock(size_t index) {
+  HBasicBlock* block = FindBlockStartingAt(index);
+  if (block == nullptr) return;
+
+  if (current_block_ != nullptr) {
+    // Branching instructions clear current_block, so we know
+    // the last instruction of the current block is not a branching
+    // instruction. We add an unconditional goto to the found block.
+    current_block_->AddInstruction(new (arena_) HGoto());
+    current_block_->AddSuccessor(block);
+  }
+  graph_->AddBlock(block);
+  current_block_ = block;
+}
+
+void HGraphBuilder::ComputeBranchTargets(const uint16_t* code_ptr, const uint16_t* code_end) {
+  // TODO: Support switch instructions.
+  branch_targets_.SetSize(code_end - code_ptr);
+
+  // Create the first block for the dex instructions, single successor of the entry block.
+  HBasicBlock* block = new (arena_) HBasicBlock(graph_);
+  branch_targets_.Put(0, block);
+  entry_block_->AddSuccessor(block);
+
+  // Iterate over all instructions and find branching instructions. Create blocks for
+  // the locations these instructions branch to.
+  size_t dex_offset = 0;
+  while (code_ptr < code_end) {
+    const Instruction& instruction = *Instruction::At(code_ptr);
+    if (instruction.IsBranch()) {
+      int32_t target = instruction.GetTargetOffset() + dex_offset;
+      // Create a block for the target instruction.
+      if (FindBlockStartingAt(target) == nullptr) {
+        block = new (arena_) HBasicBlock(graph_);
+        branch_targets_.Put(target, block);
+      }
+      dex_offset += instruction.SizeInCodeUnits();
+      code_ptr += instruction.SizeInCodeUnits();
+      if ((code_ptr < code_end) && (FindBlockStartingAt(dex_offset) == nullptr)) {
+        block = new (arena_) HBasicBlock(graph_);
+        branch_targets_.Put(dex_offset, block);
+      }
+    } else {
+      code_ptr += instruction.SizeInCodeUnits();
+      dex_offset += instruction.SizeInCodeUnits();
+    }
+  }
+}
+
+HBasicBlock* HGraphBuilder::FindBlockStartingAt(int32_t index) const {
+  DCHECK_GE(index, 0);
+  return branch_targets_.Get(index);
+}
+
+bool HGraphBuilder::AnalyzeDexInstruction(const Instruction& instruction, int32_t dex_offset) {
+  if (current_block_ == nullptr) return true;  // Dead code
+
   switch (instruction.Opcode()) {
     case Instruction::RETURN_VOID:
-      current_block_->AddInstruction(new (arena_) HReturnVoid(current_block_));
+      current_block_->AddInstruction(new (arena_) HReturnVoid());
       current_block_->AddSuccessor(exit_block_);
       current_block_ = nullptr;
       break;
+    case Instruction::IF_EQ: {
+      // TODO: Read the dex register.
+      HBasicBlock* target = FindBlockStartingAt(instruction.GetTargetOffset() + dex_offset);
+      DCHECK(target != nullptr);
+      current_block_->AddInstruction(new (arena_) HIf());
+      current_block_->AddSuccessor(target);
+      target = FindBlockStartingAt(dex_offset + instruction.SizeInCodeUnits());
+      DCHECK(target != nullptr);
+      current_block_->AddSuccessor(target);
+      current_block_ = nullptr;
+      break;
+    }
+    case Instruction::GOTO:
+    case Instruction::GOTO_16:
+    case Instruction::GOTO_32: {
+      HBasicBlock* target = FindBlockStartingAt(instruction.GetTargetOffset() + dex_offset);
+      DCHECK(target != nullptr);
+      current_block_->AddInstruction(new (arena_) HGoto());
+      current_block_->AddSuccessor(target);
+      current_block_ = nullptr;
+      break;
+    }
+    case Instruction::NOP:
+      break;
     default:
       return false;
   }