shopkeeper/korean_wiki_content_only_120125 huggingface dataset:
핍홀 최적화(Peephole optimization)는 핍홀 또는 윈도우로 알려진 소규모 컴파일러 생성 명령어 집합에 대해 수행되는 최적화 기법으로, 해당 명령어를 더 나은 성능을 가진 논리적으로 동등한 집합으로 대체하는 것을 포함한다.
핍홀 최적화라는 용어는 1965년에 윌리엄 마샬 매키먼이 도입했다.
핍홀 최적화 대체에는 다음이 포함되지만 이에 국한되지 않는다:
최신 컴파일러는 종종 패턴 매칭 알고리즘으로 핍홀 최적화를 구현한다.
느린 명령어를 빠른 명령어로 대체하기.
다음 자바 바이트코드:
은 더 빠르게 실행되는 다음 코드로 대체될 수 있다:
대부분의 핍홀 최적화와 마찬가지로, 이는 다른 명령어들의 상대적 효율성을 기반으로 한다. 이 경우, `dup` (스택의 맨 위를 복제하고 푸시하는)은 `aload` (지역 변수를 로드하고 스택에 푸시하는)보다 더 효율적인 것으로 알려져/가정된다.
불필요한 코드 제거하기.
다음 소스 코드:
는 간단히 다음과 같이 컴파일된다:
MOV b, R0 ; b를 레지스터로 복사
ADD c, R0 ; c를 레지스터에 더함, 레지스터는 이제 b+c
MOV R0, a ; 레지스터를 a로 복사
MOV a, R0 ; a를 레지스터로 복사
ADD e, R0 ; e를 레지스터에 더함, 레지스터는 이제 a+e [(b+c)+e]
MOV R0, d ; 레지스터를 d로 복사
하지만 다음으로 최적화할 수 있다:
ADD c, R0 ; c를 레지스터에 더함, 이는 이제 b+c (a)
ADD e, R0 ; e를 레지스터에 더함, 이는 이제 b+c+e [(a)+e]
불필요한 스택 명령어 제거하기.
컴파일러가 서브루틴을 호출하기 전에 레지스터를 스택에 저장하고 반환할 때 복원하는 경우, 연속적인 서브루틴 호출에는 중복된 스택 명령어가 있을 수 있다.
컴파일러가 각 프로시저 호출에 대해 다음 Z80 명령어를 생성한다고 가정하자:
PUSH AF
PUSH BC
PUSH DE
PUSH HL
CALL _ADDR
POP HL
POP DE
POP BC
POP AF
두 개의 연속적인 서브루틴 호출이 있다면 다음과 같이 보일 것이다:
CALL _ADDR1
CALL _ADDR2
동일한 레지스터에 대해 POP regs 뒤에 PUSH가 오는 시퀀스는 일반적으로 중복된다. 중복되는 경우, 핍홀 최적화는 이 명령어들을 제거할 것이다. 이 예시에서는 핍홀에 또 다른 중복 POP/PUSH 쌍이 나타나게 되고, 이들은 차례로 제거될 것이다. 서브루틴 _ADDR2가 이전 레지스터 값에 의존하지 않는다고 가정하면, 위 예시의 모든 불필요한 코드를 제거하면 결국 다음 코드가 남게 될 것이다:
컴퓨터 프로그래밍에서 루프 불변 코드는 프로그램의 의미론에 영향을 주지 않고 루프 본문 밖으로 이동할 수 있는 명령문 또는 표현식( 명령형 프로그래밍 프로그래밍 언어에서)으로 구성된다. 루프 불변 코드 이동(Loop-invariant code motion, 호이스팅 또는 스칼라 승격이라고도 함)은 이 이동을 자동으로 수행하는 컴파일러 최적화이다.
다음 코드 샘플에는 두 가지 최적화가 적용될 수 있다.
while (i &lt; n) {
a[i] = 6 * i + x * x;
codice_1와 codice_2 계산은 루프 불변이지만, 코드를 루프 밖으로 이동하기 전에 주의를 기울여야 한다. 루프 조건이 codice_3일 가능성(예: codice_4이 음수 값을 가질 경우)이 있으며, 이 경우 루프 본문은 전혀 실행되지 않아야 한다. 올바른 동작을 보장하는 한 가지 방법은 루프 외부에 조건부 분기를 사용하는 것이다. 루프 조건을 평가하는 것은 부작용을 가질 수 있으므로, codice_5 구성에 의한 추가 평가는 codice_6 루프를 codice_7로 대체하여 보상해야 한다. 코드가 처음부터 codice_7을 사용했다면, 루프 본문이 최소 한 번 실행될 것이 보장되므로 전체 보호 프로세스가 필요 없다.
if (i &lt; n) {
int const t1 = x * x;
a[i] = 6 * i + t1;
} while (i &lt; n);
이 코드는 더욱 최적화될 수 있다. 예를 들어, 강도 감소는 루프 내의 두 곱셈(codice_9 및 codice_10)을 제거할 수 있고, 유도 변수 제거는 codice_11를 완전히 생략할 수 있다. codice_12는 codice_11 자체와 동기화되어야 하므로 둘 다 가질 필요는 없다.
불변 코드 감지.
일반적으로, 도달 정의 분석은 명령문이나 표현식이 루프 불변인지 감지하는 데 사용된다.
예를 들어, 어떤 단순 표현식의 피연산자에 대한 모든 도달 정의가 루프 밖에 있다면, 그 표현식은 루프 밖으로 이동될 수 있다.
모이앙, 루비아노, 세이예의 최근 연구는 데이터 흐름 의존성 분석을 사용하여 불변 명령어뿐만 아니라 내부 루프와 같은 더 큰 코드 조각도 감지한다. 이 분석은 또한 임의의 차수의 준불변, 즉 루프 본문의 고정된 반복 횟수 후에 불변이 되는 명령어 또는 코드 조각을 감지한다. 이 기술은 후에 오베르, 루비아노, 루쉬, 세이예에 의해 루프를 자동으로 병렬화하는 데 사용되었다.
루프 밖으로 이동된 루프 불변 코드는 더 적게 실행되어 속도를 향상시킨다. 이 변환의 또 다른 효과는 상수를 레지스터에 저장하고 각 반복마다 주소를 계산하고 메모리(또는 캐시 라인)에 접근할 필요가 없다는 것이다.
그러나 너무 많은 변수가 생성되면, 특히 32비트 X86과 같이 레지스터가 적은 프로세서에서는 레지스터 압박이 높아진다. 컴파일러가 레지스터를 다 소진하면 일부 변수는 레지스터 스필링된다. 이를 상쇄하기 위해 역최적화인 재자료화가 수행될 수 있다.
고래자리 A 은하군은 고래자리 A를 중심으로 한 작은 은하군이다.
이 은하군을 NGC 1068 은하군()이라고도 한다.
소속 은하.
이에 속한 은하들은 다음과 같다.
루프 언롤링(Loop unrolling) 또는 루프 언와인딩(loop unwinding)은 프로그램의 이진 크기를 늘리는 대신 실행 속도를 최적화하려는 루프 변환 기술로, 이는 공간-시간 트레이드오프라고 알려진 접근 방식이다. 변환은 프로그래머가 수동으로 수행하거나 최적화 컴파일러가 수행할 수 있다. 최신 프로세서에서는 루프 언롤링으로 인해 코드 크기가 증가하여 캐시 미스가 더 많이 발생할 수 있으므로 역효과를 낼 때가 많다. 더프의 장치를 참고하라.&lt;ref name="lkml-0008.2/0171"&gt;&lt;/ref&gt;
루프 언와인딩의 목표는 각 반복에서 포인터 연산 및 "루프 끝" 테스트와 같이 루프를 제어하는 명령어를 줄이거나 제거하여 프로그램의 속도를 높이는 것이다. 분기 페널티를 줄이고, 메모리에서 데이터를 읽는 지연을 포함한 대기 시간을 숨기는 것이다. 이러한 계산 오버헤드를 제거하기 위해 루프는 유사한 독립적인 명령문의 반복 시퀀스로 다시 작성될 수 있다.
루프 언롤링은 또한 특정 형식 검증 기술, 특히 유한 모델 검사의 일부이다.
"타이트한" 루프의 오버헤드는 종종 배열의 다음 요소에 대한 포인터나 인덱스를 증가시키는 명령어(포인터 연산)와 "루프 종료" 테스트로 구성된다. 최적화 컴파일러나 어셈블러가 개별적으로 참조되는 각 배열 변수에 대한 오프셋을 미리 계산할 수 있다면, 이들은 기계어 명령어에 직접 내장될 수 있으므로 런타임에 추가적인 산술 연산이 필요하지 않다.
최적화 컴파일러는 때때로 자동으로 또는 요청에 따라 언롤링을 수행한다.
정적/수동 루프 언롤링.
수동 (또는 정적) 루프 언롤링은 프로그래머가 루프를 분석하고 반복을 루프 오버헤드를 줄이는 일련의 명령어로 해석하는 것을 포함한다. 이는 컴파일러에 의해 수행되는 동적 언롤링과는 대조된다.
C 언어의 간단한 수동 예시.
컴퓨터 프로그램의 한 절차는 컬렉션에서 100개의 항목을 삭제하는 것이다. 이는 일반적으로 delete(item_number) 함수를 호출하는 `for` 루프를 통해 수행된다. 이 프로그램 부분이 최적화되어야 하고, 루프의 오버헤드가 delete(x) 함수에 비해 상당한 리소스를 요구하는 경우, 언와인딩을 사용하여 속도를 높일 수 있다.
이 수정의 결과로 새 프로그램은 100번 대신 20번만 반복하면 된다. 그 후에는 점프와 조건부 분기의 20%만 수행하면 되며, 이는 많은 반복에 걸쳐 루프 관리 오버헤드의 잠재적으로 상당한 감소를 나타낸다. 최적의 이점을 얻으려면 언롤링된 코드에 포인터 연산이 필요한 변수를 지정해서는 안 된다. 이는 일반적으로 인덱스 참조 방식 대신 "기준 주소 + 오프셋" 주소 지정을 필요로 한다.
반면에 이 수동 루프 언롤링은 원본 코드 크기를 3줄에서 7줄로 확장하며, 이는 작성, 확인, 디버깅해야 한다. 또한 컴파일러는 확장된 루프 반복에서 변수를 저장하기 위해 더 많은 레지스터를 할당해야 할 수도 있다. 게다가, 언롤링된 루프 구조 내의 루프 제어 변수와 연산 횟수는 결과가 원래 코드와 동일하도록 신중하게 선택해야 한다(이미 작동하는 코드에 대한 후속 최적화라고 가정할 때). 예를 들어, 반복 횟수가 5로 나누어지지 않는 경우의 영향을 고려해 보라. 테스트 조건이 변수인 경우 수동 수정 사항은 다소 더 복잡해진다. 더프의 장치도 참조하라.
초기 복잡성.
간단한 경우, 루프 제어는 생산적인 명령문을 배열하는 단순한 관리 오버헤드이다. 루프 자체는 원하는 결과에 아무런 기여도 하지 않으며, 단지 프로그래머가 코드를 백 번 복제하는 지루함을 덜어줄 뿐이다. 이는 전처리가 복제를 생성하거나 텍스트 편집기가 수행할 수 있었던 일이다. 마찬가지로, `if` 문 및 기타 흐름 제어 문은 코드 복제로 대체될 수 있지만, 코드 블롯이 발생할 수 있다. 컴퓨터 프로그램은 조합을 쉽게 추적하지만, 프로그래머는 이러한 반복을 지루해하며 실수를 저지른다.
고려해 보자:
그러나 물론 수행되는 코드가 프로시저 호출일 필요는 없으며, 다음 예시에서는 계산에 인덱스 변수가 포함된다.
이것이 컴파일되면 많은 코드를 생성할 수 있지만(프린트 문이 악명 높음), 추가 최적화가 가능하다. 이 예시는 루프에서 x(i)와 x(i - 1)만을 참조한다(후자는 새로운 값 x(i)를 개발하기 위해서만). 따라서 여기서 개발된 배열 x에 대한 나중 참조가 없다고 가정하면, 그 사용은 단순 변수로 대체될 수 있다. 그러나 그러한 변경은 값이 변경되는 단순 변수를 의미할 것이지만, 배열을 유지한다면 컴파일러의 분석은 배열의 값이 상수이며, 각각 이전 상수에서 파생되었음을 인지하고 상수 값을 전달하여 코드가 다음과 같이 될 것이다.
print 2, 2;
print 3, 6;
print 4, 24;
일반적으로 루프의 내용은 크고 복잡한 배열 인덱싱을 포함할 수 있다. 이러한 경우는 최적화 컴파일러가 언롤링하는 것이 가장 좋다. 내부 루프를 복제하면 많은 최적화가 가능하지만, n이 크지 않으면 작은 이득만 얻을 수 있다.
WHILE 루프 언롤링.
다음과 유사한 의사코드 WHILE 루프를 고려해 보자.
이 경우, ENDWHILE(루프 시작으로 점프)이 66% 덜 실행되므로 언롤링이 더 빠르다.
심지어 더 좋은 것은 일부 최적화 컴파일러가 자동으로 수행할 수 있는 "조정된" 의사코드 예시로, 무조건 점프를 완전히 제거한다.
동적 언롤링.
루프 언롤링의 이점은 종종 배열의 크기에 따라 달라지며, 이는 런타임까지 알 수 없는 경우가 많기 때문에 JIT 컴파일러는 (예를 들어) "표준" 루프 시퀀스를 호출할지 아니면 각 요소에 대해 (상대적으로 짧은) 개별 명령어 시퀀스를 생성할지 결정할 수 있다. 이러한 유연성은 루프 언롤링의 맥락에서 정적 또는 수동 최적화와 비교하여 JIT 기술의 장점 중 하나이다. 이 상황에서는 n의 값이 비교적 작을 때 절약 효과가 여전히 유용하며, 프로그램 크기 전체적으로 거의 (또는 전혀) 증가시키지 않는다 (이는 표준 라이브러리의 일부로 한 번만 포함될 수 있다).
어셈블리어 프로그래머(최적화 컴파일러 개발자 포함)도 효율적인 분기 테이블에 사용되는 방법과 유사한 방법을 사용하여 동적 루프 언롤링 기술의 이점을 얻을 수 있다. 여기서 장점은 특정 배열에서 참조되는 필드의 최대 오프셋이 기계어 명령어로 지정할 수 있는 최대 오프셋보다 작은 경우에 가장 크다(초과하면 어셈블러가 플래그를 표시한다).
어셈블러 예시 (IBM/360 또는 Z/아키텍처).
이 예시는 IBM/360 또는 Z/아키텍처 어셈블러를 위한 것으로, FROM 배열에서 TO 배열로 100바이트 필드(오프셋 0)를 복사하는 것을 가정한다. 두 배열 모두 50개의 항목을 가지며 각 요소의 길이는 256바이트이다.
LM R15,R2,INIT Set R15 = maximum number of MVC
LOOP EQU * Define LOOP label.
SR R15,R0 Subtract the remaining number of
BNP ALL If R15 is not positive, meaning we
MH R15,=AL2(ILEN) Multiply R15 by the length of one
B ALL(R15) Jump to ALL+R15, the address of the
ALL MVC 15*256(100,R2),15*256(R1) Move 100 bytes of 16th entry from
ILEN EQU *-ALL Set ILEN to the length of the previous
MVC 14*256(100,R2),14*256(R1) Move 100 bytes of 15th entry.
MVC 13*256(100,R2),13*256(R1) Move 100 bytes of 14th entry.
MVC 12*256(100,R2),12*256(R1) Move 100 bytes of 13th entry.
MVC 11*256(100,R2),11*256(R1) Move 100 bytes of 12th entry.
MVC 10*256(100,R2),10*256(R1) Move 100 bytes of 11th entry.
MVC 09*256(100,R2),09*256(R1) Move 100 bytes of 10th entry.
MVC 08*256(100,R2),08*256(R1) Move 100 bytes of 9th entry.
MVC 07*256(100,R2),07*256(R1) Move 100 bytes of 8th entry.
MVC 06*256(100,R2),06*256(R1) Move 100 bytes of 7th entry.
MVC 05*256(100,R2),05*256(R1) Move 100 bytes of 6th entry.
MVC 04*256(100,R2),04*256(R1) Move 100 bytes of 5th entry.
MVC 03*256(100,R2),03*256(R1) Move 100 bytes of 4th entry.
MVC 02*256(100,R2),02*256(R1) Move 100 bytes of 3rd entry.
MVC 01*256(100,R2),01*256(R1) Move 100 bytes of 2nd entry.
MVC 00*256(100,R2),00*256(R1) Move 100 bytes of 1st entry.
S R0,MAXM1 Reduce the number of remaining entries
BNPR R14 If no more entries to process, return
AH R1,=AL2(16*256) Increment 'FROM' array pointer beyond
AH R2,=AL2(16*256) Increment 'TO' array pointer beyond
L R15,MAXM1 Reload the maximum number of MVC
B LOOP Execute loop again.
INIT DS 0A 4 addresses (pointers) to be
MAXM1 DC A(16) Maximum number of MVC instructions
N DC A(50) Number of actual entries in array (a
DC A(FROM) Address of start of array 1
DC A(TO) Address of start of array 2
FROM DS 50CL256 Array of 50 entries of 256 bytes each.
TO DS 50CL256 Array of 50 entries of 256 bytes each.
이 예시에서는 "기존" 루프(50회 반복)를 사용하면 약 202개의 명령어가 필요하지만, 위 동적 코드는 약 89개의 명령어만 필요하므로 약 56%의 절약 효과가 있다. 배열에 두 개의 항목만 포함되어 있었다면, 원래 언롤링된 루프와 거의 같은 시간으로 실행되었을 것이다. 배열에 수천 개의 항목이 있더라도 코드 크기 증가는 약 108바이트에 불과하다.
여러 명령어가 관련되어 있는 경우에도 결합된 명령어 길이가 그에 따라 조정되는 한 유사한 기술을 사용할 수 있다. 예를 들어, 이 동일한 예시에서 복사된 100바이트 필드 직후에 각 배열 항목의 나머지를 널 문자로 지워야 하는 경우, 추가 지우기 명령어인 `XC xx*256+100(156,R1),xx*256+100(R2)`를 시퀀스의 모든 MVC 바로 뒤에 추가할 수 있다(여기서 `xx`는 위 MVC의 값과 일치한다).
물론, 단일 어셈블러 매크로 명령문을 사용하여 위 코드를 "인라인"으로 생성하고 네다섯 개의 피연산자만 지정하거나(또는 간단한 호출로 접근할 수 있는 라이브러리 서브루틴으로 만들어 매개변수 목록을 전달하는 방식으로), 최적화를 쉽게 사용할 수 있도록 하는 것이 완벽하게 가능하다.
C 언어 예시.
다음 예시는 C로 작성된 간단한 프로그램에 대한 동적 루프 언롤링을 보여준다. 위 어셈블러 예시와 달리, 이 예시에서는 변수 (i)가 여전히 배열 요소를 주소 지정하는 데 사용되므로 컴파일러가 여전히 포인터/인덱스 연산을 생성한다. 완전한 최적화는 대체 명령문에서 절대 인덱스를 사용하는 경우에만 가능하다.
/* The number of entries processed per loop iteration. */
/* Note that this number is a 'constant constant' reflecting the code below. */
BUNCHSIZE = 8
int i = 0; /* counter */
int entries = 50; /* total number to process */
/* If the number of elements is not divisible by BUNCHSIZE, */
/* get repeat times required to do most processing in the while loop */
int repeat = (entries / BUNCHSIZE); /* number of times to repeat */
int left = (entries % BUNCHSIZE); /* calculate remainder */
/* Unroll the loop in 'bunches' of 8 */
while (repeat--)
printf("process(%d)\n", i );
printf("process(%d)\n", i + 1);
printf("process(%d)\n", i + 2);
printf("process(%d)\n", i + 3);
printf("process(%d)\n", i + 4);
printf("process(%d)\n", i + 5);
printf("process(%d)\n", i + 6);
printf("process(%d)\n", i + 7);
/* update the index by amount processed in one go */
i += BUNCHSIZE;
/* Use a switch statement to process remaining by jumping to the case label */
/* at the label that will then drop through to complete the set */
switch (left)
case 7 : printf("process(%d)\n", i + 6); /* process and rely on drop
through */
case 6 : printf("process(%d)\n", i + 5);
case 5 : printf("process(%d)\n", i + 4);
case 4 : printf("process(%d)\n", i + 3);
case 3 : printf("process(%d)\n", i + 2);
case 2 : printf("process(%d)\n", i + 1); /* two left */
case 1 : printf("process(%d)\n", i); /* just one left to process */
case 0 : ; /* none left */
코드 중복은 더프의 장치와 같이 두 부분을 함께 작성하여 피할 수 있다.
C에서 MIPS 어셈블리어 루프 언롤링 예시.
다음 예시는 codice_1 타입의 100개 항목 벡터 A와 B의 스칼라곱을 계산할 것이다. C 언어 코드는 다음과 같다:
double dotProduct = 0;
for (int i = 0; i &lt; 100; i++) {
dotProduct += A[i]*B[i];
MIPS 어셈블리어로 변환.
다음은 루프 언롤링을 구현하기 전에 100개 항목의 벡터 A와 B의 스칼라곱을 계산하는 MIPS 어셈블리어 코드이다. 아래 코드는 루프 초기화를 생략한다.
배열의 한 요소 크기(a `double`)는 8바이트이다.
loop3:
l.d $f10, 0($5) ; $f10 ← A[i]
l.d $f12, 0($6) ; $f12 ← B[i]
mul.d $f10, $f10, $f12 ; $f10 ← A[i]*B[i]
add.d $f8, $f8, $f10 ; $f8 ← $f8 + A[i]*B[i]
addi $5, $5, 8 ; increment pointer for A[i] by the size
; of a double.
addi $6, $6, 8 ; increment pointer for B[i] by the size
addi $7, $7, -1 ; decrement loop count
bgtz $7, loop3 ; Continue if loop count &gt; 0
MIPS에서 루프 언롤링.
다음은 위와 같지만, 4배로 루프 언롤링을 구현한 것이다. 배열의 한 요소 크기(a `double`)는 8바이트이므로 0, 8, 16, 24 변위와 각 루프의 32 변위를 다시 참고한다.
l.d $f10, 0($5) ; iteration with displacement 0
l.d $f12, 0($6)
mul.d $f10, $f10, $f12
add.d $f8, $f8, $f10
l.d $f10, 8($5) ; iteration with displacement 8
l.d $f12, 8($6)
l.d $f10, 16($5) ; iteration with displacement 16
l.d $f12, 16($6)
l.d $f10, 24($5) ; iteration with displacement 24
l.d $f12, 24($6)
addi $5, $5, 32
addi $6, $6, 32
addi $7, $7, -4
bgtz $7, loop3 ; Continue loop if $7 &gt; 0
컴파일러 구성에서 강도 감소 또는 스트렝스 리덕션(strength reduction)은 비용이 많이 드는 연산을 동등하지만 비용이 적게 드는 연산으로 대체하는 컴파일러 최적화이다. 강도 감소의 고전적인 예는 루프 내의 강한 곱셈을 약한 덧셈으로 변환하는 것으로, 이는 배열 주소 지정에서 자주 발생한다.
강도 감소의 예로는 루프 내의 곱셈을 덧셈으로 대체하고 루프 내의 거듭제곱을 곱셈으로 대체하는 것이 있다.
프로그램 실행 시간의 대부분은 일반적으로 코드의 작은 부분(핫 스팟이라고 불림)에서 소비되며, 이 코드는 종종 반복적으로 실행되는 루프 내에 있다.
컴파일러는 루프를 식별하고 해당 루프 내의 레지스터 값 특성을 인식하는 방법을 사용한다. 강도 감소를 위해 컴파일러가 관심을 갖는 것은 다음과 같다.
루프 불변은 본질적으로 루프 내에서 상수이지만, 그 값은 루프 외부에서 변경될 수 있다. 유도 변수는 알려진 양만큼 변경된다. 이 용어는 특정 루프에 상대적이다. 루프가 중첩될 때, 바깥쪽 루프의 유도 변수는 안쪽 루프의 루프 불변이 될 수 있다.
강도 감소는 루프 불변과 유도 변수를 포함하는 표현식을 찾는다. 이러한 표현식 중 일부는 단순화될 수 있다. 예를 들어, 루프 불변 codice_1와 유도 변수 codice_2의 곱셈은
c = 7;
for (i = 0; i &lt; N; i++)
y[i] = c * i;
연속적인 약한 덧셈으로 대체될 수 있다.
y[i] = k;
k = k + c;
강도 감소 예제.
다음은 배열 인덱싱 주소 계산에서 발생한 모든 루프 곱셈을 강도 감소시키는 예제이다.
배열을 단위 행렬로 설정하는 간단한 루프를 상상해 보자.
A[i,j] = 0.0;
A[i,i] = 1.0;
중간 코드.
컴파일러는 이 코드를 다음과 같이 볼 것이다.
0010 ; for (i = 0, i &lt; n; i++)
0020 ; {
0030 r1 = #0 ; i = 0
0040 G0000:
0050 load r2, n ; i &lt; n
0060 cmp r1, r2
0070 bge G0001
0090 ; for (j = 0; j &lt; n; j++)
0100 ; {
0110 r3 = #0 ; j = 0
0120 G0002:
0130 load r4, n ; j &lt; n
0140 cmp r3, r4
0150 bge G0003
0160
0170 ; A[i,j] = 0.0;
0180 load r7, n
0190 r8 = r1 * r7 ; calculate subscript i * n + j
0200 r9 = r8 + r3
0210 r10 = r9 * #8 ; calculate byte address
0220 fr3 = #0.0
0230 fstore fr3, A[r10]
0250 r3 = r3 + #1 ; j++
0260 br G0002
0280 G0003:
0290 ; A[i,i] = 1.0;
0300 load r12, n ; calculate subscript i * n + i
0310 r13 = r1 * r12
0320 r14 = r13 + r1
0330 r15 = r14 * #8 ; calculate byte address
0340 fr4 = #1.0
0350 fstore fr4, A[r15]
0360
0370 ; i++
0380 r1 = r1 + #1
0390 br G0000
0410 G0001:
이것은 2차원 배열 A를 n*n 크기의 1차원 배열로 표현하므로, 고수준 코드가 A[x, y]를 표현할 때마다 유효한 모든 인덱스 x와 y에 대해 내부적으로 A[(x*n)+y]가 된다.
많은 최적화.
컴파일러는 강도 감소뿐만 아니라 많은 최적화를 시작한다. 루프 내에서 상수(불변)인 표현식은 루프 밖으로 끌어올려진다. 부동 소수점 레지스터 fr3 및 fr4와 같은 상수는 두 루프 외부에서 로드될 수 있다. 일부 변수가 변경되지 않는다는 인식은 레지스터를 병합할 수 있게 한다. n은 상수이므로 r2, r4, r7, r12는 끌어올려지고 병합될 수 있다. 공통 값 i*n은 (끌어올려진) r8과 r13에서 계산되므로, 이들은 합쳐진다. 가장 안쪽 루프(0120-0260)는 11개에서 7개의 중간 명령어로 감소되었다. 가장 안쪽 루프에 남아있는 유일한 곱셈은 0210번 줄의 8 곱셈이다.
0020 {
0050 load r2, n
0130 ; load r4, n killed; use r2
0180 ; load r7, n killed; use r2
0300 ; load r12, n killed; use r2
0060 cmp r1, r2 ; i &lt; n
0190 r8 = r1 * r2 ; calculate subscript i * n
0310 ; r13 = r1 * r2 killed; use r8 ; calculate subscript i * n
0100 {
0140 cmp r3, r2 ; j &lt; n
0200 r9 = r8 + r3 ; calculate subscript i * n + j
0320 r14 = r8 + r1 ; calculate subscript i * n + i
0370 ;i++
더 많은 최적화가 필요하다. 레지스터 r3은 가장 안쪽 루프(0140-0260)의 주요 변수이다. 루프를 통과할 때마다 1씩 증가한다. 레지스터 r8(가장 안쪽 루프에서 불변)이 r3에 더해진다. 컴파일러는 r3 대신 r3을 제거하고 r9를 사용할 수 있다. 루프는 r3 = 0에서 n-1까지 제어되는 대신 r9=r8+0에서 r8+n-1까지 제어될 수 있다. 이는 4개의 명령어를 추가하고 4개의 명령어를 제거하지만, 루프 내부에는 하나의 명령어가 더 적다.
0110 ; r3 = #0 killed ; j = 0
0115 r9 = r8 ; new assignment
0117 r20 = r8 + r2 ; new limit
0140 ; cmp r3, r2 killed ; j &lt; n
0145 cmp r9, r20 ; r8 + j &lt; r8 + n = r20
0200 ; r9 = r8 + r3 killed ; calculate subscript i * n + j
0250 ; r3 = r3 + #1 killed ; j++
0255 r9 = r9 + #1 ; new loop variable
이제 r9가 루프 변수이지만, 8을 곱하는 연산과 상호작용한다. 여기에서 우리는 강도 감소를 할 수 있다. 8을 곱하는 연산은 8을 연속적으로 더하는 것으로 줄일 수 있다. 이제 루프 안에 곱셈 연산이 없다.
0118 r10 = r8 * #8 ; initial value of r10
0210 ; r10 = r9 * #8 killed ; calculate byte address
0245 r10 = r10 + #8 ; strength reduced multiply
0255 r9 = r9 + #1 ; loop variable
레지스터 r9와 r10(= 8*r9) 모두 필요하지 않다. 루프에서 r9를 제거할 수 있다. 이제 루프는 5개의 명령어로 구성된다.
0115 ; r9 = r8 killed
0117 r20 = r8 + r2 ; limit
0119 r22 = r20 * #8 ; new limit
0145 ; cmp r9, r20 killed ; r8 + j &lt; r8 + n = r20
0147 cmp r10, r22 ; r10 = 8*(r8 + j) &lt; 8*(r8 + n) = r22
0255 ; r9 = r9 + #1 killed ; loop variable
바깥쪽 루프.
전체 그림으로 돌아가서:
이제 r1을 증가시키는 외부 루프 내에 4개의 곱셈이 있다. 0190번 줄의 r8 = r1*r2는 루프 진입 전(0055번 줄)에 설정하고 루프 하단(0385번 줄)에서 r2만큼 증가시켜 강도 감소할 수 있다.
값 r8*8(0118번 줄)은 초기화(0056번 줄)하고 r8이 증가할 때 8*r2를 더하여(0386번 줄) 강도 감소할 수 있다.
레지스터 r20은 루프를 통과할 때마다 0117번 줄에서 불변/상수 r2에 의해 증가하고 있다. 증가된 후 8을 곱하여 0119번 줄에서 r22를 생성한다. 이 곱셈은 루프를 통과할 때마다 8*r2를 더함으로써 강도 감소할 수 있다.
0055 r8 = r1 * r2 ; set initial value for r8
0056 r40 = r8 * #8 ; initial value for r8 * 8
0057 r30 = r2 * #8 ; increment for r40
0058 r20 = r8 + r2 ; copied from 0117
0058 r22 = r20 * #8 ; initial value of r22
0190 ; r8 = r1 * r2 killed ; calculate subscript i * n
0117 ; r20 = r8 + r2 killed - dead code
0118 r10 = r40 ; strength reduced expression to r40
0119 ; r22 = r20 * #8 killed ; strength reduced
0385 r8 = r8 + r2 ; strength reduce r8 = r1 * r2
0386 r40 = r40 + r30 ; strength reduce expression r8 * 8
0388 r22 = r22 + r30 ; strength reduce r22 = r20 * 8
마지막 곱셈.
이제 두 루프는 외부 루프 내에 하나의 곱셈 연산(0330번 줄)만 남고 내부 루프에는 곱셈 연산이 없다.
0320번 줄에서 r14는 r8과 r1의 합이며, r8과 r1은 루프 내에서 증가하고 있다. 레지스터 r8은 r2(=n)만큼 증가하고 r1은 1만큼 증가한다. 결과적으로 r14는 루프를 통과할 때마다 n+1만큼 증가한다. 0330번 줄의 마지막 루프 곱셈은 루프를 통과할 때마다 (r2+1)*8을 더함으로써 강도 감소될 수 있다.
005A r14 = r8 + r1 ; copied from 0320
005B r15 = r14 * #8 ; initial value of r15 (0330)
005C r49 = r2 + #1
005D r50 = r49 * #8 ; strength reduced increment
0320 ; r14 = r8 + r1 killed ; dead code
0330 ; r15 = r14 * #8 killed ; strength reduced
0389 r15 = r15 + r50 ; strength reduce r15 = r14 * 8
아직 더 남았다. 상수 폴딩은 프롤로그에서 r1=0임을 인식하여 여러 명령어를 정리할 것이다. r8은 루프에서 사용되지 않으므로 사라질 수 있다.
게다가, r1은 루프를 제어하기 위해서만 사용되므로, r1은 r40과 같은 다른 유도 변수로 대체될 수 있다. i가 0 &lt;= i &lt; n으로 갔던 곳에서, 레지스터 r40은 0 &lt;= r40 &lt; 8 * n * n으로 간다.
0030 ; r1 = #0 ; i = 0, becomes dead code
0055 ; r8 = #0 killed ; r8 no longer used
0056 r40 = #0 ; initial value for r8 * 8
0058 ; r20 = r2 killed ; r8 = 0, becomes dead code
0058 r22 = r2 * #8 ; r20 = r2
005A ; r14 = #0 killed ; r8 = 0, becomes dead code
005B r15 = #0 ; r14 = 0
005D r60 = r2 * r30 ; new limit for r40
0060 ; cmp r1, r2 killed ; i &lt; n; induction variable replaced
0065 cmp r40, r60 ; i * 8 * n &lt; 8 * n * n
0380 ; r1 = r1 + #1 killed ; dead code (r40 controls loop)
0385 ; r8 = r8 + r2 killed ; dead code
다른 강도 감소 연산.
연산자 강도 감소는 수학적 항등식을 사용하여 느린 수학 연산을 더 빠른 연산으로 대체한다. 이점은 대상 CPU와 때로는 주변 코드(CPU 내의 다른 기능 단위의 가용성에 영향을 미칠 수 있음)에 따라 달라진다.
유도 변수 (고아).
유도 변수 또는 재귀적 강도 감소는 체계적으로 변하는 변수의 함수를 함수의 이전 값을 사용하여 더 간단한 계산으로 대체한다. 절차형 프로그래밍 언어에서는 루프 변수를 포함하는 표현식에 적용되며, 선언형 프로그래밍 언어에서는 재귀 함수의 인수에 적용된다. 예를 들어,
f x = ... (3 ** x) ... (f (x + 1)) ...
는 다음과 같이 된다.
f x = f' x 1
f' x z = ... z ... (f' (x + 1) (3 * z)) ...
여기서 수정된 재귀 함수 는 두 번째 매개변수 z = 3 ** x를 사용하여 비용이 많이 드는 계산 (3 ** x)을 더 저렴한 (3 * z)로 대체할 수 있게 한다.
컴파일러 이론에서 공통 부분식 제거(Common subexpression elimination, CSE)는 동일한 식의 인스턴스를 찾고(즉, 모두 동일한 값으로 평가됨), 계산된 값을 포함하는 단일 변수로 대체하는 것이 가치가 있는지 분석하는 컴파일러 최적화이다.
다음 코드에서:
d = b * c * e;
코드를 다음과 같이 변환하는 것이 가치가 있을 수 있다.
d = tmp * e;
codice_1를 저장하고 검색하는 비용이 codice_2를 추가로 계산하는 비용보다 적은 경우이다.
CSE를 수행할 가능성은 사용 가능한 식 분석(일종의 데이터 흐름 분석)을 기반으로 한다. 식 codice_3는 프로그램의 지점 p에서 다음 경우에 사용 가능하다.
옵티마이저가 수행하는 비용/편익 분석은 codice_1에 저장하는 비용이 곱셈 비용보다 적은지 계산한다. 실제로 어떤 값이 어떤 레지스터에 저장되어 있는지와 같은 다른 요인들도 중요하다.
컴파일러 개발자들은 두 가지 종류의 CSE를 구분한다.
두 가지 모두 프로그램의 어떤 지점에서 어떤 식이 사용 가능한지에 대한 데이터 흐름 분석에 의존한다.
CSE를 수행하는 이점은 매우 커서 일반적으로 사용되는 최적화이다.
위 예시와 같은 간단한 경우에 프로그래머는 코드를 작성하면서 중복 식을 수동으로 제거할 수 있다. CSE의 가장 큰 원천은 컴파일러가 생성하는 중간 코드 시퀀스인데, 예를 들어 배열 인덱싱 계산과 같이 개발자가 수동으로 개입할 수 없는 경우이다. 어떤 경우에는 언어 기능이 많은 중복 식을 생성할 수 있다. 예를 들어, C 매크로의 경우, 매크로 확장이 원래 소스 코드에서는 명확하지 않은 공통 부분식을 초래할 수 있다.
컴파일러는 값을 저장하기 위해 생성되는 임시 변수의 수를 신중하게 결정해야 한다. 과도한 수의 임시 값은 레지스터 압력을 생성하여 메모리로 레지스터 스필링을 초래할 수 있으며, 이는 필요할 때 단순히 산술 결과를 재계산하는 것보다 더 오래 걸릴 수 있다.
상수 폴딩(constant folding)과 상수 전파(constant propagation)는 많은 현대 컴파일러에서 사용되는 관련 컴파일러 최적화 기법이다. 희소 조건부 상수 전파로 알려진 상수 전파의 고급 형태는 상수를 더 정확하게 전파하고 동시에 불필요한 코드를 제거할 수 있다.
상수 폴딩.
상수 폴딩은 런타임에 계산하는 대신 컴파일 타임에 상수 표현식을 인식하고 평가하는 과정이다. 상수 표현식의 항은 일반적으로 정수 리터럴 codice_1와 같은 단순 리터럴이지만, 컴파일 타임에 값이 알려진 변수일 수도 있다. 다음 문장을 살펴보자.
대부분의 컴파일러는 이 문장에 대해 실제로 두 개의 곱셈 명령과 하나의 저장 명령을 생성하지 않는다. 대신 이러한 구문을 식별하고 컴파일 타임에 계산된 값(이 경우 codice_2)으로 대체한다.
상수 폴딩은 산술 항등식을 활용할 수 있다. codice_3가 숫자이면 컴파일러가 codice_3의 값을 모르더라도 codice_5의 값은 0이다. (이것은 codice_3가 무한대나 NaN일 수 있으므로 IEEE 부동소수점에서는 유효하지 않다는 점에 유의한다.)
상수 폴딩은 숫자 외에도 적용될 수 있다. 문자열 리터럴과 상수 문자열의 연결은 상수 폴딩될 수 있다. codice_7와 같은 코드는 codice_8로 대체될 수 있다.
상수 폴딩과 크로스 컴파일.
크로스 컴파일러를 구현할 때 호스트 아키텍처의 산술 연산 동작이 대상 아키텍처의 동작과 일치하는지 확인해야 한다. 그렇지 않으면 상수 폴딩을 활성화하면 프로그램의 동작이 변경된다. 이는 부동소수점 연산의 경우 특히 중요하며, 정밀한 구현이 크게 다를 수 있다.
상수 전파.
상수 전파는 컴파일 타임에 표현식에서 알려진 상수의 값을 대체하는 과정이다. 이러한 상수에는 위에 정의된 상수뿐만 아니라 상수 값에 적용된 내장 함수도 포함된다. 다음 의사 코드를 살펴보자.
x를 전파하면 다음과 같다.
계속 전파하면 다음과 같은 결과가 나온다 (이는 x와 y 모두에 대한 불필요한 코드 제거를 통해 추가로 최적화될 가능성이 높다.)
상수 전파는 정의 도달 분석 결과를 사용하여 컴파일러에 구현된다. 변수의 모든 도달 정의가 동일한 할당(동일한 상수를 변수에 할당하는)인 경우 변수는 항상 동일한 값을 가지므로 상수로 대체될 수 있다.
상수 전파는 또한 조건 표현식이 컴파일 타임에 참 또는 거짓으로 평가되어 유일한 가능한 결과를 결정할 수 있는 경우 조건부 분기를 하나 이상의 무조건 명령문으로 단순화할 수 있다.
최적화의 작동 방식.
상수 폴딩과 전파는 많은 단순화 및 감소를 달성하기 위해 일반적으로 함께 사용되며, 이러한 효과가 멈출 때까지 번갈아 가며 반복적으로 적용된다.
분석을 기다리는 알 수 없는 숫자를 반환하는 최적화되지 않은 다음 의사 코드를 살펴보자.
int b = 9 - (a / 5);
int c = b * 4;
if (c &gt; 10) {
상수 전파를 한 번 적용한 다음 상수 폴딩을 적용하면 다음과 같다.
두 단계를 두 번 반복하면 다음과 같다.
int c = 12;
변수 codice_9와 codice_10의 모든 사용을 상수로 대체했으므로 컴파일러의 불필요한 코드 제거가 해당 변수에 적용되어 다음과 같이 남는다.
전통적인 상수 전파는 더 이상의 최적화를 생성하지 않는다. 프로그램을 재구성하지 않는다.
그러나 유사한 최적화인 희소 조건부 상수 전파는 적절한 조건부 분기를 선택하고 항상 참인 조건부 테스트를 제거하여 더 나아간다. 따라서 변수 codice_11는 불필요해지고 상수 연산만 남는다.
만약 이 의사 코드가 함수 본문을 구성한다면, 컴파일러는 이 함수가 정수 상수 codice_12로 평가된다는 것을 알게 되어 함수 호출을 codice_12로 대체하고 프로그램 효율성을 더욱 높일 수 있다.
컴파일러 설계에서 정적 단일 대입 형식(Static single-assignment form, SSA 형식 또는 단순히 SSA로 약칭)은 각 변수가 정확히 한 번 할당되는 중간 표현 (IR)의 한 유형이다. SSA는 LLVM, GNU 컴파일러 모음 및 많은 상업용 컴파일러를 포함하여 명령형 언어에 대한 대부분의 고품질 최적화 컴파일러에서 사용된다.
프로그램을 SSA 형식으로 변환하기 위한 효율적인 알고리즘이 있다. SSA로 변환하기 위해 원래 IR의 기존 변수들은 버전으로 분할되며, 일반적으로 원래 이름에 아래첨자가 붙어 각 정의가 고유한 버전을 갖도록 한다. 두 제어 흐름 경로의 조인 지점에 변수의 새 버전에 할당하는 추가 문도 도입해야 할 수 있다. SSA 형식에서 기계 코드로 변환하는 것도 효율적이다.
SSA는 변수의 사용을 볼 때 변수가 값을 받을 수 있는 곳이 한 곳뿐이므로 사용-정의 체인 결정과 같이 최적화에 필요한 수많은 분석을 쉽게 수행할 수 있도록 한다. 대부분의 최적화는 SSA 형식을 유지하도록 조정될 수 있으므로 추가 분석 없이 한 최적화를 다른 최적화 후에 수행할 수 있다. SSA 기반 최적화는 일반적으로 비SSA 형식의 이전 최적화보다 효율적이고 강력하다.
스킴 및 ML과 같은 함수형 언어 컴파일러에서는 일반적으로 연속 전달 방식(CPS)이 사용된다. SSA는 비지역 제어 흐름을 제외한 CPS의 잘 정돈된 부분 집합과 형식적으로 동일하므로, 한 방식으로 공식화된 최적화 및 변환은 일반적으로 다른 방식에도 적용된다. CPS를 중간 표현으로 사용하는 것은 고차 함수 및 프로시저 간 분석에 더 자연스럽다. 또한 CPS는 call/cc를 쉽게 인코딩할 수 있는 반면, SSA는 그렇지 않다.
SSA는 1980년대에 IBM의 여러 연구원들에 의해 개발되었다. 팀의 핵심 멤버인 케네스 제이덱(Kenneth Zadeck)은 개발이 계속됨에 따라 브라운 대학교로 자리를 옮겼다. 1986년 논문에서는 변수가 단일 정적 할당을 갖도록 birthpoints, identity assignment, 그리고 변수 이름 변경을 소개했다. 잔 페란테와 로널드 사이트론(Ronald Cytron)의 1987년 후속 논문에서는 이전 논문에서 수행된 이름 변경이 스칼라에 대한 모든 잘못된 의존성을 제거한다는 것을 증명했다. 1988년에 배리 로젠(Barry Rosen), 마크 N. 웨그먼, 케네스 제이덱은 identity assignment를 Φ-함수로 대체하고 "정적 단일 할당 형식"이라는 이름을 도입했으며, 현재 널리 사용되는 SSA 최적화를 시연했다. Φ-함수라는 이름은 로젠이 "가짜 함수"(phony function)의 더 출판 가능한 버전으로 선택했다. 알페른(Alpern), 웨그먼, 제이덱은 또 다른 최적화를 제시했지만, "정적 단일 할당"이라는 이름을 사용했다. 마지막으로 1989년에 로젠, 웨그먼, 제이덱, 사이트론, 페란테는 프로그램을 SSA 형식으로 변환하는 효율적인 방법을 찾아냈다.
SSA의 주요 유용성은 변수의 속성을 단순화하여 다양한 컴파일러 최적화의 결과를 동시에 단순화하고 개선하는 방식에 있다. 예를 들어, 다음 코드를 고려해보자:
사람은 첫 번째 할당이 불필요하며, 세 번째 줄에서 사용되는 codice_1의 값은 codice_1의 두 번째 할당에서 비롯된다는 것을 알 수 있다. 프로그램은 이를 결정하기 위해 도달 정의 분석을 수행해야 한다. 하지만 프로그램이 SSA 형식이라면 이 두 가지는 즉각적으로 알 수 있다:
SSA 사용으로 가능해지거나 크게 향상된 컴파일러 최적화 알고리즘은 다음과 같다:
SSA로 변환.
일반 코드를 SSA 형식으로 변환하는 것은 주로 각 할당의 대상(target)을 새 변수로 교체하고, 변수의 각 사용을 해당 지점에 도달하는 변수의 "버전"으로 교체하는 문제이다. 예를 들어, 다음 제어 흐름 그래프를 고려해 보자:
"x formula_1 x - 3"의 왼쪽에 있는 이름을 변경하고 x의 다음 사용을 그 새 이름으로 변경해도 프로그램은 변경되지 않는다. 이것은 SSA에서 두 개의 새로운 변수 x1과 x2를 생성하여 활용될 수 있는데, 각각 한 번만 할당된다. 마찬가지로, 다른 모든 변수에 식별하는 아래첨자를 부여하면 다음과 같다:
각 사용이 어떤 정의를 참조하는지 명확하지만, 한 가지 경우를 제외하고는 명확하다. 즉, 아래 블록의 y의 두 사용은 제어 흐름이 어떤 경로를 택했는지에 따라 y1 또는 y2를 참조할 수 있다.
이 문제를 해결하기 위해 마지막 블록에 Φ(Phi) 함수라는 특수 문을 삽입한다. 이 문은 과거의 제어 흐름에 따라 y1 또는 y2를 "선택"하여 y3이라는 y의 새로운 정의를 생성한다.
이제 마지막 블록은 간단히 y3을 사용하고, 어떤 방식으로든 올바른 값이 얻어질 것이다. x에 대한 Φ 함수는 필요하지 않다. x의 한 가지 버전, 즉 x2만 이 위치에 도달하고 있으므로 문제가 없다(다시 말해, Φ(x2,x2)=x2).
임의의 제어 흐름 그래프가 주어졌을 때, Φ 함수를 어디에 어떤 변수에 삽입해야 할지 파악하기 어려울 수 있다. 이 일반적인 질문에는 지배 프론티어(dominance frontiers)라는 개념을 사용하여 효율적으로 계산할 수 있는 해결책이 있다(아래 참조).
Φ 함수는 대부분의 기계에서 기계 연산으로 구현되지 않는다. 컴파일러는 각 선행 블록의 끝에 "이동(move)" 연산을 삽입하여 Φ 함수를 구현할 수 있다. 위 예시에서 컴파일러는 중간 왼쪽 블록의 끝에 y1에서 y3으로의 이동을, 중간 오른쪽 블록의 끝에 y2에서 y3으로의 이동을 삽입할 수 있다. 이러한 이동 연산은 컴파일러의 레지스터 할당 절차에 따라 최종 코드에 포함되지 않을 수도 있다. 그러나, 와이드 이슈 머신에서 발생할 수 있는 것처럼 동시 작업이 투기적으로 Φ 함수의 입력을 생성하는 경우에는 이 접근 방식이 작동하지 않을 수 있다. 일반적으로 와이드 이슈 머신은 컴파일러가 Φ 함수를 구현하기 위해 이러한 상황에서 사용하는 선택 명령어를 가지고 있다.
지배 프론티어를 이용한 최소 SSA 계산.
제어 흐름 그래프에서, 노드 A가 다른 노드 B를 고 하는 것은 A를 거치지 않고는 B에 도달하는 것이 불가능하다는 것을 의미한다. 다시 말해, 노드 B에 도달하면 A가 실행되었다고 가정할 수 있다. A가 B를 지배한다(또는 B가 A에 지배된다)고 하는 것은 A가 B를 엄격히 지배하거나 A=B인 경우를 말한다.
노드 A에게 제어를 전달하는 노드는 A의 라고 불린다.
노드 A의 는 A가 B를 , B의 직접 선행자 중 일부를 지배하는 노드 B의 집합이다. 이들은 여러 제어 경로가 다시 하나의 경로로 합쳐지는 지점이다.
예를 들어, 다음 코드에서:
노드 1은 노드 2, 3, 4를 엄격히 지배하며 노드 4의 직접 선행자는 노드 2와 3이다.
지배 프론티어는 Φ 함수가 필요한 지점을 정의한다. 위 예시에서, 제어가 노드 4로 전달될 때, 사용되는 codice_5의 정의는 제어가 노드 2 또는 3에서 전달되었는지에 따라 달라진다. Φ 함수는 지배자에서 정의된 변수에는 필요하지 않다. 적용될 수 있는 유일한 정의만 있기 때문이다.
각 노드의 지배 프론티어를 찾는 효율적인 알고리즘이 있다. 이 알고리즘은 1991년 론 사이트론(Ron Cytron), 잔 페란테(Jeanne Ferrante) 등이 쓴 "Efficiently Computing Static Single Assignment Form and the Control Graph"에서 처음으로 설명되었다.