Start line:  
End line:  

Snippet Preview

Snippet HTML Code

Stack Overflow Questions
  package org.jruby.ir.representations;
  
  import java.util.BitSet;
  import java.util.HashMap;
  import java.util.HashSet;
  import java.util.List;
 import java.util.Map;
 import java.util.Set;
Represents the base build of a CFG. All information here is accessed via delegation from the CFG itself so this is meant as an internal organizational structure for a build.
 
 public class CFG {
     public enum EdgeType {
         REGULAR,       // Any non-special edge.  Not really used.
         EXCEPTION,     // Edge to exception handling basic blocks
         FALL_THROUGH,  // Edge which is the natural fall through choice on a branch
         EXIT           // Edge to dummy exit BB
     }
     
     private static final Logger LOG = LoggerFactory.getLogger("CFG");
     
     private IRScope scope;
     private Map<LabelBasicBlockbbMap;
         
     // Map of bb -> first bb of the rescue block that initiates exception handling for all exceptions thrown within this bb
     private Map<BasicBlockBasicBlockrescuerMap;
         
     // Map of bb -> first bb of the ensure block that protects this bb
     private Map<BasicBlockBasicBlockensurerMap;
         
     private List<ExceptionRegionoutermostERs;

    
Entry BB
 
     private BasicBlock entryBB;

    
Exit BB
 
     private BasicBlock exitBB;

    
BB that traps all exception-edges out of the cfg where we could add any cleanup/ensure code (ex: pop frames, etc.)
 
     private BasicBlock globalEnsureBB;

    
The graph itself
 
     private DirectedGraph<BasicBlockgraph;
     
     private int nextBBId;       // Next available basic block id
     
     LinkedList<BasicBlockpostOrderList// Post order traversal list of the cfg    
     
     public CFG(IRScope scope) {
         this. = scope;
         this. = new DirectedGraph<BasicBlock>();
         this. = new HashMap<LabelBasicBlock>();
         this. = new HashMap<BasicBlockBasicBlock>();
         this. = new HashMap<BasicBlockBasicBlock>();
         this. = new ArrayList<ExceptionRegion>();
         this. = 0;
         this. = this. = null;
         this. = null;
         this. = null;
     }
     
     public int getNextBBID() {
         ++;
         return ;
     }
 
     public int getMaxNodeID() {
         return ;
     }     
    public boolean bbIsProtected(BasicBlock b) {
        // No need to look in ensurerMap because (_bbEnsurerMap(b) != null) => (_bbResucerMap(b) != null)
        return getRescuerBBFor(b) != null;
    }    
    
    public BasicBlock getBBForLabel(Label label) {
        return .get(label);
    }
    
    public BasicBlock getEnsurerBBFor(BasicBlock block) {
        return .get(block);
    }
    
    public BasicBlock getEntryBB() {
        return ;
    }
    
    public BasicBlock getExitBB() {
        return ;
    }
    public BasicBlock getGlobalEnsureBB() {
        return ;
    }
    
        return ;
    }
    
    public LinkedList<BasicBlockpostOrderList() {
        if ( == null = buildPostOrderList();
        return ;
    }
    
        return postOrderList().listIterator();
    }
        return postOrderList().listIterator(size());
    }    
    public void resetState() {
        // SSS FIXME: anything else?
         = null;
    }
    
    public IRScope getScope() {
        return ;
    }    
    
    public int size() {
        return .size();
    }
    
    public Collection<BasicBlockgetBasicBlocks() {
        return .allData();
    }
    
        return .getInorderData();
    }
    
    public void addEdge(BasicBlock sourceBasicBlock destinationObject type) {
        .vertexFor(source).addEdgeTo(destinationtype);
    }
    public int inDegree(BasicBlock b) {
        return .findVertexFor(b).inDegree();
    }
    public int outDegree(BasicBlock b) {
        return .findVertexFor(b).outDegree();
    }
    
        return .findVertexFor(block).getIncomingSourcesData();
    }
    
    public Iterable<Edge<BasicBlock>> getIncomingEdges(BasicBlock block) {
        return .findVertexFor(block).getIncomingEdges();
    }
    
    public BasicBlock getIncomingSource(BasicBlock block) {
        return .findVertexFor(block).getIncomingSourceData();
    }    
    
    public BasicBlock getIncomingSourceOfType(BasicBlock blockObject type) {
        return .findVertexFor(block).getIncomingSourceDataOfType(type);
    }
    
    public Edge<BasicBlockgetIncomingEdgeOfType(BasicBlock blockObject type) {
        return .findVertexFor(block).getIncomingEdgeOfType(type);
    }
    public Edge<BasicBlockgetOutgoingEdgeOfType(BasicBlock blockObject type) {
        return .findVertexFor(block).getOutgoingEdgeOfType(type);
    }
    
    public BasicBlock getOutgoingDestination(BasicBlock block) {
        return .findVertexFor(block).getOutgoingDestinationData();
    }    
    
    public BasicBlock getOutgoingDestinationOfType(BasicBlock blockObject type) {
        return .findVertexFor(block).getOutgoingDestinationDataOfType(type);
    }
    
        return .findVertexFor(block).getOutgoingDestinationsData();
    }
    
        return .findVertexFor(block).getOutgoingDestinationsDataOfType(type);
    }
    
        return .findVertexFor(block).getOutgoingDestinationsDataNotOfType(type);
    }
    
    public Set<Edge<BasicBlock>> getOutgoingEdges(BasicBlock block) {
        return .findVertexFor(block).getOutgoingEdges();
    }
    
        return .findVertexFor(block).getOutgoingEdgesNotOfType(type);
    }
    
    public BasicBlock getRescuerBBFor(BasicBlock block) {
        return .get(block);
    }
    
    /* Add 'b' as a global ensure block that protects all unprotected blocks in this scope */
    public void addGlobalEnsureBB(BasicBlock geb) {
        assert  == null"CFG for scope " + getScope() + " already has a global ensure block.";
         = geb;
        addEdge(gebgetExitBB(), .);
        
        for (BasicBlock basicBlockgetBasicBlocks()) {
            if (basicBlock != geb && !bbIsProtected(basicBlock)) {
                addEdge(basicBlockgeb.);
                setRescuerBB(basicBlockgeb);
                setEnsurerBB(basicBlockgeb);
            }
        }
    }     
    public void setEnsurerBB(BasicBlock blockBasicBlock ensureBlock) {
        .put(blockensureBlock);
    }
    
    public void setRescuerBB(BasicBlock blockBasicBlock exceptionBlock) {
        .put(blockexceptionBlock);
    }
    
    
Build the Control Flow Graph
    public DirectedGraph<BasicBlockbuild(List<Instrinstrs) {
        // Map of label & basic blocks which are waiting for a bb with that label
        Map<LabelList<BasicBlock>> forwardRefs = new HashMap<LabelList<BasicBlock>>();
        // Map of return address variable and all possible targets (required to connect up ensure blocks with their targets)
        Map<VariableSet<Label>> retAddrMap = new HashMap<VariableSet<Label>>();
        Map<VariableBasicBlockretAddrTargetMap = new HashMap<VariableBasicBlock>();
        // List of bbs that have a 'return' instruction
        List<BasicBlockreturnBBs = new ArrayList<BasicBlock>();
        // List of bbs that have a 'throw' instruction
        List<BasicBlockexceptionBBs = new ArrayList<BasicBlock>();
        // Stack of nested rescue regions
        Stack<ExceptionRegionnestedExceptionRegions = new Stack<ExceptionRegion>();
        // List of all rescued regions
        List<ExceptionRegionallExceptionRegions = new ArrayList<ExceptionRegion>();
        // Dummy entry basic block (see note at end to see why)
         = createBB(nestedExceptionRegions);
        // First real bb
        BasicBlock firstBB = createBB(nestedExceptionRegions);
        // Build the rest!
        BasicBlock currBB = firstBB;
        BasicBlock newBB;
        boolean bbEnded = false;
        boolean nextBBIsFallThrough = true;
        for (Instr i : instrs) {
            Operation iop = i.getOperation();
            if (iop == .) {
                Label l = ((LabelInstri).;
                newBB = createBB(lnestedExceptionRegions);
                // Jump instruction bbs dont add an edge to the succeeding bb by default
                if (nextBBIsFallThrough.addEdge(currBBnewBB.);
                currBB = newBB;
                bbEnded = false;
                nextBBIsFallThrough = true;
                
                // Add forward reference edges
                List<BasicBlockfrefs = forwardRefs.get(l);
                if (frefs != null) {
                    for (BasicBlock b : frefs) {
                        .addEdge(bnewBB.);
                    }
                }
            } else if (bbEnded && (iop != .)) {
                newBB = createBB(nestedExceptionRegions);
                // Jump instruction bbs dont add an edge to the succeeding bb by default
                if (nextBBIsFallThrough.addEdge(currBBnewBB.); // currBB cannot be null!
                currBB = newBB;
                bbEnded = false;
                nextBBIsFallThrough = true;
            }
            if (i instanceof ExceptionRegionStartMarkerInstr) {
// SSS: Do we need this anymore?
//                currBB.addInstr(i);
                ExceptionRegionStartMarkerInstr ersmi = (ExceptionRegionStartMarkerInstri;
                ExceptionRegion rr = new ExceptionRegion(ersmi.firstRescueBlockLabelersmi.ensureBlockLabel);
                rr.addBB(currBB);
                allExceptionRegions.add(rr);
                if (nestedExceptionRegions.empty()) {
                    .add(rr);
                } else {
                    nestedExceptionRegions.peek().addNestedRegion(rr);
                }
                nestedExceptionRegions.push(rr);
            } else if (i instanceof ExceptionRegionEndMarkerInstr) {
// SSS: Do we need this anymore?
//                currBB.addInstr(i);
                nestedExceptionRegions.pop().setEndBB(currBB);
            } else if (iop.endsBasicBlock()) {
                bbEnded = true;
                currBB.addInstr(i);
                Label tgt;
                nextBBIsFallThrough = false;
                if (i instanceof BranchInstr) {
                    tgt = ((BranchInstri).getJumpTarget();
                    nextBBIsFallThrough = true;
                } else if (i instanceof JumpInstr) {
                    tgt = ((JumpInstri).getJumpTarget();
                } else if (iop.isReturn()) { // BREAK, RETURN, CLOSURE_RETURN
                    tgt = null;
                    returnBBs.add(currBB);
                } else if (i instanceof ThrowExceptionInstr) {
                    tgt = null;
                    exceptionBBs.add(currBB);
                } else if (i instanceof JumpIndirectInstr) {
                    tgt = null;
                    Set<LabelretAddrs = retAddrMap.get(((JumpIndirectInstri).getJumpTarget());
                    for (Label l : retAddrs) {
                        addEdge(currBBlforwardRefs);
                    }
                    // Record the target bb for the retaddr var for any set_addr instrs that appear later and use the same retaddr var
                    retAddrTargetMap.put(((JumpIndirectInstri).getJumpTarget(), currBB);
                } else {
                    throw new RuntimeException("Unhandled case in CFG builder for basic block ending instr: " + i);
                }
                if (tgt != nulladdEdge(currBBtgtforwardRefs);
            } else if (iop != .) {
                currBB.addInstr(i);
            }
            if (i instanceof SetReturnAddressInstr) {
                Variable v = ((SetReturnAddressInstri).getResult();
                Label tgtLbl = ((SetReturnAddressInstri).getReturnAddr();
                BasicBlock tgtBB = retAddrTargetMap.get(v);
                // If we have the target bb, add the edge
                // If not, record it for fixup later
                if (tgtBB != null) {
                    addEdge(tgtBBtgtLblforwardRefs);
                } else {
                    Set<Labeladdrs = retAddrMap.get(v);
                    if (addrs == null) {
                        addrs = new HashSet<Label>();
                        retAddrMap.put(vaddrs);
                    }
                    addrs.add(tgtLbl);
                }
            } else if (i instanceof CallBase) { // Build CFG for the closure if there exists one
                Operand closureArg = ((CallBasei).getClosureArg(getScope().getManager().getNil());
                if (closureArg instanceof WrappedIRClosure) {
                    ((WrappedIRClosureclosureArg).getClosure().buildCFG();
                }
            }
        }
        // Process all rescued regions
        for (ExceptionRegion rr : allExceptionRegions) {
            BasicBlock firstRescueBB = .get(rr.getFirstRescueBlockLabel());
            // Mark the BB as a rescue entry BB
            firstRescueBB.markRescueEntryBB();
            // 1. Tell the region that firstRescueBB is its protector!
            rr.setFirstRescueBB(firstRescueBB);
            // 2. Record a mapping from the region's exclusive basic blocks to the first bb that will start exception handling for all their exceptions.
            // 3. Add an exception edge from every exclusive bb of the region to firstRescueBB
            BasicBlock ensureBlockBB = rr.getEnsureBlockLabel() == null ? null : .get(rr.getEnsureBlockLabel());
            for (BasicBlock b : rr.getExclusiveBBs()) {
                .put(bfirstRescueBB);
                .addEdge(bfirstRescueBB.);
                if (ensureBlockBB != null) {
                    .put(bensureBlockBB);
                    if (ensureBlockBB != firstRescueBB) {
                        // SSS FIXME: This is a conservative edge because when a rescue block is present
                        // that catches an exception, control never reaches the ensure block directly.
                        // Only when we get an error or threadkill even, or when breaks propagate upward
                        // do we need to hit an ensure directly.  This edge is present to account for that
                        // control-flow scenario.
                        .addEdge(bensureBlockBB.);
                    }
                }
            }
        }
        
        buildExitBasicBlock(nestedExceptionRegionsfirstBBreturnBBsexceptionBBsnextBBIsFallThroughcurrBB);
        optimize(); // remove useless cfg edges & orphaned bbs
        
        return ;
    }
    
    private void addEdge(BasicBlock srcLabel targetLabelMap<LabelList<BasicBlock>> forwardRefs) {
        BasicBlock target = .get(targetLabel);
        
        if (target != null) {
            .addEdge(srctarget.);
            return;
        } 
          
        // Add a forward reference from target -> source
        List<BasicBlockforwardReferences = forwardRefs.get(targetLabel);
        if (forwardReferences == null) {
            forwardReferences = new ArrayList<BasicBlock>();
            forwardRefs.put(targetLabelforwardReferences);
        }
        
        forwardReferences.add(src);
    }
    
    
Create special empty exit BasicBlock that all BasicBlocks will eventually flow into. All Edges to this 'dummy' BasicBlock will get marked with an edge type of EXIT. Special BasicBlocks worth noting: 1. Exceptions, Returns, Entry(why?) -> ExitBB 2. Returns -> ExitBB
    private BasicBlock buildExitBasicBlock(Stack<ExceptionRegionnestedExceptionRegionsBasicBlock firstBB
            List<BasicBlockreturnBBsList<BasicBlockexceptionBBsboolean nextIsFallThroughBasicBlock currBBBasicBlock entryBB) {
         = createBB(nestedExceptionRegions);
        
        .addEdge(entryBB.);
        .addEdge(entryBBfirstBB.);
        
        for (BasicBlock rb : returnBBs) {
            .addEdge(rb.);
        }
        
        for (BasicBlock rb : exceptionBBs) {
            .addEdge(rb.);
        }
        
        if (nextIsFallThrough.addEdge(currBB.);
        
        return ;
    }
    
    private BasicBlock createBB(Label labelStack<ExceptionRegionnestedExceptionRegions) {
        BasicBlock basicBlock = new BasicBlock(thislabel);
        addBasicBlock(basicBlock);
        
        if (!nestedExceptionRegions.empty()) nestedExceptionRegions.peek().addBB(basicBlock);
        return basicBlock;
    }
    private BasicBlock createBB(Stack<ExceptionRegionnestedExceptionRegions) {
        return createBB(.getNewLabel(), nestedExceptionRegions);
    }
   public void addBasicBlock(BasicBlock bb) {
        .vertexFor(bb); // adds vertex to graph
        .put(bb.getLabel(), bb);
   }
    
    public void removeEdge(Edge edge) {
        .removeEdge(edge);
    }    
    public void removeAllOutgoingEdgesForBB(BasicBlock b) {
    }    
    private void deleteOrphanedBlocks(DirectedGraph<BasicBlockgraph) {
        // System.out.println("\nGraph:\n" + toStringGraph());
        // System.out.println("\nInstructions:\n" + toStringInstrs());
        // FIXME: Quick and dirty implementation
        while (true) {
            BasicBlock bbToRemove = null;
            for (BasicBlock b : graph.allData()) {
                if (b == continue// Skip entry bb!
                // Every other bb should have at least one incoming edge
                if (graph.findVertexFor(b).getIncomingEdges().isEmpty()) {
                    bbToRemove = b;
                    break;
                }
            }
            if (bbToRemove == nullbreak;
            removeBB(bbToRemove);
        }
    }    
    private boolean mergeBBs(BasicBlock aBasicBlock b) {
        BasicBlock aR = getRescuerBBFor(a);
        BasicBlock bR = getRescuerBBFor(b);
        // We can merge 'a' and 'b' if one of the following is true:
        // 1. 'a' and 'b' are both not empty
        //    They are protected by the same rescue block.
        //    NOTE: We need not check the ensure block map because all ensure blocks are already
        //    captured in the bb rescue block map.  So, if aR == bR, it is guaranteed that the
        //    ensure blocks for the two are identical.
        // 2. One of 'a' or 'b' is empty.  We dont need to check for rescue block match because
        //    an empty basic block cannot raise an exception, can it.
        if ((aR == bR) || a.isEmpty() || b.isEmpty()) {
            // First, remove straight-line jump, if present
            Instr lastInstr = a.getLastInstr();
            if (lastInstr instanceof JumpInstra.removeInstr(lastInstr);
            // Swallow b's instrs.
            a.swallowBB(b);
            // Fixup edges
            removeEdge(ab);
            for (Edge<BasicBlocke : getOutgoingEdges(b)) {
                addEdge(ae.getDestination().getData(), e.getType());
            }
            // Delete bb
            removeBB(b);
            // Update rescue and ensure maps
            if ((aR == null) && (bR != null)) {
                setRescuerBB(abR);
                BasicBlock aE = getEnsurerBBFor(a);
                BasicBlock bE = getEnsurerBBFor(b);
                if ((aE == null) && (bE != null)) setRescuerBB(abE);
            }
            return true;
        } else {
            return false;
        }
    }
     
    public void removeBB(BasicBlock b) {
        .removeVertexFor(b);
        .remove(b.getLabel());
        .remove(b);
        .remove(b);
        // SSS FIXME: Patch up rescued regions as well??
    }
    public void collapseStraightLineBBs() {
        // Collect cfgs in a list first since the cfg/graph API returns an iterator
        // over live data.  But, basic block merging modifies that live data.
        //
        // SSS FIXME: So, we need a cfg/graph API that returns an iterator over
        // frozen data rather than live data.
        List<BasicBlockcfgBBs = new ArrayList<BasicBlock>();
        for (BasicBlock bgetBasicBlocks()) cfgBBs.add(b);
        Set<BasicBlockmergedBBs = new HashSet<BasicBlock>();
        for (BasicBlock bcfgBBs) {
            if (!mergedBBs.contains(b) && (outDegree(b) == 1)) {
                for (Edge<BasicBlocke : getOutgoingEdges(b)) {
                    BasicBlock outB = e.getDestination().getData();
                    if ((e.getType() != .) && (inDegree(outB) == 1) && (mergeBBs(boutB) == true)) {
                        mergedBBs.add(outB);
                    }
                }
            }
        }
    }
    
    private void optimize() {
        // SSS FIXME: Can't we not add some of these exception edges in the first place??
        // Remove exception edges from blocks that couldn't possibly thrown an exception!
        List<EdgetoRemove = new ArrayList<Edge>();
        for (BasicBlock b : .allData()) {
            boolean noExceptions = true;
            for (Instr i : b.getInstrs()) {
                if (i.canRaiseException()) {
                    noExceptions = false;
                    break;
                }
            }
            if (noExceptions) {
                for (Edge<BasicBlocke : .findVertexFor(b).getOutgoingEdgesOfType(.)) {
                    BasicBlock source = e.getSource().getData();
                    BasicBlock destination = e.getDestination().getData();
                    toRemove.add(e);
                        
                    if (.get(source) == destination.remove(source);
                    if (.get(source) == destination.remove(source);
                }
            }
        }
        if (!toRemove.isEmpty()) {
            for (Edge edgetoRemove) {
                .removeEdge(edge);
            }
        }
        deleteOrphanedBlocks();
        collapseStraightLineBBs();
    }
    public String toStringGraph() {
        return .toString();
    }
    
    public String toStringInstrs() {
        StringBuilder buf = new StringBuilder();
        
        for (BasicBlock b : getSortedBasicBlocks()) {
            buf.append(b.toStringInstrs());
        }
        buf.append("\n\n------ Rescue block map ------\n");
        for (BasicBlock bb : .keySet()) {
            buf.append("BB ").append(bb.getID()).append(" --> BB ").append(.get(bb).getID()).append("\n");
        }
        buf.append("\n\n------ Ensure block map ------\n");
        for (BasicBlock bb : .keySet()) {
            buf.append("BB ").append(bb.getID()).append(" --> BB ").append(.get(bb).getID()).append("\n");
        }
        List<IRClosureclosures = .getClosures();
        if (!closures.isEmpty()) {
            buf.append("\n\n------ Closures encountered in this scope ------\n");
            for (IRClosure c : closures) {
                buf.append(c.toStringBody());
            }
            buf.append("------------------------------------------------\n");
        }
        return buf.toString();
    }
    public void removeEdge(BasicBlock aBasicBlock b) {
       .removeEdge(ab);
    }
        BasicBlock             root    = getEntryBB();
        LinkedList<BasicBlocklist    = new LinkedList<BasicBlock>();
        Stack<BasicBlock>      stack   = new Stack<BasicBlock>();
        BitSet                 visited = new BitSet(1 + getMaxNodeID());
        stack.push(root);
        visited.set(root.getID());
        // Non-recursive post-order traversal (the added flag is required to handle cycles and common ancestors)
        while (!stack.empty()) {
            // Check if all children of the top of the stack have been added
            BasicBlock b = stack.peek();
            boolean allChildrenVisited = true;
            for (BasicBlock dstgetOutgoingDestinations(b)) {
                int dstID = dst.getID();
                if (!visited.get(dstID)) {
                    allChildrenVisited = false;
                    // This ensures that no matter what order we visit children, we process exit nodes before anything.
                    // else.  Alternatively, getOutgoingDestinations(..) would have to return nodes in a specific order
                    // that is dependent on basic block numbering -- which would be fragile.
                    if (.findVertexFor(dst).outDegree() == 0) {
                        list.add(dst);
                    } else {
                        stack.push(dst);
                    }
                    visited.set(dstID);
                }
            }
            // If all children have been added previously, we are ready with 'b' in this round!
            if (allChildrenVisited) {
                stack.pop();
                list.add(b);
            }
        }
        // Sanity check!
        for (BasicBlock b : getBasicBlocks()) {
            if (!visited.get(b.getID())) {
                printError("BB " + b.getID() + " missing from po list!");
                break;
            }
        }
        
        return list;
    }    
    public CFG cloneForCloningClosure(IRScope scopeInlinerInfo ii) {
        Map<BasicBlockBasicBlockcloneBBMap = new HashMap<BasicBlockBasicBlock>();
        CFG clone = new CFG(scope);
        // clone bbs
        for (BasicBlock b : getBasicBlocks()) {
            BasicBlock bCloned = new BasicBlock(cloneb.getLabel().clone());
            for (Instr ib.getInstrs()) {
                Instr clonedInstr = i.cloneForBlockCloning(ii);
                if (clonedInstr != nullbCloned.addInstr(clonedInstr);
            }
            clone.addBasicBlock(bCloned);
            cloneBBMap.put(bbCloned);
        }
        // clone edges
        for (BasicBlock x : getBasicBlocks()) {
             BasicBlock rx = cloneBBMap.get(x);
             for (Edge<BasicBlocke : getOutgoingEdges(x)) {
                 BasicBlock b = e.getDestination().getData();
                 clone.addEdge(rxcloneBBMap.get(b), e.getType());
             }
        }
        clone.entryBB = cloneBBMap.get();
        clone.exitBB  = cloneBBMap.get();
        // SSS FIXME: Is this required after cfg is built?
        clone.outermostERs = null;
        // Clone rescuer map
        for (BasicBlock b.keySet()) {
            clone.rescuerMap.put(cloneBBMap.get(b), cloneBBMap.get(.get(b)));
        }
        // Clone ensurer map
        for (BasicBlock b.keySet()) {
            clone.ensurerMap.put(cloneBBMap.get(b), cloneBBMap.get(.get(b)));
        }
        return clone;
    }
    
    private void printError(String message) {
        .error(message + "\nGraph:\n" + this + "\nInstructions:\n" + toStringInstrs());
    }      
New to GrepCode? Check out our FAQ X