pr14627

[Jeffrey A Law <law at redhat dot com>]

This patch implements an const/copy unpropagation pass.

The SSA optimizers try to const/copy propagate values to the fullest
extent possible.  This includes equivalences created by following edges
in the CFG.  For example



int b; 
void foo (int a) { 
        if (a) 
                a = 3; 
        b = a; 
} 


Conversion into SSA results in:


;; Function foo (foo)

foo (a)
{
  # BLOCK 0
  # PRED: ENTRY (fallthru)
  if (a_2 != 0) goto <L0>; else goto <L1>;
  # SUCC: 1 (true) 2 (false)

  # BLOCK 1
  # PRED: 0 (true)
<L0>:;
  a_5 = 3;
  # SUCC: 2 (fallthru)

  # BLOCK 2
  # PRED: 0 (false) 1 (fallthru)
  # a_1 = PHI <a_2(0), a_5(1)>;
<L1>:;
  #   b_4 = V_MUST_DEF <b_3>;
  b = a_1;
  return;
  # SUCC: EXIT

}

There's two constant propagation opportunities here.  The obvious one
constant propagating 3 anywhere a_5 is used.  The second one is more
subtle.  When the first conditional is false we know that a_2 will
have the value zero.  Thus we know the use of a_2 in the PHI node
at the start of block #2 must have the value zero.

After propagation we have:


;; Function foo (foo)

foo (a)
{
  # BLOCK 0
  # PRED: ENTRY [100.0%]  (fallthru,exec)
  if (a_2 != 0) goto <L1>; else goto <L2>;
  # SUCC: 2 [67.0%]  (true,exec) 1 [33.0%]  (false,exec)

  # BLOCK 1
  # PRED: 0 [33.0%]  (false,exec)
<L2>:;
  # SUCC: 2 [100.0%]  (fallthru,exec)

  # BLOCK 2
  # PRED: 1 [100.0%]  (fallthru,exec) 0 [67.0%]  (true,exec)
  # a_1 = PHI <0(1), 3(0)>;
<L1>:;
  #   b_4 = V_MUST_DEF <b_3>;
  b = a_1;
  return;
  # SUCC: EXIT [100.0%] 

}


Which is precisely what we should expect.

The problem is propagation of constants into the PHI node did not
actually help optimization in this example.  Furthermore, the out-of-ssa
pass must insert the proper constant initializations to remove the
PHI node.  This results in the assignment a = 0 being placed on the
edge from block #1 to block #2 and the assignment a = 3 being placed
on the edge from block #0 to block #2.

The assignment a = 3 isn't really a concern as there's simply no way
to avoid it.  However it's not terribly difficult to see that the
assignment a = 0 is actually not necessary.  In many cases the RTL
optimizers will be unable to eliminate these constant initializations
which resulted from this kind of code.

We've had a very quick and dirty pass which tried to clean this kind
of stuff up which did an OK job.  However, some time ago I wrote a much
more effective pass, and I finally got around to tidying up a few warts
and testing it....

The basic idea behind the pass is to reverse the actions of DOM before
we go out of SSA form.  This allows us to get the benefit of propagating
constants and copies to the fullest extent possible and still be able
to undo the propagation later (and thus avoid the useless statements).

The pass basically records reverse equivalences created by conditionals
and switch statements.  It then looks at PHI node arguments which are
either constants or which have a different underlying _DECL node than
the PHI result (both cases will always require a emission of a statement
to eliminate the PHI during out-of-ssa translation).  When such PHI
arguments are found, we lookup the value of the argument in our table
and see if we can find a suitable SSA_NAME which is known to contain the
right value.  If so, we replace the argument with the more useful
SSA_NAME we found in our tables.

This new code is quite a bit better than the old remove_useless_stmts
hack, though it is slightly slower (net slowdown is on the order of
.25%)

Bootstrapped and regression tested on i686-pc-linux-gnu.  Also verified
that it gives the desired code for the PR in question and verified that
it was giving overall better code by looking at the sizes of various
.o files with and without the patch.

Attachment: PPP
Description: Text document