Start line:  
End line:  

Snippet Preview

Snippet HTML Code

Stack Overflow Questions
  import java.util.BitSet;
  import java.util.Iterator;
  import java.util.List;
This produces a linear list of BasicBlocks so that the linearized instruction list is in executable form. In generating this list, we will also add jumps where required and remove as many jumps as possible. Ordinary BasicBlocks will follow FollowThrough edges and just concatenate together eliminating the need for executing a jump instruction during execution. Notes: 1. Basic blocks ending in branches have two edges (FollowTrough/NotTaken and Taken) 2. All BasicBlocks can possibly have two additional edges related to exceptions: - one that transfers control to a rescue block (if one exists that protects the excepting instruction) which is also responsible for running ensures - one that transfers control to an ensure block (if one exists) for situations where we bypass the rescue block (breaks and thread-kill). 3. Branch, Jump, Return, and Exceptions are all boundaries for BasicBlocks 4. Dummy Entry and Exit BasicBlocks exist in all CFGs NOTE: When the IR builder first builds its list, and the CFG builder builds the CFG, the order in which BBs are created should already be a linearized list. Need to verify this and we might be able to skip linearization if the CFG has not been transformed by any code transformation passes. This might be the case when JRuby first starts up when we may just build the IR and start interpreting it right away without running any opts. In that scenario, it may be worth it to not run the linearizer at all.
 public class CFGLinearizer {
     public static List<BasicBlocklinearize(CFG cfg) {
         List<BasicBlocklist = new ArrayList<BasicBlock>();
         BitSet processed = new BitSet(cfg.size()); // Assumes all id's are used
         return list;
     private static void linearizeInner(CFG cfgList<BasicBlocklist,
             BitSet processedBasicBlock current) {
         if (processed.get(current.getID())) return;
         // Cannot lay out current block till its fall-through predecessor has been laid out already
         BasicBlock source = cfg.getIncomingSourceOfType(current.);
         if (source != null && !processed.get(source.getID())) return;
         // First, fall-through BB
         BasicBlock fallThrough = cfg.getOutgoingDestinationOfType(current.);
         if (fallThrough != nulllinearizeInner(cfglistprocessedfallThrough);
         // Next, regular edges
         for (BasicBlock destinationcfg.getOutgoingDestinationsOfType(current.)) {
         // Next, exception edges
         for (BasicBlock destinationcfg.getOutgoingDestinationsOfType(current.)) {
         // Next, exit
         for (BasicBlock destinationcfg.getOutgoingDestinationsOfType(current.)) {

Process (fixup) list of instruction and add or remove jumps.
     private static void fixupList(CFG cfgList<BasicBlocklist) {
         BasicBlock exitBB = cfg.getExitBB();
         int n = list.size();
         for (int i = 0; i < n - 1; i++) {
             BasicBlock current = list.get(i);
             if (current == exitBB) { // exit not last
                 current.addInstr(new ReturnInstr(cfg.getScope().getManager().getNil()));
             Instr lastInstr = current.getLastInstr();
             if (lastInstr instanceof JumpInstr) { // if jumping to next BB then remove it
                 tryAndRemoveUnneededJump(list.get(i + 1), cfglastInstrcurrent);
             } else {
                addJumpIfNextNotDestination(cfglist.get(i + 1), lastInstrcurrent);
        BasicBlock current = list.get(n - 1);
        if (current != exitBB) {
            Instr lastInstr = current.getLastInstr();
            // Last instruction of the last basic block in the linearized list can NEVER
            // be a branch instruction because this basic block would then have a fallthrough
            // which would have to be present after it.
            assert (!(lastInstr instanceof BranchInstr));
            if ((lastInstr == null) || !lastInstr.getOperation().transfersControl()) {
                // We are guaranteed to have at least one non-exception edge because
                // the exit BB post-dominates all BBs in the CFG even when exception
                // edges are removed.
                // Verify that we have exactly one non-exception target
                // SSS FIXME: Is this assertion any different from the BranchInstr assertion above?
                Iterator<BasicBlockiter = cfg.getOutgoingDestinationsNotOfType(current.).iterator();
                BasicBlock target =;
                assert (target != null && !iter.hasNext());
                // System.out.println("BB " + curr.getID() + " is the last bb in the layout! Adding a jump to " + tgt._label);
                current.addInstr(new JumpInstr(target.getLabel()));
    private static void tryAndRemoveUnneededJump(BasicBlock nextCFG cfgInstr lastInstrBasicBlock current) {
        if (next == cfg.getBBForLabel(((JumpInstrlastInstr).getJumpTarget())) current.removeInstr(lastInstr);
    // If there is no jump at add of block and the next block is not destination insert a valid jump
    private static void addJumpIfNextNotDestination(CFG cfgBasicBlock nextInstr lastInstrBasicBlock current) {
        Iterator<BasicBlockouts = cfg.getOutgoingDestinations(current).iterator();
        BasicBlock target = outs.hasNext() ? : null;
        if (target != null && !outs.hasNext()) {
            if ((target != next) && ((lastInstr == null) || !lastInstr.getOperation().transfersControl())) {
                current.addInstr(new JumpInstr(target.getLabel()));
    private static void verifyAllBasicBlocksProcessed(CFG cfgBitSet processedthrows RuntimeException {
        // Verify that all bbs have been laid out!
        for (BasicBlock b : cfg.getBasicBlocks()) {
            if (!processed.get(b.getID())) {
                throw new RuntimeException("Bad CFG linearization: BB " + b.getID() + " has been missed!");
New to GrepCode? Check out our FAQ X