1 /* 2 * Copyright (C) 2014 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 "base/arena_allocator.h" 18 #include "builder.h" 19 #include "dex_file.h" 20 #include "dex_instruction.h" 21 #include "nodes.h" 22 #include "optimizing_unit_test.h" 23 #include "ssa_liveness_analysis.h" 24 #include "pretty_printer.h" 25 26 #include "gtest/gtest.h" 27 28 namespace art { 29 30 class FindLoopsTest : public CommonCompilerTest {}; 31 32 TEST_F(FindLoopsTest, CFG1) { 33 // Constant is not used. 34 const uint16_t data[] = ONE_REGISTER_CODE_ITEM( 35 Instruction::CONST_4 | 0 | 0, 36 Instruction::RETURN_VOID); 37 38 ArenaPool arena; 39 ArenaAllocator allocator(&arena); 40 HGraph* graph = CreateCFG(&allocator, data); 41 for (HBasicBlock* block : graph->GetBlocks()) { 42 ASSERT_EQ(block->GetLoopInformation(), nullptr); 43 } 44 } 45 46 TEST_F(FindLoopsTest, CFG2) { 47 const uint16_t data[] = ONE_REGISTER_CODE_ITEM( 48 Instruction::CONST_4 | 0 | 0, 49 Instruction::RETURN); 50 51 ArenaPool arena; 52 ArenaAllocator allocator(&arena); 53 HGraph* graph = CreateCFG(&allocator, data); 54 for (HBasicBlock* block : graph->GetBlocks()) { 55 ASSERT_EQ(block->GetLoopInformation(), nullptr); 56 } 57 } 58 59 TEST_F(FindLoopsTest, CFG3) { 60 const uint16_t data[] = TWO_REGISTERS_CODE_ITEM( 61 Instruction::CONST_4 | 3 << 12 | 0, 62 Instruction::CONST_4 | 4 << 12 | 1 << 8, 63 Instruction::ADD_INT_2ADDR | 1 << 12, 64 Instruction::GOTO | 0x100, 65 Instruction::RETURN); 66 67 ArenaPool arena; 68 ArenaAllocator allocator(&arena); 69 HGraph* graph = CreateCFG(&allocator, data); 70 for (HBasicBlock* block : graph->GetBlocks()) { 71 ASSERT_EQ(block->GetLoopInformation(), nullptr); 72 } 73 } 74 75 TEST_F(FindLoopsTest, CFG4) { 76 const uint16_t data[] = ONE_REGISTER_CODE_ITEM( 77 Instruction::CONST_4 | 0 | 0, 78 Instruction::IF_EQ, 4, 79 Instruction::CONST_4 | 4 << 12 | 0, 80 Instruction::GOTO | 0x200, 81 Instruction::CONST_4 | 5 << 12 | 0, 82 Instruction::RETURN | 0 << 8); 83 84 ArenaPool arena; 85 ArenaAllocator allocator(&arena); 86 HGraph* graph = CreateCFG(&allocator, data); 87 for (HBasicBlock* block : graph->GetBlocks()) { 88 ASSERT_EQ(block->GetLoopInformation(), nullptr); 89 } 90 } 91 92 TEST_F(FindLoopsTest, CFG5) { 93 const uint16_t data[] = ONE_REGISTER_CODE_ITEM( 94 Instruction::CONST_4 | 0 | 0, 95 Instruction::IF_EQ, 3, 96 Instruction::CONST_4 | 4 << 12 | 0, 97 Instruction::RETURN | 0 << 8); 98 99 ArenaPool arena; 100 ArenaAllocator allocator(&arena); 101 HGraph* graph = CreateCFG(&allocator, data); 102 for (HBasicBlock* block : graph->GetBlocks()) { 103 ASSERT_EQ(block->GetLoopInformation(), nullptr); 104 } 105 } 106 107 static void TestBlock(HGraph* graph, 108 uint32_t block_id, 109 bool is_loop_header, 110 uint32_t parent_loop_header_id, 111 const int* blocks_in_loop = nullptr, 112 size_t number_of_blocks = 0) { 113 HBasicBlock* block = graph->GetBlocks()[block_id]; 114 ASSERT_EQ(block->IsLoopHeader(), is_loop_header); 115 if (parent_loop_header_id == kInvalidBlockId) { 116 ASSERT_EQ(block->GetLoopInformation(), nullptr); 117 } else { 118 ASSERT_EQ(block->GetLoopInformation()->GetHeader()->GetBlockId(), parent_loop_header_id); 119 } 120 121 if (blocks_in_loop != nullptr) { 122 HLoopInformation* info = block->GetLoopInformation(); 123 const BitVector& blocks = info->GetBlocks(); 124 ASSERT_EQ(blocks.NumSetBits(), number_of_blocks); 125 for (size_t i = 0; i < number_of_blocks; ++i) { 126 ASSERT_TRUE(blocks.IsBitSet(blocks_in_loop[i])); 127 } 128 } else { 129 ASSERT_FALSE(block->IsLoopHeader()); 130 } 131 } 132 133 TEST_F(FindLoopsTest, Loop1) { 134 // Simple loop with one preheader and one back edge. 135 // var a = 0; 136 // while (a == a) { 137 // } 138 // return; 139 const uint16_t data[] = ONE_REGISTER_CODE_ITEM( 140 Instruction::CONST_4 | 0 | 0, 141 Instruction::IF_EQ, 3, 142 Instruction::GOTO | 0xFE00, 143 Instruction::RETURN_VOID); 144 145 ArenaPool arena; 146 ArenaAllocator allocator(&arena); 147 HGraph* graph = CreateCFG(&allocator, data); 148 149 TestBlock(graph, 0, false, kInvalidBlockId); // entry block 150 TestBlock(graph, 1, false, kInvalidBlockId); // pre header 151 const int blocks2[] = {2, 3}; 152 TestBlock(graph, 2, true, 2, blocks2, 2); // loop header 153 TestBlock(graph, 3, false, 2); // block in loop 154 TestBlock(graph, 4, false, kInvalidBlockId); // return block 155 TestBlock(graph, 5, false, kInvalidBlockId); // exit block 156 } 157 158 TEST_F(FindLoopsTest, Loop2) { 159 // Make sure we support a preheader of a loop not being the first predecessor 160 // in the predecessor list of the header. 161 // var a = 0; 162 // while (a == a) { 163 // } 164 // return a; 165 const uint16_t data[] = ONE_REGISTER_CODE_ITEM( 166 Instruction::CONST_4 | 0 | 0, 167 Instruction::GOTO | 0x400, 168 Instruction::IF_EQ, 4, 169 Instruction::GOTO | 0xFE00, 170 Instruction::GOTO | 0xFD00, 171 Instruction::RETURN | 0 << 8); 172 173 ArenaPool arena; 174 ArenaAllocator allocator(&arena); 175 HGraph* graph = CreateCFG(&allocator, data); 176 177 TestBlock(graph, 0, false, kInvalidBlockId); // entry block 178 TestBlock(graph, 1, false, kInvalidBlockId); // goto block 179 const int blocks2[] = {2, 3}; 180 TestBlock(graph, 2, true, 2, blocks2, 2); // loop header 181 TestBlock(graph, 3, false, 2); // block in loop 182 TestBlock(graph, 4, false, kInvalidBlockId); // pre header 183 TestBlock(graph, 5, false, kInvalidBlockId); // return block 184 TestBlock(graph, 6, false, kInvalidBlockId); // exit block 185 } 186 187 TEST_F(FindLoopsTest, Loop3) { 188 // Make sure we create a preheader of a loop when a header originally has two 189 // incoming blocks and one back edge. 190 const uint16_t data[] = ONE_REGISTER_CODE_ITEM( 191 Instruction::CONST_4 | 0 | 0, 192 Instruction::IF_EQ, 3, 193 Instruction::GOTO | 0x100, 194 Instruction::IF_EQ, 3, 195 Instruction::GOTO | 0xFE00, 196 Instruction::RETURN | 0 << 8); 197 198 ArenaPool arena; 199 ArenaAllocator allocator(&arena); 200 HGraph* graph = CreateCFG(&allocator, data); 201 202 TestBlock(graph, 0, false, kInvalidBlockId); // entry block 203 TestBlock(graph, 1, false, kInvalidBlockId); // goto block 204 TestBlock(graph, 2, false, kInvalidBlockId); 205 const int blocks2[] = {3, 4}; 206 TestBlock(graph, 3, true, 3, blocks2, 2); // loop header 207 TestBlock(graph, 4, false, 3); // block in loop 208 TestBlock(graph, 5, false, kInvalidBlockId); // pre header 209 TestBlock(graph, 6, false, kInvalidBlockId); // return block 210 TestBlock(graph, 7, false, kInvalidBlockId); // exit block 211 TestBlock(graph, 8, false, kInvalidBlockId); // synthesized pre header 212 } 213 214 TEST_F(FindLoopsTest, Loop4) { 215 // Test loop with originally two back edges. 216 const uint16_t data[] = ONE_REGISTER_CODE_ITEM( 217 Instruction::CONST_4 | 0 | 0, 218 Instruction::IF_EQ, 6, 219 Instruction::IF_EQ, 3, 220 Instruction::GOTO | 0xFC00, 221 Instruction::GOTO | 0xFB00, 222 Instruction::RETURN | 0 << 8); 223 224 ArenaPool arena; 225 ArenaAllocator allocator(&arena); 226 HGraph* graph = CreateCFG(&allocator, data); 227 228 TestBlock(graph, 0, false, kInvalidBlockId); // entry block 229 TestBlock(graph, 1, false, kInvalidBlockId); // pre header 230 const int blocks2[] = {2, 3, 4, 5}; 231 TestBlock(graph, 2, true, 2, blocks2, arraysize(blocks2)); // loop header 232 TestBlock(graph, 3, false, 2); // block in loop 233 TestBlock(graph, 4, false, 2); // back edge 234 TestBlock(graph, 5, false, 2); // back edge 235 TestBlock(graph, 6, false, kInvalidBlockId); // return block 236 TestBlock(graph, 7, false, kInvalidBlockId); // exit block 237 } 238 239 240 TEST_F(FindLoopsTest, Loop5) { 241 // Test loop with two exit edges. 242 const uint16_t data[] = ONE_REGISTER_CODE_ITEM( 243 Instruction::CONST_4 | 0 | 0, 244 Instruction::IF_EQ, 6, 245 Instruction::IF_EQ, 3, 246 Instruction::GOTO | 0x0200, 247 Instruction::GOTO | 0xFB00, 248 Instruction::RETURN | 0 << 8); 249 250 ArenaPool arena; 251 ArenaAllocator allocator(&arena); 252 HGraph* graph = CreateCFG(&allocator, data); 253 254 TestBlock(graph, 0, false, kInvalidBlockId); // entry block 255 TestBlock(graph, 1, false, kInvalidBlockId); // pre header 256 const int blocks2[] = {2, 3, 5}; 257 TestBlock(graph, 2, true, 2, blocks2, 3); // loop header 258 TestBlock(graph, 3, false, 2); // block in loop 259 TestBlock(graph, 4, false, kInvalidBlockId); // loop exit 260 TestBlock(graph, 5, false, 2); // back edge 261 TestBlock(graph, 6, false, kInvalidBlockId); // return block 262 TestBlock(graph, 7, false, kInvalidBlockId); // exit block 263 TestBlock(graph, 8, false, kInvalidBlockId); // synthesized block at the loop exit 264 } 265 266 TEST_F(FindLoopsTest, InnerLoop) { 267 const uint16_t data[] = ONE_REGISTER_CODE_ITEM( 268 Instruction::CONST_4 | 0 | 0, 269 Instruction::IF_EQ, 6, 270 Instruction::IF_EQ, 3, 271 Instruction::GOTO | 0xFE00, // inner loop 272 Instruction::GOTO | 0xFB00, 273 Instruction::RETURN | 0 << 8); 274 275 ArenaPool arena; 276 ArenaAllocator allocator(&arena); 277 HGraph* graph = CreateCFG(&allocator, data); 278 279 TestBlock(graph, 0, false, kInvalidBlockId); // entry block 280 TestBlock(graph, 1, false, kInvalidBlockId); // pre header of outer loop 281 const int blocks2[] = {2, 3, 4, 5, 8}; 282 TestBlock(graph, 2, true, 2, blocks2, 5); // outer loop header 283 const int blocks3[] = {3, 4}; 284 TestBlock(graph, 3, true, 3, blocks3, 2); // inner loop header 285 TestBlock(graph, 4, false, 3); // back edge on inner loop 286 TestBlock(graph, 5, false, 2); // back edge on outer loop 287 TestBlock(graph, 6, false, kInvalidBlockId); // return block 288 TestBlock(graph, 7, false, kInvalidBlockId); // exit block 289 TestBlock(graph, 8, false, 2); // synthesized block as pre header of inner loop 290 291 ASSERT_TRUE(graph->GetBlocks()[3]->GetLoopInformation()->IsIn( 292 *graph->GetBlocks()[2]->GetLoopInformation())); 293 ASSERT_FALSE(graph->GetBlocks()[2]->GetLoopInformation()->IsIn( 294 *graph->GetBlocks()[3]->GetLoopInformation())); 295 } 296 297 TEST_F(FindLoopsTest, TwoLoops) { 298 const uint16_t data[] = ONE_REGISTER_CODE_ITEM( 299 Instruction::CONST_4 | 0 | 0, 300 Instruction::IF_EQ, 3, 301 Instruction::GOTO | 0xFE00, // first loop 302 Instruction::IF_EQ, 3, 303 Instruction::GOTO | 0xFE00, // second loop 304 Instruction::RETURN | 0 << 8); 305 306 ArenaPool arena; 307 ArenaAllocator allocator(&arena); 308 HGraph* graph = CreateCFG(&allocator, data); 309 310 TestBlock(graph, 0, false, kInvalidBlockId); // entry block 311 TestBlock(graph, 1, false, kInvalidBlockId); // pre header of first loop 312 const int blocks2[] = {2, 3}; 313 TestBlock(graph, 2, true, 2, blocks2, 2); // first loop header 314 TestBlock(graph, 3, false, 2); // back edge of first loop 315 const int blocks4[] = {4, 5}; 316 TestBlock(graph, 4, true, 4, blocks4, 2); // second loop header 317 TestBlock(graph, 5, false, 4); // back edge of second loop 318 TestBlock(graph, 6, false, kInvalidBlockId); // return block 319 TestBlock(graph, 7, false, kInvalidBlockId); // exit block 320 321 ASSERT_FALSE(graph->GetBlocks()[4]->GetLoopInformation()->IsIn( 322 *graph->GetBlocks()[2]->GetLoopInformation())); 323 ASSERT_FALSE(graph->GetBlocks()[2]->GetLoopInformation()->IsIn( 324 *graph->GetBlocks()[4]->GetLoopInformation())); 325 } 326 327 TEST_F(FindLoopsTest, NonNaturalLoop) { 328 const uint16_t data[] = ONE_REGISTER_CODE_ITEM( 329 Instruction::CONST_4 | 0 | 0, 330 Instruction::IF_EQ, 3, 331 Instruction::GOTO | 0x0100, 332 Instruction::IF_EQ, 3, 333 Instruction::GOTO | 0xFD00, 334 Instruction::RETURN | 0 << 8); 335 336 ArenaPool arena; 337 ArenaAllocator allocator(&arena); 338 HGraph* graph = CreateCFG(&allocator, data); 339 ASSERT_TRUE(graph->GetBlocks()[3]->IsLoopHeader()); 340 HLoopInformation* info = graph->GetBlocks()[3]->GetLoopInformation(); 341 ASSERT_EQ(1u, info->NumberOfBackEdges()); 342 ASSERT_FALSE(info->GetHeader()->Dominates(info->GetBackEdges()[0])); 343 } 344 345 TEST_F(FindLoopsTest, DoWhileLoop) { 346 const uint16_t data[] = ONE_REGISTER_CODE_ITEM( 347 Instruction::CONST_4 | 0 | 0, 348 Instruction::GOTO | 0x0100, 349 Instruction::IF_EQ, 0xFFFF, 350 Instruction::RETURN | 0 << 8); 351 352 ArenaPool arena; 353 ArenaAllocator allocator(&arena); 354 HGraph* graph = CreateCFG(&allocator, data); 355 356 TestBlock(graph, 0, false, kInvalidBlockId); // entry block 357 TestBlock(graph, 1, false, kInvalidBlockId); // pre header of first loop 358 const int blocks2[] = {2, 3, 6}; 359 TestBlock(graph, 2, true, 2, blocks2, 3); // loop header 360 TestBlock(graph, 3, false, 2); // back edge of first loop 361 TestBlock(graph, 4, false, kInvalidBlockId); // return block 362 TestBlock(graph, 5, false, kInvalidBlockId); // exit block 363 TestBlock(graph, 6, false, 2); // synthesized block to avoid a critical edge 364 } 365 366 } // namespace art 367
