Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 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 | |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 5 | #include "src/compiler/access-builder.h" |
| 6 | #include "src/compiler/common-operator.h" |
| 7 | #include "src/compiler/graph.h" |
| 8 | #include "src/compiler/graph-visualizer.h" |
| 9 | #include "src/compiler/js-graph.h" |
| 10 | #include "src/compiler/js-operator.h" |
| 11 | #include "src/compiler/loop-analysis.h" |
| 12 | #include "src/compiler/node.h" |
| 13 | #include "src/compiler/opcodes.h" |
| 14 | #include "src/compiler/operator.h" |
| 15 | #include "src/compiler/schedule.h" |
| 16 | #include "src/compiler/scheduler.h" |
| 17 | #include "src/compiler/simplified-operator.h" |
| 18 | #include "src/compiler/verifier.h" |
| 19 | #include "test/cctest/cctest.h" |
| 20 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 21 | namespace v8 { |
| 22 | namespace internal { |
| 23 | namespace compiler { |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 24 | |
| 25 | static Operator kIntAdd(IrOpcode::kInt32Add, Operator::kPure, "Int32Add", 2, 0, |
| 26 | 0, 1, 0, 0); |
| 27 | static Operator kIntLt(IrOpcode::kInt32LessThan, Operator::kPure, |
| 28 | "Int32LessThan", 2, 0, 0, 1, 0, 0); |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 29 | static Operator kStore(IrOpcode::kStore, Operator::kNoProperties, "Store", 1, 1, |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 30 | 1, 0, 1, 0); |
| 31 | |
| 32 | static const int kNumLeafs = 4; |
| 33 | |
| 34 | // A helper for all tests dealing with LoopFinder. |
| 35 | class LoopFinderTester : HandleAndZoneScope { |
| 36 | public: |
| 37 | LoopFinderTester() |
| 38 | : isolate(main_isolate()), |
| 39 | common(main_zone()), |
| 40 | graph(main_zone()), |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 41 | jsgraph(main_isolate(), &graph, &common, nullptr, nullptr, nullptr), |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 42 | start(graph.NewNode(common.Start(1))), |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 43 | end(graph.NewNode(common.End(1), start)), |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 44 | p0(graph.NewNode(common.Parameter(0), start)), |
| 45 | zero(jsgraph.Int32Constant(0)), |
| 46 | one(jsgraph.OneConstant()), |
| 47 | half(jsgraph.Constant(0.5)), |
| 48 | self(graph.NewNode(common.Int32Constant(0xaabbccdd))), |
| 49 | dead(graph.NewNode(common.Dead())), |
| 50 | loop_tree(NULL) { |
| 51 | graph.SetEnd(end); |
| 52 | graph.SetStart(start); |
| 53 | leaf[0] = zero; |
| 54 | leaf[1] = one; |
| 55 | leaf[2] = half; |
| 56 | leaf[3] = p0; |
| 57 | } |
| 58 | |
| 59 | Isolate* isolate; |
| 60 | CommonOperatorBuilder common; |
| 61 | Graph graph; |
| 62 | JSGraph jsgraph; |
| 63 | Node* start; |
| 64 | Node* end; |
| 65 | Node* p0; |
| 66 | Node* zero; |
| 67 | Node* one; |
| 68 | Node* half; |
| 69 | Node* self; |
| 70 | Node* dead; |
| 71 | Node* leaf[kNumLeafs]; |
| 72 | LoopTree* loop_tree; |
| 73 | |
| 74 | Node* Phi(Node* a) { |
| 75 | return SetSelfReferences(graph.NewNode(op(1, false), a, start)); |
| 76 | } |
| 77 | |
| 78 | Node* Phi(Node* a, Node* b) { |
| 79 | return SetSelfReferences(graph.NewNode(op(2, false), a, b, start)); |
| 80 | } |
| 81 | |
| 82 | Node* Phi(Node* a, Node* b, Node* c) { |
| 83 | return SetSelfReferences(graph.NewNode(op(3, false), a, b, c, start)); |
| 84 | } |
| 85 | |
| 86 | Node* Phi(Node* a, Node* b, Node* c, Node* d) { |
| 87 | return SetSelfReferences(graph.NewNode(op(4, false), a, b, c, d, start)); |
| 88 | } |
| 89 | |
| 90 | Node* EffectPhi(Node* a) { |
| 91 | return SetSelfReferences(graph.NewNode(op(1, true), a, start)); |
| 92 | } |
| 93 | |
| 94 | Node* EffectPhi(Node* a, Node* b) { |
| 95 | return SetSelfReferences(graph.NewNode(op(2, true), a, b, start)); |
| 96 | } |
| 97 | |
| 98 | Node* EffectPhi(Node* a, Node* b, Node* c) { |
| 99 | return SetSelfReferences(graph.NewNode(op(3, true), a, b, c, start)); |
| 100 | } |
| 101 | |
| 102 | Node* EffectPhi(Node* a, Node* b, Node* c, Node* d) { |
| 103 | return SetSelfReferences(graph.NewNode(op(4, true), a, b, c, d, start)); |
| 104 | } |
| 105 | |
| 106 | Node* SetSelfReferences(Node* node) { |
| 107 | for (Edge edge : node->input_edges()) { |
| 108 | if (edge.to() == self) node->ReplaceInput(edge.index(), node); |
| 109 | } |
| 110 | return node; |
| 111 | } |
| 112 | |
| 113 | const Operator* op(int count, bool effect) { |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 114 | return effect ? common.EffectPhi(count) |
| 115 | : common.Phi(MachineRepresentation::kTagged, count); |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 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 | } |
Ben Murdoch | da12d29 | 2016-06-02 14:46:10 +0100 | [diff] [blame] | 130 | Zone zone(main_isolate()->allocator()); |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 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]); |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 139 | CHECK(loop); |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 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())); |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 149 | // TODO(turbofan): O(n^2) set equivalence in this test. |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 150 | for (int i = 0; i < body_count; i++) { |
| 151 | // Each body node should be contained in the loop. |
| 152 | CHECK(tree->Contains(loop, body[i])); |
| 153 | CheckRangeContains(tree->BodyNodes(loop), body[i]); |
| 154 | } |
| 155 | } |
| 156 | |
| 157 | void CheckRangeContains(NodeRange range, Node* node) { |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 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); |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 167 | CHECK(loop); |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 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 | } |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 181 | |
| 182 | Zone* zone() { return main_zone(); } |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 183 | }; |
| 184 | |
| 185 | |
| 186 | struct While { |
| 187 | LoopFinderTester& t; |
| 188 | Node* branch; |
| 189 | Node* if_true; |
| 190 | Node* exit; |
| 191 | Node* loop; |
| 192 | |
| 193 | While(LoopFinderTester& R, Node* cond) : t(R) { |
| 194 | loop = t.graph.NewNode(t.common.Loop(2), t.start, t.start); |
| 195 | branch = t.graph.NewNode(t.common.Branch(), cond, loop); |
| 196 | if_true = t.graph.NewNode(t.common.IfTrue(), branch); |
| 197 | exit = t.graph.NewNode(t.common.IfFalse(), branch); |
| 198 | loop->ReplaceInput(1, if_true); |
| 199 | } |
| 200 | |
| 201 | void chain(Node* control) { loop->ReplaceInput(0, control); } |
| 202 | void nest(While& that) { |
| 203 | that.loop->ReplaceInput(1, exit); |
| 204 | this->loop->ReplaceInput(0, that.if_true); |
| 205 | } |
| 206 | }; |
| 207 | |
| 208 | |
| 209 | struct Counter { |
| 210 | Node* base; |
| 211 | Node* inc; |
| 212 | Node* phi; |
| 213 | Node* add; |
| 214 | |
| 215 | Counter(While& w, int32_t b, int32_t k) |
| 216 | : base(w.t.jsgraph.Int32Constant(b)), inc(w.t.jsgraph.Int32Constant(k)) { |
| 217 | Build(w); |
| 218 | } |
| 219 | |
| 220 | Counter(While& w, Node* b, Node* k) : base(b), inc(k) { Build(w); } |
| 221 | |
| 222 | void Build(While& w) { |
| 223 | phi = w.t.graph.NewNode(w.t.op(2, false), base, base, w.loop); |
| 224 | add = w.t.graph.NewNode(&kIntAdd, phi, inc); |
| 225 | phi->ReplaceInput(1, add); |
| 226 | } |
| 227 | }; |
| 228 | |
| 229 | |
| 230 | struct StoreLoop { |
| 231 | Node* base; |
| 232 | Node* val; |
| 233 | Node* phi; |
| 234 | Node* store; |
| 235 | |
| 236 | explicit StoreLoop(While& w) |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 237 | : base(w.t.graph.start()), val(w.t.jsgraph.Int32Constant(13)) { |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 238 | Build(w); |
| 239 | } |
| 240 | |
| 241 | StoreLoop(While& w, Node* b, Node* v) : base(b), val(v) { Build(w); } |
| 242 | |
| 243 | void Build(While& w) { |
| 244 | phi = w.t.graph.NewNode(w.t.op(2, true), base, base, w.loop); |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 245 | store = w.t.graph.NewNode(&kStore, val, phi, w.loop); |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 246 | phi->ReplaceInput(1, store); |
| 247 | } |
| 248 | }; |
| 249 | |
| 250 | |
| 251 | TEST(LaLoop1) { |
| 252 | // One loop. |
| 253 | LoopFinderTester t; |
| 254 | While w(t, t.p0); |
| 255 | t.Return(t.p0, t.start, w.exit); |
| 256 | |
| 257 | Node* chain[] = {w.loop}; |
| 258 | t.CheckNestedLoops(chain, 1); |
| 259 | |
| 260 | Node* header[] = {w.loop}; |
| 261 | Node* body[] = {w.branch, w.if_true}; |
| 262 | t.CheckLoop(header, 1, body, 2); |
| 263 | } |
| 264 | |
| 265 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 266 | TEST(LaLoop1phi) { |
| 267 | // One loop with a simple phi. |
| 268 | LoopFinderTester t; |
| 269 | While w(t, t.p0); |
| 270 | Node* phi = t.graph.NewNode(t.common.Phi(MachineRepresentation::kTagged, 2), |
| 271 | t.zero, t.one, w.loop); |
| 272 | t.Return(phi, t.start, w.exit); |
| 273 | |
| 274 | Node* chain[] = {w.loop}; |
| 275 | t.CheckNestedLoops(chain, 1); |
| 276 | |
| 277 | Node* header[] = {w.loop, phi}; |
| 278 | Node* body[] = {w.branch, w.if_true}; |
| 279 | t.CheckLoop(header, 2, body, 2); |
| 280 | } |
| 281 | |
| 282 | |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 283 | TEST(LaLoop1c) { |
| 284 | // One loop with a counter. |
| 285 | LoopFinderTester t; |
| 286 | While w(t, t.p0); |
| 287 | Counter c(w, 0, 1); |
| 288 | t.Return(c.phi, t.start, w.exit); |
| 289 | |
| 290 | Node* chain[] = {w.loop}; |
| 291 | t.CheckNestedLoops(chain, 1); |
| 292 | |
| 293 | Node* header[] = {w.loop, c.phi}; |
| 294 | Node* body[] = {w.branch, w.if_true, c.add}; |
| 295 | t.CheckLoop(header, 2, body, 3); |
| 296 | } |
| 297 | |
| 298 | |
| 299 | TEST(LaLoop1e) { |
| 300 | // One loop with an effect phi. |
| 301 | LoopFinderTester t; |
| 302 | While w(t, t.p0); |
| 303 | StoreLoop c(w); |
| 304 | t.Return(t.p0, c.phi, w.exit); |
| 305 | |
| 306 | Node* chain[] = {w.loop}; |
| 307 | t.CheckNestedLoops(chain, 1); |
| 308 | |
| 309 | Node* header[] = {w.loop, c.phi}; |
| 310 | Node* body[] = {w.branch, w.if_true, c.store}; |
| 311 | t.CheckLoop(header, 2, body, 3); |
| 312 | } |
| 313 | |
| 314 | |
| 315 | TEST(LaLoop1d) { |
| 316 | // One loop with two counters. |
| 317 | LoopFinderTester t; |
| 318 | While w(t, t.p0); |
| 319 | Counter c1(w, 0, 1); |
| 320 | Counter c2(w, 1, 1); |
| 321 | t.Return(t.graph.NewNode(&kIntAdd, c1.phi, c2.phi), t.start, w.exit); |
| 322 | |
| 323 | Node* chain[] = {w.loop}; |
| 324 | t.CheckNestedLoops(chain, 1); |
| 325 | |
| 326 | Node* header[] = {w.loop, c1.phi, c2.phi}; |
| 327 | Node* body[] = {w.branch, w.if_true, c1.add, c2.add}; |
| 328 | t.CheckLoop(header, 3, body, 4); |
| 329 | } |
| 330 | |
| 331 | |
| 332 | TEST(LaLoop2) { |
| 333 | // One loop following another. |
| 334 | LoopFinderTester t; |
| 335 | While w1(t, t.p0); |
| 336 | While w2(t, t.p0); |
| 337 | w2.chain(w1.exit); |
| 338 | t.Return(t.p0, t.start, w2.exit); |
| 339 | |
| 340 | { |
| 341 | Node* chain[] = {w1.loop}; |
| 342 | t.CheckNestedLoops(chain, 1); |
| 343 | |
| 344 | Node* header[] = {w1.loop}; |
| 345 | Node* body[] = {w1.branch, w1.if_true}; |
| 346 | t.CheckLoop(header, 1, body, 2); |
| 347 | } |
| 348 | |
| 349 | { |
| 350 | Node* chain[] = {w2.loop}; |
| 351 | t.CheckNestedLoops(chain, 1); |
| 352 | |
| 353 | Node* header[] = {w2.loop}; |
| 354 | Node* body[] = {w2.branch, w2.if_true}; |
| 355 | t.CheckLoop(header, 1, body, 2); |
| 356 | } |
| 357 | } |
| 358 | |
| 359 | |
| 360 | TEST(LaLoop2c) { |
| 361 | // One loop following another, each with counters. |
| 362 | LoopFinderTester t; |
| 363 | While w1(t, t.p0); |
| 364 | While w2(t, t.p0); |
| 365 | Counter c1(w1, 0, 1); |
| 366 | Counter c2(w2, 0, 1); |
| 367 | w2.chain(w1.exit); |
| 368 | t.Return(t.graph.NewNode(&kIntAdd, c1.phi, c2.phi), t.start, w2.exit); |
| 369 | |
| 370 | { |
| 371 | Node* chain[] = {w1.loop}; |
| 372 | t.CheckNestedLoops(chain, 1); |
| 373 | |
| 374 | Node* header[] = {w1.loop, c1.phi}; |
| 375 | Node* body[] = {w1.branch, w1.if_true, c1.add}; |
| 376 | t.CheckLoop(header, 2, body, 3); |
| 377 | } |
| 378 | |
| 379 | { |
| 380 | Node* chain[] = {w2.loop}; |
| 381 | t.CheckNestedLoops(chain, 1); |
| 382 | |
| 383 | Node* header[] = {w2.loop, c2.phi}; |
| 384 | Node* body[] = {w2.branch, w2.if_true, c2.add}; |
| 385 | t.CheckLoop(header, 2, body, 3); |
| 386 | } |
| 387 | } |
| 388 | |
| 389 | |
| 390 | TEST(LaLoop2cc) { |
| 391 | // One loop following another; second loop uses phi from first. |
| 392 | for (int i = 0; i < 8; i++) { |
| 393 | LoopFinderTester t; |
| 394 | While w1(t, t.p0); |
| 395 | While w2(t, t.p0); |
| 396 | Counter c1(w1, 0, 1); |
| 397 | |
| 398 | // various usage scenarios for the second loop. |
| 399 | Counter c2(w2, i & 1 ? t.p0 : c1.phi, i & 2 ? t.p0 : c1.phi); |
| 400 | if (i & 3) w2.branch->ReplaceInput(0, c1.phi); |
| 401 | |
| 402 | w2.chain(w1.exit); |
| 403 | t.Return(t.graph.NewNode(&kIntAdd, c1.phi, c2.phi), t.start, w2.exit); |
| 404 | |
| 405 | { |
| 406 | Node* chain[] = {w1.loop}; |
| 407 | t.CheckNestedLoops(chain, 1); |
| 408 | |
| 409 | Node* header[] = {w1.loop, c1.phi}; |
| 410 | Node* body[] = {w1.branch, w1.if_true, c1.add}; |
| 411 | t.CheckLoop(header, 2, body, 3); |
| 412 | } |
| 413 | |
| 414 | { |
| 415 | Node* chain[] = {w2.loop}; |
| 416 | t.CheckNestedLoops(chain, 1); |
| 417 | |
| 418 | Node* header[] = {w2.loop, c2.phi}; |
| 419 | Node* body[] = {w2.branch, w2.if_true, c2.add}; |
| 420 | t.CheckLoop(header, 2, body, 3); |
| 421 | } |
| 422 | } |
| 423 | } |
| 424 | |
| 425 | |
| 426 | TEST(LaNestedLoop1) { |
| 427 | // One loop nested in another. |
| 428 | LoopFinderTester t; |
| 429 | While w1(t, t.p0); |
| 430 | While w2(t, t.p0); |
| 431 | w2.nest(w1); |
| 432 | t.Return(t.p0, t.start, w1.exit); |
| 433 | |
| 434 | Node* chain[] = {w1.loop, w2.loop}; |
| 435 | t.CheckNestedLoops(chain, 2); |
| 436 | |
| 437 | Node* h1[] = {w1.loop}; |
| 438 | Node* b1[] = {w1.branch, w1.if_true, w2.loop, w2.branch, w2.if_true, w2.exit}; |
| 439 | t.CheckLoop(h1, 1, b1, 6); |
| 440 | |
| 441 | Node* h2[] = {w2.loop}; |
| 442 | Node* b2[] = {w2.branch, w2.if_true}; |
| 443 | t.CheckLoop(h2, 1, b2, 2); |
| 444 | } |
| 445 | |
| 446 | |
| 447 | TEST(LaNestedLoop1c) { |
| 448 | // One loop nested in another, each with a counter. |
| 449 | LoopFinderTester t; |
| 450 | While w1(t, t.p0); |
| 451 | While w2(t, t.p0); |
| 452 | Counter c1(w1, 0, 1); |
| 453 | Counter c2(w2, 0, 1); |
| 454 | w2.branch->ReplaceInput(0, c2.phi); |
| 455 | w2.nest(w1); |
| 456 | t.Return(c1.phi, t.start, w1.exit); |
| 457 | |
| 458 | Node* chain[] = {w1.loop, w2.loop}; |
| 459 | t.CheckNestedLoops(chain, 2); |
| 460 | |
| 461 | Node* h1[] = {w1.loop, c1.phi}; |
| 462 | Node* b1[] = {w1.branch, w1.if_true, w2.loop, w2.branch, w2.if_true, |
| 463 | w2.exit, c2.phi, c1.add, c2.add}; |
| 464 | t.CheckLoop(h1, 2, b1, 9); |
| 465 | |
| 466 | Node* h2[] = {w2.loop, c2.phi}; |
| 467 | Node* b2[] = {w2.branch, w2.if_true, c2.add}; |
| 468 | t.CheckLoop(h2, 2, b2, 3); |
| 469 | } |
| 470 | |
| 471 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 472 | TEST(LaNestedLoop1x) { |
| 473 | // One loop nested in another. |
| 474 | LoopFinderTester t; |
| 475 | While w1(t, t.p0); |
| 476 | While w2(t, t.p0); |
| 477 | w2.nest(w1); |
| 478 | |
| 479 | const Operator* op = t.common.Phi(MachineRepresentation::kWord32, 2); |
| 480 | Node* p1a = t.graph.NewNode(op, t.p0, t.p0, w1.loop); |
| 481 | Node* p1b = t.graph.NewNode(op, t.p0, t.p0, w1.loop); |
| 482 | Node* p2a = t.graph.NewNode(op, p1a, t.p0, w2.loop); |
| 483 | Node* p2b = t.graph.NewNode(op, p1b, t.p0, w2.loop); |
| 484 | |
| 485 | p1a->ReplaceInput(1, p2b); |
| 486 | p1b->ReplaceInput(1, p2a); |
| 487 | |
| 488 | p2a->ReplaceInput(1, p2b); |
| 489 | p2b->ReplaceInput(1, p2a); |
| 490 | |
| 491 | t.Return(t.p0, t.start, w1.exit); |
| 492 | |
| 493 | Node* chain[] = {w1.loop, w2.loop}; |
| 494 | t.CheckNestedLoops(chain, 2); |
| 495 | |
| 496 | Node* h1[] = {w1.loop, p1a, p1b}; |
| 497 | Node* b1[] = {w1.branch, w1.if_true, w2.loop, p2a, |
| 498 | p2b, w2.branch, w2.if_true, w2.exit}; |
| 499 | t.CheckLoop(h1, 3, b1, 8); |
| 500 | |
| 501 | Node* h2[] = {w2.loop, p2a, p2b}; |
| 502 | Node* b2[] = {w2.branch, w2.if_true}; |
| 503 | t.CheckLoop(h2, 3, b2, 2); |
| 504 | } |
| 505 | |
| 506 | |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 507 | TEST(LaNestedLoop2) { |
| 508 | // Two loops nested in an outer loop. |
| 509 | LoopFinderTester t; |
| 510 | While w1(t, t.p0); |
| 511 | While w2(t, t.p0); |
| 512 | While w3(t, t.p0); |
| 513 | w2.nest(w1); |
| 514 | w3.nest(w1); |
| 515 | w3.chain(w2.exit); |
| 516 | t.Return(t.p0, t.start, w1.exit); |
| 517 | |
| 518 | Node* chain1[] = {w1.loop, w2.loop}; |
| 519 | t.CheckNestedLoops(chain1, 2); |
| 520 | |
| 521 | Node* chain2[] = {w1.loop, w3.loop}; |
| 522 | t.CheckNestedLoops(chain2, 2); |
| 523 | |
| 524 | Node* h1[] = {w1.loop}; |
| 525 | Node* b1[] = {w1.branch, w1.if_true, w2.loop, w2.branch, w2.if_true, |
| 526 | w2.exit, w3.loop, w3.branch, w3.if_true, w3.exit}; |
| 527 | t.CheckLoop(h1, 1, b1, 10); |
| 528 | |
| 529 | Node* h2[] = {w2.loop}; |
| 530 | Node* b2[] = {w2.branch, w2.if_true}; |
| 531 | t.CheckLoop(h2, 1, b2, 2); |
| 532 | |
| 533 | Node* h3[] = {w3.loop}; |
| 534 | Node* b3[] = {w3.branch, w3.if_true}; |
| 535 | t.CheckLoop(h3, 1, b3, 2); |
| 536 | } |
| 537 | |
| 538 | |
| 539 | TEST(LaNestedLoop3) { |
| 540 | // Three nested loops. |
| 541 | LoopFinderTester t; |
| 542 | While w1(t, t.p0); |
| 543 | While w2(t, t.p0); |
| 544 | While w3(t, t.p0); |
| 545 | w2.loop->ReplaceInput(0, w1.if_true); |
| 546 | w3.loop->ReplaceInput(0, w2.if_true); |
| 547 | w2.loop->ReplaceInput(1, w3.exit); |
| 548 | w1.loop->ReplaceInput(1, w2.exit); |
| 549 | t.Return(t.p0, t.start, w1.exit); |
| 550 | |
| 551 | Node* chain[] = {w1.loop, w2.loop, w3.loop}; |
| 552 | t.CheckNestedLoops(chain, 3); |
| 553 | |
| 554 | Node* h1[] = {w1.loop}; |
| 555 | Node* b1[] = {w1.branch, w1.if_true, w2.loop, w2.branch, w2.if_true, |
| 556 | w2.exit, w3.loop, w3.branch, w3.if_true, w3.exit}; |
| 557 | t.CheckLoop(h1, 1, b1, 10); |
| 558 | |
| 559 | Node* h2[] = {w2.loop}; |
| 560 | Node* b2[] = {w2.branch, w2.if_true, w3.loop, w3.branch, w3.if_true, w3.exit}; |
| 561 | t.CheckLoop(h2, 1, b2, 6); |
| 562 | |
| 563 | Node* h3[] = {w3.loop}; |
| 564 | Node* b3[] = {w3.branch, w3.if_true}; |
| 565 | t.CheckLoop(h3, 1, b3, 2); |
| 566 | } |
| 567 | |
| 568 | |
| 569 | TEST(LaNestedLoop3c) { |
| 570 | // Three nested loops with counters. |
| 571 | LoopFinderTester t; |
| 572 | While w1(t, t.p0); |
| 573 | Counter c1(w1, 0, 1); |
| 574 | While w2(t, t.p0); |
| 575 | Counter c2(w2, 0, 1); |
| 576 | While w3(t, t.p0); |
| 577 | Counter c3(w3, 0, 1); |
| 578 | w2.loop->ReplaceInput(0, w1.if_true); |
| 579 | w3.loop->ReplaceInput(0, w2.if_true); |
| 580 | w2.loop->ReplaceInput(1, w3.exit); |
| 581 | w1.loop->ReplaceInput(1, w2.exit); |
| 582 | w1.branch->ReplaceInput(0, c1.phi); |
| 583 | w2.branch->ReplaceInput(0, c2.phi); |
| 584 | w3.branch->ReplaceInput(0, c3.phi); |
| 585 | t.Return(c1.phi, t.start, w1.exit); |
| 586 | |
| 587 | Node* chain[] = {w1.loop, w2.loop, w3.loop}; |
| 588 | t.CheckNestedLoops(chain, 3); |
| 589 | |
| 590 | Node* h1[] = {w1.loop, c1.phi}; |
| 591 | Node* b1[] = {w1.branch, w1.if_true, c1.add, c2.add, c2.add, |
| 592 | c2.phi, c3.phi, w2.loop, w2.branch, w2.if_true, |
| 593 | w2.exit, w3.loop, w3.branch, w3.if_true, w3.exit}; |
| 594 | t.CheckLoop(h1, 2, b1, 15); |
| 595 | |
| 596 | Node* h2[] = {w2.loop, c2.phi}; |
| 597 | Node* b2[] = {w2.branch, w2.if_true, c2.add, c3.add, c3.phi, |
| 598 | w3.loop, w3.branch, w3.if_true, w3.exit}; |
| 599 | t.CheckLoop(h2, 2, b2, 9); |
| 600 | |
| 601 | Node* h3[] = {w3.loop, c3.phi}; |
| 602 | Node* b3[] = {w3.branch, w3.if_true, c3.add}; |
| 603 | t.CheckLoop(h3, 2, b3, 3); |
| 604 | } |
| 605 | |
| 606 | |
| 607 | TEST(LaMultipleExit1) { |
| 608 | const int kMaxExits = 10; |
| 609 | Node* merge[1 + kMaxExits]; |
| 610 | Node* body[2 * kMaxExits]; |
| 611 | |
| 612 | // A single loop with {i} exits. |
| 613 | for (int i = 1; i < kMaxExits; i++) { |
| 614 | LoopFinderTester t; |
| 615 | Node* cond = t.p0; |
| 616 | |
| 617 | int merge_count = 0; |
| 618 | int body_count = 0; |
| 619 | Node* loop = t.graph.NewNode(t.common.Loop(2), t.start, t.start); |
| 620 | Node* last = loop; |
| 621 | |
| 622 | for (int e = 0; e < i; e++) { |
| 623 | Node* branch = t.graph.NewNode(t.common.Branch(), cond, last); |
| 624 | Node* if_true = t.graph.NewNode(t.common.IfTrue(), branch); |
| 625 | Node* exit = t.graph.NewNode(t.common.IfFalse(), branch); |
| 626 | last = if_true; |
| 627 | |
| 628 | body[body_count++] = branch; |
| 629 | body[body_count++] = if_true; |
| 630 | merge[merge_count++] = exit; |
| 631 | } |
| 632 | |
| 633 | loop->ReplaceInput(1, last); // form loop backedge. |
| 634 | Node* end = t.graph.NewNode(t.common.Merge(i), i, merge); // form exit. |
| 635 | t.graph.SetEnd(end); |
| 636 | |
| 637 | Node* h[] = {loop}; |
| 638 | t.CheckLoop(h, 1, body, body_count); |
| 639 | } |
| 640 | } |
| 641 | |
| 642 | |
| 643 | TEST(LaMultipleBackedge1) { |
| 644 | const int kMaxBackedges = 10; |
| 645 | Node* loop_inputs[1 + kMaxBackedges]; |
| 646 | Node* body[3 * kMaxBackedges]; |
| 647 | |
| 648 | // A single loop with {i} backedges. |
| 649 | for (int i = 1; i < kMaxBackedges; i++) { |
| 650 | LoopFinderTester t; |
| 651 | |
| 652 | for (int j = 0; j <= i; j++) loop_inputs[j] = t.start; |
| 653 | Node* loop = t.graph.NewNode(t.common.Loop(1 + i), 1 + i, loop_inputs); |
| 654 | |
| 655 | Node* cond = t.p0; |
| 656 | int body_count = 0; |
| 657 | Node* exit = loop; |
| 658 | |
| 659 | for (int b = 0; b < i; b++) { |
| 660 | Node* branch = t.graph.NewNode(t.common.Branch(), cond, exit); |
| 661 | Node* if_true = t.graph.NewNode(t.common.IfTrue(), branch); |
| 662 | Node* if_false = t.graph.NewNode(t.common.IfFalse(), branch); |
| 663 | exit = if_false; |
| 664 | |
| 665 | body[body_count++] = branch; |
| 666 | body[body_count++] = if_true; |
| 667 | if (b != (i - 1)) body[body_count++] = if_false; |
| 668 | |
| 669 | loop->ReplaceInput(1 + b, if_true); |
| 670 | } |
| 671 | |
| 672 | t.graph.SetEnd(exit); |
| 673 | |
| 674 | Node* h[] = {loop}; |
| 675 | t.CheckLoop(h, 1, body, body_count); |
| 676 | } |
| 677 | } |
| 678 | |
| 679 | |
| 680 | TEST(LaEdgeMatrix1) { |
| 681 | // Test various kinds of extra edges added to a simple loop. |
| 682 | for (int i = 0; i < 3; i++) { |
| 683 | for (int j = 0; j < 3; j++) { |
| 684 | for (int k = 0; k < 3; k++) { |
| 685 | LoopFinderTester t; |
| 686 | |
| 687 | Node* p1 = t.jsgraph.Int32Constant(11); |
| 688 | Node* p2 = t.jsgraph.Int32Constant(22); |
| 689 | Node* p3 = t.jsgraph.Int32Constant(33); |
| 690 | |
| 691 | Node* loop = t.graph.NewNode(t.common.Loop(2), t.start, t.start); |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 692 | Node* phi = t.graph.NewNode( |
| 693 | t.common.Phi(MachineRepresentation::kWord32, 2), t.one, p1, loop); |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 694 | Node* cond = t.graph.NewNode(&kIntAdd, phi, p2); |
| 695 | Node* branch = t.graph.NewNode(t.common.Branch(), cond, loop); |
| 696 | Node* if_true = t.graph.NewNode(t.common.IfTrue(), branch); |
| 697 | Node* exit = t.graph.NewNode(t.common.IfFalse(), branch); |
| 698 | loop->ReplaceInput(1, if_true); |
| 699 | Node* ret = t.graph.NewNode(t.common.Return(), p3, t.start, exit); |
| 700 | t.graph.SetEnd(ret); |
| 701 | |
| 702 | Node* choices[] = {p1, phi, cond}; |
| 703 | p1->ReplaceUses(choices[i]); |
| 704 | p2->ReplaceUses(choices[j]); |
| 705 | p3->ReplaceUses(choices[k]); |
| 706 | |
| 707 | Node* header[] = {loop, phi}; |
| 708 | Node* body[] = {cond, branch, if_true}; |
| 709 | t.CheckLoop(header, 2, body, 3); |
| 710 | } |
| 711 | } |
| 712 | } |
| 713 | } |
| 714 | |
| 715 | |
| 716 | void RunEdgeMatrix2(int i) { |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 717 | CHECK(i >= 0 && i < 5); |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 718 | for (int j = 0; j < 5; j++) { |
| 719 | for (int k = 0; k < 5; k++) { |
| 720 | LoopFinderTester t; |
| 721 | |
| 722 | Node* p1 = t.jsgraph.Int32Constant(11); |
| 723 | Node* p2 = t.jsgraph.Int32Constant(22); |
| 724 | Node* p3 = t.jsgraph.Int32Constant(33); |
| 725 | |
| 726 | // outer loop. |
| 727 | Node* loop1 = t.graph.NewNode(t.common.Loop(2), t.start, t.start); |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 728 | Node* phi1 = t.graph.NewNode( |
| 729 | t.common.Phi(MachineRepresentation::kWord32, 2), t.one, p1, loop1); |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 730 | Node* cond1 = t.graph.NewNode(&kIntAdd, phi1, t.one); |
| 731 | Node* branch1 = t.graph.NewNode(t.common.Branch(), cond1, loop1); |
| 732 | Node* if_true1 = t.graph.NewNode(t.common.IfTrue(), branch1); |
| 733 | Node* exit1 = t.graph.NewNode(t.common.IfFalse(), branch1); |
| 734 | |
| 735 | // inner loop. |
| 736 | Node* loop2 = t.graph.NewNode(t.common.Loop(2), if_true1, t.start); |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 737 | Node* phi2 = t.graph.NewNode( |
| 738 | t.common.Phi(MachineRepresentation::kWord32, 2), t.one, p2, loop2); |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 739 | Node* cond2 = t.graph.NewNode(&kIntAdd, phi2, p3); |
| 740 | Node* branch2 = t.graph.NewNode(t.common.Branch(), cond2, loop2); |
| 741 | Node* if_true2 = t.graph.NewNode(t.common.IfTrue(), branch2); |
| 742 | Node* exit2 = t.graph.NewNode(t.common.IfFalse(), branch2); |
| 743 | loop2->ReplaceInput(1, if_true2); |
| 744 | loop1->ReplaceInput(1, exit2); |
| 745 | |
| 746 | Node* ret = t.graph.NewNode(t.common.Return(), phi1, t.start, exit1); |
| 747 | t.graph.SetEnd(ret); |
| 748 | |
| 749 | Node* choices[] = {p1, phi1, cond1, phi2, cond2}; |
| 750 | p1->ReplaceUses(choices[i]); |
| 751 | p2->ReplaceUses(choices[j]); |
| 752 | p3->ReplaceUses(choices[k]); |
| 753 | |
| 754 | Node* header1[] = {loop1, phi1}; |
| 755 | Node* body1[] = {cond1, branch1, if_true1, exit2, loop2, |
| 756 | phi2, cond2, branch2, if_true2}; |
| 757 | t.CheckLoop(header1, 2, body1, 9); |
| 758 | |
| 759 | Node* header2[] = {loop2, phi2}; |
| 760 | Node* body2[] = {cond2, branch2, if_true2}; |
| 761 | t.CheckLoop(header2, 2, body2, 3); |
| 762 | |
| 763 | Node* chain[] = {loop1, loop2}; |
| 764 | t.CheckNestedLoops(chain, 2); |
| 765 | } |
| 766 | } |
| 767 | } |
| 768 | |
| 769 | |
| 770 | TEST(LaEdgeMatrix2_0) { RunEdgeMatrix2(0); } |
| 771 | |
| 772 | |
| 773 | TEST(LaEdgeMatrix2_1) { RunEdgeMatrix2(1); } |
| 774 | |
| 775 | |
| 776 | TEST(LaEdgeMatrix2_2) { RunEdgeMatrix2(2); } |
| 777 | |
| 778 | |
| 779 | TEST(LaEdgeMatrix2_3) { RunEdgeMatrix2(3); } |
| 780 | |
| 781 | |
| 782 | TEST(LaEdgeMatrix2_4) { RunEdgeMatrix2(4); } |
| 783 | |
| 784 | |
| 785 | // Generates a triply-nested loop with extra edges between the phis and |
| 786 | // conditions according to the edge choice parameters. |
| 787 | void RunEdgeMatrix3(int c1a, int c1b, int c1c, // line break |
| 788 | int c2a, int c2b, int c2c, // line break |
| 789 | int c3a, int c3b, int c3c) { // line break |
| 790 | LoopFinderTester t; |
| 791 | |
| 792 | Node* p1a = t.jsgraph.Int32Constant(11); |
| 793 | Node* p1b = t.jsgraph.Int32Constant(22); |
| 794 | Node* p1c = t.jsgraph.Int32Constant(33); |
| 795 | Node* p2a = t.jsgraph.Int32Constant(44); |
| 796 | Node* p2b = t.jsgraph.Int32Constant(55); |
| 797 | Node* p2c = t.jsgraph.Int32Constant(66); |
| 798 | Node* p3a = t.jsgraph.Int32Constant(77); |
| 799 | Node* p3b = t.jsgraph.Int32Constant(88); |
| 800 | Node* p3c = t.jsgraph.Int32Constant(99); |
| 801 | |
| 802 | // L1 depth = 0 |
| 803 | Node* loop1 = t.graph.NewNode(t.common.Loop(2), t.start, t.start); |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 804 | Node* phi1 = t.graph.NewNode(t.common.Phi(MachineRepresentation::kWord32, 2), |
| 805 | p1a, p1c, loop1); |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 806 | Node* cond1 = t.graph.NewNode(&kIntAdd, phi1, p1b); |
| 807 | Node* branch1 = t.graph.NewNode(t.common.Branch(), cond1, loop1); |
| 808 | Node* if_true1 = t.graph.NewNode(t.common.IfTrue(), branch1); |
| 809 | Node* exit1 = t.graph.NewNode(t.common.IfFalse(), branch1); |
| 810 | |
| 811 | // L2 depth = 1 |
| 812 | Node* loop2 = t.graph.NewNode(t.common.Loop(2), if_true1, t.start); |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 813 | Node* phi2 = t.graph.NewNode(t.common.Phi(MachineRepresentation::kWord32, 2), |
| 814 | p2a, p2c, loop2); |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 815 | Node* cond2 = t.graph.NewNode(&kIntAdd, phi2, p2b); |
| 816 | Node* branch2 = t.graph.NewNode(t.common.Branch(), cond2, loop2); |
| 817 | Node* if_true2 = t.graph.NewNode(t.common.IfTrue(), branch2); |
| 818 | Node* exit2 = t.graph.NewNode(t.common.IfFalse(), branch2); |
| 819 | |
| 820 | // L3 depth = 2 |
| 821 | Node* loop3 = t.graph.NewNode(t.common.Loop(2), if_true2, t.start); |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 822 | Node* phi3 = t.graph.NewNode(t.common.Phi(MachineRepresentation::kWord32, 2), |
| 823 | p3a, p3c, loop3); |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 824 | Node* cond3 = t.graph.NewNode(&kIntAdd, phi3, p3b); |
| 825 | Node* branch3 = t.graph.NewNode(t.common.Branch(), cond3, loop3); |
| 826 | Node* if_true3 = t.graph.NewNode(t.common.IfTrue(), branch3); |
| 827 | Node* exit3 = t.graph.NewNode(t.common.IfFalse(), branch3); |
| 828 | |
| 829 | loop3->ReplaceInput(1, if_true3); |
| 830 | loop2->ReplaceInput(1, exit3); |
| 831 | loop1->ReplaceInput(1, exit2); |
| 832 | |
| 833 | Node* ret = t.graph.NewNode(t.common.Return(), phi1, t.start, exit1); |
| 834 | t.graph.SetEnd(ret); |
| 835 | |
| 836 | // Mutate the graph according to the edge choices. |
| 837 | |
| 838 | Node* o1[] = {t.one}; |
| 839 | Node* o2[] = {t.one, phi1, cond1}; |
| 840 | Node* o3[] = {t.one, phi1, cond1, phi2, cond2}; |
| 841 | |
| 842 | p1a->ReplaceUses(o1[c1a]); |
| 843 | p1b->ReplaceUses(o1[c1b]); |
| 844 | |
| 845 | p2a->ReplaceUses(o2[c2a]); |
| 846 | p2b->ReplaceUses(o2[c2b]); |
| 847 | |
| 848 | p3a->ReplaceUses(o3[c3a]); |
| 849 | p3b->ReplaceUses(o3[c3b]); |
| 850 | |
| 851 | Node* l2[] = {phi1, cond1, phi2, cond2}; |
| 852 | Node* l3[] = {phi1, cond1, phi2, cond2, phi3, cond3}; |
| 853 | |
| 854 | p1c->ReplaceUses(l2[c1c]); |
| 855 | p2c->ReplaceUses(l3[c2c]); |
| 856 | p3c->ReplaceUses(l3[c3c]); |
| 857 | |
| 858 | // Run the tests and verify loop structure. |
| 859 | |
| 860 | Node* chain[] = {loop1, loop2, loop3}; |
| 861 | t.CheckNestedLoops(chain, 3); |
| 862 | |
| 863 | Node* header1[] = {loop1, phi1}; |
| 864 | Node* body1[] = {cond1, branch1, if_true1, exit2, loop2, |
| 865 | phi2, cond2, branch2, if_true2, exit3, |
| 866 | loop3, phi3, cond3, branch3, if_true3}; |
| 867 | t.CheckLoop(header1, 2, body1, 15); |
| 868 | |
| 869 | Node* header2[] = {loop2, phi2}; |
| 870 | Node* body2[] = {cond2, branch2, if_true2, exit3, loop3, |
| 871 | phi3, cond3, branch3, if_true3}; |
| 872 | t.CheckLoop(header2, 2, body2, 9); |
| 873 | |
| 874 | Node* header3[] = {loop3, phi3}; |
| 875 | Node* body3[] = {cond3, branch3, if_true3}; |
| 876 | t.CheckLoop(header3, 2, body3, 3); |
| 877 | } |
| 878 | |
| 879 | |
| 880 | // Runs all combinations with a fixed {i}. |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 881 | static void RunEdgeMatrix3_i(int i) { |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 882 | for (int a = 0; a < 1; a++) { |
| 883 | for (int b = 0; b < 1; b++) { |
| 884 | for (int c = 0; c < 4; c++) { |
| 885 | for (int d = 0; d < 3; d++) { |
| 886 | for (int e = 0; e < 3; e++) { |
| 887 | for (int f = 0; f < 6; f++) { |
| 888 | for (int g = 0; g < 5; g++) { |
| 889 | for (int h = 0; h < 5; h++) { |
| 890 | RunEdgeMatrix3(a, b, c, d, e, f, g, h, i); |
| 891 | } |
| 892 | } |
| 893 | } |
| 894 | } |
| 895 | } |
| 896 | } |
| 897 | } |
| 898 | } |
| 899 | } |
| 900 | |
| 901 | |
| 902 | // Test all possible legal triply-nested loops with conditions and phis. |
| 903 | TEST(LaEdgeMatrix3_0) { RunEdgeMatrix3_i(0); } |
| 904 | |
| 905 | |
| 906 | TEST(LaEdgeMatrix3_1) { RunEdgeMatrix3_i(1); } |
| 907 | |
| 908 | |
| 909 | TEST(LaEdgeMatrix3_2) { RunEdgeMatrix3_i(2); } |
| 910 | |
| 911 | |
| 912 | TEST(LaEdgeMatrix3_3) { RunEdgeMatrix3_i(3); } |
| 913 | |
| 914 | |
| 915 | TEST(LaEdgeMatrix3_4) { RunEdgeMatrix3_i(4); } |
| 916 | |
| 917 | |
| 918 | TEST(LaEdgeMatrix3_5) { RunEdgeMatrix3_i(5); } |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 919 | |
| 920 | |
| 921 | static void RunManyChainedLoops_i(int count) { |
| 922 | LoopFinderTester t; |
| 923 | Node** nodes = t.zone()->NewArray<Node*>(count * 4); |
| 924 | Node* k11 = t.jsgraph.Int32Constant(11); |
| 925 | Node* k12 = t.jsgraph.Int32Constant(12); |
| 926 | Node* last = t.start; |
| 927 | |
| 928 | // Build loops. |
| 929 | for (int i = 0; i < count; i++) { |
| 930 | Node* loop = t.graph.NewNode(t.common.Loop(2), last, t.start); |
| 931 | Node* phi = t.graph.NewNode(t.common.Phi(MachineRepresentation::kWord32, 2), |
| 932 | k11, k12, loop); |
| 933 | Node* branch = t.graph.NewNode(t.common.Branch(), phi, loop); |
| 934 | Node* if_true = t.graph.NewNode(t.common.IfTrue(), branch); |
| 935 | Node* exit = t.graph.NewNode(t.common.IfFalse(), branch); |
| 936 | loop->ReplaceInput(1, if_true); |
| 937 | |
| 938 | nodes[i * 4 + 0] = loop; |
| 939 | nodes[i * 4 + 1] = phi; |
| 940 | nodes[i * 4 + 2] = branch; |
| 941 | nodes[i * 4 + 3] = if_true; |
| 942 | |
| 943 | last = exit; |
| 944 | } |
| 945 | |
| 946 | Node* ret = t.graph.NewNode(t.common.Return(), t.p0, t.start, last); |
| 947 | t.graph.SetEnd(ret); |
| 948 | |
| 949 | // Verify loops. |
| 950 | for (int i = 0; i < count; i++) { |
| 951 | t.CheckLoop(nodes + i * 4, 2, nodes + i * 4 + 2, 2); |
| 952 | } |
| 953 | } |
| 954 | |
| 955 | |
| 956 | static void RunManyNestedLoops_i(int count) { |
| 957 | LoopFinderTester t; |
| 958 | Node** nodes = t.zone()->NewArray<Node*>(count * 5); |
| 959 | Node* k11 = t.jsgraph.Int32Constant(11); |
| 960 | Node* k12 = t.jsgraph.Int32Constant(12); |
| 961 | Node* outer = nullptr; |
| 962 | Node* entry = t.start; |
| 963 | |
| 964 | // Build loops. |
| 965 | for (int i = 0; i < count; i++) { |
| 966 | Node* loop = t.graph.NewNode(t.common.Loop(2), entry, t.start); |
| 967 | Node* phi = t.graph.NewNode(t.common.Phi(MachineRepresentation::kWord32, 2), |
| 968 | k11, k12, loop); |
| 969 | Node* branch = t.graph.NewNode(t.common.Branch(), phi, loop); |
| 970 | Node* if_true = t.graph.NewNode(t.common.IfTrue(), branch); |
| 971 | Node* exit = t.graph.NewNode(t.common.IfFalse(), branch); |
| 972 | |
| 973 | nodes[i * 5 + 0] = exit; // outside |
| 974 | nodes[i * 5 + 1] = loop; // header |
| 975 | nodes[i * 5 + 2] = phi; // header |
| 976 | nodes[i * 5 + 3] = branch; // body |
| 977 | nodes[i * 5 + 4] = if_true; // body |
| 978 | |
| 979 | if (outer != nullptr) { |
| 980 | // inner loop. |
| 981 | outer->ReplaceInput(1, exit); |
| 982 | } else { |
| 983 | // outer loop. |
| 984 | Node* ret = t.graph.NewNode(t.common.Return(), t.p0, t.start, exit); |
| 985 | t.graph.SetEnd(ret); |
| 986 | } |
| 987 | outer = loop; |
| 988 | entry = if_true; |
| 989 | } |
| 990 | outer->ReplaceInput(1, entry); // innermost loop. |
| 991 | |
| 992 | // Verify loops. |
| 993 | for (int i = 0; i < count; i++) { |
| 994 | int k = i * 5; |
| 995 | t.CheckLoop(nodes + k + 1, 2, nodes + k + 3, count * 5 - k - 3); |
| 996 | } |
| 997 | } |
| 998 | |
| 999 | |
| 1000 | TEST(LaManyChained_30) { RunManyChainedLoops_i(30); } |
| 1001 | TEST(LaManyChained_31) { RunManyChainedLoops_i(31); } |
| 1002 | TEST(LaManyChained_32) { RunManyChainedLoops_i(32); } |
| 1003 | TEST(LaManyChained_33) { RunManyChainedLoops_i(33); } |
| 1004 | TEST(LaManyChained_34) { RunManyChainedLoops_i(34); } |
| 1005 | TEST(LaManyChained_62) { RunManyChainedLoops_i(62); } |
| 1006 | TEST(LaManyChained_63) { RunManyChainedLoops_i(63); } |
| 1007 | TEST(LaManyChained_64) { RunManyChainedLoops_i(64); } |
| 1008 | |
| 1009 | TEST(LaManyNested_30) { RunManyNestedLoops_i(30); } |
| 1010 | TEST(LaManyNested_31) { RunManyNestedLoops_i(31); } |
| 1011 | TEST(LaManyNested_32) { RunManyNestedLoops_i(32); } |
| 1012 | TEST(LaManyNested_33) { RunManyNestedLoops_i(33); } |
| 1013 | TEST(LaManyNested_34) { RunManyNestedLoops_i(34); } |
| 1014 | TEST(LaManyNested_62) { RunManyNestedLoops_i(62); } |
| 1015 | TEST(LaManyNested_63) { RunManyNestedLoops_i(63); } |
| 1016 | TEST(LaManyNested_64) { RunManyNestedLoops_i(64); } |
| 1017 | |
| 1018 | |
| 1019 | TEST(LaPhiTangle) { LoopFinderTester t; } |
| 1020 | |
| 1021 | } // namespace compiler |
| 1022 | } // namespace internal |
| 1023 | } // namespace v8 |