Eliminate Unreachable Basic blocks

Algorithm

• We can delete any blocks that have no predecessors. IMPLEMENTED.
• We can also eliminate blocks that have 1 predecessor and 1 successor and only instruction is an unconditional branch instruction.
• More complex scenario is when we have predecessors but the block is not reachable from ENTRY block. Following algorithm is described by Muchnick:

1. Set again to false
2. Iterate through blocks looking for blocks such that there is no empty path from entry block to those blocks. When such a block is found delete it and adjust predecessor and successor functions to reflect its having been removed. Set again to true.
3. If again go to step 1
4. Adjust the block and related data structures to compact the blocks.

However Muchnick leaves out the description of how to implement 'there is no empty path from entry block to those blocks'.

We can perhaps we a mark and sweep approach. Start from ENTRY block and mark all reachable blocks. Then delete blocks that were left unmarked.