001: /*
002: * Bytecode Analysis Framework
003: * Copyright (C) 2003-2007 University of Maryland
004: *
005: * This library is free software; you can redistribute it and/or
006: * modify it under the terms of the GNU Lesser General Public
007: * License as published by the Free Software Foundation; either
008: * version 2.1 of the License, or (at your option) any later version.
009: *
010: * This library is distributed in the hope that it will be useful,
011: * but WITHOUT ANY WARRANTY; without even the implied warranty of
012: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
013: * Lesser General Public License for more details.
014: *
015: * You should have received a copy of the GNU Lesser General Public
016: * License along with this library; if not, write to the Free Software
017: * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
018: */
019:
020: package edu.umd.cs.findbugs.ba;
021:
022: import java.io.Serializable;
023: import java.util.Comparator;
024: import java.util.Iterator;
025: import java.util.TreeSet;
026:
027: import org.apache.bcel.generic.InstructionHandle;
028: import org.apache.bcel.generic.MethodGen;
029:
030: import edu.umd.cs.findbugs.SystemProperties;
031: import edu.umd.cs.findbugs.ba.deref.UnconditionalValueDerefAnalysis;
032: import edu.umd.cs.findbugs.ba.deref.UnconditionalValueDerefDataflow;
033: import edu.umd.cs.findbugs.ba.deref.UnconditionalValueDerefSet;
034: import edu.umd.cs.findbugs.classfile.CheckedAnalysisException;
035: import edu.umd.cs.findbugs.classfile.DescriptorFactory;
036: import edu.umd.cs.findbugs.classfile.Global;
037:
038: /**
039: * Perform dataflow analysis on a method using a control flow graph.
040: * Both forward and backward analyses can be performed.
041: * <ul>
042: * <li> The "start" point of each block is the entry (forward analyses)
043: * or the exit (backward analyses).
044: * <li> The "result" point of each block is the exit (forward analyses)
045: * or the entry (backward analyses).
046: * </ul>
047: * The analysis's transfer function is applied to transform
048: * the meet of the results of the block's logical predecessors
049: * (the block's start facts) into the block's result facts.
050: *
051: * @author David Hovemeyer
052: * @see CFG
053: * @see DataflowAnalysis
054: */
055: public class Dataflow<Fact, AnalysisType extends DataflowAnalysis<Fact>> {
056: private CFG cfg;
057: private AnalysisType analysis;
058: private BlockOrder blockOrder;
059: private boolean isForwards;
060: private int numIterations;
061:
062: public static boolean DEBUG = SystemProperties
063: .getBoolean("dataflow.debug");
064:
065: /**
066: * Constructor.
067: *
068: * @param cfg the control flow graph
069: * @param analysis the DataflowAnalysis to be run
070: */
071: public Dataflow(CFG cfg, AnalysisType analysis) {
072: this .cfg = cfg;
073: this .analysis = analysis;
074: blockOrder = analysis.getBlockOrder(cfg);
075: isForwards = analysis.isForwards();
076: numIterations = 0;
077:
078: // Initialize result facts
079: Iterator<BasicBlock> i = cfg.blockIterator();
080: while (i.hasNext()) {
081: BasicBlock block = i.next();
082:
083: Fact result = analysis.getResultFact(block);
084: if (block == logicalEntryBlock()) {
085: try {
086: // Entry block: set to entry fact
087: analysis.initEntryFact(result);
088: } catch (DataflowAnalysisException e) {
089: analysis.makeFactTop(result);
090: }
091: } else {
092: // Set to top
093: analysis.makeFactTop(result);
094: }
095: }
096: }
097:
098: // Maximum number of iterations before we assume there is a bug and give up.
099: private static final int MAX_ITERS = SystemProperties.getInteger(
100: "dataflow.maxiters", 97).intValue();
101:
102: private String getFullyQualifiedMethodName() {
103: String methodName;
104: MethodGen methodGen = cfg.getMethodGen();
105: if (methodGen == null)
106: methodName = cfg.getMethodName();
107: else
108: methodName = SignatureConverter
109: .convertMethodSignature(methodGen);
110: return methodName;
111: }
112:
113: static class ForwardProgramOrder implements Comparator<BasicBlock>,
114: Serializable {
115:
116: public int compare(BasicBlock o1, BasicBlock o2) {
117: try {
118: int p1 = o1.getLabel();
119: int p2 = o2.getLabel();
120: return p1 - p2;
121: } catch (RuntimeException e) {
122: if (false) {
123: e.printStackTrace(System.out);
124:
125: try {
126: int p1 = o1.pos();
127: int p2 = o2.pos();
128: } catch (RuntimeException e2) {
129: }
130: }
131: return o1.getLabel() - o2.getLabel();
132: }
133: }
134:
135: }
136:
137: static class BackwardProgramOrder extends ForwardProgramOrder {
138:
139: @Override
140: public int compare(BasicBlock o1, BasicBlock o2) {
141: return -super .compare(o1, o2);
142: }
143:
144: }
145:
146: /**
147: * Run the algorithm.
148: * Afterwards, caller can use the getStartFact() and getResultFact() methods to
149: * to get dataflow facts at start and result points of each block.
150: */
151: public void execute() throws DataflowAnalysisException {
152: boolean change;
153: boolean debugWas = DEBUG;
154: if (DEBUG) {
155: reportAnalysis("Executing");
156: }
157:
158: int timestamp = 0;
159: boolean firstTime = true;
160: do {
161: change = false;
162: ++numIterations;
163: if (numIterations > MAX_ITERS && !DEBUG) {
164: DEBUG = true;
165: reportAnalysis("Too many iterations");
166: System.out.println(this .getClass().getName());
167: if (this .getClass() == UnconditionalValueDerefDataflow.class
168: || this .getClass() == LiveLocalStoreDataflow.class) {
169: try {
170: ClassContext cc = Global
171: .getAnalysisCache()
172: .getClassAnalysis(
173: ClassContext.class,
174: DescriptorFactory
175: .createClassDescriptorFromDottedClassName(cfg
176: .getMethodGen()
177: .getClassName()));
178: System.out.println("Forwards cfg");
179: CFGPrinter printer = new CFGPrinter(cfg);
180: printer.setIsForwards(true);
181: printer.print(System.out);
182: System.out.println("Backwards cfg");
183: printer = new CFGPrinter(cfg);
184: printer.setIsForwards(false);
185: printer.print(System.out);
186: cc.dumpSimpleDataflowInformation(cfg
187: .getMethodGen().getMethod());
188: } catch (CheckedAnalysisException e) {
189: e.printStackTrace(System.out);
190: }
191: }
192: }
193:
194: if (DEBUG) {
195: System.out
196: .println("----------------------------------------------------------------------");
197: System.out.println(this .getClass().getName()
198: + " iteration: " + numIterations
199: + ", timestamp: " + timestamp);
200: MethodGen mg = cfg.getMethodGen();
201: System.out.println(mg.getClassName() + "."
202: + mg.getName() + mg.getSignature());
203: System.out
204: .println("----------------------------------------------------------------------");
205:
206: }
207:
208: if (numIterations >= MAX_ITERS + 9) {
209: throw new AssertionError("Too many iterations ("
210: + numIterations
211: + ") in dataflow when analyzing "
212: + getFullyQualifiedMethodName());
213: }
214:
215: analysis.startIteration();
216:
217: if (DEBUG && firstTime
218: && blockOrder instanceof ReverseDFSOrder) {
219: ReverseDFSOrder rBlockOrder = (ReverseDFSOrder) blockOrder;
220: System.out.println("Entry point is: "
221: + logicalEntryBlock());
222: System.out.println("Basic block order: ");
223: Iterator<BasicBlock> i = blockOrder.blockIterator();
224: while (i.hasNext()) {
225:
226: BasicBlock block = i.next();
227: debug(block, "rBlockOrder "
228: + rBlockOrder.rdfs.getDiscoveryTime(block)
229: + "\n");
230: }
231: }
232: Iterator<BasicBlock> i = blockOrder.blockIterator();
233: if (numIterations > 3 && numIterations % 2 == 0
234: && blockOrder instanceof ReverseDFSOrder) {
235: if (DEBUG)
236: System.out.println("Trying program order");
237: TreeSet<BasicBlock> bb = new TreeSet<BasicBlock>(
238: new BackwardProgramOrder());
239: Iterator<BasicBlock> j = blockOrder.blockIterator();
240: while (j.hasNext()) {
241: BasicBlock block = j.next();
242: bb.add(block);
243: }
244: if (DEBUG)
245: for (BasicBlock block : bb) {
246: debug(block, "\n");
247: }
248: i = bb.iterator();
249: }
250: if (DEBUG)
251: dumpDataflow(analysis);
252:
253: // For each block in CFG...
254:
255: while (i.hasNext()) {
256:
257: BasicBlock block = i.next();
258:
259: // Get start fact for block.
260: Fact start = analysis.getStartFact(block);
261: assert start != null;
262:
263: boolean needToRecompute = false;
264: // Get result facts for block,
265: Fact result = analysis.getResultFact(block);
266: assert result != null;
267:
268: int originalResultTimestamp = analysis
269: .getLastUpdateTimestamp(result);
270:
271: // Meet all of the logical predecessor results into this block's start.
272: // Special case: if the block is the logical entry, then it gets
273: // the special "entry fact".
274: if (block == logicalEntryBlock()) {
275: analysis.makeFactTop(start);
276: analysis.initEntryFact(start);
277: if (DEBUG)
278: debug(block, "Init entry fact ==> "
279: + analysis.factToString(start) + "\n");
280: needToRecompute = true;
281: } else {
282: int lastCalculated = analysis
283: .getLastUpdateTimestamp(start);
284: Iterator<Edge> predEdgeIter = logicalPredecessorEdgeIterator(block);
285:
286: int predCount = 0;
287: int rawPredCount = 0;
288: while (predEdgeIter.hasNext()) {
289: Edge edge = predEdgeIter.next();
290: rawPredCount++;
291: if (needToRecompute)
292: continue;
293: BasicBlock logicalPred = isForwards ? edge
294: .getSource() : edge.getTarget();
295:
296: // Get the predecessor result fact
297: Fact predFact = analysis
298: .getResultFact(logicalPred);
299: int predLastUpdated = analysis
300: .getLastUpdateTimestamp(predFact);
301: if (!analysis.isTop(predFact)) {
302: predCount++;
303: if (predLastUpdated >= lastCalculated) {
304:
305: needToRecompute = true;
306: if (DEBUG) {
307: debug(
308: block,
309: "\n Need to recompute. My timestamp = "
310: + lastCalculated
311: + ", pred timestamp = "
312: + predLastUpdated
313: + ",\n pred fact = "
314: + predFact + "\n");
315: }
316: // break;
317: }
318: }
319: }
320: if (predCount == 0)
321: needToRecompute = true;
322:
323: if (!needToRecompute) {
324: if (false && DEBUG) {
325: debug(block,
326: "Skipping: predecessors haven't changed");
327: System.out.println(" curr timestamp: "
328: + timestamp);
329: System.out.println(" last timestamp: "
330: + lastCalculated);
331: predEdgeIter = logicalPredecessorEdgeIterator(block);
332:
333: while (predEdgeIter.hasNext()) {
334: Edge edge = predEdgeIter.next();
335: BasicBlock logicalPred = isForwards ? edge
336: .getSource()
337: : edge.getTarget();
338:
339: // Get the predecessor result fact
340: Fact predFact = analysis
341: .getResultFact(logicalPred);
342: int predLastUpdated = analysis
343: .getLastUpdateTimestamp(predFact);
344: System.out.println(" pred timestamp: "
345: + predLastUpdated);
346: }
347: System.out.println("Fact: "
348: + analysis.factToString(start));
349: }
350: continue;
351: }
352:
353: if (needToRecompute) {
354:
355: analysis.makeFactTop(start);
356: predEdgeIter = logicalPredecessorEdgeIterator(block);
357: while (predEdgeIter.hasNext()) {
358: Edge edge = predEdgeIter.next();
359: BasicBlock logicalPred = isForwards ? edge
360: .getSource() : edge.getTarget();
361:
362: // Get the predecessor result fact
363: Fact predFact = analysis
364: .getResultFact(logicalPred);
365:
366: // Apply the edge transfer function.
367: Fact edgeFact = analysis.createFact();
368: analysis.copy(predFact, edgeFact);
369: analysis.edgeTransfer(edge, edgeFact);
370:
371: if (DEBUG
372: && !analysis.same(edgeFact,
373: predFact)) {
374: debug(
375: block,
376: logicalPred,
377: edge,
378: "Edge transfer "
379: + analysis
380: .factToString(predFact)
381: + " ==> "
382: + analysis
383: .factToString(edgeFact));
384: }
385:
386: // Merge the predecessor fact (possibly transformed by the edge transfer function)
387: // into the block's start fact.
388: if (DEBUG) {
389: if (analysis.isTop(start))
390: debug(
391: block,
392: logicalPred,
393: edge,
394: "\n First pred is "
395: + analysis
396: .factToString(edgeFact)
397: + "\n last updated at "
398: + analysis
399: .getLastUpdateTimestamp(predFact)
400: + "\n");
401: else
402: debug(
403: block,
404: logicalPred,
405: edge,
406: "\n Meet "
407: + analysis
408: .factToString(start)
409: + "\n with "
410: + analysis
411: .factToString(edgeFact)
412:
413: + "\n pred last updated at "
414: + analysis
415: .getLastUpdateTimestamp(predFact)
416: + "\n");
417: }
418:
419: if (analysis instanceof UnconditionalValueDerefAnalysis) {
420: ((UnconditionalValueDerefAnalysis) analysis)
421: .meetInto(
422: (UnconditionalValueDerefSet) edgeFact,
423: edge,
424: (UnconditionalValueDerefSet) start,
425: rawPredCount == 1);
426: } else
427: analysis
428: .meetInto(edgeFact, edge, start);
429: analysis.setLastUpdateTimestamp(start,
430: timestamp);
431:
432: int pos = -1;
433: if (block.getFirstInstruction() != null)
434: pos = block.getFirstInstruction()
435: .getPosition();
436: if (DEBUG)
437: System.out.println(" [" + pos + "]==> "
438: + analysis.factToString(start)
439: + " @ " + timestamp + " \n");
440: }
441: }
442: }
443: if (DEBUG)
444: debug(block, "start fact is "
445: + analysis.factToString(start) + "\n");
446:
447: // making a copy of result facts (so we can detect if it changed).
448: boolean resultWasTop = analysis.isTop(result);
449: Fact origResult = null;
450: if (!resultWasTop) {
451: origResult = analysis.createFact();
452: analysis.copy(result, origResult);
453: }
454:
455: if (true || analysis.isTop(start)) {
456: // Apply the transfer function.
457:
458: analysis.transfer(block, null, start, result);
459: } else {
460: analysis.copy(start, result);
461: }
462:
463: if (DEBUG
464: && SystemProperties
465: .getBoolean("dataflow.blockdebug")) {
466: debug(block, "Dumping flow values for block:\n");
467: Iterator<org.apache.bcel.generic.InstructionHandle> ii = block
468: .instructionIterator();
469: while (ii.hasNext()) {
470: org.apache.bcel.generic.InstructionHandle handle = ii
471: .next();
472: Fact tmpResult = analysis.createFact();
473: analysis.transfer(block, handle, start,
474: tmpResult);
475: System.out.println("\t" + handle + " "
476: + analysis.factToString(tmpResult));
477: }
478: }
479:
480: // See if the result changed.
481: if (DEBUG)
482: debug(block, "orig result is "
483: + (origResult == null ? "TOP" : analysis
484: .factToString(origResult)) + "\n");
485: boolean this ResultChanged = false;
486: if (resultWasTop)
487: this ResultChanged = !analysis.isTop(result);
488: else
489: this ResultChanged = !analysis.same(result,
490: origResult);
491: if (this ResultChanged) {
492: timestamp++;
493: if (DEBUG)
494: debug(block, "result changed at timestamp "
495: + timestamp + "\n");
496: if (DEBUG && !needToRecompute) {
497: System.out
498: .println("I thought I didn't need to recompute");
499: }
500: change = true;
501: analysis.setLastUpdateTimestamp(result, timestamp);
502: } else
503: analysis.setLastUpdateTimestamp(result,
504: originalResultTimestamp);
505:
506: if (DEBUG)
507: debug(block, "result is "
508: + analysis.factToString(result)
509: + " @ timestamp "
510: + analysis.getLastUpdateTimestamp(result)
511: + "\n");
512: }
513:
514: analysis.finishIteration();
515: } while (change);
516:
517: if (DEBUG) {
518: System.out
519: .println("-- Quiescence achieved-------------------------------------------------");
520: System.out.println(this .getClass().getName()
521: + " iteration: " + numIterations + ", timestamp: "
522: + timestamp);
523: MethodGen mg = cfg.getMethodGen();
524: System.out.println(mg.getClassName() + "." + mg.getName()
525: + mg.getSignature());
526: new RuntimeException(
527: "Quiescence achieved----------------------------------------------------------------")
528: .printStackTrace(System.out);
529:
530: }
531: DEBUG = debugWas;
532: }
533:
534: /**
535: * @param msg TODO
536: *
537: */
538: private void reportAnalysis(String msg) {
539: String shortAnalysisName = analysis.getClass().getName();
540: int pkgEnd = shortAnalysisName.lastIndexOf('.');
541: if (pkgEnd >= 0) {
542: shortAnalysisName = shortAnalysisName.substring(pkgEnd + 1);
543: }
544: System.out.println(msg + " " + shortAnalysisName + " on "
545: + getFullyQualifiedMethodName());
546: }
547:
548: private static String blockId(BasicBlock bb) {
549: InstructionHandle handle = bb.getFirstInstruction();
550: if (handle == null)
551: return "" + bb.getLabel();
552: return bb.getLabel() + ":" + handle.getPosition() + " "
553: + handle.getInstruction();
554: }
555:
556: private static void debug(BasicBlock bb, String msg) {
557:
558: System.out
559: .print("Dataflow (block " + blockId(bb) + "): " + msg);
560: }
561:
562: private static void debug(BasicBlock bb, BasicBlock pred,
563: Edge edge, String msg) {
564: System.out.print("Dataflow (block " + blockId(bb)
565: + ", predecessor " + blockId(pred) + " ["
566: + Edge.edgeTypeToString(edge.getType()) + "]): " + msg);
567: }
568:
569: /**
570: * Return the number of iterations of the main execution loop.
571: */
572: public int getNumIterations() {
573: return numIterations;
574: }
575:
576: /**
577: * Get dataflow facts for start of given block.
578: */
579: public Fact getStartFact(BasicBlock block) {
580: return analysis.getStartFact(block);
581: }
582:
583: /**
584: * Get dataflow facts for end of given block.
585: */
586: public Fact getResultFact(BasicBlock block) {
587: return analysis.getResultFact(block);
588: }
589:
590: /**
591: * Get dataflow fact at (just before) given Location.
592: * Note "before" is meant in the logical sense, so for backward analyses,
593: * before means after the location in the control flow sense.
594: *
595: * @param location the Location
596: * @return the dataflow value at given Location
597: * @throws DataflowAnalysisException
598: */
599: public/*final*/Fact getFactAtLocation(Location location)
600: throws DataflowAnalysisException {
601: return analysis.getFactAtLocation(location);
602: }
603:
604: /**
605: * Get the dataflow fact representing the point just after given Location.
606: * Note "after" is meant in the logical sense, so for backward analyses,
607: * after means before the location in the control flow sense.
608: *
609: * @param location the Location
610: * @return the dataflow value after given Location
611: * @throws DataflowAnalysisException
612: */
613: public/*final*/Fact getFactAfterLocation(Location location)
614: throws DataflowAnalysisException {
615: return analysis.getFactAfterLocation(location);
616: }
617:
618: /**
619: * Get the fact that is true on the given control edge.
620: *
621: * @param edge the edge
622: * @return the fact that is true on the edge
623: * @throws DataflowAnalysisException
624: */
625: public Fact getFactOnEdge(Edge edge)
626: throws DataflowAnalysisException {
627: return analysis.getFactOnEdge(edge);
628: }
629:
630: /**
631: * Get the analysis object.
632: */
633: public AnalysisType getAnalysis() {
634: return analysis;
635: }
636:
637: /**
638: * Get the CFG object.
639: */
640: public CFG getCFG() {
641: return cfg;
642: }
643:
644: /**
645: * Return an Iterator over edges that connect given block to its
646: * logical predecessors. For forward analyses, this is the incoming edges.
647: * For backward analyses, this is the outgoing edges.
648: */
649: private Iterator<Edge> logicalPredecessorEdgeIterator(
650: BasicBlock block) {
651: return isForwards ? cfg.incomingEdgeIterator(block) : cfg
652: .outgoingEdgeIterator(block);
653: }
654:
655: /**
656: * Get the "logical" entry block of the CFG.
657: * For forward analyses, this is the entry block.
658: * For backward analyses, this is the exit block.
659: */
660: private BasicBlock logicalEntryBlock() {
661: return isForwards ? cfg.getEntry() : cfg.getExit();
662: }
663:
664: public void dumpDataflow(AnalysisType analysis) {
665: System.out.println(this .getClass().getName() + " analysis for "
666: + getCFG().getMethodName() + " { ");
667: try {
668:
669: for (Location loc : getCFG().orderedLocations()) {
670: System.out
671: .println("\nBefore: "
672: + analysis
673: .factToString(getFactAtLocation(loc)));
674: System.out.println("Location: " + loc);
675: System.out
676: .println("After: "
677: + analysis
678: .factToString(getFactAfterLocation(loc)));
679: }
680: } catch (DataflowAnalysisException e) {
681: AnalysisContext.logError("error dumping dataflow analysis",
682: e);
683: System.out.println(e);
684: }
685: System.out.println("}");
686: }
687: }
688:
689: // vim:ts=4
|