Path: csiph.com!xmission!news.snarked.org!border2.nntp.dca1.giganews.com!border1.nntp.dca1.giganews.com!nntp.giganews.com!news.iecc.com!.POSTED.news.iecc.com!nerds-end From: George Neuner Newsgroups: comp.compilers Subject: Re: Optimization techniques Date: Thu, 18 Apr 2019 04:07:53 -0400 Organization: A noiseless patient Spider Lines: 81 Sender: news@iecc.com Approved: comp.compilers@iecc.com Message-ID: <19-04-006@comp.compilers> References: <19-04-004@comp.compilers> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 8bit Injection-Info: gal.iecc.com; posting-host="news.iecc.com:2001:470:1f07:1126:0:676f:7373:6970"; logging-data="27255"; mail-complaints-to="abuse@iecc.com" Keywords: optimize, comment Posted-Date: 18 Apr 2019 07:41:44 EDT X-submission-address: compilers@iecc.com X-moderator-address: compilers-request@iecc.com X-FAQ-and-archives: http://compilers.iecc.com Xref: csiph.com comp.compilers:2190 On Wed, 17 Apr 2019 09:42:21 -0400 (EDT), "Rick C. Hodgin" 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]