LCOV - code coverage report
Current view: top level - src/compiler - redundancy-elimination.cc (source / functions) Hit Total Coverage
Test: app.info Lines: 93 102 91.2 %
Date: 2017-04-26 Functions: 17 21 81.0 %

          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             : 
       9             : namespace v8 {
      10             : namespace internal {
      11             : namespace compiler {
      12             : 
      13      788477 : RedundancyElimination::RedundancyElimination(Editor* editor, Zone* zone)
      14     1576954 :     : AdvancedReducer(editor), node_checks_(zone), zone_(zone) {}
      15             : 
      16     1576942 : RedundancyElimination::~RedundancyElimination() {}
      17             : 
      18   161657653 : Reduction RedundancyElimination::Reduce(Node* node) {
      19    85832140 :   if (node_checks_.Get(node)) return NoChange();
      20    75825513 :   switch (node->opcode()) {
      21             :     case IrOpcode::kCheckBounds:
      22             :     case IrOpcode::kCheckFloat64Hole:
      23             :     case IrOpcode::kCheckHeapObject:
      24             :     case IrOpcode::kCheckIf:
      25             :     case IrOpcode::kCheckInternalizedString:
      26             :     case IrOpcode::kCheckNumber:
      27             :     case IrOpcode::kCheckReceiver:
      28             :     case IrOpcode::kCheckSmi:
      29             :     case IrOpcode::kCheckString:
      30             :     case IrOpcode::kCheckTaggedHole:
      31             :     case IrOpcode::kCheckedFloat64ToInt32:
      32             :     case IrOpcode::kCheckedInt32Add:
      33             :     case IrOpcode::kCheckedInt32Sub:
      34             :     case IrOpcode::kCheckedInt32Div:
      35             :     case IrOpcode::kCheckedInt32Mod:
      36             :     case IrOpcode::kCheckedInt32Mul:
      37             :     case IrOpcode::kCheckedTaggedToFloat64:
      38             :     case IrOpcode::kCheckedTaggedSignedToInt32:
      39             :     case IrOpcode::kCheckedTaggedToInt32:
      40             :     case IrOpcode::kCheckedUint32ToInt32:
      41      762309 :       return ReduceCheckNode(node);
      42             :     case IrOpcode::kSpeculativeNumberAdd:
      43             :     case IrOpcode::kSpeculativeNumberSubtract:
      44             :       // For increments and decrements by a constant, try to learn from the last
      45             :       // bounds check.
      46      338021 :       return TryReuseBoundsCheckForFirstInput(node);
      47             :     case IrOpcode::kEffectPhi:
      48     2103362 :       return ReduceEffectPhi(node);
      49             :     case IrOpcode::kDead:
      50             :       break;
      51             :     case IrOpcode::kStart:
      52      788476 :       return ReduceStart(node);
      53             :     default:
      54    71810974 :       return ReduceOtherNode(node);
      55             :   }
      56             :   return NoChange();
      57             : }
      58             : 
      59             : // static
      60             : RedundancyElimination::EffectPathChecks*
      61     1317600 : RedundancyElimination::EffectPathChecks::Copy(Zone* zone,
      62             :                                               EffectPathChecks const* checks) {
      63     1317600 :   return new (zone->New(sizeof(EffectPathChecks))) EffectPathChecks(*checks);
      64             : }
      65             : 
      66             : // static
      67             : RedundancyElimination::EffectPathChecks const*
      68           0 : RedundancyElimination::EffectPathChecks::Empty(Zone* zone) {
      69      788476 :   return new (zone->New(sizeof(EffectPathChecks))) EffectPathChecks(nullptr, 0);
      70             : }
      71             : 
      72           0 : bool RedundancyElimination::EffectPathChecks::Equals(
      73             :     EffectPathChecks const* that) const {
      74           0 :   if (this->size_ != that->size_) return false;
      75           0 :   Check* this_head = this->head_;
      76           0 :   Check* that_head = that->head_;
      77           0 :   while (this_head != that_head) {
      78           0 :     if (this_head->node != that_head->node) return false;
      79           0 :     this_head = this_head->next;
      80           0 :     that_head = that_head->next;
      81             :   }
      82             :   return true;
      83             : }
      84             : 
      85     1812923 : void RedundancyElimination::EffectPathChecks::Merge(
      86             :     EffectPathChecks const* that) {
      87             :   // Change the current check list to a longest common tail of this check
      88             :   // list and the other list.
      89             : 
      90             :   // First, we throw away the prefix of the longer list, so that
      91             :   // we have lists of the same length.
      92     1812923 :   Check* that_head = that->head_;
      93     1812923 :   size_t that_size = that->size_;
      94     3737764 :   while (that_size > size_) {
      95      111918 :     that_head = that_head->next;
      96      111918 :     that_size--;
      97             :   }
      98     1883324 :   while (size_ > that_size) {
      99       70401 :     head_ = head_->next;
     100       70401 :     size_--;
     101             :   }
     102             : 
     103             :   // Then we go through both lists in lock-step until we find
     104             :   // the common tail.
     105     1817923 :   while (head_ != that_head) {
     106             :     DCHECK_LT(0u, size_);
     107             :     DCHECK_NOT_NULL(head_);
     108        5000 :     size_--;
     109        5000 :     head_ = head_->next;
     110        5000 :     that_head = that_head->next;
     111             :   }
     112     1812923 : }
     113             : 
     114             : RedundancyElimination::EffectPathChecks const*
     115      282672 : RedundancyElimination::EffectPathChecks::AddCheck(Zone* zone,
     116             :                                                   Node* node) const {
     117      282672 :   Check* head = new (zone->New(sizeof(Check))) Check(node, head_);
     118             :   return new (zone->New(sizeof(EffectPathChecks)))
     119      565344 :       EffectPathChecks(head, size_ + 1);
     120             : }
     121             : 
     122             : namespace {
     123             : 
     124     4488904 : bool IsCompatibleCheck(Node const* a, Node const* b) {
     125     4488904 :   if (a->op() != b->op()) {
     126     2283901 :     if (a->opcode() == IrOpcode::kCheckInternalizedString &&
     127             :         b->opcode() == IrOpcode::kCheckString) {
     128             :       // CheckInternalizedString(node) implies CheckString(node)
     129             :     } else {
     130             :       return false;
     131             :     }
     132             :   }
     133     7075860 :   for (int i = a->op()->ValueInputCount(); --i >= 0;) {
     134     2419420 :     if (a->InputAt(i) != b->InputAt(i)) return false;
     135             :   }
     136             :   return true;
     137             : }
     138             : 
     139             : }  // namespace
     140             : 
     141      521777 : Node* RedundancyElimination::EffectPathChecks::LookupCheck(Node* node) const {
     142     4771416 :   for (Check const* check = head_; check != nullptr; check = check->next) {
     143     4488667 :     if (IsCompatibleCheck(check->node, node)) {
     144             :       DCHECK(!check->node->IsDead());
     145             :       return check->node;
     146             :     }
     147             :   }
     148             :   return nullptr;
     149             : }
     150             : 
     151      147895 : Node* RedundancyElimination::EffectPathChecks::LookupBoundsCheckFor(
     152             :     Node* node) const {
     153      237576 :   for (Check const* check = head_; check != nullptr; check = check->next) {
     154      255503 :     if (check->node->opcode() == IrOpcode::kCheckBounds &&
     155             :         check->node->InputAt(0) == node) {
     156             :       return check->node;
     157             :     }
     158             :   }
     159             :   return nullptr;
     160             : }
     161             : 
     162             : RedundancyElimination::EffectPathChecks const*
     163   136665297 : RedundancyElimination::PathChecksForEffectNodes::Get(Node* node) const {
     164   136665297 :   size_t const id = node->id();
     165   371102717 :   if (id < info_for_node_.size()) return info_for_node_[id];
     166             :   return nullptr;
     167             : }
     168             : 
     169    19050562 : void RedundancyElimination::PathChecksForEffectNodes::Set(
     170    19050562 :     Node* node, EffectPathChecks const* checks) {
     171    19050562 :   size_t const id = node->id();
     172    38101124 :   if (id >= info_for_node_.size()) info_for_node_.resize(id + 1, nullptr);
     173    19050567 :   info_for_node_[id] = checks;
     174    19050567 : }
     175             : 
     176     1044981 : Reduction RedundancyElimination::ReduceCheckNode(Node* node) {
     177      762309 :   Node* const effect = NodeProperties::GetEffectInput(node);
     178             :   EffectPathChecks const* checks = node_checks_.Get(effect);
     179             :   // If we do not know anything about the predecessor, do not propagate just yet
     180             :   // because we will have to recompute anyway once we compute the predecessor.
     181      762327 :   if (checks == nullptr) return NoChange();
     182             :   // See if we have another check that dominates us.
     183      521772 :   if (Node* check = checks->LookupCheck(node)) {
     184      239135 :     ReplaceWithValue(node, check);
     185             :     return Replace(check);
     186             :   }
     187             : 
     188             :   // Learn from this check.
     189      282672 :   return UpdateChecks(node, checks->AddCheck(zone(), node));
     190             : }
     191             : 
     192      338021 : Reduction RedundancyElimination::TryReuseBoundsCheckForFirstInput(Node* node) {
     193             :   DCHECK(node->opcode() == IrOpcode::kSpeculativeNumberAdd ||
     194             :          node->opcode() == IrOpcode::kSpeculativeNumberSubtract);
     195             : 
     196             :   DCHECK_EQ(1, node->op()->EffectInputCount());
     197             :   DCHECK_EQ(1, node->op()->EffectOutputCount());
     198             : 
     199      338021 :   Node* const effect = NodeProperties::GetEffectInput(node);
     200             :   EffectPathChecks const* checks = node_checks_.Get(effect);
     201             : 
     202             :   // If we do not know anything about the predecessor, do not propagate just yet
     203             :   // because we will have to recompute anyway once we compute the predecessor.
     204      338017 :   if (checks == nullptr) return NoChange();
     205             : 
     206             :   Node* left = node->InputAt(0);
     207      220796 :   Node* right = node->InputAt(1);
     208             :   // Only use bounds checks for increments/decrements by a constant.
     209      220796 :   if (right->opcode() == IrOpcode::kNumberConstant) {
     210      147892 :     if (Node* bounds_check = checks->LookupBoundsCheckFor(left)) {
     211             :       // Only use the bounds checked type if it is better.
     212        7914 :       if (NodeProperties::GetType(bounds_check)
     213             :               ->Is(NodeProperties::GetType(left))) {
     214        5226 :         node->ReplaceInput(0, bounds_check);
     215             :       }
     216             :     }
     217             :   }
     218             : 
     219      220799 :   return UpdateChecks(node, checks);
     220             : }
     221             : 
     222     5409567 : Reduction RedundancyElimination::ReduceEffectPhi(Node* node) {
     223     2103359 :   Node* const control = NodeProperties::GetControlInput(node);
     224     2103346 :   if (control->opcode() == IrOpcode::kLoop) {
     225             :     // Here we rely on having only reducible loops:
     226             :     // The loop entry edge always dominates the header, so we can just use
     227             :     // the information from the loop entry edge.
     228      114738 :     return TakeChecksFromFirstEffect(node);
     229             :   }
     230             :   DCHECK_EQ(IrOpcode::kMerge, control->opcode());
     231             : 
     232             :   // Shortcut for the case when we do not know anything about some input.
     233     1988608 :   int const input_count = node->op()->EffectInputCount();
     234     8649068 :   for (int i = 0; i < input_count; ++i) {
     235     7331464 :     Node* const effect = NodeProperties::GetEffectInput(node, i);
     236     7331478 :     if (node_checks_.Get(effect) == nullptr) return NoChange();
     237             :   }
     238             : 
     239             :   // Make a copy of the first input's checks and merge with the checks
     240             :   // from other inputs.
     241             :   EffectPathChecks* checks = EffectPathChecks::Copy(
     242     2635204 :       zone(), node_checks_.Get(NodeProperties::GetEffectInput(node, 0)));
     243     3130531 :   for (int i = 1; i < input_count; ++i) {
     244     1812925 :     Node* const input = NodeProperties::GetEffectInput(node, i);
     245     1812924 :     checks->Merge(node_checks_.Get(input));
     246             :   }
     247     1317606 :   return UpdateChecks(node, checks);
     248             : }
     249             : 
     250      788476 : Reduction RedundancyElimination::ReduceStart(Node* node) {
     251      788477 :   return UpdateChecks(node, EffectPathChecks::Empty(zone()));
     252             : }
     253             : 
     254    71812783 : Reduction RedundancyElimination::ReduceOtherNode(Node* node) {
     255    71812783 :   if (node->op()->EffectInputCount() == 1) {
     256    21483790 :     if (node->op()->EffectOutputCount() == 1) {
     257    20105499 :       return TakeChecksFromFirstEffect(node);
     258             :     } else {
     259             :       // Effect terminators should be handled specially.
     260             :       return NoChange();
     261             :     }
     262             :   }
     263             :   DCHECK_EQ(0, node->op()->EffectInputCount());
     264             :   DCHECK_EQ(0, node->op()->EffectOutputCount());
     265             :   return NoChange();
     266             : }
     267             : 
     268    20220232 : Reduction RedundancyElimination::TakeChecksFromFirstEffect(Node* node) {
     269             :   DCHECK_EQ(1, node->op()->EffectOutputCount());
     270    20220232 :   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    20220267 :   if (checks == nullptr) return NoChange();
     275             :   // We just propagate the information from the effect input (ideally,
     276             :   // we would only revisit effect uses if there is change).
     277    16441164 :   return UpdateChecks(node, checks);
     278             : }
     279             : 
     280    19050544 : Reduction RedundancyElimination::UpdateChecks(Node* node,
     281             :                                               EffectPathChecks const* checks) {
     282             :   EffectPathChecks const* original = node_checks_.Get(node);
     283             :   // Only signal that the {node} has Changed, if the information about {checks}
     284             :   // has changed wrt. the {original}.
     285    19050544 :   if (checks != original) {
     286    19050537 :     if (original == nullptr || !checks->Equals(original)) {
     287    19050544 :       node_checks_.Set(node, checks);
     288             :       return Changed(node);
     289             :     }
     290             :   }
     291             :   return NoChange();
     292             : }
     293             : 
     294             : }  // namespace compiler
     295             : }  // namespace internal
     296             : }  // namespace v8

Generated by: LCOV version 1.10