Question re: SSA Aggressive Dead Code Elimination

[law at redhat dot com]

Whee, I've been having oodles of fun with SSA optimizers over the last couple
weeks.  I've run into a very interesting problem and wanted to see if
anyone has any experience with this stuff.

First consider this CFG

    E
    |
    0
   / \
  1-->2--> Exit

Assume that regs 24, 27, 25 are live at entry to this mini CFG.

(insn 92 123 93 (set (reg:SI 30)
        (plus:SI (reg/v/f:SI 24)
            (reg/v:SI 27))) -1 (nil)
    (nil))

(jump_insn 93 92 124 (set (pc)
        (if_then_else (gtu:CC (reg:SI 30)
                (reg/v/f:SI 25))
            (label_ref 96)
            (pc))) -1 (nil)
    (nil))

(note 124 93 95 [bb 1] NOTE_INSN_BASIC_BLOCK 0)

(insn 95 124 96 (set (reg/v/f:SI 24)
        (plus:SI (reg/v/f:SI 24)
            (reg/v:SI 27))) -1 (nil)
    (nil))

(code_label 96 95 125 19 "" "" [1 uses])

(note 125 96 101 [bb 2] NOTE_INSN_BASIC_BLOCK 0)

(insn 101 125 108 (set (reg/i:SI 0 r0)
        (reg/v/f:SI 24)) -1 (nil)
    (nil))

(insn 108 101 0 (use (reg/i:SI 0 r0)) -1 (nil)
    (nil))


A non-optimizing translation into SSA form would result in something like this:


(insn/s 92 147 93 (set (reg:SI 30)
        (plus:SI (reg:SI 24)
            (reg/v:SI 27))) -1 (nil)
    (nil))

(jump_insn/s 93 92 124 (set (pc)
        (if_then_else (gtu:CC (reg:SI 30)
                (reg/v/f:SI 25))
            (label_ref 96)
            (pc))) -1 (nil)
    (nil))

(note/s 124 93 95 [bb 1] NOTE_INSN_BASIC_BLOCK 0)

(insn/s 95 124 96 (set (reg:SI 44)
        (plus:SI (reg:SI 24)
            (reg/v:SI 27))) -1 (nil)
    (nil))

(code_label/s 96 95 125 19 "" "" [1 uses])

(note/s 125 96 148 [bb 2] NOTE_INSN_BASIC_BLOCK 0)

(insn/s 148 125 101 (set (reg:SI 45)
        (phi[ 
                (reg:SI 44)
                (const_int 1)
                (reg:SI 24)
                (const_int 0)
            ] )) -1 (nil)
    (nil))

(insn 101 148 108 (set (reg/i:SI 0 r0)
        (reg:SI 45)) -1 (nil)
    (nil))

(insn 108 101 0 (use (reg/i:SI 0 r0)) -1 (nil)
    (nil))

So far so good?

Now note carefully the single insn in block #1.  The value in the RHS is
a redundant computation.  If we implement dominator based optimizations
during conversion to SSA per Morgan's book we'll be able to optimize away
that computation when converting to SSA which would leave us with something
like this instead:

(insn/s 92 147 93 (set (reg:SI 30)
        (plus:SI (reg:SI 24)
            (reg/v:SI 27))) -1 (nil)
    (nil))

(jump_insn/s 93 92 124 (set (pc)
        (if_then_else (gtu:CC (reg:SI 30)
                (reg/v/f:SI 25))
            (label_ref 96)
            (pc))) -1 (nil)
    (nil))

(note/s 124 93 95 [bb 15] NOTE_INSN_BASIC_BLOCK 0)

(note/s 95 124 96 NOTE_INSN_DELETED 0)

(code_label/s 96 95 125 19 "" "" [1 uses])

(note/s 125 96 148 [bb 16] NOTE_INSN_BASIC_BLOCK 0)

(insn/s 148 125 101 (set (reg:SI 44)
        (phi[ 
                (reg:SI 30)
                (const_int 1)
                (reg:SI 24)
                (const_int 0)
            ] )) -1 (nil)
    (nil))

(insn 101 148 108 (set (reg/i:SI 0 r0)
        (reg:SI 44)) -1 (nil)
    (nil))

(insn 108 101 0 (use (reg/i:SI 0 r0)) -1 (nil)
    (nil))

Note how we've deleted insn 95 and twiddled the PHI node at insn 148 to
re-use the value in reg30.

I've racked my brain on this and I'm pretty sure this is still valid code in
SSA form and that it's precisely the kind of transformations the dominator
optimizations are expected to make.

One of the key things to realize here is that block 1 is empty, but it's
still important in the sense that we get two different values for reg 44
depending on whether or not our path is 0->2 or 0->1->2.

Anyway, the aggressive dead code elimination pass fires up.

insn 101 is inherently important (sets the return value).  That causes
insn 148 to be marked as important, which in turn causes insn 92 to
be marked as important.

Note carefully that insn 93 was not marked as important as no blocks which
are control dependent on insn 93 had any important instructions. 

So, we end up with something like this after aggressive dead code elimination:



(insn 92 147 152 (set (reg:SI 30)
        (plus:SI (reg:SI 24)
            (reg/v:SI 27))) -1 (nil)
    (nil))

(jump_insn 152 92 153 (set (pc)
        (label_ref 96)) -1 (nil)
    (nil))

(barrier 153 152 124)

(note 124 153 95 [bb 1] NOTE_INSN_BASIC_BLOCK 0)

(note 95 124 96 NOTE_INSN_DELETED 0)

(code_label 96 95 125 19 "" "" [2 uses])

(note 125 96 148 [bb 2] NOTE_INSN_BASIC_BLOCK 0)

(insn 148 125 101 (set (reg:SI 44)
        (phi[ 
                (reg:SI 30)
                (const_int 1)
                (reg:SI 24)
                (const_int 0)
            ] )) -1 (nil)
    (nil))

(insn 101 148 108 (set (reg/i:SI 0 r0)
        (reg:SI 44)) -1 (nil)
    (nil))


Note that we only have one path to insn 148 now.  That path always selects
the PHI alternative for block 0.  Which, as far as I can see is wrong
(it certainly does the wrong thing for the testcase I'm looking at).



I couldn't find any information on this kind of case in any literature I've
got here.  Has anyone seen anything like this before?  If so, how was it
dealt with?


I see a couple obvious options.  One would be to not remove instructions
during dominator optimizations -- we'd go ahead and generate a new temporary
at insn 95 and assign it the value r30.  The PHI node at insn 148 would
reference that new temporary and when insn 148 was marked important, insn
95 would be marked as important then insn 93 would be marked as important.

The other option would be to have the fast DCE algorithm handle PHI nodes
a little special.  For each alternative, mark the control dependent
edges leading to block associated with the PHI alternative as important.
That would result in basically the same thing happening as we'd consider
block 1 important.  And block 1 is control dependent on insn 93.

I'm not sure which is the better solution.  

Thoughts/comments?

jeff