Package jminusminus

Class NInterval

java.lang.Object
jminusminus.NInterval
All Implemented Interfaces:
Comparable<NInterval>
class NInterval extends Object implements Comparable<NInterval>
Represents a lifetime interval, recording the interval of LIR code for which the corresponding virtual register contains a useful value.

  • Field Details

    • vRegId

      public int vRegId
      The virtual register id corresponding to the index in the array list of NIntervals used by register allocation

    • ranges

      public ArrayList<NRange> ranges
      All live ranges for this virtual register

    • usePositions

      public TreeMap<Integer,InstructionType> usePositions
      All use positions (in LIR) and their types for this virtual register

    • pRegister

      public NPhysicalRegister pRegister
      The NPhyicalRegister assigned to this interval. If an interval ends up needing more than one physical register it is split.

    • spill

      public boolean spill
      Whether or not to spill.

    • offsetFrom

      public OffsetFrom offsetFrom
      From offset.

    • offset

      public int offset
      Offset.

    • parent

      public NInterval parent
      Parent of this interval.

    • children

      public ArrayList<NInterval> children
      Children of this interval.

  • Constructor Details

    • NInterval

      public NInterval(int vRegId, NControlFlowGraph cfg)
      Constructs an NInterval object.
      Parameters:
      vRegId - program counter.
      cfg - the control flow graph.

    • NInterval

      public NInterval(int virtualRegID, NControlFlowGraph cfg, ArrayList<NRange> childRanges, NInterval parent)
      This second constructor is used in instantiating children of a split interval.
      Parameters:
      virtualRegID - program counter.
      cfg - The control flow graph.
      childRanges - The instruction ranges for this child.
      parent - The parent interval.

  • Method Details

    • addOrExtendNRange

      public void addOrExtendNRange(NRange newNRange)
      Adds a new range to the existing ranges. If the range overlaps then the old start position will be given the new start range position.
      Parameters:
      newNRange - the NRange to add

    • nextIntersection

      public int nextIntersection(NInterval otherInterval)
      Returns the very first position where an intersection with another interval occurs.
      Parameters:
      otherInterval - the interval to compare against for intersection.
      Returns:
      the position where the intersection begins.

    • nextUsageOverlapping

      public int nextUsageOverlapping(NInterval currInterval)
      Returns the next use position of this interval after the first range start of the foreign interval. If there is no such use, then the first use position is returned to preserve data flow (in case of loops).
      Parameters:
      currInterval - the interval with starting point after which we want to find the next usage of this one.
      Returns:
      the next use position.

    • firstUsage

      public int firstUsage()
      Returns the first use position in this interval.
      Returns:
      the first use position in this interval.

    • newFirstRangeStart

      public void newFirstRangeStart(int newStart)
      Sets the start value of the very first range. Note: There will always be at least one range before this method is used by the NRegisterAllocator.buildIntervals() method.
      Parameters:
      newStart - the value to which the first range's start will be set.

    • addUsePosition

      public void addUsePosition(Integer index, InstructionType type)
      Registers a use (read or write).
      Parameters:
      index - the site of the use.
      type - the instruction type.

    • isLiveAt

      public boolean isLiveAt(int atIndex)
      Returns true if this virtual register is alive at a given index, and false otherwise.
      Parameters:
      atIndex - the index at which to see if this register is live.
      Returns:
      true if this virtual register is alive at a given index, and false otherwise.

    • writeToStdOut

      public void writeToStdOut(PrettyPrinter p)
      Writes the interval information to STDOUT.
      Parameters:
      p - for pretty printing with indentation.

    • firstNRangeStart

      public int firstNRangeStart()
      Returns the start position for the first range.
      Returns:
      the start position for the first range.

    • lastNRangeStop

      public int lastNRangeStop()
      Returns the stop position for the last range.
      Returns:
      the stop position for the last range.

    • compareTo

      public int compareTo(NInterval other)
      Returns a comparison of this interval with other.
      Specified by:
      compareTo in interface Comparable<NInterval>
      Parameters:
      other - interval to compare to.
      Returns:
      a comparison of this interval with other.

    • equals

      public boolean equals(NInterval other)
      Returns true if this interval is the same as other, and false otherwise.
      Parameters:
      other - the interval we are comparing with.
      Returns:
      true if this interval is the same as other, and false otherwise.

    • splitAt

      public NInterval splitAt(int idx)
      Splits the current interval at the given index. Responsible for splitting a range if the index falls on one, moving remaining ranges over to child, and moving appropriate usePositions over to the child.
      Parameters:
      idx - the index at which this interval is to be split
      Returns:
      the child interval which is to be sorted onto unhandled. If there was no child created in the case of a pruning this interval is returned.

    • childAt

      public NInterval childAt(int idx)
      Returns the child interval at the given instruction index.
      Parameters:
      idx - the instruction index.
      Returns:
      the child interval at the given instruction index.

    • childAtOrEndingBefore

      public NInterval childAtOrEndingBefore(NBasicBlock b)
      Returns the child of this interval which is live or ends before the given basic block's end.
      Parameters:
      b - the basic block.
      Returns:
      the child of this interval which ends at or nearest (before) this basic block's end (last lir instruction index).

    • childAtOrStartingAfter

      public NInterval childAtOrStartingAfter(NBasicBlock b)
      Returns the child of this interval which is live or starts after the given basic block's start.
      Parameters:
      b - the basic block.
      Returns:
      the child of this interval which starts at or nearest (after) this basic block's start (fist lir instruction index).

    • startsAtBlock

      public int startsAtBlock()
      Returns the basic block in which this interval's start position falls.
      Returns:
      the basic block in which this interval's start position falls.

    • endsAtBlock

      public int endsAtBlock()
      Returns the basic block in which this interval's end position falls.
      Returns:
      the basic block in which this interval's end position falls.

    • spill

      public void spill()
      Assigns an offset to this interval (if one hasn't been already assigned). Assigns that same offset to any (newly created) children.

    • isChild

      public boolean isChild()
      Returns true if this is a child interval, and false otherwise.
      Returns:
      true if this is a child interval, and false otherwise.

    • isParent

      public boolean isParent()
      Returns true if this is a parent interval, and false otherwise.
      Returns:
      true if this is a parent interval, and false otherwise.