Register Allocation
রেজিস্টার অ্যালোকেশন
অসীম virtual/temp variable-কে সীমিত hardware register-এ বসানোর সমস্যা — আঁটে না হলে spill (stack-এ ঠেলে)। Graph coloring এর classic solution।
also: regalloc
Interference graph: দুই value একসাথে live হলে edge — coloring K=register:
live ranges: a[1..5], b[3..8], c[6..10]
edges: a–b, b–c → {a,c} এক color, b আলাদা- Chaitin-Briggs: simplify → potential spill → select → actual spill rewrite
- Spill মানে load/store insert — তাই “spill everywhere” অনেক সময় stack-slot codegen-এর চেয়ে খারাপ
- Live range splitting, rematerialization — spill-এর দাম কমানোর কৌশল
- JIT linear scan (Poletto-Sarkar): ধীর কিন্তু O(n log n) — compile-time latency-তে coloring-এর চেয়ে জরুরি
- ABI constraint fixed-color register (
rsp, arg registers) — pre-colored node