builder.cc revision d4dd255db1d110ceb5551f6d95ff31fb57420994
1edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep/* 2edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep * 3edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep * Copyright (C) 2014 The Android Open Source Project 4edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep * 5edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep * Licensed under the Apache License, Version 2.0 (the "License"); 6edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep * you may not use this file except in compliance with the License. 7edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep * You may obtain a copy of the License at 8edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep * 9edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep * http://www.apache.org/licenses/LICENSE-2.0 10edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep * 11edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep * Unless required by applicable law or agreed to in writing, software 12edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep * distributed under the License is distributed on an "AS IS" BASIS, 13edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 14edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep * See the License for the specific language governing permissions and 15edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep * limitations under the License. 16edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep */ 17edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 18edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep#include "dex_instruction.h" 19edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep#include "builder.h" 20edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep#include "nodes.h" 21edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 22edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoepnamespace art { 23edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 24edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander StoepHGraph* HGraphBuilder::BuildGraph(const uint16_t* code_ptr, const uint16_t* code_end) { 25edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep // Setup the graph with the entry block and exit block. 26edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep graph_ = new (arena_) HGraph(arena_); 27edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep entry_block_ = new (arena_) HBasicBlock(graph_); 28edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep graph_->AddBlock(entry_block_); 29edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep entry_block_->AddInstruction(new (arena_) HGoto()); 30edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep exit_block_ = new (arena_) HBasicBlock(graph_); 31edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep exit_block_->AddInstruction(new (arena_) HExit()); 32edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep graph_->set_entry_block(entry_block_); 33edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep graph_->set_exit_block(exit_block_); 34edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 35edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep // To avoid splitting blocks, we compute ahead of time the instructions that 36edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep // start a new block, and create these blocks. 37edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep ComputeBranchTargets(code_ptr, code_end); 38edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 39edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep size_t dex_offset = 0; 40edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep while (code_ptr < code_end) { 41edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep // Update the current block if dex_offset starts a new block. 42 MaybeUpdateCurrentBlock(dex_offset); 43 const Instruction& instruction = *Instruction::At(code_ptr); 44 if (!AnalyzeDexInstruction(instruction, dex_offset)) return nullptr; 45 dex_offset += instruction.SizeInCodeUnits(); 46 code_ptr += instruction.SizeInCodeUnits(); 47 } 48 49 // Add the exit block at the end to give it the highest id. 50 graph_->AddBlock(exit_block_); 51 return graph_; 52} 53 54void HGraphBuilder::MaybeUpdateCurrentBlock(size_t index) { 55 HBasicBlock* block = FindBlockStartingAt(index); 56 if (block == nullptr) return; 57 58 if (current_block_ != nullptr) { 59 // Branching instructions clear current_block, so we know 60 // the last instruction of the current block is not a branching 61 // instruction. We add an unconditional goto to the found block. 62 current_block_->AddInstruction(new (arena_) HGoto()); 63 current_block_->AddSuccessor(block); 64 } 65 graph_->AddBlock(block); 66 current_block_ = block; 67} 68 69void HGraphBuilder::ComputeBranchTargets(const uint16_t* code_ptr, const uint16_t* code_end) { 70 // TODO: Support switch instructions. 71 branch_targets_.SetSize(code_end - code_ptr); 72 73 // Create the first block for the dex instructions, single successor of the entry block. 74 HBasicBlock* block = new (arena_) HBasicBlock(graph_); 75 branch_targets_.Put(0, block); 76 entry_block_->AddSuccessor(block); 77 78 // Iterate over all instructions and find branching instructions. Create blocks for 79 // the locations these instructions branch to. 80 size_t dex_offset = 0; 81 while (code_ptr < code_end) { 82 const Instruction& instruction = *Instruction::At(code_ptr); 83 if (instruction.IsBranch()) { 84 int32_t target = instruction.GetTargetOffset() + dex_offset; 85 // Create a block for the target instruction. 86 if (FindBlockStartingAt(target) == nullptr) { 87 block = new (arena_) HBasicBlock(graph_); 88 branch_targets_.Put(target, block); 89 } 90 dex_offset += instruction.SizeInCodeUnits(); 91 code_ptr += instruction.SizeInCodeUnits(); 92 if ((code_ptr < code_end) && (FindBlockStartingAt(dex_offset) == nullptr)) { 93 block = new (arena_) HBasicBlock(graph_); 94 branch_targets_.Put(dex_offset, block); 95 } 96 } else { 97 code_ptr += instruction.SizeInCodeUnits(); 98 dex_offset += instruction.SizeInCodeUnits(); 99 } 100 } 101} 102 103HBasicBlock* HGraphBuilder::FindBlockStartingAt(int32_t index) const { 104 DCHECK_GE(index, 0); 105 return branch_targets_.Get(index); 106} 107 108bool HGraphBuilder::AnalyzeDexInstruction(const Instruction& instruction, int32_t dex_offset) { 109 if (current_block_ == nullptr) return true; // Dead code 110 111 switch (instruction.Opcode()) { 112 case Instruction::RETURN_VOID: 113 current_block_->AddInstruction(new (arena_) HReturnVoid()); 114 current_block_->AddSuccessor(exit_block_); 115 current_block_ = nullptr; 116 break; 117 case Instruction::IF_EQ: { 118 // TODO: Read the dex register. 119 HBasicBlock* target = FindBlockStartingAt(instruction.GetTargetOffset() + dex_offset); 120 DCHECK(target != nullptr); 121 current_block_->AddInstruction(new (arena_) HIf()); 122 current_block_->AddSuccessor(target); 123 target = FindBlockStartingAt(dex_offset + instruction.SizeInCodeUnits()); 124 DCHECK(target != nullptr); 125 current_block_->AddSuccessor(target); 126 current_block_ = nullptr; 127 break; 128 } 129 case Instruction::GOTO: 130 case Instruction::GOTO_16: 131 case Instruction::GOTO_32: { 132 HBasicBlock* target = FindBlockStartingAt(instruction.GetTargetOffset() + dex_offset); 133 DCHECK(target != nullptr); 134 current_block_->AddInstruction(new (arena_) HGoto()); 135 current_block_->AddSuccessor(target); 136 current_block_ = nullptr; 137 break; 138 } 139 case Instruction::NOP: 140 break; 141 default: 142 return false; 143 } 144 return true; 145} 146 147} // namespace art 148