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 OptimizingUnitTest { 28 public: 29 LoopOptimizationTest() 30 : graph_(CreateGraph()), 31 iva_(new (GetAllocator()) HInductionVarAnalysis(graph_)), 32 loop_opt_(new (GetAllocator()) HLoopOptimization( 33 graph_, /* compiler_options= */ nullptr, iva_, /* stats= */ nullptr)) { 34 BuildGraph(); 35 } 36 37 ~LoopOptimizationTest() { } 38 39 /** Constructs bare minimum graph. */ 40 void BuildGraph() { 41 graph_->SetNumberOfVRegs(1); 42 entry_block_ = new (GetAllocator()) HBasicBlock(graph_); 43 return_block_ = new (GetAllocator()) HBasicBlock(graph_); 44 exit_block_ = new (GetAllocator()) HBasicBlock(graph_); 45 graph_->AddBlock(entry_block_); 46 graph_->AddBlock(return_block_); 47 graph_->AddBlock(exit_block_); 48 graph_->SetEntryBlock(entry_block_); 49 graph_->SetExitBlock(exit_block_); 50 parameter_ = new (GetAllocator()) HParameterValue(graph_->GetDexFile(), 51 dex::TypeIndex(0), 52 0, 53 DataType::Type::kInt32); 54 entry_block_->AddInstruction(parameter_); 55 return_block_->AddInstruction(new (GetAllocator()) HReturnVoid()); 56 exit_block_->AddInstruction(new (GetAllocator()) HExit()); 57 entry_block_->AddSuccessor(return_block_); 58 return_block_->AddSuccessor(exit_block_); 59 } 60 61 /** Adds a loop nest at given position before successor. */ 62 HBasicBlock* AddLoop(HBasicBlock* position, HBasicBlock* successor) { 63 HBasicBlock* header = new (GetAllocator()) HBasicBlock(graph_); 64 HBasicBlock* body = new (GetAllocator()) HBasicBlock(graph_); 65 graph_->AddBlock(header); 66 graph_->AddBlock(body); 67 // Control flow. 68 position->ReplaceSuccessor(successor, header); 69 header->AddSuccessor(body); 70 header->AddSuccessor(successor); 71 header->AddInstruction(new (GetAllocator()) HIf(parameter_)); 72 body->AddSuccessor(header); 73 body->AddInstruction(new (GetAllocator()) HGoto()); 74 return header; 75 } 76 77 /** Performs analysis. */ 78 void PerformAnalysis() { 79 graph_->BuildDominatorTree(); 80 iva_->Run(); 81 // Do not release the loop hierarchy. 82 ScopedArenaAllocator loop_allocator(GetArenaStack()); 83 loop_opt_->loop_allocator_ = &loop_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 HGraph* graph_; 105 HInductionVarAnalysis* iva_; 106 HLoopOptimization* loop_opt_; 107 108 HBasicBlock* entry_block_; 109 HBasicBlock* return_block_; 110 HBasicBlock* exit_block_; 111 112 HInstruction* parameter_; 113 }; 114 115 // 116 // The actual tests. 117 // 118 119 TEST_F(LoopOptimizationTest, NoLoops) { 120 PerformAnalysis(); 121 EXPECT_EQ("", LoopStructure()); 122 } 123 124 TEST_F(LoopOptimizationTest, SingleLoop) { 125 AddLoop(entry_block_, return_block_); 126 PerformAnalysis(); 127 EXPECT_EQ("[]", LoopStructure()); 128 } 129 130 TEST_F(LoopOptimizationTest, LoopNest10) { 131 HBasicBlock* b = entry_block_; 132 HBasicBlock* s = return_block_; 133 for (int i = 0; i < 10; i++) { 134 s = AddLoop(b, s); 135 b = s->GetSuccessors()[0]; 136 } 137 PerformAnalysis(); 138 EXPECT_EQ("[[[[[[[[[[]]]]]]]]]]", LoopStructure()); 139 } 140 141 TEST_F(LoopOptimizationTest, LoopSequence10) { 142 HBasicBlock* b = entry_block_; 143 HBasicBlock* s = return_block_; 144 for (int i = 0; i < 10; i++) { 145 b = AddLoop(b, s); 146 s = b->GetSuccessors()[1]; 147 } 148 PerformAnalysis(); 149 EXPECT_EQ("[][][][][][][][][][]", LoopStructure()); 150 } 151 152 TEST_F(LoopOptimizationTest, LoopSequenceOfNests) { 153 HBasicBlock* b = entry_block_; 154 HBasicBlock* s = return_block_; 155 for (int i = 0; i < 10; i++) { 156 b = AddLoop(b, s); 157 s = b->GetSuccessors()[1]; 158 HBasicBlock* bi = b->GetSuccessors()[0]; 159 HBasicBlock* si = b; 160 for (int j = 0; j < i; j++) { 161 si = AddLoop(bi, si); 162 bi = si->GetSuccessors()[0]; 163 } 164 } 165 PerformAnalysis(); 166 EXPECT_EQ("[]" 167 "[[]]" 168 "[[[]]]" 169 "[[[[]]]]" 170 "[[[[[]]]]]" 171 "[[[[[[]]]]]]" 172 "[[[[[[[]]]]]]]" 173 "[[[[[[[[]]]]]]]]" 174 "[[[[[[[[[]]]]]]]]]" 175 "[[[[[[[[[[]]]]]]]]]]", 176 LoopStructure()); 177 } 178 179 TEST_F(LoopOptimizationTest, LoopNestWithSequence) { 180 HBasicBlock* b = entry_block_; 181 HBasicBlock* s = return_block_; 182 for (int i = 0; i < 10; i++) { 183 s = AddLoop(b, s); 184 b = s->GetSuccessors()[0]; 185 } 186 b = s; 187 s = b->GetSuccessors()[1]; 188 for (int i = 0; i < 9; i++) { 189 b = AddLoop(b, s); 190 s = b->GetSuccessors()[1]; 191 } 192 PerformAnalysis(); 193 EXPECT_EQ("[[[[[[[[[[][][][][][][][][][]]]]]]]]]]", LoopStructure()); 194 } 195 196 // Check that SimplifyLoop() doesn't invalidate data flow when ordering loop headers' 197 // predecessors. 198 // 199 // This is a test for nodes.cc functionality - HGraph::SimplifyLoop. 200 TEST_F(LoopOptimizationTest, SimplifyLoopReoderPredecessors) { 201 // Can't use AddLoop as we want special order for blocks predecessors. 202 HBasicBlock* header = new (GetAllocator()) HBasicBlock(graph_); 203 HBasicBlock* body = new (GetAllocator()) HBasicBlock(graph_); 204 graph_->AddBlock(header); 205 graph_->AddBlock(body); 206 207 // Control flow: make a loop back edge first in the list of predecessors. 208 entry_block_->RemoveSuccessor(return_block_); 209 body->AddSuccessor(header); 210 entry_block_->AddSuccessor(header); 211 header->AddSuccessor(body); 212 header->AddSuccessor(return_block_); 213 DCHECK(header->GetSuccessors()[1] == return_block_); 214 215 // Data flow. 216 header->AddInstruction(new (GetAllocator()) HIf(parameter_)); 217 body->AddInstruction(new (GetAllocator()) HGoto()); 218 219 HPhi* phi = new (GetAllocator()) HPhi(GetAllocator(), 0, 0, DataType::Type::kInt32); 220 HInstruction* add = new (GetAllocator()) HAdd(DataType::Type::kInt32, phi, parameter_); 221 header->AddPhi(phi); 222 body->AddInstruction(add); 223 224 phi->AddInput(add); 225 phi->AddInput(parameter_); 226 227 graph_->ClearLoopInformation(); 228 graph_->ClearDominanceInformation(); 229 graph_->BuildDominatorTree(); 230 231 // BuildDominatorTree inserts a block beetween loop header and entry block. 232 EXPECT_EQ(header->GetPredecessors()[0]->GetSinglePredecessor(), entry_block_); 233 234 // Check that after optimizations in BuildDominatorTree()/SimplifyCFG() phi inputs 235 // are still mapped correctly to the block predecessors. 236 for (size_t i = 0, e = phi->InputCount(); i < e; i++) { 237 HInstruction* input = phi->InputAt(i); 238 EXPECT_TRUE(input->GetBlock()->Dominates(header->GetPredecessors()[i])); 239 } 240 } 241 242 // Test that SimplifyLoop() processes the multiple-preheaders loops correctly. 243 // 244 // This is a test for nodes.cc functionality - HGraph::SimplifyLoop. 245 TEST_F(LoopOptimizationTest, SimplifyLoopSinglePreheader) { 246 HBasicBlock* header = AddLoop(entry_block_, return_block_); 247 248 header->InsertInstructionBefore( 249 new (GetAllocator()) HSuspendCheck(), header->GetLastInstruction()); 250 251 // Insert an if construct before the loop so it will have two preheaders. 252 HBasicBlock* if_block = new (GetAllocator()) HBasicBlock(graph_); 253 HBasicBlock* preheader0 = new (GetAllocator()) HBasicBlock(graph_); 254 HBasicBlock* preheader1 = new (GetAllocator()) HBasicBlock(graph_); 255 256 graph_->AddBlock(if_block); 257 graph_->AddBlock(preheader0); 258 graph_->AddBlock(preheader1); 259 260 // Fix successors/predecessors. 261 entry_block_->ReplaceSuccessor(header, if_block); 262 if_block->AddSuccessor(preheader0); 263 if_block->AddSuccessor(preheader1); 264 preheader0->AddSuccessor(header); 265 preheader1->AddSuccessor(header); 266 267 if_block->AddInstruction(new (GetAllocator()) HIf(parameter_)); 268 preheader0->AddInstruction(new (GetAllocator()) HGoto()); 269 preheader1->AddInstruction(new (GetAllocator()) HGoto()); 270 271 HBasicBlock* body = header->GetSuccessors()[0]; 272 DCHECK(body != return_block_); 273 274 // Add some data flow. 275 HIntConstant* const_0 = graph_->GetIntConstant(0); 276 HIntConstant* const_1 = graph_->GetIntConstant(1); 277 HIntConstant* const_2 = graph_->GetIntConstant(2); 278 279 HAdd* preheader0_add = new (GetAllocator()) HAdd(DataType::Type::kInt32, parameter_, const_0); 280 preheader0->AddInstruction(preheader0_add); 281 HAdd* preheader1_add = new (GetAllocator()) HAdd(DataType::Type::kInt32, parameter_, const_1); 282 preheader1->AddInstruction(preheader1_add); 283 284 HPhi* header_phi = new (GetAllocator()) HPhi(GetAllocator(), 0, 0, DataType::Type::kInt32); 285 header->AddPhi(header_phi); 286 287 HAdd* body_add = new (GetAllocator()) HAdd(DataType::Type::kInt32, parameter_, const_2); 288 body->AddInstruction(body_add); 289 290 DCHECK(header->GetPredecessors()[0] == body); 291 DCHECK(header->GetPredecessors()[1] == preheader0); 292 DCHECK(header->GetPredecessors()[2] == preheader1); 293 294 header_phi->AddInput(body_add); 295 header_phi->AddInput(preheader0_add); 296 header_phi->AddInput(preheader1_add); 297 298 graph_->ClearLoopInformation(); 299 graph_->ClearDominanceInformation(); 300 graph_->BuildDominatorTree(); 301 302 EXPECT_EQ(header->GetPredecessors().size(), 2u); 303 EXPECT_EQ(header->GetPredecessors()[1], body); 304 305 HBasicBlock* new_preheader = header->GetLoopInformation()->GetPreHeader(); 306 EXPECT_EQ(preheader0->GetSingleSuccessor(), new_preheader); 307 EXPECT_EQ(preheader1->GetSingleSuccessor(), new_preheader); 308 309 EXPECT_EQ(new_preheader->GetPhis().CountSize(), 1u); 310 HPhi* new_preheader_phi = new_preheader->GetFirstPhi()->AsPhi(); 311 EXPECT_EQ(new_preheader_phi->InputCount(), 2u); 312 EXPECT_EQ(new_preheader_phi->InputAt(0), preheader0_add); 313 EXPECT_EQ(new_preheader_phi->InputAt(1), preheader1_add); 314 315 EXPECT_EQ(header_phi->InputCount(), 2u); 316 EXPECT_EQ(header_phi->InputAt(0), new_preheader_phi); 317 EXPECT_EQ(header_phi->InputAt(1), body_add); 318 } 319 320 } // namespace art 321
