| OLD | NEW |
| 1 // Copyright 2013 the V8 project authors. All rights reserved. | 1 // Copyright 2013 the V8 project authors. All rights reserved. |
| 2 // Use of this source code is governed by a BSD-style license that can be | 2 // Use of this source code is governed by a BSD-style license that can be |
| 3 // found in the LICENSE file. | 3 // found in the LICENSE file. |
| 4 | 4 |
| 5 #include "src/compiler/scheduler.h" | 5 #include "src/compiler/scheduler.h" |
| 6 | 6 |
| 7 #include <iomanip> | 7 #include <iomanip> |
| 8 | 8 |
| 9 #include "src/bit-vector.h" | 9 #include "src/bit-vector.h" |
| 10 #include "src/compiler/common-operator.h" | 10 #include "src/compiler/common-operator.h" |
| 11 #include "src/compiler/control-equivalence.h" | 11 #include "src/compiler/control-equivalence.h" |
| 12 #include "src/compiler/graph.h" | 12 #include "src/compiler/graph.h" |
| 13 #include "src/compiler/node.h" | 13 #include "src/compiler/node.h" |
| 14 #include "src/compiler/node-marker.h" | 14 #include "src/compiler/node-marker.h" |
| 15 #include "src/compiler/node-properties.h" | 15 #include "src/compiler/node-properties.h" |
| 16 #include "src/zone-containers.h" | 16 #include "src/zone-containers.h" |
| 17 | 17 |
| 18 namespace v8 { | 18 namespace v8 { |
| 19 namespace internal { | 19 namespace internal { |
| 20 namespace compiler { | 20 namespace compiler { |
| 21 | 21 |
| 22 static inline void Trace(const char* msg, ...) { | 22 #define TRACE(...) \ |
| 23 if (FLAG_trace_turbo_scheduler) { | 23 do { \ |
| 24 va_list arguments; | 24 if (FLAG_trace_turbo_scheduler) PrintF(__VA_ARGS__); \ |
| 25 va_start(arguments, msg); | 25 } while (false) |
| 26 base::OS::VPrint(msg, arguments); | |
| 27 va_end(arguments); | |
| 28 } | |
| 29 } | |
| 30 | |
| 31 | 26 |
| 32 Scheduler::Scheduler(Zone* zone, Graph* graph, Schedule* schedule, Flags flags) | 27 Scheduler::Scheduler(Zone* zone, Graph* graph, Schedule* schedule, Flags flags) |
| 33 : zone_(zone), | 28 : zone_(zone), |
| 34 graph_(graph), | 29 graph_(graph), |
| 35 schedule_(schedule), | 30 schedule_(schedule), |
| 36 flags_(flags), | 31 flags_(flags), |
| 37 scheduled_nodes_(zone), | 32 scheduled_nodes_(zone), |
| 38 schedule_root_nodes_(zone), | 33 schedule_root_nodes_(zone), |
| 39 schedule_queue_(zone), | 34 schedule_queue_(zone), |
| 40 node_data_(graph_->NodeCount(), DefaultSchedulerData(), zone) {} | 35 node_data_(graph_->NodeCount(), DefaultSchedulerData(), zone) {} |
| (...skipping 125 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 166 if (GetPlacement(node) == kFixed) return; | 161 if (GetPlacement(node) == kFixed) return; |
| 167 | 162 |
| 168 // Use count for coupled nodes is summed up on their control. | 163 // Use count for coupled nodes is summed up on their control. |
| 169 if (GetPlacement(node) == kCoupled) { | 164 if (GetPlacement(node) == kCoupled) { |
| 170 Node* control = NodeProperties::GetControlInput(node); | 165 Node* control = NodeProperties::GetControlInput(node); |
| 171 return IncrementUnscheduledUseCount(control, index, from); | 166 return IncrementUnscheduledUseCount(control, index, from); |
| 172 } | 167 } |
| 173 | 168 |
| 174 ++(GetData(node)->unscheduled_count_); | 169 ++(GetData(node)->unscheduled_count_); |
| 175 if (FLAG_trace_turbo_scheduler) { | 170 if (FLAG_trace_turbo_scheduler) { |
| 176 Trace(" Use count of #%d:%s (used by #%d:%s)++ = %d\n", node->id(), | 171 TRACE(" Use count of #%d:%s (used by #%d:%s)++ = %d\n", node->id(), |
| 177 node->op()->mnemonic(), from->id(), from->op()->mnemonic(), | 172 node->op()->mnemonic(), from->id(), from->op()->mnemonic(), |
| 178 GetData(node)->unscheduled_count_); | 173 GetData(node)->unscheduled_count_); |
| 179 } | 174 } |
| 180 } | 175 } |
| 181 | 176 |
| 182 | 177 |
| 183 void Scheduler::DecrementUnscheduledUseCount(Node* node, int index, | 178 void Scheduler::DecrementUnscheduledUseCount(Node* node, int index, |
| 184 Node* from) { | 179 Node* from) { |
| 185 // Make sure that control edges from coupled nodes are not counted. | 180 // Make sure that control edges from coupled nodes are not counted. |
| 186 if (IsCoupledControlEdge(from, index)) return; | 181 if (IsCoupledControlEdge(from, index)) return; |
| 187 | 182 |
| 188 // Tracking use counts for fixed nodes is useless. | 183 // Tracking use counts for fixed nodes is useless. |
| 189 if (GetPlacement(node) == kFixed) return; | 184 if (GetPlacement(node) == kFixed) return; |
| 190 | 185 |
| 191 // Use count for coupled nodes is summed up on their control. | 186 // Use count for coupled nodes is summed up on their control. |
| 192 if (GetPlacement(node) == kCoupled) { | 187 if (GetPlacement(node) == kCoupled) { |
| 193 Node* control = NodeProperties::GetControlInput(node); | 188 Node* control = NodeProperties::GetControlInput(node); |
| 194 return DecrementUnscheduledUseCount(control, index, from); | 189 return DecrementUnscheduledUseCount(control, index, from); |
| 195 } | 190 } |
| 196 | 191 |
| 197 DCHECK(GetData(node)->unscheduled_count_ > 0); | 192 DCHECK(GetData(node)->unscheduled_count_ > 0); |
| 198 --(GetData(node)->unscheduled_count_); | 193 --(GetData(node)->unscheduled_count_); |
| 199 if (FLAG_trace_turbo_scheduler) { | 194 if (FLAG_trace_turbo_scheduler) { |
| 200 Trace(" Use count of #%d:%s (used by #%d:%s)-- = %d\n", node->id(), | 195 TRACE(" Use count of #%d:%s (used by #%d:%s)-- = %d\n", node->id(), |
| 201 node->op()->mnemonic(), from->id(), from->op()->mnemonic(), | 196 node->op()->mnemonic(), from->id(), from->op()->mnemonic(), |
| 202 GetData(node)->unscheduled_count_); | 197 GetData(node)->unscheduled_count_); |
| 203 } | 198 } |
| 204 if (GetData(node)->unscheduled_count_ == 0) { | 199 if (GetData(node)->unscheduled_count_ == 0) { |
| 205 Trace(" newly eligible #%d:%s\n", node->id(), node->op()->mnemonic()); | 200 TRACE(" newly eligible #%d:%s\n", node->id(), node->op()->mnemonic()); |
| 206 schedule_queue_.push(node); | 201 schedule_queue_.push(node); |
| 207 } | 202 } |
| 208 } | 203 } |
| 209 | 204 |
| 210 | 205 |
| 211 // ----------------------------------------------------------------------------- | 206 // ----------------------------------------------------------------------------- |
| 212 // Phase 1: Build control-flow graph. | 207 // Phase 1: Build control-flow graph. |
| 213 | 208 |
| 214 | 209 |
| 215 // Internal class to build a control flow graph (i.e the basic blocks and edges | 210 // Internal class to build a control flow graph (i.e the basic blocks and edges |
| (...skipping 45 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 261 component_start_ = block; | 256 component_start_ = block; |
| 262 component_end_ = schedule_->block(exit); | 257 component_end_ = schedule_->block(exit); |
| 263 scheduler_->equivalence_->Run(exit); | 258 scheduler_->equivalence_->Run(exit); |
| 264 while (!queue_.empty()) { // Breadth-first backwards traversal. | 259 while (!queue_.empty()) { // Breadth-first backwards traversal. |
| 265 Node* node = queue_.front(); | 260 Node* node = queue_.front(); |
| 266 queue_.pop(); | 261 queue_.pop(); |
| 267 | 262 |
| 268 // Use control dependence equivalence to find a canonical single-entry | 263 // Use control dependence equivalence to find a canonical single-entry |
| 269 // single-exit region that makes up a minimal component to be scheduled. | 264 // single-exit region that makes up a minimal component to be scheduled. |
| 270 if (IsSingleEntrySingleExitRegion(node, exit)) { | 265 if (IsSingleEntrySingleExitRegion(node, exit)) { |
| 271 Trace("Found SESE at #%d:%s\n", node->id(), node->op()->mnemonic()); | 266 TRACE("Found SESE at #%d:%s\n", node->id(), node->op()->mnemonic()); |
| 272 DCHECK(!component_entry_); | 267 DCHECK(!component_entry_); |
| 273 component_entry_ = node; | 268 component_entry_ = node; |
| 274 continue; | 269 continue; |
| 275 } | 270 } |
| 276 | 271 |
| 277 int max = NodeProperties::PastControlIndex(node); | 272 int max = NodeProperties::PastControlIndex(node); |
| 278 for (int i = NodeProperties::FirstControlIndex(node); i < max; i++) { | 273 for (int i = NodeProperties::FirstControlIndex(node); i < max; i++) { |
| 279 Queue(node->InputAt(i)); | 274 Queue(node->InputAt(i)); |
| 280 } | 275 } |
| 281 } | 276 } |
| (...skipping 83 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 365 break; | 360 break; |
| 366 default: | 361 default: |
| 367 break; | 362 break; |
| 368 } | 363 } |
| 369 } | 364 } |
| 370 | 365 |
| 371 BasicBlock* BuildBlockForNode(Node* node) { | 366 BasicBlock* BuildBlockForNode(Node* node) { |
| 372 BasicBlock* block = schedule_->block(node); | 367 BasicBlock* block = schedule_->block(node); |
| 373 if (block == NULL) { | 368 if (block == NULL) { |
| 374 block = schedule_->NewBasicBlock(); | 369 block = schedule_->NewBasicBlock(); |
| 375 Trace("Create block id:%d for #%d:%s\n", block->id().ToInt(), node->id(), | 370 TRACE("Create block id:%d for #%d:%s\n", block->id().ToInt(), node->id(), |
| 376 node->op()->mnemonic()); | 371 node->op()->mnemonic()); |
| 377 FixNode(block, node); | 372 FixNode(block, node); |
| 378 } | 373 } |
| 379 return block; | 374 return block; |
| 380 } | 375 } |
| 381 | 376 |
| 382 void BuildBlocksForSuccessors(Node* node) { | 377 void BuildBlocksForSuccessors(Node* node) { |
| 383 size_t const successor_cnt = node->op()->ControlOutputCount(); | 378 size_t const successor_cnt = node->op()->ControlOutputCount(); |
| 384 Node** successors = zone_->NewArray<Node*>(successor_cnt); | 379 Node** successors = zone_->NewArray<Node*>(successor_cnt); |
| 385 NodeProperties::CollectControlProjections(node, successors, successor_cnt); | 380 NodeProperties::CollectControlProjections(node, successors, successor_cnt); |
| (...skipping 122 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 508 void ConnectThrow(Node* thr) { | 503 void ConnectThrow(Node* thr) { |
| 509 Node* throw_control = NodeProperties::GetControlInput(thr); | 504 Node* throw_control = NodeProperties::GetControlInput(thr); |
| 510 BasicBlock* throw_block = FindPredecessorBlock(throw_control); | 505 BasicBlock* throw_block = FindPredecessorBlock(throw_control); |
| 511 TraceConnect(thr, throw_block, NULL); | 506 TraceConnect(thr, throw_block, NULL); |
| 512 schedule_->AddThrow(throw_block, thr); | 507 schedule_->AddThrow(throw_block, thr); |
| 513 } | 508 } |
| 514 | 509 |
| 515 void TraceConnect(Node* node, BasicBlock* block, BasicBlock* succ) { | 510 void TraceConnect(Node* node, BasicBlock* block, BasicBlock* succ) { |
| 516 DCHECK_NOT_NULL(block); | 511 DCHECK_NOT_NULL(block); |
| 517 if (succ == NULL) { | 512 if (succ == NULL) { |
| 518 Trace("Connect #%d:%s, id:%d -> end\n", node->id(), | 513 TRACE("Connect #%d:%s, id:%d -> end\n", node->id(), |
| 519 node->op()->mnemonic(), block->id().ToInt()); | 514 node->op()->mnemonic(), block->id().ToInt()); |
| 520 } else { | 515 } else { |
| 521 Trace("Connect #%d:%s, id:%d -> id:%d\n", node->id(), | 516 TRACE("Connect #%d:%s, id:%d -> id:%d\n", node->id(), |
| 522 node->op()->mnemonic(), block->id().ToInt(), succ->id().ToInt()); | 517 node->op()->mnemonic(), block->id().ToInt(), succ->id().ToInt()); |
| 523 } | 518 } |
| 524 } | 519 } |
| 525 | 520 |
| 526 bool IsExceptionalCall(Node* node) { | 521 bool IsExceptionalCall(Node* node) { |
| 527 for (Node* const use : node->uses()) { | 522 for (Node* const use : node->uses()) { |
| 528 if (use->opcode() == IrOpcode::kIfException) return true; | 523 if (use->opcode() == IrOpcode::kIfException) return true; |
| 529 } | 524 } |
| 530 return false; | 525 return false; |
| 531 } | 526 } |
| (...skipping 21 matching lines...) Expand all Loading... |
| 553 NodeMarker<bool> queued_; // Mark indicating whether node is queued. | 548 NodeMarker<bool> queued_; // Mark indicating whether node is queued. |
| 554 ZoneQueue<Node*> queue_; // Queue used for breadth-first traversal. | 549 ZoneQueue<Node*> queue_; // Queue used for breadth-first traversal. |
| 555 NodeVector control_; // List of encountered control nodes. | 550 NodeVector control_; // List of encountered control nodes. |
| 556 Node* component_entry_; // Component single-entry node. | 551 Node* component_entry_; // Component single-entry node. |
| 557 BasicBlock* component_start_; // Component single-entry block. | 552 BasicBlock* component_start_; // Component single-entry block. |
| 558 BasicBlock* component_end_; // Component single-exit block. | 553 BasicBlock* component_end_; // Component single-exit block. |
| 559 }; | 554 }; |
| 560 | 555 |
| 561 | 556 |
| 562 void Scheduler::BuildCFG() { | 557 void Scheduler::BuildCFG() { |
| 563 Trace("--- CREATING CFG -------------------------------------------\n"); | 558 TRACE("--- CREATING CFG -------------------------------------------\n"); |
| 564 | 559 |
| 565 // Instantiate a new control equivalence algorithm for the graph. | 560 // Instantiate a new control equivalence algorithm for the graph. |
| 566 equivalence_ = new (zone_) ControlEquivalence(zone_, graph_); | 561 equivalence_ = new (zone_) ControlEquivalence(zone_, graph_); |
| 567 | 562 |
| 568 // Build a control-flow graph for the main control-connected component that | 563 // Build a control-flow graph for the main control-connected component that |
| 569 // is being spanned by the graph's start and end nodes. | 564 // is being spanned by the graph's start and end nodes. |
| 570 control_flow_builder_ = new (zone_) CFGBuilder(zone_, this); | 565 control_flow_builder_ = new (zone_) CFGBuilder(zone_, this); |
| 571 control_flow_builder_->Run(); | 566 control_flow_builder_->Run(); |
| 572 | 567 |
| 573 // Initialize per-block data. | 568 // Initialize per-block data. |
| (...skipping 307 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 881 } | 876 } |
| 882 current->set_loop_header(current_header); | 877 current->set_loop_header(current_header); |
| 883 | 878 |
| 884 // Push a new loop onto the stack if this loop is a loop header. | 879 // Push a new loop onto the stack if this loop is a loop header. |
| 885 if (HasLoopNumber(current)) { | 880 if (HasLoopNumber(current)) { |
| 886 ++loop_depth; | 881 ++loop_depth; |
| 887 current_loop = &loops_[GetLoopNumber(current)]; | 882 current_loop = &loops_[GetLoopNumber(current)]; |
| 888 BasicBlock* end = current_loop->end; | 883 BasicBlock* end = current_loop->end; |
| 889 current->set_loop_end(end == NULL ? BeyondEndSentinel() : end); | 884 current->set_loop_end(end == NULL ? BeyondEndSentinel() : end); |
| 890 current_header = current_loop->header; | 885 current_header = current_loop->header; |
| 891 Trace("id:%d is a loop header, increment loop depth to %d\n", | 886 TRACE("id:%d is a loop header, increment loop depth to %d\n", |
| 892 current->id().ToInt(), loop_depth); | 887 current->id().ToInt(), loop_depth); |
| 893 } | 888 } |
| 894 | 889 |
| 895 current->set_loop_depth(loop_depth); | 890 current->set_loop_depth(loop_depth); |
| 896 | 891 |
| 897 if (current->loop_header() == NULL) { | 892 if (current->loop_header() == NULL) { |
| 898 Trace("id:%d is not in a loop (depth == %d)\n", current->id().ToInt(), | 893 TRACE("id:%d is not in a loop (depth == %d)\n", current->id().ToInt(), |
| 899 current->loop_depth()); | 894 current->loop_depth()); |
| 900 } else { | 895 } else { |
| 901 Trace("id:%d has loop header id:%d, (depth == %d)\n", | 896 TRACE("id:%d has loop header id:%d, (depth == %d)\n", |
| 902 current->id().ToInt(), current->loop_header()->id().ToInt(), | 897 current->id().ToInt(), current->loop_header()->id().ToInt(), |
| 903 current->loop_depth()); | 898 current->loop_depth()); |
| 904 } | 899 } |
| 905 } | 900 } |
| 906 } | 901 } |
| 907 | 902 |
| 908 // Computes loop membership from the backedges of the control flow graph. | 903 // Computes loop membership from the backedges of the control flow graph. |
| 909 void ComputeLoopInfo(ZoneVector<SpecialRPOStackFrame>& queue, | 904 void ComputeLoopInfo(ZoneVector<SpecialRPOStackFrame>& queue, |
| 910 size_t num_loops, ZoneVector<Backedge>* backedges) { | 905 size_t num_loops, ZoneVector<Backedge>* backedges) { |
| 911 // Extend existing loop membership vectors. | 906 // Extend existing loop membership vectors. |
| (...skipping 161 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 1073 BasicBlockVector* Scheduler::ComputeSpecialRPO(Zone* zone, Schedule* schedule) { | 1068 BasicBlockVector* Scheduler::ComputeSpecialRPO(Zone* zone, Schedule* schedule) { |
| 1074 SpecialRPONumberer numberer(zone, schedule); | 1069 SpecialRPONumberer numberer(zone, schedule); |
| 1075 numberer.ComputeSpecialRPO(); | 1070 numberer.ComputeSpecialRPO(); |
| 1076 numberer.SerializeRPOIntoSchedule(); | 1071 numberer.SerializeRPOIntoSchedule(); |
| 1077 numberer.PrintAndVerifySpecialRPO(); | 1072 numberer.PrintAndVerifySpecialRPO(); |
| 1078 return schedule->rpo_order(); | 1073 return schedule->rpo_order(); |
| 1079 } | 1074 } |
| 1080 | 1075 |
| 1081 | 1076 |
| 1082 void Scheduler::ComputeSpecialRPONumbering() { | 1077 void Scheduler::ComputeSpecialRPONumbering() { |
| 1083 Trace("--- COMPUTING SPECIAL RPO ----------------------------------\n"); | 1078 TRACE("--- COMPUTING SPECIAL RPO ----------------------------------\n"); |
| 1084 | 1079 |
| 1085 // Compute the special reverse-post-order for basic blocks. | 1080 // Compute the special reverse-post-order for basic blocks. |
| 1086 special_rpo_ = new (zone_) SpecialRPONumberer(zone_, schedule_); | 1081 special_rpo_ = new (zone_) SpecialRPONumberer(zone_, schedule_); |
| 1087 special_rpo_->ComputeSpecialRPO(); | 1082 special_rpo_->ComputeSpecialRPO(); |
| 1088 } | 1083 } |
| 1089 | 1084 |
| 1090 | 1085 |
| 1091 void Scheduler::PropagateImmediateDominators(BasicBlock* block) { | 1086 void Scheduler::PropagateImmediateDominators(BasicBlock* block) { |
| 1092 for (/*nop*/; block != NULL; block = block->rpo_next()) { | 1087 for (/*nop*/; block != NULL; block = block->rpo_next()) { |
| 1093 auto pred = block->predecessors().begin(); | 1088 auto pred = block->predecessors().begin(); |
| 1094 auto end = block->predecessors().end(); | 1089 auto end = block->predecessors().end(); |
| 1095 DCHECK(pred != end); // All blocks except start have predecessors. | 1090 DCHECK(pred != end); // All blocks except start have predecessors. |
| 1096 BasicBlock* dominator = *pred; | 1091 BasicBlock* dominator = *pred; |
| 1097 bool deferred = dominator->deferred(); | 1092 bool deferred = dominator->deferred(); |
| 1098 // For multiple predecessors, walk up the dominator tree until a common | 1093 // For multiple predecessors, walk up the dominator tree until a common |
| 1099 // dominator is found. Visitation order guarantees that all predecessors | 1094 // dominator is found. Visitation order guarantees that all predecessors |
| 1100 // except for backwards edges have been visited. | 1095 // except for backwards edges have been visited. |
| 1101 for (++pred; pred != end; ++pred) { | 1096 for (++pred; pred != end; ++pred) { |
| 1102 // Don't examine backwards edges. | 1097 // Don't examine backwards edges. |
| 1103 if ((*pred)->dominator_depth() < 0) continue; | 1098 if ((*pred)->dominator_depth() < 0) continue; |
| 1104 dominator = BasicBlock::GetCommonDominator(dominator, *pred); | 1099 dominator = BasicBlock::GetCommonDominator(dominator, *pred); |
| 1105 deferred = deferred & (*pred)->deferred(); | 1100 deferred = deferred & (*pred)->deferred(); |
| 1106 } | 1101 } |
| 1107 block->set_dominator(dominator); | 1102 block->set_dominator(dominator); |
| 1108 block->set_dominator_depth(dominator->dominator_depth() + 1); | 1103 block->set_dominator_depth(dominator->dominator_depth() + 1); |
| 1109 block->set_deferred(deferred | block->deferred()); | 1104 block->set_deferred(deferred | block->deferred()); |
| 1110 Trace("Block id:%d's idom is id:%d, depth = %d\n", block->id().ToInt(), | 1105 TRACE("Block id:%d's idom is id:%d, depth = %d\n", block->id().ToInt(), |
| 1111 dominator->id().ToInt(), block->dominator_depth()); | 1106 dominator->id().ToInt(), block->dominator_depth()); |
| 1112 } | 1107 } |
| 1113 } | 1108 } |
| 1114 | 1109 |
| 1115 | 1110 |
| 1116 void Scheduler::GenerateImmediateDominatorTree() { | 1111 void Scheduler::GenerateImmediateDominatorTree() { |
| 1117 Trace("--- IMMEDIATE BLOCK DOMINATORS -----------------------------\n"); | 1112 TRACE("--- IMMEDIATE BLOCK DOMINATORS -----------------------------\n"); |
| 1118 | 1113 |
| 1119 // Seed start block to be the first dominator. | 1114 // Seed start block to be the first dominator. |
| 1120 schedule_->start()->set_dominator_depth(0); | 1115 schedule_->start()->set_dominator_depth(0); |
| 1121 | 1116 |
| 1122 // Build the block dominator tree resulting from the above seed. | 1117 // Build the block dominator tree resulting from the above seed. |
| 1123 PropagateImmediateDominators(schedule_->start()->rpo_next()); | 1118 PropagateImmediateDominators(schedule_->start()->rpo_next()); |
| 1124 } | 1119 } |
| 1125 | 1120 |
| 1126 | 1121 |
| 1127 // ----------------------------------------------------------------------------- | 1122 // ----------------------------------------------------------------------------- |
| 1128 // Phase 3: Prepare use counts for nodes. | 1123 // Phase 3: Prepare use counts for nodes. |
| 1129 | 1124 |
| 1130 | 1125 |
| 1131 class PrepareUsesVisitor { | 1126 class PrepareUsesVisitor { |
| 1132 public: | 1127 public: |
| 1133 explicit PrepareUsesVisitor(Scheduler* scheduler) | 1128 explicit PrepareUsesVisitor(Scheduler* scheduler) |
| 1134 : scheduler_(scheduler), schedule_(scheduler->schedule_) {} | 1129 : scheduler_(scheduler), schedule_(scheduler->schedule_) {} |
| 1135 | 1130 |
| 1136 void Pre(Node* node) { | 1131 void Pre(Node* node) { |
| 1137 if (scheduler_->GetPlacement(node) == Scheduler::kFixed) { | 1132 if (scheduler_->GetPlacement(node) == Scheduler::kFixed) { |
| 1138 // Fixed nodes are always roots for schedule late. | 1133 // Fixed nodes are always roots for schedule late. |
| 1139 scheduler_->schedule_root_nodes_.push_back(node); | 1134 scheduler_->schedule_root_nodes_.push_back(node); |
| 1140 if (!schedule_->IsScheduled(node)) { | 1135 if (!schedule_->IsScheduled(node)) { |
| 1141 // Make sure root nodes are scheduled in their respective blocks. | 1136 // Make sure root nodes are scheduled in their respective blocks. |
| 1142 Trace("Scheduling fixed position node #%d:%s\n", node->id(), | 1137 TRACE("Scheduling fixed position node #%d:%s\n", node->id(), |
| 1143 node->op()->mnemonic()); | 1138 node->op()->mnemonic()); |
| 1144 IrOpcode::Value opcode = node->opcode(); | 1139 IrOpcode::Value opcode = node->opcode(); |
| 1145 BasicBlock* block = | 1140 BasicBlock* block = |
| 1146 opcode == IrOpcode::kParameter | 1141 opcode == IrOpcode::kParameter |
| 1147 ? schedule_->start() | 1142 ? schedule_->start() |
| 1148 : schedule_->block(NodeProperties::GetControlInput(node)); | 1143 : schedule_->block(NodeProperties::GetControlInput(node)); |
| 1149 DCHECK(block != NULL); | 1144 DCHECK(block != NULL); |
| 1150 schedule_->AddNode(block, node); | 1145 schedule_->AddNode(block, node); |
| 1151 } | 1146 } |
| 1152 } | 1147 } |
| 1153 } | 1148 } |
| 1154 | 1149 |
| 1155 void PostEdge(Node* from, int index, Node* to) { | 1150 void PostEdge(Node* from, int index, Node* to) { |
| 1156 // If the edge is from an unscheduled node, then tally it in the use count | 1151 // If the edge is from an unscheduled node, then tally it in the use count |
| 1157 // for all of its inputs. The same criterion will be used in ScheduleLate | 1152 // for all of its inputs. The same criterion will be used in ScheduleLate |
| 1158 // for decrementing use counts. | 1153 // for decrementing use counts. |
| 1159 if (!schedule_->IsScheduled(from)) { | 1154 if (!schedule_->IsScheduled(from)) { |
| 1160 DCHECK_NE(Scheduler::kFixed, scheduler_->GetPlacement(from)); | 1155 DCHECK_NE(Scheduler::kFixed, scheduler_->GetPlacement(from)); |
| 1161 scheduler_->IncrementUnscheduledUseCount(to, index, from); | 1156 scheduler_->IncrementUnscheduledUseCount(to, index, from); |
| 1162 } | 1157 } |
| 1163 } | 1158 } |
| 1164 | 1159 |
| 1165 private: | 1160 private: |
| 1166 Scheduler* scheduler_; | 1161 Scheduler* scheduler_; |
| 1167 Schedule* schedule_; | 1162 Schedule* schedule_; |
| 1168 }; | 1163 }; |
| 1169 | 1164 |
| 1170 | 1165 |
| 1171 void Scheduler::PrepareUses() { | 1166 void Scheduler::PrepareUses() { |
| 1172 Trace("--- PREPARE USES -------------------------------------------\n"); | 1167 TRACE("--- PREPARE USES -------------------------------------------\n"); |
| 1173 | 1168 |
| 1174 // Count the uses of every node, which is used to ensure that all of a | 1169 // Count the uses of every node, which is used to ensure that all of a |
| 1175 // node's uses are scheduled before the node itself. | 1170 // node's uses are scheduled before the node itself. |
| 1176 PrepareUsesVisitor prepare_uses(this); | 1171 PrepareUsesVisitor prepare_uses(this); |
| 1177 | 1172 |
| 1178 // TODO(turbofan): simplify the careful pre/post ordering here. | 1173 // TODO(turbofan): simplify the careful pre/post ordering here. |
| 1179 BoolVector visited(graph_->NodeCount(), false, zone_); | 1174 BoolVector visited(graph_->NodeCount(), false, zone_); |
| 1180 ZoneStack<Node::InputEdges::iterator> stack(zone_); | 1175 ZoneStack<Node::InputEdges::iterator> stack(zone_); |
| 1181 Node* node = graph_->end(); | 1176 Node* node = graph_->end(); |
| 1182 prepare_uses.Pre(node); | 1177 prepare_uses.Pre(node); |
| (...skipping 36 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 1219 | 1214 |
| 1220 private: | 1215 private: |
| 1221 // Visits one node from the queue and propagates its current schedule early | 1216 // Visits one node from the queue and propagates its current schedule early |
| 1222 // position to all uses. This in turn might push more nodes onto the queue. | 1217 // position to all uses. This in turn might push more nodes onto the queue. |
| 1223 void VisitNode(Node* node) { | 1218 void VisitNode(Node* node) { |
| 1224 Scheduler::SchedulerData* data = scheduler_->GetData(node); | 1219 Scheduler::SchedulerData* data = scheduler_->GetData(node); |
| 1225 | 1220 |
| 1226 // Fixed nodes already know their schedule early position. | 1221 // Fixed nodes already know their schedule early position. |
| 1227 if (scheduler_->GetPlacement(node) == Scheduler::kFixed) { | 1222 if (scheduler_->GetPlacement(node) == Scheduler::kFixed) { |
| 1228 data->minimum_block_ = schedule_->block(node); | 1223 data->minimum_block_ = schedule_->block(node); |
| 1229 Trace("Fixing #%d:%s minimum_block = id:%d, dominator_depth = %d\n", | 1224 TRACE("Fixing #%d:%s minimum_block = id:%d, dominator_depth = %d\n", |
| 1230 node->id(), node->op()->mnemonic(), | 1225 node->id(), node->op()->mnemonic(), |
| 1231 data->minimum_block_->id().ToInt(), | 1226 data->minimum_block_->id().ToInt(), |
| 1232 data->minimum_block_->dominator_depth()); | 1227 data->minimum_block_->dominator_depth()); |
| 1233 } | 1228 } |
| 1234 | 1229 |
| 1235 // No need to propagate unconstrained schedule early positions. | 1230 // No need to propagate unconstrained schedule early positions. |
| 1236 if (data->minimum_block_ == schedule_->start()) return; | 1231 if (data->minimum_block_ == schedule_->start()) return; |
| 1237 | 1232 |
| 1238 // Propagate schedule early position. | 1233 // Propagate schedule early position. |
| 1239 DCHECK(data->minimum_block_ != NULL); | 1234 DCHECK(data->minimum_block_ != NULL); |
| (...skipping 17 matching lines...) Expand all Loading... |
| 1257 PropagateMinimumPositionToNode(block, control); | 1252 PropagateMinimumPositionToNode(block, control); |
| 1258 } | 1253 } |
| 1259 | 1254 |
| 1260 // Propagate new position if it is deeper down the dominator tree than the | 1255 // Propagate new position if it is deeper down the dominator tree than the |
| 1261 // current. Note that all inputs need to have minimum block position inside | 1256 // current. Note that all inputs need to have minimum block position inside |
| 1262 // the dominator chain of {node}'s minimum block position. | 1257 // the dominator chain of {node}'s minimum block position. |
| 1263 DCHECK(InsideSameDominatorChain(block, data->minimum_block_)); | 1258 DCHECK(InsideSameDominatorChain(block, data->minimum_block_)); |
| 1264 if (block->dominator_depth() > data->minimum_block_->dominator_depth()) { | 1259 if (block->dominator_depth() > data->minimum_block_->dominator_depth()) { |
| 1265 data->minimum_block_ = block; | 1260 data->minimum_block_ = block; |
| 1266 queue_.push(node); | 1261 queue_.push(node); |
| 1267 Trace("Propagating #%d:%s minimum_block = id:%d, dominator_depth = %d\n", | 1262 TRACE("Propagating #%d:%s minimum_block = id:%d, dominator_depth = %d\n", |
| 1268 node->id(), node->op()->mnemonic(), | 1263 node->id(), node->op()->mnemonic(), |
| 1269 data->minimum_block_->id().ToInt(), | 1264 data->minimum_block_->id().ToInt(), |
| 1270 data->minimum_block_->dominator_depth()); | 1265 data->minimum_block_->dominator_depth()); |
| 1271 } | 1266 } |
| 1272 } | 1267 } |
| 1273 | 1268 |
| 1274 #if DEBUG | 1269 #if DEBUG |
| 1275 bool InsideSameDominatorChain(BasicBlock* b1, BasicBlock* b2) { | 1270 bool InsideSameDominatorChain(BasicBlock* b1, BasicBlock* b2) { |
| 1276 BasicBlock* dominator = BasicBlock::GetCommonDominator(b1, b2); | 1271 BasicBlock* dominator = BasicBlock::GetCommonDominator(b1, b2); |
| 1277 return dominator == b1 || dominator == b2; | 1272 return dominator == b1 || dominator == b2; |
| 1278 } | 1273 } |
| 1279 #endif | 1274 #endif |
| 1280 | 1275 |
| 1281 Scheduler* scheduler_; | 1276 Scheduler* scheduler_; |
| 1282 Schedule* schedule_; | 1277 Schedule* schedule_; |
| 1283 ZoneQueue<Node*> queue_; | 1278 ZoneQueue<Node*> queue_; |
| 1284 }; | 1279 }; |
| 1285 | 1280 |
| 1286 | 1281 |
| 1287 void Scheduler::ScheduleEarly() { | 1282 void Scheduler::ScheduleEarly() { |
| 1288 Trace("--- SCHEDULE EARLY -----------------------------------------\n"); | 1283 TRACE("--- SCHEDULE EARLY -----------------------------------------\n"); |
| 1289 if (FLAG_trace_turbo_scheduler) { | 1284 if (FLAG_trace_turbo_scheduler) { |
| 1290 Trace("roots: "); | 1285 TRACE("roots: "); |
| 1291 for (Node* node : schedule_root_nodes_) { | 1286 for (Node* node : schedule_root_nodes_) { |
| 1292 Trace("#%d:%s ", node->id(), node->op()->mnemonic()); | 1287 TRACE("#%d:%s ", node->id(), node->op()->mnemonic()); |
| 1293 } | 1288 } |
| 1294 Trace("\n"); | 1289 TRACE("\n"); |
| 1295 } | 1290 } |
| 1296 | 1291 |
| 1297 // Compute the minimum block for each node thereby determining the earliest | 1292 // Compute the minimum block for each node thereby determining the earliest |
| 1298 // position each node could be placed within a valid schedule. | 1293 // position each node could be placed within a valid schedule. |
| 1299 ScheduleEarlyNodeVisitor schedule_early_visitor(zone_, this); | 1294 ScheduleEarlyNodeVisitor schedule_early_visitor(zone_, this); |
| 1300 schedule_early_visitor.Run(&schedule_root_nodes_); | 1295 schedule_early_visitor.Run(&schedule_root_nodes_); |
| 1301 } | 1296 } |
| 1302 | 1297 |
| 1303 | 1298 |
| 1304 // ----------------------------------------------------------------------------- | 1299 // ----------------------------------------------------------------------------- |
| (...skipping 41 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 1346 // optimal scheduling position. | 1341 // optimal scheduling position. |
| 1347 void VisitNode(Node* node) { | 1342 void VisitNode(Node* node) { |
| 1348 DCHECK_EQ(0, scheduler_->GetData(node)->unscheduled_count_); | 1343 DCHECK_EQ(0, scheduler_->GetData(node)->unscheduled_count_); |
| 1349 | 1344 |
| 1350 // Don't schedule nodes that are already scheduled. | 1345 // Don't schedule nodes that are already scheduled. |
| 1351 if (schedule_->IsScheduled(node)) return; | 1346 if (schedule_->IsScheduled(node)) return; |
| 1352 DCHECK_EQ(Scheduler::kSchedulable, scheduler_->GetPlacement(node)); | 1347 DCHECK_EQ(Scheduler::kSchedulable, scheduler_->GetPlacement(node)); |
| 1353 | 1348 |
| 1354 // Determine the dominating block for all of the uses of this node. It is | 1349 // Determine the dominating block for all of the uses of this node. It is |
| 1355 // the latest block that this node can be scheduled in. | 1350 // the latest block that this node can be scheduled in. |
| 1356 Trace("Scheduling #%d:%s\n", node->id(), node->op()->mnemonic()); | 1351 TRACE("Scheduling #%d:%s\n", node->id(), node->op()->mnemonic()); |
| 1357 BasicBlock* block = GetCommonDominatorOfUses(node); | 1352 BasicBlock* block = GetCommonDominatorOfUses(node); |
| 1358 DCHECK_NOT_NULL(block); | 1353 DCHECK_NOT_NULL(block); |
| 1359 | 1354 |
| 1360 // The schedule early block dominates the schedule late block. | 1355 // The schedule early block dominates the schedule late block. |
| 1361 BasicBlock* min_block = scheduler_->GetData(node)->minimum_block_; | 1356 BasicBlock* min_block = scheduler_->GetData(node)->minimum_block_; |
| 1362 DCHECK_EQ(min_block, BasicBlock::GetCommonDominator(block, min_block)); | 1357 DCHECK_EQ(min_block, BasicBlock::GetCommonDominator(block, min_block)); |
| 1363 Trace( | 1358 TRACE( |
| 1364 "Schedule late of #%d:%s is id:%d at loop depth %d, minimum = id:%d\n", | 1359 "Schedule late of #%d:%s is id:%d at loop depth %d, minimum = id:%d\n", |
| 1365 node->id(), node->op()->mnemonic(), block->id().ToInt(), | 1360 node->id(), node->op()->mnemonic(), block->id().ToInt(), |
| 1366 block->loop_depth(), min_block->id().ToInt()); | 1361 block->loop_depth(), min_block->id().ToInt()); |
| 1367 | 1362 |
| 1368 // Hoist nodes out of loops if possible. Nodes can be hoisted iteratively | 1363 // Hoist nodes out of loops if possible. Nodes can be hoisted iteratively |
| 1369 // into enclosing loop pre-headers until they would preceed their schedule | 1364 // into enclosing loop pre-headers until they would preceed their schedule |
| 1370 // early position. | 1365 // early position. |
| 1371 BasicBlock* hoist_block = GetHoistBlock(block); | 1366 BasicBlock* hoist_block = GetHoistBlock(block); |
| 1372 if (hoist_block && | 1367 if (hoist_block && |
| 1373 hoist_block->dominator_depth() >= min_block->dominator_depth()) { | 1368 hoist_block->dominator_depth() >= min_block->dominator_depth()) { |
| 1374 do { | 1369 do { |
| 1375 Trace(" hoisting #%d:%s to block id:%d\n", node->id(), | 1370 TRACE(" hoisting #%d:%s to block id:%d\n", node->id(), |
| 1376 node->op()->mnemonic(), hoist_block->id().ToInt()); | 1371 node->op()->mnemonic(), hoist_block->id().ToInt()); |
| 1377 DCHECK_LT(hoist_block->loop_depth(), block->loop_depth()); | 1372 DCHECK_LT(hoist_block->loop_depth(), block->loop_depth()); |
| 1378 block = hoist_block; | 1373 block = hoist_block; |
| 1379 hoist_block = GetHoistBlock(hoist_block); | 1374 hoist_block = GetHoistBlock(hoist_block); |
| 1380 } while (hoist_block && | 1375 } while (hoist_block && |
| 1381 hoist_block->dominator_depth() >= min_block->dominator_depth()); | 1376 hoist_block->dominator_depth() >= min_block->dominator_depth()); |
| 1382 } else if (scheduler_->flags_ & Scheduler::kSplitNodes) { | 1377 } else if (scheduler_->flags_ & Scheduler::kSplitNodes) { |
| 1383 // Split the {node} if beneficial and return the new {block} for it. | 1378 // Split the {node} if beneficial and return the new {block} for it. |
| 1384 block = SplitNode(block, node); | 1379 block = SplitNode(block, node); |
| 1385 } | 1380 } |
| (...skipping 29 matching lines...) Expand all Loading... |
| 1415 // Clear marking bits. | 1410 // Clear marking bits. |
| 1416 DCHECK(marking_queue_.empty()); | 1411 DCHECK(marking_queue_.empty()); |
| 1417 std::fill(marked_.begin(), marked_.end(), false); | 1412 std::fill(marked_.begin(), marked_.end(), false); |
| 1418 marked_.resize(schedule_->BasicBlockCount() + 1, false); | 1413 marked_.resize(schedule_->BasicBlockCount() + 1, false); |
| 1419 | 1414 |
| 1420 // Check if the {node} has uses in {block}. | 1415 // Check if the {node} has uses in {block}. |
| 1421 for (Edge edge : node->use_edges()) { | 1416 for (Edge edge : node->use_edges()) { |
| 1422 BasicBlock* use_block = GetBlockForUse(edge); | 1417 BasicBlock* use_block = GetBlockForUse(edge); |
| 1423 if (use_block == nullptr || marked_[use_block->id().ToSize()]) continue; | 1418 if (use_block == nullptr || marked_[use_block->id().ToSize()]) continue; |
| 1424 if (use_block == block) { | 1419 if (use_block == block) { |
| 1425 Trace(" not splitting #%d:%s, it is used in id:%d\n", node->id(), | 1420 TRACE(" not splitting #%d:%s, it is used in id:%d\n", node->id(), |
| 1426 node->op()->mnemonic(), block->id().ToInt()); | 1421 node->op()->mnemonic(), block->id().ToInt()); |
| 1427 marking_queue_.clear(); | 1422 marking_queue_.clear(); |
| 1428 return block; | 1423 return block; |
| 1429 } | 1424 } |
| 1430 MarkBlock(use_block); | 1425 MarkBlock(use_block); |
| 1431 } | 1426 } |
| 1432 | 1427 |
| 1433 // Compute transitive marking closure; a block is marked if all its | 1428 // Compute transitive marking closure; a block is marked if all its |
| 1434 // successors are marked. | 1429 // successors are marked. |
| 1435 do { | 1430 do { |
| 1436 BasicBlock* top_block = marking_queue_.front(); | 1431 BasicBlock* top_block = marking_queue_.front(); |
| 1437 marking_queue_.pop_front(); | 1432 marking_queue_.pop_front(); |
| 1438 if (marked_[top_block->id().ToSize()]) continue; | 1433 if (marked_[top_block->id().ToSize()]) continue; |
| 1439 bool marked = true; | 1434 bool marked = true; |
| 1440 for (BasicBlock* successor : top_block->successors()) { | 1435 for (BasicBlock* successor : top_block->successors()) { |
| 1441 if (!marked_[successor->id().ToSize()]) { | 1436 if (!marked_[successor->id().ToSize()]) { |
| 1442 marked = false; | 1437 marked = false; |
| 1443 break; | 1438 break; |
| 1444 } | 1439 } |
| 1445 } | 1440 } |
| 1446 if (marked) MarkBlock(top_block); | 1441 if (marked) MarkBlock(top_block); |
| 1447 } while (!marking_queue_.empty()); | 1442 } while (!marking_queue_.empty()); |
| 1448 | 1443 |
| 1449 // If the (common dominator) {block} is marked, we know that all paths from | 1444 // If the (common dominator) {block} is marked, we know that all paths from |
| 1450 // {block} to the end contain at least one use of {node}, and hence there's | 1445 // {block} to the end contain at least one use of {node}, and hence there's |
| 1451 // no point in splitting the {node} in this case. | 1446 // no point in splitting the {node} in this case. |
| 1452 if (marked_[block->id().ToSize()]) { | 1447 if (marked_[block->id().ToSize()]) { |
| 1453 Trace(" not splitting #%d:%s, its common dominator id:%d is perfect\n", | 1448 TRACE(" not splitting #%d:%s, its common dominator id:%d is perfect\n", |
| 1454 node->id(), node->op()->mnemonic(), block->id().ToInt()); | 1449 node->id(), node->op()->mnemonic(), block->id().ToInt()); |
| 1455 return block; | 1450 return block; |
| 1456 } | 1451 } |
| 1457 | 1452 |
| 1458 // Split {node} for uses according to the previously computed marking | 1453 // Split {node} for uses according to the previously computed marking |
| 1459 // closure. Every marking partition has a unique dominator, which get's a | 1454 // closure. Every marking partition has a unique dominator, which get's a |
| 1460 // copy of the {node} with the exception of the first partition, which get's | 1455 // copy of the {node} with the exception of the first partition, which get's |
| 1461 // the {node} itself. | 1456 // the {node} itself. |
| 1462 ZoneMap<BasicBlock*, Node*> dominators(scheduler_->zone_); | 1457 ZoneMap<BasicBlock*, Node*> dominators(scheduler_->zone_); |
| 1463 for (Edge edge : node->use_edges()) { | 1458 for (Edge edge : node->use_edges()) { |
| 1464 BasicBlock* use_block = GetBlockForUse(edge); | 1459 BasicBlock* use_block = GetBlockForUse(edge); |
| 1465 if (use_block == nullptr) continue; | 1460 if (use_block == nullptr) continue; |
| 1466 while (marked_[use_block->dominator()->id().ToSize()]) { | 1461 while (marked_[use_block->dominator()->id().ToSize()]) { |
| 1467 use_block = use_block->dominator(); | 1462 use_block = use_block->dominator(); |
| 1468 } | 1463 } |
| 1469 auto& use_node = dominators[use_block]; | 1464 auto& use_node = dominators[use_block]; |
| 1470 if (use_node == nullptr) { | 1465 if (use_node == nullptr) { |
| 1471 if (dominators.size() == 1u) { | 1466 if (dominators.size() == 1u) { |
| 1472 // Place the {node} at {use_block}. | 1467 // Place the {node} at {use_block}. |
| 1473 block = use_block; | 1468 block = use_block; |
| 1474 use_node = node; | 1469 use_node = node; |
| 1475 Trace(" pushing #%d:%s down to id:%d\n", node->id(), | 1470 TRACE(" pushing #%d:%s down to id:%d\n", node->id(), |
| 1476 node->op()->mnemonic(), block->id().ToInt()); | 1471 node->op()->mnemonic(), block->id().ToInt()); |
| 1477 } else { | 1472 } else { |
| 1478 // Place a copy of {node} at {use_block}. | 1473 // Place a copy of {node} at {use_block}. |
| 1479 use_node = CloneNode(node); | 1474 use_node = CloneNode(node); |
| 1480 Trace(" cloning #%d:%s for id:%d\n", use_node->id(), | 1475 TRACE(" cloning #%d:%s for id:%d\n", use_node->id(), |
| 1481 use_node->op()->mnemonic(), use_block->id().ToInt()); | 1476 use_node->op()->mnemonic(), use_block->id().ToInt()); |
| 1482 scheduler_->schedule_queue_.push(use_node); | 1477 scheduler_->schedule_queue_.push(use_node); |
| 1483 } | 1478 } |
| 1484 } | 1479 } |
| 1485 edge.UpdateTo(use_node); | 1480 edge.UpdateTo(use_node); |
| 1486 } | 1481 } |
| 1487 return block; | 1482 return block; |
| 1488 } | 1483 } |
| 1489 | 1484 |
| 1490 BasicBlock* GetHoistBlock(BasicBlock* block) { | 1485 BasicBlock* GetHoistBlock(BasicBlock* block) { |
| (...skipping 30 matching lines...) Expand all Loading... |
| 1521 BasicBlock* FindPredecessorBlock(Node* node) { | 1516 BasicBlock* FindPredecessorBlock(Node* node) { |
| 1522 return scheduler_->control_flow_builder_->FindPredecessorBlock(node); | 1517 return scheduler_->control_flow_builder_->FindPredecessorBlock(node); |
| 1523 } | 1518 } |
| 1524 | 1519 |
| 1525 BasicBlock* GetBlockForUse(Edge edge) { | 1520 BasicBlock* GetBlockForUse(Edge edge) { |
| 1526 Node* use = edge.from(); | 1521 Node* use = edge.from(); |
| 1527 if (IrOpcode::IsPhiOpcode(use->opcode())) { | 1522 if (IrOpcode::IsPhiOpcode(use->opcode())) { |
| 1528 // If the use is from a coupled (i.e. floating) phi, compute the common | 1523 // If the use is from a coupled (i.e. floating) phi, compute the common |
| 1529 // dominator of its uses. This will not recurse more than one level. | 1524 // dominator of its uses. This will not recurse more than one level. |
| 1530 if (scheduler_->GetPlacement(use) == Scheduler::kCoupled) { | 1525 if (scheduler_->GetPlacement(use) == Scheduler::kCoupled) { |
| 1531 Trace(" inspecting uses of coupled #%d:%s\n", use->id(), | 1526 TRACE(" inspecting uses of coupled #%d:%s\n", use->id(), |
| 1532 use->op()->mnemonic()); | 1527 use->op()->mnemonic()); |
| 1533 DCHECK_EQ(edge.to(), NodeProperties::GetControlInput(use)); | 1528 DCHECK_EQ(edge.to(), NodeProperties::GetControlInput(use)); |
| 1534 return GetCommonDominatorOfUses(use); | 1529 return GetCommonDominatorOfUses(use); |
| 1535 } | 1530 } |
| 1536 // If the use is from a fixed (i.e. non-floating) phi, we use the | 1531 // If the use is from a fixed (i.e. non-floating) phi, we use the |
| 1537 // predecessor block of the corresponding control input to the merge. | 1532 // predecessor block of the corresponding control input to the merge. |
| 1538 if (scheduler_->GetPlacement(use) == Scheduler::kFixed) { | 1533 if (scheduler_->GetPlacement(use) == Scheduler::kFixed) { |
| 1539 Trace(" input@%d into a fixed phi #%d:%s\n", edge.index(), use->id(), | 1534 TRACE(" input@%d into a fixed phi #%d:%s\n", edge.index(), use->id(), |
| 1540 use->op()->mnemonic()); | 1535 use->op()->mnemonic()); |
| 1541 Node* merge = NodeProperties::GetControlInput(use, 0); | 1536 Node* merge = NodeProperties::GetControlInput(use, 0); |
| 1542 DCHECK(IrOpcode::IsMergeOpcode(merge->opcode())); | 1537 DCHECK(IrOpcode::IsMergeOpcode(merge->opcode())); |
| 1543 Node* input = NodeProperties::GetControlInput(merge, edge.index()); | 1538 Node* input = NodeProperties::GetControlInput(merge, edge.index()); |
| 1544 return FindPredecessorBlock(input); | 1539 return FindPredecessorBlock(input); |
| 1545 } | 1540 } |
| 1546 } else if (IrOpcode::IsMergeOpcode(use->opcode())) { | 1541 } else if (IrOpcode::IsMergeOpcode(use->opcode())) { |
| 1547 // If the use is from a fixed (i.e. non-floating) merge, we use the | 1542 // If the use is from a fixed (i.e. non-floating) merge, we use the |
| 1548 // predecessor block of the current input to the merge. | 1543 // predecessor block of the current input to the merge. |
| 1549 if (scheduler_->GetPlacement(use) == Scheduler::kFixed) { | 1544 if (scheduler_->GetPlacement(use) == Scheduler::kFixed) { |
| 1550 Trace(" input@%d into a fixed merge #%d:%s\n", edge.index(), use->id(), | 1545 TRACE(" input@%d into a fixed merge #%d:%s\n", edge.index(), use->id(), |
| 1551 use->op()->mnemonic()); | 1546 use->op()->mnemonic()); |
| 1552 return FindPredecessorBlock(edge.to()); | 1547 return FindPredecessorBlock(edge.to()); |
| 1553 } | 1548 } |
| 1554 } | 1549 } |
| 1555 BasicBlock* result = schedule_->block(use); | 1550 BasicBlock* result = schedule_->block(use); |
| 1556 if (result == NULL) return NULL; | 1551 if (result == NULL) return NULL; |
| 1557 Trace(" must dominate use #%d:%s in id:%d\n", use->id(), | 1552 TRACE(" must dominate use #%d:%s in id:%d\n", use->id(), |
| 1558 use->op()->mnemonic(), result->id().ToInt()); | 1553 use->op()->mnemonic(), result->id().ToInt()); |
| 1559 return result; | 1554 return result; |
| 1560 } | 1555 } |
| 1561 | 1556 |
| 1562 void ScheduleFloatingControl(BasicBlock* block, Node* node) { | 1557 void ScheduleFloatingControl(BasicBlock* block, Node* node) { |
| 1563 scheduler_->FuseFloatingControl(block, node); | 1558 scheduler_->FuseFloatingControl(block, node); |
| 1564 } | 1559 } |
| 1565 | 1560 |
| 1566 void ScheduleNode(BasicBlock* block, Node* node) { | 1561 void ScheduleNode(BasicBlock* block, Node* node) { |
| 1567 schedule_->PlanNode(block, node); | 1562 schedule_->PlanNode(block, node); |
| (...skipping 17 matching lines...) Expand all Loading... |
| 1585 } | 1580 } |
| 1586 | 1581 |
| 1587 Scheduler* scheduler_; | 1582 Scheduler* scheduler_; |
| 1588 Schedule* schedule_; | 1583 Schedule* schedule_; |
| 1589 BoolVector marked_; | 1584 BoolVector marked_; |
| 1590 ZoneDeque<BasicBlock*> marking_queue_; | 1585 ZoneDeque<BasicBlock*> marking_queue_; |
| 1591 }; | 1586 }; |
| 1592 | 1587 |
| 1593 | 1588 |
| 1594 void Scheduler::ScheduleLate() { | 1589 void Scheduler::ScheduleLate() { |
| 1595 Trace("--- SCHEDULE LATE ------------------------------------------\n"); | 1590 TRACE("--- SCHEDULE LATE ------------------------------------------\n"); |
| 1596 if (FLAG_trace_turbo_scheduler) { | 1591 if (FLAG_trace_turbo_scheduler) { |
| 1597 Trace("roots: "); | 1592 TRACE("roots: "); |
| 1598 for (Node* node : schedule_root_nodes_) { | 1593 for (Node* node : schedule_root_nodes_) { |
| 1599 Trace("#%d:%s ", node->id(), node->op()->mnemonic()); | 1594 TRACE("#%d:%s ", node->id(), node->op()->mnemonic()); |
| 1600 } | 1595 } |
| 1601 Trace("\n"); | 1596 TRACE("\n"); |
| 1602 } | 1597 } |
| 1603 | 1598 |
| 1604 // Schedule: Places nodes in dominator block of all their uses. | 1599 // Schedule: Places nodes in dominator block of all their uses. |
| 1605 ScheduleLateNodeVisitor schedule_late_visitor(zone_, this); | 1600 ScheduleLateNodeVisitor schedule_late_visitor(zone_, this); |
| 1606 schedule_late_visitor.Run(&schedule_root_nodes_); | 1601 schedule_late_visitor.Run(&schedule_root_nodes_); |
| 1607 } | 1602 } |
| 1608 | 1603 |
| 1609 | 1604 |
| 1610 // ----------------------------------------------------------------------------- | 1605 // ----------------------------------------------------------------------------- |
| 1611 // Phase 6: Seal the final schedule. | 1606 // Phase 6: Seal the final schedule. |
| 1612 | 1607 |
| 1613 | 1608 |
| 1614 void Scheduler::SealFinalSchedule() { | 1609 void Scheduler::SealFinalSchedule() { |
| 1615 Trace("--- SEAL FINAL SCHEDULE ------------------------------------\n"); | 1610 TRACE("--- SEAL FINAL SCHEDULE ------------------------------------\n"); |
| 1616 | 1611 |
| 1617 // Serialize the assembly order and reverse-post-order numbering. | 1612 // Serialize the assembly order and reverse-post-order numbering. |
| 1618 special_rpo_->SerializeRPOIntoSchedule(); | 1613 special_rpo_->SerializeRPOIntoSchedule(); |
| 1619 special_rpo_->PrintAndVerifySpecialRPO(); | 1614 special_rpo_->PrintAndVerifySpecialRPO(); |
| 1620 | 1615 |
| 1621 // Add collected nodes for basic blocks to their blocks in the right order. | 1616 // Add collected nodes for basic blocks to their blocks in the right order. |
| 1622 int block_num = 0; | 1617 int block_num = 0; |
| 1623 for (NodeVector& nodes : scheduled_nodes_) { | 1618 for (NodeVector& nodes : scheduled_nodes_) { |
| 1624 BasicBlock::Id id = BasicBlock::Id::FromInt(block_num++); | 1619 BasicBlock::Id id = BasicBlock::Id::FromInt(block_num++); |
| 1625 BasicBlock* block = schedule_->GetBlockById(id); | 1620 BasicBlock* block = schedule_->GetBlockById(id); |
| 1626 for (auto i = nodes.rbegin(); i != nodes.rend(); ++i) { | 1621 for (auto i = nodes.rbegin(); i != nodes.rend(); ++i) { |
| 1627 schedule_->AddNode(block, *i); | 1622 schedule_->AddNode(block, *i); |
| 1628 } | 1623 } |
| 1629 } | 1624 } |
| 1630 } | 1625 } |
| 1631 | 1626 |
| 1632 | 1627 |
| 1633 // ----------------------------------------------------------------------------- | 1628 // ----------------------------------------------------------------------------- |
| 1634 | 1629 |
| 1635 | 1630 |
| 1636 void Scheduler::FuseFloatingControl(BasicBlock* block, Node* node) { | 1631 void Scheduler::FuseFloatingControl(BasicBlock* block, Node* node) { |
| 1637 Trace("--- FUSE FLOATING CONTROL ----------------------------------\n"); | 1632 TRACE("--- FUSE FLOATING CONTROL ----------------------------------\n"); |
| 1638 if (FLAG_trace_turbo_scheduler) { | 1633 if (FLAG_trace_turbo_scheduler) { |
| 1639 OFStream os(stdout); | 1634 OFStream os(stdout); |
| 1640 os << "Schedule before control flow fusion:\n" << *schedule_; | 1635 os << "Schedule before control flow fusion:\n" << *schedule_; |
| 1641 } | 1636 } |
| 1642 | 1637 |
| 1643 // Iterate on phase 1: Build control-flow graph. | 1638 // Iterate on phase 1: Build control-flow graph. |
| 1644 control_flow_builder_->Run(block, node); | 1639 control_flow_builder_->Run(block, node); |
| 1645 | 1640 |
| 1646 // Iterate on phase 2: Compute special RPO and dominator tree. | 1641 // Iterate on phase 2: Compute special RPO and dominator tree. |
| 1647 special_rpo_->UpdateSpecialRPO(block, schedule_->block(node)); | 1642 special_rpo_->UpdateSpecialRPO(block, schedule_->block(node)); |
| 1648 // TODO(mstarzinger): Currently "iterate on" means "re-run". Fix that. | 1643 // TODO(mstarzinger): Currently "iterate on" means "re-run". Fix that. |
| 1649 for (BasicBlock* b = block->rpo_next(); b != NULL; b = b->rpo_next()) { | 1644 for (BasicBlock* b = block->rpo_next(); b != NULL; b = b->rpo_next()) { |
| 1650 b->set_dominator_depth(-1); | 1645 b->set_dominator_depth(-1); |
| 1651 b->set_dominator(NULL); | 1646 b->set_dominator(NULL); |
| 1652 } | 1647 } |
| 1653 PropagateImmediateDominators(block->rpo_next()); | 1648 PropagateImmediateDominators(block->rpo_next()); |
| 1654 | 1649 |
| 1655 // Iterate on phase 4: Schedule nodes early. | 1650 // Iterate on phase 4: Schedule nodes early. |
| 1656 // TODO(mstarzinger): The following loop gathering the propagation roots is a | 1651 // TODO(mstarzinger): The following loop gathering the propagation roots is a |
| 1657 // temporary solution and should be merged into the rest of the scheduler as | 1652 // temporary solution and should be merged into the rest of the scheduler as |
| 1658 // soon as the approach settled for all floating loops. | 1653 // soon as the approach settled for all floating loops. |
| 1659 NodeVector propagation_roots(control_flow_builder_->control_); | 1654 NodeVector propagation_roots(control_flow_builder_->control_); |
| 1660 for (Node* node : control_flow_builder_->control_) { | 1655 for (Node* node : control_flow_builder_->control_) { |
| 1661 for (Node* use : node->uses()) { | 1656 for (Node* use : node->uses()) { |
| 1662 if (NodeProperties::IsPhi(use)) propagation_roots.push_back(use); | 1657 if (NodeProperties::IsPhi(use)) propagation_roots.push_back(use); |
| 1663 } | 1658 } |
| 1664 } | 1659 } |
| 1665 if (FLAG_trace_turbo_scheduler) { | 1660 if (FLAG_trace_turbo_scheduler) { |
| 1666 Trace("propagation roots: "); | 1661 TRACE("propagation roots: "); |
| 1667 for (Node* node : propagation_roots) { | 1662 for (Node* node : propagation_roots) { |
| 1668 Trace("#%d:%s ", node->id(), node->op()->mnemonic()); | 1663 TRACE("#%d:%s ", node->id(), node->op()->mnemonic()); |
| 1669 } | 1664 } |
| 1670 Trace("\n"); | 1665 TRACE("\n"); |
| 1671 } | 1666 } |
| 1672 ScheduleEarlyNodeVisitor schedule_early_visitor(zone_, this); | 1667 ScheduleEarlyNodeVisitor schedule_early_visitor(zone_, this); |
| 1673 schedule_early_visitor.Run(&propagation_roots); | 1668 schedule_early_visitor.Run(&propagation_roots); |
| 1674 | 1669 |
| 1675 // Move previously planned nodes. | 1670 // Move previously planned nodes. |
| 1676 // TODO(mstarzinger): Improve that by supporting bulk moves. | 1671 // TODO(mstarzinger): Improve that by supporting bulk moves. |
| 1677 scheduled_nodes_.resize(schedule_->BasicBlockCount(), NodeVector(zone_)); | 1672 scheduled_nodes_.resize(schedule_->BasicBlockCount(), NodeVector(zone_)); |
| 1678 MovePlannedNodes(block, schedule_->block(node)); | 1673 MovePlannedNodes(block, schedule_->block(node)); |
| 1679 | 1674 |
| 1680 if (FLAG_trace_turbo_scheduler) { | 1675 if (FLAG_trace_turbo_scheduler) { |
| 1681 OFStream os(stdout); | 1676 OFStream os(stdout); |
| 1682 os << "Schedule after control flow fusion:\n" << *schedule_; | 1677 os << "Schedule after control flow fusion:\n" << *schedule_; |
| 1683 } | 1678 } |
| 1684 } | 1679 } |
| 1685 | 1680 |
| 1686 | 1681 |
| 1687 void Scheduler::MovePlannedNodes(BasicBlock* from, BasicBlock* to) { | 1682 void Scheduler::MovePlannedNodes(BasicBlock* from, BasicBlock* to) { |
| 1688 Trace("Move planned nodes from id:%d to id:%d\n", from->id().ToInt(), | 1683 TRACE("Move planned nodes from id:%d to id:%d\n", from->id().ToInt(), |
| 1689 to->id().ToInt()); | 1684 to->id().ToInt()); |
| 1690 NodeVector* nodes = &(scheduled_nodes_[from->id().ToSize()]); | 1685 NodeVector* nodes = &(scheduled_nodes_[from->id().ToSize()]); |
| 1691 for (Node* const node : *nodes) { | 1686 for (Node* const node : *nodes) { |
| 1692 schedule_->SetBlockForNode(to, node); | 1687 schedule_->SetBlockForNode(to, node); |
| 1693 scheduled_nodes_[to->id().ToSize()].push_back(node); | 1688 scheduled_nodes_[to->id().ToSize()].push_back(node); |
| 1694 } | 1689 } |
| 1695 nodes->clear(); | 1690 nodes->clear(); |
| 1696 } | 1691 } |
| 1697 | 1692 |
| 1698 } // namespace compiler | 1693 } // namespace compiler |
| 1699 } // namespace internal | 1694 } // namespace internal |
| 1700 } // namespace v8 | 1695 } // namespace v8 |
| OLD | NEW |