[Bug c++/13776] [tree-ssa] Many C++ compile-time regression in 3.5-tree-ssa 040120

[Richard Guenther]

dberlin at dberlin dot org wrote:
> ------- Additional Comments From dberlin at dberlin dot org  2004-03-13 02:02 -------
> Subject: Re:  [tree-ssa] Many C++ compile-time regression in 3.5-tree-ssa 040120
> 
> 
> 
>>instrumented compiler gives:
>>
>>Flat profile:
>>
>>Each sample counts as 0.01 seconds.
>>   %   cumulative   self              self     total
>>  time   seconds   seconds    calls  Ks/call  Ks/call  name
>>  15.51    183.22   183.22   726080     0.00     0.00
>>process_left_occs_and_kills
> 
> 
> 
> This one is O(n^2) or O(n^3) in the number of vuses.  Known problem. a 
> fix is really complicated.
> 
> 
> 
>>   8.55    284.25   101.03    16644     0.00     0.00
>>create_and_insert_occ_in_preorder_dt_order
> 
> 
> Hmmmm.
> It is attempting to PRE 16664 things.
> How many basic blocks do you have?
> We shouldn't end up with trying to PRE that many expressions, since we 
> only try to PRE things that occur at least twice.
> 
> 
> You must have an incredibly large number of basic blocks or something, 
> or a very weird flowgraph.
> How many BB's are we talking about?
> 
> I can't fix the algorithmic properties of the SSAPRE algorithm we use, 
> which is what you are running into, i'm betting.
> 
> I'm working on a new PRE implementation that is O(n^2) memory usage in 
> the number of phi nodes, but should be a bit faster overall.

I'm trying to look at some dump files now - looking at the optimized 
dump, is it ok to have loads of "duplicate" variable declarations in the 
dump? Like

...
   struct Domain<3,DomainTraits<Loc<3> > > * const this;
   int d;
   int d;
   int <D1144454>;
   int d;
   int T.4364;
...

and a lot more of int d farther away? Also, how are bb's marked? I see 
<bb 0>: but no more, and some gotos reference <bb 18> and <bb 16> (with 
a label, too)?

Can I get summaries somehow here?  Or just dump one interesting function 
rather than all of the program?

Also, how do I dump some stuff about the PRE pass?  Specifying 
-fdump-tree-pre just dumps the trees after PRE with no information about 
the PRE pass itself.

Thanks,

Richard.