[turbofan] Move TryCloneBranch in the EffectControlLinearizer pass.

src/compiler/effect-control-linearizer.cc

 // Copyright 2015 the V8 project authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #include "src/compiler/effect-control-linearizer.h"
 
 #include "src/code-factory.h"
 #include "src/compiler/access-builder.h"
 #include "src/compiler/js-graph.h"
 #include "src/compiler/linkage.h"
+#include "src/compiler/node-matchers.h"
 #include "src/compiler/node-properties.h"
 #include "src/compiler/node.h"
 #include "src/compiler/schedule.h"
 
 namespace v8 {
 namespace internal {
 namespace compiler {
 
 EffectControlLinearizer::EffectControlLinearizer(JSGraph* js_graph,
                                                  Schedule* schedule,
                                                  Zone* temp_zone)
     : js_graph_(js_graph), schedule_(schedule), temp_zone_(temp_zone) {}
 
 Graph* EffectControlLinearizer::graph() const { return js_graph_->graph(); }
 CommonOperatorBuilder* EffectControlLinearizer::common() const {
   return js_graph_->common();
 }
 SimplifiedOperatorBuilder* EffectControlLinearizer::simplified() const {
   return js_graph_->simplified();
 }
 MachineOperatorBuilder* EffectControlLinearizer::machine() const {
   return js_graph_->machine();
 }
 
 namespace {
 
 struct BlockEffectControlData {
-  Node* current_effect = nullptr;  // New effect.
-  Node* current_control = nullptr;  // New control.
+  Node* current_effect = nullptr;       // New effect.
+  Node* current_control = nullptr;      // New control.
   Node* current_frame_state = nullptr;  // New frame state.
 };
 
+struct BlockDataKey {
+  BasicBlock* from;

[Benedikt Meurer, 2016/07/12 03:16:14]

How about using the rpo numbers as keys instead of the pointers? That would make
the comparator below easier. 

[epertoso, 2016/07/12 10:14:44]

Done.

+  BasicBlock* to;
+
+  BlockDataKey(BasicBlock* from, BasicBlock* to) : from(from), to(to) {}
+};
+
+struct BlockDataKeyComparator {
+  bool operator()(const BlockDataKey& lhs, const BlockDataKey& rhs) const {
+    return lhs.from == rhs.from ? lhs.to < rhs.to : lhs.from < rhs.from;
+  }
+};
+
+using BlockEffectControlMap =
+    ZoneMap<BlockDataKey, BlockEffectControlData, BlockDataKeyComparator>;
+
 // Effect phis that need to be updated after the first pass.
 struct PendingEffectPhi {
   Node* effect_phi;
   BasicBlock* block;
 
   PendingEffectPhi(Node* effect_phi, BasicBlock* block)
       : effect_phi(effect_phi), block(block) {}
 };
 
 void UpdateEffectPhi(Node* node, BasicBlock* block,
-                     ZoneVector<BlockEffectControlData>* block_effects) {
+                     BlockEffectControlMap* block_effects) {
   // Update all inputs to an effect phi with the effects from the given
   // block->effect map.
   DCHECK_EQ(IrOpcode::kEffectPhi, node->opcode());
   DCHECK_EQ(node->op()->EffectInputCount(), block->PredecessorCount());
   for (int i = 0; i < node->op()->EffectInputCount(); i++) {
     Node* input = node->InputAt(i);
     BasicBlock* predecessor = block->PredecessorAt(static_cast<size_t>(i));
-    Node* input_effect =
-        (*block_effects)[predecessor->rpo_number()].current_effect;
+    BlockEffectControlMap::iterator it =
+        block_effects->find({predecessor, block});

[Benedikt Meurer, 2016/07/12 03:16:14]

This kind of uniform initialization is not supported by Chromium C++ Status
AFAIK.
Maybe you can encapsulate the lookup in some helper method on the Map class.

[epertoso, 2016/07/12 10:14:44]

Explicitly using the constructor now.

+    Node* input_effect = it->second.current_effect;
     if (input != input_effect) {
       node->ReplaceInput(i, input_effect);
     }
   }
 }
 
 void UpdateBlockControl(BasicBlock* block,
-                        ZoneVector<BlockEffectControlData>* block_effects) {
+                        BlockEffectControlMap* block_effects) {
   Node* control = block->NodeAt(0);
   DCHECK(NodeProperties::IsControl(control));
 
   // Do not rewire the end node.
   if (control->opcode() == IrOpcode::kEnd) return;
 
   // Update all inputs to the given control node with the correct control.
-  DCHECK_EQ(control->op()->ControlInputCount(), block->PredecessorCount());
+  DCHECK(control->opcode() == IrOpcode::kMerge ||
+         control->op()->ControlInputCount() == block->PredecessorCount());
+  if (control->op()->ControlInputCount() != block->PredecessorCount())
+    return;  // We already wired stuff.

[Benedikt Meurer, 2016/07/12 03:16:15]

Nit: Add { } around the return

[epertoso, 2016/07/12 10:14:44]

Done.

   for (int i = 0; i < control->op()->ControlInputCount(); i++) {
     Node* input = NodeProperties::GetControlInput(control, i);
     BasicBlock* predecessor = block->PredecessorAt(static_cast<size_t>(i));
-    Node* input_control =
-        (*block_effects)[predecessor->rpo_number()].current_control;
+    BlockEffectControlMap::iterator it =
+        block_effects->find({predecessor, block});
+    Node* input_control = it->second.current_control;
     if (input != input_control) {
       NodeProperties::ReplaceControlInput(control, input_control, i);
     }
   }
 }
 
 bool HasIncomingBackEdges(BasicBlock* block) {
   for (BasicBlock* pred : block->predecessors()) {
     if (pred->rpo_number() >= block->rpo_number()) {
       return true;
@@ skipping 13 matching lines @@
       edge.UpdateTo(NodeProperties::GetEffectInput(node));
     } else {
       DCHECK(!NodeProperties::IsControlEdge(edge));
       DCHECK(!NodeProperties::IsFrameStateEdge(edge));
       edge.UpdateTo(node->InputAt(0));
     }
   }
   node->Kill();
 }
 
+void TryCloneBranch(Node* node, BasicBlock* block, Graph* graph,
+                    CommonOperatorBuilder* common,
+                    BlockEffectControlMap* block_effects) {
+  DCHECK_EQ(IrOpcode::kBranch, node->opcode());
+
+  // This optimization is a special case of (super)block cloning. It takes an
+  // input graph as shown below and clones the Branch node for every predecessor
+  // to the Merge, essentially removing the Merge completely. This avoids
+  // materializing the bit for the Phi and may offer potential for further
+  // branch folding optimizations (i.e. because one or more inputs to the Phi is
+  // a constant). Note that there may be more Phi nodes hanging off the Merge,
+  // but we can only a certain subset of them currently (actually only Phi and
+  // EffectPhi nodes whose uses have either the IfTrue or IfFalse as control
+  // input).
+
+  //   Control1 ... ControlN
+  //      ^            ^
+  //      |            |   Cond1 ... CondN
+  //      +----+  +----+     ^         ^
+  //           |  |          |         |
+  //           |  |     +----+         |
+  //          Merge<--+ | +------------+
+  //            ^      \|/
+  //            |      Phi
+  //            |       |
+  //          Branch----+
+  //            ^
+  //            |
+  //      +-----+-----+
+  //      |           |
+  //    IfTrue     IfFalse
+  //      ^           ^
+  //      |           |
+
+  // The resulting graph (modulo the Phi and EffectPhi nodes) looks like this:
+
+  // Control1 Cond1 ... ControlN CondN
+  //    ^      ^           ^      ^
+  //    \      /           \      /
+  //     Branch     ...     Branch
+  //       ^                  ^
+  //       |                  |
+  //   +---+---+          +---+----+
+  //   |       |          |        |
+  // IfTrue IfFalse ... IfTrue  IfFalse
+  //   ^       ^          ^        ^
+  //   |       |          |        |
+  //   +--+ +-------------+        |
+  //      | |  +--------------+ +--+
+  //      | |                 | |
+  //     Merge               Merge
+  //       ^                   ^
+  //       |                   |
+
+  Node* branch = node;
+  Node* cond = NodeProperties::GetValueInput(branch, 0);
+  if (!cond->OwnedBy(branch) || cond->opcode() != IrOpcode::kPhi) return;
+  Node* merge = NodeProperties::GetControlInput(branch);
+  if (merge->opcode() != IrOpcode::kMerge ||
+      NodeProperties::GetControlInput(cond) != merge) {
+    return;
+  }
+  // Grab the IfTrue/IfFalse projections of the Branch.
+  BranchMatcher matcher(branch);
+  // Check/collect other Phi/EffectPhi nodes hanging off the Merge.
+  NodeVector phis(graph->zone());
+  for (Node* const use : merge->uses()) {
+    if (use == branch || use == cond) continue;
+    // We cannot currently deal with non-Phi/EffectPhi nodes hanging off the
+    // Merge. Ideally, we would just clone the nodes (and everything that
+    // depends on it to some distant join point), but that requires knowledge
+    // about dominance/post-dominance.
+    if (!NodeProperties::IsPhi(use)) return;
+    for (Edge edge : use->use_edges()) {
+      // Right now we can only handle Phi/EffectPhi nodes whose uses are
+      // directly control-dependend on either the IfTrue or the IfFalse
+      // successor, because we know exactly how to update those uses.
+      if (edge.from()->op()->ControlInputCount() != 1) return;
+      Node* control = NodeProperties::GetControlInput(edge.from());
+      if (NodeProperties::IsPhi(edge.from())) {
+        control = NodeProperties::GetControlInput(control, edge.index());
+      }
+      if (control != matcher.IfTrue() && control != matcher.IfFalse()) return;
+    }
+    phis.push_back(use);
+  }
+  BranchHint const hint = BranchHintOf(branch->op());
+  int const input_count = merge->op()->ControlInputCount();
+  DCHECK_LE(1, input_count);
+  Node** const inputs = graph->zone()->NewArray<Node*>(2 * input_count);
+  Node** const merge_true_inputs = &inputs[0];
+  Node** const merge_false_inputs = &inputs[input_count];
+  for (int index = 0; index < input_count; ++index) {
+    Node* cond1 = NodeProperties::GetValueInput(cond, index);
+    Node* control1 = NodeProperties::GetControlInput(merge, index);
+    Node* branch1 = graph->NewNode(common->Branch(hint), cond1, control1);
+    merge_true_inputs[index] = graph->NewNode(common->IfTrue(), branch1);
+    merge_false_inputs[index] = graph->NewNode(common->IfFalse(), branch1);
+  }
+  Node* const merge_true = matcher.IfTrue();
+  Node* const merge_false = matcher.IfFalse();
+  merge_true->TrimInputCount(0);
+  merge_false->TrimInputCount(0);
+  for (int i = 0; i < input_count; ++i) {
+    merge_true->AppendInput(graph->zone(), merge_true_inputs[i]);
+    merge_false->AppendInput(graph->zone(), merge_false_inputs[i]);
+  }
+  DCHECK_EQ(2, block->SuccessorCount());
+  NodeProperties::ChangeOp(matcher.IfTrue(), common->Merge(input_count));
+  NodeProperties::ChangeOp(matcher.IfFalse(), common->Merge(input_count));
+  int const true_index =
+      block->SuccessorAt(0)->NodeAt(0) == matcher.IfTrue() ? 0 : 1;
+  BlockEffectControlData* true_block_data =
+      &(*block_effects)[{block, block->SuccessorAt(true_index)}];
+  BlockEffectControlData* false_block_data =
+      &(*block_effects)[{block, block->SuccessorAt(true_index ^ 1)}];
+  for (Node* const phi : phis) {
+    for (int index = 0; index < input_count; ++index) {
+      inputs[index] = phi->InputAt(index);
+    }
+    inputs[input_count] = merge_true;
+    Node* phi_true = graph->NewNode(phi->op(), input_count + 1, inputs);
+    inputs[input_count] = merge_false;
+    Node* phi_false = graph->NewNode(phi->op(), input_count + 1, inputs);
+    if (phi->UseCount() == 0) {
+      DCHECK_EQ(phi->opcode(), IrOpcode::kEffectPhi);
+      DCHECK_EQ(input_count, block->SuccessorCount());
+    } else {
+      for (Edge edge : phi->use_edges()) {
+        Node* control = NodeProperties::GetControlInput(edge.from());
+        if (NodeProperties::IsPhi(edge.from())) {
+          control = NodeProperties::GetControlInput(control, edge.index());
+        }
+        DCHECK(control == matcher.IfTrue() || control == matcher.IfFalse());
+        edge.UpdateTo((control == matcher.IfTrue()) ? phi_true : phi_false);
+      }
+    }
+    true_block_data->current_effect = phi_true;
+    false_block_data->current_effect = phi_false;
+    phi->Kill();
+  }
+  // Fix up IfTrue and IfFalse and kill all dead nodes.
+  if (branch == block->control_input()) {
+    true_block_data->current_control = merge_true;
+    false_block_data->current_control = merge_false;
+  }
+  branch->Kill();
+  cond->Kill();
+  merge->Kill();
+}
 }  // namespace
 
 void EffectControlLinearizer::Run() {
-  ZoneVector<BlockEffectControlData> block_effects(temp_zone());
+  BlockEffectControlMap block_effects(temp_zone());
   ZoneVector<PendingEffectPhi> pending_effect_phis(temp_zone());
   ZoneVector<BasicBlock*> pending_block_controls(temp_zone());
-  block_effects.resize(schedule()->RpoBlockCount());
   NodeVector inputs_buffer(temp_zone());
 
   for (BasicBlock* block : *(schedule()->rpo_order())) {
+    for (BasicBlock* successor : block->successors()) {
+      block_effects[{block, successor}] = BlockEffectControlData();
+    }
     size_t instr = 0;
 
     // The control node should be the first.
     Node* control = block->NodeAt(instr);
     DCHECK(NodeProperties::IsControl(control));
     // Update the control inputs.
     if (HasIncomingBackEdges(block)) {
       // If there are back edges, we need to update later because we have not
       // computed the control yet. This should only happen for loops.
       DCHECK_EQ(IrOpcode::kLoop, control->opcode());
@@ skipping 42 matching lines @@
       if (block == schedule()->start()) {
         // Start block => effect is start.
         DCHECK_EQ(graph()->start(), control);
         effect = graph()->start();
       } else if (control->opcode() == IrOpcode::kEnd) {
         // End block is just a dummy, no effect needed.
         DCHECK_EQ(BasicBlock::kNone, block->control());
         DCHECK_EQ(1u, block->size());
         effect = nullptr;
       } else {
-        // If all the predecessors have the same effect, we can use it
-        // as our current effect.
-        int rpo_number = block->PredecessorAt(0)->rpo_number();
-        effect = block_effects[rpo_number].current_effect;
-        for (size_t i = 1; i < block->PredecessorCount(); i++) {
-          int rpo_number = block->PredecessorAt(i)->rpo_number();
-          if (block_effects[rpo_number].current_effect != effect) {
+        // If all the predecessors have the same effect, we can use it as our
+        // current effect.
+        effect = block_effects[{block->PredecessorAt(0), block}].current_effect;
+        for (size_t i = 1; i < block->PredecessorCount(); ++i) {
+          if (block_effects[{block->PredecessorAt(i), block}].current_effect !=
+              effect) {
             effect = nullptr;
             break;
           }
         }
         if (effect == nullptr) {
           DCHECK_NE(IrOpcode::kIfException, control->opcode());
           // The input blocks do not have the same effect. We have
           // to create an effect phi node.
           inputs_buffer.clear();
           inputs_buffer.resize(block->PredecessorCount(), graph()->start());
@@ skipping 19 matching lines @@
 
     // The frame state at block entry is determined by the frame states leaving
     // all predecessors. In case there is no frame state dominating this block,
     // we can rely on a checkpoint being present before the next deoptimization.
     // TODO(mstarzinger): Eventually we will need to go hunt for a frame state
     // once deoptimizing nodes roam freely through the schedule.
     Node* frame_state = nullptr;
     if (block != schedule()->start()) {
       // If all the predecessors have the same effect, we can use it
       // as our current effect.
-      int rpo_number = block->PredecessorAt(0)->rpo_number();
-      frame_state = block_effects[rpo_number].current_frame_state;
+      frame_state =
+          block_effects[{block->PredecessorAt(0), block}].current_frame_state;
       for (size_t i = 1; i < block->PredecessorCount(); i++) {
-        int rpo_number = block->PredecessorAt(i)->rpo_number();
-        if (block_effects[rpo_number].current_frame_state != frame_state) {
+        if (block_effects[{block->PredecessorAt(i), block}]
+                .current_frame_state != frame_state) {
           frame_state = nullptr;
           break;
         }
       }
     }
 
     // Process the ordinary instructions.
     for (; instr < block->NodeCount(); instr++) {
       Node* node = block->NodeAt(instr);
       ProcessNode(node, &frame_state, &effect, &control);
     }
 
     switch (block->control()) {
       case BasicBlock::kGoto:
       case BasicBlock::kNone:
         break;
 
       case BasicBlock::kCall:
       case BasicBlock::kTailCall:
       case BasicBlock::kBranch:
       case BasicBlock::kSwitch:
       case BasicBlock::kReturn:
       case BasicBlock::kDeoptimize:
-      case BasicBlock::kThrow:
+      case BasicBlock::kThrow: {
         ProcessNode(block->control_input(), &frame_state, &effect, &control);
-        break;
+        if (block->control() == BasicBlock::kBranch) {
+          TryCloneBranch(block->control_input(), block, graph(), common(),
+                         &block_effects);
+        }
+      } break;
     }
 
-    // Store the effect for later use.
-    block_effects[block->rpo_number()].current_effect = effect;
-    block_effects[block->rpo_number()].current_control = control;
-    block_effects[block->rpo_number()].current_frame_state = frame_state;
+    // Store the effect, control and frame state for later use.
+    for (BasicBlock* successor : block->successors()) {
+      BlockEffectControlData& data = block_effects[{block, successor}];
+      if (data.current_effect == nullptr) {
+        data.current_effect = effect;
+      }
+      if (data.current_control == nullptr) {
+        data.current_control = control;
+      }
+      data.current_frame_state = frame_state;
+    }
   }
 
   // Update the incoming edges of the effect phis that could not be processed
   // during the first pass (because they could have incoming back edges).
   for (const PendingEffectPhi& pending_effect_phi : pending_effect_phis) {
     UpdateEffectPhi(pending_effect_phi.effect_phi, pending_effect_phi.block,
                     &block_effects);
   }
   for (BasicBlock* pending_block_control : pending_block_controls) {
     UpdateBlockControl(pending_block_control, &block_effects);
@@ skipping 1586 matching lines @@
         isolate(), graph()->zone(), callable.descriptor(), 0, flags,
         Operator::kNoThrow);
     to_number_operator_.set(common()->Call(desc));
   }
   return to_number_operator_.get();
 }
 
 }  // namespace compiler
 }  // namespace internal
 }  // namespace v8