Interprocedural Analysis & Alias Analysis (Pointer Analysis) (작성중)
Interpocedural Analysis
f(x)를 저렇게 선언하는 대신, main에서 y=x*42를 한다음 f(x) 대신에 y를 넣으면 더 낫지 않을까?
Open vs Closed world
-> 이 둘을 구분하는 것은 볼 수 있는 코드의 영역 차이이다.
- open world assumption: 다른 숨겨진 코드들이 있다고 가정
- closed world assumption:모든 코드를 볼 수 있음
위 그림에서 closed world assumption 상황이라면 h를 지워도 된다. 왜냐하면 아무도 h를 calling하지 않으니까! 하지만 open world의 경우 i처럼 다른 함수가 h를 부르고 있을 수도 있으므로 h를 지우면 안 된다.
Why open world assumption?
- modularity : 여러 c 파일을 separte compile하고 linking하는 걸 생각해보면 될듯
- speed: subset만 하면 좀더 빠를 수 있음
Inlining
위 그림처럼 함수에서 다른 함수를 호출하는 경우를 보자. inlinling의 경우 foo함수 바디 자체를 main에 그대로 copy하는 것이다. (foo 자체를 지우지는 않음. 다른 함수에서 foo를 호출할 수도 있으니까!)
그리고 inline 과정에서는 foo의 parameter, return value 등을 어떻게 처리해야할지 고려해야할 것이다.
또한 foo 내의 변수들이 main에 영향을 끼치지 않도록 해야한다!
inlineing의 cost로는 일단 코드 크기 자체가 늘어나는게 있을것이다. 그리고 이거에 의한 overhead도 있다
한편 benfit으로는 calling 자체의 overhead를 줄여주는게 있다.
일단 근데 inline 자체가 되게 중요한 최적화 기법이라고 한다(?)
g1 call은 i에 영향을 주지만 g2는 i에 영향을 주지 않는다. 따라서 g2를 제거하면 어떨까
이를 원래 global analysis에서는 아래처럼 분석했다.
일단 f가 i를 아마 바꿀 가능성이 있으므로, f를 call하는 g1과 g2 또한 i를 바꿀 가능성이 있다고 보는 것이다.
하지만 위에서 보았듯이 g2는 i의 값을 바꿀 수 없다. 따라서 우리는 다른 분석을 해보기로 한다.
위 질문을 아래처럼 context sensitive하게 바꿀 수 있다
단순히 함수가 i의 값을 바꿀 수 있느냐를 물어보는게 아니라, function A에서 호출된 function B가 i를 바꿀 수 있느냐? 이런식으로 물어보는 것이다. 이는 context자체를 고려하는 분석이므로 context sensitive한 분석이다.
위 그림에서 보듯, g1에서 호출된 f는 i의 값을 바꾸지만, g2에서 호출된 f는 i의 값을 바꿀 수 없으므로 g2를 지워도 무방할 것이다.
이 함수가 항상 true를 반환한다고 보장할 수 없다! 왜냐하면 포인터 b가 포인터 a와 동일한 곳을 가리키는 경우, *a의 값은 'b'가 될 것이기 때문이다.
곧 Alias analysis는 서로 다른 두 개의 포인터가 같은 곳을 가리키는 때는 언제인지 등에 대한 분석을 하는 것이다.
Reference