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
22 namespace 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 */
CreateSimpleCFG(ArenaAllocator * allocator)32 HGraph* 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
TestCode(const uint16_t * data)47 static 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
TestCodeSSA(const uint16_t * data)58 static 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
TEST(GraphChecker,ReturnVoid)73 TEST(GraphChecker, ReturnVoid) {
74 const uint16_t data[] = ZERO_REGISTER_CODE_ITEM(
75 Instruction::RETURN_VOID);
76
77 TestCode(data);
78 }
79
TEST(GraphChecker,CFG1)80 TEST(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
TEST(GraphChecker,CFG2)88 TEST(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
TEST(GraphChecker,CFG3)98 TEST(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.
TEST(GraphChecker,InconsistentPredecessorsAndSuccessors)110 TEST(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.
TEST(GraphChecker,BlockEndingWithNonBranchInstruction)128 TEST(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
TEST(SSAChecker,SSAPhi)148 TEST(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