1 /* 2 * Copyright (C) 2016 The Android Open Source Project 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17 #include "loop_optimization.h" 18 #include "optimizing_unit_test.h" 19 20 namespace art { 21 22 /** 23 * Fixture class for the loop optimization tests. These unit tests focus 24 * constructing the loop hierarchy. Actual optimizations are tested 25 * through the checker tests. 26 */ 27 class LoopOptimizationTest : public CommonCompilerTest { 28 public: 29 LoopOptimizationTest() 30 : pool_(), 31 allocator_(&pool_), 32 graph_(CreateGraph(&allocator_)), 33 iva_(new (&allocator_) HInductionVarAnalysis(graph_)), 34 loop_opt_(new (&allocator_) HLoopOptimization(graph_, nullptr, iva_)) { 35 BuildGraph(); 36 } 37 38 ~LoopOptimizationTest() { } 39 40 /** Constructs bare minimum graph. */ 41 void BuildGraph() { 42 graph_->SetNumberOfVRegs(1); 43 entry_block_ = new (&allocator_) HBasicBlock(graph_); 44 return_block_ = new (&allocator_) HBasicBlock(graph_); 45 exit_block_ = new (&allocator_) HBasicBlock(graph_); 46 graph_->AddBlock(entry_block_); 47 graph_->AddBlock(return_block_); 48 graph_->AddBlock(exit_block_); 49 graph_->SetEntryBlock(entry_block_); 50 graph_->SetExitBlock(exit_block_); 51 parameter_ = new (&allocator_) HParameterValue(graph_->GetDexFile(), 52 dex::TypeIndex(0), 53 0, 54 Primitive::kPrimInt); 55 entry_block_->AddInstruction(parameter_); 56 return_block_->AddInstruction(new (&allocator_) HReturnVoid()); 57 exit_block_->AddInstruction(new (&allocator_) HExit()); 58 entry_block_->AddSuccessor(return_block_); 59 return_block_->AddSuccessor(exit_block_); 60 } 61 62 /** Adds a loop nest at given position before successor. */ 63 HBasicBlock* AddLoop(HBasicBlock* position, HBasicBlock* successor) { 64 HBasicBlock* header = new (&allocator_) HBasicBlock(graph_); 65 HBasicBlock* body = new (&allocator_) HBasicBlock(graph_); 66 graph_->AddBlock(header); 67 graph_->AddBlock(body); 68 // Control flow. 69 position->ReplaceSuccessor(successor, header); 70 header->AddSuccessor(body); 71 header->AddSuccessor(successor); 72 header->AddInstruction(new (&allocator_) HIf(parameter_)); 73 body->AddSuccessor(header); 74 body->AddInstruction(new (&allocator_) HGoto()); 75 return header; 76 } 77 78 /** Performs analysis. */ 79 void PerformAnalysis() { 80 graph_->BuildDominatorTree(); 81 iva_->Run(); 82 // Do not release the loop hierarchy. 83 loop_opt_->loop_allocator_ = &allocator_; 84 loop_opt_->LocalRun(); 85 } 86 87 /** Constructs string representation of computed loop hierarchy. */ 88 std::string LoopStructure() { 89 return LoopStructureRecurse(loop_opt_->top_loop_); 90 } 91 92 // Helper method 93 std::string LoopStructureRecurse(HLoopOptimization::LoopNode* node) { 94 std::string s; 95 for ( ; node != nullptr; node = node->next) { 96 s.append("["); 97 s.append(LoopStructureRecurse(node->inner)); 98 s.append("]"); 99 } 100 return s; 101 } 102 103 // General building fields. 104 ArenaPool pool_; 105 ArenaAllocator allocator_; 106 HGraph* graph_; 107 HInductionVarAnalysis* iva_; 108 HLoopOptimization* loop_opt_; 109 110 HBasicBlock* entry_block_; 111 HBasicBlock* return_block_; 112 HBasicBlock* exit_block_; 113 114 HInstruction* parameter_; 115 }; 116 117 // 118 // The actual tests. 119 // 120 121 TEST_F(LoopOptimizationTest, NoLoops) { 122 PerformAnalysis(); 123 EXPECT_EQ("", LoopStructure()); 124 } 125 126 TEST_F(LoopOptimizationTest, SingleLoop) { 127 AddLoop(entry_block_, return_block_); 128 PerformAnalysis(); 129 EXPECT_EQ("[]", LoopStructure()); 130 } 131 132 TEST_F(LoopOptimizationTest, LoopNest10) { 133 HBasicBlock* b = entry_block_; 134 HBasicBlock* s = return_block_; 135 for (int i = 0; i < 10; i++) { 136 s = AddLoop(b, s); 137 b = s->GetSuccessors()[0]; 138 } 139 PerformAnalysis(); 140 EXPECT_EQ("[[[[[[[[[[]]]]]]]]]]", LoopStructure()); 141 } 142 143 TEST_F(LoopOptimizationTest, LoopSequence10) { 144 HBasicBlock* b = entry_block_; 145 HBasicBlock* s = return_block_; 146 for (int i = 0; i < 10; i++) { 147 b = AddLoop(b, s); 148 s = b->GetSuccessors()[1]; 149 } 150 PerformAnalysis(); 151 EXPECT_EQ("[][][][][][][][][][]", LoopStructure()); 152 } 153 154 TEST_F(LoopOptimizationTest, LoopSequenceOfNests) { 155 HBasicBlock* b = entry_block_; 156 HBasicBlock* s = return_block_; 157 for (int i = 0; i < 10; i++) { 158 b = AddLoop(b, s); 159 s = b->GetSuccessors()[1]; 160 HBasicBlock* bi = b->GetSuccessors()[0]; 161 HBasicBlock* si = b; 162 for (int j = 0; j < i; j++) { 163 si = AddLoop(bi, si); 164 bi = si->GetSuccessors()[0]; 165 } 166 } 167 PerformAnalysis(); 168 EXPECT_EQ("[]" 169 "[[]]" 170 "[[[]]]" 171 "[[[[]]]]" 172 "[[[[[]]]]]" 173 "[[[[[[]]]]]]" 174 "[[[[[[[]]]]]]]" 175 "[[[[[[[[]]]]]]]]" 176 "[[[[[[[[[]]]]]]]]]" 177 "[[[[[[[[[[]]]]]]]]]]", 178 LoopStructure()); 179 } 180 181 TEST_F(LoopOptimizationTest, LoopNestWithSequence) { 182 HBasicBlock* b = entry_block_; 183 HBasicBlock* s = return_block_; 184 for (int i = 0; i < 10; i++) { 185 s = AddLoop(b, s); 186 b = s->GetSuccessors()[0]; 187 } 188 b = s; 189 s = b->GetSuccessors()[1]; 190 for (int i = 0; i < 9; i++) { 191 b = AddLoop(b, s); 192 s = b->GetSuccessors()[1]; 193 } 194 PerformAnalysis(); 195 EXPECT_EQ("[[[[[[[[[[][][][][][][][][][]]]]]]]]]]", LoopStructure()); 196 } 197 198 } // namespace art 199
