Re: How do I modify SSA and copy basic blocks?
On Thu, Apr 25, 2013 at 8:28 PM, Steve Ellcey wrote: > On Thu, 2013-04-25 at 09:53 +0200, Richard Biener wrote: > >> We have gimple_duplicate_sese_region for this. It may be not perfect though. >> Eventually it should be changed to handle SEME regions as well and all >> loop copying / versioning code should use it as well (though I don't think >> any of the loop copying / versioning code handles multiple exits). >> >> I've slowly started to move us in this direction by removing duplicate >> functionality >> in the compiler as I come along it ... >> >> Richard. > > One thing I have noticed with this routine is that I am trying to call > gimple_duplicate_sese_region before the various loop optimizations and > before the loop information is all set up (not sure if that is good or > bad, right now it just is). So I died when calling set_loop_copy. I > put that call and the other loop uses in an 'if (loop)' block to make > that assertion stop and I was then able to copy one (SEME) block with > this routine. When I tried to copy a second block with a second call, > it died in iterate_fix_dominators. I tried removing all the dominator > information after creating my first new block hoping it would correctly > regenerate everything before doing the second block but that didn't seem > to work. I think you need to init/finalize SSA updating, but I've never seen the dominator fixup issue. Maybe simply call loop_optimizer_init () in your pass (well, no longer needed since I just committed the patch that should make loops available everywhere). Richard. > Steve Ellcey > sell...@imgtec.com > >
Re: How do I modify SSA and copy basic blocks?
On Thu, 2013-04-25 at 09:53 +0200, Richard Biener wrote: > We have gimple_duplicate_sese_region for this. It may be not perfect though. > Eventually it should be changed to handle SEME regions as well and all > loop copying / versioning code should use it as well (though I don't think > any of the loop copying / versioning code handles multiple exits). > > I've slowly started to move us in this direction by removing duplicate > functionality > in the compiler as I come along it ... > > Richard. One thing I have noticed with this routine is that I am trying to call gimple_duplicate_sese_region before the various loop optimizations and before the loop information is all set up (not sure if that is good or bad, right now it just is). So I died when calling set_loop_copy. I put that call and the other loop uses in an 'if (loop)' block to make that assertion stop and I was then able to copy one (SEME) block with this routine. When I tried to copy a second block with a second call, it died in iterate_fix_dominators. I tried removing all the dominator information after creating my first new block hoping it would correctly regenerate everything before doing the second block but that didn't seem to work. Steve Ellcey sell...@imgtec.com
Re: How do I modify SSA and copy basic blocks?
On Thu, 2013-04-25 at 09:53 +0200, Richard Biener wrote: > > 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. > > We have gimple_duplicate_sese_region for this. It may be not perfect though. > Eventually it should be changed to handle SEME regions as well and all > loop copying / versioning code should use it as well (though I don't think > any of the loop copying / versioning code handles multiple exits). > > I've slowly started to move us in this direction by removing duplicate > functionality > in the compiler as I come along it ... > > Richard. This looks interesting. If it handled SEME regions I think I could use it because any single block by itself is going to be an SEME region, right? I notice the routine does not update the SSA web. Is there a reason for that? It looks like copy_loop_headers calls update_ssa after it calls gimple_duplicate_sese_region (the only use of gimple_duplicate_sese_region that I see). Unfortunately, at least some of the blocks I want to copy have multiple exit edges where an SSA variable defined in that block is needed on each of the exit edges from the block. Do you know what bad things will happen if I call this with a block that is SEME instead of SESE? Is there anyway (even if it was a hack) that I could compensate for it by regenerating some of the information, i.e. freeing the dominator information so it gets recalculated from scratch or something like that? Steve Ellcey sell...@imgtec.com
Re: How do I modify SSA and copy basic blocks?
Hi, > On Tue, 2013-04-23 at 15:24 -0600, Jeff Law wrote: > > > Well, you have to copy the blocks, adjust the edges and rewrite the SSA > > graph. I'd use duplicate_block to help. > > > > You really want to look at tree-ssa-threadupdate.c. There's a nice big > > block comment which gives the high level view of what needs to happen > > when you copy a block for this kind of optimization. Feel free to > > ignore the implementation which has to be fairly efficient when there's > > a large number of edges to update. > > > > Jeff > > 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. I'd suggest looking at gimple_duplicate_sese_region in tree-cfg.c. It does not do exactly what you need, but it deals with a somewhat similar situation, Zdenek
Re: How do I modify SSA and copy basic blocks?
On Thu, Apr 25, 2013 at 5:03 AM, Jeff Law wrote: > 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. We have gimple_duplicate_sese_region for this. It may be not perfect though. Eventually it should be changed to handle SEME regions as well and all loop copying / versioning code should use it as well (though I don't think any of the loop copying / versioning code handles multiple exits). I've slowly started to move us in this direction by removing duplicate functionality in the compiler as I come along it ... Richard. > 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: >> >>: >># s_1 = PHI >># t_3 = PHI <0(2), t_2(7)> >># c_4 = PHI >>if (c_4 != 0) >> goto ; >>else >> goto ; >> >> 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 > >
Re: How do I modify SSA and copy basic blocks?
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: : # s_1 = PHI # t_3 = PHI <0(2), t_2(7)> # c_4 = PHI if (c_4 != 0) goto ; else goto ; 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
Re: How do I modify SSA and copy basic blocks?
On Wed, 2013-04-24 at 15:54 -0700, Steve Ellcey wrote: > > /* 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; > } Following up to my own reply, I tried adding: update_ssa (TODO_update_ssa); to fix up the SSA code but that did not help, I tried it both with and without the calls to update_destination_phis & remove_phi_args. Steve Ellcey sell...@imgtec.com
Re: How do I modify SSA and copy basic blocks?
On Wed, 2013-04-24 at 14:31 -0600, Jeff Law wrote: > On 04/24/2013 11:38 AM, Steve Ellcey wrote: > 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) 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: /* 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. The block I am trying to copy (based on my original example) is: : # s_1 = PHI # t_3 = PHI <0(2), t_2(7)> # c_4 = PHI if (c_4 != 0) goto ; else goto ; 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. Steve Ellcey sell...@mips.com
Re: How do I modify SSA and copy basic blocks?
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
Re: How do I modify SSA and copy basic blocks?
On Tue, 2013-04-23 at 15:24 -0600, Jeff Law wrote: > Well, you have to copy the blocks, adjust the edges and rewrite the SSA > graph. I'd use duplicate_block to help. > > You really want to look at tree-ssa-threadupdate.c. There's a nice big > block comment which gives the high level view of what needs to happen > when you copy a block for this kind of optimization. Feel free to > ignore the implementation which has to be fairly efficient when there's > a large number of edges to update. > > Jeff 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); 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? 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. 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) 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? Steve Ellcey sell...@imgtec.com
Re: How do I modify SSA and copy basic blocks?
On 04/23/2013 02:43 PM, Steve Ellcey wrote: I think I have code that finds the path that I am interested in, but when I try to use copy_bbs to copy the basic blocks in order to create my new path, I get segfaults. I was wondering if anyone could help me understand what I need to do, in addition to calling copy_bbs, to create my new path and keep the various ssa and cfg information up to date, either by modifying it or by blowing it away and regenerating it, I am not worried about compilation speed at this point so if regenerating all the SSA/cfg data is easiest, I am happy to do that. Well, you have to copy the blocks, adjust the edges and rewrite the SSA graph. I'd use duplicate_block to help. You really want to look at tree-ssa-threadupdate.c. There's a nice big block comment which gives the high level view of what needs to happen when you copy a block for this kind of optimization. Feel free to ignore the implementation which has to be fairly efficient when there's a large number of edges to update. Jeff