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/v8.h" |
| 6 |
| 7 #include "src/compiler/access-builder.h" |
| 8 #include "src/compiler/common-operator.h" |
| 9 #include "src/compiler/graph.h" |
| 10 #include "src/compiler/graph-visualizer.h" |
| 11 #include "src/compiler/js-graph.h" |
| 12 #include "src/compiler/js-operator.h" |
| 13 #include "src/compiler/loop-analysis.h" |
| 14 #include "src/compiler/node.h" |
| 15 #include "src/compiler/opcodes.h" |
| 16 #include "src/compiler/operator.h" |
| 17 #include "src/compiler/schedule.h" |
| 18 #include "src/compiler/scheduler.h" |
| 19 #include "src/compiler/simplified-operator.h" |
| 20 #include "src/compiler/verifier.h" |
| 21 #include "test/cctest/cctest.h" |
| 22 |
| 23 using namespace v8::internal; |
| 24 using namespace v8::internal::compiler; |
| 25 |
| 26 static Operator kIntAdd(IrOpcode::kInt32Add, Operator::kPure, "Int32Add", 2, 0, |
| 27 0, 1, 0, 0); |
| 28 static Operator kIntLt(IrOpcode::kInt32LessThan, Operator::kPure, |
| 29 "Int32LessThan", 2, 0, 0, 1, 0, 0); |
| 30 static Operator kStore(IrOpcode::kStore, Operator::kNoProperties, "Store", 0, 2, |
| 31 1, 0, 1, 0); |
| 32 |
| 33 static const int kNumLeafs = 4; |
| 34 |
| 35 // A helper for all tests dealing with LoopFinder. |
| 36 class LoopFinderTester : HandleAndZoneScope { |
| 37 public: |
| 38 LoopFinderTester() |
| 39 : isolate(main_isolate()), |
| 40 common(main_zone()), |
| 41 graph(main_zone()), |
| 42 jsgraph(&graph, &common, NULL, NULL), |
| 43 start(graph.NewNode(common.Start(1))), |
| 44 end(graph.NewNode(common.End(), start)), |
| 45 p0(graph.NewNode(common.Parameter(0), start)), |
| 46 zero(jsgraph.Int32Constant(0)), |
| 47 one(jsgraph.OneConstant()), |
| 48 half(jsgraph.Constant(0.5)), |
| 49 self(graph.NewNode(common.Int32Constant(0xaabbccdd))), |
| 50 dead(graph.NewNode(common.Dead())), |
| 51 loop_tree(NULL) { |
| 52 graph.SetEnd(end); |
| 53 graph.SetStart(start); |
| 54 leaf[0] = zero; |
| 55 leaf[1] = one; |
| 56 leaf[2] = half; |
| 57 leaf[3] = p0; |
| 58 } |
| 59 |
| 60 Isolate* isolate; |
| 61 CommonOperatorBuilder common; |
| 62 Graph graph; |
| 63 JSGraph jsgraph; |
| 64 Node* start; |
| 65 Node* end; |
| 66 Node* p0; |
| 67 Node* zero; |
| 68 Node* one; |
| 69 Node* half; |
| 70 Node* self; |
| 71 Node* dead; |
| 72 Node* leaf[kNumLeafs]; |
| 73 LoopTree* loop_tree; |
| 74 |
| 75 Node* Phi(Node* a) { |
| 76 return SetSelfReferences(graph.NewNode(op(1, false), a, start)); |
| 77 } |
| 78 |
| 79 Node* Phi(Node* a, Node* b) { |
| 80 return SetSelfReferences(graph.NewNode(op(2, false), a, b, start)); |
| 81 } |
| 82 |
| 83 Node* Phi(Node* a, Node* b, Node* c) { |
| 84 return SetSelfReferences(graph.NewNode(op(3, false), a, b, c, start)); |
| 85 } |
| 86 |
| 87 Node* Phi(Node* a, Node* b, Node* c, Node* d) { |
| 88 return SetSelfReferences(graph.NewNode(op(4, false), a, b, c, d, start)); |
| 89 } |
| 90 |
| 91 Node* EffectPhi(Node* a) { |
| 92 return SetSelfReferences(graph.NewNode(op(1, true), a, start)); |
| 93 } |
| 94 |
| 95 Node* EffectPhi(Node* a, Node* b) { |
| 96 return SetSelfReferences(graph.NewNode(op(2, true), a, b, start)); |
| 97 } |
| 98 |
| 99 Node* EffectPhi(Node* a, Node* b, Node* c) { |
| 100 return SetSelfReferences(graph.NewNode(op(3, true), a, b, c, start)); |
| 101 } |
| 102 |
| 103 Node* EffectPhi(Node* a, Node* b, Node* c, Node* d) { |
| 104 return SetSelfReferences(graph.NewNode(op(4, true), a, b, c, d, start)); |
| 105 } |
| 106 |
| 107 Node* SetSelfReferences(Node* node) { |
| 108 for (Edge edge : node->input_edges()) { |
| 109 if (edge.to() == self) node->ReplaceInput(edge.index(), node); |
| 110 } |
| 111 return node; |
| 112 } |
| 113 |
| 114 const Operator* op(int count, bool effect) { |
| 115 return effect ? common.EffectPhi(count) : common.Phi(kMachAnyTagged, count); |
| 116 } |
| 117 |
| 118 Node* Return(Node* val, Node* effect, Node* control) { |
| 119 Node* ret = graph.NewNode(common.Return(), val, effect, control); |
| 120 end->ReplaceInput(0, ret); |
| 121 return ret; |
| 122 } |
| 123 |
| 124 LoopTree* GetLoopTree() { |
| 125 if (loop_tree == NULL) { |
| 126 if (FLAG_trace_turbo_graph) { |
| 127 OFStream os(stdout); |
| 128 os << AsRPO(graph); |
| 129 } |
| 130 Zone zone(isolate); |
| 131 loop_tree = LoopFinder::BuildLoopTree(&graph, &zone); |
| 132 } |
| 133 return loop_tree; |
| 134 } |
| 135 |
| 136 void CheckLoop(Node** header, int header_count, Node** body, int body_count) { |
| 137 LoopTree* tree = GetLoopTree(); |
| 138 LoopTree::Loop* loop = tree->ContainingLoop(header[0]); |
| 139 CHECK_NE(NULL, loop); |
| 140 |
| 141 CHECK(header_count == static_cast<int>(loop->HeaderSize())); |
| 142 for (int i = 0; i < header_count; i++) { |
| 143 // Each header node should be in the loop. |
| 144 CHECK_EQ(loop, tree->ContainingLoop(header[i])); |
| 145 CheckRangeContains(tree->HeaderNodes(loop), header[i]); |
| 146 } |
| 147 |
| 148 CHECK_EQ(body_count, static_cast<int>(loop->BodySize())); |
| 149 for (int i = 0; i < body_count; i++) { |
| 150 // Each body node should be contained in the loop. |
| 151 CHECK(tree->Contains(loop, body[i])); |
| 152 CheckRangeContains(tree->BodyNodes(loop), body[i]); |
| 153 } |
| 154 } |
| 155 |
| 156 void CheckRangeContains(NodeRange range, Node* node) { |
| 157 // O(n) ftw. |
| 158 CHECK_NE(range.end(), std::find(range.begin(), range.end(), node)); |
| 159 } |
| 160 |
| 161 void CheckNestedLoops(Node** chain, int chain_count) { |
| 162 LoopTree* tree = GetLoopTree(); |
| 163 for (int i = 0; i < chain_count; i++) { |
| 164 Node* header = chain[i]; |
| 165 // Each header should be in a loop. |
| 166 LoopTree::Loop* loop = tree->ContainingLoop(header); |
| 167 CHECK_NE(NULL, loop); |
| 168 // Check parentage. |
| 169 LoopTree::Loop* parent = |
| 170 i == 0 ? NULL : tree->ContainingLoop(chain[i - 1]); |
| 171 CHECK_EQ(parent, loop->parent()); |
| 172 for (int j = i - 1; j >= 0; j--) { |
| 173 // This loop should be nested inside all the outer loops. |
| 174 Node* outer_header = chain[j]; |
| 175 LoopTree::Loop* outer = tree->ContainingLoop(outer_header); |
| 176 CHECK(tree->Contains(outer, header)); |
| 177 CHECK(!tree->Contains(loop, outer_header)); |
| 178 } |
| 179 } |
| 180 } |
| 181 }; |
| 182 |
| 183 |
| 184 struct While { |
| 185 LoopFinderTester& t; |
| 186 Node* branch; |
| 187 Node* if_true; |
| 188 Node* exit; |
| 189 Node* loop; |
| 190 |
| 191 While(LoopFinderTester& R, Node* cond) : t(R) { |
| 192 loop = t.graph.NewNode(t.common.Loop(2), t.start, t.start); |
| 193 branch = t.graph.NewNode(t.common.Branch(), cond, loop); |
| 194 if_true = t.graph.NewNode(t.common.IfTrue(), branch); |
| 195 exit = t.graph.NewNode(t.common.IfFalse(), branch); |
| 196 loop->ReplaceInput(1, if_true); |
| 197 } |
| 198 |
| 199 void chain(Node* control) { loop->ReplaceInput(0, control); } |
| 200 void nest(While& that) { |
| 201 that.loop->ReplaceInput(1, exit); |
| 202 this->loop->ReplaceInput(0, that.if_true); |
| 203 } |
| 204 }; |
| 205 |
| 206 |
| 207 struct Counter { |
| 208 Node* base; |
| 209 Node* inc; |
| 210 Node* phi; |
| 211 Node* add; |
| 212 |
| 213 Counter(While& w, int32_t b, int32_t k) |
| 214 : base(w.t.jsgraph.Int32Constant(b)), inc(w.t.jsgraph.Int32Constant(k)) { |
| 215 Build(w); |
| 216 } |
| 217 |
| 218 Counter(While& w, Node* b, Node* k) : base(b), inc(k) { Build(w); } |
| 219 |
| 220 void Build(While& w) { |
| 221 phi = w.t.graph.NewNode(w.t.op(2, false), base, base, w.loop); |
| 222 add = w.t.graph.NewNode(&kIntAdd, phi, inc); |
| 223 phi->ReplaceInput(1, add); |
| 224 } |
| 225 }; |
| 226 |
| 227 |
| 228 struct StoreLoop { |
| 229 Node* base; |
| 230 Node* val; |
| 231 Node* phi; |
| 232 Node* store; |
| 233 |
| 234 explicit StoreLoop(While& w) |
| 235 : base(w.t.jsgraph.Int32Constant(12)), |
| 236 val(w.t.jsgraph.Int32Constant(13)) { |
| 237 Build(w); |
| 238 } |
| 239 |
| 240 StoreLoop(While& w, Node* b, Node* v) : base(b), val(v) { Build(w); } |
| 241 |
| 242 void Build(While& w) { |
| 243 phi = w.t.graph.NewNode(w.t.op(2, true), base, base, w.loop); |
| 244 store = w.t.graph.NewNode(&kStore, phi, val, w.loop); |
| 245 phi->ReplaceInput(1, store); |
| 246 } |
| 247 }; |
| 248 |
| 249 |
| 250 TEST(LaLoop1) { |
| 251 // One loop. |
| 252 LoopFinderTester t; |
| 253 While w(t, t.p0); |
| 254 t.Return(t.p0, t.start, w.exit); |
| 255 |
| 256 Node* chain[] = {w.loop}; |
| 257 t.CheckNestedLoops(chain, 1); |
| 258 |
| 259 Node* header[] = {w.loop}; |
| 260 Node* body[] = {w.branch, w.if_true}; |
| 261 t.CheckLoop(header, 1, body, 2); |
| 262 } |
| 263 |
| 264 |
| 265 TEST(LaLoop1c) { |
| 266 // One loop with a counter. |
| 267 LoopFinderTester t; |
| 268 While w(t, t.p0); |
| 269 Counter c(w, 0, 1); |
| 270 t.Return(c.phi, t.start, w.exit); |
| 271 |
| 272 Node* chain[] = {w.loop}; |
| 273 t.CheckNestedLoops(chain, 1); |
| 274 |
| 275 Node* header[] = {w.loop, c.phi}; |
| 276 Node* body[] = {w.branch, w.if_true, c.add}; |
| 277 t.CheckLoop(header, 2, body, 3); |
| 278 } |
| 279 |
| 280 |
| 281 TEST(LaLoop1e) { |
| 282 // One loop with an effect phi. |
| 283 LoopFinderTester t; |
| 284 While w(t, t.p0); |
| 285 StoreLoop c(w); |
| 286 t.Return(t.p0, c.phi, w.exit); |
| 287 |
| 288 Node* chain[] = {w.loop}; |
| 289 t.CheckNestedLoops(chain, 1); |
| 290 |
| 291 Node* header[] = {w.loop, c.phi}; |
| 292 Node* body[] = {w.branch, w.if_true, c.store}; |
| 293 t.CheckLoop(header, 2, body, 3); |
| 294 } |
| 295 |
| 296 |
| 297 TEST(LaLoop1d) { |
| 298 // One loop with two counters. |
| 299 LoopFinderTester t; |
| 300 While w(t, t.p0); |
| 301 Counter c1(w, 0, 1); |
| 302 Counter c2(w, 1, 1); |
| 303 t.Return(t.graph.NewNode(&kIntAdd, c1.phi, c2.phi), t.start, w.exit); |
| 304 |
| 305 Node* chain[] = {w.loop}; |
| 306 t.CheckNestedLoops(chain, 1); |
| 307 |
| 308 Node* header[] = {w.loop, c1.phi, c2.phi}; |
| 309 Node* body[] = {w.branch, w.if_true, c1.add, c2.add}; |
| 310 t.CheckLoop(header, 3, body, 4); |
| 311 } |
| 312 |
| 313 |
| 314 TEST(LaLoop2) { |
| 315 // One loop following another. |
| 316 LoopFinderTester t; |
| 317 While w1(t, t.p0); |
| 318 While w2(t, t.p0); |
| 319 w2.chain(w1.exit); |
| 320 t.Return(t.p0, t.start, w2.exit); |
| 321 |
| 322 { |
| 323 Node* chain[] = {w1.loop}; |
| 324 t.CheckNestedLoops(chain, 1); |
| 325 |
| 326 Node* header[] = {w1.loop}; |
| 327 Node* body[] = {w1.branch, w1.if_true}; |
| 328 t.CheckLoop(header, 1, body, 2); |
| 329 } |
| 330 |
| 331 { |
| 332 Node* chain[] = {w2.loop}; |
| 333 t.CheckNestedLoops(chain, 1); |
| 334 |
| 335 Node* header[] = {w2.loop}; |
| 336 Node* body[] = {w2.branch, w2.if_true}; |
| 337 t.CheckLoop(header, 1, body, 2); |
| 338 } |
| 339 } |
| 340 |
| 341 |
| 342 TEST(LaLoop2c) { |
| 343 // One loop following another, each with counters. |
| 344 LoopFinderTester t; |
| 345 While w1(t, t.p0); |
| 346 While w2(t, t.p0); |
| 347 Counter c1(w1, 0, 1); |
| 348 Counter c2(w2, 0, 1); |
| 349 w2.chain(w1.exit); |
| 350 t.Return(t.graph.NewNode(&kIntAdd, c1.phi, c2.phi), t.start, w2.exit); |
| 351 |
| 352 { |
| 353 Node* chain[] = {w1.loop}; |
| 354 t.CheckNestedLoops(chain, 1); |
| 355 |
| 356 Node* header[] = {w1.loop, c1.phi}; |
| 357 Node* body[] = {w1.branch, w1.if_true, c1.add}; |
| 358 t.CheckLoop(header, 2, body, 3); |
| 359 } |
| 360 |
| 361 { |
| 362 Node* chain[] = {w2.loop}; |
| 363 t.CheckNestedLoops(chain, 1); |
| 364 |
| 365 Node* header[] = {w2.loop, c2.phi}; |
| 366 Node* body[] = {w2.branch, w2.if_true, c2.add}; |
| 367 t.CheckLoop(header, 2, body, 3); |
| 368 } |
| 369 } |
| 370 |
| 371 |
| 372 TEST(LaLoop2cc) { |
| 373 // One loop following another; second loop uses phi from first. |
| 374 for (int i = 0; i < 8; i++) { |
| 375 LoopFinderTester t; |
| 376 While w1(t, t.p0); |
| 377 While w2(t, t.p0); |
| 378 Counter c1(w1, 0, 1); |
| 379 |
| 380 // various usage scenarios for the second loop. |
| 381 Counter c2(w2, i & 1 ? t.p0 : c1.phi, i & 2 ? t.p0 : c1.phi); |
| 382 if (i & 3) w2.branch->ReplaceInput(0, c1.phi); |
| 383 |
| 384 w2.chain(w1.exit); |
| 385 t.Return(t.graph.NewNode(&kIntAdd, c1.phi, c2.phi), t.start, w2.exit); |
| 386 |
| 387 { |
| 388 Node* chain[] = {w1.loop}; |
| 389 t.CheckNestedLoops(chain, 1); |
| 390 |
| 391 Node* header[] = {w1.loop, c1.phi}; |
| 392 Node* body[] = {w1.branch, w1.if_true, c1.add}; |
| 393 t.CheckLoop(header, 2, body, 3); |
| 394 } |
| 395 |
| 396 { |
| 397 Node* chain[] = {w2.loop}; |
| 398 t.CheckNestedLoops(chain, 1); |
| 399 |
| 400 Node* header[] = {w2.loop, c2.phi}; |
| 401 Node* body[] = {w2.branch, w2.if_true, c2.add}; |
| 402 t.CheckLoop(header, 2, body, 3); |
| 403 } |
| 404 } |
| 405 } |
| 406 |
| 407 |
| 408 TEST(LaNestedLoop1) { |
| 409 // One loop nested in another. |
| 410 LoopFinderTester t; |
| 411 While w1(t, t.p0); |
| 412 While w2(t, t.p0); |
| 413 w2.nest(w1); |
| 414 t.Return(t.p0, t.start, w1.exit); |
| 415 |
| 416 Node* chain[] = {w1.loop, w2.loop}; |
| 417 t.CheckNestedLoops(chain, 2); |
| 418 |
| 419 Node* h1[] = {w1.loop}; |
| 420 Node* b1[] = {w1.branch, w1.if_true, w2.loop, w2.branch, w2.if_true, w2.exit}; |
| 421 t.CheckLoop(h1, 1, b1, 6); |
| 422 |
| 423 Node* h2[] = {w2.loop}; |
| 424 Node* b2[] = {w2.branch, w2.if_true}; |
| 425 t.CheckLoop(h2, 1, b2, 2); |
| 426 } |
| 427 |
| 428 |
| 429 TEST(LaNestedLoop1c) { |
| 430 // One loop nested in another, each with a counter. |
| 431 LoopFinderTester t; |
| 432 While w1(t, t.p0); |
| 433 While w2(t, t.p0); |
| 434 Counter c1(w1, 0, 1); |
| 435 Counter c2(w2, 0, 1); |
| 436 w2.branch->ReplaceInput(0, c2.phi); |
| 437 w2.nest(w1); |
| 438 t.Return(c1.phi, t.start, w1.exit); |
| 439 |
| 440 Node* chain[] = {w1.loop, w2.loop}; |
| 441 t.CheckNestedLoops(chain, 2); |
| 442 |
| 443 Node* h1[] = {w1.loop, c1.phi}; |
| 444 Node* b1[] = {w1.branch, w1.if_true, w2.loop, w2.branch, w2.if_true, |
| 445 w2.exit, c2.phi, c1.add, c2.add}; |
| 446 t.CheckLoop(h1, 2, b1, 9); |
| 447 |
| 448 Node* h2[] = {w2.loop, c2.phi}; |
| 449 Node* b2[] = {w2.branch, w2.if_true, c2.add}; |
| 450 t.CheckLoop(h2, 2, b2, 3); |
| 451 } |
| 452 |
| 453 |
| 454 TEST(LaNestedLoop2) { |
| 455 // Two loops nested in an outer loop. |
| 456 LoopFinderTester t; |
| 457 While w1(t, t.p0); |
| 458 While w2(t, t.p0); |
| 459 While w3(t, t.p0); |
| 460 w2.nest(w1); |
| 461 w3.nest(w1); |
| 462 w3.chain(w2.exit); |
| 463 t.Return(t.p0, t.start, w1.exit); |
| 464 |
| 465 Node* chain1[] = {w1.loop, w2.loop}; |
| 466 t.CheckNestedLoops(chain1, 2); |
| 467 |
| 468 Node* chain2[] = {w1.loop, w3.loop}; |
| 469 t.CheckNestedLoops(chain2, 2); |
| 470 |
| 471 Node* h1[] = {w1.loop}; |
| 472 Node* b1[] = {w1.branch, w1.if_true, w2.loop, w2.branch, w2.if_true, |
| 473 w2.exit, w3.loop, w3.branch, w3.if_true, w3.exit}; |
| 474 t.CheckLoop(h1, 1, b1, 10); |
| 475 |
| 476 Node* h2[] = {w2.loop}; |
| 477 Node* b2[] = {w2.branch, w2.if_true}; |
| 478 t.CheckLoop(h2, 1, b2, 2); |
| 479 |
| 480 Node* h3[] = {w3.loop}; |
| 481 Node* b3[] = {w3.branch, w3.if_true}; |
| 482 t.CheckLoop(h3, 1, b3, 2); |
| 483 } |
| 484 |
| 485 |
| 486 TEST(LaNestedLoop3) { |
| 487 // Three nested loops. |
| 488 LoopFinderTester t; |
| 489 While w1(t, t.p0); |
| 490 While w2(t, t.p0); |
| 491 While w3(t, t.p0); |
| 492 w2.loop->ReplaceInput(0, w1.if_true); |
| 493 w3.loop->ReplaceInput(0, w2.if_true); |
| 494 w2.loop->ReplaceInput(1, w3.exit); |
| 495 w1.loop->ReplaceInput(1, w2.exit); |
| 496 t.Return(t.p0, t.start, w1.exit); |
| 497 |
| 498 Node* chain[] = {w1.loop, w2.loop, w3.loop}; |
| 499 t.CheckNestedLoops(chain, 3); |
| 500 |
| 501 Node* h1[] = {w1.loop}; |
| 502 Node* b1[] = {w1.branch, w1.if_true, w2.loop, w2.branch, w2.if_true, |
| 503 w2.exit, w3.loop, w3.branch, w3.if_true, w3.exit}; |
| 504 t.CheckLoop(h1, 1, b1, 10); |
| 505 |
| 506 Node* h2[] = {w2.loop}; |
| 507 Node* b2[] = {w2.branch, w2.if_true, w3.loop, w3.branch, w3.if_true, w3.exit}; |
| 508 t.CheckLoop(h2, 1, b2, 6); |
| 509 |
| 510 Node* h3[] = {w3.loop}; |
| 511 Node* b3[] = {w3.branch, w3.if_true}; |
| 512 t.CheckLoop(h3, 1, b3, 2); |
| 513 } |
| 514 |
| 515 |
| 516 TEST(LaNestedLoop3c) { |
| 517 // Three nested loops with counters. |
| 518 LoopFinderTester t; |
| 519 While w1(t, t.p0); |
| 520 Counter c1(w1, 0, 1); |
| 521 While w2(t, t.p0); |
| 522 Counter c2(w2, 0, 1); |
| 523 While w3(t, t.p0); |
| 524 Counter c3(w3, 0, 1); |
| 525 w2.loop->ReplaceInput(0, w1.if_true); |
| 526 w3.loop->ReplaceInput(0, w2.if_true); |
| 527 w2.loop->ReplaceInput(1, w3.exit); |
| 528 w1.loop->ReplaceInput(1, w2.exit); |
| 529 w1.branch->ReplaceInput(0, c1.phi); |
| 530 w2.branch->ReplaceInput(0, c2.phi); |
| 531 w3.branch->ReplaceInput(0, c3.phi); |
| 532 t.Return(c1.phi, t.start, w1.exit); |
| 533 |
| 534 Node* chain[] = {w1.loop, w2.loop, w3.loop}; |
| 535 t.CheckNestedLoops(chain, 3); |
| 536 |
| 537 Node* h1[] = {w1.loop, c1.phi}; |
| 538 Node* b1[] = {w1.branch, w1.if_true, c1.add, c2.add, c2.add, |
| 539 c2.phi, c3.phi, w2.loop, w2.branch, w2.if_true, |
| 540 w2.exit, w3.loop, w3.branch, w3.if_true, w3.exit}; |
| 541 t.CheckLoop(h1, 2, b1, 15); |
| 542 |
| 543 Node* h2[] = {w2.loop, c2.phi}; |
| 544 Node* b2[] = {w2.branch, w2.if_true, c2.add, c3.add, c3.phi, |
| 545 w3.loop, w3.branch, w3.if_true, w3.exit}; |
| 546 t.CheckLoop(h2, 2, b2, 9); |
| 547 |
| 548 Node* h3[] = {w3.loop, c3.phi}; |
| 549 Node* b3[] = {w3.branch, w3.if_true, c3.add}; |
| 550 t.CheckLoop(h3, 2, b3, 3); |
| 551 } |
| 552 |
| 553 |
| 554 TEST(LaMultipleExit1) { |
| 555 const int kMaxExits = 10; |
| 556 Node* merge[1 + kMaxExits]; |
| 557 Node* body[2 * kMaxExits]; |
| 558 |
| 559 // A single loop with {i} exits. |
| 560 for (int i = 1; i < kMaxExits; i++) { |
| 561 LoopFinderTester t; |
| 562 Node* cond = t.p0; |
| 563 |
| 564 int merge_count = 0; |
| 565 int body_count = 0; |
| 566 Node* loop = t.graph.NewNode(t.common.Loop(2), t.start, t.start); |
| 567 Node* last = loop; |
| 568 |
| 569 for (int e = 0; e < i; e++) { |
| 570 Node* branch = t.graph.NewNode(t.common.Branch(), cond, last); |
| 571 Node* if_true = t.graph.NewNode(t.common.IfTrue(), branch); |
| 572 Node* exit = t.graph.NewNode(t.common.IfFalse(), branch); |
| 573 last = if_true; |
| 574 |
| 575 body[body_count++] = branch; |
| 576 body[body_count++] = if_true; |
| 577 merge[merge_count++] = exit; |
| 578 } |
| 579 |
| 580 loop->ReplaceInput(1, last); // form loop backedge. |
| 581 Node* end = t.graph.NewNode(t.common.Merge(i), i, merge); // form exit. |
| 582 t.graph.SetEnd(end); |
| 583 |
| 584 Node* h[] = {loop}; |
| 585 t.CheckLoop(h, 1, body, body_count); |
| 586 } |
| 587 } |
| 588 |
| 589 |
| 590 TEST(LaMultipleBackedge1) { |
| 591 const int kMaxBackedges = 10; |
| 592 Node* loop_inputs[1 + kMaxBackedges]; |
| 593 Node* body[3 * kMaxBackedges]; |
| 594 |
| 595 // A single loop with {i} backedges. |
| 596 for (int i = 1; i < kMaxBackedges; i++) { |
| 597 LoopFinderTester t; |
| 598 |
| 599 for (int j = 0; j <= i; j++) loop_inputs[j] = t.start; |
| 600 Node* loop = t.graph.NewNode(t.common.Loop(1 + i), 1 + i, loop_inputs); |
| 601 |
| 602 Node* cond = t.p0; |
| 603 int body_count = 0; |
| 604 Node* exit = loop; |
| 605 |
| 606 for (int b = 0; b < i; b++) { |
| 607 Node* branch = t.graph.NewNode(t.common.Branch(), cond, exit); |
| 608 Node* if_true = t.graph.NewNode(t.common.IfTrue(), branch); |
| 609 Node* if_false = t.graph.NewNode(t.common.IfFalse(), branch); |
| 610 exit = if_false; |
| 611 |
| 612 body[body_count++] = branch; |
| 613 body[body_count++] = if_true; |
| 614 if (b != (i - 1)) body[body_count++] = if_false; |
| 615 |
| 616 loop->ReplaceInput(1 + b, if_true); |
| 617 } |
| 618 |
| 619 t.graph.SetEnd(exit); |
| 620 |
| 621 Node* h[] = {loop}; |
| 622 t.CheckLoop(h, 1, body, body_count); |
| 623 } |
| 624 } |
| 625 |
| 626 |
| 627 TEST(LaEdgeMatrix1) { |
| 628 // Test various kinds of extra edges added to a simple loop. |
| 629 for (int i = 0; i < 3; i++) { |
| 630 for (int j = 0; j < 3; j++) { |
| 631 for (int k = 0; k < 3; k++) { |
| 632 LoopFinderTester t; |
| 633 |
| 634 Node* p1 = t.jsgraph.Int32Constant(11); |
| 635 Node* p2 = t.jsgraph.Int32Constant(22); |
| 636 Node* p3 = t.jsgraph.Int32Constant(33); |
| 637 |
| 638 Node* loop = t.graph.NewNode(t.common.Loop(2), t.start, t.start); |
| 639 Node* phi = |
| 640 t.graph.NewNode(t.common.Phi(kMachInt32, 2), t.one, p1, loop); |
| 641 Node* cond = t.graph.NewNode(&kIntAdd, phi, p2); |
| 642 Node* branch = t.graph.NewNode(t.common.Branch(), cond, loop); |
| 643 Node* if_true = t.graph.NewNode(t.common.IfTrue(), branch); |
| 644 Node* exit = t.graph.NewNode(t.common.IfFalse(), branch); |
| 645 loop->ReplaceInput(1, if_true); |
| 646 Node* ret = t.graph.NewNode(t.common.Return(), p3, t.start, exit); |
| 647 t.graph.SetEnd(ret); |
| 648 |
| 649 Node* choices[] = {p1, phi, cond}; |
| 650 p1->ReplaceUses(choices[i]); |
| 651 p2->ReplaceUses(choices[j]); |
| 652 p3->ReplaceUses(choices[k]); |
| 653 |
| 654 Node* header[] = {loop, phi}; |
| 655 Node* body[] = {cond, branch, if_true}; |
| 656 t.CheckLoop(header, 2, body, 3); |
| 657 } |
| 658 } |
| 659 } |
| 660 } |
| 661 |
| 662 |
| 663 void RunEdgeMatrix2(int i) { |
| 664 DCHECK(i >= 0 && i < 5); |
| 665 for (int j = 0; j < 5; j++) { |
| 666 for (int k = 0; k < 5; k++) { |
| 667 LoopFinderTester t; |
| 668 |
| 669 Node* p1 = t.jsgraph.Int32Constant(11); |
| 670 Node* p2 = t.jsgraph.Int32Constant(22); |
| 671 Node* p3 = t.jsgraph.Int32Constant(33); |
| 672 |
| 673 // outer loop. |
| 674 Node* loop1 = t.graph.NewNode(t.common.Loop(2), t.start, t.start); |
| 675 Node* phi1 = |
| 676 t.graph.NewNode(t.common.Phi(kMachInt32, 2), t.one, p1, loop1); |
| 677 Node* cond1 = t.graph.NewNode(&kIntAdd, phi1, t.one); |
| 678 Node* branch1 = t.graph.NewNode(t.common.Branch(), cond1, loop1); |
| 679 Node* if_true1 = t.graph.NewNode(t.common.IfTrue(), branch1); |
| 680 Node* exit1 = t.graph.NewNode(t.common.IfFalse(), branch1); |
| 681 |
| 682 // inner loop. |
| 683 Node* loop2 = t.graph.NewNode(t.common.Loop(2), if_true1, t.start); |
| 684 Node* phi2 = |
| 685 t.graph.NewNode(t.common.Phi(kMachInt32, 2), t.one, p2, loop2); |
| 686 Node* cond2 = t.graph.NewNode(&kIntAdd, phi2, p3); |
| 687 Node* branch2 = t.graph.NewNode(t.common.Branch(), cond2, loop2); |
| 688 Node* if_true2 = t.graph.NewNode(t.common.IfTrue(), branch2); |
| 689 Node* exit2 = t.graph.NewNode(t.common.IfFalse(), branch2); |
| 690 loop2->ReplaceInput(1, if_true2); |
| 691 loop1->ReplaceInput(1, exit2); |
| 692 |
| 693 Node* ret = t.graph.NewNode(t.common.Return(), phi1, t.start, exit1); |
| 694 t.graph.SetEnd(ret); |
| 695 |
| 696 Node* choices[] = {p1, phi1, cond1, phi2, cond2}; |
| 697 p1->ReplaceUses(choices[i]); |
| 698 p2->ReplaceUses(choices[j]); |
| 699 p3->ReplaceUses(choices[k]); |
| 700 |
| 701 Node* header1[] = {loop1, phi1}; |
| 702 Node* body1[] = {cond1, branch1, if_true1, exit2, loop2, |
| 703 phi2, cond2, branch2, if_true2}; |
| 704 t.CheckLoop(header1, 2, body1, 9); |
| 705 |
| 706 Node* header2[] = {loop2, phi2}; |
| 707 Node* body2[] = {cond2, branch2, if_true2}; |
| 708 t.CheckLoop(header2, 2, body2, 3); |
| 709 |
| 710 Node* chain[] = {loop1, loop2}; |
| 711 t.CheckNestedLoops(chain, 2); |
| 712 } |
| 713 } |
| 714 } |
| 715 |
| 716 |
| 717 TEST(LaEdgeMatrix2_0) { RunEdgeMatrix2(0); } |
| 718 |
| 719 |
| 720 TEST(LaEdgeMatrix2_1) { RunEdgeMatrix2(1); } |
| 721 |
| 722 |
| 723 TEST(LaEdgeMatrix2_2) { RunEdgeMatrix2(2); } |
| 724 |
| 725 |
| 726 TEST(LaEdgeMatrix2_3) { RunEdgeMatrix2(3); } |
| 727 |
| 728 |
| 729 TEST(LaEdgeMatrix2_4) { RunEdgeMatrix2(4); } |
| 730 |
| 731 |
| 732 // Generates a triply-nested loop with extra edges between the phis and |
| 733 // conditions according to the edge choice parameters. |
| 734 void RunEdgeMatrix3(int c1a, int c1b, int c1c, // line break |
| 735 int c2a, int c2b, int c2c, // line break |
| 736 int c3a, int c3b, int c3c) { // line break |
| 737 LoopFinderTester t; |
| 738 |
| 739 Node* p1a = t.jsgraph.Int32Constant(11); |
| 740 Node* p1b = t.jsgraph.Int32Constant(22); |
| 741 Node* p1c = t.jsgraph.Int32Constant(33); |
| 742 Node* p2a = t.jsgraph.Int32Constant(44); |
| 743 Node* p2b = t.jsgraph.Int32Constant(55); |
| 744 Node* p2c = t.jsgraph.Int32Constant(66); |
| 745 Node* p3a = t.jsgraph.Int32Constant(77); |
| 746 Node* p3b = t.jsgraph.Int32Constant(88); |
| 747 Node* p3c = t.jsgraph.Int32Constant(99); |
| 748 |
| 749 // L1 depth = 0 |
| 750 Node* loop1 = t.graph.NewNode(t.common.Loop(2), t.start, t.start); |
| 751 Node* phi1 = t.graph.NewNode(t.common.Phi(kMachInt32, 2), p1a, p1c, loop1); |
| 752 Node* cond1 = t.graph.NewNode(&kIntAdd, phi1, p1b); |
| 753 Node* branch1 = t.graph.NewNode(t.common.Branch(), cond1, loop1); |
| 754 Node* if_true1 = t.graph.NewNode(t.common.IfTrue(), branch1); |
| 755 Node* exit1 = t.graph.NewNode(t.common.IfFalse(), branch1); |
| 756 |
| 757 // L2 depth = 1 |
| 758 Node* loop2 = t.graph.NewNode(t.common.Loop(2), if_true1, t.start); |
| 759 Node* phi2 = t.graph.NewNode(t.common.Phi(kMachInt32, 2), p2a, p2c, loop2); |
| 760 Node* cond2 = t.graph.NewNode(&kIntAdd, phi2, p2b); |
| 761 Node* branch2 = t.graph.NewNode(t.common.Branch(), cond2, loop2); |
| 762 Node* if_true2 = t.graph.NewNode(t.common.IfTrue(), branch2); |
| 763 Node* exit2 = t.graph.NewNode(t.common.IfFalse(), branch2); |
| 764 |
| 765 // L3 depth = 2 |
| 766 Node* loop3 = t.graph.NewNode(t.common.Loop(2), if_true2, t.start); |
| 767 Node* phi3 = t.graph.NewNode(t.common.Phi(kMachInt32, 2), p3a, p3c, loop3); |
| 768 Node* cond3 = t.graph.NewNode(&kIntAdd, phi3, p3b); |
| 769 Node* branch3 = t.graph.NewNode(t.common.Branch(), cond3, loop3); |
| 770 Node* if_true3 = t.graph.NewNode(t.common.IfTrue(), branch3); |
| 771 Node* exit3 = t.graph.NewNode(t.common.IfFalse(), branch3); |
| 772 |
| 773 loop3->ReplaceInput(1, if_true3); |
| 774 loop2->ReplaceInput(1, exit3); |
| 775 loop1->ReplaceInput(1, exit2); |
| 776 |
| 777 Node* ret = t.graph.NewNode(t.common.Return(), phi1, t.start, exit1); |
| 778 t.graph.SetEnd(ret); |
| 779 |
| 780 // Mutate the graph according to the edge choices. |
| 781 |
| 782 Node* o1[] = {t.one}; |
| 783 Node* o2[] = {t.one, phi1, cond1}; |
| 784 Node* o3[] = {t.one, phi1, cond1, phi2, cond2}; |
| 785 |
| 786 p1a->ReplaceUses(o1[c1a]); |
| 787 p1b->ReplaceUses(o1[c1b]); |
| 788 |
| 789 p2a->ReplaceUses(o2[c2a]); |
| 790 p2b->ReplaceUses(o2[c2b]); |
| 791 |
| 792 p3a->ReplaceUses(o3[c3a]); |
| 793 p3b->ReplaceUses(o3[c3b]); |
| 794 |
| 795 Node* l2[] = {phi1, cond1, phi2, cond2}; |
| 796 Node* l3[] = {phi1, cond1, phi2, cond2, phi3, cond3}; |
| 797 |
| 798 p1c->ReplaceUses(l2[c1c]); |
| 799 p2c->ReplaceUses(l3[c2c]); |
| 800 p3c->ReplaceUses(l3[c3c]); |
| 801 |
| 802 // Run the tests and verify loop structure. |
| 803 |
| 804 Node* chain[] = {loop1, loop2, loop3}; |
| 805 t.CheckNestedLoops(chain, 3); |
| 806 |
| 807 Node* header1[] = {loop1, phi1}; |
| 808 Node* body1[] = {cond1, branch1, if_true1, exit2, loop2, |
| 809 phi2, cond2, branch2, if_true2, exit3, |
| 810 loop3, phi3, cond3, branch3, if_true3}; |
| 811 t.CheckLoop(header1, 2, body1, 15); |
| 812 |
| 813 Node* header2[] = {loop2, phi2}; |
| 814 Node* body2[] = {cond2, branch2, if_true2, exit3, loop3, |
| 815 phi3, cond3, branch3, if_true3}; |
| 816 t.CheckLoop(header2, 2, body2, 9); |
| 817 |
| 818 Node* header3[] = {loop3, phi3}; |
| 819 Node* body3[] = {cond3, branch3, if_true3}; |
| 820 t.CheckLoop(header3, 2, body3, 3); |
| 821 } |
| 822 |
| 823 |
| 824 // Runs all combinations with a fixed {i}. |
| 825 void RunEdgeMatrix3_i(int i) { |
| 826 for (int a = 0; a < 1; a++) { |
| 827 for (int b = 0; b < 1; b++) { |
| 828 for (int c = 0; c < 4; c++) { |
| 829 for (int d = 0; d < 3; d++) { |
| 830 for (int e = 0; e < 3; e++) { |
| 831 for (int f = 0; f < 6; f++) { |
| 832 for (int g = 0; g < 5; g++) { |
| 833 for (int h = 0; h < 5; h++) { |
| 834 RunEdgeMatrix3(a, b, c, d, e, f, g, h, i); |
| 835 } |
| 836 } |
| 837 } |
| 838 } |
| 839 } |
| 840 } |
| 841 } |
| 842 } |
| 843 } |
| 844 |
| 845 |
| 846 // Test all possible legal triply-nested loops with conditions and phis. |
| 847 TEST(LaEdgeMatrix3_0) { RunEdgeMatrix3_i(0); } |
| 848 |
| 849 |
| 850 TEST(LaEdgeMatrix3_1) { RunEdgeMatrix3_i(1); } |
| 851 |
| 852 |
| 853 TEST(LaEdgeMatrix3_2) { RunEdgeMatrix3_i(2); } |
| 854 |
| 855 |
| 856 TEST(LaEdgeMatrix3_3) { RunEdgeMatrix3_i(3); } |
| 857 |
| 858 |
| 859 TEST(LaEdgeMatrix3_4) { RunEdgeMatrix3_i(4); } |
| 860 |
| 861 |
| 862 TEST(LaEdgeMatrix3_5) { RunEdgeMatrix3_i(5); } |
OLD | NEW |