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)

  • Field Details

  • Method Details

    • getProcedureGraph

      Graph<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:
      ret - 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