선택한 단어 수는 입니다.
최소 단어 이상 선택하여야 합니다.
최소 단어 이상 선택하여야 합니다.
선택한 단어 수는 30입니다.
최대 10 단어까지만 선택 가능합니다.
최대 10 단어까지만 선택 가능합니다.
문제 정의
- SSA Form으로 변경된 표현식에 대해 최적화를 적용하기 위해 본 논문에서는 부분 중복 표현식 제거 방법을 제안한다. 부분 중복 제거 (partial redundancy elimination)는 Morel 과 Renvoise에 의해 처음으로 제안된 최적화 기술이다[11].
- 또한 현재 블록에서 형태의 표현식이 존재하는가를 확인한다.
제안 방법
- 최적화된 코드로 변환이 요구된다[3]. 최적화된 코드로 변환하기 위해 CTOC(Classes To Optimized Classes) 프레임워크를 구현하였다[4, 5, 6, 7],
- 된다. 이를 해결하기위해 본 논문에서는 임시 변수인 t를 추가하였다. ti는 ti = ai + b2와 같이 표현식을 임시변수에 배정하기 위해 사용한다.
- 본 논문에서는 CTOC의 부분 중복 제거 과정을 서술하기 위해 (그림 2)와 같은 부분 중복이 존재하는 예제 프로그램을 사용한다.
- 바이트코드의 특성 때문에 기존의 제어 흐름 분석 기술을 바이트코드에 적합하게 확장해야 한다. 우선 바이트코드에 라벨 정보를 추가하여 분석을 용이하게 하고 트리 형태의 중간 표현으로 각 문장을 표현하였다. 트리 형태의 변환을 효과적이고 체계적으로 하기 위해 (그림 3)과 같이 [4]의 BNF 코드를 확장하여 사용하였다.
- 우선 바이트코드에 라벨 정보를 추가하여 분석을 용이하게 하고 트리 형태의 중간 표현으로 각 문장을 표현하였다. 트리 형태의 변환을 효과적이고 체계적으로 하기 위해 (그림 3)과 같이 [4]의 BNF 코드를 확장하여 사용하였다. (그림 3)에서 굵게 처리된 부분은 [4]에서 사용한 BNF에 부분 중복 표현식 제거를 수행하기 위해 새롭게 추가된 부분을 나타낸다.
- 이것은 5장에 SSA Form 그래프인 (그림 12)를 통해 확인 가능하다. 기존의 경우에서는 위와 같은 경우 완전히 중복된 경우가 아니기 때문에 중복된 표현식에 대한 제거가 불가능 했지만, 본 논문에서는 분석을 통해 부분적으로 중복된 표현식을 중복이 존재하지 않는 선행 노드에 복사하는 과정을 통해 전체 중복으로 변환하여 부분 중복 표현식을 제거를 수행한다. 즉, 부분 중복된 표현식을 전체 중복으로 만들어 중복 표현 식을 제거하는 것이다.
- 즉, 부분 중복된 표현식을 전체 중복으로 만들어 중복 표현 식을 제거하는 것이다. 이를 위해 본 논문에서는 중복 가능한 표현 식을 임시 변수로 대체하고 부분 중복된 표현식을 복사하여 병합지점의 선행자에 해당 표현식을 이동시켜 완전한 중복 형태로 변형한 후, SSA Form에서 사용된 것과 유사하게 임시 변수들을 병합 지점에서 P-문장에 의해 선택하도록 한다. 이런 과정을 수행하면 SSA Form으로 변환된 표현식에 대해서도 부분 중복을 처리할 수 있게 된다.
- 표현식에 대한 재명명은 SSA Form에서 이름을 설정하기 위해 사용했던 재명명 방법과 유사하게 표현식에 대한 정보를 유지하기 위해 표현식 스택을 이용하여 CFG와 지배자 트리를 방문하면서 수행한다. 표현식 스택의 꼭대기는 표현식에 대한 정보를 유지한다.
- 완전한 중복으로 만들기 위해서 표현식을 발견한 후 이를 작업리스트에 유지하고, 표현식의 정보를 유지하기 위한 표현식 스택을 이용하여 각 표현식에 대한 정의를 지정하였다, 제어 흐름의 병합 지점에서 선행자 블록을 찾아 마지막 문장 바로 앞에 부분 중복된 표현식을 추가하여 완전한 중복 형태를 만들었다.
- 따라서 빠른 실행 속도와 프로그램의 이해를 높이기 위해서는 최적화와 프로그램 분석이 요구되고 있다. 이를 위해 CTOC(Classes To Optimized Classes)를 구현하였다. CTOC에서는 바이트코드의 분석과 최적화를 위해가장 먼저 제어 흐름 분석을 수행하였다.
- 따라서 표현식에 대한 최적화를 적용하기에는 기존의 형태는 조금 어색하다는 단점이 발생하였다. 이를 위해 부분 중복 제거 방법이 제안하고 구현하였다. 부분 중복 제거는 기존의 전역 부분 표현식 제거와 루프 불변 코드 이동 기술을 결합된 기술로 데이터플로우 분석을 통해 프로그램에의 부분 중복을 제거하는 것이다.
- CTOC에서 표현식은 변수처럼 정의되지 않기 때문에 본 논문에서는 임시 변수를 추가하였다. 임시변수 ti은 ti — & + bi 와 같이 표현식이 변수에 배정되는 것을 나타내도록 하였다.
- 임시변수 ti은 ti — & + bi 와 같이 표현식이 변수에 배정되는 것을 나타내도록 하였다. 그리고 표현식이 제어 흐름의 병합 지점에 도달할 때, 임시 변수를 위한 P-문장을 추가하여 병합하였다. 이는 부분 중복된 표현 식을 완전한 중복으로 바꾸어 일반적인 부분 표현식 제거 문제로 변형하여 처리하도록 하였다.
대상 데이터
- 실험은 펜티엄 4 2.4GHz, 메모리 512MB를 가진 PC에서 수행하였으며, 사용한 소프트웨어는 CTOC 작성과 테스트를 위해 ecHpse 3.2을 사용하였고, 바이트코드 출력을 위해 editplus 2.11 버전을 사용하였다. 자바 컴파일러는 jdkl.
이론/모형
- 따라서 정적으로 값과 타입을 결정하기 위해 변수를 배정에 따라 분리하였다. 이를 위해 CTOC에서는 SSA Form을 사용하였다[5]. (그림 4)는 SSA Form에 의해 。-함수가 추가된 CFG를 보여준다.
- 0_09를 사용하였다. 또한 CFG와 SSA Form 변환 결과 확인을 위해 오픈 소스인 Graphviz를 사용하였다[21]. CTOC> 통해 필요한 정보를 .
- CTOC에서는 바이트코드의 분석과 최적화를 위해가장 먼저 제어 흐름 분석을 수행하였다. 정적으로 값과 타입을 결정하기 위해서는 변수를 배정되는 것에 따라 분리해야 하는데 이를 위해 CTOC에서는 정의-사용 체인 대신 SSA Form을 사용하였다. SSA Form은 최근 데이터 흐름 분석이나 코드 최적화를 위해 컴파일러의 중간 표현으로 많이 사용되고 있다.
- 왜냐하면 동일한 변수라도 정의와 사용에 따라 다른 위치에서 다른 값과 다른 타입을 가질 수 있기 때문이다. CTOC에서는 정의-사용 고리 대신 SSA Form(Static Sin이e Assignment FormX 사용하였다[5].
- <표 1>에서 TestPRE는 본 프로그램에서 사용된 예제이고 나머지 예제들은 Don Lance의 논문에 있는 예제 소스를 사용하였다 [22].
성능/효과
- 테스트 과정에서 병합지점에 표현식 선택을 위한 P-문장의 추가로 부분 중복 표현식 제거 과정에서 노드의 수가 늘어나는 경우도 존재하지만 이 후 상수 전파, 복사 전파 그리고 죽은 코드 제거 과정을 통해 더 효율적인 코드가 생성되는 것을 확인할 수 있다.
- 다음 두 가지 경우엔 반드시 P- 문장이 삽입해야 한다. 첫째, P-문장은 표현식이 존재하는 블록에 대한 반복적 지배자 경계가 되는 블록에 삽입된다. 둘째, P-문장은 반드시 표현식에 있는 변수들 중 하나를 위해 0-함수를 포함하는 블록에 삽입한다.
- 첫째, P-문장은 표현식이 존재하는 블록에 대한 반복적 지배자 경계가 되는 블록에 삽입된다. 둘째, P-문장은 반드시 표현식에 있는 변수들 중 하나를 위해 0-함수를 포함하는 블록에 삽입한다. 즉, 기존 CFG에서 。-함수가 존재하는 블록에 P-문장을 삽입하는 것이다.
- 완전한 중복으로 만들어야 한다. <BL_15>에 P- 문장이 존재하는 경우, 현재 블록의 선행자를 방문하여 선행자 블록에 기존의 피연산자 정보가 존재하는가를 확인하였다. <BL_15>의 P-문장이 PHI(1, UD)인 상태이기 때문에 선행 블록 <BL_12>에 피연산자에 대한 정보가 존재하지 않은 상태이다.
- 의 결과에서 프로그램에서 사용되는 에 따라 이 발생하는 것을 확인 할 수 있었으며, 또한 P-문장 수는 기존의 SSA Form 변환 과정에서 추가된 P-문장과 부분 중복 제거 과정에서 생성된 P-문장을 모두 합친 것이다.
- 실험을 통해 현재 작성된 부분 중복 표현식 제거 수행 후 생성된 노드에 복사 전파, 상수 전파, VN, 그리고 죽은 코드 제거하기 과정을 통해 좀 더 최적화된 코드를 생성할 수 있었다. 또한 추후 연구에서는 이익과 비용의 문제를 적용하여 성능 평가를 수행할 계획이다.
후속연구
- 또한 추후 연구에서는 이익과 비용의 문제를 적용하여 성능 평가를 수행할 계획이다.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.