dart::LoopInfo Class Reference

#include <loops.h>

Inheritance diagram for dart::LoopInfo:

Public Member Functions
	LoopInfo (intptr_t id, BlockEntryInstr *header, BitVector *blocks)
void	AddBlocks (BitVector *blocks)
void	AddBackEdge (BlockEntryInstr *block)
bool	IsBackEdge (BlockEntryInstr *block) const
bool	IsAlwaysTaken (BlockEntryInstr *block) const
bool	IsHeaderPhi (Definition *def) const
bool	IsIn (LoopInfo *loop) const
bool	Contains (BlockEntryInstr *block) const
intptr_t	NestingDepth () const
void	ResetInduction ()
void	AddInduction (Definition *def, InductionVar *induc)
InductionVar *	LookupInduction (Definition *def) const
bool	IsInRange (Instruction *pos, Value *index, Value *length)
intptr_t	id () const
BlockEntryInstr *	header () const
BitVector *	blocks () const
const GrowableArray< BlockEntryInstr * > &	back_edges ()
ConstraintInstr *	limit () const
InductionVar *	control () const
LoopInfo *	outer () const
LoopInfo *	inner () const
LoopInfo *	next () const
void	PrintTo (BaseTextBuffer *f) const
const char *	ToCString () const
Public Member Functions inherited from dart::ZoneAllocated
	ZoneAllocated ()
void *	operator new (size_t size)
void *	operator new (size_t size, Zone *zone)
void	operator delete (void *pointer)

Friends
class	InductionVar
class	InductionVarAnalysis
class	LoopHierarchy

Detailed Description

Definition at line 210 of file loops.h.

Constructor & Destructor Documentation

LoopInfo()

dart::LoopInfo::LoopInfo	(	intptr_t	id,
		BlockEntryInstr *	header,
		BitVector *	blocks
	)

Definition at line 980 of file loops.cc.

    : id_(id),
      header_(header),
      blocks_(blocks),
      back_edges_(),
      induction_(),
      memo_cache_(),
      limit_(nullptr),
      control_(nullptr),
      outer_(nullptr),
      inner_(nullptr),
      next_(nullptr) {}

Member Function Documentation

AddBackEdge()

void dart::LoopInfo::AddBackEdge

(

BlockEntryInstr *

block

)

Definition at line 997 of file loops.cc.

                                                 {
  back_edges_.Add(block);
}

AddBlocks()

void dart::LoopInfo::AddBlocks

(

BitVector *

blocks

)

Definition at line 993 of file loops.cc.

                                          {
  blocks_->AddAll(blocks);
}

AddInduction()

void dart::LoopInfo::AddInduction	(	Definition *	def,
		InductionVar *	induc
	)

Definition at line 1075 of file loops.cc.

                                                                {
  ASSERT(def != nullptr);
  ASSERT(induc != nullptr);
  induction_.Insert(InductionKV::Pair(def, induc));
}

back_edges()

const GrowableArray< BlockEntryInstr * > & dart::LoopInfo::back_edges ( )

inline

Definition at line 254 of file loops.h.

{ return back_edges_; }

blocks()

BitVector * dart::LoopInfo::blocks ( ) const

inline

Definition at line 253 of file loops.h.

{ return blocks_; }

Contains()

bool dart::LoopInfo::Contains

(

BlockEntryInstr *

block

)

const

Definition at line 1058 of file loops.cc.

                                                    {
  return blocks_->Contains(block->preorder_number());
}

control()

InductionVar * dart::LoopInfo::control ( ) const

inline

Definition at line 256 of file loops.h.

{ return control_; }

header()

BlockEntryInstr * dart::LoopInfo::header ( ) const

inline

Definition at line 252 of file loops.h.

{ return header_; }

id()

intptr_t dart::LoopInfo::id ( ) const

inline

Definition at line 251 of file loops.h.

{ return id_; }

inner()

LoopInfo * dart::LoopInfo::inner ( ) const

inline

Definition at line 258 of file loops.h.

{ return inner_; }

IsAlwaysTaken()

bool dart::LoopInfo::IsAlwaysTaken

(

BlockEntryInstr *

block

)

const

Definition at line 1010 of file loops.cc.

                                                         {
  // The loop header is always executed when executing a loop (including
  // loop body of a do-while). Reject any other loop body block that is
  // not directly controlled by header.
  if (block == header_) {
    return true;
  } else if (block->PredecessorCount() != 1 ||
             block->PredecessorAt(0) != header_) {
    return false;
  }
  // If the loop has a control induction, make sure the condition is such
  // that the loop body is entered at least once from the header.
  if (control_ != nullptr) {
    InductionVar* limit = nullptr;
    for (auto bound : control_->bounds()) {
      if (bound.branch_ == header_->last_instruction()) {
        limit = bound.limit_;
        break;
      }
    }
    // Control iterates at least once?
    if (limit != nullptr) {
      int64_t stride = 0;
      int64_t begin = 0;
      int64_t end = 0;
      if (InductionVar::IsLinear(control_, &stride) &&
          InductionVar::IsConstant(control_->initial(), &begin) &&
          InductionVar::IsConstant(limit, &end) &&
          ((stride == 1 && begin < end) || (stride == -1 && begin > end))) {
        return true;
      }
    }
  }
  return false;
}

IsBackEdge()

bool dart::LoopInfo::IsBackEdge

(

BlockEntryInstr *

block

)

const

Definition at line 1001 of file loops.cc.

                                                      {
  for (intptr_t i = 0, n = back_edges_.length(); i < n; i++) {
    if (back_edges_[i] == block) {
      return true;
    }
  }
  return false;
}

IsHeaderPhi()

bool dart::LoopInfo::IsHeaderPhi

(

Definition *

def

)

const

Definition at line 1046 of file loops.cc.

                                                {
  return def != nullptr && def->IsPhi() && def->GetBlock() == header_ &&
         !def->AsPhi()->IsRedundant();  // phi(x,..,x) = x
}

IsIn()

bool dart::LoopInfo::IsIn

(

LoopInfo *

loop

)

const

Definition at line 1051 of file loops.cc.

                                        {
  if (loop != nullptr) {
    return loop->Contains(header_);
  }
  return false;
}

IsInRange()

bool dart::LoopInfo::IsInRange	(	Instruction *	pos,
		Value *	index,
		Value *	length
	)

Definition at line 1093 of file loops.cc.

                                                                      {
  InductionVar* induc = LookupInduction(
      index->definition()->OriginalDefinitionIgnoreBoxingAndConstraints());
  InductionVar* len = LookupInduction(
      length->definition()->OriginalDefinitionIgnoreBoxingAndConstraints());
  if (induc != nullptr && len != nullptr) {
    // First, try the most common case. A simple induction directly
    // bounded by [c>=0,length-C>=0) for the length we are looking for.
    int64_t stride = 0;
    int64_t val = 0;
    int64_t diff = 0;
    if (InductionVar::IsLinear(induc, &stride) && stride == 1 &&
        InductionVar::IsConstant(induc->initial(), &val) && 0 <= val) {
      for (auto bound : induc->bounds()) {
        if (pos->IsDominatedBy(bound.branch_) &&
            len->CanComputeDifferenceWith(bound.limit_, &diff) && diff <= 0) {
          return true;
        }
      }
    }
    // If that fails, try to compute bounds using more outer loops.
    // Since array lengths >= 0, the conditions used during this
    // process avoid arithmetic wrap-around complications.
    InductionVar* min = nullptr;
    InductionVar* max = nullptr;
    if (induc->CanComputeBounds(this, pos, &min, &max)) {
      return InductionVar::IsConstant(min, &val) && 0 <= val &&
             len->CanComputeDifferenceWith(max, &diff) && diff < 0;
    }
  }
  return false;
}

limit()

ConstraintInstr * dart::LoopInfo::limit ( ) const

inline

Definition at line 255 of file loops.h.

{ return limit_; }

LookupInduction()

InductionVar * dart::LoopInfo::LookupInduction

(

Definition *

def

)

const

Definition at line 1081 of file loops.cc.

                                                             {
  InductionKV::Pair* pair = induction_.Lookup(def);
  if (pair != nullptr) {
    return pair->value;
  }
  return nullptr;
}

NestingDepth()

intptr_t dart::LoopInfo::NestingDepth

(

)

const

Definition at line 1062 of file loops.cc.

                                      {
  intptr_t nesting_depth = 1;
  for (LoopInfo* o = outer_; o != nullptr; o = o->outer()) {
    nesting_depth++;
  }
  return nesting_depth;
}

next()

LoopInfo * dart::LoopInfo::next ( ) const

inline

Definition at line 259 of file loops.h.

{ return next_; }

outer()

LoopInfo * dart::LoopInfo::outer ( ) const

inline

Definition at line 257 of file loops.h.

{ return outer_; }

PrintTo()

void dart::LoopInfo::PrintTo

(

BaseTextBuffer *

f

)

const

Definition at line 1126 of file loops.cc.

                                              {
  f->Printf("%*c", static_cast<int>(2 * NestingDepth()), ' ');
  f->Printf("loop%" Pd " B%" Pd " ", id_, header_->block_id());
  intptr_t num_blocks = 0;
  for (BitVector::Iterator it(blocks_); !it.Done(); it.Advance()) {
    num_blocks++;
  }
  f->Printf("#blocks=%" Pd, num_blocks);
  if (outer_ != nullptr) f->Printf(" outer=%" Pd, outer_->id_);
  if (inner_ != nullptr) f->Printf(" inner=%" Pd, inner_->id_);
  if (next_ != nullptr) f->Printf(" next=%" Pd, next_->id_);
  f->AddString(" [");
  for (intptr_t i = 0, n = back_edges_.length(); i < n; i++) {
    f->Printf(" B%" Pd, back_edges_[i]->block_id());
  }
  f->AddString(" ]");
}

ResetInduction()

void dart::LoopInfo::ResetInduction

(

)

Definition at line 1070 of file loops.cc.

                              {
  induction_.Clear();
  memo_cache_.Clear();
}

ToCString()

const char * dart::LoopInfo::ToCString

(

)

const

Definition at line 1144 of file loops.cc.

                                      {
  char buffer[1024];
  BufferFormatter f(buffer, sizeof(buffer));
  PrintTo(&f);
  return Thread::Current()->zone()->MakeCopyOfString(buffer);
}

Friends And Related Function Documentation

InductionVar

friend class InductionVar

friend

Definition at line 266 of file loops.h.

InductionVarAnalysis

friend class InductionVarAnalysis

friend

Definition at line 267 of file loops.h.

LoopHierarchy

friend class LoopHierarchy

friend

Definition at line 268 of file loops.h.

---

The documentation for this class was generated from the following files:

• third_party/dart-lang/sdk/runtime/vm/compiler/backend/loops.h
• third_party/dart-lang/sdk/runtime/vm/compiler/backend/loops.cc