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