Dataflow


1   /*
2    * Bytecode Analysis Framework
3    * Copyright (C) 2003,2004 University of Maryland
4    * 
5    * This library is free software; you can redistribute it and/or
6    * modify it under the terms of the GNU Lesser General Public
7    * License as published by the Free Software Foundation; either
8    * version 2.1 of the License, or (at your option) any later version.
9    * 
10   * This library is distributed in the hope that it will be useful,
11   * but WITHOUT ANY WARRANTY; without even the implied warranty of
12   * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
13   * Lesser General Public License for more details.
14   * 
15   * You should have received a copy of the GNU Lesser General Public
16   * License along with this library; if not, write to the Free Software
17   * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
18   */
19  
20  package edu.umd.cs.findbugs.ba;
21  
22  import java.util.Iterator  ;
23  
24  import org.apache.bcel.generic.InstructionHandle;
25  import org.apache.bcel.generic.MethodGen;
26  
27  import edu.umd.cs.findbugs.SystemProperties;
28  
29  /**
30   * Perform dataflow analysis on a method using a control flow graph.
31   * Both forward and backward analyses can be performed.
32   * <ul>
33   * <li> The "start" point of each block is the entry (forward analyses)
34   * or the exit (backward analyses).
35   * <li> The "result" point of each block is the exit (forward analyses)
36   * or the entry (backward analyses).
37   * </ul>
38   * The analysis's transfer function is applied to transform
39   * the meet of the results of the block's logical predecessors
40   * (the block's start facts) into the block's result facts.
41   *
42   * @author David Hovemeyer
43   * @see CFG
44   * @see DataflowAnalysis
45   */
46  public class Dataflow <Fact, AnalysisType extends DataflowAnalysis<Fact>> {
47      private CFG cfg;
48      private AnalysisType analysis;
49      private BlockOrder blockOrder;
50      private boolean isForwards;
51      private int numIterations;
52  
53      static final boolean DEBUG = SystemProperties.getBoolean("dataflow.debug");
54  
55      /**
56       * Constructor.
57       *
58       * @param cfg      the control flow graph
59       * @param analysis the DataflowAnalysis to be run
60       */
61      public Dataflow(CFG cfg, AnalysisType analysis) {
62          this.cfg = cfg;
63          this.analysis = analysis;
64          blockOrder = analysis.getBlockOrder(cfg);
65          isForwards = analysis.isForwards();
66          numIterations = 0;
67  
68          // Initialize result facts
69          Iterator  <BasicBlock> i = cfg.blockIterator();
70          while (i.hasNext()) {
71              BasicBlock block = i.next();
72              
73              
74              // Initial result facts are whatever the analysis sets them to be.
75              Fact result = analysis.getResultFact(block);
76              if (block == logicalEntryBlock())
77                  try {
78                      analysis.initEntryFact(result);
79                  } catch (DataflowAnalysisException e) {
80                       analysis.initResultFact(result);
81                  }
82              else analysis.initResultFact(result);
83          }
84      }
85  
86      // Maximum number of iterations before we assume there is a bug and give up.
87      private static final int MAX_ITERS = SystemProperties.getInteger("dataflow.maxiters", 100).intValue();
88  
89      private String   getFullyQualifiedMethodName() {
90          String   methodName;
91          MethodGen methodGen = cfg.getMethodGen();
92          if (methodGen == null)
93              methodName = cfg.getMethodName();
94          else methodName = SignatureConverter.convertMethodSignature(methodGen);
95          return methodName;
96      }
97      /**
98       * Run the algorithm.
99       * Afterwards, caller can use the getStartFact() and getResultFact() methods to
100      * to get dataflow facts at start and result points of each block.
101      */
102     public void execute() throws DataflowAnalysisException {
103         boolean change;
104 
105         if (DEBUG) {
106             String   shortAnalysisName = analysis.getClass().getName();
107             int pkgEnd = shortAnalysisName.lastIndexOf('.');
108             if (pkgEnd >= 0) {
109                 shortAnalysisName = shortAnalysisName.substring(pkgEnd + 1);
110             }
111             System.out.println("Executing " + shortAnalysisName + " on " + getFullyQualifiedMethodName());
112         }
113 
114         int timestamp = 0;
115         do {
116             change = false;
117             ++numIterations;
118 
119             if (DEBUG) {
120                 System.out.println("----------------------------------------------------------------------");
121                 System.out.println(this.getClass().getName() + " iteration: " + numIterations + ", timestamp: " + timestamp);
122                 System.out.println("----------------------------------------------------------------------");
123             }
124 
125             if (numIterations >= MAX_ITERS) {
126                 assert false : "Too many iterations (" + numIterations + ") in dataflow when analyzing " + getFullyQualifiedMethodName();
127                 break;
128             }
129     
130             analysis.startIteration();
131             
132             if (DEBUG) {
133                 if (blockOrder instanceof ReverseDFSOrder) {
134                     ReverseDFSOrder rBlockOrder = (ReverseDFSOrder) blockOrder;
135                     System.out.println("Entry point is: " + logicalEntryBlock());
136                     System.out.println("Basic block order: ");
137                     Iterator  <BasicBlock> i = blockOrder.blockIterator();
138                     while (i.hasNext()) {
139 
140                         BasicBlock block = i.next();
141                         if (DEBUG) debug(block, "rBlockOrder " + rBlockOrder.rdfs.getDiscoveryTime(block) + "\n");
142                     }
143                 }
144             }
145             
146             // For each block in CFG...
147             Iterator  <BasicBlock> i = blockOrder.blockIterator();
148             while (i.hasNext()) {
149 
150                 BasicBlock block = i.next();
151                 if (DEBUG) debug(block, "start\n");
152     
153                 // Get start fact for block.
154                 Fact start = analysis.getStartFact(block);
155                 boolean needToRecompute = false;
156                 //               Get result facts for block,
157                 Fact result = analysis.getResultFact(block);
158                 int originalResultTimestamp = analysis.getLastUpdateTimestamp(result);
159                 
160                 // Meet all of the logical predecessor results into this block's start.
161                 // Special case: if the block is the logical entry, then it gets
162                 // the special "entry fact".
163                 if (block == logicalEntryBlock()) {
164                     analysis.makeFactTop(start);
165                     analysis.initEntryFact(start);
166                     if (DEBUG) debug(block, "Init entry fact ==> " + start + "\n");
167                     needToRecompute = true;
168                 } else {
169                     int lastCalculated = analysis.getLastUpdateTimestamp(start);
170                     Iterator  <Edge> predEdgeIter = logicalPredecessorEdgeIterator(block);
171 
172                     int predCount = 0;
173                     while (predEdgeIter.hasNext()) {
174                         Edge edge = predEdgeIter.next();
175                         BasicBlock logicalPred = isForwards ? edge.getSource() : edge.getTarget();
176     
177                         // Get the predecessor result fact
178                         Fact predFact = analysis.getResultFact(logicalPred);
179                         int predLastUpdated = analysis.getLastUpdateTimestamp(predFact);
180                         if (!analysis.isTop(predFact)) {
181                             predCount++;
182                             if (predLastUpdated >= lastCalculated) {
183 
184                             needToRecompute = true;
185                             if (DEBUG) {
186                             System.out.println("Need to recompute. My timestamp = " + lastCalculated + ", pred timestamp = " + predLastUpdated + ", pred fact = " + predFact);
187                             }
188                             break;
189                             }
190                         }
191                     }
192                     if (predCount == 0) needToRecompute = true;
193 
194                     if (!needToRecompute) {
195                         if (DEBUG) {
196                             debug(block, "Skipping: predecessors haven't changed");
197                             System.out.println(" curr timestamp: " + timestamp);
198                             System.out.println(" last timestamp: " + lastCalculated);
199                             predEdgeIter = logicalPredecessorEdgeIterator(block);
200 
201                             while (predEdgeIter.hasNext()) {
202                                 Edge edge = predEdgeIter.next();
203                                 BasicBlock logicalPred = isForwards ? edge.getSource() : edge.getTarget();
204                                 
205                                 // Get the predecessor result fact
206                                 Fact predFact = analysis.getResultFact(logicalPred);
207                                 int predLastUpdated = analysis.getLastUpdateTimestamp(predFact);
208                                 System.out.println(" pred timestamp: " + predLastUpdated);
209                                 }
210                             System.out.println("Fact: " + start);
211                         }
212                         continue;
213                     }
214 
215                     if (needToRecompute) {
216                         
217                         analysis.makeFactTop(start);
218                         predEdgeIter = logicalPredecessorEdgeIterator(block);
219                         while (predEdgeIter.hasNext()) {
220                             Edge edge = predEdgeIter.next();
221                             BasicBlock logicalPred = isForwards ? edge.getSource() : edge.getTarget();
222 
223                             // Get the predecessor result fact
224                             Fact predFact = analysis.getResultFact(logicalPred);
225 
226                             // Apply the edge transfer function.
227                             Fact edgeFact = analysis.createFact(); 
228                             analysis.copy(predFact, edgeFact);
229                             analysis.edgeTransfer(edge, edgeFact);
230 
231                             if (DEBUG && !analysis.same(edgeFact, predFact)) {
232                                 debug(block, logicalPred, edge,
233                                         "Edge transfer " + predFact + " ==> " + edgeFact);
234                             }
235 
236                             // Merge the predecessor fact (possibly transformed by the edge transfer function)
237                             // into the block's start fact.
238                             if (DEBUG) debug(block, logicalPred, edge, "\n  Meet " + start + "\n   with " + edgeFact 
239                                     + "\n   pred last updated at " +  analysis.getLastUpdateTimestamp(predFact) +"\n");
240 
241                             
242                             analysis.meetInto(edgeFact, edge, start);
243                             analysis.setLastUpdateTimestamp(start, timestamp);
244                             
245                             int pos = -1;
246                             if (block.getFirstInstruction() != null)
247                                 pos = block.getFirstInstruction().getPosition();
248                             if (DEBUG) System.out.println(" [" + pos +"]==> " + start +" @ " + timestamp + " \n");
249                         }
250                     }
251                 }
252                 if (DEBUG) debug(block, "start fact is " + start + "\n");
253     
254                 // making a copy of result facts (so we can detect if it changed).
255                 boolean resultWasTop = analysis.isTop(result);
256                 Fact origResult = null;
257                 if (!resultWasTop) {
258                     origResult = analysis.createFact();
259                     analysis.copy(result, origResult);
260                 }
261     
262                 if (true || analysis.isTop(start)) {
263                     // Apply the transfer function.
264 
265                     analysis.transfer(block, null, start, result);
266                 } else {
267                     analysis.copy(start, result);
268                 }
269 
270                 if (DEBUG && SystemProperties.getBoolean("dataflow.blockdebug")) {
271                     debug(block, "Dumping flow values for block:\n");
272                     Iterator  <org.apache.bcel.generic.InstructionHandle> ii = block.instructionIterator();
273                     while (ii.hasNext()) {
274                         org.apache.bcel.generic.InstructionHandle handle = ii.next();
275                         Fact tmpResult = analysis.createFact();
276                         analysis.transfer(block, handle, start, tmpResult);
277                         System.out.println("\t" + handle + " " + tmpResult);
278                     }
279                 }
280     
281                 // See if the result changed.
282                 if (DEBUG) debug(block, "orig result is " + origResult + "\n");
283                 boolean thisResultChanged = false;
284                 if (resultWasTop)
285                     thisResultChanged = !analysis.isTop(result);
286                 else thisResultChanged = !analysis.same(result, origResult);
287                 if (thisResultChanged) {
288                     timestamp++;
289                     if (DEBUG) debug(block, "result changed at timestamp " + timestamp + "\n");
290                     if (DEBUG && !needToRecompute) {
291                         System.out.println("I thought I didn't need to recompute");
292                     }
293                     change = true;
294                     analysis.setLastUpdateTimestamp(result, timestamp);
295                 } else
296                     analysis.setLastUpdateTimestamp(result, originalResultTimestamp);
297 
298                 if (DEBUG) debug(block, "result is " + result + " @ timestamp " 
299                         + analysis.getLastUpdateTimestamp(result) + "\n");
300             }
301             
302             analysis.finishIteration();
303         } while (change);
304     }
305 
306     private static String   blockId(BasicBlock bb) {
307         InstructionHandle handle = bb.getFirstInstruction();
308         if (handle == null) return ""+ bb.getId();
309         return bb.getId()+":"+ handle.getPosition() + " " + handle.getInstruction();
310     }
311     private static void debug(BasicBlock bb, String   msg) {
312         
313         
314         System.out.print("Dataflow (block " + blockId(bb) + "): " + msg);
315     }
316 
317     private static void debug(BasicBlock bb, BasicBlock pred, Edge edge, String   msg) {
318         System.out.print("Dataflow (block " + blockId(bb) + ", predecessor " + blockId(pred) +
319                 " [" + Edge.edgeTypeToString(edge.getType()) + "]): " + msg);
320     }
321 
322     /**
323      * Return the number of iterations of the main execution loop.
324      */
325     public int getNumIterations() {
326         return numIterations;
327     }
328 
329     /**
330      * Get dataflow facts for start of given block.
331      */
332     public Fact getStartFact(BasicBlock block) {
333         return analysis.getStartFact(block);
334     }
335 
336     /**
337      * Get dataflow facts for end of given block.
338      */
339     public Fact getResultFact(BasicBlock block) {
340         return analysis.getResultFact(block);
341     }
342 
343     /**
344      * Get the analysis object.
345      */
346     public AnalysisType getAnalysis() {
347         return analysis;
348     }
349 
350     /**
351      * Get the CFG object.
352      */
353     public CFG getCFG() {
354         return cfg;
355     }
356 
357     /**
358      * Return an Iterator over edges that connect given block to its
359      * logical predecessors.  For forward analyses, this is the incoming edges.
360      * For backward analyses, this is the outgoing edges.
361      */
362     private Iterator  <Edge> logicalPredecessorEdgeIterator(BasicBlock block) {
363         return isForwards ? cfg.incomingEdgeIterator(block) : cfg.outgoingEdgeIterator(block);
364     }
365 
366     /**
367      * Get the "logical" entry block of the CFG.
368      * For forward analyses, this is the entry block.
369      * For backward analyses, this is the exit block.
370      */
371     private BasicBlock logicalEntryBlock() {
372         return isForwards ? cfg.getEntry() : cfg.getExit();
373     }
374 }
375 
376 // vim:ts=4
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags