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