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 444 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
456 while (!IsGapAt(index)) index--; | 456 while (!IsGapAt(index)) index--; |
457 return index; | 457 return index; |
458 } | 458 } |
459 | 459 |
460 | 460 |
461 void LChunk::AddGapMove(int index, LOperand* from, LOperand* to) { | 461 void LChunk::AddGapMove(int index, LOperand* from, LOperand* to) { |
462 GetGapAt(index)->GetOrCreateParallelMove(LGap::START)->AddMove(from, to); | 462 GetGapAt(index)->GetOrCreateParallelMove(LGap::START)->AddMove(from, to); |
463 } | 463 } |
464 | 464 |
465 | 465 |
466 class LGapNode: public ZoneObject { | |
467 public: | |
468 explicit LGapNode(LOperand* operand) | |
469 : operand_(operand), resolved_(false), visited_id_(-1) { } | |
470 | |
471 LOperand* operand() const { return operand_; } | |
472 bool IsResolved() const { return !IsAssigned() || resolved_; } | |
473 void MarkResolved() { | |
474 ASSERT(!IsResolved()); | |
475 resolved_ = true; | |
476 } | |
477 int visited_id() const { return visited_id_; } | |
478 void set_visited_id(int id) { | |
479 ASSERT(id > visited_id_); | |
480 visited_id_ = id; | |
481 } | |
482 | |
483 bool IsAssigned() const { return assigned_from_.is_set(); } | |
484 LGapNode* assigned_from() const { return assigned_from_.get(); } | |
485 void set_assigned_from(LGapNode* n) { assigned_from_.set(n); } | |
486 | |
487 private: | |
488 LOperand* operand_; | |
489 SetOncePointer<LGapNode> assigned_from_; | |
490 bool resolved_; | |
491 int visited_id_; | |
492 }; | |
493 | |
494 | |
495 LGapResolver::LGapResolver(const ZoneList<LMoveOperands>* moves, | |
496 LOperand* marker_operand) | |
497 : nodes_(4), | |
498 identified_cycles_(4), | |
499 result_(4), | |
500 marker_operand_(marker_operand), | |
501 next_visited_id_(0) { | |
502 for (int i = 0; i < moves->length(); ++i) { | |
503 LMoveOperands move = moves->at(i); | |
504 if (!move.IsRedundant()) RegisterMove(move); | |
505 } | |
506 } | |
507 | |
508 | |
509 const ZoneList<LMoveOperands>* LGapResolver::ResolveInReverseOrder() { | |
510 for (int i = 0; i < identified_cycles_.length(); ++i) { | |
511 ResolveCycle(identified_cycles_[i]); | |
512 } | |
513 | |
514 int unresolved_nodes; | |
515 do { | |
516 unresolved_nodes = 0; | |
517 for (int j = 0; j < nodes_.length(); j++) { | |
518 LGapNode* node = nodes_[j]; | |
519 if (!node->IsResolved() && node->assigned_from()->IsResolved()) { | |
520 AddResultMove(node->assigned_from(), node); | |
521 node->MarkResolved(); | |
522 } | |
523 if (!node->IsResolved()) ++unresolved_nodes; | |
524 } | |
525 } while (unresolved_nodes > 0); | |
526 return &result_; | |
527 } | |
528 | |
529 | |
530 void LGapResolver::AddResultMove(LGapNode* from, LGapNode* to) { | |
531 AddResultMove(from->operand(), to->operand()); | |
532 } | |
533 | |
534 | |
535 void LGapResolver::AddResultMove(LOperand* from, LOperand* to) { | |
536 result_.Add(LMoveOperands(from, to)); | |
537 } | |
538 | |
539 | |
540 void LGapResolver::ResolveCycle(LGapNode* start) { | |
541 ZoneList<LOperand*> circle_operands(8); | |
542 circle_operands.Add(marker_operand_); | |
543 LGapNode* cur = start; | |
544 do { | |
545 cur->MarkResolved(); | |
546 circle_operands.Add(cur->operand()); | |
547 cur = cur->assigned_from(); | |
548 } while (cur != start); | |
549 circle_operands.Add(marker_operand_); | |
550 | |
551 for (int i = circle_operands.length() - 1; i > 0; --i) { | |
552 LOperand* from = circle_operands[i]; | |
553 LOperand* to = circle_operands[i - 1]; | |
554 AddResultMove(from, to); | |
555 } | |
556 } | |
557 | |
558 | |
559 bool LGapResolver::CanReach(LGapNode* a, LGapNode* b, int visited_id) { | |
560 ASSERT(a != b); | |
561 LGapNode* cur = a; | |
562 while (cur != b && cur->visited_id() != visited_id && cur->IsAssigned()) { | |
563 cur->set_visited_id(visited_id); | |
564 cur = cur->assigned_from(); | |
565 } | |
566 | |
567 return cur == b; | |
568 } | |
569 | |
570 | |
571 bool LGapResolver::CanReach(LGapNode* a, LGapNode* b) { | |
572 ASSERT(a != b); | |
573 return CanReach(a, b, next_visited_id_++); | |
574 } | |
575 | |
576 | |
577 void LGapResolver::RegisterMove(LMoveOperands move) { | |
578 if (move.from()->IsConstantOperand()) { | |
579 // Constant moves should be last in the machine code. Therefore add them | |
580 // first to the result set. | |
581 AddResultMove(move.from(), move.to()); | |
582 } else { | |
583 LGapNode* from = LookupNode(move.from()); | |
584 LGapNode* to = LookupNode(move.to()); | |
585 if (to->IsAssigned() && to->assigned_from() == from) { | |
586 move.Eliminate(); | |
587 return; | |
588 } | |
589 ASSERT(!to->IsAssigned()); | |
590 if (CanReach(from, to)) { | |
591 // This introduces a circle. Save. | |
592 identified_cycles_.Add(from); | |
593 } | |
594 to->set_assigned_from(from); | |
595 } | |
596 } | |
597 | |
598 | |
599 LGapNode* LGapResolver::LookupNode(LOperand* operand) { | |
600 for (int i = 0; i < nodes_.length(); ++i) { | |
601 if (nodes_[i]->operand()->Equals(operand)) return nodes_[i]; | |
602 } | |
603 | |
604 // No node found => create a new one. | |
605 LGapNode* result = new LGapNode(operand); | |
606 nodes_.Add(result); | |
607 return result; | |
608 } | |
609 | |
610 | |
611 Handle<Object> LChunk::LookupLiteral(LConstantOperand* operand) const { | 466 Handle<Object> LChunk::LookupLiteral(LConstantOperand* operand) const { |
612 return HConstant::cast(graph_->LookupValue(operand->index()))->handle(); | 467 return HConstant::cast(graph_->LookupValue(operand->index()))->handle(); |
613 } | 468 } |
614 | 469 |
615 | 470 |
616 Representation LChunk::LookupLiteralRepresentation( | 471 Representation LChunk::LookupLiteralRepresentation( |
617 LConstantOperand* operand) const { | 472 LConstantOperand* operand) const { |
618 return graph_->LookupValue(operand->index())->representation(); | 473 return graph_->LookupValue(operand->index())->representation(); |
619 } | 474 } |
620 | 475 |
(...skipping 1491 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
2112 void LPointerMap::PrintTo(StringStream* stream) const { | 1967 void LPointerMap::PrintTo(StringStream* stream) const { |
2113 stream->Add("{"); | 1968 stream->Add("{"); |
2114 for (int i = 0; i < pointer_operands_.length(); ++i) { | 1969 for (int i = 0; i < pointer_operands_.length(); ++i) { |
2115 if (i != 0) stream->Add(";"); | 1970 if (i != 0) stream->Add(";"); |
2116 pointer_operands_[i]->PrintTo(stream); | 1971 pointer_operands_[i]->PrintTo(stream); |
2117 } | 1972 } |
2118 stream->Add("} @%d", position()); | 1973 stream->Add("} @%d", position()); |
2119 } | 1974 } |
2120 | 1975 |
2121 } } // namespace v8::internal | 1976 } } // namespace v8::internal |
OLD | NEW |