1*9880d681SAndroid Build Coastguard WorkerDate: Fri, 1 Jun 2001 16:38:17 -0500 (CDT) 2*9880d681SAndroid Build Coastguard WorkerFrom: Chris Lattner <[email protected]> 3*9880d681SAndroid Build Coastguard WorkerTo: Vikram S. Adve <[email protected]> 4*9880d681SAndroid Build Coastguard WorkerSubject: Interesting: GCC passes 5*9880d681SAndroid Build Coastguard Worker 6*9880d681SAndroid Build Coastguard Worker 7*9880d681SAndroid Build Coastguard WorkerTake a look at this document (which describes the order of optimizations 8*9880d681SAndroid Build Coastguard Workerthat GCC performs): 9*9880d681SAndroid Build Coastguard Worker 10*9880d681SAndroid Build Coastguard Workerhttp://gcc.gnu.org/onlinedocs/gcc_17.html 11*9880d681SAndroid Build Coastguard Worker 12*9880d681SAndroid Build Coastguard WorkerThe rundown is that after RTL generation, the following happens: 13*9880d681SAndroid Build Coastguard Worker 14*9880d681SAndroid Build Coastguard Worker1 . [t] jump optimization (jumps to jumps, etc) 15*9880d681SAndroid Build Coastguard Worker2 . [t] Delete unreachable code 16*9880d681SAndroid Build Coastguard Worker3 . Compute live ranges for CSE 17*9880d681SAndroid Build Coastguard Worker4 . [t] Jump threading (jumps to jumps with identical or inverse conditions) 18*9880d681SAndroid Build Coastguard Worker5 . [t] CSE 19*9880d681SAndroid Build Coastguard Worker6 . *** Conversion to SSA 20*9880d681SAndroid Build Coastguard Worker7 . [t] SSA Based DCE 21*9880d681SAndroid Build Coastguard Worker8 . *** Conversion to LLVM 22*9880d681SAndroid Build Coastguard Worker9 . UnSSA 23*9880d681SAndroid Build Coastguard Worker10. GCSE 24*9880d681SAndroid Build Coastguard Worker11. LICM 25*9880d681SAndroid Build Coastguard Worker12. Strength Reduction 26*9880d681SAndroid Build Coastguard Worker13. Loop unrolling 27*9880d681SAndroid Build Coastguard Worker14. [t] CSE 28*9880d681SAndroid Build Coastguard Worker15. [t] DCE 29*9880d681SAndroid Build Coastguard Worker16. Instruction combination, register movement, scheduling... etc. 30*9880d681SAndroid Build Coastguard Worker 31*9880d681SAndroid Build Coastguard WorkerI've marked optimizations with a [t] to indicate things that I believe to 32*9880d681SAndroid Build Coastguard Workerbe relatively trivial to implement in LLVM itself. The time consuming 33*9880d681SAndroid Build Coastguard Workerthings to reimplement would be SSA based PRE, Strength reduction & loop 34*9880d681SAndroid Build Coastguard Workerunrolling... these would be the major things we would miss out on if we 35*9880d681SAndroid Build Coastguard Workerdid LLVM creation from tree code [inlining and other high level 36*9880d681SAndroid Build Coastguard Workeroptimizations are done on the tree representation]. 37*9880d681SAndroid Build Coastguard Worker 38*9880d681SAndroid Build Coastguard WorkerGiven the lack of "strong" optimizations that would take a long time to 39*9880d681SAndroid Build Coastguard Workerreimplement, I am leaning a bit more towards creating LLVM from the tree 40*9880d681SAndroid Build Coastguard Workercode. Especially given that SGI has GPL'd their compiler, including many 41*9880d681SAndroid Build Coastguard WorkerSSA based optimizations that could be adapted (besides the fact that their 42*9880d681SAndroid Build Coastguard Workercode looks MUCH nicer than GCC :) 43*9880d681SAndroid Build Coastguard Worker 44*9880d681SAndroid Build Coastguard WorkerEven if we choose to do LLVM code emission from RTL, we will almost 45*9880d681SAndroid Build Coastguard Workercertainly want to move LLVM emission from step 8 down until at least CSE 46*9880d681SAndroid Build Coastguard Workerhas been rerun... which causes me to wonder if the SSA generation code 47*9880d681SAndroid Build Coastguard Workerwill still work (due to global variable dependencies and stuff). I assume 48*9880d681SAndroid Build Coastguard Workerthat it can be made to work, but might be a little more involved than we 49*9880d681SAndroid Build Coastguard Workerwould like. 50*9880d681SAndroid Build Coastguard Worker 51*9880d681SAndroid Build Coastguard WorkerI'm continuing to look at the Tree -> RTL code. It is pretty gross 52*9880d681SAndroid Build Coastguard Workerbecause they do some of the translation a statement at a time, and some 53*9880d681SAndroid Build Coastguard Workerof it a function at a time... I'm not quite clear why and how the 54*9880d681SAndroid Build Coastguard Workerdistinction is drawn, but it does not appear that there is a wonderful 55*9880d681SAndroid Build Coastguard Workerplace to attach extra info. 56*9880d681SAndroid Build Coastguard Worker 57*9880d681SAndroid Build Coastguard WorkerAnyways, I'm proceeding with the RTL -> LLVM conversion phase for now. We 58*9880d681SAndroid Build Coastguard Workercan talk about this more on Monday. 59*9880d681SAndroid Build Coastguard Worker 60*9880d681SAndroid Build Coastguard WorkerWouldn't it be nice if there were a obvious decision to be made? :) 61*9880d681SAndroid Build Coastguard Worker 62*9880d681SAndroid Build Coastguard Worker-Chris 63*9880d681SAndroid Build Coastguard Worker 64