OLD | NEW |
1 // Copyright 2010 the V8 project authors. All rights reserved. | 1 // Copyright 2011 the V8 project authors. All rights reserved. |
2 // Redistribution and use in source and binary forms, with or without | 2 // Redistribution and use in source and binary forms, with or without |
3 // modification, are permitted provided that the following conditions are | 3 // modification, are permitted provided that the following conditions are |
4 // met: | 4 // met: |
5 // | 5 // |
6 // * Redistributions of source code must retain the above copyright | 6 // * Redistributions of source code must retain the above copyright |
7 // notice, this list of conditions and the following disclaimer. | 7 // notice, this list of conditions and the following disclaimer. |
8 // * Redistributions in binary form must reproduce the above | 8 // * Redistributions in binary form must reproduce the above |
9 // copyright notice, this list of conditions and the following | 9 // copyright notice, this list of conditions and the following |
10 // disclaimer in the documentation and/or other materials provided | 10 // disclaimer in the documentation and/or other materials provided |
11 // with the distribution. | 11 // with the distribution. |
(...skipping 453 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
465 while (!IsGapAt(index)) index--; | 465 while (!IsGapAt(index)) index--; |
466 return index; | 466 return index; |
467 } | 467 } |
468 | 468 |
469 | 469 |
470 void LChunk::AddGapMove(int index, LOperand* from, LOperand* to) { | 470 void LChunk::AddGapMove(int index, LOperand* from, LOperand* to) { |
471 GetGapAt(index)->GetOrCreateParallelMove(LGap::START)->AddMove(from, to); | 471 GetGapAt(index)->GetOrCreateParallelMove(LGap::START)->AddMove(from, to); |
472 } | 472 } |
473 | 473 |
474 | 474 |
475 class LGapNode: public ZoneObject { | |
476 public: | |
477 explicit LGapNode(LOperand* operand) | |
478 : operand_(operand), resolved_(false), visited_id_(-1) { } | |
479 | |
480 LOperand* operand() const { return operand_; } | |
481 bool IsResolved() const { return !IsAssigned() || resolved_; } | |
482 void MarkResolved() { | |
483 ASSERT(!IsResolved()); | |
484 resolved_ = true; | |
485 } | |
486 int visited_id() const { return visited_id_; } | |
487 void set_visited_id(int id) { | |
488 ASSERT(id > visited_id_); | |
489 visited_id_ = id; | |
490 } | |
491 | |
492 bool IsAssigned() const { return assigned_from_.is_set(); } | |
493 LGapNode* assigned_from() const { return assigned_from_.get(); } | |
494 void set_assigned_from(LGapNode* n) { assigned_from_.set(n); } | |
495 | |
496 private: | |
497 LOperand* operand_; | |
498 SetOncePointer<LGapNode> assigned_from_; | |
499 bool resolved_; | |
500 int visited_id_; | |
501 }; | |
502 | |
503 | |
504 LGapResolver::LGapResolver(const ZoneList<LMoveOperands>* moves, | |
505 LOperand* marker_operand) | |
506 : nodes_(4), | |
507 identified_cycles_(4), | |
508 result_(4), | |
509 marker_operand_(marker_operand), | |
510 next_visited_id_(0) { | |
511 for (int i = 0; i < moves->length(); ++i) { | |
512 LMoveOperands move = moves->at(i); | |
513 if (!move.IsRedundant()) RegisterMove(move); | |
514 } | |
515 } | |
516 | |
517 | |
518 const ZoneList<LMoveOperands>* LGapResolver::ResolveInReverseOrder() { | |
519 for (int i = 0; i < identified_cycles_.length(); ++i) { | |
520 ResolveCycle(identified_cycles_[i]); | |
521 } | |
522 | |
523 int unresolved_nodes; | |
524 do { | |
525 unresolved_nodes = 0; | |
526 for (int j = 0; j < nodes_.length(); j++) { | |
527 LGapNode* node = nodes_[j]; | |
528 if (!node->IsResolved() && node->assigned_from()->IsResolved()) { | |
529 AddResultMove(node->assigned_from(), node); | |
530 node->MarkResolved(); | |
531 } | |
532 if (!node->IsResolved()) ++unresolved_nodes; | |
533 } | |
534 } while (unresolved_nodes > 0); | |
535 return &result_; | |
536 } | |
537 | |
538 | |
539 void LGapResolver::AddResultMove(LGapNode* from, LGapNode* to) { | |
540 AddResultMove(from->operand(), to->operand()); | |
541 } | |
542 | |
543 | |
544 void LGapResolver::AddResultMove(LOperand* from, LOperand* to) { | |
545 result_.Add(LMoveOperands(from, to)); | |
546 } | |
547 | |
548 | |
549 void LGapResolver::ResolveCycle(LGapNode* start) { | |
550 ZoneList<LOperand*> circle_operands(8); | |
551 circle_operands.Add(marker_operand_); | |
552 LGapNode* cur = start; | |
553 do { | |
554 cur->MarkResolved(); | |
555 circle_operands.Add(cur->operand()); | |
556 cur = cur->assigned_from(); | |
557 } while (cur != start); | |
558 circle_operands.Add(marker_operand_); | |
559 | |
560 for (int i = circle_operands.length() - 1; i > 0; --i) { | |
561 LOperand* from = circle_operands[i]; | |
562 LOperand* to = circle_operands[i - 1]; | |
563 AddResultMove(from, to); | |
564 } | |
565 } | |
566 | |
567 | |
568 bool LGapResolver::CanReach(LGapNode* a, LGapNode* b, int visited_id) { | |
569 ASSERT(a != b); | |
570 LGapNode* cur = a; | |
571 while (cur != b && cur->visited_id() != visited_id && cur->IsAssigned()) { | |
572 cur->set_visited_id(visited_id); | |
573 cur = cur->assigned_from(); | |
574 } | |
575 | |
576 return cur == b; | |
577 } | |
578 | |
579 | |
580 bool LGapResolver::CanReach(LGapNode* a, LGapNode* b) { | |
581 ASSERT(a != b); | |
582 return CanReach(a, b, next_visited_id_++); | |
583 } | |
584 | |
585 | |
586 void LGapResolver::RegisterMove(LMoveOperands move) { | |
587 if (move.from()->IsConstantOperand()) { | |
588 // Constant moves should be last in the machine code. Therefore add them | |
589 // first to the result set. | |
590 AddResultMove(move.from(), move.to()); | |
591 } else { | |
592 LGapNode* from = LookupNode(move.from()); | |
593 LGapNode* to = LookupNode(move.to()); | |
594 if (to->IsAssigned() && to->assigned_from() == from) { | |
595 move.Eliminate(); | |
596 return; | |
597 } | |
598 ASSERT(!to->IsAssigned()); | |
599 if (CanReach(from, to)) { | |
600 // This introduces a circle. Save. | |
601 identified_cycles_.Add(from); | |
602 } | |
603 to->set_assigned_from(from); | |
604 } | |
605 } | |
606 | |
607 | |
608 LGapNode* LGapResolver::LookupNode(LOperand* operand) { | |
609 for (int i = 0; i < nodes_.length(); ++i) { | |
610 if (nodes_[i]->operand()->Equals(operand)) return nodes_[i]; | |
611 } | |
612 | |
613 // No node found => create a new one. | |
614 LGapNode* result = new LGapNode(operand); | |
615 nodes_.Add(result); | |
616 return result; | |
617 } | |
618 | |
619 | |
620 Handle<Object> LChunk::LookupLiteral(LConstantOperand* operand) const { | 475 Handle<Object> LChunk::LookupLiteral(LConstantOperand* operand) const { |
621 return HConstant::cast(graph_->LookupValue(operand->index()))->handle(); | 476 return HConstant::cast(graph_->LookupValue(operand->index()))->handle(); |
622 } | 477 } |
623 | 478 |
624 | 479 |
625 Representation LChunk::LookupLiteralRepresentation( | 480 Representation LChunk::LookupLiteralRepresentation( |
626 LConstantOperand* operand) const { | 481 LConstantOperand* operand) const { |
627 return graph_->LookupValue(operand->index())->representation(); | 482 return graph_->LookupValue(operand->index())->representation(); |
628 } | 483 } |
629 | 484 |
(...skipping 1476 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
2106 void LPointerMap::PrintTo(StringStream* stream) const { | 1961 void LPointerMap::PrintTo(StringStream* stream) const { |
2107 stream->Add("{"); | 1962 stream->Add("{"); |
2108 for (int i = 0; i < pointer_operands_.length(); ++i) { | 1963 for (int i = 0; i < pointer_operands_.length(); ++i) { |
2109 if (i != 0) stream->Add(";"); | 1964 if (i != 0) stream->Add(";"); |
2110 pointer_operands_[i]->PrintTo(stream); | 1965 pointer_operands_[i]->PrintTo(stream); |
2111 } | 1966 } |
2112 stream->Add("} @%d", position()); | 1967 stream->Add("} @%d", position()); |
2113 } | 1968 } |
2114 | 1969 |
2115 } } // namespace v8::internal | 1970 } } // namespace v8::internal |
OLD | NEW |