Registerzuteilung bezeichnet in der Programmoptimierung die Zuweisung von Programmvariablen zu Prozessorregistern. Ein Compiler hat typischerweise die Aufgabe, eine große Anzahl von Variablen auf eine kleine Anzahl von Registern zuzuweisen.

Das NP-vollständige[1] Problem der Registerzuteilung und Auslagerung kann auf das Problem des Graphfärbens reduziert werden, was 1982 von Gregory Chaitin gezeigt wurde.[2]

Einzelnachweise

Bearbeiten
  1. Fernando Magno Quintão Pereira, Jens Palsberg, Register Allocation after Classical SSA Elimination is NP-complete (PDF; 493 kB)
  2. Gregory J. Chaitin, Mark A. Auslander, Ashok K. Chandra, John Cocke, Martin E. Hopkins und Peter W. Markstein. Register allocation via coloring. Computer Languages, 6:47-57, 1981