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#include "gtest/gtest.h"
25
26namespace art {
27
28TEST(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(0, Primitive::kPrimNot);
37  entry->AddInstruction(parameter);
38
39  HBasicBlock* block = new (&allocator) HBasicBlock(graph);
40  graph->AddBlock(block);
41  entry->AddSuccessor(block);
42
43  block->AddInstruction(
44      new (&allocator) HInstanceFieldGet(parameter, Primitive::kPrimNot,
45          MemberOffset(42), false));
46  block->AddInstruction(
47      new (&allocator) HInstanceFieldGet(parameter, Primitive::kPrimNot,
48          MemberOffset(42), false));
49  HInstruction* to_remove = block->GetLastInstruction();
50  block->AddInstruction(
51      new (&allocator) HInstanceFieldGet(parameter, Primitive::kPrimNot,
52          MemberOffset(43), false));
53  HInstruction* different_offset = block->GetLastInstruction();
54  // Kill the value.
55  block->AddInstruction(new (&allocator) HInstanceFieldSet(
56      parameter, parameter, Primitive::kPrimNot, MemberOffset(42), false));
57  block->AddInstruction(
58      new (&allocator) HInstanceFieldGet(parameter, Primitive::kPrimNot,
59          MemberOffset(42), false));
60  HInstruction* use_after_kill = block->GetLastInstruction();
61  block->AddInstruction(new (&allocator) HExit());
62
63  ASSERT_EQ(to_remove->GetBlock(), block);
64  ASSERT_EQ(different_offset->GetBlock(), block);
65  ASSERT_EQ(use_after_kill->GetBlock(), block);
66
67  graph->TryBuildingSsa();
68  SideEffectsAnalysis side_effects(graph);
69  side_effects.Run();
70  GVNOptimization(graph, side_effects).Run();
71
72  ASSERT_TRUE(to_remove->GetBlock() == nullptr);
73  ASSERT_EQ(different_offset->GetBlock(), block);
74  ASSERT_EQ(use_after_kill->GetBlock(), block);
75}
76
77TEST(GVNTest, GlobalFieldElimination) {
78  ArenaPool pool;
79  ArenaAllocator allocator(&pool);
80
81  HGraph* graph = CreateGraph(&allocator);
82  HBasicBlock* entry = new (&allocator) HBasicBlock(graph);
83  graph->AddBlock(entry);
84  graph->SetEntryBlock(entry);
85  HInstruction* parameter = new (&allocator) HParameterValue(0, Primitive::kPrimNot);
86  entry->AddInstruction(parameter);
87
88  HBasicBlock* block = new (&allocator) HBasicBlock(graph);
89  graph->AddBlock(block);
90  entry->AddSuccessor(block);
91  block->AddInstruction(
92      new (&allocator) HInstanceFieldGet(parameter, Primitive::kPrimBoolean,
93          MemberOffset(42), false));
94
95  block->AddInstruction(new (&allocator) HIf(block->GetLastInstruction()));
96  HBasicBlock* then = new (&allocator) HBasicBlock(graph);
97  HBasicBlock* else_ = new (&allocator) HBasicBlock(graph);
98  HBasicBlock* join = new (&allocator) HBasicBlock(graph);
99  graph->AddBlock(then);
100  graph->AddBlock(else_);
101  graph->AddBlock(join);
102
103  block->AddSuccessor(then);
104  block->AddSuccessor(else_);
105  then->AddSuccessor(join);
106  else_->AddSuccessor(join);
107
108  then->AddInstruction(
109      new (&allocator) HInstanceFieldGet(parameter, Primitive::kPrimBoolean,
110          MemberOffset(42), false));
111  then->AddInstruction(new (&allocator) HGoto());
112  else_->AddInstruction(
113      new (&allocator) HInstanceFieldGet(parameter, Primitive::kPrimBoolean,
114          MemberOffset(42), false));
115  else_->AddInstruction(new (&allocator) HGoto());
116  join->AddInstruction(
117      new (&allocator) HInstanceFieldGet(parameter, Primitive::kPrimBoolean,
118          MemberOffset(42), false));
119  join->AddInstruction(new (&allocator) HExit());
120
121  graph->TryBuildingSsa();
122  SideEffectsAnalysis side_effects(graph);
123  side_effects.Run();
124  GVNOptimization(graph, side_effects).Run();
125
126  // Check that all field get instructions have been GVN'ed.
127  ASSERT_TRUE(then->GetFirstInstruction()->IsGoto());
128  ASSERT_TRUE(else_->GetFirstInstruction()->IsGoto());
129  ASSERT_TRUE(join->GetFirstInstruction()->IsExit());
130}
131
132TEST(GVNTest, LoopFieldElimination) {
133  ArenaPool pool;
134  ArenaAllocator allocator(&pool);
135
136  HGraph* graph = CreateGraph(&allocator);
137  HBasicBlock* entry = new (&allocator) HBasicBlock(graph);
138  graph->AddBlock(entry);
139  graph->SetEntryBlock(entry);
140
141  HInstruction* parameter = new (&allocator) HParameterValue(0, Primitive::kPrimNot);
142  entry->AddInstruction(parameter);
143
144  HBasicBlock* block = new (&allocator) HBasicBlock(graph);
145  graph->AddBlock(block);
146  entry->AddSuccessor(block);
147  block->AddInstruction(
148      new (&allocator) HInstanceFieldGet(parameter, Primitive::kPrimBoolean,
149          MemberOffset(42), false));
150  block->AddInstruction(new (&allocator) HGoto());
151
152  HBasicBlock* loop_header = new (&allocator) HBasicBlock(graph);
153  HBasicBlock* loop_body = new (&allocator) HBasicBlock(graph);
154  HBasicBlock* exit = new (&allocator) HBasicBlock(graph);
155
156  graph->AddBlock(loop_header);
157  graph->AddBlock(loop_body);
158  graph->AddBlock(exit);
159  block->AddSuccessor(loop_header);
160  loop_header->AddSuccessor(loop_body);
161  loop_header->AddSuccessor(exit);
162  loop_body->AddSuccessor(loop_header);
163
164  loop_header->AddInstruction(
165      new (&allocator) HInstanceFieldGet(parameter, Primitive::kPrimBoolean,
166          MemberOffset(42), false));
167  HInstruction* field_get_in_loop_header = loop_header->GetLastInstruction();
168  loop_header->AddInstruction(new (&allocator) HIf(block->GetLastInstruction()));
169
170  // Kill inside the loop body to prevent field gets inside the loop header
171  // and the body to be GVN'ed.
172  loop_body->AddInstruction(new (&allocator) HInstanceFieldSet(
173      parameter, parameter, Primitive::kPrimNot, MemberOffset(42), false));
174  HInstruction* field_set = loop_body->GetLastInstruction();
175  loop_body->AddInstruction(
176      new (&allocator) HInstanceFieldGet(parameter, Primitive::kPrimBoolean,
177          MemberOffset(42), false));
178  HInstruction* field_get_in_loop_body = loop_body->GetLastInstruction();
179  loop_body->AddInstruction(new (&allocator) HGoto());
180
181  exit->AddInstruction(
182      new (&allocator) HInstanceFieldGet(parameter, Primitive::kPrimBoolean,
183          MemberOffset(42), false));
184  HInstruction* field_get_in_exit = exit->GetLastInstruction();
185  exit->AddInstruction(new (&allocator) HExit());
186
187  ASSERT_EQ(field_get_in_loop_header->GetBlock(), loop_header);
188  ASSERT_EQ(field_get_in_loop_body->GetBlock(), loop_body);
189  ASSERT_EQ(field_get_in_exit->GetBlock(), exit);
190
191  graph->TryBuildingSsa();
192  {
193    SideEffectsAnalysis side_effects(graph);
194    side_effects.Run();
195    GVNOptimization(graph, side_effects).Run();
196  }
197
198  // Check that all field get instructions are still there.
199  ASSERT_EQ(field_get_in_loop_header->GetBlock(), loop_header);
200  ASSERT_EQ(field_get_in_loop_body->GetBlock(), loop_body);
201  // The exit block is dominated by the loop header, whose field get
202  // does not get killed by the loop flags.
203  ASSERT_TRUE(field_get_in_exit->GetBlock() == nullptr);
204
205  // Now remove the field set, and check that all field get instructions have been GVN'ed.
206  loop_body->RemoveInstruction(field_set);
207  {
208    SideEffectsAnalysis side_effects(graph);
209    side_effects.Run();
210    GVNOptimization(graph, side_effects).Run();
211  }
212
213  ASSERT_TRUE(field_get_in_loop_header->GetBlock() == nullptr);
214  ASSERT_TRUE(field_get_in_loop_body->GetBlock() == nullptr);
215  ASSERT_TRUE(field_get_in_exit->GetBlock() == nullptr);
216}
217
218// Test that inner loops affect the side effects of the outer loop.
219TEST(GVNTest, LoopSideEffects) {
220  ArenaPool pool;
221  ArenaAllocator allocator(&pool);
222
223  HGraph* graph = CreateGraph(&allocator);
224  HBasicBlock* entry = new (&allocator) HBasicBlock(graph);
225  graph->AddBlock(entry);
226  graph->SetEntryBlock(entry);
227
228  HBasicBlock* outer_loop_header = new (&allocator) HBasicBlock(graph);
229  HBasicBlock* outer_loop_body = new (&allocator) HBasicBlock(graph);
230  HBasicBlock* outer_loop_exit = new (&allocator) HBasicBlock(graph);
231  HBasicBlock* inner_loop_header = new (&allocator) HBasicBlock(graph);
232  HBasicBlock* inner_loop_body = new (&allocator) HBasicBlock(graph);
233  HBasicBlock* inner_loop_exit = new (&allocator) HBasicBlock(graph);
234
235  graph->AddBlock(outer_loop_header);
236  graph->AddBlock(outer_loop_body);
237  graph->AddBlock(outer_loop_exit);
238  graph->AddBlock(inner_loop_header);
239  graph->AddBlock(inner_loop_body);
240  graph->AddBlock(inner_loop_exit);
241
242  entry->AddSuccessor(outer_loop_header);
243  outer_loop_header->AddSuccessor(outer_loop_body);
244  outer_loop_header->AddSuccessor(outer_loop_exit);
245  outer_loop_body->AddSuccessor(inner_loop_header);
246  inner_loop_header->AddSuccessor(inner_loop_body);
247  inner_loop_header->AddSuccessor(inner_loop_exit);
248  inner_loop_body->AddSuccessor(inner_loop_header);
249  inner_loop_exit->AddSuccessor(outer_loop_header);
250
251  HInstruction* parameter = new (&allocator) HParameterValue(0, Primitive::kPrimBoolean);
252  entry->AddInstruction(parameter);
253  entry->AddInstruction(new (&allocator) HGoto());
254  outer_loop_header->AddInstruction(new (&allocator) HIf(parameter));
255  outer_loop_body->AddInstruction(new (&allocator) HGoto());
256  inner_loop_header->AddInstruction(new (&allocator) HIf(parameter));
257  inner_loop_body->AddInstruction(new (&allocator) HGoto());
258  inner_loop_exit->AddInstruction(new (&allocator) HGoto());
259  outer_loop_exit->AddInstruction(new (&allocator) HExit());
260
261  graph->TryBuildingSsa();
262
263  ASSERT_TRUE(inner_loop_header->GetLoopInformation()->IsIn(
264      *outer_loop_header->GetLoopInformation()));
265
266  // Check that the loops don't have side effects.
267  {
268    // Make one block with a side effect.
269    entry->AddInstruction(new (&allocator) HInstanceFieldSet(
270        parameter, parameter, Primitive::kPrimNot, MemberOffset(42), false));
271
272    SideEffectsAnalysis side_effects(graph);
273    side_effects.Run();
274
275    ASSERT_TRUE(side_effects.GetBlockEffects(entry).HasSideEffects());
276    ASSERT_FALSE(side_effects.GetLoopEffects(outer_loop_header).HasSideEffects());
277    ASSERT_FALSE(side_effects.GetLoopEffects(inner_loop_header).HasSideEffects());
278  }
279
280  // Check that the side effects of the outer loop does not affect the inner loop.
281  {
282    outer_loop_body->InsertInstructionBefore(
283        new (&allocator) HInstanceFieldSet(
284            parameter, parameter, Primitive::kPrimNot, MemberOffset(42), false),
285        outer_loop_body->GetLastInstruction());
286
287    SideEffectsAnalysis side_effects(graph);
288    side_effects.Run();
289
290    ASSERT_TRUE(side_effects.GetBlockEffects(entry).HasSideEffects());
291    ASSERT_TRUE(side_effects.GetBlockEffects(outer_loop_body).HasSideEffects());
292    ASSERT_TRUE(side_effects.GetLoopEffects(outer_loop_header).HasSideEffects());
293    ASSERT_FALSE(side_effects.GetLoopEffects(inner_loop_header).HasSideEffects());
294  }
295
296  // Check that the side effects of the inner loop affects the outer loop.
297  {
298    outer_loop_body->RemoveInstruction(outer_loop_body->GetFirstInstruction());
299    inner_loop_body->InsertInstructionBefore(
300        new (&allocator) HInstanceFieldSet(
301            parameter, parameter, Primitive::kPrimNot, MemberOffset(42), false),
302        inner_loop_body->GetLastInstruction());
303
304    SideEffectsAnalysis side_effects(graph);
305    side_effects.Run();
306
307    ASSERT_TRUE(side_effects.GetBlockEffects(entry).HasSideEffects());
308    ASSERT_FALSE(side_effects.GetBlockEffects(outer_loop_body).HasSideEffects());
309    ASSERT_TRUE(side_effects.GetLoopEffects(outer_loop_header).HasSideEffects());
310    ASSERT_TRUE(side_effects.GetLoopEffects(inner_loop_header).HasSideEffects());
311  }
312}
313}  // namespace art
314