Attacking quadratic behaviors associated with SWITCH_EXPR

Attacking quadratic behaviors associated with SWITCH_EXPR

[Kazu Hirata]

Hi,

Some operations dealing with SWITCH_EXPR are known to be expensive.

Let me start out with a list of common operations with SWITCH_EXPR
along with their costs.

Let n is the the number of case labels in a SWITCH_EXPR.  Here are
summary of "given A, find B" operations related to SWITCH_EXPR.

INTEGER_CST -> CASE_LABEL_EXPR
  O(log n).  Implemented in find_case_label_for_value.

CASE_LABEL_EXPR -> LABEL_DECL
  O(1).  This is a primitive operation.

CASE_LABEL_EXPR -> basic_block (via LABEL_DECL)
  O(1).  Implemented in label_to_block.

CASE_LABEL_EXPR -> edge (via LABEL_DECL and basic_block)
  O(n).  Performed in find_taken_edge_switch_expr.
  Implemented as label_to_block, followed by find_edge

edge -> CASE_LABEL_EXPR
  O(n).  Performed in tree_redirect_edge_and_branch.

Functions dealing with SWITCH_EXPR often scan the entires set of case
labels, so if those functions perform one of the last two operations
above, we easily get O(n^2) behavior.

======================================================================

First, I am thinking about improving "CASE_LABEL_EXPR -> edge" as
follows.

1. add "edge e;" to stmt_ann_d

2. allocate stmt_ann for each CASE_LABEL_EXPR

3. stop using CASE_LABEL of CASE_LABEL_EXPR after CFG is created.  In
   fact, we should probably put null in CASE_LABEL so that people
   won't mistakenly use it.

Then we should be able to do

  stmt_ann (switch_stmt)->e

to get an edge equivalent to find_edge (label_to_block (CASE_LABEL ()))
in constant time.  Now the obvious concern is memory consumption
arising from having edge for every statement with stmt_ann.  I need
come clever ideas here.  Maybe a hash table mapping CASE_LABEL_EXPR to
edge?

======================================================================

Second, I am thinking about improving "edge -> CASE_LABEL_EXPR" as
follows.

1. Have exactly one CASE_LABEL_EXPR per edge by doing something like
   this

   case 6 ... 8, 16 ... 20: goto <L5>;

   This means that we goto <L5> if a value given to the SWITCH_EXPR is
   between 6 and 8 or 16 and 20.

2. Create a sorted array of single ranges like 6...8, so that
   "INTEGER_CST -> CASE_LABEL_EXPR" can continue to use a binary
   search.

3. Put the sorted array in the SWITCH_EXPR.  As a result, the
   SWITCH_EXPR would have a sorted array of ranges *and* an array of
   CASE_LABEL_EXPRs.

4. Put a pointer in edge to point back to CASE_LABEL_EXPR.

Then we should be able to do "edge -> CASE_LABEL_EXPR" in constant
time.

======================================================================

I think it's easier to address "CASE_LABEL_EXPR -> edge", and that
should probably be done first.

By the way, here is a message from Steven Bosscher on the same
subject.

http://gcc.gnu.org/ml/gcc/2004-09/msg01141.html

Kazu Hirata

Re: Attacking quadratic behaviors associated with SWITCH_EXPR

[Zdenek Dvorak]

Hello,

> First, I am thinking about improving "CASE_LABEL_EXPR -> edge" as
> follows.
> 
> 1. add "edge e;" to stmt_ann_d
> 
> 2. allocate stmt_ann for each CASE_LABEL_EXPR
> 
> 3. stop using CASE_LABEL of CASE_LABEL_EXPR after CFG is created.  In
>    fact, we should probably put null in CASE_LABEL so that people
>    won't mistakenly use it.
> 
> Then we should be able to do
> 
>   stmt_ann (switch_stmt)->e
> 
> to get an edge equivalent to find_edge (label_to_block (CASE_LABEL ()))
> in constant time.  Now the obvious concern is memory consumption
> arising from having edge for every statement with stmt_ann.  I need
> come clever ideas here.  Maybe a hash table mapping CASE_LABEL_EXPR to
> edge?

statement annotations are huge, so this would indeed be a bad idea.
I think it would be better to avoid using tree for CASE_LABEL_EXPR
inside switch statement completely.  I.e. TREE_OPERAND (switch, 2)
would no longer be a TREE_VEC of CASE_LABEL_EXPRs, but instead
a wrapper tree node (of type tcc_exceptional) containing
a VEC(case_label_type), where case_label_type would contain just the
fields necessary for the case label.  This should also save some
memory over the current approach, since it is a bit less bloated
representation.

Zdenek

Re: Attacking quadratic behaviors associated with SWITCH_EXPR

[Kazu Hirata]

Hi Zdenek,

> statement annotations are huge, so this would indeed be a bad idea.
> I think it would be better to avoid using tree for CASE_LABEL_EXPR
> inside switch statement completely.  I.e. TREE_OPERAND (switch, 2)
> would no longer be a TREE_VEC of CASE_LABEL_EXPRs, but instead
> a wrapper tree node (of type tcc_exceptional) containing
> a VEC(case_label_type), where case_label_type would contain just the
> fields necessary for the case label.  This should also save some
> memory over the current approach, since it is a bit less bloated
> representation.

OK, I'll try this route then.

Kazu Hirata

Re: Attacking quadratic behaviors associated with SWITCH_EXPR

[Zack Weinberg]

Zdenek Dvorak <rakdver@atrey.karlin.mff.cuni.cz> writes:

> statement annotations are huge, so this would indeed be a bad idea.
> I think it would be better to avoid using tree for CASE_LABEL_EXPR
> inside switch statement completely.  I.e. TREE_OPERAND (switch, 2)
> would no longer be a TREE_VEC of CASE_LABEL_EXPRs, but instead
> a wrapper tree node (of type tcc_exceptional) containing
> a VEC(case_label_type), where case_label_type would contain just the
> fields necessary for the case label.

I concur.  In fact, I'd go farther, and suggest that we ought to be
working with edges directly, everywhere we are currently working with
labels, except in the parsers.

One might even speculate about the feasibility of constructing the
cfg inside the parser...

zw

Re: Attacking quadratic behaviors associated with SWITCH_EXPR

[Kazu Hirata]

Hi Zack,

> I concur.  In fact, I'd go farther, and suggest that we ought to be
> working with edges directly, everywhere we are currently working with
> labels, except in the parsers.

Yes.  I am thinking about starting with SWITCH_EXPR.  After that's
complete, we can probably remove GOTO_EXPR from COND_EXPR during the
lifetime of CFG.

> One might even speculate about the feasibility of constructing the
> cfg inside the parser...

Wow, I haven't thought about that far, yet. :-)

Kazu Hirata

Re: Attacking quadratic behaviors associated with SWITCH_EXPR

[Daniel Berlin]

On Mon, 25 Oct 2004, Kazu Hirata wrote:

> Hi Zack,
>
>> I concur.  In fact, I'd go farther, and suggest that we ought to be
>> working with edges directly, everywhere we are currently working with
>> labels, except in the parsers.
>
> Yes.  I am thinking about starting with SWITCH_EXPR.  After that's
> complete, we can probably remove GOTO_EXPR from COND_EXPR during the
> lifetime of CFG.

If this means i can simply redirect edges instead of frobbing around with 
labels, edges, and little bits of fairy dust, go for it.


Let me give you an eaxmple of real code today, and if you could, can you 
tell me what will still be required?

  then_label = build1 (GOTO_EXPR, void_type_node, tree_block_label 
(latchbb));
   else_label = build1 (GOTO_EXPR, void_type_node, tree_block_label 
(olddest));
   cond_stmt = build (COND_EXPR, void_type_node,
                      build (NE_EXPR, boolean_type_node,
                             integer_one_node,
                             integer_zero_node),
                      then_label, else_label);
   bsi = bsi_start (bodybb);
   bsi_insert_after (&bsi, cond_stmt, BSI_NEW_STMT);
   make_edge (bodybb, olddest, EDGE_FALSE_VALUE);
   make_edge (bodybb, latchbb, EDGE_TRUE_VALUE);


I'm guessing all i'll need is something like
   thenedge = make_edge (bodybb, latchbb, EDGE_TRUE_VALUE)
   elseedge = make_edge (bodybb, olddest, EDGE_FALSE_VALUE)
   cond_stmt = build (COND_EXPR, void_type_node,
                      build (NE_EXPR, boolean_type_node,
                             integer_one_node,
                             integer_zero_node),
                      thenedge, elseedge);
   bsi = bsi_start (bodybb);
   bsi_insert_after (&bsi, cond_stmt, BSI_NEW_STMT);

Is that about right?

>
>> One might even speculate about the feasibility of constructing the
>> cfg inside the parser...
>
> Wow, I haven't thought about that far, yet. :-)
>
> Kazu Hirata
>

Re: Attacking quadratic behaviors associated with SWITCH_EXPR

[Andrew MacLeod]

On Mon, 2004-10-25 at 13:26, Daniel Berlin wrote:
> On Mon, 25 Oct 2004, Kazu Hirata wrote:
> 
> > Hi Zack,

> > Yes.  I am thinking about starting with SWITCH_EXPR.  After that's
> > complete, we can probably remove GOTO_EXPR from COND_EXPR during the
> > lifetime of CFG.
> 
> If this means i can simply redirect edges instead of frobbing around with 
> labels, edges, and little bits of fairy dust, go for it.
> 

>   then_label = build1 (GOTO_EXPR, void_type_node, tree_block_label 
> (latchbb));
>    else_label = build1 (GOTO_EXPR, void_type_node, tree_block_label 
> (olddest));
>    cond_stmt = build (COND_EXPR, void_type_node,
>                       build (NE_EXPR, boolean_type_node,
>                              integer_one_node,
>                              integer_zero_node),
>                       then_label, else_label);
>    bsi = bsi_start (bodybb);
>    bsi_insert_after (&bsi, cond_stmt, BSI_NEW_STMT);
>    make_edge (bodybb, olddest, EDGE_FALSE_VALUE);
>    make_edge (bodybb, latchbb, EDGE_TRUE_VALUE);
> 

I seem to recall the issue when this was first proposed was back when
Zdenek brought implicit edges and flattened tree-ssa, was that we then
have a two state COND_EXPR, depending on whether the cfg is present or
not.  At the time the decision was that it was better to leave the
stmt's in the arms of the COND_EXPR, thus we ended up with the GOTO_EXPR
placeholders.  I also believe we thought we might want/need a different
opcode if the semantics were going to be changed.

However, I dont remember well past 4 about months ago :-). Many things
have changed since then, so is there still an issue here or is it gone
now? I cant think of anything off the top of my head, or perhaps I just
remember it poorly :-) It might also be that we were being cautiously
pessimistic about changing too much at once.

Andrew

Re: Attacking quadratic behaviors associated with SWITCH_EXPR

[Kazu Hirata]

Hi Daniel,

> > Yes.  I am thinking about starting with SWITCH_EXPR.  After that's
> > complete, we can probably remove GOTO_EXPR from COND_EXPR during the
> > lifetime of CFG.
> 
> If this means i can simply redirect edges instead of frobbing around with 
> labels, edges, and little bits of fairy dust, go for it.

Yes, that's what I meant.

> Let me give you an eaxmple of real code today, and if you could, can you 
> tell me what will still be required?
> 
>   then_label = build1 (GOTO_EXPR, void_type_node, tree_block_label 
> (latchbb));
>    else_label = build1 (GOTO_EXPR, void_type_node, tree_block_label 
> (olddest));
>    cond_stmt = build (COND_EXPR, void_type_node,
>                       build (NE_EXPR, boolean_type_node,
>                              integer_one_node,
>                              integer_zero_node),
>                       then_label, else_label);
>    bsi = bsi_start (bodybb);
>    bsi_insert_after (&bsi, cond_stmt, BSI_NEW_STMT);
>    make_edge (bodybb, olddest, EDGE_FALSE_VALUE);
>    make_edge (bodybb, latchbb, EDGE_TRUE_VALUE);
> 
> 
> I'm guessing all i'll need is something like
>    thenedge = make_edge (bodybb, latchbb, EDGE_TRUE_VALUE)
>    elseedge = make_edge (bodybb, olddest, EDGE_FALSE_VALUE)
>    cond_stmt = build (COND_EXPR, void_type_node,
>                       build (NE_EXPR, boolean_type_node,
>                              integer_one_node,
>                              integer_zero_node),
>                       thenedge, elseedge);
>    bsi = bsi_start (bodybb);
>    bsi_insert_after (&bsi, cond_stmt, BSI_NEW_STMT);
> 
> Is that about right?

I wasn't thinking of increasing the number of arguments to build()
because make_edge installs an edge to corresponding edge vectors.  So,
in your example, you would write something like

  thenedge = make_edge (bodybb, latchbb, EDGE_TRUE_VALUE)
  elseedge = make_edge (bodybb, olddest, EDGE_FALSE_VALUE)
  cond_stmt = build (COND_EXPR, void_type_node,
                     build (NE_EXPR, boolean_type_node,
                            integer_one_node,
                            integer_zero_node),
                     NULL_TREE, NULL_TREE);          <- Notice this line!
  bsi = bsi_start (bodybb);
  bsi_insert_after (&bsi, cond_stmt, BSI_NEW_STMT);

Kazu Hirata

Re: Attacking quadratic behaviors associated with SWITCH_EXPR

[Kazu Hirata]

Hi Andrew,

> I seem to recall the issue when this was first proposed was back when
> Zdenek brought implicit edges and flattened tree-ssa, was that we then
> have a two state COND_EXPR, depending on whether the cfg is present or
> not.  At the time the decision was that it was better to leave the
> stmt's in the arms of the COND_EXPR, thus we ended up with the GOTO_EXPR
> placeholders.  I also believe we thought we might want/need a different
> opcode if the semantics were going to be changed.
> 
> However, I dont remember well past 4 about months ago :-). Many things
> have changed since then, so is there still an issue here or is it gone
> now? I cant think of anything off the top of my head, or perhaps I just
> remember it poorly :-) It might also be that we were being cautiously
> pessimistic about changing too much at once.

Some people were against the implicit GOTO_EXPR and the idea of making
CFG a part of IL.  See a long dicsussion starting from

http://gcc.gnu.org/ml/gcc-patches/2003-11/msg00985.html

Yes, a different opcode may be nicer than putting NULL_TREE into the
last two fields of a COND_EXPR.

Anyway, updating goto labels just for the sake of updating them does
not make sense.  I believe they are needed only before CFG is created
and at expand time.

Kazu Hirata

Re: Attacking quadratic behaviors associated with SWITCH_EXPR

[Zdenek Dvorak]

Hello,

> > I seem to recall the issue when this was first proposed was back when
> > Zdenek brought implicit edges and flattened tree-ssa, was that we then
> > have a two state COND_EXPR, depending on whether the cfg is present or
> > not.  At the time the decision was that it was better to leave the
> > stmt's in the arms of the COND_EXPR, thus we ended up with the GOTO_EXPR
> > placeholders.  I also believe we thought we might want/need a different
> > opcode if the semantics were going to be changed.
> > 
> > However, I dont remember well past 4 about months ago :-). Many things
> > have changed since then, so is there still an issue here or is it gone
> > now? I cant think of anything off the top of my head, or perhaps I just
> > remember it poorly :-) It might also be that we were being cautiously
> > pessimistic about changing too much at once.
> 
> Some people were against the implicit GOTO_EXPR and the idea of making
> CFG a part of IL.  See a long dicsussion starting from
> 
> http://gcc.gnu.org/ml/gcc-patches/2003-11/msg00985.html
> 
> Yes, a different opcode may be nicer than putting NULL_TREE into the
> last two fields of a COND_EXPR.
> 
> Anyway, updating goto labels just for the sake of updating them does
> not make sense.  I believe they are needed only before CFG is created
> and at expand time.

yes.  From what little I remember from the discussion, there were no
real arguments against the change, except for general dislike for any
change to IL (also my patch for it attempted to do too many things at
once).

It would indeed be great to be able to expand statements directly to
cfg, and it would not be principially hard; the main problems are that
it would require a complete rewrite of gimplification (the current
system in that statements may get regimplified is too messy), and
something would have to be done about exception handling (the easiest
way probably would be to have cfg constructed in several pieces
corresponding to the eh constructs and perform the eh lowering in a
later pass as we do now).

Zdenek

Re: Attacking quadratic behaviors associated with SWITCH_EXPR

[Jeffrey A Law]

On Fri, 2004-10-22 at 20:43 -0400, Kazu Hirata wrote:

> INTEGER_CST -> CASE_LABEL_EXPR
>   O(log n).  Implemented in find_case_label_for_value.
Typically only performed when we know the incoming value for the 
SWITCH_COND.  Given that it's a binary search, I'm terribly worried
about this one right now.


> CASE_LABEL_EXPR -> LABEL_DECL
>   O(1).  This is a primitive operation.
Yup.  Note this is primarily done during coalescing adjacent cases,
expansion and when redirecting edges out of the SWITCH_EXPR via
the need to map from CASE_LABEL_EXPR to a basic block.


> 
> CASE_LABEL_EXPR -> basic_block (via LABEL_DECL)
>   O(1).  Implemented in label_to_block.
I believe this happens primarily when redirecting edges out of 
the SWITCH_EXPR.


> CASE_LABEL_EXPR -> edge (via LABEL_DECL and basic_block)
>   O(n).  Performed in find_taken_edge_switch_expr.
>   Implemented as label_to_block, followed by find_edge
Actually this was O(p) where p is the number of unique outgoing
edges.  Now it's O(min (p,q)) where p is the number of unique
outgoing edges and q is the number of unique incoming edges
into the destination block.  Typically q is significantly
smaller than p or n for switch statements.

> 
> edge -> CASE_LABEL_EXPR
>   O(n).  Performed in tree_redirect_edge_and_branch.
Yup.  And this is actually the real killer these days.


> 
> 1. add "edge e;" to stmt_ann_d
> 
> 2. allocate stmt_ann for each CASE_LABEL_EXPR
Ouch. 


> 3. stop using CASE_LABEL of CASE_LABEL_EXPR after CFG is created.  In
>    fact, we should probably put null in CASE_LABEL so that people
>    won't mistakenly use it.
Very reasonable.  This alone is reasonably easy to accomplish without
changing how we represent the CASE_LABEL_EXPR.  We have a hash table
which maps an edge to the cases utilizing that edge.


> to get an edge equivalent to find_edge (label_to_block (CASE_LABEL ()))
> in constant time.  Now the obvious concern is memory consumption
> arising from having edge for every statement with stmt_ann.  I need
> come clever ideas here.  Maybe a hash table mapping CASE_LABEL_EXPR to
> edge
Well, I wouldn't tackle CASE_LABEL_EXPR to edge right now -- it's not
as important as edge to CASE_LABEL_EXPRs with my recent change to
find_edge.


> ======================================================================
> 
> Second, I am thinking about improving "edge -> CASE_LABEL_EXPR" as
> follows.
> 
> 1. Have exactly one CASE_LABEL_EXPR per edge by doing something like
>    this
> 
>    case 6 ... 8, 16 ... 20: goto <L5>;
> 
>    This means that we goto <L5> if a value given to the SWITCH_EXPR is
>    between 6 and 8 or 16 and 20.
Or chain together CASE_LABEL_EXPRs which hit the same destination
via their TREE_CHAIN field.  Your scheme might be cheaper for the
edge->case_label_expr case, but it may also introduce inefficiencies
elsewhere (INTEGER_CST->CASE_LABEL_EXPR and dealing with edge
redirections where two previously disjoint cases now reach the
same destination).


> 2. Create a sorted array of single ranges like 6...8, so that
>    "INTEGER_CST -> CASE_LABEL_EXPR" can continue to use a binary
>    search.
> 
> 3. Put the sorted array in the SWITCH_EXPR.  As a result, the
>    SWITCH_EXPR would have a sorted array of ranges *and* an array of
>    CASE_LABEL_EXPRs.
> 
> 4. Put a pointer in edge to point back to CASE_LABEL_EXPR.
> 
> Then we should be able to do "edge -> CASE_LABEL_EXPR" in constant
> time.
Yea, but I think you end up paying a pretty high cost when you need
to merge.  Of course the other schemes I've pondered have a high cost
then as well.



> I think it's easier to address "CASE_LABEL_EXPR -> edge", and that
> should probably be done first.
Possibly, but it's not going to give you the big win that dealing
with edge->CASE_LABEL_EXPR(s) would give you.

jeff

Re: Attacking quadratic behaviors associated with SWITCH_EXPR

[Steven Bosscher]

On Wednesday 10 November 2004 01:52, Jeffrey A Law wrote:
> > CASE_LABEL_EXPR -> edge (via LABEL_DECL and basic_block)
> >   O(n).  Performed in find_taken_edge_switch_expr.
> >   Implemented as label_to_block, followed by find_edge
>
> Actually this was O(p) where p is the number of unique outgoing
> edges.  Now it's O(min (p,q)) where p is the number of unique
> outgoing edges and q is the number of unique incoming edges
> into the destination block.  Typically q is significantly
> smaller than p or n for switch statements.

That was a nice catch, yes :-)


> > edge -> CASE_LABEL_EXPR
> >   O(n).  Performed in tree_redirect_edge_and_branch.
>
> Yup.  And this is actually the real killer these days.

Yup, this is a real problem in the critical edge splitting pass and
thread_jumps_from_bb.  Here are some bits from a gprof profile for
the very artificial code of PR15524:

-----------------------------------------------
                0.01   68.18   10000/100002      thread_block [37]
                0.01   68.20   10002/100002      try_forward_edges [50]
                0.02  204.55   30000/100002      tree_split_edge [23]
                0.03  340.92   50000/100002      thread_jumps_from_bb [20]
[13]    46.6    0.06  681.85  100002         redirect_edge_and_branch [13]
              264.76  412.78   90000/100000      tree_redirect_edge_and_branch [12]
                0.00    4.30   10002/10002       rtl_redirect_edge_and_branch [98]
-----------------------------------------------

It's tree_redirect_edge_and_branch that is quadratic if most outgoing
edges of a block ending in a SWITCH_EXPR are critical edges.

(Note that pass_split_crit_edges really shouldn't be a pass.  It only
provides a property, PROP_no_crit_edges, but it's run unconditionally,
so even with -fno-tree-pre (which is the only pass that requires this
property) we still run the pass_split_crit_edges pass - wasteful!)


> > 3. stop using CASE_LABEL of CASE_LABEL_EXPR after CFG is created.  In
> >    fact, we should probably put null in CASE_LABEL so that people
> >    won't mistakenly use it.
>
> Very reasonable.  This alone is reasonably easy to accomplish without
> changing how we represent the CASE_LABEL_EXPR.  We have a hash table
> which maps an edge to the cases utilizing that edge.

You think of this as a single, global hash table, or a hash table for
each SWITCH_EXPR?  You'd guess the latter is overkill but the former
could grow just huge for test cases of the kind of PR15524.  How would
you add the cases to the hash element for the edge?  Some linked list
for that?

The *cough* good news is that despite all the new tree-ssa passes with
their wards, CSE and reg_scan are now consistenly back on top in almost
any profile I look at ;-)

Gr.
Steven

Re: Attacking quadratic behaviors associated with SWITCH_EXPR

[Daniel Berlin]

> It's tree_redirect_edge_and_branch that is quadratic if most outgoing
> edges of a block ending in a SWITCH_EXPR are critical edges.
>
> (Note that pass_split_crit_edges really shouldn't be a pass.  It only
> provides a property, PROP_no_crit_edges, but it's run unconditionally,

That's the fault of the pass manager.
Passes can provide propreties.
If nothing requires the property it provides (due to them not being 
executed), it shouldn't run the pass that provides the property.

> so even with -fno-tree-pre (which is the only pass that requires this
> property) we still run the pass_split_crit_edges pass - wasteful!)

This is true, PRE is the only pass that *requires* it (and even that is 
not strictly true. I could make PRE not require it, at the expense of 
missing a bunch of redundancies).
However, splitting critical edges is *useful* to a lot of passes, AFAIK.

Re: Attacking quadratic behaviors associated with SWITCH_EXPR

[Jeffrey A Law]

On Wed, 2004-11-10 at 02:34 +0100, Steven Bosscher wrote:
> > Actually this was O(p) where p is the number of unique outgoing
> > edges.  Now it's O(min (p,q)) where p is the number of unique
> > outgoing edges and q is the number of unique incoming edges
> > into the destination block.  Typically q is significantly
> > smaller than p or n for switch statements.
> 
> That was a nice catch, yes :-)
I'd noticed it before and when it showed its ugly head again on
15524 we were finally in a position to actually solve it thanks
to those who worked on the edge-vector changes.

> 
> 
> > > edge -> CASE_LABEL_EXPR
> > >   O(n).  Performed in tree_redirect_edge_and_branch.
> >
> > Yup.  And this is actually the real killer these days.
> 
> Yup, this is a real problem in the critical edge splitting pass and
> thread_jumps_from_bb.  Here are some bits from a gprof profile for
> the very artificial code of PR15524:
I'm well aware of it  :( It's going to stick out even worse once I fix
flow_dfs_compute_reverse_execute which accounts for the remaining
lameness charged PRE and branch prediction.


> You think of this as a single, global hash table, or a hash table for
> each SWITCH_EXPR?  You'd guess the latter is overkill but the former
> could grow just huge for test cases of the kind of PR15524.  How would
> you add the cases to the hash element for the edge?  Some linked list
> for that?
I've prototyped it as a single global hash table.  It works damn well
for 15524, but I haven't looked at its behavior for more sane code.

There's this nagging voice telling me there's a better way, possibly
using a combination of Kazu's ideas and a hash table.  Anyway, I'm
continuing to prototype various approaches to see where their
strengths and weaknesses are.

> The *cough* good news is that despite all the new tree-ssa passes with
> their wards, CSE and reg_scan are now consistenly back on top in almost
> any profile I look at ;-)
Good.  That's the way I want the profiles to look right now :-)

Jeff

Re: Attacking quadratic behaviors associated with SWITCH_EXPR

[Steven Bosscher]

On Wednesday 10 November 2004 02:45, Daniel Berlin wrote:
> > It's tree_redirect_edge_and_branch that is quadratic if most outgoing
> > edges of a block ending in a SWITCH_EXPR are critical edges.
> >
> > (Note that pass_split_crit_edges really shouldn't be a pass.  It only
> > provides a property, PROP_no_crit_edges, but it's run unconditionally,
>
> That's the fault of the pass manager.
> Passes can provide propreties.
> If nothing requires the property it provides (due to them not being
> executed), it shouldn't run the pass that provides the property.
>
> > so even with -fno-tree-pre (which is the only pass that requires this
> > property) we still run the pass_split_crit_edges pass - wasteful!)
>
> This is true, PRE is the only pass that *requires* it (and even that is
> not strictly true. I could make PRE not require it, at the expense of
> missing a bunch of redundancies).
> However, splitting critical edges is *useful* to a lot of passes, AFAIK.

Perhaps we should run the pass earlier then, or always keep critical
edges split over some range of passes, etc.  The current situation is
really stupid: We split edges, then run PRE (or not), and then spend
a good amount of time unsplitting edges in cfgcleanup :-/

Gr.
Steven