How do I modify SSA and copy basic blocks?

[Jeff Law]

On 04/24/2013 11:38 AM, Steve Ellcey wrote:
>
> I think I understand the high level work, it is mapping that hight level
> description to the low level calls that I am having trouble with.  Lets
> say I have basic blocks A, B, and C, and edges from A to B and B to C.
> There may also be other edges leading into B and C that I do not want to
> change.  Now I want to make a copy of B (B') and change the A->B edge to
> be A->B'.
>
> I think this would be:
>
> 	B_prime = duplicate_block (B, find_edge (A, B), B);
Just do duplicate_block (B, NULL, NULL)

Then I'd remove the switch statement and the outgoing edges from B' 
except the edge B'->C.

Then I'd fixup the PHIs in C.  That's update_destination_phis.


Then you need to wire up A->B'.  If B' has PHIs, then you'll have to fix 
those as well as any PHIs in C.  Note that PHIs in B just lost an 
argument, but that'll be handled automatically when you redirect the 
edge from A->B to A->B'.

I think that's the proper sequencing (and I certainly had to read the 
code, it's been a long time since I looked at it in this level of detail)




>
> This leads to several questions.  Why does it matter what basic block
> I put this new block 'after' (the 3rd arg to duplicate_block).  Do all
> blocks have at least one edge leading out of them or will a block 'fall'
> into the next block if there is no succ edges?  Or does 'after' just
> affect where the block shows up in debug tree listings?
The AFTER argument shouldn't matter.  All edges are explicit.  If a 
block has a fall-thru path, it'll have an edge and the edge should be 
marked with EDGE_FALLTHRU.

>
> Looking at the code in tree-ssa-threadupdate.c and trans-mem.c I am
> guessing I need to call initialize_original_copy_tables before calling
> duplicate_block and free_original_copy_tables after it, right?  I am
> also assuming I can do a series of duplicate_block calls between the
> initialize and free calls if I need to.
Yes, you'll need to initialize & free them and you can do as many 
duplicate_block calls as you'd like.

>
> tree-ssa-threadupdate.c has a static routine called
> update_destination_phis to update the phi's in a new block, I made a
> copy of this routine and used it in my code to try and update the phi
> nodes in my new block B'.  I am not sure if that is sufficient or not
> for updating the phi nodes in my new block.  Do I also need to do
> something to adjust the phi nodes in the block I copied (B)
In your example, it's updating the PHIs in block C.  When you copy B, 
any successor nodes with PHIs will now have PHIs with an uninitialized 
argument.  That routine finds the PHI argument associated with the edge 
B'->C and initializes its value to be the same as the PHI arg associated 
with the edge B->C.



>
> So I basically am duplicating blocks with:
>
> initialize_original_copy_tables ();
> B_prime = duplicate_block (B, find_edge (A, B), A);
> update_destination_phis (B, B_prime);
> free_original_copy_tables ();
>
> But my code segfaults in nearest_common_dominator, called by update_ssa
> after my pass has changed the code.  I think I need to do more to fix
> any PHI nodes in B and B' but I am not sure what.  I also notice that
> copy_bbs in cfghooks (which calls duplicate_block) has calls to
> get_immediate_dominator and set_immediate_dominator, maybe I need to
> copy that code as well?
Make sure you call free_dominance_info.  THe code might be looking at 
cached dominance info and getting confused as hell.  Threading jumps 
like this mucks up the dominance info beyond easy repair.



jeff