1// Copyright (c) 2018, the Dart project authors. Please see the AUTHORS file
2// for details. All rights reserved. Use of this source code is governed by a
3// BSD-style license that can be found in the LICENSE file.
4//
5// Unit tests specific to loops and induction variables.
6// Note, try to avoid relying on information that is subject
7// to change (block ids, variable numbers, etc.) in order
8// to make this test less sensitive to unrelated changes.
9
10#include "vm/compiler/backend/loops.h"
11#include "vm/compiler/backend/il_printer.h"
12#include "vm/compiler/backend/il_test_helper.h"
13#include "vm/compiler/backend/inliner.h"
14#include "vm/compiler/backend/type_propagator.h"
15#include "vm/compiler/compiler_pass.h"
16#include "vm/compiler/frontend/kernel_to_il.h"
17#include "vm/compiler/jit/jit_call_specializer.h"
18#include "vm/log.h"
19#include "vm/object.h"
20#include "vm/parser.h"
21#include "vm/symbols.h"
22#include "vm/unit_test.h"
23
24namespace dart {
25
26// Helper method to construct an induction debug string for loop hierarchy.
27void TestString(BaseTextBuffer* f,
28 LoopInfo* loop,
29 const GrowableArray<BlockEntryInstr*>& preorder) {
30 for (; loop != nullptr; loop = loop->next()) {
31 intptr_t depth = loop->NestingDepth();
32 f->Printf("%*c[%" Pd "\n", static_cast<int>(2 * depth), ' ', loop->id());
33 for (BitVector::Iterator block_it(loop->blocks()); !block_it.Done();
34 block_it.Advance()) {
35 BlockEntryInstr* block = preorder[block_it.Current()];
36 if (block->IsJoinEntry()) {
37 for (PhiIterator it(block->AsJoinEntry()); !it.Done(); it.Advance()) {
38 InductionVar* induc = loop->LookupInduction(it.Current());
39 if (induc != nullptr) {
40 // Obtain the debug string for induction and bounds.
41 f->Printf("%*c%s", static_cast<int>(2 * depth), ' ',
42 induc->ToCString());
43 for (auto bound : induc->bounds()) {
44 f->Printf(" %s", bound.limit_->ToCString());
45 }
46 f->AddString("\n");
47 }
48 }
49 }
50 for (ForwardInstructionIterator it(block); !it.Done(); it.Advance()) {
51 InductionVar* induc =
52 loop->LookupInduction(it.Current()->AsDefinition());
53 if (InductionVar::IsInduction(induc)) {
54 f->Printf("%*c%s\n", static_cast<int>(2 * depth), ' ',
55 induc->ToCString());
56 }
57 }
58 }
59 TestString(f, loop->inner(), preorder);
60 f->Printf("%*c]\n", static_cast<int>(2 * depth), ' ');
61 }
62}
63
64// Helper method to build CFG and compute induction.
65static const char* ComputeInduction(Thread* thread, const char* script_chars) {
66 // Load the script and exercise the code once.
67 const auto& root_library = Library::Handle(LoadTestScript(script_chars));
68 Invoke(root_library, "main");
69
70 std::initializer_list<CompilerPass::Id> passes = {
71 CompilerPass::kComputeSSA, CompilerPass::kTypePropagation,
72 CompilerPass::kApplyICData, CompilerPass::kSelectRepresentations,
73 CompilerPass::kTypePropagation, CompilerPass::kCanonicalize,
74 };
75 const auto& function = Function::Handle(GetFunction(root_library, "foo"));
76 TestPipeline pipeline(function, CompilerPass::kJIT);
77 FlowGraph* flow_graph = pipeline.RunPasses(passes);
78
79 // Build loop hierarchy and find induction.
80 const LoopHierarchy& hierarchy = flow_graph->GetLoopHierarchy();
81 hierarchy.ComputeInduction();
82 flow_graph->RemoveRedefinitions(); // don't query later
83
84 // Construct and return a debug string for testing.
85 char buffer[1024];
86 BufferFormatter f(buffer, sizeof(buffer));
87 TestString(&f, hierarchy.top(), flow_graph->preorder());
88 return Thread::Current()->zone()->MakeCopyOfString(buffer);
89}
90
91//
92// Induction tests.
93//
94
95ISOLATE_UNIT_TEST_CASE(BasicInductionUp) {
96 const char* script_chars =
97 R"(
98 foo() {
99 for (int i = 0; i < 100; i++) {
100 }
101 }
102 main() {
103 foo();
104 }
105 )";
106 const char* expected =
107 " [0\n"
108 " LIN(0 + 1 * i) 100\n" // phi
109 " LIN(1 + 1 * i)\n" // add
110 " ]\n";
111 EXPECT_STREQ(expected, ComputeInduction(thread, script_chars));
112}
113
114ISOLATE_UNIT_TEST_CASE(BasicInductionDown) {
115 const char* script_chars =
116 R"(
117 foo() {
118 for (int i = 100; i > 0; i--) {
119 }
120 }
121 main() {
122 foo();
123 }
124 )";
125 const char* expected =
126 " [0\n"
127 " LIN(100 + -1 * i) 0\n" // phi
128 " LIN(99 + -1 * i)\n" // sub
129 " ]\n";
130 EXPECT_STREQ(expected, ComputeInduction(thread, script_chars));
131}
132
133ISOLATE_UNIT_TEST_CASE(BasicInductionStepUp) {
134 const char* script_chars =
135 R"(
136 foo() {
137 for (int i = 10; i < 100; i += 2) {
138 }
139 }
140 main() {
141 foo();
142 }
143 )";
144 const char* expected =
145 " [0\n"
146 " LIN(10 + 2 * i)\n" // phi
147 " LIN(12 + 2 * i)\n" // add
148 " ]\n";
149 EXPECT_STREQ(expected, ComputeInduction(thread, script_chars));
150}
151
152ISOLATE_UNIT_TEST_CASE(BasicInductionStepDown) {
153 const char* script_chars =
154 R"(
155 foo() {
156 for (int i = 100; i >= 0; i -= 7) {
157 }
158 }
159 main() {
160 foo();
161 }
162 )";
163 const char* expected =
164 " [0\n"
165 " LIN(100 + -7 * i)\n" // phi
166 " LIN(93 + -7 * i)\n" // sub
167 " ]\n";
168 EXPECT_STREQ(expected, ComputeInduction(thread, script_chars));
169}
170
171ISOLATE_UNIT_TEST_CASE(BasicInductionLoopNest) {
172 const char* script_chars =
173 R"(
174 foo() {
175 for (int i = 0; i < 100; i++) {
176 for (int j = 1; j < 100; j++) {
177 for (int k = 2; k < 100; k++) {
178 }
179 }
180 }
181 }
182 main() {
183 foo();
184 }
185 )";
186 const char* expected =
187 " [2\n"
188 " LIN(0 + 1 * i) 100\n" // i
189 " LIN(1 + 1 * i)\n"
190 " [1\n"
191 " LIN(1 + 1 * i) 100\n" // j
192 " LIN(2 + 1 * i)\n"
193 " [0\n"
194 " LIN(2 + 1 * i) 100\n" // k
195 " LIN(3 + 1 * i)\n"
196 " ]\n"
197 " ]\n"
198 " ]\n";
199 EXPECT_STREQ(expected, ComputeInduction(thread, script_chars));
200}
201
202ISOLATE_UNIT_TEST_CASE(ChainInduction) {
203 const char* script_chars =
204 R"(
205 foo() {
206 int j = 1;
207 for (int i = 0; i < 100; i++) {
208 j += 5;
209 j += 7;
210 }
211 }
212 main() {
213 foo();
214 }
215 )";
216 const char* expected =
217 " [0\n"
218 " LIN(1 + 12 * i)\n" // phi (j)
219 " LIN(0 + 1 * i) 100\n" // phi
220 " LIN(6 + 12 * i)\n" // j-add
221 " LIN(13 + 12 * i)\n" // j-add
222 " LIN(1 + 1 * i)\n" // add
223 " ]\n";
224 EXPECT_STREQ(expected, ComputeInduction(thread, script_chars));
225}
226
227ISOLATE_UNIT_TEST_CASE(TwoWayInduction) {
228 const char* script_chars =
229 R"(
230 foo() {
231 int j = 123;
232 for (int i = 0; i < 100; i++) {
233 if (i == 10) {
234 j += 3;
235 } else {
236 j += 3;
237 }
238 }
239 }
240 main() {
241 foo();
242 }
243 )";
244 const char* expected =
245 " [0\n"
246 " LIN(123 + 3 * i)\n" // phi (j)
247 " LIN(0 + 1 * i) 100\n" // phi
248 " LIN(126 + 3 * i)\n" // j-true
249 " LIN(126 + 3 * i)\n" // j-false
250 " LIN(1 + 1 * i)\n" // add
251 " LIN(126 + 3 * i)\n" // phi (j)
252 " ]\n";
253 EXPECT_STREQ(expected, ComputeInduction(thread, script_chars));
254}
255
256ISOLATE_UNIT_TEST_CASE(DerivedInduction) {
257 const char* script_chars =
258 R"(
259 foo() {
260 for (int i = 1; i < 100; i++) {
261 int a = i + 3;
262 int b = i - 5;
263 int c = i * 7;
264 int d = - i;
265 }
266 }
267 main() {
268 foo();
269 }
270 )";
271 const char* expected =
272 " [0\n"
273 " LIN(1 + 1 * i) 100\n" // phi
274 " LIN(4 + 1 * i)\n" // a
275 " LIN(-4 + 1 * i)\n" // b
276 " LIN(7 + 7 * i)\n" // c
277 " LIN(-1 + -1 * i)\n" // d
278 " LIN(2 + 1 * i)\n" // add
279 " ]\n";
280 EXPECT_STREQ(expected, ComputeInduction(thread, script_chars));
281}
282
283ISOLATE_UNIT_TEST_CASE(WrapAroundAndDerived) {
284 const char* script_chars =
285 R"(
286 foo() {
287 int w = 99;
288 for (int i = 0; i < 100; i++) {
289 int a = w + 3;
290 int b = w - 5;
291 int c = w * 7;
292 int d = - w;
293 w = i;
294 }
295 }
296 main() {
297 foo();
298 }
299 )";
300 const char* expected =
301 " [0\n"
302 " WRAP(99, LIN(0 + 1 * i))\n" // phi (w)
303 " LIN(0 + 1 * i) 100\n" // phi
304 " WRAP(102, LIN(3 + 1 * i))\n" // a
305 " WRAP(94, LIN(-5 + 1 * i))\n" // b
306 " WRAP(693, LIN(0 + 7 * i))\n" // c
307 " WRAP(-99, LIN(0 + -1 * i))\n" // d
308 " LIN(1 + 1 * i)\n" // add
309 " ]\n";
310 EXPECT_STREQ(expected, ComputeInduction(thread, script_chars));
311}
312
313ISOLATE_UNIT_TEST_CASE(PeriodicAndDerived) {
314 const char* script_chars =
315 R"(
316 foo() {
317 int p1 = 3;
318 int p2 = 5;
319 for (int i = 0; i < 100; i++) {
320 int a = p1 + 3;
321 int b = p1 - 5;
322 int c = p1 * 7;
323 int d = - p1;
324 p1 = - p1;
325 p2 = 100 - p2;
326 }
327 }
328 main() {
329 foo();
330 }
331 )";
332 const char* expected =
333 " [0\n"
334 " PERIOD(3, -3)\n" // phi(p1)
335 " PERIOD(5, 95)\n" // phi(p2)
336 " LIN(0 + 1 * i) 100\n" // phi
337 " PERIOD(6, 0)\n" // a
338 " PERIOD(-2, -8)\n" // b
339 " PERIOD(21, -21)\n" // c
340 " PERIOD(-3, 3)\n" // d
341 " PERIOD(-3, 3)\n" // p1
342 " PERIOD(95, 5)\n" // p2
343 " LIN(1 + 1 * i)\n" // add
344 " ]\n";
345 EXPECT_STREQ(expected, ComputeInduction(thread, script_chars));
346}
347
348//
349// Bound specific tests.
350//
351
352ISOLATE_UNIT_TEST_CASE(NonStrictConditionUp) {
353 const char* script_chars =
354 R"(
355 foo() {
356 for (int i = 0; i <= 100; i++) {
357 }
358 }
359 main() {
360 foo();
361 }
362 )";
363 const char* expected =
364 " [0\n"
365 " LIN(0 + 1 * i) 101\n" // phi
366 " LIN(1 + 1 * i)\n" // add
367 " ]\n";
368 EXPECT_STREQ(expected, ComputeInduction(thread, script_chars));
369}
370
371ISOLATE_UNIT_TEST_CASE(NonStrictConditionUpWrap) {
372 const char* script_chars =
373 R"(
374 foo() {
375 for (int i = 0x7ffffffffffffffe; i <= 0x7fffffffffffffff; i++) {
376 if (i < 0) break;
377 }
378 }
379 main() {
380 foo();
381 }
382 )";
383 const char* expected =
384 " [0\n"
385 " LIN(9223372036854775806 + 1 * i)\n" // phi
386 " LIN(9223372036854775806 + 1 * i)\n" // (un)boxing
387 " LIN(9223372036854775806 + 1 * i)\n"
388 " LIN(9223372036854775806 + 1 * i)\n"
389 " LIN(9223372036854775807 + 1 * i)\n" // add
390 " LIN(9223372036854775807 + 1 * i)\n" // unbox
391 " ]\n";
392 EXPECT_STREQ(expected, ComputeInduction(thread, script_chars));
393}
394
395ISOLATE_UNIT_TEST_CASE(NonStrictConditionDown) {
396 const char* script_chars =
397 R"(
398 foo() {
399 for (int i = 100; i >= 0; i--) {
400 }
401 }
402 main() {
403 foo();
404 }
405 )";
406 const char* expected =
407 " [0\n"
408 " LIN(100 + -1 * i) -1\n" // phi
409 " LIN(99 + -1 * i)\n" // add
410 " ]\n";
411 EXPECT_STREQ(expected, ComputeInduction(thread, script_chars));
412}
413
414ISOLATE_UNIT_TEST_CASE(NonStrictConditionDownWrap) {
415 const char* script_chars =
416 R"(
417 foo() {
418 for (int i = 0x8000000000000001; i >= 0x8000000000000000; i--) {
419 if (i > 0) break;
420 }
421 }
422 main() {
423 foo();
424 }
425 )";
426 const char* expected =
427 " [0\n"
428 " LIN(-9223372036854775807 + -1 * i)\n" // phi
429 " LIN(-9223372036854775807 + -1 * i)\n" // (un)boxing
430 " LIN(-9223372036854775807 + -1 * i)\n"
431 " LIN(-9223372036854775807 + -1 * i)\n"
432 " LIN(-9223372036854775808 + -1 * i)\n" // sub
433 " LIN(-9223372036854775808 + -1 * i)\n" // unbox
434 " ]\n";
435 EXPECT_STREQ(expected, ComputeInduction(thread, script_chars));
436}
437
438ISOLATE_UNIT_TEST_CASE(NotEqualConditionUp) {
439 const char* script_chars =
440 R"(
441 foo() {
442 for (int i = 10; i != 20; i++) {
443 }
444 }
445 main() {
446 foo();
447 }
448 )";
449 const char* expected =
450 " [0\n"
451 " LIN(10 + 1 * i) 20\n" // phi
452 " LIN(11 + 1 * i)\n" // add
453 " ]\n";
454 EXPECT_STREQ(expected, ComputeInduction(thread, script_chars));
455}
456
457ISOLATE_UNIT_TEST_CASE(NotEqualConditionDown) {
458 const char* script_chars =
459 R"(
460 foo() {
461 for (int i = 20; i != 10; i--) {
462 }
463 }
464 main() {
465 foo();
466 }
467 )";
468 const char* expected =
469 " [0\n"
470 " LIN(20 + -1 * i) 10\n" // phi
471 " LIN(19 + -1 * i)\n" // sub
472 " ]\n";
473 EXPECT_STREQ(expected, ComputeInduction(thread, script_chars));
474}
475
476ISOLATE_UNIT_TEST_CASE(SecondExitUp) {
477 const char* script_chars =
478 R"(
479 foo() {
480 for (int i = 0; i < 100; i++) {
481 if (i >= 50) break;
482 }
483 }
484 main() {
485 foo();
486 }
487 )";
488 const char* expected =
489 " [0\n"
490 " LIN(0 + 1 * i) 100 50\n" // phi
491 " LIN(1 + 1 * i)\n" // add
492 " ]\n";
493 EXPECT_STREQ(expected, ComputeInduction(thread, script_chars));
494}
495
496ISOLATE_UNIT_TEST_CASE(SecondExitDown) {
497 const char* script_chars =
498 R"(
499 foo() {
500 for (int i = 100; i > 0; i--) {
501 if (i <= 10) break;
502 }
503 }
504 main() {
505 foo();
506 }
507 )";
508 const char* expected =
509 " [0\n"
510 " LIN(100 + -1 * i) 0 10\n" // phi
511 " LIN(99 + -1 * i)\n" // sub
512 " ]\n";
513 EXPECT_STREQ(expected, ComputeInduction(thread, script_chars));
514}
515
516} // namespace dart
517