001: /* Copyright (C) 2004 - 2007 db4objects Inc. http://www.db4o.com
002:
003: This file is part of the db4o open source object database.
004:
005: db4o is free software; you can redistribute it and/or modify it under
006: the terms of version 2 of the GNU General Public License as published
007: by the Free Software Foundation and as clarified by db4objects' GPL
008: interpretation policy, available at
009: http://www.db4o.com/about/company/legalpolicies/gplinterpretation/
010: Alternatively you can write to db4objects, Inc., 1900 S Norfolk Street,
011: Suite 350, San Mateo, CA 94403, USA.
012:
013: db4o is distributed in the hope that it will be useful, but WITHOUT ANY
014: WARRANTY; without even the implied warranty of MERCHANTABILITY or
015: FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
016: for more details.
017:
018: You should have received a copy of the GNU General Public License along
019: with this program; if not, write to the Free Software Foundation, Inc.,
020: 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */
021: package EDU.purdue.cs.bloat.cfg;
022:
023: import java.util.*;
024:
025: import EDU.purdue.cs.bloat.tree.*;
026: import EDU.purdue.cs.bloat.util.*;
027:
028: /**
029: * VerifyCFG visits the nodes in a control flow graph and verifies that certain
030: * properties of the graph are true. For instance, value numbers of expressions
031: * are not equal to -1, node connections are consistent, exception handlers are
032: * set up correctly, etc. Mostly used for debugging purposes.
033: */
034: public class VerifyCFG extends TreeVisitor {
035: Block block; // The Block containing the node being visited
036:
037: Node parent; // The (expected) parent of the node being visited
038:
039: FlowGraph cfg; // The CFG being visited
040:
041: Set uses; // Expressions in which a definition is used
042:
043: Set nodes; // (Visited) nodes in the CFG
044:
045: boolean checkValueNumbers; // Do we check the value numbers of expressions?
046:
047: /**
048: * Constructor. Don't check value numbers.
049: */
050: public VerifyCFG() {
051: this (false);
052: }
053:
054: /**
055: * Constructor. Since value numbers are not strictly part of the control
056: * flow graph, they may or may not be checked. For instance, if a CFG is
057: * being verfied before value numbers are assigned, we would not want to
058: * check them.
059: *
060: * @param checkValueNumbers
061: * Are the value numbers of expressions checked?
062: */
063: public VerifyCFG(final boolean checkValueNumbers) {
064: this .checkValueNumbers = checkValueNumbers;
065: }
066:
067: /**
068: * Visit the blocks and expression trees in a control flow graph. Examine
069: * the uses of a variable that is defined in the CFG. Make that all uses are
070: * reachable (i.e. are in the CFG).
071: */
072: public void visitFlowGraph(final FlowGraph cfg) {
073: if (FlowGraph.DEBUG) {
074: System.out.println("Verifying CFG for " + cfg.method());
075: }
076:
077: this .cfg = cfg;
078:
079: uses = new HashSet();
080: nodes = new HashSet();
081:
082: cfg.visitChildren(this );
083:
084: final Iterator e = uses.iterator();
085:
086: while (e.hasNext()) {
087: final Expr use = (Expr) e.next();
088: Assert.isTrue(nodes.contains(use), "use = " + use + " ("
089: + System.identityHashCode(use)
090: + ") is not in the CFG");
091: }
092:
093: if (FlowGraph.DEBUG) {
094: System.out.println("Verification successful");
095: }
096:
097: this .cfg = null;
098: uses = null;
099: nodes = null;
100: block = null;
101: parent = null;
102: }
103:
104: /**
105: * First make sure that the <tt>Block</tt> indeed is in the CFG. If the
106: * block begins an exception handler, then make sure that all edges from
107: * protected blocks lead to the handler block. Also make sure that all of
108: * the handler block's predacessor lead to protected blocks. Finally, make
109: * sure that the successor/predacessor relationship holds.
110: */
111: public void visitBlock(final Block block) {
112: Assert.isTrue(block.graph() == cfg, block
113: + " is not in the CFG");
114:
115: Iterator e;
116:
117: final Handler handler = (Handler) cfg.handlersMap().get(block);
118:
119: // If this block is the first block in an exception handler, make
120: // sure that the only predacessor edges the block has are
121: // protected blocks that may throw the exception handled by the
122: // block. Additionally, we check that there are edges from all
123: // protected blocks to the handler block.
124: //
125: // The predacessor to the first block in an exception handler may
126: // be the init block. However, it is not really a protected
127: // block, so just overlook it.
128:
129: if (handler != null) {
130: final HashSet handlerPreds = new HashSet();
131:
132: e = handler.protectedBlocks().iterator();
133:
134: while (e.hasNext()) {
135: final Block prot = (Block) e.next();
136: handlerPreds.add(prot);
137: handlerPreds.addAll(cfg.preds(prot));
138: }
139:
140: final HashSet extra = new HashSet(cfg.preds(block));
141: extra.removeAll(handlerPreds);
142: final HashSet missing = new HashSet(handlerPreds);
143: missing.removeAll(cfg.preds(block));
144:
145: Assert.isTrue(
146: ((extra.size() == 0) && (missing.size() == 0))
147: || ((missing.size() == 1) && missing
148: .contains(cfg.init())),
149: "Handler prots = " + handlerPreds
150: + " != handler block preds = "
151: + cfg.preds(block) + " extra = " + extra
152: + " missing = " + missing);
153: }
154:
155: // Make sure that the predacessor has a successor and vice versa.
156: e = cfg.preds(block).iterator();
157:
158: while (e.hasNext()) {
159: final Block pred = (Block) e.next();
160: Assert.isTrue(cfg.succs(pred).contains(block), pred
161: + " has no succ " + block);
162: Assert.isTrue(cfg.preds(block).contains(pred), block
163: + " has no pred " + pred);
164: }
165:
166: e = cfg.succs(block).iterator();
167:
168: while (e.hasNext()) {
169: final Block succ = (Block) e.next();
170: Assert.isTrue(cfg.succs(block).contains(succ), block
171: + " has no succ " + succ);
172: Assert.isTrue(cfg.preds(succ).contains(block), succ
173: + " has no pred " + block);
174: }
175:
176: this .block = block;
177:
178: parent = null;
179: block.visitChildren(this );
180: }
181:
182: /**
183: * Make sure that all of targets of the <tt>ret</tt> are valid. The
184: * targets are the blocks to which the subroutine can return.
185: */
186: public void visitRetStmt(final RetStmt stmt) {
187: final Set targets = new HashSet();
188:
189: final Iterator iter = stmt.sub().paths().iterator();
190:
191: while (iter.hasNext()) {
192: final Block[] path = (Block[]) iter.next();
193: targets.add(path[1]);
194: }
195:
196: targets.addAll(stmt.catchTargets());
197:
198: verifyTargets(stmt.block(), targets);
199:
200: visitNode(stmt);
201: }
202:
203: /**
204: * Make sure that all of the targets of the <tt>jsr</tt> are valid. The
205: * only target is the entry block of the subroutine.
206: */
207: public void visitJsrStmt(final JsrStmt stmt) {
208: final Set targets = new HashSet();
209: targets.add(stmt.sub().entry());
210: targets.addAll(stmt.catchTargets());
211: verifyTargets(stmt.block(), targets);
212:
213: visitNode(stmt);
214: }
215:
216: /**
217: * Make sure that that all of the targets of the switch are valid.
218: */
219: public void visitSwitchStmt(final SwitchStmt stmt) {
220: final Set targets = new HashSet();
221:
222: targets.add(stmt.defaultTarget());
223:
224: for (int i = 0; i < stmt.targets().length; i++) {
225: targets.add(stmt.targets()[i]);
226: }
227:
228: targets.addAll(stmt.catchTargets());
229:
230: verifyTargets(stmt.block(), targets);
231:
232: visitNode(stmt);
233: }
234:
235: /**
236: * Make sure that the targets of the if statement are valid. Targets consist
237: * of the true target, the false target, and the first blocks of any
238: * exceptions that may be thrown by the if statement.
239: */
240: public void visitIfStmt(final IfStmt stmt) {
241: final Set targets = new HashSet();
242: targets.add(stmt.trueTarget());
243: targets.add(stmt.falseTarget());
244: targets.addAll(stmt.catchTargets());
245: verifyTargets(stmt.block(), targets);
246:
247: visitNode(stmt);
248: }
249:
250: /**
251: * Make sure that the target of <tt>goto</tt> is valid.
252: */
253: public void visitGotoStmt(final GotoStmt stmt) {
254: final Set targets = new HashSet();
255: targets.add(stmt.target());
256: targets.addAll(stmt.catchTargets());
257: verifyTargets(stmt.block(), targets);
258:
259: visitNode(stmt);
260: }
261:
262: /**
263: * Verifies information about the targets of a jump in a given block. First,
264: * make sure that the number of targets is the same as the number of
265: * sucessor nodes to the block. Make sure that targets of all of the jumps
266: * are indeed in the CFG. Make sure that every target is a successor of the
267: * block.
268: */
269: private void verifyTargets(final Block block, final Set targets) {
270: Assert.isTrue(targets.size() == cfg.succs(block).size(), block
271: + " has succs " + cfg.succs(block) + " != " + targets
272: + " in " + block.tree().lastStmt());
273:
274: final Iterator iter = targets.iterator();
275:
276: while (iter.hasNext()) {
277: final Block target = (Block) iter.next();
278: Assert.isTrue(block.graph().hasNode(target), target
279: + " is not in the CFG");
280: Assert.isTrue(cfg.succs(block).contains(target), target
281: + " is not a succ of " + block + " "
282: + block.tree().lastStmt());
283: }
284: }
285:
286: /**
287: * If desired, makes sure that the store expression's value number is not
288: * -1. Makes sure that the store expression's block and parent <tt>Node</tt>
289: * are what we expect them to be. If the type of the <tt>StoreExpr</tt> is
290: * void, then make sure that its parent is an <tt>ExprStmt</tt> (i.e. make
291: * sure it is not nested within another expression).
292: */
293: public void visitStoreExpr(final StoreExpr node) {
294: nodes.add(node);
295:
296: if (checkValueNumbers) {
297: Assert.isTrue(node.valueNumber() != -1, node
298: + ".valueNumber() = -1");
299: }
300:
301: Assert.isTrue(node.block() == block, node + ".block() = "
302: + node.block() + " != block = " + block);
303: Assert.isTrue(node.parent() == parent, node + ".parent() = "
304: + node.parent() + " != parent = " + parent);
305:
306: // Visit the MemExpr into which node stores.
307: parent = node;
308: node.target().visit(this );
309:
310: // Visit the expression whose value is being stored by node
311: parent = node;
312: node.expr().visit(this );
313:
314: parent = node.parent();
315:
316: if (node.type().isVoid()) {
317: Assert.isTrue(parent instanceof ExprStmt, "parent of "
318: + node + " = " + parent + " is not an ExprStmt");
319: }
320: }
321:
322: /**
323: * Make sure that the <tt>Node</tt> resides in the block that we expect it
324: * to and that it has the expected parent expression tree <tt>Node</tt>.
325: * Make sure that the children of this <tt>Node</tt> are also correct.
326: */
327: public void visitNode(final Node node) {
328: nodes.add(node);
329:
330: Assert.isTrue(node.block() == block, node + ".block() = "
331: + node.block() + " != block = " + block);
332: Assert.isTrue(node.parent() == parent, node + ".parent() = "
333: + node.parent() + " != parent = " + parent);
334:
335: final ArrayList children = new ArrayList();
336:
337: node.visitChildren(new TreeVisitor() {
338: public void visitNode(final Node n) {
339: children.add(n);
340: }
341: });
342:
343: final Iterator e = children.iterator();
344:
345: while (e.hasNext()) {
346: final Node child = (Node) e.next();
347: parent = node;
348: child.visit(this );
349: }
350:
351: parent = node.parent();
352: }
353:
354: /**
355: * If desired, make sure that the value number of the <tt>Expr</tt> is not
356: * -1.
357: */
358: public void visitExpr(final Expr expr) {
359: if (checkValueNumbers) {
360: Assert.isTrue(expr.valueNumber() != -1, expr
361: + ".valueNumber() = -1");
362: }
363:
364: visitNode(expr);
365: }
366:
367: /**
368: * Keep track of all the uses of the expression defined by the
369: * <tt>DefExpr</tt>. This information is used when verifying the
370: * <tt>FlowGraph</tt>.
371: */
372: public void visitDefExpr(final DefExpr expr) {
373: uses.addAll(expr.uses());
374: visitExpr(expr);
375: }
376:
377: /**
378: * Make sure that the <tt>VarExpr</tt> either defines a local variable, is
379: * defined by another expression, or is the child of a <tt>PhiStmt</tt>
380: * (therefore making the <tt>VarExpr</tt> a phi-variable).
381: */
382: public void visitVarExpr(final VarExpr expr) {
383: Assert.isTrue(expr.isDef() || (expr.def() != null)
384: || (expr.parent() instanceof PhiStmt),
385: "Null def for variable " + expr);
386:
387: visitDefExpr(expr);
388: }
389: }
|