LCOV - code coverage report
Current view: top level - src/compiler - dead-code-elimination.cc (source / functions) Hit Total Coverage
Test: app.info Lines: 156 156 100.0 %
Date: 2019-01-20 Functions: 20 20 100.0 %

          Line data    Source code
       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     2813803 : DeadCodeElimination::DeadCodeElimination(Editor* editor, Graph* graph,
      18             :                                          CommonOperatorBuilder* common,
      19             :                                          Zone* temp_zone)
      20             :     : AdvancedReducer(editor),
      21             :       graph_(graph),
      22             :       common_(common),
      23     2813803 :       dead_(graph->NewNode(common->Dead())),
      24     5627649 :       zone_(temp_zone) {
      25             :   NodeProperties::SetType(dead_, Type::None());
      26     2813846 : }
      27             : 
      28             : namespace {
      29             : 
      30             : // True if we can guarantee that {node} will never actually produce a value or
      31             : // effect.
      32   705340307 : bool NoReturn(Node* node) {
      33   705298117 :   return node->opcode() == IrOpcode::kDead ||
      34   705298158 :          node->opcode() == IrOpcode::kUnreachable ||
      35  1410590153 :          node->opcode() == IrOpcode::kDeadValue ||
      36  1410590153 :          NodeProperties::GetTypeOrAny(node).IsNone();
      37             : }
      38             : 
      39   230198254 : Node* FindDeadInput(Node* node) {
      40  1165650693 :   for (Node* input : node->inputs()) {
      41   705341703 :     if (NoReturn(input)) return input;
      42             :   }
      43             :   return nullptr;
      44             : }
      45             : 
      46             : }  // namespace
      47             : 
      48   284964151 : Reduction DeadCodeElimination::Reduce(Node* node) {
      49             :   DisallowHeapAccess no_heap_access;
      50   284964151 :   switch (node->opcode()) {
      51             :     case IrOpcode::kEnd:
      52     3005145 :       return ReduceEnd(node);
      53             :     case IrOpcode::kLoop:
      54             :     case IrOpcode::kMerge:
      55     7576683 :       return ReduceLoopOrMerge(node);
      56             :     case IrOpcode::kLoopExit:
      57      314983 :       return ReduceLoopExit(node);
      58             :     case IrOpcode::kUnreachable:
      59             :     case IrOpcode::kIfException:
      60     1918988 :       return ReduceUnreachableOrIfException(node);
      61             :     case IrOpcode::kPhi:
      62     4165489 :       return ReducePhi(node);
      63             :     case IrOpcode::kEffectPhi:
      64     7557449 :       return PropagateDeadControl(node);
      65             :     case IrOpcode::kDeoptimize:
      66             :     case IrOpcode::kReturn:
      67             :     case IrOpcode::kTerminate:
      68             :     case IrOpcode::kTailCall:
      69     4573944 :       return ReduceDeoptimizeOrReturnOrTerminateOrTailCall(node);
      70             :     case IrOpcode::kThrow:
      71      815087 :       return PropagateDeadControl(node);
      72             :     case IrOpcode::kBranch:
      73             :     case IrOpcode::kSwitch:
      74     9534729 :       return ReduceBranchOrSwitch(node);
      75             :     default:
      76   245501654 :       return ReduceNode(node);
      77             :   }
      78             :   UNREACHABLE();
      79             : }
      80             : 
      81   137381981 : Reduction DeadCodeElimination::PropagateDeadControl(Node* node) {
      82             :   DCHECK_EQ(1, node->op()->ControlInputCount());
      83   137381981 :   Node* control = NodeProperties::GetControlInput(node);
      84   137371074 :   if (control->opcode() == IrOpcode::kDead) return Replace(control);
      85             :   return NoChange();
      86             : }
      87             : 
      88     3103820 : Reduction DeadCodeElimination::ReduceEnd(Node* node) {
      89             :   DCHECK_EQ(IrOpcode::kEnd, node->opcode());
      90             :   Node::Inputs inputs = node->inputs();
      91             :   DCHECK_LE(1, inputs.count());
      92             :   int live_input_count = 0;
      93    13522258 :   for (int i = 0; i < inputs.count(); ++i) {
      94    10517098 :     Node* const input = inputs[i];
      95             :     // Skip dead inputs.
      96    10517098 :     if (input->opcode() == IrOpcode::kDead) continue;
      97             :     // Compact live inputs.
      98    10337465 :     if (i != live_input_count) node->ReplaceInput(live_input_count, input);
      99    10337487 :     ++live_input_count;
     100             :   }
     101     3005160 :   if (live_input_count == 0) {
     102             :     return Replace(dead());
     103     3005145 :   } else if (live_input_count < inputs.count()) {
     104       98667 :     node->TrimInputCount(live_input_count);
     105      197334 :     NodeProperties::ChangeOp(node, common()->End(live_input_count));
     106             :     return Changed(node);
     107             :   }
     108             :   DCHECK_EQ(inputs.count(), live_input_count);
     109             :   return NoChange();
     110             : }
     111             : 
     112             : 
     113    15178505 : Reduction DeadCodeElimination::ReduceLoopOrMerge(Node* node) {
     114             :   DCHECK(IrOpcode::IsMergeOpcode(node->opcode()));
     115             :   Node::Inputs inputs = node->inputs();
     116             :   DCHECK_LE(1, inputs.count());
     117             :   // Count the number of live inputs to {node} and compact them on the fly, also
     118             :   // compacting the inputs of the associated {Phi} and {EffectPhi} uses at the
     119             :   // same time.  We consider {Loop}s dead even if only the first control input
     120             :   // is dead.
     121             :   int live_input_count = 0;
     122     8245084 :   if (node->opcode() != IrOpcode::kLoop ||
     123      668393 :       node->InputAt(0)->opcode() != IrOpcode::kDead) {
     124    24499948 :     for (int i = 0; i < inputs.count(); ++i) {
     125    24499836 :       Node* const input = inputs[i];
     126             :       // Skip dead inputs.
     127    24499836 :       if (input->opcode() == IrOpcode::kDead) continue;
     128             :       // Compact live inputs.
     129    24105691 :       if (live_input_count != i) {
     130      433547 :         node->ReplaceInput(live_input_count, input);
     131     2395960 :         for (Node* const use : node->uses()) {
     132     1528639 :           if (NodeProperties::IsPhi(use)) {
     133             :             DCHECK_EQ(inputs.count() + 1, use->InputCount());
     134      818269 :             use->ReplaceInput(live_input_count, use->InputAt(i));
     135             :           }
     136             :         }
     137             :       }
     138    24105803 :       ++live_input_count;
     139             :     }
     140             :   }
     141     7576803 :   if (live_input_count == 0) {
     142             :     return Replace(dead());
     143     7562324 :   } else if (live_input_count == 1) {
     144      515770 :     NodeVector loop_exits(zone_);
     145             :     // Due to compaction above, the live input is at offset 0.
     146     4411080 :     for (Node* const use : node->uses()) {
     147     1689769 :       if (NodeProperties::IsPhi(use)) {
     148      523815 :         Replace(use, use->InputAt(0));
     149     1331975 :       } else if (use->opcode() == IrOpcode::kLoopExit &&
     150             :                  use->InputAt(1) == node) {
     151             :         // Remember the loop exits so that we can mark their loop input dead.
     152             :         // This has to be done after the use list iteration so that we do
     153             :         // not mutate the use list while it is being iterated.
     154        3004 :         loop_exits.push_back(use);
     155     1324412 :       } else if (use->opcode() == IrOpcode::kTerminate) {
     156             :         DCHECK_EQ(IrOpcode::kLoop, node->opcode());
     157             :         Replace(use, dead());
     158             :       }
     159             :     }
     160     1034548 :     for (Node* loop_exit : loop_exits) {
     161        3004 :       loop_exit->ReplaceInput(1, dead());
     162             :       Revisit(loop_exit);
     163             :     }
     164             :     return Replace(node->InputAt(0));
     165             :   }
     166             :   DCHECK_LE(2, live_input_count);
     167             :   DCHECK_LE(live_input_count, inputs.count());
     168             :   // Trim input count for the {Merge} or {Loop} node.
     169     7046554 :   if (live_input_count < inputs.count()) {
     170             :     // Trim input counts for all phi uses and revisit them.
     171      531841 :     for (Node* const use : node->uses()) {
     172      330286 :       if (NodeProperties::IsPhi(use)) {
     173      150818 :         use->ReplaceInput(live_input_count, node);
     174      150817 :         TrimMergeOrPhi(use, live_input_count);
     175             :         Revisit(use);
     176             :       }
     177             :     }
     178      100777 :     TrimMergeOrPhi(node, live_input_count);
     179             :     return Changed(node);
     180             :   }
     181             :   return NoChange();
     182             : }
     183             : 
     184       25579 : Reduction DeadCodeElimination::RemoveLoopExit(Node* node) {
     185             :   DCHECK_EQ(IrOpcode::kLoopExit, node->opcode());
     186      248213 :   for (Node* const use : node->uses()) {
     187       98527 :     if (use->opcode() == IrOpcode::kLoopExitValue ||
     188             :         use->opcode() == IrOpcode::kLoopExitEffect) {
     189       98369 :       Replace(use, use->InputAt(0));
     190             :     }
     191             :   }
     192       25580 :   Node* control = NodeProperties::GetControlInput(node, 0);
     193             :   Replace(node, control);
     194       25580 :   return Replace(control);
     195             : }
     196             : 
     197   266394000 : Reduction DeadCodeElimination::ReduceNode(Node* node) {
     198             :   DCHECK(!IrOpcode::IsGraphTerminator(node->opcode()));
     199   245554740 :   int const effect_input_count = node->op()->EffectInputCount();
     200   245554740 :   int const control_input_count = node->op()->ControlInputCount();
     201             :   DCHECK_LE(control_input_count, 1);
     202   245554740 :   if (control_input_count == 1) {
     203   108847488 :     Reduction reduction = PropagateDeadControl(node);
     204   108841225 :     if (reduction.Changed()) return reduction;
     205             :   }
     206   490606584 :   if (effect_input_count == 0 &&
     207    20839260 :       (control_input_count == 0 || node->op()->ControlOutputCount() == 0)) {
     208   132854926 :     return ReducePureNode(node);
     209             :   }
     210   112448366 :   if (effect_input_count > 0) {
     211    92900854 :     return ReduceEffectNode(node);
     212             :   }
     213             :   return NoChange();
     214             : }
     215             : 
     216    12324321 : Reduction DeadCodeElimination::ReducePhi(Node* node) {
     217             :   DCHECK_EQ(IrOpcode::kPhi, node->opcode());
     218     4165601 :   Reduction reduction = PropagateDeadControl(node);
     219     4165330 :   if (reduction.Changed()) return reduction;
     220     4079819 :   MachineRepresentation rep = PhiRepresentationOf(node->op());
     221    12236925 :   if (rep == MachineRepresentation::kNone ||
     222    12238215 :       NodeProperties::GetTypeOrAny(node).IsNone()) {
     223          57 :     return Replace(DeadValue(node, rep));
     224             :   }
     225     4078901 :   int input_count = node->op()->ValueInputCount();
     226    18561746 :   for (int i = 0; i < input_count; ++i) {
     227    14482944 :     Node* input = NodeProperties::GetValueInput(node, i);
     228    14485028 :     if (input->opcode() == IrOpcode::kDeadValue &&
     229        2169 :         DeadValueRepresentationOf(input->op()) != rep) {
     230         708 :       NodeProperties::ReplaceValueInput(node, DeadValue(input, rep), i);
     231             :     }
     232             :   }
     233             :   return NoChange();
     234             : }
     235             : 
     236   132855228 : Reduction DeadCodeElimination::ReducePureNode(Node* node) {
     237             :   DCHECK_EQ(0, node->op()->EffectInputCount());
     238   132855228 :   if (node->opcode() == IrOpcode::kDeadValue) return NoChange();
     239   132802724 :   if (Node* input = FindDeadInput(node)) {
     240       88963 :     return Replace(DeadValue(input));
     241             :   }
     242             :   return NoChange();
     243             : }
     244             : 
     245     1918988 : Reduction DeadCodeElimination::ReduceUnreachableOrIfException(Node* node) {
     246             :   DCHECK(node->opcode() == IrOpcode::kUnreachable ||
     247             :          node->opcode() == IrOpcode::kIfException);
     248     1918988 :   Reduction reduction = PropagateDeadControl(node);
     249     1918987 :   if (reduction.Changed()) return reduction;
     250     1847638 :   Node* effect = NodeProperties::GetEffectInput(node, 0);
     251     1847633 :   if (effect->opcode() == IrOpcode::kDead) {
     252             :     return Replace(effect);
     253             :   }
     254     1847540 :   if (effect->opcode() == IrOpcode::kUnreachable) {
     255             :     return Replace(effect);
     256             :   }
     257             :   return NoChange();
     258             : }
     259             : 
     260    92904916 : Reduction DeadCodeElimination::ReduceEffectNode(Node* node) {
     261             :   DCHECK_EQ(1, node->op()->EffectInputCount());
     262    92908081 :   Node* effect = NodeProperties::GetEffectInput(node, 0);
     263    92897953 :   if (effect->opcode() == IrOpcode::kDead) {
     264             :     return Replace(effect);
     265             :   }
     266    92888253 :   if (Node* input = FindDeadInput(node)) {
     267        7970 :     if (effect->opcode() == IrOpcode::kUnreachable) {
     268        1581 :       RelaxEffectsAndControls(node);
     269        6389 :       return Replace(DeadValue(input));
     270             :     }
     271             : 
     272        1581 :     Node* control = node->op()->ControlInputCount() == 1
     273             :                         ? NodeProperties::GetControlInput(node, 0)
     274        1643 :                         : graph()->start();
     275             :     Node* unreachable =
     276        1581 :         graph()->NewNode(common()->Unreachable(), effect, control);
     277             :     NodeProperties::SetType(unreachable, Type::None());
     278        1581 :     ReplaceWithValue(node, DeadValue(input), node, control);
     279             :     return Replace(unreachable);
     280             :   }
     281             : 
     282             :   return NoChange();
     283             : }
     284             : 
     285     4573928 : Reduction DeadCodeElimination::ReduceDeoptimizeOrReturnOrTerminateOrTailCall(
     286         375 :     Node* node) {
     287             :   DCHECK(node->opcode() == IrOpcode::kDeoptimize ||
     288             :          node->opcode() == IrOpcode::kReturn ||
     289             :          node->opcode() == IrOpcode::kTerminate ||
     290             :          node->opcode() == IrOpcode::kTailCall);
     291     4573928 :   Reduction reduction = PropagateDeadControl(node);
     292     4573957 :   if (reduction.Changed()) return reduction;
     293     4535300 :   if (FindDeadInput(node) != nullptr) {
     294         526 :     Node* effect = NodeProperties::GetEffectInput(node, 0);
     295         263 :     Node* control = NodeProperties::GetControlInput(node, 0);
     296         263 :     if (effect->opcode() != IrOpcode::kUnreachable) {
     297          56 :       effect = graph()->NewNode(common()->Unreachable(), effect, control);
     298             :       NodeProperties::SetType(effect, Type::None());
     299             :     }
     300         263 :     node->TrimInputCount(2);
     301         263 :     node->ReplaceInput(0, effect);
     302         263 :     node->ReplaceInput(1, control);
     303         263 :     NodeProperties::ChangeOp(node, common()->Throw());
     304             :     return Changed(node);
     305             :   }
     306             :   return NoChange();
     307             : }
     308             : 
     309      314983 : Reduction DeadCodeElimination::ReduceLoopExit(Node* node) {
     310      629968 :   Node* control = NodeProperties::GetControlInput(node, 0);
     311      606873 :   Node* loop = NodeProperties::GetControlInput(node, 1);
     312      606874 :   if (control->opcode() == IrOpcode::kDead ||
     313             :       loop->opcode() == IrOpcode::kDead) {
     314       25580 :     return RemoveLoopExit(node);
     315             :   }
     316             :   return NoChange();
     317             : }
     318             : 
     319     9536465 : Reduction DeadCodeElimination::ReduceBranchOrSwitch(Node* node) {
     320             :   DCHECK(node->opcode() == IrOpcode::kBranch ||
     321             :          node->opcode() == IrOpcode::kSwitch);
     322     9534715 :   Reduction reduction = PropagateDeadControl(node);
     323     9534734 :   if (reduction.Changed()) return reduction;
     324     9506748 :   Node* condition = NodeProperties::GetValueInput(node, 0);
     325     9506692 :   if (condition->opcode() == IrOpcode::kDeadValue) {
     326             :     // Branches or switches on {DeadValue} must originate from unreachable code
     327             :     // and cannot matter. Due to schedule freedom between the effect and the
     328             :     // control chain, they might still appear in reachable code. Remove them by
     329             :     // always choosing the first projection.
     330        1750 :     size_t const projection_cnt = node->op()->ControlOutputCount();
     331         875 :     Node** projections = zone_->NewArray<Node*>(projection_cnt);
     332             :     NodeProperties::CollectControlProjections(node, projections,
     333         875 :                                               projection_cnt);
     334         875 :     Replace(projections[0], NodeProperties::GetControlInput(node));
     335             :     return Replace(dead());
     336             :   }
     337             :   return NoChange();
     338             : }
     339             : 
     340      251593 : void DeadCodeElimination::TrimMergeOrPhi(Node* node, int size) {
     341      251593 :   const Operator* const op = common()->ResizeMergeOrPhi(node->op(), size);
     342      251594 :   node->TrimInputCount(OperatorProperties::GetTotalInputCount(op));
     343      251595 :   NodeProperties::ChangeOp(node, op);
     344      251595 : }
     345             : 
     346      197716 : Node* DeadCodeElimination::DeadValue(Node* node, MachineRepresentation rep) {
     347       97698 :   if (node->opcode() == IrOpcode::kDeadValue) {
     348       48522 :     if (rep == DeadValueRepresentationOf(node->op())) return node;
     349         833 :     node = NodeProperties::GetValueInput(node, 0);
     350             :   }
     351       50009 :   Node* dead_value = graph()->NewNode(common()->DeadValue(rep), node);
     352             :   NodeProperties::SetType(dead_value, Type::None());
     353       50009 :   return dead_value;
     354             : }
     355             : 
     356             : }  // namespace compiler
     357             : }  // namespace internal
     358      183867 : }  // namespace v8

Generated by: LCOV version 1.10