Re: Optimization techniques

On Wed, 17 Apr 2019 09:42:21 -0400 (EDT), "Rick C. Hodgin"
<rick.c.hodgin@gmail.com> wrote:


>Are there resources someone can point me to for learning more about
>time-honored, long-established, safely applied, optimization
>techniques for a C/C++ like language?


There really aren't many "safe" optimizations you can do before you
run into pointer aliasing problems in C. Almost any modern compiler
text will cover the bulk of them.


The "Dragon" books by Aho & Sethi (and others) are very good ... I
have a couple of them ... but my favorite intro book is:


    Cooper & Torczon, "Engineering a Compiler", Morgan Kaufman


I have the 1st edition. There is a 2nd edition now. Very well written
and quite advanced for an introduction.




There are a lot of good intro level compiler texts. I suggest you
find one that you think is easy to read. The writing style is as
important to your learning as what information is presented.




>I'm walking the abstract syntax tree and am able to find many kinds of
>optimizations, but I would like to learn some theory or pitfalls of
>various types of optimizations applied.
>
>Thank you in advance.


If you are seriously interested, I'd like to suggest:


    Allen & Kennedy, "Optimizing Compilers for Modern Architectures",
        Academic Press, 2002.


Be aware that this book may be rough sledding. Most performance
optimizations have their roots in *Fortran* - not C - and this book
deals with high performance Fortran. Once you understand what they
are doing, it's not terribly hard to figure out how you'd handle it
with C, but it won't be spelled out for you. This book is graduate
level, and I am not aware of anything similar that is C oriented.




Looking into an existing C compiler to see what it does may be more
confusing than enlightening if you are lacking some prerequisites. You
should understand the "single static assignment" (SSA) code
transformation. You should know some graph theory - particularly
domination, matching and fusion. You should understand how to
identify location aliasing (not just by pointers directly, but also
aliasing within memory blocks they refer to). You need a good
understanding of C's aliasing rules, which take into account not just
data location but also data type(s).


And you need to understand what *shoudn't* be done with floating
point. Floating point operations do not commute, so in general you
can't reorder operations or spill register temporaries without
affecting the result. Some understanding of numerical analysis is
recommended.




Any modern compiler text should cover SSA. Alias identification is
touched on in some texts, but I personally have not seen a really
thorough treatment outside of Allen & Kennedy. If you can interpolate
from the Fortran based discussion, everything you need to know is
there.


C's aliasing rules: you really need to get a copy of the standard
document - they aren't in any other text that I am aware of.


Floating point: if you can get a copy of IEEE-754 (2008), it talks
about what optimizations are possible. Again, this is not light
reading. Some further reading is suggested at:
https://en.wikipedia.org/wiki/IEEE_754




Hope this helps.
George
[Great reading list, thanks. Floating add and multiply commute but
they don't associate. a+b should be the sams as b+a, but (a+b)+c not
the same as a+(b+c). -John]

Return to the comp.compilers page.
Search the comp.compilers archives again.