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