Skip to content
This repository was archived by the owner on Feb 25, 2025. It is now read-only.

Commit a10b0d8

Browse files
aartbikcommit-bot@chromium.org
aartbik
authored and
[email protected]
committed
[vm/compiler] LICM and CSE improvements
Several improvements (1) makes implicit control dependence of a null check explicit by means of data dependence (already done for bounds checks); also see the doc in runtime/docs/compiler/data_dep_for_control_dep.md (2) improves CSE properties of various IL nodes (3) allows LICM on invariant code that may-throw as long as the visible behavior is preserved dart-lang/sdk#35323 dart-lang/sdk#34684 Change-Id: Icb4520a649da38eddc3d7c85af21427d3c64d22e Reviewed-on: https://dart-review.googlesource.com/c/93822 Commit-Queue: Aart Bik <[email protected]> Reviewed-by: Martin Kustermann <[email protected]> Reviewed-by: Alexander Markov <[email protected]>
1 parent ff6f61c commit a10b0d8

File tree

10 files changed

+713
-53
lines changed

10 files changed

+713
-53
lines changed

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

Lines changed: 7 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -267,8 +267,6 @@ void ConstantPropagator::VisitCheckSmi(CheckSmiInstr* instr) {}
267267

268268
void ConstantPropagator::VisitTailCall(TailCallInstr* instr) {}
269269

270-
void ConstantPropagator::VisitCheckNull(CheckNullInstr* instr) {}
271-
272270
void ConstantPropagator::VisitCheckEitherNonSmi(CheckEitherNonSmiInstr* instr) {
273271
}
274272

@@ -354,6 +352,13 @@ void ConstantPropagator::VisitGenericCheckBound(GenericCheckBoundInstr* instr) {
354352
SetValue(instr, non_constant_);
355353
}
356354

355+
void ConstantPropagator::VisitCheckNull(CheckNullInstr* instr) {
356+
// Don't propagate constants through check, since it would eliminate
357+
// the data dependence between the null check and its use.
358+
// Graph finalization will expose the constant eventually.
359+
SetValue(instr, non_constant_);
360+
}
361+
357362
void ConstantPropagator::VisitParameter(ParameterInstr* instr) {
358363
SetValue(instr, non_constant_);
359364
}

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

Lines changed: 7 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -1561,7 +1561,7 @@ RedefinitionInstr* FlowGraph::EnsureRedefinition(Instruction* prev,
15611561
RedefinitionInstr* redef = new RedefinitionInstr(new Value(original));
15621562

15631563
// Don't set the constrained type when the type is None(), which denotes an
1564-
// unreachable value (e.g. using value null after an explicit null check).
1564+
// unreachable value (e.g. using value null after some form of null check).
15651565
if (!compile_type.IsNone()) {
15661566
redef->set_constrained_type(new CompileType(compile_type));
15671567
}
@@ -1581,20 +1581,20 @@ void FlowGraph::RemoveRedefinitions(bool keep_checks) {
15811581
for (ForwardInstructionIterator instr_it(block_it.Current());
15821582
!instr_it.Done(); instr_it.Advance()) {
15831583
Instruction* instruction = instr_it.Current();
1584-
if (instruction->IsRedefinition()) {
1585-
RedefinitionInstr* redef = instruction->AsRedefinition();
1584+
if (auto redef = instruction->AsRedefinition()) {
15861585
redef->ReplaceUsesWith(redef->value()->definition());
15871586
instr_it.RemoveCurrentFromGraph();
15881587
} else if (keep_checks) {
15891588
continue;
1590-
} else if (instruction->IsCheckArrayBound()) {
1591-
CheckArrayBoundInstr* check = instruction->AsCheckArrayBound();
1589+
} else if (auto check = instruction->AsCheckArrayBound()) {
15921590
check->ReplaceUsesWith(check->index()->definition());
15931591
check->ClearSSATempIndex();
1594-
} else if (instruction->IsGenericCheckBound()) {
1595-
GenericCheckBoundInstr* check = instruction->AsGenericCheckBound();
1592+
} else if (auto check = instruction->AsGenericCheckBound()) {
15961593
check->ReplaceUsesWith(check->index()->definition());
15971594
check->ClearSSATempIndex();
1595+
} else if (auto check = instruction->AsCheckNull()) {
1596+
check->ReplaceUsesWith(check->value()->definition());
1597+
check->ClearSSATempIndex();
15981598
}
15991599
}
16001600
}

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

Lines changed: 14 additions & 11 deletions
Original file line numberDiff line numberDiff line change
@@ -501,16 +501,19 @@ Object& Definition::constant_value() {
501501

502502
Definition* Definition::OriginalDefinition() {
503503
Definition* defn = this;
504-
while (defn->IsRedefinition() || defn->IsAssertAssignable() ||
505-
defn->IsCheckArrayBound() || defn->IsGenericCheckBound()) {
506-
if (defn->IsRedefinition()) {
507-
defn = defn->AsRedefinition()->value()->definition();
508-
} else if (defn->IsAssertAssignable()) {
509-
defn = defn->AsAssertAssignable()->value()->definition();
510-
} else if (defn->IsCheckArrayBound()) {
511-
defn = defn->AsCheckArrayBound()->index()->definition();
504+
while (true) {
505+
if (auto redefinition = defn->AsRedefinition()) {
506+
defn = redefinition->value()->definition();
507+
} else if (auto assert_assignable = defn->AsAssertAssignable()) {
508+
defn = assert_assignable->value()->definition();
509+
} else if (auto check_array_bound = defn->AsCheckArrayBound()) {
510+
defn = check_array_bound->index()->definition();
511+
} else if (auto check_bound = defn->AsGenericCheckBound()) {
512+
defn = check_bound->index()->definition();
513+
} else if (auto check_null = defn->AsCheckNull()) {
514+
defn = check_null->value()->definition();
512515
} else {
513-
defn = defn->AsGenericCheckBound()->index()->definition();
516+
break;
514517
}
515518
}
516519
return defn;
@@ -3455,8 +3458,8 @@ Instruction* CheckEitherNonSmiInstr::Canonicalize(FlowGraph* flow_graph) {
34553458
return this;
34563459
}
34573460

3458-
Instruction* CheckNullInstr::Canonicalize(FlowGraph* flow_graph) {
3459-
return (!value()->Type()->is_nullable()) ? NULL : this;
3461+
Definition* CheckNullInstr::Canonicalize(FlowGraph* flow_graph) {
3462+
return (!value()->Type()->is_nullable()) ? value()->definition() : this;
34603463
}
34613464

34623465
BoxInstr* BoxInstr::Create(Representation from, Value* value) {

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

Lines changed: 15 additions & 10 deletions
Original file line numberDiff line numberDiff line change
@@ -7156,13 +7156,13 @@ class CheckSmiInstr : public TemplateInstruction<1, NoThrow, Pure> {
71567156
// CheckNull instruction takes one input (`value`) and tests it for `null`.
71577157
// If `value` is `null`, then `NoSuchMethodError` is thrown. Otherwise,
71587158
// execution proceeds to the next instruction.
7159-
class CheckNullInstr : public TemplateInstruction<1, Throws, NoCSE> {
7159+
class CheckNullInstr : public TemplateDefinition<1, Throws, Pure> {
71607160
public:
71617161
CheckNullInstr(Value* value,
71627162
const String& function_name,
71637163
intptr_t deopt_id,
71647164
TokenPosition token_pos)
7165-
: TemplateInstruction(deopt_id),
7165+
: TemplateDefinition(deopt_id),
71667166
token_pos_(token_pos),
71677167
function_name_(function_name) {
71687168
ASSERT(function_name.IsNotTemporaryScopedHandle());
@@ -7179,13 +7179,14 @@ class CheckNullInstr : public TemplateInstruction<1, Throws, NoCSE> {
71797179

71807180
DECLARE_INSTRUCTION(CheckNull)
71817181

7182+
virtual CompileType ComputeType() const;
7183+
virtual bool RecomputeType();
7184+
71827185
// CheckNull can implicitly call Dart code (NoSuchMethodError constructor),
71837186
// so it can lazily deopt.
71847187
virtual bool ComputeCanDeoptimize() const { return true; }
71857188

7186-
virtual Instruction* Canonicalize(FlowGraph* flow_graph);
7187-
7188-
virtual bool HasUnknownSideEffects() const { return false; }
7189+
virtual Definition* Canonicalize(FlowGraph* flow_graph);
71897190

71907191
virtual bool AttributesEqual(Instruction* other) const { return true; }
71917192

@@ -7250,6 +7251,9 @@ class CheckArrayBoundInstr : public TemplateDefinition<2, NoThrow, Pure> {
72507251

72517252
DECLARE_INSTRUCTION(CheckArrayBound)
72527253

7254+
virtual CompileType ComputeType() const;
7255+
virtual bool RecomputeType();
7256+
72537257
virtual bool ComputeCanDeoptimize() const { return true; }
72547258

72557259
bool IsRedundant(const RangeBoundary& length);
@@ -7282,7 +7286,7 @@ class CheckArrayBoundInstr : public TemplateDefinition<2, NoThrow, Pure> {
72827286
// returns the "safe" index when
72837287
// 0 <= index < length
72847288
// or otherwise throws an out-of-bounds exception (viz. non-speculative).
7285-
class GenericCheckBoundInstr : public TemplateDefinition<2, Throws, NoCSE> {
7289+
class GenericCheckBoundInstr : public TemplateDefinition<2, Throws, Pure> {
72867290
public:
72877291
GenericCheckBoundInstr(Value* length, Value* index, intptr_t deopt_id)
72887292
: TemplateDefinition(deopt_id) {
@@ -7293,10 +7297,13 @@ class GenericCheckBoundInstr : public TemplateDefinition<2, Throws, NoCSE> {
72937297
Value* length() const { return inputs_[kLengthPos]; }
72947298
Value* index() const { return inputs_[kIndexPos]; }
72957299

7296-
virtual bool HasUnknownSideEffects() const { return false; }
7300+
virtual bool AttributesEqual(Instruction* other) const { return true; }
72977301

72987302
DECLARE_INSTRUCTION(GenericCheckBound)
72997303

7304+
virtual CompileType ComputeType() const;
7305+
virtual bool RecomputeType();
7306+
73007307
// GenericCheckBound can implicitly call Dart code (RangeError or
73017308
// ArgumentError constructor), so it can lazily deopt.
73027309
virtual bool ComputeCanDeoptimize() const { return true; }
@@ -7356,7 +7363,7 @@ class CheckConditionInstr : public Instruction {
73567363
DISALLOW_COPY_AND_ASSIGN(CheckConditionInstr);
73577364
};
73587365

7359-
class UnboxedIntConverterInstr : public TemplateDefinition<1, NoThrow> {
7366+
class UnboxedIntConverterInstr : public TemplateDefinition<1, NoThrow, Pure> {
73607367
public:
73617368
UnboxedIntConverterInstr(Representation from,
73627369
Representation to,
@@ -7393,8 +7400,6 @@ class UnboxedIntConverterInstr : public TemplateDefinition<1, NoThrow> {
73937400
return from();
73947401
}
73957402

7396-
virtual bool HasUnknownSideEffects() const { return false; }
7397-
73987403
virtual bool AttributesEqual(Instruction* other) const {
73997404
ASSERT(other->IsUnboxedIntConverter());
74007405
UnboxedIntConverterInstr* converter = other->AsUnboxedIntConverter();

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

Lines changed: 41 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -443,6 +443,10 @@ void InductionVarAnalysis::ClassifyControl(LoopInfo* loop) {
443443
// on the intended use of this information, clients should still test
444444
// dominance on the test and the initial value of the induction variable.
445445
x->bounds_.Add(InductionVar::Bound(branch, y));
446+
// Record control induction.
447+
if (branch == loop->header_->last_instruction()) {
448+
loop->control_ = x;
449+
}
446450
}
447451
}
448452

@@ -774,6 +778,7 @@ LoopInfo::LoopInfo(intptr_t id, BlockEntryInstr* header, BitVector* blocks)
774778
back_edges_(),
775779
induction_(),
776780
limit_(nullptr),
781+
control_(nullptr),
777782
outer_(nullptr),
778783
inner_(nullptr),
779784
next_(nullptr) {}
@@ -795,6 +800,42 @@ bool LoopInfo::IsBackEdge(BlockEntryInstr* block) const {
795800
return false;
796801
}
797802

803+
bool LoopInfo::IsAlwaysTaken(BlockEntryInstr* block) const {
804+
// The loop header is always executed when executing a loop (including
805+
// loop body of a do-while). Reject any other loop body block that is
806+
// not directly controlled by header.
807+
if (block == header_) {
808+
return true;
809+
} else if (block->PredecessorCount() != 1 ||
810+
block->PredecessorAt(0) != header_) {
811+
return false;
812+
}
813+
// If the loop has a control induction, make sure the condition is such
814+
// that the loop body is entered at least once from the header.
815+
if (control_ != nullptr) {
816+
InductionVar* limit = nullptr;
817+
for (auto bound : control_->bounds()) {
818+
if (bound.branch_ == header_->last_instruction()) {
819+
limit = bound.limit_;
820+
break;
821+
}
822+
}
823+
// Control iterates at least once?
824+
if (limit != nullptr) {
825+
int64_t stride = 0;
826+
int64_t begin = 0;
827+
int64_t end = 0;
828+
if (InductionVar::IsLinear(control_, &stride) &&
829+
InductionVar::IsConstant(control_->initial(), &begin) &&
830+
InductionVar::IsConstant(limit, &end) &&
831+
((stride == 1 && begin < end) || (stride == -1 && begin > end))) {
832+
return true;
833+
}
834+
}
835+
}
836+
return false;
837+
}
838+
798839
bool LoopInfo::IsHeaderPhi(Definition* def) const {
799840
return def != nullptr && def->IsPhi() && def->GetBlock() == header_ &&
800841
!def->AsPhi()->IsRedundant(); // phi(x,..,x) = x

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

Lines changed: 7 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -193,6 +193,9 @@ class LoopInfo : public ZoneAllocated {
193193
// Returns true if given block is backedge of this loop.
194194
bool IsBackEdge(BlockEntryInstr* block) const;
195195

196+
// Returns true if given block is alway taken in this loop.
197+
bool IsAlwaysTaken(BlockEntryInstr* block) const;
198+
196199
// Returns true if given definition is a header phi for this loop.
197200
bool IsHeaderPhi(Definition* def) const;
198201

@@ -220,6 +223,7 @@ class LoopInfo : public ZoneAllocated {
220223
BitVector* blocks() const { return blocks_; }
221224
const GrowableArray<BlockEntryInstr*>& back_edges() { return back_edges_; }
222225
ConstraintInstr* limit() const { return limit_; }
226+
InductionVar* control() const { return control_; }
223227
LoopInfo* outer() const { return outer_; }
224228
LoopInfo* inner() const { return inner_; }
225229
LoopInfo* next() const { return next_; }
@@ -255,6 +259,9 @@ class LoopInfo : public ZoneAllocated {
255259
// should we really store it here?
256260
ConstraintInstr* limit_;
257261

262+
// Control induction.
263+
InductionVar* control_;
264+
258265
// Loop hierarchy.
259266
LoopInfo* outer_;
260267
LoopInfo* inner_;

0 commit comments

Comments
 (0)