Re: Question re: SSA Aggressive Dead Code Elimination

[Diego Novillo <dnovillo at redhat dot com>]

On Tue, 26 Jun 2001, Jeff Law wrote:

> (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?
> 
Yup.

> 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:
> 
Why?  SSA analysis should not munge the program.  Convert to SSA
and then let PRE and/or partial DCE do their magic.  Or did you
mean that?

> (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.
> 
This is the root of the problem.  We should have never decided to
remove insn 95.  The instruction is only *partially* redundant.
IMO, we should do a clean SSA conversion first and then go on
with the transformations.  Running PRE in this case would've
moved the partially redundant computation in insn 95 above the if
statement.

Let me rewrite this in p-code (I can't think straight in RTL,
sorry):

      Original			SSA 1
                            (unoptimized)

 92: r30 = r24 + r27	 92: r30 = r24 + r27
 93: if (r30 > r25)	 93: if (r30 > r25)
      goto 96		        goto 96
 95: r24 = r24 + r27	 95: r44 = r24 + r27
 96:                     96:
             		148: r45 = phi(r44, r24)
101: r0 = r24		101: r0 = r45
108:    = r0            108:    = r0


Now, in the optimized SSA, you say that since the RHS is
redundant we can optimize it away.  Yes, 'r24 + r27' is
redundant, but setting r44 is *not* redundant.  We cannot
optimize the whole instruction away because r44 is used by the
phi term in instruction 148.

  SSA 2
(optimized)

 92: r30 = r24 + r27
 93: if (r30 > r25)
        goto 96
 95: [ deleted ]
 96:
148: r44 = phi(r30, r24)
101: r0 = r44
108:    = r0

The semantics of this version are different from the original.
In this version, the phi term at 148 is trivially dead.  The
definition for r24 is postdominated by r30.  This gives you a phi
term of only one term, which can be removed.  The problem started
when we killed insn 95.

Also the phi term for r44 is no longer at a dominance frontier of
any defining node (block #1 has been optimized away).

> 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.
>
An empty node should never be important (with minor exceptions
such as landing zones and whatnot).

At most, the optimized SSA form could look like this:

 92: r30 = r24 + r27
109: r45 = r30
 93: if (r30 > r25)
        goto 96
 95: r44 = r45
 96:
148: r45 = phi(r30, r44)
101: r0 = r45
108:    = r0

Later on, copy-prop followed by dead-code would remove insn 109.

> 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. 
> 
Which is the right decision.  But at this point, all our premises
are wrong alreday.

> 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).
> 
Again, deleting insn 95 got the snowball rolling.  All the
transformations following that look correct.

> 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.
> 
Yes.  The error was removing a computation that was only
partially redundant.


Diego.