001: /*
002: * Bytecode Analysis Framework
003: * Copyright (C) 2003-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.HashSet;
024: import java.util.Set;
025:
026: import org.apache.bcel.Constants;
027: import org.apache.bcel.classfile.Method;
028: import org.apache.bcel.generic.CodeExceptionGen;
029: import org.apache.bcel.generic.Instruction;
030: import org.apache.bcel.generic.InstructionHandle;
031: import org.apache.bcel.generic.MethodGen;
032: import org.apache.bcel.generic.ObjectType;
033: import org.apache.bcel.generic.Type;
034:
035: import edu.umd.cs.findbugs.SystemProperties;
036: import edu.umd.cs.findbugs.annotations.CheckForNull;
037: import edu.umd.cs.findbugs.ba.AnalysisContext;
038: import edu.umd.cs.findbugs.ba.AnalysisFeatures;
039: import edu.umd.cs.findbugs.ba.AssertionMethods;
040: import edu.umd.cs.findbugs.ba.BasicBlock;
041: import edu.umd.cs.findbugs.ba.CFG;
042: import edu.umd.cs.findbugs.ba.CFGBuilderException;
043: import edu.umd.cs.findbugs.ba.ClassContext;
044: import edu.umd.cs.findbugs.ba.Dataflow;
045: import edu.umd.cs.findbugs.ba.DataflowAnalysisException;
046: import edu.umd.cs.findbugs.ba.DataflowTestDriver;
047: import edu.umd.cs.findbugs.ba.DepthFirstSearch;
048: import edu.umd.cs.findbugs.ba.Edge;
049: import edu.umd.cs.findbugs.ba.EdgeTypes;
050: import edu.umd.cs.findbugs.ba.FrameDataflowAnalysis;
051: import edu.umd.cs.findbugs.ba.INullnessAnnotationDatabase;
052: import edu.umd.cs.findbugs.ba.JavaClassAndMethod;
053: import edu.umd.cs.findbugs.ba.Location;
054: import edu.umd.cs.findbugs.ba.NullnessAnnotation;
055: import edu.umd.cs.findbugs.ba.XFactory;
056: import edu.umd.cs.findbugs.ba.XMethod;
057: import edu.umd.cs.findbugs.ba.XMethodParameter;
058: import edu.umd.cs.findbugs.ba.vna.AvailableLoad;
059: import edu.umd.cs.findbugs.ba.vna.ValueNumber;
060: import edu.umd.cs.findbugs.ba.vna.ValueNumberDataflow;
061: import edu.umd.cs.findbugs.ba.vna.ValueNumberFrame;
062:
063: /**
064: * A dataflow analysis to detect potential null pointer dereferences.
065: *
066: * @author David Hovemeyer
067: * @see IsNullValue
068: * @see IsNullValueFrame
069: * @see IsNullValueFrameModelingVisitor
070: */
071: public class IsNullValueAnalysis extends
072: FrameDataflowAnalysis<IsNullValue, IsNullValueFrame> implements
073: EdgeTypes, IsNullValueAnalysisFeatures {
074: static final boolean DEBUG = SystemProperties
075: .getBoolean("inva.debug");
076:
077: static {
078: if (DEBUG)
079: System.out.println("inva.debug enabled");
080: }
081:
082: private MethodGen methodGen;
083: private IsNullValueFrameModelingVisitor visitor;
084: private ValueNumberDataflow vnaDataflow;
085: private CFG cfg;
086: private Set<LocationWhereValueBecomesNull> locationWhereValueBecomesNullSet;
087: private final boolean trackValueNumbers;
088:
089: private IsNullValueFrame lastFrame;
090: private IsNullValueFrame instanceOfFrame;
091: private IsNullValueFrame cachedEntryFact;
092:
093: private JavaClassAndMethod classAndMethod;
094:
095: public IsNullValueAnalysis(MethodGen methodGen, CFG cfg,
096: ValueNumberDataflow vnaDataflow, DepthFirstSearch dfs,
097: AssertionMethods assertionMethods) {
098: super (dfs);
099:
100: this .trackValueNumbers = AnalysisContext
101: .currentAnalysisContext()
102: .getBoolProperty(
103: AnalysisFeatures.TRACK_VALUE_NUMBERS_IN_NULL_POINTER_ANALYSIS);
104:
105: this .methodGen = methodGen;
106: this .visitor = new IsNullValueFrameModelingVisitor(methodGen
107: .getConstantPool(), assertionMethods, vnaDataflow,
108: trackValueNumbers);
109: this .vnaDataflow = vnaDataflow;
110: this .cfg = cfg;
111: this .locationWhereValueBecomesNullSet = new HashSet<LocationWhereValueBecomesNull>();
112:
113: if (DEBUG) {
114: System.out.println("IsNullValueAnalysis for "
115: + methodGen.getClassName() + "."
116: + methodGen.getName() + " : "
117: + methodGen.getSignature());
118: }
119: }
120:
121: public void setClassAndMethod(JavaClassAndMethod classAndMethod) {
122: this .classAndMethod = classAndMethod;
123: }
124:
125: public JavaClassAndMethod getClassAndMethod() {
126: return classAndMethod;
127: }
128:
129: public IsNullValueFrame createFact() {
130: return new IsNullValueFrame(methodGen.getMaxLocals(),
131: trackValueNumbers);
132: }
133:
134: public void initEntryFact(IsNullValueFrame result) {
135: if (cachedEntryFact == null) {
136:
137: cachedEntryFact = createFact();
138: cachedEntryFact.setValid();
139:
140: int numLocals = methodGen.getMaxLocals();
141: boolean instanceMethod = !methodGen.isStatic();
142: XMethod xm = XFactory.createXMethod(methodGen
143: .getClassName(), methodGen.getName(), methodGen
144: .getSignature(), methodGen.isStatic());
145: INullnessAnnotationDatabase db = AnalysisContext
146: .currentAnalysisContext()
147: .getNullnessAnnotationDatabase();
148: int paramShift = instanceMethod ? 1 : 0;
149: Type[] argumentTypes = methodGen.getArgumentTypes();
150: for (int i = 0; i < numLocals; ++i) {
151: cachedEntryFact.setValue(i, IsNullValue
152: .nonReportingNotNullValue());
153: }
154: if (paramShift == 1)
155: cachedEntryFact.setValue(0, IsNullValue.nonNullValue());
156:
157: int slot = paramShift;
158: for (int paramIndex = 0; paramIndex < argumentTypes.length; paramIndex++) {
159: IsNullValue value;
160:
161: XMethodParameter methodParameter = new XMethodParameter(
162: xm, paramIndex);
163: NullnessAnnotation n = db.getResolvedAnnotation(
164: methodParameter, false);
165: if (n == NullnessAnnotation.CHECK_FOR_NULL)
166: // Parameter declared @CheckForNull
167: value = IsNullValue
168: .parameterMarkedAsMightBeNull(methodParameter);
169: else if (n == NullnessAnnotation.NONNULL)
170: // Parameter declared @NonNull
171: // TODO: label this so we don't report defensive programming
172: value = IsNullValue.nonNullValue();
173: else
174: // Don't know; use default value, normally non-reporting nonnull
175: value = IsNullValue.nonReportingNotNullValue();
176:
177: cachedEntryFact.setValue(slot, value);
178:
179: slot += argumentTypes[paramIndex].getSize();
180: }
181: }
182: copy(cachedEntryFact, result);
183: }
184:
185: @Override
186: public void transfer(BasicBlock basicBlock, @CheckForNull
187: InstructionHandle end, IsNullValueFrame start,
188: IsNullValueFrame result) throws DataflowAnalysisException {
189: startTransfer();
190: super .transfer(basicBlock, end, start, result);
191: endTransfer(basicBlock, end, result);
192: ValueNumberFrame vnaFrameAfter = vnaDataflow
193: .getFactAfterLocation(Location
194: .getLastLocation(basicBlock));
195: // purge stale information
196: if (!vnaFrameAfter.isTop())
197: result.cleanStaleKnowledge(vnaFrameAfter);
198: }
199:
200: public void startTransfer() throws DataflowAnalysisException {
201: lastFrame = null;
202: instanceOfFrame = null;
203: }
204:
205: public void endTransfer(BasicBlock basicBlock, @CheckForNull
206: InstructionHandle end, IsNullValueFrame result)
207: throws DataflowAnalysisException {
208: // Determine if this basic block ends in a redundant branch.
209: if (end == null) {
210: if (lastFrame == null)
211: result.setDecision(null);
212: else {
213: IsNullConditionDecision decision = getDecision(
214: basicBlock, lastFrame);
215: //if (DEBUG) System.out.println("Decision=" + decision);
216: result.setDecision(decision);
217: }
218: }
219: lastFrame = null;
220: instanceOfFrame = null;
221: }
222:
223: @Override
224: public void transferInstruction(InstructionHandle handle,
225: BasicBlock basicBlock, IsNullValueFrame fact)
226: throws DataflowAnalysisException {
227:
228: // If this is the last instruction in the block,
229: // save the result immediately before the instruction.
230: if (handle == basicBlock.getLastInstruction()) {
231: lastFrame = createFact();
232: lastFrame.copyFrom(fact);
233: }
234:
235: if (handle.getInstruction().getOpcode() == Constants.INSTANCEOF) {
236: instanceOfFrame = createFact();
237: instanceOfFrame.copyFrom(fact);
238: }
239:
240: // Model the instruction
241: visitor.setFrameAndLocation(fact, new Location(handle,
242: basicBlock));
243: Instruction ins = handle.getInstruction();
244: visitor.analyzeInstruction(ins);
245:
246: // Special case:
247: // The instruction may have produced previously seen values
248: // about which new is-null information is known.
249: // If any other instances of the produced values exist,
250: // update their is-null information.
251: // Also, make a note of any newly-produced null values.
252:
253: int numProduced = ins.produceStack(methodGen.getConstantPool());
254: if (numProduced == Constants.UNPREDICTABLE)
255: throw new DataflowAnalysisException(
256: "Unpredictable stack production", methodGen, handle);
257:
258: int start = fact.getNumSlots() - numProduced;
259: Location location = new Location(handle, basicBlock);
260: ValueNumberFrame vnaFrameAfter = vnaDataflow
261: .getFactAfterLocation(location);
262: if (!vnaFrameAfter.isValid()) {
263: assert false : "Invalid VNA after location " + location;
264: return;
265: }
266: for (int i = start; i < fact.getNumSlots(); ++i) {
267: ValueNumber value = vnaFrameAfter.getValue(i);
268: IsNullValue isNullValue = fact.getValue(i);
269:
270: for (int j = 0; j < start; ++j) {
271: ValueNumber otherValue = vnaFrameAfter.getValue(j);
272: if (value.equals(otherValue)) {
273: // Same value is in both slots.
274: // Update the is-null information to match
275: // the new information.
276: fact.setValue(j, isNullValue);
277: }
278: }
279: }
280:
281: if (visitor.getSlotContainingNewNullValue() >= 0) {
282: ValueNumber newNullValue = vnaFrameAfter.getValue(visitor
283: .getSlotContainingNewNullValue());
284: addLocationWhereValueBecomesNull(new LocationWhereValueBecomesNull(
285: location, newNullValue//,
286: //handle
287: ));
288: }
289:
290: }
291:
292: private static final BitSet nullComparisonInstructionSet = new BitSet();
293:
294: static {
295: nullComparisonInstructionSet.set(Constants.IFNULL);
296:
297: nullComparisonInstructionSet.set(Constants.IFNONNULL);
298: nullComparisonInstructionSet.set(Constants.IF_ACMPEQ);
299: nullComparisonInstructionSet.set(Constants.IF_ACMPNE);
300: }
301:
302: public void meetInto(IsNullValueFrame fact, Edge edge,
303: IsNullValueFrame result) throws DataflowAnalysisException {
304: meetInto(fact, edge, result, true);
305: }
306:
307: public void meetInto(IsNullValueFrame fact, Edge edge,
308: IsNullValueFrame result, boolean propagatePhiNodeInformation)
309: throws DataflowAnalysisException {
310:
311: if (fact.isValid()) {
312: IsNullValueFrame tmpFact = null;
313:
314: if (!NO_SPLIT_DOWNGRADE_NSP) {
315: // Downgrade NSP to DNR on non-exception control splits
316: if (!edge.isExceptionEdge()
317: && cfg.getNumNonExceptionSucessors(edge
318: .getSource()) > 1) {
319: tmpFact = modifyFrame(fact, tmpFact);
320: tmpFact.downgradeOnControlSplit();
321: }
322: }
323:
324: if (!NO_SWITCH_DEFAULT_AS_EXCEPTION) {
325: if (edge.getType() == SWITCH_DEFAULT_EDGE) {
326: tmpFact = modifyFrame(fact, tmpFact);
327: tmpFact.toExceptionValues();
328: }
329: }
330:
331: final BasicBlock destBlock = edge.getTarget();
332:
333: if (destBlock.isExceptionHandler()) {
334: // Exception handler - clear stack and push a non-null value
335: // to represent the exception.
336: tmpFact = modifyFrame(fact, tmpFact);
337: tmpFact.clearStack();
338:
339: // Downgrade NULL and NSP to DNR if the handler is for
340: // CloneNotSupportedException or InterruptedException
341: if (true) {
342: CodeExceptionGen handler = destBlock
343: .getExceptionGen();
344: ObjectType catchType = handler.getCatchType();
345: if (catchType != null) {
346: String catchClass = catchType.getClassName();
347: if (catchClass
348: .equals("java.lang.CloneNotSupportedException")
349: || catchClass
350: .equals("java.lang.InterruptedException")) {
351: for (int i = 0; i < tmpFact.getNumSlots(); ++i) {
352: IsNullValue value = tmpFact.getValue(i);
353: if (value.isDefinitelyNull()
354: || value.isNullOnSomePath())
355: tmpFact.setValue(i, IsNullValue
356: .nullOnComplexPathValue());
357: }
358: }
359: }
360: }
361:
362: // Mark all values as having occurred on an exception path
363: tmpFact.toExceptionValues();
364:
365: // Push the exception value
366: tmpFact.pushValue(IsNullValue.nonNullValue());
367: } else {
368: final int edgeType = edge.getType();
369: final BasicBlock sourceBlock = edge.getSource();
370: final BasicBlock targetBlock = edge.getTarget();
371: final ValueNumberFrame targetVnaFrame = vnaDataflow
372: .getStartFact(destBlock);
373: final ValueNumberFrame sourceVnaFrame = vnaDataflow
374: .getResultFact(sourceBlock);
375:
376: assert targetVnaFrame != null;
377:
378: // Determine if the edge conveys any information about the
379: // null/non-null status of operands in the incoming frame.
380: if (edgeType == IFCMP_EDGE
381: || edgeType == FALL_THROUGH_EDGE) {
382: IsNullConditionDecision decision = getResultFact(
383: edge.getSource()).getDecision();
384: if (decision != null) {
385: if (!decision.isEdgeFeasible(edgeType)) {
386: // The incoming edge is infeasible; just use TOP
387: // as the start fact for this block.
388: tmpFact = createFact();
389: tmpFact.setTop();
390: } else if (decision.getValue() != null) {
391: // A value has been determined for this edge.
392: // Use the value to update the is-null information in
393: // the start fact for this block.
394:
395: if (DEBUG) {
396: System.out
397: .println("Updating edge information for "
398: + decision.getValue());
399: }
400: final Location atIf = new Location(
401: sourceBlock.getLastInstruction(),
402: sourceBlock);
403: // TODO: prevIsNullValueFrame is not used
404: final IsNullValueFrame prevIsNullValueFrame = getFactAtLocation(atIf);
405: final ValueNumberFrame prevVnaFrame = vnaDataflow
406: .getFactAtLocation(atIf);
407:
408: IsNullValue decisionValue = decision
409: .getDecision(edgeType);
410: if (decisionValue != null) {
411: if (decisionValue.isDefinitelyNull()) {
412: // Make a note of the value that has become null
413: // due to the if comparison.
414: addLocationWhereValueBecomesNull(new LocationWhereValueBecomesNull(
415: atIf, decision.getValue()));
416: }
417: if (DEBUG) {
418: System.out
419: .println("Set decision information");
420: System.out.println(" "
421: + decision.getValue()
422: + " becomes "
423: + decisionValue);
424: System.out
425: .println(" prev available loads: "
426: + prevVnaFrame
427: .availableLoadMapAsString());
428: System.out
429: .println(" target available loads: "
430: + targetVnaFrame
431: .availableLoadMapAsString());
432: }
433: tmpFact = replaceValues(fact, tmpFact,
434: decision.getValue(),
435: prevVnaFrame, targetVnaFrame,
436: decisionValue);
437: }
438:
439: }
440: }
441: } // if (edgeType == IFCMP_EDGE || edgeType == FALL_THROUGH_EDGE)
442:
443: // If this is a fall-through edge from a null check,
444: // then we know the value checked is not null.
445: if (sourceBlock.isNullCheck()
446: && edgeType == FALL_THROUGH_EDGE) {
447: ValueNumberFrame vnaFrame = vnaDataflow
448: .getStartFact(destBlock);
449: if (vnaFrame == null)
450: throw new IllegalStateException(
451: "no vna frame at block entry?");
452:
453: Instruction firstInDest = edge.getTarget()
454: .getFirstInstruction().getInstruction();
455:
456: IsNullValue instance = fact.getInstance(
457: firstInDest, methodGen.getConstantPool());
458:
459: if (instance.isDefinitelyNull()) {
460: // If we know the variable is null, this edge is infeasible
461: tmpFact = createFact();
462: tmpFact.setTop();
463: } else if (!instance.isDefinitelyNotNull()) {
464: // If we're not sure that the instance is definitely non-null,
465: // update the is-null information for the dereferenced value.
466: InstructionHandle kaBoomLocation = targetBlock
467: .getFirstInstruction();
468: ValueNumber replaceMe = vnaFrame.getInstance(
469: firstInDest, methodGen
470: .getConstantPool());
471: IsNullValue noKaboomNonNullValue = IsNullValue
472: .noKaboomNonNullValue(new Location(
473: kaBoomLocation, targetBlock));
474: if (DEBUG) {
475: System.out.println("Start vna fact: "
476: + vnaFrame);
477: System.out.println("inva fact: " + fact);
478: System.out
479: .println("\nGenerated NoKaboom value for location "
480: + kaBoomLocation);
481: System.out.println("Dereferenced "
482: + instance);
483: System.out
484: .println("On fall through from source block "
485: + sourceBlock);
486: }
487: tmpFact = replaceValues(fact, tmpFact,
488: replaceMe, vnaFrame, targetVnaFrame,
489: noKaboomNonNullValue);
490: }
491: } // if (sourceBlock.isNullCheck() && edgeType == FALL_THROUGH_EDGE)
492:
493: if (propagatePhiNodeInformation
494: && targetVnaFrame.phiNodeForLoads) {
495: if (DEBUG)
496: System.out.println("Is phi node for loads");
497: for (ValueNumber v : fact.getKnownValues()) {
498: AvailableLoad loadForV = sourceVnaFrame
499: .getLoad(v);
500: if (DEBUG) {
501: System.out.println(" " + v + " for "
502: + loadForV);
503: }
504: if (loadForV != null) {
505: ValueNumber[] matchingValueNumbers = targetVnaFrame
506: .getAvailableLoad(loadForV);
507: if (matchingValueNumbers != null)
508: for (ValueNumber v2 : matchingValueNumbers) {
509: tmpFact = modifyFrame(fact, tmpFact);
510: tmpFact.useNewValueNumberForLoad(v,
511: v2);
512: if (DEBUG)
513: System.out.println("For "
514: + loadForV
515: + " switch from " + v
516: + " to " + v2);
517: }
518: }
519:
520: }
521: }
522: }
523: if (tmpFact != null)
524: fact = tmpFact;
525: } // if (fact.isValid())
526:
527: // Normal dataflow merge
528: mergeInto(fact, result);
529: }
530:
531: /* (non-Javadoc)
532: * @see edu.umd.cs.findbugs.ba.FrameDataflowAnalysis#mergeInto(edu.umd.cs.findbugs.ba.Frame, edu.umd.cs.findbugs.ba.Frame)
533: */
534: @Override
535: protected void mergeInto(IsNullValueFrame other,
536: IsNullValueFrame result) throws DataflowAnalysisException {
537: if (other.isTop())
538: return;
539: if (result.isTop()) {
540: result.copyFrom(other);
541: return;
542: }
543: super .mergeInto(other, result);
544: //FIXME: update decision?
545: if (trackValueNumbers) {
546: result.mergeKnownValuesWith(other);
547: }
548:
549: }
550:
551: /* (non-Javadoc)
552: * @see edu.umd.cs.findbugs.ba.AbstractDataflowAnalysis#startIteration()
553: */
554: @Override
555: public void startIteration() {
556: // At the beginning of each iteration, clear the set of locations
557: // where values become null. That way, after the final iteration
558: // of dataflow analysis the set should be as accurate as possible.
559: locationWhereValueBecomesNullSet.clear();
560: }
561:
562: public void addLocationWhereValueBecomesNull(
563: LocationWhereValueBecomesNull locationWhereValueBecomesNull) {
564: // System.out.println("Location becomes null: " + locationWhereValueBecomesNull );
565: locationWhereValueBecomesNullSet
566: .add(locationWhereValueBecomesNull);
567: }
568:
569: public Set<LocationWhereValueBecomesNull> getLocationWhereValueBecomesNullSet() {
570: return locationWhereValueBecomesNullSet;
571: }
572:
573: @Override
574: protected void mergeValues(IsNullValueFrame otherFrame,
575: IsNullValueFrame resultFrame, int slot)
576: throws DataflowAnalysisException {
577: IsNullValue value = IsNullValue.merge(resultFrame
578: .getValue(slot), otherFrame.getValue(slot));
579: resultFrame.setValue(slot, value);
580: }
581:
582: /**
583: * Determine if the given basic block ends in a redundant
584: * null comparison.
585: *
586: * @param basicBlock the basic block
587: * @param lastFrame the IsNullValueFrame representing values at the final instruction
588: * of the block
589: * @return an IsNullConditionDecision object representing the
590: * is-null information gained about the compared value,
591: * or null if no information is gained
592: */
593: private IsNullConditionDecision getDecision(BasicBlock basicBlock,
594: IsNullValueFrame lastFrame)
595: throws DataflowAnalysisException {
596:
597: assert lastFrame != null;
598:
599: final InstructionHandle lastInSourceHandle = basicBlock
600: .getLastInstruction();
601: if (lastInSourceHandle == null)
602: return null; // doesn't end in null comparison
603:
604: final short lastInSourceOpcode = lastInSourceHandle
605: .getInstruction().getOpcode();
606: // System.out.println("last opcode: " + Constants.OPCODE_NAMES[lastInSourceOpcode]);
607: if (lastInSourceOpcode == Constants.IFEQ
608: || lastInSourceOpcode == Constants.IFNE) {
609: InstructionHandle prev = lastInSourceHandle.getPrev();
610: if (prev == null)
611: return null;
612: short secondToLastOpcode = prev.getInstruction()
613: .getOpcode();
614: // System.out.println("Second last opcode: " + Constants.OPCODE_NAMES[secondToLastOpcode]);
615: if (secondToLastOpcode != Constants.INSTANCEOF)
616: return null;
617: if (instanceOfFrame == null)
618: return null;
619: IsNullValue tos = instanceOfFrame.getTopValue();
620: boolean isNotInstanceOf = (lastInSourceOpcode != Constants.IFNE);
621: Location atInstanceOf = new Location(prev, basicBlock);
622: ValueNumberFrame instanceOfVnaFrame = vnaDataflow
623: .getFactAtLocation(atInstanceOf);
624:
625: // Initially, assume neither branch is feasible.
626: IsNullValue ifcmpDecision = null;
627: IsNullValue fallThroughDecision = null;
628:
629: if (tos.isDefinitelyNull()) {
630: // Predetermined comparison - one branch is infeasible
631: if (isNotInstanceOf)
632: ifcmpDecision = tos;
633: else
634: // ifnonnull
635: fallThroughDecision = tos;
636: } else if (tos.isDefinitelyNotNull()) {
637: return null;
638: } else {
639: // As far as we know, both branches feasible
640: ifcmpDecision = isNotInstanceOf ? tos : IsNullValue
641: .pathSensitiveNonNullValue();
642: fallThroughDecision = isNotInstanceOf ? IsNullValue
643: .pathSensitiveNonNullValue() : tos;
644: }
645: if (DEBUG)
646: System.out.println("Checking..." + tos + " -> "
647: + ifcmpDecision + " or " + fallThroughDecision);
648:
649: return new IsNullConditionDecision(instanceOfVnaFrame
650: .getTopValue(), ifcmpDecision, fallThroughDecision);
651:
652: }
653: if (!nullComparisonInstructionSet.get(lastInSourceOpcode))
654: return null; // doesn't end in null comparison
655:
656: Location atIf = new Location(lastInSourceHandle, basicBlock);
657: ValueNumberFrame prevVnaFrame = vnaDataflow
658: .getFactAtLocation(atIf);
659:
660: switch (lastInSourceOpcode) {
661:
662: case Constants.IFNULL:
663: case Constants.IFNONNULL: {
664: IsNullValue tos = lastFrame.getTopValue();
665: boolean ifnull = (lastInSourceOpcode == Constants.IFNULL);
666:
667: // Initially, assume neither branch is feasible.
668: IsNullValue ifcmpDecision = null;
669: IsNullValue fallThroughDecision = null;
670:
671: if (tos.isDefinitelyNull()) {
672: // Predetermined comparison - one branch is infeasible
673: if (ifnull)
674: ifcmpDecision = IsNullValue
675: .pathSensitiveNullValue();
676: else
677: // ifnonnull
678: fallThroughDecision = IsNullValue
679: .pathSensitiveNullValue();
680: } else if (tos.isDefinitelyNotNull()) {
681: // Predetermined comparison - one branch is infeasible
682: if (ifnull)
683: fallThroughDecision = IsNullValue
684: .pathSensitiveNonNullValue();
685: else
686: // ifnonnull
687: ifcmpDecision = IsNullValue
688: .pathSensitiveNonNullValue();
689: } else {
690: // As far as we know, both branches feasible
691: ifcmpDecision = ifnull ? IsNullValue
692: .pathSensitiveNullValue() : IsNullValue
693: .pathSensitiveNonNullValue();
694: fallThroughDecision = ifnull ? IsNullValue
695: .pathSensitiveNonNullValue() : IsNullValue
696: .pathSensitiveNullValue();
697: }
698: return new IsNullConditionDecision(prevVnaFrame
699: .getTopValue(), ifcmpDecision, fallThroughDecision);
700: }
701: case Constants.IF_ACMPEQ:
702: case Constants.IF_ACMPNE: {
703: IsNullValue tos = lastFrame.getStackValue(0);
704: IsNullValue nextToTos = lastFrame.getStackValue(1);
705:
706: boolean tosNull = tos.isDefinitelyNull();
707: boolean nextToTosNull = nextToTos.isDefinitelyNull();
708:
709: boolean cmpeq = (lastInSourceOpcode == Constants.IF_ACMPEQ);
710:
711: // Initially, assume neither branch is feasible.
712: IsNullValue ifcmpDecision = null;
713: IsNullValue fallThroughDecision = null;
714: ValueNumber value;
715:
716: if (tosNull && nextToTosNull) {
717: // Redundant comparision: both values are null, only one branch is feasible
718: value = null; // no value will be replaced - just want to indicate that one of the branches is infeasible
719: if (cmpeq)
720: ifcmpDecision = IsNullValue
721: .pathSensitiveNullValue();
722: else
723: // cmpne
724: fallThroughDecision = IsNullValue
725: .pathSensitiveNullValue();
726: } else if (tosNull || nextToTosNull) {
727: // We have updated information about whichever value is not null;
728: // both branches are feasible
729: value = prevVnaFrame.getStackValue(tosNull ? 1 : 0);
730: ifcmpDecision = cmpeq ? IsNullValue
731: .pathSensitiveNullValue() : IsNullValue
732: .pathSensitiveNonNullValue();
733: fallThroughDecision = cmpeq ? IsNullValue
734: .pathSensitiveNonNullValue() : IsNullValue
735: .pathSensitiveNullValue();
736: } else if (tos.isDefinitelyNotNull()
737: && !nextToTos.isDefinitelyNotNull()) {
738: // learn that nextToTos is definitely non null on one branch
739: value = prevVnaFrame.getStackValue(1);
740: if (cmpeq) {
741: ifcmpDecision = tos;
742: fallThroughDecision = nextToTos;
743: } else {
744: fallThroughDecision = tos;
745: ifcmpDecision = nextToTos;
746: }
747: } else if (!tos.isDefinitelyNotNull()
748: && nextToTos.isDefinitelyNotNull()) {
749: // learn that tos is definitely non null on one branch
750: value = prevVnaFrame.getStackValue(0);
751: if (cmpeq) {
752: ifcmpDecision = nextToTos;
753: fallThroughDecision = tos;
754: } else {
755: fallThroughDecision = nextToTos;
756: ifcmpDecision = tos;
757: }
758: } else {
759: // No information gained
760: break;
761: }
762:
763: return new IsNullConditionDecision(value, ifcmpDecision,
764: fallThroughDecision);
765: }
766: default:
767: throw new IllegalStateException();
768: }
769:
770: return null; // no information gained
771: }
772:
773: /**
774: * Update is-null information at a branch target based on information gained at a
775: * null comparison branch.
776: *
777: * @param origFrame the original is-null frame at entry to basic block
778: * @param frame the modified version of the is-null entry frame;
779: * null if the entry frame has not been modified yet
780: * @param replaceMe the ValueNumber in the value number frame at the if comparison
781: * whose is-null information will be updated
782: * @param prevVnaFrame the ValueNumberFrame at the if comparison
783: * @param targetVnaFrame the ValueNumberFrame at entry to the basic block
784: * @param replacementValue the IsNullValue representing the updated
785: * is-null information
786: * @return a modified IsNullValueFrame with updated is-null information
787: */
788: private IsNullValueFrame replaceValues(IsNullValueFrame origFrame,
789: IsNullValueFrame frame, ValueNumber replaceMe,
790: ValueNumberFrame prevVnaFrame,
791: ValueNumberFrame targetVnaFrame,
792: IsNullValue replacementValue) {
793:
794: // If required, make a copy of the frame
795: frame = modifyFrame(origFrame, frame);
796:
797: assert frame.getNumSlots() == targetVnaFrame.getNumSlots();
798:
799: // The VNA frame may have more slots than the IsNullValueFrame
800: // if it was produced by an IF comparison (whose operand or operands
801: // are subsequently popped off the stack).
802:
803: final int targetNumSlots = targetVnaFrame.getNumSlots();
804: final int prefixNumSlots = Math.min(frame.getNumSlots(),
805: prevVnaFrame.getNumSlots());
806:
807: if (trackValueNumbers) {
808: AvailableLoad loadForV = prevVnaFrame.getLoad(replaceMe);
809: if (DEBUG && loadForV != null) {
810: System.out.println("For " + replaceMe
811: + " availableLoad is " + loadForV);
812: ValueNumber[] matchingValueNumbers = targetVnaFrame
813: .getAvailableLoad(loadForV);
814: if (matchingValueNumbers != null)
815: for (ValueNumber v2 : matchingValueNumbers)
816: System.out.println(" matches " + v2);
817: }
818: if (loadForV != null) {
819: ValueNumber[] matchingValueNumbers = targetVnaFrame
820: .getAvailableLoad(loadForV);
821: if (matchingValueNumbers != null)
822: for (ValueNumber v2 : matchingValueNumbers)
823: if (!replaceMe.equals(v2)) {
824: frame.setKnownValue(v2, replacementValue);
825: if (DEBUG)
826: System.out.println("For " + loadForV
827: + " switch from " + replaceMe
828: + " to " + v2);
829: }
830: }
831: frame.setKnownValue(replaceMe, replacementValue);
832: }
833: // Here's the deal:
834: // - "replaceMe" is the value number from the previous frame (at the if branch)
835: // which indicates a value that we have updated is-null information about
836: // - in the target value number frame (at entry to the target block),
837: // we find the value number in the stack slot corresponding to the "replaceMe"
838: // value; this is the "corresponding" value
839: // - all instances of the "corresponding" value in the target frame have
840: // their is-null information updated to "replacementValue"
841: // This should thoroughly make use of the updated information.
842:
843: for (int i = 0; i < prefixNumSlots; ++i) {
844: if (prevVnaFrame.getValue(i).equals(replaceMe)) {
845: ValueNumber corresponding = targetVnaFrame.getValue(i);
846: for (int j = 0; j < targetNumSlots; ++j) {
847: if (targetVnaFrame.getValue(j)
848: .equals(corresponding))
849: frame.setValue(j, replacementValue);
850: }
851: }
852: }
853:
854: return frame;
855:
856: }
857:
858: public IsNullValueFrame getFactAtMidEdge(Edge edge)
859: throws DataflowAnalysisException {
860: BasicBlock block = isForwards() ? edge.getSource() : edge
861: .getTarget();
862:
863: IsNullValueFrame predFact = createFact();
864: copy(getResultFact(block), predFact);
865:
866: edgeTransfer(edge, predFact);
867:
868: IsNullValueFrame result = createFact();
869: makeFactTop(result);
870: meetInto(predFact, edge, result, false);
871:
872: return result;
873: }
874:
875: /**
876: * Test driver.
877: */
878: public static void main(String[] argv) throws Exception {
879: if (argv.length != 1) {
880: System.err.println("Usage: "
881: + IsNullValueAnalysis.class.getName()
882: + " <class file>");
883: System.exit(1);
884: }
885:
886: DataflowTestDriver<IsNullValueFrame, IsNullValueAnalysis> driver = new DataflowTestDriver<IsNullValueFrame, IsNullValueAnalysis>() {
887: @Override
888: public Dataflow<IsNullValueFrame, IsNullValueAnalysis> createDataflow(
889: ClassContext classContext, Method method)
890: throws CFGBuilderException,
891: DataflowAnalysisException {
892:
893: return classContext.getIsNullValueDataflow(method);
894: }
895: };
896:
897: driver.execute(argv[0]);
898: }
899:
900: }
901:
902: // vim:ts=4
|