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 "nodes.h"
18
19 #include "base/arena_allocator.h"
20 #include "base/macros.h"
21 #include "optimizing_unit_test.h"
22
23 #include "gtest/gtest.h"
24
25 namespace art HIDDEN {
26
27 class NodeTest : public OptimizingUnitTest {};
28
29 /**
30 * Test that we can clear loop and dominator information in either order.
31 * Code is:
32 * while (true) {
33 * if (foobar) { break; }
34 * if (baz) { xyz; } else { abc; }
35 * }
36 * dosomething();
37 */
TEST_F(NodeTest,ClearLoopThenDominanceInformation)38 TEST_F(NodeTest, ClearLoopThenDominanceInformation) {
39 CreateGraph();
40 AdjacencyListGraph alg(graph_,
41 GetAllocator(),
42 "entry",
43 "exit",
44 {{"entry", "loop_pre_header"},
45
46 {"loop_pre_header", "loop_header"},
47 {"loop_header", "critical_break"},
48 {"loop_header", "loop_body"},
49 {"loop_body", "loop_if_left"},
50 {"loop_body", "loop_if_right"},
51 {"loop_if_left", "loop_merge"},
52 {"loop_if_right", "loop_merge"},
53 {"loop_merge", "loop_header"},
54
55 {"critical_break", "breturn"},
56 {"breturn", "exit"}});
57 graph_->ClearDominanceInformation();
58 graph_->BuildDominatorTree();
59
60 // Test
61 EXPECT_TRUE(
62 std::all_of(graph_->GetBlocks().begin(), graph_->GetBlocks().end(), [&](HBasicBlock* b) {
63 return b == graph_->GetEntryBlock() || b == nullptr || b->GetDominator() != nullptr;
64 }));
65 EXPECT_TRUE(
66 std::any_of(graph_->GetBlocks().begin(), graph_->GetBlocks().end(), [&](HBasicBlock* b) {
67 return b != nullptr && b->GetLoopInformation() != nullptr;
68 }));
69
70 // Clear
71 graph_->ClearLoopInformation();
72 graph_->ClearDominanceInformation();
73
74 // Test
75 EXPECT_TRUE(
76 std::none_of(graph_->GetBlocks().begin(), graph_->GetBlocks().end(), [&](HBasicBlock* b) {
77 return b != nullptr && b->GetDominator() != nullptr;
78 }));
79 EXPECT_TRUE(
80 std::all_of(graph_->GetBlocks().begin(), graph_->GetBlocks().end(), [&](HBasicBlock* b) {
81 return b == nullptr || b->GetLoopInformation() == nullptr;
82 }));
83 }
84
85 /**
86 * Test that we can clear loop and dominator information in either order.
87 * Code is:
88 * while (true) {
89 * if (foobar) { break; }
90 * if (baz) { xyz; } else { abc; }
91 * }
92 * dosomething();
93 */
TEST_F(NodeTest,ClearDominanceThenLoopInformation)94 TEST_F(NodeTest, ClearDominanceThenLoopInformation) {
95 CreateGraph();
96 AdjacencyListGraph alg(graph_,
97 GetAllocator(),
98 "entry",
99 "exit",
100 {{"entry", "loop_pre_header"},
101
102 {"loop_pre_header", "loop_header"},
103 {"loop_header", "critical_break"},
104 {"loop_header", "loop_body"},
105 {"loop_body", "loop_if_left"},
106 {"loop_body", "loop_if_right"},
107 {"loop_if_left", "loop_merge"},
108 {"loop_if_right", "loop_merge"},
109 {"loop_merge", "loop_header"},
110
111 {"critical_break", "breturn"},
112 {"breturn", "exit"}});
113 graph_->ClearDominanceInformation();
114 graph_->BuildDominatorTree();
115
116 // Test
117 EXPECT_TRUE(
118 std::all_of(graph_->GetBlocks().begin(), graph_->GetBlocks().end(), [&](HBasicBlock* b) {
119 return b == graph_->GetEntryBlock() || b == nullptr || b->GetDominator() != nullptr;
120 }));
121 EXPECT_TRUE(
122 std::any_of(graph_->GetBlocks().begin(), graph_->GetBlocks().end(), [&](HBasicBlock* b) {
123 return b != nullptr && b->GetLoopInformation() != nullptr;
124 }));
125
126 // Clear
127 graph_->ClearDominanceInformation();
128 graph_->ClearLoopInformation();
129
130 // Test
131 EXPECT_TRUE(
132 std::none_of(graph_->GetBlocks().begin(), graph_->GetBlocks().end(), [&](HBasicBlock* b) {
133 return b != nullptr && b->GetDominator() != nullptr;
134 }));
135 EXPECT_TRUE(
136 std::all_of(graph_->GetBlocks().begin(), graph_->GetBlocks().end(), [&](HBasicBlock* b) {
137 return b == nullptr || b->GetLoopInformation() == nullptr;
138 }));
139 }
140
141 /**
142 * Test that removing instruction from the graph removes itself from user lists
143 * and environment lists.
144 */
TEST_F(NodeTest,RemoveInstruction)145 TEST_F(NodeTest, RemoveInstruction) {
146 HBasicBlock* main = InitEntryMainExitGraphWithReturnVoid();
147
148 HInstruction* parameter = MakeParam(DataType::Type::kReference);
149
150 HInstruction* null_check = MakeNullCheck(main, parameter, /*env=*/ {parameter});
151
152 ASSERT_TRUE(parameter->HasEnvironmentUses());
153 ASSERT_TRUE(parameter->HasUses());
154
155 main->RemoveInstruction(null_check);
156
157 ASSERT_FALSE(parameter->HasEnvironmentUses());
158 ASSERT_FALSE(parameter->HasUses());
159 }
160
161 /**
162 * Test that inserting an instruction in the graph updates user lists.
163 */
TEST_F(NodeTest,InsertInstruction)164 TEST_F(NodeTest, InsertInstruction) {
165 HGraph* graph = CreateGraph();
166 HBasicBlock* entry = new (GetAllocator()) HBasicBlock(graph);
167 graph->AddBlock(entry);
168 graph->SetEntryBlock(entry);
169 HInstruction* parameter1 = MakeParam(DataType::Type::kReference);
170 HInstruction* parameter2 = MakeParam(DataType::Type::kReference);
171 MakeExit(entry);
172
173 ASSERT_FALSE(parameter1->HasUses());
174
175 HInstruction* to_insert = new (GetAllocator()) HNullCheck(parameter1, 0);
176 entry->InsertInstructionBefore(to_insert, parameter2);
177
178 ASSERT_TRUE(parameter1->HasUses());
179 ASSERT_TRUE(parameter1->GetUses().HasExactlyOneElement());
180 }
181
182 /**
183 * Test that adding an instruction in the graph updates user lists.
184 */
TEST_F(NodeTest,AddInstruction)185 TEST_F(NodeTest, AddInstruction) {
186 HGraph* graph = CreateGraph();
187 HBasicBlock* entry = new (GetAllocator()) HBasicBlock(graph);
188 graph->AddBlock(entry);
189 graph->SetEntryBlock(entry);
190 HInstruction* parameter = MakeParam(DataType::Type::kReference);
191
192 ASSERT_FALSE(parameter->HasUses());
193
194 MakeNullCheck(entry, parameter);
195
196 ASSERT_TRUE(parameter->HasUses());
197 ASSERT_TRUE(parameter->GetUses().HasExactlyOneElement());
198 }
199
TEST_F(NodeTest,InsertDuplicateInstructionAt)200 TEST_F(NodeTest, InsertDuplicateInstructionAt) {
201 HBasicBlock* ret = InitEntryMainExitGraphWithReturnVoid();
202 HInstruction* const0 = graph_->GetIntConstant(0);
203 HInstruction* const1 = graph_->GetIntConstant(1);
204 HInstruction* const2 = graph_->GetIntConstant(0);
205 HInstruction* const3 = graph_->GetIntConstant(1);
206
207 // We should be able to insert a duplicate input to `HPhi`s if we want to
208 // make a graph transformation that adds another predecessor to a block.
209
210 // This used to accidentally end up with correct use information but unexpectedly
211 // using the old `HUseListNode<>` for the new use and the new one for the old use.
212 HPhi* phi1 = MakePhi(ret, {const0, const1});
213 struct AccessProtected : HVariableInputSizeInstruction {
214 using HVariableInputSizeInstruction::InputRecordAt;
215 };
216 const HUseListNode<HInstruction*>* old_use_node_before =
217 std::addressof(*(phi1->*&AccessProtected::InputRecordAt)(1u).GetUseNode());
218 phi1->InsertInputAt(1u, const1); // Moves the old use from position 1 to position 2.
219 const HUseListNode<HInstruction*>* old_use_node_after =
220 std::addressof(*(phi1->*&AccessProtected::InputRecordAt)(2u).GetUseNode());
221 EXPECT_EQ(old_use_node_before, old_use_node_after);
222 EXPECT_EQ(1u, (phi1->*&AccessProtected::InputRecordAt)(1u).GetUseNode()->GetIndex());
223 EXPECT_EQ(2u, (phi1->*&AccessProtected::InputRecordAt)(2u).GetUseNode()->GetIndex());
224
225 // This used to hit a `DCHECK()`.
226 HPhi* phi2 = MakePhi(ret, {const2, const3, const3});
227 phi2->InsertInputAt(1u, const3);
228 }
229
TEST_F(NodeTest,ParentEnvironment)230 TEST_F(NodeTest, ParentEnvironment) {
231 HGraph* graph = CreateGraph();
232 HBasicBlock* entry = new (GetAllocator()) HBasicBlock(graph);
233 graph->AddBlock(entry);
234 graph->SetEntryBlock(entry);
235 HInstruction* parameter1 = MakeParam(DataType::Type::kReference);
236 HInstruction* with_environment = MakeNullCheck(entry, parameter1, /*env=*/ {parameter1});
237 MakeExit(entry);
238
239 ASSERT_TRUE(parameter1->HasUses());
240 ASSERT_TRUE(parameter1->GetUses().HasExactlyOneElement());
241
242 ASSERT_TRUE(parameter1->HasEnvironmentUses());
243 ASSERT_TRUE(parameter1->GetEnvUses().HasExactlyOneElement());
244
245 HEnvironment* parent1 = HEnvironment::Create(
246 GetAllocator(),
247 /*number_of_vregs=*/ 1,
248 graph->GetArtMethod(),
249 /*dex_pc=*/ 0,
250 /*holder=*/ nullptr);
251 parent1->CopyFrom(GetAllocator(), ArrayRef<HInstruction* const>(¶meter1, 1u));
252
253 ASSERT_EQ(parameter1->GetEnvUses().SizeSlow(), 2u);
254
255 HEnvironment* parent2 = HEnvironment::Create(
256 GetAllocator(),
257 /*number_of_vregs=*/ 1,
258 graph->GetArtMethod(),
259 /*dex_pc=*/ 0,
260 /*holder=*/ nullptr);
261 parent2->CopyFrom(GetAllocator(), ArrayRef<HInstruction* const>(¶meter1, 1u));
262 parent1->SetAndCopyParentChain(GetAllocator(), parent2);
263
264 // One use for parent2, and one other use for the new parent of parent1.
265 ASSERT_EQ(parameter1->GetEnvUses().SizeSlow(), 4u);
266
267 // We have copied the parent chain. So we now have two more uses.
268 with_environment->GetEnvironment()->SetAndCopyParentChain(GetAllocator(), parent1);
269 ASSERT_EQ(parameter1->GetEnvUses().SizeSlow(), 6u);
270 }
271
272 } // namespace art
273