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