Editing Register allocation (section)

===Common problems raised in register allocation===
Register allocation raises several problems that can be tackled (or avoided) by different register allocation approaches. Three of the most common problems are identified as follows:

;Aliasing: In some architectures, assigning a value to one register can affect the value of another: this is called aliasing. For example, the [[x86]] architecture has four general purpose 32-bit registers that can also be used as 16-bit or 8-bit registers.<ref>{{cite web |date=May 2019 |publisher=Intel |url=https://software.intel.com/sites/default/files/managed/39/c5/325462-sdm-vol-1-2abcd-3abcd.pdf | title = Intel® 64 and IA-32 Architectures Software Developer's Manual, Section 3.4.1 |url-status=dead |archive-url=https://web.archive.org/web/20190525125151/https://software.intel.com/sites/default/files/managed/39/c5/325462-sdm-vol-1-2abcd-3abcd.pdf |archive-date=2019-05-25}}</ref> In this case, assigning a 32-bit value to the eax register will affect the value of the al register.

;Pre-coloring: This problem is an act to force some variables to be assigned to particular registers. For example, in [[PowerPC]] [[calling convention]]s, parameters are commonly passed in R3-R10 and the return value is passed in R3.<ref>{{cite web |title=32-bit PowerPC function calling conventions |url=https://developer.apple.com/library/archive/documentation/DeveloperTools/Conceptual/LowLevelABI/100-32-bit_PowerPC_Function_Calling_Conventions/32bitPowerPC.html}}</ref>

;NP-Problem: Chaitin et al. showed that register allocation is an [[NP-completeness|NP-complete]] problem. They reduce the [[graph coloring]] problem to the register allocation problem by showing that for an arbitrary graph, a program can be constructed such that the register allocation for the program (with registers representing nodes and machine registers representing available colors) would be a coloring for the original graph. As Graph Coloring is an NP-Hard problem and Register Allocation is in NP, this proves the NP-completeness of the problem.{{sfn|Bouchez|Darte|Rastello|2006|p=4}}