3 ms·

> The authors promote using dozens or hundreds of compiler passes, each being as simple as possible. This kind of approach can seem wrong, because it's breatht

by 6ren 15y ago

> The authors promote using dozens or hundreds of compiler passes, each being as simple as possible. This kind of approach can seem wrong, because it's breathtakingly, disturbingly inefficient, but it's an excellent way to break down a problem, so you can see it, play with it and understand it. It's much easier to write an efficient version once you know what the hell you're doing.

onan_barbarian 15y ago
The issue of doing tiny passes is not so much efficiency or the lack thereof; it's that combining passes can allow for better decisions to be made. This can result in better code quality than could be achieved independently. The classic example is the combination of register allocation and scheduling - scheduling can benefit from knowing what the actual operations are (e.g. will this thing be a load or will it be in a register) while register allocation can benefit from not having scheduling make overly aggressive movements of code that generate more live ranges than can be successfully allocated to registers. Lots of papers on this sort of topic - the one I remember was (probably outdated): http://portal.acm.org/citation.cfm?id=106986 http://portal.acm.org/citation.cfm?id=106986 Integrating register allocation and instruction scheduling for RISCs (1991) by D G Bradlee, S J Eggers, R R Henry That being said, many quite successful compilers manage to get by with simpler passes, sometimes using heuristics or multiple passes or just plain trickery. It's nice to be able to keep things simple. Especially nice for pedagogy, as above. Compilers are lousy with 'phase ordering problems' where there's no clear-cut superior order in which to make certain decisions...
angrycoder 15y ago
Regarding compiler passes in LLVM: Depending on the optimization level, different passes are run: for example at -O0 (no optimization) the Clang compiler runs no passes, at -O3 it runs a series of 67 passes in its optimizer (as of LLVM 2.8). http://www.aosabook.org/en/llvm.html http://www.aosabook.org/en/llvm.html
- Locke1689 15y ago
  That's slightly different. First, that's post generation of the IR -- some of the steps that you want to combine are pre-IR. Second, the idea behind LLVM's optimizer structure is that each optimization provides a single task so they can be combined modularly. This may not produce the fastest code or fastest compile time but the idea is that the benefit in code organization would provide benefits that wouldn't be seen in a more tightly knit organizational structure.

by 6ren 15y ago

onan_barbarian 15y ago

The issue of doing tiny passes is not so much efficiency or the lack thereof; it's that combining passes can allow for better decisions to be made. This can result in better code quality than could be achieved independently. The classic example is the combination of register allocation and scheduling - scheduling can benefit from knowing what the actual operations are (e.g. will this thing be a load or will it be in a register) while register allocation can benefit from not having scheduling make overly aggressive movements of code that generate more live ranges than can be successfully allocated to registers. Lots of papers on this sort of topic - the one I remember was (probably outdated): http://portal.acm.org/citation.cfm?id=106986 http://portal.acm.org/citation.cfm?id=106986 Integrating register allocation and instruction scheduling for RISCs (1991) by D G Bradlee, S J Eggers, R R Henry That being said, many quite successful compilers manage to get by with simpler passes, sometimes using heuristics or multiple passes or just plain trickery. It's nice to be able to keep things simple. Especially nice for pedagogy, as above. Compilers are lousy with 'phase ordering problems' where there's no clear-cut superior order in which to make certain decisions...

angrycoder 15y ago

Regarding compiler passes in LLVM: Depending on the optimization level, different passes are run: for example at -O0 (no optimization) the Clang compiler runs no passes, at -O3 it runs a series of 67 passes in its optimizer (as of LLVM 2.8). http://www.aosabook.org/en/llvm.html http://www.aosabook.org/en/llvm.html

Locke1689 15y ago
That's slightly different. First, that's post generation of the IR -- some of the steps that you want to combine are pre-IR. Second, the idea behind LLVM's optimizer structure is that each optimization provides a single task so they can be combined modularly. This may not produce the fastest code or fastest compile time but the idea is that the benefit in code organization would provide benefits that wouldn't be seen in a more tightly knit organizational structure.