1ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain/* 2ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain * Copyright (C) 2014 The Android Open Source Project 3ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain * 4ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain * Licensed under the Apache License, Version 2.0 (the "License"); 5ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain * you may not use this file except in compliance with the License. 6ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain * You may obtain a copy of the License at 7ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain * 8ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain * http://www.apache.org/licenses/LICENSE-2.0 9ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain * 10ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain * Unless required by applicable law or agreed to in writing, software 11ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain * distributed under the License is distributed on an "AS IS" BASIS, 12ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain * See the License for the specific language governing permissions and 14ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain * limitations under the License. 15ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain */ 16ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain 17ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain#include "graph_checker.h" 18ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain#include "optimizing_unit_test.h" 19ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain 20ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillainnamespace art { 21ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain 22ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain/** 23ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain * Create a simple control-flow graph composed of two blocks: 24ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain * 25ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain * BasicBlock 0, succ: 1 26dbf5d754f542022b0ca35673d9ddd0379202e627David Brazdil * 0: ReturnVoid 1 27ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain * BasicBlock 1, pred: 0 28ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain * 1: Exit 29ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain */ 30ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland LevillainHGraph* CreateSimpleCFG(ArenaAllocator* allocator) { 310a23d74dc2751440822960eab218be4cb8843647Nicolas Geoffray HGraph* graph = CreateGraph(allocator); 32ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain HBasicBlock* entry_block = new (allocator) HBasicBlock(graph); 33dbf5d754f542022b0ca35673d9ddd0379202e627David Brazdil entry_block->AddInstruction(new (allocator) HReturnVoid()); 34ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain graph->AddBlock(entry_block); 35ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain graph->SetEntryBlock(entry_block); 36ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain HBasicBlock* exit_block = new (allocator) HBasicBlock(graph); 37ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain exit_block->AddInstruction(new (allocator) HExit()); 38ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain graph->AddBlock(exit_block); 39ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain graph->SetExitBlock(exit_block); 40ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain entry_block->AddSuccessor(exit_block); 418e73ac34f4fac4aee96ccef82e08fab0474a4c98David Brazdil graph->BuildDominatorTree(); 42ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain return graph; 43ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain} 44ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain 45ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillainstatic void TestCode(const uint16_t* data) { 46ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain ArenaPool pool; 47ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain ArenaAllocator allocator(&pool); 48ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain HGraph* graph = CreateCFG(&allocator, data); 49ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain ASSERT_NE(graph, nullptr); 50ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain 51655e585073ac271cc9afa7c9d6ff5ab4dbe4b72eVladimir Marko GraphChecker graph_checker(graph); 52633021e6ff6b9a57a374a994e74cfd69275ce100Roland Levillain graph_checker.Run(); 53ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain ASSERT_TRUE(graph_checker.IsValid()); 54ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain} 55ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain 56badd826664896d4a9628a5a89b78016894aa414bDavid Brazdilclass GraphCheckerTest : public CommonCompilerTest {}; 57ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain 58badd826664896d4a9628a5a89b78016894aa414bDavid BrazdilTEST_F(GraphCheckerTest, ReturnVoid) { 59ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain const uint16_t data[] = ZERO_REGISTER_CODE_ITEM( 60ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain Instruction::RETURN_VOID); 61ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain 62ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain TestCode(data); 63ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain} 64ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain 65badd826664896d4a9628a5a89b78016894aa414bDavid BrazdilTEST_F(GraphCheckerTest, CFG1) { 66ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain const uint16_t data[] = ZERO_REGISTER_CODE_ITEM( 67ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain Instruction::GOTO | 0x100, 68ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain Instruction::RETURN_VOID); 69ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain 70ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain TestCode(data); 71ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain} 72ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain 73badd826664896d4a9628a5a89b78016894aa414bDavid BrazdilTEST_F(GraphCheckerTest, CFG2) { 74ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain const uint16_t data[] = ONE_REGISTER_CODE_ITEM( 75ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain Instruction::CONST_4 | 0 | 0, 76ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain Instruction::IF_EQ, 3, 77ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain Instruction::GOTO | 0x100, 78ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain Instruction::RETURN_VOID); 79ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain 80ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain TestCode(data); 81ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain} 82ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain 83badd826664896d4a9628a5a89b78016894aa414bDavid BrazdilTEST_F(GraphCheckerTest, CFG3) { 84ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain const uint16_t data[] = ONE_REGISTER_CODE_ITEM( 85ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain Instruction::CONST_4 | 0 | 0, 86ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain Instruction::IF_EQ, 3, 87ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain Instruction::GOTO | 0x100, 88ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain Instruction::GOTO | 0xFF00); 89ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain 90ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain TestCode(data); 91ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain} 92ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain 93ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain// Test case with an invalid graph containing inconsistent 94ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain// predecessor/successor arcs in CFG. 95badd826664896d4a9628a5a89b78016894aa414bDavid BrazdilTEST_F(GraphCheckerTest, InconsistentPredecessorsAndSuccessors) { 96ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain ArenaPool pool; 97ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain ArenaAllocator allocator(&pool); 98ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain 99ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain HGraph* graph = CreateSimpleCFG(&allocator); 100655e585073ac271cc9afa7c9d6ff5ab4dbe4b72eVladimir Marko GraphChecker graph_checker(graph); 101633021e6ff6b9a57a374a994e74cfd69275ce100Roland Levillain graph_checker.Run(); 102ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain ASSERT_TRUE(graph_checker.IsValid()); 103ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain 104ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain // Remove the entry block from the exit block's predecessors, to create an 105ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain // inconsistent successor/predecessor relation. 106ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain graph->GetExitBlock()->RemovePredecessor(graph->GetEntryBlock()); 107633021e6ff6b9a57a374a994e74cfd69275ce100Roland Levillain graph_checker.Run(); 108ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain ASSERT_FALSE(graph_checker.IsValid()); 109ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain} 110ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain 111ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain// Test case with an invalid graph containing a non-branch last 112ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain// instruction in a block. 113badd826664896d4a9628a5a89b78016894aa414bDavid BrazdilTEST_F(GraphCheckerTest, BlockEndingWithNonBranchInstruction) { 114ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain ArenaPool pool; 115ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain ArenaAllocator allocator(&pool); 116ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain 117ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain HGraph* graph = CreateSimpleCFG(&allocator); 118655e585073ac271cc9afa7c9d6ff5ab4dbe4b72eVladimir Marko GraphChecker graph_checker(graph); 119633021e6ff6b9a57a374a994e74cfd69275ce100Roland Levillain graph_checker.Run(); 120ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain ASSERT_TRUE(graph_checker.IsValid()); 121ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain 122ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain // Remove the sole instruction of the exit block (composed of a 123ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain // single Exit instruction) to make it invalid (i.e. not ending by a 124ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain // branch instruction). 125ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain HBasicBlock* exit_block = graph->GetExitBlock(); 126ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain HInstruction* last_inst = exit_block->GetLastInstruction(); 127ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain exit_block->RemoveInstruction(last_inst); 128ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain 129633021e6ff6b9a57a374a994e74cfd69275ce100Roland Levillain graph_checker.Run(); 130ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain ASSERT_FALSE(graph_checker.IsValid()); 131ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain} 132ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain 133badd826664896d4a9628a5a89b78016894aa414bDavid BrazdilTEST_F(GraphCheckerTest, SSAPhi) { 134ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain // This code creates one Phi function during the conversion to SSA form. 135ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain const uint16_t data[] = ONE_REGISTER_CODE_ITEM( 136ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain Instruction::CONST_4 | 0 | 0, 137ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain Instruction::IF_EQ, 3, 138ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain Instruction::CONST_4 | 4 << 12 | 0, 139ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain Instruction::RETURN | 0 << 8); 140ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain 141badd826664896d4a9628a5a89b78016894aa414bDavid Brazdil TestCode(data); 142ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain} 143ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain 144ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain} // namespace art 145