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