1 /*
2 * Copyright (C) 2017 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 "ssa_liveness_analysis.h"
18
19 #include "arch/instruction_set.h"
20 #include "arch/instruction_set_features.h"
21 #include "base/arena_allocator.h"
22 #include "base/arena_containers.h"
23 #include "base/macros.h"
24 #include "code_generator.h"
25 #include "driver/compiler_options.h"
26 #include "nodes.h"
27 #include "optimizing_unit_test.h"
28
29 namespace art HIDDEN {
30
31 class SsaLivenessAnalysisTest : public OptimizingUnitTest {
32 protected:
SetUp()33 void SetUp() override {
34 OptimizingUnitTest::SetUp();
35 graph_ = CreateGraph();
36 compiler_options_ = CommonCompilerTest::CreateCompilerOptions(kRuntimeISA, "default");
37 codegen_ = CodeGenerator::Create(graph_, *compiler_options_);
38 CHECK(codegen_ != nullptr);
39 // Create entry block.
40 entry_ = new (GetAllocator()) HBasicBlock(graph_);
41 graph_->AddBlock(entry_);
42 graph_->SetEntryBlock(entry_);
43 }
44
45 protected:
CreateSuccessor(HBasicBlock * block)46 HBasicBlock* CreateSuccessor(HBasicBlock* block) {
47 HGraph* graph = block->GetGraph();
48 HBasicBlock* successor = new (GetAllocator()) HBasicBlock(graph);
49 graph->AddBlock(successor);
50 block->AddSuccessor(successor);
51 return successor;
52 }
53
54 HGraph* graph_;
55 std::unique_ptr<CompilerOptions> compiler_options_;
56 std::unique_ptr<CodeGenerator> codegen_;
57 HBasicBlock* entry_;
58 };
59
TEST_F(SsaLivenessAnalysisTest,TestReturnArg)60 TEST_F(SsaLivenessAnalysisTest, TestReturnArg) {
61 HInstruction* arg = new (GetAllocator()) HParameterValue(
62 graph_->GetDexFile(), dex::TypeIndex(0), 0, DataType::Type::kInt32);
63 entry_->AddInstruction(arg);
64
65 HBasicBlock* block = CreateSuccessor(entry_);
66 HInstruction* ret = new (GetAllocator()) HReturn(arg);
67 block->AddInstruction(ret);
68 block->AddInstruction(new (GetAllocator()) HExit());
69
70 graph_->BuildDominatorTree();
71 SsaLivenessAnalysis ssa_analysis(graph_, codegen_.get(), GetScopedAllocator());
72 ssa_analysis.Analyze();
73
74 std::ostringstream arg_dump;
75 arg->GetLiveInterval()->Dump(arg_dump);
76 EXPECT_STREQ("ranges: { [2,6) }, uses: { 6 }, { } is_fixed: 0, is_split: 0 is_low: 0 is_high: 0",
77 arg_dump.str().c_str());
78 }
79
TEST_F(SsaLivenessAnalysisTest,TestAput)80 TEST_F(SsaLivenessAnalysisTest, TestAput) {
81 HInstruction* array = new (GetAllocator()) HParameterValue(
82 graph_->GetDexFile(), dex::TypeIndex(0), 0, DataType::Type::kReference);
83 HInstruction* index = new (GetAllocator()) HParameterValue(
84 graph_->GetDexFile(), dex::TypeIndex(1), 1, DataType::Type::kInt32);
85 HInstruction* value = new (GetAllocator()) HParameterValue(
86 graph_->GetDexFile(), dex::TypeIndex(2), 2, DataType::Type::kInt32);
87 HInstruction* extra_arg1 = new (GetAllocator()) HParameterValue(
88 graph_->GetDexFile(), dex::TypeIndex(3), 3, DataType::Type::kInt32);
89 HInstruction* extra_arg2 = new (GetAllocator()) HParameterValue(
90 graph_->GetDexFile(), dex::TypeIndex(4), 4, DataType::Type::kReference);
91 HInstruction* const args[] = { array, index, value, extra_arg1, extra_arg2 };
92 for (HInstruction* insn : args) {
93 entry_->AddInstruction(insn);
94 }
95
96 HBasicBlock* block = CreateSuccessor(entry_);
97 HInstruction* null_check = new (GetAllocator()) HNullCheck(array, 0);
98 block->AddInstruction(null_check);
99 HEnvironment* null_check_env = new (GetAllocator()) HEnvironment(GetAllocator(),
100 /* number_of_vregs= */ 5,
101 /* method= */ nullptr,
102 /* dex_pc= */ 0u,
103 null_check);
104 null_check_env->CopyFrom(ArrayRef<HInstruction* const>(args));
105 null_check->SetRawEnvironment(null_check_env);
106 HInstruction* length = new (GetAllocator()) HArrayLength(array, 0);
107 block->AddInstruction(length);
108 HInstruction* bounds_check = new (GetAllocator()) HBoundsCheck(index, length, /* dex_pc= */ 0u);
109 block->AddInstruction(bounds_check);
110 HEnvironment* bounds_check_env = new (GetAllocator()) HEnvironment(GetAllocator(),
111 /* number_of_vregs= */ 5,
112 /* method= */ nullptr,
113 /* dex_pc= */ 0u,
114 bounds_check);
115 bounds_check_env->CopyFrom(ArrayRef<HInstruction* const>(args));
116 bounds_check->SetRawEnvironment(bounds_check_env);
117 HInstruction* array_set =
118 new (GetAllocator()) HArraySet(array, index, value, DataType::Type::kInt32, /* dex_pc= */ 0);
119 block->AddInstruction(array_set);
120
121 graph_->BuildDominatorTree();
122 SsaLivenessAnalysis ssa_analysis(graph_, codegen_.get(), GetScopedAllocator());
123 ssa_analysis.Analyze();
124
125 EXPECT_FALSE(graph_->IsDebuggable());
126 EXPECT_EQ(18u, bounds_check->GetLifetimePosition());
127 static const char* const expected[] = {
128 "ranges: { [2,21) }, uses: { 15 17 21 }, { 15 19 } is_fixed: 0, is_split: 0 is_low: 0 "
129 "is_high: 0",
130 "ranges: { [4,21) }, uses: { 19 21 }, { } is_fixed: 0, is_split: 0 is_low: 0 "
131 "is_high: 0",
132 "ranges: { [6,21) }, uses: { 21 }, { } is_fixed: 0, is_split: 0 is_low: 0 "
133 "is_high: 0",
134 // Environment uses do not keep the non-reference argument alive.
135 "ranges: { [8,10) }, uses: { }, { } is_fixed: 0, is_split: 0 is_low: 0 is_high: 0",
136 // Environment uses keep the reference argument alive.
137 "ranges: { [10,19) }, uses: { }, { 15 19 } is_fixed: 0, is_split: 0 is_low: 0 is_high: 0",
138 };
139 static_assert(arraysize(expected) == arraysize(args), "Array size check.");
140 size_t arg_index = 0u;
141 for (HInstruction* arg : args) {
142 std::ostringstream arg_dump;
143 arg->GetLiveInterval()->Dump(arg_dump);
144 EXPECT_STREQ(expected[arg_index], arg_dump.str().c_str()) << arg_index;
145 ++arg_index;
146 }
147 }
148
TEST_F(SsaLivenessAnalysisTest,TestDeoptimize)149 TEST_F(SsaLivenessAnalysisTest, TestDeoptimize) {
150 HInstruction* array = new (GetAllocator()) HParameterValue(
151 graph_->GetDexFile(), dex::TypeIndex(0), 0, DataType::Type::kReference);
152 HInstruction* index = new (GetAllocator()) HParameterValue(
153 graph_->GetDexFile(), dex::TypeIndex(1), 1, DataType::Type::kInt32);
154 HInstruction* value = new (GetAllocator()) HParameterValue(
155 graph_->GetDexFile(), dex::TypeIndex(2), 2, DataType::Type::kInt32);
156 HInstruction* extra_arg1 = new (GetAllocator()) HParameterValue(
157 graph_->GetDexFile(), dex::TypeIndex(3), 3, DataType::Type::kInt32);
158 HInstruction* extra_arg2 = new (GetAllocator()) HParameterValue(
159 graph_->GetDexFile(), dex::TypeIndex(4), 4, DataType::Type::kReference);
160 HInstruction* const args[] = { array, index, value, extra_arg1, extra_arg2 };
161 for (HInstruction* insn : args) {
162 entry_->AddInstruction(insn);
163 }
164
165 HBasicBlock* block = CreateSuccessor(entry_);
166 HInstruction* null_check = new (GetAllocator()) HNullCheck(array, 0);
167 block->AddInstruction(null_check);
168 HEnvironment* null_check_env = new (GetAllocator()) HEnvironment(GetAllocator(),
169 /* number_of_vregs= */ 5,
170 /* method= */ nullptr,
171 /* dex_pc= */ 0u,
172 null_check);
173 null_check_env->CopyFrom(ArrayRef<HInstruction* const>(args));
174 null_check->SetRawEnvironment(null_check_env);
175 HInstruction* length = new (GetAllocator()) HArrayLength(array, 0);
176 block->AddInstruction(length);
177 // Use HAboveOrEqual+HDeoptimize as the bounds check.
178 HInstruction* ae = new (GetAllocator()) HAboveOrEqual(index, length);
179 block->AddInstruction(ae);
180 HInstruction* deoptimize = new(GetAllocator()) HDeoptimize(
181 GetAllocator(), ae, DeoptimizationKind::kBlockBCE, /* dex_pc= */ 0u);
182 block->AddInstruction(deoptimize);
183 HEnvironment* deoptimize_env = new (GetAllocator()) HEnvironment(GetAllocator(),
184 /* number_of_vregs= */ 5,
185 /* method= */ nullptr,
186 /* dex_pc= */ 0u,
187 deoptimize);
188 deoptimize_env->CopyFrom(ArrayRef<HInstruction* const>(args));
189 deoptimize->SetRawEnvironment(deoptimize_env);
190 HInstruction* array_set =
191 new (GetAllocator()) HArraySet(array, index, value, DataType::Type::kInt32, /* dex_pc= */ 0);
192 block->AddInstruction(array_set);
193
194 graph_->BuildDominatorTree();
195 SsaLivenessAnalysis ssa_analysis(graph_, codegen_.get(), GetScopedAllocator());
196 ssa_analysis.Analyze();
197
198 EXPECT_FALSE(graph_->IsDebuggable());
199 EXPECT_EQ(20u, deoptimize->GetLifetimePosition());
200 static const char* const expected[] = {
201 "ranges: { [2,23) }, uses: { 15 17 23 }, { 15 21 } is_fixed: 0, is_split: 0 is_low: 0 "
202 "is_high: 0",
203 "ranges: { [4,23) }, uses: { 19 23 }, { 21 } is_fixed: 0, is_split: 0 is_low: 0 "
204 "is_high: 0",
205 "ranges: { [6,23) }, uses: { 23 }, { 21 } is_fixed: 0, is_split: 0 is_low: 0 is_high: 0",
206 // Environment use in HDeoptimize keeps even the non-reference argument alive.
207 "ranges: { [8,21) }, uses: { }, { 21 } is_fixed: 0, is_split: 0 is_low: 0 is_high: 0",
208 // Environment uses keep the reference argument alive.
209 "ranges: { [10,21) }, uses: { }, { 15 21 } is_fixed: 0, is_split: 0 is_low: 0 is_high: 0",
210 };
211 static_assert(arraysize(expected) == arraysize(args), "Array size check.");
212 size_t arg_index = 0u;
213 for (HInstruction* arg : args) {
214 std::ostringstream arg_dump;
215 arg->GetLiveInterval()->Dump(arg_dump);
216 EXPECT_STREQ(expected[arg_index], arg_dump.str().c_str()) << arg_index;
217 ++arg_index;
218 }
219 }
220
221 } // namespace art
222