Egloos | Log-in
F/OSS study
F/OSS study
[compiler] Lazy Code Motion (Partial Redundancy Elimination)
partial redundancy elimination (PRE)는 중복된 계산을 없애기 위한 기법이다.
그냥 redundancy가 아니라 partial redundancy라고 쓴 것은
해당 계산식(expression)이 control flow에 따라 중복될 수도 있고 아닐 수도 있다는 것을 말한다.

PRE를 수행하는 방법은 Morel과 Renvoise의 논문에서 발표하였는데
이는 bidirectional data flow analysis(DFA)를 수행하여 복잡할 뿐 아니라
올바로 동작하지 않는 경우를 포함하고 있어서 적절하지 않으므로
ACDI에서 소개한 lazy code motion (LCM)이라는 기법을 살펴보기로 한다.

LCM을 수행하기 전에는 먼저 critical edge를 제거해야 한다.
critical edge는 여러 successor를 가지는 노드와 여러 predecessor를 가지는 노드를 연결하는 edge이다.
여기서는 이미 critical edge를 제거했다고 가정하고 설명할 것이다.

LCM은 원 PRE에서 수행하는 DFA를 여러 과정으로 나누어서 unidirectional DFA로 만든 것이므로
여러 단계를 거치게 되며 수식 만으로 이해하기에는 머리가 복잡해 질 수 있으므로
Knoop, Ruthing, Steffen의 논문에 수록된 그림을 통해 살펴보기로 하자. (스크롤 압박 주의)

먼저 예제로 살펴볼 procedure의 flow graph는 다음과 같다.
(여기서는 a+b라는 expression 만을 살펴볼 것이므로 그와 관계없는 모든 코드는 무시한다.)

위의 graph에서 3, 10, 15, 16, 17번 노드에서 a+b라는 expression이 계산되고 있는 것을 볼 수 있다.
이 중 16번 노드는 8 -> 11 -> 14번 노드를 거쳐 오는 경우가 있으므로 partially redundant하다.
또한 10번 노드는 loop 내에 있으므로 몇 번이고 반복 계산될 수 있다!

이를 간단히 해결하려면 3번 노드야 그렇다 치더라도
이후의 노드들에서 중복 계산되는 식을 5번 노드로 옮기거나
어차피 7 -> 18 path는 고려하지 않아도 되므로 6번 노드로 옮기면 될 것 같다.

사실 이 방법이 PRE의 기본 개념과 같지만
만약 이 algorithm을 실제 컴파일러에 적용한다면
(possibly many) 중복된 계산이 공통 노드에서 수행될 것이므로
(적어도 해당 시점에서는) 불필요한 overhead (register pressure)를 낳게 되고
이는 컴파일러의 성능에 무시할 수 없는 영향을 미치게 된다.

따라서 가능하다면 해당 expression의 값이 정말로 필요해지는 시점까지
최대한 계산을 미루는 것이 좋으며 이것이 바로 LCM의 기본 개념이다.

시작하기 위해 먼저 다음과 같은 두 가지 개념을 정의한다.
(이는 data flow analysis의 flow function에 해당하는 것으로
해당 basic block에서 영향을 받는 모든 expression의 집합(set)을 다루어야 하지만
위의 예제에서는 a+b 하나의 expression에 대해서만 고려하고 있으므로
설명의 편의를 위해 true/false 중의 하나의 값을 갖는 predicate처럼 다룰 것이다.)
  • TRANS (Transparent) : 해당 노드에서 a 혹은 b의 값을 바꾸지 않는다.
  • USED : 해당 노드에서 a+b를 계산한다. (이는 PRE의 locally anticipatable과 비슷한 개념이다.)
이 둘은 각각의 노드의 내용을 보면 바로 알 수 있는 값들이다.
이제 이를 이용하여 다음과 같은 개념을 정의한다.
  • D-SAFE (Down Safe) : USED가 참이거나, 모든 successor들이 D-SAFE하고 TRANS가 참이다. (이는 PRE의 globally anticaipatable과 같은 개념이다.) 다시 말하면 현재 노드에서 a+b를 계산하거나, 해당 노드에서 exit 노드까지 연결된 모든 경로 상에서 a+b를 계산하고 해당 노드에서는 a나 b의 값을 바꾸지 않는다. 이는 backward problem이며 초기값은 exit 노드에서 FALSE이다. D-SAFE의 의미는 a+b의 계산이 해당 노드 혹은 이후의 노드에서 이루어지는데 그 사이에 다른 side-effect가 없으므로 계산을 앞으로 당겨서 현재 노드에서 수행해도 문제가 없다는 뜻이다.
  • EARLIEST : predecessor 중에서 TRANS가 거짓이거나, EARLIEST이지만 D-SAFE하지 않은 것이 있다. 다시 말하면 바로 앞의 노드 중 하나에서 a나 b 값을 바꾸었거나, entry 노드부터 해당 노드 사이의 어떤 노드에서 a+b를 계산하지 않았고 바로 앞의 노드는 D-SAFE하지 않다. 이는 forward problem이며 초기값은 entry 노드에서 TRUE이다. EARLIEST의 의미는 해당 노드에서 a+b를 계산하는 것과 동일한 a+b 계산이 아직 수행되지 않았으므로, 현재 노드에서 계산하면 가장 먼저 계산하는 것이 된다는 뜻이다.
벌써부터 마구 헷갈리기 시작하니 그림을 보기로 하자..

먼저 D-SAFE의 경우를 살펴보면,
D-SAFE는 이후의 모든 경로에서 해당 expression (여기서는 a+b)을 계산해야 하는데
7 -> 18의 경로는 해당하지 않으므로 1 ~ 5번 노드는 D-SAFE하지 않지만
3번 노드의 경우에는 자체적으로 a+b를 계산하고 있으므로 예외이다.
6 ~ 17번 노드는 16번 노드와 17번 노드 중 하나를 거쳐야 하므로 모두 D-SAFE이다.

EARLIEST의 경우는,
해당 노드보다 먼저 해당 expression을 계산하는 것이 없어야 하는데
5번 노드의 경우는 3번에서 이미 계산을 하긴 했지만 4번을 통해서 오는 경로가 있으므로 EARLIEST이다.
따라서 6번 노드도 EARLIEST이지만, (위에서 보듯이) D-SAFE이므로
그 아래의 8번과 9번 노드는 더이상 EARLIEST가 아니고, 그 아래도 마찬가지이다.

그림을 잘 살펴보면 D-SAFE와 EARLIEST를 동시에 만족하는 노드만 찾아도 PRE 문제가 해결될 수 있을 것 같다.
하지만 이는 위에서 말했듯이 computationally optimal한 위치가 아니다.
이를 해결하기 위해 위의 두 개념을 이용하여 다음과 같은 개념을 새로 정의한다.
  • DELAY : D-SAFE하고 EARLIEST이거나, 모든 predecessor들이 DELAY이고 USED가 거짓이다. 다시 말하면 해당 노드가 D-SAFE와 EARLIEST 조건을 만족하거나, 바로 앞의 모든 노드들이 DELAY이고 아직 a+b를 계산하지 않았다. 이는 forward problem이며 초기값은 entry 노드의 D-SAFE 여부에 달렸다.
  • LATEST : DELAY이고, USED이거나 모든 successor들이 DELAY가 아니다. 다시 말하면 연결된 DELAY 노드 중에서 제일 마지막에 있거나 해당 노드에서 a+b를 계산한다.
역시 그림을 살펴보는 것이 이해에 도움이 될 것이다.

DELAY의 경우를 먼저 살펴보면
기본적으로 DELAY가 참이 되려면 D-SAFE하고 EARLIEST여야 한다.
이를 만족하는 것은 더 위의 그림에서 찾아보면 3번과 6번 노드이며, 이는 a+b가 계산되기 전까지 계속 이어진다.
(사실 12, 13번 노드가 DELAY 조건을 만족하는 것에 대해서는 약간 의문이 남아있다.)

LATEST의 경우는 간단하다.
경로 상에서 연결된 DELAY인 노드 중 a+b를 계산했거나,
계산하지 않았더라도 가장 마지막에 있는 노드가 LATEST가 된다.

이제 거의 다 왔다.
LATEST 지점에서 해당 expression을 계산하는 것은 computationally optimal하다!!
마지막으로 LATEST의 경우 중 가려내야 할 것을 찾기 위해 다음과 같은 개념을 새로 정의한다.
  • ISOLATED : 모든 successor들이 LATEST이거나, ISOLATED이고 USED가 거짓이다. 다시 말하면 바로 뒤의 모든 노드들이 LATEST이거나, ISOLATED면서 a+b를 계산하지 않아야 한다. 이는 backward problem이지만, 초기값이 확실치 않다. ACDI에서는 exit 노드에서 FALSE라고 표기되어 있고, (논문에 정확히 나와있지는 않지만) 아래의 그림을 보면 초기값이 TRUE라고 가정하는 것 같다. ISOLATED의 의미는 해당 노드의 바로 다음에서 시작하는 모든 경로에서 a+b의 계산은 LATEST이거나 LATEST보다 뒤에 나온다는 뜻이다.
마찬가지로 그림을 살펴보자.

일단 18번 노드는 ISOLATED가 참이라고 하고,
USED가 거짓이니 그 위의 노드들도 ISOLATED를 만족한다.
17번 노드는 a+b를 계산하고 있지만 그 자체로 LATEST이니 상관없고, (3번 노드도 마찬가지이다)
16번 노드는 a+b를 계산하고 LATEST가 거짓이니 그 위의 노드들은 더이상 ISOLATED를 만족하지 않는다.
단 8번과 15번 노드는 LATEST이므로 그 위로는 다시 ISOLATED를 만족한다.

다른 관점에서 보면
6번 노드의 successor는 8번과 9번인데
8번에서 시작하는 경로는 8번 자체가 LATEST이므로 모든 계산이 LATEST보다 뒤에 나오고
9번에서 시작하는 경로는 15, 16, 17번 노드에서 계산이 이루어지는데
15번과 17번은 자체로 LATEST이고 16번은 15번 뒤에 나오므로
6번 노드는 ISOLATED가 참이 된다.

8번 노드를 보면,
successor는 11번이고 계산은 10번과 16번에서 이루어지는데
11, 10, 14, 16, 18번 노드에서 LATEST 노드가 없으므로
8번 노드는 ISOLATED가 거짓이 된다.

LATEST와 ISOLATED를 구했다면 LCM을 수행할 위치를 찾은 것이다.
LATEST이면서 동시에 ISOLATED인 노드는
그 자체로 최적의 위치이면서 다른 중복된 계산이 없으므로,
그냥 원래와 같이 계산하면 되고 별도로 코드를 이동 (code motion)할 필요가 없다.
LATEST이면서 ISOLATED가 아닌 노드는
계산에 적합한 위치이므로 (필요한 경우) expression을 이 노드로 옮기고 그 결과를 저장하여 이후에 사용한다.

중복된 계산이 일어나는 위치는
USED이면서 LATEST가 아니거나 ISOLATED가 아닌 노드이다.
이러한 노드들은 expression을 계산할 필요없이 위에서 계산한 결과를 바로 사용하면 된다.

최종적으로 LCM이 적용된 형태는 다음 그림과 같다.

3번과 17번 노드는 LATEST이면서 ISOLATED이므로 그냥 둔다.
8번과 15번 노드는 LATEST이면서 ISOLATED가 아니므로 a+b를 계산하여 h에 저장한다.
10번과 16번 노드에서는 h 값을 그냥 사용하면 된다.
by namhyung | 2009/09/02 19:09 | General | 트랙백(1) | 덧글(2)
트랙백 주소 : http://studyfoss.egloos.com/tb/5100842
☞ 내 이글루에 이 글과 관련된 글 쓰기 (트랙백 보내기) [도움말]
Tracked from tomato_house at 2010/02/17 08:50

제목 : Lazy Code Motion (Partial Re..
[compiler] Lazy Code Motion (Partial Redundancy Elimination)...more

Commented by 이상훈 at 2010/10/08 10:43
안녕하세요 ㅎㅎ
오랜만이네요 ^^;

다름이 아니라 지금 글에 보니 그래프 구조가 굉장히 질서 정연하게 그려져 있어서 ...
혹시 저런 것을 자동으로 생성하거나 쉽게 그려줄 수 있는 Tool이 따로 있나요 ?
만약 있다면, 좀 알려주십시오 ^^
Commented by namhyung at 2010/10/11 17:33
이 글에 나온 그래프는 논문의 그림을 무단 도용한 것입니다.. ;;
그래프 자동 생성에 대한 내용은 제 블로그에 소개하기도 했던 graphviz를 찾아보심이 좋을 것 같습니다.

:         :

:

비공개 덧글

◀ 이전 페이지 다음 페이지 ▶

카테고리
General
Application
System
Kernel
Book
Tips
태그
glibc memory git awk documentation binutils script perf patch blktrace C scm vcs CAaQA3 emacs compiler kernel elf sed synchronization bash build x86 gcc block-layer SMP CARM algorithm linux computer-architecture
전체보기
이글루 파인더

최근 등록된 덧글
informsi yang bagus dan be..
by pordanaia at 08/05
Informsi yang bagus dan b..
by jamalsu at 08/01
as inforasi yang menarik http..
by jamalsu at 07/22
최근 등록된 트랙백
Tod's Ferrari Homme
by Tods Pas Cher,Kodak did ..
Mocassin Femme
by Mocassins Homme, I got so..
natural garcinia cambogia
by
rss

skin by jiinny


X