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/control-flow-optimizer.h"
      6 
      7 #include "src/compiler/common-operator.h"
      8 #include "src/compiler/graph.h"
      9 #include "src/compiler/node-matchers.h"
     10 #include "src/compiler/node-properties.h"
     11 
     12 namespace v8 {
     13 namespace internal {
     14 namespace compiler {
     15 
     16 ControlFlowOptimizer::ControlFlowOptimizer(Graph* graph,
     17                                            CommonOperatorBuilder* common,
     18                                            MachineOperatorBuilder* machine,
     19                                            Zone* zone)
     20     : graph_(graph),
     21       common_(common),
     22       machine_(machine),
     23       queue_(zone),
     24       queued_(graph, 2),
     25       zone_(zone) {}
     26 
     27 
     28 void ControlFlowOptimizer::Optimize() {
     29   Enqueue(graph()->start());
     30   while (!queue_.empty()) {
     31     Node* node = queue_.front();
     32     queue_.pop();
     33     if (node->IsDead()) continue;
     34     switch (node->opcode()) {
     35       case IrOpcode::kBranch:
     36         VisitBranch(node);
     37         break;
     38       default:
     39         VisitNode(node);
     40         break;
     41     }
     42   }
     43 }
     44 
     45 
     46 void ControlFlowOptimizer::Enqueue(Node* node) {
     47   DCHECK_NOT_NULL(node);
     48   if (node->IsDead() || queued_.Get(node)) return;
     49   queued_.Set(node, true);
     50   queue_.push(node);
     51 }
     52 
     53 
     54 void ControlFlowOptimizer::VisitNode(Node* node) {
     55   for (Edge edge : node->use_edges()) {
     56     if (NodeProperties::IsControlEdge(edge)) {
     57       Enqueue(edge.from());
     58     }
     59   }
     60 }
     61 
     62 
     63 void ControlFlowOptimizer::VisitBranch(Node* node) {
     64   DCHECK_EQ(IrOpcode::kBranch, node->opcode());
     65   if (TryBuildSwitch(node)) return;
     66   if (TryCloneBranch(node)) return;
     67   VisitNode(node);
     68 }
     69 
     70 
     71 bool ControlFlowOptimizer::TryCloneBranch(Node* node) {
     72   DCHECK_EQ(IrOpcode::kBranch, node->opcode());
     73 
     74   // This optimization is a special case of (super)block cloning. It takes an
     75   // input graph as shown below and clones the Branch node for every predecessor
     76   // to the Merge, essentially removing the Merge completely. This avoids
     77   // materializing the bit for the Phi and may offer potential for further
     78   // branch folding optimizations (i.e. because one or more inputs to the Phi is
     79   // a constant). Note that there may be more Phi nodes hanging off the Merge,
     80   // but we can only a certain subset of them currently (actually only Phi and
     81   // EffectPhi nodes whose uses have either the IfTrue or IfFalse as control
     82   // input).
     83 
     84   //   Control1 ... ControlN
     85   //      ^            ^
     86   //      |            |   Cond1 ... CondN
     87   //      +----+  +----+     ^         ^
     88   //           |  |          |         |
     89   //           |  |     +----+         |
     90   //          Merge<--+ | +------------+
     91   //            ^      \|/
     92   //            |      Phi
     93   //            |       |
     94   //          Branch----+
     95   //            ^
     96   //            |
     97   //      +-----+-----+
     98   //      |           |
     99   //    IfTrue     IfFalse
    100   //      ^           ^
    101   //      |           |
    102 
    103   // The resulting graph (modulo the Phi and EffectPhi nodes) looks like this:
    104 
    105   // Control1 Cond1 ... ControlN CondN
    106   //    ^      ^           ^      ^
    107   //    \      /           \      /
    108   //     Branch     ...     Branch
    109   //       ^                  ^
    110   //       |                  |
    111   //   +---+---+          +---+----+
    112   //   |       |          |        |
    113   // IfTrue IfFalse ... IfTrue  IfFalse
    114   //   ^       ^          ^        ^
    115   //   |       |          |        |
    116   //   +--+ +-------------+        |
    117   //      | |  +--------------+ +--+
    118   //      | |                 | |
    119   //     Merge               Merge
    120   //       ^                   ^
    121   //       |                   |
    122 
    123   Node* branch = node;
    124   Node* cond = NodeProperties::GetValueInput(branch, 0);
    125   if (!cond->OwnedBy(branch) || cond->opcode() != IrOpcode::kPhi) return false;
    126   Node* merge = NodeProperties::GetControlInput(branch);
    127   if (merge->opcode() != IrOpcode::kMerge ||
    128       NodeProperties::GetControlInput(cond) != merge) {
    129     return false;
    130   }
    131   // Grab the IfTrue/IfFalse projections of the Branch.
    132   BranchMatcher matcher(branch);
    133   // Check/collect other Phi/EffectPhi nodes hanging off the Merge.
    134   NodeVector phis(zone());
    135   for (Node* const use : merge->uses()) {
    136     if (use == branch || use == cond) continue;
    137     // We cannot currently deal with non-Phi/EffectPhi nodes hanging off the
    138     // Merge. Ideally, we would just clone the nodes (and everything that
    139     // depends on it to some distant join point), but that requires knowledge
    140     // about dominance/post-dominance.
    141     if (!NodeProperties::IsPhi(use)) return false;
    142     for (Edge edge : use->use_edges()) {
    143       // Right now we can only handle Phi/EffectPhi nodes whose uses are
    144       // directly control-dependend on either the IfTrue or the IfFalse
    145       // successor, because we know exactly how to update those uses.
    146       // TODO(turbofan): Generalize this to all Phi/EffectPhi nodes using
    147       // dominance/post-dominance on the sea of nodes.
    148       if (edge.from()->op()->ControlInputCount() != 1) return false;
    149       Node* control = NodeProperties::GetControlInput(edge.from());
    150       if (NodeProperties::IsPhi(edge.from())) {
    151         control = NodeProperties::GetControlInput(control, edge.index());
    152       }
    153       if (control != matcher.IfTrue() && control != matcher.IfFalse())
    154         return false;
    155     }
    156     phis.push_back(use);
    157   }
    158   BranchHint const hint = BranchHintOf(branch->op());
    159   int const input_count = merge->op()->ControlInputCount();
    160   DCHECK_LE(1, input_count);
    161   Node** const inputs = zone()->NewArray<Node*>(2 * input_count);
    162   Node** const merge_true_inputs = &inputs[0];
    163   Node** const merge_false_inputs = &inputs[input_count];
    164   for (int index = 0; index < input_count; ++index) {
    165     Node* cond1 = NodeProperties::GetValueInput(cond, index);
    166     Node* control1 = NodeProperties::GetControlInput(merge, index);
    167     Node* branch1 = graph()->NewNode(common()->Branch(hint), cond1, control1);
    168     merge_true_inputs[index] = graph()->NewNode(common()->IfTrue(), branch1);
    169     merge_false_inputs[index] = graph()->NewNode(common()->IfFalse(), branch1);
    170     Enqueue(branch1);
    171   }
    172   Node* const merge_true = graph()->NewNode(common()->Merge(input_count),
    173                                             input_count, merge_true_inputs);
    174   Node* const merge_false = graph()->NewNode(common()->Merge(input_count),
    175                                              input_count, merge_false_inputs);
    176   for (Node* const phi : phis) {
    177     for (int index = 0; index < input_count; ++index) {
    178       inputs[index] = phi->InputAt(index);
    179     }
    180     inputs[input_count] = merge_true;
    181     Node* phi_true = graph()->NewNode(phi->op(), input_count + 1, inputs);
    182     inputs[input_count] = merge_false;
    183     Node* phi_false = graph()->NewNode(phi->op(), input_count + 1, inputs);
    184     for (Edge edge : phi->use_edges()) {
    185       Node* control = NodeProperties::GetControlInput(edge.from());
    186       if (NodeProperties::IsPhi(edge.from())) {
    187         control = NodeProperties::GetControlInput(control, edge.index());
    188       }
    189       DCHECK(control == matcher.IfTrue() || control == matcher.IfFalse());
    190       edge.UpdateTo((control == matcher.IfTrue()) ? phi_true : phi_false);
    191     }
    192     phi->Kill();
    193   }
    194   // Fix up IfTrue and IfFalse and kill all dead nodes.
    195   matcher.IfFalse()->ReplaceUses(merge_false);
    196   matcher.IfTrue()->ReplaceUses(merge_true);
    197   matcher.IfFalse()->Kill();
    198   matcher.IfTrue()->Kill();
    199   branch->Kill();
    200   cond->Kill();
    201   merge->Kill();
    202   return true;
    203 }
    204 
    205 
    206 bool ControlFlowOptimizer::TryBuildSwitch(Node* node) {
    207   DCHECK_EQ(IrOpcode::kBranch, node->opcode());
    208 
    209   Node* branch = node;
    210   if (BranchHintOf(branch->op()) != BranchHint::kNone) return false;
    211   Node* cond = NodeProperties::GetValueInput(branch, 0);
    212   if (cond->opcode() != IrOpcode::kWord32Equal) return false;
    213   Int32BinopMatcher m(cond);
    214   Node* index = m.left().node();
    215   if (!m.right().HasValue()) return false;
    216   int32_t value = m.right().Value();
    217   ZoneSet<int32_t> values(zone());
    218   values.insert(value);
    219 
    220   Node* if_false;
    221   Node* if_true;
    222   while (true) {
    223     BranchMatcher matcher(branch);
    224     DCHECK(matcher.Matched());
    225 
    226     if_true = matcher.IfTrue();
    227     if_false = matcher.IfFalse();
    228 
    229     auto it = if_false->uses().begin();
    230     if (it == if_false->uses().end()) break;
    231     Node* branch1 = *it++;
    232     if (branch1->opcode() != IrOpcode::kBranch) break;
    233     if (BranchHintOf(branch1->op()) != BranchHint::kNone) break;
    234     if (it != if_false->uses().end()) break;
    235     Node* cond1 = branch1->InputAt(0);
    236     if (cond1->opcode() != IrOpcode::kWord32Equal) break;
    237     Int32BinopMatcher m1(cond1);
    238     if (m1.left().node() != index) break;
    239     if (!m1.right().HasValue()) break;
    240     int32_t value1 = m1.right().Value();
    241     if (values.find(value1) != values.end()) break;
    242     DCHECK_NE(value, value1);
    243 
    244     if (branch != node) {
    245       branch->NullAllInputs();
    246       if_true->ReplaceInput(0, node);
    247     }
    248     NodeProperties::ChangeOp(if_true, common()->IfValue(value));
    249     if_false->NullAllInputs();
    250     Enqueue(if_true);
    251 
    252     branch = branch1;
    253     value = value1;
    254     values.insert(value);
    255   }
    256 
    257   DCHECK_EQ(IrOpcode::kBranch, node->opcode());
    258   DCHECK_EQ(IrOpcode::kBranch, branch->opcode());
    259   if (branch == node) {
    260     DCHECK_EQ(1u, values.size());
    261     return false;
    262   }
    263   DCHECK_LT(1u, values.size());
    264   node->ReplaceInput(0, index);
    265   NodeProperties::ChangeOp(node, common()->Switch(values.size() + 1));
    266   if_true->ReplaceInput(0, node);
    267   NodeProperties::ChangeOp(if_true, common()->IfValue(value));
    268   Enqueue(if_true);
    269   if_false->ReplaceInput(0, node);
    270   NodeProperties::ChangeOp(if_false, common()->IfDefault());
    271   Enqueue(if_false);
    272   branch->NullAllInputs();
    273   return true;
    274 }
    275 
    276 }  // namespace compiler
    277 }  // namespace internal
    278 }  // namespace v8
    279