Optimization advice for maintainers: go for low-hanging fruit

Optimization advice for maintainers: go for low-hanging fruit

[Martin Buchholz]

I've been staring at a lot of g++-generated x86 assembler, trying to
coax g++ into creating better code, and creating a bunch of
optimization-related PRs.  Overall, I'm disappointed by gcc's ability
to optimize some very simple things like constant-folding.

The most distressing thing about the failures is that gcc is
invariably capable of performing all the optimizations I care about,
just not consistently.  Seemingly irrelevant random features of the
source code seem to inhibit optimizations from being performed.

My suggestion for improving gcc's object code is not to add ever more
clever optimization passes, but simply to concentrate on making sure
that existing optimizations are applied everywhere they can be - not a
sexy job, certainly, but very likely low-hanging fruit.

My guess is that past maintainers, in a hurry to fix code generation
bugs, have fixed bugs "the wrong way" and thus disabled optimizations
in some paths through the code.

c++/8936: Declaration of never defined member function changes generated code
optimization/8952: failure to optimize away trivial C++ object creation
optimization/8967: Making class data members `const' pessimizes code
optimization/9016: Failure to consistently constant fold "constant" C++ objects

Martin

Re: Optimization advice for maintainers: go for low-hanging fruit

[Jan Hubicka]

> I've been staring at a lot of g++-generated x86 assembler, trying to
> coax g++ into creating better code, and creating a bunch of
> optimization-related PRs.  Overall, I'm disappointed by gcc's ability
> to optimize some very simple things like constant-folding.
> 
> The most distressing thing about the failures is that gcc is
> invariably capable of performing all the optimizations I care about,
> just not consistently.  Seemingly irrelevant random features of the
> source code seem to inhibit optimizations from being performed.

Can you send some testcases where GCC fails to do the transformation?

Honza

Re: Optimization advice for maintainers: go for low-hanging fruit

[Dan Nicolaescu]

Jan Hubicka <jh@suse.cz> writes:

  > > I've been staring at a lot of g++-generated x86 assembler, trying to
  > > coax g++ into creating better code, and creating a bunch of
  > > optimization-related PRs.  Overall, I'm disappointed by gcc's ability
  > > to optimize some very simple things like constant-folding.
  > > 
  > > The most distressing thing about the failures is that gcc is
  > > invariably capable of performing all the optimizations I care about,
  > > just not consistently.  Seemingly irrelevant random features of the
  > > source code seem to inhibit optimizations from being performed.
  > 
  > Can you send some testcases where GCC fails to do the transformation?

Look at the audit trail for PR8967, the example there shows that life
analysis fails to eliminate some insns in one case. 

Also please take a look at PR9016, the 4 functions in that generate
the same (optimal) assembly on SPARC, but some of them don't get
optimized well on x86. 

Re: Optimization advice for maintainers: go for low-hanging fruit

[Joe Buck]

On Thu, Dec 19, 2002 at 10:12:49PM -0800, Martin Buchholz wrote:
> I've been staring at a lot of g++-generated x86 assembler, trying to
> coax g++ into creating better code, and creating a bunch of
> optimization-related PRs.  Overall, I'm disappointed by gcc's ability
> to optimize some very simple things like constant-folding.

Many of the bugs you point out are well-known, and are due to
architectural problems: structs and classes are committed to memory too
early, and RTL doesn't know about a struct or class, only about memory
locations.  The result is that suboptimal code is generated and the
later passes of the compiler are too dumb to clean it up.  Currently
GCC does reasonably well for one-element structs and classes, and
generates rather bad code when there is more than one element (as in
your Complex example).  I first complained about your PR 8952 about seven
years ago, maybe more.

Many of us believe that tree-based optimizations can be the way out for
many of these cases: do optimizations that are easy on trees well before
conversion to RTL.  Work is in progress to provide an infrastructure
that will allow this to be done.

> My suggestion for improving gcc's object code is not to add ever more
> clever optimization passes, but simply to concentrate on making sure
> that existing optimizations are applied everywhere they can be - not a
> sexy job, certainly, but very likely low-hanging fruit.

If it were that easy, it would be done by now.  People have been pointing
out these problems for years, and no one has managed to fix them.
Unfortunately, the fruit is not as low-hanging as it appears.  With tree
optimizations, things should be easier.  Same if the compiler had the
ability to "scalarize" temporary structs/classes in the general case
(it doesn't).

> My guess is that past maintainers, in a hurry to fix code generation
> bugs, have fixed bugs "the wrong way" and thus disabled optimizations
> in some paths through the code.
> 
> c++/8936: Declaration of never defined member function changes generated code
> optimization/8952: failure to optimize away trivial C++ object creation
> optimization/8967: Making class data members `const' pessimizes code
> optimization/9016: Failure to consistently constant fold "constant" C++ objects

Some of the oddities you point out seem to come from the fact that
subsequent passes of the compiler seem to succeed in doing optimizations
only sometimes, and that conditions for these passes to work (e.g. dead
store elimination) are rather brittle.  It would certainly be interesting
to determine just what is different in cases 8936 and 8967.

-- 
Q. What's more of a headache than a bug in a compiler.
A. Bugs in six compilers.  -- Mark Johnson

Re: Optimization advice for maintainers: go for low-hanging fruit

[Martin Buchholz]

>>>>> "J" == Joe Buck <jbuck@synopsys.com> writes:

>> c++/8936: Declaration of never defined member function changes generated code
>> optimization/8952: failure to optimize away trivial C++ object creation
>> optimization/8967: Making class data members `const' pessimizes code
>> optimization/9016: Failure to consistently constant fold "constant" C++ objects

J> Some of the oddities you point out seem to come from the fact that
J> subsequent passes of the compiler seem to succeed in doing optimizations
J> only sometimes, and that conditions for these passes to work (e.g. dead
J> store elimination) are rather brittle.  It would certainly be interesting
J> to determine just what is different in cases 8936 and 8967.

Some of those bugs are regressions from previous g++ versions, showing
that g++ can certainly do a better job without massive infrastructure work.
For example, Wolfgang's experiments with PR8967 shows things getting
worse with successive g++ versions.

J> Many of us believe that tree-based optimizations can be the way out for
J> many of these cases: do optimizations that are easy on trees well before
J> conversion to RTL.  Work is in progress to provide an infrastructure
J> that will allow this to be done.

Another argument for why I expect g++ to do better today:

A clever C++ compiler can figure out that an expression like 

Complex(1,2) 

is a compile-time constant and optimize appropriately at
compile-time.  But semantically, this is equivalent to

double real = 1.0;
double imag = 2.0;

which a C compiler can do constant-folding on, probably just as well
as C++.

From a very high level, I regard a C++ front end's job as translating
C++ into something semantically very close to C code.  Although there
may be additional opportunities for optimization by understanding and
optimizing C++ constructs, the meat of the optimizations should be
occuring at the "C level".

For example, if a C++ compiler sees

Complex(1,a) + Complex(2,b)

it shouldn't say "no constants here, so no constant-folding here."
Instead, there should be constant-folding on the real parts of those
Complex variables, just as if it had been written in C using variables
of type "double".

So I'm still a believer in the value of low-level optimizations,
ones that don't know about higher-level things like classes.

Martin (not a compiler writer)