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 "src/compiler/graph.h" | 7 #include "src/compiler/graph.h" |
8 #include "src/compiler/graph-inl.h" | 8 #include "src/compiler/graph-inl.h" |
9 #include "src/compiler/node.h" | 9 #include "src/compiler/node.h" |
10 #include "src/compiler/node-properties.h" | 10 #include "src/compiler/node-properties.h" |
(...skipping 149 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
160 NodeVector(NodeVector::allocator_type(zone))); | 160 NodeVector(NodeVector::allocator_type(zone))); |
161 schedule_->immediate_dominator_.resize(schedule_->BasicBlockCount(), NULL); | 161 schedule_->immediate_dominator_.resize(schedule_->BasicBlockCount(), NULL); |
162 } | 162 } |
163 | 163 |
164 | 164 |
165 void Scheduler::AddPredecessorsForLoopsAndMerges() { | 165 void Scheduler::AddPredecessorsForLoopsAndMerges() { |
166 for (NodeVectorIter i = loops_and_merges_.begin(); | 166 for (NodeVectorIter i = loops_and_merges_.begin(); |
167 i != loops_and_merges_.end(); ++i) { | 167 i != loops_and_merges_.end(); ++i) { |
168 Node* merge_or_loop = *i; | 168 Node* merge_or_loop = *i; |
169 BasicBlock* block = schedule_->block(merge_or_loop); | 169 BasicBlock* block = schedule_->block(merge_or_loop); |
170 ASSERT(block != NULL); | 170 DCHECK(block != NULL); |
171 // For all of the merge's control inputs, add a goto at the end to the | 171 // For all of the merge's control inputs, add a goto at the end to the |
172 // merge's basic block. | 172 // merge's basic block. |
173 for (InputIter j = (*i)->inputs().begin(); j != (*i)->inputs().end(); ++j) { | 173 for (InputIter j = (*i)->inputs().begin(); j != (*i)->inputs().end(); ++j) { |
174 if (NodeProperties::IsBasicBlockBegin(*i)) { | 174 if (NodeProperties::IsBasicBlockBegin(*i)) { |
175 BasicBlock* predecessor_block = schedule_->block(*j); | 175 BasicBlock* predecessor_block = schedule_->block(*j); |
176 if ((*j)->opcode() != IrOpcode::kReturn && | 176 if ((*j)->opcode() != IrOpcode::kReturn && |
177 (*j)->opcode() != IrOpcode::kDeoptimize) { | 177 (*j)->opcode() != IrOpcode::kDeoptimize) { |
178 ASSERT(predecessor_block != NULL); | 178 DCHECK(predecessor_block != NULL); |
179 if (FLAG_trace_turbo_scheduler) { | 179 if (FLAG_trace_turbo_scheduler) { |
180 IrOpcode::Value opcode = (*i)->opcode(); | 180 IrOpcode::Value opcode = (*i)->opcode(); |
181 PrintF("node %d (%s) in block %d -> block %d\n", (*i)->id(), | 181 PrintF("node %d (%s) in block %d -> block %d\n", (*i)->id(), |
182 IrOpcode::Mnemonic(opcode), predecessor_block->id(), | 182 IrOpcode::Mnemonic(opcode), predecessor_block->id(), |
183 block->id()); | 183 block->id()); |
184 } | 184 } |
185 schedule_->AddGoto(predecessor_block, block); | 185 schedule_->AddGoto(predecessor_block, block); |
186 } | 186 } |
187 } | 187 } |
188 } | 188 } |
189 } | 189 } |
190 } | 190 } |
191 | 191 |
192 | 192 |
193 void Scheduler::AddSuccessorsForCalls() { | 193 void Scheduler::AddSuccessorsForCalls() { |
194 for (NodeVectorIter i = calls_.begin(); i != calls_.end(); ++i) { | 194 for (NodeVectorIter i = calls_.begin(); i != calls_.end(); ++i) { |
195 Node* call = *i; | 195 Node* call = *i; |
196 ASSERT(call->opcode() == IrOpcode::kCall); | 196 DCHECK(call->opcode() == IrOpcode::kCall); |
197 ASSERT(NodeProperties::CanLazilyDeoptimize(call)); | 197 DCHECK(NodeProperties::CanLazilyDeoptimize(call)); |
198 | 198 |
199 Node* lazy_deopt_node = NULL; | 199 Node* lazy_deopt_node = NULL; |
200 Node* cont_node = NULL; | 200 Node* cont_node = NULL; |
201 // Find the continuation and lazy-deopt nodes among the uses. | 201 // Find the continuation and lazy-deopt nodes among the uses. |
202 for (UseIter use_iter = call->uses().begin(); | 202 for (UseIter use_iter = call->uses().begin(); |
203 use_iter != call->uses().end(); ++use_iter) { | 203 use_iter != call->uses().end(); ++use_iter) { |
204 switch ((*use_iter)->opcode()) { | 204 switch ((*use_iter)->opcode()) { |
205 case IrOpcode::kContinuation: { | 205 case IrOpcode::kContinuation: { |
206 ASSERT(cont_node == NULL); | 206 DCHECK(cont_node == NULL); |
207 cont_node = *use_iter; | 207 cont_node = *use_iter; |
208 break; | 208 break; |
209 } | 209 } |
210 case IrOpcode::kLazyDeoptimization: { | 210 case IrOpcode::kLazyDeoptimization: { |
211 ASSERT(lazy_deopt_node == NULL); | 211 DCHECK(lazy_deopt_node == NULL); |
212 lazy_deopt_node = *use_iter; | 212 lazy_deopt_node = *use_iter; |
213 break; | 213 break; |
214 } | 214 } |
215 default: | 215 default: |
216 break; | 216 break; |
217 } | 217 } |
218 } | 218 } |
219 ASSERT(lazy_deopt_node != NULL); | 219 DCHECK(lazy_deopt_node != NULL); |
220 ASSERT(cont_node != NULL); | 220 DCHECK(cont_node != NULL); |
221 BasicBlock* cont_successor_block = schedule_->block(cont_node); | 221 BasicBlock* cont_successor_block = schedule_->block(cont_node); |
222 BasicBlock* deopt_successor_block = schedule_->block(lazy_deopt_node); | 222 BasicBlock* deopt_successor_block = schedule_->block(lazy_deopt_node); |
223 Node* call_block_node = NodeProperties::GetControlInput(call); | 223 Node* call_block_node = NodeProperties::GetControlInput(call); |
224 BasicBlock* call_block = schedule_->block(call_block_node); | 224 BasicBlock* call_block = schedule_->block(call_block_node); |
225 if (FLAG_trace_turbo_scheduler) { | 225 if (FLAG_trace_turbo_scheduler) { |
226 IrOpcode::Value opcode = call->opcode(); | 226 IrOpcode::Value opcode = call->opcode(); |
227 PrintF("node %d (%s) in block %d -> block %d\n", call->id(), | 227 PrintF("node %d (%s) in block %d -> block %d\n", call->id(), |
228 IrOpcode::Mnemonic(opcode), call_block->id(), | 228 IrOpcode::Mnemonic(opcode), call_block->id(), |
229 cont_successor_block->id()); | 229 cont_successor_block->id()); |
230 PrintF("node %d (%s) in block %d -> block %d\n", call->id(), | 230 PrintF("node %d (%s) in block %d -> block %d\n", call->id(), |
231 IrOpcode::Mnemonic(opcode), call_block->id(), | 231 IrOpcode::Mnemonic(opcode), call_block->id(), |
232 deopt_successor_block->id()); | 232 deopt_successor_block->id()); |
233 } | 233 } |
234 schedule_->AddCall(call_block, call, cont_successor_block, | 234 schedule_->AddCall(call_block, call, cont_successor_block, |
235 deopt_successor_block); | 235 deopt_successor_block); |
236 } | 236 } |
237 } | 237 } |
238 | 238 |
239 | 239 |
240 void Scheduler::AddSuccessorsForDeopts() { | 240 void Scheduler::AddSuccessorsForDeopts() { |
241 for (NodeVectorIter i = deopts_.begin(); i != deopts_.end(); ++i) { | 241 for (NodeVectorIter i = deopts_.begin(); i != deopts_.end(); ++i) { |
242 Node* deopt_block_node = NodeProperties::GetControlInput(*i); | 242 Node* deopt_block_node = NodeProperties::GetControlInput(*i); |
243 BasicBlock* deopt_block = schedule_->block(deopt_block_node); | 243 BasicBlock* deopt_block = schedule_->block(deopt_block_node); |
244 ASSERT(deopt_block != NULL); | 244 DCHECK(deopt_block != NULL); |
245 if (FLAG_trace_turbo_scheduler) { | 245 if (FLAG_trace_turbo_scheduler) { |
246 IrOpcode::Value opcode = (*i)->opcode(); | 246 IrOpcode::Value opcode = (*i)->opcode(); |
247 PrintF("node %d (%s) in block %d -> end\n", (*i)->id(), | 247 PrintF("node %d (%s) in block %d -> end\n", (*i)->id(), |
248 IrOpcode::Mnemonic(opcode), deopt_block->id()); | 248 IrOpcode::Mnemonic(opcode), deopt_block->id()); |
249 } | 249 } |
250 schedule_->AddDeoptimize(deopt_block, *i); | 250 schedule_->AddDeoptimize(deopt_block, *i); |
251 } | 251 } |
252 } | 252 } |
253 | 253 |
254 | 254 |
255 void Scheduler::AddSuccessorsForBranches() { | 255 void Scheduler::AddSuccessorsForBranches() { |
256 for (NodeVectorIter i = branches_.begin(); i != branches_.end(); ++i) { | 256 for (NodeVectorIter i = branches_.begin(); i != branches_.end(); ++i) { |
257 Node* branch = *i; | 257 Node* branch = *i; |
258 ASSERT(branch->opcode() == IrOpcode::kBranch); | 258 DCHECK(branch->opcode() == IrOpcode::kBranch); |
259 Node* branch_block_node = NodeProperties::GetControlInput(branch); | 259 Node* branch_block_node = NodeProperties::GetControlInput(branch); |
260 BasicBlock* branch_block = schedule_->block(branch_block_node); | 260 BasicBlock* branch_block = schedule_->block(branch_block_node); |
261 ASSERT(branch_block != NULL); | 261 DCHECK(branch_block != NULL); |
262 UseIter use_iter = branch->uses().begin(); | 262 UseIter use_iter = branch->uses().begin(); |
263 Node* first_successor = *use_iter; | 263 Node* first_successor = *use_iter; |
264 ++use_iter; | 264 ++use_iter; |
265 ASSERT(use_iter != branch->uses().end()); | 265 DCHECK(use_iter != branch->uses().end()); |
266 Node* second_successor = *use_iter; | 266 Node* second_successor = *use_iter; |
267 ASSERT(++use_iter == branch->uses().end()); | 267 DCHECK(++use_iter == branch->uses().end()); |
268 Node* true_successor_node = first_successor->opcode() == IrOpcode::kIfTrue | 268 Node* true_successor_node = first_successor->opcode() == IrOpcode::kIfTrue |
269 ? first_successor | 269 ? first_successor |
270 : second_successor; | 270 : second_successor; |
271 Node* false_successor_node = first_successor->opcode() == IrOpcode::kIfTrue | 271 Node* false_successor_node = first_successor->opcode() == IrOpcode::kIfTrue |
272 ? second_successor | 272 ? second_successor |
273 : first_successor; | 273 : first_successor; |
274 ASSERT(true_successor_node->opcode() == IrOpcode::kIfTrue); | 274 DCHECK(true_successor_node->opcode() == IrOpcode::kIfTrue); |
275 ASSERT(false_successor_node->opcode() == IrOpcode::kIfFalse); | 275 DCHECK(false_successor_node->opcode() == IrOpcode::kIfFalse); |
276 BasicBlock* true_successor_block = schedule_->block(true_successor_node); | 276 BasicBlock* true_successor_block = schedule_->block(true_successor_node); |
277 BasicBlock* false_successor_block = schedule_->block(false_successor_node); | 277 BasicBlock* false_successor_block = schedule_->block(false_successor_node); |
278 ASSERT(true_successor_block != NULL); | 278 DCHECK(true_successor_block != NULL); |
279 ASSERT(false_successor_block != NULL); | 279 DCHECK(false_successor_block != NULL); |
280 if (FLAG_trace_turbo_scheduler) { | 280 if (FLAG_trace_turbo_scheduler) { |
281 IrOpcode::Value opcode = branch->opcode(); | 281 IrOpcode::Value opcode = branch->opcode(); |
282 PrintF("node %d (%s) in block %d -> block %d\n", branch->id(), | 282 PrintF("node %d (%s) in block %d -> block %d\n", branch->id(), |
283 IrOpcode::Mnemonic(opcode), branch_block->id(), | 283 IrOpcode::Mnemonic(opcode), branch_block->id(), |
284 true_successor_block->id()); | 284 true_successor_block->id()); |
285 PrintF("node %d (%s) in block %d -> block %d\n", branch->id(), | 285 PrintF("node %d (%s) in block %d -> block %d\n", branch->id(), |
286 IrOpcode::Mnemonic(opcode), branch_block->id(), | 286 IrOpcode::Mnemonic(opcode), branch_block->id(), |
287 false_successor_block->id()); | 287 false_successor_block->id()); |
288 } | 288 } |
289 schedule_->AddBranch(branch_block, branch, true_successor_block, | 289 schedule_->AddBranch(branch_block, branch, true_successor_block, |
290 false_successor_block); | 290 false_successor_block); |
291 } | 291 } |
292 } | 292 } |
293 | 293 |
294 | 294 |
295 void Scheduler::AddSuccessorsForReturns() { | 295 void Scheduler::AddSuccessorsForReturns() { |
296 for (NodeVectorIter i = returns_.begin(); i != returns_.end(); ++i) { | 296 for (NodeVectorIter i = returns_.begin(); i != returns_.end(); ++i) { |
297 Node* return_block_node = NodeProperties::GetControlInput(*i); | 297 Node* return_block_node = NodeProperties::GetControlInput(*i); |
298 BasicBlock* return_block = schedule_->block(return_block_node); | 298 BasicBlock* return_block = schedule_->block(return_block_node); |
299 ASSERT(return_block != NULL); | 299 DCHECK(return_block != NULL); |
300 if (FLAG_trace_turbo_scheduler) { | 300 if (FLAG_trace_turbo_scheduler) { |
301 IrOpcode::Value opcode = (*i)->opcode(); | 301 IrOpcode::Value opcode = (*i)->opcode(); |
302 PrintF("node %d (%s) in block %d -> end\n", (*i)->id(), | 302 PrintF("node %d (%s) in block %d -> end\n", (*i)->id(), |
303 IrOpcode::Mnemonic(opcode), return_block->id()); | 303 IrOpcode::Mnemonic(opcode), return_block->id()); |
304 } | 304 } |
305 schedule_->AddReturn(return_block, *i); | 305 schedule_->AddReturn(return_block, *i); |
306 } | 306 } |
307 } | 307 } |
308 | 308 |
309 | 309 |
310 BasicBlock* Scheduler::GetCommonDominator(BasicBlock* b1, BasicBlock* b2) { | 310 BasicBlock* Scheduler::GetCommonDominator(BasicBlock* b1, BasicBlock* b2) { |
311 while (b1 != b2) { | 311 while (b1 != b2) { |
312 int b1_rpo = GetRPONumber(b1); | 312 int b1_rpo = GetRPONumber(b1); |
313 int b2_rpo = GetRPONumber(b2); | 313 int b2_rpo = GetRPONumber(b2); |
314 ASSERT(b1_rpo != b2_rpo); | 314 DCHECK(b1_rpo != b2_rpo); |
315 if (b1_rpo < b2_rpo) { | 315 if (b1_rpo < b2_rpo) { |
316 b2 = schedule_->immediate_dominator_[b2->id()]; | 316 b2 = schedule_->immediate_dominator_[b2->id()]; |
317 } else { | 317 } else { |
318 b1 = schedule_->immediate_dominator_[b1->id()]; | 318 b1 = schedule_->immediate_dominator_[b1->id()]; |
319 } | 319 } |
320 } | 320 } |
321 return b1; | 321 return b1; |
322 } | 322 } |
323 | 323 |
324 | 324 |
325 void Scheduler::GenerateImmediateDominatorTree() { | 325 void Scheduler::GenerateImmediateDominatorTree() { |
326 // Build the dominator graph. TODO(danno): consider using Lengauer & Tarjan's | 326 // Build the dominator graph. TODO(danno): consider using Lengauer & Tarjan's |
327 // if this becomes really slow. | 327 // if this becomes really slow. |
328 if (FLAG_trace_turbo_scheduler) { | 328 if (FLAG_trace_turbo_scheduler) { |
329 PrintF("------------ IMMEDIATE BLOCK DOMINATORS -----------\n"); | 329 PrintF("------------ IMMEDIATE BLOCK DOMINATORS -----------\n"); |
330 } | 330 } |
331 for (size_t i = 0; i < schedule_->rpo_order_.size(); i++) { | 331 for (size_t i = 0; i < schedule_->rpo_order_.size(); i++) { |
332 BasicBlock* current_rpo = schedule_->rpo_order_[i]; | 332 BasicBlock* current_rpo = schedule_->rpo_order_[i]; |
333 if (current_rpo != schedule_->entry()) { | 333 if (current_rpo != schedule_->entry()) { |
334 BasicBlock::Predecessors::iterator current_pred = | 334 BasicBlock::Predecessors::iterator current_pred = |
335 current_rpo->predecessors().begin(); | 335 current_rpo->predecessors().begin(); |
336 BasicBlock::Predecessors::iterator end = | 336 BasicBlock::Predecessors::iterator end = |
337 current_rpo->predecessors().end(); | 337 current_rpo->predecessors().end(); |
338 ASSERT(current_pred != end); | 338 DCHECK(current_pred != end); |
339 BasicBlock* dominator = *current_pred; | 339 BasicBlock* dominator = *current_pred; |
340 ++current_pred; | 340 ++current_pred; |
341 // For multiple predecessors, walk up the rpo ordering until a common | 341 // For multiple predecessors, walk up the rpo ordering until a common |
342 // dominator is found. | 342 // dominator is found. |
343 int current_rpo_pos = GetRPONumber(current_rpo); | 343 int current_rpo_pos = GetRPONumber(current_rpo); |
344 while (current_pred != end) { | 344 while (current_pred != end) { |
345 // Don't examine backwards edges | 345 // Don't examine backwards edges |
346 BasicBlock* pred = *current_pred; | 346 BasicBlock* pred = *current_pred; |
347 if (GetRPONumber(pred) < current_rpo_pos) { | 347 if (GetRPONumber(pred) < current_rpo_pos) { |
348 dominator = GetCommonDominator(dominator, *current_pred); | 348 dominator = GetCommonDominator(dominator, *current_pred); |
(...skipping 15 matching lines...) Expand all Loading... |
364 : has_changed_rpo_constraints_(true), | 364 : has_changed_rpo_constraints_(true), |
365 scheduler_(scheduler), | 365 scheduler_(scheduler), |
366 schedule_(scheduler->schedule_) {} | 366 schedule_(scheduler->schedule_) {} |
367 | 367 |
368 GenericGraphVisit::Control Pre(Node* node) { | 368 GenericGraphVisit::Control Pre(Node* node) { |
369 int id = node->id(); | 369 int id = node->id(); |
370 int max_rpo = 0; | 370 int max_rpo = 0; |
371 // Fixed nodes already know their schedule early position. | 371 // Fixed nodes already know their schedule early position. |
372 if (IsFixedNode(node)) { | 372 if (IsFixedNode(node)) { |
373 BasicBlock* block = schedule_->block(node); | 373 BasicBlock* block = schedule_->block(node); |
374 ASSERT(block != NULL); | 374 DCHECK(block != NULL); |
375 max_rpo = block->rpo_number_; | 375 max_rpo = block->rpo_number_; |
376 if (scheduler_->schedule_early_rpo_index_[id] != max_rpo) { | 376 if (scheduler_->schedule_early_rpo_index_[id] != max_rpo) { |
377 has_changed_rpo_constraints_ = true; | 377 has_changed_rpo_constraints_ = true; |
378 } | 378 } |
379 scheduler_->schedule_early_rpo_index_[id] = max_rpo; | 379 scheduler_->schedule_early_rpo_index_[id] = max_rpo; |
380 if (FLAG_trace_turbo_scheduler) { | 380 if (FLAG_trace_turbo_scheduler) { |
381 PrintF("Node %d pre-scheduled early at rpo limit %d\n", id, max_rpo); | 381 PrintF("Node %d pre-scheduled early at rpo limit %d\n", id, max_rpo); |
382 } | 382 } |
383 } | 383 } |
384 return GenericGraphVisit::CONTINUE; | 384 return GenericGraphVisit::CONTINUE; |
385 } | 385 } |
386 | 386 |
387 GenericGraphVisit::Control Post(Node* node) { | 387 GenericGraphVisit::Control Post(Node* node) { |
388 int id = node->id(); | 388 int id = node->id(); |
389 int max_rpo = 0; | 389 int max_rpo = 0; |
390 // Otherwise, the minimum rpo for the node is the max of all of the inputs. | 390 // Otherwise, the minimum rpo for the node is the max of all of the inputs. |
391 if (!IsFixedNode(node)) { | 391 if (!IsFixedNode(node)) { |
392 ASSERT(!NodeProperties::IsBasicBlockBegin(node)); | 392 DCHECK(!NodeProperties::IsBasicBlockBegin(node)); |
393 for (InputIter i = node->inputs().begin(); i != node->inputs().end(); | 393 for (InputIter i = node->inputs().begin(); i != node->inputs().end(); |
394 ++i) { | 394 ++i) { |
395 int control_rpo = scheduler_->schedule_early_rpo_index_[(*i)->id()]; | 395 int control_rpo = scheduler_->schedule_early_rpo_index_[(*i)->id()]; |
396 if (control_rpo > max_rpo) { | 396 if (control_rpo > max_rpo) { |
397 max_rpo = control_rpo; | 397 max_rpo = control_rpo; |
398 } | 398 } |
399 } | 399 } |
400 if (scheduler_->schedule_early_rpo_index_[id] != max_rpo) { | 400 if (scheduler_->schedule_early_rpo_index_[id] != max_rpo) { |
401 has_changed_rpo_constraints_ = true; | 401 has_changed_rpo_constraints_ = true; |
402 } | 402 } |
(...skipping 52 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
455 NodeProperties::HasFixedSchedulePosition(node)) { | 455 NodeProperties::HasFixedSchedulePosition(node)) { |
456 if (FLAG_trace_turbo_scheduler) { | 456 if (FLAG_trace_turbo_scheduler) { |
457 PrintF("Fixed position node %d is unscheduled, scheduling now\n", | 457 PrintF("Fixed position node %d is unscheduled, scheduling now\n", |
458 node->id()); | 458 node->id()); |
459 } | 459 } |
460 IrOpcode::Value opcode = node->opcode(); | 460 IrOpcode::Value opcode = node->opcode(); |
461 BasicBlock* block = | 461 BasicBlock* block = |
462 opcode == IrOpcode::kParameter | 462 opcode == IrOpcode::kParameter |
463 ? schedule_->entry() | 463 ? schedule_->entry() |
464 : schedule_->block(NodeProperties::GetControlInput(node)); | 464 : schedule_->block(NodeProperties::GetControlInput(node)); |
465 ASSERT(block != NULL); | 465 DCHECK(block != NULL); |
466 schedule_->AddNode(block, node); | 466 schedule_->AddNode(block, node); |
467 } | 467 } |
468 | 468 |
469 if (NodeProperties::IsScheduleRoot(node)) { | 469 if (NodeProperties::IsScheduleRoot(node)) { |
470 scheduler_->schedule_root_nodes_.push_back(node); | 470 scheduler_->schedule_root_nodes_.push_back(node); |
471 } | 471 } |
472 | 472 |
473 return GenericGraphVisit::CONTINUE; | 473 return GenericGraphVisit::CONTINUE; |
474 } | 474 } |
475 | 475 |
476 void PostEdge(Node* from, int index, Node* to) { | 476 void PostEdge(Node* from, int index, Node* to) { |
477 // If the edge is from an unscheduled node, then tally it in the use count | 477 // If the edge is from an unscheduled node, then tally it in the use count |
478 // for all of its inputs. The same criterion will be used in ScheduleLate | 478 // for all of its inputs. The same criterion will be used in ScheduleLate |
479 // for decrementing use counts. | 479 // for decrementing use counts. |
480 if (!schedule_->IsScheduled(from) && NodeProperties::CanBeScheduled(from)) { | 480 if (!schedule_->IsScheduled(from) && NodeProperties::CanBeScheduled(from)) { |
481 ASSERT(!NodeProperties::HasFixedSchedulePosition(from)); | 481 DCHECK(!NodeProperties::HasFixedSchedulePosition(from)); |
482 ++scheduler_->unscheduled_uses_[to->id()]; | 482 ++scheduler_->unscheduled_uses_[to->id()]; |
483 if (FLAG_trace_turbo_scheduler) { | 483 if (FLAG_trace_turbo_scheduler) { |
484 PrintF("Incrementing uses of node %d from %d to %d\n", to->id(), | 484 PrintF("Incrementing uses of node %d from %d to %d\n", to->id(), |
485 from->id(), scheduler_->unscheduled_uses_[to->id()]); | 485 from->id(), scheduler_->unscheduled_uses_[to->id()]); |
486 } | 486 } |
487 } | 487 } |
488 } | 488 } |
489 | 489 |
490 private: | 490 private: |
491 Scheduler* scheduler_; | 491 Scheduler* scheduler_; |
(...skipping 15 matching lines...) Expand all Loading... |
507 class ScheduleLateNodeVisitor : public NullNodeVisitor { | 507 class ScheduleLateNodeVisitor : public NullNodeVisitor { |
508 public: | 508 public: |
509 explicit ScheduleLateNodeVisitor(Scheduler* scheduler) | 509 explicit ScheduleLateNodeVisitor(Scheduler* scheduler) |
510 : scheduler_(scheduler), schedule_(scheduler_->schedule_) {} | 510 : scheduler_(scheduler), schedule_(scheduler_->schedule_) {} |
511 | 511 |
512 GenericGraphVisit::Control Pre(Node* node) { | 512 GenericGraphVisit::Control Pre(Node* node) { |
513 // Don't schedule nodes that cannot be scheduled or are already scheduled. | 513 // Don't schedule nodes that cannot be scheduled or are already scheduled. |
514 if (!NodeProperties::CanBeScheduled(node) || schedule_->IsScheduled(node)) { | 514 if (!NodeProperties::CanBeScheduled(node) || schedule_->IsScheduled(node)) { |
515 return GenericGraphVisit::CONTINUE; | 515 return GenericGraphVisit::CONTINUE; |
516 } | 516 } |
517 ASSERT(!NodeProperties::HasFixedSchedulePosition(node)); | 517 DCHECK(!NodeProperties::HasFixedSchedulePosition(node)); |
518 | 518 |
519 // If all the uses of a node have been scheduled, then the node itself can | 519 // If all the uses of a node have been scheduled, then the node itself can |
520 // be scheduled. | 520 // be scheduled. |
521 bool eligible = scheduler_->unscheduled_uses_[node->id()] == 0; | 521 bool eligible = scheduler_->unscheduled_uses_[node->id()] == 0; |
522 if (FLAG_trace_turbo_scheduler) { | 522 if (FLAG_trace_turbo_scheduler) { |
523 PrintF("Testing for schedule eligibility for node %d -> %s\n", node->id(), | 523 PrintF("Testing for schedule eligibility for node %d -> %s\n", node->id(), |
524 eligible ? "true" : "false"); | 524 eligible ? "true" : "false"); |
525 } | 525 } |
526 if (!eligible) return GenericGraphVisit::DEFER; | 526 if (!eligible) return GenericGraphVisit::DEFER; |
527 | 527 |
528 // Determine the dominating block for all of the uses of this node. It is | 528 // Determine the dominating block for all of the uses of this node. It is |
529 // the latest block that this node can be scheduled in. | 529 // the latest block that this node can be scheduled in. |
530 BasicBlock* block = NULL; | 530 BasicBlock* block = NULL; |
531 for (Node::Uses::iterator i = node->uses().begin(); i != node->uses().end(); | 531 for (Node::Uses::iterator i = node->uses().begin(); i != node->uses().end(); |
532 ++i) { | 532 ++i) { |
533 BasicBlock* use_block = GetBlockForUse(i.edge()); | 533 BasicBlock* use_block = GetBlockForUse(i.edge()); |
534 block = block == NULL ? use_block : use_block == NULL | 534 block = block == NULL ? use_block : use_block == NULL |
535 ? block | 535 ? block |
536 : scheduler_->GetCommonDominator( | 536 : scheduler_->GetCommonDominator( |
537 block, use_block); | 537 block, use_block); |
538 } | 538 } |
539 ASSERT(block != NULL); | 539 DCHECK(block != NULL); |
540 | 540 |
541 int min_rpo = scheduler_->schedule_early_rpo_index_[node->id()]; | 541 int min_rpo = scheduler_->schedule_early_rpo_index_[node->id()]; |
542 if (FLAG_trace_turbo_scheduler) { | 542 if (FLAG_trace_turbo_scheduler) { |
543 PrintF( | 543 PrintF( |
544 "Schedule late conservative for node %d is block %d at " | 544 "Schedule late conservative for node %d is block %d at " |
545 "loop depth %d, min rpo = %d\n", | 545 "loop depth %d, min rpo = %d\n", |
546 node->id(), block->id(), block->loop_depth_, min_rpo); | 546 node->id(), block->id(), block->loop_depth_, min_rpo); |
547 } | 547 } |
548 // Hoist nodes out of loops if possible. Nodes can be hoisted iteratively | 548 // Hoist nodes out of loops if possible. Nodes can be hoisted iteratively |
549 // into enlcosing loop pre-headers until they would preceed their | 549 // into enlcosing loop pre-headers until they would preceed their |
550 // ScheduleEarly position. | 550 // ScheduleEarly position. |
551 BasicBlock* hoist_block = block; | 551 BasicBlock* hoist_block = block; |
552 while (hoist_block != NULL && hoist_block->rpo_number_ >= min_rpo) { | 552 while (hoist_block != NULL && hoist_block->rpo_number_ >= min_rpo) { |
553 if (hoist_block->loop_depth_ < block->loop_depth_) { | 553 if (hoist_block->loop_depth_ < block->loop_depth_) { |
554 block = hoist_block; | 554 block = hoist_block; |
555 if (FLAG_trace_turbo_scheduler) { | 555 if (FLAG_trace_turbo_scheduler) { |
556 PrintF("Hoisting node %d to block %d\n", node->id(), block->id()); | 556 PrintF("Hoisting node %d to block %d\n", node->id(), block->id()); |
557 } | 557 } |
558 } | 558 } |
559 // Try to hoist to the pre-header of the loop header. | 559 // Try to hoist to the pre-header of the loop header. |
560 hoist_block = hoist_block->loop_header(); | 560 hoist_block = hoist_block->loop_header(); |
561 if (hoist_block != NULL) { | 561 if (hoist_block != NULL) { |
562 BasicBlock* pre_header = schedule_->dominator(hoist_block); | 562 BasicBlock* pre_header = schedule_->dominator(hoist_block); |
563 ASSERT(pre_header == NULL || | 563 DCHECK(pre_header == NULL || |
564 *hoist_block->predecessors().begin() == pre_header); | 564 *hoist_block->predecessors().begin() == pre_header); |
565 if (FLAG_trace_turbo_scheduler) { | 565 if (FLAG_trace_turbo_scheduler) { |
566 PrintF( | 566 PrintF( |
567 "Try hoist to pre-header block %d of loop header block %d," | 567 "Try hoist to pre-header block %d of loop header block %d," |
568 " depth would be %d\n", | 568 " depth would be %d\n", |
569 pre_header->id(), hoist_block->id(), pre_header->loop_depth_); | 569 pre_header->id(), hoist_block->id(), pre_header->loop_depth_); |
570 } | 570 } |
571 hoist_block = pre_header; | 571 hoist_block = pre_header; |
572 } | 572 } |
573 } | 573 } |
574 | 574 |
575 ScheduleNode(block, node); | 575 ScheduleNode(block, node); |
576 | 576 |
577 return GenericGraphVisit::CONTINUE; | 577 return GenericGraphVisit::CONTINUE; |
578 } | 578 } |
579 | 579 |
580 private: | 580 private: |
581 BasicBlock* GetBlockForUse(Node::Edge edge) { | 581 BasicBlock* GetBlockForUse(Node::Edge edge) { |
582 Node* use = edge.from(); | 582 Node* use = edge.from(); |
583 IrOpcode::Value opcode = use->opcode(); | 583 IrOpcode::Value opcode = use->opcode(); |
584 // If the use is a phi, forward through the the phi to the basic block | 584 // If the use is a phi, forward through the the phi to the basic block |
585 // corresponding to the phi's input. | 585 // corresponding to the phi's input. |
586 if (opcode == IrOpcode::kPhi || opcode == IrOpcode::kEffectPhi) { | 586 if (opcode == IrOpcode::kPhi || opcode == IrOpcode::kEffectPhi) { |
587 int index = edge.index(); | 587 int index = edge.index(); |
588 if (FLAG_trace_turbo_scheduler) { | 588 if (FLAG_trace_turbo_scheduler) { |
589 PrintF("Use %d is input %d to a phi\n", use->id(), index); | 589 PrintF("Use %d is input %d to a phi\n", use->id(), index); |
590 } | 590 } |
591 use = NodeProperties::GetControlInput(use, 0); | 591 use = NodeProperties::GetControlInput(use, 0); |
592 opcode = use->opcode(); | 592 opcode = use->opcode(); |
593 ASSERT(opcode == IrOpcode::kMerge || opcode == IrOpcode::kLoop); | 593 DCHECK(opcode == IrOpcode::kMerge || opcode == IrOpcode::kLoop); |
594 use = NodeProperties::GetControlInput(use, index); | 594 use = NodeProperties::GetControlInput(use, index); |
595 } | 595 } |
596 BasicBlock* result = schedule_->block(use); | 596 BasicBlock* result = schedule_->block(use); |
597 if (result == NULL) return NULL; | 597 if (result == NULL) return NULL; |
598 if (FLAG_trace_turbo_scheduler) { | 598 if (FLAG_trace_turbo_scheduler) { |
599 PrintF("Must dominate use %d in block %d\n", use->id(), result->id()); | 599 PrintF("Must dominate use %d in block %d\n", use->id(), result->id()); |
600 } | 600 } |
601 return result; | 601 return result; |
602 } | 602 } |
603 | 603 |
604 bool IsNodeEligible(Node* node) { | 604 bool IsNodeEligible(Node* node) { |
605 bool eligible = scheduler_->unscheduled_uses_[node->id()] == 0; | 605 bool eligible = scheduler_->unscheduled_uses_[node->id()] == 0; |
606 return eligible; | 606 return eligible; |
607 } | 607 } |
608 | 608 |
609 void ScheduleNode(BasicBlock* block, Node* node) { | 609 void ScheduleNode(BasicBlock* block, Node* node) { |
610 schedule_->PlanNode(block, node); | 610 schedule_->PlanNode(block, node); |
611 scheduler_->scheduled_nodes_[block->id()].push_back(node); | 611 scheduler_->scheduled_nodes_[block->id()].push_back(node); |
612 | 612 |
613 // Reduce the use count of the node's inputs to potentially make them | 613 // Reduce the use count of the node's inputs to potentially make them |
614 // scheduable. | 614 // scheduable. |
615 for (InputIter i = node->inputs().begin(); i != node->inputs().end(); ++i) { | 615 for (InputIter i = node->inputs().begin(); i != node->inputs().end(); ++i) { |
616 ASSERT(scheduler_->unscheduled_uses_[(*i)->id()] > 0); | 616 DCHECK(scheduler_->unscheduled_uses_[(*i)->id()] > 0); |
617 --scheduler_->unscheduled_uses_[(*i)->id()]; | 617 --scheduler_->unscheduled_uses_[(*i)->id()]; |
618 if (FLAG_trace_turbo_scheduler) { | 618 if (FLAG_trace_turbo_scheduler) { |
619 PrintF("Decrementing use count for node %d from node %d (now %d)\n", | 619 PrintF("Decrementing use count for node %d from node %d (now %d)\n", |
620 (*i)->id(), i.edge().from()->id(), | 620 (*i)->id(), i.edge().from()->id(), |
621 scheduler_->unscheduled_uses_[(*i)->id()]); | 621 scheduler_->unscheduled_uses_[(*i)->id()]); |
622 if (scheduler_->unscheduled_uses_[(*i)->id()] == 0) { | 622 if (scheduler_->unscheduled_uses_[(*i)->id()] == 0) { |
623 PrintF("node %d is now eligible for scheduling\n", (*i)->id()); | 623 PrintF("node %d is now eligible for scheduling\n", (*i)->id()); |
624 } | 624 } |
625 } | 625 } |
626 } | 626 } |
(...skipping 163 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
790 if (block->loop_end_ >= 0) { | 790 if (block->loop_end_ >= 0) { |
791 PrintF(" range: [%d, %d)", block->rpo_number_, block->loop_end_); | 791 PrintF(" range: [%d, %d)", block->rpo_number_, block->loop_end_); |
792 } | 792 } |
793 PrintF("\n"); | 793 PrintF("\n"); |
794 } | 794 } |
795 } | 795 } |
796 | 796 |
797 | 797 |
798 static void VerifySpecialRPO(int num_loops, LoopInfo* loops, | 798 static void VerifySpecialRPO(int num_loops, LoopInfo* loops, |
799 BasicBlockVector* order) { | 799 BasicBlockVector* order) { |
800 ASSERT(order->size() > 0); | 800 DCHECK(order->size() > 0); |
801 ASSERT((*order)[0]->id() == 0); // entry should be first. | 801 DCHECK((*order)[0]->id() == 0); // entry should be first. |
802 | 802 |
803 for (int i = 0; i < num_loops; i++) { | 803 for (int i = 0; i < num_loops; i++) { |
804 LoopInfo* loop = &loops[i]; | 804 LoopInfo* loop = &loops[i]; |
805 BasicBlock* header = loop->header; | 805 BasicBlock* header = loop->header; |
806 | 806 |
807 ASSERT(header != NULL); | 807 DCHECK(header != NULL); |
808 ASSERT(header->rpo_number_ >= 0); | 808 DCHECK(header->rpo_number_ >= 0); |
809 ASSERT(header->rpo_number_ < static_cast<int>(order->size())); | 809 DCHECK(header->rpo_number_ < static_cast<int>(order->size())); |
810 ASSERT(header->loop_end_ >= 0); | 810 DCHECK(header->loop_end_ >= 0); |
811 ASSERT(header->loop_end_ <= static_cast<int>(order->size())); | 811 DCHECK(header->loop_end_ <= static_cast<int>(order->size())); |
812 ASSERT(header->loop_end_ > header->rpo_number_); | 812 DCHECK(header->loop_end_ > header->rpo_number_); |
813 | 813 |
814 // Verify the start ... end list relationship. | 814 // Verify the start ... end list relationship. |
815 int links = 0; | 815 int links = 0; |
816 BlockList* l = loop->start; | 816 BlockList* l = loop->start; |
817 ASSERT(l != NULL && l->block == header); | 817 DCHECK(l != NULL && l->block == header); |
818 bool end_found; | 818 bool end_found; |
819 while (true) { | 819 while (true) { |
820 if (l == NULL || l == loop->end) { | 820 if (l == NULL || l == loop->end) { |
821 end_found = (loop->end == l); | 821 end_found = (loop->end == l); |
822 break; | 822 break; |
823 } | 823 } |
824 // The list should be in same order as the final result. | 824 // The list should be in same order as the final result. |
825 ASSERT(l->block->rpo_number_ == links + loop->header->rpo_number_); | 825 DCHECK(l->block->rpo_number_ == links + loop->header->rpo_number_); |
826 links++; | 826 links++; |
827 l = l->next; | 827 l = l->next; |
828 ASSERT(links < static_cast<int>(2 * order->size())); // cycle? | 828 DCHECK(links < static_cast<int>(2 * order->size())); // cycle? |
829 } | 829 } |
830 ASSERT(links > 0); | 830 DCHECK(links > 0); |
831 ASSERT(links == (header->loop_end_ - header->rpo_number_)); | 831 DCHECK(links == (header->loop_end_ - header->rpo_number_)); |
832 ASSERT(end_found); | 832 DCHECK(end_found); |
833 | 833 |
834 // Check the contiguousness of loops. | 834 // Check the contiguousness of loops. |
835 int count = 0; | 835 int count = 0; |
836 for (int j = 0; j < static_cast<int>(order->size()); j++) { | 836 for (int j = 0; j < static_cast<int>(order->size()); j++) { |
837 BasicBlock* block = order->at(j); | 837 BasicBlock* block = order->at(j); |
838 ASSERT(block->rpo_number_ == j); | 838 DCHECK(block->rpo_number_ == j); |
839 if (j < header->rpo_number_ || j >= header->loop_end_) { | 839 if (j < header->rpo_number_ || j >= header->loop_end_) { |
840 ASSERT(!loop->members->Contains(block->id())); | 840 DCHECK(!loop->members->Contains(block->id())); |
841 } else { | 841 } else { |
842 if (block == header) { | 842 if (block == header) { |
843 ASSERT(!loop->members->Contains(block->id())); | 843 DCHECK(!loop->members->Contains(block->id())); |
844 } else { | 844 } else { |
845 ASSERT(loop->members->Contains(block->id())); | 845 DCHECK(loop->members->Contains(block->id())); |
846 } | 846 } |
847 count++; | 847 count++; |
848 } | 848 } |
849 } | 849 } |
850 ASSERT(links == count); | 850 DCHECK(links == count); |
851 } | 851 } |
852 } | 852 } |
853 #endif // DEBUG | 853 #endif // DEBUG |
854 | 854 |
855 | 855 |
856 // Compute the special reverse-post-order block ordering, which is essentially | 856 // Compute the special reverse-post-order block ordering, which is essentially |
857 // a RPO of the graph where loop bodies are contiguous. Properties: | 857 // a RPO of the graph where loop bodies are contiguous. Properties: |
858 // 1. If block A is a predecessor of B, then A appears before B in the order, | 858 // 1. If block A is a predecessor of B, then A appears before B in the order, |
859 // unless B is a loop header and A is in the loop headed at B | 859 // unless B is a loop header and A is in the loop headed at B |
860 // (i.e. A -> B is a backedge). | 860 // (i.e. A -> B is a backedge). |
(...skipping 32 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
893 if (succ->rpo_number_ == kBlockOnStack) { | 893 if (succ->rpo_number_ == kBlockOnStack) { |
894 // The successor is on the stack, so this is a backedge (cycle). | 894 // The successor is on the stack, so this is a backedge (cycle). |
895 backedges.Add( | 895 backedges.Add( |
896 std::pair<BasicBlock*, int>(frame->block, frame->index - 1), zone_); | 896 std::pair<BasicBlock*, int>(frame->block, frame->index - 1), zone_); |
897 if (succ->loop_end_ < 0) { | 897 if (succ->loop_end_ < 0) { |
898 // Assign a new loop number to the header if it doesn't have one. | 898 // Assign a new loop number to the header if it doesn't have one. |
899 succ->loop_end_ = num_loops++; | 899 succ->loop_end_ = num_loops++; |
900 } | 900 } |
901 } else { | 901 } else { |
902 // Push the successor onto the stack. | 902 // Push the successor onto the stack. |
903 ASSERT(succ->rpo_number_ == kBlockUnvisited1); | 903 DCHECK(succ->rpo_number_ == kBlockUnvisited1); |
904 stack_depth = Push(stack, stack_depth, succ, kBlockUnvisited1); | 904 stack_depth = Push(stack, stack_depth, succ, kBlockUnvisited1); |
905 } | 905 } |
906 } else { | 906 } else { |
907 // Finished with all successors; pop the stack and add the block. | 907 // Finished with all successors; pop the stack and add the block. |
908 order = order->Add(zone_, frame->block); | 908 order = order->Add(zone_, frame->block); |
909 frame->block->rpo_number_ = kBlockVisited1; | 909 frame->block->rpo_number_ = kBlockVisited1; |
910 stack_depth--; | 910 stack_depth--; |
911 } | 911 } |
912 } | 912 } |
913 | 913 |
(...skipping 20 matching lines...) Expand all Loading... |
934 BasicBlock* succ = NULL; | 934 BasicBlock* succ = NULL; |
935 | 935 |
936 if (frame->index < block->SuccessorCount()) { | 936 if (frame->index < block->SuccessorCount()) { |
937 // Process the next normal successor. | 937 // Process the next normal successor. |
938 succ = block->SuccessorAt(frame->index++); | 938 succ = block->SuccessorAt(frame->index++); |
939 } else if (block->IsLoopHeader()) { | 939 } else if (block->IsLoopHeader()) { |
940 // Process additional outgoing edges from the loop header. | 940 // Process additional outgoing edges from the loop header. |
941 if (block->rpo_number_ == kBlockOnStack) { | 941 if (block->rpo_number_ == kBlockOnStack) { |
942 // Finish the loop body the first time the header is left on the | 942 // Finish the loop body the first time the header is left on the |
943 // stack. | 943 // stack. |
944 ASSERT(loop != NULL && loop->header == block); | 944 DCHECK(loop != NULL && loop->header == block); |
945 loop->start = order->Add(zone_, block); | 945 loop->start = order->Add(zone_, block); |
946 order = loop->end; | 946 order = loop->end; |
947 block->rpo_number_ = kBlockVisited2; | 947 block->rpo_number_ = kBlockVisited2; |
948 // Pop the loop stack and continue visiting outgoing edges within the | 948 // Pop the loop stack and continue visiting outgoing edges within the |
949 // the context of the outer loop, if any. | 949 // the context of the outer loop, if any. |
950 loop = loop->prev; | 950 loop = loop->prev; |
951 // We leave the loop header on the stack; the rest of this iteration | 951 // We leave the loop header on the stack; the rest of this iteration |
952 // and later iterations will go through its outgoing edges list. | 952 // and later iterations will go through its outgoing edges list. |
953 } | 953 } |
954 | 954 |
955 // Use the next outgoing edge if there are any. | 955 // Use the next outgoing edge if there are any. |
956 int outgoing_index = frame->index - block->SuccessorCount(); | 956 int outgoing_index = frame->index - block->SuccessorCount(); |
957 LoopInfo* info = &loops[block->loop_end_]; | 957 LoopInfo* info = &loops[block->loop_end_]; |
958 ASSERT(loop != info); | 958 DCHECK(loop != info); |
959 if (info->outgoing != NULL && | 959 if (info->outgoing != NULL && |
960 outgoing_index < info->outgoing->length()) { | 960 outgoing_index < info->outgoing->length()) { |
961 succ = info->outgoing->at(outgoing_index); | 961 succ = info->outgoing->at(outgoing_index); |
962 frame->index++; | 962 frame->index++; |
963 } | 963 } |
964 } | 964 } |
965 | 965 |
966 if (succ != NULL) { | 966 if (succ != NULL) { |
967 // Process the next successor. | 967 // Process the next successor. |
968 if (succ->rpo_number_ == kBlockOnStack) continue; | 968 if (succ->rpo_number_ == kBlockOnStack) continue; |
969 if (succ->rpo_number_ == kBlockVisited2) continue; | 969 if (succ->rpo_number_ == kBlockVisited2) continue; |
970 ASSERT(succ->rpo_number_ == kBlockUnvisited2); | 970 DCHECK(succ->rpo_number_ == kBlockUnvisited2); |
971 if (loop != NULL && !loop->members->Contains(succ->id())) { | 971 if (loop != NULL && !loop->members->Contains(succ->id())) { |
972 // The successor is not in the current loop or any nested loop. | 972 // The successor is not in the current loop or any nested loop. |
973 // Add it to the outgoing edges of this loop and visit it later. | 973 // Add it to the outgoing edges of this loop and visit it later. |
974 loop->AddOutgoing(zone_, succ); | 974 loop->AddOutgoing(zone_, succ); |
975 } else { | 975 } else { |
976 // Push the successor onto the stack. | 976 // Push the successor onto the stack. |
977 stack_depth = Push(stack, stack_depth, succ, kBlockUnvisited2); | 977 stack_depth = Push(stack, stack_depth, succ, kBlockUnvisited2); |
978 if (succ->IsLoopHeader()) { | 978 if (succ->IsLoopHeader()) { |
979 // Push the inner loop onto the loop stack. | 979 // Push the inner loop onto the loop stack. |
980 ASSERT(succ->loop_end_ >= 0 && succ->loop_end_ < num_loops); | 980 DCHECK(succ->loop_end_ >= 0 && succ->loop_end_ < num_loops); |
981 LoopInfo* next = &loops[succ->loop_end_]; | 981 LoopInfo* next = &loops[succ->loop_end_]; |
982 next->end = order; | 982 next->end = order; |
983 next->prev = loop; | 983 next->prev = loop; |
984 loop = next; | 984 loop = next; |
985 } | 985 } |
986 } | 986 } |
987 } else { | 987 } else { |
988 // Finished with all successors of the current block. | 988 // Finished with all successors of the current block. |
989 if (block->IsLoopHeader()) { | 989 if (block->IsLoopHeader()) { |
990 // If we are going to pop a loop header, then add its entire body. | 990 // If we are going to pop a loop header, then add its entire body. |
(...skipping 36 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1027 current->loop_end_ = end == NULL ? static_cast<int>(final_order->size()) | 1027 current->loop_end_ = end == NULL ? static_cast<int>(final_order->size()) |
1028 : end->block->rpo_number_; | 1028 : end->block->rpo_number_; |
1029 current_header = current_loop->header; | 1029 current_header = current_loop->header; |
1030 if (FLAG_trace_turbo_scheduler) { | 1030 if (FLAG_trace_turbo_scheduler) { |
1031 PrintF("Block %d is a loop header, increment loop depth to %d\n", | 1031 PrintF("Block %d is a loop header, increment loop depth to %d\n", |
1032 current->id(), loop_depth); | 1032 current->id(), loop_depth); |
1033 } | 1033 } |
1034 } else { | 1034 } else { |
1035 while (current_header != NULL && | 1035 while (current_header != NULL && |
1036 current->rpo_number_ >= current_header->loop_end_) { | 1036 current->rpo_number_ >= current_header->loop_end_) { |
1037 ASSERT(current_header->IsLoopHeader()); | 1037 DCHECK(current_header->IsLoopHeader()); |
1038 ASSERT(current_loop != NULL); | 1038 DCHECK(current_loop != NULL); |
1039 current_loop = current_loop->prev; | 1039 current_loop = current_loop->prev; |
1040 current_header = current_loop == NULL ? NULL : current_loop->header; | 1040 current_header = current_loop == NULL ? NULL : current_loop->header; |
1041 --loop_depth; | 1041 --loop_depth; |
1042 } | 1042 } |
1043 } | 1043 } |
1044 current->loop_depth_ = loop_depth; | 1044 current->loop_depth_ = loop_depth; |
1045 if (FLAG_trace_turbo_scheduler) { | 1045 if (FLAG_trace_turbo_scheduler) { |
1046 if (current->loop_header_ == NULL) { | 1046 if (current->loop_header_ == NULL) { |
1047 PrintF("Block %d's loop header is NULL, loop depth %d\n", current->id(), | 1047 PrintF("Block %d's loop header is NULL, loop depth %d\n", current->id(), |
1048 current->loop_depth_); | 1048 current->loop_depth_); |
1049 } else { | 1049 } else { |
1050 PrintF("Block %d's loop header is block %d, loop depth %d\n", | 1050 PrintF("Block %d's loop header is block %d, loop depth %d\n", |
1051 current->id(), current->loop_header_->id(), | 1051 current->id(), current->loop_header_->id(), |
1052 current->loop_depth_); | 1052 current->loop_depth_); |
1053 } | 1053 } |
1054 } | 1054 } |
1055 } | 1055 } |
1056 | 1056 |
1057 #if DEBUG | 1057 #if DEBUG |
1058 if (FLAG_trace_turbo_scheduler) PrintRPO(num_loops, loops, final_order); | 1058 if (FLAG_trace_turbo_scheduler) PrintRPO(num_loops, loops, final_order); |
1059 VerifySpecialRPO(num_loops, loops, final_order); | 1059 VerifySpecialRPO(num_loops, loops, final_order); |
1060 #endif | 1060 #endif |
1061 return final_order; | 1061 return final_order; |
1062 } | 1062 } |
1063 } | 1063 } |
1064 } | 1064 } |
1065 } // namespace v8::internal::compiler | 1065 } // namespace v8::internal::compiler |
OLD | NEW |