From 82581534aebc90ed779af5cf2b377f036c0fc3bc Mon Sep 17 00:00:00 2001 From: "titzer@chromium.org" Date: Mon, 27 Oct 2014 08:41:32 +0000 Subject: [PATCH] Implement control reducer, which reduces branches and phis together in a single fixpoint. R=bmeurer@chromium.org BUG= Review URL: https://codereview.chromium.org/665223006 Cr-Commit-Position: refs/heads/master@{#24891} git-svn-id: https://v8.googlecode.com/svn/branches/bleeding_edge@24891 ce2b1a6d-e550-0410-aec6-3dcde31c8c00 --- src/compiler/control-reducer.cc | 452 +++++++- src/compiler/control-reducer.h | 11 + src/compiler/operator-properties-inl.h | 3 +- src/compiler/scheduler.cc | 3 +- test/cctest/compiler/test-control-reducer.cc | 1498 +++++++++++++++++++++++++- 5 files changed, 1915 insertions(+), 52 deletions(-) diff --git a/src/compiler/control-reducer.cc b/src/compiler/control-reducer.cc index 03d0583..e1bd0c9 100644 --- a/src/compiler/control-reducer.cc +++ b/src/compiler/control-reducer.cc @@ -14,7 +14,8 @@ namespace v8 { namespace internal { namespace compiler { -enum VisitState { kUnvisited, kOnStack, kRevisit, kVisited }; +enum VisitState { kUnvisited = 0, kOnStack = 1, kRevisit = 2, kVisited = 3 }; +enum Reachability { kFromStart = 8 }; #define TRACE(x) \ if (FLAG_trace_turbo) PrintF x @@ -39,23 +40,169 @@ class ControlReducerImpl { ZoneDeque revisit_; Node* dead_; - void Trim() { - // Mark all nodes reachable from end. + void Reduce() { + Push(graph()->end()); + do { + // Process the node on the top of the stack, potentially pushing more + // or popping the node off the stack. + ReduceTop(); + // If the stack becomes empty, revisit any nodes in the revisit queue. + // If no nodes in the revisit queue, try removing dead loops. + // If no dead loops, then finish. + } while (!stack_.empty() || TryRevisit() || RepairAndRemoveLoops()); + } + + bool TryRevisit() { + while (!revisit_.empty()) { + Node* n = revisit_.back(); + revisit_.pop_back(); + if (state_[n->id()] == kRevisit) { // state can change while in queue. + Push(n); + return true; + } + } + return false; + } + + // Repair the graph after the possible creation of non-terminating or dead + // loops. Removing dead loops can produce more opportunities for reduction. + bool RepairAndRemoveLoops() { + // TODO(turbofan): we can skip this if the graph has no loops, but + // we have to be careful about proper loop detection during reduction. + + // Gather all nodes backwards-reachable from end (through inputs). + state_.assign(graph()->NodeCount(), kUnvisited); NodeVector nodes(zone_); - state_.assign(jsgraph_->graph()->NodeCount(), kUnvisited); - Push(jsgraph_->graph()->end()); + AddNodesReachableFromEnd(nodes); + + // Walk forward through control nodes, looking for back edges to nodes + // that are not connected to end. Those are non-terminating loops (NTLs). + Node* start = graph()->start(); + ZoneVector fw_reachability(graph()->NodeCount(), 0, zone_); + fw_reachability[start->id()] = kFromStart | kOnStack; + stack_.push_back(start); + while (!stack_.empty()) { - Node* node = stack_[stack_.size() - 1]; - stack_.pop_back(); - state_[node->id()] = kVisited; - nodes.push_back(node); - for (InputIter i = node->inputs().begin(); i != node->inputs().end(); - ++i) { - Recurse(*i); // pushes node onto the stack if necessary. + Node* node = stack_.back(); + TRACE(("ControlFw: #%d:%s\n", node->id(), node->op()->mnemonic())); + bool pop = true; + for (Node* const succ : node->uses()) { + byte reach = fw_reachability[succ->id()]; + if ((reach & kOnStack) != 0 && state_[succ->id()] != kVisited) { + // {succ} is on stack and not reachable from end. + ConnectNTL(nodes, succ); + fw_reachability.resize(graph()->NodeCount(), 0); + pop = false; // continue traversing inputs to this node. + break; + } + if ((reach & kFromStart) == 0 && + IrOpcode::IsControlOpcode(succ->opcode())) { + // {succ} is a control node and not yet reached from start. + fw_reachability[succ->id()] |= kFromStart | kOnStack; + stack_.push_back(succ); + pop = false; // "recurse" into successor control node. + break; + } + } + if (pop) { + fw_reachability[node->id()] &= ~kOnStack; + stack_.pop_back(); } } + + // Trim references from dead nodes to live nodes first. + jsgraph_->GetCachedNodes(&nodes); + TrimNodes(nodes); + + // Any control nodes not reachable from start are dead, even loops. + for (size_t i = 0; i < nodes.size(); i++) { + Node* node = nodes[i]; + byte reach = fw_reachability[node->id()]; + if ((reach & kFromStart) == 0 && + IrOpcode::IsControlOpcode(node->opcode())) { + ReplaceNode(node, dead()); // uses will be added to revisit queue. + } + } + return TryRevisit(); // try to push a node onto the stack. + } + + // Connect {loop}, the header of a non-terminating loop, to the end node. + void ConnectNTL(NodeVector& nodes, Node* loop) { + TRACE(("ConnectNTL: #%d:%s\n", loop->id(), loop->op()->mnemonic())); + + if (loop->opcode() != IrOpcode::kTerminate) { + // Insert a {Terminate} node if the loop has effects. + ZoneDeque effects(zone_); + for (Node* const use : loop->uses()) { + if (use->opcode() == IrOpcode::kEffectPhi) effects.push_back(use); + } + int count = static_cast(effects.size()); + if (count > 0) { + Node** inputs = zone_->NewArray(1 + count); + for (int i = 0; i < count; i++) inputs[i] = effects[i]; + inputs[count] = loop; + loop = graph()->NewNode(common_->Terminate(count), 1 + count, inputs); + TRACE(("AddTerminate: #%d:%s[%d]\n", loop->id(), loop->op()->mnemonic(), + count)); + } + } + + Node* to_add = loop; + Node* end = graph()->end(); + CHECK_EQ(IrOpcode::kEnd, end->opcode()); + Node* merge = end->InputAt(0); + if (merge == NULL || merge->opcode() == IrOpcode::kDead) { + // The end node died; just connect end to {loop}. + end->ReplaceInput(0, loop); + } else if (merge->opcode() != IrOpcode::kMerge) { + // Introduce a final merge node for {end->InputAt(0)} and {loop}. + merge = graph()->NewNode(common_->Merge(2), merge, loop); + end->ReplaceInput(0, merge); + to_add = merge; + } else { + // Append a new input to the final merge at the end. + merge->AppendInput(graph()->zone(), loop); + merge->set_op(common_->Merge(merge->InputCount())); + } + nodes.push_back(to_add); + state_.resize(graph()->NodeCount(), kUnvisited); + state_[to_add->id()] = kVisited; + AddBackwardsReachableNodes(nodes, nodes.size() - 1); + } + + void AddNodesReachableFromEnd(NodeVector& nodes) { + Node* end = graph()->end(); + state_[end->id()] = kVisited; + if (!end->IsDead()) { + nodes.push_back(end); + AddBackwardsReachableNodes(nodes, nodes.size() - 1); + } + } + + void AddBackwardsReachableNodes(NodeVector& nodes, size_t cursor) { + while (cursor < nodes.size()) { + Node* node = nodes[cursor++]; + for (Node* const input : node->inputs()) { + if (state_[input->id()] != kVisited) { + state_[input->id()] = kVisited; + nodes.push_back(input); + } + } + } + } + + void Trim() { + // Gather all nodes backwards-reachable from end through inputs. + state_.assign(graph()->NodeCount(), kUnvisited); + NodeVector nodes(zone_); + AddNodesReachableFromEnd(nodes); + // Process cached nodes in the JSGraph too. jsgraph_->GetCachedNodes(&nodes); + TrimNodes(nodes); + } + + void TrimNodes(NodeVector& nodes) { // Remove dead->live edges. for (size_t j = 0; j < nodes.size(); j++) { Node* node = nodes[j]; @@ -75,18 +222,46 @@ class ControlReducerImpl { // Verify that no inputs to live nodes are NULL. for (size_t j = 0; j < nodes.size(); j++) { Node* node = nodes[j]; - for (InputIter i = node->inputs().begin(); i != node->inputs().end(); - ++i) { - CHECK_NE(NULL, *i); + for (Node* const input : node->inputs()) { + CHECK_NE(NULL, input); } - for (UseIter i = node->uses().begin(); i != node->uses().end(); ++i) { - size_t id = static_cast((*i)->id()); + for (Node* const use : node->uses()) { + size_t id = static_cast(use->id()); CHECK_EQ(kVisited, state_[id]); } } #endif } + // Reduce the node on the top of the stack. + // If an input {i} is not yet visited or needs to be revisited, push {i} onto + // the stack and return. Otherwise, all inputs are visited, so apply + // reductions for {node} and pop it off the stack. + void ReduceTop() { + size_t height = stack_.size(); + Node* node = stack_.back(); + + if (node->IsDead()) return Pop(); // Node was killed while on stack. + + TRACE(("ControlReduce: #%d:%s\n", node->id(), node->op()->mnemonic())); + + // Recurse on an input if necessary. + for (Node* const input : node->inputs()) { + if (Recurse(input)) return; + } + + // All inputs should be visited or on stack. Apply reductions to node. + Node* replacement = ReduceNode(node); + if (replacement != node) ReplaceNode(node, replacement); + + // After reducing the node, pop it off the stack. + CHECK_EQ(static_cast(height), static_cast(stack_.size())); + Pop(); + + // If there was a replacement, reduce it after popping {node}. + if (replacement != node) Recurse(replacement); + } + // Push a node onto the stack if its state is {kUnvisited} or {kRevisit}. bool Recurse(Node* node) { size_t id = static_cast(node->id()); @@ -103,13 +278,223 @@ class ControlReducerImpl { state_[node->id()] = kOnStack; stack_.push_back(node); } + + void Pop() { + int pos = static_cast(stack_.size()) - 1; + DCHECK_GE(pos, 0); + DCHECK_EQ(kOnStack, state_[stack_[pos]->id()]); + state_[stack_[pos]->id()] = kVisited; + stack_.pop_back(); + } + + // Queue a node to be revisited if it has been visited once already. + void Revisit(Node* node) { + size_t id = static_cast(node->id()); + if (id < state_.size() && state_[id] == kVisited) { + TRACE((" Revisit #%d:%s\n", node->id(), node->op()->mnemonic())); + state_[id] = kRevisit; + revisit_.push_back(node); + } + } + + Node* dead() { + if (dead_ == NULL) dead_ = graph()->NewNode(common_->Dead()); + return dead_; + } + + //=========================================================================== + // Reducer implementation: perform reductions on a node. + //=========================================================================== + Node* ReduceNode(Node* node) { + if (OperatorProperties::GetControlInputCount(node->op()) == 1) { + // If a node has only one control input and it is dead, replace with dead. + Node* control = NodeProperties::GetControlInput(node); + if (control->opcode() == IrOpcode::kDead) { + TRACE(("ControlDead: #%d:%s\n", node->id(), node->op()->mnemonic())); + return control; + } + } + + // Reduce branches, phis, and merges. + switch (node->opcode()) { + case IrOpcode::kBranch: + return ReduceBranch(node); + case IrOpcode::kLoop: + case IrOpcode::kMerge: + return ReduceMerge(node); + case IrOpcode::kPhi: + case IrOpcode::kEffectPhi: + return ReducePhi(node); + default: + return node; + } + } + + // Reduce redundant phis. + Node* ReducePhi(Node* node) { + int n = node->InputCount(); + if (n <= 1) return dead(); // No non-control inputs. + if (n == 2) return node->InputAt(0); // Only one non-control input. + + Node* replacement = NULL; + Node::Inputs inputs = node->inputs(); + for (InputIter it = inputs.begin(); n > 1; --n, ++it) { + Node* input = *it; + if (input->opcode() == IrOpcode::kDead) continue; // ignore dead inputs. + if (input != node && input != replacement) { // non-redundant input. + if (replacement != NULL) return node; + replacement = input; + } + } + return replacement == NULL ? dead() : replacement; + } + + // Reduce merges by trimming away dead inputs from the merge and phis. + Node* ReduceMerge(Node* node) { + // Count the number of live inputs. + int live = 0; + int index = 0; + int live_index = 0; + for (Node* const input : node->inputs()) { + if (input->opcode() != IrOpcode::kDead) { + live++; + live_index = index; + } + index++; + } + + if (live > 1 && live == node->InputCount()) return node; // nothing to do. + + TRACE(("ReduceMerge: #%d:%s (%d live)\n", node->id(), + node->op()->mnemonic(), live)); + + if (live == 0) return dead(); // no remaining inputs. + + // Gather phis and effect phis to be edited. + ZoneVector phis(zone_); + for (Node* const use : node->uses()) { + if (use->opcode() == IrOpcode::kPhi || + use->opcode() == IrOpcode::kEffectPhi) { + phis.push_back(use); + } + } + + if (live == 1) { + // All phis are redundant. Replace them with their live input. + for (Node* const phi : phis) ReplaceNode(phi, phi->InputAt(live_index)); + // The merge itself is redundant. + return node->InputAt(live_index); + } + + // Edit phis in place, removing dead inputs and revisiting them. + for (Node* const phi : phis) { + TRACE((" PhiInMerge: #%d:%s (%d live)\n", phi->id(), + phi->op()->mnemonic(), live)); + RemoveDeadInputs(node, phi); + Revisit(phi); + } + // Edit the merge in place, removing dead inputs. + RemoveDeadInputs(node, node); + return node; + } + + // Reduce branches if they have constant inputs. + Node* ReduceBranch(Node* node) { + Node* cond = node->InputAt(0); + bool is_true; + switch (cond->opcode()) { + case IrOpcode::kInt32Constant: + is_true = !Int32Matcher(cond).Is(0); + break; + case IrOpcode::kNumberConstant: + is_true = !NumberMatcher(cond).Is(0); + break; + case IrOpcode::kHeapConstant: { + Handle object = + HeapObjectMatcher(cond).Value().handle(); + if (object->IsTrue()) + is_true = true; + else if (object->IsFalse()) + is_true = false; + else + return node; // TODO(turbofan): fold branches on strings, objects. + break; + } + default: + return node; + } + + TRACE(("BranchReduce: #%d:%s = %s\n", node->id(), node->op()->mnemonic(), + is_true ? "true" : "false")); + + // Replace IfTrue and IfFalse projections from this branch. + Node* control = NodeProperties::GetControlInput(node); + for (UseIter i = node->uses().begin(); i != node->uses().end();) { + Node* to = *i; + if (to->opcode() == IrOpcode::kIfTrue) { + TRACE((" IfTrue: #%d:%s\n", to->id(), to->op()->mnemonic())); + i.UpdateToAndIncrement(NULL); + ReplaceNode(to, is_true ? control : dead()); + } else if (to->opcode() == IrOpcode::kIfFalse) { + TRACE((" IfFalse: #%d:%s\n", to->id(), to->op()->mnemonic())); + i.UpdateToAndIncrement(NULL); + ReplaceNode(to, is_true ? dead() : control); + } else { + ++i; + } + } + return control; + } + + // Remove inputs to {node} corresponding to the dead inputs to {merge} + // and compact the remaining inputs, updating the operator. + void RemoveDeadInputs(Node* merge, Node* node) { + int pos = 0; + for (int i = 0; i < node->InputCount(); i++) { + // skip dead inputs. + if (i < merge->InputCount() && + merge->InputAt(i)->opcode() == IrOpcode::kDead) + continue; + // compact live inputs. + if (pos != i) node->ReplaceInput(pos, node->InputAt(i)); + pos++; + } + node->TrimInputCount(pos); + if (node->opcode() == IrOpcode::kPhi) { + node->set_op(common_->Phi(OpParameter(node->op()), pos - 1)); + } else if (node->opcode() == IrOpcode::kEffectPhi) { + node->set_op(common_->EffectPhi(pos - 1)); + } else if (node->opcode() == IrOpcode::kMerge) { + node->set_op(common_->Merge(pos)); + } else if (node->opcode() == IrOpcode::kLoop) { + node->set_op(common_->Loop(pos)); + } else { + UNREACHABLE(); + } + } + + // Replace uses of {node} with {replacement} and revisit the uses. + void ReplaceNode(Node* node, Node* replacement) { + if (node == replacement) return; + TRACE((" Replace: #%d:%s with #%d:%s\n", node->id(), + node->op()->mnemonic(), replacement->id(), + replacement->op()->mnemonic())); + for (Node* const use : node->uses()) { + // Don't revisit this node if it refers to itself. + if (use != node) Revisit(use); + } + node->ReplaceUses(replacement); + node->Kill(); + } + + Graph* graph() { return jsgraph_->graph(); } }; + void ControlReducer::ReduceGraph(Zone* zone, JSGraph* jsgraph, CommonOperatorBuilder* common) { - ControlReducerImpl impl(zone, jsgraph, NULL); - // Only trim the graph for now. Control reduction can reduce non-terminating - // loops to graphs that are unschedulable at the moment. + ControlReducerImpl impl(zone, jsgraph, common); + impl.Reduce(); impl.Trim(); } @@ -118,6 +503,33 @@ void ControlReducer::TrimGraph(Zone* zone, JSGraph* jsgraph) { ControlReducerImpl impl(zone, jsgraph, NULL); impl.Trim(); } + + +Node* ControlReducer::ReducePhiForTesting(JSGraph* jsgraph, + CommonOperatorBuilder* common, + Node* node) { + Zone zone(jsgraph->graph()->zone()->isolate()); + ControlReducerImpl impl(&zone, jsgraph, common); + return impl.ReducePhi(node); +} + + +Node* ControlReducer::ReduceMergeForTesting(JSGraph* jsgraph, + CommonOperatorBuilder* common, + Node* node) { + Zone zone(jsgraph->graph()->zone()->isolate()); + ControlReducerImpl impl(&zone, jsgraph, common); + return impl.ReduceMerge(node); +} + + +Node* ControlReducer::ReduceBranchForTesting(JSGraph* jsgraph, + CommonOperatorBuilder* common, + Node* node) { + Zone zone(jsgraph->graph()->zone()->isolate()); + ControlReducerImpl impl(&zone, jsgraph, common); + return impl.ReduceBranch(node); +} } } } // namespace v8::internal::compiler diff --git a/src/compiler/control-reducer.h b/src/compiler/control-reducer.h index e9ae9bc..e25bb88 100644 --- a/src/compiler/control-reducer.h +++ b/src/compiler/control-reducer.h @@ -11,6 +11,7 @@ namespace compiler { class JSGraph; class CommonOperatorBuilder; +class Node; class ControlReducer { public: @@ -20,6 +21,16 @@ class ControlReducer { // Trim nodes in the graph that are not reachable from end. static void TrimGraph(Zone* zone, JSGraph* graph); + + // Testing interface. + static Node* ReducePhiForTesting(JSGraph* graph, + CommonOperatorBuilder* builder, Node* node); + static Node* ReduceBranchForTesting(JSGraph* graph, + CommonOperatorBuilder* builder, + Node* node); + static Node* ReduceMergeForTesting(JSGraph* graph, + CommonOperatorBuilder* builder, + Node* node); }; } } diff --git a/src/compiler/operator-properties-inl.h b/src/compiler/operator-properties-inl.h index 771f560..7c2ae16 100644 --- a/src/compiler/operator-properties-inl.h +++ b/src/compiler/operator-properties-inl.h @@ -117,6 +117,7 @@ inline int OperatorProperties::GetEffectInputCount(const Operator* op) { } inline int OperatorProperties::GetControlInputCount(const Operator* op) { + // TODO(titzer): fix this mess; just make them a count on the operator. switch (op->opcode()) { case IrOpcode::kPhi: case IrOpcode::kEffectPhi: @@ -127,8 +128,8 @@ inline int OperatorProperties::GetControlInputCount(const Operator* op) { #define OPCODE_CASE(x) case IrOpcode::k##x: CONTROL_OP_LIST(OPCODE_CASE) #undef OPCODE_CASE - // Branch operator is special if (op->opcode() == IrOpcode::kBranch) return 1; + if (op->opcode() == IrOpcode::kTerminate) return 1; // Control operators are Operator1. return OpParameter(op); default: diff --git a/src/compiler/scheduler.cc b/src/compiler/scheduler.cc index a75a9ef..346e072 100644 --- a/src/compiler/scheduler.cc +++ b/src/compiler/scheduler.cc @@ -382,7 +382,8 @@ class CFGBuilder { } bool IsFinalMerge(Node* node) { - return (node == scheduler_->graph_->end()->InputAt(0)); + return (node->opcode() == IrOpcode::kMerge && + node == scheduler_->graph_->end()->InputAt(0)); } }; diff --git a/test/cctest/compiler/test-control-reducer.cc b/test/cctest/compiler/test-control-reducer.cc index 0e8dc17..dc80cc3 100644 --- a/test/cctest/compiler/test-control-reducer.cc +++ b/test/cctest/compiler/test-control-reducer.cc @@ -5,27 +5,82 @@ #include "src/v8.h" #include "test/cctest/cctest.h" +#include "src/base/bits.h" #include "src/compiler/common-operator.h" #include "src/compiler/control-reducer.h" #include "src/compiler/graph-inl.h" #include "src/compiler/js-graph.h" +#include "src/compiler/node-properties-inl.h" using namespace v8::internal; using namespace v8::internal::compiler; -class CTrimTester : HandleAndZoneScope { +static const size_t kNumLeafs = 4; + +// TODO(titzer): convert this whole file into unit tests. + +static int CheckInputs(Node* node, Node* i0 = NULL, Node* i1 = NULL, + Node* i2 = NULL) { + int count = 3; + if (i2 == NULL) count = 2; + if (i1 == NULL) count = 1; + if (i0 == NULL) count = 0; + CHECK_EQ(count, node->InputCount()); + if (i0 != NULL) CHECK_EQ(i0, node->InputAt(0)); + if (i1 != NULL) CHECK_EQ(i1, node->InputAt(1)); + if (i2 != NULL) CHECK_EQ(i2, node->InputAt(2)); + return count; +} + + +static int CheckMerge(Node* node, Node* i0 = NULL, Node* i1 = NULL, + Node* i2 = NULL) { + CHECK_EQ(IrOpcode::kMerge, node->opcode()); + int count = CheckInputs(node, i0, i1, i2); + CHECK_EQ(count, OperatorProperties::GetControlInputCount(node->op())); + return count; +} + + +static int CheckLoop(Node* node, Node* i0 = NULL, Node* i1 = NULL, + Node* i2 = NULL) { + CHECK_EQ(IrOpcode::kLoop, node->opcode()); + int count = CheckInputs(node, i0, i1, i2); + CHECK_EQ(count, OperatorProperties::GetControlInputCount(node->op())); + return count; +} + + +bool IsUsedBy(Node* a, Node* b) { + for (UseIter i = a->uses().begin(); i != a->uses().end(); ++i) { + if (b == *i) return true; + } + return false; +} + + +// A helper for all tests dealing with ControlTester. +class ControlReducerTester : HandleAndZoneScope { public: - CTrimTester() + ControlReducerTester() : isolate(main_isolate()), common(main_zone()), graph(main_zone()), jsgraph(&graph, &common, NULL, NULL), start(graph.NewNode(common.Start(1))), + end(graph.NewNode(common.End(), start)), p0(graph.NewNode(common.Parameter(0), start)), + zero(jsgraph.Int32Constant(0)), one(jsgraph.OneConstant()), - half(jsgraph.Constant(0.5)) { - graph.SetEnd(start); + half(jsgraph.Constant(0.5)), + self(graph.NewNode(common.Int32Constant(0xaabbccdd))), + dead(graph.NewNode(common.Dead())) { + graph.SetEnd(end); graph.SetStart(start); + leaf[0] = zero; + leaf[1] = one; + leaf[2] = half; + leaf[3] = p0; } Isolate* isolate; @@ -33,34 +88,124 @@ class CTrimTester : HandleAndZoneScope { Graph graph; JSGraph jsgraph; Node* start; + Node* end; Node* p0; + Node* zero; Node* one; Node* half; + Node* self; + Node* dead; + Node* leaf[kNumLeafs]; + + Node* Phi(Node* a) { + return SetSelfReferences(graph.NewNode(op(1, false), a, start)); + } + + Node* Phi(Node* a, Node* b) { + return SetSelfReferences(graph.NewNode(op(2, false), a, b, start)); + } + + Node* Phi(Node* a, Node* b, Node* c) { + return SetSelfReferences(graph.NewNode(op(3, false), a, b, c, start)); + } + + Node* Phi(Node* a, Node* b, Node* c, Node* d) { + return SetSelfReferences(graph.NewNode(op(4, false), a, b, c, d, start)); + } + + Node* EffectPhi(Node* a) { + return SetSelfReferences(graph.NewNode(op(1, true), a, start)); + } + + Node* EffectPhi(Node* a, Node* b) { + return SetSelfReferences(graph.NewNode(op(2, true), a, b, start)); + } + + Node* EffectPhi(Node* a, Node* b, Node* c) { + return SetSelfReferences(graph.NewNode(op(3, true), a, b, c, start)); + } + + Node* EffectPhi(Node* a, Node* b, Node* c, Node* d) { + return SetSelfReferences(graph.NewNode(op(4, true), a, b, c, d, start)); + } + + Node* SetSelfReferences(Node* node) { + Node::Inputs inputs = node->inputs(); + for (Node::Inputs::iterator iter(inputs.begin()); iter != inputs.end(); + ++iter) { + Node* input = *iter; + if (input == self) node->ReplaceInput(iter.index(), node); + } + return node; + } + + const Operator* op(int count, bool effect) { + return effect ? common.EffectPhi(count) : common.Phi(kMachAnyTagged, count); + } void Trim() { ControlReducer::TrimGraph(main_zone(), &jsgraph); } -}; + void ReduceGraph() { + ControlReducer::ReduceGraph(main_zone(), &jsgraph, &common); + } -bool IsUsedBy(Node* a, Node* b) { - for (UseIter i = a->uses().begin(); i != a->uses().end(); ++i) { - if (b == *i) return true; + // Checks one-step reduction of a phi. + void ReducePhi(Node* expect, Node* phi) { + Node* result = ControlReducer::ReducePhiForTesting(&jsgraph, &common, phi); + CHECK_EQ(expect, result); + ReducePhiIterative(expect, phi); // iterative should give the same result. + } + + void ReducePhiIterative(Node* expect, Node* phi) { + p0->ReplaceInput(0, start); // hack: parameters may be trimmed. + Node* ret = graph.NewNode(common.Return(), phi, start, start); + Node* end = graph.NewNode(common.End(), ret); + graph.SetEnd(end); + ControlReducer::ReduceGraph(main_zone(), &jsgraph, &common); + CheckInputs(end, ret); + CheckInputs(ret, expect, start, start); + } + + void ReduceMerge(Node* expect, Node* merge) { + Node* result = + ControlReducer::ReduceMergeForTesting(&jsgraph, &common, merge); + CHECK_EQ(expect, result); + } + + void ReduceMergeIterative(Node* expect, Node* merge) { + p0->ReplaceInput(0, start); // hack: parameters may be trimmed. + Node* end = graph.NewNode(common.End(), merge); + graph.SetEnd(end); + ReduceGraph(); + CheckInputs(end, expect); } - return false; -} + + void ReduceBranch(Node* expect, Node* branch) { + Node* result = + ControlReducer::ReduceBranchForTesting(&jsgraph, &common, branch); + CHECK_EQ(expect, result); + } + + Node* Return(Node* val, Node* effect, Node* control) { + Node* ret = graph.NewNode(common.Return(), val, effect, control); + end->ReplaceInput(0, ret); + return ret; + } +}; TEST(Trim1_live) { - CTrimTester T; + ControlReducerTester T; CHECK(IsUsedBy(T.start, T.p0)); T.graph.SetEnd(T.p0); T.Trim(); CHECK(IsUsedBy(T.start, T.p0)); - CHECK_EQ(T.start, T.p0->InputAt(0)); + CheckInputs(T.p0, T.start); } TEST(Trim1_dead) { - CTrimTester T; + ControlReducerTester T; CHECK(IsUsedBy(T.start, T.p0)); T.Trim(); CHECK(!IsUsedBy(T.start, T.p0)); @@ -69,7 +214,7 @@ TEST(Trim1_dead) { TEST(Trim2_live) { - CTrimTester T; + ControlReducerTester T; Node* phi = T.graph.NewNode(T.common.Phi(kMachAnyTagged, 2), T.one, T.half, T.start); CHECK(IsUsedBy(T.one, phi)); @@ -80,14 +225,12 @@ TEST(Trim2_live) { CHECK(IsUsedBy(T.one, phi)); CHECK(IsUsedBy(T.half, phi)); CHECK(IsUsedBy(T.start, phi)); - CHECK_EQ(T.one, phi->InputAt(0)); - CHECK_EQ(T.half, phi->InputAt(1)); - CHECK_EQ(T.start, phi->InputAt(2)); + CheckInputs(phi, T.one, T.half, T.start); } TEST(Trim2_dead) { - CTrimTester T; + ControlReducerTester T; Node* phi = T.graph.NewNode(T.common.Phi(kMachAnyTagged, 2), T.one, T.half, T.start); CHECK(IsUsedBy(T.one, phi)); @@ -104,7 +247,7 @@ TEST(Trim2_dead) { TEST(Trim_chain1) { - CTrimTester T; + ControlReducerTester T; const int kDepth = 15; Node* live[kDepth]; Node* dead[kDepth]; @@ -126,7 +269,7 @@ TEST(Trim_chain1) { TEST(Trim_chain2) { - CTrimTester T; + ControlReducerTester T; const int kDepth = 15; Node* live[kDepth]; Node* dead[kDepth]; @@ -149,7 +292,7 @@ TEST(Trim_chain2) { TEST(Trim_cycle1) { - CTrimTester T; + ControlReducerTester T; Node* loop = T.graph.NewNode(T.common.Loop(1), T.start, T.start); loop->ReplaceInput(1, loop); Node* end = T.graph.NewNode(T.common.End(), loop); @@ -165,14 +308,13 @@ TEST(Trim_cycle1) { CHECK(IsUsedBy(T.start, loop)); CHECK(IsUsedBy(loop, end)); CHECK(IsUsedBy(loop, loop)); - CHECK_EQ(T.start, loop->InputAt(0)); - CHECK_EQ(loop, loop->InputAt(1)); - CHECK_EQ(loop, end->InputAt(0)); + CheckInputs(loop, T.start, loop); + CheckInputs(end, loop); } TEST(Trim_cycle2) { - CTrimTester T; + ControlReducerTester T; Node* loop = T.graph.NewNode(T.common.Loop(2), T.start, T.start); loop->ReplaceInput(1, loop); Node* end = T.graph.NewNode(T.common.End(), loop); @@ -193,9 +335,8 @@ TEST(Trim_cycle2) { CHECK(IsUsedBy(T.start, loop)); CHECK(IsUsedBy(loop, end)); CHECK(IsUsedBy(loop, loop)); - CHECK_EQ(T.start, loop->InputAt(0)); - CHECK_EQ(loop, loop->InputAt(1)); - CHECK_EQ(loop, end->InputAt(0)); + CheckInputs(loop, T.start, loop); + CheckInputs(end, loop); // phi should have been trimmed away. CHECK(!IsUsedBy(loop, phi)); @@ -207,7 +348,7 @@ TEST(Trim_cycle2) { } -void CheckTrimConstant(CTrimTester* T, Node* k) { +void CheckTrimConstant(ControlReducerTester* T, Node* k) { Node* phi = T->graph.NewNode(T->common.Phi(kMachInt32, 1), k, T->start); CHECK(IsUsedBy(k, phi)); T->Trim(); @@ -218,7 +359,7 @@ void CheckTrimConstant(CTrimTester* T, Node* k) { TEST(Trim_constants) { - CTrimTester T; + ControlReducerTester T; int32_t int32_constants[] = { 0, -1, -2, 2, 2, 3, 3, 4, 4, 5, 5, 4, 5, 6, 6, 7, 8, 7, 8, 9, 0, -11, -12, 12, 12, 13, 13, 14, 14, 15, 15, 14, 15, 6, 6, 7, 8, 7, 8, 9}; @@ -240,3 +381,1300 @@ TEST(Trim_constants) { CheckTrimConstant(&T, other_constants[i]); } } + + +TEST(CReducePhi1) { + ControlReducerTester R; + + R.ReducePhi(R.leaf[0], R.Phi(R.leaf[0])); + R.ReducePhi(R.leaf[1], R.Phi(R.leaf[1])); + R.ReducePhi(R.leaf[2], R.Phi(R.leaf[2])); + R.ReducePhi(R.leaf[3], R.Phi(R.leaf[3])); +} + + +TEST(CReducePhi1_dead) { + ControlReducerTester R; + + R.ReducePhi(R.leaf[0], R.Phi(R.leaf[0], R.dead)); + R.ReducePhi(R.leaf[1], R.Phi(R.leaf[1], R.dead)); + R.ReducePhi(R.leaf[2], R.Phi(R.leaf[2], R.dead)); + R.ReducePhi(R.leaf[3], R.Phi(R.leaf[3], R.dead)); + + R.ReducePhi(R.leaf[0], R.Phi(R.dead, R.leaf[0])); + R.ReducePhi(R.leaf[1], R.Phi(R.dead, R.leaf[1])); + R.ReducePhi(R.leaf[2], R.Phi(R.dead, R.leaf[2])); + R.ReducePhi(R.leaf[3], R.Phi(R.dead, R.leaf[3])); +} + + +TEST(CReducePhi1_dead2) { + ControlReducerTester R; + + R.ReducePhi(R.leaf[0], R.Phi(R.leaf[0], R.dead, R.dead)); + R.ReducePhi(R.leaf[0], R.Phi(R.dead, R.leaf[0], R.dead)); + R.ReducePhi(R.leaf[0], R.Phi(R.dead, R.dead, R.leaf[0])); +} + + +TEST(CReducePhi2a) { + ControlReducerTester R; + + for (size_t i = 0; i < kNumLeafs; i++) { + Node* a = R.leaf[i]; + R.ReducePhi(a, R.Phi(a, a)); + } +} + + +TEST(CReducePhi2b) { + ControlReducerTester R; + + for (size_t i = 0; i < kNumLeafs; i++) { + Node* a = R.leaf[i]; + R.ReducePhi(a, R.Phi(R.self, a)); + R.ReducePhi(a, R.Phi(a, R.self)); + } +} + + +TEST(CReducePhi2c) { + ControlReducerTester R; + + for (size_t i = 1; i < kNumLeafs; i++) { + Node* a = R.leaf[i], *b = R.leaf[0]; + Node* phi1 = R.Phi(b, a); + R.ReducePhi(phi1, phi1); + + Node* phi2 = R.Phi(a, b); + R.ReducePhi(phi2, phi2); + } +} + + +TEST(CReducePhi2_dead) { + ControlReducerTester R; + + for (size_t i = 0; i < kNumLeafs; i++) { + Node* a = R.leaf[i]; + R.ReducePhi(a, R.Phi(a, a, R.dead)); + R.ReducePhi(a, R.Phi(a, R.dead, a)); + R.ReducePhi(a, R.Phi(R.dead, a, a)); + } + + for (size_t i = 0; i < kNumLeafs; i++) { + Node* a = R.leaf[i]; + R.ReducePhi(a, R.Phi(R.self, a)); + R.ReducePhi(a, R.Phi(a, R.self)); + R.ReducePhi(a, R.Phi(R.self, a, R.dead)); + R.ReducePhi(a, R.Phi(a, R.self, R.dead)); + } + + for (size_t i = 1; i < kNumLeafs; i++) { + Node* a = R.leaf[i], *b = R.leaf[0]; + Node* phi1 = R.Phi(b, a, R.dead); + R.ReducePhi(phi1, phi1); + + Node* phi2 = R.Phi(a, b, R.dead); + R.ReducePhi(phi2, phi2); + } +} + + +TEST(CReducePhi3) { + ControlReducerTester R; + + for (size_t i = 0; i < kNumLeafs; i++) { + Node* a = R.leaf[i]; + R.ReducePhi(a, R.Phi(a, a, a)); + } + + for (size_t i = 0; i < kNumLeafs; i++) { + Node* a = R.leaf[i]; + R.ReducePhi(a, R.Phi(R.self, a, a)); + R.ReducePhi(a, R.Phi(a, R.self, a)); + R.ReducePhi(a, R.Phi(a, a, R.self)); + } + + for (size_t i = 1; i < kNumLeafs; i++) { + Node* a = R.leaf[i], *b = R.leaf[0]; + Node* phi1 = R.Phi(b, a, a); + R.ReducePhi(phi1, phi1); + + Node* phi2 = R.Phi(a, b, a); + R.ReducePhi(phi2, phi2); + + Node* phi3 = R.Phi(a, a, b); + R.ReducePhi(phi3, phi3); + } +} + + +TEST(CReducePhi4) { + ControlReducerTester R; + + for (size_t i = 0; i < kNumLeafs; i++) { + Node* a = R.leaf[i]; + R.ReducePhi(a, R.Phi(a, a, a, a)); + } + + for (size_t i = 0; i < kNumLeafs; i++) { + Node* a = R.leaf[i]; + R.ReducePhi(a, R.Phi(R.self, a, a, a)); + R.ReducePhi(a, R.Phi(a, R.self, a, a)); + R.ReducePhi(a, R.Phi(a, a, R.self, a)); + R.ReducePhi(a, R.Phi(a, a, a, R.self)); + + R.ReducePhi(a, R.Phi(R.self, R.self, a, a)); + R.ReducePhi(a, R.Phi(a, R.self, R.self, a)); + R.ReducePhi(a, R.Phi(a, a, R.self, R.self)); + R.ReducePhi(a, R.Phi(R.self, a, a, R.self)); + } + + for (size_t i = 1; i < kNumLeafs; i++) { + Node* a = R.leaf[i], *b = R.leaf[0]; + Node* phi1 = R.Phi(b, a, a, a); + R.ReducePhi(phi1, phi1); + + Node* phi2 = R.Phi(a, b, a, a); + R.ReducePhi(phi2, phi2); + + Node* phi3 = R.Phi(a, a, b, a); + R.ReducePhi(phi3, phi3); + + Node* phi4 = R.Phi(a, a, a, b); + R.ReducePhi(phi4, phi4); + } +} + + +TEST(CReducePhi_iterative1) { + ControlReducerTester R; + + R.ReducePhiIterative(R.leaf[0], R.Phi(R.leaf[0], R.Phi(R.leaf[0]))); + R.ReducePhiIterative(R.leaf[0], R.Phi(R.Phi(R.leaf[0]), R.leaf[0])); +} + + +TEST(CReducePhi_iterative2) { + ControlReducerTester R; + + R.ReducePhiIterative(R.leaf[0], R.Phi(R.Phi(R.leaf[0]), R.Phi(R.leaf[0]))); +} + + +TEST(CReducePhi_iterative3) { + ControlReducerTester R; + + R.ReducePhiIterative(R.leaf[0], + R.Phi(R.leaf[0], R.Phi(R.leaf[0], R.leaf[0]))); + R.ReducePhiIterative(R.leaf[0], + R.Phi(R.Phi(R.leaf[0], R.leaf[0]), R.leaf[0])); +} + + +TEST(CReducePhi_iterative4) { + ControlReducerTester R; + + R.ReducePhiIterative(R.leaf[0], R.Phi(R.Phi(R.leaf[0], R.leaf[0]), + R.Phi(R.leaf[0], R.leaf[0]))); + + Node* p1 = R.Phi(R.leaf[0], R.leaf[0]); + R.ReducePhiIterative(R.leaf[0], R.Phi(p1, p1)); + + Node* p2 = R.Phi(R.leaf[0], R.leaf[0], R.leaf[0]); + R.ReducePhiIterative(R.leaf[0], R.Phi(p2, p2, p2)); + + Node* p3 = R.Phi(R.leaf[0], R.leaf[0], R.leaf[0]); + R.ReducePhiIterative(R.leaf[0], R.Phi(p3, p3, R.leaf[0])); +} + + +TEST(CReducePhi_iterative_self1) { + ControlReducerTester R; + + R.ReducePhiIterative(R.leaf[0], R.Phi(R.leaf[0], R.Phi(R.leaf[0], R.self))); + R.ReducePhiIterative(R.leaf[0], R.Phi(R.Phi(R.leaf[0], R.self), R.leaf[0])); +} + + +TEST(CReducePhi_iterative_self2) { + ControlReducerTester R; + + R.ReducePhiIterative( + R.leaf[0], R.Phi(R.Phi(R.leaf[0], R.self), R.Phi(R.leaf[0], R.self))); + R.ReducePhiIterative( + R.leaf[0], R.Phi(R.Phi(R.self, R.leaf[0]), R.Phi(R.self, R.leaf[0]))); + + Node* p1 = R.Phi(R.leaf[0], R.self); + R.ReducePhiIterative(R.leaf[0], R.Phi(p1, p1)); + + Node* p2 = R.Phi(R.self, R.leaf[0]); + R.ReducePhiIterative(R.leaf[0], R.Phi(p2, p2)); +} + + +TEST(EReducePhi1) { + ControlReducerTester R; + + R.ReducePhi(R.leaf[0], R.EffectPhi(R.leaf[0])); + R.ReducePhi(R.leaf[1], R.EffectPhi(R.leaf[1])); + R.ReducePhi(R.leaf[2], R.EffectPhi(R.leaf[2])); + R.ReducePhi(R.leaf[3], R.EffectPhi(R.leaf[3])); +} + + +TEST(EReducePhi1_dead) { + ControlReducerTester R; + + R.ReducePhi(R.leaf[0], R.EffectPhi(R.leaf[0], R.dead)); + R.ReducePhi(R.leaf[1], R.EffectPhi(R.leaf[1], R.dead)); + R.ReducePhi(R.leaf[2], R.EffectPhi(R.leaf[2], R.dead)); + R.ReducePhi(R.leaf[3], R.EffectPhi(R.leaf[3], R.dead)); + + R.ReducePhi(R.leaf[0], R.EffectPhi(R.dead, R.leaf[0])); + R.ReducePhi(R.leaf[1], R.EffectPhi(R.dead, R.leaf[1])); + R.ReducePhi(R.leaf[2], R.EffectPhi(R.dead, R.leaf[2])); + R.ReducePhi(R.leaf[3], R.EffectPhi(R.dead, R.leaf[3])); +} + + +TEST(EReducePhi1_dead2) { + ControlReducerTester R; + + R.ReducePhi(R.leaf[0], R.EffectPhi(R.leaf[0], R.dead, R.dead)); + R.ReducePhi(R.leaf[0], R.EffectPhi(R.dead, R.leaf[0], R.dead)); + R.ReducePhi(R.leaf[0], R.EffectPhi(R.dead, R.dead, R.leaf[0])); +} + + +TEST(CMergeReduce_simple1) { + ControlReducerTester R; + + Node* merge = R.graph.NewNode(R.common.Merge(1), R.start); + R.ReduceMerge(R.start, merge); +} + + +TEST(CMergeReduce_simple2) { + ControlReducerTester R; + + Node* merge1 = R.graph.NewNode(R.common.Merge(1), R.start); + Node* merge2 = R.graph.NewNode(R.common.Merge(1), merge1); + R.ReduceMerge(merge1, merge2); + R.ReduceMergeIterative(R.start, merge2); +} + + +TEST(CMergeReduce_none1) { + ControlReducerTester R; + + Node* merge = R.graph.NewNode(R.common.Merge(2), R.start, R.start); + R.ReduceMerge(merge, merge); +} + + +TEST(CMergeReduce_none2) { + ControlReducerTester R; + + Node* t = R.graph.NewNode(R.common.IfTrue(), R.start); + Node* f = R.graph.NewNode(R.common.IfFalse(), R.start); + Node* merge = R.graph.NewNode(R.common.Merge(2), t, f); + R.ReduceMerge(merge, merge); +} + + +TEST(CMergeReduce_self3) { + ControlReducerTester R; + + Node* merge = + R.SetSelfReferences(R.graph.NewNode(R.common.Merge(2), R.start, R.self)); + R.ReduceMerge(merge, merge); +} + + +TEST(CMergeReduce_dead1) { + ControlReducerTester R; + + Node* merge = R.graph.NewNode(R.common.Merge(2), R.start, R.dead); + R.ReduceMerge(R.start, merge); +} + + +TEST(CMergeReduce_dead2) { + ControlReducerTester R; + + Node* merge1 = R.graph.NewNode(R.common.Merge(1), R.start); + Node* merge2 = R.graph.NewNode(R.common.Merge(2), merge1, R.dead); + R.ReduceMerge(merge1, merge2); + R.ReduceMergeIterative(R.start, merge2); +} + + +TEST(CMergeReduce_dead_rm1a) { + ControlReducerTester R; + + for (int i = 0; i < 3; i++) { + Node* merge = R.graph.NewNode(R.common.Merge(3), R.start, R.start, R.start); + merge->ReplaceInput(i, R.dead); + R.ReduceMerge(merge, merge); + CheckMerge(merge, R.start, R.start); + } +} + + +TEST(CMergeReduce_dead_rm1b) { + ControlReducerTester R; + + Node* t = R.graph.NewNode(R.common.IfTrue(), R.start); + Node* f = R.graph.NewNode(R.common.IfFalse(), R.start); + for (int i = 0; i < 2; i++) { + Node* merge = R.graph.NewNode(R.common.Merge(3), R.dead, R.dead, R.dead); + for (int j = i + 1; j < 3; j++) { + merge->ReplaceInput(i, t); + merge->ReplaceInput(j, f); + R.ReduceMerge(merge, merge); + CheckMerge(merge, t, f); + } + } +} + + +TEST(CMergeReduce_dead_rm2) { + ControlReducerTester R; + + for (int i = 0; i < 3; i++) { + Node* merge = R.graph.NewNode(R.common.Merge(3), R.dead, R.dead, R.dead); + merge->ReplaceInput(i, R.start); + R.ReduceMerge(R.start, merge); + } +} + + +TEST(CLoopReduce_dead_rm1) { + ControlReducerTester R; + + for (int i = 0; i < 3; i++) { + Node* loop = R.graph.NewNode(R.common.Loop(3), R.dead, R.start, R.start); + R.ReduceMerge(loop, loop); + CheckLoop(loop, R.start, R.start); + } +} + + +TEST(CMergeReduce_edit_phi1) { + ControlReducerTester R; + + for (int i = 0; i < 3; i++) { + Node* merge = R.graph.NewNode(R.common.Merge(3), R.start, R.start, R.start); + merge->ReplaceInput(i, R.dead); + Node* phi = R.graph.NewNode(R.common.Phi(kMachAnyTagged, 3), R.leaf[0], + R.leaf[1], R.leaf[2], merge); + R.ReduceMerge(merge, merge); + CHECK_EQ(IrOpcode::kPhi, phi->opcode()); + CHECK_EQ(2, phi->op()->InputCount()); + CHECK_EQ(3, phi->InputCount()); + CHECK_EQ(R.leaf[i < 1 ? 1 : 0], phi->InputAt(0)); + CHECK_EQ(R.leaf[i < 2 ? 2 : 1], phi->InputAt(1)); + CHECK_EQ(merge, phi->InputAt(2)); + } +} + + +TEST(CMergeReduce_edit_effect_phi1) { + ControlReducerTester R; + + for (int i = 0; i < 3; i++) { + Node* merge = R.graph.NewNode(R.common.Merge(3), R.start, R.start, R.start); + merge->ReplaceInput(i, R.dead); + Node* phi = R.graph.NewNode(R.common.EffectPhi(3), R.leaf[0], R.leaf[1], + R.leaf[2], merge); + R.ReduceMerge(merge, merge); + CHECK_EQ(IrOpcode::kEffectPhi, phi->opcode()); + CHECK_EQ(0, phi->op()->InputCount()); + CHECK_EQ(2, OperatorProperties::GetEffectInputCount(phi->op())); + CHECK_EQ(3, phi->InputCount()); + CHECK_EQ(R.leaf[i < 1 ? 1 : 0], phi->InputAt(0)); + CHECK_EQ(R.leaf[i < 2 ? 2 : 1], phi->InputAt(1)); + CHECK_EQ(merge, phi->InputAt(2)); + } +} + + +static const int kSelectorSize = 4; + +// Helper to select K of N nodes according to a mask, useful for the test below. +struct Selector { + int mask; + int count; + explicit Selector(int m) { + mask = m; + count = v8::base::bits::CountPopulation32(m); + } + bool is_selected(int i) { return (mask & (1 << i)) != 0; } + void CheckNode(Node* node, IrOpcode::Value opcode, Node** inputs, + Node* control) { + CHECK_EQ(opcode, node->opcode()); + CHECK_EQ(count + (control != NULL ? 1 : 0), node->InputCount()); + int index = 0; + for (int i = 0; i < kSelectorSize; i++) { + if (mask & (1 << i)) { + CHECK_EQ(inputs[i], node->InputAt(index++)); + } + } + CHECK_EQ(count, index); + if (control != NULL) CHECK_EQ(control, node->InputAt(index++)); + } + int single_index() { + CHECK_EQ(1, count); + return WhichPowerOf2(mask); + } +}; + + +TEST(CMergeReduce_exhaustive_4) { + ControlReducerTester R; + Node* controls[] = { + R.graph.NewNode(R.common.Start(1)), R.graph.NewNode(R.common.Start(2)), + R.graph.NewNode(R.common.Start(3)), R.graph.NewNode(R.common.Start(4))}; + Node* values[] = {R.jsgraph.Int32Constant(11), R.jsgraph.Int32Constant(22), + R.jsgraph.Int32Constant(33), R.jsgraph.Int32Constant(44)}; + Node* effects[] = { + R.jsgraph.Float64Constant(123.4), R.jsgraph.Float64Constant(223.4), + R.jsgraph.Float64Constant(323.4), R.jsgraph.Float64Constant(423.4)}; + + for (int mask = 0; mask < (1 << (kSelectorSize - 1)); mask++) { + // Reduce a single merge with a given mask. + Node* merge = R.graph.NewNode(R.common.Merge(4), controls[0], controls[1], + controls[2], controls[3]); + Node* phi = R.graph.NewNode(R.common.Phi(kMachAnyTagged, 4), values[0], + values[1], values[2], values[3], merge); + Node* ephi = R.graph.NewNode(R.common.EffectPhi(4), effects[0], effects[1], + effects[2], effects[3], merge); + + Node* phi_use = + R.graph.NewNode(R.common.Phi(kMachAnyTagged, 1), phi, R.start); + Node* ephi_use = R.graph.NewNode(R.common.EffectPhi(1), ephi, R.start); + + Selector selector(mask); + + for (int i = 0; i < kSelectorSize; i++) { // set up dead merge inputs. + if (!selector.is_selected(i)) merge->ReplaceInput(i, R.dead); + } + + Node* result = + ControlReducer::ReduceMergeForTesting(&R.jsgraph, &R.common, merge); + + int count = selector.count; + if (count == 0) { + // result should be dead. + CHECK_EQ(IrOpcode::kDead, result->opcode()); + } else if (count == 1) { + // merge should be replaced with one of the controls. + CHECK_EQ(controls[selector.single_index()], result); + // Phis should have been directly replaced. + CHECK_EQ(values[selector.single_index()], phi_use->InputAt(0)); + CHECK_EQ(effects[selector.single_index()], ephi_use->InputAt(0)); + } else { + // Otherwise, nodes should be edited in place. + CHECK_EQ(merge, result); + selector.CheckNode(merge, IrOpcode::kMerge, controls, NULL); + selector.CheckNode(phi, IrOpcode::kPhi, values, merge); + selector.CheckNode(ephi, IrOpcode::kEffectPhi, effects, merge); + CHECK_EQ(phi, phi_use->InputAt(0)); + CHECK_EQ(ephi, ephi_use->InputAt(0)); + CHECK_EQ(count, phi->op()->InputCount()); + CHECK_EQ(count + 1, phi->InputCount()); + CHECK_EQ(count, OperatorProperties::GetEffectInputCount(ephi->op())); + CHECK_EQ(count + 1, ephi->InputCount()); + } + } +} + + +TEST(CMergeReduce_edit_many_phis1) { + ControlReducerTester R; + + const int kPhiCount = 10; + Node* phis[kPhiCount]; + + for (int i = 0; i < 3; i++) { + Node* merge = R.graph.NewNode(R.common.Merge(3), R.start, R.start, R.start); + merge->ReplaceInput(i, R.dead); + for (int j = 0; j < kPhiCount; j++) { + phis[j] = R.graph.NewNode(R.common.Phi(kMachAnyTagged, 3), R.leaf[0], + R.leaf[1], R.leaf[2], merge); + } + R.ReduceMerge(merge, merge); + for (int j = 0; j < kPhiCount; j++) { + Node* phi = phis[j]; + CHECK_EQ(IrOpcode::kPhi, phi->opcode()); + CHECK_EQ(2, phi->op()->InputCount()); + CHECK_EQ(3, phi->InputCount()); + CHECK_EQ(R.leaf[i < 1 ? 1 : 0], phi->InputAt(0)); + CHECK_EQ(R.leaf[i < 2 ? 2 : 1], phi->InputAt(1)); + CHECK_EQ(merge, phi->InputAt(2)); + } + } +} + + +TEST(CMergeReduce_simple_chain1) { + ControlReducerTester R; + for (int i = 0; i < 5; i++) { + Node* merge = R.graph.NewNode(R.common.Merge(1), R.start); + for (int j = 0; j < i; j++) { + merge = R.graph.NewNode(R.common.Merge(1), merge); + } + R.ReduceMergeIterative(R.start, merge); + } +} + + +TEST(CMergeReduce_dead_chain1) { + ControlReducerTester R; + for (int i = 0; i < 5; i++) { + Node* merge = R.graph.NewNode(R.common.Merge(1), R.dead); + for (int j = 0; j < i; j++) { + merge = R.graph.NewNode(R.common.Merge(1), merge); + } + Node* end = R.graph.NewNode(R.common.End(), merge); + R.graph.SetEnd(end); + R.ReduceGraph(); + CHECK(merge->IsDead()); + CHECK_EQ(NULL, end->InputAt(0)); // end dies. + } +} + + +TEST(CMergeReduce_dead_chain2) { + ControlReducerTester R; + for (int i = 0; i < 5; i++) { + Node* merge = R.graph.NewNode(R.common.Merge(1), R.start); + for (int j = 0; j < i; j++) { + merge = R.graph.NewNode(R.common.Merge(2), merge, R.dead); + } + R.ReduceMergeIterative(R.start, merge); + } +} + + +struct Branch { + Node* branch; + Node* if_true; + Node* if_false; + + Branch(ControlReducerTester& R, Node* cond, Node* control = NULL) { + if (control == NULL) control = R.start; + branch = R.graph.NewNode(R.common.Branch(), cond, control); + if_true = R.graph.NewNode(R.common.IfTrue(), branch); + if_false = R.graph.NewNode(R.common.IfFalse(), branch); + } +}; + + +struct Diamond { + Node* branch; + Node* if_true; + Node* if_false; + Node* merge; + Node* phi; + + Diamond(ControlReducerTester& R, Node* cond) { + branch = R.graph.NewNode(R.common.Branch(), cond, R.start); + if_true = R.graph.NewNode(R.common.IfTrue(), branch); + if_false = R.graph.NewNode(R.common.IfFalse(), branch); + merge = R.graph.NewNode(R.common.Merge(2), if_true, if_false); + phi = NULL; + } + + Diamond(ControlReducerTester& R, Node* cond, Node* tv, Node* fv) { + branch = R.graph.NewNode(R.common.Branch(), cond, R.start); + if_true = R.graph.NewNode(R.common.IfTrue(), branch); + if_false = R.graph.NewNode(R.common.IfFalse(), branch); + merge = R.graph.NewNode(R.common.Merge(2), if_true, if_false); + phi = R.graph.NewNode(R.common.Phi(kMachAnyTagged, 2), tv, fv, merge); + } + + void chain(Diamond& that) { branch->ReplaceInput(1, that.merge); } + + // Nest {this} into either the if_true or if_false branch of {that}. + void nest(Diamond& that, bool if_true) { + if (if_true) { + branch->ReplaceInput(1, that.if_true); + that.merge->ReplaceInput(0, merge); + } else { + branch->ReplaceInput(1, that.if_false); + that.merge->ReplaceInput(1, merge); + } + } +}; + + +struct While { + Node* branch; + Node* if_true; + Node* exit; + Node* loop; + + While(ControlReducerTester& R, Node* cond) { + loop = R.graph.NewNode(R.common.Loop(2), R.start, R.start); + branch = R.graph.NewNode(R.common.Branch(), cond, loop); + if_true = R.graph.NewNode(R.common.IfTrue(), branch); + exit = R.graph.NewNode(R.common.IfFalse(), branch); + loop->ReplaceInput(1, if_true); + } + + void chain(Node* control) { loop->ReplaceInput(0, control); } +}; + + +TEST(CBranchReduce_none1) { + ControlReducerTester R; + Diamond d(R, R.p0); + R.ReduceBranch(d.branch, d.branch); +} + + +TEST(CBranchReduce_none2) { + ControlReducerTester R; + Diamond d1(R, R.p0); + Diamond d2(R, R.p0); + d2.chain(d1); + R.ReduceBranch(d2.branch, d2.branch); +} + + +TEST(CBranchReduce_true) { + ControlReducerTester R; + Node* true_values[] = { + R.one, R.jsgraph.Int32Constant(2), + R.jsgraph.Int32Constant(0x7fffffff), R.jsgraph.Constant(1.0), + R.jsgraph.Constant(22.1), R.jsgraph.TrueConstant()}; + + for (size_t i = 0; i < arraysize(true_values); i++) { + Diamond d(R, true_values[i]); + Node* true_use = R.graph.NewNode(R.common.Merge(1), d.if_true); + Node* false_use = R.graph.NewNode(R.common.Merge(1), d.if_false); + R.ReduceBranch(R.start, d.branch); + CHECK_EQ(R.start, true_use->InputAt(0)); + CHECK_EQ(IrOpcode::kDead, false_use->InputAt(0)->opcode()); + CHECK(d.if_true->IsDead()); // replaced + CHECK(d.if_false->IsDead()); // replaced + } +} + + +TEST(CBranchReduce_false) { + ControlReducerTester R; + Node* false_values[] = {R.zero, R.jsgraph.Constant(0.0), + R.jsgraph.Constant(-0.0), R.jsgraph.FalseConstant()}; + + for (size_t i = 0; i < arraysize(false_values); i++) { + Diamond d(R, false_values[i]); + Node* true_use = R.graph.NewNode(R.common.Merge(1), d.if_true); + Node* false_use = R.graph.NewNode(R.common.Merge(1), d.if_false); + R.ReduceBranch(R.start, d.branch); + CHECK_EQ(R.start, false_use->InputAt(0)); + CHECK_EQ(IrOpcode::kDead, true_use->InputAt(0)->opcode()); + CHECK(d.if_true->IsDead()); // replaced + CHECK(d.if_false->IsDead()); // replaced + } +} + + +TEST(CDiamondReduce_true) { + ControlReducerTester R; + Diamond d1(R, R.one); + R.ReduceMergeIterative(R.start, d1.merge); +} + + +TEST(CDiamondReduce_false) { + ControlReducerTester R; + Diamond d2(R, R.zero); + R.ReduceMergeIterative(R.start, d2.merge); +} + + +TEST(CChainedDiamondsReduce_true_false) { + ControlReducerTester R; + Diamond d1(R, R.one); + Diamond d2(R, R.zero); + d2.chain(d1); + + R.ReduceMergeIterative(R.start, d2.merge); +} + + +TEST(CChainedDiamondsReduce_x_false) { + ControlReducerTester R; + Diamond d1(R, R.p0); + Diamond d2(R, R.zero); + d2.chain(d1); + + R.ReduceMergeIterative(d1.merge, d2.merge); +} + + +TEST(CChainedDiamondsReduce_false_x) { + ControlReducerTester R; + Diamond d1(R, R.zero); + Diamond d2(R, R.p0); + d2.chain(d1); + + R.ReduceMergeIterative(d2.merge, d2.merge); + CheckInputs(d2.branch, R.p0, R.start); +} + + +TEST(CChainedDiamondsReduce_phi1) { + ControlReducerTester R; + Diamond d1(R, R.zero, R.one, R.zero); // foldable branch, phi. + Diamond d2(R, d1.phi); + d2.chain(d1); + + R.ReduceMergeIterative(R.start, d2.merge); +} + + +TEST(CChainedDiamondsReduce_phi2) { + ControlReducerTester R; + Diamond d1(R, R.p0, R.one, R.one); // redundant phi. + Diamond d2(R, d1.phi); + d2.chain(d1); + + R.ReduceMergeIterative(d1.merge, d2.merge); +} + + +TEST(CNestedDiamondsReduce_true_true_false) { + ControlReducerTester R; + Diamond d1(R, R.one); + Diamond d2(R, R.zero); + d2.nest(d1, true); + + R.ReduceMergeIterative(R.start, d1.merge); +} + + +TEST(CNestedDiamondsReduce_false_true_false) { + ControlReducerTester R; + Diamond d1(R, R.one); + Diamond d2(R, R.zero); + d2.nest(d1, false); + + R.ReduceMergeIterative(R.start, d1.merge); +} + + +TEST(CNestedDiamonds_xyz) { + ControlReducerTester R; + + for (int a = 0; a < 2; a++) { + for (int b = 0; b < 2; b++) { + for (int c = 0; c < 2; c++) { + Diamond d1(R, R.jsgraph.Int32Constant(a)); + Diamond d2(R, R.jsgraph.Int32Constant(b)); + d2.nest(d1, c); + + R.ReduceMergeIterative(R.start, d1.merge); + } + } + } +} + + +TEST(CDeadLoop1) { + ControlReducerTester R; + + Node* loop = R.graph.NewNode(R.common.Loop(1), R.start); + Branch b(R, R.p0, loop); + loop->ReplaceInput(0, b.if_true); // loop is not connected to start. + Node* merge = R.graph.NewNode(R.common.Merge(2), R.start, b.if_false); + R.ReduceMergeIterative(R.start, merge); + CHECK(b.if_true->IsDead()); + CHECK(b.if_false->IsDead()); +} + + +TEST(CDeadLoop2) { + ControlReducerTester R; + + While w(R, R.p0); + Diamond d(R, R.zero); + // if (0) { while (p0) ; } else { } + w.branch->ReplaceInput(1, d.if_true); + d.merge->ReplaceInput(0, w.exit); + + R.ReduceMergeIterative(R.start, d.merge); + CHECK(d.if_true->IsDead()); + CHECK(d.if_false->IsDead()); +} + + +TEST(CNonTermLoop1) { + ControlReducerTester R; + Node* loop = + R.SetSelfReferences(R.graph.NewNode(R.common.Loop(2), R.start, R.self)); + R.ReduceGraph(); + Node* end = R.graph.end(); + CheckLoop(loop, R.start, loop); + Node* merge = end->InputAt(0); + CheckMerge(merge, R.start, loop); +} + + +TEST(CNonTermLoop2) { + ControlReducerTester R; + Diamond d(R, R.p0); + Node* loop = R.SetSelfReferences( + R.graph.NewNode(R.common.Loop(2), d.if_false, R.self)); + d.merge->ReplaceInput(1, R.dead); + Node* end = R.graph.end(); + end->ReplaceInput(0, d.merge); + R.ReduceGraph(); + CHECK_EQ(end, R.graph.end()); + CheckLoop(loop, d.if_false, loop); + Node* merge = end->InputAt(0); + CheckMerge(merge, d.if_true, loop); +} + + +TEST(NonTermLoop3) { + ControlReducerTester R; + Node* loop = R.graph.NewNode(R.common.Loop(2), R.start, R.start); + Branch b(R, R.one, loop); + loop->ReplaceInput(1, b.if_true); + Node* end = R.graph.end(); + end->ReplaceInput(0, b.if_false); + + R.ReduceGraph(); + + CHECK_EQ(end, R.graph.end()); + CheckInputs(end, loop); + CheckInputs(loop, R.start, loop); +} + + +TEST(CNonTermLoop_terminate1) { + ControlReducerTester R; + Node* loop = R.graph.NewNode(R.common.Loop(2), R.start, R.start); + Node* effect = R.SetSelfReferences( + R.graph.NewNode(R.common.EffectPhi(2), R.start, R.self, loop)); + Branch b(R, R.one, loop); + loop->ReplaceInput(1, b.if_true); + Node* end = R.graph.end(); + end->ReplaceInput(0, b.if_false); + + R.ReduceGraph(); + + CHECK_EQ(end, R.graph.end()); + CheckLoop(loop, R.start, loop); + Node* terminate = end->InputAt(0); + CHECK_EQ(IrOpcode::kTerminate, terminate->opcode()); + CHECK_EQ(2, terminate->InputCount()); + CHECK_EQ(1, OperatorProperties::GetEffectInputCount(terminate->op())); + CHECK_EQ(1, OperatorProperties::GetControlInputCount(terminate->op())); + CheckInputs(terminate, effect, loop); +} + + +TEST(CNonTermLoop_terminate2) { + ControlReducerTester R; + Node* loop = R.graph.NewNode(R.common.Loop(2), R.start, R.start); + Node* effect1 = R.SetSelfReferences( + R.graph.NewNode(R.common.EffectPhi(2), R.start, R.self, loop)); + Node* effect2 = R.SetSelfReferences( + R.graph.NewNode(R.common.EffectPhi(2), R.start, R.self, loop)); + Branch b(R, R.one, loop); + loop->ReplaceInput(1, b.if_true); + Node* end = R.graph.end(); + end->ReplaceInput(0, b.if_false); + + R.ReduceGraph(); + + CheckLoop(loop, R.start, loop); + CHECK_EQ(end, R.graph.end()); + Node* terminate = end->InputAt(0); + CHECK_EQ(IrOpcode::kTerminate, terminate->opcode()); + CHECK_EQ(3, terminate->InputCount()); + CHECK_EQ(2, OperatorProperties::GetEffectInputCount(terminate->op())); + CHECK_EQ(1, OperatorProperties::GetControlInputCount(terminate->op())); + Node* e0 = terminate->InputAt(0); + Node* e1 = terminate->InputAt(1); + CHECK(e0 == effect1 || e1 == effect1); + CHECK(e0 == effect2 || e1 == effect2); + CHECK_EQ(loop, terminate->InputAt(2)); +} + + +TEST(CNonTermLoop_terminate_m1) { + ControlReducerTester R; + Node* loop = + R.SetSelfReferences(R.graph.NewNode(R.common.Loop(2), R.start, R.self)); + Node* effect = R.SetSelfReferences( + R.graph.NewNode(R.common.EffectPhi(2), R.start, R.self, loop)); + R.ReduceGraph(); + Node* end = R.graph.end(); + CHECK_EQ(R.start, loop->InputAt(0)); + CHECK_EQ(loop, loop->InputAt(1)); + Node* merge = end->InputAt(0); + CHECK_EQ(IrOpcode::kMerge, merge->opcode()); + CHECK_EQ(2, merge->InputCount()); + CHECK_EQ(2, OperatorProperties::GetControlInputCount(merge->op())); + CHECK_EQ(R.start, merge->InputAt(0)); + + Node* terminate = merge->InputAt(1); + CHECK_EQ(IrOpcode::kTerminate, terminate->opcode()); + CHECK_EQ(2, terminate->InputCount()); + CHECK_EQ(1, OperatorProperties::GetEffectInputCount(terminate->op())); + CHECK_EQ(1, OperatorProperties::GetControlInputCount(terminate->op())); + CHECK_EQ(effect, terminate->InputAt(0)); + CHECK_EQ(loop, terminate->InputAt(1)); +} + + +TEST(CNonTermLoop_big1) { + ControlReducerTester R; + Branch b1(R, R.p0); + Node* rt = R.graph.NewNode(R.common.Return(), R.one, R.start, b1.if_true); + + Branch b2(R, R.p0, b1.if_false); + Node* rf = R.graph.NewNode(R.common.Return(), R.zero, R.start, b2.if_true); + Node* loop = R.SetSelfReferences( + R.graph.NewNode(R.common.Loop(2), b2.if_false, R.self)); + Node* merge = R.graph.NewNode(R.common.Merge(2), rt, rf); + R.end->ReplaceInput(0, merge); + + R.ReduceGraph(); + + CheckInputs(R.end, merge); + CheckInputs(merge, rt, rf, loop); + CheckInputs(loop, b2.if_false, loop); +} + + +TEST(CNonTermLoop_big2) { + ControlReducerTester R; + Branch b1(R, R.p0); + Node* rt = R.graph.NewNode(R.common.Return(), R.one, R.start, b1.if_true); + + Branch b2(R, R.zero, b1.if_false); + Node* rf = R.graph.NewNode(R.common.Return(), R.zero, R.start, b2.if_true); + Node* loop = R.SetSelfReferences( + R.graph.NewNode(R.common.Loop(2), b2.if_false, R.self)); + Node* merge = R.graph.NewNode(R.common.Merge(2), rt, rf); + R.end->ReplaceInput(0, merge); + + R.ReduceGraph(); + + Node* new_merge = R.end->InputAt(0); // old merge was reduced. + CHECK_NE(merge, new_merge); + CheckInputs(new_merge, rt, loop); + CheckInputs(loop, b1.if_false, loop); + CHECK(merge->IsDead()); + CHECK(rf->IsDead()); + CHECK(b2.if_true->IsDead()); +} + + +TEST(Return1) { + ControlReducerTester R; + Node* ret = R.Return(R.one, R.start, R.start); + R.ReduceGraph(); + CheckInputs(R.graph.end(), ret); + CheckInputs(ret, R.one, R.start, R.start); +} + + +TEST(Return2) { + ControlReducerTester R; + Diamond d(R, R.one); + Node* ret = R.Return(R.half, R.start, d.merge); + R.ReduceGraph(); + CHECK(d.branch->IsDead()); + CHECK(d.if_true->IsDead()); + CHECK(d.if_false->IsDead()); + CHECK(d.merge->IsDead()); + + CheckInputs(R.graph.end(), ret); + CheckInputs(ret, R.half, R.start, R.start); +} + + +TEST(Return_true1) { + ControlReducerTester R; + Diamond d(R, R.one, R.half, R.zero); + Node* ret = R.Return(d.phi, R.start, d.merge); + R.ReduceGraph(); + CHECK(d.branch->IsDead()); + CHECK(d.if_true->IsDead()); + CHECK(d.if_false->IsDead()); + CHECK(d.merge->IsDead()); + CHECK(d.phi->IsDead()); + + CheckInputs(R.graph.end(), ret); + CheckInputs(ret, R.half, R.start, R.start); +} + + +TEST(Return_false1) { + ControlReducerTester R; + Diamond d(R, R.zero, R.one, R.half); + Node* ret = R.Return(d.phi, R.start, d.merge); + R.ReduceGraph(); + CHECK(d.branch->IsDead()); + CHECK(d.if_true->IsDead()); + CHECK(d.if_false->IsDead()); + CHECK(d.merge->IsDead()); + CHECK(d.phi->IsDead()); + + CheckInputs(R.graph.end(), ret); + CheckInputs(ret, R.half, R.start, R.start); +} + + +void CheckDeadDiamond(Diamond& d) { + CHECK(d.branch->IsDead()); + CHECK(d.if_true->IsDead()); + CHECK(d.if_false->IsDead()); + CHECK(d.merge->IsDead()); + if (d.phi != NULL) CHECK(d.phi->IsDead()); +} + + +void CheckLiveDiamond(Diamond& d, bool live_phi = true) { + CheckInputs(d.merge, d.if_true, d.if_false); + CheckInputs(d.if_true, d.branch); + CheckInputs(d.if_false, d.branch); + if (d.phi != NULL) { + if (live_phi) { + CHECK_EQ(3, d.phi->InputCount()); + CHECK_EQ(d.merge, d.phi->InputAt(2)); + } else { + CHECK(d.phi->IsDead()); + } + } +} + + +TEST(Return_effect1) { + ControlReducerTester R; + Diamond d(R, R.one); + Node* e1 = R.jsgraph.Float64Constant(-100.1); + Node* e2 = R.jsgraph.Float64Constant(+100.1); + Node* effect = R.graph.NewNode(R.common.EffectPhi(2), e1, e2, d.merge); + Node* ret = R.Return(R.p0, effect, d.merge); + R.ReduceGraph(); + CheckDeadDiamond(d); + CHECK(effect->IsDead()); + + CheckInputs(R.graph.end(), ret); + CheckInputs(ret, R.p0, e1, R.start); +} + + +TEST(Return_nested_diamonds1) { + ControlReducerTester R; + Diamond d1(R, R.p0, R.one, R.zero); + Diamond d2(R, R.p0); + Diamond d3(R, R.p0); + + d2.nest(d1, true); + d3.nest(d1, false); + + Node* ret = R.Return(d1.phi, R.start, d1.merge); + + R.ReduceGraph(); // nothing should happen. + + CheckInputs(ret, d1.phi, R.start, d1.merge); + CheckInputs(d1.phi, R.one, R.zero, d1.merge); + CheckInputs(d1.merge, d2.merge, d3.merge); + CheckLiveDiamond(d2); + CheckLiveDiamond(d3); +} + + +TEST(Return_nested_diamonds_true1) { + ControlReducerTester R; + Diamond d1(R, R.one, R.one, R.zero); + Diamond d2(R, R.p0); + Diamond d3(R, R.p0); + + d2.nest(d1, true); + d3.nest(d1, false); + + Node* ret = R.Return(d1.phi, R.start, d1.merge); + + R.ReduceGraph(); // d1 gets folded true. + + CheckInputs(ret, R.one, R.start, d2.merge); + CheckInputs(d2.branch, R.p0, R.start); + CheckDeadDiamond(d1); + CheckLiveDiamond(d2); + CheckDeadDiamond(d3); +} + + +TEST(Return_nested_diamonds_false1) { + ControlReducerTester R; + Diamond d1(R, R.zero, R.one, R.zero); + Diamond d2(R, R.p0); + Diamond d3(R, R.p0); + + d2.nest(d1, true); + d3.nest(d1, false); + + Node* ret = R.Return(d1.phi, R.start, d1.merge); + + R.ReduceGraph(); // d1 gets folded false. + + CheckInputs(ret, R.zero, R.start, d3.merge); + CheckInputs(d3.branch, R.p0, R.start); + CheckDeadDiamond(d1); + CheckDeadDiamond(d2); + CheckLiveDiamond(d3); +} + + +TEST(Return_nested_diamonds_true_true1) { + ControlReducerTester R; + Diamond d1(R, R.one, R.one, R.zero); + Diamond d2(R, R.one); + Diamond d3(R, R.p0); + + d2.nest(d1, true); + d3.nest(d1, false); + + Node* ret = R.Return(d1.phi, R.start, d1.merge); + + R.ReduceGraph(); // d1 and d2 both get folded true. + + CheckInputs(ret, R.one, R.start, R.start); + CheckDeadDiamond(d1); + CheckDeadDiamond(d2); + CheckDeadDiamond(d3); +} + + +TEST(Return_nested_diamonds_true_false1) { + ControlReducerTester R; + Diamond d1(R, R.one, R.one, R.zero); + Diamond d2(R, R.zero); + Diamond d3(R, R.p0); + + d2.nest(d1, true); + d3.nest(d1, false); + + Node* ret = R.Return(d1.phi, R.start, d1.merge); + + R.ReduceGraph(); // d1 gets folded true and d2 gets folded false. + + CheckInputs(ret, R.one, R.start, R.start); + CheckDeadDiamond(d1); + CheckDeadDiamond(d2); + CheckDeadDiamond(d3); +} + + +TEST(Return_nested_diamonds2) { + ControlReducerTester R; + Node* x2 = R.jsgraph.Float64Constant(11.1); + Node* y2 = R.jsgraph.Float64Constant(22.2); + Node* x3 = R.jsgraph.Float64Constant(33.3); + Node* y3 = R.jsgraph.Float64Constant(44.4); + + Diamond d2(R, R.p0, x2, y2); + Diamond d3(R, R.p0, x3, y3); + Diamond d1(R, R.p0, d2.phi, d3.phi); + + d2.nest(d1, true); + d3.nest(d1, false); + + Node* ret = R.Return(d1.phi, R.start, d1.merge); + + R.ReduceGraph(); // nothing should happen. + + CheckInputs(ret, d1.phi, R.start, d1.merge); + CheckInputs(d1.phi, d2.phi, d3.phi, d1.merge); + CheckInputs(d1.merge, d2.merge, d3.merge); + CheckLiveDiamond(d2); + CheckLiveDiamond(d3); +} + + +TEST(Return_nested_diamonds_true2) { + ControlReducerTester R; + Node* x2 = R.jsgraph.Float64Constant(11.1); + Node* y2 = R.jsgraph.Float64Constant(22.2); + Node* x3 = R.jsgraph.Float64Constant(33.3); + Node* y3 = R.jsgraph.Float64Constant(44.4); + + Diamond d2(R, R.p0, x2, y2); + Diamond d3(R, R.p0, x3, y3); + Diamond d1(R, R.one, d2.phi, d3.phi); + + d2.nest(d1, true); + d3.nest(d1, false); + + Node* ret = R.Return(d1.phi, R.start, d1.merge); + + R.ReduceGraph(); // d1 gets folded true. + + CheckInputs(ret, d2.phi, R.start, d2.merge); + CheckInputs(d2.branch, R.p0, R.start); + CheckDeadDiamond(d1); + CheckLiveDiamond(d2); + CheckDeadDiamond(d3); +} + + +TEST(Return_nested_diamonds_true_true2) { + ControlReducerTester R; + Node* x2 = R.jsgraph.Float64Constant(11.1); + Node* y2 = R.jsgraph.Float64Constant(22.2); + Node* x3 = R.jsgraph.Float64Constant(33.3); + Node* y3 = R.jsgraph.Float64Constant(44.4); + + Diamond d2(R, R.one, x2, y2); + Diamond d3(R, R.p0, x3, y3); + Diamond d1(R, R.one, d2.phi, d3.phi); + + d2.nest(d1, true); + d3.nest(d1, false); + + Node* ret = R.Return(d1.phi, R.start, d1.merge); + + R.ReduceGraph(); // d1 gets folded true. + + CheckInputs(ret, x2, R.start, R.start); + CheckDeadDiamond(d1); + CheckDeadDiamond(d2); + CheckDeadDiamond(d3); +} + + +TEST(Return_nested_diamonds_true_false2) { + ControlReducerTester R; + Node* x2 = R.jsgraph.Float64Constant(11.1); + Node* y2 = R.jsgraph.Float64Constant(22.2); + Node* x3 = R.jsgraph.Float64Constant(33.3); + Node* y3 = R.jsgraph.Float64Constant(44.4); + + Diamond d2(R, R.zero, x2, y2); + Diamond d3(R, R.p0, x3, y3); + Diamond d1(R, R.one, d2.phi, d3.phi); + + d2.nest(d1, true); + d3.nest(d1, false); + + Node* ret = R.Return(d1.phi, R.start, d1.merge); + + R.ReduceGraph(); // d1 gets folded true. + + CheckInputs(ret, y2, R.start, R.start); + CheckDeadDiamond(d1); + CheckDeadDiamond(d2); + CheckDeadDiamond(d3); +} -- 2.7.4