[vm/compiler] AOT bounds check elimination
Rationale:
With the new induction variable bounds in place, this
is the first very low hanging fruit. When a loop bound
matches the array bounds check, it is redundant. This
removes AOT non-speculative bounds checks for the first
time. More improvements to follow!
Change-Id: I5dac885a1ef6fdb64b5844a0617d2fe9d800d9d6
Reviewed-on: https://dart-review.googlesource.com/c/87940
Commit-Queue: Aart Bik <ajcbik@google.com>
Reviewed-by: Vyacheslav Egorov <vegorov@google.com>
diff --git a/runtime/vm/compiler/backend/il.h b/runtime/vm/compiler/backend/il.h
index 9d4fc4e..8bbb6d1 100644
--- a/runtime/vm/compiler/backend/il.h
+++ b/runtime/vm/compiler/backend/il.h
@@ -7276,6 +7276,8 @@
// ArgumentError constructor), so it can lazily deopt.
virtual bool ComputeCanDeoptimize() const { return true; }
+ bool IsRedundant(const RangeBoundary& length);
+
// Give a name to the location/input indices.
enum { kLengthPos = 0, kIndexPos = 1 };
diff --git a/runtime/vm/compiler/backend/range_analysis.cc b/runtime/vm/compiler/backend/range_analysis.cc
index 7fa08c0..28f2199 100644
--- a/runtime/vm/compiler/backend/range_analysis.cc
+++ b/runtime/vm/compiler/backend/range_analysis.cc
@@ -107,8 +107,8 @@
}
}
}
- if (current->IsCheckArrayBound()) {
- bounds_checks_.Add(current->AsCheckArrayBound());
+ if (current->IsCheckArrayBound() || current->IsGenericCheckBound()) {
+ bounds_checks_.Add(current);
}
}
}
@@ -1017,8 +1017,8 @@
return phi;
}
// Decide between direct or indirect bound.
- Definition* bounded_phi = UnwrapConstraint(limit->value()->definition());
- if (bounded_phi == phi) {
+ Definition* bounded_def = UnwrapConstraint(limit->value()->definition());
+ if (bounded_def == phi) {
// Given a smi bounded loop with smi induction variable
//
// x <- phi(x0, x + 1)
@@ -1037,7 +1037,7 @@
//
// y <= y0 + (M - x0)
//
- InductionVar* bounded_induc = GetSmiInduction(loop, bounded_phi);
+ InductionVar* bounded_induc = GetSmiInduction(loop, bounded_def);
Definition* x0 = GenerateInvariant(bounded_induc->initial());
Definition* y0 = GenerateInvariant(induc->initial());
Definition* m = RangeBoundaryToDefinition(limit->constraint()->max());
@@ -1321,7 +1321,21 @@
BoundsCheckGeneralizer generalizer(this, flow_graph_);
for (intptr_t i = 0; i < bounds_checks_.length(); i++) {
- CheckArrayBoundInstr* check = bounds_checks_[i];
+ // Is this a non-speculative check bound?
+ GenericCheckBoundInstr* aot_check =
+ bounds_checks_[i]->AsGenericCheckBound();
+ if (aot_check != nullptr) {
+ RangeBoundary array_length =
+ RangeBoundary::FromDefinition(aot_check->length()->definition());
+ if (aot_check->IsRedundant(array_length)) {
+ aot_check->ReplaceUsesWith(aot_check->index()->definition());
+ aot_check->RemoveFromGraph();
+ }
+ continue;
+ }
+ // Must be a speculative check bound.
+ CheckArrayBoundInstr* check = bounds_checks_[i]->AsCheckArrayBound();
+ ASSERT(check != nullptr);
RangeBoundary array_length =
RangeBoundary::FromDefinition(check->length()->definition());
if (check->IsRedundant(array_length)) {
@@ -2928,6 +2942,52 @@
return false;
}
+// Check if range boundary and invariant limit are the same boundary.
+static bool IsSameBound(const RangeBoundary& a, InductionVar* b) {
+ ASSERT(InductionVar::IsInvariant(b));
+ if (a.IsSymbol()) {
+ // Check for exactly the same symbol as length.
+ return a.symbol() == b->def() && b->mult() == 1 &&
+ a.offset() == b->offset();
+ } else if (a.IsConstant()) {
+ // Check for constant in right range 0 < c <= length.
+ int64_t c = 0;
+ return InductionVar::IsConstant(b, &c) && 0 < c && c <= a.ConstantValue();
+ }
+ return false;
+}
+
+bool GenericCheckBoundInstr::IsRedundant(const RangeBoundary& length) {
+ // In loop, with index as induction?
+ LoopInfo* loop = GetBlock()->loop_info();
+ if (loop == nullptr) {
+ return false;
+ }
+ InductionVar* induc = loop->LookupInduction(index()->definition());
+ if (induc == nullptr) {
+ return false;
+ }
+ // Under 64-bit wrap-around arithmetic, it is always safe to remove the
+ // bounds check from the following, if initial >= 0 and the corresponding
+ // exit branch dominates the bounds check:
+ // for (int i = initial; i < length; i++)
+ // .... a[i] ....
+ int64_t stride = 0;
+ int64_t initial = 0;
+ if (InductionVar::IsLinear(induc, &stride) &&
+ InductionVar::IsConstant(induc->initial(), &initial)) {
+ if (stride == 1 && initial >= 0) {
+ for (auto bound : induc->bounds()) {
+ if (IsSameBound(length, bound.limit_) &&
+ this->IsDominatedBy(bound.branch_)) {
+ return true;
+ }
+ }
+ }
+ }
+ return false;
+}
+
} // namespace dart
#endif // !defined(DART_PRECOMPILED_RUNTIME)
diff --git a/runtime/vm/compiler/backend/range_analysis.h b/runtime/vm/compiler/backend/range_analysis.h
index 56dc78e..24adeed 100644
--- a/runtime/vm/compiler/backend/range_analysis.h
+++ b/runtime/vm/compiler/backend/range_analysis.h
@@ -605,8 +605,8 @@
GrowableArray<BinaryInt64OpInstr*> binary_int64_ops_;
GrowableArray<ShiftIntegerOpInstr*> shift_int64_ops_;
- // All CheckArrayBound instructions.
- GrowableArray<CheckArrayBoundInstr*> bounds_checks_;
+ // All CheckArrayBound/GenericCheckBound instructions.
+ GrowableArray<Instruction*> bounds_checks_;
// All Constraints inserted during InsertConstraints phase. They are treated
// as smi values.
