Wie ein Compiler-Autor die Registerzuweisung mit einer Lebendigkeitsanalyse meistert
An ode to livelyness analysis; SSA to registers
In einem persönlichen Erfahrungsbericht erklärt der Autor, wie er für seine Sprache purple-garden eine Lebendigkeitsanalyse implementiert, um virtuelle Register auf die begrenzten Hardware-Register und den Stack abzubilden. Der SSA-basierte IR mit Blockparametern statt Phi-Knoten macht die Analyse überraschend einfach: Blöcke durchlaufen, Terminatoren und Instruktionen rückwärts besuchen, Parameter beobachten. Anschließend fließen die berechneten Lebenszeiten in die Registerzuweisung für die Bytecode-VM und den x86-JIT-Compiler ein.
Register allocation is assigning the unlimited amount of virtual registers to the limited set of storage resources hardware has, specifically the gprs (general purpose registers), the fprs (floating point registers) and the stack.