LCOV - code coverage report
Current view: top level - src/compiler - redundancy-elimination.cc (source / functions) Hit Total Coverage
Test: app.info Lines: 129 138 93.5 %
Date: 2019-04-18 Functions: 20 22 90.9 %

          Line data    Source code
       1             : // Copyright 2016 the V8 project authors. All rights reserved.
       2             : // Use of this source code is governed by a BSD-style license that can be
       3             : // found in the LICENSE file.
       4             : 
       5             : #include "src/compiler/redundancy-elimination.h"
       6             : 
       7             : #include "src/compiler/node-properties.h"
       8             : #include "src/compiler/simplified-operator.h"
       9             : 
      10             : namespace v8 {
      11             : namespace internal {
      12             : namespace compiler {
      13             : 
      14      927831 : RedundancyElimination::RedundancyElimination(Editor* editor, Zone* zone)
      15     1855662 :     : AdvancedReducer(editor), node_checks_(zone), zone_(zone) {}
      16             : 
      17             : RedundancyElimination::~RedundancyElimination() = default;
      18             : 
      19    93508184 : Reduction RedundancyElimination::Reduce(Node* node) {
      20    93508184 :   if (node_checks_.Get(node)) return NoChange();
      21    81065024 :   switch (node->opcode()) {
      22             :     case IrOpcode::kCheckBounds:
      23             :     case IrOpcode::kCheckEqualsInternalizedString:
      24             :     case IrOpcode::kCheckEqualsSymbol:
      25             :     case IrOpcode::kCheckFloat64Hole:
      26             :     case IrOpcode::kCheckHeapObject:
      27             :     case IrOpcode::kCheckIf:
      28             :     case IrOpcode::kCheckInternalizedString:
      29             :     case IrOpcode::kCheckNotTaggedHole:
      30             :     case IrOpcode::kCheckNumber:
      31             :     case IrOpcode::kCheckReceiver:
      32             :     case IrOpcode::kCheckReceiverOrNullOrUndefined:
      33             :     case IrOpcode::kCheckSmi:
      34             :     case IrOpcode::kCheckString:
      35             :     case IrOpcode::kCheckSymbol:
      36             : #define SIMPLIFIED_CHECKED_OP(Opcode) case IrOpcode::k##Opcode:
      37             :       SIMPLIFIED_CHECKED_OP_LIST(SIMPLIFIED_CHECKED_OP)
      38             : #undef SIMPLIFIED_CHECKED_OP
      39      919724 :       return ReduceCheckNode(node);
      40             :     case IrOpcode::kSpeculativeNumberEqual:
      41             :     case IrOpcode::kSpeculativeNumberLessThan:
      42             :     case IrOpcode::kSpeculativeNumberLessThanOrEqual:
      43      168842 :       return ReduceSpeculativeNumberComparison(node);
      44             :     case IrOpcode::kSpeculativeNumberAdd:
      45             :     case IrOpcode::kSpeculativeNumberSubtract:
      46             :     case IrOpcode::kSpeculativeSafeIntegerAdd:
      47             :     case IrOpcode::kSpeculativeSafeIntegerSubtract:
      48             :     case IrOpcode::kSpeculativeToNumber:
      49      398060 :       return ReduceSpeculativeNumberOperation(node);
      50             :     case IrOpcode::kEffectPhi:
      51     1543421 :       return ReduceEffectPhi(node);
      52             :     case IrOpcode::kDead:
      53             :       break;
      54             :     case IrOpcode::kStart:
      55      927835 :       return ReduceStart(node);
      56             :     default:
      57    77081007 :       return ReduceOtherNode(node);
      58             :   }
      59             :   return NoChange();
      60             : }
      61             : 
      62             : // static
      63             : RedundancyElimination::EffectPathChecks*
      64     1027021 : RedundancyElimination::EffectPathChecks::Copy(Zone* zone,
      65             :                                               EffectPathChecks const* checks) {
      66     1027021 :   return new (zone->New(sizeof(EffectPathChecks))) EffectPathChecks(*checks);
      67             : }
      68             : 
      69             : // static
      70             : RedundancyElimination::EffectPathChecks const*
      71      927825 : RedundancyElimination::EffectPathChecks::Empty(Zone* zone) {
      72     1855654 :   return new (zone->New(sizeof(EffectPathChecks))) EffectPathChecks(nullptr, 0);
      73             : }
      74             : 
      75           0 : bool RedundancyElimination::EffectPathChecks::Equals(
      76             :     EffectPathChecks const* that) const {
      77           0 :   if (this->size_ != that->size_) return false;
      78           0 :   Check* this_head = this->head_;
      79           0 :   Check* that_head = that->head_;
      80           0 :   while (this_head != that_head) {
      81           0 :     if (this_head->node != that_head->node) return false;
      82           0 :     this_head = this_head->next;
      83           0 :     that_head = that_head->next;
      84             :   }
      85             :   return true;
      86             : }
      87             : 
      88     1441589 : void RedundancyElimination::EffectPathChecks::Merge(
      89             :     EffectPathChecks const* that) {
      90             :   // Change the current check list to a longest common tail of this check
      91             :   // list and the other list.
      92             : 
      93             :   // First, we throw away the prefix of the longer list, so that
      94             :   // we have lists of the same length.
      95     1441589 :   Check* that_head = that->head_;
      96     1441589 :   size_t that_size = that->size_;
      97     1744731 :   while (that_size > size_) {
      98      151571 :     that_head = that_head->next;
      99      151571 :     that_size--;
     100             :   }
     101     1515731 :   while (size_ > that_size) {
     102       37071 :     head_ = head_->next;
     103       37071 :     size_--;
     104             :   }
     105             : 
     106             :   // Then we go through both lists in lock-step until we find
     107             :   // the common tail.
     108     1450317 :   while (head_ != that_head) {
     109             :     DCHECK_LT(0u, size_);
     110             :     DCHECK_NOT_NULL(head_);
     111        4364 :     size_--;
     112        4364 :     head_ = head_->next;
     113        4364 :     that_head = that_head->next;
     114             :   }
     115     1441589 : }
     116             : 
     117             : RedundancyElimination::EffectPathChecks const*
     118      421001 : RedundancyElimination::EffectPathChecks::AddCheck(Zone* zone,
     119             :                                                   Node* node) const {
     120      421002 :   Check* head = new (zone->New(sizeof(Check))) Check(node, head_);
     121             :   return new (zone->New(sizeof(EffectPathChecks)))
     122      842004 :       EffectPathChecks(head, size_ + 1);
     123             : }
     124             : 
     125             : namespace {
     126             : 
     127             : // Does check {a} subsume check {b}?
     128     4746180 : bool CheckSubsumes(Node const* a, Node const* b) {
     129     4746180 :   if (a->op() != b->op()) {
     130     2562514 :     if (a->opcode() == IrOpcode::kCheckInternalizedString &&
     131             :         b->opcode() == IrOpcode::kCheckString) {
     132             :       // CheckInternalizedString(node) implies CheckString(node)
     133     2608508 :     } else if (a->opcode() == IrOpcode::kCheckSmi &&
     134             :                b->opcode() == IrOpcode::kCheckNumber) {
     135             :       // CheckSmi(node) implies CheckNumber(node)
     136     2675305 :     } else if (a->opcode() == IrOpcode::kCheckedTaggedSignedToInt32 &&
     137             :                b->opcode() == IrOpcode::kCheckedTaggedToInt32) {
     138             :       // CheckedTaggedSignedToInt32(node) implies CheckedTaggedToInt32(node)
     139     2563991 :     } else if (a->opcode() == IrOpcode::kCheckReceiver &&
     140             :                b->opcode() == IrOpcode::kCheckReceiverOrNullOrUndefined) {
     141             :       // CheckReceiver(node) implies CheckReceiverOrNullOrUndefined(node)
     142     2559478 :     } else if (a->opcode() != b->opcode()) {
     143             :       return false;
     144             :     } else {
     145       79221 :       switch (a->opcode()) {
     146             :         case IrOpcode::kCheckBounds:
     147             :         case IrOpcode::kCheckSmi:
     148             :         case IrOpcode::kCheckString:
     149             :         case IrOpcode::kCheckNumber:
     150             :           break;
     151             :         case IrOpcode::kCheckedInt32ToTaggedSigned:
     152             :         case IrOpcode::kCheckedInt64ToInt32:
     153             :         case IrOpcode::kCheckedInt64ToTaggedSigned:
     154             :         case IrOpcode::kCheckedTaggedSignedToInt32:
     155             :         case IrOpcode::kCheckedTaggedToTaggedPointer:
     156             :         case IrOpcode::kCheckedTaggedToTaggedSigned:
     157             :         case IrOpcode::kCheckedCompressedToTaggedPointer:
     158             :         case IrOpcode::kCheckedCompressedToTaggedSigned:
     159             :         case IrOpcode::kCheckedTaggedToCompressedPointer:
     160             :         case IrOpcode::kCheckedTaggedToCompressedSigned:
     161             :         case IrOpcode::kCheckedUint32Bounds:
     162             :         case IrOpcode::kCheckedUint32ToInt32:
     163             :         case IrOpcode::kCheckedUint32ToTaggedSigned:
     164             :         case IrOpcode::kCheckedUint64Bounds:
     165             :         case IrOpcode::kCheckedUint64ToInt32:
     166             :         case IrOpcode::kCheckedUint64ToTaggedSigned:
     167             :           break;
     168             :         case IrOpcode::kCheckedFloat64ToInt32:
     169             :         case IrOpcode::kCheckedFloat64ToInt64:
     170             :         case IrOpcode::kCheckedTaggedToInt32:
     171             :         case IrOpcode::kCheckedTaggedToInt64: {
     172             :           const CheckMinusZeroParameters& ap =
     173          99 :               CheckMinusZeroParametersOf(a->op());
     174             :           const CheckMinusZeroParameters& bp =
     175          99 :               CheckMinusZeroParametersOf(b->op());
     176          99 :           if (ap.mode() != bp.mode()) {
     177             :             return false;
     178             :           }
     179             :           break;
     180             :         }
     181             :         case IrOpcode::kCheckedTaggedToFloat64:
     182             :         case IrOpcode::kCheckedTruncateTaggedToWord32: {
     183             :           CheckTaggedInputParameters const& ap =
     184        7840 :               CheckTaggedInputParametersOf(a->op());
     185             :           CheckTaggedInputParameters const& bp =
     186        7840 :               CheckTaggedInputParametersOf(b->op());
     187             :           // {a} subsumes {b} if the modes are either the same, or {a} checks
     188             :           // for Number, in which case {b} will be subsumed no matter what.
     189        7840 :           if (ap.mode() != bp.mode() &&
     190             :               ap.mode() != CheckTaggedInputMode::kNumber) {
     191             :             return false;
     192             :           }
     193             :           break;
     194             :         }
     195             :         default:
     196             :           DCHECK(!IsCheckedWithFeedback(a->op()));
     197             :           return false;
     198             :       }
     199             :     }
     200             :   }
     201     2907777 :   for (int i = a->op()->ValueInputCount(); --i >= 0;) {
     202     2650773 :     if (a->InputAt(i) != b->InputAt(i)) return false;
     203             :   }
     204             :   return true;
     205             : }
     206             : 
     207      252787 : bool TypeSubsumes(Node* node, Node* replacement) {
     208      252787 :   if (!NodeProperties::IsTyped(node) || !NodeProperties::IsTyped(replacement)) {
     209             :     // If either node is untyped, we are running during an untyped optimization
     210             :     // phase, and replacement is OK.
     211             :     return true;
     212             :   }
     213             :   Type node_type = NodeProperties::GetType(node);
     214      123766 :   Type replacement_type = NodeProperties::GetType(replacement);
     215      123766 :   return replacement_type.Is(node_type);
     216             : }
     217             : 
     218             : }  // namespace
     219             : 
     220      673642 : Node* RedundancyElimination::EffectPathChecks::LookupCheck(Node* node) const {
     221     5167236 :   for (Check const* check = head_; check != nullptr; check = check->next) {
     222     4746212 :     if (CheckSubsumes(check->node, node) && TypeSubsumes(node, check->node)) {
     223             :       DCHECK(!check->node->IsDead());
     224      252754 :       return check->node;
     225             :     }
     226             :   }
     227             :   return nullptr;
     228             : }
     229             : 
     230      346874 : Node* RedundancyElimination::EffectPathChecks::LookupBoundsCheckFor(
     231             :     Node* node) const {
     232      786230 :   for (Check const* check = head_; check != nullptr; check = check->next) {
     233     1116777 :     if (check->node->opcode() == IrOpcode::kCheckBounds &&
     234             :         check->node->InputAt(0) == node) {
     235             :       return check->node;
     236             :     }
     237             :   }
     238             :   return nullptr;
     239             : }
     240             : 
     241             : RedundancyElimination::EffectPathChecks const*
     242           0 : RedundancyElimination::PathChecksForEffectNodes::Get(Node* node) const {
     243   152397176 :   size_t const id = node->id();
     244   257180296 :   if (id < info_for_node_.size()) return info_for_node_[id];
     245             :   return nullptr;
     246             : }
     247             : 
     248    24739467 : void RedundancyElimination::PathChecksForEffectNodes::Set(
     249             :     Node* node, EffectPathChecks const* checks) {
     250    24739467 :   size_t const id = node->id();
     251    24739467 :   if (id >= info_for_node_.size()) info_for_node_.resize(id + 1, nullptr);
     252    24739454 :   info_for_node_[id] = checks;
     253    24739454 : }
     254             : 
     255      919708 : Reduction RedundancyElimination::ReduceCheckNode(Node* node) {
     256      919708 :   Node* const effect = NodeProperties::GetEffectInput(node);
     257             :   EffectPathChecks const* checks = node_checks_.Get(effect);
     258             :   // If we do not know anything about the predecessor, do not propagate just yet
     259             :   // because we will have to recompute anyway once we compute the predecessor.
     260      919848 :   if (checks == nullptr) return NoChange();
     261             :   // See if we have another check that dominates us.
     262      673645 :   if (Node* check = checks->LookupCheck(node)) {
     263             :     ReplaceWithValue(node, check);
     264             :     return Replace(check);
     265             :   }
     266             : 
     267             :   // Learn from this check.
     268      421000 :   return UpdateChecks(node, checks->AddCheck(zone(), node));
     269             : }
     270             : 
     271     1543419 : Reduction RedundancyElimination::ReduceEffectPhi(Node* node) {
     272     1543419 :   Node* const control = NodeProperties::GetControlInput(node);
     273     1543435 :   if (control->opcode() == IrOpcode::kLoop) {
     274             :     // Here we rely on having only reducible loops:
     275             :     // The loop entry edge always dominates the header, so we can just use
     276             :     // the information from the loop entry edge.
     277      101808 :     return TakeChecksFromFirstEffect(node);
     278             :   }
     279             :   DCHECK_EQ(IrOpcode::kMerge, control->opcode());
     280             : 
     281             :   // Shortcut for the case when we do not know anything about some input.
     282             :   int const input_count = node->op()->EffectInputCount();
     283    10904305 :   for (int i = 0; i < input_count; ++i) {
     284     5145944 :     Node* const effect = NodeProperties::GetEffectInput(node, i);
     285     5145960 :     if (node_checks_.Get(effect) == nullptr) return NoChange();
     286             :   }
     287             : 
     288             :   // Make a copy of the first input's checks and merge with the checks
     289             :   // from other inputs.
     290     1027022 :   EffectPathChecks* checks = EffectPathChecks::Copy(
     291     1027019 :       zone(), node_checks_.Get(NodeProperties::GetEffectInput(node, 0)));
     292     3910201 :   for (int i = 1; i < input_count; ++i) {
     293     1441590 :     Node* const input = NodeProperties::GetEffectInput(node, i);
     294     1441585 :     checks->Merge(node_checks_.Get(input));
     295             :   }
     296     1027020 :   return UpdateChecks(node, checks);
     297             : }
     298             : 
     299      169072 : Reduction RedundancyElimination::ReduceSpeculativeNumberComparison(Node* node) {
     300      169072 :   NumberOperationHint const hint = NumberOperationHintOf(node->op());
     301      169071 :   Node* const first = NodeProperties::GetValueInput(node, 0);
     302      169070 :   Type const first_type = NodeProperties::GetType(first);
     303      169070 :   Node* const second = NodeProperties::GetValueInput(node, 1);
     304      169065 :   Type const second_type = NodeProperties::GetType(second);
     305      169065 :   Node* const effect = NodeProperties::GetEffectInput(node);
     306             :   EffectPathChecks const* checks = node_checks_.Get(effect);
     307             : 
     308             :   // If we do not know anything about the predecessor, do not propagate just yet
     309             :   // because we will have to recompute anyway once we compute the predecessor.
     310      169095 :   if (checks == nullptr) return NoChange();
     311             : 
     312             :   // Avoid the potentially expensive lookups below if the {node}
     313             :   // has seen non-Smi inputs in the past, which is a clear signal
     314             :   // that the comparison is probably not performed on a value that
     315             :   // already passed an array bounds check.
     316       91130 :   if (hint == NumberOperationHint::kSignedSmall) {
     317             :     // Don't bother trying to find a CheckBounds for the {first} input
     318             :     // if it's type is already in UnsignedSmall range, since the bounds
     319             :     // check is only going to narrow that range further, but the result
     320             :     // is not going to make the representation selection any better.
     321       81023 :     if (!first_type.Is(Type::UnsignedSmall())) {
     322       20188 :       if (Node* check = checks->LookupBoundsCheckFor(first)) {
     323          79 :         if (!first_type.Is(NodeProperties::GetType(check))) {
     324             :           // Replace the {first} input with the {check}. This is safe,
     325             :           // despite the fact that {check} can truncate -0 to 0, because
     326             :           // the regular Number comparisons in JavaScript also identify
     327             :           // 0 and -0 (unlike special comparisons as Object.is).
     328          79 :           NodeProperties::ReplaceValueInput(node, check, 0);
     329          79 :           Reduction const reduction = ReduceSpeculativeNumberComparison(node);
     330          79 :           return reduction.Changed() ? reduction : Changed(node);
     331             :         }
     332             :       }
     333             :     }
     334             : 
     335             :     // Don't bother trying to find a CheckBounds for the {second} input
     336             :     // if it's type is already in UnsignedSmall range, since the bounds
     337             :     // check is only going to narrow that range further, but the result
     338             :     // is not going to make the representation selection any better.
     339       80945 :     if (!second_type.Is(Type::UnsignedSmall())) {
     340       65640 :       if (Node* check = checks->LookupBoundsCheckFor(second)) {
     341         151 :         if (!second_type.Is(NodeProperties::GetType(check))) {
     342             :           // Replace the {second} input with the {check}. This is safe,
     343             :           // despite the fact that {check} can truncate -0 to 0, because
     344             :           // the regular Number comparisons in JavaScript also identify
     345             :           // 0 and -0 (unlike special comparisons as Object.is).
     346         151 :           NodeProperties::ReplaceValueInput(node, check, 1);
     347         151 :           Reduction const reduction = ReduceSpeculativeNumberComparison(node);
     348         151 :           return reduction.Changed() ? reduction : Changed(node);
     349             :         }
     350             :       }
     351             :     }
     352             :   }
     353             : 
     354       90907 :   return UpdateChecks(node, checks);
     355             : }
     356             : 
     357      398062 : Reduction RedundancyElimination::ReduceSpeculativeNumberOperation(Node* node) {
     358             :   DCHECK(node->opcode() == IrOpcode::kSpeculativeNumberAdd ||
     359             :          node->opcode() == IrOpcode::kSpeculativeNumberSubtract ||
     360             :          node->opcode() == IrOpcode::kSpeculativeSafeIntegerAdd ||
     361             :          node->opcode() == IrOpcode::kSpeculativeSafeIntegerSubtract ||
     362             :          node->opcode() == IrOpcode::kSpeculativeToNumber);
     363             :   DCHECK_EQ(1, node->op()->EffectInputCount());
     364             :   DCHECK_EQ(1, node->op()->EffectOutputCount());
     365             : 
     366      398062 :   Node* const first = NodeProperties::GetValueInput(node, 0);
     367      398047 :   Node* const effect = NodeProperties::GetEffectInput(node);
     368             :   EffectPathChecks const* checks = node_checks_.Get(effect);
     369             :   // If we do not know anything about the predecessor, do not propagate just yet
     370             :   // because we will have to recompute anyway once we compute the predecessor.
     371      398200 :   if (checks == nullptr) return NoChange();
     372             : 
     373             :   // Check if there's a CheckBounds operation on {first}
     374             :   // in the graph already, which we might be able to
     375             :   // reuse here to improve the representation selection
     376             :   // for the {node} later on.
     377      261078 :   if (Node* check = checks->LookupBoundsCheckFor(first)) {
     378             :     // Only use the bounds {check} if its type is better
     379             :     // than the type of the {first} node, otherwise we
     380             :     // would end up replacing NumberConstant inputs with
     381             :     // CheckBounds operations, which is kind of pointless.
     382       12432 :     if (!NodeProperties::GetType(first).Is(NodeProperties::GetType(check))) {
     383        3152 :       NodeProperties::ReplaceValueInput(node, check, 0);
     384             :     }
     385             :   }
     386             : 
     387      261074 :   return UpdateChecks(node, checks);
     388             : }
     389             : 
     390      927828 : Reduction RedundancyElimination::ReduceStart(Node* node) {
     391      927828 :   return UpdateChecks(node, EffectPathChecks::Empty(zone()));
     392             : }
     393             : 
     394    77083843 : Reduction RedundancyElimination::ReduceOtherNode(Node* node) {
     395    77083843 :   if (node->op()->EffectInputCount() == 1) {
     396    26626400 :     if (node->op()->EffectOutputCount() == 1) {
     397    24945853 :       return TakeChecksFromFirstEffect(node);
     398             :     } else {
     399             :       // Effect terminators should be handled specially.
     400             :       return NoChange();
     401             :     }
     402             :   }
     403             :   DCHECK_EQ(0, node->op()->EffectInputCount());
     404             :   DCHECK_EQ(0, node->op()->EffectOutputCount());
     405             :   return NoChange();
     406             : }
     407             : 
     408    25047641 : Reduction RedundancyElimination::TakeChecksFromFirstEffect(Node* node) {
     409             :   DCHECK_EQ(1, node->op()->EffectOutputCount());
     410    25047641 :   Node* const effect = NodeProperties::GetEffectInput(node);
     411             :   EffectPathChecks const* checks = node_checks_.Get(effect);
     412             :   // If we do not know anything about the predecessor, do not propagate just yet
     413             :   // because we will have to recompute anyway once we compute the predecessor.
     414    25047819 :   if (checks == nullptr) return NoChange();
     415             :   // We just propagate the information from the effect input (ideally,
     416             :   // we would only revisit effect uses if there is change).
     417    22012039 :   return UpdateChecks(node, checks);
     418             : }
     419             : 
     420    24739466 : Reduction RedundancyElimination::UpdateChecks(Node* node,
     421             :                                               EffectPathChecks const* checks) {
     422             :   EffectPathChecks const* original = node_checks_.Get(node);
     423             :   // Only signal that the {node} has Changed, if the information about {checks}
     424             :   // has changed wrt. the {original}.
     425    24739466 :   if (checks != original) {
     426    24739458 :     if (original == nullptr || !checks->Equals(original)) {
     427    24739466 :       node_checks_.Set(node, checks);
     428             :       return Changed(node);
     429             :     }
     430             :   }
     431             :   return NoChange();
     432             : }
     433             : 
     434             : }  // namespace compiler
     435             : }  // namespace internal
     436      122036 : }  // namespace v8

Generated by: LCOV version 1.10