Higher level RTL issues

[law@redhat.com]

As promised, here's an example where optimizations done on the SSA form
ultimately result in having two SSA names for the same original temporary
are live at the same time.

As I've mentioned before, when that happens it is not possible to simply
throw away the SSA names and use the original variable/temporary names.

This is not a trivial example.  I recommend you start by first taking
the info from blah.cfg and scribble out of CFG for this function.

Note carefully the loop at starting at block 23 and the backedges from
blocks 9, 16, 19, 20, 21 and 22 to block 23.


I've saved the RTL just before we convert into SSA in j.c.pressa.  Mostly
so that we can recover the original register #s from the RTL.  j.c.04.ssa
shows how we convert into SSA form without applying dominator based
optimizations.

We're concerned with the assignments and uses of two registers.

(reg 344) Defs:
  insn 209, bb5	  SSA reg 344
  insn 338, bb9	  SSA reg 607
  insn 407, bb16  SSA reg 614
  insn 458, bb18  SSA reg 617	Note this occurs after the def at insn 438

(reg 344) Uses:
  insn 312, bb8
  insn 317, bb8
  insn 438, bb18  
  insn 550, bb24

(reg 444) Defs:
  insn 305, bb8

(reg 444) Uses:
  insn 311, bb8

  
The PHI node at the start of bb23 looks like:

(insn 765 744 276 (set (reg:DI 603)
        (phi[
                (reg:DI 617)
                (const_int 22 [0x16])
                (reg:DI 617)
                (const_int 21 [0x15])
                (reg:DI 617)
                (const_int 20 [0x14])
                (reg:DI 617)
                (const_int 19 [0x13])
                (reg:DI 614)
                (const_int 16 [0x10])
                (reg:DI 607)
                (const_int 9 [0x9])
                (reg/v:DI 344)
                (const_int 7 [0x7])
            ] )) -1 (nil)
    (nil))

Verification that this makes sense is left to the reader.  Basically
(reg 344) reaches from outside the loop.  The rest reach from inside the loop.
The lifetimes of regs 344, 607, 614, 617 and 603 are disjoint.


There is no PHI node related to the definition of (reg 444) as (reg 444) is
only assigned to once in the original RTL.

Those are the key items from the translation from normal into SSA form.  If
we made no transformations to the code we could throw away the SSA register
numbers and just use the original register numbers.

Now look in j.c.04.ssa for insn 305 in block 8 and insn 458 in block 18.
They should look like:

(insn 305 303 307 (set (reg:DI 444)
        (sign_extend:DI (reg/v:SI 343))) -1 (nil)
    (nil))


(insn 458 456 461 (set (reg:DI 617)
        (sign_extend:DI (reg/v:SI 343))) -1 (nil)
    (nil))


From the CFG we know that block 8 dominates block 18 and thus insn 305 
dominates insn 458.  Since we're in SSA form we know that (reg 343) is
only assigned to once and its set dominates its uses.  Therefore, we
know that insn 458 is redundant and with a little work can be removed.

Armed with that information, let's pretend that we're doing dominator
optimizations as Morgan has described while translating from normal
form into SSA form.

When we encounter insn 305, we record that (sign_extend:DI (reg:SI 343))
can be found in (reg:DI 444).  We proceed to follow paths through the
dominator tree and eventually reach block 18 with insn 458.  Remember
block 8 (which contained insn 305) dominates block 18, so entries we
added to the hash table for block 8 are still available.

When we reach insn 458, we lookup (sign_extend:DI (reg:SI 343)) and we
get (reg:DI 444).  Cool.  That means insn 458 is redundant.  Delete it.
Do some manipulation of our renaming stacks to arrange for uses of 
(reg:DI 617) to be rewritten as (reg:DI 444).  The only uses of 
(reg:DI 617) are at insn 765.



After finishing the translation into SSA form the PHI node at the start
of block 23 would look like:

(insn 765 744 276 (set (reg:DI 603)
        (phi[
                (reg:DI 444)
                (const_int 22 [0x16])
                (reg:DI 444)
                (const_int 21 [0x15])
                (reg:DI 444)
                (const_int 20 [0x14])
                (reg:DI 444)
                (const_int 19 [0x13])
                (reg:DI 614)
                (const_int 16 [0x10])
                (reg:DI 607)
                (const_int 9 [0x9])
                (reg/v:DI 344)
                (const_int 7 [0x7])
            ] )) -1 (nil)
    (nil))


So far so good?  If you want, you can verify that the changes we made were
all valid and we're still in SSA form.

However, note carefully that SSA name (reg:DI 444) is live at the same time
as SSA name (reg:DI 603).  Specifically they are both live starting after
insn 305 in block 8.  

This happened because redundancy elimination extended the lifetime of one
register in order to eliminate a redundancy.


So, how do you turn this back into normal form?  Well, for the camp that
reflects the SSA names in the IR, it's the standard SSA->normal translation
and everything just works.

So how is this done when SSA names are not reflected in the IR?  I have
ideas, but I'd like to hear from someone with more experience in the
non-rewriting camp.  You certainly can't do the naive thing and drop the
SSA names in favor of the original names.

FWIW, k.c.04.ssa is the same as j.c.04.ssa, except that dominator opts were
applied during translation into SSA form.  It may or may not be useful to
folks that want to poke around at this issue.