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