[vm/compiler] Express control dependence as data dependence.
Rationale:
This provides a more robust way of expressing control
dependences between bounds checks and their uses, while
still allowing for CSE and LICM where possible.
This also fixes the original bug that started this
whole redesign: invalid LICM of checkbound.
Note:
Deals with bounds check, null check still TBD.
Mini design doc:
runtime/docs/compiler/data_dep_for_control_dep.md
https://github.com/dart-lang/sdk/issues/35139
https://github.com/dart-lang/sdk/issues/34684
https://github.com/dart-lang/sdk/issues/30633
Change-Id: Icfbd3ca60662e37046e48b95be7f81d05d94af88
Reviewed-on: https://dart-review.googlesource.com/c/85470
Commit-Queue: Aart Bik <ajcbik@google.com>
Reviewed-by: Alexander Markov <alexmarkov@google.com>
Reviewed-by: Vyacheslav Egorov <vegorov@google.com>
diff --git a/runtime/docs/compiler/data_dep_for_control_dep.md b/runtime/docs/compiler/data_dep_for_control_dep.md
new file mode 100644
index 0000000..8d228f6
--- /dev/null
+++ b/runtime/docs/compiler/data_dep_for_control_dep.md
@@ -0,0 +1,95 @@
+## Dart Mini Design Doc
+
+### Using Data Dependence to Preserve Control Dependence
+
+## Introduction
+
+The [DartFuzzer](http://go/dartfuzz) found [bug 34684](https://github.com/dart-lang/sdk/issues/34684) with the current LICM implementation. We need a fix urgently, since this bug may break user code, emerges for pretty much every nightly fuzz test run (making investigating new fuzz test divergences cumbersome; most of the time, it is a "same as"), and blocks moving towards more shards per nightly fuzz test run (the Q4 objective is 100 shards with 8 isolates each). Fixing the LICM bug, however, requires a bit more redesign in the way _control dependence_ is preserved in our IR.
+
+## The Problem
+
+The bug itself consists of an issue with applying LICM to an array bound check with loop invariant values. In its simplest form, LICM should not be applied to the bounds check that belongs to `l[j]` below since the loop condition (for a situation `k <= 0`) could logically protect OOB exceptions for particular values of `n` (for example, calling `foo(2,0)` should not throw).
+
+```
+void foo(int n, int k) {
+ var l = new List<int>(1);
+ var j = n - 1;
+ for (var i = 0; i < k; i++) {
+ l[j] = 10;
+ }
+}
+```
+Hosting the seemingly loop invariant bounds check out of the loop would break the control dependence between the loop condition and potentially move an OOB exception into the always-taken path.
+
+An obvious fix would simply disable hoisting `CheckBound` constructs of out loops, thereby respecting the control dependence between condition and check. However, this exposes another omission in our IR with respect to control dependence. Leaving `CheckBound` in place would not prevent hoisting the IndexLoad that follows, as illustrated below.
+
+```
+ ←-----------------+
+for loop |
+ Checkbound (length, index) | <- pinned in the loop
+ IndexLoad (base, index) ---+
+```
+In this case, this problem is caused by the fact that the control dependence from `CheckBound` to `IndexLoad` is not made explicit. Trending on the same path would require us to disable hoisting such instructions as well….
+
+At first glance, it may seem that a `Redefinition` could help here, as in:
+
+```
+for loop
+ v0 = get array
+ v1 = get length of v0
+ v2 = get index
+ CheckBound:id(v1, v2)
+ v3 <- Redefinition(v2)
+ IndexLoad(v0, v3)
+```
+This would indeed keep the index load instruction inside the loop, thereby relying on not-too-well-documented assumptions on unmovable redefinitions and the now explicit data dependence on `v3`. However, this approach would be too prohibitive, since cases that would allow for hoisting or eliminating `CheckBound` from the IR would not break the newly introduced chain on v3 (nothing in the IR expresses the relation between the `Redefinition` and the `CheckBound`).
+
+Alternatively, we could introduce control dependence as an explicit, but orthogonal order in our compiler. However, this would require introducing a new data structure to our IR as well as inspecting all code to ensure that this new order is indeed respected. The next section introduces a simpler solution.
+
+## Proposed Solution
+
+The proposed solution is making the control dependence between any check and all its uses explicit with a data dependence, as shown below.
+
+```
+ v3 <- CheckBound:id(v1, v2) // returns the index value v2 in v3
+ IndexLoad(v0, v3)
+```
+
+The semantics of the new node is that the returned value (`v3`) is a safe index (viz. checked values `v2`) into any load that uses that value. Any optimization that hoists or removes the `CheckBound` automatically exposes the opportunity for further optimization of the load by hoisting or breaking the dependence on `v3`. Common subexpression elimination can also be applied to equal-valued `CheckBound` nodes.
+
+For completeness, the same approach will be taken for null checks.
+
+The construct
+
+```
+ CheckNull:id(v2)
+ v100 <- LoadField(v2, …)
+```
+will be replaced by
+
+```
+ v3 = CheckNull:id(v2) // returns the reference value v2 in v3
+ v100 <- LoadField(v3, …)
+```
+Here, the value `v3` denotes a safe, null-checked reference of `v2`.
+
+The explicit data dependence ensures that all passes and transformations automatically preserve the required order, without the need to make adjustments anywhere else. In contrast, introducing an explicit control dependence as a new concept in our compiler would require a careful inspection of all code to make sure the new dependence is respected. A drawback of the new "indirection" through the check is that it may break some optimizations and simplifications that inspect the inputs directly. Although cumbersome, since it also involves looking at a lot of code, this is easily remedied by "looking under the hood" of checks (as is done for redefinitions). Missed opportunities for optimizations are preferable over missed correctness.
+
+The proposed solution will have _no impact_ on the register allocator or any of our backends, since the new data dependence will be removed in the `FinalizeGraph` pass, similar to what is already done now for redefinitions in `RemoveRedefinitions()`, except that this method will only redirect the inputs across checks, but obviously not remove the checks themselves. Nothing that runs after the register allocator should move code around too freely, an assumption that is already made in our current implementation with respect to redefinitions.
+
+This approach was used successfully in [the ART optimization compiler](https://cs.corp.google.com/android/art/compiler/optimizing/nodes.h). Here, check-based control dependence was made explicit with data dependence. All passes and transformations were aware that data dependence should always be satisfied (inter- and intra-basic block), whereas all optimizations that crossed basic blocks were aware of _implicit_ control dependence (e.g. using dominance relation). In combination with the actual LICM fix, the proposed solution will result in a previously proven robust framework for null and bounds checks.
+
+## IR Nodes
+
+Our IR currently has the following "check" instructions. Although potentially others could benefit form this new scheme too, the first CL will focus on the ones marked below only. As the implementation progresses, we may introduce some "object-orientedness" for check instructions that return their safe value.
+
+```
+CheckEitherNonSmiInstr
+CheckClassInstr
+CheckSmiInstr
+CheckNullInstr // returns safe non-null reference
+CheckClassIdInstr
+CheckArrayBoundInstr // returns safe non-OOBE index
+GenericCheckBoundInstr // returns safe non-OOBE index
+CheckConditionInstr
+
diff --git a/runtime/vm/compiler/aot/aot_call_specializer.cc b/runtime/vm/compiler/aot/aot_call_specializer.cc
index 571be51..fba0ee4 100644
--- a/runtime/vm/compiler/aot/aot_call_specializer.cc
+++ b/runtime/vm/compiler/aot/aot_call_specializer.cc
@@ -1196,25 +1196,6 @@
return true;
}
-void AotCallSpecializer::ReplaceArrayBoundChecks(FlowGraph* flow_graph) {
- Zone* zone = Thread::Current()->zone();
-
- for (BlockIterator block_it = flow_graph->reverse_postorder_iterator();
- !block_it.Done(); block_it.Advance()) {
- for (ForwardInstructionIterator it(block_it.Current()); !it.Done();
- it.Advance()) {
- if (CheckArrayBoundInstr* check = it.Current()->AsCheckArrayBound()) {
- GenericCheckBoundInstr* new_check = new (zone) GenericCheckBoundInstr(
- new (zone) Value(check->length()->definition()),
- new (zone) Value(check->index()->definition()), check->deopt_id());
- flow_graph->InsertBefore(check, new_check, check->env(),
- FlowGraph::kEffect);
- it.RemoveCurrentFromGraph();
- }
- }
- }
-}
-
#endif // DART_PRECOMPILER
} // namespace dart
diff --git a/runtime/vm/compiler/aot/aot_call_specializer.h b/runtime/vm/compiler/aot/aot_call_specializer.h
index a18b78c..404f2ba 100644
--- a/runtime/vm/compiler/aot/aot_call_specializer.h
+++ b/runtime/vm/compiler/aot/aot_call_specializer.h
@@ -20,11 +20,6 @@
virtual ~AotCallSpecializer() {}
- // TODO(dartbug.com/30633) these method has nothing to do with
- // specialization of calls. They are here for historical reasons.
- // Find a better place for them.
- static void ReplaceArrayBoundChecks(FlowGraph* flow_graph);
-
virtual void VisitInstanceCall(InstanceCallInstr* instr);
virtual void VisitStaticCall(StaticCallInstr* instr);
virtual void VisitPolymorphicInstanceCall(
diff --git a/runtime/vm/compiler/backend/constant_propagator.cc b/runtime/vm/compiler/backend/constant_propagator.cc
index 9342167..8716c0d 100644
--- a/runtime/vm/compiler/backend/constant_propagator.cc
+++ b/runtime/vm/compiler/backend/constant_propagator.cc
@@ -269,14 +269,9 @@
void ConstantPropagator::VisitCheckNull(CheckNullInstr* instr) {}
-void ConstantPropagator::VisitGenericCheckBound(GenericCheckBoundInstr* instr) {
-}
-
void ConstantPropagator::VisitCheckEitherNonSmi(CheckEitherNonSmiInstr* instr) {
}
-void ConstantPropagator::VisitCheckArrayBound(CheckArrayBoundInstr* instr) {}
-
void ConstantPropagator::VisitDeoptimize(DeoptimizeInstr* instr) {
// TODO(vegorov) remove all code after DeoptimizeInstr as dead.
}
@@ -337,6 +332,20 @@
}
}
+void ConstantPropagator::VisitCheckArrayBound(CheckArrayBoundInstr* instr) {
+ // Don't propagate constants through check, since it would eliminate
+ // the data dependence between the bound check and the load/store.
+ // Graph finalization will expose the constant eventually.
+ SetValue(instr, non_constant_);
+}
+
+void ConstantPropagator::VisitGenericCheckBound(GenericCheckBoundInstr* instr) {
+ // Don't propagate constants through check, since it would eliminate
+ // the data dependence between the bound check and the load/store.
+ // Graph finalization will expose the constant eventually.
+ SetValue(instr, non_constant_);
+}
+
void ConstantPropagator::VisitParameter(ParameterInstr* instr) {
SetValue(instr, non_constant_);
}
diff --git a/runtime/vm/compiler/backend/flow_graph.cc b/runtime/vm/compiler/backend/flow_graph.cc
index 3ac3092..b5d2201 100644
--- a/runtime/vm/compiler/backend/flow_graph.cc
+++ b/runtime/vm/compiler/backend/flow_graph.cc
@@ -544,6 +544,17 @@
CheckClassInstr(new (zone()) Value(to_check), deopt_id, cids, token_pos);
}
+Definition* FlowGraph::CreateCheckBound(Definition* length,
+ Definition* index,
+ intptr_t deopt_id) {
+ Value* val1 = new (zone()) Value(length);
+ Value* val2 = new (zone()) Value(index);
+ if (FLAG_precompiled_mode) {
+ return new (zone()) GenericCheckBoundInstr(val1, val2, deopt_id);
+ }
+ return new (zone()) CheckArrayBoundInstr(val1, val2, deopt_id);
+}
+
void FlowGraph::AddExactnessGuard(InstanceCallInstr* call,
intptr_t receiver_cid) {
const Class& cls = Class::Handle(
@@ -1554,21 +1565,30 @@
return redef;
}
-void FlowGraph::RemoveRedefinitions() {
- // Remove redefinition instructions inserted to inhibit hoisting.
+void FlowGraph::RemoveRedefinitions(bool keep_checks) {
+ // Remove redefinition and check instructions that were inserted
+ // to make a control dependence explicit with a data dependence,
+ // for example, to inhibit hoisting.
for (BlockIterator block_it = reverse_postorder_iterator(); !block_it.Done();
block_it.Advance()) {
thread()->CheckForSafepoint();
for (ForwardInstructionIterator instr_it(block_it.Current());
!instr_it.Done(); instr_it.Advance()) {
- RedefinitionInstr* redefinition = instr_it.Current()->AsRedefinition();
- if (redefinition != NULL) {
- Definition* original;
- do {
- original = redefinition->value()->definition();
- } while (original->IsRedefinition());
- redefinition->ReplaceUsesWith(original);
+ Instruction* instruction = instr_it.Current();
+ if (instruction->IsRedefinition()) {
+ RedefinitionInstr* redef = instruction->AsRedefinition();
+ redef->ReplaceUsesWith(redef->value()->definition());
instr_it.RemoveCurrentFromGraph();
+ } else if (keep_checks) {
+ continue;
+ } else if (instruction->IsCheckArrayBound()) {
+ CheckArrayBoundInstr* check = instruction->AsCheckArrayBound();
+ check->ReplaceUsesWith(check->index()->definition());
+ check->ClearSSATempIndex();
+ } else if (instruction->IsGenericCheckBound()) {
+ GenericCheckBoundInstr* check = instruction->AsGenericCheckBound();
+ check->ReplaceUsesWith(check->index()->definition());
+ check->ClearSSATempIndex();
}
}
}
diff --git a/runtime/vm/compiler/backend/flow_graph.h b/runtime/vm/compiler/backend/flow_graph.h
index 330bcf3..854aa81 100644
--- a/runtime/vm/compiler/backend/flow_graph.h
+++ b/runtime/vm/compiler/backend/flow_graph.h
@@ -180,6 +180,10 @@
intptr_t deopt_id,
TokenPosition token_pos);
+ Definition* CreateCheckBound(Definition* length,
+ Definition* index,
+ intptr_t deopt_id);
+
void AddExactnessGuard(InstanceCallInstr* call, intptr_t receiver_cid);
intptr_t current_ssa_temp_index() const { return current_ssa_temp_index_; }
@@ -266,7 +270,7 @@
CompileType compile_type);
// Remove the redefinition instructions inserted to inhibit code motion.
- void RemoveRedefinitions();
+ void RemoveRedefinitions(bool keep_checks = false);
// Copy deoptimization target from one instruction to another if we still
// have to keep deoptimization environment at gotos for LICM purposes.
diff --git a/runtime/vm/compiler/backend/il.cc b/runtime/vm/compiler/backend/il.cc
index b8a44ec..9864b2f 100644
--- a/runtime/vm/compiler/backend/il.cc
+++ b/runtime/vm/compiler/backend/il.cc
@@ -463,11 +463,16 @@
Definition* Definition::OriginalDefinition() {
Definition* defn = this;
- while (defn->IsRedefinition() || defn->IsAssertAssignable()) {
+ while (defn->IsRedefinition() || defn->IsAssertAssignable() ||
+ defn->IsCheckArrayBound() || defn->IsGenericCheckBound()) {
if (defn->IsRedefinition()) {
defn = defn->AsRedefinition()->value()->definition();
- } else {
+ } else if (defn->IsAssertAssignable()) {
defn = defn->AsAssertAssignable()->value()->definition();
+ } else if (defn->IsCheckArrayBound()) {
+ defn = defn->AsCheckArrayBound()->index()->definition();
+ } else {
+ defn = defn->AsGenericCheckBound()->index()->definition();
}
}
return defn;
@@ -4798,9 +4803,9 @@
return LoadFieldInstr::IsFixedLengthArrayCid(cid);
}
-Instruction* CheckArrayBoundInstr::Canonicalize(FlowGraph* flow_graph) {
+Definition* CheckArrayBoundInstr::Canonicalize(FlowGraph* flow_graph) {
return IsRedundant(RangeBoundary::FromDefinition(length()->definition()))
- ? NULL
+ ? index()->definition()
: this;
}
diff --git a/runtime/vm/compiler/backend/il.h b/runtime/vm/compiler/backend/il.h
index cc806de..9d4fc4e 100644
--- a/runtime/vm/compiler/backend/il.h
+++ b/runtime/vm/compiler/backend/il.h
@@ -7205,10 +7205,15 @@
DISALLOW_COPY_AND_ASSIGN(CheckClassIdInstr);
};
-class CheckArrayBoundInstr : public TemplateInstruction<2, NoThrow, Pure> {
+// Performs an array bounds check, where
+// safe_index := CheckArrayBound(length, index)
+// returns the "safe" index when
+// 0 <= index < length
+// or otherwise deoptimizes (viz. speculative).
+class CheckArrayBoundInstr : public TemplateDefinition<2, NoThrow, Pure> {
public:
CheckArrayBoundInstr(Value* length, Value* index, intptr_t deopt_id)
- : TemplateInstruction(deopt_id),
+ : TemplateDefinition(deopt_id),
generalized_(false),
licm_hoisted_(false) {
SetInputAt(kLengthPos, length);
@@ -7226,7 +7231,7 @@
void mark_generalized() { generalized_ = true; }
- virtual Instruction* Canonicalize(FlowGraph* flow_graph);
+ virtual Definition* Canonicalize(FlowGraph* flow_graph);
// Returns the length offset for array and string types.
static intptr_t LengthOffsetFor(intptr_t class_id);
@@ -7247,10 +7252,15 @@
DISALLOW_COPY_AND_ASSIGN(CheckArrayBoundInstr);
};
-class GenericCheckBoundInstr : public TemplateInstruction<2, Throws, NoCSE> {
+// Performs an array bounds check, where
+// safe_index := CheckArrayBound(length, index)
+// returns the "safe" index when
+// 0 <= index < length
+// or otherwise throws an out-of-bounds exception (viz. non-speculative).
+class GenericCheckBoundInstr : public TemplateDefinition<2, Throws, NoCSE> {
public:
GenericCheckBoundInstr(Value* length, Value* index, intptr_t deopt_id)
- : TemplateInstruction(deopt_id) {
+ : TemplateDefinition(deopt_id) {
SetInputAt(kLengthPos, length);
SetInputAt(kIndexPos, index);
}
diff --git a/runtime/vm/compiler/backend/inliner.cc b/runtime/vm/compiler/backend/inliner.cc
index 61a6a51..6f82314 100644
--- a/runtime/vm/compiler/backend/inliner.cc
+++ b/runtime/vm/compiler/backend/inliner.cc
@@ -2357,25 +2357,16 @@
Instruction* call,
intptr_t array_cid,
Definition** array,
- Definition* index,
- Instruction** cursor,
- bool can_speculate) {
+ Definition** index,
+ Instruction** cursor) {
// Insert array length load and bounds check.
LoadFieldInstr* length = new (Z) LoadFieldInstr(
new (Z) Value(*array), Slot::GetLengthFieldForArrayCid(array_cid),
call->token_pos());
*cursor = flow_graph->AppendTo(*cursor, length, NULL, FlowGraph::kValue);
-
- Instruction* bounds_check = NULL;
- if (can_speculate) {
- bounds_check = new (Z) CheckArrayBoundInstr(
- new (Z) Value(length), new (Z) Value(index), call->deopt_id());
- } else {
- bounds_check = new (Z) GenericCheckBoundInstr(
- new (Z) Value(length), new (Z) Value(index), call->deopt_id());
- }
- *cursor = flow_graph->AppendTo(*cursor, bounds_check, call->env(),
- FlowGraph::kEffect);
+ *index = flow_graph->CreateCheckBound(length, *index, call->deopt_id());
+ *cursor =
+ flow_graph->AppendTo(*cursor, *index, call->env(), FlowGraph::kValue);
if (array_cid == kGrowableObjectArrayCid) {
// Insert data elements load.
@@ -2401,8 +2392,7 @@
Definition* receiver,
GraphEntryInstr* graph_entry,
FunctionEntryInstr** entry,
- Instruction** last,
- bool can_speculate) {
+ Instruction** last) {
intptr_t array_cid = MethodRecognizer::MethodKindToReceiverCid(kind);
Definition* array = receiver;
@@ -2413,8 +2403,8 @@
(*entry)->InheritDeoptTarget(Z, call);
Instruction* cursor = *entry;
- array_cid = PrepareInlineIndexedOp(flow_graph, call, array_cid, &array, index,
- &cursor, can_speculate);
+ array_cid = PrepareInlineIndexedOp(flow_graph, call, array_cid, &array,
+ &index, &cursor);
intptr_t deopt_id = DeoptId::kNone;
if ((array_cid == kTypedDataInt32ArrayCid) ||
@@ -2539,8 +2529,8 @@
}
}
- array_cid = PrepareInlineIndexedOp(flow_graph, call, array_cid, &array, index,
- &cursor, /* can_speculate= */ true);
+ array_cid = PrepareInlineIndexedOp(flow_graph, call, array_cid, &array,
+ &index, &cursor);
// Check if store barrier is needed. Byte arrays don't need a store barrier.
StoreBarrierType needs_store_barrier =
@@ -2714,7 +2704,7 @@
intptr_t array_cid,
intptr_t view_cid,
Definition* array,
- Definition* byte_index,
+ Definition** byte_index,
Instruction** cursor) {
ASSERT(array_cid != kDynamicCid);
@@ -2746,19 +2736,19 @@
}
// Check adjusted_length > 0.
+ // TODO(ajcbik): this is a synthetic check that cannot
+ // be directly linked to a use, is that a sign of wrong use?
ConstantInstr* zero = flow_graph->GetConstant(Smi::Handle(Z, Smi::New(0)));
- *cursor = flow_graph->AppendTo(
- *cursor,
- new (Z) CheckArrayBoundInstr(new (Z) Value(adjusted_length),
- new (Z) Value(zero), call->deopt_id()),
- call->env(), FlowGraph::kEffect);
+ Definition* check =
+ flow_graph->CreateCheckBound(adjusted_length, zero, call->deopt_id());
+ *cursor =
+ flow_graph->AppendTo(*cursor, check, call->env(), FlowGraph::kValue);
// Check 0 <= byte_index < adjusted_length.
- *cursor = flow_graph->AppendTo(
- *cursor,
- new (Z) CheckArrayBoundInstr(new (Z) Value(adjusted_length),
- new (Z) Value(byte_index), call->deopt_id()),
- call->env(), FlowGraph::kEffect);
+ *byte_index = flow_graph->CreateCheckBound(adjusted_length, *byte_index,
+ call->deopt_id());
+ *cursor = flow_graph->AppendTo(*cursor, *byte_index, call->env(),
+ FlowGraph::kValue);
}
// Emits preparatory code for a typed getter/setter.
@@ -2866,7 +2856,7 @@
!flow_graph->isolate()->can_use_strong_mode_types();
if (needs_bounds_check) {
PrepareInlineTypedArrayBoundsCheck(flow_graph, call, array_cid, view_cid,
- array, index, &cursor);
+ array, &index, &cursor);
}
// Generates a template for the load, either a dynamic conditional
@@ -2965,7 +2955,7 @@
!flow_graph->isolate()->can_use_strong_mode_types();
if (needs_bounds_check) {
PrepareInlineTypedArrayBoundsCheck(flow_graph, call, array_cid, view_cid,
- array, index, &cursor);
+ array, &index, &cursor);
}
// Prepare additional checks.
@@ -3136,11 +3126,8 @@
cursor = flow_graph->AppendTo(cursor, length, NULL, FlowGraph::kValue);
// Bounds check.
- cursor = flow_graph->AppendTo(
- cursor,
- new (Z) CheckArrayBoundInstr(new (Z) Value(length), new (Z) Value(index),
- call->deopt_id()),
- call->env(), FlowGraph::kEffect);
+ index = flow_graph->CreateCheckBound(length, index, call->deopt_id());
+ cursor = flow_graph->AppendTo(cursor, index, call->env(), FlowGraph::kValue);
// For external strings: Load backing store.
if (cid == kExternalOneByteStringCid) {
@@ -3201,10 +3188,11 @@
if (cid == kDynamicCid) {
ASSERT(call->IsStaticCall());
return false;
+ } else if ((cid != kOneByteStringCid) && (cid != kTwoByteStringCid) &&
+ (cid != kExternalOneByteStringCid) &&
+ (cid != kExternalTwoByteStringCid)) {
+ return false;
}
- ASSERT((cid == kOneByteStringCid) || (cid == kTwoByteStringCid) ||
- (cid == kExternalOneByteStringCid) ||
- (cid == kExternalTwoByteStringCid));
Definition* str = receiver;
Definition* index = call->ArgumentAt(1);
@@ -3578,7 +3566,6 @@
const bool can_speculate = policy->IsAllowedForInlining(call->deopt_id());
const MethodRecognizer::Kind kind = MethodRecognizer::RecognizeKind(target);
-
switch (kind) {
// Recognized [] operators.
case MethodRecognizer::kImmutableArrayGetIndexed:
@@ -3592,35 +3579,35 @@
case MethodRecognizer::kInt16ArrayGetIndexed:
case MethodRecognizer::kUint16ArrayGetIndexed:
return InlineGetIndexed(flow_graph, kind, call, receiver, graph_entry,
- entry, last, can_speculate);
+ entry, last);
case MethodRecognizer::kFloat32ArrayGetIndexed:
case MethodRecognizer::kFloat64ArrayGetIndexed:
if (!CanUnboxDouble()) {
return false;
}
return InlineGetIndexed(flow_graph, kind, call, receiver, graph_entry,
- entry, last, can_speculate);
+ entry, last);
case MethodRecognizer::kFloat32x4ArrayGetIndexed:
case MethodRecognizer::kFloat64x2ArrayGetIndexed:
if (!ShouldInlineSimd()) {
return false;
}
return InlineGetIndexed(flow_graph, kind, call, receiver, graph_entry,
- entry, last, can_speculate);
+ entry, last);
case MethodRecognizer::kInt32ArrayGetIndexed:
case MethodRecognizer::kUint32ArrayGetIndexed:
if (!CanUnboxInt32()) {
return false;
}
return InlineGetIndexed(flow_graph, kind, call, receiver, graph_entry,
- entry, last, can_speculate);
+ entry, last);
case MethodRecognizer::kInt64ArrayGetIndexed:
case MethodRecognizer::kUint64ArrayGetIndexed:
if (!ShouldInlineInt64ArrayOps()) {
return false;
}
return InlineGetIndexed(flow_graph, kind, call, receiver, graph_entry,
- entry, last, can_speculate);
+ entry, last);
case MethodRecognizer::kClassIDgetID:
return InlineLoadClassId(flow_graph, call, graph_entry, entry, last);
default:
diff --git a/runtime/vm/compiler/backend/loops.cc b/runtime/vm/compiler/backend/loops.cc
index 707864e..168babf 100644
--- a/runtime/vm/compiler/backend/loops.cc
+++ b/runtime/vm/compiler/backend/loops.cc
@@ -242,13 +242,17 @@
}
} else if (def->IsPhi()) {
induc = TransferPhi(loop, def);
- } else if (def->IsRedefinition() || def->IsBox() || def->IsUnbox() ||
- def->IsConstraint()) {
- induc = Lookup(loop, def->InputAt(0)->definition()); // pass-through
} else if (def->IsBinaryIntegerOp()) {
induc = TransferBinary(loop, def);
} else if (def->IsUnaryIntegerOp()) {
induc = TransferUnary(loop, def);
+ } else if (def->IsConstraint() || def->IsBox() || def->IsUnbox()) {
+ induc = Lookup(loop, def->InputAt(0)->definition()); // pass-through
+ } else {
+ Definition* orig = def->OriginalDefinition();
+ if (orig != def) {
+ induc = Lookup(loop, orig); // pass-through
+ }
}
// Successfully classified?
if (induc != nullptr) {
@@ -281,14 +285,19 @@
InductionVar* update = nullptr;
if (def->IsPhi()) {
update = SolvePhi(loop, def);
- } else if (def->IsRedefinition() || def->IsBox() || def->IsUnbox()) {
- update = LookupCycle(def->InputAt(0)->definition()); // pass-through
- } else if (def->IsConstraint()) {
- update = SolveConstraint(loop, def, init);
} else if (def->IsBinaryIntegerOp()) {
update = SolveBinary(loop, def, init);
} else if (def->IsUnaryIntegerOp()) {
update = SolveUnary(loop, def, init);
+ } else if (def->IsConstraint()) {
+ update = SolveConstraint(loop, def, init);
+ } else if (def->IsBox() || def->IsUnbox()) {
+ update = LookupCycle(def->InputAt(0)->definition()); // pass-through
+ } else {
+ Definition* orig = def->OriginalDefinition();
+ if (orig != def) {
+ update = LookupCycle(orig); // pass-through
+ }
}
// Continue cycle?
if (update == nullptr) {
@@ -425,7 +434,7 @@
return Add(c, y);
}
}
- break;
+ return nullptr;
case Token::kSUB:
if (InductionVar::IsInvariant(x)) {
InductionVar* c = LookupCycle(def->InputAt(1)->definition());
@@ -449,11 +458,10 @@
return Sub(c, y);
}
}
- break;
+ return nullptr;
default:
- break;
+ return nullptr;
}
- return nullptr;
}
InductionVar* InductionVarAnalysis::SolveUnary(LoopInfo* loop,
diff --git a/runtime/vm/compiler/backend/range_analysis.cc b/runtime/vm/compiler/backend/range_analysis.cc
index d94536a..554d61b 100644
--- a/runtime/vm/compiler/backend/range_analysis.cc
+++ b/runtime/vm/compiler/backend/range_analysis.cc
@@ -106,7 +106,8 @@
shift_int64_ops_.Add(defn->AsShiftIntegerOp());
}
}
- } else if (current->IsCheckArrayBound()) {
+ }
+ if (current->IsCheckArrayBound()) {
bounds_checks_.Add(current->AsCheckArrayBound());
}
}
@@ -839,6 +840,9 @@
// certain preconditions. Start by emitting this preconditions.
scheduler_.Start();
+ // AOT should only see non-deopting GenericCheckBound.
+ ASSERT(!FLAG_precompiled_mode);
+
ConstantInstr* max_smi =
flow_graph_->GetConstant(Smi::Handle(Smi::New(Smi::kMaxValue)));
for (intptr_t i = 0; i < non_positive_symbols.length(); i++) {
@@ -888,6 +892,7 @@
if (binary_op != NULL) {
binary_op->set_can_overflow(false);
}
+ check->ReplaceUsesWith(check->index()->definition());
check->RemoveFromGraph();
}
@@ -1342,6 +1347,7 @@
RangeBoundary array_length =
RangeBoundary::FromDefinition(check->length()->definition());
if (check->IsRedundant(array_length)) {
+ check->ReplaceUsesWith(check->index()->definition());
check->RemoveFromGraph();
} else if (try_generalization) {
generalizer.TryGeneralize(check, array_length);
diff --git a/runtime/vm/compiler/backend/redundancy_elimination.cc b/runtime/vm/compiler/backend/redundancy_elimination.cc
index f3d89f5..c507504 100644
--- a/runtime/vm/compiler/backend/redundancy_elimination.cc
+++ b/runtime/vm/compiler/backend/redundancy_elimination.cc
@@ -1256,6 +1256,7 @@
} else if (current->IsCheckEitherNonSmi()) {
current->AsCheckEitherNonSmi()->set_licm_hoisted(true);
} else if (current->IsCheckArrayBound()) {
+ ASSERT(!FLAG_precompiled_mode); // AOT uses non-deopting GenericCheckBound
current->AsCheckArrayBound()->set_licm_hoisted(true);
} else if (current->IsTestCids()) {
current->AsTestCids()->set_licm_hoisted(true);
diff --git a/runtime/vm/compiler/compiler_pass.cc b/runtime/vm/compiler/compiler_pass.cc
index daeb0fe..e72f1a3 100644
--- a/runtime/vm/compiler/compiler_pass.cc
+++ b/runtime/vm/compiler/compiler_pass.cc
@@ -262,11 +262,6 @@
INVOKE_PASS(EliminateStackOverflowChecks);
INVOKE_PASS(Canonicalize);
INVOKE_PASS(AllocationSinking_DetachMaterializations);
-#if defined(DART_PRECOMPILER)
- if (mode == kAOT) {
- INVOKE_PASS(ReplaceArrayBoundChecksForAOT);
- }
-#endif
INVOKE_PASS(WriteBarrierElimination);
INVOKE_PASS(FinalizeGraph);
INVOKE_PASS(AllocateRegisters);
@@ -346,7 +341,7 @@
DEBUG_ASSERT(flow_graph->VerifyRedefinitions());
LICM licm(flow_graph);
licm.Optimize();
- flow_graph->RemoveRedefinitions();
+ flow_graph->RemoveRedefinitions(/*keep_checks*/ true);
});
COMPILER_PASS(DSE, { DeadStoreElimination::Optimize(flow_graph); });
@@ -446,11 +441,6 @@
flow_graph->RemoveRedefinitions();
});
-#if defined(DART_PRECOMPILER)
-COMPILER_PASS(ReplaceArrayBoundChecksForAOT,
- { AotCallSpecializer::ReplaceArrayBoundChecks(flow_graph); })
-#endif
-
} // namespace dart
#endif // DART_PRECOMPILED_RUNTIME
diff --git a/runtime/vm/compiler/compiler_pass.h b/runtime/vm/compiler/compiler_pass.h
index 92c2bfc..128343a 100644
--- a/runtime/vm/compiler/compiler_pass.h
+++ b/runtime/vm/compiler/compiler_pass.h
@@ -36,7 +36,6 @@
V(OptimizeBranches) \
V(RangeAnalysis) \
V(ReorderBlocks) \
- V(ReplaceArrayBoundChecksForAOT) \
V(SelectRepresentations) \
V(SetOuterInliningId) \
V(TryCatchOptimization) \
diff --git a/runtime/vm/compiler/intrinsifier.cc b/runtime/vm/compiler/intrinsifier.cc
index 4a22001..1d85246 100644
--- a/runtime/vm/compiler/intrinsifier.cc
+++ b/runtime/vm/compiler/intrinsifier.cc
@@ -248,6 +248,9 @@
printer.PrintBlocks();
}
+ // Prepare for register allocation (cf. FinalizeGraph).
+ graph->RemoveRedefinitions();
+
// Ensure loop hierarchy has been computed.
GrowableArray<BitVector*> dominance_frontier;
graph->ComputeDominators(&dominance_frontier);
@@ -477,14 +480,17 @@
Environment* fall_through_env_;
};
-static void PrepareIndexedOp(BlockBuilder* builder,
- Definition* array,
- Definition* index,
- const Slot& length_field) {
+static Definition* PrepareIndexedOp(FlowGraph* flow_graph,
+ BlockBuilder* builder,
+ Definition* array,
+ Definition* index,
+ const Slot& length_field) {
Definition* length = builder->AddDefinition(new LoadFieldInstr(
new Value(array), length_field, TokenPosition::kNoSource));
- builder->AddInstruction(new CheckArrayBoundInstr(
- new Value(length), new Value(index), DeoptId::kNone));
+ Definition* safe_index =
+ flow_graph->CreateCheckBound(length, index, DeoptId::kNone);
+ builder->AddDefinition(safe_index);
+ return safe_index;
}
static bool IntrinsifyArrayGetIndexed(FlowGraph* flow_graph,
@@ -496,8 +502,8 @@
Definition* index = builder.AddParameter(1);
Definition* array = builder.AddParameter(2);
- PrepareIndexedOp(&builder, array, index,
- Slot::GetLengthFieldForArrayCid(array_cid));
+ index = PrepareIndexedOp(flow_graph, &builder, array, index,
+ Slot::GetLengthFieldForArrayCid(array_cid));
if (RawObject::IsExternalTypedDataClassId(array_cid)) {
array = builder.AddDefinition(new LoadUntaggedInstr(
@@ -574,8 +580,8 @@
Definition* index = builder.AddParameter(2);
Definition* array = builder.AddParameter(3);
- PrepareIndexedOp(&builder, array, index,
- Slot::GetLengthFieldForArrayCid(array_cid));
+ index = PrepareIndexedOp(flow_graph, &builder, array, index,
+ Slot::GetLengthFieldForArrayCid(array_cid));
// Value check/conversion.
switch (array_cid) {
@@ -769,7 +775,9 @@
Definition* index = builder.AddParameter(1);
Definition* str = builder.AddParameter(2);
- PrepareIndexedOp(&builder, str, index, Slot::String_length());
+
+ index =
+ PrepareIndexedOp(flow_graph, &builder, str, index, Slot::String_length());
// For external strings: Load external data.
if (cid == kExternalOneByteStringCid) {
@@ -950,8 +958,8 @@
Definition* index = builder.AddParameter(1);
Definition* growable_array = builder.AddParameter(2);
- PrepareIndexedOp(&builder, growable_array, index,
- Slot::GrowableObjectArray_length());
+ index = PrepareIndexedOp(flow_graph, &builder, growable_array, index,
+ Slot::GrowableObjectArray_length());
Definition* backing_store = builder.AddDefinition(
new LoadFieldInstr(new Value(growable_array),
@@ -981,7 +989,8 @@
Definition* index = builder.AddParameter(2);
Definition* array = builder.AddParameter(3);
- PrepareIndexedOp(&builder, array, index, Slot::Array_length());
+ index = PrepareIndexedOp(flow_graph, &builder, array, index,
+ Slot::Array_length());
builder.AddInstruction(new StoreIndexedInstr(
new Value(array), new Value(index), new Value(value), kEmitStoreBarrier,
@@ -1011,7 +1020,8 @@
Definition* index = builder.AddParameter(2);
Definition* array = builder.AddParameter(3);
- PrepareIndexedOp(&builder, array, index, Slot::GrowableObjectArray_length());
+ index = PrepareIndexedOp(flow_graph, &builder, array, index,
+ Slot::GrowableObjectArray_length());
Definition* backing_store = builder.AddDefinition(new LoadFieldInstr(
new Value(array), Slot::GrowableObjectArray_data(), builder.TokenPos()));
diff --git a/tests/language_2/vm/regress_34684_test.dart b/tests/language_2/vm/regress_34684_test.dart
new file mode 100644
index 0000000..626cb50
--- /dev/null
+++ b/tests/language_2/vm/regress_34684_test.dart
@@ -0,0 +1,81 @@
+// Copyright (c) 2018, 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.
+
+// No LICM on array bounds check (dartbug.com/34684).
+//
+// VMOptions=--deterministic --optimization_counter_threshold=10
+
+import "package:expect/expect.dart";
+
+List<int> foo(int n, int k) {
+ var l = new List<int>(1);
+ var j = n - 1;
+ for (var i = 0; i < k; i++) {
+ l[j] = 10; // do not hoist
+ }
+ return l;
+}
+
+int x = -1;
+
+List<int> bar(int n, int k) {
+ x = -1;
+ var l = new List<int>(n);
+ for (var i = 0; i < k; i++) {
+ x = i;
+ l[4] = 10; // do not hoist
+ }
+ return l;
+}
+
+void main() {
+ List<int> l;
+
+ for (int i = 0; i < 20; ++i) {
+ l = foo(1, 0);
+ Expect.equals(1, l.length);
+ Expect.equals(null, l[0]);
+
+ l = foo(2, 0);
+ Expect.equals(1, l.length);
+ Expect.equals(null, l[0]);
+
+ l = foo(i, 0);
+ Expect.equals(1, l.length);
+ Expect.equals(null, l[0]);
+
+ l = foo(1, 1);
+ Expect.equals(1, l.length);
+ Expect.equals(10, l[0]);
+
+ l = foo(1, i + 1);
+ Expect.equals(1, l.length);
+ Expect.equals(10, l[0]);
+
+ try {
+ l = foo(-i, 1);
+ } catch (_) {
+ l = null;
+ }
+ Expect.equals(null, l);
+
+ l = bar(5, 0);
+ Expect.equals(5, l.length);
+ Expect.equals(null, l[4]);
+ Expect.equals(-1, x);
+
+ l = bar(5, i + 1);
+ Expect.equals(5, l.length);
+ Expect.equals(10, l[4]);
+ Expect.equals(i, x);
+
+ try {
+ l = bar(1, i + 1);
+ } catch (_) {
+ l = null;
+ }
+ Expect.equals(null, l);
+ Expect.equals(0, x);
+ }
+}
