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