AdvancedControlFlow

Control flow with exceptions and unconditional jumps

The method is entered with a context that is assumed a baseline for the method. The context can never get broader than this within this method. Complications can arise in cases where parts of the method are executed in more narrow contexts.

Only the following three cases may modify the context for following blocks:

• If/switch instructions depending on variational values
• INVOKE* instructions throwing a VException
• A statement is the jump target from multiple sources with potentially different contexts (cfg merge)

There are many more instructions that cause control-flow jumps, including ATHROW, GOTO, and all kinds of operations that throw exceptions (including non-VException exceptions in INVOKE* instructions). That is the block structure is usually smaller than the number of blocks that can have different contexts. Therefore, we also don't need so many context variables; in fact multiple blocks can share a single variable. We only need to make sure that we have executed all blocks in the end that still have satisfiable conditions.

The challenge is now to mix variational jumps with nonvariational jumps and exceptions.

VBlocks

We introduce the concept of a VBlock that may consist of multiple blocks. A VBlock has a context, a single entry point (i.e., a unique first instruction), and potentially multiple last blocks. There may be multiple control-flow decisions between the blocks within a VBlock, but none of them may modify the context of the execution. That is, they either must be GOTO or ATHROW instructions or IF instructions on plain values. A block context variable is associated with each VBlock.

Every last block within a VBlock must jump to the next VBlock after updating the current and next VBlock's conditions. If a block ends with a variational decision between two VBlocks, it must update their conditions and jump to the one further back (see block-ordering below). If the next VBlock starts immediately after the current instruction, no jump is necessary, otherwise, we jump to the next VBlock.

The first instruction of a VBlock determines whether the VBlock can be skipped.

Within a VBlock, we can leave elements on the stack between blocks. Only for jumps between VBlocks we need to store extra stack values in variables (see balanced stack).

We need to perform a dataflow analysis to determine which blocks can be grouped into a VBlock.

Exception handlers

Exception handlers are special blocks, called EBlocks. An EBlock can consist of multiple blocks and can have only a single entry point, just as VBlocks. An EBlock always starts with an exception value on the stack.

An EBlock has a condition variable that is not managed by the general control flow mechanism. At the beginning of each VBlock that has any blocks for which the EBlock is an exception handler, the EBlock's condition variable is initialized to the VBlock's condition. That means if an exception occurs, the EBlock's condition is already correctly initialized and always has a satisfiable condition.

To simulate throwing an exception under a restricted condition (when handling VPartialException and VException from a method call), we create a new VBlock for the possible targets. The VBlock (which is part of the normal control flow and checked for satisfiable conditions) will load the exception from a special variable, set the corresponding EBlock's condition variable to the current condition and jump to the EBlock.

Notes

Both variational if instructions and INVOKE instructions can only happen at the end of a VBlock. Variational INVOKE instructions cannot occur with any elements remaining on the stack.