Re: [tree-ssa] crash in coalesce_abnormal_edges, merge frommainline?

[Andrew MacLeod <amacleod at redhat dot com>]

On Wed, 2003-09-10 at 13:03, law@redhat.com wrote:
> In message <1063211660.30914.18.camel@p4>, Andrew MacLeod writes:
>  >On Wed, 2003-09-10 at 12:30, Andrew MacLeod wrote:
>  >> On Wed, 2003-09-10 at 11:32, Daniel Berlin wrote:
>  >
>  >> Looking at each place where may_propagate_copy() is called, in virtually
>  >> every instance that matters, we are processing the arguments of a PHI,
> "virtually every instance" is not good enough.  We need to know for any
> arbitrary copy if one of its arguments is referenced in an abnormal PHI.
> 

Im trying to remember why we need to know that. The other "virtual"
instances were ones that didnt matter.  propagating into a stmt (but not
a PHI) and the other was a double check abort() at actual copy
replacement time.

Im probably missing an example, but I havent come up with why we can't
do this now, as long as we leave PHI's alone, and all the places we do
that are disjoint from where we do it to stmts.

Dont mean to open an old wound :-)

>  >> which means have access to the edge that arguement comes across right
>  >> there on the spot... so we could just check the flag on the edge and not
>  >> do the copy propagate based on that.. Then we dont have this auxillary
>  >> bit hanging around.
> No, you really need to set the bit -- you can't assume that you're only
> going to query this information at PHI nodes.
> 

the reason I ask is that I thought its only an issue at the SSA->normal
phase, and thats because we may have to issue a copy across the edge.
There is no reason the value can't be propagated *into* the other stmts
in the block across an abnormal edge, it just cant be in the PHI because
we can't insert a copy on that edge.

So is it a bad thing to propagate the copy into the block even though
you can't propagate it into the PHI?  It seems to me that'd let you
propagate constants all over the play except into PHI's, for one thing..

Of course, I now have a mechanism for generating correct code even when
we do have abnormal edge coalesces, it just isn't pretty :-) I have
another scheme by which we can allow these coalesces to happen.
It goes something like this:

  p_1 =                   p_2 = 
  t_2 = p_1                
     \                 /
      \(ab)           /(ab)
       \             /
      p_3 = PHI (t_2, p_2)

 When we detect that we have a problem across an abnormal edge, we can
translate this into:

  p_1 =                   p_2 = 
  t_2 = p_1 
  z_5 = t_2             z_6 = p_2
     \                 /
      \(ab)           /(ab)
       \             /
      z_4 = PHI (z_5, z_6)
      p_3 = z_4


So the SSA->normal pass will end up generating the following code:
  p =                   p = 
  t = p 
  z = t                 z = p
     \                 /
      \(ab)           /(ab)
       \             /
          p = z




So, how icky is that :-).  However, there are some very distinct
properties we know about 'z' when we generate this code.
- each version only interferes with the variables which are live on exit
to its block
- They dont interfere with what they are a copy of.
- z_4 only interferes with the results of other PHI nodes plus whats
live on entry into its block

THis ought to work because the 'z's will be known to coalesce with each
other for sure, at the expense of extra copies in preceeding blocks.

That means the memory coalescer, (which is there, it just isnt turned on
yet due to nested var decls in BIND_EXPR's), can (and should) coalesce
everything together (when possible) since it isn't bound by the
restrictions of requiring the same root_variable. The only time the
copies wouldn't be coalesced is when there is a true interference, and
that would have been unresolvable and required a copy anyway.

Anyway, we ought to see something like:

  p =                 p = 
     \                 /
      \(ab)           /(ab)
       \             /
         

if there are other interferences, things will be satisfied in a
reasonable way. ie, if p1 and p2 interefer because of a use somewhere
else... we'd see something like:

  p =                   p.2 = 
		        p = p.2
     \                 /
      \(ab)           /(ab)
       \             /
           


Of course, if one of the arguments is a constant, we'll see:

                        p_2 =             
     \                 /
      \(ab)           /(ab)
       \             /
      p_3 = PHI (4, p_2)

which becomes 
                    p =
z = 4               z = p
     \                 /
      \(ab)           /(ab)
       \             /
          p = z

and again the memory coalescer will coalesce p and z in this instance:


p = 4                p =
     \                 /
      \(ab)           /(ab)
       \             /
    

This is not hard to implement, espcially since the memory coalescer is
already done. All we'd need to do is add those new PHI nodes at the
appropriate place, which I beleive to be either during or just after
building the interference graph when we still have the live range
information. I need a minor amount of prep work to ensure there is room
in the partition map for the new variables we are going to create, but
thats not too difficult.

So you can see where my motivation to remove the bit comes from... we
might be able to remove the restriction completely in the not too
distant future... and that would be a good thing.

Of course, this assume I'm not missing something in my scheme to add new
PHIs to resolve the inserting of copies on edges problem.. 

Of course, after all that, that simply argues that we ought to leave the
bit check where it is in may_propagate_copy since its localized to one
place.

So is the general perception that this is a good thing? being able to
propagate without the abnormal edge restriction? If so, and I think it
is, I'll write the code...


Andrew