1// Copyright (c) 2019, 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 BCE (bounds check eliminaton),
6// which runs as part of range analysis optimizations.
7
8#include "vm/compiler/backend/range_analysis.h"
9
10#include "vm/compiler/backend/il.h"
11#include "vm/compiler/backend/il_printer.h"
12#include "vm/compiler/backend/il_test_helper.h"
13#include "vm/compiler/compiler_pass.h"
14#include "vm/object.h"
15#include "vm/unit_test.h"
16
17namespace dart {
18
19// Helper method to count number of bounds checks.
20static intptr_t CountBoundChecks(FlowGraph* flow_graph) {
21 intptr_t count = 0;
22 for (BlockIterator block_it = flow_graph->reverse_postorder_iterator();
23 !block_it.Done(); block_it.Advance()) {
24 for (ForwardInstructionIterator it(block_it.Current()); !it.Done();
25 it.Advance()) {
26 if (it.Current()->IsCheckBoundBase()) {
27 count++;
28 }
29 }
30 }
31 return count;
32}
33
34// Helper method to build CFG, run BCE, and count number of
35// before/after bounds checks.
36static std::pair<intptr_t, intptr_t> ApplyBCE(const char* script_chars,
37 CompilerPass::PipelineMode mode) {
38 // Load the script and exercise the code once
39 // while exercising the given compiler passes.
40 const auto& root_library = Library::Handle(LoadTestScript(script_chars));
41 Invoke(root_library, "main");
42 std::initializer_list<CompilerPass::Id> passes = {
43 CompilerPass::kComputeSSA,
44 CompilerPass::kTypePropagation,
45 CompilerPass::kApplyICData,
46 CompilerPass::kInlining,
47 CompilerPass::kTypePropagation,
48 CompilerPass::kApplyICData,
49 CompilerPass::kSelectRepresentations,
50 CompilerPass::kCanonicalize,
51 CompilerPass::kConstantPropagation,
52 CompilerPass::kCSE,
53 CompilerPass::kLICM,
54 };
55 const auto& function = Function::Handle(GetFunction(root_library, "foo"));
56 TestPipeline pipeline(function, mode);
57 FlowGraph* flow_graph = pipeline.RunPasses(passes);
58 // Count the number of before/after bounds checks.
59 const intptr_t num_bc_before = CountBoundChecks(flow_graph);
60 RangeAnalysis range_analysis(flow_graph);
61 range_analysis.Analyze();
62 const intptr_t num_bc_after = CountBoundChecks(flow_graph);
63 return {num_bc_before, num_bc_after};
64}
65
66static void TestScriptJIT(const char* script_chars,
67 intptr_t expected_before,
68 intptr_t expected_after) {
69 auto jit_result = ApplyBCE(script_chars, CompilerPass::kJIT);
70 EXPECT_EQ(expected_before, jit_result.first);
71 EXPECT_EQ(expected_after, jit_result.second);
72}
73
74//
75// BCE (bounds-check-elimination) tests.
76//
77
78ISOLATE_UNIT_TEST_CASE(BCECannotRemove) {
79 const char* kScriptChars =
80 R"(
81 import 'dart:typed_data';
82 foo(Float64List l) {
83 return l[0];
84 }
85 main() {
86 foo(new Float64List(1));
87 }
88 )";
89 TestScriptJIT(kScriptChars, 1, 1);
90}
91
92ISOLATE_UNIT_TEST_CASE(BCERemoveOne) {
93 const char* kScriptChars =
94 R"(
95 import 'dart:typed_data';
96 foo(Float64List l) {
97 return l[1] + l[0];
98 }
99 main() {
100 foo(new Float64List(2));
101 }
102 )";
103 TestScriptJIT(kScriptChars, 2, 1);
104}
105
106ISOLATE_UNIT_TEST_CASE(BCESimpleLoops) {
107 const char* kScriptChars =
108 R"(
109 import 'dart:typed_data';
110 foo(Float64List l) {
111 for (int i = 0; i < l.length; i++) {
112 l[i] = 0;
113 }
114 for (int i = 10; i <= l.length - 5; i++) {
115 l[i] = 1;
116 }
117 }
118 main() {
119 foo(new Float64List(100));
120 }
121 )";
122 TestScriptJIT(kScriptChars, 2, 0);
123}
124
125ISOLATE_UNIT_TEST_CASE(BCESimpleLoopsDown) {
126 const char* kScriptChars =
127 R"(
128 import 'dart:typed_data';
129 foo(Float64List l) {
130 for (int i = l.length - 1; i >= 0; i--) {
131 l[i] = 0;
132 }
133 for (int i = l.length - 5; i >= 10; i--) {
134 l[i] = 1;
135 }
136 }
137 main() {
138 foo(new Float64List(100));
139 }
140 )";
141 TestScriptJIT(kScriptChars, 2, 0);
142}
143
144ISOLATE_UNIT_TEST_CASE(BCEModulo) {
145 const char* kScriptChars =
146 R"(
147 foo(int i) {
148 var l = List<int>.filled(3, 0);
149 return l[i % 3] ?? l[i % (-3)];
150 }
151 main() {
152 foo(0);
153 }
154 )";
155 TestScriptJIT(kScriptChars, 2, 0);
156}
157
158ISOLATE_UNIT_TEST_CASE(BCELowerTriangular) {
159 const char* kScriptChars =
160 R"(
161 import 'dart:typed_data';
162 foo(Float64List l) {
163 for (int i = 0; i < l.length; i++) {
164 for (int j = 0; j <= i; j++) {
165 l[i] += l[j];
166 }
167 }
168 }
169 main() {
170 foo(new Float64List(100));
171 }
172 )";
173 TestScriptJIT(kScriptChars, 2, 0);
174}
175
176ISOLATE_UNIT_TEST_CASE(BCEUpperTriangular) {
177 const char* kScriptChars =
178 R"(
179 import 'dart:typed_data';
180 foo(Float64List l) {
181 for (int i = 0; i < l.length; i++) {
182 for (int j = i; j < l.length; j++) {
183 l[i] += l[j];
184 }
185 }
186 }
187 main() {
188 foo(new Float64List(100));
189 }
190 )";
191 TestScriptJIT(kScriptChars, 2, 0);
192}
193
194ISOLATE_UNIT_TEST_CASE(BCETriangularDown) {
195 const char* kScriptChars =
196 R"(
197 import 'dart:typed_data';
198 foo(Float64List l) {
199 for (int i = l.length - 1; i >= 0; i--) {
200 for (int j = i; j >= 0; j--) {
201 l[i] += l[j];
202 }
203 }
204 }
205 main() {
206 foo(new Float64List(100));
207 }
208 )";
209 TestScriptJIT(kScriptChars, 2, 0);
210}
211
212ISOLATE_UNIT_TEST_CASE(BCENamedLength) {
213 const char* kScriptChars =
214 R"(
215 import 'dart:typed_data';
216 Int8List foo(int count) {
217 var x = new Int8List(count);
218 for (int i = 0; i < count; i++) {
219 x[i] = 0;
220 }
221 return x;
222 }
223 main() {
224 foo(100);
225 }
226 )";
227 TestScriptJIT(kScriptChars, 1, 0);
228}
229
230ISOLATE_UNIT_TEST_CASE(BCEBubbleSort) {
231 const char* kScriptChars =
232 R"(
233 import 'dart:typed_data';
234 foo(Float64List a) {
235 int len = a.length;
236 for (int i = len - 2; i >= 0; i--) {
237 for (int j = 0; j <= i; j++) {
238 var c = a[j];
239 var n = a[j + 1];
240 if (c > n) {
241 a[j] = n;
242 a[j + 1] = c;
243 }
244 }
245 }
246 }
247 main() {
248 foo(new Float64List(100));
249 }
250 )";
251 TestScriptJIT(kScriptChars, 2, 0);
252}
253
254ISOLATE_UNIT_TEST_CASE(BCEArithmeticWrapAround) {
255 const char* kScriptChars =
256 R"(
257 import 'dart:typed_data';
258 const kMax = 0x7fffffffffffffff;
259 foo(Float64List a) {
260 for (int i = kMax - 10; i < kMax; i++) {
261 for (int j = i + 10; j < a.length; j++) {
262 // Don't be fooled: j in [-minint, len).
263 a[j] = 1;
264 }
265 }
266 }
267 main() {
268 try {
269 foo(new Float64List(100));
270 } catch (e) {
271 }
272 }
273 )";
274 TestScriptJIT(kScriptChars, 1, 1);
275}
276
277ISOLATE_UNIT_TEST_CASE(BCEListNamedAndPlainLength) {
278 const char* kScriptChars =
279 R"(
280 List<int> foo(int count) {
281 var x = new List<int>.filled(count, 42);
282 for (int i = 0; i < count; i++) {
283 x[i] = 0;
284 }
285 for (int i = 0; i < x.length; i++) {
286 x[i] = 0;
287 }
288 return x;
289 }
290 main() {
291 foo(100);
292 }
293 )";
294 TestScriptJIT(kScriptChars, 2, 0);
295}
296
297} // namespace dart
298