This is the mail archive of the gcc@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: birthpoints in rtl.


Steven Bosscher wrote:
> On Tue, Mar 4, 2008 at 7:58 PM, Diego Novillo <dnovillo@google.com> wrote:
>   
>>  Both PHIs and birthpoints are merely factoring devices that let you cut
>>  down the number of UD links.  They don't need to be part of the IL, much
>>  like none of the DF objects are part of the RTL IL.
>>     
>
> Maybe they don't need to be, but it may be useful to have them anyway.
>
>   
>>  > What about keeping things up-to-date after applying some
>>  > transformations? It is already hard to keep UD/DU chains up-to-date
>>  > now (I don't think any pass successfully does so right now). This
>>  > should be a lot easier if you fully factorize your UD chains, right?
>>
>>  In theory, yes.  Code for keeping these things up-to-date already exists
>>  in GIMPLE SSA.
>>     
>
> That code is IMHO just awfully ugly. And slow too, last I checked.  I
> don't know if  this is still true, but update_ssa used to walk a huge
> part of the dominator tree even for seemingly trivial updates. We
> should not want that on RTL.  I don't think we should allow
> transformations on RTL that are too hard to manually update the FUD
> chains somehow.
>
> Gr.
> Steven
>   
There are many differences between fud/birthpoints and real ssa:

1) In ssa, the operands of the phis and the renaming contain
information.   The operands are paired with the cfg edges that the
values come in on.   In fud/birthpoints there is no such pairing or
renaming.   For some problems, like conditional constant, this pairing
and renaming is what makes the algorithm work.  You actually do not get
the same answer (you get an inferior but still correct answer) if you do
not use the pairing and renaming.

2) There are two "kinds" of ssa algorithms that are used in gcc.   There
are dirty ssa algorithms and "clean" algorithms.  Dirty algorithms do
not keep ssa up to date as you make the transformations.  Clean ones
do.  I have never understood why it was necessary for gcc to use so many
dirty ssa algorithms.  When NaturalBridge built our compiler, we were
able to use almost exclusively clean algorithms.   Tricks like loop
closed ssa form, help, but in general this is a matter of care on the
algorithmic design side and implementation.   We never had something
like rebuild ssa at naturalbridge.  

I do not know how much this changes with memory ssa.  I assume clean
algorithms are harder here, but I have no experience with it.  I have
had particularly heated discussions with zdenek over the years where he
asserted that it was not worth it/impossible to think about clean ssa
algorithms and i showed him simple tricks to keep things up to date.  I
believe he just simply ignored me.

fud/birthpoints are generally harder to develop clean algorithms for.  
I have never seen any published.   The information in the phis really
helps you develop clean algorithms.  

I would love to see the rtl back end use phis and renaming rather than
fuds/birthpoints.  The thing is that for phi functions to really be
profitable, you need to have a large number passes in a row that are ssa
clean.  So my plan was to basically start small and just use
fud/birthpoints to control the space/time of the existing suite of passes. 

Kenny







Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]