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/stringprintf.h"
18 #include "builder.h"
19 #include "nodes.h"
20 #include "optimizing_unit_test.h"
21 #include "pretty_printer.h"
22 #include "utils/arena_allocator.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 = new (allocator) HIntConstant(4);
32   if_block->AddInstruction(instr);
33   HInstruction* equal = new (allocator) HEqual(instr, instr);
34   if_block->AddInstruction(equal);
35   instr = new (allocator) HIf(equal);
36   if_block->AddInstruction(instr);
37   return if_block;
38 }
39 
createGotoBlock(HGraph * graph,ArenaAllocator * allocator)40 static HBasicBlock* createGotoBlock(HGraph* graph, ArenaAllocator* allocator) {
41   HBasicBlock* block = new (allocator) HBasicBlock(graph);
42   graph->AddBlock(block);
43   HInstruction* got = new (allocator) HGoto();
44   block->AddInstruction(got);
45   return block;
46 }
47 
createReturnBlock(HGraph * graph,ArenaAllocator * allocator)48 static HBasicBlock* createReturnBlock(HGraph* graph, ArenaAllocator* allocator) {
49   HBasicBlock* block = new (allocator) HBasicBlock(graph);
50   graph->AddBlock(block);
51   HInstruction* return_instr = new (allocator) HReturnVoid();
52   block->AddInstruction(return_instr);
53   return block;
54 }
55 
createExitBlock(HGraph * graph,ArenaAllocator * allocator)56 static HBasicBlock* createExitBlock(HGraph* graph, ArenaAllocator* allocator) {
57   HBasicBlock* block = new (allocator) HBasicBlock(graph);
58   graph->AddBlock(block);
59   HInstruction* exit_instr = new (allocator) HExit();
60   block->AddInstruction(exit_instr);
61   return block;
62 }
63 
64 
65 // Test that the successors of an if block stay consistent after a SimplifyCFG.
66 // This test sets the false block to be the return block.
TEST(GraphTest,IfSuccessorSimpleJoinBlock1)67 TEST(GraphTest, IfSuccessorSimpleJoinBlock1) {
68   ArenaPool pool;
69   ArenaAllocator allocator(&pool);
70 
71   HGraph* graph = new (&allocator) HGraph(&allocator);
72   HBasicBlock* entry_block = createGotoBlock(graph, &allocator);
73   HBasicBlock* if_block = createIfBlock(graph, &allocator);
74   HBasicBlock* if_true = createGotoBlock(graph, &allocator);
75   HBasicBlock* return_block = createReturnBlock(graph, &allocator);
76   HBasicBlock* exit_block = createExitBlock(graph, &allocator);
77 
78   entry_block->AddSuccessor(if_block);
79   if_block->AddSuccessor(if_true);
80   if_true->AddSuccessor(return_block);
81   if_block->AddSuccessor(return_block);
82   return_block->AddSuccessor(exit_block);
83 
84   ASSERT_EQ(if_block->GetLastInstruction()->AsIf()->IfTrueSuccessor(), if_true);
85   ASSERT_EQ(if_block->GetLastInstruction()->AsIf()->IfFalseSuccessor(), return_block);
86 
87   graph->SimplifyCFG();
88 
89   // Ensure we still have the same if true block.
90   ASSERT_EQ(if_block->GetLastInstruction()->AsIf()->IfTrueSuccessor(), if_true);
91 
92   // Ensure the critical edge has been removed.
93   HBasicBlock* false_block = if_block->GetLastInstruction()->AsIf()->IfFalseSuccessor();
94   ASSERT_NE(false_block, return_block);
95 
96   // Ensure the new block branches to the join block.
97   ASSERT_EQ(false_block->GetSuccessors().Get(0), return_block);
98 }
99 
100 // Test that the successors of an if block stay consistent after a SimplifyCFG.
101 // This test sets the true block to be the return block.
TEST(GraphTest,IfSuccessorSimpleJoinBlock2)102 TEST(GraphTest, IfSuccessorSimpleJoinBlock2) {
103   ArenaPool pool;
104   ArenaAllocator allocator(&pool);
105 
106   HGraph* graph = new (&allocator) HGraph(&allocator);
107   HBasicBlock* entry_block = createGotoBlock(graph, &allocator);
108   HBasicBlock* if_block = createIfBlock(graph, &allocator);
109   HBasicBlock* if_false = createGotoBlock(graph, &allocator);
110   HBasicBlock* return_block = createReturnBlock(graph, &allocator);
111   HBasicBlock* exit_block = createExitBlock(graph, &allocator);
112 
113   entry_block->AddSuccessor(if_block);
114   if_block->AddSuccessor(return_block);
115   if_false->AddSuccessor(return_block);
116   if_block->AddSuccessor(if_false);
117   return_block->AddSuccessor(exit_block);
118 
119   ASSERT_EQ(if_block->GetLastInstruction()->AsIf()->IfTrueSuccessor(), return_block);
120   ASSERT_EQ(if_block->GetLastInstruction()->AsIf()->IfFalseSuccessor(), if_false);
121 
122   graph->SimplifyCFG();
123 
124   // Ensure we still have the same if true block.
125   ASSERT_EQ(if_block->GetLastInstruction()->AsIf()->IfFalseSuccessor(), if_false);
126 
127   // Ensure the critical edge has been removed.
128   HBasicBlock* true_block = if_block->GetLastInstruction()->AsIf()->IfTrueSuccessor();
129   ASSERT_NE(true_block, return_block);
130 
131   // Ensure the new block branches to the join block.
132   ASSERT_EQ(true_block->GetSuccessors().Get(0), return_block);
133 }
134 
135 // Test that the successors of an if block stay consistent after a SimplifyCFG.
136 // This test sets the true block to be the loop header.
TEST(GraphTest,IfSuccessorMultipleBackEdges1)137 TEST(GraphTest, IfSuccessorMultipleBackEdges1) {
138   ArenaPool pool;
139   ArenaAllocator allocator(&pool);
140 
141   HGraph* graph = new (&allocator) HGraph(&allocator);
142   HBasicBlock* entry_block = createGotoBlock(graph, &allocator);
143   HBasicBlock* if_block = createIfBlock(graph, &allocator);
144   HBasicBlock* return_block = createReturnBlock(graph, &allocator);
145   HBasicBlock* exit_block = createExitBlock(graph, &allocator);
146 
147   graph->SetEntryBlock(entry_block);
148   entry_block->AddSuccessor(if_block);
149   if_block->AddSuccessor(if_block);
150   if_block->AddSuccessor(return_block);
151   return_block->AddSuccessor(exit_block);
152 
153   ASSERT_EQ(if_block->GetLastInstruction()->AsIf()->IfTrueSuccessor(), if_block);
154   ASSERT_EQ(if_block->GetLastInstruction()->AsIf()->IfFalseSuccessor(), return_block);
155 
156   graph->BuildDominatorTree();
157 
158   // Ensure we still have the same if false block.
159   ASSERT_EQ(if_block->GetLastInstruction()->AsIf()->IfFalseSuccessor(), return_block);
160 
161   // Ensure there is only one back edge.
162   ASSERT_EQ(if_block->GetPredecessors().Size(), 2u);
163   ASSERT_EQ(if_block->GetPredecessors().Get(0), entry_block);
164   ASSERT_NE(if_block->GetPredecessors().Get(1), if_block);
165 
166   // Ensure the new block is the back edge.
167   ASSERT_EQ(if_block->GetPredecessors().Get(1),
168             if_block->GetLastInstruction()->AsIf()->IfTrueSuccessor());
169 }
170 
171 // Test that the successors of an if block stay consistent after a SimplifyCFG.
172 // This test sets the false block to be the loop header.
TEST(GraphTest,IfSuccessorMultipleBackEdges2)173 TEST(GraphTest, IfSuccessorMultipleBackEdges2) {
174   ArenaPool pool;
175   ArenaAllocator allocator(&pool);
176 
177   HGraph* graph = new (&allocator) HGraph(&allocator);
178   HBasicBlock* entry_block = createGotoBlock(graph, &allocator);
179   HBasicBlock* if_block = createIfBlock(graph, &allocator);
180   HBasicBlock* return_block = createReturnBlock(graph, &allocator);
181   HBasicBlock* exit_block = createExitBlock(graph, &allocator);
182 
183   graph->SetEntryBlock(entry_block);
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().Get(0), entry_block);
200   ASSERT_NE(if_block->GetPredecessors().Get(1), if_block);
201 
202   // Ensure the new block is the back edge.
203   ASSERT_EQ(if_block->GetPredecessors().Get(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(GraphTest,IfSuccessorMultiplePreHeaders1)209 TEST(GraphTest, IfSuccessorMultiplePreHeaders1) {
210   ArenaPool pool;
211   ArenaAllocator allocator(&pool);
212 
213   HGraph* graph = new (&allocator) HGraph(&allocator);
214   HBasicBlock* entry_block = createGotoBlock(graph, &allocator);
215   HBasicBlock* first_if_block = createIfBlock(graph, &allocator);
216   HBasicBlock* if_block = createIfBlock(graph, &allocator);
217   HBasicBlock* loop_block = createGotoBlock(graph, &allocator);
218   HBasicBlock* return_block = createReturnBlock(graph, &allocator);
219 
220   graph->SetEntryBlock(entry_block);
221   entry_block->AddSuccessor(first_if_block);
222   first_if_block->AddSuccessor(if_block);
223   first_if_block->AddSuccessor(loop_block);
224   loop_block->AddSuccessor(loop_block);
225   if_block->AddSuccessor(loop_block);
226   if_block->AddSuccessor(return_block);
227 
228 
229   ASSERT_EQ(if_block->GetLastInstruction()->AsIf()->IfTrueSuccessor(), loop_block);
230   ASSERT_EQ(if_block->GetLastInstruction()->AsIf()->IfFalseSuccessor(), return_block);
231 
232   graph->BuildDominatorTree();
233 
234   HIf* if_instr = if_block->GetLastInstruction()->AsIf();
235   // Ensure we still have the same if false block.
236   ASSERT_EQ(if_instr->IfFalseSuccessor(), return_block);
237 
238   // Ensure there is only one pre header..
239   ASSERT_EQ(loop_block->GetPredecessors().Size(), 2u);
240 
241   // Ensure the new block is the successor of the true block.
242   ASSERT_EQ(if_instr->IfTrueSuccessor()->GetSuccessors().Size(), 1u);
243   ASSERT_EQ(if_instr->IfTrueSuccessor()->GetSuccessors().Get(0),
244             loop_block->GetLoopInformation()->GetPreHeader());
245 }
246 
247 // Test that the successors of an if block stay consistent after a SimplifyCFG.
248 // This test sets the false block to be a loop header with multiple pre headers.
TEST(GraphTest,IfSuccessorMultiplePreHeaders2)249 TEST(GraphTest, IfSuccessorMultiplePreHeaders2) {
250   ArenaPool pool;
251   ArenaAllocator allocator(&pool);
252 
253   HGraph* graph = new (&allocator) HGraph(&allocator);
254   HBasicBlock* entry_block = createGotoBlock(graph, &allocator);
255   HBasicBlock* first_if_block = createIfBlock(graph, &allocator);
256   HBasicBlock* if_block = createIfBlock(graph, &allocator);
257   HBasicBlock* loop_block = createGotoBlock(graph, &allocator);
258   HBasicBlock* return_block = createReturnBlock(graph, &allocator);
259 
260   graph->SetEntryBlock(entry_block);
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().Get(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 = new (&allocator) HGraph(&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