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/Android.mk b/compiler/Android.mk
index 0bb8770..c43d5a5 100644
--- a/compiler/Android.mk
+++ b/compiler/Android.mk
@@ -74,8 +74,8 @@
llvm/runtime_support_builder_arm.cc \
llvm/runtime_support_builder_thumb2.cc \
llvm/runtime_support_builder_x86.cc \
- stubs/portable/stubs.cc \
- stubs/quick/stubs.cc \
+ stubs/portable/stubs.cc \
+ stubs/quick/stubs.cc \
elf_fixup.cc \
elf_stripper.cc \
elf_writer.cc \
@@ -86,7 +86,9 @@
ifeq ($(ART_SEA_IR_MODE),true)
LIBART_COMPILER_SRC_FILES += \
sea_ir/frontend.cc \
- sea_ir/instruction_tools.cc
+ sea_ir/instruction_tools.cc \
+ sea_ir/sea.cc \
+ sea_ir/code_gen.cc
endif
LIBART_COMPILER_CFLAGS :=
@@ -173,7 +175,6 @@
LOCAL_SHARED_LIBRARIES += libart
endif
LOCAL_SHARED_LIBRARIES += libbcc libbcinfo libLLVM
-
ifeq ($(ART_USE_PORTABLE_COMPILER),true)
LOCAL_CFLAGS += -DART_USE_PORTABLE_COMPILER=1
endif
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
diff --git a/compiler/sea_ir/code_gen.h b/compiler/sea_ir/code_gen.h
new file mode 100644
index 0000000..0f0b2f7
--- /dev/null
+++ b/compiler/sea_ir/code_gen.h
@@ -0,0 +1,153 @@
+/*
+ * 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.
+ */
+
+#ifndef ART_COMPILER_SEA_IR_CODE_GEN_H_
+#define ART_COMPILER_SEA_IR_CODE_GEN_H_
+
+#include "llvm/IR/IRBuilder.h"
+#include "llvm/IR/LLVMContext.h"
+#include "llvm/IR/Module.h"
+#include "llvm/Analysis/Verifier.h"
+#include "visitor.h"
+
+namespace sea_ir {
+// Abstracts away the containers we use to map SEA IR objects to LLVM IR objects.
+class CodeGenData {
+ public:
+ explicit CodeGenData(): context_(&llvm::getGlobalContext()), module_("sea_ir", *context_),
+ builder_(*context_), function_(), blocks_(), values_() { }
+ // Returns the llvm::BasicBlock* corresponding to the sea_ir::Region with id @region_id.
+ llvm::BasicBlock* GetBlock(int region_id) {
+ std::map<int, llvm::BasicBlock*>::iterator block_it = blocks_.find(region_id);
+ DCHECK(block_it != blocks_.end());
+ return block_it->second;
+ }
+ // Returns the llvm::BasicBlock* corresponding top the sea_ir::Region @region.
+ llvm::BasicBlock* GetBlock(Region* region) {
+ return GetBlock(region->Id());
+ }
+ // Records @block as corresponding to the sea_ir::Region with id @region_id.
+ void AddBlock(int region_id, llvm::BasicBlock* block) {
+ blocks_.insert(std::pair<int, llvm::BasicBlock*>(region_id, block));
+ }
+ // Records @block as corresponding to the sea_ir::Region with @region.
+ void AddBlock(Region* region, llvm::BasicBlock* block) {
+ AddBlock(region->Id(), block);
+ }
+
+ llvm::Value* GetValue(int instruction_id) {
+ std::map<int, llvm::Value*>::iterator value_it = values_.find(instruction_id);
+ DCHECK(value_it != values_.end());
+ return value_it->second;
+ }
+ // Returns the llvm::Value* corresponding to the output of @instruction.
+ llvm::Value* GetValue(InstructionNode* instruction) {
+ return GetValue(instruction->Id());
+ }
+ // Records @value as corresponding to the sea_ir::InstructionNode with id @instruction_id.
+ void AddValue(int instruction_id, llvm::Value* value) {
+ values_.insert(std::pair<int, llvm::Value*>(instruction_id, value));
+ }
+ // Records @value as corresponding to the sea_ir::InstructionNode @instruction.
+ void AddValue(InstructionNode* instruction, llvm::Value* value) {
+ AddValue(instruction->Id(), value);
+ }
+
+ llvm::LLVMContext* const context_;
+ llvm::Module module_;
+ llvm::IRBuilder<> builder_;
+ llvm::Function* function_;
+
+ private:
+ std::map<int, llvm::BasicBlock*> blocks_;
+ std::map<int, llvm::Value*> values_;
+};
+
+class CodeGenPassVisitor: public IRVisitor {
+ public:
+ explicit CodeGenPassVisitor(CodeGenData* cgd): llvm_data_(cgd) { }
+ CodeGenPassVisitor(): llvm_data_(new CodeGenData()) { }
+ // Initialize any data structure needed before the start of visiting.
+ virtual void Initialize(SeaGraph* graph);
+ CodeGenData* GetData() {
+ return llvm_data_;
+ }
+ void Write(std::string file) {
+ llvm_data_->module_.dump();
+ llvm::verifyFunction(*llvm_data_->function_);
+ }
+
+ protected:
+ CodeGenData* const llvm_data_;
+};
+
+class CodeGenPrepassVisitor: public CodeGenPassVisitor {
+ public:
+ void Visit(SeaGraph* graph);
+ void Visit(SignatureNode* region);
+ void Visit(Region* region);
+ void Visit(InstructionNode* instruction) { }
+ void Visit(ConstInstructionNode* instruction) { }
+ void Visit(ReturnInstructionNode* instruction) { }
+ void Visit(IfNeInstructionNode* instruction) { }
+ //void Visit(AddIntLitInstructionNode* instruction) { }
+ void Visit(MoveResultInstructionNode* instruction) { }
+ void Visit(InvokeStaticInstructionNode* instruction) { }
+ void Visit(AddIntInstructionNode* instruction) { }
+ void Visit(GotoInstructionNode* instruction) { }
+ void Visit(IfEqzInstructionNode* instruction) { }
+ void Visit(PhiInstructionNode* region);
+};
+
+class CodeGenPostpassVisitor: public CodeGenPassVisitor {
+ public:
+ explicit CodeGenPostpassVisitor(CodeGenData* code_gen_data): CodeGenPassVisitor(code_gen_data) { }
+ void Visit(SeaGraph* graph);
+ void Visit(SignatureNode* region);
+ void Visit(Region* region);
+ void Visit(InstructionNode* region) { }
+ void Visit(ConstInstructionNode* instruction) { }
+ void Visit(ReturnInstructionNode* instruction) { }
+ void Visit(IfNeInstructionNode* instruction) { }
+ //void Visit(AddIntLitInstructionNode* instruction) { }
+ void Visit(MoveResultInstructionNode* instruction) { }
+ void Visit(InvokeStaticInstructionNode* instruction) { }
+ void Visit(AddIntInstructionNode* instruction) { }
+ void Visit(GotoInstructionNode* instruction) { }
+ void Visit(IfEqzInstructionNode* instruction) { }
+ void Visit(PhiInstructionNode* region);
+};
+
+class CodeGenVisitor: public CodeGenPassVisitor {
+ public:
+ explicit CodeGenVisitor(CodeGenData* code_gen_data): CodeGenPassVisitor(code_gen_data) { }
+ void Visit(SeaGraph* graph);
+ void Visit(SignatureNode* region);
+ void Visit(Region* region);
+ void Visit(InstructionNode* region);
+ void Visit(ConstInstructionNode* instruction);
+ void Visit(ReturnInstructionNode* instruction);
+ void Visit(IfNeInstructionNode* instruction);
+ //void Visit(AddIntLitInstructionNode* instruction);
+ void Visit(MoveResultInstructionNode* instruction);
+ void Visit(InvokeStaticInstructionNode* instruction);
+ void Visit(AddIntInstructionNode* instruction);
+ void Visit(GotoInstructionNode* instruction);
+ void Visit(IfEqzInstructionNode* instruction);
+ void Visit(PhiInstructionNode* region) { }
+};
+} // end namespace sea_ir
+#endif // ART_COMPILER_SEA_IR_CODE_GEN_H_
diff --git a/compiler/sea_ir/instruction_nodes.h b/compiler/sea_ir/instruction_nodes.h
new file mode 100644
index 0000000..f6d2dd8
--- /dev/null
+++ b/compiler/sea_ir/instruction_nodes.h
@@ -0,0 +1,250 @@
+/*
+ * 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.
+ */
+
+#ifndef ART_COMPILER_SEA_IR_INSTRUCTION_NODES_H_
+#define ART_COMPILER_SEA_IR_INSTRUCTION_NODES_H_
+#include "sea_node.h"
+#include "visitor.h"
+#include "dex_instruction-inl.h"
+
+namespace sea_ir {
+
+enum SpecialRegisters {
+ NO_REGISTER = -1, // Usually signifies that there is no register
+ // that respects the condition you asked for.
+ RETURN_REGISTER = -2, // Written by the invoke* instructions, read by move-results.
+ UNNAMED_CONST_REGISTER = -3 // Written by UnnamedConst* instructions, read by *Lit* instruction.
+};
+
+class IRVisitor;
+
+// This class represents an instruction in SEA IR.
+// As we add support for specific classes of instructions,
+// the number of InstructionNode objects should dwindle, while the
+// number of subclasses and instances of subclasses will go up.
+class InstructionNode: public SeaNode {
+ public:
+ static std::vector<sea_ir::InstructionNode*> Create(const art::Instruction* in);
+ // Returns the Dalvik instruction around which this InstructionNode is wrapped.
+ const art::Instruction* GetInstruction() const {
+ DCHECK(NULL != instruction_) << "Tried to access NULL instruction in an InstructionNode.";
+ return instruction_;
+ }
+ // Returns the register that is defined by the current instruction, or NO_REGISTER otherwise.
+ virtual int GetResultRegister() const;
+ // Returns the set of registers defined by the current instruction.
+ virtual std::vector<int> GetDefinitions() const;
+ // Returns the set of register numbers that are used by the instruction.
+ virtual std::vector<int> GetUses();
+ // Appends to @result the .dot string representation of the instruction.
+ virtual void ToDot(std::string& result) const;
+ // Mark the current instruction as a downward exposed definition.
+ void MarkAsDEDef();
+ // Rename the use of @reg_no to refer to the instruction @definition,
+ // essentially creating SSA form.
+ void RenameToSSA(int reg_no, InstructionNode* definition) {
+ definition_edges_.insert(std::pair<int, InstructionNode*>(reg_no, definition));
+ }
+ // Returns the ordered set of Instructions that define the input operands of this instruction.
+ // Precondition: SeaGraph.ConvertToSSA().
+ std::vector<InstructionNode*> GetSSAUses() {
+ std::vector<int> uses = GetUses();
+ std::vector<InstructionNode*> ssa_uses;
+ for (std::vector<int>::const_iterator cit = uses.begin(); cit != uses.end(); cit++) {
+ ssa_uses.push_back((*definition_edges_.find(*cit)).second);
+ }
+ return ssa_uses;
+ }
+
+ void Accept(IRVisitor* v) {
+ v->Visit(this);
+ v->Traverse(this);
+ }
+ // Set the region to which this instruction belongs.
+ Region* GetRegion() {
+ DCHECK(NULL != region_);
+ return region_;
+ }
+ // Get the region to which this instruction belongs.
+ void SetRegion(Region* region) {
+ region_ = region;
+ }
+
+ protected:
+ explicit InstructionNode(const art::Instruction* in):
+ SeaNode(), instruction_(in), de_def_(false), region_(NULL) { }
+
+ protected:
+ const art::Instruction* const instruction_;
+ std::map<int, InstructionNode* > definition_edges_;
+ bool de_def_;
+ Region* region_;
+};
+
+class ConstInstructionNode: public InstructionNode {
+ public:
+ explicit ConstInstructionNode(const art::Instruction* inst):
+ InstructionNode(inst) { }
+
+ void Accept(IRVisitor* v) {
+ v->Visit(this);
+ v->Traverse(this);
+ }
+
+ virtual int32_t GetConstValue() const {
+ return GetInstruction()->VRegB_11n();
+ }
+};
+
+class UnnamedConstInstructionNode: public ConstInstructionNode {
+ public:
+ explicit UnnamedConstInstructionNode(const art::Instruction* inst, int32_t value):
+ ConstInstructionNode(inst), value_(value) { }
+ void Accept(IRVisitor* v) {
+ v->Visit(this);
+ v->Traverse(this);
+ }
+
+ int GetResultRegister() const {
+ return UNNAMED_CONST_REGISTER;
+ }
+
+ int32_t GetConstValue() const {
+ return value_;
+ }
+
+ void ToDot(std::string& result) const {
+ std::ostringstream sstream;
+ sstream << GetConstValue();
+ const std::string value_as_string(sstream.str());
+ result += "// Instruction ("+StringId()+"): \n" + StringId() +
+ " [label=\"const/x v-3, #"+ value_as_string + "\"";
+ if (de_def_) {
+ result += "style=bold";
+ }
+ result += "];\n";
+ // SSA definitions:
+ for (std::map<int, InstructionNode* >::const_iterator def_it = definition_edges_.begin();
+ def_it != definition_edges_.end(); def_it++) {
+ if (NULL != def_it->second) {
+ result += def_it->second->StringId() + " -> " + StringId() +"[color=red,label=\"";
+ std::stringstream ss;
+ ss << def_it->first;
+ result.append(ss.str());
+ result += "\"] ; // ssa edge\n";
+ }
+ }
+ }
+
+ private:
+ const int32_t value_;
+};
+
+class ReturnInstructionNode: public InstructionNode {
+ public:
+ explicit ReturnInstructionNode(const art::Instruction* inst): InstructionNode(inst) { }
+ void Accept(IRVisitor* v) {
+ v->Visit(this);
+ v->Traverse(this);
+ }
+};
+
+class IfNeInstructionNode: public InstructionNode {
+ public:
+ explicit IfNeInstructionNode(const art::Instruction* inst): InstructionNode(inst) {
+ DCHECK(InstructionTools::IsDefinition(inst) == false);
+ }
+ void Accept(IRVisitor* v) {
+ v->Visit(this);
+ v->Traverse(this);
+ }
+};
+
+
+
+class MoveResultInstructionNode: public InstructionNode {
+ public:
+ explicit MoveResultInstructionNode(const art::Instruction* inst): InstructionNode(inst) { }
+ std::vector<int> GetUses() {
+ std::vector<int> uses; // Using vector<> instead of set<> because order matters.
+ uses.push_back(RETURN_REGISTER);
+ return uses;
+ }
+ void Accept(IRVisitor* v) {
+ v->Visit(this);
+ v->Traverse(this);
+ }
+};
+
+class InvokeStaticInstructionNode: public InstructionNode {
+ public:
+ explicit InvokeStaticInstructionNode(const art::Instruction* inst): InstructionNode(inst) { }
+ int GetResultRegister() const {
+ return RETURN_REGISTER;
+ }
+ void Accept(IRVisitor* v) {
+ v->Visit(this);
+ v->Traverse(this);
+ }
+};
+
+class AddIntInstructionNode: public InstructionNode {
+ public:
+ explicit AddIntInstructionNode(const art::Instruction* inst): InstructionNode(inst) { }
+ void Accept(IRVisitor* v) {
+ v->Visit(this);
+ v->Traverse(this);
+ }
+};
+
+class AddIntLitInstructionNode: public AddIntInstructionNode {
+ public:
+ explicit AddIntLitInstructionNode(const art::Instruction* inst):
+ AddIntInstructionNode(inst) { }
+
+ std::vector<int> GetUses() {
+ std::vector<int> uses = AddIntInstructionNode::GetUses();
+ uses.push_back(UNNAMED_CONST_REGISTER);
+ return uses;
+ }
+
+ void Accept(IRVisitor* v) {
+ v->Visit(this);
+ v->Traverse(this);
+ }
+};
+
+class GotoInstructionNode: public InstructionNode {
+ public:
+ explicit GotoInstructionNode(const art::Instruction* inst): InstructionNode(inst) { }
+ void Accept(IRVisitor* v) {
+ v->Visit(this);
+ v->Traverse(this);
+ }
+};
+
+class IfEqzInstructionNode: public InstructionNode {
+ public:
+ explicit IfEqzInstructionNode(const art::Instruction* inst): InstructionNode(inst) {
+ DCHECK(InstructionTools::IsDefinition(inst) == false);
+ }
+ void Accept(IRVisitor* v) {
+ v->Visit(this);
+ v->Traverse(this);
+ }
+};
+} // end namespace sea_ir
+#endif // ART_COMPILER_SEA_IR_INSTRUCTION_NODES_H_
diff --git a/compiler/sea_ir/instruction_tools.h b/compiler/sea_ir/instruction_tools.h
index b0bbc27..0c22753 100644
--- a/compiler/sea_ir/instruction_tools.h
+++ b/compiler/sea_ir/instruction_tools.h
@@ -14,12 +14,13 @@
* limitations under the License.
*/
-
+#include "sea.h"
#include "dex_instruction.h"
#ifndef ART_COMPILER_SEA_IR_INSTRUCTION_TOOLS_H_
#define ART_COMPILER_SEA_IR_INSTRUCTION_TOOLS_H_
+
// Note: This file has content cannibalized for SEA_IR from the MIR implementation,
// to avoid having a dependence on MIR.
namespace sea_ir {
diff --git a/compiler/sea_ir/sea.cc b/compiler/sea_ir/sea.cc
index c5ec2b9..347fcff 100644
--- a/compiler/sea_ir/sea.cc
+++ b/compiler/sea_ir/sea.cc
@@ -14,19 +14,42 @@
* limitations under the License.
*/
-#include "sea.h"
-
#include "file_output_stream.h"
#include "instruction_tools.h"
-
+#include "sea.h"
+#include "code_gen.h"
#define MAX_REACHING_DEF_ITERERATIONS (10)
+// TODO: When development is done, this define should not
+// be needed, it is currently used as a cutoff
+// for cases where the iterative fixed point algorithm
+// does not reach a fixed point because of a bug.
namespace sea_ir {
SeaGraph SeaGraph::graph_;
int SeaNode::current_max_node_id_ = 0;
+void IRVisitor::Traverse(Region* region) {
+ std::vector<PhiInstructionNode*>* phis = region->GetPhiNodes();
+ for (std::vector<PhiInstructionNode*>::const_iterator cit = phis->begin();
+ cit != phis->end(); cit++) {
+ (*cit)->Accept(this);
+ }
+
+ std::vector<InstructionNode*>* instructions = region->GetInstructions();
+ for (std::vector<InstructionNode*>::const_iterator cit = instructions->begin();
+ cit != instructions->end(); cit++) {
+ (*cit)->Accept(this);
+ }
+}
+
+void IRVisitor::Traverse(SeaGraph* graph) {
+ for (std::vector<Region*>::const_iterator cit = ordered_regions_.begin();
+ cit != ordered_regions_.end(); cit++ ) {
+ (*cit)->Accept(this);
+ }
+}
SeaGraph* SeaGraph::GetCurrentGraph() {
return &sea_ir::SeaGraph::graph_;
@@ -169,7 +192,10 @@
void SeaGraph::BuildMethodSeaGraph(const art::DexFile::CodeItem* code_item,
- const art::DexFile& dex_file) {
+ const art::DexFile& dex_file, uint32_t class_def_idx, uint32_t method_idx) {
+ class_def_idx_ = class_def_idx;
+ method_idx_ = method_idx;
+
const uint16_t* code = code_item->insns_;
const size_t size_in_code_units = code_item->insns_size_in_code_units_;
// This maps target instruction pointers to their corresponding region objects.
@@ -194,42 +220,53 @@
}
i += inst->SizeInCodeUnits();
}
+
+
+ Region* r = GetNewRegion();
+ // Insert one SignatureNode per function argument,
+ // to serve as placeholder definitions in dataflow analysis.
+ for (unsigned int crt_offset = 0; crt_offset < code_item->ins_size_; crt_offset++) {
+ SignatureNode* parameter_def_node =
+ new sea_ir::SignatureNode(code_item->registers_size_ - 1 - crt_offset);
+ AddParameterNode(parameter_def_node);
+ r->AddChild(parameter_def_node);
+ }
// Pass: Assign instructions to region nodes and
// assign branches their control flow successors.
i = 0;
- Region* r = GetNewRegion();
- SignatureNode* parameter_def_node = new sea_ir::SignatureNode(code_item->registers_size_-1,
- code_item->ins_size_);
- r->AddChild(parameter_def_node);
sea_ir::InstructionNode* last_node = NULL;
sea_ir::InstructionNode* node = NULL;
while (i < size_in_code_units) {
- const art::Instruction* inst = art::Instruction::At(&code[i]); //TODO: find workaround for this
- last_node = node;
- node = new sea_ir::InstructionNode(inst);
+ const art::Instruction* inst = art::Instruction::At(&code[i]);
+ std::vector<InstructionNode*> sea_instructions_for_dalvik = sea_ir::InstructionNode::Create(inst);
+ for (std::vector<InstructionNode*>::const_iterator cit = sea_instructions_for_dalvik.begin();
+ sea_instructions_for_dalvik.end() != cit; ++cit) {
+ last_node = node;
+ node = *cit;
- if (inst->IsBranch() || inst->IsUnconditional()) {
- int32_t offset = inst->GetTargetOffset();
- std::map<const uint16_t*, Region*>::iterator it = target_regions.find(&code[i + offset]);
- DCHECK(it != target_regions.end());
- AddEdge(r, it->second); // Add edge to branch target.
- }
-
- std::map<const uint16_t*, Region*>::iterator it = target_regions.find(&code[i]);
- if (target_regions.end() != it) {
- // Get the already created region because this is a branch target.
- Region* nextRegion = it->second;
- if (last_node->GetInstruction()->IsBranch()
- && last_node->GetInstruction()->CanFlowThrough()) {
- AddEdge(r, it->second); // Add flow-through edge.
+ if (inst->IsBranch() || inst->IsUnconditional()) {
+ int32_t offset = inst->GetTargetOffset();
+ std::map<const uint16_t*, Region*>::iterator it = target_regions.find(&code[i + offset]);
+ DCHECK(it != target_regions.end());
+ AddEdge(r, it->second); // Add edge to branch target.
}
- r = nextRegion;
- }
- bool definesRegister = (0 != InstructionTools::instruction_attributes_[inst->Opcode()]
- && (1 << kDA));
- LOG(INFO)<< inst->GetDexPc(code) << "*** " << inst->DumpString(&dex_file)
- << " region:" <<r->StringId() << "Definition?" << definesRegister << std::endl;
- r->AddChild(node);
+
+ std::map<const uint16_t*, Region*>::iterator it = target_regions.find(&code[i]);
+ if (target_regions.end() != it) {
+ // Get the already created region because this is a branch target.
+ Region* nextRegion = it->second;
+ if (last_node->GetInstruction()->IsBranch()
+ && last_node->GetInstruction()->CanFlowThrough()) {
+ AddEdge(r, it->second); // Add flow-through edge.
+ }
+ r = nextRegion;
+ }
+ bool definesRegister = (0 != InstructionTools::instruction_attributes_[inst->Opcode()]
+ && (1 << kDA));
+ LOG(INFO)<< inst->GetDexPc(code) << "*** " << inst->DumpString(&dex_file)
+ << " region:" <<r->StringId() << "Definition?" << definesRegister << std::endl;
+ r->AddChild(node);
+ }
i += inst->SizeInCodeUnits();
}
}
@@ -255,7 +292,6 @@
RenameAsSSA(*region_it, &scoped_table);
}
}
-
scoped_table.CloseScope();
}
@@ -366,10 +402,25 @@
scoped_table->CloseScope();
}
+void SeaGraph::GenerateLLVM() {
+ // Pass: Generate LLVM IR.
+ CodeGenPrepassVisitor code_gen_prepass_visitor;
+ std::cout << "Generating code..." << std::endl;
+ std::cout << "=== PRE VISITING ===" << std::endl;
+ Accept(&code_gen_prepass_visitor);
+ CodeGenVisitor code_gen_visitor(code_gen_prepass_visitor.GetData());
+ std::cout << "=== VISITING ===" << std::endl;
+ Accept(&code_gen_visitor);
+ std::cout << "=== POST VISITING ===" << std::endl;
+ CodeGenPostpassVisitor code_gen_postpass_visitor(code_gen_visitor.GetData());
+ Accept(&code_gen_postpass_visitor);
+ code_gen_postpass_visitor.Write(std::string("my_file.llvm"));
+}
+
void SeaGraph::CompileMethod(const art::DexFile::CodeItem* code_item,
uint32_t class_def_idx, uint32_t method_idx, const art::DexFile& dex_file) {
// Two passes: Builds the intermediate structure (non-SSA) of the sea-ir for the function.
- BuildMethodSeaGraph(code_item, dex_file);
+ BuildMethodSeaGraph(code_item, dex_file, class_def_idx, method_idx);
//Pass: Compute reverse post-order of regions.
ComputeRPO();
// Multiple passes: compute immediate dominators.
@@ -382,9 +433,10 @@
ComputeDominanceFrontier();
// Two Passes: Phi node insertion.
ConvertToSSA();
+ // Pass: Generate LLVM IR.
+ GenerateLLVM();
}
-
void SeaGraph::ComputeDominanceFrontier() {
for (std::vector<Region*>::iterator region_it = regions_.begin();
region_it != regions_.end(); region_it++) {
@@ -413,6 +465,7 @@
regions_.push_back(r);
}
+/*
void SeaNode::AddSuccessor(Region* successor) {
DCHECK(successor) << "Tried to add NULL successor to SEA node.";
successors_.push_back(successor);
@@ -423,10 +476,11 @@
DCHECK(predecessor) << "Tried to add NULL predecessor to SEA node.";
predecessors_.push_back(predecessor);
}
-
+*/
void Region::AddChild(sea_ir::InstructionNode* instruction) {
DCHECK(instruction) << "Tried to add NULL instruction to region node.";
instructions_.push_back(instruction);
+ instruction->SetRegion(this);
}
SeaNode* Region::GetLastChild() const {
@@ -582,6 +636,7 @@
if (!ContainsPhiFor(reg_no)) {
phi_set_.insert(reg_no);
PhiInstructionNode* new_phi = new PhiInstructionNode(reg_no);
+ new_phi->SetRegion(this);
phi_instructions_.push_back(new_phi);
return true;
}
@@ -606,8 +661,47 @@
}
}
+std::vector<InstructionNode*> InstructionNode::Create(const art::Instruction* in) {
+ std::vector<InstructionNode*> sea_instructions;
+ switch (in->Opcode()) {
+ case art::Instruction::CONST_4:
+ sea_instructions.push_back(new ConstInstructionNode(in));
+ break;
+ case art::Instruction::RETURN:
+ sea_instructions.push_back(new ReturnInstructionNode(in));
+ break;
+ case art::Instruction::IF_NE:
+ sea_instructions.push_back(new IfNeInstructionNode(in));
+ break;
+ case art::Instruction::ADD_INT_LIT8:
+ sea_instructions.push_back(new UnnamedConstInstructionNode(in, in->VRegB_22b()));
+ sea_instructions.push_back(new AddIntLitInstructionNode(in));
+ break;
+ case art::Instruction::MOVE_RESULT:
+ sea_instructions.push_back(new MoveResultInstructionNode(in));
+ break;
+ case art::Instruction::INVOKE_STATIC:
+ sea_instructions.push_back(new InvokeStaticInstructionNode(in));
+ break;
+ case art::Instruction::ADD_INT:
+ sea_instructions.push_back(new AddIntInstructionNode(in));
+ break;
+ case art::Instruction::GOTO:
+ sea_instructions.push_back(new GotoInstructionNode(in));
+ break;
+ case art::Instruction::IF_EQZ:
+ sea_instructions.push_back(new IfEqzInstructionNode(in));
+ break;
+ default:
+ // Default, generic IR instruction node; default case should never be reached
+ // when support for all instructions ahs been added.
+ sea_instructions.push_back(new InstructionNode(in));
+ }
+ return sea_instructions;
+}
+
void InstructionNode::ToDot(std::string& result) const {
- result += "// Instruction: \n" + StringId() +
+ result += "// Instruction ("+StringId()+"): \n" + StringId() +
" [label=\"" + instruction_->DumpString(NULL) + "\"";
if (de_def_) {
result += "style=bold";
@@ -631,7 +725,7 @@
}
int InstructionNode::GetResultRegister() const {
- if (instruction_->HasVRegA()) {
+ if (instruction_->HasVRegA() && InstructionTools::IsDefinition(instruction_)) {
return instruction_->VRegA();
}
return NO_REGISTER;
@@ -651,7 +745,6 @@
std::vector<int> InstructionNode::GetUses() {
std::vector<int> uses; // Using vector<> instead of set<> because order matters.
-
if (!InstructionTools::IsDefinition(instruction_) && (instruction_->HasVRegA())) {
int vA = instruction_->VRegA();
uses.push_back(vA);
@@ -664,7 +757,6 @@
int vC = instruction_->VRegC();
uses.push_back(vC);
}
- // TODO: Add support for function argument registers.
return uses;
}
@@ -677,24 +769,16 @@
result += ")\"";
result += "];\n";
- for (std::vector<std::map<int, InstructionNode*>*>::const_iterator pred_it = definition_edges_.begin();
+ for (std::vector<std::vector<InstructionNode*>*>::const_iterator pred_it = definition_edges_.begin();
pred_it != definition_edges_.end(); pred_it++) {
- std::map<int, InstructionNode*>* defs_from_pred = *pred_it;
- for (std::map<int, InstructionNode* >::const_iterator def_it = defs_from_pred->begin();
+ std::vector<InstructionNode*>* defs_from_pred = *pred_it;
+ for (std::vector<InstructionNode* >::const_iterator def_it = defs_from_pred->begin();
def_it != defs_from_pred->end(); def_it++) {
- if (NULL != def_it->second) {
- result += def_it->second->StringId() + " -> " + StringId() +"[color=red,label=\"vR = ";
+ result += (*def_it)->StringId() + " -> " + StringId() +"[color=red,label=\"vR = ";
std::stringstream ss;
- ss << def_it->first;
+ ss << GetRegisterNumber();
result.append(ss.str());
result += "\"] ; // phi-ssa edge\n";
- } else {
- result += StringId() + " -> " + StringId() +"[color=blue,label=\"vR = ";
- std::stringstream ss;
- ss << def_it->first;
- result.append(ss.str());
- result += "\"] ; // empty phi-ssa edge\n";
- }
}
}
}
diff --git a/compiler/sea_ir/sea.h b/compiler/sea_ir/sea.h
index 7491d21..81a1b88 100644
--- a/compiler/sea_ir/sea.h
+++ b/compiler/sea_ir/sea.h
@@ -23,14 +23,12 @@
#include "dex_file.h"
#include "dex_instruction.h"
-#include "sea_ir/instruction_tools.h"
+#include "instruction_tools.h"
+#include "instruction_nodes.h"
#include "utils/scoped_hashtable.h"
-
namespace sea_ir {
-#define NO_REGISTER (-1)
-
// Reverse post-order numbering constants
enum RegionNumbering {
NOT_VISITED = -1,
@@ -38,93 +36,23 @@
};
class Region;
+
class InstructionNode;
class PhiInstructionNode;
+class SignatureNode;
-class SeaNode {
- public:
- explicit SeaNode():id_(GetNewId()), string_id_(), successors_(), predecessors_() {
- std::stringstream ss;
- ss << id_;
- string_id_.append(ss.str());
- }
- // Adds CFG predecessors and successors to each block.
- void AddSuccessor(Region* successor);
- void AddPredecessor(Region* predecesor);
-
- std::vector<sea_ir::Region*>* GetSuccessors() {
- return &successors_;
- }
- std::vector<sea_ir::Region*>* GetPredecessors() {
- return &predecessors_;
- }
- // Returns the id of the current block as string
- const std::string& StringId() const {
- return string_id_;
- }
- // Appends to @result a dot language formatted string representing the node and
- // (by convention) outgoing edges, so that the composition of theToDot() of all nodes
- // builds a complete dot graph, but without prolog ("digraph {") and epilog ("}").
- virtual void ToDot(std::string& result) const = 0;
-
- virtual ~SeaNode() {}
-
- protected:
- static int GetNewId() {
- return current_max_node_id_++;
- }
-
- const int id_;
- std::string string_id_;
- std::vector<sea_ir::Region*> successors_; // CFG successor nodes (regions)
- std::vector<sea_ir::Region*> predecessors_; // CFG predecessor nodes (instructions/regions)
-
- private:
- static int current_max_node_id_;
-};
-
-class InstructionNode: public SeaNode {
- public:
- explicit InstructionNode(const art::Instruction* in):
- SeaNode(), instruction_(in), de_def_(false) {}
- // Returns the Dalvik instruction around which this InstructionNode is wrapped.
- const art::Instruction* GetInstruction() const {
- DCHECK(NULL != instruction_) << "Tried to access NULL instruction in an InstructionNode.";
- return instruction_;
- }
- // Returns the register that is defined by the current instruction, or NO_REGISTER otherwise.
- virtual int GetResultRegister() const;
- // Returns the set of registers defined by the current instruction.
- virtual std::vector<int> GetDefinitions() const;
- // Returns the set of register numbers that are used by the instruction.
- virtual std::vector<int> GetUses();
- // Appends to @result the .dot string representation of the instruction.
- void ToDot(std::string& result) const;
- // Mark the current instruction as a dowward exposed definition.
- void MarkAsDEDef();
- // Rename the use of @reg_no to refer to the instruction @definition,
- // essentially creating SSA form.
- void RenameToSSA(int reg_no, InstructionNode* definition) {
- definition_edges_.insert(std::pair<int, InstructionNode*>(reg_no, definition));
- }
-
- private:
- const art::Instruction* const instruction_;
- std::map<int, InstructionNode* > definition_edges_;
- bool de_def_;
-};
-
+// A SignatureNode is a declaration of one parameter in the function signature.
+// This class is used to provide place-holder definitions to which instructions
+// can return from the GetSSAUses() calls, instead of having missing SSA edges.
class SignatureNode: public InstructionNode {
public:
- explicit SignatureNode(unsigned int start_register, unsigned int count):
+ explicit SignatureNode(unsigned int parameter_register):
InstructionNode(NULL), defined_regs_() {
- for (unsigned int crt_offset = 0; crt_offset < count; crt_offset++) {
- defined_regs_.push_back(start_register - crt_offset);
- }
+ defined_regs_.push_back(parameter_register);
}
void ToDot(std::string& result) const {
- result += StringId() +"[label=\"signature:";
+ result += StringId() +" [label=\"signature:";
std::stringstream vector_printer;
if (!defined_regs_.empty()) {
for (unsigned int crt_el = 0; crt_el < defined_regs_.size()-1; crt_el++) {
@@ -147,11 +75,15 @@
return std::vector<int>();
}
+ void Accept(IRVisitor* v) {
+ v->Visit(this);
+ v->Traverse(this);
+ }
+
private:
std::vector<int> defined_regs_;
};
-
class PhiInstructionNode: public InstructionNode {
public:
explicit PhiInstructionNode(int register_no):
@@ -159,11 +91,11 @@
// Appends to @result the .dot string representation of the instruction.
void ToDot(std::string& result) const;
// Returns the register on which this phi-function is used.
- int GetRegisterNumber() {
+ int GetRegisterNumber() const {
return register_no_;
}
- // Rename the use of @reg_no to refer to the instruction @definition.
+ // Renames the use of @reg_no to refer to the instruction @definition.
// Phi-functions are different than normal instructions in that they
// have multiple predecessor regions; this is why RenameToSSA has
// the additional parameter specifying that @parameter_id is the incoming
@@ -174,27 +106,40 @@
if (definition_edges_.size() < predecessor_id+1) {
definition_edges_.resize(predecessor_id+1, NULL);
}
-
if (NULL == definition_edges_.at(predecessor_id)) {
- definition_edges_[predecessor_id] = new std::map<int, InstructionNode*>();
+ definition_edges_[predecessor_id] = new std::vector<InstructionNode*>();
}
- definition_edges_[predecessor_id]->insert(std::pair<int, InstructionNode*>(reg_no, definition));
+ definition_edges_[predecessor_id]->push_back(definition);
+ }
+
+ // Returns the instruction that defines the phi register from predecessor
+ // on position @predecessor_pos. Note that the return value is vector<> just
+ // for consistency with the return value of GetSSAUses() on regular instructions,
+ // The returned vector should always have a single element because the IR is SSA.
+ std::vector<InstructionNode*>* GetSSAUses(int predecessor_pos) {
+ return definition_edges_.at(predecessor_pos);
+ }
+
+ void Accept(IRVisitor* v) {
+ v->Visit(this);
+ v->Traverse(this);
}
private:
int register_no_;
- std::vector<std::map<int, InstructionNode*>*> definition_edges_;
+ std::vector<std::vector<InstructionNode*>*> definition_edges_;
};
+// This class corresponds to a basic block in traditional compiler IRs.
+// The dataflow analysis relies on this class both during execution and
+// for storing its results.
class Region : public SeaNode {
public:
explicit Region():
- SeaNode(), reaching_defs_size_(0), rpo_(NOT_VISITED), idom_(NULL),
- idominated_set_(), df_(), phi_set_() {}
-
+ SeaNode(), successors_(), predecessors_(), reaching_defs_size_(0),
+ rpo_(NOT_VISITED), idom_(NULL), idominated_set_(), df_(), phi_set_() {}
// Adds @instruction as an instruction node child in the current region.
- void AddChild(sea_ir::InstructionNode* insttruction);
-
+ void AddChild(sea_ir::InstructionNode* instruction);
// Returns the last instruction node child of the current region.
// This child has the CFG successors pointing to the new regions.
SeaNode* GetLastChild() const;
@@ -207,10 +152,8 @@
// builds a complete dot graph (without prolog and epilog though).
virtual void ToDot(std::string& result) const;
// Computes Downward Exposed Definitions for the current node.
-
void ComputeDownExposedDefs();
const std::map<int, sea_ir::InstructionNode*>* GetDownExposedDefs() const;
-
// Performs one iteration of the reaching definitions algorithm
// and returns true if the reaching definitions set changed.
bool UpdateReachingDefs();
@@ -240,7 +183,6 @@
const std::set<Region*>* GetIDominatedSet() {
return &idominated_set_;
}
-
// Adds @df_reg to the dominance frontier of the current region.
void AddToDominanceFrontier(Region* df_reg) {
df_.insert(df_reg);
@@ -266,7 +208,31 @@
void SetPhiDefinitionsForUses(const utils::ScopedHashtable<int, InstructionNode*>* scoped_table,
Region* predecessor);
+ void Accept(IRVisitor* v) {
+ v->Visit(this);
+ v->Traverse(this);
+ }
+
+ void AddSuccessor(Region* successor) {
+ DCHECK(successor) << "Tried to add NULL successor to SEA node.";
+ successors_.push_back(successor);
+ return;
+ }
+ void AddPredecessor(Region* predecessor) {
+ DCHECK(predecessor) << "Tried to add NULL predecessor to SEA node.";
+ predecessors_.push_back(predecessor);
+ }
+
+ std::vector<sea_ir::Region*>* GetSuccessors() {
+ return &successors_;
+ }
+ std::vector<sea_ir::Region*>* GetPredecessors() {
+ return &predecessors_;
+ }
+
private:
+ std::vector<sea_ir::Region*> successors_; // CFG successor nodes (regions)
+ std::vector<sea_ir::Region*> predecessors_; // CFG predecessor nodes (instructions/regions)
std::vector<sea_ir::InstructionNode*> instructions_;
std::map<int, sea_ir::InstructionNode*> de_defs_;
std::map<int, std::set<sea_ir::InstructionNode*>* > reaching_defs_;
@@ -283,28 +249,49 @@
std::vector<PhiInstructionNode*> phi_instructions_;
};
-class SeaGraph {
+// A SeaGraph instance corresponds to a source code function.
+// Its main point is to encapsulate the SEA IR representation of it
+// and acts as starting point for visitors (ex: during code generation).
+class SeaGraph: IVisitable {
public:
static SeaGraph* GetCurrentGraph();
void CompileMethod(const art::DexFile::CodeItem* code_item,
uint32_t class_def_idx, uint32_t method_idx, const art::DexFile& dex_file);
+ // Returns all regions corresponding to this SeaGraph.
+ std::vector<Region*>* GetRegions() {
+ return ®ions_;
+ }
// Returns a string representation of the region and its Instruction children.
void DumpSea(std::string filename) const;
// Recursively computes the reverse postorder value for @crt_bb and successors.
static void ComputeRPO(Region* crt_bb, int& crt_rpo);
// Returns the "lowest common ancestor" of @i and @j in the dominator tree.
static Region* Intersect(Region* i, Region* j);
+ //Returns the vector of parameters of the function.
+ std::vector<SignatureNode*>* GetParameterNodes() {
+ return ¶meters_;
+ }
+ uint32_t class_def_idx_;
+ uint32_t method_idx_;
private:
+ SeaGraph(): class_def_idx_(0), method_idx_(0), regions_(), parameters_() {
+ }
// Registers @childReg as a region belonging to the SeaGraph instance.
void AddRegion(Region* childReg);
// Returns new region and registers it with the SeaGraph instance.
Region* GetNewRegion();
+ // Adds a (formal) parameter node to the vector of parameters of the function.
+ void AddParameterNode(SignatureNode* parameterNode) {
+ parameters_.push_back(parameterNode);
+ }
// Adds a CFG edge from @src node to @dst node.
void AddEdge(Region* src, Region* dst) const;
- // Builds the non-SSA sea-ir representation of the function @code_item from @dex_file.
- void BuildMethodSeaGraph(const art::DexFile::CodeItem* code_item, const art::DexFile& dex_file);
+ // Builds the non-SSA sea-ir representation of the function @code_item from @dex_file
+ // with class id @class_def_idx and method id @method_idx.
+ void BuildMethodSeaGraph(const art::DexFile::CodeItem* code_item,
+ const art::DexFile& dex_file, uint32_t class_def_idx, uint32_t method_idx);
// Computes immediate dominators for each region.
// Precondition: ComputeMethodSeaGraph()
void ComputeIDominators();
@@ -322,15 +309,28 @@
// Cooper & Torczon, "Engineering a Compiler", second edition, page 499.
// Precondition: ComputeIDominators()
void ComputeDominanceFrontier();
-
+ // Converts the IR to semi-pruned SSA form.
void ConvertToSSA();
+ // Performs the renaming phase of the SSA transformation during ConvertToSSA() execution.
+ void RenameAsSSA();
// Identifies the definitions corresponding to uses for region @node
// by using the scoped hashtable of names @ scoped_table.
void RenameAsSSA(Region* node, utils::ScopedHashtable<int, InstructionNode*>* scoped_table);
- void RenameAsSSA();
+
+ virtual void Accept(IRVisitor* visitor) {
+ visitor->Initialize(this);
+ visitor->Visit(this);
+ visitor->Traverse(this);
+ }
+
+ virtual ~SeaGraph() {}
+ // Generate LLVM IR for the method.
+ // Precondition: ConvertToSSA().
+ void GenerateLLVM();
static SeaGraph graph_;
std::vector<Region*> regions_;
+ std::vector<SignatureNode*> parameters_;
};
} // end namespace sea_ir
#endif // ART_COMPILER_SEA_IR_SEA_H_
diff --git a/compiler/sea_ir/sea_node.h b/compiler/sea_ir/sea_node.h
new file mode 100644
index 0000000..bdfa501
--- /dev/null
+++ b/compiler/sea_ir/sea_node.h
@@ -0,0 +1,77 @@
+/*
+ * 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.
+ */
+
+#ifndef ART_COMPILER_SEA_IR_SEA_NODE_H_
+#define ART_COMPILER_SEA_IR_SEA_NODE_H_
+
+namespace sea_ir {
+class Region;
+class IRVisitor;
+
+class IVisitable {
+ public:
+ virtual void Accept(IRVisitor* visitor) = 0;
+ virtual ~IVisitable() {}
+};
+
+// This abstract class provides the essential services that
+// we want each SEA IR element should have.
+// At the moment, these are:
+// - an id and corresponding string representation.
+// - a .dot graph language representation for .dot output.
+//
+// Note that SEA IR nodes could also be Regions, Projects
+// which are not instructions.
+class SeaNode: public IVisitable {
+ public:
+ explicit SeaNode():id_(GetNewId()), string_id_() {
+ std::stringstream ss;
+ ss << id_;
+ string_id_.append(ss.str());
+ }
+ // Adds CFG predecessors and successors to each block.
+ void AddSuccessor(Region* successor);
+ void AddPredecessor(Region* predecesor);
+
+ // Returns the id of the current block as string
+ const std::string& StringId() const {
+ return string_id_;
+ }
+ // Returns the id of this node as int. The id is supposed to be unique among
+ // all instances of all subclasses of this class.
+ int Id() const {
+ return id_;
+ }
+ // Appends to @result a dot language formatted string representing the node and
+ // (by convention) outgoing edges, so that the composition of theToDot() of all nodes
+ // builds a complete dot graph, but without prolog ("digraph {") and epilog ("}").
+ virtual void ToDot(std::string& result) const = 0;
+
+ virtual ~SeaNode() {}
+
+ protected:
+ static int GetNewId() {
+ return current_max_node_id_++;
+ }
+
+ const int id_;
+ std::string string_id_;
+
+ private:
+ static int current_max_node_id_;
+};
+} // end namespace sea_ir
+#endif // ART_COMPILER_SEA_IR_SEA_NODE_H_
diff --git a/compiler/sea_ir/visitor.h b/compiler/sea_ir/visitor.h
new file mode 100644
index 0000000..9859008
--- /dev/null
+++ b/compiler/sea_ir/visitor.h
@@ -0,0 +1,94 @@
+/*
+ * 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.
+ */
+
+#ifndef ART_COMPILER_SEA_IR_VISITOR_H_
+#define ART_COMPILER_SEA_IR_VISITOR_H_
+
+#include "llvm/IR/IRBuilder.h"
+#include "llvm/IR/LLVMContext.h"
+#include "llvm/IR/Module.h"
+#include "llvm/Analysis/Verifier.h"
+// TODO: Separating the root visitor from the code_gen visitor
+// would allow me to not include llvm headers here.
+
+
+namespace sea_ir {
+
+class SeaGraph;
+class Region;
+class InstructionNode;
+class PhiInstructionNode;
+class SignatureNode;
+class ConstInstructionNode;
+class ReturnInstructionNode;
+class IfNeInstructionNode;
+class AddIntLit8InstructionNode;
+class MoveResultInstructionNode;
+class InvokeStaticInstructionNode;
+class AddIntInstructionNode;
+class AddIntLitInstructionNode;
+class GotoInstructionNode;
+class IfEqzInstructionNode;
+
+
+
+
+class IRVisitor {
+ public:
+ explicit IRVisitor():ordered_regions_() { }
+ virtual void Initialize(SeaGraph* graph) = 0;
+ virtual void Visit(SeaGraph* graph) = 0;
+ virtual void Visit(Region* region) = 0;
+ virtual void Visit(PhiInstructionNode* region) = 0;
+ virtual void Visit(SignatureNode* region) = 0;
+
+ virtual void Visit(InstructionNode* region) = 0;
+ virtual void Visit(ConstInstructionNode* instruction) = 0;
+ virtual void Visit(ReturnInstructionNode* instruction) = 0;
+ virtual void Visit(IfNeInstructionNode* instruction) = 0;
+ //virtual void Visit(AddIntLitInstructionNode* instruction) = 0;
+ virtual void Visit(MoveResultInstructionNode* instruction) = 0;
+ virtual void Visit(InvokeStaticInstructionNode* instruction) = 0;
+ virtual void Visit(AddIntInstructionNode* instruction) = 0;
+ virtual void Visit(GotoInstructionNode* instruction) = 0;
+ virtual void Visit(IfEqzInstructionNode* instruction) = 0;
+
+ // Note: This favor of visitor separates the traversal functions from the actual visiting part
+ // so that the Visitor subclasses don't duplicate code and can't get the traversal wrong.
+ // The disadvantage is the increased number of functions (and calls).
+ virtual void Traverse(SeaGraph* graph);
+ virtual void Traverse(Region* region);
+ // The following functions are meant to be empty and not pure virtual,
+ // because the parameter classes have no children to traverse.
+ virtual void Traverse(InstructionNode* region) { }
+ virtual void Traverse(ConstInstructionNode* instruction) { }
+ virtual void Traverse(ReturnInstructionNode* instruction) { }
+ virtual void Traverse(IfNeInstructionNode* instruction) { }
+ virtual void Traverse(AddIntLit8InstructionNode* instruction) { }
+ virtual void Traverse(MoveResultInstructionNode* instruction) { }
+ virtual void Traverse(InvokeStaticInstructionNode* instruction) { }
+ virtual void Traverse(AddIntInstructionNode* instruction) { }
+ virtual void Traverse(GotoInstructionNode* instruction) { }
+ virtual void Traverse(IfEqzInstructionNode* instruction) { }
+ virtual void Traverse(PhiInstructionNode* phi) { }
+ virtual void Traverse(SignatureNode* sig) { }
+ virtual ~IRVisitor() { }
+
+ protected:
+ std::vector<Region*> ordered_regions_;
+};
+} // end namespace sea_ir
+#endif // ART_COMPILER_SEA_IR_VISITOR_H_
diff --git a/runtime/Android.mk b/runtime/Android.mk
index 5bcd3fb..cc64b20 100644
--- a/runtime/Android.mk
+++ b/runtime/Android.mk
@@ -164,12 +164,6 @@
oat/runtime/support_throw.cc \
oat/runtime/support_interpreter.cc
-ifeq ($(ART_SEA_IR_MODE),true)
-LIBART_COMMON_SRC_FILES += \
- compiler/sea_ir/sea.cc \
- compiler/sea_ir/instruction_tools.cc
-endif
-
LIBART_TARGET_SRC_FILES := \
$(LIBART_COMMON_SRC_FILES) \
base/logging_android.cc \
diff --git a/runtime/dex_instruction.cc b/runtime/dex_instruction.cc
index a7be529..dcaa4cc 100644
--- a/runtime/dex_instruction.cc
+++ b/runtime/dex_instruction.cc
@@ -99,6 +99,7 @@
case k22s: return true;
case k22t: return true;
case k22x: return true;
+ case k23x: return true;
case k32x: return true;
default: return false;
}
@@ -147,6 +148,7 @@
case k22s: return VRegB_22s();
case k22t: return VRegB_22t();
case k22x: return VRegB_22x();
+ case k23x: return VRegB_23x();
case k32x: return VRegB_32x();
default: LOG(FATAL) << "Tried to access vB of instruction " << Name() <<
" which has no B operand.";
