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