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 <deque> | 5 #include <deque> |
6 #include <queue> | 6 #include <queue> |
7 | 7 |
8 #include "src/compiler/scheduler.h" | 8 #include "src/compiler/scheduler.h" |
9 | 9 |
10 #include "src/bit-vector.h" | 10 #include "src/bit-vector.h" |
| 11 #include "src/compiler/control-equivalence.h" |
11 #include "src/compiler/graph.h" | 12 #include "src/compiler/graph.h" |
12 #include "src/compiler/graph-inl.h" | 13 #include "src/compiler/graph-inl.h" |
13 #include "src/compiler/node.h" | 14 #include "src/compiler/node.h" |
14 #include "src/compiler/node-properties.h" | 15 #include "src/compiler/node-properties.h" |
15 #include "src/compiler/node-properties-inl.h" | 16 #include "src/compiler/node-properties-inl.h" |
16 | 17 |
17 namespace v8 { | 18 namespace v8 { |
18 namespace internal { | 19 namespace internal { |
19 namespace compiler { | 20 namespace compiler { |
20 | 21 |
(...skipping 30 matching lines...) Expand all Loading... |
51 scheduler.ScheduleEarly(); | 52 scheduler.ScheduleEarly(); |
52 scheduler.ScheduleLate(); | 53 scheduler.ScheduleLate(); |
53 | 54 |
54 scheduler.SealFinalSchedule(); | 55 scheduler.SealFinalSchedule(); |
55 | 56 |
56 return schedule; | 57 return schedule; |
57 } | 58 } |
58 | 59 |
59 | 60 |
60 Scheduler::SchedulerData Scheduler::DefaultSchedulerData() { | 61 Scheduler::SchedulerData Scheduler::DefaultSchedulerData() { |
61 SchedulerData def = {schedule_->start(), 0, false, false, kUnknown}; | 62 SchedulerData def = {schedule_->start(), 0, false, kUnknown}; |
62 return def; | 63 return def; |
63 } | 64 } |
64 | 65 |
65 | 66 |
66 Scheduler::SchedulerData* Scheduler::GetData(Node* node) { | 67 Scheduler::SchedulerData* Scheduler::GetData(Node* node) { |
67 DCHECK(node->id() < static_cast<int>(node_data_.size())); | 68 DCHECK(node->id() < static_cast<int>(node_data_.size())); |
68 return &node_data_[node->id()]; | 69 return &node_data_[node->id()]; |
69 } | 70 } |
70 | 71 |
71 | 72 |
72 Scheduler::Placement Scheduler::GetPlacement(Node* node) { | 73 Scheduler::Placement Scheduler::GetPlacement(Node* node) { |
73 SchedulerData* data = GetData(node); | 74 SchedulerData* data = GetData(node); |
74 if (data->placement_ == kUnknown) { // Compute placement, once, on demand. | 75 if (data->placement_ == kUnknown) { // Compute placement, once, on demand. |
75 switch (node->opcode()) { | 76 switch (node->opcode()) { |
76 case IrOpcode::kParameter: | 77 case IrOpcode::kParameter: |
77 // Parameters are always fixed to the start node. | 78 // Parameters are always fixed to the start node. |
78 data->placement_ = kFixed; | 79 data->placement_ = kFixed; |
79 break; | 80 break; |
80 case IrOpcode::kPhi: | 81 case IrOpcode::kPhi: |
81 case IrOpcode::kEffectPhi: { | 82 case IrOpcode::kEffectPhi: { |
82 // Phis and effect phis are fixed if their control inputs are, whereas | 83 // Phis and effect phis are fixed if their control inputs are, whereas |
83 // otherwise they are coupled to a floating control node. | 84 // otherwise they are coupled to a floating control node. |
84 Placement p = GetPlacement(NodeProperties::GetControlInput(node)); | 85 Placement p = GetPlacement(NodeProperties::GetControlInput(node)); |
85 data->placement_ = (p == kFixed ? kFixed : kCoupled); | 86 data->placement_ = (p == kFixed ? kFixed : kCoupled); |
86 break; | 87 break; |
87 } | 88 } |
88 #define DEFINE_FLOATING_CONTROL_CASE(V) case IrOpcode::k##V: | 89 #define DEFINE_CONTROL_CASE(V) case IrOpcode::k##V: |
89 CONTROL_OP_LIST(DEFINE_FLOATING_CONTROL_CASE) | 90 CONTROL_OP_LIST(DEFINE_CONTROL_CASE) |
90 #undef DEFINE_FLOATING_CONTROL_CASE | 91 #undef DEFINE_CONTROL_CASE |
91 { | 92 { |
92 // Control nodes that were not control-reachable from end may float. | 93 // Control nodes that were not control-reachable from end may float. |
93 data->placement_ = kSchedulable; | 94 data->placement_ = kSchedulable; |
94 if (!data->is_connected_control_) { | |
95 data->is_floating_control_ = true; | |
96 Trace("Floating control found: #%d:%s\n", node->id(), | |
97 node->op()->mnemonic()); | |
98 } | |
99 break; | 95 break; |
100 } | 96 } |
101 default: | 97 default: |
102 data->placement_ = kSchedulable; | 98 data->placement_ = kSchedulable; |
103 break; | 99 break; |
104 } | 100 } |
105 } | 101 } |
106 return data->placement_; | 102 return data->placement_; |
107 } | 103 } |
108 | 104 |
109 | 105 |
110 void Scheduler::UpdatePlacement(Node* node, Placement placement) { | 106 void Scheduler::UpdatePlacement(Node* node, Placement placement) { |
111 SchedulerData* data = GetData(node); | 107 SchedulerData* data = GetData(node); |
112 if (data->placement_ != kUnknown) { // Trap on mutation, not initialization. | 108 if (data->placement_ != kUnknown) { // Trap on mutation, not initialization. |
113 switch (node->opcode()) { | 109 switch (node->opcode()) { |
114 case IrOpcode::kParameter: | 110 case IrOpcode::kParameter: |
115 // Parameters are fixed once and for all. | 111 // Parameters are fixed once and for all. |
116 UNREACHABLE(); | 112 UNREACHABLE(); |
117 break; | 113 break; |
118 case IrOpcode::kPhi: | 114 case IrOpcode::kPhi: |
119 case IrOpcode::kEffectPhi: { | 115 case IrOpcode::kEffectPhi: { |
120 // Phis and effect phis are coupled to their respective blocks. | 116 // Phis and effect phis are coupled to their respective blocks. |
121 DCHECK_EQ(Scheduler::kCoupled, data->placement_); | 117 DCHECK_EQ(Scheduler::kCoupled, data->placement_); |
122 DCHECK_EQ(Scheduler::kFixed, placement); | 118 DCHECK_EQ(Scheduler::kFixed, placement); |
123 Node* control = NodeProperties::GetControlInput(node); | 119 Node* control = NodeProperties::GetControlInput(node); |
124 BasicBlock* block = schedule_->block(control); | 120 BasicBlock* block = schedule_->block(control); |
125 schedule_->AddNode(block, node); | 121 schedule_->AddNode(block, node); |
126 break; | 122 break; |
127 } | 123 } |
128 #define DEFINE_FLOATING_CONTROL_CASE(V) case IrOpcode::k##V: | 124 #define DEFINE_CONTROL_CASE(V) case IrOpcode::k##V: |
129 CONTROL_OP_LIST(DEFINE_FLOATING_CONTROL_CASE) | 125 CONTROL_OP_LIST(DEFINE_CONTROL_CASE) |
130 #undef DEFINE_FLOATING_CONTROL_CASE | 126 #undef DEFINE_CONTROL_CASE |
131 { | 127 { |
132 // Control nodes force coupled uses to be placed. | 128 // Control nodes force coupled uses to be placed. |
133 Node::Uses uses = node->uses(); | 129 Node::Uses uses = node->uses(); |
134 for (Node::Uses::iterator i = uses.begin(); i != uses.end(); ++i) { | 130 for (Node::Uses::iterator i = uses.begin(); i != uses.end(); ++i) { |
135 if (GetPlacement(*i) == Scheduler::kCoupled) { | 131 if (GetPlacement(*i) == Scheduler::kCoupled) { |
136 DCHECK_EQ(node, NodeProperties::GetControlInput(*i)); | 132 DCHECK_EQ(node, NodeProperties::GetControlInput(*i)); |
137 UpdatePlacement(*i, placement); | 133 UpdatePlacement(*i, placement); |
138 } | 134 } |
139 } | 135 } |
140 break; | 136 break; |
(...skipping 93 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
234 // between them within a Schedule) from the node graph. Visits control edges of | 230 // between them within a Schedule) from the node graph. Visits control edges of |
235 // the graph backwards from an end node in order to find the connected control | 231 // the graph backwards from an end node in order to find the connected control |
236 // subgraph, needed for scheduling. | 232 // subgraph, needed for scheduling. |
237 class CFGBuilder : public ZoneObject { | 233 class CFGBuilder : public ZoneObject { |
238 public: | 234 public: |
239 CFGBuilder(Zone* zone, Scheduler* scheduler) | 235 CFGBuilder(Zone* zone, Scheduler* scheduler) |
240 : scheduler_(scheduler), | 236 : scheduler_(scheduler), |
241 schedule_(scheduler->schedule_), | 237 schedule_(scheduler->schedule_), |
242 queue_(zone), | 238 queue_(zone), |
243 control_(zone), | 239 control_(zone), |
244 component_head_(NULL), | 240 component_entry_(NULL), |
245 component_start_(NULL), | 241 component_start_(NULL), |
246 component_end_(NULL) {} | 242 component_end_(NULL) {} |
247 | 243 |
248 // Run the control flow graph construction algorithm by walking the graph | 244 // Run the control flow graph construction algorithm by walking the graph |
249 // backwards from end through control edges, building and connecting the | 245 // backwards from end through control edges, building and connecting the |
250 // basic blocks for control nodes. | 246 // basic blocks for control nodes. |
251 void Run() { | 247 void Run() { |
252 ResetDataStructures(); | 248 ResetDataStructures(); |
253 Queue(scheduler_->graph_->end()); | 249 Queue(scheduler_->graph_->end()); |
254 | 250 |
255 while (!queue_.empty()) { // Breadth-first backwards traversal. | 251 while (!queue_.empty()) { // Breadth-first backwards traversal. |
256 Node* node = queue_.front(); | 252 Node* node = queue_.front(); |
257 queue_.pop(); | 253 queue_.pop(); |
258 int max = NodeProperties::PastControlIndex(node); | 254 int max = NodeProperties::PastControlIndex(node); |
259 for (int i = NodeProperties::FirstControlIndex(node); i < max; i++) { | 255 for (int i = NodeProperties::FirstControlIndex(node); i < max; i++) { |
260 Queue(node->InputAt(i)); | 256 Queue(node->InputAt(i)); |
261 } | 257 } |
262 } | 258 } |
263 | 259 |
264 for (NodeVector::iterator i = control_.begin(); i != control_.end(); ++i) { | 260 for (NodeVector::iterator i = control_.begin(); i != control_.end(); ++i) { |
265 ConnectBlocks(*i); // Connect block to its predecessor/successors. | 261 ConnectBlocks(*i); // Connect block to its predecessor/successors. |
266 } | 262 } |
267 } | 263 } |
268 | 264 |
269 // Run the control flow graph construction for a minimal control-connected | 265 // Run the control flow graph construction for a minimal control-connected |
270 // component ending in {node} and merge that component into an existing | 266 // component ending in {exit} and merge that component into an existing |
271 // control flow graph at the bottom of {block}. | 267 // control flow graph at the bottom of {block}. |
272 void Run(BasicBlock* block, Node* node) { | 268 void Run(BasicBlock* block, Node* exit) { |
273 ResetDataStructures(); | 269 ResetDataStructures(); |
274 Queue(node); | 270 Queue(exit); |
275 | 271 |
| 272 component_entry_ = NULL; |
276 component_start_ = block; | 273 component_start_ = block; |
277 component_end_ = schedule_->block(node); | 274 component_end_ = schedule_->block(exit); |
| 275 scheduler_->equivalence_->Run(exit); |
278 while (!queue_.empty()) { // Breadth-first backwards traversal. | 276 while (!queue_.empty()) { // Breadth-first backwards traversal. |
279 Node* node = queue_.front(); | 277 Node* node = queue_.front(); |
280 queue_.pop(); | 278 queue_.pop(); |
281 bool is_dom = true; | 279 |
| 280 // Use control dependence equivalence to find a canonical single-entry |
| 281 // single-exit region that makes up a minimal component to be scheduled. |
| 282 if (IsSingleEntrySingleExitRegion(node, exit)) { |
| 283 Trace("Found SESE at #%d:%s\n", node->id(), node->op()->mnemonic()); |
| 284 DCHECK_EQ(NULL, component_entry_); |
| 285 component_entry_ = node; |
| 286 continue; |
| 287 } |
| 288 |
282 int max = NodeProperties::PastControlIndex(node); | 289 int max = NodeProperties::PastControlIndex(node); |
283 for (int i = NodeProperties::FirstControlIndex(node); i < max; i++) { | 290 for (int i = NodeProperties::FirstControlIndex(node); i < max; i++) { |
284 is_dom = is_dom && | |
285 !scheduler_->GetData(node->InputAt(i))->is_floating_control_; | |
286 Queue(node->InputAt(i)); | 291 Queue(node->InputAt(i)); |
287 } | 292 } |
288 // TODO(mstarzinger): This is a hacky way to find component dominator. | |
289 if (is_dom) component_head_ = node; | |
290 } | 293 } |
291 DCHECK_NOT_NULL(component_head_); | 294 DCHECK_NE(NULL, component_entry_); |
292 | 295 |
293 for (NodeVector::iterator i = control_.begin(); i != control_.end(); ++i) { | 296 for (NodeVector::iterator i = control_.begin(); i != control_.end(); ++i) { |
294 scheduler_->GetData(*i)->is_floating_control_ = false; | |
295 ConnectBlocks(*i); // Connect block to its predecessor/successors. | 297 ConnectBlocks(*i); // Connect block to its predecessor/successors. |
296 } | 298 } |
297 } | 299 } |
298 | 300 |
299 private: | 301 private: |
300 // TODO(mstarzinger): Only for Scheduler::FuseFloatingControl. | 302 // TODO(mstarzinger): Only for Scheduler::FuseFloatingControl. |
301 friend class Scheduler; | 303 friend class Scheduler; |
302 | 304 |
303 void FixNode(BasicBlock* block, Node* node) { | 305 void FixNode(BasicBlock* block, Node* node) { |
304 schedule_->AddNode(block, node); | 306 schedule_->AddNode(block, node); |
305 scheduler_->UpdatePlacement(node, Scheduler::kFixed); | 307 scheduler_->UpdatePlacement(node, Scheduler::kFixed); |
306 } | 308 } |
307 | 309 |
308 void Queue(Node* node) { | 310 void Queue(Node* node) { |
309 // Mark the connected control nodes as they are queued. | 311 // Mark the connected control nodes as they are queued. |
310 Scheduler::SchedulerData* data = scheduler_->GetData(node); | 312 Scheduler::SchedulerData* data = scheduler_->GetData(node); |
311 if (!data->is_connected_control_) { | 313 if (!data->is_connected_control_) { |
312 data->is_connected_control_ = true; | 314 data->is_connected_control_ = true; |
313 BuildBlocks(node); | 315 BuildBlocks(node); |
314 queue_.push(node); | 316 queue_.push(node); |
315 control_.push_back(node); | 317 control_.push_back(node); |
316 } | 318 } |
317 } | 319 } |
318 | 320 |
319 | |
320 void BuildBlocks(Node* node) { | 321 void BuildBlocks(Node* node) { |
321 switch (node->opcode()) { | 322 switch (node->opcode()) { |
322 case IrOpcode::kEnd: | 323 case IrOpcode::kEnd: |
323 FixNode(schedule_->end(), node); | 324 FixNode(schedule_->end(), node); |
324 break; | 325 break; |
325 case IrOpcode::kStart: | 326 case IrOpcode::kStart: |
326 FixNode(schedule_->start(), node); | 327 FixNode(schedule_->start(), node); |
327 break; | 328 break; |
328 case IrOpcode::kLoop: | 329 case IrOpcode::kLoop: |
329 case IrOpcode::kMerge: | 330 case IrOpcode::kMerge: |
(...skipping 53 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
383 } | 384 } |
384 | 385 |
385 // Collect the branch-related projections from a node, such as IfTrue, | 386 // Collect the branch-related projections from a node, such as IfTrue, |
386 // IfFalse. | 387 // IfFalse. |
387 // TODO(titzer): consider moving this to node.h | 388 // TODO(titzer): consider moving this to node.h |
388 void CollectSuccessorProjections(Node* node, Node** buffer, | 389 void CollectSuccessorProjections(Node* node, Node** buffer, |
389 IrOpcode::Value true_opcode, | 390 IrOpcode::Value true_opcode, |
390 IrOpcode::Value false_opcode) { | 391 IrOpcode::Value false_opcode) { |
391 buffer[0] = NULL; | 392 buffer[0] = NULL; |
392 buffer[1] = NULL; | 393 buffer[1] = NULL; |
393 for (UseIter i = node->uses().begin(); i != node->uses().end(); ++i) { | 394 for (Node* use : node->uses()) { |
394 if ((*i)->opcode() == true_opcode) { | 395 if (use->opcode() == true_opcode) { |
395 DCHECK_EQ(NULL, buffer[0]); | 396 DCHECK_EQ(NULL, buffer[0]); |
396 buffer[0] = *i; | 397 buffer[0] = use; |
397 } | 398 } |
398 if ((*i)->opcode() == false_opcode) { | 399 if (use->opcode() == false_opcode) { |
399 DCHECK_EQ(NULL, buffer[1]); | 400 DCHECK_EQ(NULL, buffer[1]); |
400 buffer[1] = *i; | 401 buffer[1] = use; |
401 } | 402 } |
402 } | 403 } |
403 DCHECK_NE(NULL, buffer[0]); | 404 DCHECK_NE(NULL, buffer[0]); |
404 DCHECK_NE(NULL, buffer[1]); | 405 DCHECK_NE(NULL, buffer[1]); |
405 } | 406 } |
406 | 407 |
407 void CollectSuccessorBlocks(Node* node, BasicBlock** buffer, | 408 void CollectSuccessorBlocks(Node* node, BasicBlock** buffer, |
408 IrOpcode::Value true_opcode, | 409 IrOpcode::Value true_opcode, |
409 IrOpcode::Value false_opcode) { | 410 IrOpcode::Value false_opcode) { |
410 Node* successors[2]; | 411 Node* successors[2]; |
(...skipping 12 matching lines...) Expand all Loading... |
423 case BranchHint::kNone: | 424 case BranchHint::kNone: |
424 break; | 425 break; |
425 case BranchHint::kTrue: | 426 case BranchHint::kTrue: |
426 successor_blocks[1]->set_deferred(true); | 427 successor_blocks[1]->set_deferred(true); |
427 break; | 428 break; |
428 case BranchHint::kFalse: | 429 case BranchHint::kFalse: |
429 successor_blocks[0]->set_deferred(true); | 430 successor_blocks[0]->set_deferred(true); |
430 break; | 431 break; |
431 } | 432 } |
432 | 433 |
433 if (branch == component_head_) { | 434 if (branch == component_entry_) { |
434 TraceConnect(branch, component_start_, successor_blocks[0]); | 435 TraceConnect(branch, component_start_, successor_blocks[0]); |
435 TraceConnect(branch, component_start_, successor_blocks[1]); | 436 TraceConnect(branch, component_start_, successor_blocks[1]); |
436 schedule_->InsertBranch(component_start_, component_end_, branch, | 437 schedule_->InsertBranch(component_start_, component_end_, branch, |
437 successor_blocks[0], successor_blocks[1]); | 438 successor_blocks[0], successor_blocks[1]); |
438 } else { | 439 } else { |
439 Node* branch_block_node = NodeProperties::GetControlInput(branch); | 440 Node* branch_block_node = NodeProperties::GetControlInput(branch); |
440 BasicBlock* branch_block = schedule_->block(branch_block_node); | 441 BasicBlock* branch_block = schedule_->block(branch_block_node); |
441 DCHECK(branch_block != NULL); | 442 DCHECK(branch_block != NULL); |
442 | 443 |
443 TraceConnect(branch, branch_block, successor_blocks[0]); | 444 TraceConnect(branch, branch_block, successor_blocks[0]); |
444 TraceConnect(branch, branch_block, successor_blocks[1]); | 445 TraceConnect(branch, branch_block, successor_blocks[1]); |
445 schedule_->AddBranch(branch_block, branch, successor_blocks[0], | 446 schedule_->AddBranch(branch_block, branch, successor_blocks[0], |
446 successor_blocks[1]); | 447 successor_blocks[1]); |
447 } | 448 } |
448 } | 449 } |
449 | 450 |
450 void ConnectMerge(Node* merge) { | 451 void ConnectMerge(Node* merge) { |
451 // Don't connect the special merge at the end to its predecessors. | 452 // Don't connect the special merge at the end to its predecessors. |
452 if (IsFinalMerge(merge)) return; | 453 if (IsFinalMerge(merge)) return; |
453 | 454 |
454 BasicBlock* block = schedule_->block(merge); | 455 BasicBlock* block = schedule_->block(merge); |
455 DCHECK(block != NULL); | 456 DCHECK(block != NULL); |
456 // For all of the merge's control inputs, add a goto at the end to the | 457 // For all of the merge's control inputs, add a goto at the end to the |
457 // merge's basic block. | 458 // merge's basic block. |
458 for (Node* const j : merge->inputs()) { | 459 for (Node* const input : merge->inputs()) { |
459 BasicBlock* predecessor_block = schedule_->block(j); | 460 BasicBlock* predecessor_block = schedule_->block(input); |
460 TraceConnect(merge, predecessor_block, block); | 461 TraceConnect(merge, predecessor_block, block); |
461 schedule_->AddGoto(predecessor_block, block); | 462 schedule_->AddGoto(predecessor_block, block); |
462 } | 463 } |
463 } | 464 } |
464 | 465 |
465 void ConnectReturn(Node* ret) { | 466 void ConnectReturn(Node* ret) { |
466 Node* return_block_node = NodeProperties::GetControlInput(ret); | 467 Node* return_block_node = NodeProperties::GetControlInput(ret); |
467 BasicBlock* return_block = schedule_->block(return_block_node); | 468 BasicBlock* return_block = schedule_->block(return_block_node); |
468 TraceConnect(ret, return_block, NULL); | 469 TraceConnect(ret, return_block, NULL); |
469 schedule_->AddReturn(return_block, ret); | 470 schedule_->AddReturn(return_block, ret); |
470 } | 471 } |
471 | 472 |
472 void TraceConnect(Node* node, BasicBlock* block, BasicBlock* succ) { | 473 void TraceConnect(Node* node, BasicBlock* block, BasicBlock* succ) { |
473 DCHECK_NE(NULL, block); | 474 DCHECK_NE(NULL, block); |
474 if (succ == NULL) { | 475 if (succ == NULL) { |
475 Trace("Connect #%d:%s, B%d -> end\n", node->id(), node->op()->mnemonic(), | 476 Trace("Connect #%d:%s, B%d -> end\n", node->id(), node->op()->mnemonic(), |
476 block->id().ToInt()); | 477 block->id().ToInt()); |
477 } else { | 478 } else { |
478 Trace("Connect #%d:%s, B%d -> B%d\n", node->id(), node->op()->mnemonic(), | 479 Trace("Connect #%d:%s, B%d -> B%d\n", node->id(), node->op()->mnemonic(), |
479 block->id().ToInt(), succ->id().ToInt()); | 480 block->id().ToInt(), succ->id().ToInt()); |
480 } | 481 } |
481 } | 482 } |
482 | 483 |
483 bool IsFinalMerge(Node* node) { | 484 bool IsFinalMerge(Node* node) { |
484 return (node->opcode() == IrOpcode::kMerge && | 485 return (node->opcode() == IrOpcode::kMerge && |
485 node == scheduler_->graph_->end()->InputAt(0)); | 486 node == scheduler_->graph_->end()->InputAt(0)); |
486 } | 487 } |
487 | 488 |
| 489 bool IsSingleEntrySingleExitRegion(Node* entry, Node* exit) const { |
| 490 size_t entry_class = scheduler_->equivalence_->ClassOf(entry); |
| 491 size_t exit_class = scheduler_->equivalence_->ClassOf(exit); |
| 492 return entry != exit && entry_class == exit_class; |
| 493 } |
| 494 |
488 void ResetDataStructures() { | 495 void ResetDataStructures() { |
489 control_.clear(); | 496 control_.clear(); |
490 DCHECK(queue_.empty()); | 497 DCHECK(queue_.empty()); |
491 DCHECK(control_.empty()); | 498 DCHECK(control_.empty()); |
492 } | 499 } |
493 | 500 |
494 Scheduler* scheduler_; | 501 Scheduler* scheduler_; |
495 Schedule* schedule_; | 502 Schedule* schedule_; |
496 ZoneQueue<Node*> queue_; | 503 ZoneQueue<Node*> queue_; |
497 NodeVector control_; | 504 NodeVector control_; |
498 Node* component_head_; | 505 Node* component_entry_; |
499 BasicBlock* component_start_; | 506 BasicBlock* component_start_; |
500 BasicBlock* component_end_; | 507 BasicBlock* component_end_; |
501 }; | 508 }; |
502 | 509 |
503 | 510 |
504 void Scheduler::BuildCFG() { | 511 void Scheduler::BuildCFG() { |
505 Trace("--- CREATING CFG -------------------------------------------\n"); | 512 Trace("--- CREATING CFG -------------------------------------------\n"); |
506 | 513 |
| 514 // Instantiate a new control equivalence algorithm for the graph. |
| 515 equivalence_ = new (zone_) ControlEquivalence(zone_, graph_); |
| 516 |
507 // Build a control-flow graph for the main control-connected component that | 517 // Build a control-flow graph for the main control-connected component that |
508 // is being spanned by the graph's start and end nodes. | 518 // is being spanned by the graph's start and end nodes. |
509 control_flow_builder_ = new (zone_) CFGBuilder(zone_, this); | 519 control_flow_builder_ = new (zone_) CFGBuilder(zone_, this); |
510 control_flow_builder_->Run(); | 520 control_flow_builder_->Run(); |
511 | 521 |
512 // Initialize per-block data. | 522 // Initialize per-block data. |
513 scheduled_nodes_.resize(schedule_->BasicBlockCount(), NodeVector(zone_)); | 523 scheduled_nodes_.resize(schedule_->BasicBlockCount(), NodeVector(zone_)); |
514 } | 524 } |
515 | 525 |
516 | 526 |
(...skipping 839 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1356 } | 1366 } |
1357 } | 1367 } |
1358 BasicBlock* result = schedule_->block(use); | 1368 BasicBlock* result = schedule_->block(use); |
1359 if (result == NULL) return NULL; | 1369 if (result == NULL) return NULL; |
1360 Trace(" must dominate use #%d:%s in B%d\n", use->id(), | 1370 Trace(" must dominate use #%d:%s in B%d\n", use->id(), |
1361 use->op()->mnemonic(), result->id().ToInt()); | 1371 use->op()->mnemonic(), result->id().ToInt()); |
1362 return result; | 1372 return result; |
1363 } | 1373 } |
1364 | 1374 |
1365 void ScheduleFloatingControl(BasicBlock* block, Node* node) { | 1375 void ScheduleFloatingControl(BasicBlock* block, Node* node) { |
1366 DCHECK(scheduler_->GetData(node)->is_floating_control_); | |
1367 scheduler_->FuseFloatingControl(block, node); | 1376 scheduler_->FuseFloatingControl(block, node); |
1368 } | 1377 } |
1369 | 1378 |
1370 void ScheduleNode(BasicBlock* block, Node* node) { | 1379 void ScheduleNode(BasicBlock* block, Node* node) { |
1371 schedule_->PlanNode(block, node); | 1380 schedule_->PlanNode(block, node); |
1372 scheduler_->scheduled_nodes_[block->id().ToSize()].push_back(node); | 1381 scheduler_->scheduled_nodes_[block->id().ToSize()].push_back(node); |
1373 scheduler_->UpdatePlacement(node, Scheduler::kScheduled); | 1382 scheduler_->UpdatePlacement(node, Scheduler::kScheduled); |
1374 } | 1383 } |
1375 | 1384 |
1376 Scheduler* scheduler_; | 1385 Scheduler* scheduler_; |
(...skipping 105 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1482 for (NodeVectorIter i = nodes->begin(); i != nodes->end(); ++i) { | 1491 for (NodeVectorIter i = nodes->begin(); i != nodes->end(); ++i) { |
1483 schedule_->SetBlockForNode(to, *i); | 1492 schedule_->SetBlockForNode(to, *i); |
1484 scheduled_nodes_[to->id().ToSize()].push_back(*i); | 1493 scheduled_nodes_[to->id().ToSize()].push_back(*i); |
1485 } | 1494 } |
1486 nodes->clear(); | 1495 nodes->clear(); |
1487 } | 1496 } |
1488 | 1497 |
1489 } // namespace compiler | 1498 } // namespace compiler |
1490 } // namespace internal | 1499 } // namespace internal |
1491 } // namespace v8 | 1500 } // namespace v8 |
OLD | NEW |