docs/HistoricalNotes/2001-06-01-GCCOptimizations.txt

   1 Date: Fri, 1 Jun 2001 16:38:17 -0500 (CDT)
   2 From: Chris Lattner <sabre@nondot.org>
   3 To: Vikram S. Adve <vadve@cs.uiuc.edu>
   4 Subject: Interesting: GCC passes
   5
   6
   7 Take a look at this document (which describes the order of optimizations
   8 that GCC performs):
   9
  10 http://gcc.gnu.org/onlinedocs/gcc_17.html
  11
  12 The rundown is that after RTL generation, the following happens:
  13
  14 1 . [t] jump optimization (jumps to jumps, etc)
  15 2 . [t] Delete unreachable code
  16 3 .     Compute live ranges for CSE
  17 4 . [t] Jump threading (jumps to jumps with identical or inverse conditions)
  18 5 . [t] CSE
  19 6 . *** Conversion to SSA
  20 7 . [t] SSA Based DCE
  21 8 . *** Conversion to LLVM
  22 9 .     UnSSA
  23 10.     GCSE
  24 11.     LICM
  25 12.     Strength Reduction
  26 13.     Loop unrolling
  27 14. [t] CSE
  28 15. [t] DCE
  29 16.     Instruction combination, register movement, scheduling... etc.
  30
  31 I've marked optimizations with a [t] to indicate things that I believe to
  32 be relatively trivial to implement in LLVM itself.  The time consuming
  33 things to reimplement would be SSA based PRE, Strength reduction & loop
  34 unrolling... these would be the major things we would miss out on if we
  35 did LLVM creation from tree code [inlining and other high level
  36 optimizations are done on the tree representation].
  37
  38 Given the lack of "strong" optimizations that would take a long time to
  39 reimplement, I am leaning a bit more towards creating LLVM from the tree
  40 code.  Especially given that SGI has GPL'd their compiler, including many
  41 SSA based optimizations that could be adapted (besides the fact that their
  42 code looks MUCH nicer than GCC :)
  43
  44 Even if we choose to do LLVM code emission from RTL, we will almost
  45 certainly want to move LLVM emission from step 8 down until at least CSE
  46 has been rerun... which causes me to wonder if the SSA generation code
  47 will still work (due to global variable dependencies and stuff).  I assume
  48 that it can be made to work, but might be a little more involved than we
  49 would like.
  50
  51 I'm continuing to look at the Tree -> RTL code.  It is pretty gross
  52 because they do some of the translation a statement at a time, and some
  53 of it a function at a time...  I'm not quite clear why and how the
  54 distinction is drawn, but it does not appear that there is a wonderful
  55 place to attach extra info.
  56
  57 Anyways, I'm proceeding with the RTL -> LLVM conversion phase for now.  We
  58 can talk about this more on Monday.
  59
  60 Wouldn't it be nice if there were a obvious decision to be made?  :)
  61
  62 -Chris
  63