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 enum class Decision { kUnknown, kTrue, kFalse };
     23 
     24 Decision DecideCondition(Node* const cond) {
     25   switch (cond->opcode()) {
     26     case IrOpcode::kInt32Constant: {
     27       Int32Matcher mcond(cond);
     28       return mcond.Value() ? Decision::kTrue : Decision::kFalse;
     29     }
     30     case IrOpcode::kInt64Constant: {
     31       Int64Matcher mcond(cond);
     32       return mcond.Value() ? Decision::kTrue : Decision::kFalse;
     33     }
     34     case IrOpcode::kHeapConstant: {
     35       HeapObjectMatcher mcond(cond);
     36       return mcond.Value()->BooleanValue() ? Decision::kTrue : Decision::kFalse;
     37     }
     38     default:
     39       return Decision::kUnknown;
     40   }
     41 }
     42 
     43 }  // namespace
     44 
     45 
     46 CommonOperatorReducer::CommonOperatorReducer(Editor* editor, Graph* graph,
     47                                              CommonOperatorBuilder* common,
     48                                              MachineOperatorBuilder* machine)
     49     : AdvancedReducer(editor),
     50       graph_(graph),
     51       common_(common),
     52       machine_(machine),
     53       dead_(graph->NewNode(common->Dead())) {}
     54 
     55 
     56 Reduction CommonOperatorReducer::Reduce(Node* node) {
     57   switch (node->opcode()) {
     58     case IrOpcode::kBranch:
     59       return ReduceBranch(node);
     60     case IrOpcode::kMerge:
     61       return ReduceMerge(node);
     62     case IrOpcode::kEffectPhi:
     63       return ReduceEffectPhi(node);
     64     case IrOpcode::kPhi:
     65       return ReducePhi(node);
     66     case IrOpcode::kReturn:
     67       return ReduceReturn(node);
     68     case IrOpcode::kSelect:
     69       return ReduceSelect(node);
     70     case IrOpcode::kGuard:
     71       return ReduceGuard(node);
     72     default:
     73       break;
     74   }
     75   return NoChange();
     76 }
     77 
     78 
     79 Reduction CommonOperatorReducer::ReduceBranch(Node* node) {
     80   DCHECK_EQ(IrOpcode::kBranch, node->opcode());
     81   Node* const cond = node->InputAt(0);
     82   // Swap IfTrue/IfFalse on {branch} if {cond} is a BooleanNot and use the input
     83   // to BooleanNot as new condition for {branch}. Note we assume that {cond} was
     84   // already properly optimized before we get here (as guaranteed by the graph
     85   // reduction logic).
     86   if (cond->opcode() == IrOpcode::kBooleanNot) {
     87     for (Node* const use : node->uses()) {
     88       switch (use->opcode()) {
     89         case IrOpcode::kIfTrue:
     90           NodeProperties::ChangeOp(use, common()->IfFalse());
     91           break;
     92         case IrOpcode::kIfFalse:
     93           NodeProperties::ChangeOp(use, common()->IfTrue());
     94           break;
     95         default:
     96           UNREACHABLE();
     97       }
     98     }
     99     // Update the condition of {branch}. No need to mark the uses for revisit,
    100     // since we tell the graph reducer that the {branch} was changed and the
    101     // graph reduction logic will ensure that the uses are revisited properly.
    102     node->ReplaceInput(0, cond->InputAt(0));
    103     // Negate the hint for {branch}.
    104     NodeProperties::ChangeOp(
    105         node, common()->Branch(NegateBranchHint(BranchHintOf(node->op()))));
    106     return Changed(node);
    107   }
    108   Decision const decision = DecideCondition(cond);
    109   if (decision == Decision::kUnknown) return NoChange();
    110   Node* const control = node->InputAt(1);
    111   for (Node* const use : node->uses()) {
    112     switch (use->opcode()) {
    113       case IrOpcode::kIfTrue:
    114         Replace(use, (decision == Decision::kTrue) ? control : dead());
    115         break;
    116       case IrOpcode::kIfFalse:
    117         Replace(use, (decision == Decision::kFalse) ? control : dead());
    118         break;
    119       default:
    120         UNREACHABLE();
    121     }
    122   }
    123   return Replace(dead());
    124 }
    125 
    126 
    127 Reduction CommonOperatorReducer::ReduceMerge(Node* node) {
    128   DCHECK_EQ(IrOpcode::kMerge, node->opcode());
    129   //
    130   // Check if this is a merge that belongs to an unused diamond, which means
    131   // that:
    132   //
    133   //  a) the {Merge} has no {Phi} or {EffectPhi} uses, and
    134   //  b) the {Merge} has two inputs, one {IfTrue} and one {IfFalse}, which are
    135   //     both owned by the Merge, and
    136   //  c) and the {IfTrue} and {IfFalse} nodes point to the same {Branch}.
    137   //
    138   if (node->InputCount() == 2) {
    139     for (Node* const use : node->uses()) {
    140       if (IrOpcode::IsPhiOpcode(use->opcode())) return NoChange();
    141     }
    142     Node* if_true = node->InputAt(0);
    143     Node* if_false = node->InputAt(1);
    144     if (if_true->opcode() != IrOpcode::kIfTrue) std::swap(if_true, if_false);
    145     if (if_true->opcode() == IrOpcode::kIfTrue &&
    146         if_false->opcode() == IrOpcode::kIfFalse &&
    147         if_true->InputAt(0) == if_false->InputAt(0) && if_true->OwnedBy(node) &&
    148         if_false->OwnedBy(node)) {
    149       Node* const branch = if_true->InputAt(0);
    150       DCHECK_EQ(IrOpcode::kBranch, branch->opcode());
    151       DCHECK(branch->OwnedBy(if_true, if_false));
    152       Node* const control = branch->InputAt(1);
    153       // Mark the {branch} as {Dead}.
    154       branch->TrimInputCount(0);
    155       NodeProperties::ChangeOp(branch, common()->Dead());
    156       return Replace(control);
    157     }
    158   }
    159   return NoChange();
    160 }
    161 
    162 
    163 Reduction CommonOperatorReducer::ReduceEffectPhi(Node* node) {
    164   DCHECK_EQ(IrOpcode::kEffectPhi, node->opcode());
    165   int const input_count = node->InputCount() - 1;
    166   DCHECK_LE(1, input_count);
    167   Node* const merge = node->InputAt(input_count);
    168   DCHECK(IrOpcode::IsMergeOpcode(merge->opcode()));
    169   DCHECK_EQ(input_count, merge->InputCount());
    170   Node* const effect = node->InputAt(0);
    171   DCHECK_NE(node, effect);
    172   for (int i = 1; i < input_count; ++i) {
    173     Node* const input = node->InputAt(i);
    174     if (input == node) {
    175       // Ignore redundant inputs.
    176       DCHECK_EQ(IrOpcode::kLoop, merge->opcode());
    177       continue;
    178     }
    179     if (input != effect) return NoChange();
    180   }
    181   // We might now be able to further reduce the {merge} node.
    182   Revisit(merge);
    183   return Replace(effect);
    184 }
    185 
    186 
    187 Reduction CommonOperatorReducer::ReducePhi(Node* node) {
    188   DCHECK_EQ(IrOpcode::kPhi, node->opcode());
    189   int const input_count = node->InputCount() - 1;
    190   DCHECK_LE(1, input_count);
    191   Node* const merge = node->InputAt(input_count);
    192   DCHECK(IrOpcode::IsMergeOpcode(merge->opcode()));
    193   DCHECK_EQ(input_count, merge->InputCount());
    194   if (input_count == 2) {
    195     Node* vtrue = node->InputAt(0);
    196     Node* vfalse = node->InputAt(1);
    197     Node* if_true = merge->InputAt(0);
    198     Node* if_false = merge->InputAt(1);
    199     if (if_true->opcode() != IrOpcode::kIfTrue) {
    200       std::swap(if_true, if_false);
    201       std::swap(vtrue, vfalse);
    202     }
    203     if (if_true->opcode() == IrOpcode::kIfTrue &&
    204         if_false->opcode() == IrOpcode::kIfFalse &&
    205         if_true->InputAt(0) == if_false->InputAt(0)) {
    206       Node* const branch = if_true->InputAt(0);
    207       // Check that the branch is not dead already.
    208       if (branch->opcode() != IrOpcode::kBranch) return NoChange();
    209       Node* const cond = branch->InputAt(0);
    210       if (cond->opcode() == IrOpcode::kFloat32LessThan) {
    211         Float32BinopMatcher mcond(cond);
    212         if (mcond.left().Is(0.0) && mcond.right().Equals(vtrue) &&
    213             vfalse->opcode() == IrOpcode::kFloat32Sub) {
    214           Float32BinopMatcher mvfalse(vfalse);
    215           if (mvfalse.left().IsZero() && mvfalse.right().Equals(vtrue)) {
    216             // We might now be able to further reduce the {merge} node.
    217             Revisit(merge);
    218             return Change(node, machine()->Float32Abs(), vtrue);
    219           }
    220         }
    221         if (mcond.left().Equals(vtrue) && mcond.right().Equals(vfalse) &&
    222             machine()->Float32Min().IsSupported()) {
    223           // We might now be able to further reduce the {merge} node.
    224           Revisit(merge);
    225           return Change(node, machine()->Float32Min().op(), vtrue, vfalse);
    226         } else if (mcond.left().Equals(vfalse) && mcond.right().Equals(vtrue) &&
    227                    machine()->Float32Max().IsSupported()) {
    228           // We might now be able to further reduce the {merge} node.
    229           Revisit(merge);
    230           return Change(node, machine()->Float32Max().op(), vtrue, vfalse);
    231         }
    232       } else if (cond->opcode() == IrOpcode::kFloat64LessThan) {
    233         Float64BinopMatcher mcond(cond);
    234         if (mcond.left().Is(0.0) && mcond.right().Equals(vtrue) &&
    235             vfalse->opcode() == IrOpcode::kFloat64Sub) {
    236           Float64BinopMatcher mvfalse(vfalse);
    237           if (mvfalse.left().IsZero() && mvfalse.right().Equals(vtrue)) {
    238             // We might now be able to further reduce the {merge} node.
    239             Revisit(merge);
    240             return Change(node, machine()->Float64Abs(), vtrue);
    241           }
    242         }
    243         if (mcond.left().Equals(vtrue) && mcond.right().Equals(vfalse) &&
    244             machine()->Float64Min().IsSupported()) {
    245           // We might now be able to further reduce the {merge} node.
    246           Revisit(merge);
    247           return Change(node, machine()->Float64Min().op(), vtrue, vfalse);
    248         } else if (mcond.left().Equals(vfalse) && mcond.right().Equals(vtrue) &&
    249                    machine()->Float64Max().IsSupported()) {
    250           // We might now be able to further reduce the {merge} node.
    251           Revisit(merge);
    252           return Change(node, machine()->Float64Max().op(), vtrue, vfalse);
    253         }
    254       }
    255     }
    256   }
    257   Node* const value = node->InputAt(0);
    258   DCHECK_NE(node, value);
    259   for (int i = 1; i < input_count; ++i) {
    260     Node* const input = node->InputAt(i);
    261     if (input == node) {
    262       // Ignore redundant inputs.
    263       DCHECK_EQ(IrOpcode::kLoop, merge->opcode());
    264       continue;
    265     }
    266     if (input != value) return NoChange();
    267   }
    268   // We might now be able to further reduce the {merge} node.
    269   Revisit(merge);
    270   return Replace(value);
    271 }
    272 
    273 
    274 Reduction CommonOperatorReducer::ReduceReturn(Node* node) {
    275   DCHECK_EQ(IrOpcode::kReturn, node->opcode());
    276   Node* const value = node->InputAt(0);
    277   Node* const effect = node->InputAt(1);
    278   Node* const control = node->InputAt(2);
    279   if (value->opcode() == IrOpcode::kPhi &&
    280       NodeProperties::GetControlInput(value) == control &&
    281       effect->opcode() == IrOpcode::kEffectPhi &&
    282       NodeProperties::GetControlInput(effect) == control &&
    283       control->opcode() == IrOpcode::kMerge) {
    284     int const control_input_count = control->InputCount();
    285     DCHECK_NE(0, control_input_count);
    286     DCHECK_EQ(control_input_count, value->InputCount() - 1);
    287     DCHECK_EQ(control_input_count, effect->InputCount() - 1);
    288     DCHECK_EQ(IrOpcode::kEnd, graph()->end()->opcode());
    289     DCHECK_NE(0, graph()->end()->InputCount());
    290     for (int i = 0; i < control_input_count; ++i) {
    291       // Create a new {Return} and connect it to {end}. We don't need to mark
    292       // {end} as revisit, because we mark {node} as {Dead} below, which was
    293       // previously connected to {end}, so we know for sure that at some point
    294       // the reducer logic will visit {end} again.
    295       Node* ret = graph()->NewNode(common()->Return(), value->InputAt(i),
    296                                    effect->InputAt(i), control->InputAt(i));
    297       NodeProperties::MergeControlToEnd(graph(), common(), ret);
    298     }
    299     // Mark the merge {control} and return {node} as {dead}.
    300     Replace(control, dead());
    301     return Replace(dead());
    302   }
    303   return NoChange();
    304 }
    305 
    306 
    307 Reduction CommonOperatorReducer::ReduceSelect(Node* node) {
    308   DCHECK_EQ(IrOpcode::kSelect, node->opcode());
    309   Node* const cond = node->InputAt(0);
    310   Node* const vtrue = node->InputAt(1);
    311   Node* const vfalse = node->InputAt(2);
    312   if (vtrue == vfalse) return Replace(vtrue);
    313   switch (DecideCondition(cond)) {
    314     case Decision::kTrue:
    315       return Replace(vtrue);
    316     case Decision::kFalse:
    317       return Replace(vfalse);
    318     case Decision::kUnknown:
    319       break;
    320   }
    321   switch (cond->opcode()) {
    322     case IrOpcode::kFloat32LessThan: {
    323       Float32BinopMatcher mcond(cond);
    324       if (mcond.left().Is(0.0) && mcond.right().Equals(vtrue) &&
    325           vfalse->opcode() == IrOpcode::kFloat32Sub) {
    326         Float32BinopMatcher mvfalse(vfalse);
    327         if (mvfalse.left().IsZero() && mvfalse.right().Equals(vtrue)) {
    328           return Change(node, machine()->Float32Abs(), vtrue);
    329         }
    330       }
    331       if (mcond.left().Equals(vtrue) && mcond.right().Equals(vfalse) &&
    332           machine()->Float32Min().IsSupported()) {
    333         return Change(node, machine()->Float32Min().op(), vtrue, vfalse);
    334       } else if (mcond.left().Equals(vfalse) && mcond.right().Equals(vtrue) &&
    335                  machine()->Float32Max().IsSupported()) {
    336         return Change(node, machine()->Float32Max().op(), vtrue, vfalse);
    337       }
    338       break;
    339     }
    340     case IrOpcode::kFloat64LessThan: {
    341       Float64BinopMatcher mcond(cond);
    342       if (mcond.left().Is(0.0) && mcond.right().Equals(vtrue) &&
    343           vfalse->opcode() == IrOpcode::kFloat64Sub) {
    344         Float64BinopMatcher mvfalse(vfalse);
    345         if (mvfalse.left().IsZero() && mvfalse.right().Equals(vtrue)) {
    346           return Change(node, machine()->Float64Abs(), vtrue);
    347         }
    348       }
    349       if (mcond.left().Equals(vtrue) && mcond.right().Equals(vfalse) &&
    350           machine()->Float64Min().IsSupported()) {
    351         return Change(node, machine()->Float64Min().op(), vtrue, vfalse);
    352       } else if (mcond.left().Equals(vfalse) && mcond.right().Equals(vtrue) &&
    353                  machine()->Float64Max().IsSupported()) {
    354         return Change(node, machine()->Float64Max().op(), vtrue, vfalse);
    355       }
    356       break;
    357     }
    358     default:
    359       break;
    360   }
    361   return NoChange();
    362 }
    363 
    364 
    365 Reduction CommonOperatorReducer::ReduceGuard(Node* node) {
    366   DCHECK_EQ(IrOpcode::kGuard, node->opcode());
    367   Node* const input = NodeProperties::GetValueInput(node, 0);
    368   Type* const input_type = NodeProperties::GetTypeOrAny(input);
    369   Type* const guard_type = OpParameter<Type*>(node);
    370   if (input_type->Is(guard_type)) return Replace(input);
    371   return NoChange();
    372 }
    373 
    374 
    375 Reduction CommonOperatorReducer::Change(Node* node, Operator const* op,
    376                                         Node* a) {
    377   node->ReplaceInput(0, a);
    378   node->TrimInputCount(1);
    379   NodeProperties::ChangeOp(node, op);
    380   return Changed(node);
    381 }
    382 
    383 
    384 Reduction CommonOperatorReducer::Change(Node* node, Operator const* op, Node* a,
    385                                         Node* b) {
    386   node->ReplaceInput(0, a);
    387   node->ReplaceInput(1, b);
    388   node->TrimInputCount(2);
    389   NodeProperties::ChangeOp(node, op);
    390   return Changed(node);
    391 }
    392 
    393 }  // namespace compiler
    394 }  // namespace internal
    395 }  // namespace v8
    396