deps/v8/src/compiler/control-reducer.cc

   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.h"
   6 #include "src/compiler/control-reducer.h"
   7 #include "src/compiler/graph.h"
   8 #include "src/compiler/js-graph.h"
   9 #include "src/compiler/node-marker.h"
  10 #include "src/compiler/node-matchers.h"
  11 #include "src/compiler/node-properties.h"
  12 #include "src/zone-containers.h"
  13
  14 namespace v8 {
  15 namespace internal {
  16 namespace compiler {
  17
  18 #define TRACE(...)                                       \
  19   do {                                                   \
  20     if (FLAG_trace_turbo_reduction) PrintF(__VA_ARGS__); \
  21   } while (false)
  22
  23 enum VisitState { kUnvisited = 0, kOnStack = 1, kRevisit = 2, kVisited = 3 };
  24 enum Decision { kFalse, kUnknown, kTrue };
  25
  26 class ReachabilityMarker : public NodeMarker<uint8_t> {
  27  public:
  28   explicit ReachabilityMarker(Graph* graph) : NodeMarker<uint8_t>(graph, 8) {}
  29   bool SetReachableFromEnd(Node* node) {
  30     uint8_t before = Get(node);
  31     Set(node, before | kFromEnd);
  32     return before & kFromEnd;
  33   }
  34   bool IsReachableFromEnd(Node* node) { return Get(node) & kFromEnd; }
  35   bool SetReachableFromStart(Node* node) {
  36     uint8_t before = Get(node);
  37     Set(node, before | kFromStart);
  38     return before & kFromStart;
  39   }
  40   bool IsReachableFromStart(Node* node) { return Get(node) & kFromStart; }
  41   void Push(Node* node) { Set(node, Get(node) | kFwStack); }
  42   void Pop(Node* node) { Set(node, Get(node) & ~kFwStack); }
  43   bool IsOnStack(Node* node) { return Get(node) & kFwStack; }
  44
  45  private:
  46   enum Bit { kFromEnd = 1, kFromStart = 2, kFwStack = 4 };
  47 };
  48
  49
  50 class ControlReducerImpl {
  51  public:
  52   ControlReducerImpl(Zone* zone, JSGraph* jsgraph,
  53                      CommonOperatorBuilder* common)
  54       : zone_(zone),
  55         jsgraph_(jsgraph),
  56         common_(common),
  57         state_(jsgraph->graph()->NodeCount(), kUnvisited, zone_),
  58         stack_(zone_),
  59         revisit_(zone_) {}
  60
  61   Zone* zone_;
  62   JSGraph* jsgraph_;
  63   CommonOperatorBuilder* common_;
  64   ZoneVector<VisitState> state_;
  65   ZoneDeque<Node*> stack_;
  66   ZoneDeque<Node*> revisit_;
  67
  68   void Reduce() {
  69     Push(graph()->end());
  70     do {
  71       // Process the node on the top of the stack, potentially pushing more
  72       // or popping the node off the stack.
  73       ReduceTop();
  74       // If the stack becomes empty, revisit any nodes in the revisit queue.
  75       // If no nodes in the revisit queue, try removing dead loops.
  76       // If no dead loops, then finish.
  77     } while (!stack_.empty() || TryRevisit() || RepairAndRemoveLoops());
  78   }
  79
  80   bool TryRevisit() {
  81     while (!revisit_.empty()) {
  82       Node* n = revisit_.back();
  83       revisit_.pop_back();
  84       if (state_[n->id()] == kRevisit) {  // state can change while in queue.
  85         Push(n);
  86         return true;
  87       }
  88     }
  89     return false;
  90   }
  91
  92   // Repair the graph after the possible creation of non-terminating or dead
  93   // loops. Removing dead loops can produce more opportunities for reduction.
  94   bool RepairAndRemoveLoops() {
  95     // TODO(turbofan): we can skip this if the graph has no loops, but
  96     // we have to be careful about proper loop detection during reduction.
  97
  98     // Gather all nodes backwards-reachable from end (through inputs).
  99     ReachabilityMarker marked(graph());
 100     NodeVector nodes(zone_);
 101     AddNodesReachableFromEnd(marked, nodes);
 102
 103     // Walk forward through control nodes, looking for back edges to nodes
 104     // that are not connected to end. Those are non-terminating loops (NTLs).
 105     Node* start = graph()->start();
 106     marked.Push(start);
 107     marked.SetReachableFromStart(start);
 108
 109     // We use a stack of (Node, Node::UseEdges::iterator) pairs to avoid
 110     // O(n^2) traversal.
 111     typedef std::pair<Node*, Node::UseEdges::iterator> FwIter;
 112     ZoneVector<FwIter> fw_stack(zone_);
 113     fw_stack.push_back(FwIter(start, start->use_edges().begin()));
 114
 115     while (!fw_stack.empty()) {
 116       Node* node = fw_stack.back().first;
 117       TRACE("ControlFw: #%d:%s\n", node->id(), node->op()->mnemonic());
 118       bool pop = true;
 119       while (fw_stack.back().second != node->use_edges().end()) {
 120         Edge edge = *(fw_stack.back().second);
 121         if (NodeProperties::IsControlEdge(edge) &&
 122             edge.from()->op()->ControlOutputCount() > 0) {
 123           // Only walk control edges to control nodes.
 124           Node* succ = edge.from();
 125
 126           if (marked.IsOnStack(succ) && !marked.IsReachableFromEnd(succ)) {
 127             // {succ} is on stack and not reachable from end.
 128             Node* added = ConnectNTL(succ);
 129             nodes.push_back(added);
 130             marked.SetReachableFromEnd(added);
 131             AddBackwardsReachableNodes(marked, nodes, nodes.size() - 1);
 132
 133             // Reset the use iterators for the entire stack.
 134             for (size_t i = 0; i < fw_stack.size(); i++) {
 135               FwIter& iter = fw_stack[i];
 136               fw_stack[i] = FwIter(iter.first, iter.first->use_edges().begin());
 137             }
 138             pop = false;  // restart traversing successors of this node.
 139             break;
 140           }
 141           if (!marked.IsReachableFromStart(succ)) {
 142             // {succ} is not yet reached from start.
 143             marked.Push(succ);
 144             marked.SetReachableFromStart(succ);
 145             fw_stack.push_back(FwIter(succ, succ->use_edges().begin()));
 146             pop = false;  // "recurse" into successor control node.
 147             break;
 148           }
 149         }
 150         ++fw_stack.back().second;
 151       }
 152       if (pop) {
 153         marked.Pop(node);
 154         fw_stack.pop_back();
 155       }
 156     }
 157
 158     // Trim references from dead nodes to live nodes first.
 159     jsgraph_->GetCachedNodes(&nodes);
 160     TrimNodes(marked, nodes);
 161
 162     // Any control nodes not reachable from start are dead, even loops.
 163     for (size_t i = 0; i < nodes.size(); i++) {
 164       Node* node = nodes[i];
 165       if (node->op()->ControlOutputCount() > 0 &&
 166           !marked.IsReachableFromStart(node)) {
 167         ReplaceNode(node, dead());  // uses will be added to revisit queue.
 168       }
 169     }
 170     return TryRevisit();  // try to push a node onto the stack.
 171   }
 172
 173   // Connect {loop}, the header of a non-terminating loop, to the end node.
 174   Node* ConnectNTL(Node* loop) {
 175     TRACE("ConnectNTL: #%d:%s\n", loop->id(), loop->op()->mnemonic());
 176     DCHECK_EQ(IrOpcode::kLoop, loop->opcode());
 177
 178     Node* always = graph()->NewNode(common_->Always());
 179     // Mark the node as visited so that we can revisit later.
 180     MarkAsVisited(always);
 181
 182     Node* branch = graph()->NewNode(common_->Branch(), always, loop);
 183     // Mark the node as visited so that we can revisit later.
 184     MarkAsVisited(branch);
 185
 186     Node* if_true = graph()->NewNode(common_->IfTrue(), branch);
 187     // Mark the node as visited so that we can revisit later.
 188     MarkAsVisited(if_true);
 189
 190     Node* if_false = graph()->NewNode(common_->IfFalse(), branch);
 191     // Mark the node as visited so that we can revisit later.
 192     MarkAsVisited(if_false);
 193
 194     // Hook up the branch into the loop and collect all loop effects.
 195     NodeVector effects(zone_);
 196     for (auto edge : loop->use_edges()) {
 197       DCHECK_EQ(loop, edge.to());
 198       DCHECK(NodeProperties::IsControlEdge(edge));
 199       if (edge.from() == branch) continue;
 200       switch (edge.from()->opcode()) {
 201         case IrOpcode::kPhi:
 202           break;
 203         case IrOpcode::kEffectPhi:
 204           effects.push_back(edge.from());
 205           break;
 206         default:
 207           // Update all control edges (except {branch}) pointing to the {loop}.
 208           edge.UpdateTo(if_true);
 209           break;
 210       }
 211     }
 212
 213     // Compute effects for the Return.
 214     Node* effect = graph()->start();
 215     int const effects_count = static_cast<int>(effects.size());
 216     if (effects_count == 1) {
 217       effect = effects[0];
 218     } else if (effects_count > 1) {
 219       effect = graph()->NewNode(common_->EffectSet(effects_count),
 220                                 effects_count, &effects.front());
 221       // Mark the node as visited so that we can revisit later.
 222       MarkAsVisited(effect);
 223     }
 224
 225     // Add a return to connect the NTL to the end.
 226     Node* ret = graph()->NewNode(
 227         common_->Return(), jsgraph_->UndefinedConstant(), effect, if_false);
 228     // Mark the node as visited so that we can revisit later.
 229     MarkAsVisited(ret);
 230
 231     Node* end = graph()->end();
 232     CHECK_EQ(IrOpcode::kEnd, end->opcode());
 233     Node* merge = end->InputAt(0);
 234     if (merge == NULL || merge->opcode() == IrOpcode::kDead) {
 235       // The end node died; just connect end to {ret}.
 236       end->ReplaceInput(0, ret);
 237     } else if (merge->opcode() != IrOpcode::kMerge) {
 238       // Introduce a final merge node for {end->InputAt(0)} and {ret}.
 239       merge = graph()->NewNode(common_->Merge(2), merge, ret);
 240       end->ReplaceInput(0, merge);
 241       ret = merge;
 242       // Mark the node as visited so that we can revisit later.
 243       MarkAsVisited(merge);
 244     } else {
 245       // Append a new input to the final merge at the end.
 246       merge->AppendInput(graph()->zone(), ret);
 247       merge->set_op(common_->Merge(merge->InputCount()));
 248     }
 249     return ret;
 250   }
 251
 252   void AddNodesReachableFromEnd(ReachabilityMarker& marked, NodeVector& nodes) {
 253     Node* end = graph()->end();
 254     marked.SetReachableFromEnd(end);
 255     if (!end->IsDead()) {
 256       nodes.push_back(end);
 257       AddBackwardsReachableNodes(marked, nodes, nodes.size() - 1);
 258     }
 259   }
 260
 261   void AddBackwardsReachableNodes(ReachabilityMarker& marked, NodeVector& nodes,
 262                                   size_t cursor) {
 263     while (cursor < nodes.size()) {
 264       Node* node = nodes[cursor++];
 265       for (Node* const input : node->inputs()) {
 266         if (!marked.SetReachableFromEnd(input)) {
 267           nodes.push_back(input);
 268         }
 269       }
 270     }
 271   }
 272
 273   void Trim() {
 274     // Gather all nodes backwards-reachable from end through inputs.
 275     ReachabilityMarker marked(graph());
 276     NodeVector nodes(zone_);
 277     AddNodesReachableFromEnd(marked, nodes);
 278
 279     // Process cached nodes in the JSGraph too.
 280     jsgraph_->GetCachedNodes(&nodes);
 281     TrimNodes(marked, nodes);
 282   }
 283
 284   void TrimNodes(ReachabilityMarker& marked, NodeVector& nodes) {
 285     // Remove dead->live edges.
 286     for (size_t j = 0; j < nodes.size(); j++) {
 287       Node* node = nodes[j];
 288       for (Edge edge : node->use_edges()) {
 289         Node* use = edge.from();
 290         if (!marked.IsReachableFromEnd(use)) {
 291           TRACE("DeadLink: #%d:%s(%d) -> #%d:%s\n", use->id(),
 292                 use->op()->mnemonic(), edge.index(), node->id(),
 293                 node->op()->mnemonic());
 294           edge.UpdateTo(NULL);
 295         }
 296       }
 297     }
 298 #if DEBUG
 299     // Verify that no inputs to live nodes are NULL.
 300     for (Node* node : nodes) {
 301       for (int index = 0; index < node->InputCount(); index++) {
 302         Node* input = node->InputAt(index);
 303         if (input == nullptr) {
 304           std::ostringstream str;
 305           str << "GraphError: node #" << node->id() << ":" << *node->op()
 306               << "(input @" << index << ") == null";
 307           FATAL(str.str().c_str());
 308         }
 309         if (input->opcode() == IrOpcode::kDead) {
 310           std::ostringstream str;
 311           str << "GraphError: node #" << node->id() << ":" << *node->op()
 312               << "(input @" << index << ") == dead";
 313           FATAL(str.str().c_str());
 314         }
 315       }
 316       for (Node* use : node->uses()) {
 317         CHECK(marked.IsReachableFromEnd(use));
 318       }
 319     }
 320 #endif
 321   }
 322
 323   // Reduce the node on the top of the stack.
 324   // If an input {i} is not yet visited or needs to be revisited, push {i} onto
 325   // the stack and return. Otherwise, all inputs are visited, so apply
 326   // reductions for {node} and pop it off the stack.
 327   void ReduceTop() {
 328     size_t height = stack_.size();
 329     Node* node = stack_.back();
 330
 331     if (node->IsDead()) return Pop();  // Node was killed while on stack.
 332
 333     TRACE("ControlReduce: #%d:%s\n", node->id(), node->op()->mnemonic());
 334
 335     // Recurse on an input if necessary.
 336     for (Node* const input : node->inputs()) {
 337       DCHECK(input);
 338       if (Recurse(input)) return;
 339     }
 340
 341     // All inputs should be visited or on stack. Apply reductions to node.
 342     Node* replacement = ReduceNode(node);
 343     if (replacement != node) ReplaceNode(node, replacement);
 344
 345     // After reducing the node, pop it off the stack.
 346     CHECK_EQ(static_cast<int>(height), static_cast<int>(stack_.size()));
 347     Pop();
 348
 349     // If there was a replacement, reduce it after popping {node}.
 350     if (replacement != node) Recurse(replacement);
 351   }
 352
 353   void EnsureStateSize(size_t id) {
 354     if (id >= state_.size()) {
 355       state_.resize((3 * id) / 2, kUnvisited);
 356     }
 357   }
 358
 359   // Push a node onto the stack if its state is {kUnvisited} or {kRevisit}.
 360   bool Recurse(Node* node) {
 361     size_t id = static_cast<size_t>(node->id());
 362     EnsureStateSize(id);
 363     if (state_[id] != kRevisit && state_[id] != kUnvisited) return false;
 364     Push(node);
 365     return true;
 366   }
 367
 368   void Push(Node* node) {
 369     state_[node->id()] = kOnStack;
 370     stack_.push_back(node);
 371   }
 372
 373   void Pop() {
 374     int pos = static_cast<int>(stack_.size()) - 1;
 375     DCHECK_GE(pos, 0);
 376     DCHECK_EQ(kOnStack, state_[stack_[pos]->id()]);
 377     state_[stack_[pos]->id()] = kVisited;
 378     stack_.pop_back();
 379   }
 380
 381   // Queue a node to be revisited if it has been visited once already.
 382   void Revisit(Node* node) {
 383     size_t id = static_cast<size_t>(node->id());
 384     if (id < state_.size() && state_[id] == kVisited) {
 385       TRACE("  Revisit #%d:%s\n", node->id(), node->op()->mnemonic());
 386       state_[id] = kRevisit;
 387       revisit_.push_back(node);
 388     }
 389   }
 390
 391   // Mark {node} as visited.
 392   void MarkAsVisited(Node* node) {
 393     size_t id = static_cast<size_t>(node->id());
 394     EnsureStateSize(id);
 395     state_[id] = kVisited;
 396   }
 397
 398   Node* dead() { return jsgraph_->DeadControl(); }
 399
 400   //===========================================================================
 401   // Reducer implementation: perform reductions on a node.
 402   //===========================================================================
 403   Node* ReduceNode(Node* node) {
 404     if (node->op()->ControlInputCount() == 1 ||
 405         node->opcode() == IrOpcode::kLoop) {
 406       // If a node has only one control input and it is dead, replace with dead.
 407       Node* control = NodeProperties::GetControlInput(node);
 408       if (control->opcode() == IrOpcode::kDead) {
 409         TRACE("ControlDead: #%d:%s\n", node->id(), node->op()->mnemonic());
 410         return control;
 411       }
 412     }
 413
 414     // Reduce branches, phis, and merges.
 415     switch (node->opcode()) {
 416       case IrOpcode::kBranch:
 417         return ReduceBranch(node);
 418       case IrOpcode::kIfTrue:
 419         return ReduceIfTrue(node);
 420       case IrOpcode::kIfFalse:
 421         return ReduceIfFalse(node);
 422       case IrOpcode::kLoop:
 423       case IrOpcode::kMerge:
 424         return ReduceMerge(node);
 425       case IrOpcode::kSelect:
 426         return ReduceSelect(node);
 427       case IrOpcode::kPhi:
 428       case IrOpcode::kEffectPhi:
 429         return ReducePhi(node);
 430       default:
 431         return node;
 432     }
 433   }
 434
 435   // Try to statically fold a condition.
 436   Decision DecideCondition(Node* cond) {
 437     switch (cond->opcode()) {
 438       case IrOpcode::kInt32Constant:
 439         return Int32Matcher(cond).Is(0) ? kFalse : kTrue;
 440       case IrOpcode::kInt64Constant:
 441         return Int64Matcher(cond).Is(0) ? kFalse : kTrue;
 442       case IrOpcode::kNumberConstant:
 443         return NumberMatcher(cond).Is(0) ? kFalse : kTrue;
 444       case IrOpcode::kHeapConstant: {
 445         Handle<Object> object =
 446             HeapObjectMatcher<Object>(cond).Value().handle();
 447         if (object->IsTrue()) return kTrue;
 448         if (object->IsFalse()) return kFalse;
 449         // TODO(turbofan): decide more conditions for heap constants.
 450         break;
 451       }
 452       default:
 453         break;
 454     }
 455     return kUnknown;
 456   }
 457
 458   // Reduce redundant selects.
 459   Node* ReduceSelect(Node* const node) {
 460     Node* const tvalue = node->InputAt(1);
 461     Node* const fvalue = node->InputAt(2);
 462     if (tvalue == fvalue) return tvalue;
 463     Decision result = DecideCondition(node->InputAt(0));
 464     if (result == kTrue) return tvalue;
 465     if (result == kFalse) return fvalue;
 466     return node;
 467   }
 468
 469   // Reduce redundant phis.
 470   Node* ReducePhi(Node* node) {
 471     int n = node->InputCount();
 472     if (n <= 1) return dead();            // No non-control inputs.
 473     if (n == 2) return node->InputAt(0);  // Only one non-control input.
 474
 475     // Never remove an effect phi from a (potentially non-terminating) loop.
 476     // Otherwise, we might end up eliminating effect nodes, such as calls,
 477     // before the loop.
 478     if (node->opcode() == IrOpcode::kEffectPhi &&
 479         NodeProperties::GetControlInput(node)->opcode() == IrOpcode::kLoop) {
 480       return node;
 481     }
 482
 483     Node* replacement = NULL;
 484     auto const inputs = node->inputs();
 485     for (auto it = inputs.begin(); n > 1; --n, ++it) {
 486       Node* input = *it;
 487       if (input->opcode() == IrOpcode::kDead) continue;  // ignore dead inputs.
 488       if (input != node && input != replacement) {       // non-redundant input.
 489         if (replacement != NULL) return node;
 490         replacement = input;
 491       }
 492     }
 493     return replacement == NULL ? dead() : replacement;
 494   }
 495
 496   // Reduce branches.
 497   Node* ReduceBranch(Node* branch) {
 498     if (DecideCondition(branch->InputAt(0)) != kUnknown) {
 499       for (Node* use : branch->uses()) Revisit(use);
 500     }
 501     return branch;
 502   }
 503
 504   // Reduce merges by trimming away dead inputs from the merge and phis.
 505   Node* ReduceMerge(Node* node) {
 506     // Count the number of live inputs.
 507     int live = 0;
 508     int index = 0;
 509     int live_index = 0;
 510     for (Node* const input : node->inputs()) {
 511       if (input->opcode() != IrOpcode::kDead) {
 512         live++;
 513         live_index = index;
 514       }
 515       index++;
 516     }
 517
 518     TRACE("ReduceMerge: #%d:%s (%d of %d live)\n", node->id(),
 519           node->op()->mnemonic(), live, index);
 520
 521     if (live == 0) return dead();  // no remaining inputs.
 522
 523     // Gather phis and effect phis to be edited.
 524     ZoneVector<Node*> phis(zone_);
 525     for (Node* const use : node->uses()) {
 526       if (NodeProperties::IsPhi(use)) phis.push_back(use);
 527     }
 528
 529     if (live == 1) {
 530       // All phis are redundant. Replace them with their live input.
 531       for (Node* const phi : phis) ReplaceNode(phi, phi->InputAt(live_index));
 532       // The merge itself is redundant.
 533       return node->InputAt(live_index);
 534     }
 535
 536     DCHECK_LE(2, live);
 537
 538     if (live < node->InputCount()) {
 539       // Edit phis in place, removing dead inputs and revisiting them.
 540       for (Node* const phi : phis) {
 541         TRACE("  PhiInMerge: #%d:%s (%d live)\n", phi->id(),
 542               phi->op()->mnemonic(), live);
 543         RemoveDeadInputs(node, phi);
 544         Revisit(phi);
 545       }
 546       // Edit the merge in place, removing dead inputs.
 547       RemoveDeadInputs(node, node);
 548     }
 549
 550     DCHECK_EQ(live, node->InputCount());
 551
 552     // Check if it's an unused diamond.
 553     if (live == 2 && phis.empty()) {
 554       Node* node0 = node->InputAt(0);
 555       Node* node1 = node->InputAt(1);
 556       if (((node0->opcode() == IrOpcode::kIfTrue &&
 557             node1->opcode() == IrOpcode::kIfFalse) ||
 558            (node1->opcode() == IrOpcode::kIfTrue &&
 559             node0->opcode() == IrOpcode::kIfFalse)) &&
 560           node0->OwnedBy(node) && node1->OwnedBy(node)) {
 561         Node* branch0 = NodeProperties::GetControlInput(node0);
 562         Node* branch1 = NodeProperties::GetControlInput(node1);
 563         if (branch0 == branch1) {
 564           // It's a dead diamond, i.e. neither the IfTrue nor the IfFalse nodes
 565           // have users except for the Merge and the Merge has no Phi or
 566           // EffectPhi uses, so replace the Merge with the control input of the
 567           // diamond.
 568           TRACE("  DeadDiamond: #%d:%s #%d:%s #%d:%s\n", node0->id(),
 569                 node0->op()->mnemonic(), node1->id(), node1->op()->mnemonic(),
 570                 branch0->id(), branch0->op()->mnemonic());
 571           return NodeProperties::GetControlInput(branch0);
 572         }
 573       }
 574     }
 575
 576     return node;
 577   }
 578
 579   // Reduce branches if they have constant inputs.
 580   Node* ReduceIfTrue(Node* node) {
 581     Node* branch = node->InputAt(0);
 582     DCHECK_EQ(IrOpcode::kBranch, branch->opcode());
 583     Decision result = DecideCondition(branch->InputAt(0));
 584     if (result == kTrue) {
 585       // fold a true branch by replacing IfTrue with the branch control.
 586       TRACE("  BranchReduce: #%d:%s => #%d:%s\n", branch->id(),
 587             branch->op()->mnemonic(), node->id(), node->op()->mnemonic());
 588       return branch->InputAt(1);
 589     }
 590     return result == kUnknown ? node : dead();
 591   }
 592
 593   // Reduce branches if they have constant inputs.
 594   Node* ReduceIfFalse(Node* node) {
 595     Node* branch = node->InputAt(0);
 596     DCHECK_EQ(IrOpcode::kBranch, branch->opcode());
 597     Decision result = DecideCondition(branch->InputAt(0));
 598     if (result == kFalse) {
 599       // fold a false branch by replacing IfFalse with the branch control.
 600       TRACE("  BranchReduce: #%d:%s => #%d:%s\n", branch->id(),
 601             branch->op()->mnemonic(), node->id(), node->op()->mnemonic());
 602       return branch->InputAt(1);
 603     }
 604     return result == kUnknown ? node : dead();
 605   }
 606
 607   // Remove inputs to {node} corresponding to the dead inputs to {merge}
 608   // and compact the remaining inputs, updating the operator.
 609   void RemoveDeadInputs(Node* merge, Node* node) {
 610     int live = 0;
 611     for (int i = 0; i < merge->InputCount(); i++) {
 612       // skip dead inputs.
 613       if (merge->InputAt(i)->opcode() == IrOpcode::kDead) continue;
 614       // compact live inputs.
 615       if (live != i) node->ReplaceInput(live, node->InputAt(i));
 616       live++;
 617     }
 618     // compact remaining inputs.
 619     int total = live;
 620     for (int i = merge->InputCount(); i < node->InputCount(); i++) {
 621       if (total != i) node->ReplaceInput(total, node->InputAt(i));
 622       total++;
 623     }
 624     DCHECK_EQ(total, live + node->InputCount() - merge->InputCount());
 625     DCHECK_NE(total, node->InputCount());
 626     node->TrimInputCount(total);
 627     node->set_op(common_->ResizeMergeOrPhi(node->op(), live));
 628   }
 629
 630   // Replace uses of {node} with {replacement} and revisit the uses.
 631   void ReplaceNode(Node* node, Node* replacement) {
 632     if (node == replacement) return;
 633     TRACE("  Replace: #%d:%s with #%d:%s\n", node->id(), node->op()->mnemonic(),
 634           replacement->id(), replacement->op()->mnemonic());
 635     for (Node* const use : node->uses()) {
 636       // Don't revisit this node if it refers to itself.
 637       if (use != node) Revisit(use);
 638     }
 639     node->ReplaceUses(replacement);
 640     node->Kill();
 641   }
 642
 643   Graph* graph() { return jsgraph_->graph(); }
 644 };
 645
 646
 647 void ControlReducer::ReduceGraph(Zone* zone, JSGraph* jsgraph,
 648                                  CommonOperatorBuilder* common) {
 649   ControlReducerImpl impl(zone, jsgraph, common);
 650   impl.Reduce();
 651 }
 652
 653
 654 void ControlReducer::TrimGraph(Zone* zone, JSGraph* jsgraph) {
 655   ControlReducerImpl impl(zone, jsgraph, NULL);
 656   impl.Trim();
 657 }
 658
 659
 660 Node* ControlReducer::ReduceMerge(JSGraph* jsgraph,
 661                                   CommonOperatorBuilder* common, Node* node) {
 662   Zone zone;
 663   ControlReducerImpl impl(&zone, jsgraph, common);
 664   return impl.ReduceMerge(node);
 665 }
 666
 667
 668 Node* ControlReducer::ReducePhiForTesting(JSGraph* jsgraph,
 669                                           CommonOperatorBuilder* common,
 670                                           Node* node) {
 671   Zone zone;
 672   ControlReducerImpl impl(&zone, jsgraph, common);
 673   return impl.ReducePhi(node);
 674 }
 675
 676
 677 Node* ControlReducer::ReduceIfNodeForTesting(JSGraph* jsgraph,
 678                                              CommonOperatorBuilder* common,
 679                                              Node* node) {
 680   Zone zone;
 681   ControlReducerImpl impl(&zone, jsgraph, common);
 682   switch (node->opcode()) {
 683     case IrOpcode::kIfTrue:
 684       return impl.ReduceIfTrue(node);
 685     case IrOpcode::kIfFalse:
 686       return impl.ReduceIfFalse(node);
 687     default:
 688       return node;
 689   }
 690 }
 691 }
 692 }
 693 }  // namespace v8::internal::compiler