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