Ghidra P-Code 알아보기 3

Slicing

프로그램 슬라이싱이란 특정 변수를 기준으로 그 변수의 영향 아래에 있거나 변수에 영향을 주는 코드를 전부 찾아내는 기법이다.
슬라이싱은 크게 Forward Slicing과 Backward Slicing으로 구분된다. Forward Slicing은 이 지점의 변수가 앞으로 미래의 어떤 코드들에 영향을 미치는지, Backward Slicing은 이 지점의 변수에 영향을 준 코드들이 뭔지 찾아내는 것을 뜻한다. 컴파일러는 일반적으로 Forward Slicing을 가지고 Const Propagation 최적화를, Backward Slicing을 통해 Dead Code 제거 최적화를 수행할 수 있다.
간단한 예를 들어보자.(여기서는 정적 슬라이싱을 기준으로 한다.)

int w = 1;
int x = 2;
int y = 3;
int z = 4;
if (w > 0) {
    x = x + y;
}
else {
    x = z;
}
y = 5;
int total = x;
printf("%d\n", y);

이런 가상의 C 코드가 있다고 해보자. 위 total이란 변수를 기준으로 Backward 및 Forward Slicing을 수행해보면

먼저 Backward Slicing을 수행하면 저 total에 영향을 준 코드를 남겨두고 그 외의 코드들을 쳐낼 수 있을 것이다.

int w = 1; // if문 조건에 사용되므로 삭제 X
int x = 2; // total 결과값에 영향을 주므로 삭제 X
int y = 3; // if문 내부에서 사용되므로 삭제 X
int z = 4; // if문 내부에서 사용되므로 삭제 X
if (w > 0) { // if 분기 내에서 어떤 x를 실행할지 결정하므로 삭제 X
    x = x + y;
}
else {
    x = z;
}
// y = 5; 삭제
int total = x; // 여기가 기준!
// printf문은 total 이후에 사용되는 무관한 코드이므로 식제

이렇게 제거해볼 수 있을 것이다.

이번엔 Forward Slicing을 수행해보자. 이번엔 3번 줄의 y 변수를 기준으로 해서 이 값이 미래 어디에 사용되는지 추적한다.

int y = 3; // 기준
if (w > 0) { // if문 안 y값이 x 쪽에 영향을 주므로 삭제 X
    x = x + y;
}
else {
    x = z;
}
// y = 5;는 기존 y를 덮어쓰는 별개 대입이므로 삭제
int total = x; // 여기가 기준!
// printf문은 total 이후에 사용되는 무관한 코드이므로 식제

이렇게 제거해볼 수 있을 것이다.

PDG

PDG는 Program Dependence Graph의 약자로, 프로그램 의존성 그래프를 뜻한다고 한다. 프로그램 내부 코드들이 어떤 의존 관계를 맺고 있는지를 표현한 그래프로, 기존 CFG에 데이터 의존성과 제어 의존성, 이 두 가지 의존성이 추가적으로 들어간다고 한다. 데이터 의존성은 A 코드가 계산한 값을 B 코드가 사용하는 것을, 제어 의존성은 A 조건문의 참 거짓 여부에 따라 B 코드가 실행될지 말지가 결정되는 것을 뜻한다.
다시 한번 간단한 예를 들어보자.

(1) int w = 1;
(2) int x = 2;
(3) int y = 3;
(4) int z = 4;
(5) if (w > 0) {
(6)     x = x + y;
}
else {
(7)     x = z;
}
(8) y = 5;
(9) int total = x;
(10) printf("%d\n", y);

위에서 본 예제 코드고, 편의상 노드 번호를 붙였다. 여기서 먼저 데이터 의존성을 계산해본다면
1번 값을 5번에서 사용
2번 값을 6번에서 사용
3번 값을 6번에서 사용
4번 값을 7번에서 사용
6번 값을 9번에서 사용
7번 값을 9번에서 사용
8번 값을 10번에서 사용
이렇게 정의할 수 있다. 이 때 찾는 방법은 Reaching Definition때 사용했던 GEN-KILL 등을 사용한다고 한다.
다음으로 제어 의존성은
5번 결과가 참이면 6번으로
5번 결과가 거짓이면 7번으로
갈 수 있을 것이다. 제어 의존성은 Dominance 개념을 사용한다고 한다.

Dominance 개념은(이전 사람이 잘 설명해줬겠지만) CFG에서 시작 지점에서 다른 지점까지 가는 모든 경로가 어떤 지점을 지난다면 지배한다고 표현한다. 예를 들어 Entry 지점부터 B까지 가는 모든 경로에 A가 끼어있다면 A는 B를 지배(Dominance)한다 라고 표현한다. 반대로 역지배(Post-Dominance)란 B에서 Exit 지점까지 가는 모든 경로에 A가 끼어있다면 A가 B를 역지배한다고 표현한다.

(5) if (w > 0) {
(6)     x = x + y;
}
else {
(7)     x = z;
}
(8) y = 5;

아까 이 코드를 다시 보자. 8번은 5, 6, 7번을 역지배한다. 6번 7번을 시작하고 나면 8번을 거처야하며, 5번 조건문이 참이듯 거짓이든 결국 갈라졌다 8번에서 만나게 된다. 그리고 이를 기반으로 제어 의존성을 계산하게 된다.
알고리즘은 다음과 같다.

모든 CFG 간선 X -> Y에 대하여:
    Y가 X를 역지배하지 않으면:
    현재 탐색 노드 = Y
    현재 탐색 노드가 X의 역지배자가 아닌 동안:
        제어 의존성 집합 = 제어 의존성 집합 + X -> 현재 탐색 노드
        현재 탐색 노드 = 현재 탐색 노드의 부모 노드

예제 코드로 보자. 먼저 5->6번 화살표를 본다. 6번은 5번을 역지배하지 않으므로 루프를 돈다. 5번의 직속 역지배자는 8번이므로 6과 8이 같은지 확인한 뒤, 아니므로 제어 의존성 집합에 5->6번을 넣는다. 이후 6번의 부모 노드인 8번 노드로 간다(역지배자 트리이므로 거꾸로). 8번의 경우 5번의 직속 역지배자와 같으므로 반복문을 종료한다. 이렇게 하면 이제 5->6번 간선 하나가 끝난거고 이제 5->7번, 6->8번, 7->8번 전부 다 수행해주면 되는 것이다.

그래서 이게 슬라이싱이랑 무슨 관계냐?

PDG를 만들었으면 슬라이싱을 바로 끝낼 수 있는 것이다. Backward Slicing을 통해 Dead Code를 지운다면 관심있는 변수 노드 하나를 찍고 PDG에서 역순으로 올라가며 그래프를 돌리게 되는데, 데이터 의존과 제어 의존이 모두 없는 노드를 전부 쳐내면서 Dead Code를 지울 수 있는 것이다.
반대로 Forward Slicing을 수행할 때 역시 순방향 그래프 탐색을 하고, 데이터 의존 및 제어 의존이 없는 모든 값들을 잘라버릴 수 있다. 상수 전파를 할 때는 데이터 의존성을 보면서 변수를 상수로 바꿔쳐버리고, 이 때 어떤걸 바꿔치기할지 결정을 제어 의존성이 결정해준다.

개발하는 쿼카

Contact

Slicing

PDG

그래서 이게 슬라이싱이랑 무슨 관계냐?