Add conditional branches, and build dominator tree.
Change-Id: I4b151a07b72692961235a1419b54b6b45cf54e63
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.
+ exit_block_->AddInstruction(new (arena_) HExit());
- entry_block_->AddInstruction(new (arena_) HGoto(entry_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);
- current_block_ = new (arena_) HBasicBlock(graph_);
- graph_->AddBlock(current_block_);
- entry_block_->AddSuccessor(current_block_);
-
+ 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;
}