dart::LiveRange Class Reference

#include <linearscan.h>

Inheritance diagram for dart::LiveRange:

Public Member Functions
	LiveRange (intptr_t vreg, Representation rep)
intptr_t	vreg () const
Representation	representation () const
LiveRange *	next_sibling () const
UsePosition *	first_use () const
void	set_first_use (UsePosition *use)
UseInterval *	first_use_interval () const
UseInterval *	last_use_interval () const
Location	assigned_location () const
Location *	assigned_location_slot ()
intptr_t	Start () const
intptr_t	End () const
SafepointPosition *	first_safepoint () const
AllocationFinger *	finger ()
void	set_assigned_location (Location location)
void	set_spill_slot (Location spill_slot)
void	DefineAt (intptr_t pos)
void	AddSafepoint (intptr_t pos, LocationSummary *locs)
UsePosition *	AddUse (intptr_t pos, Location *location_slot)
void	AddHintedUse (intptr_t pos, Location *location_slot, Location *hint)
void	AddUseInterval (intptr_t start, intptr_t end)
void	Print ()
LiveRange *	SplitAt (intptr_t pos)
bool	CanCover (intptr_t pos) const
bool	Contains (intptr_t pos) const
Location	spill_slot () const
bool	HasOnlyUnconstrainedUsesInLoop (intptr_t loop_id) const
void	MarkHasOnlyUnconstrainedUsesInLoop (intptr_t loop_id)
bool	is_loop_phi () const
void	mark_loop_phi ()
void	mark_has_uses_which_require_stack ()
bool	has_uses_which_require_stack () 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)

Detailed Description

Definition at line 512 of file linearscan.h.

Constructor & Destructor Documentation

LiveRange()

dart::LiveRange::LiveRange ( intptr_t  vreg, Representation  rep  )

inlineexplicit

Definition at line 514 of file linearscan.h.

      : vreg_(vreg),
        representation_(rep),
        assigned_location_(),
        spill_slot_(),
        uses_(nullptr),
        first_use_interval_(nullptr),
        last_use_interval_(nullptr),
        first_safepoint_(nullptr),
        last_safepoint_(nullptr),
        next_sibling_(nullptr),
        has_only_any_uses_in_loops_(0),
        is_loop_phi_(false),
        finger_() {}

Member Function Documentation

AddHintedUse()

void dart::LiveRange::AddHintedUse	(	intptr_t	pos,
		Location *	location_slot,
		Location *	hint
	)

Definition at line 368 of file linearscan.cc.

                                             {
  ASSERT(hint != nullptr);
  AddUse(pos, location_slot)->set_hint(hint);
}

AddSafepoint()

void dart::LiveRange::AddSafepoint	(	intptr_t	pos,
		LocationSummary *	locs
	)

Definition at line 340 of file linearscan.cc.

                                                                {
  if (spill_slot().IsConstant() &&
      (locs->always_calls() && !locs->callee_safe_call())) {
    // Constants have pseudo spill slot assigned to them from
    // the very beginning. This means that we don't need to associate
    // "always_calls" safepoints with these ranges, because they will never
    // be spilled. We still need to associate slow-path safepoints because
    // a value might be allocated to a register across a slow-path call.
    return;
  }
 
  ASSERT(IsInstructionStartPosition(pos));
  SafepointPosition* safepoint =
      new SafepointPosition(ToInstructionEnd(pos), locs);
 
  if (first_safepoint_ == nullptr) {
    ASSERT(last_safepoint_ == nullptr);
    first_safepoint_ = last_safepoint_ = safepoint;
  } else {
    ASSERT(last_safepoint_ != nullptr);
    // We assume that safepoints list is sorted by position and that
    // safepoints are added in this order.
    ASSERT(last_safepoint_->pos() < pos);
    last_safepoint_->set_next(safepoint);
    last_safepoint_ = safepoint;
  }
}

AddUse()

UsePosition * dart::LiveRange::AddUse	(	intptr_t	pos,
		Location *	location_slot
	)

Definition at line 305 of file linearscan.cc.

                                                                    {
  ASSERT(location_slot != nullptr);
  ASSERT((first_use_interval_->start_ <= pos) &&
         (pos <= first_use_interval_->end_));
  if (uses_ != nullptr) {
    if ((uses_->pos() == pos) && (uses_->location_slot() == location_slot)) {
      return uses_;
    } else if (uses_->pos() < pos) {
      // If an instruction at position P is using the same value both as
      // a fixed register input and a non-fixed input (in this order) we will
      // add uses both at position P-1 and *then* P which will make
      // uses_ unsorted unless we account for it here.
      UsePosition* insert_after = uses_;
      while ((insert_after->next() != nullptr) &&
             (insert_after->next()->pos() < pos)) {
        insert_after = insert_after->next();
      }
 
      UsePosition* insert_before = insert_after->next();
      while (insert_before != nullptr && (insert_before->pos() == pos)) {
        if (insert_before->location_slot() == location_slot) {
          return insert_before;
        }
        insert_before = insert_before->next();
      }
 
      insert_after->set_next(
          new UsePosition(pos, insert_after->next(), location_slot));
      return insert_after->next();
    }
  }
  uses_ = new UsePosition(pos, uses_, location_slot);
  return uses_;
}

AddUseInterval()

void dart::LiveRange::AddUseInterval	(	intptr_t	start,
		intptr_t	end
	)

Definition at line 375 of file linearscan.cc.

                                                           {
  ASSERT(start < end);
 
  // Live ranges are being build by visiting instructions in post-order.
  // This implies that use intervals will be prepended in a monotonically
  // decreasing order.
  if (first_use_interval() != nullptr) {
    // If the first use interval and the use interval we are adding
    // touch then we can just extend the first interval to cover their
    // union.
    if (start > first_use_interval()->start()) {
      // The only case when we can add intervals with start greater than
      // start of an already created interval is BlockLocation.
      ASSERT(vreg() == kNoVirtualRegister);
      ASSERT(end <= first_use_interval()->end());
      return;
    } else if (start == first_use_interval()->start()) {
      // Grow first interval if necessary.
      if (end <= first_use_interval()->end()) return;
      first_use_interval_->end_ = end;
      return;
    } else if (end == first_use_interval()->start()) {
      first_use_interval()->start_ = start;
      return;
    }
 
    ASSERT(end < first_use_interval()->start());
  }
 
  first_use_interval_ = new UseInterval(start, end, first_use_interval_);
  if (last_use_interval_ == nullptr) {
    ASSERT(first_use_interval_->next() == nullptr);
    last_use_interval_ = first_use_interval_;
  }
}

assigned_location()

Location dart::LiveRange::assigned_location ( ) const

inline

Definition at line 536 of file linearscan.h.

{ return assigned_location_; }

assigned_location_slot()

Location * dart::LiveRange::assigned_location_slot ( )

inline

Definition at line 537 of file linearscan.h.

{ return &assigned_location_; }

CanCover()

bool dart::LiveRange::CanCover ( intptr_t  pos ) const

inline

Definition at line 567 of file linearscan.h.

                                    {
    return (Start() <= pos) && (pos < End());
  }

Contains()

bool dart::LiveRange::Contains

(

intptr_t

pos

)

const

Definition at line 2777 of file linearscan.cc.

                                           {
  if (!CanCover(pos)) return false;
 
  for (UseInterval* interval = first_use_interval_; interval != nullptr;
       interval = interval->next()) {
    if (interval->Contains(pos)) {
      return true;
    }
  }
 
  return false;
}

DefineAt()

void dart::LiveRange::DefineAt

(

intptr_t

pos

)

Definition at line 411 of file linearscan.cc.

                                     {
  // Live ranges are being build by visiting instructions in post-order.
  // This implies that use intervals will be prepended in a monotonically
  // decreasing order.
  // When we encounter a use of a value inside a block we optimistically
  // expand the first use interval to cover the block from the start
  // to the last use in the block and then we shrink it if we encounter
  // definition of the value inside the same block.
  if (first_use_interval_ == nullptr) {
    // Definition without a use.
    first_use_interval_ = new UseInterval(pos, pos + 1, nullptr);
    last_use_interval_ = first_use_interval_;
  } else {
    // Shrink the first use interval. It was optimistically expanded to
    // cover the block from the start to the last use in the block.
    ASSERT(first_use_interval_->start_ <= pos);
    first_use_interval_->start_ = pos;
  }
}

End()

intptr_t dart::LiveRange::End ( ) const

inline

Definition at line 539 of file linearscan.h.

{ return last_use_interval()->end(); }

finger()

AllocationFinger * dart::LiveRange::finger ( )

inline

Definition at line 543 of file linearscan.h.

{ return &finger_; }

first_safepoint()

SafepointPosition * dart::LiveRange::first_safepoint ( ) const

inline

Definition at line 541 of file linearscan.h.

{ return first_safepoint_; }

first_use()

UsePosition * dart::LiveRange::first_use ( ) const

inline

Definition at line 532 of file linearscan.h.

{ return uses_; }

first_use_interval()

UseInterval * dart::LiveRange::first_use_interval ( ) const

inline

Definition at line 534 of file linearscan.h.

{ return first_use_interval_; }

has_uses_which_require_stack()

bool dart::LiveRange::has_uses_which_require_stack ( ) const

inline

Definition at line 596 of file linearscan.h.

                                            {
    return has_uses_which_require_stack_;
  }

HasOnlyUnconstrainedUsesInLoop()

bool dart::LiveRange::HasOnlyUnconstrainedUsesInLoop ( intptr_t  loop_id ) const

inline

Definition at line 576 of file linearscan.h.

                                                              {
    if (loop_id < kMaxLoops) {
      const uint64_t mask = static_cast<uint64_t>(1) << loop_id;
      return (has_only_any_uses_in_loops_ & mask) != 0;
    }
    return false;
  }

is_loop_phi()

bool dart::LiveRange::is_loop_phi ( ) const

inline

Definition at line 590 of file linearscan.h.

{ return is_loop_phi_; }

last_use_interval()

UseInterval * dart::LiveRange::last_use_interval ( ) const

inline

Definition at line 535 of file linearscan.h.

{ return last_use_interval_; }

mark_has_uses_which_require_stack()

void dart::LiveRange::mark_has_uses_which_require_stack ( )

inline

Definition at line 593 of file linearscan.h.

                                           {
    has_uses_which_require_stack_ = true;
  }

mark_loop_phi()

void dart::LiveRange::mark_loop_phi ( )

inline

Definition at line 591 of file linearscan.h.

{ is_loop_phi_ = true; }

MarkHasOnlyUnconstrainedUsesInLoop()

void dart::LiveRange::MarkHasOnlyUnconstrainedUsesInLoop ( intptr_t  loop_id )

inline

Definition at line 584 of file linearscan.h.

                                                            {
    if (loop_id < kMaxLoops) {
      has_only_any_uses_in_loops_ |= static_cast<uint64_t>(1) << loop_id;
    }
  }

next_sibling()

LiveRange * dart::LiveRange::next_sibling ( ) const

inline

Definition at line 531 of file linearscan.h.

{ return next_sibling_; }

Print()

void dart::LiveRange::Print

(

)

Definition at line 507 of file linearscan.cc.

                      {
  if (first_use_interval() == nullptr) {
    return;
  }
 
  THR_Print("  live range v%" Pd " [%" Pd ", %" Pd ") in ", vreg(), Start(),
            End());
  assigned_location().Print();
  if (assigned_location().IsConstant()) {
    THR_Print(" %s", assigned_location().constant().ToCString());
  }
  if (!spill_slot_.IsInvalid() && !spill_slot_.IsConstant()) {
    THR_Print(" assigned spill slot: %s", spill_slot_.ToCString());
  }
  THR_Print("\n");
 
  SafepointPosition* safepoint = first_safepoint();
  while (safepoint != nullptr) {
    THR_Print("    Safepoint [%" Pd "]: ", safepoint->pos());
    safepoint->locs()->stack_bitmap().Print();
    THR_Print("\n");
    safepoint = safepoint->next();
  }
 
  UsePosition* use_pos = uses_;
  for (UseInterval* interval = first_use_interval_; interval != nullptr;
       interval = interval->next()) {
    THR_Print("    use interval [%" Pd ", %" Pd ")\n", interval->start(),
              interval->end());
    while ((use_pos != nullptr) && (use_pos->pos() <= interval->end())) {
      THR_Print("      use at %" Pd "", use_pos->pos());
      if (use_pos->location_slot() != nullptr) {
        THR_Print(" as ");
        use_pos->location_slot()->Print();
      }
      THR_Print("\n");
      use_pos = use_pos->next();
    }
  }
 
  if (next_sibling() != nullptr) {
    next_sibling()->Print();
  }
}

representation()

Representation dart::LiveRange::representation ( ) const

inline

Definition at line 530 of file linearscan.h.

{ return representation_; }

set_assigned_location()

void dart::LiveRange::set_assigned_location ( Location  location )

inline

Definition at line 545 of file linearscan.h.

                                                {
    assigned_location_ = location;
  }

set_first_use()

void dart::LiveRange::set_first_use ( UsePosition *  use )

inline

Definition at line 533 of file linearscan.h.

{ uses_ = use; }

set_spill_slot()

void dart::LiveRange::set_spill_slot ( Location  spill_slot )

inline

Definition at line 549 of file linearscan.h.

{ spill_slot_ = spill_slot; }

spill_slot()

Location dart::LiveRange::spill_slot ( ) const

inline

Definition at line 574 of file linearscan.h.

{ return spill_slot_; }

SplitAt()

LiveRange * dart::LiveRange::SplitAt

(

intptr_t

pos

)

Definition at line 1895 of file linearscan.cc.

                                                {
  if (Start() == split_pos) return this;
 
  UseInterval* interval = finger_.first_pending_use_interval();
  if (interval == nullptr) {
    finger_.Initialize(this);
    interval = finger_.first_pending_use_interval();
  }
 
  ASSERT(split_pos < End());
 
  // Corner case. Split position can be inside the a lifetime hole or at its
  // end. We need to start over to find the previous interval.
  if (split_pos <= interval->start()) interval = first_use_interval_;
 
  UseInterval* last_before_split = nullptr;
  while (interval->end() <= split_pos) {
    last_before_split = interval;
    interval = interval->next();
  }
 
  const bool split_at_start = (interval->start() == split_pos);
 
  UseInterval* first_after_split = interval;
  if (!split_at_start && interval->Contains(split_pos)) {
    first_after_split =
        new UseInterval(split_pos, interval->end(), interval->next());
    interval->end_ = split_pos;
    interval->next_ = first_after_split;
    last_before_split = interval;
  }
 
  ASSERT(last_before_split != nullptr);
  ASSERT(last_before_split->next() == first_after_split);
  ASSERT(last_before_split->end() <= split_pos);
  ASSERT(split_pos <= first_after_split->start());
 
  UsePosition* first_use_after_split =
      SplitListOfPositions(&uses_, split_pos, split_at_start);
 
  SafepointPosition* first_safepoint_after_split =
      SplitListOfPositions(&first_safepoint_, split_pos, split_at_start);
 
  UseInterval* last_use_interval = (last_before_split == last_use_interval_)
                                       ? first_after_split
                                       : last_use_interval_;
  next_sibling_ = new LiveRange(vreg(), representation(), first_use_after_split,
                                first_after_split, last_use_interval,
                                first_safepoint_after_split, next_sibling_);
 
  TRACE_ALLOC(THR_Print("  split sibling [%" Pd ", %" Pd ")\n",
                        next_sibling_->Start(), next_sibling_->End()));
 
  last_use_interval_ = last_before_split;
  last_use_interval_->next_ = nullptr;
 
  if (first_use_after_split != nullptr) {
    finger_.UpdateAfterSplit(first_use_after_split->pos());
  }
 
  return next_sibling_;
}

Start()

intptr_t dart::LiveRange::Start ( ) const

inline

Definition at line 538 of file linearscan.h.

{ return first_use_interval()->start(); }

vreg()

intptr_t dart::LiveRange::vreg ( ) const

inline

Definition at line 529 of file linearscan.h.

{ return vreg_; }

---

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

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