deps/v8/test/unittests/compiler/control-equivalence-unittest.cc

   1 // Copyright 2014 the V8 project authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style license that can be
   3 // found in the LICENSE file.
   4
   5 #include "src/bit-vector.h"
   6 #include "src/compiler/control-equivalence.h"
   7 #include "src/compiler/graph-visualizer.h"
   8 #include "src/compiler/node-properties.h"
   9 #include "src/zone-containers.h"
  10 #include "test/unittests/compiler/graph-unittest.h"
  11
  12 namespace v8 {
  13 namespace internal {
  14 namespace compiler {
  15
  16 #define ASSERT_EQUIVALENCE(...)                           \
  17   do {                                                    \
  18     Node* __n[] = {__VA_ARGS__};                          \
  19     ASSERT_TRUE(IsEquivalenceClass(arraysize(__n), __n)); \
  20   } while (false);
  21
  22 class ControlEquivalenceTest : public GraphTest {
  23  public:
  24   ControlEquivalenceTest() : all_nodes_(zone()), classes_(zone()) {
  25     Store(graph()->start());
  26   }
  27
  28  protected:
  29   void ComputeEquivalence(Node* node) {
  30     graph()->SetEnd(graph()->NewNode(common()->End(), node));
  31     if (FLAG_trace_turbo) {
  32       OFStream os(stdout);
  33       os << AsDOT(*graph());
  34     }
  35     ControlEquivalence equivalence(zone(), graph());
  36     equivalence.Run(node);
  37     classes_.resize(graph()->NodeCount());
  38     for (Node* node : all_nodes_) {
  39       classes_[node->id()] = equivalence.ClassOf(node);
  40     }
  41   }
  42
  43   bool IsEquivalenceClass(size_t length, Node** nodes) {
  44     BitVector in_class(graph()->NodeCount(), zone());
  45     size_t expected_class = classes_[nodes[0]->id()];
  46     for (size_t i = 0; i < length; ++i) {
  47       in_class.Add(nodes[i]->id());
  48     }
  49     for (Node* node : all_nodes_) {
  50       if (in_class.Contains(node->id())) {
  51         if (classes_[node->id()] != expected_class) return false;
  52       } else {
  53         if (classes_[node->id()] == expected_class) return false;
  54       }
  55     }
  56     return true;
  57   }
  58
  59   Node* Value() { return NumberConstant(0.0); }
  60
  61   Node* Branch(Node* control) {
  62     return Store(graph()->NewNode(common()->Branch(), Value(), control));
  63   }
  64
  65   Node* IfTrue(Node* control) {
  66     return Store(graph()->NewNode(common()->IfTrue(), control));
  67   }
  68
  69   Node* IfFalse(Node* control) {
  70     return Store(graph()->NewNode(common()->IfFalse(), control));
  71   }
  72
  73   Node* Merge2(Node* control1, Node* control2) {
  74     return Store(graph()->NewNode(common()->Merge(2), control1, control2));
  75   }
  76
  77   Node* Loop2(Node* control) {
  78     return Store(graph()->NewNode(common()->Loop(2), control, control));
  79   }
  80
  81   Node* End(Node* control) {
  82     return Store(graph()->NewNode(common()->End(), control));
  83   }
  84
  85  private:
  86   Node* Store(Node* node) {
  87     all_nodes_.push_back(node);
  88     return node;
  89   }
  90
  91   ZoneVector<Node*> all_nodes_;
  92   ZoneVector<size_t> classes_;
  93 };
  94
  95
  96 // -----------------------------------------------------------------------------
  97 // Test cases.
  98
  99
 100 TEST_F(ControlEquivalenceTest, Empty1) {
 101   Node* start = graph()->start();
 102   ComputeEquivalence(start);
 103
 104   ASSERT_EQUIVALENCE(start);
 105 }
 106
 107
 108 TEST_F(ControlEquivalenceTest, Empty2) {
 109   Node* start = graph()->start();
 110   Node* end = End(start);
 111   ComputeEquivalence(end);
 112
 113   ASSERT_EQUIVALENCE(start, end);
 114 }
 115
 116
 117 TEST_F(ControlEquivalenceTest, Diamond1) {
 118   Node* start = graph()->start();
 119   Node* b = Branch(start);
 120   Node* t = IfTrue(b);
 121   Node* f = IfFalse(b);
 122   Node* m = Merge2(t, f);
 123   ComputeEquivalence(m);
 124
 125   ASSERT_EQUIVALENCE(b, m, start);
 126   ASSERT_EQUIVALENCE(f);
 127   ASSERT_EQUIVALENCE(t);
 128 }
 129
 130
 131 TEST_F(ControlEquivalenceTest, Diamond2) {
 132   Node* start = graph()->start();
 133   Node* b1 = Branch(start);
 134   Node* t1 = IfTrue(b1);
 135   Node* f1 = IfFalse(b1);
 136   Node* b2 = Branch(f1);
 137   Node* t2 = IfTrue(b2);
 138   Node* f2 = IfFalse(b2);
 139   Node* m2 = Merge2(t2, f2);
 140   Node* m1 = Merge2(t1, m2);
 141   ComputeEquivalence(m1);
 142
 143   ASSERT_EQUIVALENCE(b1, m1, start);
 144   ASSERT_EQUIVALENCE(t1);
 145   ASSERT_EQUIVALENCE(f1, b2, m2);
 146   ASSERT_EQUIVALENCE(t2);
 147   ASSERT_EQUIVALENCE(f2);
 148 }
 149
 150
 151 TEST_F(ControlEquivalenceTest, Diamond3) {
 152   Node* start = graph()->start();
 153   Node* b1 = Branch(start);
 154   Node* t1 = IfTrue(b1);
 155   Node* f1 = IfFalse(b1);
 156   Node* m1 = Merge2(t1, f1);
 157   Node* b2 = Branch(m1);
 158   Node* t2 = IfTrue(b2);
 159   Node* f2 = IfFalse(b2);
 160   Node* m2 = Merge2(t2, f2);
 161   ComputeEquivalence(m2);
 162
 163   ASSERT_EQUIVALENCE(b1, m1, b2, m2, start);
 164   ASSERT_EQUIVALENCE(t1);
 165   ASSERT_EQUIVALENCE(f1);
 166   ASSERT_EQUIVALENCE(t2);
 167   ASSERT_EQUIVALENCE(f2);
 168 }
 169
 170
 171 TEST_F(ControlEquivalenceTest, Switch1) {
 172   Node* start = graph()->start();
 173   Node* b1 = Branch(start);
 174   Node* t1 = IfTrue(b1);
 175   Node* f1 = IfFalse(b1);
 176   Node* b2 = Branch(f1);
 177   Node* t2 = IfTrue(b2);
 178   Node* f2 = IfFalse(b2);
 179   Node* b3 = Branch(f2);
 180   Node* t3 = IfTrue(b3);
 181   Node* f3 = IfFalse(b3);
 182   Node* m1 = Merge2(t1, t2);
 183   Node* m2 = Merge2(m1, t3);
 184   Node* m3 = Merge2(m2, f3);
 185   ComputeEquivalence(m3);
 186
 187   ASSERT_EQUIVALENCE(b1, m3, start);
 188   ASSERT_EQUIVALENCE(t1);
 189   ASSERT_EQUIVALENCE(f1, b2);
 190   ASSERT_EQUIVALENCE(t2);
 191   ASSERT_EQUIVALENCE(f2, b3);
 192   ASSERT_EQUIVALENCE(t3);
 193   ASSERT_EQUIVALENCE(f3);
 194   ASSERT_EQUIVALENCE(m1);
 195   ASSERT_EQUIVALENCE(m2);
 196 }
 197
 198
 199 TEST_F(ControlEquivalenceTest, Loop1) {
 200   Node* start = graph()->start();
 201   Node* l = Loop2(start);
 202   l->ReplaceInput(1, l);
 203   ComputeEquivalence(l);
 204
 205   ASSERT_EQUIVALENCE(start);
 206   ASSERT_EQUIVALENCE(l);
 207 }
 208
 209
 210 TEST_F(ControlEquivalenceTest, Loop2) {
 211   Node* start = graph()->start();
 212   Node* l = Loop2(start);
 213   Node* b = Branch(l);
 214   Node* t = IfTrue(b);
 215   Node* f = IfFalse(b);
 216   l->ReplaceInput(1, t);
 217   ComputeEquivalence(f);
 218
 219   ASSERT_EQUIVALENCE(f, start);
 220   ASSERT_EQUIVALENCE(t);
 221   ASSERT_EQUIVALENCE(l, b);
 222 }
 223
 224
 225 TEST_F(ControlEquivalenceTest, Irreducible) {
 226   Node* start = graph()->start();
 227   Node* b1 = Branch(start);
 228   Node* t1 = IfTrue(b1);
 229   Node* f1 = IfFalse(b1);
 230   Node* lp = Loop2(f1);
 231   Node* m1 = Merge2(t1, lp);
 232   Node* b2 = Branch(m1);
 233   Node* t2 = IfTrue(b2);
 234   Node* f2 = IfFalse(b2);
 235   Node* m2 = Merge2(t2, f2);
 236   Node* b3 = Branch(m2);
 237   Node* t3 = IfTrue(b3);
 238   Node* f3 = IfFalse(b3);
 239   lp->ReplaceInput(1, f3);
 240   ComputeEquivalence(t3);
 241
 242   ASSERT_EQUIVALENCE(b1, t3, start);
 243   ASSERT_EQUIVALENCE(t1);
 244   ASSERT_EQUIVALENCE(f1);
 245   ASSERT_EQUIVALENCE(m1, b2, m2, b3);
 246   ASSERT_EQUIVALENCE(t2);
 247   ASSERT_EQUIVALENCE(f2);
 248   ASSERT_EQUIVALENCE(f3);
 249   ASSERT_EQUIVALENCE(lp);
 250 }
 251
 252
 253 }  // namespace compiler
 254 }  // namespace internal
 255 }  // namespace v8