1 /* 2 * Copyright (C) 2013 The Android Open Source Project 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17 #include <llvm/Support/raw_ostream.h> 18 19 #include "base/logging.h" 20 #include "utils.h" 21 22 #include "sea_ir/ir/sea.h" 23 #include "sea_ir/code_gen/code_gen.h" 24 #include "sea_ir/types/type_inference.h" 25 #include "sea_ir/types/types.h" 26 27 namespace sea_ir { 28 29 void CodeGenPrepassVisitor::Visit(PhiInstructionNode* phi) { 30 Region* r = phi->GetRegion(); 31 const std::vector<Region*>* predecessors = r->GetPredecessors(); 32 DCHECK(NULL != predecessors); 33 DCHECK_GT(predecessors->size(), 0u); 34 llvm::PHINode *llvm_phi = llvm_data_->builder_.CreatePHI( 35 llvm::Type::getInt32Ty(*llvm_data_->context_), predecessors->size(), phi->StringId()); 36 llvm_data_->AddValue(phi, llvm_phi); 37 } 38 39 void CodeGenPassVisitor::Initialize(SeaGraph* graph) { 40 Region* root_region; 41 ordered_regions_.clear(); 42 for (std::vector<Region*>::const_iterator cit = graph->GetRegions()->begin(); 43 cit != graph->GetRegions()->end(); cit++ ) { 44 if ((*cit)->GetIDominator() == (*cit)) { 45 root_region = *cit; 46 } 47 } 48 ordered_regions_.push_back(root_region); 49 for (unsigned int id = 0; id < ordered_regions_.size(); id++) { 50 Region* current_region = ordered_regions_.at(id); 51 const std::set<Region*>* dominated_regions = current_region->GetIDominatedSet(); 52 for (std::set<Region*>::const_iterator cit = dominated_regions->begin(); 53 cit != dominated_regions->end(); cit++ ) { 54 ordered_regions_.push_back(*cit); 55 } 56 } 57 } 58 59 void CodeGenPostpassVisitor::Visit(SeaGraph* graph) { } 60 void CodeGenVisitor::Visit(SeaGraph* graph) { } 61 void CodeGenPrepassVisitor::Visit(SeaGraph* graph) { 62 std::vector<SignatureNode*>* parameters = graph->GetParameterNodes(); 63 // TODO: It may be better to extract correct types from dex 64 // instead than from type inference. 65 DCHECK(parameters != NULL); 66 std::vector<llvm::Type*> parameter_types; 67 for (std::vector<SignatureNode*>::const_iterator param_iterator = parameters->begin(); 68 param_iterator!= parameters->end(); param_iterator++) { 69 const Type* param_type = graph->ti_->type_data_.FindTypeOf((*param_iterator)->Id()); 70 DCHECK(param_type->Equals(graph->ti_->type_cache_->Integer())) 71 << "Code generation for types other than integer not implemented."; 72 parameter_types.push_back(llvm::Type::getInt32Ty(*llvm_data_->context_)); 73 } 74 75 // TODO: Get correct function return type. 76 const Type* return_type = graph->ti_->type_data_.FindTypeOf(-1); 77 DCHECK(return_type->Equals(graph->ti_->type_cache_->Integer())) 78 << "Code generation for types other than integer not implemented."; 79 llvm::FunctionType *function_type = llvm::FunctionType::get( 80 llvm::Type::getInt32Ty(*llvm_data_->context_), 81 parameter_types, false); 82 83 llvm_data_->function_ = llvm::Function::Create(function_type, 84 llvm::Function::ExternalLinkage, function_name_, &llvm_data_->module_); 85 unsigned param_id = 0; 86 for (llvm::Function::arg_iterator arg_it = llvm_data_->function_->arg_begin(); 87 param_id != llvm_data_->function_->arg_size(); ++arg_it, ++param_id) { 88 // TODO: The "+1" is because of the Method parameter on position 0. 89 DCHECK(parameters->size() > param_id) << "Insufficient parameters for function signature"; 90 // Build parameter register name for LLVM IR clarity. 91 std::string arg_name = art::StringPrintf("r%d", parameters->at(param_id)->GetResultRegister()); 92 arg_it->setName(arg_name); 93 SignatureNode* parameter = parameters->at(param_id); 94 llvm_data_->AddValue(parameter, arg_it); 95 } 96 97 std::vector<Region*>* regions = &ordered_regions_; 98 DCHECK_GT(regions->size(), 0u); 99 // Then create all other basic blocks. 100 for (std::vector<Region*>::const_iterator cit = regions->begin(); cit != regions->end(); cit++) { 101 llvm::BasicBlock* new_basic_block = llvm::BasicBlock::Create(*llvm_data_->context_, 102 (*cit)->StringId(), llvm_data_->function_); 103 llvm_data_->AddBlock((*cit), new_basic_block); 104 } 105 } 106 107 void CodeGenPrepassVisitor::Visit(Region* region) { 108 llvm_data_->builder_.SetInsertPoint(llvm_data_->GetBlock(region)); 109 } 110 void CodeGenPostpassVisitor::Visit(Region* region) { 111 llvm_data_->builder_.SetInsertPoint(llvm_data_->GetBlock(region)); 112 } 113 void CodeGenVisitor::Visit(Region* region) { 114 llvm_data_->builder_.SetInsertPoint(llvm_data_->GetBlock(region)); 115 } 116 117 118 void CodeGenVisitor::Visit(InstructionNode* instruction) { 119 std::string instr = instruction->GetInstruction()->DumpString(NULL); 120 DCHECK(0); // This whole function is useful only during development. 121 } 122 123 void CodeGenVisitor::Visit(UnnamedConstInstructionNode* instruction) { 124 std::string instr = instruction->GetInstruction()->DumpString(NULL); 125 std::cout << "1.Instruction: " << instr << std::endl; 126 llvm_data_->AddValue(instruction, 127 llvm::ConstantInt::get(*llvm_data_->context_, llvm::APInt(32, instruction->GetConstValue()))); 128 } 129 130 void CodeGenVisitor::Visit(ConstInstructionNode* instruction) { 131 std::string instr = instruction->GetInstruction()->DumpString(NULL); 132 std::cout << "1.Instruction: " << instr << std::endl; 133 llvm_data_->AddValue(instruction, 134 llvm::ConstantInt::get(*llvm_data_->context_, llvm::APInt(32, instruction->GetConstValue()))); 135 } 136 void CodeGenVisitor::Visit(ReturnInstructionNode* instruction) { 137 std::string instr = instruction->GetInstruction()->DumpString(NULL); 138 std::cout << "2.Instruction: " << instr << std::endl; 139 DCHECK_GT(instruction->GetSSAProducers().size(), 0u); 140 llvm::Value* return_value = llvm_data_->GetValue(instruction->GetSSAProducers().at(0)); 141 llvm_data_->builder_.CreateRet(return_value); 142 } 143 void CodeGenVisitor::Visit(IfNeInstructionNode* instruction) { 144 std::string instr = instruction->GetInstruction()->DumpString(NULL); 145 std::cout << "3.Instruction: " << instr << std::endl; 146 std::vector<InstructionNode*> ssa_uses = instruction->GetSSAProducers(); 147 DCHECK_GT(ssa_uses.size(), 1u); 148 InstructionNode* use_l = ssa_uses.at(0); 149 llvm::Value* left = llvm_data_->GetValue(use_l); 150 151 InstructionNode* use_r = ssa_uses.at(1); 152 llvm::Value* right = llvm_data_->GetValue(use_r); 153 llvm::Value* ifne = llvm_data_->builder_.CreateICmpNE(left, right, instruction->StringId()); 154 DCHECK(instruction->GetRegion() != NULL); 155 std::vector<Region*>* successors = instruction->GetRegion()->GetSuccessors(); 156 DCHECK_GT(successors->size(), 0u); 157 llvm::BasicBlock* then_block = llvm_data_->GetBlock(successors->at(0)); 158 llvm::BasicBlock* else_block = llvm_data_->GetBlock(successors->at(1)); 159 160 llvm_data_->builder_.CreateCondBr(ifne, then_block, else_block); 161 } 162 163 /* 164 void CodeGenVisitor::Visit(AddIntLitInstructionNode* instruction) { 165 std::string instr = instruction->GetInstruction()->DumpString(NULL); 166 std::cout << "4.Instruction: " << instr << std::endl; 167 std::vector<InstructionNode*> ssa_uses = instruction->GetSSAUses(); 168 InstructionNode* use_l = ssa_uses.at(0); 169 llvm::Value* left = llvm_data->GetValue(use_l); 170 llvm::Value* right = llvm::ConstantInt::get(*llvm_data->context_, 171 llvm::APInt(32, instruction->GetConstValue())); 172 llvm::Value* result = llvm_data->builder_.CreateAdd(left, right); 173 llvm_data->AddValue(instruction, result); 174 } 175 */ 176 void CodeGenVisitor::Visit(MoveResultInstructionNode* instruction) { 177 std::string instr = instruction->GetInstruction()->DumpString(NULL); 178 std::cout << "5.Instruction: " << instr << std::endl; 179 // TODO: Currently, this "mov" instruction is simulated by "res = return_register + 0". 180 // This is inefficient, but should be optimized out by the coalescing phase of the reg alloc. 181 // The TODO is to either ensure that this happens, or to 182 // remove the move-result instructions completely from the IR 183 // by merging them with the invoke-* instructions, 184 // since their purpose of minimizing the number of opcodes in dex is 185 // not relevant for the IR. (Will need to have different 186 // instruction subclasses for functions and procedures.) 187 std::vector<InstructionNode*> ssa_uses = instruction->GetSSAProducers(); 188 InstructionNode* use_l = ssa_uses.at(0); 189 llvm::Value* left = llvm_data_->GetValue(use_l); 190 llvm::Value* right = llvm::ConstantInt::get(*llvm_data_->context_, llvm::APInt(32, 0)); 191 llvm::Value* result = llvm_data_->builder_.CreateAdd(left, right); 192 llvm_data_->AddValue(instruction, result); 193 } 194 void CodeGenVisitor::Visit(InvokeStaticInstructionNode* invoke) { 195 std::string instr = invoke->GetInstruction()->DumpString(NULL); 196 std::cout << "6.Instruction: " << instr << std::endl; 197 // TODO: Build callee LLVM function name. 198 std::string symbol = "dex_"; 199 symbol += art::MangleForJni(PrettyMethod(invoke->GetCalledMethodIndex(), dex_file_)); 200 std::string function_name = "dex_int_00020Main_fibonacci_00028int_00029"; 201 llvm::Function *callee = llvm_data_->module_.getFunction(function_name); 202 // TODO: Add proper checking of the matching between formal and actual signature. 203 DCHECK(NULL != callee); 204 std::vector<llvm::Value*> parameter_values; 205 std::vector<InstructionNode*> parameter_sources = invoke->GetSSAProducers(); 206 // TODO: Replace first parameter with Method argument instead of 0. 207 parameter_values.push_back(llvm::ConstantInt::get(*llvm_data_->context_, llvm::APInt(32, 0))); 208 for (std::vector<InstructionNode*>::const_iterator cit = parameter_sources.begin(); 209 cit != parameter_sources.end(); ++cit) { 210 llvm::Value* parameter_value = llvm_data_->GetValue((*cit)); 211 DCHECK(NULL != parameter_value); 212 parameter_values.push_back(parameter_value); 213 } 214 llvm::Value* return_value = llvm_data_->builder_.CreateCall(callee, 215 parameter_values, invoke->StringId()); 216 llvm_data_->AddValue(invoke, return_value); 217 } 218 void CodeGenVisitor::Visit(AddIntInstructionNode* instruction) { 219 std::string instr = instruction->GetInstruction()->DumpString(NULL); 220 std::cout << "7.Instruction: " << instr << std::endl; 221 std::vector<InstructionNode*> ssa_uses = instruction->GetSSAProducers(); 222 DCHECK_GT(ssa_uses.size(), 1u); 223 InstructionNode* use_l = ssa_uses.at(0); 224 InstructionNode* use_r = ssa_uses.at(1); 225 llvm::Value* left = llvm_data_->GetValue(use_l); 226 llvm::Value* right = llvm_data_->GetValue(use_r); 227 llvm::Value* result = llvm_data_->builder_.CreateAdd(left, right); 228 llvm_data_->AddValue(instruction, result); 229 } 230 void CodeGenVisitor::Visit(GotoInstructionNode* instruction) { 231 std::string instr = instruction->GetInstruction()->DumpString(NULL); 232 std::cout << "8.Instruction: " << instr << std::endl; 233 std::vector<sea_ir::Region*>* targets = instruction->GetRegion()->GetSuccessors(); 234 DCHECK_EQ(targets->size(), 1u); 235 llvm::BasicBlock* target_block = llvm_data_->GetBlock(targets->at(0)); 236 llvm_data_->builder_.CreateBr(target_block); 237 } 238 void CodeGenVisitor::Visit(IfEqzInstructionNode* instruction) { 239 std::string instr = instruction->GetInstruction()->DumpString(NULL); 240 std::cout << "9. Instruction: " << instr << "; Id: " <<instruction << std::endl; 241 std::vector<InstructionNode*> ssa_uses = instruction->GetSSAProducers(); 242 DCHECK_GT(ssa_uses.size(), 0u); 243 InstructionNode* use_l = ssa_uses.at(0); 244 llvm::Value* left = llvm_data_->GetValue(use_l); 245 llvm::Value* ifeqz = llvm_data_->builder_.CreateICmpEQ(left, 246 llvm::ConstantInt::get(*llvm_data_->context_, llvm::APInt::getNullValue(32)), 247 instruction->StringId()); 248 DCHECK(instruction->GetRegion() != NULL); 249 std::vector<Region*>* successors = instruction->GetRegion()->GetSuccessors(); 250 DCHECK_GT(successors->size(), 0u); 251 llvm::BasicBlock* then_block = llvm_data_->GetBlock(successors->at(0)); 252 llvm::BasicBlock* else_block = llvm_data_->GetBlock(successors->at(1)); 253 llvm_data_->builder_.CreateCondBr(ifeqz, then_block, else_block); 254 } 255 256 void CodeGenPostpassVisitor::Visit(PhiInstructionNode* phi) { 257 std::cout << "10. Instruction: Phi(" << phi->GetRegisterNumber() << ")" << std::endl; 258 Region* r = phi->GetRegion(); 259 const std::vector<Region*>* predecessors = r->GetPredecessors(); 260 DCHECK(NULL != predecessors); 261 DCHECK_GT(predecessors->size(), 0u); 262 // Prepass (CodeGenPrepassVisitor) should create the phi function value. 263 llvm::PHINode* llvm_phi = (llvm::PHINode*) llvm_data_->GetValue(phi); 264 int predecessor_pos = 0; 265 for (std::vector<Region*>::const_iterator cit = predecessors->begin(); 266 cit != predecessors->end(); ++cit) { 267 std::vector<InstructionNode*>* defining_instructions = phi->GetSSAUses(predecessor_pos++); 268 DCHECK_EQ(defining_instructions->size(), 1u); 269 InstructionNode* defining_instruction = defining_instructions->at(0); 270 DCHECK(NULL != defining_instruction); 271 Region* incoming_region = *cit; 272 llvm::BasicBlock* incoming_basic_block = llvm_data_->GetBlock(incoming_region); 273 llvm::Value* incoming_value = llvm_data_->GetValue(defining_instruction); 274 llvm_phi->addIncoming(incoming_value, incoming_basic_block); 275 } 276 } 277 278 void CodeGenVisitor::Visit(SignatureNode* signature) { 279 DCHECK_EQ(signature->GetDefinitions().size(), 1u) << 280 "Signature nodes must correspond to a single parameter register."; 281 } 282 void CodeGenPrepassVisitor::Visit(SignatureNode* signature) { 283 DCHECK_EQ(signature->GetDefinitions().size(), 1u) << 284 "Signature nodes must correspond to a single parameter register."; 285 } 286 void CodeGenPostpassVisitor::Visit(SignatureNode* signature) { 287 DCHECK_EQ(signature->GetDefinitions().size(), 1u) << 288 "Signature nodes must correspond to a single parameter register."; 289 } 290 291 } // namespace sea_ir 292
