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 "base/macros.h"
24 #include "code_generator.h"
25 #include "driver/compiler_options.h"
26 #include "nodes.h"
27 #include "optimizing_unit_test.h"
28
29 namespace art HIDDEN {
30
31 class SsaLivenessAnalysisTest : public OptimizingUnitTest {
32 protected:
SetUp()33 void SetUp() override {
34 OptimizingUnitTest::SetUp();
35 graph_ = CreateGraph();
36 compiler_options_ = CommonCompilerTest::CreateCompilerOptions(kRuntimeISA, "default");
37 codegen_ = CodeGenerator::Create(graph_, *compiler_options_);
38 CHECK(codegen_ != nullptr);
39 // Create entry block.
40 entry_ = new (GetAllocator()) HBasicBlock(graph_);
41 graph_->AddBlock(entry_);
42 graph_->SetEntryBlock(entry_);
43 }
44
45 protected:
CreateSuccessor(HBasicBlock * block)46 HBasicBlock* CreateSuccessor(HBasicBlock* block) {
47 HGraph* graph = block->GetGraph();
48 HBasicBlock* successor = new (GetAllocator()) HBasicBlock(graph);
49 graph->AddBlock(successor);
50 block->AddSuccessor(successor);
51 return successor;
52 }
53
54 HGraph* graph_;
55 std::unique_ptr<CompilerOptions> compiler_options_;
56 std::unique_ptr<CodeGenerator> codegen_;
57 HBasicBlock* entry_;
58 };
59
TEST_F(SsaLivenessAnalysisTest,TestReturnArg)60 TEST_F(SsaLivenessAnalysisTest, TestReturnArg) {
61 HInstruction* arg = MakeParam(DataType::Type::kInt32);
62
63 HBasicBlock* block = CreateSuccessor(entry_);
64 MakeReturn(block, arg);
65 MakeExit(block);
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 = MakeParam(DataType::Type::kReference);
79 HInstruction* index = MakeParam(DataType::Type::kInt32);
80 HInstruction* value = MakeParam(DataType::Type::kInt32);
81 HInstruction* extra_arg1 = MakeParam(DataType::Type::kInt32);
82 HInstruction* extra_arg2 = MakeParam(DataType::Type::kReference);
83 std::initializer_list<HInstruction*> args{array, index, value, extra_arg1, extra_arg2};
84
85 HBasicBlock* block = CreateSuccessor(entry_);
86 HInstruction* null_check = MakeNullCheck(block, array, /*env=*/ args);
87 HInstruction* length = MakeArrayLength(block, array);
88 HInstruction* bounds_check = MakeBoundsCheck(block, index, length, /*env=*/ args);
89 MakeArraySet(block, array, index, value, DataType::Type::kInt32);
90
91 graph_->BuildDominatorTree();
92 SsaLivenessAnalysis ssa_analysis(graph_, codegen_.get(), GetScopedAllocator());
93 ssa_analysis.Analyze();
94
95 EXPECT_FALSE(graph_->IsDebuggable());
96 EXPECT_EQ(18u, bounds_check->GetLifetimePosition());
97 static const char* const expected[] = {
98 "ranges: { [2,21) }, uses: { 15 17 21 }, { 15 19 } is_fixed: 0, is_split: 0 is_low: 0 "
99 "is_high: 0",
100 "ranges: { [4,21) }, uses: { 19 21 }, { } is_fixed: 0, is_split: 0 is_low: 0 "
101 "is_high: 0",
102 "ranges: { [6,21) }, uses: { 21 }, { } is_fixed: 0, is_split: 0 is_low: 0 "
103 "is_high: 0",
104 // Environment uses do not keep the non-reference argument alive.
105 "ranges: { [8,10) }, uses: { }, { } is_fixed: 0, is_split: 0 is_low: 0 is_high: 0",
106 // Environment uses keep the reference argument alive.
107 "ranges: { [10,19) }, uses: { }, { 15 19 } is_fixed: 0, is_split: 0 is_low: 0 is_high: 0",
108 };
109 CHECK_EQ(arraysize(expected), args.size());
110 size_t arg_index = 0u;
111 for (HInstruction* arg : args) {
112 std::ostringstream arg_dump;
113 arg->GetLiveInterval()->Dump(arg_dump);
114 EXPECT_STREQ(expected[arg_index], arg_dump.str().c_str()) << arg_index;
115 ++arg_index;
116 }
117 }
118
TEST_F(SsaLivenessAnalysisTest,TestDeoptimize)119 TEST_F(SsaLivenessAnalysisTest, TestDeoptimize) {
120 HInstruction* array = MakeParam(DataType::Type::kReference);
121 HInstruction* index = MakeParam(DataType::Type::kInt32);
122 HInstruction* value = MakeParam(DataType::Type::kInt32);
123 HInstruction* extra_arg1 = MakeParam(DataType::Type::kInt32);
124 HInstruction* extra_arg2 = MakeParam(DataType::Type::kReference);
125 std::initializer_list<HInstruction*> args{array, index, value, extra_arg1, extra_arg2};
126
127 HBasicBlock* block = CreateSuccessor(entry_);
128 HInstruction* null_check = MakeNullCheck(block, array, /*env=*/ args);
129 HInstruction* length = MakeArrayLength(block, array);
130 // Use HAboveOrEqual+HDeoptimize as the bounds check.
131 HInstruction* ae = MakeCondition(block, kCondAE, index, length);
132 HInstruction* deoptimize = new(GetAllocator()) HDeoptimize(
133 GetAllocator(), ae, DeoptimizationKind::kBlockBCE, /* dex_pc= */ 0u);
134 block->AddInstruction(deoptimize);
135 ManuallyBuildEnvFor(deoptimize, /*env=*/ args);
136 MakeArraySet(block, array, index, value, DataType::Type::kInt32);
137
138 graph_->BuildDominatorTree();
139 SsaLivenessAnalysis ssa_analysis(graph_, codegen_.get(), GetScopedAllocator());
140 ssa_analysis.Analyze();
141
142 EXPECT_FALSE(graph_->IsDebuggable());
143 EXPECT_EQ(20u, deoptimize->GetLifetimePosition());
144 static const char* const expected[] = {
145 "ranges: { [2,23) }, uses: { 15 17 23 }, { 15 21 } is_fixed: 0, is_split: 0 is_low: 0 "
146 "is_high: 0",
147 "ranges: { [4,23) }, uses: { 19 23 }, { 21 } is_fixed: 0, is_split: 0 is_low: 0 "
148 "is_high: 0",
149 "ranges: { [6,23) }, uses: { 23 }, { 21 } is_fixed: 0, is_split: 0 is_low: 0 is_high: 0",
150 // Environment use in HDeoptimize keeps even the non-reference argument alive.
151 "ranges: { [8,21) }, uses: { }, { 21 } is_fixed: 0, is_split: 0 is_low: 0 is_high: 0",
152 // Environment uses keep the reference argument alive.
153 "ranges: { [10,21) }, uses: { }, { 15 21 } is_fixed: 0, is_split: 0 is_low: 0 is_high: 0",
154 };
155 CHECK_EQ(arraysize(expected), args.size());
156 size_t arg_index = 0u;
157 for (HInstruction* arg : args) {
158 std::ostringstream arg_dump;
159 arg->GetLiveInterval()->Dump(arg_dump);
160 EXPECT_STREQ(expected[arg_index], arg_dump.str().c_str()) << arg_index;
161 ++arg_index;
162 }
163 }
164
165 } // namespace art
166