KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > edu > umd > cs > findbugs > ba > npe > IsNullValueAnalysis


1 /*
2  * Bytecode Analysis Framework
3  * Copyright (C) 2003-2005 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.npe;
21
22 import java.util.BitSet JavaDoc;
23 import java.util.HashSet JavaDoc;
24 import java.util.Iterator JavaDoc;
25 import java.util.Set JavaDoc;
26
27 import org.apache.bcel.Constants;
28 import org.apache.bcel.classfile.Method;
29 import org.apache.bcel.generic.CodeExceptionGen;
30 import org.apache.bcel.generic.Instruction;
31 import org.apache.bcel.generic.InstructionHandle;
32 import org.apache.bcel.generic.MethodGen;
33 import org.apache.bcel.generic.ObjectType;
34
35 import edu.umd.cs.findbugs.SystemProperties;
36 import edu.umd.cs.findbugs.annotations.CheckForNull;
37 import edu.umd.cs.findbugs.annotations.Nullable;
38 import edu.umd.cs.findbugs.ba.AnalysisContext;
39 import edu.umd.cs.findbugs.ba.AnalysisFeatures;
40 import edu.umd.cs.findbugs.ba.AssertionMethods;
41 import edu.umd.cs.findbugs.ba.BasicBlock;
42 import edu.umd.cs.findbugs.ba.CFG;
43 import edu.umd.cs.findbugs.ba.CFGBuilderException;
44 import edu.umd.cs.findbugs.ba.ClassContext;
45 import edu.umd.cs.findbugs.ba.Dataflow;
46 import edu.umd.cs.findbugs.ba.DataflowAnalysisException;
47 import edu.umd.cs.findbugs.ba.DataflowTestDriver;
48 import edu.umd.cs.findbugs.ba.DepthFirstSearch;
49 import edu.umd.cs.findbugs.ba.Edge;
50 import edu.umd.cs.findbugs.ba.EdgeTypes;
51 import edu.umd.cs.findbugs.ba.FrameDataflowAnalysis;
52 import edu.umd.cs.findbugs.ba.JavaClassAndMethod;
53 import edu.umd.cs.findbugs.ba.Location;
54 import edu.umd.cs.findbugs.ba.NullnessAnnotation;
55 import edu.umd.cs.findbugs.ba.NullnessAnnotationDatabase;
56 import edu.umd.cs.findbugs.ba.XFactory;
57 import edu.umd.cs.findbugs.ba.XMethod;
58 import edu.umd.cs.findbugs.ba.XMethodParameter;
59 import edu.umd.cs.findbugs.ba.vna.AvailableLoad;
60 import edu.umd.cs.findbugs.ba.vna.ValueNumber;
61 import edu.umd.cs.findbugs.ba.vna.ValueNumberDataflow;
62 import edu.umd.cs.findbugs.ba.vna.ValueNumberFrame;
63
64 /**
65  * A dataflow analysis to detect potential null pointer dereferences.
66  *
67  * @author David Hovemeyer
68  * @see IsNullValue
69  * @see IsNullValueFrame
70  * @see IsNullValueFrameModelingVisitor
71  */
72 public class IsNullValueAnalysis
73         extends FrameDataflowAnalysis<IsNullValue, IsNullValueFrame>
74         implements EdgeTypes, IsNullValueAnalysisFeatures {
75     static final boolean DEBUG = SystemProperties.getBoolean("inva.debug");
76
77     static {
78         if (DEBUG) System.out.println("inva.debug enabled");
79     }
80
81     private MethodGen methodGen;
82     private IsNullValueFrameModelingVisitor visitor;
83     private ValueNumberDataflow vnaDataflow;
84     private int[] numNonExceptionSuccessorMap;
85     private Set JavaDoc<LocationWhereValueBecomesNull> locationWhereValueBecomesNullSet;
86     private final boolean trackValueNumbers;
87
88     private IsNullValueFrame lastFrame;
89     private IsNullValueFrame instanceOfFrame;
90     private IsNullValueFrame cachedEntryFact;
91     
92     private JavaClassAndMethod classAndMethod;
93
94     public IsNullValueAnalysis(MethodGen methodGen, CFG cfg, ValueNumberDataflow vnaDataflow, DepthFirstSearch dfs,
95                                AssertionMethods assertionMethods) {
96         super(dfs);
97         
98         this.trackValueNumbers = AnalysisContext.currentAnalysisContext().getBoolProperty(
99                 AnalysisFeatures.TRACK_VALUE_NUMBERS_IN_NULL_POINTER_ANALYSIS);
100         
101         this.methodGen = methodGen;
102         this.visitor = new IsNullValueFrameModelingVisitor(
103                 methodGen.getConstantPool(),
104                 assertionMethods,
105                 vnaDataflow,
106                 trackValueNumbers);
107         this.vnaDataflow = vnaDataflow;
108         this.numNonExceptionSuccessorMap = new int[cfg.getNumBasicBlocks()];
109         this.locationWhereValueBecomesNullSet = new HashSet JavaDoc<LocationWhereValueBecomesNull>();
110
111         // For each basic block, calculate the number of non-exception successors.
112 Iterator JavaDoc<Edge> i = cfg.edgeIterator();
113         while (i.hasNext()) {
114             Edge edge = i.next();
115             if (edge.isExceptionEdge())
116                 continue;
117             int srcBlockId = edge.getSource().getId();
118             numNonExceptionSuccessorMap[srcBlockId]++;
119         }
120         if (DEBUG) {
121             System.out.println("IsNullValueAnalysis for " + methodGen.getClassName() + "." + methodGen.getName() + " : " + methodGen.getSignature());
122         }
123     }
124     
125         
126     
127     public void setClassAndMethod(JavaClassAndMethod classAndMethod) {
128         this.classAndMethod = classAndMethod;
129     }
130     public JavaClassAndMethod getClassAndMethod( ) {
131         return classAndMethod;
132     }
133     public IsNullValueFrame createFact() {
134         return new IsNullValueFrame(methodGen.getMaxLocals(), trackValueNumbers);
135     }
136     
137
138
139     public void initEntryFact(IsNullValueFrame result) {
140         if (cachedEntryFact == null) {
141             
142             cachedEntryFact = createFact();
143             cachedEntryFact.setValid();
144
145             int numLocals = methodGen.getMaxLocals();
146             boolean instanceMethod = !methodGen.isStatic();
147             XMethod xm = XFactory.createXMethod(methodGen.getClassName(),
148                     methodGen.getName(), methodGen.getSignature(), methodGen.isStatic());
149             NullnessAnnotationDatabase db = AnalysisContext.currentAnalysisContext().getNullnessAnnotationDatabase();
150             int paramShift = instanceMethod ? 1 : 0;
151             for (int i = 0; i < numLocals; ++i) {
152                 IsNullValue value;
153                 
154                 int paramIndex = i - paramShift;
155                 
156                 if (instanceMethod && i == 0) {
157                     value = IsNullValue.nonNullValue();
158                 } else if (paramIndex >= methodGen.getArgumentTypes().length) {
159                     value = IsNullValue.nonReportingNotNullValue();
160                 } else {
161                     XMethodParameter methodParameter = new XMethodParameter(xm, paramIndex);
162                     NullnessAnnotation n = db.getResolvedAnnotation(methodParameter, false);
163                     if (n == NullnessAnnotation.CHECK_FOR_NULL)
164                         // Parameter declared @CheckForNull
165 value = IsNullValue.parameterMarkedAsMightBeNull(methodParameter);
166                     else if (n == NullnessAnnotation.NONNULL)
167                         // Parameter declared @NonNull
168 // TODO: label this so we don't report defensive programming
169 value = IsNullValue.nonNullValue();
170                     else
171                         // Don't know; use default value, normally non-reporting nonnull
172 value = IsNullValue.nonReportingNotNullValue();
173                 }
174                 
175                 cachedEntryFact.setValue(i, value);
176             }
177         }
178         copy(cachedEntryFact, result);
179     }
180
181     
182     @Override JavaDoc
183     public void transfer(BasicBlock basicBlock, @CheckForNull InstructionHandle end, IsNullValueFrame start, IsNullValueFrame result)
184     throws DataflowAnalysisException {
185         startTransfer();
186         super.transfer(basicBlock, end, start, result);
187         endTransfer(basicBlock, end, result);
188         ValueNumberFrame vnaFrameAfter = vnaDataflow.getFactAfterLocation(Location.getLastLocation(basicBlock));
189         // purge stale information
190 if (!vnaFrameAfter.isTop())
191             result.cleanStaleKnowledge(vnaFrameAfter);
192     }
193
194     public void startTransfer() throws DataflowAnalysisException {
195         lastFrame = null;
196         instanceOfFrame = null;
197     }
198
199     public void endTransfer(BasicBlock basicBlock, @CheckForNull InstructionHandle end, IsNullValueFrame result)
200             throws DataflowAnalysisException {
201         // Determine if this basic block ends in a redundant branch.
202 if (end == null) {
203             if (lastFrame == null)
204                 result.setDecision(null);
205             else {
206                 IsNullConditionDecision decision = getDecision(basicBlock, lastFrame);
207                 //if (DEBUG) System.out.println("Decision=" + decision);
208 result.setDecision(decision);
209             }
210         }
211         lastFrame = null;
212         instanceOfFrame = null;
213     }
214
215     @Override JavaDoc
216     public void transferInstruction(InstructionHandle handle, BasicBlock basicBlock, IsNullValueFrame fact)
217             throws DataflowAnalysisException {
218
219         // If this is the last instruction in the block,
220 // save the result immediately before the instruction.
221 if (handle == basicBlock.getLastInstruction()) {
222             lastFrame = createFact();
223             lastFrame.copyFrom(fact);
224         }
225
226         if (handle.getInstruction().getOpcode() == Constants.INSTANCEOF) {
227             instanceOfFrame = createFact();
228             instanceOfFrame.copyFrom(fact);
229         }
230         
231         // Model the instruction
232 visitor.setFrameAndLocation(fact, new Location(handle, basicBlock));
233         Instruction ins = handle.getInstruction();
234         visitor.analyzeInstruction(ins);
235
236         // Special case:
237 // The instruction may have produced previously seen values
238 // about which new is-null information is known.
239 // If any other instances of the produced values exist,
240 // update their is-null information.
241 // Also, make a note of any newly-produced null values.
242
243         int numProduced = ins.produceStack(methodGen.getConstantPool());
244         if (numProduced == Constants.UNPREDICTABLE)
245             throw new DataflowAnalysisException("Unpredictable stack production", methodGen, handle);
246
247         int start = fact.getNumSlots() - numProduced;
248         Location location = new Location(handle, basicBlock);
249         ValueNumberFrame vnaFrameAfter = vnaDataflow.getFactAfterLocation(location);
250
251         for (int i = start; i < fact.getNumSlots(); ++i) {
252             ValueNumber value = vnaFrameAfter.getValue(i);
253             IsNullValue isNullValue = fact.getValue(i);
254
255             for (int j = 0; j < start; ++j) {
256                 ValueNumber otherValue = vnaFrameAfter.getValue(j);
257                 if (value.equals(otherValue)) {
258                     // Same value is in both slots.
259 // Update the is-null information to match
260 // the new information.
261 fact.setValue(j, isNullValue);
262                 }
263             }
264         }
265         
266         if (visitor.getSlotContainingNewNullValue() >= 0) {
267             ValueNumber newNullValue = vnaFrameAfter.getValue(visitor.getSlotContainingNewNullValue());
268             addLocationWhereValueBecomesNull(new LocationWhereValueBecomesNull(
269                     location,
270                     newNullValue//,
271 //handle
272 ));
273         }
274
275     }
276
277     private static final BitSet JavaDoc nullComparisonInstructionSet = new BitSet JavaDoc();
278
279     static {
280         nullComparisonInstructionSet.set(Constants.IFNULL);
281         
282         nullComparisonInstructionSet.set(Constants.IFNONNULL);
283         nullComparisonInstructionSet.set(Constants.IF_ACMPEQ);
284         nullComparisonInstructionSet.set(Constants.IF_ACMPNE);
285     }
286
287     public void meetInto(IsNullValueFrame fact, Edge edge, IsNullValueFrame result)
288             throws DataflowAnalysisException {
289
290         if (fact.isValid()) {
291             IsNullValueFrame tmpFact = null;
292
293             final int numSlots = fact.getNumSlots();
294
295             if (!NO_SPLIT_DOWNGRADE_NSP) {
296                 // Downgrade NSP to DNR on non-exception control splits
297 if (!edge.isExceptionEdge()
298                         && numNonExceptionSuccessorMap[edge.getSource().getId()] > 1) {
299                     tmpFact = modifyFrame(fact, tmpFact);
300                     tmpFact.downgradeOnControlSplit();
301                 }
302             }
303
304             if (!NO_SWITCH_DEFAULT_AS_EXCEPTION) {
305                 if (edge.getType() == SWITCH_DEFAULT_EDGE) {
306                     tmpFact = modifyFrame(fact, tmpFact);
307                     tmpFact.toExceptionValues();
308                 }
309             }
310
311             final BasicBlock destBlock = edge.getTarget();
312
313             if (destBlock.isExceptionHandler()) {
314                 // Exception handler - clear stack and push a non-null value
315 // to represent the exception.
316 tmpFact = modifyFrame(fact, tmpFact);
317                 tmpFact.clearStack();
318
319                 // Downgrade NULL and NSP to DNR if the handler is for
320 // CloneNotSupportedException or InterruptedException
321 if (true) {
322                 CodeExceptionGen handler = destBlock.getExceptionGen();
323                 ObjectType catchType = handler.getCatchType();
324                 if (catchType != null) {
325                     String JavaDoc catchClass = catchType.getClassName();
326                     if (catchClass.equals("java.lang.CloneNotSupportedException") ||
327                             catchClass.equals("java.lang.InterruptedException")) {
328                         for (int i = 0; i < tmpFact.getNumSlots(); ++i) {
329                             IsNullValue value = tmpFact.getValue(i);
330                             if (value.isDefinitelyNull() || value.isNullOnSomePath())
331                                 tmpFact.setValue(i, IsNullValue.nullOnComplexPathValue());
332                         }
333                     }
334                 }
335                 }
336
337                 // Mark all values as having occurred on an exception path
338 tmpFact.toExceptionValues();
339
340                 // Push the exception value
341 tmpFact.pushValue(IsNullValue.nonNullValue());
342             } else {
343                 final int edgeType = edge.getType();
344                 final BasicBlock sourceBlock = edge.getSource();
345                 final BasicBlock targetBlock = edge.getTarget();
346                 final ValueNumberFrame targetVnaFrame = vnaDataflow.getStartFact(destBlock);
347                 final ValueNumberFrame sourceVnaFrame = vnaDataflow.getResultFact(sourceBlock);
348                 
349                 
350                 assert targetVnaFrame != null;
351
352                 // Determine if the edge conveys any information about the
353 // null/non-null status of operands in the incoming frame.
354 if (edgeType == IFCMP_EDGE || edgeType == FALL_THROUGH_EDGE) {
355                     IsNullConditionDecision decision = getResultFact(edge.getSource()).getDecision();
356                     if (decision != null) {
357                         if (!decision.isEdgeFeasible(edgeType)) {
358                             // The incoming edge is infeasible; just use TOP
359 // as the start fact for this block.
360 tmpFact = createFact();
361                             tmpFact.setTop();
362                         } else if (decision.getValue() != null) {
363                             // A value has been determined for this edge.
364 // Use the value to update the is-null information in
365 // the start fact for this block.
366
367                             if (DEBUG) {
368                                 System.out.println("Updating edge information for " + decision.getValue());
369                             }
370                             final Location atIf = new Location(sourceBlock.getLastInstruction(), sourceBlock);
371                             // TODO: prevIsNullValueFrame is not used
372 final IsNullValueFrame prevIsNullValueFrame = getFactAtLocation(atIf);
373                             final ValueNumberFrame prevVnaFrame = vnaDataflow.getFactAtLocation(atIf);
374                             
375                             IsNullValue decisionValue = decision.getDecision(edgeType);
376                             if (decisionValue != null) {
377                                 if (decisionValue.isDefinitelyNull()) {
378                                     // Make a note of the value that has become null
379 // due to the if comparison.
380 addLocationWhereValueBecomesNull(new LocationWhereValueBecomesNull(
381                                             atIf,
382                                             decision.getValue()
383                                     ));
384                                 }
385                                 if (DEBUG) {
386                                     System.out.println("Set decision information");
387                                     System.out.println(" " + decision.getValue() + " becomes " + decisionValue);
388                                     System.out.println(" prev available loads: " + prevVnaFrame.availableLoadMapAsString());
389                                     System.out.println(" target available loads: " + targetVnaFrame.availableLoadMapAsString());
390                                 }
391                                 tmpFact = replaceValues(fact, tmpFact, decision.getValue(), prevVnaFrame,
392                                         targetVnaFrame, decisionValue);
393                             }
394
395                         }
396                     }
397                 } // if (edgeType == IFCMP_EDGE || edgeType == FALL_THROUGH_EDGE)
398
399                 // If this is a fall-through edge from a null check,
400 // then we know the value checked is not null.
401 if (sourceBlock.isNullCheck() && edgeType == FALL_THROUGH_EDGE) {
402                     ValueNumberFrame vnaFrame = vnaDataflow.getStartFact(destBlock);
403                     if (vnaFrame == null)
404                         throw new IllegalStateException JavaDoc("no vna frame at block entry?");
405
406                     Instruction firstInDest = edge.getTarget().getFirstInstruction().getInstruction();
407             
408         
409                     IsNullValue instance = fact.getInstance(firstInDest, methodGen.getConstantPool());
410                     
411                     
412                     if (instance.isDefinitelyNull()) {
413                         // If we know the variable is null, this edge is infeasible
414 tmpFact = createFact();
415                         tmpFact.setTop();
416                     }
417                     else if (!instance.isDefinitelyNotNull()) {
418                         // If we're not sure that the instance is definitely non-null,
419 // update the is-null information for the dereferenced value.
420 InstructionHandle kaBoomLocation = targetBlock.getFirstInstruction();
421                         ValueNumber replaceMe = vnaFrame.getInstance(firstInDest, methodGen.getConstantPool());
422                         IsNullValue noKaboomNonNullValue = IsNullValue.noKaboomNonNullValue(
423                                                         new Location(kaBoomLocation, targetBlock)
424                                                         );
425                         if (DEBUG) {
426                             System.out.println("Start vna fact: " + vnaFrame);
427                             System.out.println("inva fact: " + fact);
428                             System.out.println("\nGenerated NoKaboom value for location " + kaBoomLocation);
429                             System.out.println("Dereferenced " + instance);
430                             System.out.println("On fall through from source block " + sourceBlock);
431                         }
432                         tmpFact = replaceValues(fact, tmpFact, replaceMe, vnaFrame, targetVnaFrame, noKaboomNonNullValue);
433                     }
434                 } // if (sourceBlock.isNullCheck() && edgeType == FALL_THROUGH_EDGE)
435
436                 if (targetVnaFrame.phiNodeForLoads) {
437                     if (DEBUG)
438                         System.out.println("Is phi node for loads");
439                     for(ValueNumber v : fact.getKnownValues()) {
440                         AvailableLoad loadForV = sourceVnaFrame.getLoad(v);
441                         if (DEBUG) {
442                             System.out.println(" " + v + " for " + loadForV);
443                         }
444                         if (loadForV != null) {
445                             ValueNumber[] matchingValueNumbers = targetVnaFrame.getAvailableLoad(loadForV);
446                             if (matchingValueNumbers != null)
447                                 for(ValueNumber v2 : matchingValueNumbers) {
448                                     tmpFact = modifyFrame(fact, tmpFact);
449                                     tmpFact.useNewValueNumberForLoad(v, v2);
450                                     if (DEBUG) System.out.println("For " + loadForV + " switch from " + v + " to " + v2);
451                                 }
452                         }
453
454                     }
455                 }
456             }
457             if (tmpFact != null)
458                 fact = tmpFact;
459         } // if (fact.isValid())
460
461         // Normal dataflow merge
462 mergeInto(fact, result);
463     }
464
465     /* (non-Javadoc)
466      * @see edu.umd.cs.findbugs.ba.FrameDataflowAnalysis#mergeInto(edu.umd.cs.findbugs.ba.Frame, edu.umd.cs.findbugs.ba.Frame)
467      */
468     @Override JavaDoc
469     protected void mergeInto(IsNullValueFrame other, IsNullValueFrame result) throws DataflowAnalysisException {
470         if (other.isTop()) return;
471         if (result.isTop()) {
472             result.copyFrom(other);
473             return;
474         }
475         super.mergeInto(other, result);
476         //FIXME: update decision?
477 if (trackValueNumbers) {
478             result.mergeKnownValuesWith(other);
479         }
480         
481     }
482     
483     /* (non-Javadoc)
484      * @see edu.umd.cs.findbugs.ba.AbstractDataflowAnalysis#startIteration()
485      */
486     @Override JavaDoc
487     public void startIteration() {
488         // At the beginning of each iteration, clear the set of locations
489 // where values become null. That way, after the final iteration
490 // of dataflow analysis the set should be as accurate as possible.
491 locationWhereValueBecomesNullSet.clear();
492     }
493     
494     public void addLocationWhereValueBecomesNull(LocationWhereValueBecomesNull locationWhereValueBecomesNull) {
495         // System.out.println("Location becomes null: " + locationWhereValueBecomesNull );
496 locationWhereValueBecomesNullSet.add(locationWhereValueBecomesNull);
497     }
498     
499     public Set JavaDoc<LocationWhereValueBecomesNull> getLocationWhereValueBecomesNullSet() {
500         return locationWhereValueBecomesNullSet;
501     }
502
503     @Override JavaDoc
504     protected void mergeValues(IsNullValueFrame otherFrame, IsNullValueFrame resultFrame, int slot)
505             throws DataflowAnalysisException {
506         IsNullValue value = IsNullValue.merge(resultFrame.getValue(slot), otherFrame.getValue(slot));
507         resultFrame.setValue(slot, value);
508     }
509
510     /**
511      * Determine if the given basic block ends in a redundant
512      * null comparison.
513      *
514      * @param basicBlock the basic block
515      * @param lastFrame the IsNullValueFrame representing values at the final instruction
516      * of the block
517      * @return an IsNullConditionDecision object representing the
518      * is-null information gained about the compared value,
519      * or null if no information is gained
520      */
521     private IsNullConditionDecision getDecision(BasicBlock basicBlock, IsNullValueFrame lastFrame)
522             throws DataflowAnalysisException {
523
524         assert lastFrame != null;
525
526         final InstructionHandle lastInSourceHandle = basicBlock.getLastInstruction();
527         if (lastInSourceHandle == null)
528             return null; // doesn't end in null comparison
529
530         final short lastInSourceOpcode = lastInSourceHandle.getInstruction().getOpcode();
531         // System.out.println("last opcode: " + Constants.OPCODE_NAMES[lastInSourceOpcode]);
532 if (lastInSourceOpcode == Constants.IFEQ || lastInSourceOpcode == Constants.IFNE ) {
533             InstructionHandle prev = lastInSourceHandle.getPrev();
534             if (prev == null) return null;
535             short secondToLastOpcode = prev.getInstruction().getOpcode();
536             // System.out.println("Second last opcode: " + Constants.OPCODE_NAMES[secondToLastOpcode]);
537 if (secondToLastOpcode != Constants.INSTANCEOF) return null;
538             IsNullValue tos = instanceOfFrame.getTopValue();
539             boolean isNotInstanceOf = (lastInSourceOpcode != Constants.IFNE);
540             Location atInstanceOf = new Location(prev, basicBlock);
541             ValueNumberFrame instanceOfVnaFrame = vnaDataflow.getFactAtLocation(atInstanceOf);
542     
543             // Initially, assume neither branch is feasible.
544 IsNullValue ifcmpDecision = null;
545             IsNullValue fallThroughDecision = null;
546
547             if (tos.isDefinitelyNull()) {
548                 // Predetermined comparison - one branch is infeasible
549 if (isNotInstanceOf)
550                     ifcmpDecision =tos;
551                 else // ifnonnull
552 fallThroughDecision = tos;
553             } else if (tos.isDefinitelyNotNull()) {
554                 return null;
555             } else {
556                 // As far as we know, both branches feasible
557 ifcmpDecision = isNotInstanceOf ? tos : IsNullValue.pathSensitiveNonNullValue();
558                 fallThroughDecision = isNotInstanceOf ? IsNullValue.pathSensitiveNonNullValue() : tos;
559             }
560              if (DEBUG) System.out.println("Checking..." + tos + " -> " + ifcmpDecision + " or " + fallThroughDecision);
561                 
562             return new IsNullConditionDecision(instanceOfVnaFrame.getTopValue(), ifcmpDecision, fallThroughDecision);
563
564         }
565         if (!nullComparisonInstructionSet.get(lastInSourceOpcode))
566             return null; // doesn't end in null comparison
567
568         Location atIf = new Location(lastInSourceHandle, basicBlock);
569         ValueNumberFrame prevVnaFrame = vnaDataflow.getFactAtLocation(atIf);
570
571         switch (lastInSourceOpcode) {
572     
573         case Constants.IFNULL:
574         case Constants.IFNONNULL:
575             {
576                 IsNullValue tos = lastFrame.getTopValue();
577                 boolean ifnull = (lastInSourceOpcode == Constants.IFNULL);
578
579                 // Initially, assume neither branch is feasible.
580 IsNullValue ifcmpDecision = null;
581                 IsNullValue fallThroughDecision = null;
582
583                 if (tos.isDefinitelyNull()) {
584                     // Predetermined comparison - one branch is infeasible
585 if (ifnull)
586                         ifcmpDecision = IsNullValue.pathSensitiveNullValue();
587                     else // ifnonnull
588 fallThroughDecision = IsNullValue.pathSensitiveNullValue();
589                 } else if (tos.isDefinitelyNotNull()) {
590                     // Predetermined comparison - one branch is infeasible
591 if (ifnull)
592                         fallThroughDecision = IsNullValue.pathSensitiveNonNullValue();
593                     else // ifnonnull
594 ifcmpDecision = IsNullValue.pathSensitiveNonNullValue();
595                 } else {
596                     // As far as we know, both branches feasible
597 ifcmpDecision = ifnull ? IsNullValue.pathSensitiveNullValue() : IsNullValue.pathSensitiveNonNullValue();
598                     fallThroughDecision = ifnull ? IsNullValue.pathSensitiveNonNullValue() : IsNullValue.pathSensitiveNullValue();
599                 }
600                 return new IsNullConditionDecision(prevVnaFrame.getTopValue(), ifcmpDecision, fallThroughDecision);
601             }
602         case Constants.IF_ACMPEQ:
603         case Constants.IF_ACMPNE:
604             {
605                 IsNullValue tos = lastFrame.getStackValue(0);
606                 IsNullValue nextToTos = lastFrame.getStackValue(1);
607
608                 boolean tosNull = tos.isDefinitelyNull();
609                 boolean nextToTosNull = nextToTos.isDefinitelyNull();
610
611                 boolean cmpeq = (lastInSourceOpcode == Constants.IF_ACMPEQ);
612
613                 // Initially, assume neither branch is feasible.
614 IsNullValue ifcmpDecision = null;
615                 IsNullValue fallThroughDecision = null;
616                 ValueNumber value;
617
618                 if (tosNull && nextToTosNull) {
619                     // Redundant comparision: both values are null, only one branch is feasible
620 value = null; // no value will be replaced - just want to indicate that one of the branches is infeasible
621 if (cmpeq)
622                         ifcmpDecision = IsNullValue.pathSensitiveNullValue();
623                     else // cmpne
624 fallThroughDecision = IsNullValue.pathSensitiveNullValue();
625                 } else if (tosNull || nextToTosNull) {
626                     // We have updated information about whichever value is not null;
627 // both branches are feasible
628 value = prevVnaFrame.getStackValue(tosNull ? 1 : 0);
629                     ifcmpDecision = cmpeq ? IsNullValue.pathSensitiveNullValue() : IsNullValue.pathSensitiveNonNullValue();
630                     fallThroughDecision = cmpeq ? IsNullValue.pathSensitiveNonNullValue() : IsNullValue.pathSensitiveNullValue();
631                 } else if (tos.isDefinitelyNotNull() && !nextToTos.isDefinitelyNotNull()) {
632                     // learn that nextToTos is definitely non null on one branch
633 value = prevVnaFrame.getStackValue(1);
634                     if (cmpeq) {
635                         ifcmpDecision = tos;
636                         fallThroughDecision = nextToTos;
637                     } else {
638                         fallThroughDecision = tos;
639                         ifcmpDecision = nextToTos;
640                     }
641                 } else if (!tos.isDefinitelyNotNull() && nextToTos.isDefinitelyNotNull()) {
642                     // learn that tos is definitely non null on one branch
643 value = prevVnaFrame.getStackValue(0);
644                     if (cmpeq) {
645                         ifcmpDecision = nextToTos;
646                         fallThroughDecision = tos;
647                     } else {
648                         fallThroughDecision = nextToTos;
649                         ifcmpDecision = tos;
650                     }
651                 } else {
652                     // No information gained
653 break;
654                 }
655
656                 return new IsNullConditionDecision(value, ifcmpDecision, fallThroughDecision);
657             }
658         default:
659             throw new IllegalStateException JavaDoc();
660         }
661
662         return null; // no information gained
663 }
664
665     /**
666      * Update is-null information at a branch target based on information gained at a
667      * null comparison branch.
668      *
669      * @param origFrame the original is-null frame at entry to basic block
670      * @param frame the modified version of the is-null entry frame;
671      * null if the entry frame has not been modified yet
672      * @param replaceMe the ValueNumber in the value number frame at the if comparison
673      * whose is-null information will be updated
674      * @param prevVnaFrame the ValueNumberFrame at the if comparison
675      * @param targetVnaFrame the ValueNumberFrame at entry to the basic block
676      * @param replacementValue the IsNullValue representing the updated
677      * is-null information
678      * @return a modified IsNullValueFrame with updated is-null information
679      */
680     private IsNullValueFrame replaceValues(IsNullValueFrame origFrame, IsNullValueFrame frame,
681                                            ValueNumber replaceMe, ValueNumberFrame prevVnaFrame, ValueNumberFrame targetVnaFrame,
682                                           IsNullValue replacementValue) {
683
684         // If required, make a copy of the frame
685 frame = modifyFrame(origFrame, frame);
686
687         assert frame.getNumSlots() == targetVnaFrame.getNumSlots();
688
689         // The VNA frame may have more slots than the IsNullValueFrame
690 // if it was produced by an IF comparison (whose operand or operands
691 // are subsequently popped off the stack).
692
693         final int targetNumSlots = targetVnaFrame.getNumSlots();
694         final int prefixNumSlots = Math.min(frame.getNumSlots(), prevVnaFrame.getNumSlots());
695
696         if (trackValueNumbers) {
697             AvailableLoad loadForV = prevVnaFrame.getLoad(replaceMe);
698             if (DEBUG && loadForV != null) {
699                 System.out.println("For " + replaceMe + " availableLoad is " + loadForV);
700                 ValueNumber[] matchingValueNumbers = targetVnaFrame.getAvailableLoad(loadForV);
701                 if (matchingValueNumbers != null)
702                     for(ValueNumber v2 : matchingValueNumbers) System.out.println(" matches " + v2);
703             }
704             if (loadForV != null) {
705                 ValueNumber[] matchingValueNumbers = targetVnaFrame.getAvailableLoad(loadForV);
706                 if (matchingValueNumbers != null)
707                     for(ValueNumber v2 : matchingValueNumbers) if (!replaceMe.equals(v2)) {
708                         frame.setKnownValue(v2, replacementValue);
709                         if (DEBUG) System.out.println("For " + loadForV + " switch from " + replaceMe + " to " + v2);
710                     }
711             }
712             frame.setKnownValue(replaceMe, replacementValue);
713         }
714         // Here's the deal:
715 // - "replaceMe" is the value number from the previous frame (at the if branch)
716 // which indicates a value that we have updated is-null information about
717 // - in the target value number frame (at entry to the target block),
718 // we find the value number in the stack slot corresponding to the "replaceMe"
719 // value; this is the "corresponding" value
720 // - all instances of the "corresponding" value in the target frame have
721 // their is-null information updated to "replacementValue"
722 // This should thoroughly make use of the updated information.
723
724         for (int i = 0; i < prefixNumSlots; ++i) {
725             if (prevVnaFrame.getValue(i).equals(replaceMe)) {
726                 ValueNumber corresponding = targetVnaFrame.getValue(i);
727                 for (int j = 0; j < targetNumSlots; ++j) {
728                     if (targetVnaFrame.getValue(j).equals(corresponding))
729                         frame.setValue(j, replacementValue);
730                 }
731             }
732         }
733
734         return frame;
735
736     }
737
738     /**
739      * Test driver.
740      */
741     public static void main(String JavaDoc[] argv) throws Exception JavaDoc {
742         if (argv.length != 1) {
743             System.err.println("Usage: " + IsNullValueAnalysis.class.getName() + " <class file>");
744             System.exit(1);
745         }
746
747         DataflowTestDriver<IsNullValueFrame, IsNullValueAnalysis> driver = new DataflowTestDriver<IsNullValueFrame, IsNullValueAnalysis>() {
748             @Override JavaDoc
749             public Dataflow<IsNullValueFrame, IsNullValueAnalysis> createDataflow(ClassContext classContext, Method method)
750                     throws CFGBuilderException, DataflowAnalysisException {
751
752                 return classContext.getIsNullValueDataflow(method);
753             }
754         };
755
756         driver.execute(argv[0]);
757     }
758
759 }
760
761 // vim:ts=4
762
Popular Tags