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