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