docs/HistoricalNotes/2001-06-01-GCCOptimizations2.txt - llvm-project/llvm - Git at Google

 Date: Fri, 1 Jun 2001 17:08:44 -0500 (CDT)
 From: Chris Lattner <sabre@nondot.org>
 To: Vikram S. Adve <vadve@cs.uiuc.edu>
 Subject: RE: Interesting: GCC passes

 > That is very interesting.  I agree that some of these could be done on LLVM
 > at link-time, but it is the extra time required that concerns me.  Link-time
 > optimization is severely time-constrained.

 If we were to reimplement any of these optimizations, I assume that we
 could do them a translation unit at a time, just as GCC does now.  This
 would lead to a pipeline like this:

 Static optimizations, xlation unit at a time:
 .c --GCC--> .llvm --llvmopt--> .llvm

 Link time optimizations:
 .llvm --llvm-ld--> .llvm --llvm-link-opt--> .llvm

 Of course, many optimizations could be shared between llvmopt and
 llvm-link-opt, but the wouldn't need to be shared...  Thus compile time
 could be faster, because we are using a "smarter" IR (SSA based).

 > BTW, about SGI, "borrowing" SSA-based optimizations from one compiler and
 > putting it into another is not necessarily easier than re-doing it.
 > Optimization code is usually heavily tied in to the specific IR they use.

 Understood.  The only reason that I brought this up is because SGI's IR is
 more similar to LLVM than it is different in many respects (SSA based,
 relatively low level, etc), and could be easily adapted.  Also their
 optimizations are written in C++ and are actually somewhat
 structured... of course it would be no walk in the park, but it would be
 much less time consuming to adapt, say, SSA-PRE than to rewrite it.

 > But your larger point is valid that adding SSA based optimizations is
 > feasible and should be fun.  (Again, link time cost is the issue.)

 Assuming linktime cost wasn't an issue, the question is:
 Does using GCC's backend buy us anything?

 > It also occurs to me that GCC is probably doing quite a bit of back-end
 > optimization (step 16 in your list).  Do you have a breakdown of that?

 Not really.  The irritating part of GCC is that it mixes it all up and
 doesn't have a clean separation of concerns.  A lot of the "back end
 optimization" happens right along with other data optimizations (ie, CSE
 of machine specific things).

 As far as REAL back end optimizations go, it looks something like this:

 1. Instruction combination: try to make CISCy instructions, if available
 2. Register movement: try to get registers in the right places for the
 architecture to avoid register to register moves.  For example, try to get
 the first argument of a function to naturally land in %o0 for sparc.
 3. Instruction scheduling: 'nuff said :)
 4. Register class preferencing: ??
 5. Local register allocation
 6. global register allocation
 7. Spilling
 8. Local regalloc
 9. Jump optimization
 10. Delay slot scheduling
 11. Branch shorting for CISC machines
 12. Instruction selection & peephole optimization
 13. Debug info output

 But none of this would be usable for LLVM anyways, unless we were using
 GCC as a static compiler.

 -Chris
	Date: Fri, 1 Jun 2001 17:08:44 -0500 (CDT)
	From: Chris Lattner <sabre@nondot.org>
	To: Vikram S. Adve <vadve@cs.uiuc.edu>
	Subject: RE: Interesting: GCC passes

	> That is very interesting. I agree that some of these could be done on LLVM
	> at link-time, but it is the extra time required that concerns me. Link-time
	> optimization is severely time-constrained.

	If we were to reimplement any of these optimizations, I assume that we
	could do them a translation unit at a time, just as GCC does now. This
	would lead to a pipeline like this:

	Static optimizations, xlation unit at a time:
	.c --GCC--> .llvm --llvmopt--> .llvm

	Link time optimizations:
	.llvm --llvm-ld--> .llvm --llvm-link-opt--> .llvm

	Of course, many optimizations could be shared between llvmopt and
	llvm-link-opt, but the wouldn't need to be shared... Thus compile time
	could be faster, because we are using a "smarter" IR (SSA based).

	> BTW, about SGI, "borrowing" SSA-based optimizations from one compiler and
	> putting it into another is not necessarily easier than re-doing it.
	> Optimization code is usually heavily tied in to the specific IR they use.

	Understood. The only reason that I brought this up is because SGI's IR is
	more similar to LLVM than it is different in many respects (SSA based,
	relatively low level, etc), and could be easily adapted. Also their
	optimizations are written in C++ and are actually somewhat
	structured... of course it would be no walk in the park, but it would be
	much less time consuming to adapt, say, SSA-PRE than to rewrite it.

	> But your larger point is valid that adding SSA based optimizations is
	> feasible and should be fun. (Again, link time cost is the issue.)

	Assuming linktime cost wasn't an issue, the question is:
	Does using GCC's backend buy us anything?

	> It also occurs to me that GCC is probably doing quite a bit of back-end
	> optimization (step 16 in your list). Do you have a breakdown of that?

	Not really. The irritating part of GCC is that it mixes it all up and
	doesn't have a clean separation of concerns. A lot of the "back end
	optimization" happens right along with other data optimizations (ie, CSE
	of machine specific things).

	As far as REAL back end optimizations go, it looks something like this:

	1. Instruction combination: try to make CISCy instructions, if available
	2. Register movement: try to get registers in the right places for the
	architecture to avoid register to register moves. For example, try to get
	the first argument of a function to naturally land in %o0 for sparc.
	3. Instruction scheduling: 'nuff said :)
	4. Register class preferencing: ??
	5. Local register allocation
	6. global register allocation
	7. Spilling
	8. Local regalloc
	9. Jump optimization
	10. Delay slot scheduling
	11. Branch shorting for CISC machines
	12. Instruction selection & peephole optimization
	13. Debug info output

	But none of this would be usable for LLVM anyways, unless we were using
	GCC as a static compiler.

	-Chris