Index: test/unittests/compiler/control-equivalence-unittest.cc |
diff --git a/test/unittests/compiler/control-equivalence-unittest.cc b/test/unittests/compiler/control-equivalence-unittest.cc |
new file mode 100644 |
index 0000000000000000000000000000000000000000..b44f671a3d0c33549841a7248da8bd1e893af2c0 |
--- /dev/null |
+++ b/test/unittests/compiler/control-equivalence-unittest.cc |
@@ -0,0 +1,254 @@ |
+// Copyright 2014 the V8 project authors. All rights reserved. |
+// Use of this source code is governed by a BSD-style license that can be |
+// found in the LICENSE file. |
+ |
+#include "src/compiler/control-equivalence.h" |
+#include "src/compiler/graph-visualizer.h" |
+#include "src/compiler/node-properties-inl.h" |
+#include "src/zone-containers.h" |
+#include "test/unittests/compiler/graph-unittest.h" |
+ |
+namespace v8 { |
+namespace internal { |
+namespace compiler { |
+ |
+#define ASSERT_EQUIVALENCE(...) \ |
+ do { \ |
+ Node* __n[] = {__VA_ARGS__}; \ |
+ ASSERT_TRUE(IsEquivalenceClass(arraysize(__n), __n)); \ |
+ } while (false); |
+ |
+class ControlEquivalenceTest : public GraphTest { |
+ public: |
+ ControlEquivalenceTest() : all_nodes_(zone()), classes_(zone()) { |
+ Store(graph()->start()); |
+ } |
+ |
+ protected: |
+ void ComputeEquivalence(Node* node) { |
+ graph()->SetEnd(graph()->NewNode(common()->End(), node)); |
+ if (FLAG_trace_turbo) { |
+ OFStream os(stdout); |
+ os << AsDOT(*graph()); |
+ } |
+ ControlEquivalence equivalence(zone(), graph()); |
+ equivalence.Run(node); |
+ classes_.resize(graph()->NodeCount()); |
+ for (Node* node : all_nodes_) { |
+ classes_[node->id()] = equivalence.ClassOf(node); |
+ } |
+ } |
+ |
+ bool IsEquivalenceClass(size_t length, Node** nodes) { |
+ BitVector in_class(graph()->NodeCount(), zone()); |
+ size_t expected_class = classes_[nodes[0]->id()]; |
+ for (size_t i = 0; i < length; ++i) { |
+ in_class.Add(nodes[i]->id()); |
+ } |
+ for (Node* node : all_nodes_) { |
+ if (in_class.Contains(node->id())) { |
+ if (classes_[node->id()] != expected_class) return false; |
+ } else { |
+ if (classes_[node->id()] == expected_class) return false; |
+ } |
+ } |
+ return true; |
+ } |
+ |
+ Node* Value() { return NumberConstant(0.0); } |
+ |
+ Node* Branch(Node* control) { |
+ return Store(graph()->NewNode(common()->Branch(), Value(), control)); |
+ } |
+ |
+ Node* IfTrue(Node* control) { |
+ return Store(graph()->NewNode(common()->IfTrue(), control)); |
+ } |
+ |
+ Node* IfFalse(Node* control) { |
+ return Store(graph()->NewNode(common()->IfFalse(), control)); |
+ } |
+ |
+ Node* Merge2(Node* control1, Node* control2) { |
+ return Store(graph()->NewNode(common()->Merge(2), control1, control2)); |
+ } |
+ |
+ Node* Loop2(Node* control) { |
+ return Store(graph()->NewNode(common()->Loop(2), control, control)); |
+ } |
+ |
+ Node* End(Node* control) { |
+ return Store(graph()->NewNode(common()->End(), control)); |
+ } |
+ |
+ private: |
+ Node* Store(Node* node) { |
+ all_nodes_.push_back(node); |
+ return node; |
+ } |
+ |
+ ZoneVector<Node*> all_nodes_; |
+ ZoneVector<size_t> classes_; |
+}; |
+ |
+ |
+// ----------------------------------------------------------------------------- |
+// Test cases. |
+ |
+ |
+TEST_F(ControlEquivalenceTest, Empty1) { |
+ Node* start = graph()->start(); |
+ ComputeEquivalence(start); |
+ |
+ ASSERT_EQUIVALENCE(start); |
+} |
+ |
+ |
+TEST_F(ControlEquivalenceTest, Empty2) { |
+ Node* start = graph()->start(); |
+ Node* end = End(start); |
+ ComputeEquivalence(end); |
+ |
+ ASSERT_EQUIVALENCE(start, end); |
+} |
+ |
+ |
+TEST_F(ControlEquivalenceTest, Diamond1) { |
+ Node* start = graph()->start(); |
+ Node* b = Branch(start); |
+ Node* t = IfTrue(b); |
+ Node* f = IfFalse(b); |
+ Node* m = Merge2(t, f); |
+ ComputeEquivalence(m); |
+ |
+ ASSERT_EQUIVALENCE(b, m, start); |
+ ASSERT_EQUIVALENCE(f); |
+ ASSERT_EQUIVALENCE(t); |
+} |
+ |
+ |
+TEST_F(ControlEquivalenceTest, Diamond2) { |
+ Node* start = graph()->start(); |
+ Node* b1 = Branch(start); |
+ Node* t1 = IfTrue(b1); |
+ Node* f1 = IfFalse(b1); |
+ Node* b2 = Branch(f1); |
+ Node* t2 = IfTrue(b2); |
+ Node* f2 = IfFalse(b2); |
+ Node* m2 = Merge2(t2, f2); |
+ Node* m1 = Merge2(t1, m2); |
+ ComputeEquivalence(m1); |
+ |
+ ASSERT_EQUIVALENCE(b1, m1, start); |
+ ASSERT_EQUIVALENCE(t1); |
+ ASSERT_EQUIVALENCE(f1, b2, m2); |
+ ASSERT_EQUIVALENCE(t2); |
+ ASSERT_EQUIVALENCE(f2); |
+} |
+ |
+ |
+TEST_F(ControlEquivalenceTest, Diamond3) { |
+ Node* start = graph()->start(); |
+ Node* b1 = Branch(start); |
+ Node* t1 = IfTrue(b1); |
+ Node* f1 = IfFalse(b1); |
+ Node* m1 = Merge2(t1, f1); |
+ Node* b2 = Branch(m1); |
+ Node* t2 = IfTrue(b2); |
+ Node* f2 = IfFalse(b2); |
+ Node* m2 = Merge2(t2, f2); |
+ ComputeEquivalence(m2); |
+ |
+ ASSERT_EQUIVALENCE(b1, m1, b2, m2, start); |
+ ASSERT_EQUIVALENCE(t1); |
+ ASSERT_EQUIVALENCE(f1); |
+ ASSERT_EQUIVALENCE(t2); |
+ ASSERT_EQUIVALENCE(f2); |
+} |
+ |
+ |
+TEST_F(ControlEquivalenceTest, Switch1) { |
+ Node* start = graph()->start(); |
+ Node* b1 = Branch(start); |
+ Node* t1 = IfTrue(b1); |
+ Node* f1 = IfFalse(b1); |
+ Node* b2 = Branch(f1); |
+ Node* t2 = IfTrue(b2); |
+ Node* f2 = IfFalse(b2); |
+ Node* b3 = Branch(f2); |
+ Node* t3 = IfTrue(b3); |
+ Node* f3 = IfFalse(b3); |
+ Node* m1 = Merge2(t1, t2); |
+ Node* m2 = Merge2(m1, t3); |
+ Node* m3 = Merge2(m2, f3); |
+ ComputeEquivalence(m3); |
+ |
+ ASSERT_EQUIVALENCE(b1, m3, start); |
+ ASSERT_EQUIVALENCE(t1); |
+ ASSERT_EQUIVALENCE(f1, b2); |
+ ASSERT_EQUIVALENCE(t2); |
+ ASSERT_EQUIVALENCE(f2, b3); |
+ ASSERT_EQUIVALENCE(t3); |
+ ASSERT_EQUIVALENCE(f3); |
+ ASSERT_EQUIVALENCE(m1); |
+ ASSERT_EQUIVALENCE(m2); |
+} |
+ |
+ |
+TEST_F(ControlEquivalenceTest, Loop1) { |
+ Node* start = graph()->start(); |
+ Node* l = Loop2(start); |
+ l->ReplaceInput(1, l); |
+ ComputeEquivalence(l); |
+ |
+ ASSERT_EQUIVALENCE(start); |
+ ASSERT_EQUIVALENCE(l); |
+} |
+ |
+ |
+TEST_F(ControlEquivalenceTest, Loop2) { |
+ Node* start = graph()->start(); |
+ Node* l = Loop2(start); |
+ Node* b = Branch(l); |
+ Node* t = IfTrue(b); |
+ Node* f = IfFalse(b); |
+ l->ReplaceInput(1, t); |
+ ComputeEquivalence(f); |
+ |
+ ASSERT_EQUIVALENCE(f, start); |
+ ASSERT_EQUIVALENCE(t); |
+ ASSERT_EQUIVALENCE(l, b); |
+} |
+ |
+ |
+TEST_F(ControlEquivalenceTest, Irreducible) { |
+ Node* start = graph()->start(); |
+ Node* b1 = Branch(start); |
+ Node* t1 = IfTrue(b1); |
+ Node* f1 = IfFalse(b1); |
+ Node* lp = Loop2(f1); |
+ Node* m1 = Merge2(t1, lp); |
+ Node* b2 = Branch(m1); |
+ Node* t2 = IfTrue(b2); |
+ Node* f2 = IfFalse(b2); |
+ Node* m2 = Merge2(t2, f2); |
+ Node* b3 = Branch(m2); |
+ Node* t3 = IfTrue(b3); |
+ Node* f3 = IfFalse(b3); |
+ lp->ReplaceInput(1, f3); |
+ ComputeEquivalence(t3); |
+ |
+ ASSERT_EQUIVALENCE(b1, t3, start); |
+ ASSERT_EQUIVALENCE(t1); |
+ ASSERT_EQUIVALENCE(f1); |
+ ASSERT_EQUIVALENCE(m1, b2, m2, b3); |
+ ASSERT_EQUIVALENCE(t2); |
+ ASSERT_EQUIVALENCE(f2); |
+ ASSERT_EQUIVALENCE(f3); |
+ ASSERT_EQUIVALENCE(lp); |
+} |
+ |
+ |
+} // namespace compiler |
+} // namespace internal |
+} // namespace v8 |