Add codegen support to the optimizing compiler.
Change-Id: I9aae76908ff1d6e64fb71a6718fc1426b67a5c28
diff --git a/compiler/optimizing/builder.cc b/compiler/optimizing/builder.cc
index e6db7bc..f78e56b 100644
--- a/compiler/optimizing/builder.cc
+++ b/compiler/optimizing/builder.cc
@@ -29,6 +29,8 @@
entry_block_->AddInstruction(new (arena_) HGoto());
exit_block_ = new (arena_) HBasicBlock(graph_);
exit_block_->AddInstruction(new (arena_) HExit());
+ graph_->set_entry_block(entry_block_);
+ graph_->set_exit_block(exit_block_);
// To avoid splitting blocks, we compute ahead of time the instructions that
// start a new block, and create these blocks.
diff --git a/compiler/optimizing/code_generator.cc b/compiler/optimizing/code_generator.cc
new file mode 100644
index 0000000..01fc23b
--- /dev/null
+++ b/compiler/optimizing/code_generator.cc
@@ -0,0 +1,79 @@
+/*
+ * Copyright (C) 2014 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 "code_generator.h"
+
+#include "code_generator_arm.h"
+#include "code_generator_x86.h"
+#include "utils/assembler.h"
+#include "utils/arm/assembler_arm.h"
+#include "utils/mips/assembler_mips.h"
+#include "utils/x86/assembler_x86.h"
+
+namespace art {
+
+void CodeGenerator::Compile(CodeAllocator* allocator) {
+ GenerateFrameEntry();
+ const GrowableArray<HBasicBlock*>* blocks = graph()->blocks();
+ for (size_t i = 0; i < blocks->Size(); i++) {
+ CompileBlock(blocks->Get(i));
+ }
+ size_t code_size = assembler_->CodeSize();
+ uint8_t* buffer = allocator->Allocate(code_size);
+ MemoryRegion code(buffer, code_size);
+ assembler_->FinalizeInstructions(code);
+}
+
+void CodeGenerator::CompileBlock(HBasicBlock* block) {
+ Bind(GetLabelOf(block));
+ for (HInstructionIterator it(block); !it.Done(); it.Advance()) {
+ it.Current()->Accept(this);
+ }
+}
+
+bool CodeGenerator::GoesToNextBlock(HGoto* goto_instruction) const {
+ HBasicBlock* successor = goto_instruction->GetSuccessor();
+ // We currently iterate over the block in insertion order.
+ return goto_instruction->block()->block_id() + 1 == successor->block_id();
+}
+
+Label* CodeGenerator::GetLabelOf(HBasicBlock* block) const {
+ return block_labels_.GetRawStorage() + block->block_id();
+}
+
+bool CodeGenerator::CompileGraph(HGraph* graph,
+ InstructionSet instruction_set,
+ CodeAllocator* allocator) {
+ switch (instruction_set) {
+ case kArm:
+ case kThumb2: {
+ arm::ArmAssembler assembler;
+ arm::CodeGeneratorARM(&assembler, graph).Compile(allocator);
+ return true;
+ }
+ case kMips:
+ return false;
+ case kX86: {
+ x86::X86Assembler assembler;
+ x86::CodeGeneratorX86(&assembler, graph).Compile(allocator);
+ return true;
+ }
+ default:
+ return false;
+ }
+}
+
+} // namespace art
diff --git a/compiler/optimizing/code_generator.h b/compiler/optimizing/code_generator.h
new file mode 100644
index 0000000..2a5ae7d
--- /dev/null
+++ b/compiler/optimizing/code_generator.h
@@ -0,0 +1,82 @@
+/*
+ * Copyright (C) 2014 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_OPTIMIZING_CODE_GENERATOR_H_
+#define ART_COMPILER_OPTIMIZING_CODE_GENERATOR_H_
+
+#include "instruction_set.h"
+#include "memory_region.h"
+#include "nodes.h"
+#include "utils/assembler.h"
+
+namespace art {
+
+class CodeAllocator {
+ public:
+ CodeAllocator() { }
+ virtual ~CodeAllocator() { }
+
+ virtual uint8_t* Allocate(size_t size) = 0;
+
+ private:
+ DISALLOW_COPY_AND_ASSIGN(CodeAllocator);
+};
+
+class CodeGenerator : public HGraphVisitor {
+ public:
+ // Compiles the graph to executable instructions. Returns whether the compilation
+ // succeeded.
+ static bool CompileGraph(
+ HGraph* graph, InstructionSet instruction_set, CodeAllocator* allocator);
+
+ Assembler* assembler() const { return assembler_; }
+
+ // Visit functions for instruction classes.
+#define DECLARE_VISIT_INSTRUCTION(name) \
+ virtual void Visit##name(H##name* instr) = 0;
+
+ FOR_EACH_INSTRUCTION(DECLARE_VISIT_INSTRUCTION)
+
+#undef DECLARE_VISIT_INSTRUCTION
+
+ protected:
+ CodeGenerator(Assembler* assembler, HGraph* graph)
+ : HGraphVisitor(graph), assembler_(assembler), block_labels_(graph->arena(), 0) {
+ block_labels_.SetSize(graph->blocks()->Size());
+ }
+
+ Label* GetLabelOf(HBasicBlock* block) const;
+ bool GoesToNextBlock(HGoto* got) const;
+
+ private:
+ virtual void GenerateFrameEntry() = 0;
+ virtual void GenerateFrameExit() = 0;
+ virtual void Bind(Label* label) = 0;
+
+ void Compile(CodeAllocator* allocator);
+ void CompileBlock(HBasicBlock* block);
+
+ Assembler* const assembler_;
+
+ // Labels for each block that will be compiled.
+ GrowableArray<Label> block_labels_;
+
+ DISALLOW_COPY_AND_ASSIGN(CodeGenerator);
+};
+
+} // namespace art
+
+#endif // ART_COMPILER_OPTIMIZING_CODE_GENERATOR_H_
diff --git a/compiler/optimizing/code_generator_arm.cc b/compiler/optimizing/code_generator_arm.cc
new file mode 100644
index 0000000..99bbaa0
--- /dev/null
+++ b/compiler/optimizing/code_generator_arm.cc
@@ -0,0 +1,65 @@
+/*
+ * Copyright (C) 2014 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 "code_generator_arm.h"
+#include "utils/assembler.h"
+#include "utils/arm/assembler_arm.h"
+
+#define __ reinterpret_cast<ArmAssembler*>(assembler())->
+
+namespace art {
+namespace arm {
+
+void CodeGeneratorARM::GenerateFrameEntry() {
+ RegList registers = (1 << LR) | (1 << FP);
+ __ PushList(registers);
+}
+
+void CodeGeneratorARM::GenerateFrameExit() {
+ RegList registers = (1 << PC) | (1 << FP);
+ __ PopList(registers);
+}
+
+void CodeGeneratorARM::Bind(Label* label) {
+ __ Bind(label);
+}
+
+void CodeGeneratorARM::VisitGoto(HGoto* got) {
+ HBasicBlock* successor = got->GetSuccessor();
+ if (graph()->exit_block() == successor) {
+ GenerateFrameExit();
+ } else if (!GoesToNextBlock(got)) {
+ __ b(GetLabelOf(successor));
+ }
+}
+
+void CodeGeneratorARM::VisitExit(HExit* exit) {
+ if (kIsDebugBuild) {
+ __ Comment("Unreachable");
+ __ bkpt(0);
+ }
+}
+
+void CodeGeneratorARM::VisitIf(HIf* if_instr) {
+ LOG(FATAL) << "UNIMPLEMENTED";
+}
+
+void CodeGeneratorARM::VisitReturnVoid(HReturnVoid* ret) {
+ GenerateFrameExit();
+}
+
+} // namespace arm
+} // namespace art
diff --git a/compiler/optimizing/code_generator_arm.h b/compiler/optimizing/code_generator_arm.h
new file mode 100644
index 0000000..27a83b8
--- /dev/null
+++ b/compiler/optimizing/code_generator_arm.h
@@ -0,0 +1,54 @@
+/*
+ * Copyright (C) 2014 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_OPTIMIZING_CODE_GENERATOR_ARM_H_
+#define ART_COMPILER_OPTIMIZING_CODE_GENERATOR_ARM_H_
+
+#include "code_generator.h"
+#include "nodes.h"
+
+namespace art {
+
+class Assembler;
+class Label;
+
+namespace arm {
+
+class CodeGeneratorARM : public CodeGenerator {
+ public:
+ CodeGeneratorARM(Assembler* assembler, HGraph* graph)
+ : CodeGenerator(assembler, graph) { }
+
+ // Visit functions for instruction classes.
+#define DECLARE_VISIT_INSTRUCTION(name) \
+ virtual void Visit##name(H##name* instr);
+
+ FOR_EACH_INSTRUCTION(DECLARE_VISIT_INSTRUCTION)
+
+#undef DECLARE_VISIT_INSTRUCTION
+
+ private:
+ virtual void GenerateFrameEntry();
+ virtual void GenerateFrameExit();
+ virtual void Bind(Label* label);
+
+ DISALLOW_COPY_AND_ASSIGN(CodeGeneratorARM);
+};
+
+} // namespace arm
+} // namespace art
+
+#endif // ART_COMPILER_OPTIMIZING_CODE_GENERATOR_ARM_H_
diff --git a/compiler/optimizing/code_generator_x86.cc b/compiler/optimizing/code_generator_x86.cc
new file mode 100644
index 0000000..1facfd7
--- /dev/null
+++ b/compiler/optimizing/code_generator_x86.cc
@@ -0,0 +1,66 @@
+/*
+ * Copyright (C) 2014 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 "code_generator_x86.h"
+#include "utils/assembler.h"
+#include "utils/x86/assembler_x86.h"
+
+#define __ reinterpret_cast<X86Assembler*>(assembler())->
+
+namespace art {
+namespace x86 {
+
+void CodeGeneratorX86::GenerateFrameEntry() {
+ __ pushl(EBP);
+ __ movl(EBP, ESP);
+}
+
+void CodeGeneratorX86::GenerateFrameExit() {
+ __ movl(ESP, EBP);
+ __ popl(EBP);
+}
+
+void CodeGeneratorX86::Bind(Label* label) {
+ __ Bind(label);
+}
+
+void CodeGeneratorX86::VisitGoto(HGoto* got) {
+ HBasicBlock* successor = got->GetSuccessor();
+ if (graph()->exit_block() == successor) {
+ GenerateFrameExit();
+ } else if (!GoesToNextBlock(got)) {
+ __ jmp(GetLabelOf(successor));
+ }
+}
+
+void CodeGeneratorX86::VisitExit(HExit* exit) {
+ if (kIsDebugBuild) {
+ __ Comment("Unreachable");
+ __ int3();
+ }
+}
+
+void CodeGeneratorX86::VisitIf(HIf* if_instr) {
+ LOG(FATAL) << "UNIMPLEMENTED";
+}
+
+void CodeGeneratorX86::VisitReturnVoid(HReturnVoid* ret) {
+ GenerateFrameExit();
+ __ ret();
+}
+
+} // namespace x86
+} // namespace art
diff --git a/compiler/optimizing/code_generator_x86.h b/compiler/optimizing/code_generator_x86.h
new file mode 100644
index 0000000..7dae2ab
--- /dev/null
+++ b/compiler/optimizing/code_generator_x86.h
@@ -0,0 +1,54 @@
+/*
+ * Copyright (C) 2014 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_OPTIMIZING_CODE_GENERATOR_X86_H_
+#define ART_COMPILER_OPTIMIZING_CODE_GENERATOR_X86_H_
+
+#include "code_generator.h"
+#include "nodes.h"
+
+namespace art {
+
+class Assembler;
+class Label;
+
+namespace x86 {
+
+class CodeGeneratorX86 : public CodeGenerator {
+ public:
+ CodeGeneratorX86(Assembler* assembler, HGraph* graph)
+ : CodeGenerator(assembler, graph) { }
+
+ // Visit functions for instruction classes.
+#define DECLARE_VISIT_INSTRUCTION(name) \
+ virtual void Visit##name(H##name* instr);
+
+ FOR_EACH_INSTRUCTION(DECLARE_VISIT_INSTRUCTION)
+
+#undef DECLARE_VISIT_INSTRUCTION
+
+ private:
+ virtual void GenerateFrameEntry();
+ virtual void GenerateFrameExit();
+ virtual void Bind(Label* label);
+
+ DISALLOW_COPY_AND_ASSIGN(CodeGeneratorX86);
+};
+
+} // namespace x86
+} // namespace art
+
+#endif // ART_COMPILER_OPTIMIZING_CODE_GENERATOR_X86_H_
diff --git a/compiler/optimizing/codegen_test.cc b/compiler/optimizing/codegen_test.cc
new file mode 100644
index 0000000..dc4999b
--- /dev/null
+++ b/compiler/optimizing/codegen_test.cc
@@ -0,0 +1,124 @@
+/*
+ * Copyright (C) 2014 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 "builder.h"
+#include "code_generator.h"
+#include "common_compiler_test.h"
+#include "dex_instruction.h"
+#include "instruction_set.h"
+#include "nodes.h"
+
+#include "gtest/gtest.h"
+
+namespace art {
+
+class ExecutableMemoryAllocator : public CodeAllocator {
+ public:
+ ExecutableMemoryAllocator() { }
+
+ virtual uint8_t* Allocate(size_t size) {
+ memory_.reset(new uint8_t[size]);
+ CommonCompilerTest::MakeExecutable(memory_.get(), size);
+ return memory_.get();
+ }
+
+ uint8_t* memory() const { return memory_.get(); }
+
+ private:
+ UniquePtr<uint8_t[]> memory_;
+
+ DISALLOW_COPY_AND_ASSIGN(ExecutableMemoryAllocator);
+};
+
+static void TestCode(const uint16_t* data, int length) {
+ ArenaPool pool;
+ ArenaAllocator arena(&pool);
+ HGraphBuilder builder(&arena);
+ HGraph* graph = builder.BuildGraph(data, data + length);
+ ASSERT_NE(graph, nullptr);
+ ExecutableMemoryAllocator allocator;
+ CHECK(CodeGenerator::CompileGraph(graph, kX86, &allocator));
+ typedef void (*fptr)();
+#if defined(__i386__)
+ reinterpret_cast<fptr>(allocator.memory())();
+#endif
+ CHECK(CodeGenerator::CompileGraph(graph, kArm, &allocator));
+#if defined(__arm__)
+ reinterpret_cast<fptr>(allocator.memory())();
+#endif
+}
+
+TEST(CodegenTest, ReturnVoid) {
+ const uint16_t data[] = { Instruction::RETURN_VOID };
+ TestCode(data, sizeof(data) / sizeof(uint16_t));
+}
+
+TEST(PrettyPrinterTest, CFG1) {
+ const uint16_t data[] = {
+ Instruction::GOTO | 0x100,
+ Instruction::RETURN_VOID
+ };
+
+ TestCode(data, sizeof(data) / sizeof(uint16_t));
+}
+
+TEST(PrettyPrinterTest, CFG2) {
+ const uint16_t data[] = {
+ Instruction::GOTO | 0x100,
+ Instruction::GOTO | 0x100,
+ Instruction::RETURN_VOID
+ };
+
+ TestCode(data, sizeof(data) / sizeof(uint16_t));
+}
+
+TEST(PrettyPrinterTest, CFG3) {
+ const uint16_t data1[] = {
+ Instruction::GOTO | 0x200,
+ Instruction::RETURN_VOID,
+ Instruction::GOTO | 0xFF00
+ };
+
+ TestCode(data1, sizeof(data1) / sizeof(uint16_t));
+
+ const uint16_t data2[] = {
+ Instruction::GOTO_16, 3,
+ Instruction::RETURN_VOID,
+ Instruction::GOTO_16, 0xFFFF
+ };
+
+ TestCode(data2, sizeof(data2) / sizeof(uint16_t));
+
+ const uint16_t data3[] = {
+ Instruction::GOTO_32, 4, 0,
+ Instruction::RETURN_VOID,
+ Instruction::GOTO_32, 0xFFFF, 0xFFFF
+ };
+
+ TestCode(data3, sizeof(data3) / sizeof(uint16_t));
+}
+
+TEST(PrettyPrinterTest, CFG4) {
+ const uint16_t data[] = {
+ Instruction::RETURN_VOID,
+ Instruction::GOTO | 0x100,
+ Instruction::GOTO | 0xFE00
+ };
+
+ TestCode(data, sizeof(data) / sizeof(uint16_t));
+}
+
+} // namespace art
diff --git a/compiler/optimizing/nodes.cc b/compiler/optimizing/nodes.cc
index 9ec8e89..aefb089 100644
--- a/compiler/optimizing/nodes.cc
+++ b/compiler/optimizing/nodes.cc
@@ -26,7 +26,7 @@
void HGraph::FindBackEdges(ArenaBitVector* visited) const {
ArenaBitVector visiting(arena_, blocks_.Size(), false);
- VisitBlockForBackEdges(GetEntryBlock(), visited, &visiting);
+ VisitBlockForBackEdges(entry_block_, visited, &visiting);
}
void HGraph::RemoveDeadBlocks(const ArenaBitVector& visited) const {
@@ -75,10 +75,9 @@
// have been processed.
GrowableArray<size_t> visits(arena_, blocks_.Size());
visits.SetSize(blocks_.Size());
- HBasicBlock* entry = GetEntryBlock();
- dominator_order_.Add(entry);
- for (size_t i = 0; i < entry->successors()->Size(); i++) {
- VisitBlockForDominatorTree(entry->successors()->Get(i), entry, &visits);
+ dominator_order_.Add(entry_block_);
+ for (size_t i = 0; i < entry_block_->successors()->Size(); i++) {
+ VisitBlockForDominatorTree(entry_block_->successors()->Get(i), entry_block_, &visits);
}
}
@@ -122,6 +121,7 @@
}
void HBasicBlock::AddInstruction(HInstruction* instruction) {
+ instruction->set_block(this);
if (first_instruction_ == nullptr) {
DCHECK(last_instruction_ == nullptr);
first_instruction_ = last_instruction_ = instruction;
diff --git a/compiler/optimizing/nodes.h b/compiler/optimizing/nodes.h
index 3d5d531..46fe95e 100644
--- a/compiler/optimizing/nodes.h
+++ b/compiler/optimizing/nodes.h
@@ -43,6 +43,13 @@
ArenaAllocator* arena() const { return arena_; }
const GrowableArray<HBasicBlock*>* blocks() const { return &blocks_; }
+ HBasicBlock* entry_block() const { return entry_block_; }
+ HBasicBlock* exit_block() const { return exit_block_; }
+
+ void set_entry_block(HBasicBlock* block) { entry_block_ = block; }
+ void set_exit_block(HBasicBlock* block) { exit_block_ = block; }
+
+
void AddBlock(HBasicBlock* block);
void BuildDominatorTree();
@@ -57,8 +64,6 @@
ArenaBitVector* visiting) const;
void RemoveDeadBlocks(const ArenaBitVector& visited) const;
- HBasicBlock* GetEntryBlock() const { return blocks_.Get(0); }
-
ArenaAllocator* const arena_;
// List of blocks in insertion order.
@@ -67,6 +72,9 @@
// List of blocks to perform a pre-order dominator tree traversal.
GrowableArray<HBasicBlock*> dominator_order_;
+ HBasicBlock* entry_block_;
+ HBasicBlock* exit_block_;
+
DISALLOW_COPY_AND_ASSIGN(HGraph);
};
@@ -174,12 +182,15 @@
class HInstruction : public ArenaObject {
public:
- HInstruction() : previous_(nullptr), next_(nullptr) { }
+ HInstruction() : previous_(nullptr), next_(nullptr), block_(nullptr) { }
virtual ~HInstruction() { }
HInstruction* next() const { return next_; }
HInstruction* previous() const { return previous_; }
+ HBasicBlock* block() const { return block_; }
+ void set_block(HBasicBlock* block) { block_ = block; }
+
virtual intptr_t InputCount() const = 0;
virtual HInstruction* InputAt(intptr_t i) const = 0;
@@ -189,6 +200,7 @@
private:
HInstruction* previous_;
HInstruction* next_;
+ HBasicBlock* block_;
friend class HBasicBlock;
@@ -304,6 +316,10 @@
public:
HGoto() { }
+ HBasicBlock* GetSuccessor() const {
+ return block()->successors()->Get(0);
+ }
+
DECLARE_INSTRUCTION(Goto)
private:
@@ -333,6 +349,8 @@
void VisitInsertionOrder();
+ HGraph* graph() const { return graph_; }
+
// Visit functions for instruction classes.
#define DECLARE_VISIT_INSTRUCTION(name) \
virtual void Visit##name(H##name* instr) { VisitInstruction(instr); }