Package kilim.analysis

Class Usage

java.lang.Object
kilim.analysis.Usage
public class Usage extends Object
Each BasicBlock owns one instance of Usage. This class maintains, in essence, three vectors of booleans, indexed by the local variable number. Since it is very rare for a method to have more than 31 local variables, the vectors are represented by int bitmaps. For more than this, the basic block creates an instance of BigUsage that is functionally identical (TODO) Note that we don't need to track usage of operand stack. All elements of the operand stack are always live, and always need to be stored and restored (during stack switching). This is not true of local vars; a var may have a valid value which may not be used downstream, so we track which vars must be taken seriously.
See Also:

  • Field Summary

    Fields
    Modifier and Type
    Field
    Description
    private BitSet
    born
    born.bit(i) == 1 (from LSB) if the ith var has been defined prior either as a method parameter or by a write only vars that have been born can be live (used to protect against vars that are def'd in a block and used in the catch, eg the exception)
    private BitSet
    def
    def.bit(i) == 1 (from LSB) if the ith var is written into before it has been read.
    private BitSet
    in
    bit(i) == 1 (counting from LSB) if the ith local var is live downstream
    private int
    nLocals
    The number of local vars in the owning BB's frame
    private BitSet
    use
    use.bit(i) == 1 (from LSB) if the ith var is read before it has been written.

  • Constructor Summary

    Constructors
    Constructor
    Description
    Usage(int numLocals)
     

  • Method Summary

    Modifier and Type
    Method
    Description
    (package private) void
    absorb(Usage succ)
    Called to coalesce a successor's usage into the current BB.
    void
    born(int var)
     
    (package private) Usage
    copy()
     
    (package private) boolean
    evalBornIn(Usage pred, BitSet combo)
    evolve the born value a single iteration by mixing in either pred or combo
    boolean
    evalLiveIn(ArrayList<Usage> succUsage, ArrayList<Handler> handUsage)
    This is the standard liveness calculation (Dragon Book, section 10.6).
    (package private) BitSet
    getCombo()
    get def OR born
    (package private) void
    initBorn(BitSet first)
    set born - used for the first BB only, others are calculated
    boolean
    isLiveIn(int var)
    return true if var is live at the entrance to this BB.
    (package private) void
    mergeBorn()
    merge def into born
    private void
    printBits(StringBuffer sb, BitSet b)
     
    private void
    printBitsFull(StringBuffer sb, BitSet b)
     
    private String
    printBitsFull(BitSet b)
     
    void
    read(int var)
     
    void
    setBornIn(int var)
    This is purely for testing purposes.
    void
    setLiveIn(int var)
    This is purely for testing purposes.
    String
    toString()
     
    String
    toStringBits(String sep)
     
    void
    write(int var)
     

    Methods inherited from class java.lang.Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

  • Field Details

    • nLocals

      private int nLocals
      The number of local vars in the owning BB's frame

    • in

      private BitSet in
      bit(i) == 1 (counting from LSB) if the ith local var is live downstream

    • born

      private BitSet born
      born.bit(i) == 1 (from LSB) if the ith var has been defined prior either as a method parameter or by a write only vars that have been born can be live (used to protect against vars that are def'd in a block and used in the catch, eg the exception)

    • use

      private BitSet use
      use.bit(i) == 1 (from LSB) if the ith var is read before it has been written. The bit vector as a whole represents the set of vars that the BB needs from its predecessors.

    • def

      private BitSet def
      def.bit(i) == 1 (from LSB) if the ith var is written into before it has been read. It represents all the vars that this BB is capable of supplying downstream on its own, hence those vars are not required to be supplied by its predecessors (even if they do supply them, they will be overwritten anyway).

  • Constructor Details

    • Usage

      public Usage(int numLocals)

  • Method Details

    • read

      public void read(int var)

    • write

      public void write(int var)

    • born

      public void born(int var)

    • isLiveIn

      public boolean isLiveIn(int var)
      return true if var is live at the entrance to this BB.

    • evalLiveIn

      public boolean evalLiveIn(ArrayList<Usage> succUsage, ArrayList<Handler> handUsage)
      This is the standard liveness calculation (Dragon Book, section 10.6). At each BB (and its corresponding usage), we evaluate "in" using use and def. in = use U (out \ def) where out = U succ.in, for all successors this algorithm has been modified to treat catch blocks as occurring anywhere ie, that vars defined in a try may never be set however, this only applies to vars that have been defined at least once (ie, born)

    • getCombo

      BitSet getCombo()
      get def OR born

    • mergeBorn

      void mergeBorn()
      merge def into born

    • initBorn

      void initBorn(BitSet first)
      set born - used for the first BB only, others are calculated

    • evalBornIn

      boolean evalBornIn(Usage pred, BitSet combo)
      evolve the born value a single iteration by mixing in either pred or combo
      Parameters:
      pred - if combo is null, use pred.born
      combo - if non-null, the value to mix in
      Returns:
      true if the evolution resulted in a change in the born value

    • absorb

      void absorb(Usage succ)
      Called to coalesce a successor's usage into the current BB. Important: This should be called before live variable analysis begins, because we don't bother merging this.in or this.born.

    • toString

      public String toString()
      Overrides:
      toString in class Object

    • toStringBits

      public String toStringBits(String sep)

    • printBits

      private void printBits(StringBuffer sb, BitSet b)

    • printBitsFull

      private String printBitsFull(BitSet b)

    • printBitsFull

      private void printBitsFull(StringBuffer sb, BitSet b)

    • setLiveIn

      public void setLiveIn(int var)
      This is purely for testing purposes.
      Parameters:
      var - local var index

    • setBornIn

      public void setBornIn(int var)
      This is purely for testing purposes.
      Parameters:
      var - local var index

    • copy

      Usage copy()