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