Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(175)

Issues Search
    My Issues | Starred     Open | Closed | All

Unified Diff: test/cctest/compiler/test-control-reducer.cc

Issue 665223006: Implement control reducer, which reduces branches and phis together in a single fixpoint. (Closed) Base URL: https://v8.googlecode.com/svn/branches/bleeding_edge
Patch Set: Created 6 years, 2 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View side-by-side diff with in-line comments
Download patch
« src/compiler/control-reducer.cc ('K') | « src/compiler/control-reducer.cc ('k') | no next file » | no next file with comments »
Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
Index: test/cctest/compiler/test-control-reducer.cc
diff --git a/test/cctest/compiler/test-control-reducer.cc b/test/cctest/compiler/test-control-reducer.cc
index 0e8dc177e234c1de6a2fb58ef8882cb4b6e03c57..d3ecc4f8857b2e4c46124520a411321e94a16a9d 100644
--- a/test/cctest/compiler/test-control-reducer.cc
+++ b/test/cctest/compiler/test-control-reducer.cc
@@ -5,27 +5,40 @@
#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;
+
+// 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,11 +46,98 @@ 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); }
+
+ // 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);
+ Node* end = graph.NewNode(common.End(), ret);
+ graph.SetEnd(end);
+ ControlReducer::ReduceGraph(main_zone(), &jsgraph, &common);
+ CHECK_EQ(expect, ret->InputAt(0));
+ }
+
+ 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);
+ ControlReducer::ReduceGraph(main_zone(), &jsgraph, &common);
+ CHECK_EQ(expect, end->InputAt(0));
+ }
+
+ void ReduceBranch(Node* expect, Node* branch) {
+ Node* result =
+ ControlReducer::ReduceBranchForTesting(&jsgraph, &common, branch);
+ CHECK_EQ(expect, result);
+ }
};
@@ -50,7 +150,7 @@ bool IsUsedBy(Node* a, Node* b) {
TEST(Trim1_live) {
- CTrimTester T;
+ ControlReducerTester T;
CHECK(IsUsedBy(T.start, T.p0));
T.graph.SetEnd(T.p0);
T.Trim();
@@ -60,7 +160,7 @@ TEST(Trim1_live) {
TEST(Trim1_dead) {
- CTrimTester T;
+ ControlReducerTester T;
CHECK(IsUsedBy(T.start, T.p0));
T.Trim();
CHECK(!IsUsedBy(T.start, T.p0));
@@ -69,7 +169,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));
@@ -87,7 +187,7 @@ TEST(Trim2_live) {
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 +204,7 @@ TEST(Trim2_dead) {
TEST(Trim_chain1) {
- CTrimTester T;
+ ControlReducerTester T;
const int kDepth = 15;
Node* live[kDepth];
Node* dead[kDepth];
@@ -126,7 +226,7 @@ TEST(Trim_chain1) {
TEST(Trim_chain2) {
- CTrimTester T;
+ ControlReducerTester T;
const int kDepth = 15;
Node* live[kDepth];
Node* dead[kDepth];
@@ -149,7 +249,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);
@@ -172,7 +272,7 @@ TEST(Trim_cycle1) {
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);
@@ -207,7 +307,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 +318,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 +340,813 @@ 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);
+ CHECK_EQ(IrOpcode::kMerge, merge->opcode());
+ CHECK_EQ(2, OpParameter<int32_t>(merge->op()));
+ CHECK_EQ(2, merge->InputCount());
+ CHECK_EQ(R.start, merge->InputAt(0));
+ CHECK_EQ(R.start, merge->InputAt(1));
+ }
+}
+
+
+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);
+ CHECK_EQ(IrOpcode::kMerge, merge->opcode());
+ CHECK_EQ(2, OpParameter<int32_t>(merge->op()));
+ CHECK_EQ(2, merge->InputCount());
+ CHECK_EQ(t, merge->InputAt(0));
+ CHECK_EQ(f, merge->InputAt(1));
+ }
+ }
+}
+
+
+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);
+ CHECK_EQ(IrOpcode::kLoop, loop->opcode());
+ CHECK_EQ(2, OpParameter<int32_t>(loop->op()));
+ CHECK_EQ(2, loop->InputCount());
+ CHECK_EQ(R.start, loop->InputAt(0));
+ CHECK_EQ(R.start, loop->InputAt(1));
+ }
+}
+
+
+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));
+ }
+}
+
+
+TEST(CMergeReduce_exhaustive_4) {
+ ControlReducerTester R;
+ Node* control[] = {
+ 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.graph.NewNode(R.common.Start(5)), R.graph.NewNode(R.common.Start(6)),
+ R.graph.NewNode(R.common.Start(7)), R.graph.NewNode(R.common.Start(8))};
+
+ for (int p = 0; p < 16; p++) {
+ int a = p & 1, b = p & 2, c = p & 4, d = p & 8;
+ Node* merge = R.graph.NewNode(R.common.Merge(4), control[0], control[1],
+ control[2], control[3]);
+
+ if (!a) merge->ReplaceInput(0, R.dead);
+ if (!b) merge->ReplaceInput(1, R.dead);
+ if (!c) merge->ReplaceInput(2, R.dead);
+ if (!d) merge->ReplaceInput(3, R.dead);
+ Node* phi = R.graph.NewNode(R.common.Phi(kMachAnyTagged, 4), values[0],
+ values[1], values[2], values[3], merge);
+ Node* effect = R.graph.NewNode(R.common.EffectPhi(4), effects[0],
+ effects[1], effects[2], effects[3], merge);
+
+ int count = v8::base::bits::CountPopulation32(p);
+ if (count == 0) {
+ // result should be dead.
+ Node* r =
+ ControlReducer::ReduceMergeForTesting(&R.jsgraph, &R.common, merge);
+ CHECK_EQ(IrOpcode::kDead, r->opcode());
+ } else if (count == 1) {
+ // result should be one of the controls.
+ Node* expect = control[WhichPowerOf2(p)];
+ R.ReduceMerge(expect, merge);
+ } else {
+ // merge should be edited.
+ R.ReduceMerge(merge, merge);
+ CHECK_EQ(count, merge->InputCount());
+ CHECK_EQ(count, OperatorProperties::GetControlInputCount(merge->op()));
+
+ CHECK_EQ(IrOpcode::kPhi, phi->opcode());
+ CHECK_EQ(count, phi->op()->InputCount());
+ CHECK_EQ(count + 1, phi->InputCount());
+
+ CHECK_EQ(IrOpcode::kEffectPhi, effect->opcode());
+ CHECK_EQ(0, effect->op()->InputCount());
+ CHECK_EQ(count, OperatorProperties::GetEffectInputCount(effect->op()));
+ CHECK_EQ(count + 1, effect->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);
+ }
+ // TODO(titzer): the NULL is because end gets killed. Check for dead
+ // properly.
+ R.ReduceMergeIterative(NULL, merge);
+ }
+}
+
+
+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 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); }
+
+ 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);
+ CHECK_EQ(R.start, d2.branch->InputAt(1));
+}
+
+
+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);
+ Node* branch = R.graph.NewNode(R.common.Branch(), R.p0, loop);
+ Node* if_true = R.graph.NewNode(R.common.IfTrue(), branch);
+ Node* if_false = R.graph.NewNode(R.common.IfFalse(), branch);
+ loop->ReplaceInput(0, if_true); // loop is not connected to start (i.e. dead)
+ Node* merge = R.graph.NewNode(R.common.Merge(2), R.start, if_false);
+ R.ReduceMergeIterative(R.start, merge);
+ CHECK_EQ(NULL, if_true->InputAt(0));
+ CHECK_EQ(NULL, if_false->InputAt(0));
+}
+
+
+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_EQ(NULL, d.if_true->InputAt(0));
+ CHECK_EQ(NULL, d.if_false->InputAt(0));
+}
+
+
+TEST(CNonTermLoop1) {
+ ControlReducerTester R;
+ Node* loop =
+ R.SetSelfReferences(R.graph.NewNode(R.common.Loop(1), R.start, R.self));
+ ControlReducer::ReduceGraph(R.graph.zone(), &R.jsgraph, &R.common);
+ 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));
+ CHECK_EQ(loop, merge->InputAt(1));
+}
+
+
+TEST(CNonTermLoop2) {}
« src/compiler/control-reducer.cc ('K') | « src/compiler/control-reducer.cc ('k') | no next file » | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698