Кіріспе

NOTOC
Компьютерлік ғылымда нұсқауды таңдау – компилятордың артқы бөлігінің (бэкенд) орта деңгейлі аралық өрнегін (IR) төмен деңгейлі IR-ге түрлендіретін кезеңі. Типик компиляторда нұсқауды таңдау нұсқауды жоспарлау және регистрлерді бөлуден бұрын орындалады; демек, оның шығыс IR-і шексіз псевдо-регистрлер жиынтығын (көбінесе уақытша шамалар деп аталады) қамтиды және одан әрі тесік арқылы оңтайландыруға түсуі мүмкін, және көбінесе түседі. Басқа жағдайларда ол мақсатты машина кодына, байт-кодына немесе тілдік құрастыруға өте ұқсас болады. Мысалы, келесі орта деңгейлі IR коды тізбегі үшін:
t1 = a
t2 = b
t3 = t1 + t2
a = t3
b = t1

x86 архитектурасы үшін жақсы нұсқаулар тізбегі:

MOV EAX, a
XCHG EAX, b
ADD a, EAX

Нұсқауды таңдау туралы толық шолу үшін қараңыз.

Макролық кеңею

Нұсқауды таңдаудың ең қарапайым тәсілі макро кеңейту немесе интерпретациялық кодты құру деп аталады. Макроны кеңейтетін нұсқау таңдаушысы орта деңгейдегі ИЖ-де (IR) үлгілерді сәйкестендіру арқылы жұмыс істейді. Сәйкестік табылғаннан кейін, тиісті макро орындалады, ол IR-дің сәйкес келетін бөлігін кіріс ретінде пайдаланады және тиісті мақсатты нұсқауларды шығарады. Макро кеңейтуді тікелей орта деңгейдің мәтіндік көрсетілімі бойынша жасауға болады, немесе IR алдымен графикалық көрсетілімге түрлендіріліп, содан кейін тереңдік бойынша қарастырылады. Соңғы жағдайда, үлгі графиктегі бір немесе бірнеше жақын түйіндерге сәйкес келеді. Егер мақсатты машина өте қарапайым болмаса, макро кеңейтуді жеке пайдалану көбінесе тиімсіз кодты тудырады. Бұл шектеуді азайту үшін, осы тәсілді қолданатын компиляторлар оны «көз тіткісі» (peephole) оптимизациясымен біріктіреді, бұл қарапайым нұсқаулардың комбинацияларын өнімділікті арттыратын және код көлемін азайтатын күрделі эквиваленттерімен алмастырады. Бұл Дэвидсон-Фрейзер тәсілі деп аталады және қазіргі уақытта GCC-де қолданылады.

Графикті жабу

Тағы бір тәсіл – орта деңгейдегі аралық тілді (IR) алдымен графқа түрлендіру, содан кейін осы графты үлгілермен жабу. Үлгі – графтың бір бөлігімен сәйкес келетін және нысаналық машинаның бір ғана нұсқауы арқылы іске асырылатын шаблон. Мақсат – таңдалған үлгілердің жалпы құны ең төмендеуін қамтамасыз ету арқылы графты жабу, мұнда құн әдетте нұсқауды орындауға қажетті циклдар санын көрсетеді. Ағаш тәрізді графтар үшін ең төмен құнды жабу динамикалық бағдарламалау арқылы сызықтық уақытта табылады, бірақ бағытталған ациклдық графтар (DAG) және толыққанды графтар үшін мәселе NP-толық болып табылады, сондықтан көбінесе ашкөз алгоритмдер немесе комбинаторлық оптимизациялау әдістері қолданылады.