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/arena_allocator.h"
18 #include "builder.h"
19 #include "nodes.h"
20 #include "optimizing_unit_test.h"
21 #include "pretty_printer.h"
22
23 #include "gtest/gtest.h"
24
25 namespace art {
26
27 class GraphTest : public OptimizingUnitTest {
28 protected:
29 HBasicBlock* CreateIfBlock(HGraph* graph);
30 HBasicBlock* CreateGotoBlock(HGraph* graph);
31 HBasicBlock* CreateEntryBlock(HGraph* graph);
32 HBasicBlock* CreateReturnBlock(HGraph* graph);
33 HBasicBlock* CreateExitBlock(HGraph* graph);
34 };
35
CreateIfBlock(HGraph * graph)36 HBasicBlock* GraphTest::CreateIfBlock(HGraph* graph) {
37 HBasicBlock* if_block = new (GetAllocator()) HBasicBlock(graph);
38 graph->AddBlock(if_block);
39 HInstruction* instr = graph->GetIntConstant(4);
40 HInstruction* equal = new (GetAllocator()) HEqual(instr, instr);
41 if_block->AddInstruction(equal);
42 instr = new (GetAllocator()) HIf(equal);
43 if_block->AddInstruction(instr);
44 return if_block;
45 }
46
CreateGotoBlock(HGraph * graph)47 HBasicBlock* GraphTest::CreateGotoBlock(HGraph* graph) {
48 HBasicBlock* block = new (GetAllocator()) HBasicBlock(graph);
49 graph->AddBlock(block);
50 HInstruction* got = new (GetAllocator()) HGoto();
51 block->AddInstruction(got);
52 return block;
53 }
54
CreateEntryBlock(HGraph * graph)55 HBasicBlock* GraphTest::CreateEntryBlock(HGraph* graph) {
56 HBasicBlock* block = CreateGotoBlock(graph);
57 graph->SetEntryBlock(block);
58 return block;
59 }
60
CreateReturnBlock(HGraph * graph)61 HBasicBlock* GraphTest::CreateReturnBlock(HGraph* graph) {
62 HBasicBlock* block = new (GetAllocator()) HBasicBlock(graph);
63 graph->AddBlock(block);
64 HInstruction* return_instr = new (GetAllocator()) HReturnVoid();
65 block->AddInstruction(return_instr);
66 return block;
67 }
68
CreateExitBlock(HGraph * graph)69 HBasicBlock* GraphTest::CreateExitBlock(HGraph* graph) {
70 HBasicBlock* block = new (GetAllocator()) HBasicBlock(graph);
71 graph->AddBlock(block);
72 HInstruction* exit_instr = new (GetAllocator()) HExit();
73 block->AddInstruction(exit_instr);
74 return block;
75 }
76
77
78 // Test that the successors of an if block stay consistent after a SimplifyCFG.
79 // This test sets the false block to be the return block.
TEST_F(GraphTest,IfSuccessorSimpleJoinBlock1)80 TEST_F(GraphTest, IfSuccessorSimpleJoinBlock1) {
81 HGraph* graph = CreateGraph();
82 HBasicBlock* entry_block = CreateEntryBlock(graph);
83 HBasicBlock* if_block = CreateIfBlock(graph);
84 HBasicBlock* if_true = CreateGotoBlock(graph);
85 HBasicBlock* return_block = CreateReturnBlock(graph);
86 HBasicBlock* exit_block = CreateExitBlock(graph);
87
88 entry_block->AddSuccessor(if_block);
89 if_block->AddSuccessor(if_true);
90 if_true->AddSuccessor(return_block);
91 if_block->AddSuccessor(return_block);
92 return_block->AddSuccessor(exit_block);
93
94 ASSERT_EQ(if_block->GetLastInstruction()->AsIf()->IfTrueSuccessor(), if_true);
95 ASSERT_EQ(if_block->GetLastInstruction()->AsIf()->IfFalseSuccessor(), return_block);
96
97 graph->SimplifyCFG();
98
99 // Ensure we still have the same if true block.
100 ASSERT_EQ(if_block->GetLastInstruction()->AsIf()->IfTrueSuccessor(), if_true);
101
102 // Ensure the critical edge has been removed.
103 HBasicBlock* false_block = if_block->GetLastInstruction()->AsIf()->IfFalseSuccessor();
104 ASSERT_NE(false_block, return_block);
105
106 // Ensure the new block branches to the join block.
107 ASSERT_EQ(false_block->GetSuccessors()[0], return_block);
108 }
109
110 // Test that the successors of an if block stay consistent after a SimplifyCFG.
111 // This test sets the true block to be the return block.
TEST_F(GraphTest,IfSuccessorSimpleJoinBlock2)112 TEST_F(GraphTest, IfSuccessorSimpleJoinBlock2) {
113 HGraph* graph = CreateGraph();
114 HBasicBlock* entry_block = CreateEntryBlock(graph);
115 HBasicBlock* if_block = CreateIfBlock(graph);
116 HBasicBlock* if_false = CreateGotoBlock(graph);
117 HBasicBlock* return_block = CreateReturnBlock(graph);
118 HBasicBlock* exit_block = CreateExitBlock(graph);
119
120 entry_block->AddSuccessor(if_block);
121 if_block->AddSuccessor(return_block);
122 if_false->AddSuccessor(return_block);
123 if_block->AddSuccessor(if_false);
124 return_block->AddSuccessor(exit_block);
125
126 ASSERT_EQ(if_block->GetLastInstruction()->AsIf()->IfTrueSuccessor(), return_block);
127 ASSERT_EQ(if_block->GetLastInstruction()->AsIf()->IfFalseSuccessor(), if_false);
128
129 graph->SimplifyCFG();
130
131 // Ensure we still have the same if true block.
132 ASSERT_EQ(if_block->GetLastInstruction()->AsIf()->IfFalseSuccessor(), if_false);
133
134 // Ensure the critical edge has been removed.
135 HBasicBlock* true_block = if_block->GetLastInstruction()->AsIf()->IfTrueSuccessor();
136 ASSERT_NE(true_block, return_block);
137
138 // Ensure the new block branches to the join block.
139 ASSERT_EQ(true_block->GetSuccessors()[0], return_block);
140 }
141
142 // Test that the successors of an if block stay consistent after a SimplifyCFG.
143 // This test sets the true block to be the loop header.
TEST_F(GraphTest,IfSuccessorMultipleBackEdges1)144 TEST_F(GraphTest, IfSuccessorMultipleBackEdges1) {
145 HGraph* graph = CreateGraph();
146 HBasicBlock* entry_block = CreateEntryBlock(graph);
147 HBasicBlock* if_block = CreateIfBlock(graph);
148 HBasicBlock* return_block = CreateReturnBlock(graph);
149 HBasicBlock* exit_block = CreateExitBlock(graph);
150
151 entry_block->AddSuccessor(if_block);
152 if_block->AddSuccessor(if_block);
153 if_block->AddSuccessor(return_block);
154 return_block->AddSuccessor(exit_block);
155
156 ASSERT_EQ(if_block->GetLastInstruction()->AsIf()->IfTrueSuccessor(), if_block);
157 ASSERT_EQ(if_block->GetLastInstruction()->AsIf()->IfFalseSuccessor(), return_block);
158
159 graph->BuildDominatorTree();
160
161 // Ensure we still have the same if false block.
162 ASSERT_EQ(if_block->GetLastInstruction()->AsIf()->IfFalseSuccessor(), return_block);
163
164 // Ensure there is only one back edge.
165 ASSERT_EQ(if_block->GetPredecessors().size(), 2u);
166 ASSERT_EQ(if_block->GetPredecessors()[0], entry_block->GetSingleSuccessor());
167 ASSERT_NE(if_block->GetPredecessors()[1], if_block);
168
169 // Ensure the new block is the back edge.
170 ASSERT_EQ(if_block->GetPredecessors()[1],
171 if_block->GetLastInstruction()->AsIf()->IfTrueSuccessor());
172 }
173
174 // Test that the successors of an if block stay consistent after a SimplifyCFG.
175 // This test sets the false block to be the loop header.
TEST_F(GraphTest,IfSuccessorMultipleBackEdges2)176 TEST_F(GraphTest, IfSuccessorMultipleBackEdges2) {
177 HGraph* graph = CreateGraph();
178 HBasicBlock* entry_block = CreateEntryBlock(graph);
179 HBasicBlock* if_block = CreateIfBlock(graph);
180 HBasicBlock* return_block = CreateReturnBlock(graph);
181 HBasicBlock* exit_block = CreateExitBlock(graph);
182
183 entry_block->AddSuccessor(if_block);
184 if_block->AddSuccessor(return_block);
185 if_block->AddSuccessor(if_block);
186 return_block->AddSuccessor(exit_block);
187
188 ASSERT_EQ(if_block->GetLastInstruction()->AsIf()->IfTrueSuccessor(), return_block);
189 ASSERT_EQ(if_block->GetLastInstruction()->AsIf()->IfFalseSuccessor(), if_block);
190
191 graph->BuildDominatorTree();
192
193 // Ensure we still have the same if true block.
194 ASSERT_EQ(if_block->GetLastInstruction()->AsIf()->IfTrueSuccessor(), return_block);
195
196 // Ensure there is only one back edge.
197 ASSERT_EQ(if_block->GetPredecessors().size(), 2u);
198 ASSERT_EQ(if_block->GetPredecessors()[0], entry_block->GetSingleSuccessor());
199 ASSERT_NE(if_block->GetPredecessors()[1], if_block);
200
201 // Ensure the new block is the back edge.
202 ASSERT_EQ(if_block->GetPredecessors()[1],
203 if_block->GetLastInstruction()->AsIf()->IfFalseSuccessor());
204 }
205
206 // Test that the successors of an if block stay consistent after a SimplifyCFG.
207 // This test sets the true block to be a loop header with multiple pre headers.
TEST_F(GraphTest,IfSuccessorMultiplePreHeaders1)208 TEST_F(GraphTest, IfSuccessorMultiplePreHeaders1) {
209 HGraph* graph = CreateGraph();
210 HBasicBlock* entry_block = CreateEntryBlock(graph);
211 HBasicBlock* first_if_block = CreateIfBlock(graph);
212 HBasicBlock* if_block = CreateIfBlock(graph);
213 HBasicBlock* loop_block = CreateGotoBlock(graph);
214 HBasicBlock* return_block = CreateReturnBlock(graph);
215
216 entry_block->AddSuccessor(first_if_block);
217 first_if_block->AddSuccessor(if_block);
218 first_if_block->AddSuccessor(loop_block);
219 loop_block->AddSuccessor(loop_block);
220 if_block->AddSuccessor(loop_block);
221 if_block->AddSuccessor(return_block);
222
223
224 ASSERT_EQ(if_block->GetLastInstruction()->AsIf()->IfTrueSuccessor(), loop_block);
225 ASSERT_EQ(if_block->GetLastInstruction()->AsIf()->IfFalseSuccessor(), return_block);
226
227 graph->BuildDominatorTree();
228
229 HIf* if_instr = if_block->GetLastInstruction()->AsIf();
230 // Ensure we still have the same if false block.
231 ASSERT_EQ(if_instr->IfFalseSuccessor(), return_block);
232
233 // Ensure there is only one pre header..
234 ASSERT_EQ(loop_block->GetPredecessors().size(), 2u);
235
236 // Ensure the new block is the successor of the true block.
237 ASSERT_EQ(if_instr->IfTrueSuccessor()->GetSuccessors().size(), 1u);
238 ASSERT_EQ(if_instr->IfTrueSuccessor()->GetSuccessors()[0],
239 loop_block->GetLoopInformation()->GetPreHeader());
240 }
241
242 // Test that the successors of an if block stay consistent after a SimplifyCFG.
243 // This test sets the false block to be a loop header with multiple pre headers.
TEST_F(GraphTest,IfSuccessorMultiplePreHeaders2)244 TEST_F(GraphTest, IfSuccessorMultiplePreHeaders2) {
245 HGraph* graph = CreateGraph();
246 HBasicBlock* entry_block = CreateEntryBlock(graph);
247 HBasicBlock* first_if_block = CreateIfBlock(graph);
248 HBasicBlock* if_block = CreateIfBlock(graph);
249 HBasicBlock* loop_block = CreateGotoBlock(graph);
250 HBasicBlock* return_block = CreateReturnBlock(graph);
251
252 entry_block->AddSuccessor(first_if_block);
253 first_if_block->AddSuccessor(if_block);
254 first_if_block->AddSuccessor(loop_block);
255 loop_block->AddSuccessor(loop_block);
256 if_block->AddSuccessor(return_block);
257 if_block->AddSuccessor(loop_block);
258
259 ASSERT_EQ(if_block->GetLastInstruction()->AsIf()->IfTrueSuccessor(), return_block);
260 ASSERT_EQ(if_block->GetLastInstruction()->AsIf()->IfFalseSuccessor(), loop_block);
261
262 graph->BuildDominatorTree();
263
264 HIf* if_instr = if_block->GetLastInstruction()->AsIf();
265 // Ensure we still have the same if true block.
266 ASSERT_EQ(if_instr->IfTrueSuccessor(), return_block);
267
268 // Ensure there is only one pre header..
269 ASSERT_EQ(loop_block->GetPredecessors().size(), 2u);
270
271 // Ensure the new block is the successor of the false block.
272 ASSERT_EQ(if_instr->IfFalseSuccessor()->GetSuccessors().size(), 1u);
273 ASSERT_EQ(if_instr->IfFalseSuccessor()->GetSuccessors()[0],
274 loop_block->GetLoopInformation()->GetPreHeader());
275 }
276
TEST_F(GraphTest,InsertInstructionBefore)277 TEST_F(GraphTest, InsertInstructionBefore) {
278 HGraph* graph = CreateGraph();
279 HBasicBlock* block = CreateGotoBlock(graph);
280 HInstruction* got = block->GetLastInstruction();
281 ASSERT_TRUE(got->IsControlFlow());
282
283 // Test at the beginning of the block.
284 HInstruction* first_instruction = new (GetAllocator()) HIntConstant(4);
285 block->InsertInstructionBefore(first_instruction, got);
286
287 ASSERT_NE(first_instruction->GetId(), -1);
288 ASSERT_EQ(first_instruction->GetBlock(), block);
289 ASSERT_EQ(block->GetFirstInstruction(), first_instruction);
290 ASSERT_EQ(block->GetLastInstruction(), got);
291 ASSERT_EQ(first_instruction->GetNext(), got);
292 ASSERT_EQ(first_instruction->GetPrevious(), nullptr);
293 ASSERT_EQ(got->GetNext(), nullptr);
294 ASSERT_EQ(got->GetPrevious(), first_instruction);
295
296 // Test in the middle of the block.
297 HInstruction* second_instruction = new (GetAllocator()) HIntConstant(4);
298 block->InsertInstructionBefore(second_instruction, got);
299
300 ASSERT_NE(second_instruction->GetId(), -1);
301 ASSERT_EQ(second_instruction->GetBlock(), block);
302 ASSERT_EQ(block->GetFirstInstruction(), first_instruction);
303 ASSERT_EQ(block->GetLastInstruction(), got);
304 ASSERT_EQ(first_instruction->GetNext(), second_instruction);
305 ASSERT_EQ(first_instruction->GetPrevious(), nullptr);
306 ASSERT_EQ(second_instruction->GetNext(), got);
307 ASSERT_EQ(second_instruction->GetPrevious(), first_instruction);
308 ASSERT_EQ(got->GetNext(), nullptr);
309 ASSERT_EQ(got->GetPrevious(), second_instruction);
310 }
311
312 } // namespace art
313