Understanding LLVM Instruction Scheduling Algorithms and Topological Sorting

Instruction scheduling is essential for modern pipelined CPUs because each pipeline stage (fetch, decode, execute, write‑back) can be idle if successive instructions have dependencies, leading to low overall throughput.

Dependencies are categorized as data (the next instruction uses the previous result), chain (ordering constraints within memory accesses), and glue (instructions that must stay together), and eliminating them enables parallel execution.

Scheduling can be dynamic, performed at runtime with hardware support, or static, performed by the compiler; the article focuses on static scheduling.

LLVM implements several scheduling scopes: local (per basic block using List Scheduling heuristics), global (across multiple blocks with Trace, Superblock, or Hyperblock techniques), and loop scheduling for iterative code.

Because instruction scheduling and register allocation influence each other, LLVM provides pre‑register‑allocation (Pre‑RA‑MISched) and post‑register‑allocation (Post‑RA‑TDList, Post‑RA‑MISched) schedulers, as well as SelectionDAG‑based algorithms.

LLVM offers three configurable stages for scheduling: Stage Ⅰ (SelectionDAG‑based algorithms such as Linearize, Fast, BURR List, Source List, Hybrid List), Stage Ⅱ (MIR‑based pre‑RA scheduling including Pre‑RA‑MISched and Swing Modulo Scheduling), and Stage Ⅲ (MIR‑based post‑RA scheduling with Post‑RA‑TDList and Post‑RA‑MISched).

The core of these algorithms is topological sorting of the instruction dependency DAG: nodes with zero in‑degree are queued, processed, and removed while updating successors, repeating until the queue is empty; heuristics then prioritize nodes to improve parallelism.

Overall, LLVM’s instruction scheduling combines topological sorting with various heuristics across multiple compilation phases to reduce pipeline stalls and increase execution efficiency.