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