From 3ff386aafefd5282bb76c8a50506a70a4321e698 Mon Sep 17 00:00:00 2001 From: Nicolas Geoffray Date: Tue, 4 Mar 2014 14:46:47 +0000 Subject: Add register support to the optimizing compiler. Also make if take an input and build the use list for instructions. Change-Id: I1938cee7dce5bd4c66b259fa2b431d2c79b3cf82 --- compiler/optimizing/builder.cc | 76 ++++++++++- compiler/optimizing/builder.h | 21 +++- compiler/optimizing/code_generator_arm.cc | 20 +++ compiler/optimizing/code_generator_x86.cc | 20 +++ compiler/optimizing/codegen_test.cc | 53 ++++---- compiler/optimizing/dominator_test.cc | 135 ++++++++++---------- compiler/optimizing/nodes.cc | 4 + compiler/optimizing/nodes.h | 181 ++++++++++++++++++++++++-- compiler/optimizing/optimizing_unit_test.h | 29 +++++ compiler/optimizing/pretty_printer.h | 28 +++++ compiler/optimizing/pretty_printer_test.cc | 195 +++++++++++++++++------------ 11 files changed, 563 insertions(+), 199 deletions(-) create mode 100644 compiler/optimizing/optimizing_unit_test.h diff --git a/compiler/optimizing/builder.cc b/compiler/optimizing/builder.cc index f78e56bf5f..190c92562f 100644 --- a/compiler/optimizing/builder.cc +++ b/compiler/optimizing/builder.cc @@ -15,23 +15,46 @@ * limitations under the License. */ +#include "dex_file.h" #include "dex_instruction.h" +#include "dex_instruction-inl.h" #include "builder.h" #include "nodes.h" namespace art { -HGraph* HGraphBuilder::BuildGraph(const uint16_t* code_ptr, const uint16_t* code_end) { +void HGraphBuilder::InitializeLocals(int count) { + locals_.SetSize(count); + for (int i = 0; i < count; i++) { + HLocal* local = new (arena_) HLocal(i); + entry_block_->AddInstruction(local); + locals_.Put(0, local); + } +} + +static bool CanHandleCodeItem(const DexFile::CodeItem& code_item) { + if (code_item.tries_size_ > 0) return false; + if (code_item.outs_size_ > 0) return false; + if (code_item.ins_size_ > 0) return false; + return true; +} + +HGraph* HGraphBuilder::BuildGraph(const DexFile::CodeItem& code_item) { + if (!CanHandleCodeItem(code_item)) return nullptr; + + const uint16_t* code_ptr = code_item.insns_; + const uint16_t* code_end = code_item.insns_ + code_item.insns_size_in_code_units_; + // Setup the graph with the entry block and exit block. graph_ = new (arena_) HGraph(arena_); entry_block_ = new (arena_) HBasicBlock(graph_); graph_->AddBlock(entry_block_); - 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_); + InitializeLocals(code_item.registers_size_); + // To avoid splitting blocks, we compute ahead of time the instructions that // start a new block, and create these blocks. ComputeBranchTargets(code_ptr, code_end); @@ -48,6 +71,8 @@ HGraph* HGraphBuilder::BuildGraph(const uint16_t* code_ptr, const uint16_t* code // Add the exit block at the end to give it the highest id. graph_->AddBlock(exit_block_); + exit_block_->AddInstruction(new (arena_) HExit()); + entry_block_->AddInstruction(new (arena_) HGoto()); return graph_; } @@ -109,16 +134,24 @@ bool HGraphBuilder::AnalyzeDexInstruction(const Instruction& instruction, int32_ if (current_block_ == nullptr) return true; // Dead code switch (instruction.Opcode()) { + case Instruction::CONST_4: { + int32_t register_index = instruction.VRegA(); + HIntConstant* constant = GetConstant(instruction.VRegB_11n()); + UpdateLocal(register_index, constant); + break; + } case Instruction::RETURN_VOID: current_block_->AddInstruction(new (arena_) HReturnVoid()); current_block_->AddSuccessor(exit_block_); current_block_ = nullptr; break; case Instruction::IF_EQ: { - // TODO: Read the dex register. + HInstruction* first = LoadLocal(instruction.VRegA()); + HInstruction* second = LoadLocal(instruction.VRegB()); + current_block_->AddInstruction(new (arena_) HEqual(first, second)); + current_block_->AddInstruction(new (arena_) HIf(current_block_->last_instruction())); HBasicBlock* target = FindBlockStartingAt(instruction.GetTargetOffset() + dex_offset); DCHECK(target != nullptr); - current_block_->AddInstruction(new (arena_) HIf()); current_block_->AddSuccessor(target); target = FindBlockStartingAt(dex_offset + instruction.SizeInCodeUnits()); DCHECK(target != nullptr); @@ -144,4 +177,37 @@ bool HGraphBuilder::AnalyzeDexInstruction(const Instruction& instruction, int32_ return true; } +HIntConstant* HGraphBuilder::GetConstant0() { + if (constant0_ != nullptr) return constant0_; + HIntConstant* constant = new(arena_) HIntConstant(0); + entry_block_->AddInstruction(constant); + return constant; +} + +HIntConstant* HGraphBuilder::GetConstant(int constant) { + switch (constant) { + case 0: return GetConstant0(); + default: { + HIntConstant* instruction = new (arena_) HIntConstant(constant); + entry_block_->AddInstruction(instruction); + return instruction; + } + } +} + +HLocal* HGraphBuilder::GetLocalAt(int register_index) const { + return locals_.Get(register_index); +} + +void HGraphBuilder::UpdateLocal(int register_index, HInstruction* instruction) const { + HLocal* local = GetLocalAt(register_index); + current_block_->AddInstruction(new (arena_) HStoreLocal(local, instruction)); +} + +HInstruction* HGraphBuilder::LoadLocal(int register_index) const { + HLocal* local = GetLocalAt(register_index); + current_block_->AddInstruction(new (arena_) HLoadLocal(local)); + return current_block_->last_instruction(); +} + } // namespace art diff --git a/compiler/optimizing/builder.h b/compiler/optimizing/builder.h index fbeb7a7dab..399dd63ae0 100644 --- a/compiler/optimizing/builder.h +++ b/compiler/optimizing/builder.h @@ -17,6 +17,7 @@ #ifndef ART_COMPILER_OPTIMIZING_BUILDER_H_ #define ART_COMPILER_OPTIMIZING_BUILDER_H_ +#include "dex_file.h" #include "utils/allocation.h" #include "utils/growable_array.h" @@ -26,18 +27,23 @@ class ArenaAllocator; class Instruction; class HBasicBlock; class HGraph; +class HIntConstant; +class HInstruction; +class HLocal; class HGraphBuilder : public ValueObject { public: explicit HGraphBuilder(ArenaAllocator* arena) : arena_(arena), branch_targets_(arena, 0), + locals_(arena, 0), entry_block_(nullptr), exit_block_(nullptr), current_block_(nullptr), - graph_(nullptr) { } + graph_(nullptr), + constant0_(nullptr) { } - HGraph* BuildGraph(const uint16_t* start, const uint16_t* end); + HGraph* BuildGraph(const DexFile::CodeItem& code); private: // Analyzes the dex instruction and adds HInstruction to the graph @@ -51,6 +57,13 @@ class HGraphBuilder : public ValueObject { void MaybeUpdateCurrentBlock(size_t index); HBasicBlock* FindBlockStartingAt(int32_t index) const; + HIntConstant* GetConstant0(); + HIntConstant* GetConstant(int constant); + void InitializeLocals(int count); + HLocal* GetLocalAt(int register_index) const; + void UpdateLocal(int register_index, HInstruction* instruction) const; + HInstruction* LoadLocal(int register_index) const; + ArenaAllocator* const arena_; // A list of the size of the dex code holding block information for @@ -58,11 +71,15 @@ class HGraphBuilder : public ValueObject { // starting at that entry is the first instruction of a new block. GrowableArray branch_targets_; + GrowableArray locals_; + HBasicBlock* entry_block_; HBasicBlock* exit_block_; HBasicBlock* current_block_; HGraph* graph_; + HIntConstant* constant0_; + DISALLOW_COPY_AND_ASSIGN(HGraphBuilder); }; diff --git a/compiler/optimizing/code_generator_arm.cc b/compiler/optimizing/code_generator_arm.cc index 99bbaa0514..356e909467 100644 --- a/compiler/optimizing/code_generator_arm.cc +++ b/compiler/optimizing/code_generator_arm.cc @@ -57,6 +57,26 @@ void CodeGeneratorARM::VisitIf(HIf* if_instr) { LOG(FATAL) << "UNIMPLEMENTED"; } +void CodeGeneratorARM::VisitEqual(HEqual* equal) { + LOG(FATAL) << "UNIMPLEMENTED"; +} + +void CodeGeneratorARM::VisitLocal(HLocal* local) { + LOG(FATAL) << "UNIMPLEMENTED"; +} + +void CodeGeneratorARM::VisitLoadLocal(HLoadLocal* local) { + LOG(FATAL) << "UNIMPLEMENTED"; +} + +void CodeGeneratorARM::VisitStoreLocal(HStoreLocal* local) { + LOG(FATAL) << "UNIMPLEMENTED"; +} + +void CodeGeneratorARM::VisitIntConstant(HIntConstant* constant) { + LOG(FATAL) << "UNIMPLEMENTED"; +} + void CodeGeneratorARM::VisitReturnVoid(HReturnVoid* ret) { GenerateFrameExit(); } diff --git a/compiler/optimizing/code_generator_x86.cc b/compiler/optimizing/code_generator_x86.cc index 1facfd7eea..ab34599c94 100644 --- a/compiler/optimizing/code_generator_x86.cc +++ b/compiler/optimizing/code_generator_x86.cc @@ -57,6 +57,26 @@ void CodeGeneratorX86::VisitIf(HIf* if_instr) { LOG(FATAL) << "UNIMPLEMENTED"; } +void CodeGeneratorX86::VisitLocal(HLocal* local) { + LOG(FATAL) << "UNIMPLEMENTED"; +} + +void CodeGeneratorX86::VisitLoadLocal(HLoadLocal* local) { + LOG(FATAL) << "UNIMPLEMENTED"; +} + +void CodeGeneratorX86::VisitStoreLocal(HStoreLocal* local) { + LOG(FATAL) << "UNIMPLEMENTED"; +} + +void CodeGeneratorX86::VisitEqual(HEqual* equal) { + LOG(FATAL) << "UNIMPLEMENTED"; +} + +void CodeGeneratorX86::VisitIntConstant(HIntConstant* constant) { + LOG(FATAL) << "UNIMPLEMENTED"; +} + void CodeGeneratorX86::VisitReturnVoid(HReturnVoid* ret) { GenerateFrameExit(); __ ret(); diff --git a/compiler/optimizing/codegen_test.cc b/compiler/optimizing/codegen_test.cc index dc4999b114..6d4588dd3d 100644 --- a/compiler/optimizing/codegen_test.cc +++ b/compiler/optimizing/codegen_test.cc @@ -17,9 +17,11 @@ #include "builder.h" #include "code_generator.h" #include "common_compiler_test.h" +#include "dex_file.h" #include "dex_instruction.h" #include "instruction_set.h" #include "nodes.h" +#include "optimizing_unit_test.h" #include "gtest/gtest.h" @@ -43,11 +45,12 @@ class ExecutableMemoryAllocator : public CodeAllocator { DISALLOW_COPY_AND_ASSIGN(ExecutableMemoryAllocator); }; -static void TestCode(const uint16_t* data, int length) { +static void TestCode(const uint16_t* data) { ArenaPool pool; ArenaAllocator arena(&pool); HGraphBuilder builder(&arena); - HGraph* graph = builder.BuildGraph(data, data + length); + const DexFile::CodeItem* item = reinterpret_cast(data); + HGraph* graph = builder.BuildGraph(*item); ASSERT_NE(graph, nullptr); ExecutableMemoryAllocator allocator; CHECK(CodeGenerator::CompileGraph(graph, kX86, &allocator)); @@ -62,63 +65,57 @@ static void TestCode(const uint16_t* data, int length) { } TEST(CodegenTest, ReturnVoid) { - const uint16_t data[] = { Instruction::RETURN_VOID }; - TestCode(data, sizeof(data) / sizeof(uint16_t)); + const uint16_t data[] = ZERO_REGISTER_CODE_ITEM(Instruction::RETURN_VOID); + TestCode(data); } TEST(PrettyPrinterTest, CFG1) { - const uint16_t data[] = { + const uint16_t data[] = ZERO_REGISTER_CODE_ITEM( Instruction::GOTO | 0x100, - Instruction::RETURN_VOID - }; + Instruction::RETURN_VOID); - TestCode(data, sizeof(data) / sizeof(uint16_t)); + TestCode(data); } TEST(PrettyPrinterTest, CFG2) { - const uint16_t data[] = { + const uint16_t data[] = ZERO_REGISTER_CODE_ITEM( Instruction::GOTO | 0x100, Instruction::GOTO | 0x100, - Instruction::RETURN_VOID - }; + Instruction::RETURN_VOID); - TestCode(data, sizeof(data) / sizeof(uint16_t)); + TestCode(data); } TEST(PrettyPrinterTest, CFG3) { - const uint16_t data1[] = { + const uint16_t data1[] = ZERO_REGISTER_CODE_ITEM( Instruction::GOTO | 0x200, Instruction::RETURN_VOID, - Instruction::GOTO | 0xFF00 - }; + Instruction::GOTO | 0xFF00); - TestCode(data1, sizeof(data1) / sizeof(uint16_t)); + TestCode(data1); - const uint16_t data2[] = { + const uint16_t data2[] = ZERO_REGISTER_CODE_ITEM( Instruction::GOTO_16, 3, Instruction::RETURN_VOID, - Instruction::GOTO_16, 0xFFFF - }; + Instruction::GOTO_16, 0xFFFF); - TestCode(data2, sizeof(data2) / sizeof(uint16_t)); + TestCode(data2); - const uint16_t data3[] = { + const uint16_t data3[] = ZERO_REGISTER_CODE_ITEM( Instruction::GOTO_32, 4, 0, Instruction::RETURN_VOID, - Instruction::GOTO_32, 0xFFFF, 0xFFFF - }; + Instruction::GOTO_32, 0xFFFF, 0xFFFF); - TestCode(data3, sizeof(data3) / sizeof(uint16_t)); + TestCode(data3); } TEST(PrettyPrinterTest, CFG4) { - const uint16_t data[] = { + const uint16_t data[] = ZERO_REGISTER_CODE_ITEM( Instruction::RETURN_VOID, Instruction::GOTO | 0x100, - Instruction::GOTO | 0xFE00 - }; + Instruction::GOTO | 0xFE00); - TestCode(data, sizeof(data) / sizeof(uint16_t)); + TestCode(data); } } // namespace art diff --git a/compiler/optimizing/dominator_test.cc b/compiler/optimizing/dominator_test.cc index 30f288ff54..9b68535268 100644 --- a/compiler/optimizing/dominator_test.cc +++ b/compiler/optimizing/dominator_test.cc @@ -17,17 +17,19 @@ #include "builder.h" #include "dex_instruction.h" #include "nodes.h" +#include "optimizing_unit_test.h" #include "utils/arena_allocator.h" #include "gtest/gtest.h" namespace art { -static void TestCode(const uint16_t* data, int length, const int* blocks, size_t blocks_length) { +static void TestCode(const uint16_t* data, const int* blocks, size_t blocks_length) { ArenaPool pool; ArenaAllocator allocator(&pool); HGraphBuilder builder(&allocator); - HGraph* graph = builder.BuildGraph(data, data + length); + const DexFile::CodeItem* item = reinterpret_cast(data); + HGraph* graph = builder.BuildGraph(*item); ASSERT_NE(graph, nullptr); graph->BuildDominatorTree(); ASSERT_EQ(graph->blocks()->Size(), blocks_length); @@ -42,9 +44,8 @@ static void TestCode(const uint16_t* data, int length, const int* blocks, size_t } TEST(OptimizerTest, ReturnVoid) { - const uint16_t data[] = { - Instruction::RETURN_VOID // Block number 1 - }; + const uint16_t data[] = ZERO_REGISTER_CODE_ITEM( + Instruction::RETURN_VOID); // Block number 1 const int dominators[] = { -1, @@ -52,14 +53,13 @@ TEST(OptimizerTest, ReturnVoid) { 1 }; - TestCode(data, sizeof(data) / sizeof(uint16_t), dominators, sizeof(dominators) / sizeof(int)); + TestCode(data, dominators, sizeof(dominators) / sizeof(int)); } TEST(OptimizerTest, CFG1) { - const uint16_t data[] = { + const uint16_t data[] = ZERO_REGISTER_CODE_ITEM( Instruction::GOTO | 0x100, // Block number 1 - Instruction::RETURN_VOID // Block number 2 - }; + Instruction::RETURN_VOID); // Block number 2 const int dominators[] = { -1, @@ -68,15 +68,14 @@ TEST(OptimizerTest, CFG1) { 2 }; - TestCode(data, sizeof(data) / sizeof(uint16_t), dominators, sizeof(dominators) / sizeof(int)); + TestCode(data, dominators, sizeof(dominators) / sizeof(int)); } TEST(OptimizerTest, CFG2) { - const uint16_t data[] = { + const uint16_t data[] = ZERO_REGISTER_CODE_ITEM( Instruction::GOTO | 0x100, // Block number 1 Instruction::GOTO | 0x100, // Block number 2 - Instruction::RETURN_VOID // Block number 3 - }; + Instruction::RETURN_VOID); // Block number 3 const int dominators[] = { -1, @@ -86,15 +85,15 @@ TEST(OptimizerTest, CFG2) { 3 }; - TestCode(data, sizeof(data) / sizeof(uint16_t), dominators, sizeof(dominators) / sizeof(int)); + TestCode(data, dominators, sizeof(dominators) / sizeof(int)); } TEST(OptimizerTest, CFG3) { - const uint16_t data1[] = { - Instruction::GOTO | 0x200, // Block number 1 - Instruction::RETURN_VOID, // Block number 2 - Instruction::GOTO | 0xFF00 // Block number 3 - }; + const uint16_t data1[] = ZERO_REGISTER_CODE_ITEM( + Instruction::GOTO | 0x200, // Block number 1 + Instruction::RETURN_VOID, // Block number 2 + Instruction::GOTO | 0xFF00); // Block number 3 + const int dominators[] = { -1, 0, @@ -103,30 +102,27 @@ TEST(OptimizerTest, CFG3) { 2 }; - TestCode(data1, sizeof(data1) / sizeof(uint16_t), dominators, sizeof(dominators) / sizeof(int)); + TestCode(data1, dominators, sizeof(dominators) / sizeof(int)); - const uint16_t data2[] = { + const uint16_t data2[] = ZERO_REGISTER_CODE_ITEM( Instruction::GOTO_16, 3, Instruction::RETURN_VOID, - Instruction::GOTO_16, 0xFFFF - }; + Instruction::GOTO_16, 0xFFFF); - TestCode(data2, sizeof(data2) / sizeof(uint16_t), dominators, sizeof(dominators) / sizeof(int)); + TestCode(data2, dominators, sizeof(dominators) / sizeof(int)); - const uint16_t data3[] = { + const uint16_t data3[] = ZERO_REGISTER_CODE_ITEM( Instruction::GOTO_32, 4, 0, Instruction::RETURN_VOID, - Instruction::GOTO_32, 0xFFFF, 0xFFFF - }; + Instruction::GOTO_32, 0xFFFF, 0xFFFF); - TestCode(data3, sizeof(data3) / sizeof(uint16_t), dominators, sizeof(dominators) / sizeof(int)); + TestCode(data3, dominators, sizeof(dominators) / sizeof(int)); } TEST(OptimizerTest, CFG4) { - const uint16_t data1[] = { + const uint16_t data1[] = ZERO_REGISTER_CODE_ITEM( Instruction::NOP, - Instruction::GOTO | 0xFF00 - }; + Instruction::GOTO | 0xFF00); const int dominators[] = { -1, @@ -134,21 +130,20 @@ TEST(OptimizerTest, CFG4) { -1 }; - TestCode(data1, sizeof(data1) / sizeof(uint16_t), dominators, sizeof(dominators) / sizeof(int)); + TestCode(data1, dominators, sizeof(dominators) / sizeof(int)); - const uint16_t data2[] = { - Instruction::GOTO_32, 0, 0 - }; + const uint16_t data2[] = ZERO_REGISTER_CODE_ITEM( + Instruction::GOTO_32, 0, 0); - TestCode(data2, sizeof(data2) / sizeof(uint16_t), dominators, sizeof(dominators) / sizeof(int)); + TestCode(data2, dominators, sizeof(dominators) / sizeof(int)); } TEST(OptimizerTest, CFG5) { - const uint16_t data[] = { - Instruction::RETURN_VOID, // Block number 1 - Instruction::GOTO | 0x100, // Dead block - Instruction::GOTO | 0xFE00 // Block number 2 - }; + const uint16_t data[] = ZERO_REGISTER_CODE_ITEM( + Instruction::RETURN_VOID, // Block number 1 + Instruction::GOTO | 0x100, // Dead block + Instruction::GOTO | 0xFE00); // Block number 2 + const int dominators[] = { -1, @@ -157,15 +152,15 @@ TEST(OptimizerTest, CFG5) { 1 }; - TestCode(data, sizeof(data) / sizeof(uint16_t), dominators, sizeof(dominators) / sizeof(int)); + TestCode(data, dominators, sizeof(dominators) / sizeof(int)); } TEST(OptimizerTest, CFG6) { - const uint16_t data[] = { + const uint16_t data[] = ONE_REGISTER_CODE_ITEM( + Instruction::CONST_4 | 0 | 0, Instruction::IF_EQ, 3, Instruction::GOTO | 0x100, - Instruction::RETURN_VOID - }; + Instruction::RETURN_VOID); const int dominators[] = { -1, @@ -175,15 +170,15 @@ TEST(OptimizerTest, CFG6) { 3 }; - TestCode(data, sizeof(data) / sizeof(uint16_t), dominators, sizeof(dominators) / sizeof(int)); + TestCode(data, dominators, sizeof(dominators) / sizeof(int)); } TEST(OptimizerTest, CFG7) { - const uint16_t data[] = { - Instruction::IF_EQ, 3, // Block number 1 - Instruction::GOTO | 0x100, // Block number 2 - Instruction::GOTO | 0xFF00 // Block number 3 - }; + const uint16_t data[] = ONE_REGISTER_CODE_ITEM( + Instruction::CONST_4 | 0 | 0, + Instruction::IF_EQ, 3, // Block number 1 + Instruction::GOTO | 0x100, // Block number 2 + Instruction::GOTO | 0xFF00); // Block number 3 const int dominators[] = { -1, @@ -193,16 +188,16 @@ TEST(OptimizerTest, CFG7) { -1 // exit block is not dominated by any block due to the spin loop. }; - TestCode(data, sizeof(data) / sizeof(uint16_t), dominators, sizeof(dominators) / sizeof(int)); + TestCode(data, dominators, sizeof(dominators) / sizeof(int)); } TEST(OptimizerTest, CFG8) { - const uint16_t data[] = { - Instruction::IF_EQ, 3, // Block number 1 - Instruction::GOTO | 0x200, // Block number 2 - Instruction::GOTO | 0x100, // Block number 3 - Instruction::GOTO | 0xFF00 // Block number 4 - }; + const uint16_t data[] = ONE_REGISTER_CODE_ITEM( + Instruction::CONST_4 | 0 | 0, + Instruction::IF_EQ, 3, // Block number 1 + Instruction::GOTO | 0x200, // Block number 2 + Instruction::GOTO | 0x100, // Block number 3 + Instruction::GOTO | 0xFF00); // Block number 4 const int dominators[] = { -1, @@ -213,16 +208,16 @@ TEST(OptimizerTest, CFG8) { -1 // exit block is not dominated by any block due to the spin loop. }; - TestCode(data, sizeof(data) / sizeof(uint16_t), dominators, sizeof(dominators) / sizeof(int)); + TestCode(data, dominators, sizeof(dominators) / sizeof(int)); } TEST(OptimizerTest, CFG9) { - const uint16_t data[] = { - Instruction::IF_EQ, 3, // Block number 1 - Instruction::GOTO | 0x200, // Block number 2 - Instruction::GOTO | 0x100, // Block number 3 - Instruction::GOTO | 0xFE00 // Block number 4 - }; + const uint16_t data[] = ONE_REGISTER_CODE_ITEM( + Instruction::CONST_4 | 0 | 0, + Instruction::IF_EQ, 3, // Block number 1 + Instruction::GOTO | 0x200, // Block number 2 + Instruction::GOTO | 0x100, // Block number 3 + Instruction::GOTO | 0xFE00); // Block number 4 const int dominators[] = { -1, @@ -233,17 +228,17 @@ TEST(OptimizerTest, CFG9) { -1 // exit block is not dominated by any block due to the spin loop. }; - TestCode(data, sizeof(data) / sizeof(uint16_t), dominators, sizeof(dominators) / sizeof(int)); + TestCode(data, dominators, sizeof(dominators) / sizeof(int)); } TEST(OptimizerTest, CFG10) { - const uint16_t data[] = { + const uint16_t data[] = ONE_REGISTER_CODE_ITEM( + Instruction::CONST_4 | 0 | 0, Instruction::IF_EQ, 6, // Block number 1 Instruction::IF_EQ, 3, // Block number 2 Instruction::GOTO | 0x100, // Block number 3 Instruction::GOTO | 0x100, // Block number 4 - Instruction::RETURN_VOID // Block number 5 - }; + Instruction::RETURN_VOID); // Block number 5 const int dominators[] = { -1, @@ -255,7 +250,7 @@ TEST(OptimizerTest, CFG10) { 5 // Block number 5 dominates exit block }; - TestCode(data, sizeof(data) / sizeof(uint16_t), dominators, sizeof(dominators) / sizeof(int)); + TestCode(data, dominators, sizeof(dominators) / sizeof(int)); } } // namespace art diff --git a/compiler/optimizing/nodes.cc b/compiler/optimizing/nodes.cc index aefb0898b9..16dfb9465c 100644 --- a/compiler/optimizing/nodes.cc +++ b/compiler/optimizing/nodes.cc @@ -122,6 +122,7 @@ void HGraph::VisitBlockForDominatorTree(HBasicBlock* block, void HBasicBlock::AddInstruction(HInstruction* instruction) { instruction->set_block(this); + instruction->set_id(graph()->GetNextInstructionId()); if (first_instruction_ == nullptr) { DCHECK(last_instruction_ == nullptr); first_instruction_ = last_instruction_ = instruction; @@ -130,6 +131,9 @@ void HBasicBlock::AddInstruction(HInstruction* instruction) { instruction->previous_ = last_instruction_; last_instruction_ = instruction; } + for (int i = 0; i < instruction->InputCount(); i++) { + instruction->InputAt(i)->AddUse(instruction); + } } #define DEFINE_ACCEPT(name) \ diff --git a/compiler/optimizing/nodes.h b/compiler/optimizing/nodes.h index 46fe95e99f..bb08bd0e9a 100644 --- a/compiler/optimizing/nodes.h +++ b/compiler/optimizing/nodes.h @@ -25,6 +25,7 @@ namespace art { class HBasicBlock; class HInstruction; +class HIntConstant; class HGraphVisitor; static const int kDefaultNumberOfBlocks = 8; @@ -38,7 +39,8 @@ class HGraph : public ArenaObject { explicit HGraph(ArenaAllocator* arena) : arena_(arena), blocks_(arena, kDefaultNumberOfBlocks), - dominator_order_(arena, kDefaultNumberOfBlocks) { } + dominator_order_(arena, kDefaultNumberOfBlocks), + current_instruction_id_(0) { } ArenaAllocator* arena() const { return arena_; } const GrowableArray* blocks() const { return &blocks_; } @@ -49,10 +51,13 @@ class HGraph : public ArenaObject { void set_entry_block(HBasicBlock* block) { entry_block_ = block; } void set_exit_block(HBasicBlock* block) { exit_block_ = block; } - void AddBlock(HBasicBlock* block); void BuildDominatorTree(); + int GetNextInstructionId() { + return current_instruction_id_++; + } + private: HBasicBlock* FindCommonDominator(HBasicBlock* first, HBasicBlock* second) const; void VisitBlockForDominatorTree(HBasicBlock* block, @@ -75,6 +80,9 @@ class HGraph : public ArenaObject { HBasicBlock* entry_block_; HBasicBlock* exit_block_; + // The current id to assign to a newly added instruction. See HInstruction.id_. + int current_instruction_id_; + DISALLOW_COPY_AND_ASSIGN(HGraph); }; @@ -171,18 +179,38 @@ class HBasicBlock : public ArenaObject { }; #define FOR_EACH_INSTRUCTION(M) \ + M(Equal) \ M(Exit) \ M(Goto) \ M(If) \ + M(IntConstant) \ + M(LoadLocal) \ + M(Local) \ M(ReturnVoid) \ + M(StoreLocal) \ #define DECLARE_INSTRUCTION(type) \ virtual void Accept(HGraphVisitor* visitor); \ virtual const char* DebugName() const { return #type; } \ +class HUseListNode : public ArenaObject { + public: + HUseListNode(HInstruction* instruction, HUseListNode* tail) + : instruction_(instruction), tail_(tail) { } + + HUseListNode* tail() const { return tail_; } + HInstruction* instruction() const { return instruction_; } + + private: + HInstruction* const instruction_; + HUseListNode* const tail_; + + DISALLOW_COPY_AND_ASSIGN(HUseListNode); +}; + class HInstruction : public ArenaObject { public: - HInstruction() : previous_(nullptr), next_(nullptr), block_(nullptr) { } + HInstruction() : previous_(nullptr), next_(nullptr), block_(nullptr), id_(-1), uses_(nullptr) { } virtual ~HInstruction() { } HInstruction* next() const { return next_; } @@ -197,16 +225,71 @@ class HInstruction : public ArenaObject { virtual void Accept(HGraphVisitor* visitor) = 0; virtual const char* DebugName() const = 0; + void AddUse(HInstruction* user) { + uses_ = new (block_->graph()->arena()) HUseListNode(user, uses_); + } + + HUseListNode* uses() const { return uses_; } + + bool HasUses() const { return uses_ != nullptr; } + + int id() const { return id_; } + void set_id(int id) { id_ = id; } + private: HInstruction* previous_; HInstruction* next_; HBasicBlock* block_; + // An instruction gets an id when it is added to the graph. + // It reflects creation order. A negative id means the instruction + // has not beed added to the graph. + int id_; + + HUseListNode* uses_; + friend class HBasicBlock; DISALLOW_COPY_AND_ASSIGN(HInstruction); }; +class HUseIterator : public ValueObject { + public: + explicit HUseIterator(HInstruction* instruction) : current_(instruction->uses()) { } + + bool Done() const { return current_ == nullptr; } + + void Advance() { + DCHECK(!Done()); + current_ = current_->tail(); + } + + HInstruction* Current() const { + DCHECK(!Done()); + return current_->instruction(); + } + + private: + HUseListNode* current_; + + friend class HValue; +}; + +class HInputIterator : public ValueObject { + public: + explicit HInputIterator(HInstruction* instruction) : instruction_(instruction), index_(0) { } + + bool Done() const { return index_ == instruction_->InputCount(); } + HInstruction* Current() const { return instruction_->InputAt(index_); } + void Advance() { index_++; } + + private: + HInstruction* instruction_; + int index_; + + DISALLOW_COPY_AND_ASSIGN(HInputIterator); +}; + class HInstructionIterator : public ValueObject { public: explicit HInstructionIterator(HBasicBlock* block) @@ -214,9 +297,9 @@ class HInstructionIterator : public ValueObject { next_ = Done() ? nullptr : instruction_->next(); } - inline bool Done() const { return instruction_ == nullptr; } - inline HInstruction* Current() { return instruction_; } - inline void Advance() { + bool Done() const { return instruction_ == nullptr; } + HInstruction* Current() const { return instruction_; } + void Advance() { instruction_ = next_; next_ = Done() ? nullptr : instruction_->next(); } @@ -236,12 +319,12 @@ class EmbeddedArray { intptr_t length() const { return N; } const T& operator[](intptr_t i) const { - ASSERT(i < length()); + DCHECK_LT(i, length()); return elements_[i]; } T& operator[](intptr_t i) { - ASSERT(i < length()); + DCHECK_LT(i, length()); return elements_[i]; } @@ -282,6 +365,11 @@ class HTemplateInstruction: public HInstruction { virtual intptr_t InputCount() const { return N; } virtual HInstruction* InputAt(intptr_t i) const { return inputs_[i]; } + protected: + void SetRawInputAt(intptr_t i, HInstruction* instruction) { + inputs_[i] = instruction; + } + private: EmbeddedArray inputs_; }; @@ -328,10 +416,11 @@ class HGoto : public HTemplateInstruction<0> { // Conditional branch. A block ending with an HIf instruction must have // two successors. -// TODO: Make it take an input. -class HIf : public HTemplateInstruction<0> { +class HIf : public HTemplateInstruction<1> { public: - HIf() { } + explicit HIf(HInstruction* input) { + SetRawInputAt(0, input); + } DECLARE_INSTRUCTION(If) @@ -339,6 +428,76 @@ class HIf : public HTemplateInstruction<0> { DISALLOW_COPY_AND_ASSIGN(HIf); }; +// Instruction to check if two inputs are equal to each other. +class HEqual : public HTemplateInstruction<2> { + public: + HEqual(HInstruction* first, HInstruction* second) { + SetRawInputAt(0, first); + SetRawInputAt(1, second); + } + + DECLARE_INSTRUCTION(Equal) + + private: + DISALLOW_COPY_AND_ASSIGN(HEqual); +}; + +// A local in the graph. Corresponds to a Dex register. +class HLocal : public HTemplateInstruction<0> { + public: + explicit HLocal(uint16_t reg_number) : reg_number_(reg_number) { } + + DECLARE_INSTRUCTION(Local) + + private: + // The register number in Dex. + uint16_t reg_number_; + + DISALLOW_COPY_AND_ASSIGN(HLocal); +}; + +// Load a given local. The local is an input of this instruction. +class HLoadLocal : public HTemplateInstruction<1> { + public: + explicit HLoadLocal(HLocal* local) { + SetRawInputAt(0, local); + } + + DECLARE_INSTRUCTION(LoadLocal) + + private: + DISALLOW_COPY_AND_ASSIGN(HLoadLocal); +}; + +// Store a value in a given local. This instruction has two inputs: the value +// and the local. +class HStoreLocal : public HTemplateInstruction<2> { + public: + HStoreLocal(HLocal* local, HInstruction* value) { + SetRawInputAt(0, local); + SetRawInputAt(1, value); + } + + DECLARE_INSTRUCTION(StoreLocal) + + private: + DISALLOW_COPY_AND_ASSIGN(HStoreLocal); +}; + +// Constants of the type int. Those can be from Dex instructions, or +// synthesized (for example with the if-eqz instruction). +class HIntConstant : public HTemplateInstruction<0> { + public: + explicit HIntConstant(int32_t value) : value_(value) { } + + DECLARE_INSTRUCTION(IntConstant) + + private: + const int32_t value_; + + DISALLOW_COPY_AND_ASSIGN(HIntConstant); +}; + class HGraphVisitor : public ValueObject { public: explicit HGraphVisitor(HGraph* graph) : graph_(graph) { } diff --git a/compiler/optimizing/optimizing_unit_test.h b/compiler/optimizing/optimizing_unit_test.h new file mode 100644 index 0000000000..bf13a41397 --- /dev/null +++ b/compiler/optimizing/optimizing_unit_test.h @@ -0,0 +1,29 @@ +/* + * 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_OPTIMIZING_UNIT_TEST_H_ +#define ART_COMPILER_OPTIMIZING_OPTIMIZING_UNIT_TEST_H_ + +#define NUM_INSTRUCTIONS(...) \ + (sizeof((uint16_t[]) {__VA_ARGS__}) /sizeof(uint16_t)) + +#define ZERO_REGISTER_CODE_ITEM(...) \ + { 0, 0, 0, 0, 0, 0, NUM_INSTRUCTIONS(__VA_ARGS__), 0, __VA_ARGS__ } + +#define ONE_REGISTER_CODE_ITEM(...) \ + { 1, 0, 0, 0, 0, 0, NUM_INSTRUCTIONS(__VA_ARGS__), 0, __VA_ARGS__ } + +#endif // ART_COMPILER_OPTIMIZING_OPTIMIZING_UNIT_TEST_H_ diff --git a/compiler/optimizing/pretty_printer.h b/compiler/optimizing/pretty_printer.h index d4b61651dc..0c0f70224b 100644 --- a/compiler/optimizing/pretty_printer.h +++ b/compiler/optimizing/pretty_printer.h @@ -27,7 +27,35 @@ class HPrettyPrinter : public HGraphVisitor { virtual void VisitInstruction(HInstruction* instruction) { PrintString(" "); + PrintInt(instruction->id()); + PrintString(": "); PrintString(instruction->DebugName()); + if (instruction->InputCount() != 0) { + PrintString("("); + bool first = true; + for (HInputIterator it(instruction); !it.Done(); it.Advance()) { + if (first) { + first = false; + } else { + PrintString(", "); + } + PrintInt(it.Current()->id()); + } + PrintString(")"); + } + if (instruction->HasUses()) { + PrintString(" ["); + bool first = true; + for (HUseIterator it(instruction); !it.Done(); it.Advance()) { + if (first) { + first = false; + } else { + PrintString(", "); + } + PrintInt(it.Current()->id()); + } + PrintString("]"); + } PrintNewLine(); } diff --git a/compiler/optimizing/pretty_printer_test.cc b/compiler/optimizing/pretty_printer_test.cc index 4c8201e53e..b99370d16d 100644 --- a/compiler/optimizing/pretty_printer_test.cc +++ b/compiler/optimizing/pretty_printer_test.cc @@ -16,8 +16,10 @@ #include "base/stringprintf.h" #include "builder.h" +#include "dex_file.h" #include "dex_instruction.h" #include "nodes.h" +#include "optimizing_unit_test.h" #include "pretty_printer.h" #include "utils/arena_allocator.h" @@ -52,7 +54,9 @@ class StringPrettyPrinter : public HPrettyPrinter { } virtual void VisitGoto(HGoto* gota) { - str_ += " Goto "; + PrintString(" "); + PrintInt(gota->id()); + PrintString(": Goto "); PrintInt(current_block_->successors()->Get(0)->block_id()); PrintNewLine(); } @@ -64,12 +68,12 @@ class StringPrettyPrinter : public HPrettyPrinter { DISALLOW_COPY_AND_ASSIGN(StringPrettyPrinter); }; - -static void TestCode(const uint16_t* data, int length, const char* expected) { +static void TestCode(const uint16_t* data, const char* expected) { ArenaPool pool; ArenaAllocator allocator(&pool); HGraphBuilder builder(&allocator); - HGraph* graph = builder.BuildGraph(data, data + length); + const DexFile::CodeItem* item = reinterpret_cast(data); + HGraph* graph = builder.BuildGraph(*item); ASSERT_NE(graph, nullptr); StringPrettyPrinter printer(graph); printer.VisitInsertionOrder(); @@ -77,182 +81,207 @@ static void TestCode(const uint16_t* data, int length, const char* expected) { } TEST(PrettyPrinterTest, ReturnVoid) { - const uint16_t data[] = { Instruction::RETURN_VOID }; + const uint16_t data[] = ZERO_REGISTER_CODE_ITEM( + Instruction::RETURN_VOID); const char* expected = "BasicBlock 0, succ: 1\n" - " Goto 1\n" + " 2: Goto 1\n" "BasicBlock 1, pred: 0, succ: 2\n" - " ReturnVoid\n" + " 0: ReturnVoid\n" "BasicBlock 2, pred: 1\n" - " Exit\n"; + " 1: Exit\n"; - TestCode(data, sizeof(data) / sizeof(uint16_t), expected); + TestCode(data, expected); } TEST(PrettyPrinterTest, CFG1) { const char* expected = "BasicBlock 0, succ: 1\n" - " Goto 1\n" + " 3: Goto 1\n" "BasicBlock 1, pred: 0, succ: 2\n" - " Goto 2\n" + " 0: Goto 2\n" "BasicBlock 2, pred: 1, succ: 3\n" - " ReturnVoid\n" + " 1: ReturnVoid\n" "BasicBlock 3, pred: 2\n" - " Exit\n"; + " 2: Exit\n"; - const uint16_t data[] = { - Instruction::GOTO | 0x100, - Instruction::RETURN_VOID - }; + const uint16_t data[] = + ZERO_REGISTER_CODE_ITEM( + Instruction::GOTO | 0x100, + Instruction::RETURN_VOID); - TestCode(data, sizeof(data) / sizeof(uint16_t), expected); + TestCode(data, expected); } TEST(PrettyPrinterTest, CFG2) { const char* expected = "BasicBlock 0, succ: 1\n" - " Goto 1\n" + " 4: Goto 1\n" "BasicBlock 1, pred: 0, succ: 2\n" - " Goto 2\n" + " 0: Goto 2\n" "BasicBlock 2, pred: 1, succ: 3\n" - " Goto 3\n" + " 1: Goto 3\n" "BasicBlock 3, pred: 2, succ: 4\n" - " ReturnVoid\n" + " 2: ReturnVoid\n" "BasicBlock 4, pred: 3\n" - " Exit\n"; + " 3: Exit\n"; - const uint16_t data[] = { + const uint16_t data[] = ZERO_REGISTER_CODE_ITEM( Instruction::GOTO | 0x100, Instruction::GOTO | 0x100, - Instruction::RETURN_VOID - }; + Instruction::RETURN_VOID); - TestCode(data, sizeof(data) / sizeof(uint16_t), expected); + TestCode(data, expected); } TEST(PrettyPrinterTest, CFG3) { const char* expected = "BasicBlock 0, succ: 1\n" - " Goto 1\n" + " 4: Goto 1\n" "BasicBlock 1, pred: 0, succ: 3\n" - " Goto 3\n" + " 0: Goto 3\n" "BasicBlock 2, pred: 3, succ: 4\n" - " ReturnVoid\n" + " 1: ReturnVoid\n" "BasicBlock 3, pred: 1, succ: 2\n" - " Goto 2\n" + " 2: Goto 2\n" "BasicBlock 4, pred: 2\n" - " Exit\n"; + " 3: Exit\n"; - const uint16_t data1[] = { + const uint16_t data1[] = ZERO_REGISTER_CODE_ITEM( Instruction::GOTO | 0x200, Instruction::RETURN_VOID, - Instruction::GOTO | 0xFF00 - }; + Instruction::GOTO | 0xFF00); - TestCode(data1, sizeof(data1) / sizeof(uint16_t), expected); + TestCode(data1, expected); - const uint16_t data2[] = { + const uint16_t data2[] = ZERO_REGISTER_CODE_ITEM( Instruction::GOTO_16, 3, Instruction::RETURN_VOID, - Instruction::GOTO_16, 0xFFFF - }; + Instruction::GOTO_16, 0xFFFF); - TestCode(data2, sizeof(data2) / sizeof(uint16_t), expected); + TestCode(data2, expected); - const uint16_t data3[] = { + const uint16_t data3[] = ZERO_REGISTER_CODE_ITEM( Instruction::GOTO_32, 4, 0, Instruction::RETURN_VOID, - Instruction::GOTO_32, 0xFFFF, 0xFFFF - }; + Instruction::GOTO_32, 0xFFFF, 0xFFFF); - TestCode(data3, sizeof(data3) / sizeof(uint16_t), expected); + TestCode(data3, expected); } TEST(PrettyPrinterTest, CFG4) { const char* expected = "BasicBlock 0, succ: 1\n" - " Goto 1\n" + " 2: Goto 1\n" "BasicBlock 1, pred: 0, 1, succ: 1\n" - " Goto 1\n" + " 0: Goto 1\n" "BasicBlock 2\n" - " Exit\n"; + " 1: Exit\n"; - const uint16_t data1[] = { + const uint16_t data1[] = ZERO_REGISTER_CODE_ITEM( Instruction::NOP, - Instruction::GOTO | 0xFF00 - }; + Instruction::GOTO | 0xFF00); - TestCode(data1, sizeof(data1) / sizeof(uint16_t), expected); + TestCode(data1, expected); - const uint16_t data2[] = { - Instruction::GOTO_32, 0, 0 - }; + const uint16_t data2[] = ZERO_REGISTER_CODE_ITEM( + Instruction::GOTO_32, 0, 0); - TestCode(data2, sizeof(data2) / sizeof(uint16_t), expected); + TestCode(data2, expected); } TEST(PrettyPrinterTest, CFG5) { const char* expected = "BasicBlock 0, succ: 1\n" - " Goto 1\n" + " 3: Goto 1\n" "BasicBlock 1, pred: 0, 2, succ: 3\n" - " ReturnVoid\n" + " 0: ReturnVoid\n" "BasicBlock 2, succ: 1\n" - " Goto 1\n" + " 1: Goto 1\n" "BasicBlock 3, pred: 1\n" - " Exit\n"; + " 2: Exit\n"; - const uint16_t data[] = { + const uint16_t data[] = ZERO_REGISTER_CODE_ITEM( Instruction::RETURN_VOID, Instruction::GOTO | 0x100, - Instruction::GOTO | 0xFE00 - }; + Instruction::GOTO | 0xFE00); - TestCode(data, sizeof(data) / sizeof(uint16_t), expected); + TestCode(data, expected); } -TEST(OptimizerTest, CFG6) { +TEST(PrettyPrinterTest, CFG6) { const char* expected = "BasicBlock 0, succ: 1\n" - " Goto 1\n" + " 0: Local [4, 3, 2]\n" + " 1: IntConstant [2]\n" + " 10: Goto 1\n" "BasicBlock 1, pred: 0, succ: 3, 2\n" - " If\n" + " 2: StoreLocal(0, 1)\n" + " 3: LoadLocal(0) [5]\n" + " 4: LoadLocal(0) [5]\n" + " 5: Equal(3, 4) [6]\n" + " 6: If(5)\n" "BasicBlock 2, pred: 1, succ: 3\n" - " Goto 3\n" + " 7: Goto 3\n" "BasicBlock 3, pred: 1, 2, succ: 4\n" - " ReturnVoid\n" + " 8: ReturnVoid\n" "BasicBlock 4, pred: 3\n" - " Exit\n"; + " 9: Exit\n"; - const uint16_t data[] = { + const uint16_t data[] = ONE_REGISTER_CODE_ITEM( + Instruction::CONST_4 | 0 | 0, Instruction::IF_EQ, 3, Instruction::GOTO | 0x100, - Instruction::RETURN_VOID - }; + Instruction::RETURN_VOID); - TestCode(data, sizeof(data) / sizeof(uint16_t), expected); + TestCode(data, expected); } -TEST(OptimizerTest, CFG7) { +TEST(PrettyPrinterTest, CFG7) { const char* expected = "BasicBlock 0, succ: 1\n" - " Goto 1\n" + " 0: Local [4, 3, 2]\n" + " 1: IntConstant [2]\n" + " 10: Goto 1\n" "BasicBlock 1, pred: 0, succ: 3, 2\n" - " If\n" + " 2: StoreLocal(0, 1)\n" + " 3: LoadLocal(0) [5]\n" + " 4: LoadLocal(0) [5]\n" + " 5: Equal(3, 4) [6]\n" + " 6: If(5)\n" "BasicBlock 2, pred: 1, 3, succ: 3\n" - " Goto 3\n" + " 7: Goto 3\n" "BasicBlock 3, pred: 1, 2, succ: 2\n" - " Goto 2\n" + " 8: Goto 2\n" "BasicBlock 4\n" - " Exit\n"; + " 9: Exit\n"; - const uint16_t data[] = { + const uint16_t data[] = ONE_REGISTER_CODE_ITEM( + Instruction::CONST_4 | 0 | 0, Instruction::IF_EQ, 3, Instruction::GOTO | 0x100, - Instruction::GOTO | 0xFF00 - }; + Instruction::GOTO | 0xFF00); + + TestCode(data, expected); +} + +TEST(PrettyPrinterTest, IntConstant) { + const char* expected = + "BasicBlock 0, succ: 1\n" + " 0: Local [2]\n" + " 1: IntConstant [2]\n" + " 5: Goto 1\n" + "BasicBlock 1, pred: 0, succ: 2\n" + " 2: StoreLocal(0, 1)\n" + " 3: ReturnVoid\n" + "BasicBlock 2, pred: 1\n" + " 4: Exit\n"; + + const uint16_t data[] = ONE_REGISTER_CODE_ITEM( + Instruction::CONST_4 | 0 | 0, + Instruction::RETURN_VOID); - TestCode(data, sizeof(data) / sizeof(uint16_t), expected); + TestCode(data, expected); } } // namespace art -- cgit v1.2.3