값 번호부여

값 번호부여는 프로그램 내의 두 계산이 동일한지를 판단하고 의미론을 보존하는 최적화를 통해 그 중 하나를 제거하는 기술입니다.

글로벌 값 번호부여부

Global Value Numbering(GVN; 글로벌 값 번호부여)은 Static Single Assignment Form(SSA; 단일 할당 형식) 중간 표현을 기반으로 한 컴파일러 최적화입니다.CSE(Common Sub Expression Elimation)에서는 불가능한 중복 코드를 제거하는 데 도움이 될 수 있습니다.단, 동시에 CSE는 GVN에 없는 코드를 제거할 수 있기 때문에 둘 다 최신 컴파일러에서 자주 볼 수 있습니다.글로벌 값 번호는 값 번호 매핑이 기본 블록 경계에서도 유지되고 매핑 계산에 서로 다른 알고리즘이 사용된다는 점에서 로컬 값 번호 매기기와는 다릅니다.

글로벌 값 번호는 변수 및 식에 값 번호를 할당함으로써 작동합니다.이러한 변수 및 식에는 동일한 값 번호가 할당되어 있습니다.예를 들어, 다음과 같은 코드입니다.

w : = 3 x : = 3 y : = x + 4 z : = w + 4

GVN 루틴이 적절할 경우 동일한 값 번호가 할당됩니다.w그리고.x, 및 같은 값 번호입니다.y그리고.z예를 들어 맵${\displaystyle }${ ${\displaystyle w1}$1, ${\displaystyle x1}$1, y${\displaystyle 2}$2, ${\displaystyle z2}$ 2$}$ { $display$style \$left$ \ { $w$} \ $mapsto$1, { $x$} \ $mapsto$ 1, { $y$} \ $mapsto$ 2, { $z$} \ $mapsto$2 \ $right$\ }는$$ 이 블록에 최적인 값 매핑을 구성합니다.이 정보를 사용하여 이전 코드 fragment를 안전하게 다음과 같이 변환할 수 있습니다.

w : = 3 x : = w : = w + 4 z : = y

이 fragment 뒤의 코드에 따라서는, 카피 전파에 의해서, 다음의 할당이 삭제될 가능성이 있습니다.x및 에 대해서z.

GVN이 CSE보다 강력할 수 있는 이유는 CSE가 어휘적으로 동일한 표현과 일치하는 반면 GVN은 기본적인 동등성을 판별하려고 하기 때문입니다.예를 들어, 코드에서:

a := c × d e := c f := e × d

카피의 전파가 없으면, CSE는, 다음에 할당된 재계산을 배제하지 않습니다.f단, 부실한 GVN 알고리즘이라도 이 용장성을 검출하여 배제할 수 있습니다.

SSA 폼은 ${\displaystyle \text{잘못된}}{\displaystyle }${${\displaystyle \text{변수명}}$값 $}{$ name$}}\map$to {$text{value$ number$}}\right\}$ 매핑이$$ 생성되지 않도록 GVN을 실행하기 위해 필요합니다.

로컬 값 번호부여부

Local Value Numbering(LVN; 로컬 값 번호부여)은 컴파일러 최적화로, 동등한 표현의 여러 인스턴스(즉, 같은 결과를 내는 식)를 찾아 첫 번째 오카렌스로 대체하는 것을 목적으로 합니다.LVN은 로컬 최적화입니다.즉, 글로벌 값 번호 부여와는 달리 한 번에 하나의 기본 블록으로 동작합니다.

로컬 값 번호부여는 각 조작에 하나의 번호를 할당하고 이러한 관련성을 기억함으로써 기능합니다.그런 다음 후속 명령이 조회되고 동일한 명령이 이미 등록된 경우 이전 명령의 결과로 대체됩니다.예를 들어 다음과 같습니다.

a ← 4 a는 #1 b로 태그 지정 ← 5 b는 #2 c로 태그 지정 ← a + b c(#1 + #2)로 태그 지정 ← 5 d는 #2로 태그 지정되며, b e ← a + de와 같으며, '#1 + #2'는 #3으로 태그 지정됩니다.

명령어에 숫자를 할당함으로써 중복되는 부분을 단순 정수 비교로 변환합니다.이 예에서는,c그리고.e같은 번호(#3)가 할당되기 때문에 컴파일러에 대한 모든 참조가e간단히 하기 위한 것으로 대체될 수 있다c.

어려움과 확장

SSA를 사용하지 않을 때의 문제

단순한 구현에서는 숫자 대신 변수 이름을 직접 사용하여 최적화를 시도할 수 있습니다.그러나 변수 값이 변경될 수 있는 경우에는 이 방법이 작동하지 않습니다.의사 코드에 대해 생각해 봅시다.

a ← 1 a는 #1 b로 태그 지정 ← 2 b는 #2 c로 태그 지정 ← a + b c는 #3 b ← 3 d ← a + b d가 #3으로 잘못 태그 지정됨

이 시나리오에서는d인수가 다음 인수와 일치하기 때문에 번호3이 잘못 할당되어 있습니다.c그러나 이는 올바르지 않습니다.b값이 2에서 3으로 변경되어 실제 결과가 다릅니다.SSA 표현을 사용하면 이 차이가 해결됩니다.

수학적 아이덴티티 사용

간단한 구현에서는 피연산자의 순서에 의해서만 다른 경우에도 모든 동등한 식을 포착할 수 없는 경우가 있습니다.다음 예제에서는a그리고.b같은 번호를 할당할 수 있습니다.

a ← 1 + 2 b ← 2 + 1

이 문제는, 양쪽의 케이스에 같은 번호를 할당하는 것으로 간단하게 해결할 수 있습니다(예:a + b그리고.b + a동일한 번호로 기록되거나 피연산자를 정렬한 후 ^[1]등가물을 확인합니다.

로컬 값 번호 지정 최적화 도구도 수학적 식별 정보를 인식할 수 있습니다.가정하다a는 정수입니다.다음 식에 모두 같은 ^[2]값을 할당할 수 있습니다.

b ← a + 0 c ← a * 1 d ← min(a, MAX_INT) e ← max(a, a) f ← a & 0xFF..FF('&'는 비트의 AND를 나타낸다고 가정)

「 」를 참조해 주세요.

• 부분 용장성 배제
• 컴파일러 최적화
• 공통 하위 표현식 제거

레퍼런스

추가 정보

• Kildall, Gary Arlen (1973). "A Unified Approach to Global Program Optimization". Proceedings of the 1st Annual ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages. Popl '73: 194–206. doi:10.1145/512927.512945. hdl:10945/42162. ISBN 9781450373494. S2CID 10219496. Retrieved 2006-11-20. [1]
• 앨퍼른, 보웬, 웨그먼, 마크 N, 자덱, F. 케네스."프로그램 변수 균등성 검출." 제15회 연례 프로그래밍 언어 원칙 ACM 심포지엄 회의 기록, ACM Press, 샌디에이고, CA, 미국, 1988년 1월, 1~11페이지.
• L. Taylor Simpson, "가치 주도형 중복 배제"기술보고서 96-308, 라이스대학교 컴퓨터공학부, 1996. (저자 박사논문)
• Muchnick, Steven Stanley (1997). Advanced Compiler Design and Implementation. Morgan Kaufmann Publishers. ISBN 978-1-55860-320-2.
• Briggs, P.; Cooper, Keith D.; Simpson, L. Taylor (1997). "Value Numbering". Software-Practice and Experience. 27 (6): 701–724.