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
26namespace art {
27
28static 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
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
47static HBasicBlock* createEntryBlock(HGraph* graph, ArenaAllocator* allocator) {
48  HBasicBlock* block = createGotoBlock(graph, allocator);
49  graph->SetEntryBlock(block);
50  return block;
51}
52
53static 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 = 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()[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 = 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()[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 = 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()[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.
177TEST(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()[0], entry_block->GetSingleSuccessor());
203  ASSERT_NE(if_block->GetPredecessors()[1], if_block);
204
205  // Ensure the new block is the back edge.
206  ASSERT_EQ(if_block->GetPredecessors()[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 = 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()[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 = 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()[0],
284            loop_block->GetLoopInformation()->GetPreHeader());
285}
286
287TEST(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