Package EDU.purdue.cs.bloat.cfg

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.

Field Summary

Fields inherited from class EDU.purdue.cs.bloat.tree.TreeVisitor

FORWARD, REVERSE

Constructor Summary

Constructors

Constructor	Description
VerifyCFG()	Constructor.
VerifyCFG(boolean checkValueNumbers)	Constructor.

Method Summary

Modifier and Type	Method	Description
void	visitBlock(Block block)	First make sure that the Block indeed is in the CFG.
void	visitDefExpr(DefExpr expr)	Keep track of all the uses of the expression defined by the DefExpr.
void	visitExpr(Expr expr)	If desired, make sure that the value number of the Expr is not -1.
void	visitFlowGraph(FlowGraph cfg)	Visit the blocks and expression trees in a control flow graph.
void	visitGotoStmt(GotoStmt stmt)	Make sure that the target of goto is valid.
void	visitIfStmt(IfStmt stmt)	Make sure that the targets of the if statement are valid.
void	visitJsrStmt(JsrStmt stmt)	Make sure that all of the targets of the jsr are valid.
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.
void	visitRetStmt(RetStmt stmt)	Make sure that all of targets of the ret are valid.
void	visitStoreExpr(StoreExpr node)	If desired, makes sure that the store expression's value number is not -1.
void	visitSwitchStmt(SwitchStmt stmt)	Make sure that that all of the targets of the switch are valid.
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).

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Methods inherited from class EDU.purdue.cs.bloat.tree.TreeVisitor

direction, forward, prune, reverse, setPrune, visitAddressStoreStmt, visitArithExpr, visitArrayLengthExpr, visitArrayRefExpr, visitCallExpr, visitCallMethodExpr, visitCallStaticExpr, visitCastExpr, visitCatchExpr, visitCheckExpr, visitConstantExpr, visitExprStmt, visitFieldExpr, visitIfCmpStmt, visitIfZeroStmt, visitInitStmt, visitInstanceOfExpr, visitLabelStmt, visitLocalExpr, visitMemExpr, visitMemRefExpr, visitMonitorStmt, visitNegExpr, visitNewArrayExpr, visitNewExpr, visitNewMultiArrayExpr, visitPhiCatchStmt, visitPhiJoinStmt, visitPhiStmt, visitRCExpr, visitReturnAddressExpr, visitReturnExprStmt, visitReturnStmt, visitSCStmt, visitShiftExpr, visitSRStmt, visitStackExpr, visitStackManipStmt, visitStaticFieldExpr, visitStmt, visitThrowStmt, visitTree, visitUCExpr, visitZeroCheckExpr

Constructor Detail

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 Detail

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