Skip to content

Commit a9f6e03

Browse files
aartbikcommit-bot@chromium.org
aartbik
authored and
[email protected]
committed
[vm/compiler] Unify IsRedundant for JIT/AOT bounds checks
Rationale: The range analysis carefully computes ranges on Smis such that the results are valid for both JIT and AOT. So the IsRedundant() tests between the speculative and non-speculative bounds checks can be shared. This does not only reduce the amount of code, but also improves actual bounds check elimination. #37687 Change-Id: I883a16d4be4d3704cad3e42264e1f36a5afc3b89 Reviewed-on: https://dart-review.googlesource.com/c/sdk/+/112167 Commit-Queue: Aart Bik <[email protected]> Reviewed-by: Martin Kustermann <[email protected]>
1 parent 63a1478 commit a9f6e03

File tree

6 files changed

+189
-75
lines changed

6 files changed

+189
-75
lines changed

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

Lines changed: 125 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,125 @@
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+
17+
namespace dart {
18+
19+
// Helper method to count number of bounds checks.
20+
static 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.
36+
static std::pair<intptr_t, intptr_t> ApplyBCE(const char* script_chars) {
37+
// Load the script and exercise the code once
38+
// while exercising the given compiler passes.
39+
const auto& root_library = Library::Handle(LoadTestScript(script_chars));
40+
Invoke(root_library, "main");
41+
std::initializer_list<CompilerPass::Id> passes = {
42+
CompilerPass::kComputeSSA,
43+
CompilerPass::kTypePropagation,
44+
CompilerPass::kApplyICData,
45+
CompilerPass::kInlining,
46+
CompilerPass::kTypePropagation,
47+
CompilerPass::kApplyICData,
48+
CompilerPass::kSelectRepresentations,
49+
CompilerPass::kCanonicalize,
50+
CompilerPass::kCSE,
51+
CompilerPass::kLICM,
52+
};
53+
const auto& function = Function::Handle(GetFunction(root_library, "foo"));
54+
// TODO(ajcbik): test CompilerPass::kAOT too, but how to deal
55+
// with FLAG_precompiled_mode and DART_PRECOMPILER?
56+
TestPipeline pipeline(function, CompilerPass::kJIT);
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+
66+
//
67+
// BCE (bounds-check-elimination) tests.
68+
//
69+
70+
ISOLATE_UNIT_TEST_CASE(BCECannotRemove) {
71+
const char* kScriptChars =
72+
R"(
73+
import 'dart:typed_data';
74+
foo(Float64List l) {
75+
return l[0];
76+
}
77+
main() {
78+
var l = new Float64List(1);
79+
foo(l);
80+
}
81+
)";
82+
auto result = ApplyBCE(kScriptChars);
83+
EXPECT_STREQ(1, result.first);
84+
EXPECT_STREQ(1, result.second);
85+
}
86+
87+
ISOLATE_UNIT_TEST_CASE(BCERemoveOne) {
88+
const char* kScriptChars =
89+
R"(
90+
import 'dart:typed_data';
91+
foo(Float64List l) {
92+
return l[1] + l[0];
93+
}
94+
main() {
95+
var l = new Float64List(2);
96+
foo(l);
97+
}
98+
)";
99+
auto result = ApplyBCE(kScriptChars);
100+
EXPECT_STREQ(2, result.first);
101+
EXPECT_STREQ(1, result.second);
102+
}
103+
104+
ISOLATE_UNIT_TEST_CASE(BCESimpleLoop) {
105+
const char* kScriptChars =
106+
R"(
107+
import 'dart:typed_data';
108+
foo(Float64List l) {
109+
for (int i = 0; i < l.length; i++) {
110+
l[i] = 0;
111+
}
112+
}
113+
main() {
114+
var l = new Float64List(100);
115+
foo(l);
116+
}
117+
)";
118+
auto result = ApplyBCE(kScriptChars);
119+
EXPECT_STREQ(1, result.first);
120+
EXPECT_STREQ(0, result.second);
121+
}
122+
123+
// TODO(ajcbik): add more tests
124+
125+
} // namespace dart

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

Lines changed: 1 addition & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -5176,9 +5176,7 @@ bool CheckArrayBoundInstr::IsFixedLengthArrayType(intptr_t cid) {
51765176
}
51775177

51785178
Definition* CheckArrayBoundInstr::Canonicalize(FlowGraph* flow_graph) {
5179-
return IsRedundant(RangeBoundary::FromDefinition(length()->definition()))
5180-
? index()->definition()
5181-
: this;
5179+
return IsRedundant() ? index()->definition() : this;
51825180
}
51835181

51845182
intptr_t CheckArrayBoundInstr::LengthOffsetFor(intptr_t class_id) {

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

Lines changed: 5 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -7692,7 +7692,7 @@ class CheckClassIdInstr : public TemplateInstruction<1, NoThrow> {
76927692
};
76937693

76947694
// Base class for speculative [CheckArrayBoundInstr] and
7695-
// [GenericCheckBoundInstr]
7695+
// non-speculative [GenericCheckBoundInstr] bounds checking.
76967696
class CheckBoundBase : public TemplateDefinition<2, NoThrow, Pure> {
76977697
public:
76987698
CheckBoundBase(Value* length, Value* index, intptr_t deopt_id)
@@ -7708,6 +7708,10 @@ class CheckBoundBase : public TemplateDefinition<2, NoThrow, Pure> {
77087708
virtual CheckBoundBase* AsCheckBoundBase() { return this; }
77097709
virtual Value* RedefinedValue() const;
77107710

7711+
// Returns true if the bounds check can be eliminated without
7712+
// changing the semantics (viz. 0 <= index < length).
7713+
bool IsRedundant();
7714+
77117715
// Give a name to the location/input indices.
77127716
enum { kLengthPos = 0, kIndexPos = 1 };
77137717

@@ -7734,8 +7738,6 @@ class CheckArrayBoundInstr : public CheckBoundBase {
77347738

77357739
virtual bool ComputeCanDeoptimize() const { return true; }
77367740

7737-
bool IsRedundant(const RangeBoundary& length);
7738-
77397741
void mark_generalized() { generalized_ = true; }
77407742

77417743
virtual Definition* Canonicalize(FlowGraph* flow_graph);
@@ -7777,8 +7779,6 @@ class GenericCheckBoundInstr : public CheckBoundBase {
77777779
// ArgumentError constructor), so it can lazily deopt.
77787780
virtual bool ComputeCanDeoptimize() const { return true; }
77797781

7780-
bool IsRedundant(const RangeBoundary& length);
7781-
77827782
virtual bool MayThrow() const { return true; }
77837783

77847784
private:

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

Lines changed: 56 additions & 66 deletions
Original file line numberDiff line numberDiff line change
@@ -103,8 +103,8 @@ void RangeAnalysis::CollectValues() {
103103
}
104104
}
105105
}
106-
if (current->IsCheckArrayBound() || current->IsGenericCheckBound()) {
107-
bounds_checks_.Add(current);
106+
if (auto check = current->AsCheckBoundBase()) {
107+
bounds_checks_.Add(check);
108108
}
109109
}
110110
}
@@ -723,8 +723,7 @@ class BoundsCheckGeneralizer {
723723
flow_graph_(flow_graph),
724724
scheduler_(flow_graph) {}
725725

726-
void TryGeneralize(CheckArrayBoundInstr* check,
727-
const RangeBoundary& array_length) {
726+
void TryGeneralize(CheckArrayBoundInstr* check) {
728727
Definition* upper_bound =
729728
ConstructUpperBound(check->index()->definition(), check);
730729
if (upper_bound == UnwrapConstraint(check->index()->definition())) {
@@ -837,7 +836,7 @@ class BoundsCheckGeneralizer {
837836
new Value(UnwrapConstraint(check->length()->definition())),
838837
new Value(upper_bound), DeoptId::kNone);
839838
new_check->mark_generalized();
840-
if (new_check->IsRedundant(array_length)) {
839+
if (new_check->IsRedundant()) {
841840
if (FLAG_trace_range_analysis) {
842841
THR_Print(" => generalized check is redundant\n");
843842
}
@@ -1307,38 +1306,20 @@ void RangeAnalysis::EliminateRedundantBoundsChecks() {
13071306
if (FLAG_array_bounds_check_elimination) {
13081307
const Function& function = flow_graph_->function();
13091308
// Generalization only if we have not deoptimized on a generalized
1310-
// check earlier, or we're compiling precompiled code (no
1311-
// optimistic hoisting of checks possible)
1309+
// check earlier and we are not compiling precompiled code
1310+
// (no optimistic hoisting of checks possible)
13121311
const bool try_generalization =
1313-
!function.ProhibitsBoundsCheckGeneralization() &&
1314-
!FLAG_precompiled_mode;
1315-
1312+
!FLAG_precompiled_mode &&
1313+
!function.ProhibitsBoundsCheckGeneralization();
13161314
BoundsCheckGeneralizer generalizer(this, flow_graph_);
1317-
1318-
for (intptr_t i = 0; i < bounds_checks_.length(); i++) {
1319-
// Is this a non-speculative check bound?
1320-
auto aot_check = bounds_checks_[i]->AsGenericCheckBound();
1321-
if (aot_check != nullptr) {
1322-
auto length = aot_check->length()
1323-
->definition()
1324-
->OriginalDefinitionIgnoreBoxingAndConstraints();
1325-
auto array_length = RangeBoundary::FromDefinition(length);
1326-
if (aot_check->IsRedundant(array_length)) {
1327-
aot_check->ReplaceUsesWith(aot_check->index()->definition());
1328-
aot_check->RemoveFromGraph();
1329-
}
1330-
continue;
1331-
}
1332-
// Must be a speculative check bound.
1333-
CheckArrayBoundInstr* check = bounds_checks_[i]->AsCheckArrayBound();
1334-
ASSERT(check != nullptr);
1335-
RangeBoundary array_length =
1336-
RangeBoundary::FromDefinition(check->length()->definition());
1337-
if (check->IsRedundant(array_length)) {
1315+
for (CheckBoundBase* check : bounds_checks_) {
1316+
if (check->IsRedundant()) {
13381317
check->ReplaceUsesWith(check->index()->definition());
13391318
check->RemoveFromGraph();
13401319
} else if (try_generalization) {
1341-
generalizer.TryGeneralize(check, array_length);
1320+
if (auto jit_check = check->AsCheckArrayBound()) {
1321+
generalizer.TryGeneralize(jit_check);
1322+
}
13421323
}
13431324
}
13441325
}
@@ -2931,33 +2912,31 @@ void IntConverterInstr::InferRange(RangeAnalysis* analysis, Range* range) {
29312912
}
29322913
}
29332914

2934-
bool CheckArrayBoundInstr::IsRedundant(const RangeBoundary& length) {
2935-
Range* index_range = index()->definition()->range();
2936-
2915+
static bool IsRedundantBasedOnRangeInformation(Value* index, Value* length) {
29372916
// Range of the index is unknown can't decide if the check is redundant.
2938-
if (index_range == NULL) {
2939-
if (!(index()->BindsToConstant() &&
2940-
compiler::target::IsSmi(index()->BoundConstant()))) {
2917+
Range* index_range = index->definition()->range();
2918+
if (index_range == nullptr) {
2919+
if (!(index->BindsToConstant() &&
2920+
compiler::target::IsSmi(index->BoundConstant()))) {
29412921
return false;
29422922
}
2943-
29442923
Range range;
2945-
index()->definition()->InferRange(NULL, &range);
2924+
index->definition()->InferRange(nullptr, &range);
29462925
ASSERT(!Range::IsUnknown(&range));
2947-
index()->definition()->set_range(range);
2948-
index_range = index()->definition()->range();
2926+
index->definition()->set_range(range);
2927+
index_range = index->definition()->range();
29492928
}
29502929

29512930
// Range of the index is not positive. Check can't be redundant.
29522931
if (Range::ConstantMinSmi(index_range).ConstantValue() < 0) {
29532932
return false;
29542933
}
29552934

2956-
RangeBoundary max = RangeBoundary::FromDefinition(index()->definition());
2957-
2935+
RangeBoundary max = RangeBoundary::FromDefinition(index->definition());
29582936
RangeBoundary max_upper = max.UpperBound();
2959-
RangeBoundary length_lower = length.LowerBound();
2960-
2937+
RangeBoundary array_length =
2938+
RangeBoundary::FromDefinition(length->definition());
2939+
RangeBoundary length_lower = array_length.LowerBound();
29612940
if (max_upper.OverflowedSmi() || length_lower.OverflowedSmi()) {
29622941
return false;
29632942
}
@@ -2968,7 +2947,7 @@ bool CheckArrayBoundInstr::IsRedundant(const RangeBoundary& length) {
29682947
}
29692948

29702949
RangeBoundary canonical_length =
2971-
CanonicalizeBoundary(length, RangeBoundary::PositiveInfinity());
2950+
CanonicalizeBoundary(array_length, RangeBoundary::PositiveInfinity());
29722951
if (canonical_length.OverflowedSmi()) {
29732952
return false;
29742953
}
@@ -3000,30 +2979,41 @@ static bool IsSameBound(const RangeBoundary& a, InductionVar* b) {
30002979
return false;
30012980
}
30022981

3003-
bool GenericCheckBoundInstr::IsRedundant(const RangeBoundary& length) {
3004-
// In loop, with index as induction?
3005-
LoopInfo* loop = GetBlock()->loop_info();
3006-
if (loop == nullptr) {
3007-
return false;
3008-
}
3009-
InductionVar* induc = loop->LookupInduction(index()->definition());
3010-
if (induc == nullptr) {
3011-
return false;
2982+
bool CheckBoundBase::IsRedundant() {
2983+
// First, try to prove redundancy with the results of range analysis.
2984+
if (IsRedundantBasedOnRangeInformation(index(), length())) {
2985+
return true;
2986+
} else if (previous() == nullptr) {
2987+
return false; // check is not in flow graph yet
30122988
}
2989+
// Next, try to prove redundancy with the results of induction analysis.
30132990
// Under 64-bit wrap-around arithmetic, it is always safe to remove the
3014-
// bounds check from the following, if initial >= 0 and the corresponding
2991+
// bounds check from the following loop, if initial >= 0 and the loop
30152992
// exit branch dominates the bounds check:
2993+
//
30162994
// for (int i = initial; i < length; i++)
30172995
// .... a[i] ....
3018-
int64_t stride = 0;
3019-
int64_t initial = 0;
3020-
if (InductionVar::IsLinear(induc, &stride) &&
3021-
InductionVar::IsConstant(induc->initial(), &initial)) {
3022-
if (stride == 1 && initial >= 0) {
3023-
for (auto bound : induc->bounds()) {
3024-
if (IsSameBound(length, bound.limit_) &&
3025-
this->IsDominatedBy(bound.branch_)) {
3026-
return true;
2996+
//
2997+
LoopInfo* loop = GetBlock()->loop_info();
2998+
if (loop != nullptr) {
2999+
InductionVar* induc = loop->LookupInduction(index()->definition());
3000+
if (induc != nullptr) {
3001+
int64_t stride = 0;
3002+
int64_t initial = 0;
3003+
if (InductionVar::IsLinear(induc, &stride) &&
3004+
InductionVar::IsConstant(induc->initial(), &initial)) {
3005+
if (stride == 1 && initial >= 0) {
3006+
// Deeply trace back the range of the array length.
3007+
RangeBoundary deep_length = RangeBoundary::FromDefinition(
3008+
length()
3009+
->definition()
3010+
->OriginalDefinitionIgnoreBoxingAndConstraints());
3011+
for (auto bound : induc->bounds()) {
3012+
if (IsSameBound(deep_length, bound.limit_) &&
3013+
this->IsDominatedBy(bound.branch_)) {
3014+
return true;
3015+
}
3016+
}
30273017
}
30283018
}
30293019
}

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

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -622,7 +622,7 @@ class RangeAnalysis : public ValueObject {
622622
GrowableArray<ShiftIntegerOpInstr*> shift_int64_ops_;
623623

624624
// All CheckArrayBound/GenericCheckBound instructions.
625-
GrowableArray<Instruction*> bounds_checks_;
625+
GrowableArray<CheckBoundBase*> bounds_checks_;
626626

627627
// All Constraints inserted during InsertConstraints phase. They are treated
628628
// as smi values.

‎runtime/vm/compiler/compiler_sources.gni‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -169,6 +169,7 @@ compiler_sources_tests = [
169169
"assembler/assembler_test.cc",
170170
"assembler/assembler_x64_test.cc",
171171
"assembler/disassembler_test.cc",
172+
"backend/bce_test.cc",
172173
"backend/il_test.cc",
173174
"backend/il_test_helper.h",
174175
"backend/il_test_helper.cc",

0 commit comments

Comments
 (0)