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