diff options
Diffstat (limited to 'compiler/optimizing')
-rw-r--r-- | compiler/optimizing/builder.cc | 64 | ||||
-rw-r--r-- | compiler/optimizing/builder.h | 57 | ||||
-rw-r--r-- | compiler/optimizing/nodes.cc | 60 | ||||
-rw-r--r-- | compiler/optimizing/nodes.h | 274 | ||||
-rw-r--r-- | compiler/optimizing/pretty_printer.h | 51 | ||||
-rw-r--r-- | compiler/optimizing/pretty_printer_test.cc | 87 |
6 files changed, 593 insertions, 0 deletions
diff --git a/compiler/optimizing/builder.cc b/compiler/optimizing/builder.cc new file mode 100644 index 0000000..2c1091c --- /dev/null +++ b/compiler/optimizing/builder.cc @@ -0,0 +1,64 @@ +/* + * + * 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 "dex_instruction.h" +#include "builder.h" +#include "nodes.h" + +namespace art { + +HGraph* HGraphBuilder::BuildGraph(const uint16_t* code_ptr, const uint16_t* code_end) { + graph_ = new (arena_) HGraph(arena_); + + entry_block_ = new (arena_) HBasicBlock(graph_); + graph_->AddBlock(entry_block_); + + exit_block_ = new (arena_) HBasicBlock(graph_); + // The exit block is added at the end of this method to ensure + // its id is the greatest. This is needed for dominator computation. + + entry_block_->AddInstruction(new (arena_) HGoto(entry_block_)); + + current_block_ = new (arena_) HBasicBlock(graph_); + graph_->AddBlock(current_block_); + entry_block_->AddSuccessor(current_block_); + + while (code_ptr < code_end) { + const Instruction& instruction = *Instruction::At(code_ptr); + if (!AnalyzeDexInstruction(instruction)) return nullptr; + code_ptr += instruction.SizeInCodeUnits(); + } + + exit_block_->AddInstruction(new (arena_) HExit(exit_block_)); + graph_->AddBlock(exit_block_); + return graph_; +} + +bool HGraphBuilder::AnalyzeDexInstruction(const Instruction& instruction) { + switch (instruction.Opcode()) { + case Instruction::RETURN_VOID: + current_block_->AddInstruction(new (arena_) HReturnVoid(current_block_)); + current_block_->AddSuccessor(exit_block_); + current_block_ = nullptr; + break; + default: + return false; + } + return true; +} + +} // namespace art diff --git a/compiler/optimizing/builder.h b/compiler/optimizing/builder.h new file mode 100644 index 0000000..3e94fba --- /dev/null +++ b/compiler/optimizing/builder.h @@ -0,0 +1,57 @@ +/* + * 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_BUILDER_H_ +#define ART_COMPILER_OPTIMIZING_BUILDER_H_ + +#include "utils/allocation.h" + +namespace art { + +class ArenaAllocator; +class Instruction; +class HBasicBlock; +class HGraph; + +class HGraphBuilder : public ValueObject { + public: + explicit HGraphBuilder(ArenaAllocator* arena) + : arena_(arena), + entry_block_(nullptr), + exit_block_(nullptr), + current_block_(nullptr), + graph_(nullptr) { } + + HGraph* BuildGraph(const uint16_t* start, const uint16_t* end); + + private: + // Analyzes the dex instruction and adds HInstruction to the graph + // to execute that instruction. Returns whether the instruction can + // be handled. + bool AnalyzeDexInstruction(const Instruction& instruction); + + ArenaAllocator* const arena_; + HBasicBlock* entry_block_; + HBasicBlock* exit_block_; + HBasicBlock* current_block_; + HGraph* graph_; + + DISALLOW_COPY_AND_ASSIGN(HGraphBuilder); +}; + +} // namespace art + +#endif // ART_COMPILER_OPTIMIZING_BUILDER_H_ diff --git a/compiler/optimizing/nodes.cc b/compiler/optimizing/nodes.cc new file mode 100644 index 0000000..e7e9f47 --- /dev/null +++ b/compiler/optimizing/nodes.cc @@ -0,0 +1,60 @@ +/* + * 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 "nodes.h" +#include "utils/growable_array.h" + +namespace art { + +void HGraph::AddBlock(HBasicBlock* block) { + block->set_block_id(blocks_.Size()); + blocks_.Add(block); +} + +void HBasicBlock::AddInstruction(HInstruction* instruction) { + if (first_instruction_ == nullptr) { + DCHECK(last_instruction_ == nullptr); + first_instruction_ = last_instruction_ = instruction; + } else { + last_instruction_->next_ = instruction; + instruction->previous_ = last_instruction_; + last_instruction_ = instruction; + } +} + +#define DEFINE_ACCEPT(name) \ +void H##name::Accept(HGraphVisitor* visitor) { \ + visitor->Visit##name(this); \ +} + +FOR_EACH_INSTRUCTION(DEFINE_ACCEPT) + +#undef DEFINE_ACCEPT + +void HGraphVisitor::VisitInsertionOrder() { + const GrowableArray<HBasicBlock*>* blocks = graph_->blocks(); + for (size_t i = 0 ; i < blocks->Size(); i++) { + VisitBasicBlock(blocks->Get(i)); + } +} + +void HGraphVisitor::VisitBasicBlock(HBasicBlock* block) { + for (HInstructionIterator it(block); !it.Done(); it.Advance()) { + it.Current()->Accept(this); + } +} + +} // namespace art diff --git a/compiler/optimizing/nodes.h b/compiler/optimizing/nodes.h new file mode 100644 index 0000000..9365670 --- /dev/null +++ b/compiler/optimizing/nodes.h @@ -0,0 +1,274 @@ +/* + * 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_NODES_H_ +#define ART_COMPILER_OPTIMIZING_NODES_H_ + +#include "utils/allocation.h" +#include "utils/growable_array.h" + +namespace art { + +class HBasicBlock; +class HInstruction; +class HGraphVisitor; + +static const int kDefaultNumberOfBlocks = 8; +static const int kDefaultNumberOfSuccessors = 2; +static const int kDefaultNumberOfPredecessors = 2; + +// Control-flow graph of a method. Contains a list of basic blocks. +class HGraph : public ArenaObject { + public: + explicit HGraph(ArenaAllocator* arena) + : arena_(arena), + blocks_(arena, kDefaultNumberOfBlocks) { } + + ArenaAllocator* arena() const { return arena_; } + const GrowableArray<HBasicBlock*>* blocks() const { return &blocks_; } + + void AddBlock(HBasicBlock* block); + + private: + ArenaAllocator* const arena_; + GrowableArray<HBasicBlock*> blocks_; + + DISALLOW_COPY_AND_ASSIGN(HGraph); +}; + +// A block in a method. Contains the list of instructions represented +// as a double linked list. Each block knows its predecessors and +// successors. +class HBasicBlock : public ArenaObject { + public: + explicit HBasicBlock(HGraph* graph) + : graph_(graph), + predecessors_(graph->arena(), kDefaultNumberOfPredecessors), + successors_(graph->arena(), kDefaultNumberOfSuccessors), + first_instruction_(nullptr), + last_instruction_(nullptr), + block_id_(-1) { } + + const GrowableArray<HBasicBlock*>* predecessors() const { + return &predecessors_; + } + + const GrowableArray<HBasicBlock*>* successors() const { + return &successors_; + } + + HGraph* graph() const { return graph_; } + + int block_id() const { return block_id_; } + void set_block_id(int id) { block_id_ = id; } + + HInstruction* first_instruction() const { return first_instruction_; } + HInstruction* last_instruction() const { return last_instruction_; } + + void AddSuccessor(HBasicBlock* block) { + successors_.Add(block); + block->predecessors_.Add(this); + } + + void AddInstruction(HInstruction* instruction); + + private: + HGraph* const graph_; + GrowableArray<HBasicBlock*> predecessors_; + GrowableArray<HBasicBlock*> successors_; + HInstruction* first_instruction_; + HInstruction* last_instruction_; + int block_id_; + + DISALLOW_COPY_AND_ASSIGN(HBasicBlock); +}; + +#define FOR_EACH_INSTRUCTION(M) \ + M(Exit) \ + M(Goto) \ + M(ReturnVoid) \ + +#define DECLARE_INSTRUCTION(type) \ + virtual void Accept(HGraphVisitor* visitor); \ + virtual const char* DebugName() const { return #type; } \ + +class HInstruction : public ArenaObject { + public: + explicit HInstruction(HBasicBlock* block) + : previous_(nullptr), + next_(nullptr) { } + + HInstruction* next() const { return next_; } + HInstruction* previous() const { return previous_; } + + virtual intptr_t InputCount() const = 0; + virtual HInstruction* InputAt(intptr_t i) const = 0; + + virtual void Accept(HGraphVisitor* visitor) = 0; + virtual const char* DebugName() const = 0; + + private: + HInstruction* previous_; + HInstruction* next_; + + friend class HBasicBlock; + + DISALLOW_COPY_AND_ASSIGN(HInstruction); +}; + +class HInstructionIterator : public ValueObject { + public: + explicit HInstructionIterator(HBasicBlock* block) + : instruction_(block->first_instruction()) { + next_ = Done() ? nullptr : instruction_->next(); + } + + inline bool Done() const { return instruction_ == nullptr; } + inline HInstruction* Current() { return instruction_; } + inline void Advance() { + instruction_ = next_; + next_ = Done() ? nullptr : instruction_->next(); + } + + private: + HInstruction* instruction_; + HInstruction* next_; +}; + +// An embedded container with N elements of type T. Used (with partial +// specialization for N=0) because embedded arrays cannot have size 0. +template<typename T, intptr_t N> +class EmbeddedArray { + public: + EmbeddedArray() : elements_() { } + + intptr_t length() const { return N; } + + const T& operator[](intptr_t i) const { + ASSERT(i < length()); + return elements_[i]; + } + + T& operator[](intptr_t i) { + ASSERT(i < length()); + return elements_[i]; + } + + const T& At(intptr_t i) const { + return (*this)[i]; + } + + void SetAt(intptr_t i, const T& val) { + (*this)[i] = val; + } + + private: + T elements_[N]; +}; + +template<typename T> +class EmbeddedArray<T, 0> { + public: + intptr_t length() const { return 0; } + const T& operator[](intptr_t i) const { + LOG(FATAL) << "Unreachable"; + static T sentinel = 0; + return sentinel; + } + T& operator[](intptr_t i) { + LOG(FATAL) << "Unreachable"; + static T sentinel = 0; + return sentinel; + } +}; + +template<intptr_t N> +class HTemplateInstruction: public HInstruction { + public: + HTemplateInstruction<N>(HBasicBlock* block) + : HInstruction(block), + inputs_() { } + + virtual intptr_t InputCount() const { return N; } + virtual HInstruction* InputAt(intptr_t i) const { return inputs_[i]; } + + private: + EmbeddedArray<HInstruction*, N> inputs_; +}; + +// Represents dex's RETURN_VOID opcode. A HReturnVoid is a control flow +// instruction that branches to the exit block. +class HReturnVoid : public HTemplateInstruction<0> { + public: + explicit HReturnVoid(HBasicBlock* block) : HTemplateInstruction<0>(block) { } + + DECLARE_INSTRUCTION(ReturnVoid) + + private: + DISALLOW_COPY_AND_ASSIGN(HReturnVoid); +}; + +// The exit instruction is the only instruction of the exit block. +// Instructions aborting the method (HTrow and HReturn) must branch to the +// exit block. +class HExit : public HTemplateInstruction<0> { + public: + explicit HExit(HBasicBlock* block) : HTemplateInstruction<0>(block) { } + + DECLARE_INSTRUCTION(Exit) + + private: + DISALLOW_COPY_AND_ASSIGN(HExit); +}; + +// Jumps from one block to another. +class HGoto : public HTemplateInstruction<0> { + public: + explicit HGoto(HBasicBlock* block) : HTemplateInstruction<0>(block) { } + + DECLARE_INSTRUCTION(Goto) + + private: + DISALLOW_COPY_AND_ASSIGN(HGoto); +}; + +class HGraphVisitor : public ValueObject { + public: + explicit HGraphVisitor(HGraph* graph) : graph_(graph) { } + virtual ~HGraphVisitor() { } + + virtual void VisitInstruction(HInstruction* instruction) { } + virtual void VisitBasicBlock(HBasicBlock* block); + + void VisitInsertionOrder(); + + // Visit functions for instruction classes. +#define DECLARE_VISIT_INSTRUCTION(name) \ + virtual void Visit##name(H##name* instr) { VisitInstruction(instr); } + + FOR_EACH_INSTRUCTION(DECLARE_VISIT_INSTRUCTION) + +#undef DECLARE_VISIT_INSTRUCTION + + private: + HGraph* graph_; + + DISALLOW_COPY_AND_ASSIGN(HGraphVisitor); +}; + +} // namespace art + +#endif // ART_COMPILER_OPTIMIZING_NODES_H_ diff --git a/compiler/optimizing/pretty_printer.h b/compiler/optimizing/pretty_printer.h new file mode 100644 index 0000000..62a5a2c --- /dev/null +++ b/compiler/optimizing/pretty_printer.h @@ -0,0 +1,51 @@ +/* + * 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_PRETTY_PRINTER_H_ +#define ART_COMPILER_OPTIMIZING_PRETTY_PRINTER_H_ + +#include "nodes.h" + +namespace art { + +class HPrettyPrinter : public HGraphVisitor { + public: + explicit HPrettyPrinter(HGraph* graph) : HGraphVisitor(graph) { } + + virtual void VisitInstruction(HInstruction* instruction) { + PrintString(" "); + PrintString(instruction->DebugName()); + PrintNewLine(); + } + + virtual void VisitBasicBlock(HBasicBlock* block) { + PrintString("BasicBlock "); + PrintInt(block->block_id()); + PrintNewLine(); + HGraphVisitor::VisitBasicBlock(block); + } + + virtual void PrintNewLine() = 0; + virtual void PrintInt(int value) = 0; + virtual void PrintString(const char* value) = 0; + + private: + DISALLOW_COPY_AND_ASSIGN(HPrettyPrinter); +}; + +} // namespace art + +#endif // ART_COMPILER_OPTIMIZING_PRETTY_PRINTER_H_ diff --git a/compiler/optimizing/pretty_printer_test.cc b/compiler/optimizing/pretty_printer_test.cc new file mode 100644 index 0000000..81a0d91 --- /dev/null +++ b/compiler/optimizing/pretty_printer_test.cc @@ -0,0 +1,87 @@ +/* + * 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 "base/stringprintf.h" +#include "builder.h" +#include "dex_instruction.h" +#include "nodes.h" +#include "pretty_printer.h" +#include "utils/arena_allocator.h" + +#include "gtest/gtest.h" + +namespace art { + +const uint16_t data[] = { Instruction::RETURN_VOID }; + +const char* expected = + "BasicBlock 0\n" + " Goto\n" + "BasicBlock 1\n" + " ReturnVoid\n" + "BasicBlock 2\n" + " Exit\n"; + +class StringPrettyPrinter : public HPrettyPrinter { + public: + explicit StringPrettyPrinter(HGraph* graph) : HPrettyPrinter(graph), str_("") { } + + virtual void PrintInt(int value) { + str_ += StringPrintf("%d", value); + } + + virtual void PrintString(const char* value) { + str_ += value; + } + + virtual void PrintNewLine() { + str_ += '\n'; + } + + void Clear() { str_.clear(); } + + std::string str() const { return str_; } + + private: + std::string str_; + DISALLOW_COPY_AND_ASSIGN(StringPrettyPrinter); +}; + +TEST(OptimizerTest, ReturnVoid) { + ArenaPool pool; + ArenaAllocator allocator(&pool); + HGraphBuilder builder(&allocator); + HGraph* graph = builder.BuildGraph(data, data + 1); + ASSERT_NE(graph, nullptr); + StringPrettyPrinter printer(graph); + printer.VisitInsertionOrder(); + ASSERT_STREQ(expected, printer.str().c_str()); + + const GrowableArray<HBasicBlock*>* blocks = graph->blocks(); + ASSERT_EQ(blocks->Get(0)->predecessors()->Size(), (size_t)0); + ASSERT_EQ(blocks->Get(1)->predecessors()->Size(), (size_t)1); + ASSERT_EQ(blocks->Get(1)->predecessors()->Get(0), blocks->Get(0)); + ASSERT_EQ(blocks->Get(2)->predecessors()->Size(), (size_t)1); + ASSERT_EQ(blocks->Get(2)->predecessors()->Get(0), blocks->Get(1)); + + ASSERT_EQ(blocks->Get(0)->successors()->Size(), (size_t)1); + ASSERT_EQ(blocks->Get(1)->successors()->Get(0), blocks->Get(2)); + ASSERT_EQ(blocks->Get(1)->successors()->Size(), (size_t)1); + ASSERT_EQ(blocks->Get(1)->successors()->Get(0), blocks->Get(2)); + ASSERT_EQ(blocks->Get(2)->successors()->Size(), (size_t)0); +} + +} // namespace art |