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 HGraph* graph = CreateGraph();
147 HBasicBlock* entry = new (GetAllocator()) HBasicBlock(graph);
148 graph->AddBlock(entry);
149 graph->SetEntryBlock(entry);
150 HInstruction* parameter = new (GetAllocator()) HParameterValue(
151 graph->GetDexFile(), dex::TypeIndex(0), 0, DataType::Type::kReference);
152 entry->AddInstruction(parameter);
153 entry->AddInstruction(new (GetAllocator()) HGoto());
154
155 HBasicBlock* first_block = new (GetAllocator()) HBasicBlock(graph);
156 graph->AddBlock(first_block);
157 entry->AddSuccessor(first_block);
158 HInstruction* null_check = new (GetAllocator()) HNullCheck(parameter, 0);
159 first_block->AddInstruction(null_check);
160 first_block->AddInstruction(new (GetAllocator()) HReturnVoid());
161
162 HBasicBlock* exit_block = new (GetAllocator()) HBasicBlock(graph);
163 graph->AddBlock(exit_block);
164 first_block->AddSuccessor(exit_block);
165 exit_block->AddInstruction(new (GetAllocator()) HExit());
166
167 HEnvironment* environment = new (GetAllocator()) HEnvironment(
168 GetAllocator(), 1, graph->GetArtMethod(), 0, null_check);
169 null_check->SetRawEnvironment(environment);
170 environment->SetRawEnvAt(0, parameter);
171 parameter->AddEnvUseAt(null_check->GetEnvironment(), 0);
172
173 ASSERT_TRUE(parameter->HasEnvironmentUses());
174 ASSERT_TRUE(parameter->HasUses());
175
176 first_block->RemoveInstruction(null_check);
177
178 ASSERT_FALSE(parameter->HasEnvironmentUses());
179 ASSERT_FALSE(parameter->HasUses());
180 }
181
182 /**
183 * Test that inserting an instruction in the graph updates user lists.
184 */
TEST_F(NodeTest,InsertInstruction)185 TEST_F(NodeTest, InsertInstruction) {
186 HGraph* graph = CreateGraph();
187 HBasicBlock* entry = new (GetAllocator()) HBasicBlock(graph);
188 graph->AddBlock(entry);
189 graph->SetEntryBlock(entry);
190 HInstruction* parameter1 = new (GetAllocator()) HParameterValue(
191 graph->GetDexFile(), dex::TypeIndex(0), 0, DataType::Type::kReference);
192 HInstruction* parameter2 = new (GetAllocator()) HParameterValue(
193 graph->GetDexFile(), dex::TypeIndex(0), 0, DataType::Type::kReference);
194 entry->AddInstruction(parameter1);
195 entry->AddInstruction(parameter2);
196 entry->AddInstruction(new (GetAllocator()) HExit());
197
198 ASSERT_FALSE(parameter1->HasUses());
199
200 HInstruction* to_insert = new (GetAllocator()) HNullCheck(parameter1, 0);
201 entry->InsertInstructionBefore(to_insert, parameter2);
202
203 ASSERT_TRUE(parameter1->HasUses());
204 ASSERT_TRUE(parameter1->GetUses().HasExactlyOneElement());
205 }
206
207 /**
208 * Test that adding an instruction in the graph updates user lists.
209 */
TEST_F(NodeTest,AddInstruction)210 TEST_F(NodeTest, AddInstruction) {
211 HGraph* graph = CreateGraph();
212 HBasicBlock* entry = new (GetAllocator()) HBasicBlock(graph);
213 graph->AddBlock(entry);
214 graph->SetEntryBlock(entry);
215 HInstruction* parameter = new (GetAllocator()) HParameterValue(
216 graph->GetDexFile(), dex::TypeIndex(0), 0, DataType::Type::kReference);
217 entry->AddInstruction(parameter);
218
219 ASSERT_FALSE(parameter->HasUses());
220
221 HInstruction* to_add = new (GetAllocator()) HNullCheck(parameter, 0);
222 entry->AddInstruction(to_add);
223
224 ASSERT_TRUE(parameter->HasUses());
225 ASSERT_TRUE(parameter->GetUses().HasExactlyOneElement());
226 }
227
TEST_F(NodeTest,ParentEnvironment)228 TEST_F(NodeTest, ParentEnvironment) {
229 HGraph* graph = CreateGraph();
230 HBasicBlock* entry = new (GetAllocator()) HBasicBlock(graph);
231 graph->AddBlock(entry);
232 graph->SetEntryBlock(entry);
233 HInstruction* parameter1 = new (GetAllocator()) HParameterValue(
234 graph->GetDexFile(), dex::TypeIndex(0), 0, DataType::Type::kReference);
235 HInstruction* with_environment = new (GetAllocator()) HNullCheck(parameter1, 0);
236 entry->AddInstruction(parameter1);
237 entry->AddInstruction(with_environment);
238 entry->AddInstruction(new (GetAllocator()) HExit());
239
240 ASSERT_TRUE(parameter1->HasUses());
241 ASSERT_TRUE(parameter1->GetUses().HasExactlyOneElement());
242
243 HEnvironment* environment = new (GetAllocator()) HEnvironment(
244 GetAllocator(), 1, graph->GetArtMethod(), 0, with_environment);
245 HInstruction* const array[] = { parameter1 };
246
247 environment->CopyFrom(ArrayRef<HInstruction* const>(array));
248 with_environment->SetRawEnvironment(environment);
249
250 ASSERT_TRUE(parameter1->HasEnvironmentUses());
251 ASSERT_TRUE(parameter1->GetEnvUses().HasExactlyOneElement());
252
253 HEnvironment* parent1 = new (GetAllocator()) HEnvironment(
254 GetAllocator(), 1, graph->GetArtMethod(), 0, nullptr);
255 parent1->CopyFrom(ArrayRef<HInstruction* const>(array));
256
257 ASSERT_EQ(parameter1->GetEnvUses().SizeSlow(), 2u);
258
259 HEnvironment* parent2 = new (GetAllocator()) HEnvironment(
260 GetAllocator(), 1, graph->GetArtMethod(), 0, nullptr);
261 parent2->CopyFrom(ArrayRef<HInstruction* const>(array));
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 environment->SetAndCopyParentChain(GetAllocator(), parent1);
269 ASSERT_EQ(parameter1->GetEnvUses().SizeSlow(), 6u);
270 }
271
272 } // namespace art
273