Home | History | Annotate | Download | only in compiler 
      1 // Copyright 2015 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/dead-code-elimination.h"
      6 
      7 #include "src/compiler/common-operator.h"
      8 #include "src/compiler/graph.h"
      9 #include "src/compiler/js-operator.h"
     10 #include "src/compiler/node-properties.h"
     11 #include "src/compiler/operator-properties.h"
     12 
     13 namespace v8 {
     14 namespace internal {
     15 namespace compiler {
     16 
     17 DeadCodeElimination::DeadCodeElimination(Editor* editor, Graph* graph,
     18                                          CommonOperatorBuilder* common,
     19                                          Zone* temp_zone)
     20     : AdvancedReducer(editor),
     21       graph_(graph),
     22       common_(common),
     23       dead_(graph->NewNode(common->Dead())),
     24       zone_(temp_zone) {
     25   NodeProperties::SetType(dead_, Type::None());
     26 }
     27 
     28 namespace {
     29 
     30 // True if we can guarantee that {node} will never actually produce a value or
     31 // effect.
     32 bool NoReturn(Node* node) {
     33   return node->opcode() == IrOpcode::kDead ||
     34          node->opcode() == IrOpcode::kUnreachable ||
     35          node->opcode() == IrOpcode::kDeadValue ||
     36          NodeProperties::GetTypeOrAny(node).IsNone();
     37 }
     38 
     39 Node* FindDeadInput(Node* node) {
     40   for (Node* input : node->inputs()) {
     41     if (NoReturn(input)) return input;
     42   }
     43   return nullptr;
     44 }
     45 
     46 }  // namespace
     47 
     48 Reduction DeadCodeElimination::Reduce(Node* node) {
     49   DisallowHeapAccess no_heap_access;
     50   switch (node->opcode()) {
     51     case IrOpcode::kEnd:
     52       return ReduceEnd(node);
     53     case IrOpcode::kLoop:
     54     case IrOpcode::kMerge:
     55       return ReduceLoopOrMerge(node);
     56     case IrOpcode::kLoopExit:
     57       return ReduceLoopExit(node);
     58     case IrOpcode::kUnreachable:
     59     case IrOpcode::kIfException:
     60       return ReduceUnreachableOrIfException(node);
     61     case IrOpcode::kPhi:
     62       return ReducePhi(node);
     63     case IrOpcode::kEffectPhi:
     64       return PropagateDeadControl(node);
     65     case IrOpcode::kDeoptimize:
     66     case IrOpcode::kReturn:
     67     case IrOpcode::kTerminate:
     68       return ReduceDeoptimizeOrReturnOrTerminate(node);
     69     case IrOpcode::kThrow:
     70       return PropagateDeadControl(node);
     71     case IrOpcode::kBranch:
     72     case IrOpcode::kSwitch:
     73       return ReduceBranchOrSwitch(node);
     74     default:
     75       return ReduceNode(node);
     76   }
     77   UNREACHABLE();
     78 }
     79 
     80 Reduction DeadCodeElimination::PropagateDeadControl(Node* node) {
     81   DCHECK_EQ(1, node->op()->ControlInputCount());
     82   Node* control = NodeProperties::GetControlInput(node);
     83   if (control->opcode() == IrOpcode::kDead) return Replace(control);
     84   return NoChange();
     85 }
     86 
     87 Reduction DeadCodeElimination::ReduceEnd(Node* node) {
     88   DCHECK_EQ(IrOpcode::kEnd, node->opcode());
     89   Node::Inputs inputs = node->inputs();
     90   DCHECK_LE(1, inputs.count());
     91   int live_input_count = 0;
     92   for (int i = 0; i < inputs.count(); ++i) {
     93     Node* const input = inputs[i];
     94     // Skip dead inputs.
     95     if (input->opcode() == IrOpcode::kDead) continue;
     96     // Compact live inputs.
     97     if (i != live_input_count) node->ReplaceInput(live_input_count, input);
     98     ++live_input_count;
     99   }
    100   if (live_input_count == 0) {
    101     return Replace(dead());
    102   } else if (live_input_count < inputs.count()) {
    103     node->TrimInputCount(live_input_count);
    104     NodeProperties::ChangeOp(node, common()->End(live_input_count));
    105     return Changed(node);
    106   }
    107   DCHECK_EQ(inputs.count(), live_input_count);
    108   return NoChange();
    109 }
    110 
    111 
    112 Reduction DeadCodeElimination::ReduceLoopOrMerge(Node* node) {
    113   DCHECK(IrOpcode::IsMergeOpcode(node->opcode()));
    114   Node::Inputs inputs = node->inputs();
    115   DCHECK_LE(1, inputs.count());
    116   // Count the number of live inputs to {node} and compact them on the fly, also
    117   // compacting the inputs of the associated {Phi} and {EffectPhi} uses at the
    118   // same time.  We consider {Loop}s dead even if only the first control input
    119   // is dead.
    120   int live_input_count = 0;
    121   if (node->opcode() != IrOpcode::kLoop ||
    122       node->InputAt(0)->opcode() != IrOpcode::kDead) {
    123     for (int i = 0; i < inputs.count(); ++i) {
    124       Node* const input = inputs[i];
    125       // Skip dead inputs.
    126       if (input->opcode() == IrOpcode::kDead) continue;
    127       // Compact live inputs.
    128       if (live_input_count != i) {
    129         node->ReplaceInput(live_input_count, input);
    130         for (Node* const use : node->uses()) {
    131           if (NodeProperties::IsPhi(use)) {
    132             DCHECK_EQ(inputs.count() + 1, use->InputCount());
    133             use->ReplaceInput(live_input_count, use->InputAt(i));
    134           }
    135         }
    136       }
    137       ++live_input_count;
    138     }
    139   }
    140   if (live_input_count == 0) {
    141     return Replace(dead());
    142   } else if (live_input_count == 1) {
    143     NodeVector loop_exits(zone_);
    144     // Due to compaction above, the live input is at offset 0.
    145     for (Node* const use : node->uses()) {
    146       if (NodeProperties::IsPhi(use)) {
    147         Replace(use, use->InputAt(0));
    148       } else if (use->opcode() == IrOpcode::kLoopExit &&
    149                  use->InputAt(1) == node) {
    150         // Remember the loop exits so that we can mark their loop input dead.
    151         // This has to be done after the use list iteration so that we do
    152         // not mutate the use list while it is being iterated.
    153         loop_exits.push_back(use);
    154       } else if (use->opcode() == IrOpcode::kTerminate) {
    155         DCHECK_EQ(IrOpcode::kLoop, node->opcode());
    156         Replace(use, dead());
    157       }
    158     }
    159     for (Node* loop_exit : loop_exits) {
    160       loop_exit->ReplaceInput(1, dead());
    161       Revisit(loop_exit);
    162     }
    163     return Replace(node->InputAt(0));
    164   }
    165   DCHECK_LE(2, live_input_count);
    166   DCHECK_LE(live_input_count, inputs.count());
    167   // Trim input count for the {Merge} or {Loop} node.
    168   if (live_input_count < inputs.count()) {
    169     // Trim input counts for all phi uses and revisit them.
    170     for (Node* const use : node->uses()) {
    171       if (NodeProperties::IsPhi(use)) {
    172         use->ReplaceInput(live_input_count, node);
    173         TrimMergeOrPhi(use, live_input_count);
    174         Revisit(use);
    175       }
    176     }
    177     TrimMergeOrPhi(node, live_input_count);
    178     return Changed(node);
    179   }
    180   return NoChange();
    181 }
    182 
    183 Reduction DeadCodeElimination::RemoveLoopExit(Node* node) {
    184   DCHECK_EQ(IrOpcode::kLoopExit, node->opcode());
    185   for (Node* const use : node->uses()) {
    186     if (use->opcode() == IrOpcode::kLoopExitValue ||
    187         use->opcode() == IrOpcode::kLoopExitEffect) {
    188       Replace(use, use->InputAt(0));
    189     }
    190   }
    191   Node* control = NodeProperties::GetControlInput(node, 0);
    192   Replace(node, control);
    193   return Replace(control);
    194 }
    195 
    196 Reduction DeadCodeElimination::ReduceNode(Node* node) {
    197   DCHECK(!IrOpcode::IsGraphTerminator(node->opcode()));
    198   int const effect_input_count = node->op()->EffectInputCount();
    199   int const control_input_count = node->op()->ControlInputCount();
    200   DCHECK_LE(control_input_count, 1);
    201   if (control_input_count == 1) {
    202     Reduction reduction = PropagateDeadControl(node);
    203     if (reduction.Changed()) return reduction;
    204   }
    205   if (effect_input_count == 0 &&
    206       (control_input_count == 0 || node->op()->ControlOutputCount() == 0)) {
    207     return ReducePureNode(node);
    208   }
    209   if (effect_input_count > 0) {
    210     return ReduceEffectNode(node);
    211   }
    212   return NoChange();
    213 }
    214 
    215 Reduction DeadCodeElimination::ReducePhi(Node* node) {
    216   DCHECK_EQ(IrOpcode::kPhi, node->opcode());
    217   Reduction reduction = PropagateDeadControl(node);
    218   if (reduction.Changed()) return reduction;
    219   MachineRepresentation rep = PhiRepresentationOf(node->op());
    220   if (rep == MachineRepresentation::kNone ||
    221       NodeProperties::GetTypeOrAny(node).IsNone()) {
    222     return Replace(DeadValue(node, rep));
    223   }
    224   int input_count = node->op()->ValueInputCount();
    225   for (int i = 0; i < input_count; ++i) {
    226     Node* input = NodeProperties::GetValueInput(node, i);
    227     if (input->opcode() == IrOpcode::kDeadValue &&
    228         DeadValueRepresentationOf(input->op()) != rep) {
    229       NodeProperties::ReplaceValueInput(node, DeadValue(input, rep), i);
    230     }
    231   }
    232   return NoChange();
    233 }
    234 
    235 Reduction DeadCodeElimination::ReducePureNode(Node* node) {
    236   DCHECK_EQ(0, node->op()->EffectInputCount());
    237   if (node->opcode() == IrOpcode::kDeadValue) return NoChange();
    238   if (Node* input = FindDeadInput(node)) {
    239     return Replace(DeadValue(input));
    240   }
    241   return NoChange();
    242 }
    243 
    244 Reduction DeadCodeElimination::ReduceUnreachableOrIfException(Node* node) {
    245   DCHECK(node->opcode() == IrOpcode::kUnreachable ||
    246          node->opcode() == IrOpcode::kIfException);
    247   Reduction reduction = PropagateDeadControl(node);
    248   if (reduction.Changed()) return reduction;
    249   Node* effect = NodeProperties::GetEffectInput(node, 0);
    250   if (effect->opcode() == IrOpcode::kDead) {
    251     return Replace(effect);
    252   }
    253   if (effect->opcode() == IrOpcode::kUnreachable) {
    254     return Replace(effect);
    255   }
    256   return NoChange();
    257 }
    258 
    259 Reduction DeadCodeElimination::ReduceEffectNode(Node* node) {
    260   DCHECK_EQ(1, node->op()->EffectInputCount());
    261   Node* effect = NodeProperties::GetEffectInput(node, 0);
    262   if (effect->opcode() == IrOpcode::kDead) {
    263     return Replace(effect);
    264   }
    265   if (Node* input = FindDeadInput(node)) {
    266     if (effect->opcode() == IrOpcode::kUnreachable) {
    267       RelaxEffectsAndControls(node);
    268       return Replace(DeadValue(input));
    269     }
    270 
    271     Node* control = node->op()->ControlInputCount() == 1
    272                         ? NodeProperties::GetControlInput(node, 0)
    273                         : graph()->start();
    274     Node* unreachable =
    275         graph()->NewNode(common()->Unreachable(), effect, control);
    276     NodeProperties::SetType(unreachable, Type::None());
    277     ReplaceWithValue(node, DeadValue(input), node, control);
    278     return Replace(unreachable);
    279   }
    280 
    281   return NoChange();
    282 }
    283 
    284 Reduction DeadCodeElimination::ReduceDeoptimizeOrReturnOrTerminate(Node* node) {
    285   DCHECK(node->opcode() == IrOpcode::kDeoptimize ||
    286          node->opcode() == IrOpcode::kReturn ||
    287          node->opcode() == IrOpcode::kTerminate);
    288   Reduction reduction = PropagateDeadControl(node);
    289   if (reduction.Changed()) return reduction;
    290   if (FindDeadInput(node) != nullptr) {
    291     Node* effect = NodeProperties::GetEffectInput(node, 0);
    292     Node* control = NodeProperties::GetControlInput(node, 0);
    293     if (effect->opcode() != IrOpcode::kUnreachable) {
    294       effect = graph()->NewNode(common()->Unreachable(), effect, control);
    295       NodeProperties::SetType(effect, Type::None());
    296     }
    297     node->TrimInputCount(2);
    298     node->ReplaceInput(0, effect);
    299     node->ReplaceInput(1, control);
    300     NodeProperties::ChangeOp(node, common()->Throw());
    301     return Changed(node);
    302   }
    303   return NoChange();
    304 }
    305 
    306 Reduction DeadCodeElimination::ReduceLoopExit(Node* node) {
    307   Node* control = NodeProperties::GetControlInput(node, 0);
    308   Node* loop = NodeProperties::GetControlInput(node, 1);
    309   if (control->opcode() == IrOpcode::kDead ||
    310       loop->opcode() == IrOpcode::kDead) {
    311     return RemoveLoopExit(node);
    312   }
    313   return NoChange();
    314 }
    315 
    316 Reduction DeadCodeElimination::ReduceBranchOrSwitch(Node* node) {
    317   DCHECK(node->opcode() == IrOpcode::kBranch ||
    318          node->opcode() == IrOpcode::kSwitch);
    319   Reduction reduction = PropagateDeadControl(node);
    320   if (reduction.Changed()) return reduction;
    321   Node* condition = NodeProperties::GetValueInput(node, 0);
    322   if (condition->opcode() == IrOpcode::kDeadValue) {
    323     // Branches or switches on {DeadValue} must originate from unreachable code
    324     // and cannot matter. Due to schedule freedom between the effect and the
    325     // control chain, they might still appear in reachable code. Remove them by
    326     // always choosing the first projection.
    327     size_t const projection_cnt = node->op()->ControlOutputCount();
    328     Node** projections = zone_->NewArray<Node*>(projection_cnt);
    329     NodeProperties::CollectControlProjections(node, projections,
    330                                               projection_cnt);
    331     Replace(projections[0], NodeProperties::GetControlInput(node));
    332     return Replace(dead());
    333   }
    334   return NoChange();
    335 }
    336 
    337 void DeadCodeElimination::TrimMergeOrPhi(Node* node, int size) {
    338   const Operator* const op = common()->ResizeMergeOrPhi(node->op(), size);
    339   node->TrimInputCount(OperatorProperties::GetTotalInputCount(op));
    340   NodeProperties::ChangeOp(node, op);
    341 }
    342 
    343 Node* DeadCodeElimination::DeadValue(Node* node, MachineRepresentation rep) {
    344   if (node->opcode() == IrOpcode::kDeadValue) {
    345     if (rep == DeadValueRepresentationOf(node->op())) return node;
    346     node = NodeProperties::GetValueInput(node, 0);
    347   }
    348   Node* dead_value = graph()->NewNode(common()->DeadValue(rep), node);
    349   NodeProperties::SetType(dead_value, Type::None());
    350   return dead_value;
    351 }
    352 
    353 }  // namespace compiler
    354 }  // namespace internal
    355 }  // namespace v8
    356