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