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/node-properties.h"
     10 #include "src/compiler/operator-properties.h"
     11 
     12 namespace v8 {
     13 namespace internal {
     14 namespace compiler {
     15 
     16 DeadCodeElimination::DeadCodeElimination(Editor* editor, Graph* graph,
     17                                          CommonOperatorBuilder* common)
     18     : AdvancedReducer(editor),
     19       graph_(graph),
     20       common_(common),
     21       dead_(graph->NewNode(common->Dead())) {}
     22 
     23 
     24 Reduction DeadCodeElimination::Reduce(Node* node) {
     25   switch (node->opcode()) {
     26     case IrOpcode::kEnd:
     27       return ReduceEnd(node);
     28     case IrOpcode::kLoop:
     29     case IrOpcode::kMerge:
     30       return ReduceLoopOrMerge(node);
     31     default:
     32       return ReduceNode(node);
     33   }
     34   UNREACHABLE();
     35   return NoChange();
     36 }
     37 
     38 
     39 Reduction DeadCodeElimination::ReduceEnd(Node* node) {
     40   DCHECK_EQ(IrOpcode::kEnd, node->opcode());
     41   int const input_count = node->InputCount();
     42   DCHECK_LE(1, input_count);
     43   int live_input_count = 0;
     44   for (int i = 0; i < input_count; ++i) {
     45     Node* const input = node->InputAt(i);
     46     // Skip dead inputs.
     47     if (input->opcode() == IrOpcode::kDead) continue;
     48     // Compact live inputs.
     49     if (i != live_input_count) node->ReplaceInput(live_input_count, input);
     50     ++live_input_count;
     51   }
     52   if (live_input_count == 0) {
     53     return Replace(dead());
     54   } else if (live_input_count < input_count) {
     55     node->TrimInputCount(live_input_count);
     56     NodeProperties::ChangeOp(node, common()->End(live_input_count));
     57     return Changed(node);
     58   }
     59   DCHECK_EQ(input_count, live_input_count);
     60   return NoChange();
     61 }
     62 
     63 
     64 Reduction DeadCodeElimination::ReduceLoopOrMerge(Node* node) {
     65   DCHECK(IrOpcode::IsMergeOpcode(node->opcode()));
     66   int const input_count = node->InputCount();
     67   DCHECK_LE(1, input_count);
     68   // Count the number of live inputs to {node} and compact them on the fly, also
     69   // compacting the inputs of the associated {Phi} and {EffectPhi} uses at the
     70   // same time.  We consider {Loop}s dead even if only the first control input
     71   // is dead.
     72   int live_input_count = 0;
     73   if (node->opcode() != IrOpcode::kLoop ||
     74       node->InputAt(0)->opcode() != IrOpcode::kDead) {
     75     for (int i = 0; i < input_count; ++i) {
     76       Node* const input = node->InputAt(i);
     77       // Skip dead inputs.
     78       if (input->opcode() == IrOpcode::kDead) continue;
     79       // Compact live inputs.
     80       if (live_input_count != i) {
     81         node->ReplaceInput(live_input_count, input);
     82         for (Node* const use : node->uses()) {
     83           if (NodeProperties::IsPhi(use)) {
     84             DCHECK_EQ(input_count + 1, use->InputCount());
     85             use->ReplaceInput(live_input_count, use->InputAt(i));
     86           }
     87         }
     88       }
     89       ++live_input_count;
     90     }
     91   }
     92   if (live_input_count == 0) {
     93     return Replace(dead());
     94   } else if (live_input_count == 1) {
     95     // Due to compaction above, the live input is at offset 0.
     96     for (Node* const use : node->uses()) {
     97       if (NodeProperties::IsPhi(use)) {
     98         Replace(use, use->InputAt(0));
     99       } else if (use->opcode() == IrOpcode::kTerminate) {
    100         DCHECK_EQ(IrOpcode::kLoop, node->opcode());
    101         Replace(use, dead());
    102       }
    103     }
    104     return Replace(node->InputAt(0));
    105   }
    106   DCHECK_LE(2, live_input_count);
    107   DCHECK_LE(live_input_count, input_count);
    108   // Trim input count for the {Merge} or {Loop} node.
    109   if (live_input_count < input_count) {
    110     // Trim input counts for all phi uses and revisit them.
    111     for (Node* const use : node->uses()) {
    112       if (NodeProperties::IsPhi(use)) {
    113         use->ReplaceInput(live_input_count, node);
    114         TrimMergeOrPhi(use, live_input_count);
    115         Revisit(use);
    116       }
    117     }
    118     TrimMergeOrPhi(node, live_input_count);
    119     return Changed(node);
    120   }
    121   return NoChange();
    122 }
    123 
    124 
    125 Reduction DeadCodeElimination::ReduceNode(Node* node) {
    126   // If {node} has exactly one control input and this is {Dead},
    127   // replace {node} with {Dead}.
    128   int const control_input_count = node->op()->ControlInputCount();
    129   if (control_input_count == 0) return NoChange();
    130   DCHECK_EQ(1, control_input_count);
    131   Node* control = NodeProperties::GetControlInput(node);
    132   if (control->opcode() == IrOpcode::kDead) return Replace(control);
    133   return NoChange();
    134 }
    135 
    136 
    137 void DeadCodeElimination::TrimMergeOrPhi(Node* node, int size) {
    138   const Operator* const op = common()->ResizeMergeOrPhi(node->op(), size);
    139   node->TrimInputCount(OperatorProperties::GetTotalInputCount(op));
    140   NodeProperties::ChangeOp(node, op);
    141 }
    142 
    143 }  // namespace compiler
    144 }  // namespace internal
    145 }  // namespace v8
    146