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