1 /* 2 * Copyright (C) 2016 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 "scheduler.h" 18 19 #include "base/arena_allocator.h" 20 #include "builder.h" 21 #include "codegen_test_utils.h" 22 #include "common_compiler_test.h" 23 #include "load_store_analysis.h" 24 #include "nodes.h" 25 #include "optimizing_unit_test.h" 26 #include "pc_relative_fixups_x86.h" 27 #include "register_allocator.h" 28 29 #ifdef ART_ENABLE_CODEGEN_arm64 30 #include "scheduler_arm64.h" 31 #endif 32 33 #ifdef ART_ENABLE_CODEGEN_arm 34 #include "scheduler_arm.h" 35 #endif 36 37 namespace art { 38 39 // Return all combinations of ISA and code generator that are executable on 40 // hardware, or on simulator, and that we'd like to test. 41 static ::std::vector<CodegenTargetConfig> GetTargetConfigs() { 42 ::std::vector<CodegenTargetConfig> v; 43 ::std::vector<CodegenTargetConfig> test_config_candidates = { 44 #ifdef ART_ENABLE_CODEGEN_arm 45 // TODO: Should't this be `kThumb2` instead of `kArm` here? 46 CodegenTargetConfig(InstructionSet::kArm, create_codegen_arm_vixl32), 47 #endif 48 #ifdef ART_ENABLE_CODEGEN_arm64 49 CodegenTargetConfig(InstructionSet::kArm64, create_codegen_arm64), 50 #endif 51 #ifdef ART_ENABLE_CODEGEN_x86 52 CodegenTargetConfig(InstructionSet::kX86, create_codegen_x86), 53 #endif 54 #ifdef ART_ENABLE_CODEGEN_x86_64 55 CodegenTargetConfig(InstructionSet::kX86_64, create_codegen_x86_64), 56 #endif 57 #ifdef ART_ENABLE_CODEGEN_mips 58 CodegenTargetConfig(InstructionSet::kMips, create_codegen_mips), 59 #endif 60 #ifdef ART_ENABLE_CODEGEN_mips64 61 CodegenTargetConfig(InstructionSet::kMips64, create_codegen_mips64) 62 #endif 63 }; 64 65 for (const CodegenTargetConfig& test_config : test_config_candidates) { 66 if (CanExecute(test_config.GetInstructionSet())) { 67 v.push_back(test_config); 68 } 69 } 70 71 return v; 72 } 73 74 class SchedulerTest : public OptimizingUnitTest { 75 public: 76 SchedulerTest() : graph_(CreateGraph()) { } 77 78 // Build scheduling graph, and run target specific scheduling on it. 79 void TestBuildDependencyGraphAndSchedule(HScheduler* scheduler) { 80 HBasicBlock* entry = new (GetAllocator()) HBasicBlock(graph_); 81 HBasicBlock* block1 = new (GetAllocator()) HBasicBlock(graph_); 82 graph_->AddBlock(entry); 83 graph_->AddBlock(block1); 84 graph_->SetEntryBlock(entry); 85 86 // entry: 87 // array ParameterValue 88 // c1 IntConstant 89 // c2 IntConstant 90 // block1: 91 // add1 Add [c1, c2] 92 // add2 Add [add1, c2] 93 // mul Mul [add1, add2] 94 // div_check DivZeroCheck [add2] (env: add2, mul) 95 // div Div [add1, div_check] 96 // array_get1 ArrayGet [array, add1] 97 // array_set1 ArraySet [array, add1, add2] 98 // array_get2 ArrayGet [array, add1] 99 // array_set2 ArraySet [array, add1, add2] 100 101 HInstruction* array = new (GetAllocator()) HParameterValue(graph_->GetDexFile(), 102 dex::TypeIndex(0), 103 0, 104 DataType::Type::kReference); 105 HInstruction* c1 = graph_->GetIntConstant(1); 106 HInstruction* c2 = graph_->GetIntConstant(10); 107 HInstruction* add1 = new (GetAllocator()) HAdd(DataType::Type::kInt32, c1, c2); 108 HInstruction* add2 = new (GetAllocator()) HAdd(DataType::Type::kInt32, add1, c2); 109 HInstruction* mul = new (GetAllocator()) HMul(DataType::Type::kInt32, add1, add2); 110 HInstruction* div_check = new (GetAllocator()) HDivZeroCheck(add2, 0); 111 HInstruction* div = new (GetAllocator()) HDiv(DataType::Type::kInt32, add1, div_check, 0); 112 HInstruction* array_get1 = 113 new (GetAllocator()) HArrayGet(array, add1, DataType::Type::kInt32, 0); 114 HInstruction* array_set1 = 115 new (GetAllocator()) HArraySet(array, add1, add2, DataType::Type::kInt32, 0); 116 HInstruction* array_get2 = 117 new (GetAllocator()) HArrayGet(array, add1, DataType::Type::kInt32, 0); 118 HInstruction* array_set2 = 119 new (GetAllocator()) HArraySet(array, add1, add2, DataType::Type::kInt32, 0); 120 121 DCHECK(div_check->CanThrow()); 122 123 entry->AddInstruction(array); 124 125 HInstruction* block_instructions[] = {add1, 126 add2, 127 mul, 128 div_check, 129 div, 130 array_get1, 131 array_set1, 132 array_get2, 133 array_set2}; 134 for (HInstruction* instr : block_instructions) { 135 block1->AddInstruction(instr); 136 } 137 138 HEnvironment* environment = new (GetAllocator()) HEnvironment(GetAllocator(), 139 2, 140 graph_->GetArtMethod(), 141 0, 142 div_check); 143 div_check->SetRawEnvironment(environment); 144 environment->SetRawEnvAt(0, add2); 145 add2->AddEnvUseAt(div_check->GetEnvironment(), 0); 146 environment->SetRawEnvAt(1, mul); 147 mul->AddEnvUseAt(div_check->GetEnvironment(), 1); 148 149 SchedulingGraph scheduling_graph(scheduler, GetScopedAllocator()); 150 // Instructions must be inserted in reverse order into the scheduling graph. 151 for (HInstruction* instr : ReverseRange(block_instructions)) { 152 scheduling_graph.AddNode(instr); 153 } 154 155 // Should not have dependencies cross basic blocks. 156 ASSERT_FALSE(scheduling_graph.HasImmediateDataDependency(add1, c1)); 157 ASSERT_FALSE(scheduling_graph.HasImmediateDataDependency(add2, c2)); 158 159 // Define-use dependency. 160 ASSERT_TRUE(scheduling_graph.HasImmediateDataDependency(add2, add1)); 161 ASSERT_FALSE(scheduling_graph.HasImmediateDataDependency(add1, add2)); 162 ASSERT_TRUE(scheduling_graph.HasImmediateDataDependency(div_check, add2)); 163 ASSERT_FALSE(scheduling_graph.HasImmediateDataDependency(div_check, add1)); 164 ASSERT_TRUE(scheduling_graph.HasImmediateDataDependency(div, div_check)); 165 ASSERT_TRUE(scheduling_graph.HasImmediateDataDependency(array_set1, add1)); 166 ASSERT_TRUE(scheduling_graph.HasImmediateDataDependency(array_set1, add2)); 167 168 // Read and write dependencies 169 ASSERT_TRUE(scheduling_graph.HasImmediateOtherDependency(array_set1, array_get1)); 170 ASSERT_TRUE(scheduling_graph.HasImmediateOtherDependency(array_set2, array_get2)); 171 ASSERT_TRUE(scheduling_graph.HasImmediateOtherDependency(array_get2, array_set1)); 172 ASSERT_TRUE(scheduling_graph.HasImmediateOtherDependency(array_set2, array_set1)); 173 174 // Env dependency. 175 ASSERT_TRUE(scheduling_graph.HasImmediateOtherDependency(div_check, mul)); 176 ASSERT_FALSE(scheduling_graph.HasImmediateOtherDependency(mul, div_check)); 177 178 // CanThrow. 179 ASSERT_TRUE(scheduling_graph.HasImmediateOtherDependency(array_set1, div_check)); 180 181 // Exercise the code path of target specific scheduler and SchedulingLatencyVisitor. 182 scheduler->Schedule(graph_); 183 } 184 185 void CompileWithRandomSchedulerAndRun(const std::vector<uint16_t>& data, 186 bool has_result, 187 int expected) { 188 for (CodegenTargetConfig target_config : GetTargetConfigs()) { 189 HGraph* graph = CreateCFG(data); 190 191 // Schedule the graph randomly. 192 HInstructionScheduling scheduling(graph, target_config.GetInstructionSet()); 193 scheduling.Run(/*only_optimize_loop_blocks*/ false, /*schedule_randomly*/ true); 194 195 RunCode(target_config, 196 graph, 197 [](HGraph* graph_arg) { RemoveSuspendChecks(graph_arg); }, 198 has_result, expected); 199 } 200 } 201 202 void TestDependencyGraphOnAliasingArrayAccesses(HScheduler* scheduler) { 203 HBasicBlock* entry = new (GetAllocator()) HBasicBlock(graph_); 204 graph_->AddBlock(entry); 205 graph_->SetEntryBlock(entry); 206 graph_->BuildDominatorTree(); 207 208 HInstruction* arr = new (GetAllocator()) HParameterValue(graph_->GetDexFile(), 209 dex::TypeIndex(0), 210 0, 211 DataType::Type::kReference); 212 HInstruction* i = new (GetAllocator()) HParameterValue(graph_->GetDexFile(), 213 dex::TypeIndex(1), 214 1, 215 DataType::Type::kInt32); 216 HInstruction* j = new (GetAllocator()) HParameterValue(graph_->GetDexFile(), 217 dex::TypeIndex(1), 218 1, 219 DataType::Type::kInt32); 220 HInstruction* object = new (GetAllocator()) HParameterValue(graph_->GetDexFile(), 221 dex::TypeIndex(0), 222 0, 223 DataType::Type::kReference); 224 HInstruction* c0 = graph_->GetIntConstant(0); 225 HInstruction* c1 = graph_->GetIntConstant(1); 226 HInstruction* add0 = new (GetAllocator()) HAdd(DataType::Type::kInt32, i, c0); 227 HInstruction* add1 = new (GetAllocator()) HAdd(DataType::Type::kInt32, i, c1); 228 HInstruction* sub0 = new (GetAllocator()) HSub(DataType::Type::kInt32, i, c0); 229 HInstruction* sub1 = new (GetAllocator()) HSub(DataType::Type::kInt32, i, c1); 230 HInstruction* arr_set_0 = 231 new (GetAllocator()) HArraySet(arr, c0, c0, DataType::Type::kInt32, 0); 232 HInstruction* arr_set_1 = 233 new (GetAllocator()) HArraySet(arr, c1, c0, DataType::Type::kInt32, 0); 234 HInstruction* arr_set_i = new (GetAllocator()) HArraySet(arr, i, c0, DataType::Type::kInt32, 0); 235 HInstruction* arr_set_add0 = 236 new (GetAllocator()) HArraySet(arr, add0, c0, DataType::Type::kInt32, 0); 237 HInstruction* arr_set_add1 = 238 new (GetAllocator()) HArraySet(arr, add1, c0, DataType::Type::kInt32, 0); 239 HInstruction* arr_set_sub0 = 240 new (GetAllocator()) HArraySet(arr, sub0, c0, DataType::Type::kInt32, 0); 241 HInstruction* arr_set_sub1 = 242 new (GetAllocator()) HArraySet(arr, sub1, c0, DataType::Type::kInt32, 0); 243 HInstruction* arr_set_j = new (GetAllocator()) HArraySet(arr, j, c0, DataType::Type::kInt32, 0); 244 HInstanceFieldSet* set_field10 = new (GetAllocator()) HInstanceFieldSet(object, 245 c1, 246 nullptr, 247 DataType::Type::kInt32, 248 MemberOffset(10), 249 false, 250 kUnknownFieldIndex, 251 kUnknownClassDefIndex, 252 graph_->GetDexFile(), 253 0); 254 255 HInstruction* block_instructions[] = {arr, 256 i, 257 j, 258 object, 259 add0, 260 add1, 261 sub0, 262 sub1, 263 arr_set_0, 264 arr_set_1, 265 arr_set_i, 266 arr_set_add0, 267 arr_set_add1, 268 arr_set_sub0, 269 arr_set_sub1, 270 arr_set_j, 271 set_field10}; 272 273 for (HInstruction* instr : block_instructions) { 274 entry->AddInstruction(instr); 275 } 276 277 SchedulingGraph scheduling_graph(scheduler, GetScopedAllocator()); 278 HeapLocationCollector heap_location_collector(graph_); 279 heap_location_collector.VisitBasicBlock(entry); 280 heap_location_collector.BuildAliasingMatrix(); 281 scheduling_graph.SetHeapLocationCollector(heap_location_collector); 282 283 for (HInstruction* instr : ReverseRange(block_instructions)) { 284 // Build scheduling graph with memory access aliasing information 285 // from LSA/heap_location_collector. 286 scheduling_graph.AddNode(instr); 287 } 288 289 // LSA/HeapLocationCollector should see those ArraySet instructions. 290 ASSERT_EQ(heap_location_collector.GetNumberOfHeapLocations(), 9U); 291 ASSERT_TRUE(heap_location_collector.HasHeapStores()); 292 293 // Test queries on HeapLocationCollector's aliasing matrix after load store analysis. 294 // HeapLocationCollector and SchedulingGraph should report consistent relationships. 295 size_t loc1 = HeapLocationCollector::kHeapLocationNotFound; 296 size_t loc2 = HeapLocationCollector::kHeapLocationNotFound; 297 298 // Test side effect dependency: array[0] and array[1] 299 loc1 = heap_location_collector.GetArrayHeapLocation(arr, c0); 300 loc2 = heap_location_collector.GetArrayHeapLocation(arr, c1); 301 ASSERT_FALSE(heap_location_collector.MayAlias(loc1, loc2)); 302 ASSERT_FALSE(scheduling_graph.HasImmediateOtherDependency(arr_set_1, arr_set_0)); 303 304 // Test side effect dependency based on LSA analysis: array[i] and array[j] 305 loc1 = heap_location_collector.GetArrayHeapLocation(arr, i); 306 loc2 = heap_location_collector.GetArrayHeapLocation(arr, j); 307 ASSERT_TRUE(heap_location_collector.MayAlias(loc1, loc2)); 308 ASSERT_TRUE(scheduling_graph.HasImmediateOtherDependency(arr_set_j, arr_set_i)); 309 310 // Test side effect dependency based on LSA analysis: array[i] and array[i+0] 311 loc1 = heap_location_collector.GetArrayHeapLocation(arr, i); 312 loc2 = heap_location_collector.GetArrayHeapLocation(arr, add0); 313 ASSERT_TRUE(heap_location_collector.MayAlias(loc1, loc2)); 314 ASSERT_TRUE(scheduling_graph.HasImmediateOtherDependency(arr_set_add0, arr_set_i)); 315 316 // Test side effect dependency based on LSA analysis: array[i] and array[i-0] 317 loc1 = heap_location_collector.GetArrayHeapLocation(arr, i); 318 loc2 = heap_location_collector.GetArrayHeapLocation(arr, sub0); 319 ASSERT_TRUE(heap_location_collector.MayAlias(loc1, loc2)); 320 ASSERT_TRUE(scheduling_graph.HasImmediateOtherDependency(arr_set_sub0, arr_set_i)); 321 322 // Test side effect dependency based on LSA analysis: array[i] and array[i+1] 323 loc1 = heap_location_collector.GetArrayHeapLocation(arr, i); 324 loc2 = heap_location_collector.GetArrayHeapLocation(arr, add1); 325 ASSERT_FALSE(heap_location_collector.MayAlias(loc1, loc2)); 326 ASSERT_FALSE(scheduling_graph.HasImmediateOtherDependency(arr_set_add1, arr_set_i)); 327 328 // Test side effect dependency based on LSA analysis: array[i+1] and array[i-1] 329 loc1 = heap_location_collector.GetArrayHeapLocation(arr, add1); 330 loc2 = heap_location_collector.GetArrayHeapLocation(arr, sub1); 331 ASSERT_FALSE(heap_location_collector.MayAlias(loc1, loc2)); 332 ASSERT_FALSE(scheduling_graph.HasImmediateOtherDependency(arr_set_sub1, arr_set_add1)); 333 334 // Test side effect dependency based on LSA analysis: array[j] and all others array accesses 335 ASSERT_TRUE(scheduling_graph.HasImmediateOtherDependency(arr_set_j, arr_set_i)); 336 ASSERT_TRUE(scheduling_graph.HasImmediateOtherDependency(arr_set_j, arr_set_add0)); 337 ASSERT_TRUE(scheduling_graph.HasImmediateOtherDependency(arr_set_j, arr_set_sub0)); 338 ASSERT_TRUE(scheduling_graph.HasImmediateOtherDependency(arr_set_j, arr_set_add1)); 339 ASSERT_TRUE(scheduling_graph.HasImmediateOtherDependency(arr_set_j, arr_set_sub1)); 340 341 // Test that ArraySet and FieldSet should not have side effect dependency 342 ASSERT_FALSE(scheduling_graph.HasImmediateOtherDependency(arr_set_i, set_field10)); 343 ASSERT_FALSE(scheduling_graph.HasImmediateOtherDependency(arr_set_j, set_field10)); 344 345 // Exercise target specific scheduler and SchedulingLatencyVisitor. 346 scheduler->Schedule(graph_); 347 } 348 349 HGraph* graph_; 350 }; 351 352 #if defined(ART_ENABLE_CODEGEN_arm64) 353 TEST_F(SchedulerTest, DependencyGraphAndSchedulerARM64) { 354 CriticalPathSchedulingNodeSelector critical_path_selector; 355 arm64::HSchedulerARM64 scheduler(GetScopedAllocator(), &critical_path_selector); 356 TestBuildDependencyGraphAndSchedule(&scheduler); 357 } 358 359 TEST_F(SchedulerTest, ArrayAccessAliasingARM64) { 360 CriticalPathSchedulingNodeSelector critical_path_selector; 361 arm64::HSchedulerARM64 scheduler(GetScopedAllocator(), &critical_path_selector); 362 TestDependencyGraphOnAliasingArrayAccesses(&scheduler); 363 } 364 #endif 365 366 #if defined(ART_ENABLE_CODEGEN_arm) 367 TEST_F(SchedulerTest, DependencyGraphAndSchedulerARM) { 368 CriticalPathSchedulingNodeSelector critical_path_selector; 369 arm::SchedulingLatencyVisitorARM arm_latency_visitor(/*CodeGenerator*/ nullptr); 370 arm::HSchedulerARM scheduler(GetScopedAllocator(), &critical_path_selector, &arm_latency_visitor); 371 TestBuildDependencyGraphAndSchedule(&scheduler); 372 } 373 374 TEST_F(SchedulerTest, ArrayAccessAliasingARM) { 375 CriticalPathSchedulingNodeSelector critical_path_selector; 376 arm::SchedulingLatencyVisitorARM arm_latency_visitor(/*CodeGenerator*/ nullptr); 377 arm::HSchedulerARM scheduler(GetScopedAllocator(), &critical_path_selector, &arm_latency_visitor); 378 TestDependencyGraphOnAliasingArrayAccesses(&scheduler); 379 } 380 #endif 381 382 TEST_F(SchedulerTest, RandomScheduling) { 383 // 384 // Java source: crafted code to make sure (random) scheduling should get correct result. 385 // 386 // int result = 0; 387 // float fr = 10.0f; 388 // for (int i = 1; i < 10; i++) { 389 // fr ++; 390 // int t1 = result >> i; 391 // int t2 = result * i; 392 // result = result + t1 - t2; 393 // fr = fr / i; 394 // result += (int)fr; 395 // } 396 // return result; 397 // 398 const std::vector<uint16_t> data = SIX_REGISTERS_CODE_ITEM( 399 Instruction::CONST_4 | 0 << 12 | 2 << 8, // const/4 v2, #int 0 400 Instruction::CONST_HIGH16 | 0 << 8, 0x4120, // const/high16 v0, #float 10.0 // #41200000 401 Instruction::CONST_4 | 1 << 12 | 1 << 8, // const/4 v1, #int 1 402 Instruction::CONST_16 | 5 << 8, 0x000a, // const/16 v5, #int 10 403 Instruction::IF_GE | 5 << 12 | 1 << 8, 0x0014, // if-ge v1, v5, 001a // +0014 404 Instruction::CONST_HIGH16 | 5 << 8, 0x3f80, // const/high16 v5, #float 1.0 // #3f800000 405 Instruction::ADD_FLOAT_2ADDR | 5 << 12 | 0 << 8, // add-float/2addr v0, v5 406 Instruction::SHR_INT | 3 << 8, 1 << 8 | 2 , // shr-int v3, v2, v1 407 Instruction::MUL_INT | 4 << 8, 1 << 8 | 2, // mul-int v4, v2, v1 408 Instruction::ADD_INT | 5 << 8, 3 << 8 | 2, // add-int v5, v2, v3 409 Instruction::SUB_INT | 2 << 8, 4 << 8 | 5, // sub-int v2, v5, v4 410 Instruction::INT_TO_FLOAT | 1 << 12 | 5 << 8, // int-to-float v5, v1 411 Instruction::DIV_FLOAT_2ADDR | 5 << 12 | 0 << 8, // div-float/2addr v0, v5 412 Instruction::FLOAT_TO_INT | 0 << 12 | 5 << 8, // float-to-int v5, v0 413 Instruction::ADD_INT_2ADDR | 5 << 12 | 2 << 8, // add-int/2addr v2, v5 414 Instruction::ADD_INT_LIT8 | 1 << 8, 1 << 8 | 1, // add-int/lit8 v1, v1, #int 1 // #01 415 Instruction::GOTO | 0xeb << 8, // goto 0004 // -0015 416 Instruction::RETURN | 2 << 8); // return v2 417 418 constexpr int kNumberOfRuns = 10; 419 for (int i = 0; i < kNumberOfRuns; ++i) { 420 CompileWithRandomSchedulerAndRun(data, true, 138774); 421 } 422 } 423 424 } // namespace art 425
