Interface ISupergraph<T,​P>

  • All Superinterfaces:
    EdgeManager<T>, Graph<T>, Iterable<T>, NodeManager<T>, NumberedEdgeManager<T>, NumberedGraph<T>, NumberedNodeManager<T>
    All Known Implementing Classes:
    BackwardsSupergraph, ICFGSupergraph

    public interface ISupergraph<T,​P>
    extends NumberedGraph<T>
    A supergraph as defined by Reps, Horwitz, and Sagiv POPL95

    In our implementation we don't require explicit entry and exit nodes. So, the first basic block in a method is implicitly the entry node, but might also be a call node too. Similarly for exit nodes. The solver is coded to deal with this appropriately.

    Additionally, due to exceptional control flow, each method might have multiple exits or multiple entries. T type of node in the supergraph P type of a procedure (like a box in an RSM)

    • Method Detail

      • getProcedureGraph

        Graph<? extends P> getProcedureGraph()
        Returns:
        the graph of procedures (e.g. a call graph) over which this supergraph is induced.
      • isCall

        boolean isCall​(T n)
        Parameters:
        n - a node in this supergraph
        Returns:
        true iff this node includes a call.
      • getCalledNodes

        Iterator<? extends T> getCalledNodes​(T call)
        Parameters:
        call - a "call" node in the supergraph
        Returns:
        an Iterator of nodes that are targets of this call.
      • getNormalSuccessors

        Iterator<T> getNormalSuccessors​(T call)
        Parameters:
        call - a "call" node in the supergraph
        Returns:
        an Iterator of nodes that are normal (non-call) successors of this call. This should only apply to backwards problems, where we might have, say, a call and a goto flow into a return site.
      • getReturnSites

        Iterator<? extends T> getReturnSites​(T call,
                                             P callee)
        Parameters:
        call - a "call" node in the supergraph
        callee - a "called" "procedure" in the supergraph. if callee is null, answer return sites for which no callee was found.
        Returns:
        the corresponding return nodes. There may be many, because of exceptional control flow.
      • getCallSites

        Iterator<? extends T> getCallSites​(T ret,
                                           P callee)
        Parameters:
        r - a "return" node in the supergraph
        callee - a "called" "procedure" in the supergraph. if callee is null, answer return sites for which no callee was found.
        Returns:
        the corresponding call nodes. There may be many.
      • isExit

        boolean isExit​(T n)
        Parameters:
        n - a node in the supergraph
        Returns:
        true iff this node is an exit node
      • getProcOf

        P getProcOf​(T n)
        Parameters:
        n - a node in the supergraph
        Returns:
        an object which represents the procedure which contains n
      • getEntriesForProcedure

        T[] getEntriesForProcedure​(P procedure)
        Returns:
        the blocks in the supergraph that represents entry nodes for procedure p
      • getExitsForProcedure

        T[] getExitsForProcedure​(P procedure)
        Returns:
        the blocks in the supergraph that represents exit nodes for procedure p
      • getNumberOfBlocks

        int getNumberOfBlocks​(P procedure)
        Parameters:
        procedure - an object that represents a procedure
        Returns:
        the number of blocks from this procedure in this supergraph
      • getLocalBlockNumber

        int getLocalBlockNumber​(T n)
        Parameters:
        n - a node in the supergraph
        Returns:
        the "logical" basic block number of n in its procedure
      • getLocalBlock

        T getLocalBlock​(P procedure,
                        int i)
        Parameters:
        procedure - an object that represents a procedure
        i - the "logical" basic block number of a node in the procedure
        Returns:
        the corresponding node in the supergraph
      • isReturn

        boolean isReturn​(T n)
        Parameters:
        n - a node in this supergraph
        Returns:
        true iff this node is a return site.
      • isEntry

        boolean isEntry​(T n)
        Returns:
        true iff this node is an entry node s_p for a procedure
      • classifyEdge

        byte classifyEdge​(T src,
                          T dest)
        Parameters:
        src - node in the supergraph
        dest - a successor of src in the supergraph
        Returns:
        one of CALL_EDGE, RETURN_EDGE, CALL_TO_RETURN_EDGE, or OTHER