LCOV - code coverage report
Current view: top level - src/compiler - common-operator-reducer.cc (source / functions) Hit Total Coverage
Test: app.info Lines: 136 147 92.5 %
Date: 2017-04-26 Functions: 11 12 91.7 %

          Line data    Source code
       1             : // Copyright 2014 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/common-operator-reducer.h"
       6             : 
       7             : #include <algorithm>
       8             : 
       9             : #include "src/compiler/common-operator.h"
      10             : #include "src/compiler/graph.h"
      11             : #include "src/compiler/machine-operator.h"
      12             : #include "src/compiler/node.h"
      13             : #include "src/compiler/node-matchers.h"
      14             : #include "src/compiler/node-properties.h"
      15             : 
      16             : namespace v8 {
      17             : namespace internal {
      18             : namespace compiler {
      19             : 
      20             : namespace {
      21             : 
      22     9282908 : Decision DecideCondition(Node* const cond) {
      23     9282908 :   switch (cond->opcode()) {
      24             :     case IrOpcode::kInt32Constant: {
      25             :       Int32Matcher mcond(cond);
      26      421680 :       return mcond.Value() ? Decision::kTrue : Decision::kFalse;
      27             :     }
      28             :     case IrOpcode::kHeapConstant: {
      29             :       HeapObjectMatcher mcond(cond);
      30       71282 :       return mcond.Value()->BooleanValue() ? Decision::kTrue : Decision::kFalse;
      31             :     }
      32             :     default:
      33             :       return Decision::kUnknown;
      34             :   }
      35             : }
      36             : 
      37             : }  // namespace
      38             : 
      39     2446735 : CommonOperatorReducer::CommonOperatorReducer(Editor* editor, Graph* graph,
      40             :                                              CommonOperatorBuilder* common,
      41             :                                              MachineOperatorBuilder* machine)
      42             :     : AdvancedReducer(editor),
      43             :       graph_(graph),
      44             :       common_(common),
      45             :       machine_(machine),
      46     4893478 :       dead_(graph->NewNode(common->Dead())) {
      47             :   NodeProperties::SetType(dead_, Type::None());
      48     2446743 : }
      49             : 
      50   225930747 : Reduction CommonOperatorReducer::Reduce(Node* node) {
      51   225930747 :   switch (node->opcode()) {
      52             :     case IrOpcode::kBranch:
      53     8540551 :       return ReduceBranch(node);
      54             :     case IrOpcode::kDeoptimizeIf:
      55             :     case IrOpcode::kDeoptimizeUnless:
      56      616020 :       return ReduceDeoptimizeConditional(node);
      57             :     case IrOpcode::kMerge:
      58     6313169 :       return ReduceMerge(node);
      59             :     case IrOpcode::kEffectPhi:
      60     6217824 :       return ReduceEffectPhi(node);
      61             :     case IrOpcode::kPhi:
      62     4710406 :       return ReducePhi(node);
      63             :     case IrOpcode::kReturn:
      64     3472694 :       return ReduceReturn(node);
      65             :     case IrOpcode::kSelect:
      66       72581 :       return ReduceSelect(node);
      67             :     default:
      68             :       break;
      69             :   }
      70             :   return NoChange();
      71             : }
      72             : 
      73             : 
      74     9447307 : Reduction CommonOperatorReducer::ReduceBranch(Node* node) {
      75             :   DCHECK_EQ(IrOpcode::kBranch, node->opcode());
      76     8540533 :   Node* const cond = node->InputAt(0);
      77             :   // Swap IfTrue/IfFalse on {branch} if {cond} is a BooleanNot and use the input
      78             :   // to BooleanNot as new condition for {branch}. Note we assume that {cond} was
      79             :   // already properly optimized before we get here (as guaranteed by the graph
      80             :   // reduction logic). The same applies if {cond} is a Select acting as boolean
      81             :   // not (i.e. true being returned in the false case and vice versa).
      82    17081066 :   if (cond->opcode() == IrOpcode::kBooleanNot ||
      83       58624 :       (cond->opcode() == IrOpcode::kSelect &&
      84       67347 :        DecideCondition(cond->InputAt(1)) == Decision::kFalse &&
      85             :        DecideCondition(cond->InputAt(2)) == Decision::kTrue)) {
      86       66140 :     for (Node* const use : node->uses()) {
      87       26456 :       switch (use->opcode()) {
      88             :         case IrOpcode::kIfTrue:
      89       13228 :           NodeProperties::ChangeOp(use, common()->IfFalse());
      90       13228 :           break;
      91             :         case IrOpcode::kIfFalse:
      92       13228 :           NodeProperties::ChangeOp(use, common()->IfTrue());
      93       13228 :           break;
      94             :         default:
      95           0 :           UNREACHABLE();
      96             :       }
      97             :     }
      98             :     // Update the condition of {branch}. No need to mark the uses for revisit,
      99             :     // since we tell the graph reducer that the {branch} was changed and the
     100             :     // graph reduction logic will ensure that the uses are revisited properly.
     101       13228 :     node->ReplaceInput(0, cond->InputAt(0));
     102             :     // Negate the hint for {branch}.
     103             :     NodeProperties::ChangeOp(
     104       26456 :         node, common()->Branch(NegateBranchHint(BranchHintOf(node->op()))));
     105             :     return Changed(node);
     106             :   }
     107     8527305 :   Decision const decision = DecideCondition(cond);
     108     8527296 :   if (decision == Decision::kUnknown) return NoChange();
     109             :   Node* const control = node->InputAt(1);
     110     2134655 :   for (Node* const use : node->uses()) {
     111      853862 :     switch (use->opcode()) {
     112             :       case IrOpcode::kIfTrue:
     113     1280793 :         Replace(use, (decision == Decision::kTrue) ? control : dead());
     114             :         break;
     115             :       case IrOpcode::kIfFalse:
     116      426931 :         Replace(use, (decision == Decision::kFalse) ? control : dead());
     117             :         break;
     118             :       default:
     119           0 :         UNREACHABLE();
     120             :     }
     121             :   }
     122             :   return Replace(dead());
     123             : }
     124             : 
     125      642852 : Reduction CommonOperatorReducer::ReduceDeoptimizeConditional(Node* node) {
     126             :   DCHECK(node->opcode() == IrOpcode::kDeoptimizeIf ||
     127             :          node->opcode() == IrOpcode::kDeoptimizeUnless);
     128      616018 :   bool condition_is_true = node->opcode() == IrOpcode::kDeoptimizeUnless;
     129      616018 :   DeoptimizeParameters p = DeoptimizeParametersOf(node->op());
     130     1232034 :   Node* condition = NodeProperties::GetValueInput(node, 0);
     131      616020 :   Node* frame_state = NodeProperties::GetValueInput(node, 1);
     132      616018 :   Node* effect = NodeProperties::GetEffectInput(node);
     133      616016 :   Node* control = NodeProperties::GetControlInput(node);
     134             :   // Swap DeoptimizeIf/DeoptimizeUnless on {node} if {cond} is a BooleaNot
     135             :   // and use the input to BooleanNot as new condition for {node}.  Note we
     136             :   // assume that {cond} was already properly optimized before we get here
     137             :   // (as guaranteed by the graph reduction logic).
     138      616015 :   if (condition->opcode() == IrOpcode::kBooleanNot) {
     139           0 :     NodeProperties::ReplaceValueInput(node, condition->InputAt(0), 0);
     140             :     NodeProperties::ChangeOp(
     141             :         node, condition_is_true
     142             :                   ? common()->DeoptimizeIf(p.kind(), p.reason())
     143           0 :                   : common()->DeoptimizeUnless(p.kind(), p.reason()));
     144             :     return Changed(node);
     145             :   }
     146      616015 :   Decision const decision = DecideCondition(condition);
     147      616015 :   if (decision == Decision::kUnknown) return NoChange();
     148        6463 :   if (condition_is_true == (decision == Decision::kTrue)) {
     149        6463 :     ReplaceWithValue(node, dead(), effect, control);
     150             :   } else {
     151             :     control = graph()->NewNode(common()->Deoptimize(p.kind(), p.reason()),
     152        4636 :                                frame_state, effect, control);
     153             :     // TODO(bmeurer): This should be on the AdvancedReducer somehow.
     154        4636 :     NodeProperties::MergeControlToEnd(graph(), common(), control);
     155        4636 :     Revisit(graph()->end());
     156             :   }
     157             :   return Replace(dead());
     158             : }
     159             : 
     160     6315616 : Reduction CommonOperatorReducer::ReduceMerge(Node* node) {
     161             :   DCHECK_EQ(IrOpcode::kMerge, node->opcode());
     162             :   //
     163             :   // Check if this is a merge that belongs to an unused diamond, which means
     164             :   // that:
     165             :   //
     166             :   //  a) the {Merge} has no {Phi} or {EffectPhi} uses, and
     167             :   //  b) the {Merge} has two inputs, one {IfTrue} and one {IfFalse}, which are
     168             :   //     both owned by the Merge, and
     169             :   //  c) and the {IfTrue} and {IfFalse} nodes point to the same {Branch}.
     170             :   //
     171     6312664 :   if (node->InputCount() == 2) {
     172    30454183 :     for (Node* const use : node->uses()) {
     173    15128947 :       if (IrOpcode::IsPhiOpcode(use->opcode())) return NoChange();
     174             :     }
     175             :     Node* if_true = node->InputAt(0);
     176             :     Node* if_false = node->InputAt(1);
     177      395559 :     if (if_true->opcode() != IrOpcode::kIfTrue) std::swap(if_true, if_false);
     178      310589 :     if (if_true->opcode() == IrOpcode::kIfTrue &&
     179      176817 :         if_false->opcode() == IrOpcode::kIfFalse &&
     180      202242 :         if_true->InputAt(0) == if_false->InputAt(0) && if_true->OwnedBy(node) &&
     181        2972 :         if_false->OwnedBy(node)) {
     182             :       Node* const branch = if_true->InputAt(0);
     183             :       DCHECK_EQ(IrOpcode::kBranch, branch->opcode());
     184             :       DCHECK(branch->OwnedBy(if_true, if_false));
     185             :       Node* const control = branch->InputAt(1);
     186             :       // Mark the {branch} as {Dead}.
     187        2952 :       branch->TrimInputCount(0);
     188        2952 :       NodeProperties::ChangeOp(branch, common()->Dead());
     189             :       return Replace(control);
     190             :     }
     191             :   }
     192             :   return NoChange();
     193             : }
     194             : 
     195             : 
     196     6217822 : Reduction CommonOperatorReducer::ReduceEffectPhi(Node* node) {
     197             :   DCHECK_EQ(IrOpcode::kEffectPhi, node->opcode());
     198             :   Node::Inputs inputs = node->inputs();
     199     6217822 :   int const effect_input_count = inputs.count() - 1;
     200             :   DCHECK_LE(1, effect_input_count);
     201             :   Node* const merge = inputs[effect_input_count];
     202             :   DCHECK(IrOpcode::IsMergeOpcode(merge->opcode()));
     203             :   DCHECK_EQ(effect_input_count, merge->InputCount());
     204             :   Node* const effect = inputs[0];
     205             :   DCHECK_NE(node, effect);
     206     6465826 :   for (int i = 1; i < effect_input_count; ++i) {
     207             :     Node* const input = inputs[i];
     208     6407040 :     if (input == node) {
     209             :       // Ignore redundant inputs.
     210             :       DCHECK_EQ(IrOpcode::kLoop, merge->opcode());
     211             :       continue;
     212             :     }
     213     6406967 :     if (input != effect) return NoChange();
     214             :   }
     215             :   // We might now be able to further reduce the {merge} node.
     216       58786 :   Revisit(merge);
     217             :   return Replace(effect);
     218             : }
     219             : 
     220             : 
     221     4710532 : Reduction CommonOperatorReducer::ReducePhi(Node* node) {
     222             :   DCHECK_EQ(IrOpcode::kPhi, node->opcode());
     223             :   Node::Inputs inputs = node->inputs();
     224     4710530 :   int const value_input_count = inputs.count() - 1;
     225             :   DCHECK_LE(1, value_input_count);
     226             :   Node* const merge = inputs[value_input_count];
     227             :   DCHECK(IrOpcode::IsMergeOpcode(merge->opcode()));
     228             :   DCHECK_EQ(value_input_count, merge->InputCount());
     229     4710530 :   if (value_input_count == 2) {
     230             :     Node* vtrue = inputs[0];
     231             :     Node* vfalse = inputs[1];
     232             :     Node::Inputs merge_inputs = merge->inputs();
     233             :     Node* if_true = merge_inputs[0];
     234             :     Node* if_false = merge_inputs[1];
     235     8114090 :     if (if_true->opcode() != IrOpcode::kIfTrue) {
     236             :       std::swap(if_true, if_false);
     237             :       std::swap(vtrue, vfalse);
     238             :     }
     239     6325767 :     if (if_true->opcode() == IrOpcode::kIfTrue &&
     240     5143142 :         if_false->opcode() == IrOpcode::kIfFalse &&
     241             :         if_true->InputAt(0) == if_false->InputAt(0)) {
     242     1063718 :       Node* const branch = if_true->InputAt(0);
     243             :       // Check that the branch is not dead already.
     244     1063718 :       if (branch->opcode() != IrOpcode::kBranch) return NoChange();
     245     1063718 :       Node* const cond = branch->InputAt(0);
     246     1063718 :       if (cond->opcode() == IrOpcode::kFloat32LessThan) {
     247         603 :         Float32BinopMatcher mcond(cond);
     248         612 :         if (mcond.left().Is(0.0) && mcond.right().Equals(vtrue) &&
     249          61 :             vfalse->opcode() == IrOpcode::kFloat32Sub) {
     250           1 :           Float32BinopMatcher mvfalse(vfalse);
     251           2 :           if (mvfalse.left().IsZero() && mvfalse.right().Equals(vtrue)) {
     252             :             // We might now be able to further reduce the {merge} node.
     253      125671 :             Revisit(merge);
     254           1 :             return Change(node, machine()->Float32Abs(), vtrue);
     255             :           }
     256             :         }
     257     1063115 :       } else if (cond->opcode() == IrOpcode::kFloat64LessThan) {
     258        3964 :         Float64BinopMatcher mcond(cond);
     259        5589 :         if (mcond.left().Is(0.0) && mcond.right().Equals(vtrue) &&
     260             :             vfalse->opcode() == IrOpcode::kFloat64Sub) {
     261           1 :           Float64BinopMatcher mvfalse(vfalse);
     262           2 :           if (mvfalse.left().IsZero() && mvfalse.right().Equals(vtrue)) {
     263             :             // We might now be able to further reduce the {merge} node.
     264             :             Revisit(merge);
     265           1 :             return Change(node, machine()->Float64Abs(), vtrue);
     266             :           }
     267             :         }
     268             :       }
     269             :     }
     270             :   }
     271             :   Node* const value = inputs[0];
     272             :   DCHECK_NE(node, value);
     273     5396922 :   for (int i = 1; i < value_input_count; ++i) {
     274             :     Node* const input = inputs[i];
     275     5271253 :     if (input == node) {
     276             :       // Ignore redundant inputs.
     277             :       DCHECK_EQ(IrOpcode::kLoop, merge->opcode());
     278             :       continue;
     279             :     }
     280     5197610 :     if (input != value) return NoChange();
     281             :   }
     282             :   // We might now be able to further reduce the {merge} node.
     283             :   Revisit(merge);
     284             :   return Replace(value);
     285             : }
     286             : 
     287     7315937 : Reduction CommonOperatorReducer::ReduceReturn(Node* node) {
     288             :   DCHECK_EQ(IrOpcode::kReturn, node->opcode());
     289     3562605 :   Node* effect = NodeProperties::GetEffectInput(node);
     290     3518411 :   if (effect->opcode() == IrOpcode::kCheckpoint) {
     291             :     // Any {Return} node can never be used to insert a deoptimization point,
     292             :     // hence checkpoints can be cut out of the effect chain flowing into it.
     293       45724 :     effect = NodeProperties::GetEffectInput(effect);
     294       45724 :     NodeProperties::ReplaceEffectInput(node, effect);
     295       45724 :     Reduction const reduction = ReduceReturn(node);
     296       45724 :     return reduction.Changed() ? reduction : Changed(node);
     297             :   }
     298             :   // TODO(ahaas): Extend the reduction below to multiple return values.
     299     3472687 :   if (ValueInputCountOfReturn(node->op()) != 1) {
     300             :     return NoChange();
     301             :   }
     302     3457969 :   Node* pop_count = NodeProperties::GetValueInput(node, 0);
     303     6916028 :   Node* value = NodeProperties::GetValueInput(node, 1);
     304     3510072 :   Node* control = NodeProperties::GetControlInput(node);
     305     3597869 :   if (value->opcode() == IrOpcode::kPhi &&
     306     3510086 :       NodeProperties::GetControlInput(value) == control &&
     307             :       control->opcode() == IrOpcode::kMerge) {
     308             :     // This optimization pushes {Return} nodes through merges. It checks that
     309             :     // the return value is actually a {Phi} and the return control dependency
     310             :     // is the {Merge} to which the {Phi} belongs.
     311             : 
     312             :     // Value1 ... ValueN Control1 ... ControlN
     313             :     //   ^          ^       ^            ^
     314             :     //   |          |       |            |
     315             :     //   +----+-----+       +------+-----+
     316             :     //        |                    |
     317             :     //       Phi --------------> Merge
     318             :     //        ^                    ^
     319             :     //        |                    |
     320             :     //        |  +-----------------+
     321             :     //        |  |
     322             :     //       Return -----> Effect
     323             :     //         ^
     324             :     //         |
     325             :     //        End
     326             : 
     327             :     // Now the effect input to the {Return} node can be either an {EffectPhi}
     328             :     // hanging off the same {Merge}, or the {Merge} node is only connected to
     329             :     // the {Return} and the {Phi}, in which case we know that the effect input
     330             :     // must somehow dominate all merged branches.
     331             : 
     332             :     Node::Inputs control_inputs = control->inputs();
     333             :     Node::Inputs value_inputs = value->inputs();
     334             :     DCHECK_NE(0, control_inputs.count());
     335             :     DCHECK_EQ(control_inputs.count(), value_inputs.count() - 1);
     336             :     DCHECK_EQ(IrOpcode::kEnd, graph()->end()->opcode());
     337             :     DCHECK_NE(0, graph()->end()->InputCount());
     338       52063 :     if (control->OwnedBy(node, value)) {
     339       15913 :       for (int i = 0; i < control_inputs.count(); ++i) {
     340             :         // Create a new {Return} and connect it to {end}. We don't need to mark
     341             :         // {end} as revisit, because we mark {node} as {Dead} below, which was
     342             :         // previously connected to {end}, so we know for sure that at some point
     343             :         // the reducer logic will visit {end} again.
     344             :         Node* ret = graph()->NewNode(node->op(), pop_count, value_inputs[i],
     345             :                                      effect, control_inputs[i]);
     346       15913 :         NodeProperties::MergeControlToEnd(graph(), common(), ret);
     347             :       }
     348             :       // Mark the Merge {control} and Return {node} as {dead}.
     349       50678 :       Replace(control, dead());
     350             :       return Replace(dead());
     351       87031 :     } else if (effect->opcode() == IrOpcode::kEffectPhi &&
     352       42834 :                NodeProperties::GetControlInput(effect) == control) {
     353             :       Node::Inputs effect_inputs = effect->inputs();
     354             :       DCHECK_EQ(control_inputs.count(), effect_inputs.count() - 1);
     355      138642 :       for (int i = 0; i < control_inputs.count(); ++i) {
     356             :         // Create a new {Return} and connect it to {end}. We don't need to mark
     357             :         // {end} as revisit, because we mark {node} as {Dead} below, which was
     358             :         // previously connected to {end}, so we know for sure that at some point
     359             :         // the reducer logic will visit {end} again.
     360             :         Node* ret = graph()->NewNode(node->op(), pop_count, value_inputs[i],
     361             :                                      effect_inputs[i], control_inputs[i]);
     362       95830 :         NodeProperties::MergeControlToEnd(graph(), common(), ret);
     363             :       }
     364             :       // Mark the Merge {control} and Return {node} as {dead}.
     365             :       Replace(control, dead());
     366             :       return Replace(dead());
     367             :     }
     368             :   }
     369             :   return NoChange();
     370             : }
     371             : 
     372       72583 : Reduction CommonOperatorReducer::ReduceSelect(Node* node) {
     373             :   DCHECK_EQ(IrOpcode::kSelect, node->opcode());
     374       72280 :   Node* const cond = node->InputAt(0);
     375             :   Node* const vtrue = node->InputAt(1);
     376          50 :   Node* const vfalse = node->InputAt(2);
     377       72581 :   if (vtrue == vfalse) return Replace(vtrue);
     378       72405 :   switch (DecideCondition(cond)) {
     379             :     case Decision::kTrue:
     380             :       return Replace(vtrue);
     381             :     case Decision::kFalse:
     382             :       return Replace(vfalse);
     383             :     case Decision::kUnknown:
     384             :       break;
     385             :   }
     386       72280 :   switch (cond->opcode()) {
     387             :     case IrOpcode::kFloat32LessThan: {
     388           1 :       Float32BinopMatcher mcond(cond);
     389           3 :       if (mcond.left().Is(0.0) && mcond.right().Equals(vtrue) &&
     390             :           vfalse->opcode() == IrOpcode::kFloat32Sub) {
     391           1 :         Float32BinopMatcher mvfalse(vfalse);
     392           2 :         if (mvfalse.left().IsZero() && mvfalse.right().Equals(vtrue)) {
     393           1 :           return Change(node, machine()->Float32Abs(), vtrue);
     394             :         }
     395             :       }
     396           0 :       break;
     397             :     }
     398             :     case IrOpcode::kFloat64LessThan: {
     399        2305 :       Float64BinopMatcher mcond(cond);
     400        3441 :       if (mcond.left().Is(0.0) && mcond.right().Equals(vtrue) &&
     401             :           vfalse->opcode() == IrOpcode::kFloat64Sub) {
     402           1 :         Float64BinopMatcher mvfalse(vfalse);
     403           2 :         if (mvfalse.left().IsZero() && mvfalse.right().Equals(vtrue)) {
     404           1 :           return Change(node, machine()->Float64Abs(), vtrue);
     405             :         }
     406             :       }
     407        2304 :       break;
     408             :     }
     409             :     default:
     410             :       break;
     411             :   }
     412             :   return NoChange();
     413             : }
     414             : 
     415             : 
     416           4 : Reduction CommonOperatorReducer::Change(Node* node, Operator const* op,
     417             :                                         Node* a) {
     418           4 :   node->ReplaceInput(0, a);
     419           4 :   node->TrimInputCount(1);
     420           4 :   NodeProperties::ChangeOp(node, op);
     421           4 :   return Changed(node);
     422             : }
     423             : 
     424             : 
     425           0 : Reduction CommonOperatorReducer::Change(Node* node, Operator const* op, Node* a,
     426             :                                         Node* b) {
     427           0 :   node->ReplaceInput(0, a);
     428           0 :   node->ReplaceInput(1, b);
     429           0 :   node->TrimInputCount(2);
     430           0 :   NodeProperties::ChangeOp(node, op);
     431           0 :   return Changed(node);
     432             : }
     433             : 
     434             : }  // namespace compiler
     435             : }  // namespace internal
     436             : }  // namespace v8

Generated by: LCOV version 1.10