deps/v8/src/compiler/control-flow-optimizer.cc

   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/js-graph.h"
   8 #include "src/compiler/node-matchers.h"
   9 #include "src/compiler/node-properties.h"
  10
  11 namespace v8 {
  12 namespace internal {
  13 namespace compiler {
  14
  15 ControlFlowOptimizer::ControlFlowOptimizer(JSGraph* jsgraph, Zone* zone)
  16     : jsgraph_(jsgraph),
  17       queue_(zone),
  18       queued_(jsgraph->graph(), 2),
  19       zone_(zone) {}
  20
  21
  22 void ControlFlowOptimizer::Optimize() {
  23   Enqueue(graph()->start());
  24   while (!queue_.empty()) {
  25     Node* node = queue_.front();
  26     queue_.pop();
  27     if (node->IsDead()) continue;
  28     switch (node->opcode()) {
  29       case IrOpcode::kBranch:
  30         VisitBranch(node);
  31         break;
  32       default:
  33         VisitNode(node);
  34         break;
  35     }
  36   }
  37 }
  38
  39
  40 void ControlFlowOptimizer::Enqueue(Node* node) {
  41   DCHECK_NOT_NULL(node);
  42   if (node->IsDead() || queued_.Get(node)) return;
  43   queued_.Set(node, true);
  44   queue_.push(node);
  45 }
  46
  47
  48 void ControlFlowOptimizer::VisitNode(Node* node) {
  49   for (Edge edge : node->use_edges()) {
  50     if (NodeProperties::IsControlEdge(edge)) {
  51       Enqueue(edge.from());
  52     }
  53   }
  54 }
  55
  56
  57 void ControlFlowOptimizer::VisitBranch(Node* node) {
  58   DCHECK_EQ(IrOpcode::kBranch, node->opcode());
  59   if (TryBuildSwitch(node)) return;
  60   if (TryCloneBranch(node)) return;
  61   VisitNode(node);
  62 }
  63
  64
  65 bool ControlFlowOptimizer::TryCloneBranch(Node* node) {
  66   DCHECK_EQ(IrOpcode::kBranch, node->opcode());
  67
  68   // This optimization is a special case of (super)block cloning. It takes an
  69   // input graph as shown below and clones the Branch node for every predecessor
  70   // to the Merge, essentially removing the Merge completely. This avoids
  71   // materializing the bit for the Phi and may offer potential for further
  72   // branch folding optimizations (i.e. because one or more inputs to the Phi is
  73   // a constant). Note that there may be more Phi nodes hanging off the Merge,
  74   // but we can only a certain subset of them currently (actually only Phi and
  75   // EffectPhi nodes whose uses have either the IfTrue or IfFalse as control
  76   // input).
  77
  78   //   Control1 ... ControlN
  79   //      ^            ^
  80   //      |            |   Cond1 ... CondN
  81   //      +----+  +----+     ^         ^
  82   //           |  |          |         |
  83   //           |  |     +----+         |
  84   //          Merge<--+ | +------------+
  85   //            ^      \|/
  86   //            |      Phi
  87   //            |       |
  88   //          Branch----+
  89   //            ^
  90   //            |
  91   //      +-----+-----+
  92   //      |           |
  93   //    IfTrue     IfFalse
  94   //      ^           ^
  95   //      |           |
  96
  97   // The resulting graph (modulo the Phi and EffectPhi nodes) looks like this:
  98
  99   // Control1 Cond1 ... ControlN CondN
 100   //    ^      ^           ^      ^
 101   //    \      /           \      /
 102   //     Branch     ...     Branch
 103   //       ^                  ^
 104   //       |                  |
 105   //   +---+---+          +---+----+
 106   //   |       |          |        |
 107   // IfTrue IfFalse ... IfTrue  IfFalse
 108   //   ^       ^          ^        ^
 109   //   |       |          |        |
 110   //   +--+ +-------------+        |
 111   //      | |  +--------------+ +--+
 112   //      | |                 | |
 113   //     Merge               Merge
 114   //       ^                   ^
 115   //       |                   |
 116
 117   Node* branch = node;
 118   Node* cond = NodeProperties::GetValueInput(branch, 0);
 119   if (!cond->OwnedBy(branch) || cond->opcode() != IrOpcode::kPhi) return false;
 120   Node* merge = NodeProperties::GetControlInput(branch);
 121   if (merge->opcode() != IrOpcode::kMerge ||
 122       NodeProperties::GetControlInput(cond) != merge) {
 123     return false;
 124   }
 125   // Grab the IfTrue/IfFalse projections of the Branch.
 126   Node* control_projections[2];
 127   NodeProperties::CollectControlProjections(branch, control_projections,
 128                                             arraysize(control_projections));
 129   Node* if_true = control_projections[0];
 130   Node* if_false = control_projections[1];
 131   DCHECK_EQ(IrOpcode::kIfTrue, if_true->opcode());
 132   DCHECK_EQ(IrOpcode::kIfFalse, if_false->opcode());
 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 != if_true && control != if_false) return false;
 154     }
 155     phis.push_back(use);
 156   }
 157   BranchHint const hint = BranchHintOf(branch->op());
 158   int const input_count = merge->op()->ControlInputCount();
 159   DCHECK_LE(1, input_count);
 160   Node** const inputs = zone()->NewArray<Node*>(2 * input_count);
 161   Node** const merge_true_inputs = &inputs[0];
 162   Node** const merge_false_inputs = &inputs[input_count];
 163   for (int index = 0; index < input_count; ++index) {
 164     Node* cond1 = NodeProperties::GetValueInput(cond, index);
 165     Node* control1 = NodeProperties::GetControlInput(merge, index);
 166     Node* branch1 = graph()->NewNode(common()->Branch(hint), cond1, control1);
 167     merge_true_inputs[index] = graph()->NewNode(common()->IfTrue(), branch1);
 168     merge_false_inputs[index] = graph()->NewNode(common()->IfFalse(), branch1);
 169     Enqueue(branch1);
 170   }
 171   Node* const merge_true = graph()->NewNode(common()->Merge(input_count),
 172                                             input_count, merge_true_inputs);
 173   Node* const merge_false = graph()->NewNode(common()->Merge(input_count),
 174                                              input_count, merge_false_inputs);
 175   for (Node* const phi : phis) {
 176     for (int index = 0; index < input_count; ++index) {
 177       inputs[index] = phi->InputAt(index);
 178     }
 179     inputs[input_count] = merge_true;
 180     Node* phi_true = graph()->NewNode(phi->op(), input_count + 1, inputs);
 181     inputs[input_count] = merge_false;
 182     Node* phi_false = graph()->NewNode(phi->op(), input_count + 1, inputs);
 183     for (Edge edge : phi->use_edges()) {
 184       Node* control = NodeProperties::GetControlInput(edge.from());
 185       if (NodeProperties::IsPhi(edge.from())) {
 186         control = NodeProperties::GetControlInput(control, edge.index());
 187       }
 188       DCHECK(control == if_true || control == if_false);
 189       edge.UpdateTo((control == if_true) ? phi_true : phi_false);
 190     }
 191     phi->Kill();
 192   }
 193   // Fix up IfTrue and IfFalse and kill all dead nodes.
 194   if_false->ReplaceUses(merge_false);
 195   if_true->ReplaceUses(merge_true);
 196   if_false->Kill();
 197   if_true->Kill();
 198   branch->Kill();
 199   cond->Kill();
 200   merge->Kill();
 201   return true;
 202 }
 203
 204
 205 bool ControlFlowOptimizer::TryBuildSwitch(Node* node) {
 206   DCHECK_EQ(IrOpcode::kBranch, node->opcode());
 207
 208   Node* branch = node;
 209   if (BranchHintOf(branch->op()) != BranchHint::kNone) return false;
 210   Node* cond = NodeProperties::GetValueInput(branch, 0);
 211   if (cond->opcode() != IrOpcode::kWord32Equal) return false;
 212   Int32BinopMatcher m(cond);
 213   Node* index = m.left().node();
 214   if (!m.right().HasValue()) return false;
 215   int32_t value = m.right().Value();
 216   ZoneSet<int32_t> values(zone());
 217   values.insert(value);
 218
 219   Node* if_false;
 220   Node* if_true;
 221   while (true) {
 222     Node* control_projections[2];
 223     NodeProperties::CollectControlProjections(branch, control_projections, 2);
 224     if_true = control_projections[0];
 225     if_false = control_projections[1];
 226     DCHECK_EQ(IrOpcode::kIfTrue, if_true->opcode());
 227     DCHECK_EQ(IrOpcode::kIfFalse, if_false->opcode());
 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     if_true->set_op(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   DCHECK_EQ(IrOpcode::kIfTrue, if_true->opcode());
 260   DCHECK_EQ(IrOpcode::kIfFalse, if_false->opcode());
 261   if (branch == node) {
 262     DCHECK_EQ(1u, values.size());
 263     return false;
 264   }
 265   DCHECK_LT(1u, values.size());
 266   node->set_op(common()->Switch(values.size() + 1));
 267   node->ReplaceInput(0, index);
 268   if_true->set_op(common()->IfValue(value));
 269   if_true->ReplaceInput(0, node);
 270   Enqueue(if_true);
 271   if_false->set_op(common()->IfDefault());
 272   if_false->ReplaceInput(0, node);
 273   Enqueue(if_false);
 274   branch->NullAllInputs();
 275   return true;
 276 }
 277
 278
 279 CommonOperatorBuilder* ControlFlowOptimizer::common() const {
 280   return jsgraph()->common();
 281 }
 282
 283
 284 Graph* ControlFlowOptimizer::graph() const { return jsgraph()->graph(); }
 285
 286
 287 MachineOperatorBuilder* ControlFlowOptimizer::machine() const {
 288   return jsgraph()->machine();
 289 }
 290
 291 }  // namespace compiler
 292 }  // namespace internal
 293 }  // namespace v8