Кіріспе
Басқару ағыны графигіндегі әрбір жол бір тораптан өтіп, екіншісіне жетуі керек.
1 dom 3 4 5 6 2 dom 3 dom 4 dom 5 dom 6 dom Тиісті үстемдік қатынасы: қатаң үстемдік етілмейді, бірден үстемдік етеді.
Компьютерлік ғылымда, бақылау ағыны графигінің d торабы n торабына үстемдік етеді, егер кіріс торабынан n-ге дейінгі барлық жол d-ден өтуі керек болса. Белгіленуі бойынша, бұл d dom n (немесе кейде d ≫ n) деп жазылады. Анықтама бойынша, әрбір торап өзіне үстемдік етеді. Бірнеше байланысты ұғымдар бар:
d торабы n торабына қатаң үстемдік етеді, егер d n-ге үстемдік етсе және d, n-ге тең болмаса.
n торабының тікелей үстемдігі немесе idom – бұл n-ге қатаң үстемдік ететін, бірақ n-ге қатаң үстемдік ететін басқа торапқа қатаң үстемдік етпейтін бірегей торап. Кіріс торабынан басқа әрбір тораптың тікелей үстемдігі бар. Проссер доминантты есептеу алгоритмін ұсынған жоқ, ол Эдвард С. Лоури мен С. В. Медлок күтетін он жылды құрады. Рон Сайтрон және басқалар 1989 жылы оны статикалық бір тапсырма түрінде қолданылатын φ функцияларының орналасуын тиімді есептеу мәселесіне қолданған кезде үстемдікке қызығушылықты қайта жаңартты.
The immediate dominator or idom of a node n is the unique node that strictly dominates n but does not strictly dominate any other node that strictly dominates n. Every node, except the entry node, has an immediate dominator. Prosser did not present an algorithm for computing dominance, which had to wait ten years for Edward S. Lowry and C. W. Medlock. Ron Cytron et al. rekindled interest in dominance in 1989 when they applied it to the problem of efficiently computing the placement of φ functions, which are used in static single assignment form.
Қолданбалар
Доминаторлар, әсіресе доминанттық шекаралар, статикалық бір ғана тапсырманы есептеу үшін компиляторларда қолданылады. Компиляторды оңтайландырудың көптеген түрлері де доминаторлардан пайда көреді. Бұл жағдайда ағын графигі негізгі блоктардан тұрады. Автоматты параллелдеу доминанттықтан кейінгі шекаралар арқылы жақсартылады. Бұл бақылау тәуелділігін есептеудің тиімді әдісі болып табылады, бұл талдау үшін маңызды. Жадты пайдалануды талдау, ақауларды оңай табу және жоғары жадты пайдалануды анықтау үшін доминатор ағашынан пайдалана алады. Аппараттық жүйелерде доминаторлар сигналдардың ықтималдығын есептеу үшін, қуат және шуды талдау үшін коммутациялық белсенділікті бағалау және эквиваленттілікті тексеруде кесу нүктелерін таңдау үшін қолданылады. Бағдарламалық жүйелерде олар құрылымдық сынау техникаларында, мысалы, операторлар мен тармақтарды қамтуда сынақ жиынтығының мөлшерін азайту үшін қолданылады.
Үстемдікке дейінгі кезең
Жоғарыдағы доминанттық анықтамасына ұқсас, егер n түйінінен басталып, графтың шығу түйініне баратын барлық жолдар z түйіні арқылы өтуі керек болса, z түйіні n түйінін постдоминациялайды делінеді. Сол сияқты, n түйінінің тікелей постдоминаторы – n түйінінің басқа постдоминаторларын қатаң түрде постдоминацияламайтын постдоминаторы болып табылады.