Chris Lattner | 0095054 | 2001-06-06 20:29:01 +0000 | [diff] [blame] | 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 |
Misha Brukman | 318efde | 2003-08-21 22:14:57 +0000 | [diff] [blame] | 47 | will still work (due to global variable dependencies and stuff). I assume |
Chris Lattner | 0095054 | 2001-06-06 20:29:01 +0000 | [diff] [blame] | 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 | |