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: 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: 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 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 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 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
