Кіріспе

Компьютерлік компиляторды оңтайландыру әдісі

Компиляторды оңтайландыруда регистрді бөлу – процессордың шектеулі санындағы регистрлеріне жергілікті автоматты айнымалыларды және өрнектердің нәтижелерін тағайындау процесі болып табылады. Регистрді бөлу негізгі блок бойынша (жергілікті регистрді бөлу), бүкіл функция/процедура бойынша (жалпы регистрді бөлу) немесе шақыру графигі арқылы өтетін функция шекаралары бойынша (процедурааралық регистрді бөлу) жүзеге асырылуы мүмкін. Егер функция/процедура бойынша орындалса, шақыру конвенциясы әр шақыру орнына сақтау/қайта келтіру операцияларын енгізуді талап етуі мүмкін.

Тізілімді бөлу компоненттері

Тіркелімдерді бөлу, орындалу кезінде айнымалыларды қайда сақтауды таңдаудан тұрады, яғни тіркелімдердің ішінде немесе сыртында. Егер айнымалы тіркелімдерде сақталса, бөлуші осы айнымалының қай тіркелімдерде сақталарынын анықтауы керек. Соңында, тағы бір қиындық – айнымалы бір орында қанша уақыт сақталуы керектігін анықтау. Тіркелімдерді бөлуші, таңдалған бөлу стратегиясын ескермей, осы қиындықтарды шешу үшін негізгі әрекеттер жиынтығына сүйене алады. Бұл әрекеттерді бірнеше санатқа бөлуге болады:

Қозғалыс енгізу – Бұл регистрлер арасындағы қозғалыс нұсқауларының санын арттырудан тұрады, яғни айнымалының өмір бойы бір емес, әртүрлі тіркелімдерде болуын қамтамасыз ету. Бұл екіге бөлінген тірі диапазон тәсілінде кездеседі.
Жадыға құю – Бұл тіркелімдердің орнына айнымалыны жадқа сақтаудан тұрады.
Тағайындау – Бұл тіркелімді айнымалыға тағайындаудан тұрады.
Біріктіру – Бұл регистрлер арасындағы қозғалыстар санын шектеуден тұрады, соның арқасында нұсқаулардың жалпы саны азаяды. Мысалы, әртүрлі әдістерде тірі айнымалыны анықтап, оны өмір бойы бір тіркелімде сақтау арқылы.
Көптеген тіркелімдерді бөлу тәсілдері бір немесе бірнеше нақты әрекеттер санаттарын оңтайландыруға бағытталған.

Тізілімдерді бөлуде кездесетін жалпы проблемалар

Тізілімдерді бөлуде әртүрлі тәсілдермен шешілетін (немесе одан сақталынатын) бірнеше мәселелер туындайды. Ең көп кездесетін үш мәселе келесідей сипатталады:

Алиасинг Кейбір архитектураларда бір тізілімге мән тағайындау екінші тізілімнің мәніне әсер етуі мүмкін: мұны алиасинг деп атайды. Мысалы, x86 архитектурасында төрт жалпы мақсаттағы 32 биттік тізілім бар, оларды 16 биттік немесе 8 биттік тізілімдер ретінде де пайдалануға болады. Осы жағдайда, eax тізіліміне 32 биттік мән тағайындалса, al тізілімінің мәні де өзгереді. Алдын ала түстің тағайындалуы Бұл мәселе кейбір айнымалыларды нақты тізілімдерге тағайындауға мәжбүрлеу болып табылады. Мысалы, PowerPC шақыру конвенцияларында параметрлер әдетте R3-R10 арқылы беріледі, ал қайтарылатын мән R3 арқылы беріледі. NP мәселесі Chaitin және авторлар тобы тізілімдерді бөлу NP-толық мәселе екенін көрсетті. Олар графикті бояу мәселесін тізілімдерді бөлу мәселесіне келтіріп, кез келген граф үшін бағдарламаны құруға болатынын көрсетті, онда бағдарлама үшін тізілімдерді бөлу (тізілімдер түйіндерді, ал қол жетімді түстерді білдіретін машина тізілімдері) бастапқы графты бояуға сәйкес келеді. Графикті бояу NP-қиын мәселе болғандықтан және тізілімдерді бөлу NP класында болғандықтан, бұл мәселенің NP-толықтығын дәлелдейді.

Тіркелімдерді бөлу әдістері

Тіркелімді бөлу кодтың негізгі блогы бойынша жүзеге асырылуы мүмкін: мұндай бөлу "жергілікті" деп аталады және алғаш рет Хорвиц және авторлар тобы атап өткен. Негізгі блоктарда тармақталулар болмайтындықтан, бөлу процесі жылдам деп есептеледі, себебі бақылау ағыны графигінің біріктірілу нүктелерін басқару тіркелімді бөлу кезінде көп уақыт алатын операция болып табылады. Дегенмен, бұл тәсілдің бүкіл компиляция бірлігі (мысалы, әдіс немесе процедура) бойынша жұмыс істейтін "жаһандық" тәсілдей оңтайландырылған кодты тудырмайды деп саналады.

Графикті бояулауды бөлу

Графикті бояу арқылы бөлу – регистрлерді бөлу мәселесін шешудің басым тәсілі. Оны алғаш рет Chaitin және авторлар тобы ұсынған. Бұл тәсілде графтың түйіндері тірі диапазонды (айнымалылар, уақытша сақтағыштар, виртуалды/символдық регистрлер) көрсетеді, олар регистрлерді бөлуге үміткер. Графтың қабырғалары бір-бірімен араласатын, яғни бағдарламаның кем дегенде бір нүктесінде бірдей уақытта қолданылатын тірі диапазонды байланыстырады. Регистрлерді бөлу мәселесі графты бояу мәселесіне дейін тоғытылады, онда түстер (регистрлер) түйіндерге тағайындалады, сонда қабырғамен байланысқан екі түйін бірдей түс алмайды. Тіршілік талдауды қолдану арқылы араласу графы құрылуы мүмкін. Араласу графы – бағдарламаның айнымалылары түйіндер болатын бағытталмаған граф. Ол қай айнымалыларды бір регистрге тағайындауға болмайтынын модельдеу үшін қолданылады.

Кемшіліктері мен одан әрі жетілдірілгендер

Графикті бояу арқылы тіркелімдерді бөлудің үш негізгі кемшілігі бар. Біріншіден, ол графикті бояуға сүйенеді, ол NP-толық проблемасы болып табылады және қай айнымалылардың төгілу керектігін анықтау үшін қолданылады. Минималды боялған графты табу да NP-толық проблема болып табылады. Екіншіден, егер тірі диапазонды бөлу қолданылмаса, шығарылған айнымалылар толығымен төгіледі: сақтау командалары айнымалылар анықталғаннан кейін мүмкіндігінше ертерек енгізіледі, ал жүктеу командалары айнымалылар қолданылғанға дейін кейінірек енгізіледі. Үшіншіден, төгілмеген айнымалы өмір бойында бір тіркелімде сақталады. Екінші жағынан, бір тіркелім атауы бірнеше тіркелім кластарында кездесуі мүмкін, мұнда класс – белгілі бір рөлде бір-бірімен алмастырылатын тіркелім атауларының жиынтығы. Содан кейін, бірнеше тіркелім атаулары бір аппараттық тіркелімнің синонимі болуы мүмкін. Ақырында, графикті бояу – тіркелімдерді бөлудің агрессивті әдісі, бірақ ол интерференциялық графты пайдалануға байланысты есептеу жағынан қымбат, оның ең нашар жағдайдағы мөлшері тірі диапазон санының квадратына тең болуы мүмкін. Графикті бояу арқылы тіркелімдерді бөлудің дәстүрлі түрі жалпы мақсаттағы тіркелімдердің бір банкін қарастырады және бір-бірімен қабаттаспайтын тіркелімдер жұптары, арнайы тіркелімдер және бірнеше тіркелімдер банктері сияқты ерекше архитектуралық ерекшеліктерді ескермейді. Chaitin стиліндегі графикті бояу әдісін жетілдірушілердің бірі Briggs және авторлар тобы болды: олардың әдісі консервативті біріктіру деп аталады. Бұл жетістік екі тірі диапазонды біріктірудің қашан мүмкін екенін анықтау үшін критерий қосады. Бастысы, араласпау талаптарынан басқа, екі айнымалыны біріктіру тек олардың бірігуі одан әрі төгілуге әкелмесе ғана мүмкін. Бриггс және авторлар тобы Шайтиннің жұмысына тағы бір жақсарту енгізді, ол – бағытталған бояу. Бағытталған бояу көшірмемен байланысты тірі диапазонға графиктегі бірдей түсті тағайындауға тырысады.

Сызықтық сканерлеу

Сызықтық сканерлеу – тағы бір жаһандық тіркелімдерді бөлу әдісі. Оны алғаш рет 1999 жылы Poletto және авторлар ұсынған. Бұл әдісте кодты графқа түрлендірмейді. Оның орнына, барлық айнымалылар олардың тірі аралығын анықтау үшін сызықтық түрде сканерленеді, ол интервал түрінде көрсетіледі. Барлық айнымалылардың тірі аралықтары анықталғаннан кейін, интервалдар хронологиялық ретпен қарастырылады. Бұл қарастыру тірі аралықтары қақтығысатын айнымалыларды анықтауға көмектеседі, бірақ қақтығыс графы құрылмайды және айнымалылар ашкөздік принципі бойынша бөлінеді. Бұл әдістің мақсаты – жылдамдық, бірақ жасалған кодтың орындалу уақытында емес, кодты құруға жұмсалатын уақыт тұрғысынан. Әдетте, стандартты графқа бояу әдістері сапалы кодты шығарады, бірақ олардың үлкен қосымша шығындары бар, себебі қолданылатын графқа бояу алгоритмінің күрделігі квадраттық. Осы ерекшелігінің арқасында сызықтық сканерлеу қазіргі уақытта бірнеше JIT компиляторларында қолданылады, мысалы Hotspot клиенттік компиляторы, V8, Jikes RVM және Android Runtime (ART). Hotspot серверлік компиляторы өзінің жоғары сапалы коды үшін графқа бояу әдісін пайдаланады.

Кемшіліктері мен одан әрі жетілдірілгендер

Алайда, сызықтық сканерлеудің екі маңызды кемшілігі бар. Біріншіден, оның «ашкөздік» қасиетіне байланысты, ол өмірлік аралықтағы бос орындарды, яғни «айнымалының мәні қажет емес кезеңдерді» ескермейді. Сонымен қатар, төгілген айнымалы өмір бойында төгіліп қалады. Полеттоның сызықтық сканерлеу алгоритміне көптеген зерттеу жұмыстары жандама жатты. Мысалы, Traub және авторлар жақсы сапалы кодты жасауға бағытталған «екінші мүмкіндік бинпакингі» деп аталатын алгоритмді ұсынды. Бұл тәсілде төгілген айнымалылар стандартты сызықтық сканерлеу алгоритмінен өзгеше эвристика қолдану арқылы кейінірек тіркелімге сақталу мүмкіндігіне ие болады. Алгоритм тірі аралықтарды пайдаланудың орнына тірі диапазонға сүйенеді, яғни диапазонды төгу қажет болса, осы айнымалыға сәйкес келетін басқа барлық диапазонды төгудің қажеті жоқ. Сызықтық сканерлеуді SSA формасының артықшылықтарын пайдалану үшін де бейімдеуге болады: осы аралық өрнектеудің қасиеттері бөлу алгоритмін жеңілдетеді және өмірлік аралықтағы бос орындарды тікелей есептеуге мүмкіндік береді. Біріншіден, өмірлік аралықтарды құруға бағытталған деректер ағыны графигін талдауға жұмсалатын уақыт қысқарады, әсіресе айнымалылар бірегей болғандықтан. Осының салдарынан, жаңа тапсырманың әрқайсысы жаңа тірі аралыққа сәйкес келетіндей, қысқа тірі аралықтар жасалады. Интервалдарды және өмірлік аралықтағы бос орындарды модельдеуден аулақ болу үшін Роджерс «болашақ белсенді жиынтықтар» деп аталатын жеңілдетуді көрсетті, ол нұсқаулардың 80% үшін интервалдарды сәтті жойды.

Гибридті бөлу

Кейбір басқа тіркелімдерді бөлу тәсілдері тіркелімдерді пайдалануды оңтайландыру үшін бір ғана әдіспен шектелмейді. Мысалы, Кавазос және авторлар сызықтық сканерлеу және графты бояу алгоритмдерін бірдей қолдануға мүмкіндік беретін шешім ұсынды. Бұл тәсілде, қай шешімді таңдау динамикалық түрде анықталады: алдымен, машиналық оқыту алгоритмі "оффлайн" режимінде, яғни жұмыс істеу кезінде емес, қандай бөлу алгоритмін қолдану керектігін анықтайтын эвристикалық функцияны құру үшін қолданылады. Содан кейін эвристикалық функция жұмыс істеу кезінде пайдаланылады; кодтың мінез-құлқына байланысты, бөлуші екі қолжетімді алгоритмнің біреуін таңдай алады. Трассалық тіркелімдерді бөлу – Eisl және авторлар әзірлеген жаңа тәсіл. Бұл техника бөлуді жергілікті түрде жүзеге асырады: ол динамикалық профильдеу деректеріне сүйене отырып, берілген басқару ағыны графигінде қай тармақтар ең көп қолданылатынын анықтайды. Содан кейін ол "трассалар" (яғни код сегменттері) жиынтығын анықтайды, онда ең көп қолданылатын тармаққа басымдық беріліп, біріктіру нүктесі ескерілмейді. Әрбір трасса бөлушімен жеке өңделеді. Бұл тәсіл гибридтік деп санауға болады, өйткені әртүрлі трассаларда әртүрлі тіркелімдерді бөлу алгоритмдерін қолдануға болады.

Бөлінген үлестіру

Бөлшек бөлу – әртүрлі тәсілдерді біріктіретін, көбінесе қарама-қарсы саналатын, тағы бір тіркелімдерді бөлу әдісі. Мысалы, гибридтік бөлу әдісін бөліп қарастыруға болады, себебі бірінші эвристикалық құрастыру кезеңі оффлайн режимінде, ал эвристикалық қолданылуы онлайн режимінде жүзеге асырылады. Сол сияқты, Б. Диуф және авторлар тобы оффлайн және онлайн мінез-құлқына негізделген, атап айтқанда статикалық және динамикалық компиляцияға негізделген бөлу әдісін ұсынды. Оффлайн кезеңінде, ең алдымен, бүтін сандық сызықтық бағдарламалау арқылы ең оңтайлы төгілу жиынтығы анықталады. Содан кейін, тірі диапазонды бұрын анықталған оңтайлы төгілу жиынтығына сүйенетін компресс-аннотация алгоритмі арқылы белгілеу жүргізіледі. Тіркелімдерді бөлу кейіннен онлайн кезеңінде, оффлайн кезеңінде жиналған деректер негізінде жүзеге асырылады. 2007 жылы Буше және авторлар тобы тіркелімдерді бөлуді әртүрлі кезеңдерге бөлуді ұсынды, бір кезең төгілуге, ал екіншісі бояуға және біріктіруге арналған.

Әртүрлі әдістерді салыстыру

Бірнеше өлшемдер бір тізілімді бөлу әдісін екіншісімен салыстыру үшін қолданылды. Тізілімді бөлу әдетте код сапасы, яғни жылдам орындалатын код, және талдау жүктемесі, яғни оңтайландырылған тізілімді бөлумен код жасау үшін бастапқы кодты талдауға жұмсалатын уақыт арасындағы қарым-қатынасты ескереді. Осы тұрғыдан алғанда, жасалған кодтың орындалу уақыты және тірілік талдауына жұмсалған уақыт әртүрлі әдістерді салыстыру үшін маңызды өлшемдер болып табылады. Тиісті өлшемдер таңдалғаннан кейін, өлшемдер қолданылатын код қолжетімді болуы керек және мәселеге қатысты болуы тиіс, не нақты қолданбалардың мінез-құлқысын көрсету арқылы, не алгоритм шешуге тырысатын нақты мәселеге қатысты болуы керек. Тізілімді бөлу туралы жақындағы мақалаларда Dacapo сынақ жиынтығы жиі қолданылады.