[tree-ssa] copy propagation and the abstraction penalty

[Joe Buck]

On Thu, May 15, 2003 at 10:10:22AM -0400, Diego Novillo wrote:

> There's a few bits still missing, but we should be getting there.  In
> this particular testcase I see:
> 
>       * Structures.  We only build enough SSA links to prove liveness. 
>         Two alternatives to dealing with this is using ESSA from the
>         SSAPRE engine and/or rely on a scalarization pass.

Since this is the absolutely most common defect in our current C++
compiler, it seems worth trying to tune optimization to solve it directly,
rather than trying to solve a harder, more general problem.

If copy propagation can store the content of individual structure fields,
then it seems that you don't need the rest of scalarization.

>       * Aliasing.  Our default type-based aliasing mechanism gets all
>         tangled up (it's really naive):

I think that the aliasing problem can be finessed.

Again, generalized copy propagation would appear to solve this without
solving any aliasing problem: replace pointers to known addresses by the
addresses.  Even stupid aliasing, that kills everything on the first
pointer write, still can win if this is done.

Let me step through this to show how it might work.

;; Function complex addone(const complex&) (_Z6addoneRK7complex)

complex addone(const complex&) (arg)
{
  struct complex retval.12;
  struct complex <UVa150>;
  struct complex * T.8;
  struct complex * T.9;
  struct complex & T.10;
  struct complex T.11;

  {
    T.8_2 = &<UVa150>;
    {
      double i;
      double r;
      struct complex * const this;

      this_3 = (struct complex * const)T.8_2;

Here this_3 is &<UVa150> (copy prop).

      r_5 = 1.0e+0;
      i_6 = 0.0;
      {
        this->re = 1.0e+0;

This is presumably this_3.  Now we know that UVa150.re is 1.0e+0.
(That is, we track fields of local structs, as part of copy propagation).

        this->im = 0.0;

Now we know that Uva150.im is 0.0.  We do need to care about aliasing, but
that means that we might have invalidate the value of these fields if we
get a write through a pointer that might alias UVa150.  This program has
no pointer writes at all, though.

I think that even a very simple-minded approach that discards all stored
structure field values on the first indirect write would still show huge
gains, because these temporary structs are often live for an extremely
short distance (they just pass information across an inlined call).

      }
    };
    T.9_9 = &<UVa150>;
    T.10_10 = (struct complex &)T.9_9;

T.10_10 is &<Uva150>.

    {
      struct complex & b;
      struct complex <UVa770>;

      b_11 = T.10_10;

b_11 is &<Uva150>.

      {
        struct complex * T.1;
        double T.2;
        double T.3;
        double T.4;
        double T.5;
        double T.6;
        double T.7;

        {
          T.1_13 = &<UVa770>;
          T.2_15 = arg->re;
          T.3_16 = b->re;

T.3_16 is (&<UVa150>)->re, or UVa150.re, or 1.0.

          T.4_17 = T.2_15 + T.3_16;
          T.5_18 = arg->im;

T.5_18 is (&<UVa150>)->im, or UVa150.im, or 1.0.
After doing this substitution, UVa150 is dead, and we can kill it.

          T.6_19 = b->im;
          T.7_20 = T.5_18 + T.6_19;
          {
            double i;
            double r;
            struct complex * const this;

            this_21 = (struct complex * const)T.1_13;
            r_23 = T.4_17;
            i_24 = T.7_20;
            {
              this->re = T.4_17;
              this->im = T.7_20;
            }
          };
        }
      };
      retval.12_27 = <UVa770>
    };
    T.11_28 = retval.12_27;
    return retval.12_27;
  }
}