Steven Bosscher wrote: > On Tue, Mar 4, 2008 at 7:58 PM, Diego Novillo <[EMAIL PROTECTED]> 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
