Maintaining CFG up to Date

Important task is to keep both control flow graph and profile up-to-date with the instruction stream during optimization passes. Reconstruction of control flow graph after each pass is not an option, as it is too expensive and we lose profile information.

At the moment, the basic block boundaries are maintained transparently during emitting instruction, so rarely there is need to move them manually (such as in case someone wants to output instruction outside basic block explicitly). Each instruction has defined BLOCK_FOR_INSN value that represents pointer to the basic block owning it, so the basic block list may be better viewed as integral part of instruction chain, than structure built on the top of it.

Updating of edges is not transparent and optimization pass is required to do that manually. However only few cases occur in practice. Commonly the optimization pass simplifies the instruction possibly eliminating some edge. This may happen by simplifying the conditional jump into unconditional, but also by simplifying possibly trapping instruction to non-trapping while compiling Java. The pass may call purge_dead_edges on given basic block to remove unneeded edges, if any.

Other common scenario is redirection of branch instructions, but this is best modeled as redirection of edges in the control flow graph and thus use of redirect_edge_and_branch is preferred over more low level functions, such as redirect_jump that operate on RTL chain only.

Last common case is inserting control flow instruction into middle of basic block. The find_sub_basic_blocks may be used to split existing basic block and add necessary edges, or split_block may be used when instruction in middle of basic block wants to become target of branch instruction.

For global optimizer, a common operation is to split edges in the flow graph and insert instruction to them. This can be easily done via function commit_insn_to_edge that emits instruction ``to the edge'' caching it for later commit_edge_insertions call that will care creation of new basic block where needed and flushing the instruction to actual instruction stream.

While debugging the optimization pass, an verify_flow_info function may be useful to find bugs in the control flow graph updating code.