[tree-ssa] Translation out of SSA

[Jan Vroonhof]

Sorry to to but in, but if you could spare a few minutes to clear up a
few details for us lurkers trying to follow what is going on.

>  - conflict graph based coalesing of partitions.

Unless  I am very confused doesn't this mean this the comment in tree-ssa.c

/* The following procedures implement the out of SSA algorithm detailed in 
   the Morgan Book pages 176-186.  */

is not quite true (anymore)? The partition equivalence relation given
in the Morgan book seems much weaker (only coalescing partitions just
enough to avoid inserting copies on abnormal critical edges), whereas
the one you just implemented seems to be right on the other end of the
spectrum (i.e. coalesce unless we absolute cannot[1]).


Is it explained somewhere:
  1. Why you went for this particular option? Is it to minimise the
number of temporaries left over after unssa? I presume Morgan is just
relying on a coalescing register allocator to come just after.
  2. How the partitioning in your algorithm avoids inserting copies on
abnormal critical edges (at least to me it is non-obvious that the
algorithm guarantees the SSA temps of the same variable on both sides
of an abnormal edge end up in the same partition).
or am I just showing my lack of knowledge and this is all trivial?


> Then we'll remove the abort() permanently, and start allowing overlapping 
> live ranges, but not before I debug them :-). I know there is a bug in edge
> insertion I have to get to, and a couple of other things.

Are you talking about the following[2]

gcc -O3 -ftree-copyprop -c foo.c

for foo.c

void foo(int i)
{
  int b;
  b = 0;
  
  if (i)
    {
      b = i;
    }
  else
    {
      i = b;
    }
  foo(i);
  foo(b);
}

gives

Program received signal SIGSEGV, Segmentation fault.
bsi_insert_after (curr_bsi=0xbffff108, t=0x40344760, mode=BSI_NEW_STMT)
    at ../../gcc/tree-flow-inline.h:72
72      {
(gdb) where
#0  bsi_insert_after (curr_bsi=0xbffff108, t=0x40344760, mode=BSI_NEW_STMT)
    at ../../gcc/tree-flow-inline.h:72
#1  0x080bbd93 in bsi_commit_first_edge_insert (e=0x8716738, stmt=0x40344760)
    at ../../gcc/tree-cfg.c:3466
#2  0x080bd036 in bsi_commit_edge_inserts (update_annotations=0,
    new_blocks=0x0) at ../../gcc/tree-cfg.c:3598
#3  0x080cae2a in rewrite_out_of_ssa (fndecl=0x4036d700)

> 500 seconds, so thats a 2% hit. We might be able to decrease it, but
> we are doing a *heck* of a lot more work. Building the live ranges,
> a conflict graph, coalescing partitions, and running it through the
> real PHI node copy generator, which itself generates little
> interference graphs for copies on edges.

The Briggs, e.a. "Practical Improvements ..." paper that is the basis
for the SSA rewriting phase actually claims that you can solve the
latter problem (possible cycles in the PHI nodes within one block)
without actually constructing the graph itself. At first glance at
least they seem to be solving the same problem.

Thanks for your consideration,

Jan

Footnotes: 
[1]  The code even optimistically assumes it can map all the
partitions to their root variable and maps it to a different temporary
if it absolutely has to (quite different from the union-find proposed
by Morgan).

[2]  I actually have enabled the #if 0 bits in the to-SSA conversion
that do basic value numbering etc as well[3]. But I don't think it matters
in the above case.

[3]  They have actually bit-rotted a bit because they are #if'ed out.

-	  bsi_remove (si);
+	  bsi_remove (&si);