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