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