Abstrakt. Registertilldelningen är NP-komplett i allmänhet men kan lösas i linjär tid för linjära program där varje variabel har högst en definitionspunkt om registerbanken är homogen. I detta dokument studerar vi register som kan vara alias: ett aliasregister kan användas både självständigt eller i kombination med ett närliggande register. Sådana register finns i vanliga arkitekturer som x86, HP PA-RISC, Sun SPARC-processorn och MIPS flyttal. År 2004 presenterade Smith, Ramsey och Holloway den bästa algoritmen för aliaserad registerallokering hittills; deras algoritm är baserad på en heuristisk för färgning av allmänna grafer. De flesta arkitekturer med registeralias gör det möjligt att kombinera endast likriktade register: till exempel måste registret med låg adress ha ett jämnt nummer. Frågan om huruvida arbete med begränsade programklasser kan förbättra komplexiteten hos aliaserad registerfördelning med anpassningsbegränsningar är öppen hittills. I detta dokument visar vi att aliasd register allokering med anpassningsbegränsningar för straight-line-program är NP-fullständig.
Problemet med gratis tilldelning av register är NP-komplett även i närvaro av registerklasser och alias REF ].
Aliased Register Allocation for Straight-line Programs is NP-complete
{'venue': 'Theor. Comput. Sci.', 'journal': 'Theor. Comput. Sci.', 'mag_field_of_study': ['Mathematics', 'Computer Science']}