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