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 
26 namespace art {
27 
TEST(GVNTest,LocalFieldElimination)28 TEST(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 
TEST(GVNTest,GlobalFieldElimination)77 TEST(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 
TEST(GVNTest,LoopFieldElimination)132 TEST(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.
TEST(GVNTest,LoopSideEffects)219 TEST(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