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 "nodes.h" 20 #include "optimizing_unit_test.h" 21 #include "pretty_printer.h" 22 23 #include "gtest/gtest.h" 24 25 namespace art { 26 27 static HBasicBlock* createIfBlock(HGraph* graph, ArenaAllocator* allocator) { 28 HBasicBlock* if_block = new (allocator) HBasicBlock(graph); 29 graph->AddBlock(if_block); 30 HInstruction* instr = graph->GetIntConstant(4); 31 HInstruction* equal = new (allocator) HEqual(instr, instr); 32 if_block->AddInstruction(equal); 33 instr = new (allocator) HIf(equal); 34 if_block->AddInstruction(instr); 35 return if_block; 36 } 37 38 static HBasicBlock* createGotoBlock(HGraph* graph, ArenaAllocator* allocator) { 39 HBasicBlock* block = new (allocator) HBasicBlock(graph); 40 graph->AddBlock(block); 41 HInstruction* got = new (allocator) HGoto(); 42 block->AddInstruction(got); 43 return block; 44 } 45 46 static HBasicBlock* createEntryBlock(HGraph* graph, ArenaAllocator* allocator) { 47 HBasicBlock* block = createGotoBlock(graph, allocator); 48 graph->SetEntryBlock(block); 49 return block; 50 } 51 52 static HBasicBlock* createReturnBlock(HGraph* graph, ArenaAllocator* allocator) { 53 HBasicBlock* block = new (allocator) HBasicBlock(graph); 54 graph->AddBlock(block); 55 HInstruction* return_instr = new (allocator) HReturnVoid(); 56 block->AddInstruction(return_instr); 57 return block; 58 } 59 60 static HBasicBlock* createExitBlock(HGraph* graph, ArenaAllocator* allocator) { 61 HBasicBlock* block = new (allocator) HBasicBlock(graph); 62 graph->AddBlock(block); 63 HInstruction* exit_instr = new (allocator) HExit(); 64 block->AddInstruction(exit_instr); 65 return block; 66 } 67 68 69 // Test that the successors of an if block stay consistent after a SimplifyCFG. 70 // This test sets the false block to be the return block. 71 TEST(GraphTest, IfSuccessorSimpleJoinBlock1) { 72 ArenaPool pool; 73 ArenaAllocator allocator(&pool); 74 75 HGraph* graph = CreateGraph(&allocator); 76 HBasicBlock* entry_block = createEntryBlock(graph, &allocator); 77 HBasicBlock* if_block = createIfBlock(graph, &allocator); 78 HBasicBlock* if_true = createGotoBlock(graph, &allocator); 79 HBasicBlock* return_block = createReturnBlock(graph, &allocator); 80 HBasicBlock* exit_block = createExitBlock(graph, &allocator); 81 82 entry_block->AddSuccessor(if_block); 83 if_block->AddSuccessor(if_true); 84 if_true->AddSuccessor(return_block); 85 if_block->AddSuccessor(return_block); 86 return_block->AddSuccessor(exit_block); 87 88 ASSERT_EQ(if_block->GetLastInstruction()->AsIf()->IfTrueSuccessor(), if_true); 89 ASSERT_EQ(if_block->GetLastInstruction()->AsIf()->IfFalseSuccessor(), return_block); 90 91 graph->SimplifyCFG(); 92 93 // Ensure we still have the same if true block. 94 ASSERT_EQ(if_block->GetLastInstruction()->AsIf()->IfTrueSuccessor(), if_true); 95 96 // Ensure the critical edge has been removed. 97 HBasicBlock* false_block = if_block->GetLastInstruction()->AsIf()->IfFalseSuccessor(); 98 ASSERT_NE(false_block, return_block); 99 100 // Ensure the new block branches to the join block. 101 ASSERT_EQ(false_block->GetSuccessors()[0], return_block); 102 } 103 104 // Test that the successors of an if block stay consistent after a SimplifyCFG. 105 // This test sets the true block to be the return block. 106 TEST(GraphTest, IfSuccessorSimpleJoinBlock2) { 107 ArenaPool pool; 108 ArenaAllocator allocator(&pool); 109 110 HGraph* graph = CreateGraph(&allocator); 111 HBasicBlock* entry_block = createEntryBlock(graph, &allocator); 112 HBasicBlock* if_block = createIfBlock(graph, &allocator); 113 HBasicBlock* if_false = createGotoBlock(graph, &allocator); 114 HBasicBlock* return_block = createReturnBlock(graph, &allocator); 115 HBasicBlock* exit_block = createExitBlock(graph, &allocator); 116 117 entry_block->AddSuccessor(if_block); 118 if_block->AddSuccessor(return_block); 119 if_false->AddSuccessor(return_block); 120 if_block->AddSuccessor(if_false); 121 return_block->AddSuccessor(exit_block); 122 123 ASSERT_EQ(if_block->GetLastInstruction()->AsIf()->IfTrueSuccessor(), return_block); 124 ASSERT_EQ(if_block->GetLastInstruction()->AsIf()->IfFalseSuccessor(), if_false); 125 126 graph->SimplifyCFG(); 127 128 // Ensure we still have the same if true block. 129 ASSERT_EQ(if_block->GetLastInstruction()->AsIf()->IfFalseSuccessor(), if_false); 130 131 // Ensure the critical edge has been removed. 132 HBasicBlock* true_block = if_block->GetLastInstruction()->AsIf()->IfTrueSuccessor(); 133 ASSERT_NE(true_block, return_block); 134 135 // Ensure the new block branches to the join block. 136 ASSERT_EQ(true_block->GetSuccessors()[0], return_block); 137 } 138 139 // Test that the successors of an if block stay consistent after a SimplifyCFG. 140 // This test sets the true block to be the loop header. 141 TEST(GraphTest, IfSuccessorMultipleBackEdges1) { 142 ArenaPool pool; 143 ArenaAllocator allocator(&pool); 144 145 HGraph* graph = CreateGraph(&allocator); 146 HBasicBlock* entry_block = createEntryBlock(graph, &allocator); 147 HBasicBlock* if_block = createIfBlock(graph, &allocator); 148 HBasicBlock* return_block = createReturnBlock(graph, &allocator); 149 HBasicBlock* exit_block = createExitBlock(graph, &allocator); 150 151 entry_block->AddSuccessor(if_block); 152 if_block->AddSuccessor(if_block); 153 if_block->AddSuccessor(return_block); 154 return_block->AddSuccessor(exit_block); 155 156 ASSERT_EQ(if_block->GetLastInstruction()->AsIf()->IfTrueSuccessor(), if_block); 157 ASSERT_EQ(if_block->GetLastInstruction()->AsIf()->IfFalseSuccessor(), return_block); 158 159 graph->BuildDominatorTree(); 160 161 // Ensure we still have the same if false block. 162 ASSERT_EQ(if_block->GetLastInstruction()->AsIf()->IfFalseSuccessor(), return_block); 163 164 // Ensure there is only one back edge. 165 ASSERT_EQ(if_block->GetPredecessors().size(), 2u); 166 ASSERT_EQ(if_block->GetPredecessors()[0], entry_block->GetSingleSuccessor()); 167 ASSERT_NE(if_block->GetPredecessors()[1], if_block); 168 169 // Ensure the new block is the back edge. 170 ASSERT_EQ(if_block->GetPredecessors()[1], 171 if_block->GetLastInstruction()->AsIf()->IfTrueSuccessor()); 172 } 173 174 // Test that the successors of an if block stay consistent after a SimplifyCFG. 175 // This test sets the false block to be the loop header. 176 TEST(GraphTest, IfSuccessorMultipleBackEdges2) { 177 ArenaPool pool; 178 ArenaAllocator allocator(&pool); 179 180 HGraph* graph = CreateGraph(&allocator); 181 HBasicBlock* entry_block = createEntryBlock(graph, &allocator); 182 HBasicBlock* if_block = createIfBlock(graph, &allocator); 183 HBasicBlock* return_block = createReturnBlock(graph, &allocator); 184 HBasicBlock* exit_block = createExitBlock(graph, &allocator); 185 186 entry_block->AddSuccessor(if_block); 187 if_block->AddSuccessor(return_block); 188 if_block->AddSuccessor(if_block); 189 return_block->AddSuccessor(exit_block); 190 191 ASSERT_EQ(if_block->GetLastInstruction()->AsIf()->IfTrueSuccessor(), return_block); 192 ASSERT_EQ(if_block->GetLastInstruction()->AsIf()->IfFalseSuccessor(), if_block); 193 194 graph->BuildDominatorTree(); 195 196 // Ensure we still have the same if true block. 197 ASSERT_EQ(if_block->GetLastInstruction()->AsIf()->IfTrueSuccessor(), return_block); 198 199 // Ensure there is only one back edge. 200 ASSERT_EQ(if_block->GetPredecessors().size(), 2u); 201 ASSERT_EQ(if_block->GetPredecessors()[0], entry_block->GetSingleSuccessor()); 202 ASSERT_NE(if_block->GetPredecessors()[1], if_block); 203 204 // Ensure the new block is the back edge. 205 ASSERT_EQ(if_block->GetPredecessors()[1], 206 if_block->GetLastInstruction()->AsIf()->IfFalseSuccessor()); 207 } 208 209 // Test that the successors of an if block stay consistent after a SimplifyCFG. 210 // This test sets the true block to be a loop header with multiple pre headers. 211 TEST(GraphTest, IfSuccessorMultiplePreHeaders1) { 212 ArenaPool pool; 213 ArenaAllocator allocator(&pool); 214 215 HGraph* graph = CreateGraph(&allocator); 216 HBasicBlock* entry_block = createEntryBlock(graph, &allocator); 217 HBasicBlock* first_if_block = createIfBlock(graph, &allocator); 218 HBasicBlock* if_block = createIfBlock(graph, &allocator); 219 HBasicBlock* loop_block = createGotoBlock(graph, &allocator); 220 HBasicBlock* return_block = createReturnBlock(graph, &allocator); 221 222 entry_block->AddSuccessor(first_if_block); 223 first_if_block->AddSuccessor(if_block); 224 first_if_block->AddSuccessor(loop_block); 225 loop_block->AddSuccessor(loop_block); 226 if_block->AddSuccessor(loop_block); 227 if_block->AddSuccessor(return_block); 228 229 230 ASSERT_EQ(if_block->GetLastInstruction()->AsIf()->IfTrueSuccessor(), loop_block); 231 ASSERT_EQ(if_block->GetLastInstruction()->AsIf()->IfFalseSuccessor(), return_block); 232 233 graph->BuildDominatorTree(); 234 235 HIf* if_instr = if_block->GetLastInstruction()->AsIf(); 236 // Ensure we still have the same if false block. 237 ASSERT_EQ(if_instr->IfFalseSuccessor(), return_block); 238 239 // Ensure there is only one pre header.. 240 ASSERT_EQ(loop_block->GetPredecessors().size(), 2u); 241 242 // Ensure the new block is the successor of the true block. 243 ASSERT_EQ(if_instr->IfTrueSuccessor()->GetSuccessors().size(), 1u); 244 ASSERT_EQ(if_instr->IfTrueSuccessor()->GetSuccessors()[0], 245 loop_block->GetLoopInformation()->GetPreHeader()); 246 } 247 248 // Test that the successors of an if block stay consistent after a SimplifyCFG. 249 // This test sets the false block to be a loop header with multiple pre headers. 250 TEST(GraphTest, IfSuccessorMultiplePreHeaders2) { 251 ArenaPool pool; 252 ArenaAllocator allocator(&pool); 253 254 HGraph* graph = CreateGraph(&allocator); 255 HBasicBlock* entry_block = createEntryBlock(graph, &allocator); 256 HBasicBlock* first_if_block = createIfBlock(graph, &allocator); 257 HBasicBlock* if_block = createIfBlock(graph, &allocator); 258 HBasicBlock* loop_block = createGotoBlock(graph, &allocator); 259 HBasicBlock* return_block = createReturnBlock(graph, &allocator); 260 261 entry_block->AddSuccessor(first_if_block); 262 first_if_block->AddSuccessor(if_block); 263 first_if_block->AddSuccessor(loop_block); 264 loop_block->AddSuccessor(loop_block); 265 if_block->AddSuccessor(return_block); 266 if_block->AddSuccessor(loop_block); 267 268 ASSERT_EQ(if_block->GetLastInstruction()->AsIf()->IfTrueSuccessor(), return_block); 269 ASSERT_EQ(if_block->GetLastInstruction()->AsIf()->IfFalseSuccessor(), loop_block); 270 271 graph->BuildDominatorTree(); 272 273 HIf* if_instr = if_block->GetLastInstruction()->AsIf(); 274 // Ensure we still have the same if true block. 275 ASSERT_EQ(if_instr->IfTrueSuccessor(), return_block); 276 277 // Ensure there is only one pre header.. 278 ASSERT_EQ(loop_block->GetPredecessors().size(), 2u); 279 280 // Ensure the new block is the successor of the false block. 281 ASSERT_EQ(if_instr->IfFalseSuccessor()->GetSuccessors().size(), 1u); 282 ASSERT_EQ(if_instr->IfFalseSuccessor()->GetSuccessors()[0], 283 loop_block->GetLoopInformation()->GetPreHeader()); 284 } 285 286 TEST(GraphTest, InsertInstructionBefore) { 287 ArenaPool pool; 288 ArenaAllocator allocator(&pool); 289 290 HGraph* graph = CreateGraph(&allocator); 291 HBasicBlock* block = createGotoBlock(graph, &allocator); 292 HInstruction* got = block->GetLastInstruction(); 293 ASSERT_TRUE(got->IsControlFlow()); 294 295 // Test at the beginning of the block. 296 HInstruction* first_instruction = new (&allocator) HIntConstant(4); 297 block->InsertInstructionBefore(first_instruction, got); 298 299 ASSERT_NE(first_instruction->GetId(), -1); 300 ASSERT_EQ(first_instruction->GetBlock(), block); 301 ASSERT_EQ(block->GetFirstInstruction(), first_instruction); 302 ASSERT_EQ(block->GetLastInstruction(), got); 303 ASSERT_EQ(first_instruction->GetNext(), got); 304 ASSERT_EQ(first_instruction->GetPrevious(), nullptr); 305 ASSERT_EQ(got->GetNext(), nullptr); 306 ASSERT_EQ(got->GetPrevious(), first_instruction); 307 308 // Test in the middle of the block. 309 HInstruction* second_instruction = new (&allocator) HIntConstant(4); 310 block->InsertInstructionBefore(second_instruction, got); 311 312 ASSERT_NE(second_instruction->GetId(), -1); 313 ASSERT_EQ(second_instruction->GetBlock(), block); 314 ASSERT_EQ(block->GetFirstInstruction(), first_instruction); 315 ASSERT_EQ(block->GetLastInstruction(), got); 316 ASSERT_EQ(first_instruction->GetNext(), second_instruction); 317 ASSERT_EQ(first_instruction->GetPrevious(), nullptr); 318 ASSERT_EQ(second_instruction->GetNext(), got); 319 ASSERT_EQ(second_instruction->GetPrevious(), first_instruction); 320 ASSERT_EQ(got->GetNext(), nullptr); 321 ASSERT_EQ(got->GetPrevious(), second_instruction); 322 } 323 324 } // namespace art 325
