Revert "[vm/compiler] Express control dependence as data dependence."
This reverts commit 41f3d4326ee7fa7a075e96ab95f8f943a0cb1bcc.
Reason for revert: I hit +2 by accident when I wanted to submit do a dry run
Original change's description:
> [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>
TBR=vegorov@google.com,kustermann@google.com,rmacnak@google.com,alexmarkov@google.com,asiva@google.com,ajcbik@google.com
Change-Id: Id20699f957681c248851b37d545b330fd4972d7a
No-Presubmit: true
No-Tree-Checks: true
No-Try: true
Reviewed-on: https://dart-review.googlesource.com/c/85522
Reviewed-by: Aart Bik <ajcbik@google.com>
Commit-Queue: Aart Bik <ajcbik@google.com>
diff --git a/runtime/docs/compiler/data_dep_for_control_dep.md b/runtime/docs/compiler/data_dep_for_control_dep.md
deleted file mode 100644
index 8d228f6..0000000
--- a/runtime/docs/compiler/data_dep_for_control_dep.md
+++ /dev/null
@@ -1,95 +0,0 @@
-## 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 fba0ee4..571be51 100644
--- a/runtime/vm/compiler/aot/aot_call_specializer.cc
+++ b/runtime/vm/compiler/aot/aot_call_specializer.cc
@@ -1196,6 +1196,25 @@
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 404f2ba..a18b78c 100644
--- a/runtime/vm/compiler/aot/aot_call_specializer.h
+++ b/runtime/vm/compiler/aot/aot_call_specializer.h
@@ -20,6 +20,11 @@
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 8716c0d..9342167 100644
--- a/runtime/vm/compiler/backend/constant_propagator.cc
+++ b/runtime/vm/compiler/backend/constant_propagator.cc
@@ -269,9 +269,14 @@
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.
}
@@ -332,20 +337,6 @@
}
}
-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 b5d2201..3ac3092 100644
--- a/runtime/vm/compiler/backend/flow_graph.cc
+++ b/runtime/vm/compiler/backend/flow_graph.cc
@@ -544,17 +544,6 @@
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(
@@ -1565,30 +1554,21 @@
return redef;
}
-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.
+void FlowGraph::RemoveRedefinitions() {
+ // Remove redefinition instructions inserted 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()) {
- Instruction* instruction = instr_it.Current();
- if (instruction->IsRedefinition()) {
- RedefinitionInstr* redef = instruction->AsRedefinition();
- redef->ReplaceUsesWith(redef->value()->definition());
+ RedefinitionInstr* redefinition = instr_it.Current()->AsRedefinition();
+ if (redefinition != NULL) {
+ Definition* original;
+ do {
+ original = redefinition->value()->definition();
+ } while (original->IsRedefinition());
+ redefinition->ReplaceUsesWith(original);
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 854aa81..330bcf3 100644
--- a/runtime/vm/compiler/backend/flow_graph.h
+++ b/runtime/vm/compiler/backend/flow_graph.h
@@ -180,10 +180,6 @@
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_; }
@@ -270,7 +266,7 @@
CompileType compile_type);
// Remove the redefinition instructions inserted to inhibit code motion.
- void RemoveRedefinitions(bool keep_checks = false);
+ void RemoveRedefinitions();
// 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 9864b2f..b8a44ec 100644
--- a/runtime/vm/compiler/backend/il.cc
+++ b/runtime/vm/compiler/backend/il.cc
@@ -463,16 +463,11 @@
Definition* Definition::OriginalDefinition() {
Definition* defn = this;
- while (defn->IsRedefinition() || defn->IsAssertAssignable() ||
- defn->IsCheckArrayBound() || defn->IsGenericCheckBound()) {
+ while (defn->IsRedefinition() || defn->IsAssertAssignable()) {
if (defn->IsRedefinition()) {
defn = defn->AsRedefinition()->value()->definition();
- } else if (defn->IsAssertAssignable()) {
- defn = defn->AsAssertAssignable()->value()->definition();
- } else if (defn->IsCheckArrayBound()) {
- defn = defn->AsCheckArrayBound()->index()->definition();
} else {
- defn = defn->AsGenericCheckBound()->index()->definition();
+ defn = defn->AsAssertAssignable()->value()->definition();
}
}
return defn;
@@ -4803,9 +4798,9 @@
return LoadFieldInstr::IsFixedLengthArrayCid(cid);
}
-Definition* CheckArrayBoundInstr::Canonicalize(FlowGraph* flow_graph) {
+Instruction* CheckArrayBoundInstr::Canonicalize(FlowGraph* flow_graph) {
return IsRedundant(RangeBoundary::FromDefinition(length()->definition()))
- ? index()->definition()
+ ? NULL
: this;
}
diff --git a/runtime/vm/compiler/backend/il.h b/runtime/vm/compiler/backend/il.h
index 9d4fc4e..cc806de 100644
--- a/runtime/vm/compiler/backend/il.h
+++ b/runtime/vm/compiler/backend/il.h
@@ -7205,15 +7205,10 @@
DISALLOW_COPY_AND_ASSIGN(CheckClassIdInstr);
};
-// 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> {
+class CheckArrayBoundInstr : public TemplateInstruction<2, NoThrow, Pure> {
public:
CheckArrayBoundInstr(Value* length, Value* index, intptr_t deopt_id)
- : TemplateDefinition(deopt_id),
+ : TemplateInstruction(deopt_id),
generalized_(false),
licm_hoisted_(false) {
SetInputAt(kLengthPos, length);
@@ -7231,7 +7226,7 @@
void mark_generalized() { generalized_ = true; }
- virtual Definition* Canonicalize(FlowGraph* flow_graph);
+ virtual Instruction* Canonicalize(FlowGraph* flow_graph);
// Returns the length offset for array and string types.
static intptr_t LengthOffsetFor(intptr_t class_id);
@@ -7252,15 +7247,10 @@
DISALLOW_COPY_AND_ASSIGN(CheckArrayBoundInstr);
};
-// 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> {
+class GenericCheckBoundInstr : public TemplateInstruction<2, Throws, NoCSE> {
public:
GenericCheckBoundInstr(Value* length, Value* index, intptr_t deopt_id)
- : TemplateDefinition(deopt_id) {
+ : TemplateInstruction(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 6f82314..61a6a51 100644
--- a/runtime/vm/compiler/backend/inliner.cc
+++ b/runtime/vm/compiler/backend/inliner.cc
@@ -2357,16 +2357,25 @@
Instruction* call,
intptr_t array_cid,
Definition** array,
- Definition** index,
- Instruction** cursor) {
+ Definition* index,
+ Instruction** cursor,
+ bool can_speculate) {
// 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);
- *index = flow_graph->CreateCheckBound(length, *index, call->deopt_id());
- *cursor =
- flow_graph->AppendTo(*cursor, *index, call->env(), 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);
if (array_cid == kGrowableObjectArrayCid) {
// Insert data elements load.
@@ -2392,7 +2401,8 @@
Definition* receiver,
GraphEntryInstr* graph_entry,
FunctionEntryInstr** entry,
- Instruction** last) {
+ Instruction** last,
+ bool can_speculate) {
intptr_t array_cid = MethodRecognizer::MethodKindToReceiverCid(kind);
Definition* array = receiver;
@@ -2403,8 +2413,8 @@
(*entry)->InheritDeoptTarget(Z, call);
Instruction* cursor = *entry;
- array_cid = PrepareInlineIndexedOp(flow_graph, call, array_cid, &array,
- &index, &cursor);
+ array_cid = PrepareInlineIndexedOp(flow_graph, call, array_cid, &array, index,
+ &cursor, can_speculate);
intptr_t deopt_id = DeoptId::kNone;
if ((array_cid == kTypedDataInt32ArrayCid) ||
@@ -2529,8 +2539,8 @@
}
}
- array_cid = PrepareInlineIndexedOp(flow_graph, call, array_cid, &array,
- &index, &cursor);
+ array_cid = PrepareInlineIndexedOp(flow_graph, call, array_cid, &array, index,
+ &cursor, /* can_speculate= */ true);
// Check if store barrier is needed. Byte arrays don't need a store barrier.
StoreBarrierType needs_store_barrier =
@@ -2704,7 +2714,7 @@
intptr_t array_cid,
intptr_t view_cid,
Definition* array,
- Definition** byte_index,
+ Definition* byte_index,
Instruction** cursor) {
ASSERT(array_cid != kDynamicCid);
@@ -2736,19 +2746,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)));
- Definition* check =
- flow_graph->CreateCheckBound(adjusted_length, zero, call->deopt_id());
- *cursor =
- flow_graph->AppendTo(*cursor, check, call->env(), FlowGraph::kValue);
+ *cursor = flow_graph->AppendTo(
+ *cursor,
+ new (Z) CheckArrayBoundInstr(new (Z) Value(adjusted_length),
+ new (Z) Value(zero), call->deopt_id()),
+ call->env(), FlowGraph::kEffect);
// Check 0 <= byte_index < adjusted_length.
- *byte_index = flow_graph->CreateCheckBound(adjusted_length, *byte_index,
- call->deopt_id());
- *cursor = flow_graph->AppendTo(*cursor, *byte_index, call->env(),
- FlowGraph::kValue);
+ *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);
}
// Emits preparatory code for a typed getter/setter.
@@ -2856,7 +2866,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
@@ -2955,7 +2965,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.
@@ -3126,8 +3136,11 @@
cursor = flow_graph->AppendTo(cursor, length, NULL, FlowGraph::kValue);
// Bounds check.
- index = flow_graph->CreateCheckBound(length, index, call->deopt_id());
- cursor = flow_graph->AppendTo(cursor, index, call->env(), FlowGraph::kValue);
+ cursor = flow_graph->AppendTo(
+ cursor,
+ new (Z) CheckArrayBoundInstr(new (Z) Value(length), new (Z) Value(index),
+ call->deopt_id()),
+ call->env(), FlowGraph::kEffect);
// For external strings: Load backing store.
if (cid == kExternalOneByteStringCid) {
@@ -3188,11 +3201,10 @@
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);
@@ -3566,6 +3578,7 @@
const bool can_speculate = policy->IsAllowedForInlining(call->deopt_id());
const MethodRecognizer::Kind kind = MethodRecognizer::RecognizeKind(target);
+
switch (kind) {
// Recognized [] operators.
case MethodRecognizer::kImmutableArrayGetIndexed:
@@ -3579,35 +3592,35 @@
case MethodRecognizer::kInt16ArrayGetIndexed:
case MethodRecognizer::kUint16ArrayGetIndexed:
return InlineGetIndexed(flow_graph, kind, call, receiver, graph_entry,
- entry, last);
+ entry, last, can_speculate);
case MethodRecognizer::kFloat32ArrayGetIndexed:
case MethodRecognizer::kFloat64ArrayGetIndexed:
if (!CanUnboxDouble()) {
return false;
}
return InlineGetIndexed(flow_graph, kind, call, receiver, graph_entry,
- entry, last);
+ entry, last, can_speculate);
case MethodRecognizer::kFloat32x4ArrayGetIndexed:
case MethodRecognizer::kFloat64x2ArrayGetIndexed:
if (!ShouldInlineSimd()) {
return false;
}
return InlineGetIndexed(flow_graph, kind, call, receiver, graph_entry,
- entry, last);
+ entry, last, can_speculate);
case MethodRecognizer::kInt32ArrayGetIndexed:
case MethodRecognizer::kUint32ArrayGetIndexed:
if (!CanUnboxInt32()) {
return false;
}
return InlineGetIndexed(flow_graph, kind, call, receiver, graph_entry,
- entry, last);
+ entry, last, can_speculate);
case MethodRecognizer::kInt64ArrayGetIndexed:
case MethodRecognizer::kUint64ArrayGetIndexed:
if (!ShouldInlineInt64ArrayOps()) {
return false;
}
return InlineGetIndexed(flow_graph, kind, call, receiver, graph_entry,
- entry, last);
+ entry, last, can_speculate);
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 168babf..707864e 100644
--- a/runtime/vm/compiler/backend/loops.cc
+++ b/runtime/vm/compiler/backend/loops.cc
@@ -242,17 +242,13 @@
}
} 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) {
@@ -285,19 +281,14 @@
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) {
@@ -434,7 +425,7 @@
return Add(c, y);
}
}
- return nullptr;
+ break;
case Token::kSUB:
if (InductionVar::IsInvariant(x)) {
InductionVar* c = LookupCycle(def->InputAt(1)->definition());
@@ -458,10 +449,11 @@
return Sub(c, y);
}
}
- return nullptr;
+ break;
default:
- return nullptr;
+ break;
}
+ 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 554d61b..d94536a 100644
--- a/runtime/vm/compiler/backend/range_analysis.cc
+++ b/runtime/vm/compiler/backend/range_analysis.cc
@@ -106,8 +106,7 @@
shift_int64_ops_.Add(defn->AsShiftIntegerOp());
}
}
- }
- if (current->IsCheckArrayBound()) {
+ } else if (current->IsCheckArrayBound()) {
bounds_checks_.Add(current->AsCheckArrayBound());
}
}
@@ -840,9 +839,6 @@
// 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++) {
@@ -892,7 +888,6 @@
if (binary_op != NULL) {
binary_op->set_can_overflow(false);
}
- check->ReplaceUsesWith(check->index()->definition());
check->RemoveFromGraph();
}
@@ -1347,7 +1342,6 @@
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 c507504..f3d89f5 100644
--- a/runtime/vm/compiler/backend/redundancy_elimination.cc
+++ b/runtime/vm/compiler/backend/redundancy_elimination.cc
@@ -1256,7 +1256,6 @@
} 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 e72f1a3..daeb0fe 100644
--- a/runtime/vm/compiler/compiler_pass.cc
+++ b/runtime/vm/compiler/compiler_pass.cc
@@ -262,6 +262,11 @@
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);
@@ -341,7 +346,7 @@
DEBUG_ASSERT(flow_graph->VerifyRedefinitions());
LICM licm(flow_graph);
licm.Optimize();
- flow_graph->RemoveRedefinitions(/*keep_checks*/ true);
+ flow_graph->RemoveRedefinitions();
});
COMPILER_PASS(DSE, { DeadStoreElimination::Optimize(flow_graph); });
@@ -441,6 +446,11 @@
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 128343a..92c2bfc 100644
--- a/runtime/vm/compiler/compiler_pass.h
+++ b/runtime/vm/compiler/compiler_pass.h
@@ -36,6 +36,7 @@
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 1d85246..4a22001 100644
--- a/runtime/vm/compiler/intrinsifier.cc
+++ b/runtime/vm/compiler/intrinsifier.cc
@@ -248,9 +248,6 @@
printer.PrintBlocks();
}
- // Prepare for register allocation (cf. FinalizeGraph).
- graph->RemoveRedefinitions();
-
// Ensure loop hierarchy has been computed.
GrowableArray<BitVector*> dominance_frontier;
graph->ComputeDominators(&dominance_frontier);
@@ -480,17 +477,14 @@
Environment* fall_through_env_;
};
-static Definition* PrepareIndexedOp(FlowGraph* flow_graph,
- BlockBuilder* builder,
- Definition* array,
- Definition* index,
- const Slot& length_field) {
+static void PrepareIndexedOp(BlockBuilder* builder,
+ Definition* array,
+ Definition* index,
+ const Slot& length_field) {
Definition* length = builder->AddDefinition(new LoadFieldInstr(
new Value(array), length_field, TokenPosition::kNoSource));
- Definition* safe_index =
- flow_graph->CreateCheckBound(length, index, DeoptId::kNone);
- builder->AddDefinition(safe_index);
- return safe_index;
+ builder->AddInstruction(new CheckArrayBoundInstr(
+ new Value(length), new Value(index), DeoptId::kNone));
}
static bool IntrinsifyArrayGetIndexed(FlowGraph* flow_graph,
@@ -502,8 +496,8 @@
Definition* index = builder.AddParameter(1);
Definition* array = builder.AddParameter(2);
- index = PrepareIndexedOp(flow_graph, &builder, array, index,
- Slot::GetLengthFieldForArrayCid(array_cid));
+ PrepareIndexedOp(&builder, array, index,
+ Slot::GetLengthFieldForArrayCid(array_cid));
if (RawObject::IsExternalTypedDataClassId(array_cid)) {
array = builder.AddDefinition(new LoadUntaggedInstr(
@@ -580,8 +574,8 @@
Definition* index = builder.AddParameter(2);
Definition* array = builder.AddParameter(3);
- index = PrepareIndexedOp(flow_graph, &builder, array, index,
- Slot::GetLengthFieldForArrayCid(array_cid));
+ PrepareIndexedOp(&builder, array, index,
+ Slot::GetLengthFieldForArrayCid(array_cid));
// Value check/conversion.
switch (array_cid) {
@@ -775,9 +769,7 @@
Definition* index = builder.AddParameter(1);
Definition* str = builder.AddParameter(2);
-
- index =
- PrepareIndexedOp(flow_graph, &builder, str, index, Slot::String_length());
+ PrepareIndexedOp(&builder, str, index, Slot::String_length());
// For external strings: Load external data.
if (cid == kExternalOneByteStringCid) {
@@ -958,8 +950,8 @@
Definition* index = builder.AddParameter(1);
Definition* growable_array = builder.AddParameter(2);
- index = PrepareIndexedOp(flow_graph, &builder, growable_array, index,
- Slot::GrowableObjectArray_length());
+ PrepareIndexedOp(&builder, growable_array, index,
+ Slot::GrowableObjectArray_length());
Definition* backing_store = builder.AddDefinition(
new LoadFieldInstr(new Value(growable_array),
@@ -989,8 +981,7 @@
Definition* index = builder.AddParameter(2);
Definition* array = builder.AddParameter(3);
- index = PrepareIndexedOp(flow_graph, &builder, array, index,
- Slot::Array_length());
+ PrepareIndexedOp(&builder, array, index, Slot::Array_length());
builder.AddInstruction(new StoreIndexedInstr(
new Value(array), new Value(index), new Value(value), kEmitStoreBarrier,
@@ -1020,8 +1011,7 @@
Definition* index = builder.AddParameter(2);
Definition* array = builder.AddParameter(3);
- index = PrepareIndexedOp(flow_graph, &builder, array, index,
- Slot::GrowableObjectArray_length());
+ PrepareIndexedOp(&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
deleted file mode 100644
index 626cb50..0000000
--- a/tests/language_2/vm/regress_34684_test.dart
+++ /dev/null
@@ -1,81 +0,0 @@
-// 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);
- }
-}
