Compiler Analysis: 3.3, 3.4, or tree-ssa?

Compiler Analysis: 3.3, 3.4, or tree-ssa?

[Scott Robert Ladd]

A couple months ago, I gave a preliminary report on my project to 
analyze the effectiveness of gcc optimizations via an evolutionary 
algorithm. At that time, the responses I received lead me to spend time 
reworking my research code into soemthing a bit more formal and modular.

Where the original framework was gcc and Intel specific, the current 
program is both compiler and platform independent.

Now that I'm ready to publish Acovea (Analysis of Compiler Options Via 
Evolutionary Algorithm), I'm wondering which version of gcc I should 
analyze.

3.3.x is the current release; analyzing it would provide a baseline, but 
any discoveries are unlikely to have much impact on 3.3's development at 
this point.

3.4 is in active development, and is the subject of my current tests. 
I've discovered a number of anomalies and an ICE; I'll report the 
results here as soon the the entire test set is complete.

Should I also analyze tree-ssa, aka 3.5? Is there value in comparing 
results from 3.3, 3.4, and 3.5?

Considered opinions will be appreciated.

..Scott

-- 
Scott Robert Ladd
Coyote Gulch Productions (http://www.coyotegulch.com)
Software Invention for High-Performance Computing

Re: Compiler Analysis: 3.3, 3.4, or tree-ssa?

[Andreas Jaeger]

[-- Attachment #1: Type: text/plain, Size: 1590 bytes --]

Scott Robert Ladd <coyote@coyotegulch.com> writes:

> A couple months ago, I gave a preliminary report on my project to
> analyze the effectiveness of gcc optimizations via an evolutionary
> algorithm. At that time, the responses I received lead me to spend
> time reworking my research code into soemthing a bit more formal and
> modular.
>
> Where the original framework was gcc and Intel specific, the current
> program is both compiler and platform independent.
>
> Now that I'm ready to publish Acovea (Analysis of Compiler Options Via
> Evolutionary Algorithm), I'm wondering which version of gcc I should
> analyze.
>
> 3.3.x is the current release; analyzing it would provide a baseline,
> but any discoveries are unlikely to have much impact on 3.3's
> development at this point.
>
> 3.4 is in active development, and is the subject of my current
> tests. I've discovered a number of anomalies and an ICE; I'll report
> the results here as soon the the entire test set is complete.

3.4 is soon in feature freeze, so it's too late for major changes.

> Should I also analyze tree-ssa, aka 3.5? Is there value in comparing
> results from 3.3, 3.4, and 3.5?

Yes since I see:
- 3.3 as baseline and as platform that is stable
- 3.4 to test what progress has been made already and
- 3.5 as the tree that will hopefully ;-) have fixed everything

Andreas
-- 
 Andreas Jaeger, aj@suse.de, http://www.suse.de/~aj
  SuSE Linux AG, Deutschherrnstr. 15-19, 90429 Nürnberg, Germany
   GPG fingerprint = 93A3 365E CE47 B889 DF7F  FED1 389A 563C C272 A126

[-- Attachment #2: Type: application/pgp-signature, Size: 197 bytes --]

Re: Compiler Analysis: 3.3, 3.4, or tree-ssa?

[Scott Robert Ladd]

Andreas Jaeger wrote:
> 3.4 is soon in feature freeze, so it's too late for major changes.
> 
>> Should I also analyze tree-ssa, aka 3.5? Is there value in
>> comparing results from 3.3, 3.4, and 3.5?
> 
> Yes since I see: - 3.3 as baseline and as platform that is stable -
> 3.4 to test what progress has been made already and - 3.5 as the tree
> that will hopefully ;-) have fixed everything

Sounds good. My reserach has two goals: To give people an idea of the
"best" options for a given version of the compiler, and to find problems
or inconsistencies in gcc. So I'll continue my tests on 3.4, then move
on to tree-ssa and 3.3.

-- 
Scott Robert Ladd
Coyote Gulch Productions (http://www.coyotegulch.com)
Software Invention for High-Performance Computing

Re: Compiler Analysis: 3.3, 3.4, or tree-ssa?

[Gerald Pfeifer]

On Wed, 15 Oct 2003, Andreas Jaeger wrote:
>> Should I also analyze tree-ssa, aka 3.5? Is there value in comparing
>> results from 3.3, 3.4, and 3.5?
> Yes since I see:
> - 3.3 as baseline and as platform that is stable
> - 3.4 to test what progress has been made already and
> - 3.5 as the tree that will hopefully ;-) have fixed everything

Testing tree-ssa may seem a bit pre-mature, given that I haven't been able
to compile my projects (which work fine with GCC 2.95-3.4) for many months
now and that Scott uses heavy C++ as well, IIRC.

Though testing and comparing 3.3 versus 3.4 seems an excellent idea;
in fact, Scott, you may consider using 2.95 as a baseline which is
still better than 3.x in many cases wrt. code generation for my stuff,
surprisingly as that may sound.

And if you could also consider compile time with different optimizations,
say -O1, -O3, and some mix of your choice, that definitely would be
interesting.

Gerald
-- 
Gerald Pfeifer (Jerry)   gerald@pfeifer.com   http://www.pfeifer.com/gerald/

Re: Compiler Analysis: 3.3, 3.4, or tree-ssa?

[Scott Robert Ladd]

Gerald Pfeifer wrote:
> Testing tree-ssa may seem a bit pre-mature, given that I haven't been able
> to compile my projects (which work fine with GCC 2.95-3.4) for many months
> now and that Scott uses heavy C++ as well, IIRC.

I've had some trouble with tree-ssa as well, although I haven't used it 
very much. I'm really looking forward to the Fortran 95.

I do both C and C++, although my work tends toward the object-oriented 
end of the spectrum. My benchmarks are both C and C++, including some 
tests written in both languages (i.e., the FFT benchmark uses 
complex<double> for C++ and the instrinsic double complex for C).

> Though testing and comparing 3.3 versus 3.4 seems an excellent idea;
> in fact, Scott, you may consider using 2.95 as a baseline which is
> still better than 3.x in many cases wrt. code generation for my stuff,
> surprisingly as that may sound.

I'll build and install 2.95.3, and add it to the test suite. I assume 
there's no real reason to look at 3.0.x, 3.1.x, or 3.2.x?

> And if you could also consider compile time with different optimizations,
> say -O1, -O3, and some mix of your choice, that definitely would be
> interesting.

That's another direction. I'm also trying to develop an accuracy test.

-- 
Scott Robert Ladd
Coyote Gulch Productions (http://www.coyotegulch.com)
Software Invention for High-Performance Computing

Re: Compiler Analysis: 3.3, 3.4, or tree-ssa?

[Joe Buck]

Scott Robert Ladd <coyote@coyotegulch.com> writes:
> > Now that I'm ready to publish Acovea (Analysis of Compiler Options Via
> > Evolutionary Algorithm), I'm wondering which version of gcc I should
> > analyze.

On Wed, Oct 15, 2003 at 07:18:53PM +0200, Andreas Jaeger wrote:
> 3.4 is soon in feature freeze, so it's too late for major changes.

Right, but if Scott should discover that, say, a different combination of
-f options in -O2 would be significantly better, it seems that this would
be a low-risk change that still could be accepted.

Re: Compiler Analysis: 3.3, 3.4, or tree-ssa?

[Falk Hueffner]

Scott Robert Ladd <coyote@coyotegulch.com> writes:

> A couple months ago, I gave a preliminary report on my project to
> analyze the effectiveness of gcc optimizations via an evolutionary
> algorithm. At that time, the responses I received lead me to spend
> time reworking my research code into soemthing a bit more formal and
> modular.

Interestingly, I did something similar just this week. My attempt was
pretty half-assed though, just a small Python script. In each
generation, it keeps the best 16 and creates 16 new by crossover of
two random others. The genome is based only on bits, which is also not
so great, because I end up with stuff like "-mmemory-latency=12
-mmemory-latency=256 -mmemory-latency=3". Still, I got some
interesting results, e. g., all of the fittest individuals have
"-mno-bwx", which for this test case (gzip) is probably the option I
would have bet to have the *worst* possible effect (it turns off byte
access instructions on Alpha). Overall, I could improve run time on my
gzip test case from 10s at -O3 to 9.3s.

I tried the tree-ssa branch; I also got lots of ICEs, especially with
-fnew-ra (but that was already filed long ago), and when combining
-fno-expensive-optimizations with disabling loop optimizations
(PR12628).

Is your framework available somewhere? I'd be interested in comparing
the methods...

-- 
	Falk

Re: Compiler Analysis: 3.3, 3.4, or tree-ssa?

[Scott Robert Ladd]

Falk Hueffner wrote:
> Interestingly, I did something similar just this week. My attempt was
>  pretty half-assed though, just a small Python script. In each 
> generation, it keeps the best 16 and creates 16 new by crossover of 
> two random others. The genome is based only on bits, which is also 
> not so great, because I end up with stuff like "-mmemory-latency=12 
> -mmemory-latency=256 -mmemory-latency=3".

My Acovea framework is written in C++; I began working on it early this
year, in my spare time.

Until two months ago, I, too, was using bit-strings to represent 
compiler option sets. That proved inadequate, considering that some 
options have numeric values, while other can have several specific 
states (e.g., -mfpmath=387, -mfpmath=sse, and -mfpmath=sse,387). I found 
a combination of polymorphism and templates to provide the most 
flexibility and functional coverage.

At the moment, I'm testing combinations of approximately 50 different
options. I can test with and without certain option sets; for example,
most of my current runs avoid any options implied in
-ffast-math, since those options tend to mask the effects of other
optimizations.

Once I have the runtime "speed" tests complete, I'll work on my accuracy
test, then (given time) on a compile-time optimization. The framework 
should be capable of handling different goals. In essence, Acovea solves 
a minimization problem, a task well-suited to evolutionary analysis.

> Still, I got some interesting results, e. g., all of the fittest 
> individuals have "-mno-bwx", which for this test case (gzip) is 
> probably the option I would have bet to have the *worst* possible 
> effect (it turns off byte access instructions on Alpha). Overall, I 
> could improve run time on my gzip test case from 10s at -O3 to 9.3s.

I've been able to identify improvements over -O3 (and -O2 and -O1) of up
to 40%. Note that most of my early tests involve floating-point
intensive code, given that my work often requires number crunching. I'm
testing other benchmarks (bit-twiddling, test processing, etc.) at the
moment.

The initial tests focus on Pentium systems, since those are what I have
at hand. Once I get the first cut published, I'll expand into other
processors (SPARC, as I have the hardware, and AMD if I can procure the
hardware) and languages other than C and C++ (GNU Fortran 95, for example).

> Is your framework available somewhere? I'd be interested in comparing
>  the methods...

The ACOVEA framework is code and concept complete, and in testing
even as we speak. If testing goes well, I'll release the code in the
next week or so.

-- 
Scott Robert Ladd
Coyote Gulch Productions (http://www.coyotegulch.com)
Software Invention for High-Performance Computing

Re: Compiler Analysis: 3.3, 3.4, or tree-ssa?

[Gerald Pfeifer]

On Thu, 16 Oct 2003, Scott Robert Ladd wrote:
> I'll build and install 2.95.3, and add it to the test suite. I assume
> there's no real reason to look at 3.0.x, 3.1.x, or 3.2.x?

According to my tests 3.0-3.0.2 were extremely bad in terms of compile-
time performance for C++, 3.0.3->3.2.3 went relatively monotonic though
code quality improved slightly.

I think the selection you're currently using makes most sense, and I'm
definitely looking forward to your paper!

Gerald

Re: Compiler Analysis: 3.3, 3.4, or tree-ssa?

[Scott Robert Ladd]

tm_gccmail@kloo.net wrote:
> IMHO, it will be more efficient to determine the optimization problem in
> the compiler and fix it, instead of requiring everyone to waste CPU cycles
> by running a genetic optimizer.

Agreed. I'm looking at this as a general testing and optimization tool 
for *applications*, at the same level of development as unit testing and 
profiling.

That Acovea may also useful in making GCC a better compiler is 
serendipitous.

> This isn't meant to denigrate your optimizer; it's merely to point out
> that it's most useful as a compiler development tool to identify
> optimization problems rather than as a end-user optimization tool.

The genetic algorithm is entirely impractical as a component of the 
compiler, and I don't intend it as such.

The original concept grew out of my published benchmarks; people kept 
telling me to use such-and-such options that often did little or nothing 
to improve performance. I wanted to *know* which options generated the 
fastest code. Acovea gives me that knowledge.

As the genetic algorithm evolved over the last year, I've found it 
useful in other ways -- such as in verifying the interactions of 
optimization algorithms. Algorithms may not necessarily be broken just 
because they pessimize code, and certain optimizations may conflict in 
combination; GCCis, after all, a complex system (in the mathematical sense).

> The problem is that you're using this tool to identify the problem, then
> avoid it. What we should be doing with it is to identify the problem and
> fix it.

No, I'm using the tool to find the best set of optimizations for a given 
performance-critical section of code. My framework identifies 
pessimistic options for a given piece of code, and produces option sets 
that produce substantially faster code than any -On option.

Yes, this may be because of a bug in GCC -- or, it could simply be 
because a given piece of code is well-suited to a select group of 
optimization algorithms.

Another note: This tool is not designed just for gcc; it works with any 
language or compiler. While it certainly can find bugs and problems in a 
specific compiler -- like GCC -- it is designed for other purposes as 
well. For example, a GA can be quite illuminating in selecting 
variations on algorithms, buffer sizes, inline limits -- the list goes 
on and on.

> If you can send me the source code and the resultant assembly code for the
> "slow" and "fast" compiler options, I will take a look at it.

I'm doing this on my own time as quickly as I can. The test cases and 
framework are finished and tested; I'll spend tomorrow polishing my 
paper on the topic, and people can then decide how it fits with their 
own goals.

-- 
Scott Robert Ladd
Coyote Gulch Productions (http://www.coyotegulch.com)
Software Invention for High-Performance Computing

Re: Compiler Analysis: 3.3, 3.4, or tree-ssa?

[tm_gccmail]

On Sat, 18 Oct 2003, Scott Robert Ladd wrote:

> Matt Fago wrote:
> >> The -O1, -O2, and -O3 options are general-purpose choices for 
> >> producing good code in general circumstances.
> > 
> > Are they? How is this determined?
> 
> I'll amend my statement...
> 
> "The -O1, -O2, and -O3 options *SHOULD BE* general-purpose choices for 
> producing good code in general circumstances."
> 
> > I think Acovea might allow the flags implied by these options to be 
> > chosen in a more quantitative way. Obviously Acovia should give better 
> > results when used with a specific code of interest.
> 
> I note that on some experiments, -O2 and -O3 produce *slower* code than 
> does -O1; and in several cases, Acovea finds options sets that produce 
> code which runs in 40% less time than it does when compiled with any of 
> the predefined optimization sets.
>
> We could define variations on the -O?? theme... -Ofp, for example, that 
> optimizes for floating-point applications.

IMHO, it will be more efficient to determine the optimization problem in
the compiler and fix it, instead of requiring everyone to waste CPU cycles
by running a genetic optimizer.

This isn't meant to denigrate your optimizer; it's merely to point out
that it's most useful as a compiler development tool to identify
optimization problems rather than as a end-user optimization tool.

The problem is that you're using this tool to identify the problem, then
avoid it. What we should be doing with it is to identify the problem and
fix it.

So, I hereby reextend my offer to lend my code analysis skills to peruse
your testcases (and the outputs thereof) to identify the compiler problems
which result in slower code at -O2 and -O3 optimization levels.

If you can send me the source code and the resultant assembly code for the
"slow" and "fast" compiler options, I will take a look at it.

Toshi

Re: Compiler Analysis: 3.3, 3.4, or tree-ssa?

[Scott Robert Ladd]

Matt Fago wrote:
>> The -O1, -O2, and -O3 options are general-purpose choices for 
>> producing good code in general circumstances.
> 
> Are they? How is this determined?

I'll amend my statement...

"The -O1, -O2, and -O3 options *SHOULD BE* general-purpose choices for 
producing good code in general circumstances."

> I think Acovea might allow the flags implied by these options to be 
> chosen in a more quantitative way. Obviously Acovia should give better 
> results when used with a specific code of interest.

I note that on some experiments, -O2 and -O3 produce *slower* code than 
does -O1; and in several cases, Acovea finds options sets that produce 
code which runs in 40% less time than it does when compiled with any of 
the predefined optimization sets.

We could define variations on the -O?? theme... -Ofp, for example, that 
optimizes for floating-point applications.

-- 
Scott Robert Ladd
Coyote Gulch Productions (http://www.coyotegulch.com)
Software Invention for High-Performance Computing

Re: Compiler Analysis: 3.3, 3.4, or tree-ssa?

[Matt Fago]

Scott Robert Ladd wrote:

> The -O1, -O2, and -O3 options are general-purpose choices for producing 
> good code in general circumstances.

Are they? How is this determined?

I think Acovea might allow the flags implied by these options to be 
chosen in a more quantitative way. Obviously Acovia should give better 
results when used with a specific code of interest.

Good luck this weekend. I look forward to trying Acovia on my thesis 
research code (and will happily cite your paper).


  - Matt

Re: Compiler Analysis: 3.3, 3.4, or tree-ssa?

[Scott Robert Ladd]

Matthew Fago wrote:
> However, its application to optimize (on "average") the default -O? flags
> is much more generally beneficial. I would also love to use it in my
> upcoming work on the "-farch-auto" flag.
> 
> This latter class of work requires a standard set of representative code.
> Does such a collection already exist?

I do not think a "representative" code base exists, nor do I believe
such a beast *can* exist. Programming styles, languages, and 
applications differ too much to define an "average" program. If 
anything, Acovea is proving that point; I'm finding that two 
similar-seeming programs can have very different optimization requirements.

The -O1, -O2, and -O3 options are general-purpose choices for producing 
good code in general circumstances. Acovea is, in its current form, a 
tool for refinement.

I'm using profiling to identify performance-critical code, then applying 
Acovea to find the options that produce the fastest code for that 
target. I'm thinking of this as another form of unit testing.

A future version will examine the way options affect accuracy, assuming 
I can ever settle on an accuracy benchmark. I might look into compile 
speed, too, as a tool for analyzing gcc's performance.

I'm still deciding which benchmarks to use for the initial release and 
paper. Assuming all the ducks quack this weekend, I'll have them in a 
row for publication early next week. Then everyone can kibbitz what I've 
done...

... although I may learn what it feels like to be nibbled to death by ducks.

Quack.

..Scott (who's had far too little sleep and much too much caffiene)

-- 
Scott Robert Ladd
Coyote Gulch Productions (http://www.coyotegulch.com)
Software Invention for High-Performance Computing

Re: Compiler Analysis: 3.3, 3.4, or tree-ssa?

[Matthew Fago]

The usefulness of this tool is clear for optimizing the compilation of a
specific code. For example, a set of flags for SPEC (anyone have the
time?) ...

However, its application to optimize (on "average") the default -O? flags
is much more generally beneficial. I would also love to use it in my
upcoming work on the "-farch-auto" flag.

This latter class of work requires a standard set of representative code.
Does such a collection already exist?

Thanks Scott!


- Matt