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
24namespace art {
25
26class GVNTest : public CommonCompilerTest {};
27
28TEST_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
113TEST_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
196TEST_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.
319TEST_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