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 <string> 18 19 #include "scheduler.h" 20 21 #include "base/scoped_arena_allocator.h" 22 #include "base/scoped_arena_containers.h" 23 #include "data_type-inl.h" 24 #include "prepare_for_register_allocation.h" 25 26 #ifdef ART_ENABLE_CODEGEN_arm64 27 #include "scheduler_arm64.h" 28 #endif 29 30 #ifdef ART_ENABLE_CODEGEN_arm 31 #include "scheduler_arm.h" 32 #endif 33 34 namespace art { 35 36 void SchedulingGraph::AddDependency(SchedulingNode* node, 37 SchedulingNode* dependency, 38 bool is_data_dependency) { 39 if (node == nullptr || dependency == nullptr) { 40 // A `nullptr` node indicates an instruction out of scheduling range (eg. in 41 // an other block), so we do not need to add a dependency edge to the graph. 42 return; 43 } 44 45 if (is_data_dependency) { 46 if (!HasImmediateDataDependency(node, dependency)) { 47 node->AddDataPredecessor(dependency); 48 } 49 } else if (!HasImmediateOtherDependency(node, dependency)) { 50 node->AddOtherPredecessor(dependency); 51 } 52 } 53 54 static bool MayHaveReorderingDependency(SideEffects node, SideEffects other) { 55 // Read after write. 56 if (node.MayDependOn(other)) { 57 return true; 58 } 59 60 // Write after read. 61 if (other.MayDependOn(node)) { 62 return true; 63 } 64 65 // Memory write after write. 66 if (node.DoesAnyWrite() && other.DoesAnyWrite()) { 67 return true; 68 } 69 70 return false; 71 } 72 73 size_t SchedulingGraph::ArrayAccessHeapLocation(HInstruction* array, HInstruction* index) const { 74 DCHECK(heap_location_collector_ != nullptr); 75 size_t heap_loc = heap_location_collector_->GetArrayHeapLocation(array, index); 76 // This array access should be analyzed and added to HeapLocationCollector before. 77 DCHECK(heap_loc != HeapLocationCollector::kHeapLocationNotFound); 78 return heap_loc; 79 } 80 81 bool SchedulingGraph::ArrayAccessMayAlias(const HInstruction* node, 82 const HInstruction* other) const { 83 DCHECK(heap_location_collector_ != nullptr); 84 size_t node_heap_loc = ArrayAccessHeapLocation(node->InputAt(0), node->InputAt(1)); 85 size_t other_heap_loc = ArrayAccessHeapLocation(other->InputAt(0), other->InputAt(1)); 86 87 // For example: arr[0] and arr[0] 88 if (node_heap_loc == other_heap_loc) { 89 return true; 90 } 91 92 // For example: arr[0] and arr[i] 93 if (heap_location_collector_->MayAlias(node_heap_loc, other_heap_loc)) { 94 return true; 95 } 96 97 return false; 98 } 99 100 static bool IsArrayAccess(const HInstruction* instruction) { 101 return instruction->IsArrayGet() || instruction->IsArraySet(); 102 } 103 104 static bool IsInstanceFieldAccess(const HInstruction* instruction) { 105 return instruction->IsInstanceFieldGet() || 106 instruction->IsInstanceFieldSet() || 107 instruction->IsUnresolvedInstanceFieldGet() || 108 instruction->IsUnresolvedInstanceFieldSet(); 109 } 110 111 static bool IsStaticFieldAccess(const HInstruction* instruction) { 112 return instruction->IsStaticFieldGet() || 113 instruction->IsStaticFieldSet() || 114 instruction->IsUnresolvedStaticFieldGet() || 115 instruction->IsUnresolvedStaticFieldSet(); 116 } 117 118 static bool IsResolvedFieldAccess(const HInstruction* instruction) { 119 return instruction->IsInstanceFieldGet() || 120 instruction->IsInstanceFieldSet() || 121 instruction->IsStaticFieldGet() || 122 instruction->IsStaticFieldSet(); 123 } 124 125 static bool IsUnresolvedFieldAccess(const HInstruction* instruction) { 126 return instruction->IsUnresolvedInstanceFieldGet() || 127 instruction->IsUnresolvedInstanceFieldSet() || 128 instruction->IsUnresolvedStaticFieldGet() || 129 instruction->IsUnresolvedStaticFieldSet(); 130 } 131 132 static bool IsFieldAccess(const HInstruction* instruction) { 133 return IsResolvedFieldAccess(instruction) || IsUnresolvedFieldAccess(instruction); 134 } 135 136 static const FieldInfo* GetFieldInfo(const HInstruction* instruction) { 137 if (instruction->IsInstanceFieldGet()) { 138 return &instruction->AsInstanceFieldGet()->GetFieldInfo(); 139 } else if (instruction->IsInstanceFieldSet()) { 140 return &instruction->AsInstanceFieldSet()->GetFieldInfo(); 141 } else if (instruction->IsStaticFieldGet()) { 142 return &instruction->AsStaticFieldGet()->GetFieldInfo(); 143 } else if (instruction->IsStaticFieldSet()) { 144 return &instruction->AsStaticFieldSet()->GetFieldInfo(); 145 } else { 146 LOG(FATAL) << "Unexpected field access type"; 147 UNREACHABLE(); 148 } 149 } 150 151 size_t SchedulingGraph::FieldAccessHeapLocation(HInstruction* obj, const FieldInfo* field) const { 152 DCHECK(obj != nullptr); 153 DCHECK(field != nullptr); 154 DCHECK(heap_location_collector_ != nullptr); 155 156 size_t heap_loc = heap_location_collector_->GetFieldHeapLocation(obj, field); 157 // This field access should be analyzed and added to HeapLocationCollector before. 158 DCHECK(heap_loc != HeapLocationCollector::kHeapLocationNotFound); 159 160 return heap_loc; 161 } 162 163 bool SchedulingGraph::FieldAccessMayAlias(const HInstruction* node, 164 const HInstruction* other) const { 165 DCHECK(heap_location_collector_ != nullptr); 166 167 // Static and instance field accesses should not alias. 168 if ((IsInstanceFieldAccess(node) && IsStaticFieldAccess(other)) || 169 (IsStaticFieldAccess(node) && IsInstanceFieldAccess(other))) { 170 return false; 171 } 172 173 // If either of the field accesses is unresolved. 174 if (IsUnresolvedFieldAccess(node) || IsUnresolvedFieldAccess(other)) { 175 // Conservatively treat these two accesses may alias. 176 return true; 177 } 178 179 // If both fields accesses are resolved. 180 const FieldInfo* node_field = GetFieldInfo(node); 181 const FieldInfo* other_field = GetFieldInfo(other); 182 183 size_t node_loc = FieldAccessHeapLocation(node->InputAt(0), node_field); 184 size_t other_loc = FieldAccessHeapLocation(other->InputAt(0), other_field); 185 186 if (node_loc == other_loc) { 187 return true; 188 } 189 190 if (!heap_location_collector_->MayAlias(node_loc, other_loc)) { 191 return false; 192 } 193 194 return true; 195 } 196 197 bool SchedulingGraph::HasMemoryDependency(const HInstruction* node, 198 const HInstruction* other) const { 199 if (!MayHaveReorderingDependency(node->GetSideEffects(), other->GetSideEffects())) { 200 return false; 201 } 202 203 if (heap_location_collector_ == nullptr || 204 heap_location_collector_->GetNumberOfHeapLocations() == 0) { 205 // Without HeapLocation information from load store analysis, 206 // we cannot do further disambiguation analysis on these two instructions. 207 // Just simply say that those two instructions have memory dependency. 208 return true; 209 } 210 211 if (IsArrayAccess(node) && IsArrayAccess(other)) { 212 return ArrayAccessMayAlias(node, other); 213 } 214 if (IsFieldAccess(node) && IsFieldAccess(other)) { 215 return FieldAccessMayAlias(node, other); 216 } 217 218 // TODO(xueliang): LSA to support alias analysis among HVecLoad, HVecStore and ArrayAccess 219 if (node->IsVecMemoryOperation() && other->IsVecMemoryOperation()) { 220 return true; 221 } 222 if (node->IsVecMemoryOperation() && IsArrayAccess(other)) { 223 return true; 224 } 225 if (IsArrayAccess(node) && other->IsVecMemoryOperation()) { 226 return true; 227 } 228 229 // Heap accesses of different kinds should not alias. 230 if (IsArrayAccess(node) && IsFieldAccess(other)) { 231 return false; 232 } 233 if (IsFieldAccess(node) && IsArrayAccess(other)) { 234 return false; 235 } 236 if (node->IsVecMemoryOperation() && IsFieldAccess(other)) { 237 return false; 238 } 239 if (IsFieldAccess(node) && other->IsVecMemoryOperation()) { 240 return false; 241 } 242 243 // We conservatively treat all other cases having dependency, 244 // for example, Invoke and ArrayGet. 245 return true; 246 } 247 248 bool SchedulingGraph::HasExceptionDependency(const HInstruction* node, 249 const HInstruction* other) const { 250 if (other->CanThrow() && node->GetSideEffects().DoesAnyWrite()) { 251 return true; 252 } 253 if (other->GetSideEffects().DoesAnyWrite() && node->CanThrow()) { 254 return true; 255 } 256 if (other->CanThrow() && node->CanThrow()) { 257 return true; 258 } 259 260 // Above checks should cover all cases where we cannot reorder two 261 // instructions which may throw exception. 262 return false; 263 } 264 265 // Check whether `node` depends on `other`, taking into account `SideEffect` 266 // information and `CanThrow` information. 267 bool SchedulingGraph::HasSideEffectDependency(const HInstruction* node, 268 const HInstruction* other) const { 269 if (HasMemoryDependency(node, other)) { 270 return true; 271 } 272 273 // Even if above memory dependency check has passed, it is still necessary to 274 // check dependencies between instructions that can throw and instructions 275 // that write to memory. 276 if (HasExceptionDependency(node, other)) { 277 return true; 278 } 279 280 return false; 281 } 282 283 void SchedulingGraph::AddDependencies(HInstruction* instruction, bool is_scheduling_barrier) { 284 SchedulingNode* instruction_node = GetNode(instruction); 285 286 // Define-use dependencies. 287 for (const HUseListNode<HInstruction*>& use : instruction->GetUses()) { 288 AddDataDependency(GetNode(use.GetUser()), instruction_node); 289 } 290 291 // Scheduling barrier dependencies. 292 DCHECK(!is_scheduling_barrier || contains_scheduling_barrier_); 293 if (contains_scheduling_barrier_) { 294 // A barrier depends on instructions after it. And instructions before the 295 // barrier depend on it. 296 for (HInstruction* other = instruction->GetNext(); other != nullptr; other = other->GetNext()) { 297 SchedulingNode* other_node = GetNode(other); 298 CHECK(other_node != nullptr) 299 << other->DebugName() 300 << " is in block " << other->GetBlock()->GetBlockId() 301 << ", and expected in block " << instruction->GetBlock()->GetBlockId(); 302 bool other_is_barrier = other_node->IsSchedulingBarrier(); 303 if (is_scheduling_barrier || other_is_barrier) { 304 AddOtherDependency(other_node, instruction_node); 305 } 306 if (other_is_barrier) { 307 // This other scheduling barrier guarantees ordering of instructions after 308 // it, so avoid creating additional useless dependencies in the graph. 309 // For example if we have 310 // instr_1 311 // barrier_2 312 // instr_3 313 // barrier_4 314 // instr_5 315 // we only create the following non-data dependencies 316 // 1 -> 2 317 // 2 -> 3 318 // 2 -> 4 319 // 3 -> 4 320 // 4 -> 5 321 // and do not create 322 // 1 -> 4 323 // 2 -> 5 324 // Note that in this example we could also avoid creating the dependency 325 // `2 -> 4`. But if we remove `instr_3` that dependency is required to 326 // order the barriers. So we generate it to avoid a special case. 327 break; 328 } 329 } 330 } 331 332 // Side effect dependencies. 333 if (!instruction->GetSideEffects().DoesNothing() || instruction->CanThrow()) { 334 for (HInstruction* other = instruction->GetNext(); other != nullptr; other = other->GetNext()) { 335 SchedulingNode* other_node = GetNode(other); 336 if (other_node->IsSchedulingBarrier()) { 337 // We have reached a scheduling barrier so we can stop further 338 // processing. 339 DCHECK(HasImmediateOtherDependency(other_node, instruction_node)); 340 break; 341 } 342 if (HasSideEffectDependency(other, instruction)) { 343 AddOtherDependency(other_node, instruction_node); 344 } 345 } 346 } 347 348 // Environment dependencies. 349 // We do not need to process those if the instruction is a scheduling barrier, 350 // since the barrier already has non-data dependencies on all following 351 // instructions. 352 if (!is_scheduling_barrier) { 353 for (const HUseListNode<HEnvironment*>& use : instruction->GetEnvUses()) { 354 // Note that here we could stop processing if the environment holder is 355 // across a scheduling barrier. But checking this would likely require 356 // more work than simply iterating through environment uses. 357 AddOtherDependency(GetNode(use.GetUser()->GetHolder()), instruction_node); 358 } 359 } 360 } 361 362 bool SchedulingGraph::HasImmediateDataDependency(const SchedulingNode* node, 363 const SchedulingNode* other) const { 364 return ContainsElement(node->GetDataPredecessors(), other); 365 } 366 367 bool SchedulingGraph::HasImmediateDataDependency(const HInstruction* instruction, 368 const HInstruction* other_instruction) const { 369 const SchedulingNode* node = GetNode(instruction); 370 const SchedulingNode* other = GetNode(other_instruction); 371 if (node == nullptr || other == nullptr) { 372 // Both instructions must be in current basic block, i.e. the SchedulingGraph can see their 373 // corresponding SchedulingNode in the graph, and tell whether there is a dependency. 374 // Otherwise there is no dependency from SchedulingGraph's perspective, for example, 375 // instruction and other_instruction are in different basic blocks. 376 return false; 377 } 378 return HasImmediateDataDependency(node, other); 379 } 380 381 bool SchedulingGraph::HasImmediateOtherDependency(const SchedulingNode* node, 382 const SchedulingNode* other) const { 383 return ContainsElement(node->GetOtherPredecessors(), other); 384 } 385 386 bool SchedulingGraph::HasImmediateOtherDependency(const HInstruction* instruction, 387 const HInstruction* other_instruction) const { 388 const SchedulingNode* node = GetNode(instruction); 389 const SchedulingNode* other = GetNode(other_instruction); 390 if (node == nullptr || other == nullptr) { 391 // Both instructions must be in current basic block, i.e. the SchedulingGraph can see their 392 // corresponding SchedulingNode in the graph, and tell whether there is a dependency. 393 // Otherwise there is no dependency from SchedulingGraph's perspective, for example, 394 // instruction and other_instruction are in different basic blocks. 395 return false; 396 } 397 return HasImmediateOtherDependency(node, other); 398 } 399 400 static const std::string InstructionTypeId(const HInstruction* instruction) { 401 return DataType::TypeId(instruction->GetType()) + std::to_string(instruction->GetId()); 402 } 403 404 // Ideally we would reuse the graph visualizer code, but it is not available 405 // from here and it is not worth moving all that code only for our use. 406 static void DumpAsDotNode(std::ostream& output, const SchedulingNode* node) { 407 const HInstruction* instruction = node->GetInstruction(); 408 // Use the instruction typed id as the node identifier. 409 std::string instruction_id = InstructionTypeId(instruction); 410 output << instruction_id << "[shape=record, label=\"" 411 << instruction_id << ' ' << instruction->DebugName() << " ["; 412 // List the instruction's inputs in its description. When visualizing the 413 // graph this helps differentiating data inputs from other dependencies. 414 const char* seperator = ""; 415 for (const HInstruction* input : instruction->GetInputs()) { 416 output << seperator << InstructionTypeId(input); 417 seperator = ","; 418 } 419 output << "]"; 420 // Other properties of the node. 421 output << "\\ninternal_latency: " << node->GetInternalLatency(); 422 output << "\\ncritical_path: " << node->GetCriticalPath(); 423 if (node->IsSchedulingBarrier()) { 424 output << "\\n(barrier)"; 425 } 426 output << "\"];\n"; 427 // We want program order to go from top to bottom in the graph output, so we 428 // reverse the edges and specify `dir=back`. 429 for (const SchedulingNode* predecessor : node->GetDataPredecessors()) { 430 const HInstruction* predecessor_instruction = predecessor->GetInstruction(); 431 output << InstructionTypeId(predecessor_instruction) << ":s -> " << instruction_id << ":n " 432 << "[label=\"" << predecessor->GetLatency() << "\",dir=back]\n"; 433 } 434 for (const SchedulingNode* predecessor : node->GetOtherPredecessors()) { 435 const HInstruction* predecessor_instruction = predecessor->GetInstruction(); 436 output << InstructionTypeId(predecessor_instruction) << ":s -> " << instruction_id << ":n " 437 << "[dir=back,color=blue]\n"; 438 } 439 } 440 441 void SchedulingGraph::DumpAsDotGraph(const std::string& description, 442 const ScopedArenaVector<SchedulingNode*>& initial_candidates) { 443 // TODO(xueliang): ideally we should move scheduling information into HInstruction, after that 444 // we should move this dotty graph dump feature to visualizer, and have a compiler option for it. 445 std::ofstream output("scheduling_graphs.dot", std::ofstream::out | std::ofstream::app); 446 // Description of this graph, as a comment. 447 output << "// " << description << "\n"; 448 // Start the dot graph. Use an increasing index for easier differentiation. 449 output << "digraph G {\n"; 450 for (const auto& entry : nodes_map_) { 451 SchedulingNode* node = entry.second.get(); 452 DumpAsDotNode(output, node); 453 } 454 // Create a fake 'end_of_scheduling' node to help visualization of critical_paths. 455 for (SchedulingNode* node : initial_candidates) { 456 const HInstruction* instruction = node->GetInstruction(); 457 output << InstructionTypeId(instruction) << ":s -> end_of_scheduling:n " 458 << "[label=\"" << node->GetLatency() << "\",dir=back]\n"; 459 } 460 // End of the dot graph. 461 output << "}\n"; 462 output.close(); 463 } 464 465 SchedulingNode* CriticalPathSchedulingNodeSelector::SelectMaterializedCondition( 466 ScopedArenaVector<SchedulingNode*>* nodes, const SchedulingGraph& graph) const { 467 // Schedule condition inputs that can be materialized immediately before their use. 468 // In following example, after we've scheduled HSelect, we want LessThan to be scheduled 469 // immediately, because it is a materialized condition, and will be emitted right before HSelect 470 // in codegen phase. 471 // 472 // i20 HLessThan [...] HLessThan HAdd HAdd 473 // i21 HAdd [...] ===> | | | 474 // i22 HAdd [...] +----------+---------+ 475 // i23 HSelect [i21, i22, i20] HSelect 476 477 if (prev_select_ == nullptr) { 478 return nullptr; 479 } 480 481 const HInstruction* instruction = prev_select_->GetInstruction(); 482 const HCondition* condition = nullptr; 483 DCHECK(instruction != nullptr); 484 485 if (instruction->IsIf()) { 486 condition = instruction->AsIf()->InputAt(0)->AsCondition(); 487 } else if (instruction->IsSelect()) { 488 condition = instruction->AsSelect()->GetCondition()->AsCondition(); 489 } 490 491 SchedulingNode* condition_node = (condition != nullptr) ? graph.GetNode(condition) : nullptr; 492 493 if ((condition_node != nullptr) && 494 condition->HasOnlyOneNonEnvironmentUse() && 495 ContainsElement(*nodes, condition_node)) { 496 DCHECK(!condition_node->HasUnscheduledSuccessors()); 497 // Remove the condition from the list of candidates and schedule it. 498 RemoveElement(*nodes, condition_node); 499 return condition_node; 500 } 501 502 return nullptr; 503 } 504 505 SchedulingNode* CriticalPathSchedulingNodeSelector::PopHighestPriorityNode( 506 ScopedArenaVector<SchedulingNode*>* nodes, const SchedulingGraph& graph) { 507 DCHECK(!nodes->empty()); 508 SchedulingNode* select_node = nullptr; 509 510 // Optimize for materialized condition and its emit before use scenario. 511 select_node = SelectMaterializedCondition(nodes, graph); 512 513 if (select_node == nullptr) { 514 // Get highest priority node based on critical path information. 515 select_node = (*nodes)[0]; 516 size_t select = 0; 517 for (size_t i = 1, e = nodes->size(); i < e; i++) { 518 SchedulingNode* check = (*nodes)[i]; 519 SchedulingNode* candidate = (*nodes)[select]; 520 select_node = GetHigherPrioritySchedulingNode(candidate, check); 521 if (select_node == check) { 522 select = i; 523 } 524 } 525 DeleteNodeAtIndex(nodes, select); 526 } 527 528 prev_select_ = select_node; 529 return select_node; 530 } 531 532 SchedulingNode* CriticalPathSchedulingNodeSelector::GetHigherPrioritySchedulingNode( 533 SchedulingNode* candidate, SchedulingNode* check) const { 534 uint32_t candidate_path = candidate->GetCriticalPath(); 535 uint32_t check_path = check->GetCriticalPath(); 536 // First look at the critical_path. 537 if (check_path != candidate_path) { 538 return check_path < candidate_path ? check : candidate; 539 } 540 // If both critical paths are equal, schedule instructions with a higher latency 541 // first in program order. 542 return check->GetLatency() < candidate->GetLatency() ? check : candidate; 543 } 544 545 void HScheduler::Schedule(HGraph* graph) { 546 // We run lsa here instead of in a separate pass to better control whether we 547 // should run the analysis or not. 548 LoadStoreAnalysis lsa(graph); 549 if (!only_optimize_loop_blocks_ || graph->HasLoops()) { 550 lsa.Run(); 551 scheduling_graph_.SetHeapLocationCollector(lsa.GetHeapLocationCollector()); 552 } 553 554 for (HBasicBlock* block : graph->GetReversePostOrder()) { 555 if (IsSchedulable(block)) { 556 Schedule(block); 557 } 558 } 559 } 560 561 void HScheduler::Schedule(HBasicBlock* block) { 562 ScopedArenaVector<SchedulingNode*> scheduling_nodes(allocator_->Adapter(kArenaAllocScheduler)); 563 564 // Build the scheduling graph. 565 scheduling_graph_.Clear(); 566 for (HBackwardInstructionIterator it(block->GetInstructions()); !it.Done(); it.Advance()) { 567 HInstruction* instruction = it.Current(); 568 CHECK_EQ(instruction->GetBlock(), block) 569 << instruction->DebugName() 570 << " is in block " << instruction->GetBlock()->GetBlockId() 571 << ", and expected in block " << block->GetBlockId(); 572 SchedulingNode* node = scheduling_graph_.AddNode(instruction, IsSchedulingBarrier(instruction)); 573 CalculateLatency(node); 574 scheduling_nodes.push_back(node); 575 } 576 577 if (scheduling_graph_.Size() <= 1) { 578 scheduling_graph_.Clear(); 579 return; 580 } 581 582 cursor_ = block->GetLastInstruction(); 583 584 // Find the initial candidates for scheduling. 585 candidates_.clear(); 586 for (SchedulingNode* node : scheduling_nodes) { 587 if (!node->HasUnscheduledSuccessors()) { 588 node->MaybeUpdateCriticalPath(node->GetLatency()); 589 candidates_.push_back(node); 590 } 591 } 592 593 ScopedArenaVector<SchedulingNode*> initial_candidates(allocator_->Adapter(kArenaAllocScheduler)); 594 if (kDumpDotSchedulingGraphs) { 595 // Remember the list of initial candidates for debug output purposes. 596 initial_candidates.assign(candidates_.begin(), candidates_.end()); 597 } 598 599 // Schedule all nodes. 600 while (!candidates_.empty()) { 601 Schedule(selector_->PopHighestPriorityNode(&candidates_, scheduling_graph_)); 602 } 603 604 if (kDumpDotSchedulingGraphs) { 605 // Dump the graph in `dot` format. 606 HGraph* graph = block->GetGraph(); 607 std::stringstream description; 608 description << graph->GetDexFile().PrettyMethod(graph->GetMethodIdx()) 609 << " B" << block->GetBlockId(); 610 scheduling_graph_.DumpAsDotGraph(description.str(), initial_candidates); 611 } 612 } 613 614 void HScheduler::Schedule(SchedulingNode* scheduling_node) { 615 // Check whether any of the node's predecessors will be valid candidates after 616 // this node is scheduled. 617 uint32_t path_to_node = scheduling_node->GetCriticalPath(); 618 for (SchedulingNode* predecessor : scheduling_node->GetDataPredecessors()) { 619 predecessor->MaybeUpdateCriticalPath( 620 path_to_node + predecessor->GetInternalLatency() + predecessor->GetLatency()); 621 predecessor->DecrementNumberOfUnscheduledSuccessors(); 622 if (!predecessor->HasUnscheduledSuccessors()) { 623 candidates_.push_back(predecessor); 624 } 625 } 626 for (SchedulingNode* predecessor : scheduling_node->GetOtherPredecessors()) { 627 // Do not update the critical path. 628 // The 'other' (so 'non-data') dependencies (usually) do not represent a 629 // 'material' dependency of nodes on others. They exist for program 630 // correctness. So we do not use them to compute the critical path. 631 predecessor->DecrementNumberOfUnscheduledSuccessors(); 632 if (!predecessor->HasUnscheduledSuccessors()) { 633 candidates_.push_back(predecessor); 634 } 635 } 636 637 Schedule(scheduling_node->GetInstruction()); 638 } 639 640 // Move an instruction after cursor instruction inside one basic block. 641 static void MoveAfterInBlock(HInstruction* instruction, HInstruction* cursor) { 642 DCHECK_EQ(instruction->GetBlock(), cursor->GetBlock()); 643 DCHECK_NE(cursor, cursor->GetBlock()->GetLastInstruction()); 644 DCHECK(!instruction->IsControlFlow()); 645 DCHECK(!cursor->IsControlFlow()); 646 instruction->MoveBefore(cursor->GetNext(), /* do_checks */ false); 647 } 648 649 void HScheduler::Schedule(HInstruction* instruction) { 650 if (instruction == cursor_) { 651 cursor_ = cursor_->GetPrevious(); 652 } else { 653 MoveAfterInBlock(instruction, cursor_); 654 } 655 } 656 657 bool HScheduler::IsSchedulable(const HInstruction* instruction) const { 658 // We want to avoid exhaustively listing all instructions, so we first check 659 // for instruction categories that we know are safe. 660 if (instruction->IsControlFlow() || 661 instruction->IsConstant()) { 662 return true; 663 } 664 // Currently all unary and binary operations are safe to schedule, so avoid 665 // checking for each of them individually. 666 // Since nothing prevents a new scheduling-unsafe HInstruction to subclass 667 // HUnaryOperation (or HBinaryOperation), check in debug mode that we have 668 // the exhaustive lists here. 669 if (instruction->IsUnaryOperation()) { 670 DCHECK(instruction->IsBooleanNot() || 671 instruction->IsNot() || 672 instruction->IsNeg()) << "unexpected instruction " << instruction->DebugName(); 673 return true; 674 } 675 if (instruction->IsBinaryOperation()) { 676 DCHECK(instruction->IsAdd() || 677 instruction->IsAnd() || 678 instruction->IsCompare() || 679 instruction->IsCondition() || 680 instruction->IsDiv() || 681 instruction->IsMul() || 682 instruction->IsOr() || 683 instruction->IsRem() || 684 instruction->IsRor() || 685 instruction->IsShl() || 686 instruction->IsShr() || 687 instruction->IsSub() || 688 instruction->IsUShr() || 689 instruction->IsXor()) << "unexpected instruction " << instruction->DebugName(); 690 return true; 691 } 692 // The scheduler should not see any of these. 693 DCHECK(!instruction->IsParallelMove()) << "unexpected instruction " << instruction->DebugName(); 694 // List of instructions explicitly excluded: 695 // HClearException 696 // HClinitCheck 697 // HDeoptimize 698 // HLoadClass 699 // HLoadException 700 // HMemoryBarrier 701 // HMonitorOperation 702 // HNativeDebugInfo 703 // HThrow 704 // HTryBoundary 705 // TODO: Some of the instructions above may be safe to schedule (maybe as 706 // scheduling barriers). 707 return instruction->IsArrayGet() || 708 instruction->IsArraySet() || 709 instruction->IsArrayLength() || 710 instruction->IsBoundType() || 711 instruction->IsBoundsCheck() || 712 instruction->IsCheckCast() || 713 instruction->IsClassTableGet() || 714 instruction->IsCurrentMethod() || 715 instruction->IsDivZeroCheck() || 716 (instruction->IsInstanceFieldGet() && !instruction->AsInstanceFieldGet()->IsVolatile()) || 717 (instruction->IsInstanceFieldSet() && !instruction->AsInstanceFieldSet()->IsVolatile()) || 718 instruction->IsInstanceOf() || 719 instruction->IsInvokeInterface() || 720 instruction->IsInvokeStaticOrDirect() || 721 instruction->IsInvokeUnresolved() || 722 instruction->IsInvokeVirtual() || 723 instruction->IsLoadString() || 724 instruction->IsNewArray() || 725 instruction->IsNewInstance() || 726 instruction->IsNullCheck() || 727 instruction->IsPackedSwitch() || 728 instruction->IsParameterValue() || 729 instruction->IsPhi() || 730 instruction->IsReturn() || 731 instruction->IsReturnVoid() || 732 instruction->IsSelect() || 733 (instruction->IsStaticFieldGet() && !instruction->AsStaticFieldGet()->IsVolatile()) || 734 (instruction->IsStaticFieldSet() && !instruction->AsStaticFieldSet()->IsVolatile()) || 735 instruction->IsSuspendCheck() || 736 instruction->IsTypeConversion(); 737 } 738 739 bool HScheduler::IsSchedulable(const HBasicBlock* block) const { 740 // We may be only interested in loop blocks. 741 if (only_optimize_loop_blocks_ && !block->IsInLoop()) { 742 return false; 743 } 744 if (block->GetTryCatchInformation() != nullptr) { 745 // Do not schedule blocks that are part of try-catch. 746 // Because scheduler cannot see if catch block has assumptions on the instruction order in 747 // the try block. In following example, if we enable scheduler for the try block, 748 // MulitiplyAccumulate may be scheduled before DivZeroCheck, 749 // which can result in an incorrect value in the catch block. 750 // try { 751 // a = a/b; // DivZeroCheck 752 // // Div 753 // c = c*d+e; // MulitiplyAccumulate 754 // } catch {System.out.print(c); } 755 return false; 756 } 757 // Check whether all instructions in this block are schedulable. 758 for (HInstructionIterator it(block->GetInstructions()); !it.Done(); it.Advance()) { 759 if (!IsSchedulable(it.Current())) { 760 return false; 761 } 762 } 763 return true; 764 } 765 766 bool HScheduler::IsSchedulingBarrier(const HInstruction* instr) const { 767 return instr->IsControlFlow() || 768 // Don't break calling convention. 769 instr->IsParameterValue() || 770 // Code generation of goto relies on SuspendCheck's position. 771 instr->IsSuspendCheck(); 772 } 773 774 void HInstructionScheduling::Run(bool only_optimize_loop_blocks, 775 bool schedule_randomly) { 776 #if defined(ART_ENABLE_CODEGEN_arm64) || defined(ART_ENABLE_CODEGEN_arm) 777 // Phase-local allocator that allocates scheduler internal data structures like 778 // scheduling nodes, internel nodes map, dependencies, etc. 779 ScopedArenaAllocator allocator(graph_->GetArenaStack()); 780 CriticalPathSchedulingNodeSelector critical_path_selector; 781 RandomSchedulingNodeSelector random_selector; 782 SchedulingNodeSelector* selector = schedule_randomly 783 ? static_cast<SchedulingNodeSelector*>(&random_selector) 784 : static_cast<SchedulingNodeSelector*>(&critical_path_selector); 785 #else 786 // Avoid compilation error when compiling for unsupported instruction set. 787 UNUSED(only_optimize_loop_blocks); 788 UNUSED(schedule_randomly); 789 UNUSED(codegen_); 790 #endif 791 792 switch (instruction_set_) { 793 #ifdef ART_ENABLE_CODEGEN_arm64 794 case InstructionSet::kArm64: { 795 arm64::HSchedulerARM64 scheduler(&allocator, selector); 796 scheduler.SetOnlyOptimizeLoopBlocks(only_optimize_loop_blocks); 797 scheduler.Schedule(graph_); 798 break; 799 } 800 #endif 801 #if defined(ART_ENABLE_CODEGEN_arm) 802 case InstructionSet::kThumb2: 803 case InstructionSet::kArm: { 804 arm::SchedulingLatencyVisitorARM arm_latency_visitor(codegen_); 805 arm::HSchedulerARM scheduler(&allocator, selector, &arm_latency_visitor); 806 scheduler.SetOnlyOptimizeLoopBlocks(only_optimize_loop_blocks); 807 scheduler.Schedule(graph_); 808 break; 809 } 810 #endif 811 default: 812 break; 813 } 814 } 815 816 } // namespace art 817