isnullvalueanalysis.java

一个查找java程序里bug的程序的源代码,该程序本身也是java写的,对提高java编程水平很有用

				// Mark all values as having occurred on an exception path
				tmpFact.toExceptionValues();

				// Push the exception value
				tmpFact.pushValue(IsNullValue.nonNullValue());
			} else {
				final int edgeType = edge.getType();
				final BasicBlock sourceBlock = edge.getSource();
				final ValueNumberFrame targetVnaFrame = vnaDataflow.getStartFact(destBlock);
				assert targetVnaFrame != null;

				// Determine if the edge conveys any information about the
				// null/non-null status of operands in the incoming frame.
				if (edgeType == IFCMP_EDGE || edgeType == FALL_THROUGH_EDGE) {
					IsNullConditionDecision decision = getResultFact(edge.getSource()).getDecision();
					if (decision != null) {
						if (!decision.isEdgeFeasible(edgeType)) {
							// The incoming edge is infeasible; just use TOP
							// as the start fact for this block.
							tmpFact = createFact();
							tmpFact.setTop();
						} else if (decision.getValue() != null) {
							// A value has been determined for this edge.
							// Use the value to update the is-null information in
							// the start fact for this block.

							final Location atIf = new Location(sourceBlock.getLastInstruction(), sourceBlock);
							final IsNullValueFrame prevIsNullValueFrame = getFactAtLocation(atIf);
							final ValueNumberFrame prevVnaFrame = vnaDataflow.getFactAtLocation(atIf);

							tmpFact = replaceValues(fact, tmpFact, decision.getValue(), prevVnaFrame,
							        targetVnaFrame, decision.getDecision(edgeType));
						}
					}
				}

				// 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();
					// If we're not sure that the instance is definitely non-null,
					// update the is-null information for the dereferenced value.
					IsNullValue instance = fact.getInstance(firstInDest, methodGen.getConstantPool());
					if (!instance.isDefinitelyNotNull()) {
						ValueNumber replaceMe = vnaFrame.getInstance(firstInDest, methodGen.getConstantPool());
						tmpFact = replaceValues(fact, tmpFact, replaceMe, vnaFrame, targetVnaFrame, IsNullValue.nonNullValue());
					}
				}
			}

			if (tmpFact != null)
				fact = tmpFact;
		}

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

	protected IsNullValue mergeValues(IsNullValueFrame frame, int slot, IsNullValue a, IsNullValue b)
	        throws DataflowAnalysisException {
		return IsNullValue.merge(a, b);
	}

	/**
	 * 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();
		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.flowSensitiveNullValue();
					else // ifnonnull
						fallThroughDecision = IsNullValue.flowSensitiveNullValue();
				} else if (tos.isDefinitelyNotNull()) {
					// Predetermined comparison - one branch is infeasible
					if (ifnull)
						fallThroughDecision = IsNullValue.flowSensitiveNonNullValue();
					else // ifnonnull
						ifcmpDecision = IsNullValue.flowSensitiveNonNullValue();
				} else {
					// As far as we know, both branches feasible
					ifcmpDecision = ifnull ? IsNullValue.flowSensitiveNullValue() : IsNullValue.flowSensitiveNonNullValue();
					fallThroughDecision = ifnull ? IsNullValue.flowSensitiveNonNullValue() : IsNullValue.flowSensitiveNullValue();
				}
				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.flowSensitiveNullValue();
					else // cmpne
						fallThroughDecision = IsNullValue.flowSensitiveNullValue();
				} 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.flowSensitiveNullValue() : IsNullValue.flowSensitiveNonNullValue();
					fallThroughDecision = cmpeq ? IsNullValue.flowSensitiveNonNullValue() : IsNullValue.flowSensitiveNullValue();
				} 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());

		// 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;

	}

	/**
	 * 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>() {
			public Dataflow<IsNullValueFrame, IsNullValueAnalysis> createDataflow(ClassContext classContext, Method method)
			        throws CFGBuilderException, DataflowAnalysisException {

				return classContext.getIsNullValueDataflow(method);
			}
		};

		driver.execute(argv[0]);
	}

}

// vim:ts=4