isnullvalueanalysis.java

A static analysis tool to find bugs in Java programs

									System.out.println("  target available loads: " + targetVnaFrame.availableLoadMapAsString());
								}
								tmpFact = replaceValues(fact, tmpFact, decision.getValue(), prevVnaFrame,
										targetVnaFrame, decisionValue);
							}

						}
					}
				} // if (edgeType == IFCMP_EDGE || edgeType == FALL_THROUGH_EDGE)

				// If this is a fall-through edge from a null check,
				// then we know the value checked is not null.
				if (sourceBlock.isNullCheck() && edgeType == FALL_THROUGH_EDGE) {
					ValueNumberFrame vnaFrame = vnaDataflow.getStartFact(destBlock);
					if (vnaFrame == null)
						throw new IllegalStateException("no vna frame at block entry?");

					Instruction firstInDest = edge.getTarget().getFirstInstruction().getInstruction();


					IsNullValue instance = fact.getInstance(firstInDest, methodGen.getConstantPool());


					if (instance.isDefinitelyNull()) {
						// If we know the variable is null, this edge is infeasible
						tmpFact = createFact();
						tmpFact.setTop();
					}
					else if (!instance.isDefinitelyNotNull()) {
						// If we're not sure that the instance is definitely non-null,
						// update the is-null information for the dereferenced value.
						InstructionHandle kaBoomLocation = targetBlock.getFirstInstruction();
						ValueNumber replaceMe = vnaFrame.getInstance(firstInDest, methodGen.getConstantPool());
						IsNullValue noKaboomNonNullValue = IsNullValue.noKaboomNonNullValue(
														new Location(kaBoomLocation, targetBlock)
														);
						if (DEBUG) {
							System.out.println("Start vna fact: " + vnaFrame);
							System.out.println("inva fact: " + fact);
							System.out.println("\nGenerated NoKaboom value for location " + kaBoomLocation);
							System.out.println("Dereferenced " + instance);
							System.out.println("On fall through from source block " + sourceBlock);
						}
						tmpFact = replaceValues(fact, tmpFact, replaceMe, vnaFrame, targetVnaFrame, noKaboomNonNullValue);
					}
				} // if (sourceBlock.isNullCheck() && edgeType == FALL_THROUGH_EDGE)

				if (propagatePhiNodeInformation && targetVnaFrame.phiNodeForLoads) {
					if (DEBUG) 
						System.out.println("Is phi node for loads");
					for(ValueNumber v : fact.getKnownValues()) {
						AvailableLoad loadForV = sourceVnaFrame.getLoad(v);
						if (DEBUG) {
							System.out.println("  " + v + " for " + loadForV);
						}
						if (loadForV != null) {
							ValueNumber[] matchingValueNumbers = targetVnaFrame.getAvailableLoad(loadForV);
							if (matchingValueNumbers != null)
								for(ValueNumber v2 : matchingValueNumbers) {
									tmpFact = modifyFrame(fact, tmpFact);
									tmpFact.useNewValueNumberForLoad(v, v2);
									if (DEBUG) System.out.println("For " + loadForV + " switch from " + v + " to " + v2);
								}
						}

					}
				}
			}
			if (tmpFact != null)
				fact = tmpFact;
		} // if (fact.isValid())

		// Normal dataflow merge
		mergeInto(fact, result);
	}

	/* (non-Javadoc)
	 * @see edu.umd.cs.findbugs.ba.FrameDataflowAnalysis#mergeInto(edu.umd.cs.findbugs.ba.Frame, edu.umd.cs.findbugs.ba.Frame)
	 */
	@Override
	protected void mergeInto(IsNullValueFrame other, IsNullValueFrame result) throws DataflowAnalysisException {
		if (other.isTop()) return;
		if (result.isTop()) {
			result.copyFrom(other);
			return;	
		}
		super.mergeInto(other, result);
		//FIXME: update decision?
		if (trackValueNumbers) {
			result.mergeKnownValuesWith(other);
		}

	}

	/* (non-Javadoc)
	 * @see edu.umd.cs.findbugs.ba.AbstractDataflowAnalysis#startIteration()
	 */
	@Override
	public void startIteration() {
		// At the beginning of each iteration, clear the set of locations
		// where values become null.  That way, after the final iteration
		// of dataflow analysis the set should be as accurate as possible.
		locationWhereValueBecomesNullSet.clear();
	}

	public void addLocationWhereValueBecomesNull(LocationWhereValueBecomesNull locationWhereValueBecomesNull) {
		// System.out.println("Location becomes null: " + locationWhereValueBecomesNull );
		locationWhereValueBecomesNullSet.add(locationWhereValueBecomesNull);
	}

	public Set<LocationWhereValueBecomesNull> getLocationWhereValueBecomesNullSet() {
		return locationWhereValueBecomesNullSet;
	}

	@Override
	protected void mergeValues(IsNullValueFrame otherFrame, IsNullValueFrame resultFrame, int slot)
			throws DataflowAnalysisException {
		IsNullValue value = IsNullValue.merge(resultFrame.getValue(slot), otherFrame.getValue(slot));
		resultFrame.setValue(slot, value);
	}

	/**
	 * Determine if the given basic block ends in a redundant
	 * null comparison.
	 *
	 * @param basicBlock the basic block
	 * @param lastFrame  the IsNullValueFrame representing values at the final instruction
	 *                   of the block
	 * @return an IsNullConditionDecision object representing the
	 *         is-null information gained about the compared value,
	 *         or null if no information is gained
	 */
	private IsNullConditionDecision getDecision(BasicBlock basicBlock,  IsNullValueFrame lastFrame)
			throws DataflowAnalysisException {

		assert lastFrame != null;

		final InstructionHandle lastInSourceHandle = basicBlock.getLastInstruction();
		if (lastInSourceHandle == null)
			return null; // doesn't end in null comparison

		final short lastInSourceOpcode = lastInSourceHandle.getInstruction().getOpcode();
		// System.out.println("last opcode: " + Constants.OPCODE_NAMES[lastInSourceOpcode]);
		if (lastInSourceOpcode == Constants.IFEQ || lastInSourceOpcode == Constants.IFNE ) {
			InstructionHandle prev = lastInSourceHandle.getPrev();
			if (prev == null) return null;
			short secondToLastOpcode = prev.getInstruction().getOpcode();
			// System.out.println("Second last opcode: " +  Constants.OPCODE_NAMES[secondToLastOpcode]);
			if (secondToLastOpcode != Constants.INSTANCEOF) return null;
			if (instanceOfFrame == null) return null;
			IsNullValue tos = instanceOfFrame.getTopValue();
			boolean isNotInstanceOf = (lastInSourceOpcode != Constants.IFNE);
			Location atInstanceOf = new Location(prev, basicBlock);
			ValueNumberFrame instanceOfVnaFrame = vnaDataflow.getFactAtLocation(atInstanceOf);

			// Initially, assume neither branch is feasible.
			IsNullValue ifcmpDecision = null;
			IsNullValue fallThroughDecision = null;

			if (tos.isDefinitelyNull()) {
				// Predetermined comparison - one branch is infeasible
				if (isNotInstanceOf)
					ifcmpDecision =tos;
				else // ifnonnull
					fallThroughDecision = tos;
			} else if (tos.isDefinitelyNotNull()) {
				return null;
			} else {
				// As far as we know, both branches feasible
				ifcmpDecision = isNotInstanceOf ? tos : IsNullValue.pathSensitiveNonNullValue();
				fallThroughDecision = isNotInstanceOf ? IsNullValue.pathSensitiveNonNullValue() : tos;
			}
			 if (DEBUG) System.out.println("Checking..." + tos + " -> " + ifcmpDecision + " or " + fallThroughDecision);

			return new IsNullConditionDecision(instanceOfVnaFrame.getTopValue(), ifcmpDecision, fallThroughDecision);

		}
		if (!nullComparisonInstructionSet.get(lastInSourceOpcode))
			return null; // doesn't end in null comparison

		Location atIf = new Location(lastInSourceHandle, basicBlock);
		ValueNumberFrame prevVnaFrame = vnaDataflow.getFactAtLocation(atIf);

		switch (lastInSourceOpcode) {

		case Constants.IFNULL:
		case Constants.IFNONNULL:
			{
				IsNullValue tos = lastFrame.getTopValue();
				boolean ifnull = (lastInSourceOpcode == Constants.IFNULL);

				// Initially, assume neither branch is feasible.
				IsNullValue ifcmpDecision = null;
				IsNullValue fallThroughDecision = null;

				if (tos.isDefinitelyNull()) {
					// Predetermined comparison - one branch is infeasible
					if (ifnull)
						ifcmpDecision = IsNullValue.pathSensitiveNullValue();
					else // ifnonnull
						fallThroughDecision = IsNullValue.pathSensitiveNullValue();
				} else if (tos.isDefinitelyNotNull()) {
					// Predetermined comparison - one branch is infeasible
					if (ifnull)
						fallThroughDecision = IsNullValue.pathSensitiveNonNullValue();
					else // ifnonnull
						ifcmpDecision = IsNullValue.pathSensitiveNonNullValue();
				} else {
					// As far as we know, both branches feasible
					ifcmpDecision = ifnull ? IsNullValue.pathSensitiveNullValue() : IsNullValue.pathSensitiveNonNullValue();
					fallThroughDecision = ifnull ? IsNullValue.pathSensitiveNonNullValue() : IsNullValue.pathSensitiveNullValue();
				}
				return new IsNullConditionDecision(prevVnaFrame.getTopValue(), ifcmpDecision, fallThroughDecision);
			}
		case Constants.IF_ACMPEQ:
		case Constants.IF_ACMPNE:
			{
				IsNullValue tos = lastFrame.getStackValue(0);
				IsNullValue nextToTos = lastFrame.getStackValue(1);

				boolean tosNull = tos.isDefinitelyNull();
				boolean nextToTosNull = nextToTos.isDefinitelyNull();

				boolean cmpeq = (lastInSourceOpcode == Constants.IF_ACMPEQ);

				// Initially, assume neither branch is feasible.
				IsNullValue ifcmpDecision = null;
				IsNullValue fallThroughDecision = null;
				ValueNumber value;

				if (tosNull && nextToTosNull) {
					// Redundant comparision: both values are null, only one branch is feasible
					value = null; // no value will be replaced - just want to indicate that one of the branches is infeasible
					if (cmpeq)
						ifcmpDecision = IsNullValue.pathSensitiveNullValue();
					else // cmpne
						fallThroughDecision = IsNullValue.pathSensitiveNullValue();
				} else if (tosNull || nextToTosNull) {
					// We have updated information about whichever value is not null;
					// both branches are feasible
					value = prevVnaFrame.getStackValue(tosNull ? 1 : 0);
					ifcmpDecision = cmpeq ? IsNullValue.pathSensitiveNullValue() : IsNullValue.pathSensitiveNonNullValue();
					fallThroughDecision = cmpeq ? IsNullValue.pathSensitiveNonNullValue() : IsNullValue.pathSensitiveNullValue();
				} else if (tos.isDefinitelyNotNull() && !nextToTos.isDefinitelyNotNull()) {
					// learn that nextToTos is definitely non null on one branch
					value = prevVnaFrame.getStackValue(1);
					if (cmpeq) {
						ifcmpDecision = tos;
						fallThroughDecision = nextToTos;
					} else {
						fallThroughDecision = tos;
						ifcmpDecision = nextToTos;
					}
				} else if (!tos.isDefinitelyNotNull() && nextToTos.isDefinitelyNotNull()) {
					// learn that tos is definitely non null on one branch
					value = prevVnaFrame.getStackValue(0);
					if (cmpeq) {
						ifcmpDecision = nextToTos;
						fallThroughDecision = tos;
					} else {
						fallThroughDecision = nextToTos;
						ifcmpDecision = tos;
					}
				} else {
					// No information gained
					break;
				}

				return new IsNullConditionDecision(value, ifcmpDecision, fallThroughDecision);
			}
		default:
			throw new IllegalStateException();
		}

		return null; // no information gained
	}

	/**
	 * Update is-null information at a branch target based on information gained at a
	 * null comparison branch.
	 *
	 * @param origFrame        the original is-null frame at entry to basic block
	 * @param frame            the modified version of the is-null entry frame;
	 *                         null if the entry frame has not been modified yet
	 * @param replaceMe        the ValueNumber in the value number frame at the if comparison
	 *                         whose is-null information will be updated
	 * @param prevVnaFrame     the ValueNumberFrame at the if comparison
	 * @param targetVnaFrame   the ValueNumberFrame at entry to the basic block
	 * @param replacementValue the IsNullValue representing the updated
	 *                         is-null information
	 * @return a modified IsNullValueFrame with updated is-null information
	 */
	private IsNullValueFrame replaceValues(IsNullValueFrame origFrame, IsNullValueFrame frame,
										   ValueNumber replaceMe, ValueNumberFrame prevVnaFrame, ValueNumberFrame targetVnaFrame, 
										  IsNullValue replacementValue) {

		// If required, make a copy of the frame
		frame = modifyFrame(origFrame, frame);

		assert frame.getNumSlots() == targetVnaFrame.getNumSlots();

		// The VNA frame may have more slots than the IsNullValueFrame
		// if it was produced by an IF comparison (whose operand or operands
		// are subsequently popped off the stack).

		final int targetNumSlots = targetVnaFrame.getNumSlots();
		final int prefixNumSlots = Math.min(frame.getNumSlots(), prevVnaFrame.getNumSlots());

		if (trackValueNumbers) {
			AvailableLoad loadForV = prevVnaFrame.getLoad(replaceMe);
			if (DEBUG && loadForV != null) {
				System.out.println("For " + replaceMe + " availableLoad is " + loadForV);
				ValueNumber[] matchingValueNumbers = targetVnaFrame.getAvailableLoad(loadForV);
				if (matchingValueNumbers != null)
					for(ValueNumber v2 : matchingValueNumbers) System.out.println("  matches " + v2);
			}
			if (loadForV != null) {
				ValueNumber[] matchingValueNumbers = targetVnaFrame.getAvailableLoad(loadForV);
				if (matchingValueNumbers != null)
					for(ValueNumber v2 : matchingValueNumbers) if (!replaceMe.equals(v2)) {
						frame.setKnownValue(v2, replacementValue);
						if (DEBUG) System.out.println("For " + loadForV + " switch from " + replaceMe + " to " + v2);
					}
			}	
			frame.setKnownValue(replaceMe, replacementValue);
		}
		// Here's the deal:
		// - "replaceMe" is the value number from the previous frame (at the if branch)
		//   which indicates a value that we have updated is-null information about
		// - in the target value number frame (at entry to the target block),
		//   we find the value number in the stack slot corresponding to the "replaceMe"
		//   value; this is the "corresponding" value
		// - all instances of the "corresponding" value in the target frame have
		//   their is-null information updated to "replacementValue"
		// This should thoroughly make use of the updated information.

		for (int i = 0; i < prefixNumSlots; ++i) {
			if (prevVnaFrame.getValue(i).equals(replaceMe)) {
				ValueNumber corresponding = targetVnaFrame.getValue(i);
				for (int j = 0; j < targetNumSlots; ++j) {
					if (targetVnaFrame.getValue(j).equals(corresponding))
						frame.setValue(j, replacementValue);
				}
			}
		}

		return frame;

	}

	public IsNullValueFrame getFactAtMidEdge(Edge edge) throws DataflowAnalysisException {
		BasicBlock block = isForwards() ? edge.getSource() : edge.getTarget();

		IsNullValueFrame predFact = createFact();
		copy(getResultFact(block), predFact);

		edgeTransfer(edge, predFact);

		IsNullValueFrame result = createFact();
		makeFactTop(result);
		meetInto(predFact, edge, result, false);

		return result;
	}

	/**
	 * Test driver.
	 */
	public static void main(String[] argv) throws Exception {
		if (argv.length != 1) {
			System.err.println("Usage: " + IsNullValueAnalysis.class.getName() + " <class file>");
			System.exit(1);
		}

		DataflowTestDriver<IsNullValueFrame, IsNullValueAnalysis> driver = new DataflowTestDriver<IsNullValueFrame, IsNullValueAnalysis>() {
			@Override
			public Dataflow<IsNullValueFrame, IsNullValueAnalysis> createDataflow(ClassContext classContext, Method method)
					throws CFGBuilderException, DataflowAnalysisException {

				return classContext.getIsNullValueDataflow(method);
			}
		};

		driver.execute(argv[0]);
	}

}

// vim:ts=4