[VM] Generalize generic bounds check elimination
When eliminating bounds checks using loop information the length of
GenericBoundsCheckInstr is directly compared to the loop bound.
Instead we should compare the original definitions, ignoring any
boxing/unboxing. This allows the elimination of more bounds checks.
Issue https://github.com/dart-lang/sdk/issues/35154
Cq-Include-Trybots: luci.dart.try:vm-canary-linux-debug-try, vm-dartkb-linux-debug-x64-try, vm-dartkb-linux-release-x64-try, vm-kernel-asan-linux-release-x64-try, vm-kernel-checked-linux-release-x64-try, vm-kernel-linux-debug-ia32-try, vm-kernel-linux-debug-simdbc64-try, vm-kernel-linux-debug-x64-try, vm-kernel-linux-product-x64-try, vm-kernel-linux-release-ia32-try, vm-kernel-linux-release-simarm-try, vm-kernel-linux-release-simarm64-try, vm-kernel-linux-release-simdbc64-try, vm-kernel-linux-release-x64-try, vm-kernel-optcounter-threshold-linux-release-ia32-try, vm-kernel-optcounter-threshold-linux-release-x64-try, vm-kernel-precomp-android-release-arm-try, vm-kernel-precomp-bare-linux-release-simarm-try, vm-kernel-precomp-bare-linux-release-simarm64-try, vm-kernel-precomp-bare-linux-release-x64-try, vm-kernel-precomp-linux-debug-x64-try, vm-kernel-precomp-linux-product-x64-try, vm-kernel-precomp-linux-release-simarm-try, vm-kernel-precomp-linux-release-simarm64-try, vm-kernel-precomp-linux-release-x64-try, vm-kernel-precomp-obfuscate-linux-release-x64-try, vm-kernel-precomp-win-release-simarm64-try, vm-kernel-precomp-win-release-x64-try, vm-kernel-reload-linux-debug-x64-try, vm-kernel-reload-linux-release-x64-try, vm-kernel-reload-rollback-linux-debug-x64-try, vm-kernel-reload-rollback-linux-release-x64-try, vm-kernel-win-debug-ia32-try, vm-kernel-win-debug-x64-try, vm-kernel-win-product-x64-try, vm-kernel-win-release-ia32-try, vm-kernel-win-release-x64-try
Change-Id: Ie10880f833f3b55d0804a03c4be9bd9d1ad52f66
Reviewed-on: https://dart-review.googlesource.com/c/sdk/+/97331
Commit-Queue: Martin Kustermann <kustermann@google.com>
Reviewed-by: Aart Bik <ajcbik@google.com>
Reviewed-by: Vyacheslav Egorov <vegorov@google.com>
diff --git a/runtime/vm/compiler/backend/il.cc b/runtime/vm/compiler/backend/il.cc
index fbaf069..4d35d2f 100644
--- a/runtime/vm/compiler/backend/il.cc
+++ b/runtime/vm/compiler/backend/il.cc
@@ -520,6 +520,20 @@
return defn;
}
+Definition* Definition::OriginalDefinitionIgnoreBoxingAndConstraints() {
+ Definition* def = this;
+ while (true) {
+ Definition* orig;
+ if (def->IsConstraint() || def->IsBox() || def->IsUnbox()) {
+ orig = def->InputAt(0)->definition();
+ } else {
+ orig = def->OriginalDefinition();
+ }
+ if (orig == def) return def;
+ def = orig;
+ }
+}
+
const ICData* Instruction::GetICData(
const ZoneGrowableArray<const ICData*>& ic_data_array) const {
// The deopt_id can be outside the range of the IC data array for
diff --git a/runtime/vm/compiler/backend/il.h b/runtime/vm/compiler/backend/il.h
index 20d2bd3..7164da81 100644
--- a/runtime/vm/compiler/backend/il.h
+++ b/runtime/vm/compiler/backend/il.h
@@ -1938,8 +1938,16 @@
virtual void SetIdentity(AliasIdentity identity) { UNREACHABLE(); }
+ // Find the original definition of [this] by following through any
+ // redefinition and check instructions.
Definition* OriginalDefinition();
+ // Find the original definition of [this].
+ //
+ // This is an extension of [OriginalDefinition] which also follows through any
+ // boxing/unboxing and constraint instructions.
+ Definition* OriginalDefinitionIgnoreBoxingAndConstraints();
+
virtual Definition* AsDefinition() { return this; }
protected:
diff --git a/runtime/vm/compiler/backend/loops.cc b/runtime/vm/compiler/backend/loops.cc
index f307a21..a641557 100644
--- a/runtime/vm/compiler/backend/loops.cc
+++ b/runtime/vm/compiler/backend/loops.cc
@@ -132,22 +132,6 @@
return false;
}
-// Helper method to trace back to original true definition, now
-// also ignoring constraints and (un)boxing operations, since
-// these are not relevant to the induction behavior.
-static Definition* OriginalDefinition(Definition* def) {
- while (true) {
- Definition* orig;
- if (def->IsConstraint() || def->IsBox() || def->IsUnbox()) {
- orig = def->InputAt(0)->definition();
- } else {
- orig = def->OriginalDefinition();
- }
- if (orig == def) return def;
- def = orig;
- }
-}
-
void InductionVarAnalysis::VisitHierarchy(LoopInfo* loop) {
for (; loop != nullptr; loop = loop->next_) {
VisitLoop(loop);
@@ -273,7 +257,7 @@
} else if (def->IsUnaryIntegerOp()) {
induc = TransferUnary(loop, def);
} else {
- Definition* orig = OriginalDefinition(def);
+ Definition* orig = def->OriginalDefinitionIgnoreBoxingAndConstraints();
if (orig != def) {
induc = Lookup(loop, orig); // pass-through
}
@@ -316,7 +300,7 @@
} else if (def->IsConstraint()) {
update = SolveConstraint(loop, def, init);
} else {
- Definition* orig = OriginalDefinition(def);
+ Definition* orig = def->OriginalDefinitionIgnoreBoxingAndConstraints();
if (orig != def) {
update = LookupCycle(orig); // pass-through
}
@@ -370,10 +354,14 @@
// Comparison against linear constant stride induction?
// Express the comparison such that induction appears left.
int64_t stride = 0;
- InductionVar* x =
- Lookup(loop, OriginalDefinition(compare->left()->definition()));
- InductionVar* y =
- Lookup(loop, OriginalDefinition(compare->right()->definition()));
+ auto left = compare->left()
+ ->definition()
+ ->OriginalDefinitionIgnoreBoxingAndConstraints();
+ auto right = compare->right()
+ ->definition()
+ ->OriginalDefinitionIgnoreBoxingAndConstraints();
+ InductionVar* x = Lookup(loop, left);
+ InductionVar* y = Lookup(loop, right);
if (InductionVar::IsLinear(x, &stride) && InductionVar::IsInvariant(y)) {
// ok as is
} else if (InductionVar::IsInvariant(x) &&
diff --git a/runtime/vm/compiler/backend/range_analysis.cc b/runtime/vm/compiler/backend/range_analysis.cc
index 8793f26..65d61e9 100644
--- a/runtime/vm/compiler/backend/range_analysis.cc
+++ b/runtime/vm/compiler/backend/range_analysis.cc
@@ -1321,11 +1321,12 @@
for (intptr_t i = 0; i < bounds_checks_.length(); i++) {
// Is this a non-speculative check bound?
- GenericCheckBoundInstr* aot_check =
- bounds_checks_[i]->AsGenericCheckBound();
+ auto aot_check = bounds_checks_[i]->AsGenericCheckBound();
if (aot_check != nullptr) {
- RangeBoundary array_length =
- RangeBoundary::FromDefinition(aot_check->length()->definition());
+ auto length = aot_check->length()
+ ->definition()
+ ->OriginalDefinitionIgnoreBoxingAndConstraints();
+ auto array_length = RangeBoundary::FromDefinition(length);
if (aot_check->IsRedundant(array_length)) {
aot_check->ReplaceUsesWith(aot_check->index()->definition());
aot_check->RemoveFromGraph();
