Requesting ideas for basic block reordering+debugging.

[Jason Eckhardt]

I'm seeking ideas on how to handle debugging information when basic-block
reordering is enabled. Below is a short overview of operation which shows
how the basic blocks can change. I've looked at find_loop_tree_blocks() and
unroll_tree_blocks() (used by the unrolling code) which use identify_blocks()
and reorder_blocks() respectively. Could these functions be useful as
a starting point?
A very good explanation of how the lexical blocks and basic blocks are
related and how the debugging information is tied to it all would be
helpful as well.

>Overview of operation:
>The main entry is reorder_basic_blocks.  It first finds the natural
>loops.  Then if there is no profiling information it estimates
>conditional branches.  Two types are currently predicted:
> if a condjump in a loop has a successor that is not part of
>    the natural loop, predict it not taken.
> if a condition is testing an integer is less than zero, predict it
>    not taken.
> there are some other possibilities mentioned in Larus's paper (I'll be
> adding some of these to predict.c).
>
>Call make_reorder_chain on block 0:
> Look at probabilities to determine which condjump path is most likely
> Each block has added info pointed to by aux
> Call chain_reorder_blocks on most likely edge
> Recurse on edge destination
> When this returns after following a chain of blocks as far as it can go
> (see ascii figure below)
>      call chain_reorder_blocks on other successors
>
>chain_reorder_blocks chains blocks as it encounters them.
> First it determines what type of destination block and condition it has.
> The possibilities are:
>                        Predicted:      Becomes:
>1 if() then{} else{}  then              if() then{} else{go X}
>                                        Y:{}... X:{...;go Y}
>2 if() then{} else{}  else              if() then{go X} else{}
>                                        Y:{}... X:{...}
>3 if() then{}         then              if() then {}
>4 if() then{}        not then           if() then{go X} 
>                                        Y:{}... X:{...;go Y}
>The first code block handles adding {go X} X: for 2 and 4
>The second code block handles adding go Y for 4 as a then without an
>else will have a fall-through edge
>The third code block handles adding {go Y} for 1
>The fourth code block handles adding a branch to a visited successor
> whenever we reach the end of a chain (e.g. 8 - 4 below)
>
>The blocks are handled as they are seen.  If insns were only 
>accessible within a basic block so labels/jumps could be added to the
>beginning/end only of a basic block then the above would be easier
>than what the code does.  What it does is try and insure the addition only
>effects that block and does not change the insn chaining in a possibly
>already reordered block.  These sections of code are demarcated with
>the BEGIN/END splice comments.  As one can probably imagine, most of
>the errors have concerned this.  
>
>skip_insns_between_blocks tries to skip over those pesky insns that
>can appear between blocks.
>
>                        0      ascii representation indicating
>                      /   \    a possible order that blocks would
>                     1     9   be visited and placed in
>                   /  \   / \
>                  2    5 10 11
>                 / \  / \    |
>                4   3 6  7  12
>                \        |   |
>                 --------8  13
>