001: /*
002: * FindBugs - Find Bugs in Java programs
003: * Copyright (C) 2006, 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.deref;
021:
022: import java.util.Set;
023:
024: import org.apache.bcel.classfile.Method;
025: import org.apache.bcel.generic.ARETURN;
026: import org.apache.bcel.generic.FieldInstruction;
027: import org.apache.bcel.generic.Instruction;
028: import org.apache.bcel.generic.InstructionHandle;
029: import org.apache.bcel.generic.InvokeInstruction;
030: import org.apache.bcel.generic.MethodGen;
031: import org.apache.bcel.generic.PUTFIELD;
032: import org.apache.bcel.generic.PUTSTATIC;
033:
034: import edu.umd.cs.findbugs.SystemProperties;
035: import edu.umd.cs.findbugs.annotations.CheckForNull;
036: import edu.umd.cs.findbugs.ba.AnalysisContext;
037: import edu.umd.cs.findbugs.ba.AssertionMethods;
038: import edu.umd.cs.findbugs.ba.BackwardDataflowAnalysis;
039: import edu.umd.cs.findbugs.ba.BasicBlock;
040: import edu.umd.cs.findbugs.ba.CFG;
041: import edu.umd.cs.findbugs.ba.CFGBuilderException;
042: import edu.umd.cs.findbugs.ba.ClassContext;
043: import edu.umd.cs.findbugs.ba.Dataflow;
044: import edu.umd.cs.findbugs.ba.DataflowAnalysisException;
045: import edu.umd.cs.findbugs.ba.DataflowTestDriver;
046: import edu.umd.cs.findbugs.ba.DepthFirstSearch;
047: import edu.umd.cs.findbugs.ba.Edge;
048: import edu.umd.cs.findbugs.ba.EdgeTypes;
049: import edu.umd.cs.findbugs.ba.Hierarchy2;
050: import edu.umd.cs.findbugs.ba.INullnessAnnotationDatabase;
051: import edu.umd.cs.findbugs.ba.Location;
052: import edu.umd.cs.findbugs.ba.NullnessAnnotation;
053: import edu.umd.cs.findbugs.ba.ReverseDepthFirstSearch;
054: import edu.umd.cs.findbugs.ba.SignatureParser;
055: import edu.umd.cs.findbugs.ba.XFactory;
056: import edu.umd.cs.findbugs.ba.XField;
057: import edu.umd.cs.findbugs.ba.XMethod;
058: import edu.umd.cs.findbugs.ba.npe.IsNullConditionDecision;
059: import edu.umd.cs.findbugs.ba.npe.IsNullValue;
060: import edu.umd.cs.findbugs.ba.npe.IsNullValueDataflow;
061: import edu.umd.cs.findbugs.ba.npe.IsNullValueFrame;
062: import edu.umd.cs.findbugs.ba.npe.ParameterNullnessProperty;
063: import edu.umd.cs.findbugs.ba.npe.ParameterNullnessPropertyDatabase;
064: import edu.umd.cs.findbugs.ba.type.TypeDataflow;
065: import edu.umd.cs.findbugs.ba.type.TypeFrame;
066: import edu.umd.cs.findbugs.ba.vna.AvailableLoad;
067: import edu.umd.cs.findbugs.ba.vna.ValueNumber;
068: import edu.umd.cs.findbugs.ba.vna.ValueNumberDataflow;
069: import edu.umd.cs.findbugs.ba.vna.ValueNumberFrame;
070: import edu.umd.cs.findbugs.visitclass.Util;
071:
072: /**
073: * Dataflow analysis to find values unconditionally dereferenced in the future.
074: *
075: * @author David Hovemeyer
076: */
077: public class UnconditionalValueDerefAnalysis extends
078: BackwardDataflowAnalysis<UnconditionalValueDerefSet> {
079:
080: public static final boolean DEBUG = SystemProperties
081: .getBoolean("fnd.derefs.debug");
082: public static final boolean ASSUME_NONZERO_TRIP_LOOPS = SystemProperties
083: .getBoolean("fnd.derefs.nonzerotrip");
084: public static final boolean IGNORE_DEREF_OF_NCP = SystemProperties
085: .getBoolean("fnd.derefs.ignoreNCP", false);
086:
087: public static final boolean CHECK_ANNOTATIONS = SystemProperties
088: .getBoolean("fnd.derefs.checkannotations", true);
089: public static final boolean CHECK_CALLS = SystemProperties
090: .getBoolean("fnd.derefs.checkcalls", true);
091: public static final boolean DEBUG_CHECK_CALLS = SystemProperties
092: .getBoolean("fnd.derefs.checkcalls.debug");
093:
094: private CFG cfg;
095: private final Method method;
096: private MethodGen methodGen;
097: private ValueNumberDataflow vnaDataflow;
098: private AssertionMethods assertionMethods;
099:
100: private IsNullValueDataflow invDataflow;
101: private TypeDataflow typeDataflow;
102:
103: /**
104: * Constructor.
105: *
106: * @param rdfs the reverse depth-first-search (for the block order)
107: * @param dfs TODO
108: * @param cfg the CFG for the method
109: * @param method TODO
110: * @param methodGen the MethodGen for the method
111: * @param vnaDataflow
112: * @param assertionMethods AssertionMethods for the analyzed class
113: */
114: public UnconditionalValueDerefAnalysis(
115: ReverseDepthFirstSearch rdfs, DepthFirstSearch dfs,
116: CFG cfg, Method method, MethodGen methodGen,
117: ValueNumberDataflow vnaDataflow,
118: AssertionMethods assertionMethods) {
119: super (rdfs, dfs);
120: this .cfg = cfg;
121: this .methodGen = methodGen;
122: this .method = method;
123: this .vnaDataflow = vnaDataflow;
124: this .assertionMethods = assertionMethods;
125: if (DEBUG) {
126: System.out
127: .println("UnconditionalValueDerefAnalysis analysis "
128: + methodGen.getClassName()
129: + "."
130: + methodGen.getName()
131: + " : "
132: + methodGen.getSignature());
133: }
134:
135: }
136:
137: /**
138: * HACK: use the given is-null dataflow to clear deref sets for
139: * values that are known to be definitely non-null on a branch.
140: *
141: * @param invDataflow the IsNullValueDataflow to use
142: */
143: public void clearDerefsOnNonNullBranches(
144: IsNullValueDataflow invDataflow) {
145: this .invDataflow = invDataflow;
146: }
147:
148: /**
149: *
150: *
151: */
152: public void setTypeDataflow(TypeDataflow typeDataflow) {
153: this .typeDataflow = typeDataflow;
154: }
155:
156: /* (non-Javadoc)
157: * @see edu.umd.cs.findbugs.ba.AbstractDataflowAnalysis#isFactValid(java.lang.Object)
158: */
159: @Override
160: public boolean isFactValid(UnconditionalValueDerefSet fact) {
161: return !fact.isTop() && !fact.isBottom();
162: }
163:
164: /* (non-Javadoc)
165: * @see edu.umd.cs.findbugs.ba.AbstractDataflowAnalysis#transferInstruction(org.apache.bcel.generic.InstructionHandle, edu.umd.cs.findbugs.ba.BasicBlock, java.lang.Object)
166: */
167: @Override
168: public void transferInstruction(InstructionHandle handle,
169: BasicBlock basicBlock, UnconditionalValueDerefSet fact)
170: throws DataflowAnalysisException {
171:
172: Instruction instruction = handle.getInstruction();
173: if (false && DEBUG) {
174: System.out.println("XXX: " + handle.getPosition() + " "
175: + instruction);
176: }
177: if (fact.isTop())
178: return;
179: Location location = new Location(handle, basicBlock);
180:
181: // If this is a call to an assertion method,
182: // change the dataflow value to be TOP.
183: // We don't want to report future derefs that would
184: // be guaranteed only if the assertion methods
185: // returns normally.
186: // TODO: at some point, evaluate whether we should revisit this
187: if (isAssertion(handle) // || handle.getInstruction() instanceof ATHROW
188: ) {
189: if (DEBUG)
190: System.out.println("MAKING BOTTOM0 AT: " + location);
191: fact.clear();
192: return;
193: }
194:
195: // Get value number frame
196: ValueNumberFrame vnaFrame = vnaDataflow
197: .getFactAtLocation(location);
198: if (!vnaFrame.isValid()) {
199: if (DEBUG)
200: System.out.println("MAKING TOP1 AT: " + location);
201: // Probably dead code.
202: // Assume this location can't be reached.
203: makeFactTop(fact);
204: return;
205: }
206:
207: // Check for calls to a method that unconditionally dereferences
208: // a parameter. Mark any such arguments as derefs.
209: if (CHECK_CALLS && instruction instanceof InvokeInstruction) {
210: checkUnconditionalDerefDatabase(location, vnaFrame, fact);
211: }
212:
213: // If this is a method call instruction,
214: // check to see if any of the parameters are @NonNull,
215: // and treat them as dereferences.
216: if (CHECK_ANNOTATIONS
217: && instruction instanceof InvokeInstruction) {
218: checkNonNullParams(location, vnaFrame, fact);
219: }
220:
221: if (CHECK_ANNOTATIONS && instruction instanceof ARETURN) {
222: XMethod this Method = XFactory.createXMethod(methodGen);
223: checkNonNullReturnValue(this Method, location, vnaFrame,
224: fact);
225: }
226:
227: if (CHECK_ANNOTATIONS
228: && (instruction instanceof PUTFIELD || instruction instanceof PUTSTATIC)) {
229: checkNonNullPutField(location, vnaFrame, fact);
230: }
231:
232: // Check to see if an instance value is dereferenced here
233: checkInstance(location, vnaFrame, fact);
234:
235: if (false)
236: fact.cleanDerefSet(location, vnaFrame);
237:
238: if (DEBUG && fact.isTop())
239: System.out.println("MAKING TOP2 At: " + location);
240:
241: }
242:
243: /**
244: * Check method call at given location to see if it unconditionally
245: * dereferences a parameter. Mark any such arguments as derefs.
246: *
247: * @param location the Location of the method call
248: * @param vnaFrame ValueNumberFrame at the Location
249: * @param fact the dataflow value to modify
250: * @throws DataflowAnalysisException
251: */
252: private void checkUnconditionalDerefDatabase(Location location,
253: ValueNumberFrame vnaFrame, UnconditionalValueDerefSet fact)
254: throws DataflowAnalysisException {
255: InvokeInstruction inv = (InvokeInstruction) location
256: .getHandle().getInstruction();
257:
258: SignatureParser sigParser = new SignatureParser(inv
259: .getSignature(methodGen.getConstantPool()));
260: int numParams = sigParser.getNumParameters();
261: if (numParams == 0 || !sigParser.hasReferenceParameters())
262: return;
263: ParameterNullnessPropertyDatabase database = AnalysisContext
264: .currentAnalysisContext()
265: .getUnconditionalDerefParamDatabase();
266: if (database == null) {
267: if (DEBUG_CHECK_CALLS)
268: System.out.println("no database!");
269: return;
270: }
271:
272: TypeFrame typeFrame = typeDataflow.getFactAtLocation(location);
273: if (!typeFrame.isValid()) {
274: if (DEBUG_CHECK_CALLS)
275: System.out.println("invalid type frame!");
276: return;
277: }
278:
279: try {
280: Set<XMethod> targetSet = Hierarchy2
281: .resolveMethodCallTargets(inv, typeFrame, methodGen
282: .getConstantPool());
283:
284: if (targetSet.isEmpty())
285: return;
286:
287: if (DEBUG_CHECK_CALLS)
288: System.out.println("target set size: "
289: + targetSet.size());
290: // Compute the intersection of all properties
291: ParameterNullnessProperty derefParamSet = null;
292: for (XMethod target : targetSet) {
293: if (DEBUG_CHECK_CALLS)
294: System.out.print("Checking: " + target + ": ");
295:
296: ParameterNullnessProperty targetDerefParamSet = database
297: .getProperty(target.getMethodDescriptor());
298: if (targetDerefParamSet == null) {
299: // Hmm...no information for this target.
300: // assume it doesn't dereference anything
301: if (DEBUG_CHECK_CALLS)
302: System.out
303: .println("==> no information, assume no guaranteed dereferences");
304: return;
305: }
306:
307: if (DEBUG_CHECK_CALLS) {
308: System.out.println("==> " + targetDerefParamSet);
309: }
310: if (derefParamSet == null) {
311: derefParamSet = new ParameterNullnessProperty();
312: derefParamSet.copyFrom(targetDerefParamSet);
313: } else {
314: derefParamSet.intersectWith(targetDerefParamSet);
315: }
316: }
317:
318: if (derefParamSet == null || derefParamSet.isEmpty()) {
319: if (DEBUG)
320: System.out.println("** Nothing");
321: return;
322: }
323: if (DEBUG_CHECK_CALLS) {
324: System.out.println("** Summary of call @ "
325: + location.getHandle().getPosition() + ": "
326: + derefParamSet);
327: }
328:
329: IsNullValueFrame invFrame = invDataflow
330: .getFactAtLocation(location);
331:
332: if (invFrame != null && invFrame.isValid()) {
333: for (int i = 0; i < numParams; i++) {
334: if (!derefParamSet.isNonNull(i)) {
335: continue;
336: }
337: int argSlot = vnaFrame.getStackLocation(sigParser
338: .getSlotsFromTopOfStackForParameter(i));
339: if (!reportDereference(invFrame, argSlot))
340: continue;
341: if (DEBUG_CHECK_CALLS)
342: System.out.println(" dereference @ "
343: + location.getHandle().getPosition()
344: + " of parameter " + i);
345:
346: fact.addDeref(vnaFrame.getValue(argSlot), location);
347: }
348: }
349: } catch (ClassNotFoundException e) {
350: AnalysisContext.reportMissingClass(e);
351: }
352: }
353:
354: public static final boolean VERBOSE_NULLARG_DEBUG = SystemProperties
355: .getBoolean("fnd.debug.nullarg.verbose");
356:
357: /**
358: * If this is a method call instruction,
359: * check to see if any of the parameters are @NonNull,
360: * and treat them as dereferences.
361: * @param thisMethod TODO
362: * @param location the Location of the instruction
363: * @param vnaFrame the ValueNumberFrame at the Location of the instruction
364: * @param fact the dataflow value to modify
365: *
366: * @throws DataflowAnalysisException
367: */
368: private void checkNonNullReturnValue(XMethod this Method,
369: Location location, ValueNumberFrame vnaFrame,
370: UnconditionalValueDerefSet fact)
371: throws DataflowAnalysisException {
372: INullnessAnnotationDatabase database = AnalysisContext
373: .currentAnalysisContext()
374: .getNullnessAnnotationDatabase();
375: if (database == null) {
376: return;
377: }
378: IsNullValueFrame invFrame = invDataflow
379: .getFactAtLocation(location);
380: if (!invFrame.isValid())
381: return;
382:
383: if (database.getResolvedAnnotation(this Method, true) != NullnessAnnotation.NONNULL)
384: return;
385: IsNullValue value = invFrame.getTopValue();
386: if (value.isDefinitelyNotNull())
387: return;
388: if (value.isDefinitelyNull())
389: return;
390: ValueNumber vn = vnaFrame.getTopValue();
391: if (true)
392: fact.addDeref(vn, location);
393: }
394:
395: /**
396: * If this is a putfield or putstatic instruction,
397: * check to see if the field is @NonNull,
398: * and treat it as dereferences.
399: *
400: * @param location the Location of the instruction
401: * @param vnaFrame the ValueNumberFrame at the Location of the instruction
402: * @param fact the dataflow value to modify
403: * @throws DataflowAnalysisException
404: */
405: private void checkNonNullPutField(Location location,
406: ValueNumberFrame vnaFrame, UnconditionalValueDerefSet fact)
407: throws DataflowAnalysisException {
408: INullnessAnnotationDatabase database = AnalysisContext
409: .currentAnalysisContext()
410: .getNullnessAnnotationDatabase();
411: if (database == null) {
412: return;
413: }
414:
415: FieldInstruction fieldIns = (FieldInstruction) location
416: .getHandle().getInstruction();
417:
418: XField field = XFactory.createXField(fieldIns, methodGen
419: .getConstantPool());
420: char firstChar = field.getSignature().charAt(0);
421: if (firstChar != 'L' && firstChar != '[')
422: return;
423: NullnessAnnotation resolvedAnnotation = database
424: .getResolvedAnnotation(field, true);
425: if (resolvedAnnotation == NullnessAnnotation.NONNULL) {
426: IsNullValueFrame invFrame = invDataflow
427: .getFactAtLocation(location);
428: if (!invFrame.isValid())
429: return;
430: IsNullValue value = invFrame.getTopValue();
431: if (reportDereference(value)) {
432: ValueNumber vn = vnaFrame.getTopValue();
433: fact.addDeref(vn, location);
434: }
435: }
436: }
437:
438: /**
439: * If this is a method call instruction,
440: * check to see if any of the parameters are @NonNull,
441: * and treat them as dereferences.
442: *
443: * @param location the Location of the instruction
444: * @param vnaFrame the ValueNumberFrame at the Location of the instruction
445: * @param fact the dataflow value to modify
446: * @throws DataflowAnalysisException
447: */
448: private void checkNonNullParams(Location location,
449: ValueNumberFrame vnaFrame, UnconditionalValueDerefSet fact)
450: throws DataflowAnalysisException {
451: INullnessAnnotationDatabase database = AnalysisContext
452: .currentAnalysisContext()
453: .getNullnessAnnotationDatabase();
454: if (database == null) {
455: return;
456: }
457:
458: InvokeInstruction inv = (InvokeInstruction) location
459: .getHandle().getInstruction();
460: XMethod called = XFactory.createXMethod(inv, methodGen
461: .getConstantPool());
462: SignatureParser sigParser = new SignatureParser(called
463: .getSignature());
464: int numParams = sigParser.getNumParameters();
465: IsNullValueFrame invFrame = invDataflow
466: .getFactAtLocation(location);
467:
468: if (!invFrame.isValid())
469: return;
470: for (int i = 0; i < numParams; i++) {
471: int offset = sigParser
472: .getSlotsFromTopOfStackForParameter(i);
473: int slot = invFrame.getStackLocation(offset);
474: IsNullValue value = invFrame.getValue(slot);
475: if (reportDereference(invFrame, slot)
476: && database.parameterMustBeNonNull(called, i)) {
477: int catchSizeNPE = Util.getSizeOfSurroundingTryBlock(
478: method, "java/lang/NullPointerException",
479: location.getHandle().getPosition());
480: int catchSizeNFE = Util.getSizeOfSurroundingTryBlock(
481: method, "java/lang/NumberFormatException",
482: location.getHandle().getPosition());
483: if (catchSizeNPE == Integer.MAX_VALUE
484: && (!called.getClassName().equals(
485: "java.lang.Integer") || catchSizeNFE == Integer.MAX_VALUE)) {
486: // Get the corresponding value number
487: ValueNumber vn = vnaFrame.getArgument(inv,
488: methodGen.getConstantPool(), i, sigParser);
489: fact.addDeref(vn, location);
490: }
491: }
492: }
493: }
494:
495: /**
496: * Check to see if the instruction has a null check associated with it,
497: * and if so, add a dereference.
498: *
499: * @param location the Location of the instruction
500: * @param vnaFrame ValueNumberFrame at the Location of the instruction
501: * @param fact the dataflow value to modify
502: * @throws DataflowAnalysisException
503: */
504: private void checkInstance(Location location,
505: ValueNumberFrame vnaFrame, UnconditionalValueDerefSet fact)
506: throws DataflowAnalysisException {
507: // See if this instruction has a null check.
508: // If it does, the fall through predecessor will be
509: // identify itself as the null check.
510: if (!location.isFirstInstructionInBasicBlock()) {
511: return;
512: }
513: if (invDataflow == null)
514: return;
515: BasicBlock fallThroughPredecessor = cfg
516: .getPredecessorWithEdgeType(location.getBasicBlock(),
517: EdgeTypes.FALL_THROUGH_EDGE);
518: if (fallThroughPredecessor == null
519: || !fallThroughPredecessor.isNullCheck()) {
520: return;
521: }
522:
523: // Get the null-checked value
524: ValueNumber vn = vnaFrame.getInstance(location.getHandle()
525: .getInstruction(), methodGen.getConstantPool());
526:
527: // Ignore dereferences of this
528: if (!methodGen.isStatic()) {
529: ValueNumber v = vnaFrame.getValue(0);
530: if (v.equals(vn))
531: return;
532: }
533: if (vn.hasFlag(ValueNumber.CONSTANT_CLASS_OBJECT))
534: return;
535:
536: IsNullValueFrame startFact = null;
537:
538: startFact = invDataflow.getStartFact(fallThroughPredecessor);
539:
540: if (!startFact.isValid())
541: return;
542:
543: int slot = startFact.getInstanceSlot(location.getHandle()
544: .getInstruction(), methodGen.getConstantPool());
545: if (!reportDereference(startFact, slot))
546: return;
547: if (DEBUG) {
548: System.out.println("FOUND GUARANTEED DEREFERENCE");
549: System.out.println("Load: " + vnaFrame.getLoad(vn));
550: System.out.println("Pred: " + fallThroughPredecessor);
551: System.out.println("startFact: " + startFact);
552: System.out.println("Location: " + location);
553: System.out.println("Value number frame: " + vnaFrame);
554: System.out.println("Dereferenced valueNumber: " + vn);
555: System.out.println("invDataflow: " + startFact);
556: System.out.println("IGNORE_DEREF_OF_NCP: "
557: + IGNORE_DEREF_OF_NCP);
558: }
559: // Mark the value number as being dereferenced at this location
560: fact.addDeref(vn, location);
561: }
562:
563: private boolean reportDereference(
564: IsNullValueFrame invFrameAtNullCheck, int instance) {
565: return reportDereference(invFrameAtNullCheck.getValue(instance));
566: }
567:
568: private boolean reportDereference(IsNullValue value) {
569: if (value.isDefinitelyNotNull())
570: return false;
571: if (value.isDefinitelyNull())
572: return false;
573: if (IGNORE_DEREF_OF_NCP && value.isNullOnComplicatedPath())
574: return false;
575: return true;
576: }
577:
578: /**
579: * Return whether or not given instruction is an assertion.
580: *
581: * @param handle the instruction
582: * @return true if instruction is an assertion, false otherwise
583: */
584: private boolean isAssertion(InstructionHandle handle) {
585: return assertionMethods.isAssertionInstruction(handle
586: .getInstruction(), methodGen.getConstantPool());
587:
588: }
589:
590: /* (non-Javadoc)
591: * @see edu.umd.cs.findbugs.ba.DataflowAnalysis#copy(java.lang.Object, java.lang.Object)
592: */
593: public void copy(UnconditionalValueDerefSet source,
594: UnconditionalValueDerefSet dest) {
595: dest.makeSameAs(source);
596: }
597:
598: /* (non-Javadoc)
599: * @see edu.umd.cs.findbugs.ba.DataflowAnalysis#createFact()
600: */
601: public UnconditionalValueDerefSet createFact() {
602: return new UnconditionalValueDerefSet(vnaDataflow.getAnalysis()
603: .getNumValuesAllocated());
604: }
605:
606: /* (non-Javadoc)
607: * @see edu.umd.cs.findbugs.ba.DataflowAnalysis#initEntryFact(java.lang.Object)
608: */
609: public void initEntryFact(UnconditionalValueDerefSet result)
610: throws DataflowAnalysisException {
611: result.clear();
612: }
613:
614: // /* (non-Javadoc)
615: // * @see edu.umd.cs.findbugs.ba.DataflowAnalysis#initResultFact(java.lang.Object)
616: // */
617: // public void initResultFact(UnconditionalValueDerefSet result) {
618: // result.setIsTop();
619: // }
620:
621: /* (non-Javadoc)
622: * @see edu.umd.cs.findbugs.ba.DataflowAnalysis#makeFactTop(java.lang.Object)
623: */
624: public void makeFactTop(UnconditionalValueDerefSet fact) {
625: fact.setIsTop();
626: }
627:
628: public boolean isTop(UnconditionalValueDerefSet fact) {
629: return fact.isTop();
630: }
631:
632: /* (non-Javadoc)
633: * @see edu.umd.cs.findbugs.ba.DataflowAnalysis#meetInto(java.lang.Object, edu.umd.cs.findbugs.ba.Edge, java.lang.Object)
634: */
635: public void meetInto(UnconditionalValueDerefSet fact, Edge edge,
636: UnconditionalValueDerefSet result)
637: throws DataflowAnalysisException {
638: meetInto(fact, edge, result, false);
639: }
640:
641: /* (non-Javadoc)
642: * @see edu.umd.cs.findbugs.ba.DataflowAnalysis#meetInto(java.lang.Object, edu.umd.cs.findbugs.ba.Edge, java.lang.Object)
643: */
644: public void meetInto(UnconditionalValueDerefSet fact, Edge edge,
645: UnconditionalValueDerefSet result, boolean onlyEdge)
646: throws DataflowAnalysisException {
647:
648: if (isExceptionEdge(edge) && !onlyEdge) {
649: if (DEBUG)
650: System.out.println("Skipping exception edge");
651: return;
652: }
653:
654: ValueNumber knownNonnullOnBranch = null;
655: // Edge transfer function
656: if (isFactValid(fact)) {
657: fact = propagateDerefSetsToMergeInputValues(fact, edge);
658: if (invDataflow != null) {
659: knownNonnullOnBranch = findValueKnownNonnullOnBranch(
660: fact, edge);
661: if (knownNonnullOnBranch != null) {
662: fact = duplicateFact(fact);
663: fact.clearDerefSet(knownNonnullOnBranch);
664: }
665: }
666: }
667: boolean isBackEdge = edge.isBackwardInBytecode();
668: Set<Integer> loopExitBranches = ClassContext
669: .getLoopExitBranches(method, methodGen);
670: assert loopExitBranches != null;
671: boolean sourceIsTopOfLoop = edge
672: .sourceIsTopOfLoop(loopExitBranches);
673: if (sourceIsTopOfLoop
674: && edge.getType() == EdgeTypes.FALL_THROUGH_EDGE)
675: isBackEdge = true;
676: if (false && (edge.getType() == EdgeTypes.IFCMP_EDGE || sourceIsTopOfLoop)) {
677: System.out.println("Meet into " + edge);
678: System.out.println(" foo2: " + sourceIsTopOfLoop);
679: System.out.println(" getType: " + edge.getType());
680: System.out.println(" Backedge according to bytecode: "
681: + isBackEdge);
682: System.out.println(" Fact hashCode: "
683: + System.identityHashCode(result));
684: System.out.println(" Initial fact: " + result);
685: System.out.println(" Edge fact: " + fact);
686: }
687: if (result.isTop() || fact.isBottom()) {
688: // Make result identical to other fact
689: copy(fact, result);
690: if (ASSUME_NONZERO_TRIP_LOOPS && isBackEdge
691: && !fact.isTop())
692: result.resultsFromBackEdge = true;
693: } else if (ASSUME_NONZERO_TRIP_LOOPS && isBackEdge
694: && !fact.isTop()) {
695: result.unionWith(fact, vnaDataflow.getAnalysis()
696: .getFactory());
697: result.resultsFromBackEdge = true;
698: if (DEBUG) {
699: System.out.println("\n Forcing union of "
700: + System.identityHashCode(result)
701: + " due to backedge info");
702: System.out.println(" result: " + result);
703: }
704:
705: } else if (result.isBottom() || fact.isTop()) {
706: // No change in result fact
707: } else {
708: // Dataflow merge
709: // (intersection of unconditional deref values)
710: if (ASSUME_NONZERO_TRIP_LOOPS && result.resultsFromBackEdge) {
711: result.backEdgeUpdateCount++;
712: if (result.backEdgeUpdateCount < 10) {
713: if (DEBUG)
714: System.out.println("\n Union update of "
715: + System.identityHashCode(result)
716: + " due to backedge info");
717: result.unionWith(fact, vnaDataflow.getAnalysis()
718: .getFactory());
719: return;
720: }
721: }
722: result.mergeWith(fact, knownNonnullOnBranch, vnaDataflow
723: .getAnalysis().getFactory());
724: if (DEBUG) {
725: System.out.println(" updated: "
726: + System.identityHashCode(result));
727: System.out.println(" result: " + result);
728:
729: }
730: }
731: if (DEBUG && isBackEdge
732: && edge.getType() == EdgeTypes.IFCMP_EDGE) {
733: System.out.println(" result: " + result);
734: }
735:
736: }
737:
738: /**
739: * Find out if any VNs in the source block
740: * contribute to unconditionally dereferenced VNs in the
741: * target block. If so, the VN in the source block is
742: * also unconditionally dereferenced, and we must propagate
743: * the target VN's dereferences.
744: *
745: * @param fact a dataflow value
746: * @param edge edge to check for merge input values
747: * @return possibly-modified dataflow value
748: */
749: private UnconditionalValueDerefSet propagateDerefSetsToMergeInputValues(
750: UnconditionalValueDerefSet fact, Edge edge) {
751:
752: ValueNumberFrame blockValueNumberFrame = vnaDataflow
753: .getResultFact(edge.getSource());
754: ValueNumberFrame targetValueNumberFrame = vnaDataflow
755: .getStartFact(edge.getTarget());
756:
757: UnconditionalValueDerefSet originalFact = fact;
758: fact = duplicateFact(fact);
759:
760: if (blockValueNumberFrame.isValid()
761: && targetValueNumberFrame.isValid()
762: && blockValueNumberFrame.getNumSlots() == targetValueNumberFrame
763: .getNumSlots()) {
764: if (DEBUG) {
765: System.out.println("** Valid VNA frames for " + edge);
766: System.out.println("** Block : "
767: + blockValueNumberFrame);
768: System.out.println("** Target: "
769: + targetValueNumberFrame);
770: }
771:
772: for (int i = 0; i < blockValueNumberFrame.getNumSlots(); i++) {
773: ValueNumber blockVN = blockValueNumberFrame.getValue(i);
774: ValueNumber targetVN = targetValueNumberFrame
775: .getValue(i);
776: if (blockVN.equals(targetVN))
777: continue;
778: fact.clearDerefSet(blockVN);
779: if (originalFact
780: .isUnconditionallyDereferenced(targetVN))
781: fact
782: .setDerefSet(
783: blockVN,
784: originalFact
785: .getUnconditionalDerefLocationSet(targetVN));
786:
787: } // for all slots
788:
789: for (ValueNumber blockVN : blockValueNumberFrame
790: .valueNumbersForLoads()) {
791: AvailableLoad load = blockValueNumberFrame
792: .getLoad(blockVN);
793: if (load == null)
794: continue;
795: ValueNumber[] targetVNs = targetValueNumberFrame
796: .getAvailableLoad(load);
797: if (targetVNs != null)
798: for (ValueNumber targetVN : targetVNs)
799: if (targetVN.hasFlag(ValueNumber.PHI_NODE)
800: && fact
801: .isUnconditionallyDereferenced(targetVN)
802: && !fact
803: .isUnconditionallyDereferenced(blockVN)) {
804: // Block VN is also dereferenced unconditionally.
805: AvailableLoad targetLoad = targetValueNumberFrame
806: .getLoad(targetVN);
807: if (!load.equals(targetLoad))
808: continue;
809: if (DEBUG) {
810: System.out
811: .println("** Copy vn derefs for "
812: + load
813: + " from "
814: + targetVN
815: + " --> "
816: + blockVN);
817: System.out
818: .println("** block phi for "
819: + System
820: .identityHashCode(blockValueNumberFrame)
821: + " is "
822: + blockValueNumberFrame.phiNodeForLoads);
823: System.out
824: .println("** target phi for "
825: + System
826: .identityHashCode(targetValueNumberFrame)
827: + " is "
828: + targetValueNumberFrame.phiNodeForLoads);
829: }
830: fact
831: .setDerefSet(
832: blockVN,
833: fact
834: .getUnconditionalDerefLocationSet(targetVN));
835:
836: }
837:
838: }
839: }
840: if (DEBUG) {
841: System.out.println("Target VNF: " + targetValueNumberFrame);
842: System.out.println("Block VNF: " + blockValueNumberFrame);
843: System.out.println("fact: " + fact);
844: }
845: fact.cleanDerefSet(null, blockValueNumberFrame);
846: return fact;
847: }
848:
849: /**
850: * Return a duplicate of given dataflow fact.
851: *
852: * @param fact a dataflow fact
853: * @return a duplicate of the input dataflow fact
854: */
855: private UnconditionalValueDerefSet duplicateFact(
856: UnconditionalValueDerefSet fact) {
857: UnconditionalValueDerefSet copyOfFact = createFact();
858: copy(fact, copyOfFact);
859: fact = copyOfFact;
860: return fact;
861: }
862:
863: /**
864: * Clear deref sets of values if this edge is the non-null branch
865: * of an if comparison.
866: *
867: * @param fact a datflow fact
868: * @param edge edge to check
869: * @return possibly-modified dataflow fact
870: */
871: private @CheckForNull
872: ValueNumber findValueKnownNonnullOnBranch(
873: UnconditionalValueDerefSet fact, Edge edge) {
874:
875: IsNullValueFrame invFrame = invDataflow.getResultFact(edge
876: .getSource());
877: if (!invFrame.isValid()) {
878: return null;
879: }
880: IsNullConditionDecision decision = invFrame.getDecision();
881: if (decision == null) {
882: return null;
883: }
884:
885: IsNullValue inv = decision.getDecision(edge.getType());
886: if (inv == null || !inv.isDefinitelyNotNull()) {
887: return null;
888: }
889: ValueNumber value = decision.getValue();
890: if (DEBUG) {
891: System.out.println("Value number " + value
892: + " is known nonnull on " + edge);
893: }
894:
895: return value;
896: }
897:
898: /**
899: * Determine whether dataflow should be propagated on given edge.
900: *
901: * @param edge the edge
902: * @return true if dataflow should be propagated on the edge, false otherwise
903: */
904: private boolean isExceptionEdge(Edge edge) {
905: boolean isExceptionEdge = edge.isExceptionEdge();
906: if (DEBUG && isExceptionEdge)
907: System.out.println("Ignoring " + edge);
908: return isExceptionEdge;
909: }
910:
911: /* (non-Javadoc)
912: * @see edu.umd.cs.findbugs.ba.DataflowAnalysis#same(java.lang.Object, java.lang.Object)
913: */
914: public boolean same(UnconditionalValueDerefSet fact1,
915: UnconditionalValueDerefSet fact2) {
916: return fact1.resultsFromBackEdge || fact1.isSameAs(fact2);
917: }
918:
919: @Override
920: public void startIteration() {
921: // System.out.println("analysis iteration in " + methodGen.getClassName() + " on " + methodGen.toString());
922: }
923:
924: @Override
925: public int getLastUpdateTimestamp(UnconditionalValueDerefSet fact) {
926: return fact.getLastUpdateTimestamp();
927: }
928:
929: @Override
930: public void setLastUpdateTimestamp(UnconditionalValueDerefSet fact,
931: int lastUpdate) {
932: fact.setLastUpdateTimestamp(lastUpdate);
933: }
934:
935: public static void main(String[] args) throws Exception {
936: if (args.length != 1) {
937: System.err.println("Usage: "
938: + UnconditionalValueDerefAnalysis.class.getName()
939: + " <classfile>");
940: System.exit(1);
941: }
942:
943: DataflowTestDriver<UnconditionalValueDerefSet, UnconditionalValueDerefAnalysis> driver = new DataflowTestDriver<UnconditionalValueDerefSet, UnconditionalValueDerefAnalysis>() {
944: /* (non-Javadoc)
945: * @see edu.umd.cs.findbugs.ba.DataflowTestDriver#createDataflow(edu.umd.cs.findbugs.ba.ClassContext, org.apache.bcel.classfile.Method)
946: */
947: @Override
948: public Dataflow<UnconditionalValueDerefSet, UnconditionalValueDerefAnalysis> createDataflow(
949: ClassContext classContext, Method method)
950: throws CFGBuilderException,
951: DataflowAnalysisException {
952: return classContext
953: .getUnconditionalValueDerefDataflow(method);
954: }
955: };
956: if (SystemProperties.getBoolean("forwardcfg")) {
957: driver.overrideIsForwards();
958: }
959: driver.execute(args[0]);
960: }
961: }
|