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