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