blob: 50398b47904fd6288c175e7f69a514a3e3080ce0 [file] [log] [blame]
Nicolas Geoffrayec7e4722014-06-06 11:24:33 +01001/*
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
Mathieu Chartierb666f482015-02-18 14:33:14 -080017#include "base/arena_allocator.h"
Nicolas Geoffrayec7e4722014-06-06 11:24:33 +010018#include "base/stringprintf.h"
19#include "builder.h"
20#include "nodes.h"
21#include "optimizing_unit_test.h"
22#include "pretty_printer.h"
Nicolas Geoffrayec7e4722014-06-06 11:24:33 +010023
24#include "gtest/gtest.h"
25
26namespace art {
27
28static HBasicBlock* createIfBlock(HGraph* graph, ArenaAllocator* allocator) {
29 HBasicBlock* if_block = new (allocator) HBasicBlock(graph);
30 graph->AddBlock(if_block);
David Brazdil8d5b8b22015-03-24 10:51:52 +000031 HInstruction* instr = graph->GetIntConstant(4);
Dave Allison20dfc792014-06-16 20:44:29 -070032 HInstruction* equal = new (allocator) HEqual(instr, instr);
33 if_block->AddInstruction(equal);
34 instr = new (allocator) HIf(equal);
Nicolas Geoffrayec7e4722014-06-06 11:24:33 +010035 if_block->AddInstruction(instr);
36 return if_block;
37}
38
39static 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
David Brazdil8d5b8b22015-03-24 10:51:52 +000047static HBasicBlock* createEntryBlock(HGraph* graph, ArenaAllocator* allocator) {
48 HBasicBlock* block = createGotoBlock(graph, allocator);
49 graph->SetEntryBlock(block);
50 return block;
51}
52
Nicolas Geoffrayec7e4722014-06-06 11:24:33 +010053static 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
61static 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.
72TEST(GraphTest, IfSuccessorSimpleJoinBlock1) {
73 ArenaPool pool;
74 ArenaAllocator allocator(&pool);
75
76 HGraph* graph = new (&allocator) HGraph(&allocator);
David Brazdil8d5b8b22015-03-24 10:51:52 +000077 HBasicBlock* entry_block = createEntryBlock(graph, &allocator);
Nicolas Geoffrayec7e4722014-06-06 11:24:33 +010078 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.
107TEST(GraphTest, IfSuccessorSimpleJoinBlock2) {
108 ArenaPool pool;
109 ArenaAllocator allocator(&pool);
110
111 HGraph* graph = new (&allocator) HGraph(&allocator);
David Brazdil8d5b8b22015-03-24 10:51:52 +0000112 HBasicBlock* entry_block = createEntryBlock(graph, &allocator);
Nicolas Geoffrayec7e4722014-06-06 11:24:33 +0100113 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.
142TEST(GraphTest, IfSuccessorMultipleBackEdges1) {
143 ArenaPool pool;
144 ArenaAllocator allocator(&pool);
145
146 HGraph* graph = new (&allocator) HGraph(&allocator);
David Brazdil8d5b8b22015-03-24 10:51:52 +0000147 HBasicBlock* entry_block = createEntryBlock(graph, &allocator);
Nicolas Geoffrayec7e4722014-06-06 11:24:33 +0100148 HBasicBlock* if_block = createIfBlock(graph, &allocator);
149 HBasicBlock* return_block = createReturnBlock(graph, &allocator);
150 HBasicBlock* exit_block = createExitBlock(graph, &allocator);
151
Nicolas Geoffrayec7e4722014-06-06 11:24:33 +0100152 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.
177TEST(GraphTest, IfSuccessorMultipleBackEdges2) {
178 ArenaPool pool;
179 ArenaAllocator allocator(&pool);
180
181 HGraph* graph = new (&allocator) HGraph(&allocator);
David Brazdil8d5b8b22015-03-24 10:51:52 +0000182 HBasicBlock* entry_block = createEntryBlock(graph, &allocator);
Nicolas Geoffrayec7e4722014-06-06 11:24:33 +0100183 HBasicBlock* if_block = createIfBlock(graph, &allocator);
184 HBasicBlock* return_block = createReturnBlock(graph, &allocator);
185 HBasicBlock* exit_block = createExitBlock(graph, &allocator);
186
Nicolas Geoffrayec7e4722014-06-06 11:24:33 +0100187 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.
212TEST(GraphTest, IfSuccessorMultiplePreHeaders1) {
213 ArenaPool pool;
214 ArenaAllocator allocator(&pool);
215
216 HGraph* graph = new (&allocator) HGraph(&allocator);
David Brazdil8d5b8b22015-03-24 10:51:52 +0000217 HBasicBlock* entry_block = createEntryBlock(graph, &allocator);
Nicolas Geoffrayec7e4722014-06-06 11:24:33 +0100218 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
Nicolas Geoffrayec7e4722014-06-06 11:24:33 +0100223 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.
251TEST(GraphTest, IfSuccessorMultiplePreHeaders2) {
252 ArenaPool pool;
253 ArenaAllocator allocator(&pool);
254
255 HGraph* graph = new (&allocator) HGraph(&allocator);
David Brazdil8d5b8b22015-03-24 10:51:52 +0000256 HBasicBlock* entry_block = createEntryBlock(graph, &allocator);
Nicolas Geoffrayec7e4722014-06-06 11:24:33 +0100257 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
Nicolas Geoffrayec7e4722014-06-06 11:24:33 +0100262 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
287TEST(GraphTest, InsertInstructionBefore) {
288 ArenaPool pool;
289 ArenaAllocator allocator(&pool);
290
291 HGraph* graph = new (&allocator) HGraph(&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