LCOV - code coverage report
Current view: top level - src/compiler - redundancy-elimination.cc (source / functions) Hit Total Coverage
Test: app.info Lines: 134 143 93.7 %
Date: 2019-03-21 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      927707 : RedundancyElimination::RedundancyElimination(Editor* editor, Zone* zone)
      15     1855414 :     : AdvancedReducer(editor), node_checks_(zone), zone_(zone) {}
      16             : 
      17             : RedundancyElimination::~RedundancyElimination() = default;
      18             : 
      19    96523572 : Reduction RedundancyElimination::Reduce(Node* node) {
      20    96523572 :   if (node_checks_.Get(node)) return NoChange();
      21    83563333 :   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::kCheckNonEmptyString:
      30             :     case IrOpcode::kCheckNonEmptyOneByteString:
      31             :     case IrOpcode::kCheckNonEmptyTwoByteString:
      32             :     case IrOpcode::kCheckNotTaggedHole:
      33             :     case IrOpcode::kCheckNumber:
      34             :     case IrOpcode::kCheckReceiver:
      35             :     case IrOpcode::kCheckReceiverOrNullOrUndefined:
      36             :     case IrOpcode::kCheckSmi:
      37             :     case IrOpcode::kCheckString:
      38             :     case IrOpcode::kCheckSymbol:
      39             : #define SIMPLIFIED_CHECKED_OP(Opcode) case IrOpcode::k##Opcode:
      40             :       SIMPLIFIED_CHECKED_OP_LIST(SIMPLIFIED_CHECKED_OP)
      41             : #undef SIMPLIFIED_CHECKED_OP
      42      945675 :       return ReduceCheckNode(node);
      43             :     case IrOpcode::kSpeculativeNumberEqual:
      44             :     case IrOpcode::kSpeculativeNumberLessThan:
      45             :     case IrOpcode::kSpeculativeNumberLessThanOrEqual:
      46      170887 :       return ReduceSpeculativeNumberComparison(node);
      47             :     case IrOpcode::kSpeculativeNumberAdd:
      48             :     case IrOpcode::kSpeculativeNumberSubtract:
      49             :     case IrOpcode::kSpeculativeSafeIntegerAdd:
      50             :     case IrOpcode::kSpeculativeSafeIntegerSubtract:
      51             :     case IrOpcode::kSpeculativeToNumber:
      52      403435 :       return ReduceSpeculativeNumberOperation(node);
      53             :     case IrOpcode::kEffectPhi:
      54     1539135 :       return ReduceEffectPhi(node);
      55             :     case IrOpcode::kDead:
      56             :       break;
      57             :     case IrOpcode::kStart:
      58      927721 :       return ReduceStart(node);
      59             :     default:
      60    79550381 :       return ReduceOtherNode(node);
      61             :   }
      62             :   return NoChange();
      63             : }
      64             : 
      65             : // static
      66             : RedundancyElimination::EffectPathChecks*
      67     1021906 : RedundancyElimination::EffectPathChecks::Copy(Zone* zone,
      68             :                                               EffectPathChecks const* checks) {
      69     1021907 :   return new (zone->New(sizeof(EffectPathChecks))) EffectPathChecks(*checks);
      70             : }
      71             : 
      72             : // static
      73             : RedundancyElimination::EffectPathChecks const*
      74      927698 : RedundancyElimination::EffectPathChecks::Empty(Zone* zone) {
      75     1855408 :   return new (zone->New(sizeof(EffectPathChecks))) EffectPathChecks(nullptr, 0);
      76             : }
      77             : 
      78           0 : bool RedundancyElimination::EffectPathChecks::Equals(
      79             :     EffectPathChecks const* that) const {
      80           0 :   if (this->size_ != that->size_) return false;
      81           0 :   Check* this_head = this->head_;
      82           0 :   Check* that_head = that->head_;
      83           0 :   while (this_head != that_head) {
      84           0 :     if (this_head->node != that_head->node) return false;
      85           0 :     this_head = this_head->next;
      86           0 :     that_head = that_head->next;
      87             :   }
      88             :   return true;
      89             : }
      90             : 
      91     1426960 : void RedundancyElimination::EffectPathChecks::Merge(
      92             :     EffectPathChecks const* that) {
      93             :   // Change the current check list to a longest common tail of this check
      94             :   // list and the other list.
      95             : 
      96             :   // First, we throw away the prefix of the longer list, so that
      97             :   // we have lists of the same length.
      98     1426960 :   Check* that_head = that->head_;
      99     1426960 :   size_t that_size = that->size_;
     100     1743590 :   while (that_size > size_) {
     101      158315 :     that_head = that_head->next;
     102      158315 :     that_size--;
     103             :   }
     104     1502564 :   while (size_ > that_size) {
     105       37802 :     head_ = head_->next;
     106       37802 :     size_--;
     107             :   }
     108             : 
     109             :   // Then we go through both lists in lock-step until we find
     110             :   // the common tail.
     111     1435778 :   while (head_ != that_head) {
     112             :     DCHECK_LT(0u, size_);
     113             :     DCHECK_NOT_NULL(head_);
     114        4409 :     size_--;
     115        4409 :     head_ = head_->next;
     116        4409 :     that_head = that_head->next;
     117             :   }
     118     1426960 : }
     119             : 
     120             : RedundancyElimination::EffectPathChecks const*
     121      428675 : RedundancyElimination::EffectPathChecks::AddCheck(Zone* zone,
     122             :                                                   Node* node) const {
     123      428674 :   Check* head = new (zone->New(sizeof(Check))) Check(node, head_);
     124             :   return new (zone->New(sizeof(EffectPathChecks)))
     125      857348 :       EffectPathChecks(head, size_ + 1);
     126             : }
     127             : 
     128             : namespace {
     129             : 
     130             : // Does check {a} subsume check {b}?
     131     5016020 : bool CheckSubsumes(Node const* a, Node const* b) {
     132     5016020 :   if (a->op() != b->op()) {
     133     2724082 :     if (a->opcode() == IrOpcode::kCheckInternalizedString &&
     134             :         b->opcode() == IrOpcode::kCheckString) {
     135             :       // CheckInternalizedString(node) implies CheckString(node)
     136     2720608 :     } else if (a->opcode() == IrOpcode::kCheckNonEmptyString &&
     137             :                b->opcode() == IrOpcode::kCheckString) {
     138             :       // CheckNonEmptyString(node) implies CheckString(node)
     139     2765884 :     } else if (a->opcode() == IrOpcode::kCheckNonEmptyOneByteString &&
     140             :                b->opcode() == IrOpcode::kCheckNonEmptyString) {
     141             :       // CheckNonEmptyOneByteString(node) implies CheckNonEmptyString(node)
     142     2721214 :     } else if (a->opcode() == IrOpcode::kCheckNonEmptyTwoByteString &&
     143             :                b->opcode() == IrOpcode::kCheckNonEmptyString) {
     144             :       // CheckNonEmptyTwoByteString(node) implies CheckNonEmptyString(node)
     145     2765933 :     } else if (a->opcode() == IrOpcode::kCheckNonEmptyOneByteString &&
     146             :                b->opcode() == IrOpcode::kCheckString) {
     147             :       // CheckNonEmptyOneByteString(node) implies CheckString(node)
     148     2720094 :     } else if (a->opcode() == IrOpcode::kCheckNonEmptyTwoByteString &&
     149             :                b->opcode() == IrOpcode::kCheckString) {
     150             :       // CheckNonEmptyTwoByteString(node) implies CheckString(node)
     151     2769981 :     } else if (a->opcode() == IrOpcode::kCheckSmi &&
     152             :                b->opcode() == IrOpcode::kCheckNumber) {
     153             :       // CheckSmi(node) implies CheckNumber(node)
     154     2835090 :     } else if (a->opcode() == IrOpcode::kCheckedTaggedSignedToInt32 &&
     155             :                b->opcode() == IrOpcode::kCheckedTaggedToInt32) {
     156             :       // CheckedTaggedSignedToInt32(node) implies CheckedTaggedToInt32(node)
     157     2723899 :     } else if (a->opcode() == IrOpcode::kCheckReceiver &&
     158             :                b->opcode() == IrOpcode::kCheckReceiverOrNullOrUndefined) {
     159             :       // CheckReceiver(node) implies CheckReceiverOrNullOrUndefined(node)
     160     2719343 :     } else if (a->opcode() != b->opcode()) {
     161             :       return false;
     162             :     } else {
     163       83313 :       switch (a->opcode()) {
     164             :         case IrOpcode::kCheckBounds:
     165             :         case IrOpcode::kCheckSmi:
     166             :         case IrOpcode::kCheckString:
     167             :         case IrOpcode::kCheckNumber:
     168             :           break;
     169             :         case IrOpcode::kCheckedInt32ToTaggedSigned:
     170             :         case IrOpcode::kCheckedInt64ToInt32:
     171             :         case IrOpcode::kCheckedInt64ToTaggedSigned:
     172             :         case IrOpcode::kCheckedTaggedSignedToInt32:
     173             :         case IrOpcode::kCheckedTaggedToTaggedPointer:
     174             :         case IrOpcode::kCheckedTaggedToTaggedSigned:
     175             :         case IrOpcode::kCheckedUint32Bounds:
     176             :         case IrOpcode::kCheckedUint32ToInt32:
     177             :         case IrOpcode::kCheckedUint32ToTaggedSigned:
     178             :         case IrOpcode::kCheckedUint64Bounds:
     179             :         case IrOpcode::kCheckedUint64ToInt32:
     180             :         case IrOpcode::kCheckedUint64ToTaggedSigned:
     181             :           break;
     182             :         case IrOpcode::kCheckedFloat64ToInt32:
     183             :         case IrOpcode::kCheckedFloat64ToInt64:
     184             :         case IrOpcode::kCheckedTaggedToInt32:
     185             :         case IrOpcode::kCheckedTaggedToInt64: {
     186             :           const CheckMinusZeroParameters& ap =
     187         163 :               CheckMinusZeroParametersOf(a->op());
     188             :           const CheckMinusZeroParameters& bp =
     189         163 :               CheckMinusZeroParametersOf(b->op());
     190         163 :           if (ap.mode() != bp.mode()) {
     191             :             return false;
     192             :           }
     193             :           break;
     194             :         }
     195             :         case IrOpcode::kCheckedTaggedToFloat64:
     196             :         case IrOpcode::kCheckedTruncateTaggedToWord32: {
     197             :           CheckTaggedInputParameters const& ap =
     198        8821 :               CheckTaggedInputParametersOf(a->op());
     199             :           CheckTaggedInputParameters const& bp =
     200        8821 :               CheckTaggedInputParametersOf(b->op());
     201             :           // {a} subsumes {b} if the modes are either the same, or {a} checks
     202             :           // for Number, in which case {b} will be subsumed no matter what.
     203        8821 :           if (ap.mode() != bp.mode() &&
     204             :               ap.mode() != CheckTaggedInputMode::kNumber) {
     205             :             return false;
     206             :           }
     207             :           break;
     208             :         }
     209             :         default:
     210             :           DCHECK(!IsCheckedWithFeedback(a->op()));
     211             :           return false;
     212             :       }
     213             :     }
     214             :   }
     215     2956741 :   for (int i = a->op()->ValueInputCount(); --i >= 0;) {
     216     2701900 :     if (a->InputAt(i) != b->InputAt(i)) return false;
     217             :   }
     218             :   return true;
     219             : }
     220             : 
     221      254586 : bool TypeSubsumes(Node* node, Node* replacement) {
     222      254586 :   if (!NodeProperties::IsTyped(node) || !NodeProperties::IsTyped(replacement)) {
     223             :     // If either node is untyped, we are running during an untyped optimization
     224             :     // phase, and replacement is OK.
     225             :     return true;
     226             :   }
     227             :   Type node_type = NodeProperties::GetType(node);
     228      124658 :   Type replacement_type = NodeProperties::GetType(replacement);
     229      124658 :   return replacement_type.Is(node_type);
     230             : }
     231             : 
     232             : }  // namespace
     233             : 
     234      683100 : Node* RedundancyElimination::EffectPathChecks::LookupCheck(Node* node) const {
     235     5444949 :   for (Check const* check = head_; check != nullptr; check = check->next) {
     236     5016059 :     if (CheckSubsumes(check->node, node) && TypeSubsumes(node, check->node)) {
     237             :       DCHECK(!check->node->IsDead());
     238      254570 :       return check->node;
     239             :     }
     240             :   }
     241             :   return nullptr;
     242             : }
     243             : 
     244      347382 : Node* RedundancyElimination::EffectPathChecks::LookupBoundsCheckFor(
     245             :     Node* node) const {
     246      842395 :   for (Check const* check = head_; check != nullptr; check = check->next) {
     247     1190769 :     if (check->node->opcode() == IrOpcode::kCheckBounds &&
     248             :         check->node->InputAt(0) == node) {
     249             :       return check->node;
     250             :     }
     251             :   }
     252             :   return nullptr;
     253             : }
     254             : 
     255             : RedundancyElimination::EffectPathChecks const*
     256           0 : RedundancyElimination::PathChecksForEffectNodes::Get(Node* node) const {
     257   157517138 :   size_t const id = node->id();
     258   265535211 :   if (id < info_for_node_.size()) return info_for_node_[id];
     259             :   return nullptr;
     260             : }
     261             : 
     262    25796906 : void RedundancyElimination::PathChecksForEffectNodes::Set(
     263             :     Node* node, EffectPathChecks const* checks) {
     264    25796906 :   size_t const id = node->id();
     265    25796906 :   if (id >= info_for_node_.size()) info_for_node_.resize(id + 1, nullptr);
     266    25796878 :   info_for_node_[id] = checks;
     267    25796878 : }
     268             : 
     269      945654 : Reduction RedundancyElimination::ReduceCheckNode(Node* node) {
     270      945654 :   Node* const effect = NodeProperties::GetEffectInput(node);
     271             :   EffectPathChecks const* checks = node_checks_.Get(effect);
     272             :   // If we do not know anything about the predecessor, do not propagate just yet
     273             :   // because we will have to recompute anyway once we compute the predecessor.
     274      945832 :   if (checks == nullptr) return NoChange();
     275             :   // See if we have another check that dominates us.
     276      683116 :   if (Node* check = checks->LookupCheck(node)) {
     277             :     ReplaceWithValue(node, check);
     278             :     return Replace(check);
     279             :   }
     280             : 
     281             :   // Learn from this check.
     282      428674 :   return UpdateChecks(node, checks->AddCheck(zone(), node));
     283             : }
     284             : 
     285     1539129 : Reduction RedundancyElimination::ReduceEffectPhi(Node* node) {
     286     1539129 :   Node* const control = NodeProperties::GetControlInput(node);
     287     1539145 :   if (control->opcode() == IrOpcode::kLoop) {
     288             :     // Here we rely on having only reducible loops:
     289             :     // The loop entry edge always dominates the header, so we can just use
     290             :     // the information from the loop entry edge.
     291      102430 :     return TakeChecksFromFirstEffect(node);
     292             :   }
     293             :   DCHECK_EQ(IrOpcode::kMerge, control->opcode());
     294             : 
     295             :   // Shortcut for the case when we do not know anything about some input.
     296             :   int const input_count = node->op()->EffectInputCount();
     297    10696985 :   for (int i = 0; i < input_count; ++i) {
     298     5044941 :     Node* const effect = NodeProperties::GetEffectInput(node, i);
     299     5044965 :     if (node_checks_.Get(effect) == nullptr) return NoChange();
     300             :   }
     301             : 
     302             :   // Make a copy of the first input's checks and merge with the checks
     303             :   // from other inputs.
     304     1021909 :   EffectPathChecks* checks = EffectPathChecks::Copy(
     305     1021907 :       zone(), node_checks_.Get(NodeProperties::GetEffectInput(node, 0)));
     306     3875830 :   for (int i = 1; i < input_count; ++i) {
     307     1426965 :     Node* const input = NodeProperties::GetEffectInput(node, i);
     308     1426954 :     checks->Merge(node_checks_.Get(input));
     309             :   }
     310     1021904 :   return UpdateChecks(node, checks);
     311             : }
     312             : 
     313      171106 : Reduction RedundancyElimination::ReduceSpeculativeNumberComparison(Node* node) {
     314      171106 :   NumberOperationHint const hint = NumberOperationHintOf(node->op());
     315      171103 :   Node* const first = NodeProperties::GetValueInput(node, 0);
     316      171100 :   Type const first_type = NodeProperties::GetType(first);
     317      171100 :   Node* const second = NodeProperties::GetValueInput(node, 1);
     318      171097 :   Type const second_type = NodeProperties::GetType(second);
     319      171097 :   Node* const effect = NodeProperties::GetEffectInput(node);
     320             :   EffectPathChecks const* checks = node_checks_.Get(effect);
     321             : 
     322             :   // If we do not know anything about the predecessor, do not propagate just yet
     323             :   // because we will have to recompute anyway once we compute the predecessor.
     324      171118 :   if (checks == nullptr) return NoChange();
     325             : 
     326             :   // Avoid the potentially expensive lookups below if the {node}
     327             :   // has seen non-Smi inputs in the past, which is a clear signal
     328             :   // that the comparison is probably not performed on a value that
     329             :   // already passed an array bounds check.
     330       91305 :   if (hint == NumberOperationHint::kSignedSmall) {
     331             :     // Don't bother trying to find a CheckBounds for the {first} input
     332             :     // if it's type is already in UnsignedSmall range, since the bounds
     333             :     // check is only going to narrow that range further, but the result
     334             :     // is not going to make the representation selection any better.
     335       80778 :     if (!first_type.Is(Type::UnsignedSmall())) {
     336       19746 :       if (Node* check = checks->LookupBoundsCheckFor(first)) {
     337          79 :         if (!first_type.Is(NodeProperties::GetType(check))) {
     338             :           // Replace the {first} input with the {check}. This is safe,
     339             :           // despite the fact that {check} can truncate -0 to 0, because
     340             :           // the regular Number comparisons in JavaScript also identify
     341             :           // 0 and -0 (unlike special comparisons as Object.is).
     342          79 :           NodeProperties::ReplaceValueInput(node, check, 0);
     343          79 :           Reduction const reduction = ReduceSpeculativeNumberComparison(node);
     344          79 :           return reduction.Changed() ? reduction : Changed(node);
     345             :         }
     346             :       }
     347             :     }
     348             : 
     349             :     // Don't bother trying to find a CheckBounds for the {second} input
     350             :     // if it's type is already in UnsignedSmall range, since the bounds
     351             :     // check is only going to narrow that range further, but the result
     352             :     // is not going to make the representation selection any better.
     353       80700 :     if (!second_type.Is(Type::UnsignedSmall())) {
     354       65403 :       if (Node* check = checks->LookupBoundsCheckFor(second)) {
     355         136 :         if (!second_type.Is(NodeProperties::GetType(check))) {
     356             :           // Replace the {second} input with the {check}. This is safe,
     357             :           // despite the fact that {check} can truncate -0 to 0, because
     358             :           // the regular Number comparisons in JavaScript also identify
     359             :           // 0 and -0 (unlike special comparisons as Object.is).
     360         136 :           NodeProperties::ReplaceValueInput(node, check, 1);
     361         136 :           Reduction const reduction = ReduceSpeculativeNumberComparison(node);
     362         136 :           return reduction.Changed() ? reduction : Changed(node);
     363             :         }
     364             :       }
     365             :     }
     366             :   }
     367             : 
     368       91097 :   return UpdateChecks(node, checks);
     369             : }
     370             : 
     371      403439 : Reduction RedundancyElimination::ReduceSpeculativeNumberOperation(Node* node) {
     372             :   DCHECK(node->opcode() == IrOpcode::kSpeculativeNumberAdd ||
     373             :          node->opcode() == IrOpcode::kSpeculativeNumberSubtract ||
     374             :          node->opcode() == IrOpcode::kSpeculativeSafeIntegerAdd ||
     375             :          node->opcode() == IrOpcode::kSpeculativeSafeIntegerSubtract ||
     376             :          node->opcode() == IrOpcode::kSpeculativeToNumber);
     377             :   DCHECK_EQ(1, node->op()->EffectInputCount());
     378             :   DCHECK_EQ(1, node->op()->EffectOutputCount());
     379             : 
     380      403439 :   Node* const first = NodeProperties::GetValueInput(node, 0);
     381      403432 :   Node* const effect = NodeProperties::GetEffectInput(node);
     382             :   EffectPathChecks const* checks = node_checks_.Get(effect);
     383             :   // If we do not know anything about the predecessor, do not propagate just yet
     384             :   // because we will have to recompute anyway once we compute the predecessor.
     385      403508 :   if (checks == nullptr) return NoChange();
     386             : 
     387             :   // Check if there's a CheckBounds operation on {first}
     388             :   // in the graph already, which we might be able to
     389             :   // reuse here to improve the representation selection
     390             :   // for the {node} later on.
     391      262262 :   if (Node* check = checks->LookupBoundsCheckFor(first)) {
     392             :     // Only use the bounds {check} if its type is better
     393             :     // than the type of the {first} node, otherwise we
     394             :     // would end up replacing NumberConstant inputs with
     395             :     // CheckBounds operations, which is kind of pointless.
     396       12366 :     if (!NodeProperties::GetType(first).Is(NodeProperties::GetType(check))) {
     397        3141 :       NodeProperties::ReplaceValueInput(node, check, 0);
     398             :     }
     399             :   }
     400             : 
     401      262261 :   return UpdateChecks(node, checks);
     402             : }
     403             : 
     404      927699 : Reduction RedundancyElimination::ReduceStart(Node* node) {
     405      927699 :   return UpdateChecks(node, EffectPathChecks::Empty(zone()));
     406             : }
     407             : 
     408    79552437 : Reduction RedundancyElimination::ReduceOtherNode(Node* node) {
     409    79552437 :   if (node->op()->EffectInputCount() == 1) {
     410    27764109 :     if (node->op()->EffectOutputCount() == 1) {
     411    26079858 :       return TakeChecksFromFirstEffect(node);
     412             :     } else {
     413             :       // Effect terminators should be handled specially.
     414             :       return NoChange();
     415             :     }
     416             :   }
     417             :   DCHECK_EQ(0, node->op()->EffectInputCount());
     418             :   DCHECK_EQ(0, node->op()->EffectOutputCount());
     419             :   return NoChange();
     420             : }
     421             : 
     422    26182284 : Reduction RedundancyElimination::TakeChecksFromFirstEffect(Node* node) {
     423             :   DCHECK_EQ(1, node->op()->EffectOutputCount());
     424    26182284 :   Node* const effect = NodeProperties::GetEffectInput(node);
     425             :   EffectPathChecks const* checks = node_checks_.Get(effect);
     426             :   // If we do not know anything about the predecessor, do not propagate just yet
     427             :   // because we will have to recompute anyway once we compute the predecessor.
     428    26182375 :   if (checks == nullptr) return NoChange();
     429             :   // We just propagate the information from the effect input (ideally,
     430             :   // we would only revisit effect uses if there is change).
     431    23065589 :   return UpdateChecks(node, checks);
     432             : }
     433             : 
     434    25796907 : Reduction RedundancyElimination::UpdateChecks(Node* node,
     435             :                                               EffectPathChecks const* checks) {
     436             :   EffectPathChecks const* original = node_checks_.Get(node);
     437             :   // Only signal that the {node} has Changed, if the information about {checks}
     438             :   // has changed wrt. the {original}.
     439    25796907 :   if (checks != original) {
     440    25796908 :     if (original == nullptr || !checks->Equals(original)) {
     441    25796907 :       node_checks_.Set(node, checks);
     442             :       return Changed(node);
     443             :     }
     444             :   }
     445             :   return NoChange();
     446             : }
     447             : 
     448             : }  // namespace compiler
     449             : }  // namespace internal
     450      120216 : }  // namespace v8

Generated by: LCOV version 1.10