Flutter Engine
The Flutter Engine
loops_test.cc
Go to the documentation of this file.
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
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.
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,
72 CompilerPass::kTypePropagation,
73 CompilerPass::kApplyICData,
74 CompilerPass::kTypePropagation,
75 CompilerPass::kSelectRepresentations,
76 CompilerPass::kTypePropagation,
77 CompilerPass::kCanonicalize,
78 };
79 const auto& function = Function::Handle(GetFunction(root_library, "foo"));
81 FlowGraph* flow_graph = pipeline.RunPasses(passes);
82
83 // Build loop hierarchy and find induction.
84 const LoopHierarchy& hierarchy = flow_graph->GetLoopHierarchy();
85 hierarchy.ComputeInduction();
86 flow_graph->RemoveRedefinitions(); // don't query later
87
88 // Construct and return a debug string for testing.
89 char buffer[1024];
91 TestString(&f, hierarchy.top(), flow_graph->preorder());
93}
94
95//
96// Induction tests.
97//
98
99ISOLATE_UNIT_TEST_CASE(BasicInductionUp) {
100 const char* script_chars =
101 R"(
102 foo() {
103 for (int i = 0; i < 100; i++) {
104 }
105 }
106 main() {
107 foo();
108 }
109 )";
110 const char* expected =
111 " [0\n"
112 " LIN(0 + 1 * i) 100\n" // phi
113 " LIN(1 + 1 * i)\n" // add
114 " ]\n";
115 EXPECT_STREQ(expected, ComputeInduction(thread, script_chars));
116}
117
118ISOLATE_UNIT_TEST_CASE(BasicInductionDown) {
119 const char* script_chars =
120 R"(
121 foo() {
122 for (int i = 100; i > 0; i--) {
123 }
124 }
125 main() {
126 foo();
127 }
128 )";
129 const char* expected =
130 " [0\n"
131 " LIN(100 + -1 * i) 0\n" // phi
132 " LIN(99 + -1 * i)\n" // sub
133 " ]\n";
134 EXPECT_STREQ(expected, ComputeInduction(thread, script_chars));
135}
136
137ISOLATE_UNIT_TEST_CASE(BasicInductionStepUp) {
138 const char* script_chars =
139 R"(
140 foo() {
141 for (int i = 10; i < 100; i += 2) {
142 }
144 main() {
145 foo();
146 }
147 )";
148 const char* expected =
149 " [0\n"
150 " LIN(10 + 2 * i)\n" // phi
151 " LIN(12 + 2 * i)\n" // add
152 " ]\n";
153 EXPECT_STREQ(expected, ComputeInduction(thread, script_chars));
154}
155
156ISOLATE_UNIT_TEST_CASE(BasicInductionStepDown) {
157 const char* script_chars =
158 R"(
159 foo() {
160 for (int i = 100; i >= 0; i -= 7) {
161 }
163 main() {
164 foo();
165 }
166 )";
167 const char* expected =
168 " [0\n"
169 " LIN(100 + -7 * i)\n" // phi
170 " LIN(93 + -7 * i)\n" // sub
171 " ]\n";
172 EXPECT_STREQ(expected, ComputeInduction(thread, script_chars));
173}
174
175ISOLATE_UNIT_TEST_CASE(BasicInductionLoopNest) {
176 const char* script_chars =
177 R"(
178 foo() {
179 for (int i = 0; i < 100; i++) {
180 for (int j = 1; j < 100; j++) {
181 for (int k = 2; k < 100; k++) {
182 }
183 }
184 }
185 }
186 main() {
187 foo();
188 }
189 )";
190 const char* expected =
191 " [2\n"
192 " LIN(0 + 1 * i) 100\n" // i
193 " LIN(1 + 1 * i)\n"
194 " [1\n"
195 " LIN(1 + 1 * i) 100\n" // j
196 " LIN(2 + 1 * i)\n"
197 " [0\n"
198 " LIN(2 + 1 * i) 100\n" // k
199 " LIN(3 + 1 * i)\n"
200 " ]\n"
201 " ]\n"
202 " ]\n";
203 EXPECT_STREQ(expected, ComputeInduction(thread, script_chars));
204}
205
206ISOLATE_UNIT_TEST_CASE(ChainInduction) {
207 const char* script_chars =
208 R"(
209 foo() {
210 int j = 1;
211 for (int i = 0; i < 100; i++) {
212 j += 5;
213 j += 7;
214 }
215 }
216 main() {
217 foo();
218 }
219 )";
220 const char* expected =
221 " [0\n"
222 " LIN(1 + 12 * i)\n" // phi (j)
223 " LIN(0 + 1 * i) 100\n" // phi
224 " LIN(6 + 12 * i)\n" // j-add
225 " LIN(13 + 12 * i)\n" // j-add
226 " LIN(1 + 1 * i)\n" // add
227 " ]\n";
228 EXPECT_STREQ(expected, ComputeInduction(thread, script_chars));
229}
230
231ISOLATE_UNIT_TEST_CASE(TwoWayInduction) {
232 const char* script_chars =
233 R"(
234 foo() {
235 int j = 123;
236 for (int i = 0; i < 100; i++) {
237 if (i == 10) {
238 j += 3;
239 } else {
240 j += 3;
241 }
242 }
243 }
244 main() {
245 foo();
246 }
247 )";
248 const char* expected =
249 " [0\n"
250 " LIN(123 + 3 * i)\n" // phi (j)
251 " LIN(0 + 1 * i) 100\n" // phi
252 " LIN(126 + 3 * i)\n" // j-true
253 " LIN(126 + 3 * i)\n" // j-false
254 " LIN(1 + 1 * i)\n" // add
255 " LIN(126 + 3 * i)\n" // phi (j)
256 " ]\n";
257 EXPECT_STREQ(expected, ComputeInduction(thread, script_chars));
258}
259
260ISOLATE_UNIT_TEST_CASE(DerivedInduction) {
261 const char* script_chars =
262 R"(
263 foo() {
264 for (int i = 1; i < 100; i++) {
265 int a = i + 3;
266 int b = i - 5;
267 int c = i * 7;
268 int d = - i;
269 }
270 }
271 main() {
272 foo();
273 }
274 )";
275 const char* expected =
276 " [0\n"
277 " LIN(1 + 1 * i) 100\n" // phi
278 " LIN(4 + 1 * i)\n" // a
279 " LIN(-4 + 1 * i)\n" // b
280 " LIN(7 + 7 * i)\n" // c
281 " LIN(-1 + -1 * i)\n" // d
282 " LIN(2 + 1 * i)\n" // add
283 " ]\n";
284 EXPECT_STREQ(expected, ComputeInduction(thread, script_chars));
285}
286
287ISOLATE_UNIT_TEST_CASE(WrapAroundAndDerived) {
288 const char* script_chars =
289 R"(
290 foo() {
291 int w = 99;
292 for (int i = 0; i < 100; i++) {
293 int a = w + 3;
294 int b = w - 5;
295 int c = w * 7;
296 int d = - w;
297 w = i;
298 }
299 }
300 main() {
301 foo();
302 }
303 )";
304 const char* expected =
305 " [0\n"
306 " WRAP(99, LIN(0 + 1 * i))\n" // phi (w)
307 " LIN(0 + 1 * i) 100\n" // phi (i)
308 " WRAP(102, LIN(3 + 1 * i))\n" // a
309 " WRAP(94, LIN(-5 + 1 * i))\n" // b
310 " WRAP(693, LIN(0 + 7 * i))\n" // c
311 " WRAP(-99, LIN(0 + -1 * i))\n" // d
312 " LIN(1 + 1 * i)\n" // add
313 " ]\n";
314 EXPECT_STREQ(expected, ComputeInduction(thread, script_chars));
315}
316
317ISOLATE_UNIT_TEST_CASE(PeriodicAndDerived) {
318 const char* script_chars =
319 R"(
320 foo() {
321 int p1 = 3;
322 int p2 = 5;
323 for (int i = 0; i < 100; i++) {
324 int a = p1 + 3;
325 int b = p1 - 5;
326 int c = p1 * 7;
327 int d = - p1;
328 p1 = - p1;
329 p2 = 100 - p2;
330 }
331 }
332 main() {
333 foo();
334 }
335 )";
336 const char* expected =
337 " [0\n"
338 " PERIOD(3, -3)\n" // phi(p1)
339 " PERIOD(5, 95)\n" // phi(p2)
340 " LIN(0 + 1 * i) 100\n" // phi
341 " PERIOD(6, 0)\n" // a
342 " PERIOD(-2, -8)\n" // b
343 " PERIOD(21, -21)\n" // c
344 " PERIOD(-3, 3)\n" // d
345 " PERIOD(-3, 3)\n" // p1
346 " PERIOD(95, 5)\n" // p2
347 " LIN(1 + 1 * i)\n" // add
348 " ]\n";
349 EXPECT_STREQ(expected, ComputeInduction(thread, script_chars));
350}
351
352//
353// Bound specific tests.
354//
355
356ISOLATE_UNIT_TEST_CASE(NonStrictConditionUp) {
357 const char* script_chars =
358 R"(
359 foo() {
360 for (int i = 0; i <= 100; i++) {
361 }
362 }
363 main() {
364 foo();
365 }
366 )";
367 const char* expected =
368 " [0\n"
369 " LIN(0 + 1 * i) 101\n" // phi
370 " LIN(1 + 1 * i)\n" // add
371 " ]\n";
372 EXPECT_STREQ(expected, ComputeInduction(thread, script_chars));
373}
374
375ISOLATE_UNIT_TEST_CASE(NonStrictConditionUpWrap) {
376 const char* script_chars =
377 R"(
378 foo() {
379 for (int i = 0x7ffffffffffffffe; i <= 0x7fffffffffffffff; i++) {
380 if (i < 0) break;
381 }
382 }
383 main() {
384 foo();
385 }
386 )";
387 const char* expected =
388 " [0\n"
389 " LIN(9223372036854775806 + 1 * i)\n" // phi
390 " LIN(9223372036854775807 + 1 * i)\n" // add
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(-9223372036854775808 + -1 * i)\n" // sub
430 " ]\n";
431 EXPECT_STREQ(expected, ComputeInduction(thread, script_chars));
432}
433
434ISOLATE_UNIT_TEST_CASE(NotEqualConditionUp) {
435 const char* script_chars =
436 R"(
437 foo() {
438 for (int i = 10; i != 20; i++) {
439 }
440 }
441 main() {
442 foo();
443 }
444 )";
445 const char* expected =
446 " [0\n"
447 " LIN(10 + 1 * i) 20\n" // phi
448 " LIN(11 + 1 * i)\n" // add
449 " ]\n";
450 EXPECT_STREQ(expected, ComputeInduction(thread, script_chars));
451}
452
453ISOLATE_UNIT_TEST_CASE(NotEqualConditionDown) {
454 const char* script_chars =
455 R"(
456 foo() {
457 for (int i = 20; i != 10; i--) {
458 }
459 }
460 main() {
461 foo();
462 }
463 )";
464 const char* expected =
465 " [0\n"
466 " LIN(20 + -1 * i) 10\n" // phi
467 " LIN(19 + -1 * i)\n" // sub
468 " ]\n";
469 EXPECT_STREQ(expected, ComputeInduction(thread, script_chars));
470}
471
472ISOLATE_UNIT_TEST_CASE(SecondExitUp) {
473 const char* script_chars =
474 R"(
475 foo() {
476 for (int i = 0; i < 100; i++) {
477 if (i >= 50) break;
478 }
479 }
480 main() {
481 foo();
482 }
483 )";
484 const char* expected =
485 " [0\n"
486 " LIN(0 + 1 * i) 100 50\n" // phi
487 " LIN(1 + 1 * i)\n" // add
488 " ]\n";
489 EXPECT_STREQ(expected, ComputeInduction(thread, script_chars));
490}
491
492ISOLATE_UNIT_TEST_CASE(SecondExitDown) {
493 const char* script_chars =
494 R"(
495 foo() {
496 for (int i = 100; i > 0; i--) {
497 if (i <= 10) break;
498 }
499 }
500 main() {
501 foo();
502 }
503 )";
504 const char* expected =
505 " [0\n"
506 " LIN(100 + -1 * i) 0 10\n" // phi
507 " LIN(99 + -1 * i)\n" // sub
508 " ]\n";
509 EXPECT_STREQ(expected, ComputeInduction(thread, script_chars));
510}
511
512} // namespace dart
void RemoveRedefinitions(bool keep_checks=false)
Definition: flow_graph.cc:1810
const GrowableArray< BlockEntryInstr * > & preorder() const
Definition: flow_graph.h:203
const LoopHierarchy & GetLoopHierarchy()
Definition: flow_graph.h:430
const GrowableArray< Bound > & bounds()
Definition: loops.h:128
static bool IsInduction(const InductionVar *x)
Definition: loops.h:177
const char * ToCString() const
Definition: loops.cc:973
LoopInfo * top() const
Definition: loops.h:332
void ComputeInduction() const
Definition: loops.cc:1207
InductionVar * LookupInduction(Definition *def) const
Definition: loops.cc:1081
BitVector * blocks() const
Definition: loops.h:253
LoopInfo * next() const
Definition: loops.h:259
intptr_t id() const
Definition: loops.h:251
intptr_t NestingDepth() const
Definition: loops.cc:1062
LoopInfo * inner() const
Definition: loops.h:258
static Object & Handle()
Definition: object.h:407
bool Done() const
Definition: il.h:2121
FlowGraph * RunPasses(std::initializer_list< CompilerPass::Id > passes)
Zone * zone() const
Definition: thread_state.h:37
static Thread * Current()
Definition: thread.h:362
char * MakeCopyOfString(const char *str)
Definition: zone.cc:270
Dart_NativeFunction function
Definition: fuchsia.cc:51
Definition: dart_vm.cc:33
LibraryPtr LoadTestScript(const char *script, Dart_NativeEntryResolver resolver, const char *lib_uri)
void TestString(BaseTextBuffer *f, LoopInfo *loop, const GrowableArray< BlockEntryInstr * > &preorder)
Definition: loops_test.cc:27
ObjectPtr Invoke(const Library &lib, const char *name)
FunctionPtr GetFunction(const Library &lib, const char *name)
ISOLATE_UNIT_TEST_CASE(StackAllocatedDestruction)
static const char * ComputeInduction(Thread *thread, const char *script_chars)
Definition: loops_test.cc:65
DEF_SWITCHES_START aot vmservice shared library Name of the *so containing AOT compiled Dart assets for launching the service isolate vm snapshot The VM snapshot data that will be memory mapped as read only SnapshotAssetPath must be present isolate snapshot The isolate snapshot data that will be memory mapped as read only SnapshotAssetPath must be present cache dir Path to the cache directory This is different from the persistent_cache_path in embedder which is used for Skia shader cache icu native lib Path to the library file that exports the ICU data vm service The hostname IP address on which the Dart VM Service should be served If not defaults to or::depending on whether ipv6 is specified vm service A custom Dart VM Service port The default is to pick a randomly available open port disable vm Disable the Dart VM Service The Dart VM Service is never available in release mode disable vm service Disable mDNS Dart VM Service publication Bind to the IPv6 localhost address for the Dart VM Service Ignored if vm service host is set endless trace buffer
Definition: switches.h:126
#define Pd
Definition: globals.h:408