Added code generation framework.
visitors.h: Contains only IR visitor declarations for now.
code_gen.h: Code generation vistor declaration (needs llvm).
code_gen.cc:Code generation visitor implementation (needs llvm).
instruction_nodes.h: Classes for each type of instruction; this
enables the visitor to visit each instruction differently and
corresponds to the sea of nodes paper.
sea_node.h : Moved base Sea IR Node to this separate header.
Replaced NO_REGISTER with enum (including RETURN_REGISTER)
sea.cc: Addded code generation call.
Set parent region for SignatureNodes.
Propagate method and class ids in IR generation routine.
Create InstructionNode subclasses.
*.mk: Updated to support the new files. Fixed some pre-existing formatting.
instruction_tools.h: Fixed double-define of NO_REGISTER to
refer to the new enum.
dex_instruction.cc: Added support for one more instruction in
HasRegXX and VRegXX functions.
Change-Id: I7c78f603e41df7bf9da5b77951b8485dd1b49200
diff --git a/compiler/sea_ir/code_gen.cc b/compiler/sea_ir/code_gen.cc
new file mode 100644
index 0000000..0bb3a26
--- /dev/null
+++ b/compiler/sea_ir/code_gen.cc
@@ -0,0 +1,282 @@
+/*
+ * Copyright (C) 2013 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include <llvm/Support/raw_ostream.h>
+#include "sea.h"
+#include "code_gen.h"
+
+namespace sea_ir {
+
+void CodeGenPrepassVisitor::Visit(PhiInstructionNode* phi) {
+ Region* r = phi->GetRegion();
+ const std::vector<Region*>* predecessors = r->GetPredecessors();
+ DCHECK(NULL != predecessors);
+ DCHECK_GT(predecessors->size(), 0u);
+ llvm::PHINode *llvm_phi = llvm_data_->builder_.CreatePHI(
+ llvm::Type::getInt32Ty(*llvm_data_->context_), predecessors->size(), phi->StringId());
+ llvm_data_->AddValue(phi, llvm_phi);
+}
+
+void CodeGenPassVisitor::Initialize(SeaGraph* graph) {
+ Region* root_region;
+ ordered_regions_.clear();
+ for (std::vector<Region*>::const_iterator cit = graph->GetRegions()->begin();
+ cit != graph->GetRegions()->end(); cit++ ) {
+ if ((*cit)->GetIDominator() == (*cit)) {
+ root_region = *cit;
+ }
+ }
+ ordered_regions_.push_back(root_region);
+ for (unsigned int id = 0; id < ordered_regions_.size(); id++) {
+ Region* current_region = ordered_regions_.at(id);
+ const std::set<Region*>* dominated_regions = current_region->GetIDominatedSet();
+ for (std::set<Region*>::const_iterator cit = dominated_regions->begin();
+ cit != dominated_regions->end(); cit++ ) {
+ ordered_regions_.push_back(*cit);
+ }
+ }
+}
+
+void CodeGenPostpassVisitor::Visit(SeaGraph* graph) {
+ std::vector<SignatureNode*>* parameters = graph->GetParameterNodes();
+ std::cout << "=== SeaGraph ===" << parameters->size() << std::endl;
+}
+void CodeGenVisitor::Visit(SeaGraph* graph) {
+ std::vector<SignatureNode*>* parameters = graph->GetParameterNodes();
+ std::cout << "=== SeaGraph ===" << parameters->size() << std::endl;
+}
+void CodeGenPrepassVisitor::Visit(SeaGraph* graph) {
+ std::vector<SignatureNode*>* parameters = graph->GetParameterNodes();
+ std::cout << "=== SeaGraph ===" << parameters->size() << std::endl;
+ // TODO: Extract correct types from dex for params and return value.
+ DCHECK(parameters != NULL);
+ std::vector<llvm::Type*> parameter_types(parameters->size(),
+ llvm::Type::getInt32Ty(*llvm_data_->context_));
+ // Build llvm function name.
+ std::string function_name = "class=";
+ std::stringstream ss;
+ ss << graph->class_def_idx_ << "_method=" << graph->method_idx_;
+ function_name.append(ss.str());
+
+ // Build llvm function type and parameters.
+ llvm::FunctionType *function_type = llvm::FunctionType::get(
+ llvm::Type::getInt32Ty(*llvm_data_->context_),
+ parameter_types, false);
+ llvm_data_->function_ = llvm::Function::Create(function_type,
+ llvm::Function::ExternalLinkage, function_name, &llvm_data_->module_);
+ unsigned param_id = 0;
+ for (llvm::Function::arg_iterator arg_it = llvm_data_->function_->arg_begin();
+ param_id != llvm_data_->function_->arg_size(); ++arg_it, ++param_id) {
+ DCHECK(parameters->size() > param_id) << "Insufficient parameters for function signature";
+ // Build parameter register name for LLVM IR clarity.
+ std::stringstream ss;
+ ss << "r" << parameters->at(param_id);
+ std::string arg_name;
+ arg_name.append(ss.str());
+ arg_it->setName(arg_name);
+ SignatureNode* parameter = parameters->at(param_id);
+ llvm_data_->AddValue(parameter, arg_it);
+ }
+
+ std::vector<Region*>* regions = &ordered_regions_;
+ DCHECK_GT(regions->size(), 0u);
+ // Then create all other basic blocks.
+ for (std::vector<Region*>::const_iterator cit = regions->begin(); cit != regions->end(); cit++) {
+ llvm::BasicBlock* new_basic_block = llvm::BasicBlock::Create(*llvm_data_->context_,
+ (*cit)->StringId(), llvm_data_->function_);
+ llvm_data_->AddBlock((*cit), new_basic_block);
+ }
+}
+
+void CodeGenPrepassVisitor::Visit(Region* region) {
+ std::cout << " == Region " << region->StringId() << " ==" << std::endl;
+ llvm_data_->builder_.SetInsertPoint(llvm_data_->GetBlock(region));
+}
+void CodeGenPostpassVisitor::Visit(Region* region) {
+ std::cout << " == Region " << region->StringId() << " ==" << std::endl;
+ llvm_data_->builder_.SetInsertPoint(llvm_data_->GetBlock(region));
+}
+void CodeGenVisitor::Visit(Region* region) {
+ std::cout << " == Region " << region->StringId() << " ==" << std::endl;
+ llvm_data_->builder_.SetInsertPoint(llvm_data_->GetBlock(region));
+}
+
+
+void CodeGenVisitor::Visit(InstructionNode* instruction) {
+ std::string instr = instruction->GetInstruction()->DumpString(NULL);
+ DCHECK(0); // This whole function is useful only during development.
+}
+void CodeGenVisitor::Visit(ConstInstructionNode* instruction) {
+ std::string instr = instruction->GetInstruction()->DumpString(NULL);
+ std::cout << "1.Instruction: " << instr << std::endl;
+ llvm_data_->AddValue(instruction,
+ llvm::ConstantInt::get(*llvm_data_->context_, llvm::APInt(32, instruction->GetConstValue())));
+}
+void CodeGenVisitor::Visit(ReturnInstructionNode* instruction) {
+ std::string instr = instruction->GetInstruction()->DumpString(NULL);
+ std::cout << "2.Instruction: " << instr << std::endl;
+ DCHECK_GT(instruction->GetSSAUses().size(), 0u);
+ llvm::Value* return_value = llvm_data_->GetValue(instruction->GetSSAUses().at(0));
+ llvm_data_->builder_.CreateRet(return_value);
+}
+void CodeGenVisitor::Visit(IfNeInstructionNode* instruction) {
+ std::string instr = instruction->GetInstruction()->DumpString(NULL);
+ std::cout << "3.Instruction: " << instr << std::endl;
+ std::vector<InstructionNode*> ssa_uses = instruction->GetSSAUses();
+ DCHECK_GT(ssa_uses.size(), 1u);
+ InstructionNode* use_l = ssa_uses.at(0);
+ llvm::Value* left = llvm_data_->GetValue(use_l);
+
+ InstructionNode* use_r = ssa_uses.at(1);
+ llvm::Value* right = llvm_data_->GetValue(use_r);
+ llvm::Value* ifne = llvm_data_->builder_.CreateICmpNE(left, right, instruction->StringId());
+ DCHECK(instruction->GetRegion() != NULL);
+ std::vector<Region*>* successors = instruction->GetRegion()->GetSuccessors();
+ DCHECK_GT(successors->size(), 0u);
+ llvm::BasicBlock* then_block = llvm_data_->GetBlock(successors->at(0));
+ llvm::BasicBlock* else_block = llvm_data_->GetBlock(successors->at(1));
+
+ llvm_data_->builder_.CreateCondBr(ifne, then_block, else_block);
+}
+
+/*
+void CodeGenVisitor::Visit(AddIntLitInstructionNode* instruction) {
+ std::string instr = instruction->GetInstruction()->DumpString(NULL);
+ std::cout << "4.Instruction: " << instr << std::endl;
+ std::vector<InstructionNode*> ssa_uses = instruction->GetSSAUses();
+ InstructionNode* use_l = ssa_uses.at(0);
+ llvm::Value* left = llvm_data->GetValue(use_l);
+ llvm::Value* right = llvm::ConstantInt::get(*llvm_data->context_,
+ llvm::APInt(32, instruction->GetConstValue()));
+ llvm::Value* result = llvm_data->builder_.CreateAdd(left, right);
+ llvm_data->AddValue(instruction, result);
+}
+*/
+void CodeGenVisitor::Visit(MoveResultInstructionNode* instruction) {
+ std::string instr = instruction->GetInstruction()->DumpString(NULL);
+ std::cout << "5.Instruction: " << instr << std::endl;
+ // TODO: Currently, this "mov" instruction is simulated by "res = return_register + 0".
+ // This is inefficient, but should be optimized out by the coalescing phase of the reg alloc.
+ // The TODO is to either ensure that this happens, or to
+ // remove the move-result instructions completely from the IR
+ // by merging them with the invoke-* instructions,
+ // since their purpose of minimizing the number of opcodes in dex is
+ // not relevant for the IR. (Will need to have different
+ // instruction subclasses for functions and procedures.)
+ std::vector<InstructionNode*> ssa_uses = instruction->GetSSAUses();
+ InstructionNode* use_l = ssa_uses.at(0);
+ llvm::Value* left = llvm_data_->GetValue(use_l);
+ llvm::Value* right = llvm::ConstantInt::get(*llvm_data_->context_, llvm::APInt(32, 0));
+ llvm::Value* result = llvm_data_->builder_.CreateAdd(left, right);
+ llvm_data_->AddValue(instruction, result);
+}
+void CodeGenVisitor::Visit(InvokeStaticInstructionNode* invoke) {
+ std::string instr = invoke->GetInstruction()->DumpString(NULL);
+ std::cout << "6.Instruction: " << instr << std::endl;
+ // TODO: Build callee llvm function name.
+ std::string function_name = "class=";
+ std::stringstream ss;
+ ss << 0 << "_method=" << 1;
+ function_name.append(ss.str());
+ llvm::Function *callee = llvm_data_->module_.getFunction(function_name);
+ // TODO: Add proper checking of the matching between formal and actual signature.
+ DCHECK(NULL != callee);
+ std::vector<llvm::Value*> parameter_values;
+ std::vector<InstructionNode*> parameter_sources = invoke->GetSSAUses();
+ for (std::vector<InstructionNode*>::const_iterator cit = parameter_sources.begin();
+ cit != parameter_sources.end(); ++cit) {
+ llvm::Value* parameter_value = llvm_data_->GetValue((*cit));
+ DCHECK(NULL != parameter_value);
+ parameter_values.push_back(parameter_value);
+ }
+ llvm::Value* return_value = llvm_data_->builder_.CreateCall(callee,
+ parameter_values, invoke->StringId());
+ llvm_data_->AddValue(invoke, return_value);
+}
+void CodeGenVisitor::Visit(AddIntInstructionNode* instruction) {
+ std::string instr = instruction->GetInstruction()->DumpString(NULL);
+ std::cout << "7.Instruction: " << instr << std::endl;
+ std::vector<InstructionNode*> ssa_uses = instruction->GetSSAUses();
+ DCHECK_GT(ssa_uses.size(), 1u);
+ InstructionNode* use_l = ssa_uses.at(0);
+ InstructionNode* use_r = ssa_uses.at(1);
+ llvm::Value* left = llvm_data_->GetValue(use_l);
+ llvm::Value* right = llvm_data_->GetValue(use_r);
+ llvm::Value* result = llvm_data_->builder_.CreateAdd(left, right);
+ llvm_data_->AddValue(instruction, result);
+}
+void CodeGenVisitor::Visit(GotoInstructionNode* instruction) {
+ std::string instr = instruction->GetInstruction()->DumpString(NULL);
+ std::cout << "8.Instruction: " << instr << std::endl;
+ std::vector<sea_ir::Region*>* targets = instruction->GetRegion()->GetSuccessors();
+ DCHECK_EQ(targets->size(), 1u);
+ llvm::BasicBlock* target_block = llvm_data_->GetBlock(targets->at(0));
+ llvm_data_->builder_.CreateBr(target_block);
+}
+void CodeGenVisitor::Visit(IfEqzInstructionNode* instruction) {
+ std::string instr = instruction->GetInstruction()->DumpString(NULL);
+ std::cout << "9. Instruction: " << instr << "; Id: " <<instruction << std::endl;
+ std::vector<InstructionNode*> ssa_uses = instruction->GetSSAUses();
+ DCHECK_GT(ssa_uses.size(), 0u);
+ InstructionNode* use_l = ssa_uses.at(0);
+ llvm::Value* left = llvm_data_->GetValue(use_l);
+ llvm::Value* ifeqz = llvm_data_->builder_.CreateICmpEQ(left,
+ llvm::ConstantInt::get(*llvm_data_->context_, llvm::APInt::getNullValue(32)),
+ instruction->StringId());
+ DCHECK(instruction->GetRegion() != NULL);
+ std::vector<Region*>* successors = instruction->GetRegion()->GetSuccessors();
+ DCHECK_GT(successors->size(), 0u);
+ llvm::BasicBlock* then_block = llvm_data_->GetBlock(successors->at(0));
+ llvm::BasicBlock* else_block = llvm_data_->GetBlock(successors->at(1));
+ llvm_data_->builder_.CreateCondBr(ifeqz, then_block, else_block);
+}
+
+void CodeGenPostpassVisitor::Visit(PhiInstructionNode* phi) {
+ std::cout << "Phi node for: " << phi->GetRegisterNumber() << std::endl;
+ Region* r = phi->GetRegion();
+ const std::vector<Region*>* predecessors = r->GetPredecessors();
+ DCHECK(NULL != predecessors);
+ DCHECK_GT(predecessors->size(), 0u);
+ // Prepass (CodeGenPrepassVisitor) should create the phi function value.
+ llvm::PHINode* llvm_phi = (llvm::PHINode*) llvm_data_->GetValue(phi);
+ int predecessor_pos = 0;
+ for (std::vector<Region*>::const_iterator cit = predecessors->begin();
+ cit != predecessors->end(); ++cit) {
+ std::vector<InstructionNode*>* defining_instructions = phi->GetSSAUses(predecessor_pos++);
+ DCHECK_EQ(defining_instructions->size(), 1u);
+ InstructionNode* defining_instruction = defining_instructions->at(0);
+ DCHECK(NULL != defining_instruction);
+ Region* incoming_region = *cit;
+ llvm::BasicBlock* incoming_basic_block = llvm_data_->GetBlock(incoming_region);
+ llvm::Value* incoming_value = llvm_data_->GetValue(defining_instruction);
+ llvm_phi->addIncoming(incoming_value, incoming_basic_block);
+ }
+}
+
+void CodeGenVisitor::Visit(SignatureNode* signature) {
+ std::cout << "Signature: ;" << "Id:" << signature->StringId() << std::endl;
+ DCHECK_EQ(signature->GetDefinitions().size(), 1u) << "Signature nodes must correspond to a single parameter register.";
+}
+void CodeGenPrepassVisitor::Visit(SignatureNode* signature) {
+ std::cout << "Signature: ;" << "Id:" << signature->StringId() << std::endl;
+ DCHECK_EQ(signature->GetDefinitions().size(), 1u) << "Signature nodes must correspond to a single parameter register.";
+}
+void CodeGenPostpassVisitor::Visit(SignatureNode* signature) {
+ std::cout << "Signature: ;" << "Id:" << signature->StringId() << std::endl;
+ DCHECK_EQ(signature->GetDefinitions().size(), 1u) << "Signature nodes must correspond to a single parameter register.";
+}
+
+} // end namespace sea_ir