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