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