hotchpotch/wikipedia-multilingual-ir-pairs huggingface dataset:
정적 단일 대입 형식
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의 주요 유용성은 변수의 속성을 단순화하여 다양한 컴파일러 최적화의 결과를 동시에 단순화하고 개선하는 방식에 있다. 예를 들어, 다음 코드를 고려해보자:
사람은 첫 번째 할당이 불필요하며, 세 번째 줄에서 사용되는 y의 값은 y의 두 번째 할당에서 비롯된다는 것을 알 수 있다. 프로그램은 이를 결정하기 위해 도달 정의 분석을 수행해야 한다. 하지만 프로그램이 SSA 형식이라면 이 두 가지는 즉각적으로 알 수 있다:
SSA 사용으로 가능해지거나 크게 향상된 컴파일러 최적화 알고리즘은 다음과 같다:
정적 단일 대입 형식 SSA로 변환
일반 코드를 SSA 형식으로 변환하는 것은 주로 각 할당의 대상(target)을 새 변수로 교체하고, 변수의 각 사용을 해당 지점에 도달하는 변수의 "버전"으로 교체하는 문제이다. 예를 들어, 다음 제어 흐름 그래프를 고려해 보자:
"x  x - 3"의 왼쪽에 있는 이름을 변경하고 x의 다음 사용을 그 새 이름으로 변경해도 프로그램은 변경되지 않는다. 이것은 SSA에서 두 개의 새로운 변수 x1과 x2를 생성하여 활용될 수 있는데, 각각 한 번만 할당된다. 마찬가지로, 다른 모든 변수에 식별하는 아래첨자를 부여하면 다음과 같다:
각 사용이 어떤 정의를 참조하는지 명확하지만, 한 가지 경우를 제외하고는 명확하다. 즉, 아래 블록의 y의 두 사용은 제어 흐름이 어떤 경로를 택했는지에 따라 y1 또는 y2를 참조할 수 있다.
이 문제를 해결하기 위해 마지막 블록에 Φ(Phi) 함수라는 특수 문을 삽입한다. 이 문은 과거의 제어 흐름에 따라 y1 또는 y2를 "선택"하여 y3이라는 y의 새로운 정의를 생성한다.
정적 단일 대입 형식 SSA로 변환
이제 마지막 블록은 간단히 y3을 사용하고, 어떤 방식으로든 올바른 값이 얻어질 것이다. x에 대한 Φ 함수는 필요하지 않다. x의 한 가지 버전, 즉 x2만 이 위치에 도달하고 있으므로 문제가 없다(다시 말해, Φ(x2,x2)=x2).
임의의 제어 흐름 그래프가 주어졌을 때, Φ 함수를 어디에 어떤 변수에 삽입해야 할지 파악하기 어려울 수 있다. 이 일반적인 질문에는 지배 프론티어(dominance frontiers)라는 개념을 사용하여 효율적으로 계산할 수 있는 해결책이 있다(아래 참조).
정적 단일 대입 형식 SSA로 변환
Φ 함수는 대부분의 기계에서 기계 연산으로 구현되지 않는다. 컴파일러는 각 선행 블록의 끝에 "이동(move)" 연산을 삽입하여 Φ 함수를 구현할 수 있다. 위 예시에서 컴파일러는 중간 왼쪽 블록의 끝에 y1에서 y3으로의 이동을, 중간 오른쪽 블록의 끝에 y2에서 y3으로의 이동을 삽입할 수 있다. 이러한 이동 연산은 컴파일러의 레지스터 할당 절차에 따라 최종 코드에 포함되지 않을 수도 있다. 그러나, 와이드 이슈 머신에서 발생할 수 있는 것처럼 동시 작업이 투기적으로 Φ 함수의 입력을 생성하는 경우에는 이 접근 방식이 작동하지 않을 수 있다. 일반적으로 와이드 이슈 머신은 컴파일러가 Φ 함수를 구현하기 위해 이러한 상황에서 사용하는 선택 명령어를 가지고 있다.
제어 흐름 그래프에서, 노드 A가 다른 노드 B를 엄격히 지배한다고 하는 것은 A를 거치지 않고는 B에 도달하는 것이 불가능하다는 것을 의미한다. 다시 말해, 노드 B에 도달하면 A가 실행되었다고 가정할 수 있다. A가 B를 지배한다(또는 B가 A에 지배된다)고 하는 것은 A가 B를 엄격히 지배하거나 A=B인 경우를 말한다.
노드 A에게 제어를 전달하는 노드는 A의 직접 선행자라고 불린다.
정적 단일 대입 형식 SSA로 변환
노드 A의 지배 프론티어는 A가 B를 엄격히 지배하지 않지만, B의 직접 선행자 중 일부를 지배하는 노드 B의 집합이다. 이들은 여러 제어 경로가 다시 하나의 경로로 합쳐지는 지점이다.
예를 들어, 다음 코드에서:
노드 1은 노드 2, 3, 4를 엄격히 지배하며 노드 4의 직접 선행자는 노드 2와 3이다.
지배 프론티어는 Φ 함수가 필요한 지점을 정의한다. 위 예시에서, 제어가 노드 4로 전달될 때, 사용되는 result의 정의는 제어가 노드 2 또는 3에서 전달되었는지에 따라 달라진다. Φ 함수는 지배자에서 정의된 변수에는 필요하지 않다. 적용될 수 있는 유일한 정의만 있기 때문이다.
각 노드의 지배 프론티어를 찾는 효율적인 알고리즘이 있다. 이 알고리즘은 1991년 론 사이트론(Ron Cytron), 잔 페란테(Jeanne Ferrante) 등이 쓴 "Efficiently Computing Static Single Assignment Form and the Control Graph"에서 처음으로 설명되었다.
라이스 대학교의 키스 D. 쿠퍼(Keith D. Cooper), 티모시 J. 하비(Timothy J. Harvey), 켄 케네디(Ken Kennedy)는 그들의 논문 "A Simple, Fast Dominance Algorithm"에서 한 알고리즘을 설명한다.
위 코드에서 idom(b)는 b의 직접 지배자(immediate dominator)로, b를 엄격히 지배하지만 b를 엄격히 지배하는 다른 어떤 노드도 엄격히 지배하지 않는 유일한 노드이다.
정적 단일 대입 형식 Φ 함수의 수를 줄이는 변형
"최소" SSA는 각 이름이 정확히 한 번 값을 할당받고, 원래 프로그램에서 이름의 각 참조(사용)가 여전히 고유한 이름을 참조할 수 있도록 하는 데 필요한 최소한의 Φ 함수를 삽입한다. (후자의 요구 사항은 컴파일러가 각 연산에서 각 피연산자에 대한 이름을 기록할 수 있도록 하는 데 필요하다.)
그러나 이러한 Φ 함수 중 일부는 죽은 코드일 수 있다. 이러한 이유로 최소 SSA가 특정 절차에 필요한 가장 적은 수의 Φ 함수를 생성하는 것은 아니다. 일부 유형의 분석에서는 이러한 Φ 함수가 불필요하며 분석을 덜 효율적으로 실행시킬 수 있다.
가지치기된 SSA 형식은 간단한 관찰에 기반한다. Φ 함수는 Φ 함수 후에 "활성화"(live)된 변수에만 필요하다. (여기서 "활성화"는 값이 문제의 Φ 함수에서 시작하는 특정 경로를 따라 사용된다는 의미이다.) 변수가 활성화되어 있지 않으면 Φ 함수의 결과는 사용될 수 없으며 Φ 함수에 의한 할당은 죽은 코드이다.
정적 단일 대입 형식 Φ 함수의 수를 줄이는 변형
가지치기된 SSA 형식을 구성할 때는 Φ 함수 삽입 단계에서 활성 변수 정보를 사용하여 주어진 Φ 함수가 필요한지 여부를 결정한다. 원래 변수 이름이 Φ 함수 삽입 지점에서 활성화되어 있지 않으면 Φ 함수는 삽입되지 않는다.
가지치기를 데드 코드 제거 문제로 취급하는 또 다른 가능성도 있다. 이 경우 Φ 함수는 입력 프로그램의 모든 사용이 해당 함수로 다시 작성되거나, 다른 Φ 함수의 인수로 사용될 경우에만 활성화된다. SSA 형식으로 들어갈 때 각 사용은 해당 사용을 지배하는 가장 가까운 정의로 다시 작성된다. 그런 다음 Φ 함수는 적어도 하나의 사용을 지배하는 가장 가까운 정의이거나, 활성 Φ 함수의 적어도 하나의 인수일 경우 활성으로 간주된다.
부분적으로 가지치기된 SSA 형식은 활성 변수 정보를 계산하는 상대적으로 높은 비용을 들이지 않고 Φ 함수의 수를 줄이려는 시도이다. 이 형식은 다음과 같은 관찰을 기반으로 한다. 변수가 기본 블록에 진입할 때 활성화되지 않으면 Φ 함수가 필요하지 않다. SSA 구성 중에 "블록 로컬" 변수에 대한 Φ 함수는 생략된다.
정적 단일 대입 형식 Φ 함수의 수를 줄이는 변형
블록 로컬 변수 집합을 계산하는 것은 전체 활성 변수 분석보다 간단하고 빠른 절차이므로, 부분적으로 가지치기된 SSA 형식을 계산하는 것이 가지치기된 SSA 형식보다 효율적이다. 반면에 부분적으로 가지치기된 SSA 형식은 더 많은 Φ 함수를 포함하게 된다.
블록 인수는 Φ 함수의 대안이며 표현상 동일하지만 실제로는 최적화 과정에서 더 편리할 수 있다. 블록은 이름이 지정되고 함수 매개변수처럼 표기되는 블록 인수 목록을 취한다. 블록을 호출할 때 블록 인수는 지정된 값에 바인딩된다. MLton, 스위프트 SIL, LLVM MLIR은 블록 인수를 사용한다.
정적 단일 대입 형식 SSA 형식에서 벗어나기
SSA 형식은 일반적으로 직접 실행에 사용되지 않으며(SSA를 해석하는 것이 가능하긴 하지만), 종종 직접적으로 대응하는 다른 IR "위에" 사용된다. 이는 기존 IR의 부분(기본 블록, 명령어, 피연산자 등)과 SSA 대응 부분 사이를 매핑하는 일련의 함수로 SSA를 "구성"함으로써 달성할 수 있다. SSA 형식이 더 이상 필요 없을 때, 이러한 매핑 함수는 버려져서 이제 최적화된 IR만 남게 된다.
SSA 형식에서 최적화를 수행하면 일반적으로 얽힌 SSA 웹이 발생하며, 이는 피연산자가 모두 동일한 루트 피연산자를 갖지 않는 Φ 명령어가 있음을 의미한다. 이러한 경우 컬러아웃(color-out) 알고리즘이 SSA에서 벗어나기 위해 사용된다. 순진한 알고리즘은 Φ에 다른 루트 심볼의 소스를 놓는 각 선행 경로를 따라 복사본을 도입한다. 복사본을 적게 사용하여 SSA에서 벗어나는 여러 알고리즘이 있으며, 대부분은 간섭 그래프 또는 그 근사치를 사용하여 복사본 병합을 수행한다.
정적 단일 대입 형식 확장
SSA 형식에 대한 확장은 두 가지 범주로 나눌 수 있다.
이름 변경 방식 확장은 이름 변경 기준을 변경한다. SSA 형식은 값이 할당될 때마다 각 변수의 이름을 변경한다. 대안적인 방식으로는 정적 단일 사용 형식(각 변수가 사용될 때마다 각 문에서 이름을 변경함)과 정적 단일 정보 형식(각 변수가 값이 할당될 때마다, 그리고 후지배 프론티어에서 이름을 변경함)이 있다.
기능별 확장은 변수의 단일 할당 속성을 유지하면서 추가 기능을 모델링하기 위한 새로운 의미론을 통합한다. 일부 기능별 확장은 배열, 객체 및 별칭 포인터와 같은 고수준 프로그래밍 언어 기능을 모델링한다. 다른 기능별 확장은 투기와 예측과 같은 저수준 아키텍처 기능을 모델링한다.
정적 단일 대입 형식 SSA 형식을 사용하는 컴파일러
GNU 컴파일러 모음 (GCC)은 버전 4 (2005년 4월 출시)부터 SSA를 광범위하게 사용한다. 프론트엔드는 "GENERIC" 코드를 생성하며, 이는 "gimplifier"에 의해 "GIMPLE" 코드로 변환된다. 그런 다음 "GIMPLE"의 SSA 형식에 고수준 최적화가 적용된다. 결과적으로 최적화된 중간 코드는 RTL로 번역되며, 여기서 저수준 최적화가 적용된다. 아키텍처별 백엔드는 마지막으로 RTL을 어셈블리어로 변환한다.
IBM의 오픈 소스 적응형 자바 가상 머신, Jikes RVM은 SSA의 확장인 Extended Array SSA를 사용한다. 이는 스칼라, 배열, 객체 필드를 통합된 프레임워크에서 분석할 수 있게 해준다. Extended Array SSA 분석은 최대 최적화 수준에서만 활성화되며, 이는 가장 자주 실행되는 코드 부분에 적용된다.
정적 단일 대입 형식 SSA 형식을 사용하는 컴파일러
jackcc는 학술 명령어 집합 Jackal 3.0용 오픈 소스 컴파일러이다. 이 컴파일러는 중간 표현을 위해 SSA와 함께 간단한 3-피연산자 코드를 사용한다. 흥미로운 변형으로, Φ 함수를 소위 SAME 명령어로 대체하는데, 이는 레지스터 할당기에게 두 개의 활성 범위(live range)를 동일한 물리적 레지스터에 배치하도록 지시한다.
1994년경 일리노이 콘서트 컴파일러(Illinois Concert Compiler)는 SSU(Static Single Use)라는 SSA 변형을 사용했는데, 이는 각 변수에 값이 할당될 때마다 그리고 해당 변수가 사용되는 각 조건부 문맥에서 이름을 변경한다. 이는 본질적으로 위에서 언급된 정적 단일 정보 형식이다. SSU 형식은 존 플레비악(John Plevyak)의 박사 논문에 문서화되어 있다.
희소 조건부 상수 전파
컴퓨터 과학에서 희소 조건부 상수 전파(Sparse conditional constant propagation, SCCP)는 정적 단일 대입 형식(SSA)으로 변환된 후 컴파일러에 자주 적용되는 최적화 기법이다. 이는 컴파일 시점에 계산될 수 있는 정적 값의 계산인 상수 폴딩을 전파한다. 더욱이, 이는 어떤 순서로든 또는 어떤 횟수로든 데드 코드 제거와 상수 전파를 개별적으로 적용하는 것보다 더 많은 상수 값과 따라서 더 많은 개선 기회를 찾을 수 있다.
이 알고리즘은 SSA 형식 코드의 추상 해석을 수행하여 작동한다. 추상 해석 중에는 일반적으로 값에 대한 평탄한 격자와 SSA 변수를 이 격자의 값에 매핑하는 전역 환경을 사용한다. 알고리즘의 핵심은 분기 명령어의 해석을 처리하는 방식에 있다. 분기 명령어를 만나면, 분기 조건은 조건에 있는 변수에 바인딩된 추상 값의 정밀도를 고려하여 가능한 한 최적으로 평가된다. 값들이 완벽하게 정밀하여(최상도 최하도 아닌) 추상 실행이 어느 방향으로 분기할지 결정할 수 있는 경우가 있을 수 있다. 값들이 상수가 아니거나 조건의 변수가 정의되지 않은 경우, 보수성을 유지하기 위해 두 분기 방향 모두를 취해야 한다.
희소 조건부 상수 전파
추상 해석이 완료되면, 결코 도달하지 않은 명령어들은 데드 코드로 표시된다. 상수 값을 가진 것으로 발견된 SSA 변수들은 그 사용 지점에서 인라인될 수 있다(전파될 수 있다).
개인 보안
개인의 안보는 1948년 유엔이 채택한 세계 인권 선언에서 보장하는 기본적인 권리이다. 또한 유럽 인권 조약, 캐나다의 헌법, 남아프리카 공화국의 헌법 및 전 세계의 다른 법률에 의해 명시적으로 정의되고 보장되는 인권이기도 하다.
일반적으로 개인의 안보에 대한 권리는 자유와 관련이 있으며, 부당하게 투옥될 경우 인신보호청원과 같은 구제책을 받을 권리를 포함한다. 개인의 안보는 고문과 잔인하고 비정상적인 형벌 금지에 기반한 권리의 확장으로 볼 수도 있다. 개인의 안보에 대한 권리는 덜 치명적인 행위를 막을 수 있으며, 수감자 권리와 관련하여 사용될 수 있다.
개인 보안 유엔
개인의 안보에 대한 권리는 세계 인권 선언 제3조에 의해 보장된다. 이 조항에서 개인의 안보는 생존권 및 자유와 결합되어 있다. 전문은 "모든 사람은 생명, 자유 및 개인의 안전에 대한 권리를 가진다."고 되어 있다.
유엔 조약인 시민적 및 정치적 권리에 관한 국제규약(1966)도 개인의 안보에 대한 권리를 인정한다. 제3조는 "모든 사람은 자유와 개인의 안전에 대한 권리를 가진다."고 명시하며, 이 조항은 "자의적인 체포 또는 구금"을 금지한다. 이 조항은 "누구든지 법률에 의해 정해진 근거와 절차에 따르지 아니하고는 그 자유를 박탈당하지 아니한다."고 계속된다.
개인 보안 유럽
개인의 안보에 대한 권리는 유럽 인권 조약 제5조 (1)항의 자유와 안보에 대한 권리("모든 사람은 자유와 개인의 안보에 대한 권리를 가진다. 다음의 경우 및 법률에 규정된 절차에 따르지 아니하고는 누구도 자유를 박탈당하지 아니한다") 및 유럽 연합 기본권 헌장 제6조("모든 사람은 자유와 개인의 안보에 대한 권리를 가진다")에 명시되어 있다.
개인 보안 캐나다
개인의 안보에 대한 권리는 1960년 캐나다의 캐나다 권리장전에서 인정되었다. 이 법의 제1조 (a)항은 "개인의 생명, 자유, 개인의 안전 및 재산 향유에 대한 권리, 그리고 적법절차에 따르지 아니하고는 이를 박탈당하지 않을 권리"를 인정했다. 그러나 권리장전은 법률이었고 헌법의 일부가 아니었다.
1982년, 개인의 안보에 대한 권리가 헌법에 추가되었다. 이는 캐나다 권리 및 자유 헌장의 제7조에 포함되었는데, "모든 사람은 생명, 자유 및 개인의 안전에 대한 권리와 기본적 정의의 원칙에 따르지 아니하고는 이를 박탈당하지 않을 권리를 가진다."고 규정하고 있다. 제7조의 개인의 안보는 신체와 건강의 사생활에 대한 권리와 개인의 "심리적 완전성"을 보호하는 권리로 구성된다. 즉, 이 권리는 개인의 정신 상태에 대한 정부에 의한 중대한 해( 스트레스 )로부터 보호한다. (블렌코 대 브리티시컬럼비아 인권위원회 사건, 2000년)
개인 보안 캐나다
이 권리는 상당한 판례를 만들어냈다. 캐나다의 낙태는 R. 대 모르겐탈러 (1988) 사건에서 대법원이 치료적 낙태 위원회가 여성의 건강을 위협하여 개인의 안보를 침해했다고 판결한 후 합법화되었다. 일부 판사들은 또한 신체에 대한 통제권이 개인의 안보 내에 있는 권리이며, 낙태법에 의해 침해되었다고 느꼈다. 작전 해체 대 국왕 (1985) 사건에서 순항 미사일 시험은 핵전쟁 위험을 야기하여 개인의 안보를 침해한다는 주장이 제기되었으나 실패했다. 쇼이 대 퀘벡주 (법무장관) (2005) 사건에서 일부 대법원 판사들은 퀘벡주의 민간 의료 금지가 의료 지연이 신체적 및 심리적 결과를 초래할 수 있기 때문에 개인의 안보를 침해한다고 간주하기도 했다.
캐나다 대법원과 학계에서는 개인의 안보가 일부 경제적 권리도 보장하는지에 대한 논의가 있어왔다. 이론적으로, 정부가 복지를 거부하거나, 직업에 필수적인 재산을 빼앗거나, 면허를 거부함으로써 개인의 소득 창출 능력을 제한한다면 개인의 안보는 침해될 것이다. 그러나 제7조는 주로 법적 권리와 관련되어 있으므로 경제적 권리에 대한 이러한 해석은 의문스럽다. 많은 경제적 문제 또한 통치행위일 수 있다.
개인 보안 남아프리카 공화국
1996년 남아프리카 공화국 정부는 제12조에서 개인의 안보에 대한 권리를 인정한 헌법적 권리장전을 채택했다. 여기서 개인의 안보는 "자유에 대한 권리"와 결합되었다. 제12조는 신체 통제 및 재생산 통제, 고문 및 잔인하고 비정상적인 형벌로부터의 자유, 재판을 받을 권리를 포함하여 개인의 안보와 자유에 대한 권리를 더 자세히 정의했다. 전문은 다음과 같다.
12. (1) 모든 사람은 자유와 개인의 안전에 대한 권리를 가지며, 이는 다음을 포함한다.
(a) 자의적으로 또는 정당한 이유 없이 자유를 박탈당하지 않을 권리;
(b) 재판 없이 구금되지 않을 권리;
(c) 공적 또는 사적 출처로부터의 모든 형태의 폭력으로부터 자유로울 권리;
(d) 어떤 식으로든 고문당하지 않을 권리; 그리고
(e) 잔인하고 비인간적이거나 굴욕적인 대우나 처벌을 받지 않을 권리.
(2) 모든 사람은 신체적, 심리적 완전성에 대한 권리를 가지며, 이는 다음을 포함한다.
(a) 재생산에 관한 결정을 내릴 권리;
(b) 자신의 신체에 대한 안전과 통제권을 가질 권리; 그리고
(c) 정보에 입각한 동의 없이 의료 또는 과학 실험을 받지 않을 권리.
개인 보안 튀르키예
튀르키예 헌법은 1982년에 제정되고 2001년에 개정된 제19조에서 자유에 대한 권리와 함께 개인의 안전을 보장한다. 이 조항은 정신 병원 및 중독자 시설, 범죄인 인도 등을 허용하는 법률에 따른 법원의 판결 형태로 이러한 권리의 제한을 명시한다. 이 조항은 또한 판사가 허용하는 경우, 충분한 시간이 없는 경우 또는 범죄를 저지른 것으로 보이는 경우에만 체포 및 구금을 제한한다. 그러면 체포된 사람은 체포 이유를 고지받게 되며, 근친자에게도 체포 사실이 통보된다. 마지막으로, 이 조항은 이러한 권리가 침해될 경우 정부의 보상을 허용한다.
개인 보안 뉴질랜드
1990년에 채택된 뉴질랜드 권리장전법은 제8조부터 제11조까지 "생명과 개인의 안전"을 보장한다. 제8조는 기본적 정의에 따라 박탈되는 경우를 제외하고는 생존권을 보장하며, 제9조는 잔인하고 비정상적인 처벌을 금지한다. 제10조는 개인의 의지에 반하여 의료 치료를 받지 않도록 금지한다. 마지막으로, 제11조는 뉴질랜드인에게 의료 치료를 받지 않을 권리를 부여한다.
개인 보안 영국
개인의 안전은 1998년 영국 인권법 제1부 제5조에 명시되어 있다. 이 버전은 이 법의 최신 형태이며, 이후 약간의 수정이 있었다. 이 새로운 법은 토니 블레어가 약속한 헌법 개혁의 한 측면을 나타낸다.
명령어 스케줄링
컴퓨터 과학에서 명령어 스케줄링(Instruction scheduling)은 명령어 수준 병렬성을 향상시키기 위해 사용되는 컴파일러 최적화 기법으로, 명령어 파이프라인을 사용하는 시스템의 성능을 향상시킨다. 간단히 말해서, 코드의 의미를 변경하지 않으면서 다음을 수행하려고 한다.
파이프라인 지연은 구조적 위험(프로세서 리소스 제한), 데이터 위험(한 명령어의 출력이 다른 명령어에 의해 필요함), 제어 위험(분기)으로 인해 발생할 수 있다.
명령어 스케줄링 데이터 위험
명령어 스케줄링은 일반적으로 단일 기본 블록에서 수행된다. 블록의 명령어를 특정 방식으로 재배열하는 것이 해당 블록의 동작을 보존하는지 확인하기 위해 데이터 종속성 개념이 필요하다. 세 가지 유형의 종속성이 있으며, 이는 세 가지 데이터 위험이기도 하다.
기술적으로 네 번째 유형인 읽기 후 읽기(RAR 또는 "Input")도 있다. 두 명령어 모두 동일한 위치를 읽는다. 입력 종속성은 두 명령문의 실행 순서를 제한하지 않지만, 배열 요소의 스칼라 교체에 유용하다.
세 가지 유형의 종속성을 존중하도록 하기 위해 종속성 그래프를 구성한다. 종속성 그래프는 각 정점이 명령어이고, I1이 종속성으로 인해 I2보다 먼저 와야 한다면 I1에서 I2로 가는 간선이 있는 유향 그래프이다. 루프 전달 종속성을 제외하면 종속성 그래프는 유향 비순환 그래프이다. 그러면 이 그래프의 모든 위상 정렬이 유효한 명령어 스케줄이 된다. 그래프의 간선은 일반적으로 종속성의 지연 시간으로 레이블이 지정된다. 이는 파이프라인이 지연 없이 대상 명령어를 진행하기 전에 경과해야 하는 클럭 사이클 수이다.
명령어 스케줄링 알고리즘
위상 정렬을 찾는 가장 간단한 알고리즘은 자주 사용되며 리스트 스케줄링으로 알려져 있다. 개념적으로, 이 알고리즘은 종속성 그래프의 소스를 반복적으로 선택하여 현재 명령어 스케줄에 추가하고 그래프에서 제거한다. 이로 인해 다른 정점이 소스가 될 수 있으며, 이들도 스케줄링을 위해 고려된다. 그래프가 비어 있으면 알고리즘이 종료된다.
좋은 스케줄을 만들기 위해서는 지연을 방지해야 한다. 이는 스케줄링될 다음 명령어의 선택에 따라 결정된다. 일반적으로 다음과 같은 휴리스틱이 사용된다.
명령어 스케줄링 위상 순서
명령어 스케줄링은 레지스터 할당 전 또는 후에, 또는 전후 모두 수행될 수 있다. 레지스터 할당 전에 수행하는 장점은 최대 병렬성을 얻을 수 있다는 것이다. 레지스터 할당 전에 수행하는 단점은 레지스터 할당자가 사용 가능한 레지스터 수를 초과하는 레지스터를 사용해야 할 수 있다는 것이다. 이로 인해 스필/필 코드가 도입되어 해당 코드 섹션의 성능이 저하된다.
스케줄링되는 아키텍처에 잠재적으로 불법적인 조합(명령어 연동 부족으로 인해)을 가진 명령어 시퀀스가 있는 경우, 명령어는 레지스터 할당 후에 스케줄링되어야 한다. 이 두 번째 스케줄링 패스는 스필/필 코드의 배치도 개선한다.
스케줄링이 레지스터 할당 후에만 수행되면, 레지스터 할당으로 인해 스케줄러가 가능한 명령어 이동량을 제한하는 잘못된 종속성이 도입될 것이다.
명령어 스케줄링 유형
명령어 스케줄링에는 여러 유형이 있다.
명령어 스케줄링 컴파일러 예시
GNU 컴파일러 모음은 -march(명령어 집합 및 스케줄링 모두) 또는 -mtune(스케줄링만) 플래그를 사용하여 명령어 스케줄링을 수행하는 것으로 알려진 컴파일러 중 하나이다. 각 마이크로아키텍처에 대한 명령어 지연 시간 및 어떤 명령어가 병렬로 실행될 수 있는지(또는 이에 상응하게 각 "포트"가 무엇을 사용하는지)에 대한 설명을 사용하여 작업을 수행한다. 이 기능은 GCC가 지원하는 거의 모든 아키텍처에서 사용할 수 있다.
버전 12.0.0까지 LLVM/Clang의 명령어 스케줄링은 명령어 집합 및 스케줄링 모두에 대해 -march(LLVM 용어로 target-cpu라고 함) 스위치만 허용했다. 버전 12부터 x86에 대해서만 -mtune(tune-cpu) 지원이 추가되었다.
지연 시간 및 포트 사용 정보 출처는 다음과 같다.
LLVM의 llvm-exegesis는 모든 시스템에서 특히 x86이 아닌 시스템에 대한 정보를 수집하는 데 사용할 수 있어야 한다.
명령어 스케줄링 추가 자료
Fisher, Joseph A. (1981). 《Trace Scheduling: A Technique for Global Microcode Compaction》. 《IEEE Transactions on Computers》 30. 478–490쪽. doi:10.1109/TC.1981.1675827. S2CID 1650655.  (트레이스 스케줄링)
Nicolau, Alexandru; Fisher, Joseph A. (1984). 《Measuring the Parallelism Available for Very Long Instruction Word Architectures》. 《IEEE Transactions on Computers》 33.  (Percolation scheduling)
명령어 스케줄링 추가 자료
Bernstein, David; Rodeh, Michael (June 1991). 《Global Instruction Scheduling for Superscalar Machines》 (PDF). 《Proceedings of the ACM, SIGPLAN '91 Conference on Programming Language Design and Implementation》.  (Global scheduling)
레지스터 할당
컴파일러 최적화에서 레지스터 할당(Register allocation)은 지역 자동 변수와 식의 결과를 제한된 수의 프로세서 레지스터에 할당하는 과정이다.
레지스터 할당은 기본 블록(지역 레지스터 할당) 전체, 함수/프로시저 전체(전역 레지스터 할당), 또는 호출 그래프를 통해 트래버스되는 함수 경계(프로시저 간 레지스터 할당)를 넘어 발생할 수 있다. 함수/프로시저별로 수행될 때, 호출 규약은 각 호출 사이트 주변에 저장/복원 삽입을 요구할 수 있다.
레지스터 할당 컨텍스트
많은 프로그래밍 언어에서 프로그래머는 원하는 만큼 변수를 사용할 수 있다. 컴퓨터는 CPU의 레지스터를 빠르게 읽고 쓸 수 있으므로, 더 많은 변수가 CPU 레지스터에 있을 때 컴퓨터 프로그램은 더 빠르게 실행된다. 또한, 레지스터에 접근하는 코드는 때로는 더 간결하여 코드가 더 작아지고, 메모리 대신 레지스터를 사용하면 더 빠르게 가져올 수 있다. 그러나 레지스터의 수는 제한적이다. 따라서 컴파일러가 코드를 기계어로 번역할 때, 제한된 수의 CPU 레지스터에 변수를 어떻게 할당할지 결정해야 한다.
레지스터 할당 컨텍스트
모든 변수가 동시에 사용 중(또는 "활성")인 것은 아니므로, 프로그램의 수명 동안 특정 레지스터는 다른 변수를 저장하는 데 사용될 수 있다. 그러나 동시에 사용 중인 두 변수는 변수 중 하나를 손상시키지 않고 동일한 레지스터에 할당될 수 없다. 모든 변수를 담을 레지스터가 충분하지 않으면 일부 변수는 RAM으로 이동되거나 RAM에서 가져올 수 있다. 이 과정을 레지스터 "스필링"(spilling)이라고 한다. 프로그램의 수명 동안 변수는 스필링될 수도 있고 레지스터에 저장될 수도 있다. 이 변수는 "분할"(split)된 것으로 간주된다. RAM에 접근하는 것은 레지스터에 접근하는 것보다 훨씬 느리므로 컴파일된 프로그램은 더 느리게 실행된다. 따라서 최적화 컴파일러는 가능한 한 많은 변수를 레지스터에 할당하는 것을 목표로 한다. 높은 "레지스터 압력"은 더 많은 스필링 및 재로드가 필요하다는 기술 용어이며, 브라운(Braun) 등이 "명령어에서 동시에 활성 상태인 변수의 수"로 정의했다.
레지스터 할당 컨텍스트
또한, 일부 컴퓨터 설계는 자주 접근하는 레지스터를 캐시한다. 따라서 가능한 한 `move` 명령어의 원본과 대상에 동일한 레지스터를 할당함으로써 프로그램을 더욱 최적화할 수 있다. 컴파일러가 정적 단일 대입 형식(SSA)과 같은 중간 표현을 사용하는 경우 특히 중요하다. 특히 SSA가 완전히 최적화되지 않은 경우 인위적으로 추가적인 `move` 명령어를 생성할 수 있다.
따라서 레지스터 할당은 런타임에 변수를 어디에 저장할지, 즉 레지스터 내부 또는 외부에 저장할지 선택하는 것으로 구성된다. 변수를 레지스터에 저장해야 하는 경우 할당자는 이 변수가 어떤 레지스터에 저장될지 결정해야 한다. 궁극적으로 또 다른 과제는 변수가 동일한 위치에 얼마나 오랫동안 머물러야 하는지 결정하는 것이다.
레지스터 할당자는 선택된 할당 전략에 관계없이 이러한 과제를 해결하기 위해 일련의 핵심 동작에 의존할 수 있다. 이러한 동작은 여러 범주로 분류할 수 있다.
이동 삽입
이 동작은 레지스터 간의 이동 명령어 수를 늘리는 것으로, 즉 하나의 레지스터 대신 변수가 수명 동안 다른 레지스터에서 활성화되도록 하는 것이다. 이는 분할 활성 범위 접근 방식에서 발생한다.
스필링
레지스터 할당 컨텍스트
이 동작은 변수를 레지스터 대신 메모리에 저장하는 것이다.
할당
이 동작은 변수에 레지스터를 할당하는 것이다.
통합과 집약
이 동작은 레지스터 간의 이동 횟수를 제한하여 총 명령어 수를 제한하는 것이다. 예를 들어, 여러 메서드에서 활성화되는 변수를 식별하고 해당 수명 동안 하나의 레지스터에 저장하는 방식이다.
많은 레지스터 할당 접근 방식은 하나 이상의 특정 동작 범주에 최적화되어 있다.
레지스터 할당은 다양한 레지스터 할당 접근 방식으로 해결(또는 피할 수 있는) 여러 문제를 제기한다. 가장 일반적인 세 가지 문제는 다음과 같다.
별칭(Aliasing)
일부 아키텍처에서는 한 레지스터에 값을 할당하면 다른 레지스터의 값에 영향을 줄 수 있다. 이를 별칭이라고 한다. 예를 들어, X86 아키텍처는 16비트 또는 8비트 레지스터로도 사용될 수 있는 4개의 범용 32비트 레지스터를 가지고 있다. 이 경우 eax 레지스터에 32비트 값을 할당하면 al 레지스터의 값에 영향을 준다.
사전 색칠(Pre-coloring)
이 문제는 일부 변수를 특정 레지스터에 강제로 할당하는 행위이다. 예를 들어, PowerPC 호출 규약에서 매개변수는 일반적으로 R3-R10으로 전달되며 반환 값은 R3으로 전달된다.
NP-문제
채틴(Chaitin) 등이 레지스터 할당이 NP-완전 문제임을 보였다. 그들은 임의의 그래프에 대해, (레지스터를 노드로, 기계 레지스터를 사용 가능한 색상으로 나타내는) 프로그램에 대한 레지스터 할당이 원래 그래프에 대한 색칠이 되도록 프로그램을 구성할 수 있음을 보여줌으로써 그래프 색칠 문제를 레지스터 할당 문제로 환원시킨다. 그래프 색칠이 NP-난해 문제이고 레지스터 할당이 NP에 속하므로, 이는 문제의 NP-완전성을 증명한다.
레지스터 할당 레지스터 할당 기술
레지스터 할당은 코드의 기본 블록에서 발생할 수 있다. 이를 "지역적"이라고 하며, 호르위츠(Horwitz) 등이 처음 언급했다. 기본 블록에는 분기가 없으므로 할당 과정은 빠르다고 생각된다. 레지스터 할당에서 제어 흐름 그래프 병합 지점의 관리가 시간 소모적인 작업으로 드러나기 때문이다. 그러나 이 접근 방식은 전체 컴파일 단위(예를 들어 메서드 또는 프로시저)에서 작동하는 "전역적" 접근 방식만큼 최적화된 코드를 생성하지 못한다고 생각된다.
그래프 색칠 할당은 레지스터 할당을 해결하는 지배적인 접근 방식이다. 이는 채틴(Chaitin) 등이 처음 제안했다.
이 접근 방식에서 그래프의 노드는 레지스터 할당 후보인 활성 범위(변수, 임시 변수, 가상/심볼릭 레지스터)를 나타낸다. 간선은 충돌하는 활성 범위, 즉 적어도 하나의 프로그램 지점에서 동시에 활성 상태인 활성 범위를 연결한다. 레지스터 할당은 간선으로 연결된 두 노드가 같은 색을 받지 않도록 노드에 색상(레지스터)을 할당하는 그래프 색칠 문제로 축소된다.
레지스터 할당 레지스터 할당 기술
활성도 분석을 사용하여 간섭 그래프를 구축할 수 있다. 노드가 프로그램 변수인 간격 그래프인 간섭 그래프는 어떤 변수가 동일한 레지스터에 할당될 수 없는지를 모델링하는 데 사용된다.
채틴 스타일의 그래프 색칠 기반 레지스터 할당자의 주요 단계는 다음과 같다.
그래프 색칠 할당은 세 가지 주요 단점이 있다. 첫째, 어떤 변수가 스필링될지 결정하기 위해 NP-완전 문제인 그래프 색칠에 의존한다. 일반 그래프에 대한 최소 색칠을 찾는 것은 실제로 NP-완전 문제이지만, 간격 그래프(간섭 그래프 포함)의 최소 색칠은 선형 시간에 수행될 수 있다(아래 선형 스캔 참조). 따라서 이 기술은 문제의 가정을 완전히 활용하지 못한다. 둘째, 활성 범위 분할이 사용되지 않는 한, 제거된 변수는 모든 곳에서 스필링된다. 저장 명령어는 변수 정의 직후 가능한 한 빨리 삽입되고, 로드 명령어는 변수 사용 직전에 삽입된다. 셋째, 스필링되지 않은 변수는 전체 수명 동안 동일한 레지스터에 유지된다.
레지스터 할당 레지스터 할당 기술
반면에, 단일 레지스터 이름이 여러 레지스터 클래스에 나타날 수 있는데, 여기서 클래스는 특정 역할에서 상호 교환 가능한 레지스터 이름들의 집합이다. 그러면 여러 레지스터 이름이 단일 하드웨어 레지스터의 별칭일 수 있다.
마지막으로, 그래프 색칠은 레지스터 할당에 강력한 기술이지만, 활성 범위 수에 대해 제곱에 해당하는 최악의 경우 크기를 가질 수 있는 간섭 그래프를 사용하기 때문에 계산 비용이 많이 든다.
그래프 색칠 레지스터 할당의 전통적인 공식화는 암시적으로 단일 뱅크의 겹치지 않는 범용 레지스터를 가정하며, 겹치는 레지스터 쌍, 특수 목적 레지스터 및 여러 레지스터 뱅크와 같은 불규칙한 아키텍처 기능을 처리하지 않는다.
레지스터 할당 레지스터 할당 기술
채틴 스타일 그래프 색칠 접근 방식의 한 가지 나중 개선점은 브릭스(Briggs) 등이 발견한 것이다. 이는 보존적 통합(conservative coalescing)이라고 불린다. 이 개선점은 두 활성 범위가 병합될 수 있는 시점을 결정하기 위한 기준을 추가한다. 주로, 비간섭 요구 사항 외에도 두 변수는 병합이 추가적인 스필링을 유발하지 않는 경우에만 통합될 수 있다. 브릭스 등은 채틴의 작업에 두 번째 개선점인 편향 색칠(biased coloring)을 도입한다. 편향 색칠은 복사 관련 활성 범위에 그래프 색칠에서 동일한 색상을 할당하려고 시도한다.
선형 스캔은 또 다른 전역 레지스터 할당 접근 방식이다. 이는 1999년 포레토(Poletto) 등이 처음 제안했다. 이 접근 방식에서는 코드가 그래프로 변환되지 않는다. 대신, 모든 변수를 선형적으로 스캔하여 간격으로 표현되는 활성 범위를 결정한다. 모든 변수의 활성 범위가 파악되면 간격을 시간 순서대로 순회한다. 이 순회가 활성 범위가 충돌하는 변수를 식별하는 데 도움이 될 수 있지만, 간섭 그래프는 구축되지 않으며 변수는 탐욕스러운 방식으로 할당된다.
레지스터 할당 레지스터 할당 기술
이 접근 방식의 동기는 속도이다. 생성된 코드의 실행 시간 측면이 아니라 코드 생성에 소요되는 시간 측면에서의 속도이다. 일반적으로 표준 그래프 색칠 접근 방식은 고품질 코드를 생성하지만, 상당한 오버헤드가 있으며, 사용된 그래프 색칠 알고리즘은 2차 비용을 가진다. 이러한 특징 덕분에 선형 스캔은 현재 핫스팟 클라이언트 컴파일러, V8, Jikes RVM, 그리고 안드로이드 런타임(ART)과 같은 여러 JIT 컴파일러에서 사용되는 접근 방식이다. 핫스팟 서버 컴파일러는 우수한 코드를 위해 그래프 색칠을 사용한다.
이것은 폴레토(Poletto) 등이 처음 제안한 알고리즘을 설명한다. 여기서:
그러나 선형 스캔은 두 가지 주요 단점을 보인다. 첫째, 탐욕적인 특성 때문에 수명 구멍(lifetime holes), 즉 "변수 값이 필요하지 않은 범위"를 고려하지 않는다. 게다가, 스필링된 변수는 전체 수명 동안 스필링된 상태로 남아 있다.
레지스터 할당 레지스터 할당 기술
많은 다른 연구들이 폴레토(Poletto)의 선형 스캔 알고리즘을 뒤따랐다. 예를 들어, 트라우브(Traub) 등이 더 나은 품질의 코드를 생성하기 위해 second-chance binpacking이라는 알고리즘을 제안했다. 이 접근 방식에서는 스필링된 변수들이 표준 선형 스캔 알고리즘에서 사용된 것과는 다른 휴리스틱을 사용하여 나중에 레지스터에 저장될 기회를 얻는다. 이 알고리즘은 활성 구간 대신 활성 범위에 의존하는데, 이는 범위가 스필링되어야 할 경우 이 변수에 해당하는 다른 모든 범위가 스필링될 필요는 없음을 의미한다.
레지스터 할당 레지스터 할당 기술
선형 스캔 할당은 SSA 형식의 이점을 활용하도록 조정되기도 했다. 이 중간 표현의 속성은 할당 알고리즘을 단순화하고 수명 구멍을 직접 계산할 수 있도록 한다. 우선, 활성 구간을 구축하기 위한 데이터 흐름 그래프 분석에 소요되는 시간이 줄어들었는데, 이는 변수가 고유하기 때문이다. 결과적으로 각 새로운 할당이 새로운 활성 구간에 해당하므로 더 짧은 활성 구간을 생성한다. 구간 및 활성 구멍을 모델링하는 것을 피하기 위해 로저스(Rogers)는 명령어의 80%에 대해 구간을 성공적으로 제거한 future-active sets라는 단순화를 보여주었다.
레지스터 할당의 맥락에서 통합과 집약은 변수-변수 이동 작업을 두 변수를 동일한 위치에 할당함으로써 병합하는 행위이다. 통합과 집약 작업은 간섭 그래프가 구축된 후에 발생한다. 두 노드가 통합되면 동일한 색상을 얻고 동일한 레지스터에 할당되어야 하며, 그 후에 복사 작업은 불필요해진다.
레지스터 할당 레지스터 할당 기술
통합과 집약은 간섭 그래프의 색칠 가능성에 긍정적 및 부정적 영향을 모두 미칠 수 있다. 예를 들어, 통합과 집약이 그래프 추론 색칠 가능성에 미칠 수 있는 부정적인 영향 중 하나는 두 노드가 통합될 때 결과 노드가 통합되는 노드들의 간선들의 합집합을 가지게 되는 경우이다.
간섭 그래프 색칠 가능성에 대한 통합과 집약의 긍정적인 영향은, 예를 들어, 노드가 통합되는 두 노드 모두와 간섭할 때, 노드의 차수가 하나 줄어들어 간섭 그래프의 전반적인 색칠 가능성을 향상시키는 경우이다.
여러 통합과 집약 휴리스틱이 존재한다.
적극적 통합과 집약
채틴의 원래 레지스터 할당자에서 처음 도입되었다. 이 휴리스틱은 비간섭적인, 복사 관련 노드를 통합하는 것을 목표로 한다. 복사 제거 관점에서 이 휴리스틱은 최상의 결과를 낸다. 반면에 적극적 통합과 집약은 추론 그래프의 색칠 가능성에 영향을 미칠 수 있다.
보존적 통합과 집약
적극적 통합과 집약과 동일한 휴리스틱을 주로 사용하지만, 간섭 그래프의 색칠 가능성을 손상시키지 않는 경우에만 이동을 병합한다.
반복적 통합과 집약
그래프의 색칠 가능성을 유지하면서 한 번에 하나의 특정 이동을 제거한다.
낙관적 통합과 집약
레지스터 할당 레지스터 할당 기술
적극적 통합과 집약에 기반하지만, 추론 그래프 색칠 가능성이 손상되는 경우 가능한 한 적은 이동을 포기한다.
일부 다른 레지스터 할당 접근 방식은 레지스터 사용을 최적화하기 위해 한 가지 기술에 국한되지 않는다. 예를 들어, 카바소스(Cavazos) 등은 선형 스캔과 그래프 색칠 알고리즘을 모두 사용할 수 있는 솔루션을 제안했다. 이 접근 방식에서 두 솔루션 중 하나를 선택하는 것은 동적으로 결정된다. 먼저, 기계 학습 알고리즘이 "오프라인"으로, 즉 런타임이 아닌 시점에 사용되어 어떤 할당 알고리즘을 사용해야 할지 결정하는 휴리스틱 함수를 구축한다. 그런 다음 이 휴리스틱 함수는 런타임에 사용되며, 코드 동작에 따라 할당자는 사용 가능한 두 알고리즘 중 하나를 선택할 수 있다.
트레이스 레지스터 할당은 아이슬(Eisl) 등이 개발한 최근 접근 방식이다. 이 기술은 할당을 지역적으로 처리한다. 이는 동적 프로파일링 데이터에 의존하여 주어진 제어 흐름 그래프에서 가장 자주 사용될 분기를 결정한다. 그런 다음 병합 지점을 가장 많이 사용된 분기 위주로 무시하는 "트레이스"(즉 코드 세그먼트) 세트를 추론한다. 각 트레이스는 할당자에 의해 독립적으로 처리된다. 이 접근 방식은 다른 트레이스 간에 다른 레지스터 할당 알고리즘을 사용할 수 있기 때문에 하이브리드로 간주될 수 있다.
분할 할당은 서로 다른 접근 방식을 결합하는 또 다른 레지스터 할당 기술로, 일반적으로 상반되는 것으로 간주된다. 예를 들어, 하이브리드 할당 기술은 첫 번째 휴리스틱 구축 단계가 오프라인에서 수행되고 휴리스틱 사용이 온라인에서 수행되기 때문에 분할된 것으로 간주될 수 있다. 같은 방식으로 B. 디우프(Diouf) 등이 오프라인 및 온라인 동작, 즉 정적 및 동적 컴파일에 모두 의존하는 할당 기술을 제안했다. 오프라인 단계에서는 먼저 정수 선형 계획법을 사용하여 최적의 스필 세트가 수집된다. 그런 다음 라이브 범위는 이전에 식별된 최적의 스필 세트에 의존하는 `compressAnnotation` 알고리즘을 사용하여 주석 처리된다. 레지스터 할당은 오프라인 단계에서 수집된 데이터를 기반으로 온라인 단계에서 수행된다.
2007년에 부셰(Bouchez) 등이 레지스터 할당을 스필링 전용 단계와 색칠 및 통합과 집약 전용 단계로 나누는 것을 제안하기도 했다.
레지스터 할당 다양한 기술 간 비교
여러 메트릭이 하나의 레지스터 할당 기술과 다른 기술의 성능을 평가하는 데 사용되었다. 레지스터 할당은 일반적으로 코드 품질, 즉 빠르게 실행되는 코드와 분석 오버헤드, 즉 최적화된 레지스터 할당으로 코드를 생성하기 위해 소스 코드를 분석하는 데 소요되는 시간 사이의 균형을 다루어야 한다. 이러한 관점에서 생성된 코드의 실행 시간과 활성 분석에 소요된 시간은 다양한 기술을 비교하는 데 적합한 메트릭이다.
적합한 메트릭이 선택되면, 메트릭이 적용될 코드는 실제 응용 프로그램의 동작을 반영하거나 알고리즘이 해결하려는 특정 문제와 관련성이 있어야 한다. 레지스터 할당에 관한 최근 기사들은 특히 다카포(Dacapo) 벤치마크 스위트를 사용한다.
리머티리얼라이제이션
컴퓨터 과학에서 리머티리얼라이제이션(rematerialization) 또는 리맷(remat)은 값을 메모리에서 로드하는 대신 재계산하여 시간을 절약하는 컴파일러 최적화 기법이다. 이는 일반적으로 레지스터 할당과 밀접하게 통합되어 있으며, 레지스터를 메모리로 스필링하는 대안으로 사용된다. 이 개념은 그레고리 차이틴, 마크 아우스랜더, 아쇼크 찬드라, 존 코크, 마틴 홉킨스 및 피터 마크스타인에 의해 고안되었으며 1970년대 후반 801 미니컴퓨터용 Pl.8 컴파일러에 구현되었다. 이후 1992년 프레스턴 브릭스, 키스 D. 쿠퍼, 린다 토르크존에 의해 개선되었다.
리머티리얼라이제이션
공통 부분식 제거 및 루프 불변 코드 이동과 같은 전통적인 최적화는 종종 중복 계산을 제거하는 데 중점을 둔다. 계산은 CPU 사이클을 필요로 하므로 이는 일반적으로 좋은 일이지만, 변수의 라이브 범위를 늘리고 많은 새로운 변수를 생성하여 레지스터 할당 중 스필링을 초래할 수 있는 잠재적으로 파괴적인 부작용이 있다. 리머티리얼라이제이션은 거의 정반대이다. 즉, CPU 계산량을 늘려 레지스터 압력을 줄인다. 불필요한 계산 시간을 추가하는 것을 피하기 위해 리머티리얼라이제이션은 컴파일러가 이점이 있다고 확신할 때만 수행된다. 즉, 메모리로 레지스터 스필링이 발생할 경우에만 수행된다.
리머티리얼라이제이션은 사용 가능 표현식의 개념을 사용하여 각 변수를 계산하는 데 사용되는 표현식을 추적함으로써 작동한다. 때때로 값을 계산하는 데 사용되는 변수가 수정되어 더 이상 해당 값을 리머티리얼라이즈하는 데 사용될 수 없는 경우가 있다. 그러면 해당 표현식은 더 이상 사용 가능하지 않다고 말한다. 다른 기준도 충족되어야 한다. 예를 들어 값을 리머티리얼라이즈하는 데 사용되는 표현식의 최대 복잡성 등이 있다. 로드보다 더 많은 시간이 걸리는 복잡한 계산을 사용하여 값을 리머티리얼라이즈하는 것은 도움이 되지 않을 것이다. 일반적으로 표현식은 부작용이 없어야 한다.
불필요한 코드 제거
컴파일러 이론에서 불필요한 코드 제거(Dead-code elimination, DCE, dead-code removal, dead-code stripping, 또는 dead-code strip)는 불필요한 코드(프로그램 결과에 영향을 미치지 않는 코드)를 제거하는 컴파일러 최적화이다. 이러한 코드를 제거하면 몇 가지 이점이 있다. 프로그램 크기를 줄여 일부 상황에서 중요한 고려 사항이 되고 전송할 바이트 수와 같은 리소스 사용량을 줄이며 실행 중인 프로그램이 관련 없는 연산을 실행하는 것을 피하게 하여 실행 시간을 단축한다. 또한 프로그램 구조를 단순화하여 추가 최적화를 가능하게 한다. 불필요한 코드에는 절대로 실행될 수 없는 코드(도달 불가능한 코드)와 불필요한 변수(쓰여졌지만 다시는 읽히지 않는 변수)에만 영향을 미치는, 즉 프로그램과 무관한 코드가 포함된다.
불필요한 코드 제거 예시
다음은 C로 작성된 예시이다.
값 사용에 대한 간단한 분석은 첫 번째 할당 후 b의 값이 foo 내부에서 사용되지 않음을 보여준다. 게다가 b는 foo 내부에 지역 변수로 선언되었으므로 foo 외부에서는 그 값을 사용할 수 없다. 따라서 변수 b는 불필요하며 최적화 프로그램은 해당 저장 공간을 회수하고 초기화를 제거할 수 있다.
또한 첫 번째 return 문이 무조건 실행되고 그 뒤에 "goto"가 도달할 수 있는 레이블이 없으므로, 두 번째 b에 대한 할당에 도달하는 실행 경로는 존재하지 않는다. 따라서 해당 할당은 도달 불가능하며 제거될 수 있다.
만약 해당 프로시저에 return 문 뒤에 레이블이 있고 프로시저의 다른 곳에 goto와 같은 더 복잡한 제어 흐름이 있었다면, b에 대한 할당에 도달할 수 있는 실행 경로가 존재했을 수도 있다.
또한 함수 내에서 일부 계산이 수행되더라도 그 값은 이 함수 스코프 외부에서 접근 가능한 위치에 저장되지 않는다. 게다가 함수가 정적 값(96)을 반환한다는 점을 고려할 때, 반환하는 값으로 단순화될 수 있다 (이 단순화는 상수 폴딩이라고 한다).
불필요한 코드 제거 예시
대부분의 고급 컴파일러는 불필요한 코드 제거를 활성화하는 옵션을 제공하며, 때로는 다양한 수준으로 제공한다. 낮은 수준은 실행될 수 없는 명령어만 제거할 수 있다. 높은 수준은 사용되지 않는 변수에 대한 공간도 예약하지 않을 수 있다. 더 높은 수준은 목적 없는 명령어 또는 함수를 판별하고 제거할 수 있다.
불필요한 코드 제거의 일반적인 사용 사례는 전처리기를 통한 선택적 코드 포함의 대안이다. 다음 코드를 고려해 보자.
표현식 0은 항상 거짓으로 평가되므로 if 문 내부의 코드는 절대로 실행될 수 없으며, 불필요한 코드 제거는 최적화된 프로그램에서 이를 완전히 제거한다. 이 기술은 디버그에서 선택적으로 코드 블록을 활성화하는 데 흔히 사용된다. 불필요한 코드 제거가 있는 최적화 프로그램을 사용하면 동일한 작업을 수행하기 위해 전처리기를 사용할 필요가 없어진다.
불필요한 코드 제거 예시
실제로 최적화 프로그램이 발견하는 불필요한 코드의 대부분은 최적화 프로그램의 다른 변환에 의해 생성된다. 예를 들어, 연산자 강도 감소의 고전적인 기술은 코드에 새로운 계산을 삽입하고 이전의 더 비싼 계산을 불필요하게 만든다. 이어진 불필요한 코드 제거는 이러한 계산을 제거하고 효과를 완료한다 (강도 감소 알고리즘을 복잡하게 하지 않고).
역사적으로 불필요한 코드 제거는 데이터 흐름 분석에서 파생된 정보를 사용하여 수행되었다. 정적 단일 대입 형식(SSA)에 기반한 알고리즘은 론 사이트론(Ron Cytron) 등이 쓴 SSA 형식에 대한 원본 학술 논문에 나타난다. 로버트 실링스버그(Robert Shillingsburg, aka Shillner)는 이 알고리즘을 개선하고 쓸모없는 제어 흐름 연산을 제거하기 위한 동반 알고리즘을 개발했다.