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