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
How do I modify SSA and copy basic blocks?
I decided to take a crack at the coremark optimization (PR 54742) for switch
statements. Since I couldn't figure out the existing jump threading
optimization enough to extend it properly, I decided to try a plugin
optimization pass just for this case and see if I could get that to work.
The basic idea is to find a path from where a variable is assigned a constant
value to where that variable is used in a switch statement. Then I want to
duplicate the blocks in that path (thus removing any alternative entry points
into the path that may give the variable a different value) and plug it into
the cfg.
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.
Attached is my plugin as it exists right now and a simple test case using a
switch statement. I am not including the actual coremark code because it is
copyrighted. If you run my example you will see output showing 4 places where
I think I can do my optimization. For example we assign t the value of 0 in
block 2 and from there we go to block 8 and (possibly) to block 3 where we have
our switch statement.
So what I try to do is copy blocks 8 and 3 and change the edge from block
2 to block 8 to go from block 2 to my new copy of block 8 which should
then go to the new copy of block 3. After this we should be able to
optimize the new copy of block 3 to finish with a goto to the 'case 0'
label instead of with a switch/goto.
If you remove the '#if 0' in my code where I comment out the call to
copy_bbs, you will get a seg fault, this is the code that I need help
with. For example, If I copy block 8 and block 3, and there is an edge
from 8 to 3, does copy_bbs automatically create a new edge pointing from the
copy of block 8 to block 3 and replace that in the copied blocks? I think it
does, but I am not sure.
Steve Ellcey
sell...@imgtec.com
Output from the test program using my new optimization phase.
In plugin, registering new pass
Block 2 assigns variable t a constant value of 0
Basic blocks (leading from basic block 2 to switch) are:
8
3
Block 4 assigns variable t a constant value of 1
Basic blocks (leading from basic block 4 to switch) are:
7
8
3
Block 5 assigns variable t a constant value of 2
Basic blocks (leading from basic block 5 to switch) are:
7
8
3
Block 6 assigns variable t a constant value of 1
Basic blocks (leading from basic block 6 to switch) are:
7
8
3
/* This file implements an optimization where, when a variable is set
to a constant value and there is a path that leads from this definition
to a switch statement that uses that variable as its controlling expression
we duplicate the blocks on this path and change the switch goto to a
direct goto to the label of the switch block that control would goto based
on the value of the variable. */
#include
#include
#include
#include
#include
#include
#include
#include
#include
int plugin_is_GPL_compatible;
/* Helper function for find_path, visited_bbs is used to make sure we don't
fall into an infinite loop. */
static int
find_path_1(basic_block start_bb, basic_block end_bb, struct pointer_set_t *visited_bbs)
{
edge_iterator ei;
edge e;
if (start_bb == end_bb) return 1;
if (!pointer_set_insert (visited_bbs, start_bb))
{
FOR_EACH_EDGE (e, ei, start_bb->succs)
if (find_path_1 (e->dest, end_bb, visited_bbs)) return 1;
}
return 0;
}
/* Return 1 if there is a path from start_bb to end_bb and 0 if there
is not. */
static int
find_path(basic_block start_bb, basic_block end_bb)
{
edge_iterator ei;
edge e;
struct pointer_set_t *visited_bbs;
int p = 0;
if (start_bb == end_bb) return 1;
visited_bbs = pointer_set_create ();
if (!pointer_set_insert (visited_bbs, start_bb))
{
FOR_EACH_EDGE (e, ei, start_bb->succs)
if (find_path_1 (e->dest, end_bb, visited_bbs))
{
p = 1;
break;
}
}
pointer_set_destroy (visited_bbs);
return p;
}
/* bbs_list[0] is the block with the switch statement,
bbs_list[n-1] is the block where the switch statement variable is assigned
a constant value,
The entries in between make a (reverse) path between the two.
We don't want to copy bb_list[n-1], we want to leave that alone and
copy bb_list[n-2]...bb_list[0], and change the edge from bb_list[n-1]
to bb_list[n-2] to point to the copy of bb_list[n-2]. Then we
should change the switch in bb_list[0] to a simple goto, but maybe we
can let a later optimization phase (constant propogati
