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 Levillain#include "gtest/gtest.h" 21ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain 22ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillainnamespace art { 23ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain 24ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain/** 25ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain * Create a simple control-flow graph composed of two blocks: 26ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain * 27ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain * BasicBlock 0, succ: 1 28ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain * 0: Goto 1 29ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain * BasicBlock 1, pred: 0 30ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain * 1: Exit 31ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain */ 32ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland LevillainHGraph* CreateSimpleCFG(ArenaAllocator* allocator) { 330a23d74dc2751440822960eab218be4cb8843647Nicolas Geoffray HGraph* graph = CreateGraph(allocator); 34ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain HBasicBlock* entry_block = new (allocator) HBasicBlock(graph); 35ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain entry_block->AddInstruction(new (allocator) HGoto()); 36ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain graph->AddBlock(entry_block); 37ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain graph->SetEntryBlock(entry_block); 38ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain HBasicBlock* exit_block = new (allocator) HBasicBlock(graph); 39ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain exit_block->AddInstruction(new (allocator) HExit()); 40ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain graph->AddBlock(exit_block); 41ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain graph->SetExitBlock(exit_block); 42ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain entry_block->AddSuccessor(exit_block); 43ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain return graph; 44ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain} 45ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain 46ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain 47ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillainstatic void TestCode(const uint16_t* data) { 48ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain ArenaPool pool; 49ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain ArenaAllocator allocator(&pool); 50ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain HGraph* graph = CreateCFG(&allocator, data); 51ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain ASSERT_NE(graph, nullptr); 52ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain 53ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain GraphChecker graph_checker(&allocator, graph); 54633021e6ff6b9a57a374a994e74cfd69275ce100Roland Levillain graph_checker.Run(); 55ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain ASSERT_TRUE(graph_checker.IsValid()); 56ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain} 57ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain 58ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillainstatic void TestCodeSSA(const uint16_t* data) { 59ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain ArenaPool pool; 60ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain ArenaAllocator allocator(&pool); 61ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain HGraph* graph = CreateCFG(&allocator, data); 62ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain ASSERT_NE(graph, nullptr); 63ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain 64ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain graph->BuildDominatorTree(); 65e53798a7e3267305f696bf658e418c92e63e0834Nicolas Geoffray graph->TransformToSsa(); 66ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain 67ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain SSAChecker ssa_checker(&allocator, graph); 68633021e6ff6b9a57a374a994e74cfd69275ce100Roland Levillain ssa_checker.Run(); 69ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain ASSERT_TRUE(ssa_checker.IsValid()); 70ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain} 71ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain 72ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain 73ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland LevillainTEST(GraphChecker, ReturnVoid) { 74ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain const uint16_t data[] = ZERO_REGISTER_CODE_ITEM( 75ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain Instruction::RETURN_VOID); 76ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain 77ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain TestCode(data); 78ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain} 79ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain 80ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland LevillainTEST(GraphChecker, CFG1) { 81ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain const uint16_t data[] = ZERO_REGISTER_CODE_ITEM( 82ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain Instruction::GOTO | 0x100, 83ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain Instruction::RETURN_VOID); 84ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain 85ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain TestCode(data); 86ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain} 87ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain 88ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland LevillainTEST(GraphChecker, CFG2) { 89ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain const uint16_t data[] = ONE_REGISTER_CODE_ITEM( 90ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain Instruction::CONST_4 | 0 | 0, 91ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain Instruction::IF_EQ, 3, 92ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain Instruction::GOTO | 0x100, 93ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain Instruction::RETURN_VOID); 94ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain 95ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain TestCode(data); 96ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain} 97ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain 98ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland LevillainTEST(GraphChecker, CFG3) { 99ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain const uint16_t data[] = ONE_REGISTER_CODE_ITEM( 100ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain Instruction::CONST_4 | 0 | 0, 101ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain Instruction::IF_EQ, 3, 102ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain Instruction::GOTO | 0x100, 103ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain Instruction::GOTO | 0xFF00); 104ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain 105ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain TestCode(data); 106ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain} 107ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain 108ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain// Test case with an invalid graph containing inconsistent 109ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain// predecessor/successor arcs in CFG. 110ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland LevillainTEST(GraphChecker, InconsistentPredecessorsAndSuccessors) { 111ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain ArenaPool pool; 112ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain ArenaAllocator allocator(&pool); 113ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain 114ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain HGraph* graph = CreateSimpleCFG(&allocator); 115ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain GraphChecker graph_checker(&allocator, graph); 116633021e6ff6b9a57a374a994e74cfd69275ce100Roland Levillain graph_checker.Run(); 117ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain ASSERT_TRUE(graph_checker.IsValid()); 118ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain 119ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain // Remove the entry block from the exit block's predecessors, to create an 120ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain // inconsistent successor/predecessor relation. 121ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain graph->GetExitBlock()->RemovePredecessor(graph->GetEntryBlock()); 122633021e6ff6b9a57a374a994e74cfd69275ce100Roland Levillain graph_checker.Run(); 123ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain ASSERT_FALSE(graph_checker.IsValid()); 124ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain} 125ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain 126ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain// Test case with an invalid graph containing a non-branch last 127ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain// instruction in a block. 128ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland LevillainTEST(GraphChecker, BlockEndingWithNonBranchInstruction) { 129ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain ArenaPool pool; 130ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain ArenaAllocator allocator(&pool); 131ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain 132ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain HGraph* graph = CreateSimpleCFG(&allocator); 133ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain GraphChecker graph_checker(&allocator, graph); 134633021e6ff6b9a57a374a994e74cfd69275ce100Roland Levillain graph_checker.Run(); 135ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain ASSERT_TRUE(graph_checker.IsValid()); 136ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain 137ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain // Remove the sole instruction of the exit block (composed of a 138ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain // single Exit instruction) to make it invalid (i.e. not ending by a 139ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain // branch instruction). 140ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain HBasicBlock* exit_block = graph->GetExitBlock(); 141ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain HInstruction* last_inst = exit_block->GetLastInstruction(); 142ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain exit_block->RemoveInstruction(last_inst); 143ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain 144633021e6ff6b9a57a374a994e74cfd69275ce100Roland Levillain graph_checker.Run(); 145ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain ASSERT_FALSE(graph_checker.IsValid()); 146ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain} 147ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain 148ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland LevillainTEST(SSAChecker, SSAPhi) { 149ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain // This code creates one Phi function during the conversion to SSA form. 150ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain const uint16_t data[] = ONE_REGISTER_CODE_ITEM( 151ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain Instruction::CONST_4 | 0 | 0, 152ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain Instruction::IF_EQ, 3, 153ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain Instruction::CONST_4 | 4 << 12 | 0, 154ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain Instruction::RETURN | 0 << 8); 155ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain 156ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain TestCodeSSA(data); 157ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain} 158ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain 159ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain} // namespace art 160