001: /*
002: * Bytecode analysis framework
003: * Copyright (C) 2005, 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.npe;
021:
022: import java.util.BitSet;
023: import java.util.HashMap;
024: import java.util.HashSet;
025: import java.util.Iterator;
026: import java.util.LinkedList;
027: import java.util.List;
028: import java.util.Map;
029: import java.util.Set;
030: import java.util.SortedSet;
031: import java.util.TreeSet;
032:
033: import org.apache.bcel.Constants;
034: import org.apache.bcel.classfile.LineNumberTable;
035: import org.apache.bcel.classfile.Method;
036: import org.apache.bcel.generic.GETFIELD;
037: import org.apache.bcel.generic.GETSTATIC;
038: import org.apache.bcel.generic.Instruction;
039: import org.apache.bcel.generic.InstructionHandle;
040: import org.apache.bcel.generic.InvokeInstruction;
041:
042: import edu.umd.cs.findbugs.BugAnnotation;
043: import edu.umd.cs.findbugs.FieldAnnotation;
044: import edu.umd.cs.findbugs.LocalVariableAnnotation;
045: import edu.umd.cs.findbugs.SystemProperties;
046: import edu.umd.cs.findbugs.TigerSubstitutes;
047: import edu.umd.cs.findbugs.ba.AnalysisContext;
048: import edu.umd.cs.findbugs.ba.AnalysisFeatures;
049: import edu.umd.cs.findbugs.ba.AssertionMethods;
050: import edu.umd.cs.findbugs.ba.BasicBlock;
051: import edu.umd.cs.findbugs.ba.CFGBuilderException;
052: import edu.umd.cs.findbugs.ba.ClassContext;
053: import edu.umd.cs.findbugs.ba.DataflowAnalysisException;
054: import edu.umd.cs.findbugs.ba.Edge;
055: import edu.umd.cs.findbugs.ba.EdgeTypes;
056: import edu.umd.cs.findbugs.ba.Location;
057: import edu.umd.cs.findbugs.ba.MissingClassException;
058: import edu.umd.cs.findbugs.ba.PostDominatorsAnalysis;
059: import edu.umd.cs.findbugs.ba.XField;
060: import edu.umd.cs.findbugs.ba.deref.UnconditionalValueDerefDataflow;
061: import edu.umd.cs.findbugs.ba.deref.UnconditionalValueDerefSet;
062: import edu.umd.cs.findbugs.ba.vna.ValueNumber;
063: import edu.umd.cs.findbugs.ba.vna.ValueNumberDataflow;
064: import edu.umd.cs.findbugs.ba.vna.ValueNumberFrame;
065: import edu.umd.cs.findbugs.ba.vna.ValueNumberSourceInfo;
066: import edu.umd.cs.findbugs.classfile.CheckedAnalysisException;
067: import edu.umd.cs.findbugs.log.Profiler;
068:
069: /**
070: * A user-friendly front end for finding null pointer dereferences
071: * and redundant null comparisions.
072: *
073: * @see IsNullValueAnalysis
074: * @author David Hovemeyer
075: */
076: public class NullDerefAndRedundantComparisonFinder {
077: private static final boolean DEBUG = SystemProperties
078: .getBoolean("fnd.debug");
079: private static final boolean PRUNE_GUARANTEED_DEREFERENCES = SystemProperties
080: .getBoolean("fnd.prune", true);
081:
082: private static final boolean DEBUG_DEREFS = SystemProperties
083: .getBoolean("fnd.derefs.debug");
084:
085: private ClassContext classContext;
086: private Method method;
087: private NullDerefAndRedundantComparisonCollector collector;
088: private final boolean findGuaranteedDerefs;
089:
090: private List<RedundantBranch> redundantBranchList;
091: private BitSet definitelySameBranchSet;
092: private BitSet definitelyDifferentBranchSet;
093: private BitSet undeterminedBranchSet;
094: private BitSet lineMentionedMultipleTimes;
095:
096: private IsNullValueDataflow invDataflow;
097: private ValueNumberDataflow vnaDataflow;
098: private UnconditionalValueDerefDataflow uvdDataflow;
099: private AssertionMethods assertionMethods;
100:
101: static {
102: if (DEBUG)
103: System.out.println("fnd.debug enabled");
104: }
105:
106: /**
107: * Constructor.
108: *
109: * @param classContext the ClassContext
110: * @param method the method to analyze
111: * @param collector the NullDerefAndRedundantComparisonCollector used to report
112: * null derefs and redundant null comparisons
113: */
114: public NullDerefAndRedundantComparisonFinder(
115: ClassContext classContext, Method method,
116: NullDerefAndRedundantComparisonCollector collector) {
117:
118: this .classContext = classContext;
119: this .method = method;
120: this .collector = collector;
121: this .findGuaranteedDerefs = classContext
122: .getAnalysisContext()
123: .getBoolProperty(
124: AnalysisFeatures.TRACK_GUARANTEED_VALUE_DEREFS_IN_NULL_POINTER_ANALYSIS);
125: this .lineMentionedMultipleTimes = ClassContext
126: .linesMentionedMultipleTimes(method);
127:
128: this .redundantBranchList = new LinkedList<RedundantBranch>();
129: this .definitelySameBranchSet = new BitSet();
130: this .definitelyDifferentBranchSet = new BitSet();
131: this .undeterminedBranchSet = new BitSet();
132: this .assertionMethods = classContext.getAssertionMethods();
133: }
134:
135: public void execute() {
136: Profiler profiler = Profiler.getInstance();
137: profiler.start(this .getClass());
138: try {
139: // Do the null-value analysis
140: this .invDataflow = classContext
141: .getIsNullValueDataflow(method);
142: this .vnaDataflow = classContext
143: .getValueNumberDataflow(method);
144: if (findGuaranteedDerefs) {
145: if (DEBUG_DEREFS) {
146: System.out
147: .println("Checking for guaranteed derefs in "
148: + method.getName());
149: }
150: this .uvdDataflow = classContext
151: .getUnconditionalValueDerefDataflow(method);
152: }
153:
154: // Check method and report potential null derefs and
155: // redundant null comparisons.
156: examineBasicBlocks();
157: if (findGuaranteedDerefs) {
158: examineNullValues();
159: }
160: examineRedundantBranches();
161: } catch (MissingClassException e) {
162: AnalysisContext.reportMissingClass(e
163: .getClassNotFoundException());
164: } catch (CheckedAnalysisException e) {
165: AnalysisContext.logError(
166: "Error while for guaranteed derefs in "
167: + method.getName(), e);
168: } finally {
169: profiler.end(this .getClass());
170: }
171:
172: }
173:
174: /**
175: * Examine basic blocks for null checks and potentially-redundant
176: * null comparisons.
177: *
178: * @throws DataflowAnalysisException
179: * @throws CFGBuilderException
180: */
181: private void examineBasicBlocks() throws DataflowAnalysisException,
182: CFGBuilderException {
183: // Look for null check blocks where the reference being checked
184: // is definitely null, or null on some path
185: Iterator<BasicBlock> bbIter = invDataflow.getCFG()
186: .blockIterator();
187: while (bbIter.hasNext()) {
188: BasicBlock basicBlock = bbIter.next();
189:
190: if (basicBlock.isNullCheck()) {
191: analyzeNullCheck(classContext, method, invDataflow,
192: basicBlock);
193: } else if (!basicBlock.isEmpty()) {
194: // Look for all reference comparisons where
195: // - both values compared are definitely null, or
196: // - one value is definitely null and one is definitely not null
197: // These cases are not null dereferences,
198: // but they are quite likely to indicate an error, so while we've got
199: // information about null values, we may as well report them.
200: InstructionHandle lastHandle = basicBlock
201: .getLastInstruction();
202: Instruction last = lastHandle.getInstruction();
203: switch (last.getOpcode()) {
204: case Constants.IF_ACMPEQ:
205: case Constants.IF_ACMPNE:
206: analyzeRefComparisonBranch(basicBlock, lastHandle);
207: break;
208: case Constants.IFNULL:
209: case Constants.IFNONNULL:
210: analyzeIfNullBranch(basicBlock, lastHandle);
211: break;
212: }
213: }
214: }
215: }
216:
217: /**
218: * Examine null values.
219: * Report any that are guaranteed to be dereferenced on
220: * non-implicit-exception paths.
221: *
222: * @throws CFGBuilderException
223: * @throws DataflowAnalysisException
224: */
225: private void examineNullValues() throws CFGBuilderException,
226: DataflowAnalysisException {
227: Set<LocationWhereValueBecomesNull> locationWhereValueBecomesNullSet = invDataflow
228: .getAnalysis().getLocationWhereValueBecomesNullSet();
229: if (DEBUG_DEREFS) {
230: System.out
231: .println("----------------------- examineNullValues "
232: + locationWhereValueBecomesNullSet.size());
233: }
234:
235: Map<ValueNumber, SortedSet<Location>> bugStatementLocationMap = new HashMap<ValueNumber, SortedSet<Location>>();
236: // Inspect the method for locations where a null value is guaranteed to
237: // be dereferenced. Add the dereference locations
238: Map<ValueNumber, NullValueUnconditionalDeref> nullValueGuaranteedDerefMap = new HashMap<ValueNumber, NullValueUnconditionalDeref>();
239:
240: // Check every location
241: for (Iterator<Location> i = classContext.getCFG(method)
242: .locationIterator(); i.hasNext();) {
243: Location location = i.next();
244:
245: if (DEBUG_DEREFS) {
246: System.out.println("At location " + location);
247: }
248: if (false) {
249: Instruction in = location.getHandle().getInstruction();
250:
251: if (in instanceof InvokeInstruction
252: && in.produceStack(classContext
253: .getConstantPoolGen()) == 1
254: || in instanceof GETFIELD
255: || in instanceof GETSTATIC) {
256: IsNullValueFrame invFrame = invDataflow
257: .getFactAfterLocation(location);
258: if (invFrame.getStackDepth() > 0) {
259: IsNullValue isNullValue = invFrame
260: .getTopValue();
261: if (isNullValue.isNullOnSomePath()) {
262: // OK, must be from return value
263: ValueNumber vn = vnaDataflow
264: .getFactAfterLocation(location)
265: .getTopValue();
266: UnconditionalValueDerefSet uvd = uvdDataflow
267: .getFactAfterLocation(location);
268: if (uvd.isUnconditionallyDereferenced(vn)) {
269: // System.out.println("Found it");
270: SortedSet<Location> knownNullAndDoomedAt = bugStatementLocationMap
271: .get(vn);
272: noteUnconditionallyDereferencedNullValue(
273: location,
274: bugStatementLocationMap,
275: nullValueGuaranteedDerefMap,
276: uvd, isNullValue, vn);
277: }
278: }
279: }
280: }
281:
282: if (assertionMethods.isAssertionInstruction(in,
283: classContext.getConstantPoolGen())) {
284: if (DEBUG_DEREFS)
285: System.out
286: .println("Skipping because it is an assertion method ");
287: continue;
288: }
289:
290: }
291:
292: checkForUnconditionallyDereferencedNullValues(location,
293: bugStatementLocationMap,
294: nullValueGuaranteedDerefMap, vnaDataflow
295: .getFactAtLocation(location), invDataflow
296: .getFactAtLocation(location), uvdDataflow
297: .getFactAfterLocation(location));
298: }
299: HashSet<ValueNumber> npeIfStatementCovered = new HashSet<ValueNumber>(
300: nullValueGuaranteedDerefMap.keySet());
301: Map<ValueNumber, SortedSet<Location>> bugEdgeLocationMap = new HashMap<ValueNumber, SortedSet<Location>>();
302:
303: // Check every non-exception control edge
304: for (Iterator<Edge> i = classContext.getCFG(method)
305: .edgeIterator(); i.hasNext();) {
306: Edge edge = i.next();
307:
308: if (edge.isExceptionEdge()) {
309: continue;
310: }
311:
312: if (DEBUG_DEREFS) {
313: System.out.println("On edge "
314: + edge.formatAsString(false));
315: }
316:
317: ValueNumberFrame vnaFact = vnaDataflow.getResultFact(edge
318: .getSource());
319: ValueNumberFrame vnaEdgeFact = vnaDataflow
320: .getFactOnEdge(edge);
321: ValueNumberFrame vnaTargetFact = vnaDataflow
322: .getStartFact(edge.getTarget());
323:
324: IsNullValueFrame invFact = invDataflow
325: .getFactAtMidEdge(edge);
326:
327: IsNullValueFrame invSourceFact = invDataflow
328: .getResultFact(edge.getSource());
329: IsNullValueFrame invTargetFact = invDataflow
330: .getStartFact(edge.getTarget());
331: UnconditionalValueDerefSet uvdSourceFact = uvdDataflow
332: .getStartFact(edge.getSource());
333: UnconditionalValueDerefSet uvdTargetFact = uvdDataflow
334: .getResultFact(edge.getTarget());
335: Location location = Location.getLastLocation(edge
336: .getSource());
337:
338: UnconditionalValueDerefSet uvdFact = uvdDataflow
339: .getFactOnEdge(edge);
340: // UnconditionalValueDerefSet uvdFact = uvdDataflow.getStartFact(edge.getTarget());
341:
342: if (uvdFact.isEmpty())
343: continue;
344: if (location != null) {
345:
346: Instruction in = location.getHandle().getInstruction();
347: if (assertionMethods.isAssertionInstruction(in,
348: classContext.getConstantPoolGen())) {
349: if (DEBUG_DEREFS)
350: System.out
351: .println("Skipping because it is an assertion method ");
352: continue;
353: }
354:
355: checkForUnconditionallyDereferencedNullValues(location,
356: bugEdgeLocationMap,
357: nullValueGuaranteedDerefMap, vnaFact, invFact,
358: uvdFact);
359: }
360: }
361: Map<ValueNumber, SortedSet<Location>> bugLocationMap = bugEdgeLocationMap;
362: bugLocationMap.putAll(bugStatementLocationMap);
363: // For each value number that is null somewhere in the
364: // method, collect the set of locations where it becomes null.
365: // FIXME: we may see some locations that are not guaranteed to be dereferenced (how to fix this?)
366: Map<ValueNumber, Set<Location>> nullValueAssignmentMap = new HashMap<ValueNumber, Set<Location>>();
367: for (LocationWhereValueBecomesNull lwvbn : locationWhereValueBecomesNullSet) {
368: if (DEBUG_DEREFS)
369: System.out.println("OOO " + lwvbn);
370: Set<Location> locationSet = nullValueAssignmentMap
371: .get(lwvbn.getValueNumber());
372: if (locationSet == null) {
373: locationSet = new HashSet<Location>();
374: nullValueAssignmentMap.put(lwvbn.getValueNumber(),
375: locationSet);
376: }
377: locationSet.add(lwvbn.getLocation());
378: if (DEBUG_DEREFS)
379: System.out.println(lwvbn.getValueNumber()
380: + " becomes null at " + lwvbn.getLocation());
381: }
382:
383: // Report
384: for (Map.Entry<ValueNumber, NullValueUnconditionalDeref> e : nullValueGuaranteedDerefMap
385: .entrySet()) {
386: ValueNumber valueNumber = e.getKey();
387: Set<Location> derefLocationSet = e.getValue()
388: .getDerefLocationSet();
389: Set<Location> assignedNullLocationSet = nullValueAssignmentMap
390: .get(valueNumber);
391: if (assignedNullLocationSet == null) {
392: if (DEBUG_DEREFS) {
393: String where = classContext.getJavaClass()
394: .getClassName()
395: + "."
396: + method.getName()
397: + ":"
398: + method.getSignature();
399: System.out.println("Problem at " + where);
400: for (Location loc : derefLocationSet) {
401: System.out.println("Dereference at " + loc);
402: }
403: }
404: // TODO: figure out why this is failing
405: if (false)
406: assert false : "No assigned NullLocationSet for "
407: + valueNumber
408: + " in "
409: + nullValueAssignmentMap.keySet()
410: + " while analyzing "
411: + classContext.getJavaClass()
412: .getClassName() + "."
413: + method.getName();
414: assignedNullLocationSet = TigerSubstitutes.emptySet();
415: }
416: SortedSet<Location> knownNullAndDoomedAt = bugLocationMap
417: .get(valueNumber);
418:
419: BugAnnotation variableAnnotation = null;
420: try {
421: for (Location loc : derefLocationSet) {
422: variableAnnotation = ValueNumberSourceInfo
423: .findAnnotationFromValueNumber(method, loc,
424: valueNumber, vnaDataflow
425: .getFactAtLocation(loc));
426: if (variableAnnotation != null)
427: break;
428: }
429: if (variableAnnotation == null)
430: for (Location loc : knownNullAndDoomedAt) {
431: variableAnnotation = ValueNumberSourceInfo
432: .findAnnotationFromValueNumber(method,
433: loc, valueNumber, vnaDataflow
434: .getFactAtLocation(loc));
435: if (variableAnnotation != null)
436: break;
437: }
438: if (variableAnnotation == null)
439: for (Location loc : assignedNullLocationSet) {
440: variableAnnotation = ValueNumberSourceInfo
441: .findAnnotationFromValueNumber(method,
442: loc, valueNumber, vnaDataflow
443: .getFactAtLocation(loc));
444: if (variableAnnotation != null)
445: break;
446: }
447:
448: } catch (DataflowAnalysisException e2) {
449: }
450: if (variableAnnotation == null)
451: variableAnnotation = new LocalVariableAnnotation("?",
452: -1, -1);
453:
454: if (PRUNE_GUARANTEED_DEREFERENCES) {
455: PostDominatorsAnalysis postDomAnalysis = classContext
456: .getNonExceptionPostDominatorsAnalysis(method);
457: removeStrictlyPostDominatedLocations(derefLocationSet,
458: postDomAnalysis);
459:
460: removeStrictlyPostDominatedLocations(
461: knownNullAndDoomedAt, postDomAnalysis);
462:
463: removeStrictlyPostDominatedLocations(
464: assignedNullLocationSet, postDomAnalysis);
465: }
466:
467: collector.foundGuaranteedNullDeref(assignedNullLocationSet,
468: derefLocationSet, knownNullAndDoomedAt,
469: vnaDataflow, valueNumber, variableAnnotation, e
470: .getValue(), npeIfStatementCovered
471: .contains(valueNumber));
472: }
473: }
474:
475: private void removeStrictlyPostDominatedLocations(
476: Set<Location> locations,
477: PostDominatorsAnalysis postDomAnalysis) {
478: BitSet strictlyDominated = new BitSet();
479: for (Location loc : locations) {
480: BitSet allDominatedBy = postDomAnalysis
481: .getAllDominatedBy(loc.getBasicBlock());
482: allDominatedBy.clear(loc.getBasicBlock().getLabel());
483: strictlyDominated.or(allDominatedBy);
484: }
485: LinkedList<Location> locations2 = new LinkedList<Location>(
486: locations);
487:
488: for (Iterator<Location> i = locations.iterator(); i.hasNext();) {
489: Location loc = i.next();
490: if (strictlyDominated.get(loc.getBasicBlock().getLabel())) {
491: i.remove();
492: continue;
493: }
494: for (Location loc2 : locations2) {
495: if (loc.getBasicBlock().equals(loc2.getBasicBlock())
496: && loc.getHandle().getPosition() > loc2
497: .getHandle().getPosition()) {
498: i.remove();
499: break;
500: }
501: }
502: }
503: }
504:
505: private static final boolean MY_DEBUG = false;
506:
507: /**
508: * Check for unconditionally dereferenced null values
509: * at a particular location in the CFG.
510: * @param thisLocation TODO
511: * @param knownNullAndDoomedAt TODO
512: * @param nullValueGuaranteedDerefMap map to be populated with null values and where they are derefed
513: * @param vnaFrame value number frame to check
514: * @param invFrame null-value frame to check
515: * @param derefSet set of unconditionally derefed values at this location
516: */
517: private void checkForUnconditionallyDereferencedNullValues(
518: Location this Location,
519: Map<ValueNumber, SortedSet<Location>> knownNullAndDoomedAt,
520: Map<ValueNumber, NullValueUnconditionalDeref> nullValueGuaranteedDerefMap,
521: ValueNumberFrame vnaFrame, IsNullValueFrame invFrame,
522: UnconditionalValueDerefSet derefSet) {
523:
524: if (DEBUG_DEREFS) {
525: System.out.println("vna *** " + vnaFrame);
526: System.out.println("inv *** " + invFrame);
527: System.out.println("deref * " + derefSet);
528: }
529:
530: // Make sure the frames contain meaningful information
531: if (!vnaFrame.isValid() || !invFrame.isValid()
532: || vnaFrame.getNumSlots() != invFrame.getNumSlots()) {
533: return;
534: }
535: if (derefSet.isEmpty())
536: return;
537: // See if there are any definitely-null values in the frame
538: for (int j = 0; j < invFrame.getNumSlots(); j++) {
539: IsNullValue isNullValue = invFrame.getValue(j);
540: ValueNumber valueNumber = vnaFrame.getValue(j);
541: if ((isNullValue.isDefinitelyNull() || isNullValue
542: .isNullOnSomePath()
543: && isNullValue.isReturnValue())
544: && (derefSet
545: .isUnconditionallyDereferenced(valueNumber))) {
546: if (MY_DEBUG) {
547: System.out.println("Found NP bug");
548: System.out.println("Location: " + this Location);
549: System.out.println("Value number: " + valueNumber);
550: System.out
551: .println("IsNullValue frame: " + invFrame);
552: System.out.println("IsNullValue value: "
553: + isNullValue);
554: System.out.println("Unconditional dere framef: "
555: + derefSet);
556: System.out
557: .println("Unconditionally dereferenced: "
558: + derefSet
559: .isUnconditionallyDereferenced(valueNumber));
560:
561: }
562: noteUnconditionallyDereferencedNullValue(this Location,
563: knownNullAndDoomedAt,
564: nullValueGuaranteedDerefMap, derefSet,
565: isNullValue, valueNumber);
566: }
567: }
568:
569: // See if there are any known-null values in the heap that
570: // will be dereferenced in the future.
571: for (Map.Entry<ValueNumber, IsNullValue> entry : invFrame
572: .getKnownValueMapEntrySet()) {
573: ValueNumber valueNumber = entry.getKey();
574: IsNullValue isNullValue = entry.getValue();
575: if ((isNullValue.isDefinitelyNull() || isNullValue
576: .isNullOnSomePath()
577: && (isNullValue.isReturnValue() || isNullValue
578: .isFieldValue()))
579: && derefSet
580: .isUnconditionallyDereferenced(valueNumber)) {
581:
582: noteUnconditionallyDereferencedNullValue(this Location,
583: knownNullAndDoomedAt,
584: nullValueGuaranteedDerefMap, derefSet,
585: isNullValue, valueNumber);
586: }
587: }
588: }
589:
590: /**
591: * Note the locations where a known-null value is unconditionally
592: * dereferenced.
593: * @param thisLocation TODO
594: * @param bugLocations TODO
595: * @param nullValueGuaranteedDerefMap map of null values to sets of Locations where they are derefed
596: * @param derefSet set of values known to be unconditionally dereferenced
597: * @param isNullValue the null value
598: * @param valueNumber the value number of the null value
599: */
600: private void noteUnconditionallyDereferencedNullValue(
601: Location this Location,
602: Map<ValueNumber, SortedSet<Location>> bugLocations,
603: Map<ValueNumber, NullValueUnconditionalDeref> nullValueGuaranteedDerefMap,
604: UnconditionalValueDerefSet derefSet,
605: IsNullValue isNullValue, ValueNumber valueNumber) {
606: if (DEBUG) {
607: System.out.println("%%% HIT for value number "
608: + valueNumber + " @ " + this Location);
609: }
610:
611: // OK, we have a null value that is unconditionally
612: // derferenced. Make a note of the locations where it
613: // will be dereferenced.
614: NullValueUnconditionalDeref this NullValueDeref = nullValueGuaranteedDerefMap
615: .get(valueNumber);
616: if (this NullValueDeref == null) {
617: this NullValueDeref = new NullValueUnconditionalDeref();
618: nullValueGuaranteedDerefMap.put(valueNumber,
619: this NullValueDeref);
620: }
621: this NullValueDeref.add(isNullValue, derefSet
622: .getUnconditionalDerefLocationSet(valueNumber));
623:
624: if (this Location != null) {
625: SortedSet<Location> locationsForThisBug = bugLocations
626: .get(valueNumber);
627:
628: if (locationsForThisBug == null) {
629: locationsForThisBug = new TreeSet<Location>();
630: bugLocations.put(valueNumber, locationsForThisBug);
631: }
632: locationsForThisBug.add(this Location);
633: }
634: }
635:
636: /**
637: * Examine redundant branches.
638: */
639: private void examineRedundantBranches() {
640: for (RedundantBranch redundantBranch : redundantBranchList) {
641: if (DEBUG)
642: System.out.println("Redundant branch: "
643: + redundantBranch);
644: int lineNumber = redundantBranch.lineNumber;
645:
646: // The source to bytecode compiler may sometimes duplicate blocks of
647: // code along different control paths. So, to report the bug,
648: // we check to ensure that the branch is REALLY determined each
649: // place it is duplicated, and that it is determined in the same way.
650:
651: boolean confused = undeterminedBranchSet.get(lineNumber)
652: || (definitelySameBranchSet.get(lineNumber) && definitelyDifferentBranchSet
653: .get(lineNumber));
654:
655: // confused if there is JSR confusion or multiple null checks with different results on the same line
656:
657: boolean reportIt = true;
658: if (lineMentionedMultipleTimes.get(lineNumber) && confused)
659: reportIt = false;
660: if (redundantBranch.location.getBasicBlock()
661: .isInJSRSubroutine() /* occurs in a JSR */
662: && confused)
663: reportIt = false;
664: if (reportIt) {
665: collector.foundRedundantNullCheck(
666: redundantBranch.location, redundantBranch);
667: }
668: }
669: }
670:
671: private void analyzeRefComparisonBranch(BasicBlock basicBlock,
672: InstructionHandle lastHandle)
673: throws DataflowAnalysisException {
674:
675: Location location = new Location(lastHandle, basicBlock);
676:
677: IsNullValueFrame frame = invDataflow
678: .getFactAtLocation(location);
679: if (!frame.isValid()) {
680: // Probably dead code due to pruning infeasible exception edges.
681: return;
682: }
683: if (frame.getStackDepth() < 2)
684: throw new DataflowAnalysisException("Stack underflow at "
685: + lastHandle);
686:
687: // Find the line number.
688: int lineNumber = getLineNumber(method, lastHandle);
689: if (lineNumber < 0)
690: return;
691:
692: int numSlots = frame.getNumSlots();
693: IsNullValue top = frame.getValue(numSlots - 1);
694: IsNullValue topNext = frame.getValue(numSlots - 2);
695:
696: boolean definitelySame = top.isDefinitelyNull()
697: && topNext.isDefinitelyNull();
698: boolean definitelyDifferent = (top.isDefinitelyNull() && topNext
699: .isDefinitelyNotNull())
700: || (top.isDefinitelyNotNull() && topNext
701: .isDefinitelyNull());
702:
703: if (definitelySame || definitelyDifferent) {
704: if (definitelySame) {
705: if (DEBUG)
706: System.out.println("Line " + lineNumber
707: + " always same");
708: definitelySameBranchSet.set(lineNumber);
709: }
710: if (definitelyDifferent) {
711: if (DEBUG)
712: System.out.println("Line " + lineNumber
713: + " always different");
714: definitelyDifferentBranchSet.set(lineNumber);
715: }
716:
717: RedundantBranch redundantBranch = new RedundantBranch(
718: location, lineNumber, top, topNext);
719:
720: // Figure out which control edge is made infeasible by the redundant comparison
721: boolean wantSame = (lastHandle.getInstruction().getOpcode() == Constants.IF_ACMPEQ);
722: int infeasibleEdgeType = (wantSame == definitelySame) ? EdgeTypes.FALL_THROUGH_EDGE
723: : EdgeTypes.IFCMP_EDGE;
724: Edge infeasibleEdge = invDataflow.getCFG()
725: .getOutgoingEdgeWithType(basicBlock,
726: infeasibleEdgeType);
727: redundantBranch.setInfeasibleEdge(infeasibleEdge);
728:
729: if (DEBUG)
730: System.out.println("Adding redundant branch: "
731: + redundantBranch);
732: redundantBranchList.add(redundantBranch);
733: } else {
734: if (DEBUG)
735: System.out.println("Line " + lineNumber
736: + " undetermined");
737: undeterminedBranchSet.set(lineNumber);
738: }
739: }
740:
741: // This is called for both IFNULL and IFNONNULL instructions.
742: private void analyzeIfNullBranch(BasicBlock basicBlock,
743: InstructionHandle lastHandle)
744: throws DataflowAnalysisException {
745:
746: Location location = new Location(lastHandle, basicBlock);
747:
748: IsNullValueFrame frame = invDataflow
749: .getFactAtLocation(location);
750:
751: if (!frame.isValid()) {
752: // This is probably dead code due to an infeasible exception edge.
753: return;
754: }
755:
756: IsNullValue top = frame.getTopValue();
757:
758: // Find the line number.
759: int lineNumber = getLineNumber(method, lastHandle);
760: if (lineNumber < 0)
761: return;
762:
763: if (!(top.isDefinitelyNull() || top.isDefinitelyNotNull())) {
764: if (DEBUG)
765: System.out.println("Line " + lineNumber
766: + " undetermined");
767: undeterminedBranchSet.set(lineNumber);
768: return;
769: }
770:
771: // Figure out if the branch is always taken
772: // or always not taken.
773: short opcode = lastHandle.getInstruction().getOpcode();
774: boolean definitelySame = top.isDefinitelyNull();
775: if (opcode != Constants.IFNULL)
776: definitelySame = !definitelySame;
777:
778: if (definitelySame) {
779: if (DEBUG)
780: System.out.println("Line " + lineNumber
781: + " always same");
782: definitelySameBranchSet.set(lineNumber);
783: } else {
784: if (DEBUG)
785: System.out.println("Line " + lineNumber
786: + " always different");
787: definitelyDifferentBranchSet.set(lineNumber);
788: }
789:
790: RedundantBranch redundantBranch = new RedundantBranch(location,
791: lineNumber, top);
792:
793: // Determine which control edge is made infeasible by the redundant comparison
794: boolean wantNull = (opcode == Constants.IFNULL);
795: int infeasibleEdgeType = (wantNull == top.isDefinitelyNull()) ? EdgeTypes.FALL_THROUGH_EDGE
796: : EdgeTypes.IFCMP_EDGE;
797: Edge infeasibleEdge = invDataflow
798: .getCFG()
799: .getOutgoingEdgeWithType(basicBlock, infeasibleEdgeType);
800: redundantBranch.setInfeasibleEdge(infeasibleEdge);
801:
802: if (DEBUG)
803: System.out.println("Adding redundant branch: "
804: + redundantBranch);
805: redundantBranchList.add(redundantBranch);
806: }
807:
808: private void analyzeNullCheck(ClassContext classContext,
809: Method method, IsNullValueDataflow invDataflow,
810: BasicBlock basicBlock) throws DataflowAnalysisException,
811: CFGBuilderException {
812: // Look for null checks where the value checked is definitely
813: // null or null on some path.
814:
815: InstructionHandle exceptionThrowerHandle = basicBlock
816: .getExceptionThrower();
817: Instruction exceptionThrower = exceptionThrowerHandle
818: .getInstruction();
819:
820: // Get the stack values at entry to the null check.
821: IsNullValueFrame frame = invDataflow.getStartFact(basicBlock);
822: if (!frame.isValid())
823: return;
824:
825: // Could the reference be null?
826: IsNullValue refValue = frame.getInstance(exceptionThrower,
827: classContext.getConstantPoolGen());
828: if (DEBUG) {
829: System.out.println("For basic block " + basicBlock
830: + " value is " + refValue);
831: }
832: if (!refValue.mightBeNull())
833: return;
834:
835: // if (!refValue.isDefinitelyNull()) return;
836: // Get the value number
837: ValueNumberFrame vnaFrame = classContext
838: .getValueNumberDataflow(method)
839: .getStartFact(basicBlock);
840: if (!vnaFrame.isValid())
841: return;
842: ValueNumber valueNumber = vnaFrame.getInstance(
843: exceptionThrower, classContext.getConstantPoolGen());
844: Location location = new Location(exceptionThrowerHandle,
845: basicBlock);
846: if (DEBUG)
847: System.out.println("Warning: VN " + valueNumber + " invf: "
848: + frame + " @ " + location);
849:
850: // Issue a warning
851: collector.foundNullDeref(classContext, location, valueNumber,
852: refValue, vnaFrame);
853: }
854:
855: /**
856: * @deprecated Use {@link ValueNumberSourceInfo#findXFieldFromValueNumber(Method,Location,ValueNumber,ValueNumberFrame)} instead
857: */
858: public static XField findXFieldFromValueNumber(Method method,
859: Location location, ValueNumber valueNumber,
860: ValueNumberFrame vnaFrame) {
861: return ValueNumberSourceInfo.findXFieldFromValueNumber(method,
862: location, valueNumber, vnaFrame);
863: }
864:
865: /**
866: * @deprecated Use {@link ValueNumberSourceInfo#findFieldAnnotationFromValueNumber(Method,Location,ValueNumber,ValueNumberFrame)} instead
867: */
868: public static FieldAnnotation findFieldAnnotationFromValueNumber(
869: Method method, Location location, ValueNumber valueNumber,
870: ValueNumberFrame vnaFrame) {
871: return ValueNumberSourceInfo
872: .findFieldAnnotationFromValueNumber(method, location,
873: valueNumber, vnaFrame);
874: }
875:
876: /**
877: * @deprecated Use {@link ValueNumberSourceInfo#findLocalAnnotationFromValueNumber(Method,Location,ValueNumber,ValueNumberFrame)} instead
878: */
879: public static LocalVariableAnnotation findLocalAnnotationFromValueNumber(
880: Method method, Location location, ValueNumber valueNumber,
881: ValueNumberFrame vnaFrame) {
882: return ValueNumberSourceInfo
883: .findLocalAnnotationFromValueNumber(method, location,
884: valueNumber, vnaFrame);
885: }
886:
887: /**
888: * @param method
889: * TODO
890: * @param location
891: * @param valueNumber
892: * @param vnaFrame
893: * @return
894: * @deprecated Use {@link ValueNumberSourceInfo#findAnnotationFromValueNumber(Method,Location,ValueNumber,ValueNumberFrame)} instead
895: */
896: public static BugAnnotation findAnnotationFromValueNumber(
897: Method method, Location location, ValueNumber valueNumber,
898: ValueNumberFrame vnaFrame) {
899: return ValueNumberSourceInfo.findAnnotationFromValueNumber(
900: method, location, valueNumber, vnaFrame);
901: }
902:
903: private static int getLineNumber(Method method,
904: InstructionHandle handle) {
905: LineNumberTable table = method.getCode().getLineNumberTable();
906: if (table == null)
907: return -1;
908: return table.getSourceLine(handle.getPosition());
909: }
910: }
|