KR101379556B1

KR101379556B1 - 바이-엔디언 컴파일러를 사용한 코드 최적화

Info

Publication number: KR101379556B1
Application number: KR1020117030086A
Authority: KR
Inventors: 미카일 유리에비치 레온코
Original assignee: 인텔 코오퍼레이션
Priority date: 2009-06-25
Filing date: 2009-06-25
Publication date: 2014-04-10
Also published as: CN102804142A; JP2012529698A; US8910114B2; RU2515546C2; EP2446352A4; KR20120058467A; RU2011152760A; JP5392689B2; CN102804142B; EP2446352A1; US20120185836A1; SG175951A1; WO2010151167A1

Abstract

일 실시예에서, 방법은 바이트 교환 연산을 식별하는 단계, 바이트 교환 연산 및 다른 표현들을 포함하는 도메인을 생성하는 단계, 도메인과 연관된 도메인 엔트리들 및 도메인 엑시트들을 식별하는 단계, 도메인의 교환을 실행함으로써 이득이 획득될 것이라고 결정하는 단계, 및 상기 결정에 응답해서, 도메인의 교환을 실행하고, 기억 매체에 교환된 도메인을 저장하는 단계를 포함한다. 다른 실시예들이 기술 및 청구된다.

Description

바이-엔디언 컴파일러를 사용한 코드 최적화{OPTIMIZING CODE USING A BI-ENDIAN COMPILER}

바이트 엔디언은 저장 및 검색이 다수의 액세스 크기들(예를 들어, 8-비트, 16-비트, 32-비트, 64-비트)을 지원하는 경우의 데이터 저장 및 검색의 속성이다. 더 미세한 입상도 액세스들은, 더 큰 액세스들이 메모리에 바이트들을 저장하는 순서를 프로그래머가 알게 허용한다. 빅-엔디언 변수들은 리틀-엔디언(little-endian) 변수들과는 반대 바이트 순서로 메모리에 저장된다. 리틀-엔디언 변수들은 최하위 메모리 바이트 어드레스에 최하위 바이트로 저장된다. 동일한 값을 포함하는 빅-엔디언 및 리틀-엔디언 변수들은 프로세서 레지스터에 존재할 때 동일하다. 상이한 것은 오직 메모리에서의 순서이다.

16-비트, 32-비트 및 64-비트 데이터 내의 바이트들의 순서는 프로그래머에게 가시적이다. C 프로그래밍 언어에서, 프로그래머는 유니온(union), 오버레이 데이터 구조의 타입을 사용해서, 또는 다수의 바이트들의 데이터에 대한 포인터를 싱글 바이트들에 대한 포인터로 캐스팅함으로써 바이트들에 액세스할 수 있다. 역사상, 이러한 기술들은 성능을 향상시키는데 사용되었다. 따라서, 상이한 엔디언의 아키텍처들에서 실행되는 동일한 C/C++ 코드는 상이한 결과들을 야기할 수 있다. 예를 들어, C 코드: int i = 0x12345678; 및 char c = *((char*)&i)의 경우, 코드가 빅-엔디언 아키텍처에서 컴파일링 및 실행되면, 'c'의 값은 0x12일 것이고, 코드가 리틀-엔디언 아키텍처에서 컴파일링 및 실행되면, 'c'의 값은 0x78일 것이다.

바이-엔디언 기술에 의한 컴파일러는, 원래 빅-엔디언 아키텍처에 대해 개발된 소스 코드의 컴파일링이 리틀-엔디언 아키텍처에서 실행될 수 있게 한다. 코드가 특별한 모드에서 컴파일링되면, 대부분의 경우들에서, 빅-엔디언 아키텍처에서 컴파일링 및 실행되는 경우에 작업하는 것과 동일한 방법으로 작업하고, 즉, 'c'는 상기 일례에서 0x12와 동일하다. 이러한 연산은 빅-엔디언으로 지정된 데이터를 메모리에 로딩 및 저장하기 전에 '바이트 교환' 연산들을 추가함으로써 달성된다.

바이-엔디언 기술에 의한 컴파일러는, 통상 최신 리틀-엔디언 아키텍처들에서 실행되도록 레거시 코드를 컴파일링하는데 사용된다. 데이터의 각각의 특정 피스가 빅-엔디언일지 리틀-엔디언일지를 결정하기보다는, 통상 프로그래머는 모든 레거시 코드를 빅-엔디언으로서 표시한다. 따라서, 데이터의 엔디언이 프로그래머에게 중요하지 않더라도, 컴파일러는 데이터의 로딩 및 저장 전에 바이트 교환을 추가한다. 이는 성능에 부정적인 영향을 준다.

도 1은 본 발명의 일 실시예에 따라 바이트 교환 제거를 실행하는 방법의 플로우챠트이다.
도 2는 본 발명의 일 실시예에 따라 데이터 바이트 순서를 제어함으로써 코드를 최적화하는 방법의 플로우챠트이다.
도 3은 본 발명의 일 실시예에 따른 성능 통계를 저장하기 위한 각종 데이터 기억 장치들의 블록도이다.
도 4는 본 발명의 일 실시예에 따른 시스템의 블록도이다.

실시예들은 도메인 교환 개념을 기반으로 바이트 교환 연산들의 더 인기 없는 경로들의 제거/이동을 통해 생성된 코드의 성능을 향상시킬 수 있다. 또한, 실시예들은 성능 향상이 가능할 때 데이터 바이트 순서 타입의 선택을 무시할 수 있다.

본 명세서에서 사용된, 교환을 허용하는 표현(swap-tolerant expression)은 상이한 바이트 순서의 일부(또는 모든) 인수들에서 연산되고 동일한 또는 상이한 바이트 순서의 유효한 결과를 야기하는 대응 표현으로 대체될 수 있는 컴파일링되는 코드의 표현이다. 일부 일례들로서, 상수에 대한 비교(예를 들어, x == 0x12345678)는 교환을 허용하는데, 교환된 인수 SWAP(x)를 고려할 때, 원래의 표현과 동일한 결과를 야기하는 경우, 대응값(Y == 0x78563412)를 갖기 때문이다. 여기서, SWAP은 바이트 교환 연산을 실행하는 표현이다. 비트 AND 연산은 교환을 허용하는데, 교환된 인수를 취해서 정확하지만 상이한 바이트 순서 결과를 야기하도록 하는 연산(동일한 비트 AND)이 존재하기 때문이다. 그러나, 산술(예를 들어, +, -, *, /) 연산들은 교환을 허용하지 않은데, 데이터에게 특정 바이트 순서를 엄격하게 요구하며, 교환된 인수들이 취해지는 경우 오류 결과를 야기하기 때문이다.

도메인은 컴파일링되는 코드 표현들의 집합이다. 도메인 엔트리는 도메인 밖의 표현이고, 그 결과는 도메인에 속한 표현에 의해 인수로서 취해진다. 도메인 엑시트는 도메인에 속한 표현의 결과를 인수로서 취하는 도메인 밖의 표현이다. 교환을 허용하는 도메인은, 일부(또는 모든) 도메인 엔트리들이 상이한 바이트 순서의 데이터로 대체되는 경우, 모든 도메인 엑시트들이 동일한 또는 상이한 바이트 순서의 유효 결과들이 되도록, 그들의 대응 표현들에 의해 대체될 수 있는 교환을 허용하는 표현들의 집합이다.

도메인의 교환은: 코드 의미론(semantics)이 보존되도록, (1) 필요한 도메인 엔트리들 및 엑시트들에서 바이트 교환 연산들을 배치 또는 제거함으로써 일부 또는 모든 도메인 엔트리들 및 엑시트들의 바이트 순서를 변경하고; (2) 상이한 바이트 순서로 연산되는 대응 표현들로 도메인의 모든 표현들을 대체하는, 컴파일링되는 코드의 변환이다. 엔트리들 및 엑시트들에 관한 도메인 교환에 있어서, 엔트리 또는 엑시트 표현이 바이트 교환인 경우, 바이트 교환은 제거될 수 있고, 그렇지 않은 경우, 바이트 교환은 삽입될 수 있다.

일례로서,

T1 = SWAP(A)

T2 = SWAP(B)

RES = T1 = T2

표현 "T1 = T2"는 교환을 허용하는 도메인이고, 표현들 "SWAP(A)" 및 "SWAP(B)"는 도메인 엔트리들이고, 대입 "RES = ..."는 도메인 엑시트이다. 여기서, 이러한 코드에 대한 도메인 교환은 다음과 같다:

T1 = A //바이트 교환이 제거됨

T2 = B //바이트 교환이 제거됨

RES = T1 = T2 //결과의 바이트 순서는 동일하다: 아무것도 추가되거나 제거되지 않음.

따라서, 각각의 교환을 허용하는 표현에 있어서, 도메인 교환이 실행되면, 엔트리들(즉, 인수들) 및 엑시트들(즉, 결과들)중 어느 것이 바이트 순서를 변경할 것인지가 알려진다. 예를 들어, 표현 X?Y:Z(X이면, Y, 아니면 Z)에서, Y 및 Z의 바이트 순서는 변경될 것이고, X의 바이트 순서는 유지될 것이다: X?Y':Z'. 따라서, 도메인의 엔트리들 및 엑시트들 중 어느 것이 바이트 순서를 변경하고 바이트 교환 연산(SWAP)이 이를 위해서만 삽입/제거됨이 알려진다.

도메인 교환 이득은, 삽입된 코드의 양에서 제거된 코드의 양(추정된 실행 카운터들뿐만 아니라 행해진/제거된 특정 명령어들의 가중치들을 고려함)을 뺀 것이 양수가 되게 하는 도메인 교환으로부터의 성능 이득이다.

일례로서,

T1 = A

T2 = SWAP(B)

RES = T1 = T2

여기서, 도메인 교환은 다음과 같다:

T1 = SWAP(A) //바이트 교환이 행해짐

T2 = B //바이트 교환이 제거됨

RES = T1 = T2 //아무것도 추가되거나 제거되지 않음.

도메인 교환 이득은, 원래의 코드의 "T1 = A"가 "T2 = SWAP(B)"보다 더 인기 없는 경우 양수이다. 용어들 "인기 없는(cold)" 및 "인기 있는(hot)"은 소정의 코드 세그먼트의 상대적 빈도 또는 사용과 관련됨을 주지하라. "인기 없는" 코드 세그먼트는 다른 코드 세그먼트에 대해 덜 자주 또는 시간상 더 띄엄 띄엄 사용된다. 따라서, 본 일례에 의해 도시된 바와 같이, 도메인 교환은 코드 주위에서 SWAP들의 이동을 야기할 수 있다.

이제 도 1을 참조하면, 본 발명의 일 실시예에 따라 바이트 교환 제거를 실행하는 방법의 플로우챠트가 도시되어 있다. 방법(10)은 컴퓨터 시스템의 하나 이상의 프로세서들에서 실행되는 컴파일러에 의해 실행될 수 있다. 본 발명의 범위가 이와 관련해서 제한되지 않으며, 일부 실시예들은 빅-엔디언 아키텍처에 대해 기록된 코드를 리틀-엔디언 아키텍처를 위해 최적화하도록 실행될 수 있다. 즉, 컴파일러는 리틀-엔디언 아키텍처인 프로세서에서 실행될 수 있다.

도 1에 도시된 바와 같이, 방법(10)은 개시해서, 최적화될 코드의 표현이 바이트 교환 연산을 포함하는 지를 결정할 수 있다(단계(20)). 포함하지 않으면, 제어는 다음 표현으로 반복할 수 있다(단계(30)). 바이트 교환 표현이 발생될 때, 제어는 단계(40)로 진행해서, 이러한 표현을 포함하는 도메인이 생성될 수 있다. 본 발명의 범위가 이와 관련해서 제한되지 않으며, 실시예들은 단일 과정으로 다수의 표현들을 최적화할 수 있도록 도메인의 범위를 확장시키고자 할 수 있다. 도메인의 생성의 세부 사항들은 더 후술된다. 도메인 생성 중에, 도메인은 가능하면 추가 표현들로 확장될 수 있다(단계(50)). 도메인 확장의 다른 세부 사항들도 후술된다. 도메인 생성 마지막에, 바이트 순서를 변경하는 도메인에 대한 각종 엔트리들 및 엑시트들이 식별될 수 있다(단계(60)). 후술되는 바와 같이, 도메인 엔트리들은 도메인으로의 입력들인 각종 인수들일 수 있는 반면, 엑시트들은 도메인 밖의 인수들로서 사용되는 각종 결과들일 수 있다.

여전히 도 1을 참조하면, 단계(70)에서, 바이트 교환 제거가 이득을 제공하는 지가 결정될 수 있다(단계(70)). 상술된 바와 같이, 이러한 결정은, 코드에 삽입된 표현들의 양 및 코드로부터 제거된 표현들의 양 간의 차이의 결정, 및 이러한 표현들과 연관된 각종 실행 카운트들에 대한 프로파일링 정보를 포함하는, 각종 프로파일링 정보를 기반으로 컴파일러에 의해 실행될 수 있다. 이 이득이 임계값보다 큰 지가 더 결정될 수 있다. 일 실시예에서, 이득 결정이 양수를 야기하면, 이득이 제공되도록, 이득이 제공됨을 나타내는 임계값은 0일 수 있다. 이득이 바이트 교환 제거에 의해 제공되지 않으면, 바이트 교환 제거가 실행되지 않으며, 컴파일러는 다음 표현으로 반복할 수 있음(상술된 단계(30)와 관련됨)을 주지하라.

대신, 제거가 이득을 제공한다고 결정되면, 제어는 단계(80)로 진행한다. 단계(80)에서, 바이트 교환 표현은 제거될 수 있고, 따라서, 상기 표현은 대응 표현으로 대체된다. 또한, 하나 이상의 추가 바이트 교환들은 도메인 내의 다른 로케이션들에서 삽입/제거될 수 있다(단계(80)). 또한, 이러한 바이트 교환 표현들은 하나 이상의 도메인 엔트리들 및/또는 엑시트들에서 유사하게 삽입 또는 제거될 수 있다. 변경된 코드는, 그 후, 변경된 코드를 포함하는 프로그램이 호출될 때의 차후의 실행을 위해, 시스템 메모리 또는 비휘발성 기억 장치 등의 적합한 기억 장치에 저장될 수 있다. 도 1의 실시예에 특정 구현으로 도시되지만, 본 발명의 범위는 이와 관련해서 제한되지 않으며, 다른 구현들이 가능함을 이해하라.

교환을 허용하는 도메인을 생성하기 위해, 임의의 교환을 허용하는 표현으로, 또는 제거되기를 희망하는 바이트 교환으로부터 시작해서 연결된 교환을 허용하는 표현들로 도메인을 확장할 수 있다. 다른 도메인 확장이 불가능하거나 실행이 어려우면, 도메인 교환이 실행될 수 있으며, 다른 도메인들이 생성될 수 있다. 인접한 교환을 허용하는 표현들이 있을 때, 도메인 확장이 가능하다. 여전히, 수개의 도메인들이 생성될 수 있는데, 각각의 인접한 교환을 허용하는 표현에 있어서, 현재 도메인에 추가하지 않기로 결정될 수 있으며, 수개의 도메인들이 상이한 도메인-교환 이득들을 가질 것이기 때문이다. 따라서, 최상의 생성된 도메인을 찾기 위해 전체 탐색이 실행될 수 있으며, 또는 일부 발견법(heuristics)이 적용될 수 있다. 특정 실시예들은 발견법의 사용을 기반으로 할 수 있다. 따라서, 바이트 교환 제거는 상술된 바와 같이 양수의 교환 이득을 제공하는 모든 교환을 허용하는 도메인들을 식별 및 교환할 수 있다.

따라서, 각종 실시예들에서, 일부 바이트 순서의 데이터에 대한 연산들은 상이한 바이트 순서의 동일한 데이터에 대한 동등한 연산들로 대체된다. 또한, 다수의 연결된 표현들 및 다수의 연결된 데이터는 단일 과정으로 동시에 최적화될 수 있다. 최적화의 결과로서, 일부 바이트 교환들이 제거될 뿐만 아니라 다른 바이트 교환들이 더 인기 없는 경로들로 이동된다. 따라서, 표현들은 상이한 바이트 순서의 데이터에서 연산되는 대응 표현으로 대체될 수 있으며, 교환들이 코드 내에서 이동될 수 있으며, 다수의 연결된 데이터가 바이트 순서를 변경할 수 있다. 이러한 방법으로, 바이트 교환들은 한 바이트 순서의 데이터에서 연산되는 코드의 한 피스를 상이한 바이트 순서의 데이터에서 연산되는 코드의 동등한 피스로 대체함으로써 제거될 수 있다.

이제 표 1을 참조하면, 본 발명의 일 실시예에 따른 알고리즘의 가능한 구현을 나타내는 의사 코드가 도시되어 있다. 표 1에 도시된 바와 같이, 바이트 교환 제거 및 도메인 생성을 위한 수개의 함수들이 제공될 수 있다. 도시된 바와 같이, 바이트 교환 함수는 도메인 생성 함수를 호출한다. 또한, 이득이 바이트 교환 표현의 제거에 내재되어 있는 지를 결정할 때, BENEFIT이라고 하는 다른 함수가 실행될 수 있다. 상술된 바와 같이, 이 함수는, 계산이 양수 값을 야기하면 이득이 존재한다고 결정할 수 있다. 양수 값이 발견되면, SWAP_DOMAIN이라고 하는 다른 함수가 실행되어, 도메인 뿐만 아니라 도메인 엔트리들 및 엑시트들 내의 적합한 로케이션들에서 바이트 교환 연산들의 실제 제거 및 삽입을 구현할 수 있다. 이러한 의사 코드는 일례이며, 다른 구현들이 가능함을 주지하라.

실시예들은 데이터 바이트 순서의 선택을 더 제어할 수 있다. 즉, 프로그래머가 지정한 대로 데이터 바이트 순서를 선택하기보다, 컴파일러는 데이터의 각각의 특정 피스의 바이트 순서가 프로그램의 의미에 영향을 주는 지를 검사할 수 있으며, 영향을 주지 않으면, 데이터의 이 특정 피스에 대한 바이트 순서는 성능의 관점에서 설정될 수 있다.

본 명세서에서 사용된, 데이터(예를 들어, 변수들, 데이터 구조들, 히프(heap) 데이터, 함수 인수들 등)의 바이트 순서는, 데이터의 모든 저장들 및 검색들이 동일한 크기이면, 프로그래머에게 가시적이지 않다. 데이터의 모든 저장들 및 검색들이 동일한 크기임을 증명하기 위해, 컴파일러는: 데이터가 상이한 크기의 다른 변수들(예를 들어, 유니온 멤버들)을 통해 액세스될 수 없고; 데이터의 어드레스(취해지더라도) 외부에서(즉, 컴파일링되는 코드 밖에서) 보이지 않으며, 외부에서 가시적인 변수에 저장되지 않으며, 외부 함수로 전달/외부 함수로부터 획득되지 않으며, 컴파일러가 따라 갈 수 없는 표현들로 참여/획득되지 않으며; 데이터의 어드레스가 취해져서 상이한 크기의 데이터에 대한 포인터에 캐스팅되면, 그 포인터에 의해 판독/기록되지 않음을 보장한다. 그러나, 컴파일러는 maloc/free/etc와 같은 외부 함수들에 대한 전제 조건들로부터의 공지된 제외 사항들을 허용하고, 모든 검색들 및 저장들이 동일한 크기임을 여전히 보장한다.

데이터 바이트 순서 가시성은 보수적으로 계산될 수 있다. 예를 들어, 바이트 순서는 달리 입증되지 않는 한 가시적인 것으로 처리될 수 있다. 함수 인수들의 바이트 순서 가시성을 정의하기 위해, 컴파일러는 함수의 모든 호출들이 (간접 호출들을 포함해서) 공지됨을 추가로 보장할 수 있다. 일례들로서, 그 어드레스가 결코 취해지지 않는, 최상위 레벨 정적 변수의 바이트 순서는 프로그래머에게 가시적이지 않으며, 모듈당 편집에서의 전역 변수의 바이트 순서는 프로그래머에게 가시적인 것으로 고려된다.

동일한 바이트 순서를 가져야만 하는 경우, 데이터의 피스들은 그룹을 구성한다. 이하의 일례에서, 변수들 'a' 및 'b'는 동일한 바이트 순서를 가져야만 하며, 따라서, 컴파일러는 이 순서를 보존해야만 한다:

int*ptr = condition? &a : &b

ptr[3] = 10.

특정 데이터의 어떤 바이트 순서가 실행이 용이한지를 결정하기 위해, 본 발명의 일 실시예에 따른 컴파일러는 데이터가 어떻게 사용되는 지를 검사한다. 실행 카운터들에 따라 데이터가 빅-엔디언 문맥에서 더 자주 사용되면, 컴파일러는 가능할 때 해당 데이터를 빅-엔디언으로 한다. 때때로, 문맥의 바이트 순서는 알려지지 않는다(예를 들어, 데이터는 하나의 변수로부터 다른 변수로 복사되고, 컴파일러는 양 변수들의 바이트 순서에 대해 아직 결정하지 않았다). 이러한 경우, 더 높은 확률을 가진 더 나은 엔디언을 선택하기 위해 발견법이 사용될 수 있다.

따라서, 본 발명의 일 실시예에 따른 컴파일러는 1) 프로그램이 연산하는 모든 데이터를 동일한 바이트 순서를 가져야만 하는 그룹들로 분할하고; 2) 그룹의 모든 데이터의 바이트 순서가 프로그래머에게 가시적이지 않도록 그룹들을 선택하며; 3) 바이트 순서가 변경되면, 양수의 성능 이득을 제공하는 그룹들만을 선택함으로써 선택을 개선하고; 4) 그룹들의 데이터의 모든 판독들/기록들을 조정함으로써 선택된 그룹들의 바이트 순서를 변경할 수 있다.

이제 도 2를 참조하면, 본 발명의 일 실시예에 따라 데이터 바이트 순서를 제어함으로써 코드를 최적화하는 방법의 플로우챠트가 도시되어 있다. 도 2에 도시된 바와 같이, 방법(100)은 시스템의 프로세서, 예를 들어, 리틀-엔디언 아키텍처를 가진 프로세서에서 실행되는 바이-엔디언 컴파일러를 사용해서 구현될 수 있다. 도 2에 도시된 바와 같이, 방법(100)은 코드를 실행하거나 발견법을 적용함으로써 개시되어 코드의 소정의 세그먼트에 대한 통계 정보를 획득할 수 있다(단계(110)). 이러한 통계 정보는 컴파일러의 제1 과정 실행에서 획득될 수 있고, 상기 컴파일러는 코드를 실행하거나 다른 연산들을 실행해서 통계 정보를 획득할 수 있다. 그 후, 데이터는 그룹들로 파싱될 수 있다(단계(120)). 좀 더 구체적으로, 데이터는 데이터 각각이 동일한 바이트 순서를 갖는 그룹들로 파싱될 수 있다. 즉, 그룹의 모든 데이터는 빅-엔디언 또는 리틀-엔디언일 수 있다.

각각의 그룹에 있어서, 그룹의 바이트 순서가 프로그래머에게 가시적인지의 여부가 결정될 수 있다(단계(130)). 더 후술되는 바와 같이, 바이트 순서가 가시적인지를 결정하기 위해 각종 분석들이 실행될 수 있다. 이러한 분석들은 제1 과정 중에 획득된 통계 정보를 적어도 일부 기반으로 할 수 있다. 바이트 순서가 가시적이면, 제어는 단계(140)로 이동되어, 이 그룹의 데이터에서 최적화가 가능하지 않기에, 다음 그룹이 선택될 수 있다.

바이트 순서가 가시적이지 않으면, 제어는 단계(130)로부터 단계(150)로 넘어가서, 그룹의 데이터에 대한 바이트 순서 변경이 성능으로부터 이득을 보는지가 결정될 수 있다. 각종 구현들로 더 후술되는 바와 같이, 성능 이득이 제공되는 지를 결정하기 위해 상이한 계산들이 실행될 수 있다. 이득이 제공되지 않으면, 최적화가 실행되지 않으며, 다음 그룹이 선택될 수 있다(단계(140)). 그렇지 않고, 바이트 순서 변경이 성능 이득을 제공하면, 제어는 단계(160)로 이동되어, 그룹의 바이트 순서가 변경될 수 있다. 변경된 코드는, 그 후, 변경된 코드를 포함하는 프로그램이 호출될 때 차후의 실행을 위해, 시스템 메모리 또는 비휘발성 기억 장치 등의 적합한 기억 장치에 저장될 수 있다. 도 2의 실시예에 특정 구현으로 도시되지만, 본 발명의 범위는 이와 관련해서 제한되지 않는다.

일 구현에서, 컴파일러 최적화는 2 편집 과정들에서 작업할 수 있다. 제1 과정에서, 데이터 사용에 대한 정보가 축적되며 바이트 순서 선호도가 성능 관점에서 계산된다. 제2 과정에서, 데이터 사용은 데이터의 각각의 특정 피스에 대한 선택된 바이트 순서에 따라 조정된다. 따라서, 데이터의 특정 피스의 바이트 순서가 가시적인 지의 여부가 결정될 수 있다. 둘째로, 성능 관점에서 더 의미 있는 바이트 순서가 식별될 수 있다. 마지막으로, 특정 데이터의 바이트 순서가 변환될 수 있다.

데이터(변수, 함수 인수, 함수 등)의 각각의 피스는 그 데이터의 어드레스를 포함하는 보통의 포인터처럼 처리되는 DATA_ADDRESS 위조 포인터를 갖는다. 일 실시예에서, 각각의 포인터(및 DATA_ADDRESS 위조 포인터들)는 각종 데이터 구조들을 유지한다.

일 실시예에서, 구조들은 도 3에 도시된 바와 같은 성능 모니터 표(150)에 저장될 수 있다. 도 3은 본 발명의 일 실시예에 따른 성능 통계를 저장하기 위한 각종 기억 장치들의 블록도이다. 일부 실시예들에서, 표(150)는 시스템 메모리에 저장될 수 있지만, 다른 구현들에서, 표는 컴파일러가 실행되는 프로세서의 캐시 메모리에 저장될 수 있다. 도 3에 도시된 바와 같이, 표(150)는 각각의 포인터 및 데이터 어드레스 위조 포인터에 대해, 포인터가 복사된 포인터들의 리스트를 저장하기 위한 행선지 리스트(160)를 포함할 수 있다. 유사하게, 소스 리스트(165)는 대응 포인터와 연관된 소스들의 리스트를 저장한다. 또한, 액세스 크기 리스트(170)는 대응 포인터와 연관된 판독/기록의 크기를 저장할 수 있다. 차례로, 이득 카운터(175)는 바이트 순서 변경이 포인터와 연관된 표현과 관련해서 성능에 (긍정적 또는 부정적) 영향을 주는 지에 따라 증가/감소될 수 있다. 따라서, 각각의 포인터 및 위조 포인터는 상기 리스트들 각각을 유지할 수 있다. 일 실시예에서, VALUE_COPIED_TO 및 VALUE_COPIED_FROM 리스트들(행선지 리스트(160) 및 소스 리스트(165)에 대응함)은 다른 포인터들을 포함할 수 있으며; ACCESS_SIZE 리스트(액세스 리스트(170)에 대응함)는 정수들을 포함하고; 이득 카운터(175)는 데이터 사용 통계들을 누적한다. 처음에, 외부적으로 가시적인 심볼들(변수들, 함수들) 뿐만 아니라 다른 변수들(예를 들어, 유니온 멤버들)을 통해 액세스될 수 있는 변수들 및 상이한 크기의 다른 변수들에 대응하는 DATA_ADDRESS 위조 포인터들에 대한 ACCESS_SIZE 리스트는 (제로 액세스 크기가 가시적인 바이트 순서를 나타내는 일 실시예에서) 제로 값을 포함한다. 다른 리스트들은 처음에는 비어 있으며, 이득 카운터들은 처음에 0으로 설정된다.

제1 과정에서, 컴파일러는 실제 데이터로 상기 리스트들을 채운다. 값이 한 포인터로부터 다른 포인터로 복사될 때마다, 소스의 VALUE_COPIED_TO 리스트 및 행선지의 VALUE_COPIED_FROM 리스트는 적당하게 확장된다. 데이터의 어드레스가 저장될 때마다, 소스 ADDRESS_DATA의 VALUE_COPIED_TO 및 행선지의 VALUE_COPIED_FROM은 적당하게 확장된다.

판독/기록이 발견될 때마다, 대응 ACCESS_SIZE 리스트 엔트리는 판독/기록 크기로 확장된다. 이 때, 이득 카운터는 현재 표현의 발견적 실행 카운터에 의해 증가 또는 감소되거나, 바이트 순서 변경이 어떻게 표현을 변경하는 지에 따라 본래 그대로 유지된다. 후술된 일례들에서, 각종 표현들의 변경들은 변수 A의 바이트 순서의 변경을 반영한다:

A = SWAP(B) → A = B //이득 카운터 증가

A = 0x12345678 → A = 0x78563412 //이득 카운터가 그대로 유지됨

A = B → A = SWAP(B) //이득 카운터 감소.

포인터 또는 데이터 어드레스에서 지원되지 않은 연산이 발견될 때마다, 대응 ACCESS_SIZE 리스트는 제로 값으로 확장된다. 제1 과정의 마지막에, 모든 리스트들이 생성되고, 컴파일러는 바이트 순서 가시성을 결정하기 위해 충분한 정보를 갖는다. 소정의 데이터에 있어서, ADDRESS_DATA의 VALUE_COPIED_TO 리스트를 통해 타동적으로 달성 가능한 모든 포인터 변수들의 ACCESS_SIZE 리스트들의 유니온이 단일 요소보다 더 많이 포함하지 않으면(또한, 해당 요소가 제로가 아니면), 데이터의 모든 판독들/기록들은 특정 크기이며, 따라서, 이러한 특정 데이터의 바이트 순서는 프로그래머에게 가시적이지 않다.

어떤 데이터 피스들이 소정의 데이터와 동일한 바이트 순서를 가져야만 하는지를(즉, 어떤 데이터 피스들이 그룹을 구성하는지를) 찾기 위해, 컴파일러는 VALUE_COPIED_TO 및 VALUE_COPIED_FROM 리스트들을 통해 타동적으로 달성 가능한 ADDRESS_DATA 포인터들의 리스트를 생성한다. VALUE_COPIED_TO 및 VALUE_COPIED_FROM 리스트들을 통해 타동적으로 달성 가능한 모든 포인터들의 ACCESS_SIZE 리스트들의 유니온이 단일 요소보다 더 많이 포함하지 않으며 해당 요소가 제로가 아니면, 전체 그룹에 대한 최적화가 가능하다.

전체 그룹의 바이트 순서가 프로그래머에게 가시적이지 않으며 전체 그룹에 대한 상이한 바이트 순서의 선택이 성능 이득을 제공하면(예를 들어, 타동적으로 액세스 가능한 모든 포인터들의 BENEFIT들의 합이 양수이면), 컴파일러는 교환을 실행하고 데이터 사용을 조정한다.

따라서, 실시예들은 데이터의 각각의 특정 피스가 어떻게 사용되는 지를 검사하고, 실행 카운터들 및 데이터 사용을 기반으로 바이트 순서를 결정한다. 또한, 실시예들은 특정 부류의 데이터(예를 들어, 오직 반환 값들)가 아닌, 기준에 적합한 모든 데이터에 적용될 수 있다. 바이트 순서 선택은 컴파일링되는 애플리케이션의 데이터 사용을 기반으로 하고; 결정은 "두루 적용되는(one fits all)" 모델이 아닌, 각각의 특정 애플리케이션에 대한 데이터의 각각의 특정 피스에 대해 이루어진다. 이러한 방법으로, 컴파일러는 사용자 결정에 의존하지 않고 어떤 데이터가 상이한 바이트 순서인지를 결정할 수 있어서, 생성된 코드는 더 높은 성능을 가질 수 있다.

이제 표 2를 참조하면, 본 발명의 일 실시예에 따라 2 과정들을 제공하기 위한 간소화된 의사 코드가 도시되어 있다. 표 2에 도시된 바와 같이, 2 과정들은 특정 데이터에 대한 바이트 순서의 선택을 제어하기 위해 컴파일러에 의해 실행된다. 도시된 바와 같이, 제1 과정은 각각의 변수 및 코드의 포인터와 연관된 각종 리스트들의 갱신을 포함하는 사용 통계들을 수집하기 위해 코드를 실행하거나 다른 발견법을 실행하는데 사용될 수 있다. 제2 과정은 수집된 사용 통계들을 기반으로 코드를 최적화하도록 실행된다. 바이트 순서 변경이 코드를 최적화할 것으로 결정될 때, 이러한 바이트 교환 연산들이 코드로부터 삽입/제거된다.

표 2에 도시된 바와 같이, 총 BENEFIT가 양수이기 때문에, 여기에 입력되는 교환들은 이하의 변환들 중 하나를 사용해서 최적화될 것이다:

SWAP(SWAP(X)) → X

SWAP(const) → const_swapped

따라서, 표현은 다음과 같다:

X := SWAP(SWAP(X)+1) //X는 빅-엔디언이며 다음과 같이 변환된다:

X := SWAP(SWAP(SWAP(SWAP(X))+1))) //X는 리틀-엔디언이고 차후에 다음과 같이 최적화된다:

X := X + 1

실시예들은 다수의 상이한 시스템 타입들로 구현될 수 있다. 이제 도 4를 참조하면, 본 발명의 일 실시예에 따른 시스템의 블록도가 도시되어 있다. 도 4에 도시된 바와 같이, 멀티프로세서 시스템(300)은 지점간 상호 연결 시스템이고, 지점간 인터커텍트(350)를 통해 연결된 제1 프로세서(370) 및 제2 프로세서(380)를 포함한다. 도 4에 도시된 바와 같이, 프로세서들(370, 380) 각각은 제1 및 제2 프 코어들(즉, 프로세서 코어들(374a, 374b) 및 프로세서 코어들(384a, 384b))을 포함하는 멀티코어 프로세서들일 수 있다.

여전히 도 4를 참조하면, 제1 프로세서(370)는 메모리 제어기 허브(MCH)(372) 및 지점간(P-P) 인터페이스들(376, 378)을 더 포함한다. 유사하게, 제2 프로세서(380)는 MCH(382) 및 P-P 인터페이스들(386, 388)을 포함한다. 도 4에 도시된 바와 같이, MCH들(372, 382)은 각각의 메모리들, 즉, 메모리(332) 및 메모리(334)에 프로세서들을 연결하고, 상기 메모리들은 각각의 프로세서들에 국부적으로 부착된 메인 메모리(예를 들어, 동적 랜덤 액세스 메모리(DRAM))의 부분일 수 있다. 제1 프로세서(370) 및 제2 프로세서(380)는, 각각, P-P 인터커텍트들(352, 354)을 통해 칩셋(390)에 연결될 수 있다. 도 4에 도시된 바와 같이, 칩셋(390)은 P-P 인터페이스들(394, 398)을 포함한다.

또한, 칩셋(390)은 고 성능 그래픽 엔진(338)과 칩셋(390)을 연결하는 인터페이스(392)를 포함한다. 차례로, 칩셋(390)은 인터페이스(396)를 통해 제1 버스(316)에 연결될 수 있다. 도 4에 도시된 바와 같이, 각종 I/O 디바이스들(314)은, 제1 버스(316)를 제2 버스(320)에 연결하는 버스 브리지(318)와 함께, 제1 버스(316)에 연결될 수 있다. 일 실시예에서, 각종 디바이스들, 예를 들어, 키보드/마우스(322), 통신 디바이스들(326), 및 디스크 드라이브 또는 코드(330)를 포함할 수 있는 다른 대용량 기억 장치 등의 데이터 기억 유닛(328)은, 제2 버스(320)에 연결될 수 있다. 이러한 코드는, 프로세서들(370, 380) 중 하나 이상에서 실행될 수 있는, 본 발명의 일 실시예에 따른 컴파일러를 포함할 수 있다. 또한, 오디오 I/O(324)는 제2 버스(320)에 연결될 수 있다.

실시예들은 코드로 구현될 수 있으며, 명령어들을 실행하도록 시스템을 프로그래밍하는데 사용될 수 있는 명령어들이 저장된 기억 매체에 저장될 수 있다. 기억 매체는, 플로피 디스크들, 광 디스크들, SSD들(solid state drives), CD-ROM들(compact disk read-only memories), CD-RW들(compact disk rewritables), 및 자기-광 디스크들을 포함하는 임의의 타입의 디스크, ROM(read-only memories), DRAM(dynamic random access memories), SRAM(static random access memories) 등의 RAM(random access memories), EPROM(erasable programmable read-only memories), 플래시 메모리들, EEPROM(electrically erasable programmable read-only memories), 자기 또는 광 카드 등의 반도체 디바이스들, 또는 전자 명령어들을 저장하기에 적합한 임의의 다른 타입의 매체를 포함할 수 있지만, 이들로만 제한되지 않는다.

본 발명이 제한된 수의 실시예들과 관련해서 기술되었지만, 당업자는 다수의 변경들 및 변형들을 인식할 것이다. 첨부된 청구항들은 본 발명의 정확한 원리 및 범위 내에 속한 모든 변경들 및 변형들을 포함한다고 의도된다.

Claims

컴퓨터 시스템의 프로세서에서 실행되는 컴파일러를 사용해서, 바이트 교환(swap) 연산을 식별하는 단계;
상기 컴파일러를 사용해서, 상기 바이트 교환 연산 및 교환을 허용하는 다른 표현들을 포함하는 도메인을 생성하고, 상기 도메인과 연관된 도메인 엔트리들 및 도메인 엑시트들을 식별하는 단계;
상기 컴파일러를 사용해서, 상기 도메인의 교환을 실행함으로써 성능 이득이 제공될 것이라고 결정하고, 상기 결정에 응답해서, 상기 도메인의 교환을 실행하는 단계; 및
상기 컴퓨터 시스템의 기억 매체에 상기 교환된 도메인을 저장하는 단계
를 포함하는 방법.
제1항에 있어서,
상기 도메인의 교환을 실행하는 단계는 상기 연관된 도메인 엔트리들 및 도메인 엑시트들 중 적어도 일부의 바이트 순서를 변경하는 단계, 및 상기 도메인의 표현들을 상이한 바이트 순서로 연산되는 대응 연산들로 대체하는 단계를 포함하는 방법.
제2항에 있어서,
상기 도메인으로의 도메인 엔트리의 바이트 순서를 변경하는 단계는, 상기 도메인 엔트리가 상기 바이트 교환 연산을 포함하면 바이트 교환 연산을 제거하고, 상기 도메인 엔트리가 상기 바이트 교환 연산을 포함하지 않으면 바이트 교환 연산을 삽입하는 단계를 포함하는 방법.
제2항에 있어서,
상기 도메인으로부터의 도메인 엑시트의 바이트 순서를 변경하는 단계는, 상기 도메인 엑시트가 상기 바이트 교환 연산을 포함하면 바이트 교환 연산을 제거하고, 상기 도메인 엑시트가 상기 바이트 교환 연산을 포함하지 않으면 바이트 교환 연산을 삽입하는 단계를 포함하는 방법.
제2항에 있어서,
제1 표현으로부터 바이트 교환 연산을 제거하고 제2 표현에 바이트 교환 연산을 삽입하는 단계를 더 포함하고, 상기 제1 표현은 상기 제2 표현의 경로보다 더 인기 있는 경로인 방법.
제1항에 있어서,
상기 도메인으로부터 제거된 코드의 양에서 상기 도메인에 삽입된 코드의 양을 뺀 것이 임계값보다 더 크다고 결정함으로써 이득을 계산하는 단계를 더 포함하는 방법.
제6항에 있어서,
상기 이득을 계산하는 단계는 상기 삽입된 코드 및 상기 제거된 코드에 가중치를 주고, 상기 삽입된 코드 및 상기 제거된 코드와 연관된 실행 카운터들을 분석하는 단계를 포함하는 방법.
제1항에 있어서,
상기 도메인의 교환을 실행하는 단계는 단일 과정으로 상기 도메인의 다수의 연결된 표현들을 최적화하는 단계를 포함하는 방법.
명령어들이 실행될 때 컴퓨터 시스템이,
상기 컴퓨터 시스템의 프로세서에서의 코드의 실행에 대한 통계 정보를 획득하고 - 상기 통계 정보는 상기 컴퓨터 시스템의 통계 기억 장치에 저장됨 - ;
상기 프로세서에서 실행되는 컴파일러에서, 상기 코드가 연산하는 데이터를 복수의 그룹들로 파싱하며 - 상기 그룹들 각각의 데이터는 상기 코드의 적합한 실행을 위해 동일한 바이트 순서를 가짐 - ;
상기 컴파일러에서, 상기 복수의 그룹들 각각에 대해, 한 그룹의 데이터의 바이트 순서가 프로그래머에게 가시적인지를 결정하고;
상기 바이트 순서가 가시적이지 않은 각각의 그룹에 대해, 상기 컴파일러에서, 상기 바이트 순서의 변경이 성능 이득을 제공하는 지를 결정하며;
상기 바이트 순서의 변경이 성능 이득을 제공하는 각각의 그룹에 대해, 대응 그룹의 바이트 순서를 변경해서 변경된 그룹을 획득하고;
상기 컴퓨터 시스템의 기억 매체에 상기 변경된 그룹들 각각을 저장하도록
하는 상기 명령어들을 포함하는 프로그램을 기록한 컴퓨터 판독가능한 기록매체.
제9항에 있어서,
실행될 때 상기 컴퓨터 시스템이, 제1 포인터가 제2 포인터에 대한 소스일 때 상기 제1 포인터의 행선지 리스트를 갱신하고, 다른 포인터가 상기 제1 포인터에 대한 소스일 때 상기 제1 포인터의 소스 리스트를 갱신하도록 하는 명령어들을 더 포함하는 프로그램을 기록한 컴퓨터 판독가능한 기록매체.
제10항에 있어서,
실행될 때 상기 컴퓨터 시스템이, 제3 포인터와 연관된 메모리 액세스가 발생될 때 액세스의 크기로 상기 제3 포인터의 액세스 리스트를 갱신하도록 하는 명령어들을 더 포함하는 프로그램을 기록한 컴퓨터 판독가능한 기록매체.
제11항에 있어서,
실행될 때 상기 컴퓨터 시스템이, 표현에 대한 바이트 순서 변경으로 인한 성능 이득의 영향을 기반으로 상기 코드의 표현의 이득 카운터를 갱신하도록 하는 명령어들을 더 포함하는 프로그램을 기록한 컴퓨터 판독가능한 기록매체.
제10항에 있어서,
실행될 때 상기 컴퓨터 시스템이, 상기 소스 리스트 및 상기 행선지 리스트를 통해 타동적으로 달성 가능한 포인터들의 리스트를 생성하도록 하는 명령어들을 더 포함하는 프로그램을 기록한 컴퓨터 판독가능한 기록매체.
제13항에 있어서,
실행될 때 상기 컴퓨터 시스템이, 상기 소스 리스트 및 상기 행선지 리스트를 통해 타동적으로 달성 가능한 상기 포인터들의 상기 리스트의 유니온이 하나의 비제로 요소(non-zero element)보다 더 많이 포함하지 않고 타동적으로 액세스 가능한 모든 포인터들에 대한 이득 계산의 합이 양수이면 상기 바이트 순서의 변경이 성능 이득을 제공한다고 결정하도록 하는 명령어들을 더 포함하는 프로그램을 기록한 컴퓨터 판독가능한 기록매체.
명령어들을 실행하는 프로세서 - 상기 프로세서는, 상기 프로세서에서의 코드의 실행에 대한 통계 정보를 획득하고, 상기 코드가 연산하는 데이터를 복수의 그룹들로 파싱하며 - 상기 그룹들 각각의 데이터는 상기 코드의 적합한 실행을 위해 동일한 바이트 순서를 가짐 - , 상기 바이트 순서가 프로그래머에게 가시적이지 않은 각각의 그룹에 대해, 상기 바이트 순서의 변경이 성능 이득을 제공하는 지를 결정하고 만일 그렇다면 대응 그룹의 바이트 순서를 변경해서 변경된 그룹을 획득하고, 본 시스템의 제1 기억 매체에 상기 변경된 그룹들 각각을 저장하도록, 컴파일러를 실행시킴 - ; 및
상기 코드의 각각의 포인터에 대한 소스 리스트, 행선지 리스트, 및 액세스 리스트를 저장하는 기억 장치
를 포함하는 시스템.
제15항에 있어서,
상기 컴파일러는, 제1 포인터가 제2 포인터에 대한 소스일 때 상기 제1 포인터의 행선지 리스트를 갱신하고, 다른 포인터가 상기 제1 포인터에 대한 소스일 때 상기 제1 포인터의 소스 리스트를 갱신하며, 제3 포인터와 연관된 메모리 액세스가 발생될 때 액세스의 크기로 상기 제3 포인터의 액세스 리스트를 갱신하는 시스템.
제16항에 있어서,
상기 기억 장치는 표현에 대한 바이트 순서 변경으로 인한 성능 이득의 영향을 기반으로 갱신 가능한 이득 카운터를 더 포함하는 시스템.
제15항에 있어서,
상기 컴파일러는, 바이트 교환 연산을 식별하고, 상기 바이트 교환 연산 및 교환을 허용하는 다른 표현들을 포함하는 도메인을 생성하며, 상기 도메인과 연관된 도메인 엔트리들 및 도메인 엑시트들을 식별하고, 상기 도메인의 교환을 실행함으로써 성능 이득이 제공될 것이라고 결정하는 시스템.
제18항에 있어서,
상기 컴파일러는, 상기 결정에 응답해서, 상기 도메인의 교환을 실행하고, 상기 제1 기억 매체에 상기 교환된 도메인을 저장하는 시스템.