KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > edu > umd > cs > findbugs > ba > deref > UnconditionalValueDerefAnalysis


1 /*
2  * FindBugs - Find Bugs in Java programs
3  * Copyright (C) 2006, 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.deref;
21
22 import java.util.BitSet JavaDoc;
23 import java.util.Set JavaDoc;
24
25 import org.apache.bcel.classfile.Method;
26 import org.apache.bcel.generic.ATHROW;
27 import org.apache.bcel.generic.InstructionHandle;
28 import org.apache.bcel.generic.InvokeInstruction;
29 import org.apache.bcel.generic.MethodGen;
30
31 import edu.umd.cs.findbugs.SystemProperties;
32 import edu.umd.cs.findbugs.annotations.CheckForNull;
33 import edu.umd.cs.findbugs.ba.AnalysisContext;
34 import edu.umd.cs.findbugs.ba.AssertionMethods;
35 import edu.umd.cs.findbugs.ba.BackwardDataflowAnalysis;
36 import edu.umd.cs.findbugs.ba.BasicBlock;
37 import edu.umd.cs.findbugs.ba.CFG;
38 import edu.umd.cs.findbugs.ba.CFGBuilderException;
39 import edu.umd.cs.findbugs.ba.ClassContext;
40 import edu.umd.cs.findbugs.ba.Dataflow;
41 import edu.umd.cs.findbugs.ba.DataflowAnalysisException;
42 import edu.umd.cs.findbugs.ba.DataflowTestDriver;
43 import edu.umd.cs.findbugs.ba.DepthFirstSearch;
44 import edu.umd.cs.findbugs.ba.Edge;
45 import edu.umd.cs.findbugs.ba.EdgeTypes;
46 import edu.umd.cs.findbugs.ba.Hierarchy;
47 import edu.umd.cs.findbugs.ba.JavaClassAndMethod;
48 import edu.umd.cs.findbugs.ba.Location;
49 import edu.umd.cs.findbugs.ba.NullnessAnnotationDatabase;
50 import edu.umd.cs.findbugs.ba.ReverseDepthFirstSearch;
51 import edu.umd.cs.findbugs.ba.SignatureParser;
52 import edu.umd.cs.findbugs.ba.XFactory;
53 import edu.umd.cs.findbugs.ba.XMethod;
54 import edu.umd.cs.findbugs.ba.npe.IsNullConditionDecision;
55 import edu.umd.cs.findbugs.ba.npe.IsNullValue;
56 import edu.umd.cs.findbugs.ba.npe.IsNullValueDataflow;
57 import edu.umd.cs.findbugs.ba.npe.IsNullValueFrame;
58 import edu.umd.cs.findbugs.ba.npe.ParameterNullnessProperty;
59 import edu.umd.cs.findbugs.ba.npe.ParameterNullnessPropertyDatabase;
60 import edu.umd.cs.findbugs.ba.type.TypeDataflow;
61 import edu.umd.cs.findbugs.ba.type.TypeFrame;
62 import edu.umd.cs.findbugs.ba.vna.AvailableLoad;
63 import edu.umd.cs.findbugs.ba.vna.ValueNumber;
64 import edu.umd.cs.findbugs.ba.vna.ValueNumberDataflow;
65 import edu.umd.cs.findbugs.ba.vna.ValueNumberFrame;
66 import edu.umd.cs.findbugs.detect.BuildUnconditionalParamDerefDatabase;
67
68 /**
69  * Dataflow analysis to find values unconditionally derefenced in the future.
70  *
71  * @author David Hovemeyer
72  */
73 public class UnconditionalValueDerefAnalysis extends
74         BackwardDataflowAnalysis<UnconditionalValueDerefSet> {
75     
76     public static final boolean DEBUG = SystemProperties.getBoolean("fnd.derefs.debug");
77     public static final boolean ASSUME_NONZERO_TRIP_LOOPS = SystemProperties.getBoolean("fnd.derefs.nonzerotrip");
78     public static final boolean IGNORE_DEREF_OF_NONNCP =
79         SystemProperties.getBoolean("fnd.derefs.ignorenonNCP", true);
80
81     public static final boolean IGNORE_DEREF_OF_NONNULL = IGNORE_DEREF_OF_NONNCP
82                                     || SystemProperties.getBoolean("fnd.derefs.ignorenonnull");
83     public static final boolean CHECK_ANNOTATIONS =
84         SystemProperties.getBoolean("fnd.derefs.checkannotations", true);
85     public static final boolean CHECK_CALLS =
86         SystemProperties.getBoolean("fnd.derefs.checkcalls", true);
87     public static final boolean DEBUG_CHECK_CALLS =
88         SystemProperties.getBoolean("fnd.derefs.checkcalls.debug");
89     
90     private CFG cfg;
91     private MethodGen methodGen;
92     private ValueNumberDataflow vnaDataflow;
93     private AssertionMethods assertionMethods;
94     
95     private IsNullValueDataflow invDataflow;
96     private TypeDataflow typeDataflow;
97     
98     /**
99      * Constructor.
100      *
101      * @param rdfs the reverse depth-first-search (for the block order)
102      * @param dfs TODO
103      * @param cfg the CFG for the method
104      * @param methodGen the MethodGen for the method
105      * @param vnaDataflow
106      * @param assertionMethods AssertionMethods for the analyzed class
107      */
108     public UnconditionalValueDerefAnalysis(
109             ReverseDepthFirstSearch rdfs,
110             DepthFirstSearch dfs,
111             CFG cfg,
112             MethodGen methodGen,
113             ValueNumberDataflow vnaDataflow,
114             AssertionMethods assertionMethods
115             ) {
116         super(rdfs, dfs);
117         this.cfg = cfg;
118         this.methodGen = methodGen;
119         this.vnaDataflow = vnaDataflow;
120         this.assertionMethods = assertionMethods;
121         if (DEBUG) {
122             System.out.println("UnconditionalValueDerefAnalysis analysis " + methodGen.getClassName() + "." + methodGen.getName() + " : " + methodGen.getSignature());
123         }
124         if (DEBUG && IGNORE_DEREF_OF_NONNULL) {
125             System.out.println("** Ignoring dereferences of definitely non-null values");
126         }
127     }
128     
129     /**
130      * HACK: use the given is-null dataflow to clear deref sets for
131      * values that are known to be definitely non-null on a branch.
132      *
133      * @param invDataflow the IsNullValueDataflow to use
134      */
135     public void clearDerefsOnNonNullBranches(IsNullValueDataflow invDataflow) {
136         this.invDataflow = invDataflow;
137     }
138     
139     /**
140      *
141      *
142      */
143     public void setTypeDataflow(TypeDataflow typeDataflow) {
144         this.typeDataflow= typeDataflow;
145     }
146
147     /* (non-Javadoc)
148      * @see edu.umd.cs.findbugs.ba.AbstractDataflowAnalysis#isFactValid(java.lang.Object)
149      */
150     @Override JavaDoc
151     public boolean isFactValid(UnconditionalValueDerefSet fact) {
152         return !fact.isTop() && !fact.isBottom();
153     }
154
155     /* (non-Javadoc)
156      * @see edu.umd.cs.findbugs.ba.AbstractDataflowAnalysis#transferInstruction(org.apache.bcel.generic.InstructionHandle, edu.umd.cs.findbugs.ba.BasicBlock, java.lang.Object)
157      */
158     @Override JavaDoc
159     public void transferInstruction(InstructionHandle handle,
160             BasicBlock basicBlock, UnconditionalValueDerefSet fact)
161             throws DataflowAnalysisException {
162         
163         if (fact.isTop()) return;
164         Location location = new Location(handle, basicBlock);
165         
166         // If this is a call to an assertion method,
167 // change the dataflow value to be TOP.
168 // We don't want to report future derefs that would
169 // be guaranteed only if the assertion methods
170 // returns normally.
171 // TODO: at some point, evaluate whether we should revisit this
172 if (isAssertion(handle) || handle.getInstruction() instanceof ATHROW ) {
173             if (DEBUG) System.out.println("MAKING BOTTOM0 AT: " + location);
174             fact.clear();
175             return;
176         }
177         
178         // Get value number frame
179 ValueNumberFrame vnaFrame = vnaDataflow.getFactAtLocation(location);
180         if (!vnaFrame.isValid()) {
181             if (DEBUG) System.out.println("MAKING TOP1 AT: " + location);
182             // Probably dead code.
183 // Assume this location can't be reached.
184 makeFactTop(fact);
185             return;
186         }
187         
188
189         // Check for calls to a method that unconditionally dereferences
190 // a parameter. Mark any such arguments as derefs.
191 if (CHECK_CALLS && handle.getInstruction() instanceof InvokeInstruction) {
192             checkUnconditionalDerefDatabase(location, vnaFrame, fact);
193         }
194         
195         // If this is a method call instruction,
196 // check to see if any of the parameters are @NonNull,
197 // and treat them as dereferences.
198 if (CHECK_ANNOTATIONS && handle.getInstruction() instanceof InvokeInstruction) {
199             checkNonNullParams(location, vnaFrame, fact);
200         }
201
202         // Check to see if an instance value is dereferenced here
203 checkInstance(location, vnaFrame, fact);
204         
205         if (false) fact.cleanDerefSet(location, vnaFrame);
206
207         if (DEBUG && fact.isTop()) System.out.println("MAKING TOP2 At: " + location);
208         
209     }
210
211     /**
212      * Check method call at given location to see if it unconditionally
213      * dereferences a parameter. Mark any such arguments as derefs.
214      *
215      * @param location the Location of the method call
216      * @param vnaFrame ValueNumberFrame at the Location
217      * @param fact the dataflow value to modify
218      * @throws DataflowAnalysisException
219      */
220     private void checkUnconditionalDerefDatabase(
221             Location location,
222             ValueNumberFrame vnaFrame,
223             UnconditionalValueDerefSet fact) throws DataflowAnalysisException {
224         
225         ParameterNullnessPropertyDatabase database =
226             AnalysisContext.currentAnalysisContext().getUnconditionalDerefParamDatabase();
227         if (database == null) {
228             if (DEBUG_CHECK_CALLS) {
229                 System.out.println("no database!");
230             }
231             return;
232         }
233         
234         InvokeInstruction inv = (InvokeInstruction) location.getHandle().getInstruction();
235         TypeFrame typeFrame = typeDataflow.getFactAtLocation(location);
236         if (!typeFrame.isValid()) {
237             if (DEBUG_CHECK_CALLS) {
238                 System.out.println("invalid type frame!");
239             }
240             return;
241         }
242         
243         SignatureParser sigParser = new SignatureParser(inv.getSignature(methodGen.getConstantPool()));
244         int numParams = sigParser.getNumParameters();
245         
246         try {
247             Set JavaDoc<JavaClassAndMethod> targetSet = Hierarchy.resolveMethodCallTargets(
248                     inv,
249                     typeFrame,
250                     methodGen.getConstantPool());
251             
252             if (targetSet.isEmpty()) {
253                 return;
254             }
255             
256             // Compute the intersection of all properties
257 ParameterNullnessProperty derefParamSet = null;
258             for (JavaClassAndMethod target : targetSet) {
259                 if (DEBUG_CHECK_CALLS) {
260                     System.out.print("Checking " + target + ": ");
261                 }
262                 
263                 ParameterNullnessProperty targetDerefParamSet = database.getProperty(target.toXMethod());
264                 if (targetDerefParamSet == null) {
265                     // Hmm...no information for this target.
266 // assume it doesn't dereference anything
267 if (DEBUG_CHECK_CALLS) {
268                         System.out.print("==> no information, assume no guaranteed dereferences");
269                     }
270             
271                     return;
272                 }
273                 
274                 if (DEBUG_CHECK_CALLS) {
275                     System.out.println("==> " + targetDerefParamSet);
276                 }
277                 if (derefParamSet == null) {
278                     derefParamSet = new ParameterNullnessProperty();
279                     derefParamSet.copyFrom(targetDerefParamSet);
280                 } else {
281                     derefParamSet.intersectWith(targetDerefParamSet);
282                 }
283             }
284             
285             if (derefParamSet == null || derefParamSet.isEmpty()) {
286                 return;
287             }
288             if (DEBUG_CHECK_CALLS) {
289                 System.out.println("** Summary of call: " + derefParamSet);
290             }
291             
292             IsNullValueFrame invFrame = null;
293             if (IGNORE_DEREF_OF_NONNULL && invDataflow != null) {
294                 invFrame = invDataflow.getFactAtLocation(location);
295                 if (!invFrame.isValid()) {
296                     invFrame = null;
297                 }
298             }
299             
300             for (int i = 0; i < numParams; i++) {
301                 if (!derefParamSet.isNonNull(i)) {
302                     continue;
303                 }
304                 
305                 int argSlot = vnaFrame.getArgumentSlot(i, numParams);
306
307                 if (invFrame != null) {
308                     IsNullValue val = invFrame.getValue(argSlot);
309                     if (val.isDefinitelyNotNull()) {
310                         continue;
311                     }
312                     if (IGNORE_DEREF_OF_NONNCP && !val.isNullOnComplicatedPath()) continue;
313                 }
314                 
315                 fact.addDeref(vnaFrame.getValue(argSlot), location);
316                 if (DEBUG_CHECK_CALLS ||VERBOSE_NULLARG_DEBUG) {
317                     System.out.println("Adding deref of " + vnaFrame.getValue(argSlot) + " at location " + location);
318                     for (JavaClassAndMethod target : targetSet) {
319
320                         System.out.print("Checking " + target + ": ");
321                         ParameterNullnessProperty targetDerefParamSet = database.getProperty(target.toXMethod());
322                         if (targetDerefParamSet == null) {
323                             System.out.println(" ==> unknown");
324                             continue;
325                         }
326
327
328                         System.out.println("==> " + targetDerefParamSet);
329
330                     }
331
332                 }
333             }
334         } catch (ClassNotFoundException JavaDoc e) {
335             AnalysisContext.reportMissingClass(e);
336         }
337     }
338     public static final boolean VERBOSE_NULLARG_DEBUG = SystemProperties.getBoolean("fnd.debug.nullarg.verbose");
339     
340     /**
341      * If this is a method call instruction,
342      * check to see if any of the parameters are @NonNull,
343      * and treat them as dereferences.
344      *
345      * @param location the Location of the instruction
346      * @param vnaFrame the ValueNumberFrame at the Location of the instruction
347      * @param fact the dataflow value to modify
348      * @throws DataflowAnalysisException
349      */
350     private void checkNonNullParams(Location location, ValueNumberFrame vnaFrame, UnconditionalValueDerefSet fact) throws DataflowAnalysisException {
351         NullnessAnnotationDatabase database = AnalysisContext.currentAnalysisContext().getNullnessAnnotationDatabase();
352         if (database == null) {
353             return;
354         }
355
356         InvokeInstruction inv = (InvokeInstruction) location.getHandle().getInstruction();
357         XMethod called = XFactory.createXMethod(
358                 inv,
359                 methodGen.getConstantPool());
360         SignatureParser sigParser = new SignatureParser(called.getSignature());
361         int numParams = sigParser.getNumParameters();
362
363         for (int i = 0; i < numParams; i++) {
364             if (IGNORE_DEREF_OF_NONNULL
365                     && invDataflow != null) {
366                 IsNullValueFrame invFrame = invDataflow.getFactAtLocation(location);
367                 if (isNonNullValue(invFrame, invFrame.getArgumentSlot(i, numParams))) {
368                     continue;
369                 }
370             }
371             if (database.parameterMustBeNonNull(called, i)) {
372                 // Get the corresponding value number
373 ValueNumber vn = vnaFrame.getArgument(inv, methodGen.getConstantPool(), i, numParams);
374                 fact.addDeref(vn, location);
375             }
376         }
377     }
378
379     /**
380      * Check to see if the instruction has a null check associated with it,
381      * and if so, add a dereference.
382      *
383      * @param location the Location of the instruction
384      * @param vnaFrame ValueNumberFrame at the Location of the instruction
385      * @param fact the dataflow value to modify
386      * @throws DataflowAnalysisException
387      */
388     private void checkInstance(
389             Location location,
390             ValueNumberFrame vnaFrame,
391             UnconditionalValueDerefSet fact) throws DataflowAnalysisException {
392         // See if this instruction has a null check.
393 // If it does, the fall through predecessor will be
394 // identify itself as the null check.
395 if (!location.isFirstInstructionInBasicBlock()) {
396             return;
397         }
398         BasicBlock fallThroughPredecessor =
399             cfg.getPredecessorWithEdgeType(location.getBasicBlock(), EdgeTypes.FALL_THROUGH_EDGE);
400         if (fallThroughPredecessor == null || !fallThroughPredecessor.isNullCheck()) {
401             return;
402         }
403         
404         // Get the null-checked value
405 ValueNumber vn = vnaFrame.getInstance(location.getHandle().getInstruction(), methodGen.getConstantPool());
406         
407         // Ignore dereferences of this
408 if (!methodGen.isStatic()) {
409             ValueNumber v = vnaFrame.getValue(0);
410             if (v.equals(vn)) return;
411         }
412         if (vn.hasFlag(ValueNumber.CONSTANT_CLASS_OBJECT)) return;
413
414         IsNullValueFrame startFact = null;
415
416         if (invDataflow != null) {
417             startFact = invDataflow.getStartFact(fallThroughPredecessor);
418         }
419
420         // Ignore dereferences of values that are definitely non-null
421 if (IGNORE_DEREF_OF_NONNULL
422                 && invDataflow != null
423                 && isDerefOfNonNullValue(location, startFact)) {
424             return;
425         }
426         
427         if (IGNORE_DEREF_OF_NONNCP
428                 && invDataflow != null
429                 && !isDerefOfNullOnComplexPathValue(location, startFact)) {
430             return;
431         }
432         
433         if (DEBUG) {
434             System.out.println("FOUND GUARANTEED DEREFERENCE");
435             System.out.println("Load: " + vnaFrame.getLoad(vn));
436             System.out.println("Pred: " + fallThroughPredecessor);
437             System.out.println("startFact: " + startFact);
438             System.out.println("Location: " + location);
439             System.out.println("Value number frame: " + vnaFrame);
440             System.out.println("Dereferenced valueNumber: " + vn);
441             System.out.println("invDataflow: " + startFact);
442             System.out.println("IGNORE_DEREF_OF_NONNCP: " + IGNORE_DEREF_OF_NONNCP);
443             System.out.println("IGNORE_DEREF_OF_NONNULL: " + IGNORE_DEREF_OF_NONNULL);
444             System.out.println("isNonNull: " + isDerefOfNonNullValue(location, startFact));
445             System.out.println("isDerefOfNullOnComplexPathValue: " + isDerefOfNullOnComplexPathValue(location, startFact));
446
447             
448         }
449         // Mark the value number as being dereferenced at this location
450 fact.addDeref(vn, location);
451     }
452
453     /**
454      * Determine whether instruction at given Location is a dereference of
455      * a definitely non-null value.
456      *
457      * @param locationOfDeref the dereference instruction Location
458      * @param invFrameAtNullCheck the IsNullValueFrame at the location of the null check
459      * @return true if the instruction at the location is a dereference of a definitely
460      * non-null value, false otherwise
461      * @throws DataflowAnalysisException
462      */
463     private boolean isDerefOfNonNullValue(Location locationOfDeref, IsNullValueFrame invFrameAtNullCheck)
464             throws DataflowAnalysisException {
465         if (!invFrameAtNullCheck.isValid()) {
466             // Probably dead code
467 return false;
468         }
469         
470         int instance = invFrameAtNullCheck.getInstanceSlot(
471                 locationOfDeref.getHandle().getInstruction(),
472                 methodGen.getConstantPool());
473         return isNonNullValue(invFrameAtNullCheck, instance);
474     }
475
476     /**
477      * Determine whether instruction at given Location is a dereference of
478      * a value null on a complex path
479      *
480      * @param locationOfDeref the dereference instruction Location
481      * @param invFrameAtNullCheck the IsNullValueFrame at the location of the null check
482      * @return true if the instruction at the location is a dereference of a definitely
483      * non-null value, false otherwise
484      * @throws DataflowAnalysisException
485      */
486     private boolean isDerefOfNullOnComplexPathValue(Location locationOfDeref, IsNullValueFrame invFrameAtNullCheck)
487             throws DataflowAnalysisException {
488         if (!invFrameAtNullCheck.isValid()) {
489             // Probably dead code
490 return false;
491         }
492         
493         int instance = invFrameAtNullCheck.getInstanceSlot(
494                 locationOfDeref.getHandle().getInstruction(),
495                 methodGen.getConstantPool());
496         return isNullOnComplexPath(invFrameAtNullCheck, instance);
497     }
498     /**
499      * Return whether or not given slot in given is-null frame
500      * is definitely non-null.
501      *
502      * @param invFrame an IsNullValueFrame
503      * @param slot slot in the frame
504      * @return true if value in the slot is definitely non-null, false otherwise
505      */
506     private boolean isNonNullValue(IsNullValueFrame invFrame, int slot) {
507         if (invFrame == null || !invFrame.isValid()) {
508             return false;
509         }
510         return invFrame.getValue(slot).isDefinitelyNotNull();
511     }
512     /**
513      * Return whether or not given slot in given is-null frame
514      * is definitely non-null.
515      *
516      * @param invFrame an IsNullValueFrame
517      * @param slot slot in the frame
518      * @return true if value in the slot is null on a complicated path
519      */
520     private boolean isNullOnComplexPath(IsNullValueFrame invFrame, int slot) {
521         if (invFrame == null || !invFrame.isValid()) {
522             return false;
523         }
524         IsNullValue value = invFrame.getValue(slot);
525         return value.isNullOnComplicatedPath();
526     }
527     /**
528      * Return whether or not given instruction is an assertion.
529      *
530      * @param handle the instruction
531      * @return true if instruction is an assertion, false otherwise
532      */
533     private boolean isAssertion(InstructionHandle handle) {
534         return handle.getInstruction() instanceof InvokeInstruction
535                 && assertionMethods.isAssertionCall((InvokeInstruction) handle.getInstruction());
536     }
537
538     /* (non-Javadoc)
539      * @see edu.umd.cs.findbugs.ba.DataflowAnalysis#copy(java.lang.Object, java.lang.Object)
540      */
541     public void copy(UnconditionalValueDerefSet source, UnconditionalValueDerefSet dest) {
542         dest.makeSameAs(source);
543     }
544
545     /* (non-Javadoc)
546      * @see edu.umd.cs.findbugs.ba.DataflowAnalysis#createFact()
547      */
548     public UnconditionalValueDerefSet createFact() {
549         return new UnconditionalValueDerefSet(vnaDataflow.getAnalysis().getNumValuesAllocated());
550     }
551
552     /* (non-Javadoc)
553      * @see edu.umd.cs.findbugs.ba.DataflowAnalysis#initEntryFact(java.lang.Object)
554      */
555     public void initEntryFact(UnconditionalValueDerefSet result)
556             throws DataflowAnalysisException {
557         result.clear();
558     }
559
560     /* (non-Javadoc)
561      * @see edu.umd.cs.findbugs.ba.DataflowAnalysis#initResultFact(java.lang.Object)
562      */
563     public void initResultFact(UnconditionalValueDerefSet result) {
564         result.setIsTop();
565     }
566
567     /* (non-Javadoc)
568      * @see edu.umd.cs.findbugs.ba.DataflowAnalysis#makeFactTop(java.lang.Object)
569      */
570     public void makeFactTop(UnconditionalValueDerefSet fact) {
571         fact.setIsTop();
572     }
573
574     public boolean isTop(UnconditionalValueDerefSet fact) {
575         return fact.isTop();
576     }
577     /* (non-Javadoc)
578      * @see edu.umd.cs.findbugs.ba.DataflowAnalysis#meetInto(java.lang.Object, edu.umd.cs.findbugs.ba.Edge, java.lang.Object)
579      */
580     public void meetInto(UnconditionalValueDerefSet fact, Edge edge,
581             UnconditionalValueDerefSet result) throws DataflowAnalysisException {
582         
583         if (ignoreThisEdge(edge)) {
584             return;
585         }
586         
587         ValueNumber knownNonnullOnBranch = null;
588         // Edge transfer function
589 if (isFactValid(fact)) {
590             fact = propagateDerefSetsToMergeInputValues(fact, edge);
591             if (invDataflow != null) {
592                 knownNonnullOnBranch = findValueKnownNonnullOnBranch(fact, edge);
593                 if (knownNonnullOnBranch != null) {
594                     fact = duplicateFact(fact);
595                     fact.clearDerefSet(knownNonnullOnBranch);
596                 }
597             }
598         }
599         boolean isBackEdge = edge.isBackwardInBytecode();
600         boolean sourceIsTopOfLoop = edge.sourceIsTopOfLoop(ClassContext.getLoopExitBranches(methodGen));
601         if (sourceIsTopOfLoop && edge.getType() == EdgeTypes.FALL_THROUGH_EDGE)
602             isBackEdge = true;
603         if (false && (edge.getType() == EdgeTypes.IFCMP_EDGE || sourceIsTopOfLoop)) {
604             System.out.println("Meet into " + edge);
605             System.out.println(" foo2: " + sourceIsTopOfLoop);
606             System.out.println(" getType: " + edge.getType() );
607             System.out.println(" Backedge according to bytecode: " + isBackEdge);
608             System.out.println(" Fact hashCode: " + System.identityHashCode(result));
609             System.out.println(" Initial fact: " + result);
610             System.out.println(" Edge fact: " + fact);
611         }
612         if (result.isTop() || fact.isBottom()) {
613             // Make result identical to other fact
614 copy(fact, result);
615             if (ASSUME_NONZERO_TRIP_LOOPS && isBackEdge && !fact.isTop())
616                 result.resultsFromBackEdge = true;
617         } else if (ASSUME_NONZERO_TRIP_LOOPS && isBackEdge && !fact.isTop()) {
618             result.unionWith(fact, vnaDataflow.getAnalysis().getFactory());
619             result.resultsFromBackEdge = true;
620             if (DEBUG) {
621                 System.out.println("\n Forcing union of " + System.identityHashCode(result) + " due to backedge info");
622                 System.out.println(" result: " + result);
623             }
624             
625         } else if (result.isBottom() || fact.isTop()) {
626             // No change in result fact
627 } else {
628             // Dataflow merge
629 // (intersection of unconditional deref values)
630 if (ASSUME_NONZERO_TRIP_LOOPS && result.resultsFromBackEdge) {
631                 result.backEdgeUpdateCount++;
632                 if (result.backEdgeUpdateCount < 10) {
633                     if (DEBUG) System.out.println("\n Union update of " + System.identityHashCode(result) + " due to backedge info");
634                     result.unionWith(fact, vnaDataflow.getAnalysis().getFactory());
635                     return;
636                 }
637             }
638             result.mergeWith(fact, knownNonnullOnBranch, vnaDataflow.getAnalysis().getFactory());
639             if (DEBUG) {
640                 System.out.println(" updated: " + System.identityHashCode(result));
641                  System.out.println(" result: " + result);
642                  return;
643             }
644         }
645         if (DEBUG && isBackEdge && edge.getType() == EdgeTypes.IFCMP_EDGE) {
646          System.out.println(" result: " + result);
647         }
648     }
649
650     /**
651      * Find out if any VNs in the source block
652      * contribute to unconditionally dereferenced VNs in the
653      * target block. If so, the VN in the source block is
654      * also unconditionally dereferenced, and we must propagate
655      * the target VN's dereferences.
656      *
657      * @param fact a dataflow value
658      * @param edge edge to check for merge input values
659      * @return possibly-modified dataflow value
660      */
661     private UnconditionalValueDerefSet propagateDerefSetsToMergeInputValues(
662             UnconditionalValueDerefSet fact, Edge edge) {
663         
664         ValueNumberFrame blockValueNumberFrame =
665             vnaDataflow.getResultFact(edge.getSource());
666         ValueNumberFrame targetValueNumberFrame =
667             vnaDataflow.getStartFact(edge.getTarget());
668
669         UnconditionalValueDerefSet originalFact = fact;
670         fact = duplicateFact(fact);
671
672         if (blockValueNumberFrame.isValid() && targetValueNumberFrame.isValid() &&
673                 blockValueNumberFrame.getNumSlots() == targetValueNumberFrame.getNumSlots()) {
674             if (DEBUG) {
675                 System.out.println("** Valid VNA frames for " + edge);
676                 System.out.println("** Block : " + blockValueNumberFrame);
677                 System.out.println("** Target: " + targetValueNumberFrame);
678             }
679
680             for (int i = 0; i < blockValueNumberFrame.getNumSlots(); i++) {
681                 ValueNumber blockVN = blockValueNumberFrame.getValue(i);
682                 ValueNumber targetVN = targetValueNumberFrame.getValue(i);
683                 fact.clearDerefSet(blockVN);
684                 if (originalFact.isUnconditionallyDereferenced(targetVN))
685                     fact.setDerefSet(blockVN, originalFact.getUnconditionalDerefLocationSet(targetVN));
686
687             } // for all slots
688
689             for(ValueNumber blockVN : blockValueNumberFrame.valueNumbersForLoads()) {
690                 AvailableLoad load = blockValueNumberFrame.getLoad(blockVN);
691                 if (load == null) continue;
692                 ValueNumber [] targetVNs = targetValueNumberFrame.getAvailableLoad(load);
693                 if (targetVNs != null)
694                     for(ValueNumber targetVN : targetVNs)
695                         if (targetVN.hasFlag(ValueNumber.PHI_NODE) && fact.isUnconditionallyDereferenced(targetVN)
696                                 && !fact.isUnconditionallyDereferenced(blockVN)) {
697                             // Block VN is also dereferenced unconditionally.
698 AvailableLoad targetLoad = targetValueNumberFrame.getLoad(targetVN);
699                             if (!load.equals(targetLoad)) continue;
700                             if (DEBUG) {
701                                 System.out.println("** Copy vn derefs for " + load +" from " + targetVN +
702                                         " --> " + blockVN);
703                                 System.out.println("** block phi for " + System.identityHashCode(blockValueNumberFrame)
704                                         + "is " + blockValueNumberFrame.phiNodeForLoads);
705                                 System.out.println("** target phi for " + System.identityHashCode(targetValueNumberFrame)
706                                         + "is " + targetValueNumberFrame.phiNodeForLoads);
707                             }
708                             fact.setDerefSet(blockVN, fact.getUnconditionalDerefLocationSet(targetVN));
709
710                         }
711
712             }
713         }
714         if (DEBUG) {
715             System.out.println("Target VNF: " + targetValueNumberFrame);
716             System.out.println("Block VNF: " + blockValueNumberFrame);
717             System.out.println("fact: " + fact);
718         }
719         fact.cleanDerefSet(null, blockValueNumberFrame);
720         return fact;
721     }
722
723     /**
724      * Return a duplicate of given dataflow fact.
725      *
726      * @param fact a dataflow fact
727      * @return a duplicate of the input dataflow fact
728      */
729     private UnconditionalValueDerefSet duplicateFact(UnconditionalValueDerefSet fact) {
730         UnconditionalValueDerefSet copyOfFact = createFact();
731         copy(fact, copyOfFact);
732         fact = copyOfFact;
733         return fact;
734     }
735
736     /**
737      * Clear deref sets of values if this edge is the non-null branch
738      * of an if comparison.
739      *
740      * @param fact a datflow fact
741      * @param edge edge to check
742      * @return possibly-modified dataflow fact
743      */
744     private @CheckForNull ValueNumber findValueKnownNonnullOnBranch(
745             UnconditionalValueDerefSet fact, Edge edge) {
746         
747         IsNullValueFrame invFrame = invDataflow.getResultFact(edge.getSource());
748         if (!invFrame.isValid()) {
749             return null;
750         }
751         IsNullConditionDecision decision = invFrame.getDecision();
752         if (decision == null) {
753             return null;
754         }
755         
756         IsNullValue inv = decision.getDecision(edge.getType());
757         if (inv == null || !inv.isDefinitelyNotNull()) {
758             return null;
759         }
760         ValueNumber value = decision.getValue();
761         if (DEBUG) {
762             System.out.println("Value number " + value + " is known nonnull on " + edge);
763         }
764         
765         return value;
766     }
767
768     /**
769      * Determine whether dataflow should be propagated on given edge.
770      *
771      * @param edge the edge
772      * @return true if dataflow should be propagated on the edge, false otherwise
773      */
774     private boolean ignoreThisEdge(Edge edge) {
775         return edge.isExceptionEdge();
776     }
777
778     /* (non-Javadoc)
779      * @see edu.umd.cs.findbugs.ba.DataflowAnalysis#same(java.lang.Object, java.lang.Object)
780      */
781     public boolean same(UnconditionalValueDerefSet fact1, UnconditionalValueDerefSet fact2) {
782         return fact1.resultsFromBackEdge || fact1.isSameAs(fact2);
783     }
784
785     @Override JavaDoc
786     public void startIteration() {
787         // System.out.println("analysis iteration in " + methodGen.getClassName() + " on " + methodGen.toString());
788 }
789     
790     @Override JavaDoc
791     public int getLastUpdateTimestamp(UnconditionalValueDerefSet fact) {
792         return fact.getLastUpdateTimestamp();
793     }
794     @Override JavaDoc
795     public void setLastUpdateTimestamp(UnconditionalValueDerefSet fact, int lastUpdate) {
796         fact.setLastUpdateTimestamp(lastUpdate);
797     }
798     public static void main(String JavaDoc[] args) throws Exception JavaDoc {
799         if (args.length != 1) {
800             System.err.println("Usage: " + UnconditionalValueDerefAnalysis.class.getName() + " <classfile>");
801             System.exit(1);
802         }
803         
804         DataflowTestDriver<UnconditionalValueDerefSet, UnconditionalValueDerefAnalysis> driver =
805             new DataflowTestDriver<UnconditionalValueDerefSet, UnconditionalValueDerefAnalysis>() {
806             /* (non-Javadoc)
807              * @see edu.umd.cs.findbugs.ba.DataflowTestDriver#createDataflow(edu.umd.cs.findbugs.ba.ClassContext, org.apache.bcel.classfile.Method)
808              */
809             @Override JavaDoc
810             public Dataflow<UnconditionalValueDerefSet, UnconditionalValueDerefAnalysis> createDataflow(ClassContext classContext, Method method) throws CFGBuilderException, DataflowAnalysisException {
811                 return classContext.getUnconditionalValueDerefDataflow(method);
812             }
813         };
814         if (SystemProperties.getBoolean("forwardcfg")) {
815             driver.overrideIsForwards();
816         }
817         driver.execute(args[0]);
818     }
819 }
Popular Tags