3.3.3. Unison-Style Global Code Generator (Compiler Core)

[Mathnerd314]

Desired function
Solve instruction selection, register allocation, and scheduling in one integrated NP-hard model, with tunable optimization budgets. github

Futamura role
Provides the low-level back-end used by the compiler (c) to map residual programs or interpreter specializations to machine code.

Inputs

• Low-level IR from partial evaluator or front-end.
• Target machine model (instructions, register classes, pipeline resources, ABI).
• Optional profile data and throughput predictions
  • edge frequencies, block hotness, branch statistics
  • uiCA/Facile semanticscholar
• Optimization weights (runtime vs. size vs. compile time vs. power).

Processing

• Build unified constraint model:
  • Instruction selection alternatives, register constraints, scheduling constraints, ABI constraints.
• Seed with heuristic solution (pattern matching + linear scan + list scheduling).
• Run combinatorial search (ILP/CP-SAT/branch-and-bound), using implied constraints and dominance rules as in Unison presolver. past.date-conference
• Evaluate candidates via the tunable optimization objective engine (2.4).

Outputs

• Machine code per function/trace.
• Mapping IR → instructions/registers/schedule.
• Metadata: live ranges, spills, estimated cost.

Key references

• Unison, implied constraints for the presolver. diva-portal

[Mathnerd314]

More references:

• https://unison-code.github.io/publications.html
• https://unison-code.github.io/doc/manual.pdf
• Unison github

Also the main Unison project (and their publications list) covers only register allocation and instruction scheduling, but there was some more work from a guy associated with the project who explored constraint-based "universal instruction selection":

• https://github.com/unison-code/uni-instr-sel
• short paper: https://dcatkth.github.io/papers/diva2:1139368.pdf
• doctoral thesis: https://kth.diva-portal.org/smash/record.jsf?pid=diva2%3A1185339&dswid=-9800

Arguably code motion and dealing with choosing basic block boundaries is also a part of code generation, sort of an extension of instruction scheduling, but Wikipedia explicitly defines code generation as the trifecta of instruction scheduling, instruction selection, and register allocation (and also debugging info, but we are filing that under #10).

So it seems good to draw the boundary for the "code generator" component specifically as "takes fixed basic block structure, does trifecta of instruction scheduling, instruction selection, and register allocation", and say that the rest of the optimizations consist of the higher-level IR passes, #27.

[Mathnerd314]

More notes:

• Need abstraction for target machine model (instructions, register classes, pipeline resources, ABI).
• profile data and throughput predictions as input - edge frequencies, block hotness, branch statistics - do 1.3 Runtime Profiling, Instrumentation, & Baseline Behavior Estimator #16 first
• Build unified constraint model:
  • Instruction selection alternatives, register allocation constraints, scheduling constraints, ABI constraints.
• Seed with heuristic solution (pattern matching + linear scan + list scheduling) - this is the "fast path" and we may want to stop here if we're doing minimal optimization (we will analyze this tradeoff as part of 3.3.2 Tunable Optimization Objective Engine #28 and build a statistical model of the compile time vs. runtime performance tradeoff)
• Run combinatorial search (ILP/branch-and-bound) - NP-hard model - plan is to use Python CP-SAT bindings
• Evaluate candidates
  • combination of uiCA/Facile semanticscholar and the tunable optimization objective engine 3.3.2 Tunable Optimization Objective Engine #28 - should be able to directly encode optimization objective as CP-SAT objective
• Generate machine code Assembly code generation in Unison, also interrupt recovery tables for 0.1.3 Exceptions, Traps, and Error Handling #10
• implied constraints for the Unison presolver paper - adding "obvious" constraints and dominance rules helps the solver a lot, it can waste a lot of time exploring infeasible parts of the space