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 "gvn.h"
18
19 #include "base/arena_allocator.h"
20 #include "base/macros.h"
21 #include "builder.h"
22 #include "nodes.h"
23 #include "optimizing_unit_test.h"
24 #include "side_effects_analysis.h"
25
26 namespace art HIDDEN {
27
28 class GVNTest : public OptimizingUnitTest {};
29
TEST_F(GVNTest,LocalFieldElimination)30 TEST_F(GVNTest, LocalFieldElimination) {
31 HGraph* graph = CreateGraph();
32 HBasicBlock* entry = new (GetAllocator()) HBasicBlock(graph);
33 graph->AddBlock(entry);
34 graph->SetEntryBlock(entry);
35 HInstruction* parameter = new (GetAllocator()) HParameterValue(graph->GetDexFile(),
36 dex::TypeIndex(0),
37 0,
38 DataType::Type::kReference);
39 entry->AddInstruction(parameter);
40
41 HBasicBlock* block = new (GetAllocator()) HBasicBlock(graph);
42 graph->AddBlock(block);
43 entry->AddSuccessor(block);
44
45 block->AddInstruction(new (GetAllocator()) HInstanceFieldGet(parameter,
46 nullptr,
47 DataType::Type::kReference,
48 MemberOffset(42),
49 false,
50 kUnknownFieldIndex,
51 kUnknownClassDefIndex,
52 graph->GetDexFile(),
53 0));
54 block->AddInstruction(new (GetAllocator()) HInstanceFieldGet(parameter,
55 nullptr,
56 DataType::Type::kReference,
57 MemberOffset(42),
58 false,
59 kUnknownFieldIndex,
60 kUnknownClassDefIndex,
61 graph->GetDexFile(),
62 0));
63 HInstruction* to_remove = block->GetLastInstruction();
64 block->AddInstruction(new (GetAllocator()) HInstanceFieldGet(parameter,
65 nullptr,
66 DataType::Type::kReference,
67 MemberOffset(43),
68 false,
69 kUnknownFieldIndex,
70 kUnknownClassDefIndex,
71 graph->GetDexFile(),
72 0));
73 HInstruction* different_offset = block->GetLastInstruction();
74 // Kill the value.
75 block->AddInstruction(new (GetAllocator()) HInstanceFieldSet(parameter,
76 parameter,
77 nullptr,
78 DataType::Type::kReference,
79 MemberOffset(42),
80 false,
81 kUnknownFieldIndex,
82 kUnknownClassDefIndex,
83 graph->GetDexFile(),
84 0));
85 block->AddInstruction(new (GetAllocator()) HInstanceFieldGet(parameter,
86 nullptr,
87 DataType::Type::kReference,
88 MemberOffset(42),
89 false,
90 kUnknownFieldIndex,
91 kUnknownClassDefIndex,
92 graph->GetDexFile(),
93 0));
94 HInstruction* use_after_kill = block->GetLastInstruction();
95 block->AddInstruction(new (GetAllocator()) HExit());
96
97 ASSERT_EQ(to_remove->GetBlock(), block);
98 ASSERT_EQ(different_offset->GetBlock(), block);
99 ASSERT_EQ(use_after_kill->GetBlock(), block);
100
101 graph->BuildDominatorTree();
102 SideEffectsAnalysis side_effects(graph);
103 side_effects.Run();
104 GVNOptimization(graph, side_effects).Run();
105
106 ASSERT_TRUE(to_remove->GetBlock() == nullptr);
107 ASSERT_EQ(different_offset->GetBlock(), block);
108 ASSERT_EQ(use_after_kill->GetBlock(), block);
109 }
110
TEST_F(GVNTest,GlobalFieldElimination)111 TEST_F(GVNTest, GlobalFieldElimination) {
112 HGraph* graph = CreateGraph();
113 HBasicBlock* entry = new (GetAllocator()) HBasicBlock(graph);
114 graph->AddBlock(entry);
115 graph->SetEntryBlock(entry);
116 HInstruction* parameter = new (GetAllocator()) HParameterValue(graph->GetDexFile(),
117 dex::TypeIndex(0),
118 0,
119 DataType::Type::kReference);
120 entry->AddInstruction(parameter);
121
122 HBasicBlock* block = new (GetAllocator()) HBasicBlock(graph);
123 graph->AddBlock(block);
124 entry->AddSuccessor(block);
125 block->AddInstruction(new (GetAllocator()) HInstanceFieldGet(parameter,
126 nullptr,
127 DataType::Type::kBool,
128 MemberOffset(42),
129 false,
130 kUnknownFieldIndex,
131 kUnknownClassDefIndex,
132 graph->GetDexFile(),
133 0));
134
135 block->AddInstruction(new (GetAllocator()) HIf(block->GetLastInstruction()));
136 HBasicBlock* then = new (GetAllocator()) HBasicBlock(graph);
137 HBasicBlock* else_ = new (GetAllocator()) HBasicBlock(graph);
138 HBasicBlock* join = new (GetAllocator()) HBasicBlock(graph);
139 graph->AddBlock(then);
140 graph->AddBlock(else_);
141 graph->AddBlock(join);
142
143 block->AddSuccessor(then);
144 block->AddSuccessor(else_);
145 then->AddSuccessor(join);
146 else_->AddSuccessor(join);
147
148 then->AddInstruction(new (GetAllocator()) HInstanceFieldGet(parameter,
149 nullptr,
150 DataType::Type::kBool,
151 MemberOffset(42),
152 false,
153 kUnknownFieldIndex,
154 kUnknownClassDefIndex,
155 graph->GetDexFile(),
156 0));
157 then->AddInstruction(new (GetAllocator()) HGoto());
158 else_->AddInstruction(new (GetAllocator()) HInstanceFieldGet(parameter,
159 nullptr,
160 DataType::Type::kBool,
161 MemberOffset(42),
162 false,
163 kUnknownFieldIndex,
164 kUnknownClassDefIndex,
165 graph->GetDexFile(),
166 0));
167 else_->AddInstruction(new (GetAllocator()) HGoto());
168 join->AddInstruction(new (GetAllocator()) HInstanceFieldGet(parameter,
169 nullptr,
170 DataType::Type::kBool,
171 MemberOffset(42),
172 false,
173 kUnknownFieldIndex,
174 kUnknownClassDefIndex,
175 graph->GetDexFile(),
176 0));
177 join->AddInstruction(new (GetAllocator()) HExit());
178
179 graph->BuildDominatorTree();
180 SideEffectsAnalysis side_effects(graph);
181 side_effects.Run();
182 GVNOptimization(graph, side_effects).Run();
183
184 // Check that all field get instructions have been GVN'ed.
185 ASSERT_TRUE(then->GetFirstInstruction()->IsGoto());
186 ASSERT_TRUE(else_->GetFirstInstruction()->IsGoto());
187 ASSERT_TRUE(join->GetFirstInstruction()->IsExit());
188 }
189
TEST_F(GVNTest,LoopFieldElimination)190 TEST_F(GVNTest, LoopFieldElimination) {
191 HGraph* graph = CreateGraph();
192 HBasicBlock* entry = new (GetAllocator()) HBasicBlock(graph);
193 graph->AddBlock(entry);
194 graph->SetEntryBlock(entry);
195
196 HInstruction* parameter = new (GetAllocator()) HParameterValue(graph->GetDexFile(),
197 dex::TypeIndex(0),
198 0,
199 DataType::Type::kReference);
200 entry->AddInstruction(parameter);
201
202 HBasicBlock* block = new (GetAllocator()) HBasicBlock(graph);
203 graph->AddBlock(block);
204 entry->AddSuccessor(block);
205 block->AddInstruction(new (GetAllocator()) HInstanceFieldGet(parameter,
206 nullptr,
207 DataType::Type::kBool,
208 MemberOffset(42),
209 false,
210 kUnknownFieldIndex,
211 kUnknownClassDefIndex,
212 graph->GetDexFile(),
213 0));
214 block->AddInstruction(new (GetAllocator()) HGoto());
215
216 HBasicBlock* loop_header = new (GetAllocator()) HBasicBlock(graph);
217 HBasicBlock* loop_body = new (GetAllocator()) HBasicBlock(graph);
218 HBasicBlock* exit = new (GetAllocator()) HBasicBlock(graph);
219
220 graph->AddBlock(loop_header);
221 graph->AddBlock(loop_body);
222 graph->AddBlock(exit);
223 block->AddSuccessor(loop_header);
224 loop_header->AddSuccessor(loop_body);
225 loop_header->AddSuccessor(exit);
226 loop_body->AddSuccessor(loop_header);
227
228 loop_header->AddInstruction(new (GetAllocator()) HInstanceFieldGet(parameter,
229 nullptr,
230 DataType::Type::kBool,
231 MemberOffset(42),
232 false,
233 kUnknownFieldIndex,
234 kUnknownClassDefIndex,
235 graph->GetDexFile(),
236 0));
237 HInstruction* field_get_in_loop_header = loop_header->GetLastInstruction();
238 loop_header->AddInstruction(new (GetAllocator()) HIf(block->GetLastInstruction()));
239
240 // Kill inside the loop body to prevent field gets inside the loop header
241 // and the body to be GVN'ed.
242 loop_body->AddInstruction(new (GetAllocator()) HInstanceFieldSet(parameter,
243 parameter,
244 nullptr,
245 DataType::Type::kBool,
246 MemberOffset(42),
247 false,
248 kUnknownFieldIndex,
249 kUnknownClassDefIndex,
250 graph->GetDexFile(),
251 0));
252 HInstruction* field_set = loop_body->GetLastInstruction();
253 loop_body->AddInstruction(new (GetAllocator()) HInstanceFieldGet(parameter,
254 nullptr,
255 DataType::Type::kBool,
256 MemberOffset(42),
257 false,
258 kUnknownFieldIndex,
259 kUnknownClassDefIndex,
260 graph->GetDexFile(),
261 0));
262 HInstruction* field_get_in_loop_body = loop_body->GetLastInstruction();
263 loop_body->AddInstruction(new (GetAllocator()) HGoto());
264
265 exit->AddInstruction(new (GetAllocator()) HInstanceFieldGet(parameter,
266 nullptr,
267 DataType::Type::kBool,
268 MemberOffset(42),
269 false,
270 kUnknownFieldIndex,
271 kUnknownClassDefIndex,
272 graph->GetDexFile(),
273 0));
274 HInstruction* field_get_in_exit = exit->GetLastInstruction();
275 exit->AddInstruction(new (GetAllocator()) HExit());
276
277 ASSERT_EQ(field_get_in_loop_header->GetBlock(), loop_header);
278 ASSERT_EQ(field_get_in_loop_body->GetBlock(), loop_body);
279 ASSERT_EQ(field_get_in_exit->GetBlock(), exit);
280
281 graph->BuildDominatorTree();
282 {
283 SideEffectsAnalysis side_effects(graph);
284 side_effects.Run();
285 GVNOptimization(graph, side_effects).Run();
286 }
287
288 // Check that all field get instructions are still there.
289 ASSERT_EQ(field_get_in_loop_header->GetBlock(), loop_header);
290 ASSERT_EQ(field_get_in_loop_body->GetBlock(), loop_body);
291 // The exit block is dominated by the loop header, whose field get
292 // does not get killed by the loop flags.
293 ASSERT_TRUE(field_get_in_exit->GetBlock() == nullptr);
294
295 // Now remove the field set, and check that all field get instructions have been GVN'ed.
296 loop_body->RemoveInstruction(field_set);
297 {
298 SideEffectsAnalysis side_effects(graph);
299 side_effects.Run();
300 GVNOptimization(graph, side_effects).Run();
301 }
302
303 ASSERT_TRUE(field_get_in_loop_header->GetBlock() == nullptr);
304 ASSERT_TRUE(field_get_in_loop_body->GetBlock() == nullptr);
305 ASSERT_TRUE(field_get_in_exit->GetBlock() == nullptr);
306 }
307
308 // Test that inner loops affect the side effects of the outer loop.
TEST_F(GVNTest,LoopSideEffects)309 TEST_F(GVNTest, LoopSideEffects) {
310 static const SideEffects kCanTriggerGC = SideEffects::CanTriggerGC();
311
312 HGraph* graph = CreateGraph();
313 HBasicBlock* entry = new (GetAllocator()) HBasicBlock(graph);
314 graph->AddBlock(entry);
315 graph->SetEntryBlock(entry);
316
317 HBasicBlock* outer_loop_header = new (GetAllocator()) HBasicBlock(graph);
318 HBasicBlock* outer_loop_body = new (GetAllocator()) HBasicBlock(graph);
319 HBasicBlock* outer_loop_exit = new (GetAllocator()) HBasicBlock(graph);
320 HBasicBlock* inner_loop_header = new (GetAllocator()) HBasicBlock(graph);
321 HBasicBlock* inner_loop_body = new (GetAllocator()) HBasicBlock(graph);
322 HBasicBlock* inner_loop_exit = new (GetAllocator()) HBasicBlock(graph);
323
324 graph->AddBlock(outer_loop_header);
325 graph->AddBlock(outer_loop_body);
326 graph->AddBlock(outer_loop_exit);
327 graph->AddBlock(inner_loop_header);
328 graph->AddBlock(inner_loop_body);
329 graph->AddBlock(inner_loop_exit);
330
331 entry->AddSuccessor(outer_loop_header);
332 outer_loop_header->AddSuccessor(outer_loop_body);
333 outer_loop_header->AddSuccessor(outer_loop_exit);
334 outer_loop_body->AddSuccessor(inner_loop_header);
335 inner_loop_header->AddSuccessor(inner_loop_body);
336 inner_loop_header->AddSuccessor(inner_loop_exit);
337 inner_loop_body->AddSuccessor(inner_loop_header);
338 inner_loop_exit->AddSuccessor(outer_loop_header);
339
340 HInstruction* parameter = new (GetAllocator()) HParameterValue(graph->GetDexFile(),
341 dex::TypeIndex(0),
342 0,
343 DataType::Type::kBool);
344 entry->AddInstruction(parameter);
345 entry->AddInstruction(new (GetAllocator()) HGoto());
346 outer_loop_header->AddInstruction(new (GetAllocator()) HSuspendCheck());
347 outer_loop_header->AddInstruction(new (GetAllocator()) HIf(parameter));
348 outer_loop_body->AddInstruction(new (GetAllocator()) HGoto());
349 inner_loop_header->AddInstruction(new (GetAllocator()) HSuspendCheck());
350 inner_loop_header->AddInstruction(new (GetAllocator()) HIf(parameter));
351 inner_loop_body->AddInstruction(new (GetAllocator()) HGoto());
352 inner_loop_exit->AddInstruction(new (GetAllocator()) HGoto());
353 outer_loop_exit->AddInstruction(new (GetAllocator()) HExit());
354
355 graph->BuildDominatorTree();
356
357 ASSERT_TRUE(inner_loop_header->GetLoopInformation()->IsIn(
358 *outer_loop_header->GetLoopInformation()));
359
360 // Check that the only side effect of loops is to potentially trigger GC.
361 {
362 // Make one block with a side effect.
363 entry->AddInstruction(new (GetAllocator()) HInstanceFieldSet(parameter,
364 parameter,
365 nullptr,
366 DataType::Type::kReference,
367 MemberOffset(42),
368 false,
369 kUnknownFieldIndex,
370 kUnknownClassDefIndex,
371 graph->GetDexFile(),
372 0));
373
374 SideEffectsAnalysis side_effects(graph);
375 side_effects.Run();
376
377 ASSERT_TRUE(side_effects.GetBlockEffects(entry).DoesAnyWrite());
378 ASSERT_FALSE(side_effects.GetBlockEffects(outer_loop_body).DoesAnyWrite());
379 ASSERT_FALSE(side_effects.GetLoopEffects(outer_loop_header).DoesAnyWrite());
380 ASSERT_FALSE(side_effects.GetLoopEffects(inner_loop_header).DoesAnyWrite());
381 ASSERT_TRUE(side_effects.GetLoopEffects(outer_loop_header).Equals(kCanTriggerGC));
382 ASSERT_TRUE(side_effects.GetLoopEffects(inner_loop_header).Equals(kCanTriggerGC));
383 }
384
385 // Check that the side effects of the outer loop does not affect the inner loop.
386 {
387 outer_loop_body->InsertInstructionBefore(
388 new (GetAllocator()) HInstanceFieldSet(parameter,
389 parameter,
390 nullptr,
391 DataType::Type::kReference,
392 MemberOffset(42),
393 false,
394 kUnknownFieldIndex,
395 kUnknownClassDefIndex,
396 graph->GetDexFile(),
397 0),
398 outer_loop_body->GetLastInstruction());
399
400 SideEffectsAnalysis side_effects(graph);
401 side_effects.Run();
402
403 ASSERT_TRUE(side_effects.GetBlockEffects(entry).DoesAnyWrite());
404 ASSERT_TRUE(side_effects.GetBlockEffects(outer_loop_body).DoesAnyWrite());
405 ASSERT_TRUE(side_effects.GetLoopEffects(outer_loop_header).DoesAnyWrite());
406 ASSERT_FALSE(side_effects.GetLoopEffects(inner_loop_header).DoesAnyWrite());
407 ASSERT_TRUE(side_effects.GetLoopEffects(inner_loop_header).Equals(kCanTriggerGC));
408 }
409
410 // Check that the side effects of the inner loop affects the outer loop.
411 {
412 outer_loop_body->RemoveInstruction(outer_loop_body->GetFirstInstruction());
413 inner_loop_body->InsertInstructionBefore(
414 new (GetAllocator()) HInstanceFieldSet(parameter,
415 parameter,
416 nullptr,
417 DataType::Type::kReference,
418 MemberOffset(42),
419 false,
420 kUnknownFieldIndex,
421 kUnknownClassDefIndex,
422 graph->GetDexFile(),
423 0),
424 inner_loop_body->GetLastInstruction());
425
426 SideEffectsAnalysis side_effects(graph);
427 side_effects.Run();
428
429 ASSERT_TRUE(side_effects.GetBlockEffects(entry).DoesAnyWrite());
430 ASSERT_FALSE(side_effects.GetBlockEffects(outer_loop_body).DoesAnyWrite());
431 ASSERT_TRUE(side_effects.GetLoopEffects(outer_loop_header).DoesAnyWrite());
432 ASSERT_TRUE(side_effects.GetLoopEffects(inner_loop_header).DoesAnyWrite());
433 }
434 }
435 } // namespace art
436