Skip to content

References — Chapter 23 · Instruction Scheduling & Machine-Level Optimization

Every source this chapter cites, grouped by kind. Lessons cite entries inline as [KEY]; each entry says why and when to read it. Core reading marks the entries the chapter assumes you will open.

Foundational and research papers

  • [AKPW83] J. R. Allen, Ken Kennedy, Carrie Porterfield, and Joe Warren. Conversion of Control Dependence to Data Dependence. POPL 1983, pp. 177-189, 1983. doi:10.1145/567067.567085
    Why and when: The origin of if-conversion: guards as data dependences so a vectorizer can handle conditionals (Algorithm 23.5.3).
    Cited in: 05-if-conversion

  • [AR22] Andreas Abel and Jan Reineke. uiCA: Accurate Throughput Prediction of Basic Blocks on Recent Intel Microarchitectures. ICS 2022, 2022. doi:10.1145/3524059.3532396 · pdf
    Why and when: A detailed simulator of Intel front ends, measured against hardware, with a comparison of llvm-mca, IACA and OSACA. Read it to see where Definition 23.1.10's bounds are not the whole story (Lesson 23.1 §6).
    Cited in: 01-machine-models

  • [BEH91] David G. Bradlee, Susan J. Eggers, and Robert R. Henry. Integrating Register Allocation and Instruction Scheduling for RISCs. ASPLOS IV (ACM SIGPLAN Notices 26(4)), pp. 122–131, 1991.
    Why and when: An empirical comparison of postpass, IPS and a fully integrated strategy; the evidence that a pressure-aware prepass scheduler gets most of the benefit (Lesson 23.8 §1, §8).
    Note: In the ASPLOS IV proceedings, 1991.
    Cited in: 08-scheduling-and-register-allocation

  • [Ber66] A. J. Bernstein. Analysis of Programs for Parallel Processing. IEEE Transactions on Electronic Computers EC-15(5), pp. 757–763, 1966. doi:10.1109/PGEC.1966.264565
    Why and when: Bernstein's conditions: two operations may run in parallel when neither writes what the other reads or writes. They are Definition 23.2.2's three register dependences in their original form.
    Cited in: 02-dependence-dags

  • [BR91] David Bernstein and Michael Rodeh. Global Instruction Scheduling for Superscalar Machines. PLDI 1991, pp. 241–255, 1991. doi:10.1145/113445.113466
    Why and when: Scheduling over acyclic regions with useful and speculative motion, the design behind GCC's sched-rgn.cc (Lesson 23.4 §6–7).
    Cited in: 04-region-scheduling

  • [BR95] Vasanth Bala and Norman Rubin. Efficient Instruction Scheduling Using Finite State Automata. MICRO-28, pp. 46–56, 1995. link
    Why and when: Extends the pipeline automaton with reverse automata and factoring, the ideas behind GCC's define_automaton split (Lesson 23.1 §6). Read §3–4 if you care about VLIW packers.
    Cited in: 01-machine-models

  • [CG72] E. G. Coffman Jr. and R. L. Graham. Optimal Scheduling for Two-Processor Systems. Acta Informatica 1(3), pp. 200–213, 1972. doi:10.1007/BF00288685
    Why and when: Optimal scheduling of unit-time DAGs on two processors by lexicographic labeling, the polynomial boundary case of Theorem 23.3.4.
    Cited in: 03-list-scheduling

  • [DHB89] James C. Dehnert, Peter Y.-T. Hsu, and Joseph P. Bratt. Overlapped Loop Support in the Cydra 5. ASPLOS III, pp. 26–38, 1989. doi:10.1145/68182.68185
    Why and when: Rotating registers and predicated stages in hardware: the machine support the lab's toy machine imitates (SPEC §6.4, Algorithm 23.6.12).
    Cited in: 06-software-pipelining

  • [DSTP75] Edward S. Davidson, Leonard E. Shar, A. Thampy Thomas, and Janak H. Patel. Effective Control for Pipelined Computers. IEEE COMPCON Spring 1975, pp. 181–184, 1975.
    Why and when: The origin of reservation tables, forbidden latencies and collision vectors (Lesson 23.1 §1). Four pages; read it after Definition 23.1.5 to see the hardware controller the compiler's hazard recognizer imitates.
    Note: Conference digest paper without a DOI; widely reprinted in pipeline-design course readers.
    Cited in: 01-machine-models

  • [Fis81] Joseph A. Fisher. Trace Scheduling: A Technique for Global Microcode Compaction. IEEE Transactions on Computers C-30(7), pp. 478–490, 1981. doi:10.1109/TC.1981.1675827
    Why and when: Core reading. The origin of trace scheduling and compensation code (Algorithm 23.4.5). Read the trace selection and bookkeeping sections after Lesson 23.4 §2; the correctness argument is informal but complete.
    Cited in: 04-region-scheduling

  • [FOW87] Jeanne Ferrante, Karl J. Ottenstein, and Joe D. Warren. The Program Dependence Graph and Its Use in Optimization. ACM TOPLAS 9(3), pp. 319–349, 1987. doi:10.1145/24039.24041
    Why and when: Control dependence from post-dominance, which the RK predicate assignment is built on (Definition 23.5.4). Read §2–3 if Ch 15's Lesson 15.4 is not fresh.
    Cited in: 05-if-conversion

  • [GH88] James R. Goodman and Wei-Chung Hsu. Code Scheduling and Register Allocation in Large Basic Blocks. ICS 1988, pp. 442–452, 1988. doi:10.1145/55364.55407
    Why and when: Core reading. Integrated prepass scheduling: latency-first until registers run short, then pressure-first. The origin of Algorithm 23.3.10 and Algorithm 23.8.4, and of the lab's ★ pressure algorithm.
    Cited in: 03-list-scheduling, 08-scheduling-and-register-allocation

  • [GM86] Philip B. Gibbons and Steven S. Muchnick. Efficient Instruction Scheduling for a Pipelined Architecture. SIGPLAN '86 Symposium on Compiler Construction, pp. 11–16, 1986. doi:10.1145/12276.13312
    Why and when: Core reading. The table-driven backward DAG construction (Algorithm 23.2.6) and a top-down list scheduler with lookahead-free priorities, in six pages. The model for most RISC-era schedulers; read it right after Lesson 23.2.
    Cited in: overview, 02-dependence-dags, 03-list-scheduling, 08-scheduling-and-register-allocation

  • [Gra66] R. L. Graham. Bounds for Certain Multiprocessing Anomalies. Bell System Technical Journal 45(9), pp. 1563–1581, 1966. doi:10.1002/j.1538-7305.1966.tb01709.x
    Why and when: The first proof that any list schedule is within a factor 2 − 1/m of the optimum on m identical processors (Theorem 23.3.3). The argument is two pages; read it after the lesson's proof.
    Cited in: 03-list-scheduling

  • [Gra69] R. L. Graham. Bounds on Multiprocessing Timing Anomalies. SIAM Journal on Applied Mathematics 17(2), pp. 416–429, 1969. doi:10.1137/0117039
    Why and when: The anomalies (more processors, shorter tasks or fewer edges can lengthen a list schedule) and the tightness of the bound. Read §2 for the examples behind Lesson 23.3 §4's pitfall.
    Cited in: 03-list-scheduling

  • [HBC98] William A. Havanki, Sanjeev Banerjia, and Thomas M. Conte. Treegion Scheduling for Wide Issue Processors. HPCA-4, 1998, 1998. link
    Why and when: Tree-shaped regions that need no join compensation (Definition 23.4.8, Proposition 23.4.12), with heuristics compared against traces and superblocks.
    Cited in: 04-region-scheduling

  • [HG83] John L. Hennessy and Thomas Gross. Postpass Code Optimization of Pipeline Constraints. ACM TOPLAS 5(3), pp. 422–448, 1983. doi:10.1145/2166.357217
    Why and when: Scheduling for the MIPS pipeline without interlocks, with an NP-completeness proof for pipelines with delays. Read it for the phase-ordering discussion that Lesson 23.8 picks up.
    Cited in: 03-list-scheduling, 08-scheduling-and-register-allocation

  • [HMC+93] Wen-mei W. Hwu, Scott A. Mahlke, William Y. Chen, Pohua P. Chang, Nancy J. Warter, Roger A. Bringmann, Roland G. Ouellette, Richard E. Hank, Tokuzo Kiyohara, Grant E. Haab, John G. Holm, and Daniel M. Lavery. The Superblock: An Effective Technique for VLIW and Superscalar Compilation. The Journal of Supercomputing 7(1–2), pp. 229–248, 1993. doi:10.1007/BF01205185
    Why and when: Core reading. Superblock formation by tail duplication and the superblock optimizations of IMPACT (Algorithm 23.4.6). Shorter and more practical than the trace-scheduling literature; read it right after Lesson 23.4 §2.
    Cited in: overview, 04-region-scheduling

  • [Hu61] T. C. Hu. Parallel Sequencing and Assembly Line Problems. Operations Research 9(6), pp. 841–848, 1961. doi:10.1287/opre.9.6.841
    Why and when: Level (height) priority is optimal for in-trees of unit tasks on any number of processors, the origin of critical-path priority (Theorem 23.3.4's polynomial cases).
    Cited in: 02-dependence-dags, 03-list-scheduling

  • [Lam88] Monica Lam. Software Pipelining: An Effective Scheduling Technique for VLIW Machines. PLDI 1988, pp. 318–328, 1988. doi:10.1145/53990.54022
    Why and when: Software pipelining in a real compiler (Warp): modulo variable expansion and hierarchical reduction of conditionals. Read it after Algorithm 23.6.12 to compare MVE with rotating registers.
    Cited in: 06-software-pipelining

  • [LFK+93] P. Geoffrey Lowney, Stefan M. Freudenberger, Thomas J. Karzes, W. D. Lichtenstein, Robert P. Nix, John S. O'Donnell, and John C. Ruttenberg. The Multiflow Trace Scheduling Compiler. The Journal of Supercomputing 7(1–2), pp. 51–142, 1993. doi:10.1007/BF01205182
    Why and when: Ninety pages on the only commercial trace-scheduling compiler: what worked, what compensation code cost, and how the machine model shaped the compiler. Read selectively after Lesson 23.4.
    Cited in: 04-region-scheduling

  • [LGAV96] Josep Llosa, Antonio González, Eduard Ayguadé, and Mateo Valero. Swing Modulo Scheduling: A Lifetime-Sensitive Approach. PACT 1996, pp. 80–86, 1996. link
    Why and when: Core reading. SMS (Algorithm 23.6.10): the node ordering that avoids backtracking and keeps lifetimes short, implemented by LLVM's MachinePipeliner and GCC's modulo-sched.cc.
    Cited in: overview, 06-software-pipelining

  • [Mak03] Vladimir N. Makarov. The Finite State Automaton Based Pipeline Hazard Recognizer and Instruction Scheduler in GCC. GCC Developers' Summit 2003, pp. 135–150, 2003. link
    Why and when: How GCC's genautomata turns define_insn_reservation descriptions into factored automata and how haifa-sched queries them. Read after Lesson 23.1 §7 alongside the .md files of a GCC target.
    Cited in: 01-machine-models

  • [ME92] Soo-Mook Moon and Kemal Ebcioğlu. An Efficient Resource-Constrained Global Scheduling Technique for Superscalar and VLIW Processors. MICRO-25, pp. 55–71, 1992.
    Why and when: Selective scheduling: moving operations upward through the CFG with renaming and bookkeeping, the algorithm of GCC's sel-sched.cc (Lesson 23.4 §6).
    Note: Also IBM Research Report RC 17962, 1992.
    Cited in: 04-region-scheduling

  • [MHM+95] Scott A. Mahlke, Richard E. Hank, James E. McCormick, David I. August, and Wen-mei W. Hwu. A Comparison of Full and Partial Predicated Execution Support for ILP Processors. ISCA 1995, pp. 138–150, 1995. doi:10.1145/223982.225965
    Why and when: Full predication versus conditional moves only: how much of the benefit selects keep. The background for LLVM's EarlyIfConversion design (Lesson 23.5 §6–7).
    Cited in: 05-if-conversion

  • [MLC+92] Scott A. Mahlke, David C. Lin, William Y. Chen, Richard E. Hank, and Roger A. Bringmann. Effective Compiler Support for Predicated Execution Using the Hyperblock. MICRO-25, pp. 45–54, 1992. link
    Why and when: Core reading. Hyperblocks: select blocks by frequency, size and hazards, tail-duplicate, then if-convert (Algorithm 23.5.6). Read it after Lesson 23.5 §2.
    Cited in: 05-if-conversion

  • [NP20] Andy Newell and Sergey Pupyrev. Improved Basic Block Reordering. IEEE Transactions on Computers 69(12), 2020. pdf
    Why and when: Core reading. The ext-TSP model and its greedy chain-merging algorithm (Definition 23.9.5, Algorithm 23.9.6), with the NP-hardness proof and measurements on large binaries.
    Cited in: overview, 09-code-layout

  • [NP93] Cindy Norris and Lori L. Pollock. A Scheduler-Sensitive Global Register Allocator. Supercomputing '93, pp. 804–813, 1993.
    Why and when: Adds scheduling edges to a Chaitin-style allocator and removes them before spilling (Algorithm 23.8.7).
    Note: In the proceedings of Supercomputing '93 (ACM/IEEE).
    Cited in: 08-scheduling-and-register-allocation

  • [OM17] Guilherme Ottoni and Bertrand Maher. Optimizing Function Placement for Large-Scale Data-Center Applications. CGO 2017, pp. 233–244, 2017.
    Why and when: hfsort / C³: call-graph clustering for function order, used by BOLT and linkers (Lessons 23.9 §6 and 23.10 §7).
    Note: In the CGO 2017 proceedings (IEEE/ACM).
    Cited in: 09-code-layout, 10-machine-peepholes-and-post-link

  • [PAN+19] Maksim Panchenko, Rafael Auler, Bill Nell, and Guilherme Ottoni. BOLT: A Practical Binary Optimizer for Data Centers and Beyond. CGO 2019, 2019. pdf
    Why and when: Core reading. Post-link layout by binary rewriting: profile mapping, block reordering, function splitting and ordering, with production speedups (Lesson 23.10 §2 and §7).
    Cited in: overview, 10-machine-peepholes-and-post-link

  • [PF94] Todd A. Proebsting and Christopher W. Fraser. Detecting Pipeline Structural Hazards Quickly. POPL 1994, pp. 280–286, 1994. doi:10.1145/174675.177904
    Why and when: Compiles reservation tables into a finite automaton so a scheduler's "does it fit?" is one table lookup (Proposition 23.1.7). Short and clear; read it after Lesson 23.1 §2.
    Cited in: 01-machine-models

  • [PH90] Karl Pettis and Robert C. Hansen. Profile Guided Code Positioning. PLDI 1990, 1990. doi:10.1145/93542.93550
    Why and when: Core reading. Procedure ordering, basic-block chaining and procedure splitting from profiles (Algorithm 23.9.2). Read §4 (basic blocks) after Lesson 23.9 §2.
    Cited in: overview, 09-code-layout

  • [Pin93] Shlomit S. Pinter. Register Allocation with Instruction Scheduling: A New Approach. PLDI 1993, pp. 248–257, 1993. doi:10.1145/173262.155114
    Why and when: The parallelizable interference graph (Definition 23.8.5, Theorem 23.8.6): a coloring that introduces no restricting false dependence.
    Cited in: 08-scheduling-and-register-allocation

  • [Rau94] B. Ramakrishna Rau. Iterative Modulo Scheduling: An Algorithm for Software Pipelining Loops. MICRO-27, pp. 63–74, 1994. doi:10.1145/192724.192731
    Why and when: Core reading. The algorithm the lab implements (Algorithm 23.6.9): HeightR priority, the MRT, eviction and the budget, with measurements on over 1300 loops. Read it before E4.
    Cited in: overview, 06-software-pipelining

  • [RG81] B. R. Rau and C. D. Glaeser. Some Scheduling Techniques and an Easily Schedulable Horizontal Architecture for High Performance Scientific Computing. 14th Annual Workshop on Microprogramming (MICRO-14), pp. 183–198, 1981.
    Why and when: The first modulo scheduler and the resource bound ResMII (Definition 23.6.3), with the polycyclic architecture it targeted.
    Note: In the MICRO-14 proceedings (ACM/IEEE), 1981.
    Cited in: 06-software-pipelining

  • [Set75] Ravi Sethi. Complete Register Allocation Problems. SIAM Journal on Computing 4(3), pp. 226–248, 1975. doi:10.1137/0204020
    Why and when: Minimizing registers for a DAG's evaluation order is NP-complete (Lesson 23.3 §4): why pressure-aware schedulers are heuristics.
    Cited in: 03-list-scheduling

  • [SPL+23] Han Shen, Krzysztof Pszeniczny, Rahman Lavaee, Snehasish Kumar, Sriraman Tallam, and Xinliang David Li. Propeller: A Profile Guided, Relinking Optimizer for Warehouse-Scale Applications. ASPLOS 2023, pp. 617–631, 2023. doi:10.1145/3575693.3575727
    Why and when: Post-link layout by relinking with basic-block sections instead of rewriting; read it after [PAN+19] for the other half of Lesson 23.10's comparison.
    Cited in: overview, 10-machine-peepholes-and-post-link

  • [SU70] Ravi Sethi and Jeffrey D. Ullman. The Generation of Optimal Code for Arithmetic Expressions. Journal of the ACM 17(4), pp. 715–728, 1970. doi:10.1145/321607.321620
    Why and when: The register-need numbering that is optimal on expression trees and is the priority of SelectionDAG's list-burr scheduler (Lessons 23.3 and 23.7).
    Cited in: 03-list-scheduling, 07-llvm-schedulers

  • [Ull75] J. D. Ullman. NP-Complete Scheduling Problems. Journal of Computer and System Sciences 10(3), pp. 384–393, 1975. doi:10.1016/S0022-0000(75)80008-0
    Why and when: NP-completeness of precedence-constrained scheduling of unit tasks, the reduction behind Theorem 23.3.4. Read §2 for the construction.
    Cited in: 03-list-scheduling

  • [War90] Henry S. Warren Jr.. Instruction Scheduling for the IBM RISC System/6000 Processor. IBM Journal of Research and Development 34(1), pp. 85–92, 1990. doi:10.1147/rd.341.0085
    Why and when: A production list scheduler with a precise priority list for a superscalar processor; a good second example after [GM86] (Lesson 23.3 §7).
    Cited in: 03-list-scheduling

Textbooks and monographs

  • [Dragon2] Alfred V. Aho, Monica S. Lam, Ravi Sethi, and Jeffrey D. Ullman. Compilers: Principles, Techniques, and Tools, 2nd ed.. Addison-Wesley, 2006. Read: Ch. 10 (Instruction-Level Parallelism: §10.3 basic-block scheduling, §10.4 global code scheduling, §10.5 software pipelining).
    Why and when: Lam's chapter: the most rigorous textbook treatment of modulo scheduling and its bounds (Lesson 23.6), with global scheduling as a bonus.
    Cited in: overview

  • [EaC3] Keith D. Cooper and Linda Torczon. Engineering a Compiler, 3rd ed.. Morgan Kaufmann, 2022. Read: Ch. 12 (Instruction Scheduling: dependence graphs, list scheduling, regional scheduling, software pipelining).
    Why and when: Core reading. The clearest textbook companion to Lessons 23.2–23.4 and 23.6; read it as a second explanation of list scheduling and its priorities.
    Cited in: overview

  • [GJ79] Michael R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, 1979. Read: Appendix A5 (Sequencing and Scheduling), problem SS9 (Precedence Constrained Scheduling).
    Why and when: The catalogue entry for the problem list scheduling approximates, with the known hard and polynomial special cases in one place (Theorem 23.3.4).

  • [HP6] John L. Hennessy and David A. Patterson. Computer Architecture: A Quantitative Approach, 6th ed.. Morgan Kaufmann, 2017. Read: Ch. 3 (Instruction-Level Parallelism and Its Exploitation), Appendix H (Hardware and Software for VLIW and EPIC).
    Why and when: The hardware side of this chapter: pipelines, dynamic scheduling (why out-of-order cores forgive bad schedules) and the VLIW/EPIC support (predication, rotating registers) that Lessons 23.5–23.6 compile for.

  • [Kog81] Peter M. Kogge. The Architecture of Pipelined Computers. McGraw-Hill, 1981. Read: the chapters on static pipeline control: reservation tables, forbidden latencies, collision vectors and the state diagram of a pipeline controller.
    Why and when: The textbook collection of the reservation-table theory of Lesson 23.1 (collision vectors, greedy cycles, minimum average latency). Useful if Lemma 23.1.6 and the automaton of Proposition 23.1.7 feel too compressed.
    Cited in: 01-machine-models

  • [Muchnick] Steven S. Muchnick. Advanced Compiler Design and Implementation. Morgan Kaufmann, 1997. Read: Ch. 17 (Code Scheduling: list scheduling, speculative loads, software pipelining, trace and superblock scheduling).
    Why and when: A broad engineering treatment, written by the co-author of [GM86]; strongest on the RISC-era block scheduler and on software pipelining variants (Lessons 23.3 and 23.6).

Surveys and tutorials

  • [LDSM80] David Landskov, Scott Davidson, Bruce Shriver, and Patrick W. Mallett. Local Microcode Compaction Techniques. ACM Computing Surveys 12(3), pp. 261–294, 1980. doi:10.1145/356819.356822
    Why and when: Core reading. The survey that turned dependence graphs and list scheduling into compiler techniques (for horizontal microcode). Read its DAG construction and list-scheduling sections after Lessons 23.2–23.3: the algorithms are recognizably the ones in LLVM today.
    Cited in: overview, 02-dependence-dags, 03-list-scheduling

Theses and technical reports

  • [Ell85] John R. Ellis. Bulldog: A Compiler for VLIW Architectures. Yale University, PhD thesis (Research Report YALEU/DCS/RR-364); MIT Press, 1986, 1985.
    Why and when: The engineering of a trace-scheduling compiler: the full bookkeeping rules, memory disambiguation and code generation for a VLIW. Read the trace-scheduling chapters for the cases Theorem 23.4.10's sketch skips.
    Note: Published as a book by MIT Press (ACM Doctoral Dissertation Award series), 1986.
    Cited in: 04-region-scheduling

  • [PS91] Joseph C. H. Park and Michael S. Schlansker. On Predicated Execution. Hewlett-Packard Laboratories, Technical Report HPL-91-58, 1991. pdf
    Why and when: The RK algorithm: predicates from control dependence, one per predicate class (Definition 23.5.4, Proposition 23.5.10). Read it after Lesson 23.5 §2.
    Cited in: 05-if-conversion

Source code (pinned versions)

  • [GCC-bbreorder] GCC's basic-block reordering — gcc/bb-reorder.cc in gcc-mirror/gcc at releases/gcc-15.1.0. Symbols: reorder_basic_blocks, find_traces, reorder_basic_blocks_simple.
    Why and when: Trace-based ("software trace cache") and simple reordering, and hot/cold partitioning; compare with [LLVM-MBP].
    Cited in: 09-code-layout

  • [GCC-genautomata] GCC's pipeline-automaton generator — gcc/genautomata.cc in gcc-mirror/gcc at releases/gcc-15.1.0. Symbols: define_automaton, define_insn_reservation, minimize_DFA.
    Why and when: Builds, minimizes and factors the automata of Proposition 23.1.7 from a target's reservation descriptions. The long header comment is the design document; read it after [Mak03].
    Cited in: 01-machine-models

  • [GCC-haifa] GCC's list scheduler (Haifa) — gcc/haifa-sched.cc in gcc-mirror/gcc at releases/gcc-15.1.0. Symbols: schedule_block, priority, rank_for_schedule, model_schedule.
    Why and when: A cycle-driven top-down scheduler with a long list of tie-breaks (rank_for_schedule) and the -fsched-pressure model. Read priority after Lesson 23.2 and schedule_block after Algorithm 23.3.2.
    Cited in: 02-dependence-dags, 03-list-scheduling, 08-scheduling-and-register-allocation

  • [GCC-ifcvt] GCC's RTL if-converter — gcc/ifcvt.cc in gcc-mirror/gcc at releases/gcc-15.1.0. Symbols: noce_process_if_block, cond_exec_process_if_block.
    Why and when: Both flavors in one file: selects/cmov (noce_*) and predication (cond_exec_*). Compare with LLVM's two passes after Lesson 23.5 §7.
    Cited in: 05-if-conversion

  • [GCC-regrename] GCC's post-allocation register renaming — gcc/regrename.cc in gcc-mirror/gcc at releases/gcc-15.1.0. Symbols: regrename_analyze, find_rename_reg.
    Why and when: Removes false dependences after allocation by renaming chains to free registers (Algorithm 23.8.8); compare with LLVM's anti-dependence breakers.
    Cited in: 08-scheduling-and-register-allocation

  • [GCC-sched-deps] GCC's dependence analysis for the scheduler — gcc/sched-deps.cc in gcc-mirror/gcc at releases/gcc-15.1.0. Symbols: sched_analyze, add_dependence, flush_pending_lists.
    Why and when: GCC's counterpart of buildSchedGraph, with pending read/write lists capped by --param max-pending-list-length. Compare with [LLVM-SDInstrs] after Lesson 23.2 §7.
    Cited in: 02-dependence-dags

  • [GCC-sched-rgn] GCC's interblock (region) scheduler — gcc/sched-rgn.cc in gcc-mirror/gcc at releases/gcc-15.1.0. Symbols: find_rgns, add_branch_dependences, compute_trg_info.
    Why and when: Region formation over the CFG and speculative interblock motion ([BR91]); also where GCC adds the control edges of Definition 23.2.7. Read find_rgns after Lesson 23.4 §7.
    Cited in: 02-dependence-dags, 04-region-scheduling, 08-scheduling-and-register-allocation

  • [GCC-selsched] GCC's selective scheduler — gcc/sel-sched.cc in gcc-mirror/gcc at releases/gcc-15.1.0. Symbols: sel_sched_region, moveup_expr, generate_bookkeeping_insn.
    Why and when: A living trace-scheduling descendant that still generates bookkeeping copies (generate_bookkeeping_insn). Read after Theorem 23.4.10 to see compensation in production code.
    Cited in: 04-region-scheduling

  • [GCC-sms] GCC's swing modulo scheduler (-fmodulo-sched) — gcc/modulo-sched.cc in gcc-mirror/gcc at releases/gcc-15.1.0. Symbols: sms_schedule, sms_schedule_by_order, res_MII, generate_prolog_epilog.
    Why and when: SMS on RTL with MII computation and prologue/epilogue generation; compare with [LLVM-Pipeliner] after Lesson 23.6 §7.
    Cited in: 06-software-pipelining

  • [GCC-tracer] GCC's superblock formation pass (-ftracer) — gcc/tracer.cc in gcc-mirror/gcc at releases/gcc-15.1.0. Symbols: find_trace, tail_duplicate.
    Why and when: Trace selection by profile and tail duplication on GIMPLE, a short and readable version of Algorithms 23.4.3 and 23.4.6.
    Cited in: 04-region-scheduling

  • [LLVM-AMDGPU-CF] AMDGPU's divergent control flow as execution masks — llvm/lib/Target/AMDGPU/SIAnnotateControlFlow.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: SIAnnotateControlFlow.
    Why and when: How a GPU back end turns divergent branches into mask manipulation (with SILowerControlFlow.cpp in the same directory): if-conversion with exec as the predicate (Lesson 23.5 §7).
    Cited in: 05-if-conversion

  • [LLVM-BBSections] LLVM's basic-block sections (the compiler side of Propeller) — llvm/lib/CodeGen/BasicBlockSections.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: BasicBlockSections::runOnMachineFunction.
    Why and when: Reads cluster directives and places each cluster in its own section so the linker can lay out blocks (Lesson 23.10 §7).
    Cited in: 10-machine-peepholes-and-post-link

  • [LLVM-BOLT] BOLT's block-reordering algorithms — bolt/lib/Passes/ReorderAlgorithm.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: ReorderAlgorithm, ExtTSPReorderAlgorithm.
    Why and when: BOLT's layout algorithms, including the ext-TSP default; the rest of BOLT lives in bolt/lib/Passes/ and bolt/lib/Rewrite/. Read after Lesson 23.9 and 23.10 §7.
    Cited in: 10-machine-peepholes-and-post-link

  • [LLVM-BranchFolding] LLVM's branch folding and tail merging — llvm/lib/CodeGen/BranchFolding.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: BranchFolder::TailMergeBlocks, BranchFolder::OptimizeBlock.
    Why and when: Jump threading of empty blocks, branch simplification and common-tail merging (Algorithm 23.9.9, Proposition 23.9.10).
    Cited in: 09-code-layout

  • [LLVM-CodeLayout] LLVM's ext-TSP implementation — llvm/lib/Transforms/Utils/CodeLayout.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: codelayout::computeExtTspLayout, codelayout::calcExtTspScore.
    Why and when: The score of Definition 23.9.5 with its weights and distance limits, and the greedy merging of Algorithm 23.9.6. The lab's drill code-layout uses the same weights.
    Cited in: 09-code-layout

  • [LLVM-EarlyIfCvt] LLVM's early if-conversion to selects — llvm/lib/CodeGen/EarlyIfConversion.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: SSAIfConv::canConvertIf, EarlyIfConverter::shouldConvertIf.
    Why and when: Diamonds and triangles to selects with a trace-metrics cost model (Algorithm 23.5.7). Read shouldConvertIf for the "half the mispredict penalty" rule.
    Cited in: 05-if-conversion

  • [LLVM-HexEIF] Hexagon's multi-block early if-converter — llvm/lib/Target/Hexagon/HexagonEarlyIfConv.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: HexagonEarlyIfConversion::isProfitable, HexagonEarlyIfConversion::convert.
    Why and when: The closest thing to hyperblock formation in LLVM: nested regions predicated with a cost limit. Read after Lesson 23.5's Hexagon box.
    Cited in: 05-if-conversion

  • [LLVM-IfCvt] LLVM's post-RA if-converter (full predication) — llvm/lib/CodeGen/IfConversion.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: IfConverter::AnalyzeBlock, IfConverter::IfConvertDiamond, IfConverter::IfConvertTriangle.
    Why and when: Predicates whole blocks on ARM/Thumb-2 and other predicated targets. Read after the ARM box of Lesson 23.5 §7.
    Cited in: 05-if-conversion

  • [LLVM-MachineCSE] LLVM's machine CSE — llvm/lib/CodeGen/MachineCSE.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: MachineCSE::PerformCSE, MachineCSE::isProfitableToCSE.
    Why and when: Scoped value numbering over the dominator tree on SSA MachineInstrs (Proposition 23.10.4).
    Cited in: 10-machine-peepholes-and-post-link

  • [LLVM-MachineLICM] LLVM's machine LICM (early and post-RA) — llvm/lib/CodeGen/MachineLICM.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: MachineLICMImpl::HoistOutOfLoop, MachineLICMImpl::IsProfitableToHoist.
    Why and when: Hoisting with register-pressure checks before allocation and only with free registers after it (Proposition 23.10.8).
    Cited in: 10-machine-peepholes-and-post-link

  • [LLVM-MachineSink] LLVM's machine sinking — llvm/lib/CodeGen/MachineSink.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: MachineSinking::SinkInstruction, MachineSinking::FindSuccToSinkTo.
    Why and when: Moves instructions into the successor that uses them (Lesson 23.10 §2); read FindSuccToSinkTo for the legality and profitability rules.
    Cited in: 10-machine-peepholes-and-post-link

  • [LLVM-MBP] LLVM's block placement (chains, loop rotation, tail duplication, ext-TSP) — llvm/lib/CodeGen/MachineBlockPlacement.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: MachineBlockPlacement::buildChain, MachineBlockPlacement::selectBestSuccessor, MachineBlockPlacement::applyExtTsp.
    Why and when: A loop-aware descendant of Pettis–Hansen, with an optional ext-TSP stage. Read buildChain after Algorithm 23.9.2.
    Cited in: 09-code-layout

  • [LLVM-MCASrc] llvm-mca's block reciprocal-throughput bound — llvm/lib/MCA/Support.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: computeBlockRThroughput.
    Why and when: Ten lines that compute the "Block RThroughput" of every llvm-mca report: exactly the maximum of Definition 23.1.10. Read it after Theorem 23.1.12.
    Cited in: 01-machine-models

  • [LLVM-MISched] LLVM's MachineScheduler and GenericScheduler — llvm/lib/CodeGen/MachineScheduler.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: GenericScheduler::tryCandidate, SchedBoundary::getNextResourceCycle, SchedBoundary::bumpCycle, ScheduleDAGMILive::schedule.
    Why and when: Core reading. The default pre-RA scheduler: bidirectional list scheduling with pressure, latency and resource heuristics. Read tryCandidate after Lesson 23.3 and again after Lesson 23.7, with -misched-print-dags output in hand.
    Cited in: overview, 01-machine-models, 02-dependence-dags, 03-list-scheduling, 07-llvm-schedulers

  • [LLVM-ModuloSchedule] LLVM's modulo-schedule code generators (prologue, kernel, epilogue; MVE; peeling) — llvm/lib/CodeGen/ModuloSchedule.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: ModuloScheduleExpander::expand, ModuloScheduleExpanderMVE, PeelingModuloScheduleExpander.
    Why and when: Three code generators for one schedule (Definition 23.6.11): phi renaming, modulo variable expansion and stage peeling. Read after Theorem 23.6.15.
    Cited in: 06-software-pipelining

  • [LLVM-NV2Sched] LLVM's Arm Neoverse V2 scheduling model — llvm/lib/Target/AArch64/AArch64SchedNeoverseV2.td in llvm/llvm-project at llvmorg-23.1.2. Symbols: NeoverseV2Model.
    Why and when: A modern Arm server-core model to compare with Skylake's (Lesson 23.1 §7): wider buffers, different port structure, the same TableGen vocabulary.
    Cited in: 01-machine-models

  • [LLVM-Peephole] LLVM's machine peephole optimizer — llvm/lib/CodeGen/PeepholeOptimizer.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: PeepholeOptimizer::optimizeCmpInstr, PeepholeOptimizer::isLoadFoldable, PeepholeOptimizer::optimizeExtInstr.
    Why and when: Target-hook-driven rewrites before allocation: compare elimination, load folding, copy rewriting (Lesson 23.10 §2).
    Cited in: 10-machine-peepholes-and-post-link

  • [LLVM-Pipeliner] LLVM's MachinePipeliner (swing modulo scheduling) — llvm/lib/CodeGen/MachinePipeliner.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: SwingSchedulerDAG::schedulePipeline, SwingSchedulerDAG::calculateRecMII, SwingSchedulerDAG::computeNodeOrder, ResourceManager::calculateResMII.
    Why and when: Core reading. SMS in production: MII, node sets, ordering and scheduling, with -pipeliner-* debug options. Read it after Lesson 23.6 §7 with the Hexagon box's -debug-only=pipeliner output.
    Cited in: 06-software-pipelining

  • [LLVM-PostRA] LLVM's legacy post-RA list scheduler with anti-dependence breaking — llvm/lib/CodeGen/PostRASchedulerList.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: SchedulePostRATDList, PostRAScheduler::runOnMachineFunction.
    Why and when: Top-down scheduling after allocation with a hazard recognizer and optional CriticalAntiDepBreaker / AggressiveAntiDepBreaker (Proposition 23.7.10).
    Cited in: 07-llvm-schedulers

  • [LLVM-RRList] SelectionDAG's bottom-up list schedulers (source, list-burr, list-hybrid, list-ilp) — llvm/lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: ScheduleDAGRRList::ListScheduleBottomUp, bu_ls_rr_sort, hybrid_ls_rr_sort, ilp_ls_rr_sort, src_ls_rr_sort.
    Why and when: Four priority functions on one bottom-up engine (Lesson 23.7 §2). Compare the sort functions with the priorities of Lesson 23.3.
    Cited in: 03-list-scheduling, 07-llvm-schedulers

  • [LLVM-ScheduleDAG] LLVM's scheduling-DAG node and edge types — llvm/include/llvm/CodeGen/ScheduleDAG.h in llvm/llvm-project at llvmorg-23.1.2. Symbols: SDep, SUnit.
    Why and when: SUnit and SDep (kinds Data, Anti, Output, Order, with latencies), shared by the SelectionDAG and MachineInstr schedulers. Read it to decode DAG dumps.
    Cited in: 02-dependence-dags

  • [LLVM-SDInstrs] LLVM's dependence-DAG construction for MachineInstrs — llvm/lib/CodeGen/ScheduleDAGInstrs.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: ScheduleDAGInstrs::buildSchedGraph, ScheduleDAGInstrs::addPhysRegDeps, ScheduleDAGInstrs::addVRegDefDeps, ScheduleDAGInstrs::addChainDependencies.
    Why and when: The production version of Algorithm 23.2.6: a bottom-up walk with def/use maps, memory chains with a barrier, and the -dag-maps-huge-region cap. Read buildSchedGraph after Lesson 23.2 §7 with a -debug-only=machine-scheduler dump next to it.
    Cited in: 02-dependence-dags

  • [LLVM-SKLSched] LLVM's Skylake client scheduling model — llvm/lib/Target/X86/X86SchedSkylakeClient.td in llvm/llvm-project at llvmorg-23.1.2. Symbols: SkylakeClientModel, SKLWriteResPair, SKLFPDivider.
    Why and when: A full out-of-order model: ports, port groups, the non-pipelined FP divider and per-class latencies. Lesson 23.1's vdivpd example comes from here; grep a class name from an llvm-mca report to find its definition.
    Cited in: 01-machine-models

  • [LLVM-TailDup] LLVM's machine-level tail duplication — llvm/lib/CodeGen/TailDuplicator.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: TailDuplicator::tailDuplicateAndUpdate, TailDuplicator::shouldTailDuplicate.
    Why and when: The tail duplication LLVM runs early and during block placement. shouldTailDuplicate is the size heuristic; read it after Algorithm 23.4.6.
    Cited in: 04-region-scheduling

  • [LLVM-TargetSched] How schedulers query the machine model (operand latency with ReadAdvance) — llvm/lib/CodeGen/TargetSchedule.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: TargetSchedModel::computeOperandLatency, TargetSchedModel::computeInstrLatency.
    Why and when: The code behind Proposition 23.1.9: operand latency is the write's latency minus the read's advance. Read computeOperandLatency when a -debug-only=machine-scheduler dump shows an unexpected edge latency.
    Cited in: 01-machine-models

  • [LLVM-TargetSchedTD] The TableGen classes of LLVM's per-operand machine model — llvm/include/llvm/Target/TargetSchedule.td in llvm/llvm-project at llvmorg-23.1.2. Symbols: SchedMachineModel, ProcResource, SchedWriteRes, WriteRes, ReadAdvance.
    Why and when: The documentation-in-comments of the machine model of Definition 23.1.8: issue width, micro-op buffer, resources with ReleaseAtCycles, per-operand latency and forwarding. Read the header comment first, then look up each class a .td model uses.
    Cited in: 01-machine-models

  • [LLVM-TPC] Where the scheduling and machine-optimization passes sit in LLVM's code generator pipeline — llvm/lib/CodeGen/TargetPassConfig.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: TargetPassConfig::addMachinePasses, TargetPassConfig::addOptimizedRegAlloc.
    Why and when: The pass order of Lessons 23.7–23.10 in one function: MachineScheduler before allocation, post-RA scheduling after it, block placement and branch folding at the end.
    Cited in: 08-scheduling-and-register-allocation

Official documentation and specifications

  • [LLVM-MCA] llvm-mca — LLVM Machine Code Analyzer (command guide). LLVM 23.1.2. link
    Why and when: Options, views (-timeline, -resource-pressure, -bottleneck-analysis) and the meaning of every column in the summary. Keep it open while reproducing Lesson 23.1's boxes.
    Cited in: 01-machine-models

Talks and videos

  • [DD18] Andrea Di Biagio and Matt Davis. Understanding the Performance of Code Using LLVM's Machine Code Analyzer (llvm-mca). 2018 LLVM Developers' Meeting, 2018. link
    Why and when: The authors of llvm-mca walk through its pipeline (dispatch, scheduler, retire) and its views. Watch it before reading the llvm-mca boxes of Lesson 23.1 §7.
    Cited in: 01-machine-models