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