Compilers · Cluster
Code Generation
Instruction selection, scheduling, and peepholes.
- 01 Instruction Selection as Tree Tiling How a back end maps an intermediate representation onto machine instructions by covering expression trees with patterns, and why legality and cost are separate questions.
- 02 Maximal Munch and Dynamic-Programming Tiling Two ways to choose which instruction patterns cover an expression tree, why greedy top-down matching can be arbitrarily bad, and what the optimal algorithm costs to run.
- 03 Folding Address Computation into Memory Operands How base, index, scale, and displacement get absorbed into load and store encodings, which arithmetic survives the fold, and why the selector must sometimes refuse.
- 04 Two-Address Instructions and Destructive Operands Why many instruction sets overwrite an input register to produce a result, how that constraint turns selection into a copy-insertion problem, and what the copies cost.
- 05 Peephole Optimization and the Sliding Window How local rewrites over a small instruction window remove redundant loads, collapse moves, and turn compare-and-branch pairs into single instructions, and where the window size stops helping.
- 06 List Scheduling and the Critical Path How a basic-block scheduler orders instructions to hide latency, why the critical path bounds the result, and how register pressure forces it to give that bound up.
- 07 Modulo Scheduling and Software Pipelining How a loop is transformed so that successive iterations overlap in the pipeline, what the initiation interval bounds are, and why prologue and epilogue code appears at the edges.
- 08 Scheduling Before Allocation and the Pressure Trade Why an aggressive instruction schedule can force spills that erase its own benefit, how pressure-aware scheduling caps live values, and what iterative repair actually converges on.
- 09 If-Conversion, Predication, and the Limits of Speculation How conditional branches become data dependences on a predicate, when that is profitable, and why the transformation must respect faults, exceptions, and the register file.
- 10 Bundling Instructions for VLIW Issue Slots How a compiler packs independent operations into fixed-width bundles, why empty slots become explicit no-ops, and how slot assignment and stop bits constrain the scheduler.