Revision: 24891
Author: [email protected]
Date: Mon Oct 27 08:41:32 2014 UTC
Log: Implement control reducer, which reduces branches and phis
together in a single fixpoint.
[email protected]
BUG=
Review URL: https://codereview.chromium.org/665223006
https://code.google.com/p/v8/source/detail?r=24891
Modified:
/branches/bleeding_edge/src/compiler/control-reducer.cc
/branches/bleeding_edge/src/compiler/control-reducer.h
/branches/bleeding_edge/src/compiler/operator-properties-inl.h
/branches/bleeding_edge/src/compiler/scheduler.cc
/branches/bleeding_edge/test/cctest/compiler/test-control-reducer.cc
=======================================
--- /branches/bleeding_edge/src/compiler/control-reducer.cc Tue Oct 21
14:44:50 2014 UTC
+++ /branches/bleeding_edge/src/compiler/control-reducer.cc Mon Oct 27
08:41:32 2014 UTC
@@ -14,7 +14,8 @@
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 @@
ZoneDeque<Node*> 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<byte> 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<Node*> effects(zone_);
+ for (Node* const use : loop->uses()) {
+ if (use->opcode() == IrOpcode::kEffectPhi) effects.push_back(use);
+ }
+ int count = static_cast<int>(effects.size());
+ if (count > 0) {
+ Node** inputs = zone_->NewArray<Node*>(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,17 +222,45 @@
// 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<size_t>((*i)->id());
+ for (Node* const use : node->uses()) {
+ size_t id = static_cast<size_t>(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<int>(height), static_cast<int>(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) {
@@ -103,13 +278,223 @@
state_[node->id()] = kOnStack;
stack_.push_back(node);
}
+
+ void Pop() {
+ int pos = static_cast<int>(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<size_t>(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<Node*> 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> object =
+ HeapObjectMatcher<Object>(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<MachineType>(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 @@
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
=======================================
--- /branches/bleeding_edge/src/compiler/control-reducer.h Tue Oct 21
14:44:50 2014 UTC
+++ /branches/bleeding_edge/src/compiler/control-reducer.h Mon Oct 27
08:41:32 2014 UTC
@@ -11,6 +11,7 @@
class JSGraph;
class CommonOperatorBuilder;
+class Node;
class ControlReducer {
public:
@@ -20,6 +21,16 @@
// 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);
};
}
}
=======================================
--- /branches/bleeding_edge/src/compiler/operator-properties-inl.h Sun Oct
26 10:24:49 2014 UTC
+++ /branches/bleeding_edge/src/compiler/operator-properties-inl.h Mon Oct
27 08:41:32 2014 UTC
@@ -117,6 +117,7 @@
}
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 @@
#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<int>.
return OpParameter<int>(op);
default:
=======================================
--- /branches/bleeding_edge/src/compiler/scheduler.cc Fri Oct 24 13:57:32
2014 UTC
+++ /branches/bleeding_edge/src/compiler/scheduler.cc Mon Oct 27 08:41:32
2014 UTC
@@ -382,7 +382,8 @@
}
bool IsFinalMerge(Node* node) {
- return (node == scheduler_->graph_->end()->InputAt(0));
+ return (node->opcode() == IrOpcode::kMerge &&
+ node == scheduler_->graph_->end()->InputAt(0));
}
};
=======================================
--- /branches/bleeding_edge/test/cctest/compiler/test-control-reducer.cc
Tue Oct 21 14:44:50 2014 UTC
+++ /branches/bleeding_edge/test/cctest/compiler/test-control-reducer.cc
Mon Oct 27 08:41:32 2014 UTC
@@ -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 @@
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.
}
- return false;
-}
+ 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);
+ }
+
+ 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(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 @@
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(Trim_chain1) {
- CTrimTester T;
+ ControlReducerTester T;
const int kDepth = 15;
Node* live[kDepth];
Node* dead[kDepth];
@@ -126,7 +269,7 @@
TEST(Trim_chain2) {
- CTrimTester T;
+ ControlReducerTester T;
const int kDepth = 15;
Node* live[kDepth];
Node* dead[kDepth];
@@ -149,7 +292,7 @@
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 @@
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 @@
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 @@
}
-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 @@
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 @@
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]);
***The diff for this file has been truncated for email.***
--
--
v8-dev mailing list
[email protected]
http://groups.google.com/group/v8-dev
---
You received this message because you are subscribed to the Google Groups "v8-dev" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
For more options, visit https://groups.google.com/d/optout.
