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