1ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray/* 2ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray * Copyright (C) 2014 The Android Open Source Project 3ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray * 4ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray * Licensed under the Apache License, Version 2.0 (the "License"); 5ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray * you may not use this file except in compliance with the License. 6ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray * You may obtain a copy of the License at 7ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray * 8ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray * http://www.apache.org/licenses/LICENSE-2.0 9ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray * 10ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray * Unless required by applicable law or agreed to in writing, software 11ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray * distributed under the License is distributed on an "AS IS" BASIS, 12ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray * See the License for the specific language governing permissions and 14ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray * limitations under the License. 15ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray */ 16ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray 17b666f4805c8ae707ea6fd7f6c7f375e0b000dba8Mathieu Chartier#include "base/arena_allocator.h" 18ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray#include "base/stringprintf.h" 19ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray#include "builder.h" 20ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray#include "nodes.h" 21ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray#include "optimizing_unit_test.h" 22ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray#include "pretty_printer.h" 23ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray 24ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray#include "gtest/gtest.h" 25ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray 26ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffraynamespace art { 27ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray 28ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffraystatic HBasicBlock* createIfBlock(HGraph* graph, ArenaAllocator* allocator) { 29ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray HBasicBlock* if_block = new (allocator) HBasicBlock(graph); 30ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray graph->AddBlock(if_block); 318d5b8b295930aaa43255c4f0b74ece3ee8b43a47David Brazdil HInstruction* instr = graph->GetIntConstant(4); 3220dfc797dc631bf8d655dcf123f46f13332d3074Dave Allison HInstruction* equal = new (allocator) HEqual(instr, instr); 3320dfc797dc631bf8d655dcf123f46f13332d3074Dave Allison if_block->AddInstruction(equal); 3420dfc797dc631bf8d655dcf123f46f13332d3074Dave Allison instr = new (allocator) HIf(equal); 35ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray if_block->AddInstruction(instr); 36ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray return if_block; 37ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray} 38ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray 39ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffraystatic HBasicBlock* createGotoBlock(HGraph* graph, ArenaAllocator* allocator) { 40ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray HBasicBlock* block = new (allocator) HBasicBlock(graph); 41ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray graph->AddBlock(block); 42ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray HInstruction* got = new (allocator) HGoto(); 43ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray block->AddInstruction(got); 44ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray return block; 45ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray} 46ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray 478d5b8b295930aaa43255c4f0b74ece3ee8b43a47David Brazdilstatic HBasicBlock* createEntryBlock(HGraph* graph, ArenaAllocator* allocator) { 488d5b8b295930aaa43255c4f0b74ece3ee8b43a47David Brazdil HBasicBlock* block = createGotoBlock(graph, allocator); 498d5b8b295930aaa43255c4f0b74ece3ee8b43a47David Brazdil graph->SetEntryBlock(block); 508d5b8b295930aaa43255c4f0b74ece3ee8b43a47David Brazdil return block; 518d5b8b295930aaa43255c4f0b74ece3ee8b43a47David Brazdil} 528d5b8b295930aaa43255c4f0b74ece3ee8b43a47David Brazdil 53ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffraystatic HBasicBlock* createReturnBlock(HGraph* graph, ArenaAllocator* allocator) { 54ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray HBasicBlock* block = new (allocator) HBasicBlock(graph); 55ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray graph->AddBlock(block); 56ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray HInstruction* return_instr = new (allocator) HReturnVoid(); 57ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray block->AddInstruction(return_instr); 58ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray return block; 59ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray} 60ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray 61ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffraystatic HBasicBlock* createExitBlock(HGraph* graph, ArenaAllocator* allocator) { 62ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray HBasicBlock* block = new (allocator) HBasicBlock(graph); 63ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray graph->AddBlock(block); 64ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray HInstruction* exit_instr = new (allocator) HExit(); 65ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray block->AddInstruction(exit_instr); 66ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray return block; 67ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray} 68ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray 69ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray 70ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray// Test that the successors of an if block stay consistent after a SimplifyCFG. 71ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray// This test sets the false block to be the return block. 72ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas GeoffrayTEST(GraphTest, IfSuccessorSimpleJoinBlock1) { 73ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray ArenaPool pool; 74ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray ArenaAllocator allocator(&pool); 75ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray 760a23d74dc2751440822960eab218be4cb8843647Nicolas Geoffray HGraph* graph = CreateGraph(&allocator); 778d5b8b295930aaa43255c4f0b74ece3ee8b43a47David Brazdil HBasicBlock* entry_block = createEntryBlock(graph, &allocator); 78ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray HBasicBlock* if_block = createIfBlock(graph, &allocator); 79ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray HBasicBlock* if_true = createGotoBlock(graph, &allocator); 80ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray HBasicBlock* return_block = createReturnBlock(graph, &allocator); 81ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray HBasicBlock* exit_block = createExitBlock(graph, &allocator); 82ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray 83ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray entry_block->AddSuccessor(if_block); 84ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray if_block->AddSuccessor(if_true); 85ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray if_true->AddSuccessor(return_block); 86ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray if_block->AddSuccessor(return_block); 87ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray return_block->AddSuccessor(exit_block); 88ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray 89ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray ASSERT_EQ(if_block->GetLastInstruction()->AsIf()->IfTrueSuccessor(), if_true); 90ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray ASSERT_EQ(if_block->GetLastInstruction()->AsIf()->IfFalseSuccessor(), return_block); 91ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray 92ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray graph->SimplifyCFG(); 93ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray 94ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray // Ensure we still have the same if true block. 95ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray ASSERT_EQ(if_block->GetLastInstruction()->AsIf()->IfTrueSuccessor(), if_true); 96ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray 97ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray // Ensure the critical edge has been removed. 98ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray HBasicBlock* false_block = if_block->GetLastInstruction()->AsIf()->IfFalseSuccessor(); 99ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray ASSERT_NE(false_block, return_block); 100ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray 101ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray // Ensure the new block branches to the join block. 102ec7802a102d49ab5c17495118d4fe0bcc7287bebVladimir Marko ASSERT_EQ(false_block->GetSuccessors()[0], return_block); 103ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray} 104ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray 105ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray// Test that the successors of an if block stay consistent after a SimplifyCFG. 106ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray// This test sets the true block to be the return block. 107ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas GeoffrayTEST(GraphTest, IfSuccessorSimpleJoinBlock2) { 108ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray ArenaPool pool; 109ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray ArenaAllocator allocator(&pool); 110ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray 1110a23d74dc2751440822960eab218be4cb8843647Nicolas Geoffray HGraph* graph = CreateGraph(&allocator); 1128d5b8b295930aaa43255c4f0b74ece3ee8b43a47David Brazdil HBasicBlock* entry_block = createEntryBlock(graph, &allocator); 113ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray HBasicBlock* if_block = createIfBlock(graph, &allocator); 114ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray HBasicBlock* if_false = createGotoBlock(graph, &allocator); 115ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray HBasicBlock* return_block = createReturnBlock(graph, &allocator); 116ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray HBasicBlock* exit_block = createExitBlock(graph, &allocator); 117ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray 118ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray entry_block->AddSuccessor(if_block); 119ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray if_block->AddSuccessor(return_block); 120ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray if_false->AddSuccessor(return_block); 121ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray if_block->AddSuccessor(if_false); 122ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray return_block->AddSuccessor(exit_block); 123ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray 124ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray ASSERT_EQ(if_block->GetLastInstruction()->AsIf()->IfTrueSuccessor(), return_block); 125ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray ASSERT_EQ(if_block->GetLastInstruction()->AsIf()->IfFalseSuccessor(), if_false); 126ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray 127ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray graph->SimplifyCFG(); 128ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray 129ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray // Ensure we still have the same if true block. 130ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray ASSERT_EQ(if_block->GetLastInstruction()->AsIf()->IfFalseSuccessor(), if_false); 131ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray 132ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray // Ensure the critical edge has been removed. 133ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray HBasicBlock* true_block = if_block->GetLastInstruction()->AsIf()->IfTrueSuccessor(); 134ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray ASSERT_NE(true_block, return_block); 135ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray 136ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray // Ensure the new block branches to the join block. 137ec7802a102d49ab5c17495118d4fe0bcc7287bebVladimir Marko ASSERT_EQ(true_block->GetSuccessors()[0], return_block); 138ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray} 139ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray 140ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray// Test that the successors of an if block stay consistent after a SimplifyCFG. 141ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray// This test sets the true block to be the loop header. 142ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas GeoffrayTEST(GraphTest, IfSuccessorMultipleBackEdges1) { 143ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray ArenaPool pool; 144ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray ArenaAllocator allocator(&pool); 145ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray 1460a23d74dc2751440822960eab218be4cb8843647Nicolas Geoffray HGraph* graph = CreateGraph(&allocator); 1478d5b8b295930aaa43255c4f0b74ece3ee8b43a47David Brazdil HBasicBlock* entry_block = createEntryBlock(graph, &allocator); 148ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray HBasicBlock* if_block = createIfBlock(graph, &allocator); 149ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray HBasicBlock* return_block = createReturnBlock(graph, &allocator); 150ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray HBasicBlock* exit_block = createExitBlock(graph, &allocator); 151ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray 152ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray entry_block->AddSuccessor(if_block); 153ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray if_block->AddSuccessor(if_block); 154ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray if_block->AddSuccessor(return_block); 155ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray return_block->AddSuccessor(exit_block); 156ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray 157ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray ASSERT_EQ(if_block->GetLastInstruction()->AsIf()->IfTrueSuccessor(), if_block); 158ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray ASSERT_EQ(if_block->GetLastInstruction()->AsIf()->IfFalseSuccessor(), return_block); 159ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray 160ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray graph->BuildDominatorTree(); 161ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray 162ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray // Ensure we still have the same if false block. 163ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray ASSERT_EQ(if_block->GetLastInstruction()->AsIf()->IfFalseSuccessor(), return_block); 164ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray 165ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray // Ensure there is only one back edge. 1666058455d486219994921b63a2d774dc9908415a2Vladimir Marko ASSERT_EQ(if_block->GetPredecessors().size(), 2u); 167788f2f05c3e5b0e5bda247b00e34f0094585546fNicolas Geoffray ASSERT_EQ(if_block->GetPredecessors()[0], entry_block->GetSingleSuccessor()); 168ec7802a102d49ab5c17495118d4fe0bcc7287bebVladimir Marko ASSERT_NE(if_block->GetPredecessors()[1], if_block); 169ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray 170ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray // Ensure the new block is the back edge. 171ec7802a102d49ab5c17495118d4fe0bcc7287bebVladimir Marko ASSERT_EQ(if_block->GetPredecessors()[1], 172ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray if_block->GetLastInstruction()->AsIf()->IfTrueSuccessor()); 173ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray} 174ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray 175ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray// Test that the successors of an if block stay consistent after a SimplifyCFG. 176ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray// This test sets the false block to be the loop header. 177ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas GeoffrayTEST(GraphTest, IfSuccessorMultipleBackEdges2) { 178ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray ArenaPool pool; 179ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray ArenaAllocator allocator(&pool); 180ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray 1810a23d74dc2751440822960eab218be4cb8843647Nicolas Geoffray HGraph* graph = CreateGraph(&allocator); 1828d5b8b295930aaa43255c4f0b74ece3ee8b43a47David Brazdil HBasicBlock* entry_block = createEntryBlock(graph, &allocator); 183ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray HBasicBlock* if_block = createIfBlock(graph, &allocator); 184ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray HBasicBlock* return_block = createReturnBlock(graph, &allocator); 185ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray HBasicBlock* exit_block = createExitBlock(graph, &allocator); 186ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray 187ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray entry_block->AddSuccessor(if_block); 188ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray if_block->AddSuccessor(return_block); 189ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray if_block->AddSuccessor(if_block); 190ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray return_block->AddSuccessor(exit_block); 191ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray 192ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray ASSERT_EQ(if_block->GetLastInstruction()->AsIf()->IfTrueSuccessor(), return_block); 193ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray ASSERT_EQ(if_block->GetLastInstruction()->AsIf()->IfFalseSuccessor(), if_block); 194ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray 195ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray graph->BuildDominatorTree(); 196ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray 197ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray // Ensure we still have the same if true block. 198ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray ASSERT_EQ(if_block->GetLastInstruction()->AsIf()->IfTrueSuccessor(), return_block); 199ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray 200ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray // Ensure there is only one back edge. 2016058455d486219994921b63a2d774dc9908415a2Vladimir Marko ASSERT_EQ(if_block->GetPredecessors().size(), 2u); 202788f2f05c3e5b0e5bda247b00e34f0094585546fNicolas Geoffray ASSERT_EQ(if_block->GetPredecessors()[0], entry_block->GetSingleSuccessor()); 203ec7802a102d49ab5c17495118d4fe0bcc7287bebVladimir Marko ASSERT_NE(if_block->GetPredecessors()[1], if_block); 204ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray 205ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray // Ensure the new block is the back edge. 206ec7802a102d49ab5c17495118d4fe0bcc7287bebVladimir Marko ASSERT_EQ(if_block->GetPredecessors()[1], 207ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray if_block->GetLastInstruction()->AsIf()->IfFalseSuccessor()); 208ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray} 209ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray 210ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray// Test that the successors of an if block stay consistent after a SimplifyCFG. 211ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray// This test sets the true block to be a loop header with multiple pre headers. 212ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas GeoffrayTEST(GraphTest, IfSuccessorMultiplePreHeaders1) { 213ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray ArenaPool pool; 214ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray ArenaAllocator allocator(&pool); 215ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray 2160a23d74dc2751440822960eab218be4cb8843647Nicolas Geoffray HGraph* graph = CreateGraph(&allocator); 2178d5b8b295930aaa43255c4f0b74ece3ee8b43a47David Brazdil HBasicBlock* entry_block = createEntryBlock(graph, &allocator); 218ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray HBasicBlock* first_if_block = createIfBlock(graph, &allocator); 219ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray HBasicBlock* if_block = createIfBlock(graph, &allocator); 220ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray HBasicBlock* loop_block = createGotoBlock(graph, &allocator); 221ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray HBasicBlock* return_block = createReturnBlock(graph, &allocator); 222ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray 223ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray entry_block->AddSuccessor(first_if_block); 224ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray first_if_block->AddSuccessor(if_block); 225ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray first_if_block->AddSuccessor(loop_block); 226ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray loop_block->AddSuccessor(loop_block); 227ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray if_block->AddSuccessor(loop_block); 228ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray if_block->AddSuccessor(return_block); 229ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray 230ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray 231ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray ASSERT_EQ(if_block->GetLastInstruction()->AsIf()->IfTrueSuccessor(), loop_block); 232ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray ASSERT_EQ(if_block->GetLastInstruction()->AsIf()->IfFalseSuccessor(), return_block); 233ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray 234ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray graph->BuildDominatorTree(); 235ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray 236ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray HIf* if_instr = if_block->GetLastInstruction()->AsIf(); 237ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray // Ensure we still have the same if false block. 238ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray ASSERT_EQ(if_instr->IfFalseSuccessor(), return_block); 239ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray 240ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray // Ensure there is only one pre header.. 2416058455d486219994921b63a2d774dc9908415a2Vladimir Marko ASSERT_EQ(loop_block->GetPredecessors().size(), 2u); 242ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray 243ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray // Ensure the new block is the successor of the true block. 2446058455d486219994921b63a2d774dc9908415a2Vladimir Marko ASSERT_EQ(if_instr->IfTrueSuccessor()->GetSuccessors().size(), 1u); 245ec7802a102d49ab5c17495118d4fe0bcc7287bebVladimir Marko ASSERT_EQ(if_instr->IfTrueSuccessor()->GetSuccessors()[0], 246ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray loop_block->GetLoopInformation()->GetPreHeader()); 247ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray} 248ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray 249ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray// Test that the successors of an if block stay consistent after a SimplifyCFG. 250ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray// This test sets the false block to be a loop header with multiple pre headers. 251ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas GeoffrayTEST(GraphTest, IfSuccessorMultiplePreHeaders2) { 252ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray ArenaPool pool; 253ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray ArenaAllocator allocator(&pool); 254ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray 2550a23d74dc2751440822960eab218be4cb8843647Nicolas Geoffray HGraph* graph = CreateGraph(&allocator); 2568d5b8b295930aaa43255c4f0b74ece3ee8b43a47David Brazdil HBasicBlock* entry_block = createEntryBlock(graph, &allocator); 257ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray HBasicBlock* first_if_block = createIfBlock(graph, &allocator); 258ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray HBasicBlock* if_block = createIfBlock(graph, &allocator); 259ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray HBasicBlock* loop_block = createGotoBlock(graph, &allocator); 260ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray HBasicBlock* return_block = createReturnBlock(graph, &allocator); 261ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray 262ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray entry_block->AddSuccessor(first_if_block); 263ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray first_if_block->AddSuccessor(if_block); 264ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray first_if_block->AddSuccessor(loop_block); 265ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray loop_block->AddSuccessor(loop_block); 266ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray if_block->AddSuccessor(return_block); 267ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray if_block->AddSuccessor(loop_block); 268ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray 269ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray ASSERT_EQ(if_block->GetLastInstruction()->AsIf()->IfTrueSuccessor(), return_block); 270ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray ASSERT_EQ(if_block->GetLastInstruction()->AsIf()->IfFalseSuccessor(), loop_block); 271ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray 272ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray graph->BuildDominatorTree(); 273ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray 274ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray HIf* if_instr = if_block->GetLastInstruction()->AsIf(); 275ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray // Ensure we still have the same if true block. 276ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray ASSERT_EQ(if_instr->IfTrueSuccessor(), return_block); 277ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray 278ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray // Ensure there is only one pre header.. 2796058455d486219994921b63a2d774dc9908415a2Vladimir Marko ASSERT_EQ(loop_block->GetPredecessors().size(), 2u); 280ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray 281ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray // Ensure the new block is the successor of the false block. 2826058455d486219994921b63a2d774dc9908415a2Vladimir Marko ASSERT_EQ(if_instr->IfFalseSuccessor()->GetSuccessors().size(), 1u); 283ec7802a102d49ab5c17495118d4fe0bcc7287bebVladimir Marko ASSERT_EQ(if_instr->IfFalseSuccessor()->GetSuccessors()[0], 284ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray loop_block->GetLoopInformation()->GetPreHeader()); 285ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray} 286ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray 287ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas GeoffrayTEST(GraphTest, InsertInstructionBefore) { 288ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray ArenaPool pool; 289ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray ArenaAllocator allocator(&pool); 290ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray 2910a23d74dc2751440822960eab218be4cb8843647Nicolas Geoffray HGraph* graph = CreateGraph(&allocator); 292ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray HBasicBlock* block = createGotoBlock(graph, &allocator); 293ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray HInstruction* got = block->GetLastInstruction(); 294ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray ASSERT_TRUE(got->IsControlFlow()); 295ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray 296ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray // Test at the beginning of the block. 297ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray HInstruction* first_instruction = new (&allocator) HIntConstant(4); 298ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray block->InsertInstructionBefore(first_instruction, got); 299ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray 300ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray ASSERT_NE(first_instruction->GetId(), -1); 301ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray ASSERT_EQ(first_instruction->GetBlock(), block); 302ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray ASSERT_EQ(block->GetFirstInstruction(), first_instruction); 303ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray ASSERT_EQ(block->GetLastInstruction(), got); 304ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray ASSERT_EQ(first_instruction->GetNext(), got); 305ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray ASSERT_EQ(first_instruction->GetPrevious(), nullptr); 306ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray ASSERT_EQ(got->GetNext(), nullptr); 307ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray ASSERT_EQ(got->GetPrevious(), first_instruction); 308ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray 309ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray // Test in the middle of the block. 310ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray HInstruction* second_instruction = new (&allocator) HIntConstant(4); 311ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray block->InsertInstructionBefore(second_instruction, got); 312ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray 313ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray ASSERT_NE(second_instruction->GetId(), -1); 314ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray ASSERT_EQ(second_instruction->GetBlock(), block); 315ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray ASSERT_EQ(block->GetFirstInstruction(), first_instruction); 316ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray ASSERT_EQ(block->GetLastInstruction(), got); 317ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray ASSERT_EQ(first_instruction->GetNext(), second_instruction); 318ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray ASSERT_EQ(first_instruction->GetPrevious(), nullptr); 319ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray ASSERT_EQ(second_instruction->GetNext(), got); 320ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray ASSERT_EQ(second_instruction->GetPrevious(), first_instruction); 321ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray ASSERT_EQ(got->GetNext(), nullptr); 322ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray ASSERT_EQ(got->GetPrevious(), second_instruction); 323ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray} 324ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray 325ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray} // namespace art 326