Package kilim.analysis

Class Usage

  • public class Usage
extends java.lang.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:
    BasicBlock

    • Field Summary

      Fields 
      Modifier and Type Field Description
      private java.util.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 java.util.BitSet def
      def.bit(i) == 1 (from LSB) if the ith var is written into before it has been read.
      private java.util.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 java.util.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

      All Methods Instance Methods Concrete Methods 
      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, java.util.BitSet combo)
      evolve the born value a single iteration by mixing in either pred or combo
      boolean evalLiveIn​(java.util.ArrayList<Usage> succUsage, java.util.ArrayList<Handler> handUsage)
      This is the standard liveness calculation (Dragon Book, section 10.6).
      (package private) java.util.BitSet getCombo()
      get def OR born
      (package private) void initBorn​(java.util.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​(java.lang.StringBuffer sb, java.util.BitSet b)  
      private void printBitsFull​(java.lang.StringBuffer sb, java.util.BitSet b)  
      private java.lang.String printBitsFull​(java.util.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.
      java.lang.String toString()  
      java.lang.String toStringBits​(java.lang.String sep)  
      void write​(int var)  

      • Methods inherited from class java.lang.Object

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

    • Field Detail

      • nLocals

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

      • in

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

      • born

        private java.util.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 java.util.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 java.util.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 Detail

      • Usage

        public Usage​(int numLocals)

    • Method Detail

      • 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​(java.util.ArrayList<Usage> succUsage,
                          java.util.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

        java.util.BitSet getCombo()
        get def OR born

      • mergeBorn

        void mergeBorn()
        merge def into born

      • initBorn

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

      • evalBornIn

        boolean evalBornIn​(Usage pred,
                   java.util.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 java.lang.String toString()
        Overrides:
        toString in class java.lang.Object

      • toStringBits

        public java.lang.String toStringBits​(java.lang.String sep)

      • printBits

        private void printBits​(java.lang.StringBuffer sb,
                       java.util.BitSet b)

      • printBitsFull

        private java.lang.String printBitsFull​(java.util.BitSet b)

      • printBitsFull

        private void printBitsFull​(java.lang.StringBuffer sb,
                           java.util.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