Class VerifyCFG

java.lang.Object
EDU.purdue.cs.bloat.tree.TreeVisitor
EDU.purdue.cs.bloat.cfg.VerifyCFG
public class VerifyCFG extends TreeVisitor
VerifyCFG visits the nodes in a control flow graph and verifies that certain properties of the graph are true. For instance, value numbers of expressions are not equal to -1, node connections are consistent, exception handlers are set up correctly, etc. Mostly used for debugging purposes.

  • Constructor Details

    • VerifyCFG

      public VerifyCFG()
      Constructor. Don't check value numbers.

    • VerifyCFG

      public VerifyCFG(boolean checkValueNumbers)
      Constructor. Since value numbers are not strictly part of the control flow graph, they may or may not be checked. For instance, if a CFG is being verfied before value numbers are assigned, we would not want to check them.
      Parameters:
      checkValueNumbers - Are the value numbers of expressions checked?

  • Method Details

    • visitFlowGraph

      public void visitFlowGraph(FlowGraph cfg)
      Visit the blocks and expression trees in a control flow graph. Examine the uses of a variable that is defined in the CFG. Make that all uses are reachable (i.e. are in the CFG).
      Overrides:
      visitFlowGraph in class TreeVisitor

    • visitBlock

      public void visitBlock(Block block)
      First make sure that the Block indeed is in the CFG. If the block begins an exception handler, then make sure that all edges from protected blocks lead to the handler block. Also make sure that all of the handler block's predacessor lead to protected blocks. Finally, make sure that the successor/predacessor relationship holds.
      Overrides:
      visitBlock in class TreeVisitor

    • visitRetStmt

      public void visitRetStmt(RetStmt stmt)
      Make sure that all of targets of the ret are valid. The targets are the blocks to which the subroutine can return.
      Overrides:
      visitRetStmt in class TreeVisitor

    • visitJsrStmt

      public void visitJsrStmt(JsrStmt stmt)
      Make sure that all of the targets of the jsr are valid. The only target is the entry block of the subroutine.
      Overrides:
      visitJsrStmt in class TreeVisitor

    • visitSwitchStmt

      public void visitSwitchStmt(SwitchStmt stmt)
      Make sure that that all of the targets of the switch are valid.
      Overrides:
      visitSwitchStmt in class TreeVisitor

    • visitIfStmt

      public void visitIfStmt(IfStmt stmt)
      Make sure that the targets of the if statement are valid. Targets consist of the true target, the false target, and the first blocks of any exceptions that may be thrown by the if statement.
      Overrides:
      visitIfStmt in class TreeVisitor

    • visitGotoStmt

      public void visitGotoStmt(GotoStmt stmt)
      Make sure that the target of goto is valid.
      Overrides:
      visitGotoStmt in class TreeVisitor

    • visitStoreExpr

      public void visitStoreExpr(StoreExpr node)
      If desired, makes sure that the store expression's value number is not -1. Makes sure that the store expression's block and parent Node are what we expect them to be. If the type of the StoreExpr is void, then make sure that its parent is an ExprStmt (i.e. make sure it is not nested within another expression).
      Overrides:
      visitStoreExpr in class TreeVisitor

    • visitNode

      public void visitNode(Node node)
      Make sure that the Node resides in the block that we expect it to and that it has the expected parent expression tree Node. Make sure that the children of this Node are also correct.
      Overrides:
      visitNode in class TreeVisitor

    • visitExpr

      public void visitExpr(Expr expr)
      If desired, make sure that the value number of the Expr is not -1.
      Overrides:
      visitExpr in class TreeVisitor

    • visitDefExpr

      public void visitDefExpr(DefExpr expr)
      Keep track of all the uses of the expression defined by the DefExpr. This information is used when verifying the FlowGraph.
      Overrides:
      visitDefExpr in class TreeVisitor

    • visitVarExpr

      public void visitVarExpr(VarExpr expr)
      Make sure that the VarExpr either defines a local variable, is defined by another expression, or is the child of a PhiStmt (therefore making the VarExpr a phi-variable).
      Overrides:
      visitVarExpr in class TreeVisitor