blob: 9a70102f5c8505f7f0e23b4c111a0e41a97ddb51 [file] [log] [blame]
// 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.
#error "AOT runtime should not use compiler sources (including header files)"
#include <utility>
#include "vm/allocation.h"
#include "vm/compiler/backend/il.h"
namespace dart {
// Information on an induction variable in a particular loop.
// Invariant:
// offset + mult * def
// Linear:
// initial + next * i, for invariant initial and next,
// and a "normalized" loop index i
// Wrap-around:
// initial then next, for invariant initial and any next
// Periodic:
// alternate initial and next, for invariant initial and next
class InductionVar : public ZoneAllocated {
enum Kind {
// Strict (exclusive) upper or lower bound on unit stride linear induction:
// i < U (i++)
// i > L (i--)
struct Bound {
Bound(BranchInstr* b, InductionVar* l) : branch_(b), limit_(l) {}
BranchInstr* branch_;
InductionVar* limit_;
// Constructor for an invariant.
InductionVar(int64_t offset, int64_t mult, Definition* def)
: kind_(kInvariant), offset_(offset), mult_(mult), def_(def), bounds_() {
ASSERT(mult_ == 0 || def != nullptr);
// Constructor for a constant.
explicit InductionVar(int64_t offset) : InductionVar(offset, 0, nullptr) {}
// Constructor for an induction.
InductionVar(Kind kind, InductionVar* initial, InductionVar* next)
: kind_(kind), initial_(initial), next_(next), bounds_() {
switch (kind) {
case kLinear:
case kPeriodic:
case kWrapAround:
ASSERT(next != nullptr);
// Returns true if the other induction is structually equivalent.
bool IsEqual(const InductionVar* other) const {
ASSERT(other != nullptr);
if (kind_ == other->kind_) {
switch (kind_) {
case kInvariant:
return offset_ == other->offset_ && mult_ == other->mult_ &&
(mult_ == 0 || def_ == other->def_);
case kLinear:
case kWrapAround:
case kPeriodic:
return initial_->IsEqual(other->initial_) &&
return false;
// Returns true if a fixed difference between this and the other induction
// can be computed. Sets the output parameter diff on success.
bool CanComputeDifferenceWith(const InductionVar* other, int64_t* diff) const;
// Returns true if this induction in the given loop can be bounded as
// min <= this <= max by using bounds of more outer loops. On success
// the output parameters min and max are set, which are always loop
// invariant expressions inside the given loop.
bool CanComputeBounds(LoopInfo* loop,
Instruction* pos,
InductionVar** min,
InductionVar** max);
// Getters.
Kind kind() const { return kind_; }
int64_t offset() const {
ASSERT(kind_ == kInvariant);
return offset_;
int64_t mult() const {
ASSERT(kind_ == kInvariant);
return mult_;
Definition* def() const {
ASSERT(kind_ == kInvariant);
return def_;
InductionVar* initial() const {
ASSERT(kind_ != kInvariant);
return initial_;
InductionVar* next() const {
ASSERT(kind_ != kInvariant);
return next_;
const GrowableArray<Bound>& bounds() { return bounds_; }
// For debugging.
void PrintTo(BaseTextBuffer* f) const;
const char* ToCString() const;
// Returns true if x is invariant.
static bool IsInvariant(const InductionVar* x) {
return x != nullptr && x->kind_ == kInvariant;
// Returns true if x is a constant (and invariant).
static bool IsConstant(const InductionVar* x) {
return x != nullptr && x->kind_ == kInvariant && x->mult_ == 0;
// Returns true if x is a constant. Sets the value.
static bool IsConstant(const InductionVar* x, int64_t* c) {
if (IsConstant(x)) {
*c = x->offset_;
return true;
return false;
// Returns true if x is linear.
static bool IsLinear(const InductionVar* x) {
return x != nullptr && x->kind_ == kLinear;
// Returns true if x is linear with constant stride. Sets the stride.
static bool IsLinear(const InductionVar* x, int64_t* s) {
if (IsLinear(x)) {
return IsConstant(x->next_, s);
return false;
// Returns true if x is wrap-around.
static bool IsWrapAround(const InductionVar* x) {
return x != nullptr && x->kind_ == kWrapAround;
// Returns true if x is periodic.
static bool IsPeriodic(const InductionVar* x) {
return x != nullptr && x->kind_ == kPeriodic;
// Returns true if x is any induction.
static bool IsInduction(const InductionVar* x) {
return x != nullptr && x->kind_ != kInvariant;
friend class InductionVarAnalysis;
// Induction classification.
const Kind kind_;
union {
struct {
int64_t offset_;
int64_t mult_;
Definition* def_;
struct {
InductionVar* initial_;
InductionVar* next_;
bool CanComputeBoundsImpl(LoopInfo* loop,
Instruction* pos,
InductionVar** min,
InductionVar** max);
// Bounds on induction.
GrowableArray<Bound> bounds_;
// Information on a "natural loop" in the flow graph.
class LoopInfo : public ZoneAllocated {
LoopInfo(intptr_t id, BlockEntryInstr* header, BitVector* blocks);
// Merges given blocks to this loop.
void AddBlocks(BitVector* blocks);
// Adds back edge to this loop.
void AddBackEdge(BlockEntryInstr* block);
// Returns true if given block is backedge of this loop.
bool IsBackEdge(BlockEntryInstr* block) const;
// Returns true if given block is alway taken in this loop.
bool IsAlwaysTaken(BlockEntryInstr* block) const;
// Returns true if given definition is a header phi for this loop.
bool IsHeaderPhi(Definition* def) const;
// Returns true if this loop is nested inside given loop.
bool IsIn(LoopInfo* loop) const;
// Returns true if this loop contains given block.
bool Contains(BlockEntryInstr* block) const;
// Returns the nesting depth of this loop.
intptr_t NestingDepth() const;
// Resets induction.
void ResetInduction();
// Assigns induction to a definition.
void AddInduction(Definition* def, InductionVar* induc);
// Looks up induction.
InductionVar* LookupInduction(Definition* def) const;
// Tests if index stays in [0,length) range in this loop at given position.
bool IsInRange(Instruction* pos, Value* index, Value* length);
// Getters.
intptr_t id() const { return id_; }
BlockEntryInstr* header() const { return header_; }
BitVector* blocks() const { return blocks_; }
const GrowableArray<BlockEntryInstr*>& back_edges() { return back_edges_; }
ConstraintInstr* limit() const { return limit_; }
InductionVar* control() const { return control_; }
LoopInfo* outer() const { return outer_; }
LoopInfo* inner() const { return inner_; }
LoopInfo* next() const { return next_; }
// For debugging.
void PrintTo(BaseTextBuffer* f) const;
const char* ToCString() const;
friend class InductionVar;
friend class InductionVarAnalysis;
friend class LoopHierarchy;
// Mapping from definition to induction.
typedef RawPointerKeyValueTrait<Definition, InductionVar*> InductionKV;
// Mapping from induction to mapping from instruction to induction pair.
class MemoVal : public ZoneAllocated {
typedef RawPointerKeyValueTrait<Instruction,
std::pair<InductionVar*, InductionVar*>>
MemoVal() : memo_() {}
DirectChainedHashMap<PosKV> memo_;
typedef RawPointerKeyValueTrait<InductionVar, MemoVal*> MemoKV;
// Unique id of loop. We use its index in the
// loop header array for this.
const intptr_t id_;
// Header of loop.
BlockEntryInstr* header_;
// Compact represention of every block in the loop,
// indexed by its "preorder_number".
BitVector* blocks_;
// Back edges of loop (usually one).
GrowableArray<BlockEntryInstr*> back_edges_;
// Map definition -> induction for this loop.
DirectChainedHashMap<InductionKV> induction_;
// A small, per-loop memoization cache, to avoid costly
// recomputations while traversing very deeply nested loops.
DirectChainedHashMap<MemoKV> memo_cache_;
// Constraint on a header phi.
// TODO(ajcbik): very specific to smi range analysis,
// should we really store it here?
ConstraintInstr* limit_;
// Control induction.
InductionVar* control_;
// Loop hierarchy.
LoopInfo* outer_;
LoopInfo* inner_;
LoopInfo* next_;
// Information on the loop hierarchy in the flow graph.
class LoopHierarchy : public ZoneAllocated {
LoopHierarchy(ZoneGrowableArray<BlockEntryInstr*>* headers,
const GrowableArray<BlockEntryInstr*>& preorder);
// Getters.
const ZoneGrowableArray<BlockEntryInstr*>& headers() const {
return *headers_;
LoopInfo* top() const { return top_; }
// Returns total number of loops in the hierarchy.
intptr_t num_loops() const { return headers_->length(); }
// Performs induction variable analysis on all loops.
void ComputeInduction() const;
void Build();
void Print(LoopInfo* loop) const;
ZoneGrowableArray<BlockEntryInstr*>* headers_;
const GrowableArray<BlockEntryInstr*>& preorder_;
LoopInfo* top_;
} // namespace dart