How do I modify SSA and copy basic blocks?

[Jeff Law]

On 04/24/2013 04:54 PM, Steve Ellcey wrote:
>
> I am still having trouble with this and with figuring out how to
> straighten out my PHI nodes.  I have decided to try a slightly different
> tack and see if I could create a routine that would do a generic basic
> block copy, handling all the needed bookkeeping internally and fixing
> all the PHI nodes after the copy.  I am trying to create a slow but
> dependable and easy to use function and would consider completely
> regenerating all the PHI information if that was the easiest thing to
> do.  Here is what I have so far:
Interesting you should mention this; one of the things I really want to 
get back to is a more generic mechanism to copy block regions.

Threading is really just path isolation by copying and some 
equivalency/redundancy elimination enabled by the path isolation.

We're missing a lot of threading opportunities because the current 
method for copying blocks is so limited.  There's finally some good 
literature on this stuff, both in terms of finding the redundancies that 
lead to useful optimization and in terms of identifying regions of 
blocks that need to be copied.  All the nonsense we do needs to be 
reformulated using better known methods.

>
>
> /* Copy the basic block that is the destination block of orig_edge, then
>     modify/replace the edge in orig_edge->src basic block with a new edge
>     that goes to the new block.  Fix up any PHI nodes that may need to be
>     updated.  Remove the dominance info since it may have been messed up.  */
>
> edge
> duplicate_succ_block (edge orig_edge)
> {
>    edge new_edge;
>    basic_block orig_block, new_block;
>
>    initialize_original_copy_tables ();
>    orig_block = orig_edge->dest;
>    fprintf(stderr, "Duplicating block %d\n", orig_block->index);
>    new_block = duplicate_block (orig_block, NULL, NULL);
>    update_destination_phis (orig_block, new_block);
>    new_edge = redirect_edge_and_branch (orig_edge, new_block);
>    remove_phi_args (orig_edge);
>    free_dominance_info (CDI_DOMINATORS);
>    free_original_copy_tables ();
>    return new_edge;
> }
>
> When I use this to copy a block I get a failure from verify_ssa.
Well, with that structure you need to update PHIs at the destination of 
every outgoing edge from new_block.  That's one of the reasons you want 
to delete the control statement and dead edges in the copy -- that 
leaves you just updating the single successor of new_block.

You don't mention why verify_ssa fails.  I'd hazard a guess you've got a 
use not dominated by its set.   It'll be important to know where the use 
occurs and where the dominating set is supposed to be.  Presumably you 
call into update_ssa or whatever it's called these days before trying to 
verify_ssa?


>
> The block I am trying to copy (based on my original example) is:
>
>    <bb 8>:
>    # s_1 = PHI <s_6(D)(2), s_8(7)>
>    # t_3 = PHI <0(2), t_2(7)>
>    # c_4 = PHI <c_7(2), c_9(7)>
>    if (c_4 != 0)
>      goto <bb 3>;
>    else
>      goto <bb 9>;
>
> There are two edges leading here (from block 2 and block 7) and I want
> to change the 2->8 edge to be a 2->8_prime edge where 8_prime is my new
> basic block.  That obviously affects the PHI nodes in both block 8 and
> the new 8_prime block.  I don't think any other PHI's are affected in
> this case, but obviously, I would like my routine to work on any block I
> want to copy even if it does affect PHI nodes in successor blocks.
You have to update the PHIs in bb3 & bb9.  You want to copy the PHI arg 
associated with 8->3 for the 8'->3 edge, similarly for for PHI args 
associated with the 8->9 edge to the 8'->9 edge.  See copy_phi_args.

jeff