two-element struct performance (was: strict-aliasing and typedefs)

[law@redhat.com]

In message <20030514152914.A12355@synopsys.com>, Joe Buck writes:
 >On Thu, May 15, 2003 at 12:16:56AM +0200, Gabriel Dos Reis wrote:
 >> Joe Buck <jbuck@synopsys.com> writes:
 >> 
 >> | GCC does a decent job with one-element structs; its performance
 >> | quickly drops like a rock as soon as there are two elements.  Still,
 >> | there may well be some loss from using it.
 >> 
 >> Would that loss of performance be related to ABI issues (in single
 >> element case)? 
 >
 >No, it has to do with premature commitment of structs to memory.  The only
 >way out is to be able to do more aggressive transformations on trees, to get
 >rid of structs that aren't needed.  For the one-element case, there are some
 >special-case tricks, which give us a nice (but misleading) Stepanov
 >abstraction penalty score.  Every object in the Stepanov benchmark has one
 >element.
 >
 >Actually there's another way out: be able to treat aggregates as scalars.
 >However, it seems this isn't really needed for many of the cases that hurt
 > C++ performance (e.g. iterators with more than one element).
 >
 >Take a look, for example, at the code generated for the following:
 >
 >--------------------------------
 >struct complex {
 >    double re, im;
 >    complex(double r, double i) : re(r), im(i) {}
 >};
 >
 >inline complex operator+(const complex& a, const complex& b) {
 >    return complex(a.re+b.re, a.im+b.im);
 >}
 >
 >complex addone(const complex& arg) {
 >    return arg + complex(1,0);
 >}
 >------------------------------
 >
 >It's pretty horrific, because gcc insists on making an actual RAM object
 > for the temporary struct (even for tree-ssa).
 >
 >>From looking at the tree dumps on the tree-ssa branch, it would seem that a
 >decent copy propagation pass could propagate the 1.0 and 0.0 values through,
 >leaving the temporary struct as a dead object.
We're getting closer, but we're not quite there yet.

As of this morning we got the following at the end of DCE2:

  this<D1518>_1 = &<D1509>;
  this<D1518>_1->re = 1.0e+0;
  this<D1518>_1->im = 0.0;
  b<D1523>_6 = &<D1509>;
  T.0<D1526>_7 = arg<D1506>_4->im;
  T.1<D1527>_8 = b<D1523>_6->im;
  T.2<D1528>_9 = T.0<D1526>_7 + T.1<D1527>_8;
  T.3<D1529>_10 = arg<D1506>_4->re;
  T.4<D1530>_11 = b<D1523>_6->re;
  T.5<D1531>_12 = T.3<D1529>_10 + T.4<D1530>_11;
  this<D1533>_13 = &<D1525>;
  this<D1533>_13->re = T.5<D1531>_12;
  this<D1533>_13->im = T.2<D1528>_9;
  retval.7<D1532> = <D1525>;
  T.6<D1513> = retval.7<D1532>;
  return T.6<D1513>;


Egad.  How in the world are we supposed to get good code from that mess.
That's AWFUL.


Of particular interest is the fact that this_1 and this_13 are totally
unnecessary -- we should have const-propagated the address of D1509
and D1525 in all uses of this_1 and this_13.

It turns out there's a couple minor oversights in the dominator optimizer
which are preventing that constant propagation.  Fixing those leads to the
following code out of DCE2:

  <D1509>.re = 1.0e+0;
  <D1509>.im = 0.0;
  b<D1523>_6 = &<D1509>;
  T.0<D1526>_7 = arg<D1506>_4->im;
  T.1<D1527>_8 = b<D1523>_6->im;
  T.2<D1528>_9 = T.0<D1526>_7 + T.1<D1527>_8;
  T.3<D1529>_10 = arg<D1506>_4->re;
  T.4<D1530>_11 = b<D1523>_6->re; 
  T.5<D1531>_12 = T.3<D1529>_10 + T.4<D1530>_11;
  <D1525>.re = T.5<D1531>_12;
  <D1525>.im = T.2<D1528>_9;
  retval.7<D1532> = <D1525>;
  T.6<D1513> = retval.7<D1532>;
  return T.6<D1513>;


Which is marginally better.    It allows us to generate slightly
better code during tree->rtl conversion and avoid creating a useless
stack object.  In terms of the final assembly code we just reduced the
stack allocation for that function from 56 bytes to 40 bytes.  Nothing
to write home about, but it's a start.

However, if we look at the DCE2 output even closer, we'll see that there's
still a constant propagation opportunity we're missing.  Namely b = &<D1509>.
This is simply a matter of the dominator optimizer playing it too safe
regarding types.  Fix that results in the following code after DSE2:


  T.0<D1526>_7 = arg<D1506>_4->im;
  T.2<D1528>_9 = T.0<D1526>_7 + 0.0;
  T.3<D1529>_10 = arg<D1506>_4->re;
  T.5<D1531>_12 = T.3<D1529>_10 + 1.0e+0;
  T.6<D1513>.re = T.5<D1531>_12;
  T.6<D1513>.im = T.2<D1528>_9;
  return T.6<D1513>;



Which is looking much better -- the constants are propagated in the manner
we want and the resulting assembly code looks quite a bit nicer too.
It's also much cleaner from an aliasing standpoint, so there may be
secondary effects if this code were inlined into some other function.

Doing better would require that the tree-ssa optimizers know about ABI
details for passing parameters and return values -- if it had that knowledge
then it would know that the caller will provide a suitable memory location
for the return value and we could use it directly instead of first building
the return value in T.6.

Anyway, I'll be testing those changes today/tomorrow.  It'll be interesting to
see if/how they affect other C++ code.

jeff