shopkeeper/korean_wiki_content_only_120125 huggingface dataset:
라이스 대학교의 키스 D. 쿠퍼(Keith D. Cooper), 티모시 J. 하비(Timothy J. Harvey), 켄 케네디(Ken Kennedy)는 그들의 논문 "A Simple, Fast Dominance Algorithm"에서 한 알고리즘을 설명한다.
위 코드에서 codice_6는 b의 (immediate dominator)로, b를 엄격히 지배하지만 b를 엄격히 지배하는 다른 어떤 노드도 엄격히 지배하지 않는 유일한 노드이다.
Φ 함수의 수를 줄이는 변형.
"최소" SSA는 각 이름이 정확히 한 번 값을 할당받고, 원래 프로그램에서 이름의 각 참조(사용)가 여전히 고유한 이름을 참조할 수 있도록 하는 데 필요한 최소한의 Φ 함수를 삽입한다. (후자의 요구 사항은 컴파일러가 각 연산에서 각 피연산자에 대한 이름을 기록할 수 있도록 하는 데 필요하다.)
그러나 이러한 Φ 함수 중 일부는 죽은 코드일 수 있다. 이러한 이유로 최소 SSA가 특정 절차에 필요한 가장 적은 수의 Φ 함수를 생성하는 것은 아니다. 일부 유형의 분석에서는 이러한 Φ 함수가 불필요하며 분석을 덜 효율적으로 실행시킬 수 있다.
가지치기된 SSA.
가지치기된 SSA 형식은 간단한 관찰에 기반한다. Φ 함수는 Φ 함수 후에 "활성화"(live)된 변수에만 필요하다. (여기서 "활성화"는 값이 문제의 Φ 함수에서 시작하는 특정 경로를 따라 사용된다는 의미이다.) 변수가 활성화되어 있지 않으면 Φ 함수의 결과는 사용될 수 없으며 Φ 함수에 의한 할당은 죽은 코드이다.
가지치기된 SSA 형식을 구성할 때는 Φ 함수 삽입 단계에서 활성 변수 정보를 사용하여 주어진 Φ 함수가 필요한지 여부를 결정한다. 원래 변수 이름이 Φ 함수 삽입 지점에서 활성화되어 있지 않으면 Φ 함수는 삽입되지 않는다.
가지치기를 데드 코드 제거 문제로 취급하는 또 다른 가능성도 있다. 이 경우 Φ 함수는 입력 프로그램의 모든 사용이 해당 함수로 다시 작성되거나, 다른 Φ 함수의 인수로 사용될 경우에만 활성화된다. 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 형식은 값이 할당될 때마다 각 변수의 이름을 변경한다. 대안적인 방식으로는 정적 단일 사용 형식(각 변수가 사용될 때마다 각 문에서 이름을 변경함)과 정적 단일 정보 형식(각 변수가 값이 할당될 때마다, 그리고 후지배 프론티어에서 이름을 변경함)이 있다.
기능별 확장은 변수의 단일 할당 속성을 유지하면서 추가 기능을 모델링하기 위한 새로운 의미론을 통합한다. 일부 기능별 확장은 배열, 객체 및 별칭 포인터와 같은 고수준 프로그래밍 언어 기능을 모델링한다. 다른 기능별 확장은 투기와 예측과 같은 저수준 아키텍처 기능을 모델링한다.
컴퓨터 과학에서 희소 조건부 상수 전파(Sparse conditional constant propagation, SCCP)는 정적 단일 대입 형식(SSA)으로 변환된 후 컴파일러에 자주 적용되는 최적화 기법이다. 이는 컴파일 시점에 계산될 수 있는 정적 값의 계산인 상수 폴딩을 전파한다. 더욱이, 이는 어떤 순서로든 또는 어떤 횟수로든 데드 코드 제거와 상수 전파를 개별적으로 적용하는 것보다 더 많은 상수 값과 따라서 더 많은 개선 기회를 찾을 수 있다.
이 알고리즘은 SSA 형식 코드의 추상 해석을 수행하여 작동한다. 추상 해석 중에는 일반적으로 값에 대한 평탄한 격자와 SSA 변수를 이 격자의 값에 매핑하는 전역 환경을 사용한다. 알고리즘의 핵심은 분기 명령어의 해석을 처리하는 방식에 있다. 분기 명령어를 만나면, 분기 조건은 조건에 있는 변수에 바인딩된 추상 값의 정밀도를 고려하여 가능한 한 최적으로 평가된다. 값들이 완벽하게 정밀하여(최상도 최하도 아닌) 추상 실행이 어느 방향으로 분기할지 결정할 수 있는 경우가 있을 수 있다. 값들이 상수가 아니거나 조건의 변수가 정의되지 않은 경우, 보수성을 유지하기 위해 두 분기 방향 모두를 취해야 한다.
추상 해석이 완료되면, 결코 도달하지 않은 명령어들은 데드 코드로 표시된다. 상수 값을 가진 것으로 발견된 SSA 변수들은 그 사용 지점에서 인라인될 수 있다(전파될 수 있다).
SCCP는 다음 뜻이 있다.
개인의 안보는 1948년 유엔이 채택한 세계 인권 선언에서 보장하는 기본적인 권리이다. 또한 유럽 인권 조약, 캐나다의 헌법, 남아프리카 공화국의 헌법 및 전 세계의 다른 법률에 의해 명시적으로 정의되고 보장되는 인권이기도 하다.
일반적으로 개인의 안보에 대한 권리는 자유와 관련이 있으며, 부당하게 투옥될 경우 인신보호청원과 같은 구제책을 받을 권리를 포함한다. 개인의 안보는 고문과 잔인하고 비정상적인 형벌 금지에 기반한 권리의 확장으로 볼 수도 있다. 개인의 안보에 대한 권리는 덜 치명적인 행위를 막을 수 있으며, 수감자 권리와 관련하여 사용될 수 있다.
개인의 안보에 대한 권리는 세계 인권 선언 제3조에 의해 보장된다. 이 조항에서 개인의 안보는 생존권 및 자유와 결합되어 있다. 전문은 "모든 사람은 생명, 자유 및 개인의 안전에 대한 권리를 가진다."고 되어 있다.
유엔 조약인 시민적 및 정치적 권리에 관한 국제규약(1966)도 개인의 안보에 대한 권리를 인정한다. 제3조는 "모든 사람은 자유와 개인의 안전에 대한 권리를 가진다."고 명시하며, 이 조항은 "자의적인 체포 또는 구금"을 금지한다. 이 조항은 "누구든지 법률에 의해 정해진 근거와 절차에 따르지 아니하고는 그 자유를 박탈당하지 아니한다."고 계속된다.
개인의 안보에 대한 권리는 유럽 인권 조약 제5조 (1)항의 자유와 안보에 대한 권리("모든 사람은 자유와 개인의 안보에 대한 권리를 가진다. 다음의 경우 및 법률에 규정된 절차에 따르지 아니하고는 누구도 자유를 박탈당하지 아니한다") 및 유럽 연합 기본권 헌장 제6조("모든 사람은 자유와 개인의 안보에 대한 권리를 가진다")에 명시되어 있다.
개인의 안보에 대한 권리는 1960년 캐나다의 캐나다 권리장전에서 인정되었다. 이 법의 제1조 (a)항은 "개인의 생명, 자유, 개인의 안전 및 재산 향유에 대한 권리, 그리고 적법절차에 따르지 아니하고는 이를 박탈당하지 않을 권리"를 인정했다. 그러나 권리장전은 법률이었고 헌법의 일부가 아니었다.
1982년, 개인의 안보에 대한 권리가 헌법에 추가되었다. 이는 캐나다 권리 및 자유 헌장의 제7조에 포함되었는데, "모든 사람은 생명, 자유 및 개인의 안전에 대한 권리와 기본적 정의의 원칙에 따르지 아니하고는 이를 박탈당하지 않을 권리를 가진다."고 규정하고 있다. 제7조의 개인의 안보는 신체와 건강의 사생활에 대한 권리와 개인의 "심리적 완전성"을 보호하는 권리로 구성된다. 즉, 이 권리는 개인의 정신 상태에 대한 정부에 의한 중대한 해( 스트레스 )로부터 보호한다. (블렌코 대 브리티시컬럼비아 인권위원회 사건, 2000년)
이 권리는 상당한 판례를 만들어냈다. 캐나다의 낙태는 R. 대 모르겐탈러 (1988) 사건에서 대법원이 치료적 낙태 위원회가 여성의 건강을 위협하여 개인의 안보를 침해했다고 판결한 후 합법화되었다. 일부 판사들은 또한 신체에 대한 통제권이 개인의 안보 내에 있는 권리이며, 낙태법에 의해 침해되었다고 느꼈다. 작전 해체 대 국왕 (1985) 사건에서 순항 미사일 시험은 핵전쟁 위험을 야기하여 개인의 안보를 침해한다는 주장이 제기되었으나 실패했다. 쇼이 대 퀘벡주 (법무장관) (2005) 사건에서 일부 대법원 판사들은 퀘벡주의 민간 의료 금지가 의료 지연이 신체적 및 심리적 결과를 초래할 수 있기 때문에 개인의 안보를 침해한다고 간주하기도 했다.
캐나다 대법원과 학계에서는 개인의 안보가 일부 경제적 권리도 보장하는지에 대한 논의가 있어왔다. 이론적으로, 정부가 복지를 거부하거나, 직업에 필수적인 재산을 빼앗거나, 면허를 거부함으로써 개인의 소득 창출 능력을 제한한다면 개인의 안보는 침해될 것이다. 그러나 제7조는 주로 법적 권리와 관련되어 있으므로 경제적 권리에 대한 이러한 해석은 의문스럽다. 많은 경제적 문제 또한 통치행위일 수 있다.
1996년 남아프리카 공화국 정부는 제12조에서 개인의 안보에 대한 권리를 인정한 헌법적 을 채택했다. 여기서 개인의 안보는 "자유에 대한 권리"와 결합되었다. 제12조는 신체 통제 및 재생산 통제, 고문 및 잔인하고 비정상적인 형벌로부터의 자유, 재판을 받을 권리를 포함하여 개인의 안보와 자유에 대한 권리를 더 자세히 정의했다. 전문은 다음과 같다.
튀르키예 헌법은 1982년에 제정되고 2001년에 개정된 제19조에서 자유에 대한 권리와 함께 개인의 안전을 보장한다. 이 조항은 정신 병원 및 중독자 시설, 범죄인 인도 등을 허용하는 법률에 따른 법원의 판결 형태로 이러한 권리의 제한을 명시한다. 이 조항은 또한 판사가 허용하는 경우, 충분한 시간이 없는 경우 또는 범죄를 저지른 것으로 보이는 경우에만 체포 및 구금을 제한한다. 그러면 체포된 사람은 체포 이유를 고지받게 되며, 근친자에게도 체포 사실이 통보된다. 마지막으로, 이 조항은 이러한 권리가 침해될 경우 정부의 보상을 허용한다.
1990년에 채택된 뉴질랜드 권리장전법은 제8조부터 제11조까지 "생명과 개인의 안전"을 보장한다. 제8조는 기본적 정의에 따라 박탈되는 경우를 제외하고는 생존권을 보장하며, 제9조는 잔인하고 비정상적인 처벌을 금지한다. 제10조는 개인의 의지에 반하여 의료 치료를 받지 않도록 금지한다. 마지막으로, 제11조는 뉴질랜드인에게 의료 치료를 받지 않을 권리를 부여한다.
개인의 안전은 1998년 영국 인권법 제1부 제5조에 명시되어 있다. 이 버전은 이 법의 최신 형태이며, 이후 약간의 수정이 있었다. 이 새로운 법은 토니 블레어가 약속한 헌법 개혁의 한 측면을 나타낸다.
컴퓨터 과학에서 명령어 스케줄링(Instruction scheduling)은 명령어 수준 병렬성을 향상시키기 위해 사용되는 컴파일러 최적화 기법으로, 명령어 파이프라인을 사용하는 시스템의 성능을 향상시킨다. 간단히 말해서, 코드의 의미를 변경하지 않으면서 다음을 수행하려고 한다.
파이프라인 지연은 구조적 위험(프로세서 리소스 제한), 데이터 위험(한 명령어의 출력이 다른 명령어에 의해 필요함), 제어 위험(분기)으로 인해 발생할 수 있다.
데이터 위험.
명령어 스케줄링은 일반적으로 단일 기본 블록에서 수행된다. 블록의 명령어를 특정 방식으로 재배열하는 것이 해당 블록의 동작을 보존하는지 확인하기 위해 데이터 종속성 개념이 필요하다. 세 가지 유형의 종속성이 있으며, 이는 세 가지 데이터 위험이기도 하다.
기술적으로 네 번째 유형인 읽기 후 읽기(RAR 또는 "Input")도 있다. 두 명령어 모두 동일한 위치를 읽는다. 입력 종속성은 두 명령문의 실행 순서를 제한하지 않지만, 배열 요소의 스칼라 교체에 유용하다.
세 가지 유형의 종속성을 존중하도록 하기 위해 종속성 그래프를 구성한다. 종속성 그래프는 각 정점이 명령어이고, I1이 종속성으로 인해 I2보다 먼저 와야 한다면 I1에서 I2로 가는 간선이 있는 유향 그래프이다. 루프 전달 종속성을 제외하면 종속성 그래프는 유향 비순환 그래프이다. 그러면 이 그래프의 모든 위상 정렬이 유효한 명령어 스케줄이 된다. 그래프의 간선은 일반적으로 종속성의 지연 시간으로 레이블이 지정된다. 이는 파이프라인이 지연 없이 대상 명령어를 진행하기 전에 경과해야 하는 클럭 사이클 수이다.
위상 정렬을 찾는 가장 간단한 알고리즘은 자주 사용되며 리스트 스케줄링으로 알려져 있다. 개념적으로, 이 알고리즘은 종속성 그래프의 소스를 반복적으로 선택하여 현재 명령어 스케줄에 추가하고 그래프에서 제거한다. 이로 인해 다른 정점이 소스가 될 수 있으며, 이들도 스케줄링을 위해 고려된다. 그래프가 비어 있으면 알고리즘이 종료된다.
좋은 스케줄을 만들기 위해서는 지연을 방지해야 한다. 이는 스케줄링될 다음 명령어의 선택에 따라 결정된다. 일반적으로 다음과 같은 휴리스틱이 사용된다.
위상 순서.
명령어 스케줄링은 레지스터 할당 전 또는 후에, 또는 전후 모두 수행될 수 있다. 레지스터 할당 전에 수행하는 장점은 최대 병렬성을 얻을 수 있다는 것이다. 레지스터 할당 전에 수행하는 단점은 레지스터 할당자가 사용 가능한 레지스터 수를 초과하는 레지스터를 사용해야 할 수 있다는 것이다. 이로 인해 스필/필 코드가 도입되어 해당 코드 섹션의 성능이 저하된다.
스케줄링되는 아키텍처에 잠재적으로 불법적인 조합(명령어 연동 부족으로 인해)을 가진 명령어 시퀀스가 있는 경우, 명령어는 레지스터 할당 후에 스케줄링되어야 한다. 이 두 번째 스케줄링 패스는 스필/필 코드의 배치도 개선한다.
스케줄링이 레지스터 할당 후에만 수행되면, 레지스터 할당으로 인해 스케줄러가 가능한 명령어 이동량을 제한하는 잘못된 종속성이 도입될 것이다.
명령어 스케줄링에는 여러 유형이 있다.
컴파일러 예시.
GNU 컴파일러 모음은 (명령어 집합 및 스케줄링 모두) 또는 (스케줄링만) 플래그를 사용하여 명령어 스케줄링을 수행하는 것으로 알려진 컴파일러 중 하나이다. 각 마이크로아키텍처에 대한 명령어 지연 시간 및 어떤 명령어가 병렬로 실행될 수 있는지(또는 이에 상응하게 각 "포트"가 무엇을 사용하는지)에 대한 설명을 사용하여 작업을 수행한다. 이 기능은 GCC가 지원하는 거의 모든 아키텍처에서 사용할 수 있다.
버전 12.0.0까지 LLVM/Clang의 명령어 스케줄링은 명령어 집합 및 스케줄링 모두에 대해 (LLVM 용어로 라고 함) 스위치만 허용했다. 버전 12부터 x86에 대해서만 () 지원이 추가되었다.
지연 시간 및 포트 사용 정보 출처는 다음과 같다.
LLVM의 는 모든 시스템에서 특히 x86이 아닌 시스템에 대한 정보를 수집하는 데 사용할 수 있어야 한다.
컴파일러 최적화에서 레지스터 할당(Register allocation)은 지역 자동 변수와 식의 결과를 제한된 수의 프로세서 레지스터에 할당하는 과정이다.
레지스터 할당은 기본 블록(지역 레지스터 할당) 전체, 함수/프로시저 전체(전역 레지스터 할당), 또는 호출 그래프를 통해 트래버스되는 함수 경계(프로시저 간 레지스터 할당)를 넘어 발생할 수 있다. 함수/프로시저별로 수행될 때, 호출 규약은 각 호출 사이트 주변에 저장/복원 삽입을 요구할 수 있다.
많은 프로그래밍 언어에서 프로그래머는 원하는 만큼 변수를 사용할 수 있다. 컴퓨터는 CPU의 레지스터를 빠르게 읽고 쓸 수 있으므로, 더 많은 변수가 CPU 레지스터에 있을 때 컴퓨터 프로그램은 더 빠르게 실행된다. 또한, 레지스터에 접근하는 코드는 때로는 더 간결하여 코드가 더 작아지고, 메모리 대신 레지스터를 사용하면 더 빠르게 가져올 수 있다. 그러나 레지스터의 수는 제한적이다. 따라서 컴파일러가 코드를 기계어로 번역할 때, 제한된 수의 CPU 레지스터에 변수를 어떻게 할당할지 결정해야 한다.
모든 변수가 동시에 사용 중(또는 "활성")인 것은 아니므로, 프로그램의 수명 동안 특정 레지스터는 다른 변수를 저장하는 데 사용될 수 있다. 그러나 동시에 사용 중인 두 변수는 변수 중 하나를 손상시키지 않고 동일한 레지스터에 할당될 수 없다. 모든 변수를 담을 레지스터가 충분하지 않으면 일부 변수는 RAM으로 이동되거나 RAM에서 가져올 수 있다. 이 과정을 레지스터 "스필링"(spilling)이라고 한다. 프로그램의 수명 동안 변수는 스필링될 수도 있고 레지스터에 저장될 수도 있다. 이 변수는 "분할"(split)된 것으로 간주된다. RAM에 접근하는 것은 레지스터에 접근하는 것보다 훨씬 느리므로 컴파일된 프로그램은 더 느리게 실행된다. 따라서 최적화 컴파일러는 가능한 한 많은 변수를 레지스터에 할당하는 것을 목표로 한다. 높은 "레지스터 압력"은 더 많은 스필링 및 재로드가 필요하다는 기술 용어이며, 브라운(Braun) 등이 "명령어에서 동시에 활성 상태인 변수의 수"로 정의했다.
또한, 일부 컴퓨터 설계는 자주 접근하는 레지스터를 캐시한다. 따라서 가능한 한 `move` 명령어의 원본과 대상에 동일한 레지스터를 할당함으로써 프로그램을 더욱 최적화할 수 있다. 컴파일러가 정적 단일 대입 형식(SSA)과 같은 중간 표현을 사용하는 경우 특히 중요하다. 특히 SSA가 완전히 최적화되지 않은 경우 인위적으로 추가적인 `move` 명령어를 생성할 수 있다.
레지스터 할당의 구성 요소.
따라서 레지스터 할당은 런타임에 변수를 어디에 저장할지, 즉 레지스터 내부 또는 외부에 저장할지 선택하는 것으로 구성된다. 변수를 레지스터에 저장해야 하는 경우 할당자는 이 변수가 어떤 레지스터에 저장될지 결정해야 한다. 궁극적으로 또 다른 과제는 변수가 동일한 위치에 얼마나 오랫동안 머물러야 하는지 결정하는 것이다.
레지스터 할당자는 선택된 할당 전략에 관계없이 이러한 과제를 해결하기 위해 일련의 핵심 동작에 의존할 수 있다. 이러한 동작은 여러 범주로 분류할 수 있다.
많은 레지스터 할당 접근 방식은 하나 이상의 특정 동작 범주에 최적화되어 있다.
레지스터 할당에서 발생하는 일반적인 문제.
레지스터 할당은 다양한 레지스터 할당 접근 방식으로 해결(또는 피할 수 있는) 여러 문제를 제기한다. 가장 일반적인 세 가지 문제는 다음과 같다.
레지스터 할당 기술.
레지스터 할당은 코드의 기본 블록에서 발생할 수 있다. 이를 "지역적"이라고 하며, 호르위츠(Horwitz) 등이 처음 언급했다. 기본 블록에는 분기가 없으므로 할당 과정은 빠르다고 생각된다. 레지스터 할당에서 제어 흐름 그래프 병합 지점의 관리가 시간 소모적인 작업으로 드러나기 때문이다. 그러나 이 접근 방식은 전체 컴파일 단위(예를 들어 메서드 또는 프로시저)에서 작동하는 "전역적" 접근 방식만큼 최적화된 코드를 생성하지 못한다고 생각된다.
그래프 색칠 할당.
그래프 색칠 할당은 레지스터 할당을 해결하는 지배적인 접근 방식이다. 이는 채틴(Chaitin) 등이 처음 제안했다.
이 접근 방식에서 그래프의 노드는 레지스터 할당 후보인 활성 범위(변수, 임시 변수, 가상/심볼릭 레지스터)를 나타낸다. 간선은 충돌하는 활성 범위, 즉 적어도 하나의 프로그램 지점에서 동시에 활성 상태인 활성 범위를 연결한다. 레지스터 할당은 간선으로 연결된 두 노드가 같은 색을 받지 않도록 노드에 색상(레지스터)을 할당하는 그래프 색칠 문제로 축소된다.
활성도 분석을 사용하여 간섭 그래프를 구축할 수 있다. 노드가 프로그램 변수인 간격 그래프인 간섭 그래프는 어떤 변수가 동일한 레지스터에 할당될 수 없는지를 모델링하는 데 사용된다.
채틴 스타일의 그래프 색칠 기반 레지스터 할당자의 주요 단계는 다음과 같다.
단점 및 추가 개선 사항.
그래프 색칠 할당은 세 가지 주요 단점이 있다. 첫째, 어떤 변수가 스필링될지 결정하기 위해 NP-완전 문제인 그래프 색칠에 의존한다. 일반 그래프에 대한 최소 색칠을 찾는 것은 실제로 NP-완전 문제이지만, 간격 그래프(간섭 그래프 포함)의 최소 색칠은 선형 시간에 수행될 수 있다(아래 선형 스캔 참조). 따라서 이 기술은 문제의 가정을 완전히 활용하지 못한다. 둘째, 활성 범위 분할이 사용되지 않는 한, 제거된 변수는 모든 곳에서 스필링된다. 저장 명령어는 변수 정의 직후 가능한 한 빨리 삽입되고, 로드 명령어는 변수 사용 직전에 삽입된다. 셋째, 스필링되지 않은 변수는 전체 수명 동안 동일한 레지스터에 유지된다.
반면에, 단일 레지스터 이름이 여러 레지스터 클래스에 나타날 수 있는데, 여기서 클래스는 특정 역할에서 상호 교환 가능한 레지스터 이름들의 집합이다. 그러면 여러 레지스터 이름이 단일 하드웨어 레지스터의 별칭일 수 있다.
마지막으로, 그래프 색칠은 레지스터 할당에 강력한 기술이지만, 활성 범위 수에 대해 제곱에 해당하는 최악의 경우 크기를 가질 수 있는 간섭 그래프를 사용하기 때문에 계산 비용이 많이 든다.
그래프 색칠 레지스터 할당의 전통적인 공식화는 암시적으로 단일 뱅크의 겹치지 않는 범용 레지스터를 가정하며, 겹치는 레지스터 쌍, 특수 목적 레지스터 및 여러 레지스터 뱅크와 같은 불규칙한 아키텍처 기능을 처리하지 않는다.
채틴 스타일 그래프 색칠 접근 방식의 한 가지 나중 개선점은 브릭스(Briggs) 등이 발견한 것이다. 이는 보존적 통합(conservative coalescing)이라고 불린다. 이 개선점은 두 활성 범위가 병합될 수 있는 시점을 결정하기 위한 기준을 추가한다. 주로, 비간섭 요구 사항 외에도 두 변수는 병합이 추가적인 스필링을 유발하지 않는 경우에만 통합될 수 있다. 브릭스 등은 채틴의 작업에 두 번째 개선점인 편향 색칠(biased coloring)을 도입한다. 편향 색칠은 복사 관련 활성 범위에 그래프 색칠에서 동일한 색상을 할당하려고 시도한다.
선형 스캔.
선형 스캔은 또 다른 전역 레지스터 할당 접근 방식이다. 이는 1999년 포레토(Poletto) 등이 처음 제안했다. 이 접근 방식에서는 코드가 그래프로 변환되지 않는다. 대신, 모든 변수를 선형적으로 스캔하여 간격으로 표현되는 활성 범위를 결정한다. 모든 변수의 활성 범위가 파악되면 간격을 시간 순서대로 순회한다. 이 순회가 활성 범위가 충돌하는 변수를 식별하는 데 도움이 될 수 있지만, 간섭 그래프는 구축되지 않으며 변수는 탐욕스러운 방식으로 할당된다.
이 접근 방식의 동기는 속도이다. 생성된 코드의 실행 시간 측면이 아니라 코드 생성에 소요되는 시간 측면에서의 속도이다. 일반적으로 표준 그래프 색칠 접근 방식은 고품질 코드를 생성하지만, 상당한 오버헤드가 있으며, 사용된 그래프 색칠 알고리즘은 2차 비용을 가진다. 이러한 특징 덕분에 선형 스캔은 현재 핫스팟 클라이언트 컴파일러, V8, Jikes RVM, 그리고 안드로이드 런타임(ART)과 같은 여러 JIT 컴파일러에서 사용되는 접근 방식이다. 핫스팟 서버 컴파일러는 우수한 코드를 위해 그래프 색칠을 사용한다.
이것은 폴레토(Poletto) 등이 처음 제안한 알고리즘을 설명한다. 여기서:
LinearScanRegisterAllocation
각 활성 구간 i에 대해, 시작점 기준으로 오름차순 반복
ExpireOldIntervals(i)
만약 length(active) = R 이면
SpillAtInterval(i)
그렇지 않으면
register[i] ← 사용 가능한 레지스터 풀에서 제거된 레지스터
i를 active에 추가, 끝점 기준으로 오름차순 정렬
각 구간 j 에 대해 active에서, 끝점 기준으로 오름차순 반복
만약 endpoint[j] ≥ startpoint[i] 이면
반환
active에서 j 제거
register[j]를 사용 가능한 레지스터 풀에 추가
spill ← active의 마지막 구간
만약 endpoint[spill] &gt; endpoint[i] 이면
register[i] ← register[spill]
location[spill] ← 새로운 스택 위치
active에서 spill 제거
location[i] ← 새로운 스택 위치
그러나 선형 스캔은 두 가지 주요 단점을 보인다. 첫째, 탐욕적인 특성 때문에 수명 구멍(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로 작성된 예시이다.
int foo(void) {
int b = 25; /* Assignment to dead variable */
c = a * 4;
b = 24; /* Unreachable code */
값 사용에 대한 간단한 분석은 첫 번째 할당 후 codice_1의 값이 codice_2 내부에서 사용되지 않음을 보여준다. 게다가 codice_1는 codice_2 내부에 지역 변수로 선언되었으므로 codice_2 외부에서는 그 값을 사용할 수 없다. 따라서 변수 codice_1는 불필요하며 최적화 프로그램은 해당 저장 공간을 회수하고 초기화를 제거할 수 있다.
또한 첫 번째 return 문이 무조건 실행되고 그 뒤에 "goto"가 도달할 수 있는 레이블이 없으므로, 두 번째 codice_1에 대한 할당에 도달하는 실행 경로는 존재하지 않는다. 따라서 해당 할당은 도달 불가능하며 제거될 수 있다.
만약 해당 프로시저에 return 문 뒤에 레이블이 있고 프로시저의 다른 곳에 codice_8와 같은 더 복잡한 제어 흐름이 있었다면, codice_1에 대한 할당에 도달할 수 있는 실행 경로가 존재했을 수도 있다.
또한 함수 내에서 일부 계산이 수행되더라도 그 값은 이 함수 스코프 외부에서 접근 가능한 위치에 저장되지 않는다. 게다가 함수가 정적 값(96)을 반환한다는 점을 고려할 때, 반환하는 값으로 단순화될 수 있다 (이 단순화는 상수 폴딩이라고 한다).
대부분의 고급 컴파일러는 불필요한 코드 제거를 활성화하는 옵션을 제공하며, 때로는 다양한 수준으로 제공한다. 낮은 수준은 실행될 수 없는 명령어만 제거할 수 있다. 높은 수준은 사용되지 않는 변수에 대한 공간도 예약하지 않을 수 있다. 더 높은 수준은 목적 없는 명령어 또는 함수를 판별하고 제거할 수 있다.
불필요한 코드 제거의 일반적인 사용 사례는 전처리기를 통한 선택적 코드 포함의 대안이다. 다음 코드를 고려해 보자.
c = a * (b / 2);
if (0) { /* DEBUG */
표현식 0은 항상 거짓으로 평가되므로 if 문 내부의 코드는 절대로 실행될 수 없으며, 불필요한 코드 제거는 최적화된 프로그램에서 이를 완전히 제거한다. 이 기술은 디버그에서 선택적으로 코드 블록을 활성화하는 데 흔히 사용된다. 불필요한 코드 제거가 있는 최적화 프로그램을 사용하면 동일한 작업을 수행하기 위해 전처리기를 사용할 필요가 없어진다.
실제로 최적화 프로그램이 발견하는 불필요한 코드의 대부분은 최적화 프로그램의 다른 변환에 의해 생성된다. 예를 들어, 연산자 강도 감소의 고전적인 기술은 코드에 새로운 계산을 삽입하고 이전의 더 비싼 계산을 불필요하게 만든다. 이어진 불필요한 코드 제거는 이러한 계산을 제거하고 효과를 완료한다 (강도 감소 알고리즘을 복잡하게 하지 않고).
역사적으로 불필요한 코드 제거는 데이터 흐름 분석에서 파생된 정보를 사용하여 수행되었다. 정적 단일 대입 형식(SSA)에 기반한 알고리즘은 론 사이트론(Ron Cytron) 등이 쓴 SSA 형식에 대한 원본 학술 논문에 나타난다. 로버트 실링스버그(Robert Shillingsburg, aka Shillner)는 이 알고리즘을 개선하고 쓸모없는 제어 흐름 연산을 제거하기 위한 동반 알고리즘을 개발했다.
동적으로 불필요한 코드 제거.
불필요한 코드는 일반적으로 무조건 불필요한 것으로 간주된다. 따라서 컴파일 타임에 불필요한 코드 제거를 통해 불필요한 코드를 제거하는 것이 합리적이다.
그러나 실제로 특정 조건에서만 불필요하거나 도달 불가능한 코드 섹션이 되는 경우가 흔하며, 이는 컴파일 또는 어셈블리 시점에는 알려지지 않을 수 있다. 이러한 조건은 다양한 런타임 환경(예: 운영 체제의 다른 버전, 특정 대상 환경에 로드된 드라이버 또는 서비스의 다른 세트 및 조합)에 의해 부과될 수 있으며, 이는 코드에 다른 특수 사례 세트를 요구하지만 동시에 다른 경우에 대해 조건부 불필요한 코드가 될 수 있다. 또한 소프트웨어(예: 드라이버 또는 상주 서비스)는 사용자 기본 설정에 따라 특정 기능을 포함하거나 제외하도록 구성될 수 있어 특정 시나리오에서 사용되지 않는 코드 부분이 쓸모없게 될 수 있다. 모듈형 소프트웨어는 필요에 따라 동적으로 라이브러리를 로드하도록 개발될 수 있지만, 대부분의 경우 특정 라이브러리에서 관련 루틴만 로드하는 것은 불가능하며, 설령 이것이 지원되더라도 루틴에는 주어진 시나리오에서 불필요한 코드로 간주될 수 있지만 컴파일 타임에는 제외될 수 없었던 코드 섹션이 포함될 수 있다.
수요를 동적으로 감지하고, 종속성을 식별 및 해결하며, 이러한 조건부 불필요한 코드를 제거하고, 로드 또는 런타임에 나머지 코드를 재결합하는 데 사용되는 기술을 동적 불필요한 코드 제거 또는 동적 불필요한 명령어 제거라고 한다.
대부분의 프로그래밍 언어, 컴파일러 및 운영 체제는 동적 적재 라이브러리 및 늦은 연결 외에는 거의 또는 전혀 지원을 제공하지 않으므로 선행 컴파일된 언어로 작성되거나 어셈블리어로 작성된 언어와 함께 동적 불필요한 코드 제거를 활용하는 소프트웨어는 매우 드물다. 그러나 Just-in-time 컴파일을 수행하는 언어 구현은 동적으로 불필요한 코드 제거를 위해 최적화할 수 있다.
비록 초점은 다소 다르지만, 유사한 접근 방식은 때때로 동적 소프트웨어 업데이트 및 핫 패치에도 활용된다.
별칭 분석(alias analysis)은 컴파일러 이론에서 저장 위치가 두 가지 이상의 방식으로 접근될 수 있는지 확인하는 데 사용되는 기술이다. 두 포인터가 동일한 위치를 가리키는 경우 별칭 처리된다고 말한다.
별칭 분석 기술은 일반적으로 흐름 민감도와 문맥 민감도에 따라 분류된다. 이는 may-alias 또는 must-alias 정보를 결정할 수 있다. 별칭 분석이라는 용어는 특정 사례인 포인터 분석과 종종 상호 교환적으로 사용된다.
별칭 분석기는 프로그램 내 별칭 처리를 이해하는 데 유용한 정보를 만들고 계산하는 것을 목표로 한다.
일반적으로 별칭 분석은 별개의 메모리 참조가 메모리의 동일한 영역을 가리키는지 여부를 결정한다. 이를 통해 컴파일러는 프로그램의 어떤 변수가 특정 문장에 의해 영향을 받을지 결정할 수 있다. 예를 들어, 구조체 멤버에 접근하는 다음 코드 섹션을 고려해 보자:
여기에는 세 가지 가능한 별칭 사례가 있다:
만약 p와 q가 별칭 처리될 수 없다면, codice_1는 codice_2로 변경될 수 있다. 만약 p와 q가 반드시 별칭 처리되어야 한다면, codice_1는 codice_4로 변경될 수 있는데, 왜냐하면 codice_5 = codice_6이기 때문이다. 두 경우 모두, 별칭 지식으로부터 최적화를 수행할 수 있다 (다른 스레드가 동일한 위치를 업데이트하여 현재 스레드와 인터리빙될 수 없거나, 언어 메모리 모델이 명시적인 동기화 구성이 없는 경우 현재 스레드에게 즉시 보이지 않도록 해당 업데이트를 허용한다고 가정한다). 반면에, p와 q가 별칭 처리되는지 여부가 알려지지 않으면, 어떤 최적화도 수행할 수 없으며 결과를 얻기 위해 전체 코드가 실행되어야 한다. 두 메모리 참조는 별칭 처리가 알려지지 않은 경우 may-alias 관계를 갖는다고 말한다.
별칭 분석 수행.
별칭 분석에서 우리는 프로그램의 메모리를 별칭 클래스로 나눈다. 별칭 클래스는 서로 별칭 처리될 수 없는 위치들의 분리된 집합이다. 여기서는 여기서 수행되는 최적화가 프로그램의 저수준 중간 표현에서 발생한다고 가정한다. 즉, 프로그램이 이진 연산, 점프, 레지스터 간 이동, 레지스터에서 메모리로 이동, 메모리에서 레지스터로 이동, 분기, 함수 호출/반환으로 컴파일되었다는 의미이다.
타입 기반 별칭 분석.
컴파일되는 언어가 타입 안전하고, 컴파일러의 타입 검사기가 정확하며, 언어가 지역 변수를 참조하는 포인터를 생성하는 기능이 부족하다면 (예: ML, 하스켈, 또는 자바), 유용한 최적화를 수행할 수 있다. 두 메모리 위치가 다른 별칭 클래스에 있어야 한다고 아는 많은 경우가 있다:
코드에 대한 별칭 분석을 수행할 때, 메모리에 대한 모든 로드 및 스토어는 해당 클래스로 레이블이 지정되어야 한다. 그러면 formula_1 별칭 클래스를 갖는 메모리 위치 formula_2와 formula_3가 주어졌을 때, formula_4이면 formula_2는 formula_3와 may-alias 관계를 가지며, formula_7이면 메모리 위치는 별칭 처리되지 않는다는 유용한 속성을 갖게 된다.
흐름 기반 별칭 분석.
흐름 기반 분석은 참조 또는 타입 캐스팅이 있는 언어의 프로그램에 적용될 수 있다. 흐름 기반 분석은 타입 기반 분석을 대신하거나 보완하는 데 사용될 수 있다. 흐름 기반 분석에서 새로운 별칭 클래스는 각 메모리 할당에 대해, 그리고 주소가 사용된 모든 전역 및 지역 변수에 대해 생성된다. 참조는 시간이 지남에 따라 하나 이상의 값을 가리킬 수 있으므로 하나 이상의 별칭 클래스에 속할 수 있다. 이는 각 메모리 위치가 단일 별칭 클래스 대신 별칭 클래스 집합을 갖는다는 것을 의미한다.
컴파일러 최적화에서 이스케이프 분석(Escape analysis)은 포인터의 동적 범위를 결정하는 방법이다. 이 분석은 프로그램 내에서 포인터가 어디에 접근될 수 있는지를 파악한다. 이는 포인터 분석 및 형태 분석과 관련이 있다.
변수(또는 객체)가 서브루틴에 할당될 때, 변수에 대한 포인터는 다른 실행 스레드나 호출 서브루틴으로 이스케이프될 수 있다. 구현에서 꼬리 재귀 최적화(일반적으로 함수형 프로그래밍 언어에서 요구됨)를 사용하는 경우, 객체는 호출된 서브루틴으로 이스케이프하는 것으로 간주될 수도 있다. 언어가 1급 연속을 지원하는 경우(예: 스킴 및 Standard ML of New Jersey), 콜 스택의 일부도 이스케이프될 수 있다.
서브루틴이 객체를 할당하고 그 객체에 대한 포인터를 반환하는 경우, 해당 객체는 프로그램 내의 불특정한 위치에서 접근될 수 있다. 즉, 포인터가 "이스케이프"한 것이다. 포인터는 또한 전역 변수나 현재 프로시저를 벗어나는 다른 데이터 구조에 저장될 때도 이스케이프할 수 있다.
이스케이프 분석은 포인터가 저장될 수 있는 모든 위치와 포인터의 생명 주기가 현재 프로시저 및 스레드에만 제한되는지 여부를 판단한다.
컴파일러는 이스케이프 분석 결과를 기반으로 최적화를 수행할 수 있다.
실용적 고려 사항.
객체 지향 프로그래밍 언어에서 동적 컴파일러는 이스케이프 분석을 수행하는 데 특히 적합하다. 전통적인 정적 컴파일에서는 메소드 오버라이딩으로 인해 이스케이프 분석이 불가능할 수 있다. 이는 호출된 모든 메소드가 포인터를 이스케이프시킬 수 있는 버전으로 오버라이드될 수 있기 때문이다. 동적 컴파일러는 오버로딩에 대한 가용한 정보를 사용하여 이스케이프 분석을 수행할 수 있으며, 관련 메소드가 동적 코드 로딩에 의해 오버라이드될 때 분석을 다시 수행할 수 있다.
자바 프로그래밍 언어의 인기로 인해 이스케이프 분석은 관심의 대상이 되었다. 자바의 힙 전용 객체 할당, 내장 스레딩, 썬 핫스팟 동적 컴파일러, 그리고 OpenJ9의 JIT 컴파일러 (JIT)의 조합은 이스케이프 분석 관련 최적화를 위한 후보 플랫폼을 제공한다 (자세한 내용은 자바의 이스케이프 분석 참조). 이스케이프 분석은 자바 표준 에디션 6에 구현되어 있다. 일부 JVM은 함수의 특정 경로에서 객체가 이스케이프하더라도 할당된 객체의 스칼라 대체를 가능하게 하는 부분 이스케이프 분석이라는 더 강력한 이스케이프 분석 변형을 지원한다.
example();
public static void example() {
Foo foo = new Foo(); //alloc
Bar bar = new Bar(); //alloc
이 예시에서는 두 개의 객체가 생성되고(alloc 주석), 그 중 하나가 다른 객체의 메소드에 인수로 제공된다. `setFoo()` 메소드는 받은 Foo 객체에 대한 참조를 저장한다. Bar 객체가 힙에 있었다면 Foo에 대한 참조는 이스케이프되었을 것이다. 그러나 이 경우 컴파일러는 이스케이프 분석을 통해 Bar 객체 자체가 `example()` 호출을 벗어나지 않는다는 것을 판단할 수 있다. 결과적으로 Foo에 대한 참조도 이스케이프할 수 없으며, 컴파일러는 두 객체를 안전하게 스택에 할당할 수 있다.
예시 (스킴).
다음 예시에서 벡터 p는 g로 이스케이프되지 않으므로 스택에 할당된 후 g를 호출하기 전에 스택에서 제거될 수 있다.
그러나 만약 다음과 같다면
p는 힙에 할당되거나 (g가 f가 컴파일될 때 컴파일러에 알려져 있고 잘 작동한다면) g가 호출될 때 제자리에 유지될 수 있는 방식으로 스택에 할당되어야 한다.
연속을 사용하여 예외와 같은 제어 구조를 구현하는 경우, 이스케이프 분석은 이를 자주 감지하여 실제 연속을 할당하고 콜 스택을 복사하는 것을 피할 수 있다. 예를 들어, 다음에서
(cond
((eof-object? next-object) '())
이스케이프 분석은 `call/cc`에 의해 캡처된 연속이 이스케이프하지 않으므로 연속 구조를 할당할 필요가 없으며, `continuation`을 호출하여 연속을 호출하는 것은 스택 풀기를 통해 구현될 수 있다고 판단할 것이다.
전자 회로 시뮬레이션(Electronic circuit simulation)은 실제 전자 장치나 회로의 동작을 복제하기 위해 수학적 모델을 사용한다.
시뮬레이션 소프트웨어는 회로 동작 모델링을 가능하게 하며 귀중한 분석 도구이다. 높은 정확도의 모델링 능력 덕분에 많은 대학교에서 이 유형의 소프트웨어를 전자기술자 및 전자공학 프로그램 교육에 활용한다. 전자 시뮬레이션 소프트웨어는 사용자를 학습 경험에 통합시킴으로써 사용자를 참여시킨다. 이러한 종류의 상호작용은 학습자가 내용을 분석하고, 합성하고, 구성하고, 평가하도록 적극적으로 참여시켜 학습자가 자신의 지식을 구성하게 한다.
실제로 회로를 구축하기 전에 회로의 동작을 시뮬레이션하는 것은 결함이 있는 설계를 알려주고 전자 회로 설계의 동작에 대한 통찰력을 제공함으로써 설계 효율성을 크게 향상시킬 수 있다. 특히 집적 회로의 경우, 툴링(포토마스크)은 비싸고, 브레드보드는 비실용적이며, 내부 신호의 동작을 탐침하는 것은 매우 어렵다. 따라서 거의 모든 IC 설계는 시뮬레이션에 크게 의존한다. 가장 잘 알려진 아날로그 시뮬레이터는 SPICE이다. 아마도 가장 잘 알려진 디지털 시뮬레이터는 베릴로그 및 VHDL 기반의 시뮬레이터일 것이다.
일부 전자 시뮬레이터는 회로도 편집기, 시뮬레이션 엔진 및 온스크린 파형 표시(그림 1 참조)를 통합하여 설계자가 시뮬레이션된 회로를 신속하게 수정하고 변경 사항이 출력에 미치는 영향을 확인할 수 있도록 한다. 또한 일반적으로 광범위한 모델 및 장치 라이브러리를 포함한다. 이러한 모델에는 일반적으로 BSIM과 같은 IC 특정 트랜지스터 모델, 저항기, 축전기, 유도자 및 변압기와 같은 일반 구성 요소, 사용자 정의 모델(베릴로그-A 또는 VHDL-AMS의 제어 전류 및 전압 소스 또는 모델 등)이 포함된다. 인쇄 회로 기판 (PCB) 설계에는 트레이스용 전송선로 및 구동 및 수신 전자장치용 IBIS 모델과 같은 특정 모델도 필요하다.
엄격히 아날로그 신호 시뮬레이터가 존재하지만, 인기 있는 시뮬레이터는 종종 아날로그 및 이벤트 기반 디지털 시뮬레이션 기능을 모두 포함하며 동시에 둘 다 시뮬레이션할 수 있는 경우 혼합 모드 또는 혼합 신호 시뮬레이터로 알려져 있다. 전체 혼합 신호 분석은 하나의 통합 회로도로부터 구동될 수 있다. 혼합 모드 시뮬레이터의 모든 디지털 모델은 전파 시간 및 상승/하강 시간 지연에 대한 정확한 사양을 제공한다.
혼합 모드 시뮬레이터가 제공하는 이벤트 기반 알고리즘은 범용이며 비디지털 유형의 데이터를 지원한다. 예를 들어, 요소는 실제 또는 정수 값을 사용하여 DSP 기능 또는 샘플링된 데이터 필터를 시뮬레이션할 수 있다. 이벤트 기반 알고리즘이 표준 SPICE 매트릭스 솔루션보다 빠르기 때문에 아날로그 모델 대신 이벤트 기반 모델을 사용하는 회로의 시뮬레이션 시간이 크게 단축된다.