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 "gvn.h"
18
19 #include "base/arena_allocator.h"
20 #include "base/macros.h"
21 #include "builder.h"
22 #include "nodes.h"
23 #include "optimizing_unit_test.h"
24 #include "side_effects_analysis.h"
25
26 namespace art HIDDEN {
27
28 class GVNTest : public OptimizingUnitTest {};
29
TEST_F(GVNTest,LocalFieldElimination)30 TEST_F(GVNTest, LocalFieldElimination) {
31 HBasicBlock* block = InitEntryMainExitGraphWithReturnVoid();
32
33 HInstruction* parameter = MakeParam(DataType::Type::kReference);
34
35 MakeIFieldGet(block, parameter, DataType::Type::kReference, MemberOffset(42));
36 HInstruction* to_remove =
37 MakeIFieldGet(block, parameter, DataType::Type::kReference, MemberOffset(42));
38 HInstruction* different_offset =
39 MakeIFieldGet(block, parameter, DataType::Type::kReference, MemberOffset(43));
40 // Kill the value.
41 MakeIFieldSet(block, parameter, parameter, MemberOffset(42));
42 HInstruction* use_after_kill =
43 MakeIFieldGet(block, parameter, DataType::Type::kReference, MemberOffset(42));
44
45 ASSERT_EQ(to_remove->GetBlock(), block);
46 ASSERT_EQ(different_offset->GetBlock(), block);
47 ASSERT_EQ(use_after_kill->GetBlock(), block);
48
49 graph_->BuildDominatorTree();
50 SideEffectsAnalysis side_effects(graph_);
51 side_effects.Run();
52 GVNOptimization(graph_, side_effects).Run();
53
54 ASSERT_TRUE(to_remove->GetBlock() == nullptr);
55 ASSERT_EQ(different_offset->GetBlock(), block);
56 ASSERT_EQ(use_after_kill->GetBlock(), block);
57 }
58
TEST_F(GVNTest,GlobalFieldElimination)59 TEST_F(GVNTest, GlobalFieldElimination) {
60 HBasicBlock* join = InitEntryMainExitGraphWithReturnVoid();
61 auto [block, then, else_] = CreateDiamondPattern(join);
62
63 HInstruction* parameter = MakeParam(DataType::Type::kReference);
64
65 HInstruction* field_get =
66 MakeIFieldGet(block, parameter, DataType::Type::kBool, MemberOffset(42));
67 MakeIf(block, field_get);
68
69 MakeIFieldGet(then, parameter, DataType::Type::kBool, MemberOffset(42));
70 MakeIFieldGet(else_, parameter, DataType::Type::kBool, MemberOffset(42));
71 MakeIFieldGet(join, parameter, DataType::Type::kBool, MemberOffset(42));
72
73 graph_->BuildDominatorTree();
74 SideEffectsAnalysis side_effects(graph_);
75 side_effects.Run();
76 GVNOptimization(graph_, side_effects).Run();
77
78 // Check that all field get instructions have been GVN'ed.
79 ASSERT_TRUE(then->GetFirstInstruction()->IsGoto());
80 ASSERT_TRUE(else_->GetFirstInstruction()->IsGoto());
81 ASSERT_TRUE(join->GetFirstInstruction()->IsReturnVoid());
82 }
83
TEST_F(GVNTest,LoopFieldElimination)84 TEST_F(GVNTest, LoopFieldElimination) {
85 HBasicBlock* return_block = InitEntryMainExitGraphWithReturnVoid();
86 auto [pre_header, loop_header, loop_body] = CreateWhileLoop(return_block);
87 loop_header->SwapSuccessors(); // Move the loop exit to the "else" successor.
88
89 HInstruction* parameter = MakeParam(DataType::Type::kReference);
90
91 MakeIFieldGet(pre_header, parameter, DataType::Type::kBool, MemberOffset(42));
92
93 HInstruction* field_get_in_loop_header =
94 MakeIFieldGet(loop_header, parameter, DataType::Type::kBool, MemberOffset(42));
95 MakeIf(loop_header, field_get_in_loop_header);
96
97 // Kill inside the loop body to prevent field gets inside the loop header
98 // and the body to be GVN'ed.
99 HInstruction* field_set =
100 MakeIFieldSet(loop_body, parameter, parameter, DataType::Type::kBool, MemberOffset(42));
101 HInstruction* field_get_in_loop_body =
102 MakeIFieldGet(loop_body, parameter, DataType::Type::kBool, MemberOffset(42));
103
104 HInstruction* field_get_in_return_block =
105 MakeIFieldGet(return_block, parameter, DataType::Type::kBool, MemberOffset(42));
106
107 ASSERT_EQ(field_get_in_loop_header->GetBlock(), loop_header);
108 ASSERT_EQ(field_get_in_loop_body->GetBlock(), loop_body);
109 ASSERT_EQ(field_get_in_return_block->GetBlock(), return_block);
110
111 graph_->BuildDominatorTree();
112 {
113 SideEffectsAnalysis side_effects(graph_);
114 side_effects.Run();
115 GVNOptimization(graph_, side_effects).Run();
116 }
117
118 // Check that all field get instructions are still there.
119 ASSERT_EQ(field_get_in_loop_header->GetBlock(), loop_header);
120 ASSERT_EQ(field_get_in_loop_body->GetBlock(), loop_body);
121 // The `return_block` is dominated by the `loop_header`, whose field get
122 // does not get killed by the loop flags.
123 ASSERT_TRUE(field_get_in_return_block->GetBlock() == nullptr);
124
125 // Now remove the field set, and check that all field get instructions have been GVN'ed.
126 loop_body->RemoveInstruction(field_set);
127 {
128 SideEffectsAnalysis side_effects(graph_);
129 side_effects.Run();
130 GVNOptimization(graph_, side_effects).Run();
131 }
132
133 ASSERT_TRUE(field_get_in_loop_header->GetBlock() == nullptr);
134 ASSERT_TRUE(field_get_in_loop_body->GetBlock() == nullptr);
135 ASSERT_TRUE(field_get_in_return_block->GetBlock() == nullptr);
136 }
137
138 // Test that inner loops affect the side effects of the outer loop.
TEST_F(GVNTest,LoopSideEffects)139 TEST_F(GVNTest, LoopSideEffects) {
140 static const SideEffects kCanTriggerGC = SideEffects::CanTriggerGC();
141
142 HBasicBlock* outer_loop_exit = InitEntryMainExitGraphWithReturnVoid();
143 auto [outer_preheader, outer_loop_header, inner_loop_exit] = CreateWhileLoop(outer_loop_exit);
144 outer_loop_header->SwapSuccessors(); // Move the loop exit to the "else" successor.
145 auto [outer_loop_body, inner_loop_header, inner_loop_body] = CreateWhileLoop(inner_loop_exit);
146 inner_loop_header->SwapSuccessors(); // Move the loop exit to the "else" successor.
147
148 HInstruction* parameter = MakeParam(DataType::Type::kBool);
149 MakeSuspendCheck(outer_loop_header);
150 MakeIf(outer_loop_header, parameter);
151 MakeSuspendCheck(inner_loop_header);
152 MakeIf(inner_loop_header, parameter);
153
154 graph_->BuildDominatorTree();
155
156 ASSERT_TRUE(inner_loop_header->GetLoopInformation()->IsIn(
157 *outer_loop_header->GetLoopInformation()));
158
159 // Check that the only side effect of loops is to potentially trigger GC.
160 {
161 // Make one block with a side effect.
162 MakeIFieldSet(entry_block_, parameter, parameter, DataType::Type::kReference, MemberOffset(42));
163
164 SideEffectsAnalysis side_effects(graph_);
165 side_effects.Run();
166
167 ASSERT_TRUE(side_effects.GetBlockEffects(entry_block_).DoesAnyWrite());
168 ASSERT_FALSE(side_effects.GetBlockEffects(outer_loop_body).DoesAnyWrite());
169 ASSERT_FALSE(side_effects.GetLoopEffects(outer_loop_header).DoesAnyWrite());
170 ASSERT_FALSE(side_effects.GetLoopEffects(inner_loop_header).DoesAnyWrite());
171 ASSERT_TRUE(side_effects.GetLoopEffects(outer_loop_header).Equals(kCanTriggerGC));
172 ASSERT_TRUE(side_effects.GetLoopEffects(inner_loop_header).Equals(kCanTriggerGC));
173 }
174
175 // Check that the side effects of the outer loop does not affect the inner loop.
176 {
177 MakeIFieldSet(
178 outer_loop_body, parameter, parameter, DataType::Type::kReference, MemberOffset(42));
179
180 SideEffectsAnalysis side_effects(graph_);
181 side_effects.Run();
182
183 ASSERT_TRUE(side_effects.GetBlockEffects(entry_block_).DoesAnyWrite());
184 ASSERT_TRUE(side_effects.GetBlockEffects(outer_loop_body).DoesAnyWrite());
185 ASSERT_TRUE(side_effects.GetLoopEffects(outer_loop_header).DoesAnyWrite());
186 ASSERT_FALSE(side_effects.GetLoopEffects(inner_loop_header).DoesAnyWrite());
187 ASSERT_TRUE(side_effects.GetLoopEffects(inner_loop_header).Equals(kCanTriggerGC));
188 }
189
190 // Check that the side effects of the inner loop affects the outer loop.
191 {
192 outer_loop_body->RemoveInstruction(outer_loop_body->GetFirstInstruction());
193 MakeIFieldSet(
194 inner_loop_body, parameter, parameter, DataType::Type::kReference, MemberOffset(42));
195
196 SideEffectsAnalysis side_effects(graph_);
197 side_effects.Run();
198
199 ASSERT_TRUE(side_effects.GetBlockEffects(entry_block_).DoesAnyWrite());
200 ASSERT_FALSE(side_effects.GetBlockEffects(outer_loop_body).DoesAnyWrite());
201 ASSERT_TRUE(side_effects.GetLoopEffects(outer_loop_header).DoesAnyWrite());
202 ASSERT_TRUE(side_effects.GetLoopEffects(inner_loop_header).DoesAnyWrite());
203 }
204 }
205 } // namespace art
206