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,ParentEnvironment)200 TEST_F(NodeTest, ParentEnvironment) {
201 HGraph* graph = CreateGraph();
202 HBasicBlock* entry = new (GetAllocator()) HBasicBlock(graph);
203 graph->AddBlock(entry);
204 graph->SetEntryBlock(entry);
205 HInstruction* parameter1 = MakeParam(DataType::Type::kReference);
206 HInstruction* with_environment = MakeNullCheck(entry, parameter1, /*env=*/ {parameter1});
207 MakeExit(entry);
208
209 ASSERT_TRUE(parameter1->HasUses());
210 ASSERT_TRUE(parameter1->GetUses().HasExactlyOneElement());
211
212 ASSERT_TRUE(parameter1->HasEnvironmentUses());
213 ASSERT_TRUE(parameter1->GetEnvUses().HasExactlyOneElement());
214
215 HEnvironment* parent1 = HEnvironment::Create(
216 GetAllocator(),
217 /*number_of_vregs=*/ 1,
218 graph->GetArtMethod(),
219 /*dex_pc=*/ 0,
220 /*holder=*/ nullptr);
221 parent1->CopyFrom(ArrayRef<HInstruction* const>(¶meter1, 1u));
222
223 ASSERT_EQ(parameter1->GetEnvUses().SizeSlow(), 2u);
224
225 HEnvironment* parent2 = HEnvironment::Create(
226 GetAllocator(),
227 /*number_of_vregs=*/ 1,
228 graph->GetArtMethod(),
229 /*dex_pc=*/ 0,
230 /*holder=*/ nullptr);
231 parent2->CopyFrom(ArrayRef<HInstruction* const>(¶meter1, 1u));
232 parent1->SetAndCopyParentChain(GetAllocator(), parent2);
233
234 // One use for parent2, and one other use for the new parent of parent1.
235 ASSERT_EQ(parameter1->GetEnvUses().SizeSlow(), 4u);
236
237 // We have copied the parent chain. So we now have two more uses.
238 with_environment->GetEnvironment()->SetAndCopyParentChain(GetAllocator(), parent1);
239 ASSERT_EQ(parameter1->GetEnvUses().SizeSlow(), 6u);
240 }
241
242 } // namespace art
243