Package kilim.analysis

Class BasicBlock

java.lang.Object
kilim.analysis.BasicBlock
All Implemented Interfaces:
Comparable<BasicBlock>
public class BasicBlock extends Object implements Comparable<BasicBlock>
A basic block is a contiguous set of instructions that has one label at the first instruction and a transfer-of-control instruction at the very end. A transfer-of-control instruction includes all branching instructions that have labelled targets (IF_x, GOTO, and JSR) and the rest (ATHROW, xRETURN, RET). There can be no target labels in the middle of a basic block; in other words, you can't jump into the middle of a basic block. This is the standard definition; we make a few changes.
  • We create BasicBlocks whenever we encounter a label (in a linear scanning of a method's instructions. Some labels are meant for catch handlers and debug (line number) information only; they are not the target of a branching instruction, but we don't know that in the first pass. We coalesce those BasicBlocks that merely follow another, provided the preceding BB is the only preceder. Note that blocks connected with a GOTO can't coalesce because they are not likely to be contiguous, even if they obey the constraint of a single edge. We also don't coalesce blocks starting with a pausable method invocation with their predecessor, because we need these blocks to tell us about downstream usage of local vars to help us generate optimal continuations.
  • All catch handlers that intersect a basic block are treated as successors to the block, for the purposes of liveness analysis.
  • Subroutines (targets of JSR) are treated specially. We inline all JSR calls, including nested JSRs, to simplify liveness analysis. In this phase, a JSR/RET is treated the same as a GOTO sub followed by a GOTO to the caller. During the weaving phase, we ignore the inlining information if the subroutine doesn't have any pausable methods. If it does, then we spit out duplicate code, complete with GOTOs as described above. This allows us to jump in the middle of a "finally" block during rewinding. Note: The JVM reference doesn't specify the boundaries of a JSR instruction; in other words, there is no definitive way of saying which blocks belong to a subroutine. This code treats the set of all nodes reachable via branching instructions from the subroutine's entry point. (exception catch blocks don't count)

    • Field Details

      • id

        public int id
        A number handed out in increasing order of starting position, to ease sorting as well as for debug information

      • flags

        int flags

      • ENQUEUED

        static final int ENQUEUED
        See Also:

      • SUBROUTINE_CLAIMED

        static final int SUBROUTINE_CLAIMED
        See Also:

      • COALESCED

        static final int COALESCED
        See Also:

      • PAUSABLE

        static final int PAUSABLE
        See Also:

      • IS_SUBROUTINE

        static final int IS_SUBROUTINE
        See Also:

      • SUB_BLOCK

        static final int SUB_BLOCK
        See Also:

      • INLINE_CHECKED

        static final int INLINE_CHECKED
        See Also:

      • PAUSABLE_SUB

        static final int PAUSABLE_SUB
        See Also:

      • flow

        public MethodFlow flow
        The flow to which this BB belongs.

      • startLabel

        public org.objectweb.asm.tree.LabelNode startLabel
        The label that starts this BB. In some cases we create a label where it didn't exist originally (after a jmp instruction, for example). This allows us a unique indexing scheme.

      • startPos

        public int startPos
        Start and end points (both inclusive) in the current method's list of instructions (this.flow.instructions)

      • endPos

        public int endPos

      • successors

        public ArrayList<BasicBlock> successors
        List of successors (follower and all branch targets). Should be null

      • handlers

        public ArrayList<Handler> handlers

      • numPredecessors

        int numPredecessors

      • usage

        public Usage usage
        usage initially contains the usage of local variables in this block (without reference to any other block). After flow analysis it contains the combined effect of this and all downstream blocks

      • visited

        boolean visited
        the block has already been visited during the born calculation

      • succUsage

        ArrayList<Usage> succUsage
        A cached version of all sucessors' usage, successors being catch handlers and real successors.

      • handUsage

        ArrayList<Usage> handUsage

      • startFrame

        public Frame startFrame
        The frame at the BB's entry point. It changes when propagating changes from its predeccessors, until there's a fixed point.

      • caughtExceptionType

        String caughtExceptionType

      • follower

        BasicBlock follower

      • subBlocks

        ArrayList<BasicBlock> subBlocks

    • Constructor Details

      • BasicBlock

        public BasicBlock(MethodFlow aflow, org.objectweb.asm.tree.LabelNode aStartLabel)

    • Method Details

      • initialize

        int initialize(int pos)
        Absorb as many instructions until the next label or the next transfer of control instruction. In the first pass we may end up creating many many BBs because there may be a lot of non-target labels (esp. when debug information is available). The constraints are as follows: 1. A transfer of control instruction must be the last instruction. It may also be the first (and only) instruction 2. A labeled instruction must be the first instruction in a BB. It may optionally be the last (and only) instruction 3. A pausable method is treated like a labeled instruction, and is given a label if there isn't one already. Constraint 2 applies.

      • addFollower

        void addFollower(BasicBlock bb)

      • addSuccessor

        void addSuccessor(BasicBlock bb)

      • getVarUsage

        public Usage getVarUsage()

      • lastInstruction

        int lastInstruction()

      • coalesceTrivialFollowers

        void coalesceTrivialFollowers()

      • setFlag

        public void setFlag(int bitFlag)

      • unsetFlag

        public void unsetFlag(int bitFlag)

      • hasFlag

        public boolean hasFlag(int bitFlag)

      • compareTo

        public int compareTo(BasicBlock o)
        Specified by:
        compareTo in interface Comparable<BasicBlock>

      • interpret

        void interpret()

      • isCatchHandler

        public boolean isCatchHandler()

      • mergeSuccessors

        void mergeSuccessors(Frame frame)

      • merge

        void merge(Frame inframe, boolean localsOnly)
        Parameters:
        inframe -
        localsOnly -

      • chooseCatchHandlers

        public void chooseCatchHandlers(ArrayList<Handler> handlerList)

      • getInstruction

        public org.objectweb.asm.tree.AbstractInsnNode getInstruction(int pos)

      • printGeniology

        String printGeniology()
        pretty print successor and catch BB ids

      • flowVarUsage

        public boolean flowVarUsage()
        calculate the liveness usage by evolution (assume born usage has already been calculated)

      • inline

        ArrayList<BasicBlock> inline() throws KilimException
        This basic block's last instruction is JSR. This method initiates a subgraph traversal to identify the called subroutine's boundaries and to make all encountered RET instructions point back to this BB's follower, in essence turning it to a goto. The reason for not actually turning it into a GOTO is that if we don't find any pausable methods in a subroutine, then during code generation we'll simply use the original code. The duplication is still required for flow analysis. The VM spec is fuzzy on what constitutes the boundaries of a subroutine. We consider the following situations invalid, even though the verifier is ok with it: (a) looping back to itself (b) encountering xRETURN in a subroutine inline() traverses the graph creating copies of BasicBlocks and labels and keeps a mapping between the old and the new. In the second round, it copies instructions translating any that have labels (branch and switch instructions).
        Returns:
        mapping of orig basic blocks to new.
        Throws:
        KilimException

      • dupBBAndLabels

        void dupBBAndLabels(boolean deepCopy, HashMap<BasicBlock,BasicBlock> bbCopyMap, HashMap<org.objectweb.asm.tree.LabelNode,org.objectweb.asm.tree.LabelNode> labelCopyMap, BasicBlock returnToBB) throws KilimException
        Throws:
        KilimException

      • dupCopyContents

        static ArrayList<BasicBlock> dupCopyContents(boolean deepCopy, BasicBlock targetBB, BasicBlock returnToBB, HashMap<BasicBlock,BasicBlock> bbCopyMap, HashMap<org.objectweb.asm.tree.LabelNode,org.objectweb.asm.tree.LabelNode> labelCopyMap) throws KilimException
        Throws:
        KilimException

      • getJSRTarget

        public BasicBlock getJSRTarget()

      • getSubBlocks

        public ArrayList<BasicBlock> getSubBlocks() throws KilimException
        Throws:
        KilimException

      • getFollowingBlock

        BasicBlock getFollowingBlock()

      • toString

        public String toString()
        Overrides:
        toString in class Object

      • isPausable

        public boolean isPausable()

      • setId

        void setId(int aid)

      • checkPausableJSR

        void checkPausableJSR() throws KilimException
        Throws:
        KilimException

      • changeJSR_RET_toGOTOs

        void changeJSR_RET_toGOTOs() throws KilimException
        Throws:
        KilimException

      • setInstruction

        void setInstruction(int pos, org.objectweb.asm.tree.AbstractInsnNode insn)

      • changeLastInsnToGOTO

        void changeLastInsnToGOTO(org.objectweb.asm.tree.LabelNode label)

      • isGetCurrentTask

        public boolean isGetCurrentTask()

      • isInitialized

        boolean isInitialized()