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