blob: 093b46abdbcd87ede6ef1bc33450a439a6fa6169 [file] [log] [blame]
// 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/bit-vector.h"
#include "src/compiler/compiler-source-position-table.h"
#include "src/compiler/graph-visualizer.h"
#include "src/compiler/node-properties.h"
#include "src/zone/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(1), node));
if (FLAG_trace_turbo) {
OFStream os(stdout);
SourcePositionTable table(graph());
os << AsJSON(*graph(), &table);
}
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(static_cast<int>(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* Merge1(Node* control) {
return Store(graph()->NewNode(common()->Merge(1), 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(1), 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* merge1 = Merge1(start);
ComputeEquivalence(merge1);
ASSERT_EQUIVALENCE(start, merge1);
}
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