| // Copyright (c) 2018, the Dart project authors. Please see the AUTHORS file |
| // for details. All rights reserved. Use of this source code is governed by a |
| // BSD-style license that can be found in the LICENSE file. |
| // |
| // Unit tests specific to loops and induction variables. |
| // Note, try to avoid relying on information that is subject |
| // to change (block ids, variable numbers, etc.) in order |
| // to make this test less sensitive to unrelated changes. |
| |
| #include "vm/compiler/backend/loops.h" |
| #include "vm/compiler/backend/il_printer.h" |
| #include "vm/compiler/backend/inliner.h" |
| #include "vm/compiler/backend/type_propagator.h" |
| #include "vm/compiler/compiler_pass.h" |
| #include "vm/compiler/frontend/kernel_to_il.h" |
| #include "vm/compiler/jit/jit_call_specializer.h" |
| #include "vm/log.h" |
| #include "vm/object.h" |
| #include "vm/parser.h" |
| #include "vm/symbols.h" |
| #include "vm/unit_test.h" |
| |
| namespace dart { |
| |
| // Helper method to construct an induction debug string for loop hierarchy. |
| void TestString(BufferFormatter* f, |
| LoopInfo* loop, |
| const GrowableArray<BlockEntryInstr*>& preorder) { |
| for (; loop != nullptr; loop = loop->next()) { |
| intptr_t depth = loop->NestingDepth(); |
| f->Print("%*c[%" Pd "\n", static_cast<int>(2 * depth), ' ', loop->id()); |
| for (BitVector::Iterator block_it(loop->blocks()); !block_it.Done(); |
| block_it.Advance()) { |
| BlockEntryInstr* block = preorder[block_it.Current()]; |
| if (block->IsJoinEntry()) { |
| for (PhiIterator it(block->AsJoinEntry()); !it.Done(); it.Advance()) { |
| InductionVar* induc = loop->LookupInduction(it.Current()); |
| if (induc != nullptr) { |
| // Obtain the debug string for induction and bounds. |
| f->Print("%*c%s", static_cast<int>(2 * depth), ' ', |
| induc->ToCString()); |
| for (auto bound : induc->bounds()) { |
| f->Print(" %s", bound.limit_->ToCString()); |
| } |
| f->Print("\n"); |
| } |
| } |
| } |
| for (ForwardInstructionIterator it(block); !it.Done(); it.Advance()) { |
| InductionVar* induc = |
| loop->LookupInduction(it.Current()->AsDefinition()); |
| if (InductionVar::IsInduction(induc)) { |
| f->Print("%*c%s\n", static_cast<int>(2 * depth), ' ', |
| induc->ToCString()); |
| } |
| } |
| } |
| TestString(f, loop->inner(), preorder); |
| f->Print("%*c]\n", static_cast<int>(2 * depth), ' '); |
| } |
| } |
| |
| // Helper method to build CFG and compute induction. |
| static const char* ComputeInduction(Thread* thread, const char* script_chars) { |
| // Invoke the script. |
| Dart_Handle script = TestCase::LoadTestScript(script_chars, NULL); |
| Dart_Handle result = Dart_Invoke(script, NewString("main"), 0, NULL); |
| EXPECT_VALID(result); |
| |
| // Find parsed function "foo". |
| TransitionNativeToVM transition(thread); |
| Zone* zone = thread->zone(); |
| Library& lib = |
| Library::ZoneHandle(Library::RawCast(Api::UnwrapHandle(script))); |
| RawFunction* raw_func = |
| lib.LookupLocalFunction(String::Handle(Symbols::New(thread, "foo"))); |
| ParsedFunction* parsed_function = |
| new (zone) ParsedFunction(thread, Function::ZoneHandle(zone, raw_func)); |
| EXPECT(parsed_function != nullptr); |
| |
| // Build flow graph. |
| CompilerState state(thread); |
| ZoneGrowableArray<const ICData*>* ic_data_array = |
| new (zone) ZoneGrowableArray<const ICData*>(); |
| parsed_function->function().RestoreICDataMap(ic_data_array, true); |
| kernel::FlowGraphBuilder builder(parsed_function, ic_data_array, nullptr, |
| nullptr, true, DeoptId::kNone); |
| FlowGraph* flow_graph = builder.BuildGraph(); |
| EXPECT(flow_graph != nullptr); |
| |
| // Setup some pass data structures and perform minimum passes. |
| SpeculativeInliningPolicy speculative_policy(/*enable_blacklist*/ false); |
| CompilerPassState pass_state(thread, flow_graph, &speculative_policy); |
| JitCallSpecializer call_specializer(flow_graph, &speculative_policy); |
| pass_state.call_specializer = &call_specializer; |
| flow_graph->ComputeSSA(0, nullptr); |
| FlowGraphTypePropagator::Propagate(flow_graph); |
| call_specializer.ApplyICData(); |
| flow_graph->SelectRepresentations(); |
| FlowGraphTypePropagator::Propagate(flow_graph); |
| flow_graph->Canonicalize(); |
| |
| // Build loop hierarchy and find induction. |
| const LoopHierarchy& hierarchy = flow_graph->GetLoopHierarchy(); |
| hierarchy.ComputeInduction(); |
| flow_graph->RemoveRedefinitions(); // don't query later |
| |
| // Construct and return a debug string for testing. |
| char buffer[1024]; |
| BufferFormatter f(buffer, sizeof(buffer)); |
| TestString(&f, hierarchy.top(), flow_graph->preorder()); |
| return Thread::Current()->zone()->MakeCopyOfString(buffer); |
| } |
| |
| // |
| // Induction tests. |
| // |
| |
| TEST_CASE(BasicInductionUp) { |
| const char* script_chars = |
| "foo() {\n" |
| " for (int i = 0; i < 100; i++) {\n" |
| " }\n" |
| "}\n" |
| "main() {\n" |
| " foo();\n" |
| "}\n"; |
| const char* expected = |
| " [0\n" |
| " LIN(0 + 1 * i) 100\n" // phi |
| " LIN(1 + 1 * i)\n" // add |
| " ]\n"; |
| EXPECT_STREQ(expected, ComputeInduction(thread, script_chars)); |
| } |
| |
| TEST_CASE(BasicInductionDown) { |
| const char* script_chars = |
| "foo() {\n" |
| " for (int i = 100; i > 0; i--) {\n" |
| " }\n" |
| "}\n" |
| "main() {\n" |
| " foo();\n" |
| "}\n"; |
| const char* expected = |
| " [0\n" |
| " LIN(100 + -1 * i) 0\n" // phi |
| " LIN(99 + -1 * i)\n" // sub |
| " ]\n"; |
| EXPECT_STREQ(expected, ComputeInduction(thread, script_chars)); |
| } |
| |
| TEST_CASE(BasicInductionStepUp) { |
| const char* script_chars = |
| "foo() {\n" |
| " for (int i = 10; i < 100; i += 2) {\n" |
| " }\n" |
| "}\n" |
| "main() {\n" |
| " foo();\n" |
| "}\n"; |
| const char* expected = |
| " [0\n" |
| " LIN(10 + 2 * i)\n" // phi |
| " LIN(12 + 2 * i)\n" // add |
| " ]\n"; |
| EXPECT_STREQ(expected, ComputeInduction(thread, script_chars)); |
| } |
| |
| TEST_CASE(BasicInductionStepDown) { |
| const char* script_chars = |
| "foo() {\n" |
| " for (int i = 100; i >= 0; i -= 7) {\n" |
| " }\n" |
| "}\n" |
| "main() {\n" |
| " foo();\n" |
| "}\n"; |
| const char* expected = |
| " [0\n" |
| " LIN(100 + -7 * i)\n" // phi |
| " LIN(93 + -7 * i)\n" // sub |
| " ]\n"; |
| EXPECT_STREQ(expected, ComputeInduction(thread, script_chars)); |
| } |
| |
| TEST_CASE(BasicInductionLoopNest) { |
| const char* script_chars = |
| "foo() {\n" |
| " for (int i = 0; i < 100; i++) {\n" |
| " for (int j = 1; j < 100; j++) {\n" |
| " for (int k = 2; k < 100; k++) {\n" |
| " }\n" |
| " }\n" |
| " }\n" |
| "}\n" |
| "main() {\n" |
| " foo();\n" |
| "}\n"; |
| const char* expected = |
| " [2\n" |
| " LIN(0 + 1 * i) 100\n" // i |
| " LIN(1 + 1 * i)\n" |
| " [1\n" |
| " LIN(1 + 1 * i) 100\n" // j |
| " LIN(2 + 1 * i)\n" |
| " [0\n" |
| " LIN(2 + 1 * i) 100\n" // k |
| " LIN(3 + 1 * i)\n" |
| " ]\n" |
| " ]\n" |
| " ]\n"; |
| EXPECT_STREQ(expected, ComputeInduction(thread, script_chars)); |
| } |
| |
| TEST_CASE(ChainInduction) { |
| const char* script_chars = |
| "foo() {\n" |
| " int j = 1;\n" |
| " for (int i = 0; i < 100; i++) {\n" |
| " j += 5;\n" |
| " j += 7;\n" |
| " }\n" |
| "}\n" |
| "main() {\n" |
| " foo();\n" |
| "}\n"; |
| const char* expected = |
| " [0\n" |
| " LIN(1 + 12 * i)\n" // phi (j) |
| " LIN(0 + 1 * i) 100\n" // phi |
| " LIN(6 + 12 * i)\n" // j-add |
| " LIN(13 + 12 * i)\n" // j-add |
| " LIN(1 + 1 * i)\n" // add |
| " ]\n"; |
| EXPECT_STREQ(expected, ComputeInduction(thread, script_chars)); |
| } |
| |
| TEST_CASE(TwoWayInduction) { |
| const char* script_chars = |
| "foo() {\n" |
| " int j = 123;\n" |
| " for (int i = 0; i < 100; i++) {\n" |
| " if (i == 10) {\n" |
| " j += 3;\n" |
| " } else {\n" |
| " j += 3;\n" |
| " }\n" |
| " }\n" |
| "}\n" |
| "main() {\n" |
| " foo();\n" |
| "}\n"; |
| const char* expected = |
| " [0\n" |
| " LIN(123 + 3 * i)\n" // phi (j) |
| " LIN(0 + 1 * i) 100\n" // phi |
| " LIN(126 + 3 * i)\n" // j-true |
| " LIN(126 + 3 * i)\n" // j-false |
| " LIN(1 + 1 * i)\n" // add |
| " LIN(126 + 3 * i)\n" // phi (j) |
| " ]\n"; |
| EXPECT_STREQ(expected, ComputeInduction(thread, script_chars)); |
| } |
| |
| TEST_CASE(DerivedInduction) { |
| const char* script_chars = |
| "foo() {\n" |
| " for (int i = 1; i < 100; i++) {\n" |
| " int a = i + 3;\n" |
| " int b = i - 5;\n" |
| " int c = i * 7;\n" |
| " int d = - i;\n" |
| " }\n" |
| "}\n" |
| "main() {\n" |
| " foo();\n" |
| "}\n"; |
| const char* expected = |
| " [0\n" |
| " LIN(1 + 1 * i) 100\n" // phi |
| " LIN(4 + 1 * i)\n" // a |
| " LIN(-4 + 1 * i)\n" // b |
| " LIN(7 + 7 * i)\n" // c |
| " LIN(-1 + -1 * i)\n" // d |
| " LIN(2 + 1 * i)\n" // add |
| " ]\n"; |
| EXPECT_STREQ(expected, ComputeInduction(thread, script_chars)); |
| } |
| |
| TEST_CASE(WrapAroundAndDerived) { |
| const char* script_chars = |
| "foo() {\n" |
| " int w = 99;\n" |
| " for (int i = 0; i < 100; i++) {\n" |
| " int a = w + 3;\n" |
| " int b = w - 5;\n" |
| " int c = w * 7;\n" |
| " int d = - w;\n" |
| " w = i;\n" |
| " }\n" |
| "}\n" |
| "main() {\n" |
| " foo();\n" |
| "}\n"; |
| const char* expected = |
| " [0\n" |
| " WRAP(99, LIN(0 + 1 * i))\n" // phi (w) |
| " LIN(0 + 1 * i) 100\n" // phi |
| " WRAP(102, LIN(3 + 1 * i))\n" // a |
| " WRAP(94, LIN(-5 + 1 * i))\n" // b |
| " WRAP(693, LIN(0 + 7 * i))\n" // c |
| " WRAP(-99, LIN(0 + -1 * i))\n" // d |
| " LIN(1 + 1 * i)\n" // add |
| " ]\n"; |
| EXPECT_STREQ(ComputeInduction(thread, script_chars), expected); |
| } |
| |
| TEST_CASE(PeriodicAndDerived) { |
| const char* script_chars = |
| "foo() {\n" |
| " int p1 = 3;\n" |
| " int p2 = 5;\n" |
| " for (int i = 0; i < 100; i++) {\n" |
| " int a = p1 + 3;\n" |
| " int b = p1 - 5;\n" |
| " int c = p1 * 7;\n" |
| " int d = - p1;\n" |
| " p1 = - p1;\n" |
| " p2 = 100 - p2;\n" |
| " }\n" |
| "}\n" |
| "main() {\n" |
| " foo();\n" |
| "}\n"; |
| const char* expected = |
| " [0\n" |
| " PERIOD(3, -3)\n" // phi(p1) |
| " PERIOD(5, 95)\n" // phi(p2) |
| " LIN(0 + 1 * i) 100\n" // phi |
| " PERIOD(6, 0)\n" // a |
| " PERIOD(-2, -8)\n" // b |
| " PERIOD(21, -21)\n" // c |
| " PERIOD(-3, 3)\n" // d |
| " PERIOD(-3, 3)\n" // p1 |
| " PERIOD(95, 5)\n" // p2 |
| " LIN(1 + 1 * i)\n" // add |
| " ]\n"; |
| EXPECT_STREQ(ComputeInduction(thread, script_chars), expected); |
| } |
| |
| // |
| // Bound specific tests. |
| // |
| |
| TEST_CASE(NonStrictConditionUp) { |
| const char* script_chars = |
| "foo() {\n" |
| " for (int i = 0; i <= 100; i++) {\n" |
| " }\n" |
| "}\n" |
| "main() {\n" |
| " foo();\n" |
| "}\n"; |
| const char* expected = |
| " [0\n" |
| " LIN(0 + 1 * i) 101\n" // phi |
| " LIN(1 + 1 * i)\n" // add |
| " ]\n"; |
| EXPECT_STREQ(expected, ComputeInduction(thread, script_chars)); |
| } |
| |
| #ifndef TARGET_ARCH_DBC |
| TEST_CASE(NonStrictConditionUpWrap) { |
| const char* script_chars = |
| "foo() {\n" |
| " for (int i = 0x7ffffffffffffffe; i <= 0x7fffffffffffffff; i++) {\n" |
| " if (i < 0) break;\n" |
| " }\n" |
| "}\n" |
| "main() {\n" |
| " foo();\n" |
| "}\n"; |
| const char* expected = |
| " [0\n" |
| " LIN(9223372036854775806 + 1 * i)\n" // phi |
| " LIN(9223372036854775806 + 1 * i)\n" // (un)boxing |
| " LIN(9223372036854775806 + 1 * i)\n" |
| " LIN(9223372036854775806 + 1 * i)\n" |
| " LIN(9223372036854775807 + 1 * i)\n" // add |
| " LIN(9223372036854775807 + 1 * i)\n" // unbox |
| " ]\n"; |
| EXPECT_STREQ(expected, ComputeInduction(thread, script_chars)); |
| } |
| #endif |
| |
| TEST_CASE(NonStrictConditionDown) { |
| const char* script_chars = |
| "foo() {\n" |
| " for (int i = 100; i >= 0; i--) {\n" |
| " }\n" |
| "}\n" |
| "main() {\n" |
| " foo();\n" |
| "}\n"; |
| const char* expected = |
| " [0\n" |
| " LIN(100 + -1 * i) -1\n" // phi |
| " LIN(99 + -1 * i)\n" // add |
| " ]\n"; |
| EXPECT_STREQ(expected, ComputeInduction(thread, script_chars)); |
| } |
| |
| #ifndef TARGET_ARCH_DBC |
| TEST_CASE(NonStrictConditionDownWrap) { |
| const char* script_chars = |
| "foo() {\n" |
| " for (int i = 0x8000000000000001; i >= 0x8000000000000000; i--) {\n" |
| " if (i > 0) break;\n" |
| " }\n" |
| "}\n" |
| "main() {\n" |
| " foo();\n" |
| "}\n"; |
| const char* expected = |
| " [0\n" |
| " LIN(-9223372036854775807 + -1 * i)\n" // phi |
| " LIN(-9223372036854775807 + -1 * i)\n" // (un)boxing |
| " LIN(-9223372036854775807 + -1 * i)\n" |
| " LIN(-9223372036854775807 + -1 * i)\n" |
| " LIN(-9223372036854775808 + -1 * i)\n" // sub |
| " LIN(-9223372036854775808 + -1 * i)\n" // unbox |
| " ]\n"; |
| EXPECT_STREQ(expected, ComputeInduction(thread, script_chars)); |
| } |
| #endif |
| |
| TEST_CASE(NotEqualConditionUp) { |
| const char* script_chars = |
| "foo() {\n" |
| " for (int i = 10; i != 20; i++) {\n" |
| " }\n" |
| "}\n" |
| "main() {\n" |
| " foo();\n" |
| "}\n"; |
| const char* expected = |
| " [0\n" |
| " LIN(10 + 1 * i) 20\n" // phi |
| " LIN(11 + 1 * i)\n" // add |
| " ]\n"; |
| EXPECT_STREQ(expected, ComputeInduction(thread, script_chars)); |
| } |
| |
| TEST_CASE(NotEqualConditionDown) { |
| const char* script_chars = |
| "foo() {\n" |
| " for (int i = 20; i != 10; i--) {\n" |
| " }\n" |
| "}\n" |
| "main() {\n" |
| " foo();\n" |
| "}\n"; |
| const char* expected = |
| " [0\n" |
| " LIN(20 + -1 * i) 10\n" // phi |
| " LIN(19 + -1 * i)\n" // sub |
| " ]\n"; |
| EXPECT_STREQ(expected, ComputeInduction(thread, script_chars)); |
| } |
| |
| TEST_CASE(SecondExitUp) { |
| const char* script_chars = |
| "foo() {\n" |
| " for (int i = 0; i < 100; i++) {\n" |
| " if (i >= 50) break;\n" |
| " }\n" |
| "}\n" |
| "main() {\n" |
| " foo();\n" |
| "}\n"; |
| const char* expected = |
| " [0\n" |
| " LIN(0 + 1 * i) 100 50\n" // phi |
| " LIN(1 + 1 * i)\n" // add |
| " ]\n"; |
| EXPECT_STREQ(expected, ComputeInduction(thread, script_chars)); |
| } |
| |
| TEST_CASE(SecondExitDown) { |
| const char* script_chars = |
| "foo() {\n" |
| " for (int i = 100; i > 0; i--) {\n" |
| " if (i <= 10) break;\n" |
| " }\n" |
| "}\n" |
| "main() {\n" |
| " foo();\n" |
| "}\n"; |
| const char* expected = |
| " [0\n" |
| " LIN(100 + -1 * i) 0 10\n" // phi |
| " LIN(99 + -1 * i)\n" // sub |
| " ]\n"; |
| EXPECT_STREQ(expected, ComputeInduction(thread, script_chars)); |
| } |
| |
| } // namespace dart |
