[vm/compiler] Handle _GrowableList.length as a symbolic boundary in range analysis
TEST=runtime/tests/vm/dart/regress_56099_il_test.dart
Fixes https://github.com/dart-lang/sdk/issues/56099
Change-Id: Ie078bfbc547e2aaa078144802c2ddfd00e0ec3aa
Reviewed-on: https://dart-review.googlesource.com/c/sdk/+/377060
Reviewed-by: Tess Strickland <sstrickl@google.com>
Commit-Queue: Alexander Markov <alexmarkov@google.com>
diff --git a/runtime/tests/vm/dart/regress_56099_il_test.dart b/runtime/tests/vm/dart/regress_56099_il_test.dart
new file mode 100644
index 0000000..fa34a16
--- /dev/null
+++ b/runtime/tests/vm/dart/regress_56099_il_test.dart
@@ -0,0 +1,69 @@
+// Copyright (c) 2024, 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.
+
+// Verifies that bounds check is removed from _GrowableList.add.
+
+import 'package:vm/testing/il_matchers.dart';
+
+@pragma('vm:never-inline')
+@pragma('vm:testing:print-flow-graph')
+void addElement(List<int> list, int value) {
+ list.add(value);
+}
+
+void main() {
+ addElement([], int.parse('42'));
+}
+
+void matchIL$addElement(FlowGraph graph) {
+ if (is32BitConfiguration) {
+ return;
+ }
+ graph.dump();
+ graph.match([
+ match.block('Graph', [
+ 'c_null' << match.Constant(value: null),
+ 'c_one' << match.UnboxedConstant(value: 1),
+ ]),
+ match.block('Function', [
+ 'list' << match.Parameter(index: 0),
+ 'value' << match.Parameter(index: 1),
+ match.CheckStackOverflow(),
+ 'list.length' <<
+ match.LoadField('list', slot: 'GrowableObjectArray.length'),
+ 'list.data' << match.LoadField('list', slot: 'GrowableObjectArray.data'),
+ 'capacity' << match.LoadField('list.data', slot: 'Array.length'),
+ 'length_unboxed' << match.UnboxInt64('list.length'),
+ 'capacity_unboxed' << match.UnboxInt64('capacity'),
+ match.Branch(
+ match.EqualityCompare('length_unboxed', 'capacity_unboxed',
+ kind: '=='),
+ ifTrue: 'B5',
+ ifFalse: 'B6'),
+ ]),
+ 'B5' <<
+ match.block('Target', [
+ match.StaticCall(),
+ match.Goto('B7'),
+ ]),
+ 'B6' <<
+ match.block('Target', [
+ match.Goto('B7'),
+ ]),
+ 'B7' <<
+ match.block('Join', [
+ 'length_plus_1' << match.BinaryInt64Op('length_unboxed', 'c_one'),
+ 'length_plus_1_boxed' << match.BoxInt64('length_plus_1'),
+ match.StoreField('list', 'length_plus_1_boxed',
+ slot: 'GrowableObjectArray.length'),
+ // No bounds check here.
+ 'list.data_v2' <<
+ match.LoadField('list',
+ slot: 'GrowableObjectArray.data', skipUntilMatched: false),
+ 'value_boxed' << match.BoxInt64('value', skipUntilMatched: false),
+ match.StoreIndexed('list.data_v2', 'length_unboxed', 'value_boxed'),
+ match.DartReturn('c_null'),
+ ]),
+ ]);
+}
diff --git a/runtime/vm/compiler/backend/il.cc b/runtime/vm/compiler/backend/il.cc
index 0316283..3889614 100644
--- a/runtime/vm/compiler/backend/il.cc
+++ b/runtime/vm/compiler/backend/il.cc
@@ -582,11 +582,11 @@
}
}
-bool Definition::IsArrayLength(Definition* def) {
+bool Definition::IsLengthLoad(Definition* def) {
if (def != nullptr) {
if (auto load = def->OriginalDefinitionIgnoreBoxingAndConstraints()
->AsLoadField()) {
- return load->IsImmutableLengthLoad();
+ return load->slot().IsLengthSlot();
}
}
return false;
diff --git a/runtime/vm/compiler/backend/il.h b/runtime/vm/compiler/backend/il.h
index 49220279..303c592 100644
--- a/runtime/vm/compiler/backend/il.h
+++ b/runtime/vm/compiler/backend/il.h
@@ -2677,8 +2677,9 @@
// boxing/unboxing and constraint instructions.
Definition* OriginalDefinitionIgnoreBoxingAndConstraints();
- // Helper method to determine if definition denotes an array length.
- static bool IsArrayLength(Definition* def);
+ // Helper method to determine if definition denotes a load of
+ // length of array/growable array/string/typed data/type arguments vector.
+ static bool IsLengthLoad(Definition* def);
virtual Definition* AsDefinition() { return this; }
virtual const Definition* AsDefinition() const { return this; }
diff --git a/runtime/vm/compiler/backend/loops.cc b/runtime/vm/compiler/backend/loops.cc
index 6dd395c..ede1273 100644
--- a/runtime/vm/compiler/backend/loops.cc
+++ b/runtime/vm/compiler/backend/loops.cc
@@ -149,7 +149,7 @@
} else if (InductionVar::IsConstant(max, &end)) {
return end < kMaxInt64;
} else if (InductionVar::IsInvariant(max) && max->mult() == 1 &&
- Definition::IsArrayLength(max->def())) {
+ Definition::IsLengthLoad(max->def())) {
return max->offset() < 0; // a.length - C, C > 0
}
}
@@ -184,7 +184,7 @@
success = (l <= u);
} else if (InductionVar::IsInvariant(upper_bound) &&
upper_bound->mult() == 1 &&
- Definition::IsArrayLength(upper_bound->def())) {
+ Definition::IsLengthLoad(upper_bound->def())) {
// No arithmetic wrap-around on the lower bound, and a properly
// non-positive offset on an array length, which is always >= 0.
const int64_t c = upper_bound->offset() + upper_bound_offset;
diff --git a/runtime/vm/compiler/backend/range_analysis.cc b/runtime/vm/compiler/backend/range_analysis.cc
index 3c4a0bf..c8886c0 100644
--- a/runtime/vm/compiler/backend/range_analysis.cc
+++ b/runtime/vm/compiler/backend/range_analysis.cc
@@ -2372,11 +2372,11 @@
ASSERT(result_min != nullptr);
ASSERT(result_max != nullptr);
- RangeBoundary left_min = Definition::IsArrayLength(left_defn)
+ RangeBoundary left_min = Definition::IsLengthLoad(left_defn)
? RangeBoundary::FromDefinition(left_defn)
: left_range->min();
- RangeBoundary left_max = Definition::IsArrayLength(left_defn)
+ RangeBoundary left_max = Definition::IsLengthLoad(left_defn)
? RangeBoundary::FromDefinition(left_defn)
: left_range->max();
@@ -2417,11 +2417,11 @@
ASSERT(result_min != nullptr);
ASSERT(result_max != nullptr);
- RangeBoundary left_min = Definition::IsArrayLength(left_defn)
+ RangeBoundary left_min = Definition::IsLengthLoad(left_defn)
? RangeBoundary::FromDefinition(left_defn)
: left_range->min();
- RangeBoundary left_max = Definition::IsArrayLength(left_defn)
+ RangeBoundary left_max = Definition::IsLengthLoad(left_defn)
? RangeBoundary::FromDefinition(left_defn)
: left_range->max();
diff --git a/runtime/vm/compiler/backend/slot.cc b/runtime/vm/compiler/backend/slot.cc
index 522bd78..5092771 100644
--- a/runtime/vm/compiler/backend/slot.cc
+++ b/runtime/vm/compiler/backend/slot.cc
@@ -205,6 +205,19 @@
return SlotCache::Instance(Thread::Current()).GetNativeSlot(kind);
}
+bool Slot::IsLengthSlot() const {
+ switch (kind()) {
+ case Slot::Kind::kArray_length:
+ case Slot::Kind::kTypedDataBase_length:
+ case Slot::Kind::kString_length:
+ case Slot::Kind::kTypeArguments_length:
+ case Slot::Kind::kGrowableObjectArray_length:
+ return true;
+ default:
+ return false;
+ }
+}
+
bool Slot::IsImmutableLengthSlot() const {
switch (kind()) {
case Slot::Kind::kArray_length:
@@ -212,37 +225,9 @@
case Slot::Kind::kString_length:
case Slot::Kind::kTypeArguments_length:
return true;
- case Slot::Kind::kGrowableObjectArray_length:
- return false;
-
- // Not length loads.
- case Slot::Kind::kArrayElement:
- case Slot::Kind::kCapturedVariable:
- case Slot::Kind::kDartField:
- case Slot::Kind::kRecordField:
- case Slot::Kind::kTypeArguments:
- case Slot::Kind::kTypeArgumentsIndex:
-#define NOT_TAGGED_INT_NATIVE_SLOT_CASE(Class, __, Field, ___, ____) \
- case Slot::Kind::k##Class##_##Field:
- NOT_INT_NATIVE_SLOTS_LIST(NOT_TAGGED_INT_NATIVE_SLOT_CASE)
- UNBOXED_NATIVE_SLOTS_LIST(NOT_TAGGED_INT_NATIVE_SLOT_CASE)
-#undef NONTAGGED_NATIVE_DART_SLOT_CASE
- case Slot::Kind::kLinkedHashBase_hash_mask:
- case Slot::Kind::kLinkedHashBase_used_data:
- case Slot::Kind::kLinkedHashBase_deleted_keys:
- case Slot::Kind::kArgumentsDescriptor_type_args_len:
- case Slot::Kind::kArgumentsDescriptor_positional_count:
- case Slot::Kind::kArgumentsDescriptor_count:
- case Slot::Kind::kArgumentsDescriptor_size:
- case Slot::Kind::kTypeArguments_hash:
- case Slot::Kind::kTypedDataView_offset_in_bytes:
- case Slot::Kind::kClosure_hash:
- case Slot::Kind::kRecord_shape:
- case Slot::Kind::kAbstractType_hash:
+ default:
return false;
}
- UNREACHABLE();
- return false;
}
// Note: should only be called with cids of array-like classes.
diff --git a/runtime/vm/compiler/backend/slot.h b/runtime/vm/compiler/backend/slot.h
index c6bb983..51fd780 100644
--- a/runtime/vm/compiler/backend/slot.h
+++ b/runtime/vm/compiler/backend/slot.h
@@ -506,6 +506,7 @@
bool IsArgumentOfType() const { return kind() == Kind::kTypeArgumentsIndex; }
bool IsArrayElement() const { return kind() == Kind::kArrayElement; }
bool IsRecordField() const { return kind() == Kind::kRecordField; }
+ bool IsLengthSlot() const;
bool IsImmutableLengthSlot() const;
const char* Name() const;
