Anderson Algorithm for Pointer Analysis

CUBIC_SOLVER.txt

===============================================================================
Anderson Algorithm
===============================================================================
0. Basic
C언어에서 pointer 는 다음 세가지의 값을 가진다.

0.1 Example Code
```c
    int main(){
      int *pointerA;
      return 0;
}
```
여기에서 " pointerA " 이라는 literal string 은 곧장 Reference Value 을 가리킨다.
Adnerson Algorithm 에서는 포인터를 분석을 할 때에 Reference Value 으로서
  "pointerA" 와, Right Value 으로 서의 "pointerA" 을 구분한다.
L-Value 으로서의 pointerA 와, 적합한 R-Value 으로서의 pointerA 을 가리킨다.

===============================================================================
1. Anderson Algorithm
Pointer Analysis 에서는 다음 4가지의 Syntax가 나타날 수 있다.

1.1. Anderson Example.
```
    0. A = alloc P
    1. A = &B
    2. A = B
    3. A = *B
    4. *A = B
```

각각 다음과 같이 나타난다.

1.2. Anderson Example.
```
    0. [[P]] = { P }, [[A]] = { [[A]], P }
    1. [[A]] = { [[A]], B }
    2. [[A]] = { [[A]], [[B]]}
    3. [[A]] = { [[A]], [[var1]], [[var2]], [[var3]], ... },
                      and var is element of [[B]]
    4. [[var1]] = { [[var1]], [[pointerB]]},
       [[var2]] = { [[var2]], [[pointerB]] }, 
       [[var3]] = { [[var3]], [[pointerB]] },
       ...
       and var is element of [[A]]
```

===============================================================================
2. Variable and Token
Anderson Algorithm 에서,
Variable을 Pointer Variable. 즉 Value Reference 인 L-Value 이라고 하자.
    즉. Variable A == pts(A) == [[A]] 이다.
Token을 Pointer Value. 즉 실제 값인 R-Value 이라고 하자.
    즉. Token A == location(A) == A == 0x...
    
가장 헷갈리는 부분이 Token이 상수값이 아닌 변수이름일 때 이것이 무척이나 헷갈린다.
하지만 Token에 나타나는 변수이름을 어떠한 상수인 주소값의 Alias이라고 이해 하는
    것이 올바르다.

위의 1.1. Anderson Example 에서 0과 1을 살펴볼 필요가 있다.
Token 의 값이 숫자 상수 값이 될 때에는 오로지 A = alloca P 일 때 뿐이다.
Token 의 값이 문자열이 될 때에는 오로지 A = &B 일 때 뿐이다.

2.1. Token Example
```
    A = 0x0
    A = &B
```

위와 같은 Example 이 있을 때에 아래와 같이 정의할 수 있다.

[[0x0]] = { 0x0 }
[[A]]   = { [[A]], [[0x0]], B }

===============================================================================
3. Critical Variable

2.1 에서의 이해를 바탕으로, 'Critical' 이라는 특별한 이름의 Variable 을 가정할 수
있다. 'Critical' 은 민감한 영역을 가리키고 있다는 가정이다.

[[Critical]] = { Critical }

0x0000 ~ 0x4000 까지의 값을 할당하는 경우에 Critical 이라는 토큰을 추가하는 제약식
을 추가하면 다음과 같이 사용할 수 있다.

3.1. Critical Variable Example
```
    A = 0x123
    B = A
```

[[0x123]] = { 0x123, Critical }
[[A]] = { [[A]], [[0x123]] }