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