Skip to content

Commit 29ff784

Browse files
aartbikcommit-bot@chromium.org
aartbik
authored and
[email protected]
committed
[dart/compiler] Loop analysis and BCE improvements
Rationale: Loop analysis did not take outer indices used as bounds (triangular loops) into account to enhance analysis. This left some obvious BCE optimizations on the table (mainly AOT). Observed improvements (performance and code size): About 5-15% performance on golem benchmarks: mainly armv7, and TypedData*Bench Minor overall code size reduction on flutter gallery (arm32,arm64) Comparing ./orig32.json (old) to ./new32.json (new) Old   : 6614912 bytes. New   : 6600336 bytes. Change: -14576 bytes. Comparing ./orig64.json (old) to ./new64.json (new) Old   : 6459216 bytes. New   : 6458736 bytes. Change: -480 bytes. Similar on velocity_tracker_bench (arm32,arm64) Comparing orig32.json (old) to new32.json (new) Old : 804280 bytes. New : 794552 bytes. Change: -9728 bytes. Comparing orig64.json (old) to new64.json (new) Old   : 705520 bytes. New   : 705312 bytes. Change: -208 bytes. Change-Id: Ifc3b3a378ae6fd98743c48944a86a9e90ce4da5c Reviewed-on: https://dart-review.googlesource.com/c/sdk/+/117200 Reviewed-by: Vyacheslav Egorov <[email protected]> Reviewed-by: Martin Kustermann <[email protected]> Commit-Queue: Aart Bik <[email protected]>
1 parent b716efb commit 29ff784

7 files changed

Lines changed: 897 additions & 119 deletions

File tree

‎runtime/vm/compiler/backend/bce_test.cc‎

Lines changed: 165 additions & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -83,8 +83,7 @@ ISOLATE_UNIT_TEST_CASE(BCECannotRemove) {
8383
return l[0];
8484
}
8585
main() {
86-
var l = new Float64List(1);
87-
foo(l);
86+
foo(new Float64List(1));
8887
}
8988
)";
9089
TestScriptJIT(kScriptChars, 1, 1);
@@ -98,28 +97,48 @@ ISOLATE_UNIT_TEST_CASE(BCERemoveOne) {
9897
return l[1] + l[0];
9998
}
10099
main() {
101-
var l = new Float64List(2);
102-
foo(l);
100+
foo(new Float64List(2));
103101
}
104102
)";
105103
TestScriptJIT(kScriptChars, 2, 1);
106104
}
107105

108-
ISOLATE_UNIT_TEST_CASE(BCESimpleLoop) {
106+
ISOLATE_UNIT_TEST_CASE(BCESimpleLoops) {
109107
const char* kScriptChars =
110108
R"(
111109
import 'dart:typed_data';
112110
foo(Float64List l) {
113111
for (int i = 0; i < l.length; i++) {
114112
l[i] = 0;
115113
}
114+
for (int i = 10; i <= l.length - 5; i++) {
115+
l[i] = 1;
116+
}
116117
}
117118
main() {
118-
var l = new Float64List(100);
119-
foo(l);
119+
foo(new Float64List(100));
120120
}
121121
)";
122-
TestScriptJIT(kScriptChars, 1, 0);
122+
TestScriptJIT(kScriptChars, 2, 0);
123+
}
124+
125+
ISOLATE_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);
123142
}
124143

125144
ISOLATE_UNIT_TEST_CASE(BCEModulo) {
@@ -136,6 +155,143 @@ ISOLATE_UNIT_TEST_CASE(BCEModulo) {
136155
TestScriptJIT(kScriptChars, 2, 0);
137156
}
138157

139-
// TODO(ajcbik): add more tests
158+
ISOLATE_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+
176+
ISOLATE_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+
194+
ISOLATE_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+
212+
ISOLATE_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+
230+
ISOLATE_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+
254+
ISOLATE_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+
277+
ISOLATE_UNIT_TEST_CASE(BCEListNamedAndPlainLength) {
278+
const char* kScriptChars =
279+
R"(
280+
List<int> foo(int count) {
281+
var x = new List<int>(count);
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+
}
140296

141297
} // namespace dart

‎runtime/vm/compiler/backend/il.cc‎

Lines changed: 10 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -543,6 +543,16 @@ Definition* Definition::OriginalDefinitionIgnoreBoxingAndConstraints() {
543543
}
544544
}
545545

546+
bool Definition::IsArrayLength(Definition* def) {
547+
if (def != nullptr) {
548+
if (auto load = def->OriginalDefinitionIgnoreBoxingAndConstraints()
549+
->AsLoadField()) {
550+
return load->IsImmutableLengthLoad();
551+
}
552+
}
553+
return false;
554+
}
555+
546556
const ICData* Instruction::GetICData(
547557
const ZoneGrowableArray<const ICData*>& ic_data_array) const {
548558
// The deopt_id can be outside the range of the IC data array for

‎runtime/vm/compiler/backend/il.h‎

Lines changed: 4 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -2225,6 +2225,9 @@ class Definition : public Instruction {
22252225
// boxing/unboxing and constraint instructions.
22262226
Definition* OriginalDefinitionIgnoreBoxingAndConstraints();
22272227

2228+
// Helper method to determine if definition denotes an array length.
2229+
static bool IsArrayLength(Definition* def);
2230+
22282231
virtual Definition* AsDefinition() { return this; }
22292232
virtual const Definition* AsDefinition() const { return this; }
22302233

@@ -7916,7 +7919,7 @@ class CheckBoundBase : public TemplateDefinition<2, NoThrow, Pure> {
79167919

79177920
// Returns true if the bounds check can be eliminated without
79187921
// changing the semantics (viz. 0 <= index < length).
7919-
bool IsRedundant();
7922+
bool IsRedundant(bool use_loops = false);
79207923

79217924
// Give a name to the location/input indices.
79227925
enum { kLengthPos = 0, kIndexPos = 1 };

0 commit comments

Comments
 (0)