bettercfgbuilder2.java

A static analysis tool to find bugs in Java programs

							while (i.hasNext()) {
								Target target = i.next();
								subroutine.addEdgeAndExplore(basicBlock, target.getTargetInstruction(),
										target.getEdgeType());
							}
						}
					}
				}

				if (!endOfBasicBlock) {
					InstructionHandle next = handle.getNext();
					if (next == null)
						throw new CFGBuilderException("Control falls off end of method: " + handle);

					// Is the next instruction a control merge or a PEI?
					if (isMerge(next) || isPEI(next)) {
						subroutine.addEdgeAndExplore(basicBlock, next, FALL_THROUGH_EDGE);
						endOfBasicBlock = true;
					} else {
						// Basic block continues
						handle = next;
					}
				}

			} while (!endOfBasicBlock);
		}
	}

	/**
	 * Add exception edges for given instruction.
	 *
	 * @param subroutine the subroutine containing the instruction
	 * @param pei        the instruction which throws an exception
	 * @param etb        the exception thrower block (ETB) for the instruction
	 */
	private void handleExceptions(Subroutine subroutine, InstructionHandle pei, BasicBlock etb) {
		etb.setExceptionThrower(pei);

		// Remember whether or not a universal exception handler
		// is reachable.  If so, then we know that exceptions raised
		// at this instruction cannot propagate out of the method.
		boolean sawUniversalExceptionHandler = false;

		List<CodeExceptionGen> exceptionHandlerList = exceptionHandlerMap.getHandlerList(pei);
		if (exceptionHandlerList != null) {
			for (CodeExceptionGen exceptionHandler : exceptionHandlerList) {
				InstructionHandle handlerStart = exceptionHandler.getHandlerPC();
				subroutine.addEdgeAndExplore(etb, handlerStart, HANDLED_EXCEPTION_EDGE);

				if (Hierarchy.isUniversalExceptionHandler(exceptionHandler.getCatchType()))
					sawUniversalExceptionHandler = true;
			}
		}

		// If required, mark this block as throwing an unhandled exception.
		// For now, we assume that if there is no reachable handler that handles
		// ANY exception type, then the exception can be thrown out of the method.
		if (!sawUniversalExceptionHandler) {
			if (DEBUG) System.out.println("Adding unhandled exception edge from " + pei);
			subroutine.setUnhandledExceptionBlock(etb);
		}
	}

	/**
	 * Return whether or not the given instruction can throw exceptions.
	 *
	 * @param handle the instruction
	 * @return true if the instruction can throw an exception, false otherwise
	 */
	private boolean isPEI(InstructionHandle handle) {
		Instruction ins = handle.getInstruction();

		if (!(ins instanceof ExceptionThrower))
			return false;

		if (ins instanceof NEW) return false;
		// if (ins instanceof ATHROW) return false;
		if (ins instanceof GETSTATIC) return false;
		if (ins instanceof PUTSTATIC) return false;
		if (ins instanceof ReturnInstruction) return false;
		if (ins instanceof INSTANCEOF) return false;
		// if (ins instanceof INVOKESTATIC) return false;
		if (ins instanceof MONITORENTER) return false;
		if (ins instanceof MONITOREXIT) return false;
		return true;

	}
	/**
	 * Determine whether or not the given instruction is a control flow merge.
	 *
	 * @param handle the instruction
	 * @return true if the instruction is a control merge, false otherwise
	 */
	private static boolean isMerge(InstructionHandle handle) {
		if (handle.hasTargeters()) {
			// Check all targeters of this handle to see if any
			// of them are branches.  If so, the instruction is a merge.
			InstructionTargeter[] targeterList = handle.getTargeters();
			for (InstructionTargeter targeter : targeterList) {
				if (targeter instanceof BranchInstruction)
					return true;
			}
		}
		return false;
	}

	/**
	 * Inline all JSR subroutines into the top-level subroutine.
	 * This produces a complete CFG for the entire method, in which
	 * all JSR subroutines are inlined.
	 *
	 * @return the CFG for the method
	 */
	private CFG inlineAll() throws CFGBuilderException {
		CFG result = new CFG();

		Context rootContext = new Context(null, topLevelSubroutine, result);
		rootContext.mapBlock(topLevelSubroutine.getEntry(), result.getEntry());
		rootContext.mapBlock(topLevelSubroutine.getExit(), result.getExit());

		BasicBlock resultStartBlock = rootContext.getBlock(topLevelSubroutine.getStartBlock());
		result.createEdge(result.getEntry(), resultStartBlock, START_EDGE);

		inline(rootContext);

		return result;
	}

	/**
	 * Inline a subroutine into a calling context.
	 *
	 * @param context the Context
	 */
	public void inline(Context context) throws CFGBuilderException {

		CFG result = context.getResult();

		// Check to ensure we're not trying to inline something that is recursive
		context.checkForRecursion();

		Subroutine subroutine = context.getSubroutine();
		CFG subCFG = subroutine.getCFG();

		while (context.hasMoreWork()) {
			BasicBlock subBlock = context.nextItem();
			BasicBlock resultBlock = context.getBlock(subBlock);

			// Mark blocks which are in JSR subroutines
			resultBlock.setInJSRSubroutine(context.getCaller() != null);

			// Copy instructions into the result block
			BasicBlock.InstructionIterator insIter = subBlock.instructionIterator();
			while (insIter.hasNext()) {
				InstructionHandle handle = insIter.next();
				resultBlock.addInstruction(handle);
			}

			// Set exception thrower status
			if (subBlock.isExceptionThrower())
				resultBlock.setExceptionThrower(subBlock.getExceptionThrower());

			// Set exception handler status
			if (subBlock.isExceptionHandler())
				resultBlock.setExceptionGen(subBlock.getExceptionGen());

			// Add control edges (including inlining JSR subroutines)
			Iterator<Edge> edgeIter = subCFG.outgoingEdgeIterator(subBlock);
			while (edgeIter.hasNext()) {
				Edge edge = edgeIter.next();
				int edgeType = edge.getType();

				if (edgeType == JSR_EDGE) {
					// Inline a JSR subroutine...

					// Create a new Context
					InstructionHandle jsrHandle = subBlock.getLastInstruction();
					JsrInstruction jsr = (JsrInstruction) jsrHandle.getInstruction();
					Subroutine jsrSub = jsrSubroutineMap.get(jsr.getTarget());
					Context jsrContext = new Context(context, jsrSub, context.getResult());

					// The start block in the JSR subroutine maps to the first
					// inlined block in the result CFG.
					BasicBlock resultJSRStartBlock = jsrContext.getBlock(jsrSub.getStartBlock());
					result.createEdge(resultBlock, resultJSRStartBlock, GOTO_EDGE);

					// The exit block in the JSR subroutine maps to the result block
					// corresponding to the instruction following the JSR.
					// (I.e., that is where control returns after the execution of
					// the JSR subroutine.)
					BasicBlock subJSRSuccessorBlock = subroutine.getBlock(jsrHandle.getNext());
					BasicBlock resultJSRSuccessorBlock = context.getBlock(subJSRSuccessorBlock);
					jsrContext.mapBlock(jsrSub.getExit(), resultJSRSuccessorBlock);

					// Inline the JSR subroutine
					inline(jsrContext);
				} else {
					// Ordinary control edge
					BasicBlock resultTarget = context.getBlock(edge.getTarget());
					result.createEdge(resultBlock, resultTarget, edge.getType());
				}
			}

			// Add control edges for escape targets
			Iterator<EscapeTarget> escapeTargetIter = subroutine.escapeTargetIterator(subBlock);
			while (escapeTargetIter.hasNext()) {
				EscapeTarget escapeTarget = escapeTargetIter.next();
				InstructionHandle targetInstruction = escapeTarget.getTarget();

				// Look for the calling context which has the target instruction
				Context caller = context.getCaller();
				while (caller != null) {
					if (caller.getSubroutine().containsInstruction(targetInstruction))
						break;
					caller = caller.getCaller();
				}

				if (caller == null)
					throw new CFGBuilderException("Unknown caller for escape target " + targetInstruction +
							" referenced by " + context.getSubroutine().getStartInstruction());

				// Find result block in caller
				BasicBlock subCallerTargetBlock = caller.getSubroutine().getBlock(targetInstruction);
				BasicBlock resultCallerTargetBlock = caller.getBlock(subCallerTargetBlock);

				// Add an edge to caller context
				result.createEdge(resultBlock, resultCallerTargetBlock, escapeTarget.getEdgeType());
			}

			// If the block returns from the method, add a return edge
			if (subroutine.isReturnBlock(subBlock)) {
				result.createEdge(resultBlock, result.getExit(), RETURN_EDGE);
			}

			// If the block calls System.exit(), add an exit edge
			if (subroutine.isExitBlock(subBlock)) {
				result.createEdge(resultBlock, result.getExit(), EXIT_EDGE);
			}

			// If the block throws an unhandled exception, add an unhandled
			// exception edge
			if (subroutine.isUnhandledExceptionBlock(subBlock)) {
				result.createEdge(resultBlock, result.getExit(), UNHANDLED_EXCEPTION_EDGE);
			}

		}

/*
		while (blocks are left) {

			get block from subroutine
			get corresponding block from result
			copy instructions into result block

			if (block terminated by JSR) {
				get JSR subroutine
				create new context
				create GOTO edge from current result block to start block of new inlined context
				map subroutine exit block to result JSR successor block
				inline (new context, result)
			} else {
				for each outgoing edge {
					map each target to result blocks (add block to to work list if needed)
					add edges to result
				}

				for each outgoing escape target {
					add edges into blocks in outer contexts (adding those blocks to outer work list if needed)
				}

				if (block returns) {
					add return edge from result block to result CFG exit block
				}

				if (block calls System.exit()) {
					add exit edge from result block to result CFG exit block
				}

				if (block throws unhandled exception) {
					add unhandled exception edge from result block to result CFG exit block
				}
			}

		}
*/
	}

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

		String methodName = SystemProperties.getProperty("cfgbuilder.method");

		JavaClass jclass = new ClassParser(argv[0]).parse();
		ClassGen classGen = new ClassGen(jclass);

		Method[] methodList = jclass.getMethods();
		for (Method method : methodList) {
			if (method.isAbstract() || method.isNative())
				continue;

			if (methodName != null && !method.getName().equals(methodName))
				continue;

			MethodGen methodGen = new MethodGen(method, jclass.getClassName(), classGen.getConstantPool());

			CFGBuilder cfgBuilder = new BetterCFGBuilder2(methodGen);
			cfgBuilder.build();

			CFG cfg = cfgBuilder.getCFG();

			CFGPrinter cfgPrinter = new CFGPrinter(cfg);
			System.out.println("---------------------------------------------------------------------");
			System.out.println("Method: " + SignatureConverter.convertMethodSignature(methodGen));
			System.out.println("---------------------------------------------------------------------");
			cfgPrinter.print(System.out);
		}
	}

}

// vim:ts=4