Home | History | Annotate | Download | only in compiler 
      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 RedundancyElimination::RedundancyElimination(Editor* editor, Zone* zone)
     14     : AdvancedReducer(editor), node_checks_(zone), zone_(zone) {}
     15 
     16 RedundancyElimination::~RedundancyElimination() {}
     17 
     18 Reduction RedundancyElimination::Reduce(Node* node) {
     19   switch (node->opcode()) {
     20     case IrOpcode::kCheckFloat64Hole:
     21     case IrOpcode::kCheckTaggedHole:
     22     case IrOpcode::kCheckTaggedPointer:
     23     case IrOpcode::kCheckTaggedSigned:
     24     case IrOpcode::kCheckedFloat64ToInt32:
     25     case IrOpcode::kCheckedInt32Add:
     26     case IrOpcode::kCheckedInt32Sub:
     27     case IrOpcode::kCheckedTaggedToFloat64:
     28     case IrOpcode::kCheckedTaggedToInt32:
     29     case IrOpcode::kCheckedUint32ToInt32:
     30       return ReduceCheckNode(node);
     31     case IrOpcode::kEffectPhi:
     32       return ReduceEffectPhi(node);
     33     case IrOpcode::kDead:
     34       break;
     35     case IrOpcode::kStart:
     36       return ReduceStart(node);
     37     default:
     38       return ReduceOtherNode(node);
     39   }
     40   return NoChange();
     41 }
     42 
     43 // static
     44 RedundancyElimination::EffectPathChecks*
     45 RedundancyElimination::EffectPathChecks::Copy(Zone* zone,
     46                                               EffectPathChecks const* checks) {
     47   return new (zone->New(sizeof(EffectPathChecks))) EffectPathChecks(*checks);
     48 }
     49 
     50 // static
     51 RedundancyElimination::EffectPathChecks const*
     52 RedundancyElimination::EffectPathChecks::Empty(Zone* zone) {
     53   return new (zone->New(sizeof(EffectPathChecks))) EffectPathChecks(nullptr, 0);
     54 }
     55 
     56 void RedundancyElimination::EffectPathChecks::Merge(
     57     EffectPathChecks const* that) {
     58   // Change the current check list to a longest common tail of this check
     59   // list and the other list.
     60 
     61   // First, we throw away the prefix of the longer list, so that
     62   // we have lists of the same length.
     63   Check* that_head = that->head_;
     64   size_t that_size = that->size_;
     65   while (that_size > size_) {
     66     that_head = that_head->next;
     67     that_size--;
     68   }
     69   while (size_ > that_size) {
     70     head_ = head_->next;
     71     size_--;
     72   }
     73 
     74   // Then we go through both lists in lock-step until we find
     75   // the common tail.
     76   while (head_ != that_head) {
     77     DCHECK_LT(0u, size_);
     78     DCHECK_NOT_NULL(head_);
     79     size_--;
     80     head_ = head_->next;
     81     that_head = that_head->next;
     82   }
     83 }
     84 
     85 RedundancyElimination::EffectPathChecks const*
     86 RedundancyElimination::EffectPathChecks::AddCheck(Zone* zone,
     87                                                   Node* node) const {
     88   Check* head = new (zone->New(sizeof(Check))) Check(node, head_);
     89   return new (zone->New(sizeof(EffectPathChecks)))
     90       EffectPathChecks(head, size_ + 1);
     91 }
     92 
     93 namespace {
     94 
     95 bool IsCompatibleCheck(Node const* a, Node const* b) {
     96   if (a->op() != b->op()) return false;
     97   for (int i = a->op()->ValueInputCount(); --i >= 0;) {
     98     if (a->InputAt(i) != b->InputAt(i)) return false;
     99   }
    100   return true;
    101 }
    102 
    103 }  // namespace
    104 
    105 Node* RedundancyElimination::EffectPathChecks::LookupCheck(Node* node) const {
    106   for (Check const* check = head_; check != nullptr; check = check->next) {
    107     if (IsCompatibleCheck(check->node, node)) {
    108       DCHECK(!check->node->IsDead());
    109       return check->node;
    110     }
    111   }
    112   return nullptr;
    113 }
    114 
    115 RedundancyElimination::EffectPathChecks const*
    116 RedundancyElimination::PathChecksForEffectNodes::Get(Node* node) const {
    117   size_t const id = node->id();
    118   if (id < info_for_node_.size()) return info_for_node_[id];
    119   return nullptr;
    120 }
    121 
    122 void RedundancyElimination::PathChecksForEffectNodes::Set(
    123     Node* node, EffectPathChecks const* checks) {
    124   size_t const id = node->id();
    125   if (id >= info_for_node_.size()) info_for_node_.resize(id + 1, nullptr);
    126   info_for_node_[id] = checks;
    127 }
    128 
    129 Reduction RedundancyElimination::ReduceCheckNode(Node* node) {
    130   Node* const effect = NodeProperties::GetEffectInput(node);
    131   EffectPathChecks const* checks = node_checks_.Get(effect);
    132   // If we do not know anything about the predecessor, do not propagate just yet
    133   // because we will have to recompute anyway once we compute the predecessor.
    134   if (checks == nullptr) return NoChange();
    135   // See if we have another check that dominates us.
    136   if (Node* check = checks->LookupCheck(node)) {
    137     ReplaceWithValue(node, check);
    138     return Replace(check);
    139   }
    140   // Learn from this check.
    141   return UpdateChecks(node, checks->AddCheck(zone(), node));
    142 }
    143 
    144 Reduction RedundancyElimination::ReduceEffectPhi(Node* node) {
    145   Node* const control = NodeProperties::GetControlInput(node);
    146   if (control->opcode() == IrOpcode::kLoop) {
    147     // Here we rely on having only reducible loops:
    148     // The loop entry edge always dominates the header, so we can just use
    149     // the information from the loop entry edge.
    150     return TakeChecksFromFirstEffect(node);
    151   }
    152   DCHECK_EQ(IrOpcode::kMerge, control->opcode());
    153 
    154   // Shortcut for the case when we do not know anything about some input.
    155   int const input_count = node->op()->EffectInputCount();
    156   for (int i = 0; i < input_count; ++i) {
    157     Node* const effect = NodeProperties::GetEffectInput(node, i);
    158     if (node_checks_.Get(effect) == nullptr) return NoChange();
    159   }
    160 
    161   // Make a copy of the first input's checks and merge with the checks
    162   // from other inputs.
    163   EffectPathChecks* checks = EffectPathChecks::Copy(
    164       zone(), node_checks_.Get(NodeProperties::GetEffectInput(node, 0)));
    165   for (int i = 1; i < input_count; ++i) {
    166     Node* const input = NodeProperties::GetEffectInput(node, i);
    167     checks->Merge(node_checks_.Get(input));
    168   }
    169   return UpdateChecks(node, checks);
    170 }
    171 
    172 Reduction RedundancyElimination::ReduceStart(Node* node) {
    173   return UpdateChecks(node, EffectPathChecks::Empty(zone()));
    174 }
    175 
    176 Reduction RedundancyElimination::ReduceOtherNode(Node* node) {
    177   if (node->op()->EffectInputCount() == 1) {
    178     if (node->op()->EffectOutputCount() == 1) {
    179       return TakeChecksFromFirstEffect(node);
    180     } else {
    181       // Effect terminators should be handled specially.
    182       return NoChange();
    183     }
    184   }
    185   DCHECK_EQ(0, node->op()->EffectInputCount());
    186   DCHECK_EQ(0, node->op()->EffectOutputCount());
    187   return NoChange();
    188 }
    189 
    190 Reduction RedundancyElimination::TakeChecksFromFirstEffect(Node* node) {
    191   DCHECK_EQ(1, node->op()->EffectOutputCount());
    192   Node* const effect = NodeProperties::GetEffectInput(node);
    193   EffectPathChecks const* checks = node_checks_.Get(effect);
    194   // If we do not know anything about the predecessor, do not propagate just yet
    195   // because we will have to recompute anyway once we compute the predecessor.
    196   if (checks == nullptr) return NoChange();
    197   // We just propagate the information from the effect input (ideally,
    198   // we would only revisit effect uses if there is change).
    199   return UpdateChecks(node, checks);
    200 }
    201 
    202 Reduction RedundancyElimination::UpdateChecks(Node* node,
    203                                               EffectPathChecks const* checks) {
    204   EffectPathChecks const* original = node_checks_.Get(node);
    205   // Only signal that the {node} has Changed, if the information about {checks}
    206   // has changed wrt. the {original}.
    207   if (checks != original) {
    208     node_checks_.Set(node, checks);
    209     return Changed(node);
    210   }
    211   return NoChange();
    212 }
    213 
    214 }  // namespace compiler
    215 }  // namespace internal
    216 }  // namespace v8
    217