Home | History | Annotate | Download | only in compiler 
      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 Decision DecideCondition(Node* const cond) {
     23   switch (cond->opcode()) {
     24     case IrOpcode::kInt32Constant: {
     25       Int32Matcher mcond(cond);
     26       return mcond.Value() ? Decision::kTrue : Decision::kFalse;
     27     }
     28     case IrOpcode::kHeapConstant: {
     29       HeapObjectMatcher mcond(cond);
     30       return mcond.Value()->BooleanValue() ? Decision::kTrue : Decision::kFalse;
     31     }
     32     default:
     33       return Decision::kUnknown;
     34   }
     35 }
     36 
     37 }  // namespace
     38 
     39 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       dead_(graph->NewNode(common->Dead())) {
     47   NodeProperties::SetType(dead_, Type::None());
     48 }
     49 
     50 Reduction CommonOperatorReducer::Reduce(Node* node) {
     51   switch (node->opcode()) {
     52     case IrOpcode::kBranch:
     53       return ReduceBranch(node);
     54     case IrOpcode::kDeoptimizeIf:
     55     case IrOpcode::kDeoptimizeUnless:
     56       return ReduceDeoptimizeConditional(node);
     57     case IrOpcode::kMerge:
     58       return ReduceMerge(node);
     59     case IrOpcode::kEffectPhi:
     60       return ReduceEffectPhi(node);
     61     case IrOpcode::kPhi:
     62       return ReducePhi(node);
     63     case IrOpcode::kReturn:
     64       return ReduceReturn(node);
     65     case IrOpcode::kSelect:
     66       return ReduceSelect(node);
     67     default:
     68       break;
     69   }
     70   return NoChange();
     71 }
     72 
     73 
     74 Reduction CommonOperatorReducer::ReduceBranch(Node* node) {
     75   DCHECK_EQ(IrOpcode::kBranch, node->opcode());
     76   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   if (cond->opcode() == IrOpcode::kBooleanNot ||
     83       (cond->opcode() == IrOpcode::kSelect &&
     84        DecideCondition(cond->InputAt(1)) == Decision::kFalse &&
     85        DecideCondition(cond->InputAt(2)) == Decision::kTrue)) {
     86     for (Node* const use : node->uses()) {
     87       switch (use->opcode()) {
     88         case IrOpcode::kIfTrue:
     89           NodeProperties::ChangeOp(use, common()->IfFalse());
     90           break;
     91         case IrOpcode::kIfFalse:
     92           NodeProperties::ChangeOp(use, common()->IfTrue());
     93           break;
     94         default:
     95           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     node->ReplaceInput(0, cond->InputAt(0));
    102     // Negate the hint for {branch}.
    103     NodeProperties::ChangeOp(
    104         node, common()->Branch(NegateBranchHint(BranchHintOf(node->op()))));
    105     return Changed(node);
    106   }
    107   Decision const decision = DecideCondition(cond);
    108   if (decision == Decision::kUnknown) return NoChange();
    109   Node* const control = node->InputAt(1);
    110   for (Node* const use : node->uses()) {
    111     switch (use->opcode()) {
    112       case IrOpcode::kIfTrue:
    113         Replace(use, (decision == Decision::kTrue) ? control : dead());
    114         break;
    115       case IrOpcode::kIfFalse:
    116         Replace(use, (decision == Decision::kFalse) ? control : dead());
    117         break;
    118       default:
    119         UNREACHABLE();
    120     }
    121   }
    122   return Replace(dead());
    123 }
    124 
    125 Reduction CommonOperatorReducer::ReduceDeoptimizeConditional(Node* node) {
    126   DCHECK(node->opcode() == IrOpcode::kDeoptimizeIf ||
    127          node->opcode() == IrOpcode::kDeoptimizeUnless);
    128   bool condition_is_true = node->opcode() == IrOpcode::kDeoptimizeUnless;
    129   DeoptimizeParameters p = DeoptimizeParametersOf(node->op());
    130   Node* condition = NodeProperties::GetValueInput(node, 0);
    131   Node* frame_state = NodeProperties::GetValueInput(node, 1);
    132   Node* effect = NodeProperties::GetEffectInput(node);
    133   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   if (condition->opcode() == IrOpcode::kBooleanNot) {
    139     NodeProperties::ReplaceValueInput(node, condition->InputAt(0), 0);
    140     NodeProperties::ChangeOp(
    141         node, condition_is_true
    142                   ? common()->DeoptimizeIf(p.kind(), p.reason())
    143                   : common()->DeoptimizeUnless(p.kind(), p.reason()));
    144     return Changed(node);
    145   }
    146   Decision const decision = DecideCondition(condition);
    147   if (decision == Decision::kUnknown) return NoChange();
    148   if (condition_is_true == (decision == Decision::kTrue)) {
    149     ReplaceWithValue(node, dead(), effect, control);
    150   } else {
    151     control = graph()->NewNode(common()->Deoptimize(p.kind(), p.reason()),
    152                                frame_state, effect, control);
    153     // TODO(bmeurer): This should be on the AdvancedReducer somehow.
    154     NodeProperties::MergeControlToEnd(graph(), common(), control);
    155     Revisit(graph()->end());
    156   }
    157   return Replace(dead());
    158 }
    159 
    160 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   if (node->InputCount() == 2) {
    172     for (Node* const use : node->uses()) {
    173       if (IrOpcode::IsPhiOpcode(use->opcode())) return NoChange();
    174     }
    175     Node* if_true = node->InputAt(0);
    176     Node* if_false = node->InputAt(1);
    177     if (if_true->opcode() != IrOpcode::kIfTrue) std::swap(if_true, if_false);
    178     if (if_true->opcode() == IrOpcode::kIfTrue &&
    179         if_false->opcode() == IrOpcode::kIfFalse &&
    180         if_true->InputAt(0) == if_false->InputAt(0) && if_true->OwnedBy(node) &&
    181         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       branch->TrimInputCount(0);
    188       NodeProperties::ChangeOp(branch, common()->Dead());
    189       return Replace(control);
    190     }
    191   }
    192   return NoChange();
    193 }
    194 
    195 
    196 Reduction CommonOperatorReducer::ReduceEffectPhi(Node* node) {
    197   DCHECK_EQ(IrOpcode::kEffectPhi, node->opcode());
    198   Node::Inputs inputs = node->inputs();
    199   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   for (int i = 1; i < effect_input_count; ++i) {
    207     Node* const input = inputs[i];
    208     if (input == node) {
    209       // Ignore redundant inputs.
    210       DCHECK_EQ(IrOpcode::kLoop, merge->opcode());
    211       continue;
    212     }
    213     if (input != effect) return NoChange();
    214   }
    215   // We might now be able to further reduce the {merge} node.
    216   Revisit(merge);
    217   return Replace(effect);
    218 }
    219 
    220 
    221 Reduction CommonOperatorReducer::ReducePhi(Node* node) {
    222   DCHECK_EQ(IrOpcode::kPhi, node->opcode());
    223   Node::Inputs inputs = node->inputs();
    224   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   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     if (if_true->opcode() != IrOpcode::kIfTrue) {
    236       std::swap(if_true, if_false);
    237       std::swap(vtrue, vfalse);
    238     }
    239     if (if_true->opcode() == IrOpcode::kIfTrue &&
    240         if_false->opcode() == IrOpcode::kIfFalse &&
    241         if_true->InputAt(0) == if_false->InputAt(0)) {
    242       Node* const branch = if_true->InputAt(0);
    243       // Check that the branch is not dead already.
    244       if (branch->opcode() != IrOpcode::kBranch) return NoChange();
    245       Node* const cond = branch->InputAt(0);
    246       if (cond->opcode() == IrOpcode::kFloat32LessThan) {
    247         Float32BinopMatcher mcond(cond);
    248         if (mcond.left().Is(0.0) && mcond.right().Equals(vtrue) &&
    249             vfalse->opcode() == IrOpcode::kFloat32Sub) {
    250           Float32BinopMatcher mvfalse(vfalse);
    251           if (mvfalse.left().IsZero() && mvfalse.right().Equals(vtrue)) {
    252             // We might now be able to further reduce the {merge} node.
    253             Revisit(merge);
    254             return Change(node, machine()->Float32Abs(), vtrue);
    255           }
    256         }
    257       } else if (cond->opcode() == IrOpcode::kFloat64LessThan) {
    258         Float64BinopMatcher mcond(cond);
    259         if (mcond.left().Is(0.0) && mcond.right().Equals(vtrue) &&
    260             vfalse->opcode() == IrOpcode::kFloat64Sub) {
    261           Float64BinopMatcher mvfalse(vfalse);
    262           if (mvfalse.left().IsZero() && mvfalse.right().Equals(vtrue)) {
    263             // We might now be able to further reduce the {merge} node.
    264             Revisit(merge);
    265             return Change(node, machine()->Float64Abs(), vtrue);
    266           }
    267         }
    268       }
    269     }
    270   }
    271   Node* const value = inputs[0];
    272   DCHECK_NE(node, value);
    273   for (int i = 1; i < value_input_count; ++i) {
    274     Node* const input = inputs[i];
    275     if (input == node) {
    276       // Ignore redundant inputs.
    277       DCHECK_EQ(IrOpcode::kLoop, merge->opcode());
    278       continue;
    279     }
    280     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 Reduction CommonOperatorReducer::ReduceReturn(Node* node) {
    288   DCHECK_EQ(IrOpcode::kReturn, node->opcode());
    289   Node* effect = NodeProperties::GetEffectInput(node);
    290   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     effect = NodeProperties::GetEffectInput(effect);
    294     NodeProperties::ReplaceEffectInput(node, effect);
    295     Reduction const reduction = ReduceReturn(node);
    296     return reduction.Changed() ? reduction : Changed(node);
    297   }
    298   // TODO(ahaas): Extend the reduction below to multiple return values.
    299   if (ValueInputCountOfReturn(node->op()) != 1) {
    300     return NoChange();
    301   }
    302   Node* pop_count = NodeProperties::GetValueInput(node, 0);
    303   Node* value = NodeProperties::GetValueInput(node, 1);
    304   Node* control = NodeProperties::GetControlInput(node);
    305   if (value->opcode() == IrOpcode::kPhi &&
    306       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     if (control->OwnedBy(node, value)) {
    339       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         NodeProperties::MergeControlToEnd(graph(), common(), ret);
    347       }
    348       // Mark the Merge {control} and Return {node} as {dead}.
    349       Replace(control, dead());
    350       return Replace(dead());
    351     } else if (effect->opcode() == IrOpcode::kEffectPhi &&
    352                NodeProperties::GetControlInput(effect) == control) {
    353       Node::Inputs effect_inputs = effect->inputs();
    354       DCHECK_EQ(control_inputs.count(), effect_inputs.count() - 1);
    355       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         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 Reduction CommonOperatorReducer::ReduceSelect(Node* node) {
    373   DCHECK_EQ(IrOpcode::kSelect, node->opcode());
    374   Node* const cond = node->InputAt(0);
    375   Node* const vtrue = node->InputAt(1);
    376   Node* const vfalse = node->InputAt(2);
    377   if (vtrue == vfalse) return Replace(vtrue);
    378   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   switch (cond->opcode()) {
    387     case IrOpcode::kFloat32LessThan: {
    388       Float32BinopMatcher mcond(cond);
    389       if (mcond.left().Is(0.0) && mcond.right().Equals(vtrue) &&
    390           vfalse->opcode() == IrOpcode::kFloat32Sub) {
    391         Float32BinopMatcher mvfalse(vfalse);
    392         if (mvfalse.left().IsZero() && mvfalse.right().Equals(vtrue)) {
    393           return Change(node, machine()->Float32Abs(), vtrue);
    394         }
    395       }
    396       break;
    397     }
    398     case IrOpcode::kFloat64LessThan: {
    399       Float64BinopMatcher mcond(cond);
    400       if (mcond.left().Is(0.0) && mcond.right().Equals(vtrue) &&
    401           vfalse->opcode() == IrOpcode::kFloat64Sub) {
    402         Float64BinopMatcher mvfalse(vfalse);
    403         if (mvfalse.left().IsZero() && mvfalse.right().Equals(vtrue)) {
    404           return Change(node, machine()->Float64Abs(), vtrue);
    405         }
    406       }
    407       break;
    408     }
    409     default:
    410       break;
    411   }
    412   return NoChange();
    413 }
    414 
    415 
    416 Reduction CommonOperatorReducer::Change(Node* node, Operator const* op,
    417                                         Node* a) {
    418   node->ReplaceInput(0, a);
    419   node->TrimInputCount(1);
    420   NodeProperties::ChangeOp(node, op);
    421   return Changed(node);
    422 }
    423 
    424 
    425 Reduction CommonOperatorReducer::Change(Node* node, Operator const* op, Node* a,
    426                                         Node* b) {
    427   node->ReplaceInput(0, a);
    428   node->ReplaceInput(1, b);
    429   node->TrimInputCount(2);
    430   NodeProperties::ChangeOp(node, op);
    431   return Changed(node);
    432 }
    433 
    434 }  // namespace compiler
    435 }  // namespace internal
    436 }  // namespace v8
    437