The complexity of register allocation

We complement these results by showing that optimal register allocation parametrized by r is W[SAT]-hard. This even holds for programs using only if/else and while as control structures; these programs form are subclass of the structured programs.