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