19) Loop Transformations

데이터 의존성 까지 고려 하는 것이다.

Loop variables

-induction variable

변수에서의 모든 변화가 단지 증가 또는 감소가 constant value로 발생 하는 경우

-Basic induction variable

루프당 딱 1번 변화하는 것을 발한다. 1번 루푸당 1번씩 변화하는것

Primary induction variable

basic induction variable이 loop를 제어하면 그것이 Primary induction variable이 된다.

Derived induction variable

its value is decided with a linear function of the basic induction variable

Induction Variable Substitution

필요 없는 것을 loop에서 제거 해버린다.

Before and after induction-variable substitution of KI in the inner loop

KI를 제거 하자.

Before and after induction-variable substitution of KI in the outer loop

Before and after constant propagation of KI and INC

Loop Merge

Improve locality

Reduce loop overhead

- 첫번쨰 루푸의 생산결과가 다음 루프에서 바로 사용될 질경우, 이 둘을 병합하면, 지역성을 높일 수 있다.

merge의 가능성을 높이는 기법으로는

enablers, bump, extend/reduce, split, reverse 가 있다.

Tools [1] - loop Bump

Loop extend /reduce

Loops and Data Dependence

Dependency Types

3가지 종류의 의존성이 존재함.

S1: A=B+C

S2: D=A+2

S3: A=E+F

- Flow Dependence (true dependence)  S1S2

새로 어사인된 변수가 다음 구문에서 바로 이용될 때

- Anti-dependence  S2  S3

사용되어 지는 변수가 다음 번에 바로 어사인 되어 버릴때

- Output dependence S1 S3

새로 어사인된 변수가 다음번 구문에서 재차 어사인 되었을때

Dependency Types - LOOP

for k < m

= : k번쨰 인터레이션이 그것의 것에 의존 할때

m 이라는것이 k에 의존할때

k가 m에 의존 할떄

Distance Vector

for ( i =3; i<=7; i++)

for(j=6; j >=2; j=j-2)

Z[i,j] = Z[i, j+2] + 1

for( i =0; i<=4; I++)

for(j = 0; j<=2; J++)

i+3, j*-2+6 = Z [i+3, j*-2+8] + 1

Cf. Affine Functions.

어떤 변수들이 i1, i2, i3, i4, i5, i6 이러하 연속 성을 가지고,

1) 상수 들의 합

2) 변수 곱하기 상수 한 것들의 합

Formal Definition of Loop-Carriedness 의존성 문제

▣GCD = 최대공약수

루프 간의 의존성으 공약수로 나눠지 냐 안 나눠지냐로 알 수 있다.

나눌수 없으면 확실히 의존성이 없는 것이며, 나눌수 있다고해서 의존성이 있는 것은 아니다.

Advanced Compilers Reuse Optimization

Reuse Optimization 

Types of reuse optimization

- vn(value numbering)

- cse(common subexpression elimination)

- pre (partial redundancy elimination)

Value Numbering

Determines that two computations are equivalent and eliminates one of them.

Local Value Numbering

Idea

각각의 변수 표현 상수는 unique number로 어사인 된다.

변수, 표현 상수 들이 어떤 숫자로 이미 지정되어져 있었다면,

그것들을 그 상수로 사용한다.

그렇지 않다면 그것을 새로운 숫자로 사용한다.

같은 number는 같은 변수이다.

Loca의 경우는 별다른 어려움 없이 된다.

Global Value Numbering

두가지 기법이 있다.

Pessimistic

어떤 변수도 일치하지 않는다로 가정 한다.

지속적을 일치하는 것을 합쳐 나간다.

Optimistic (Slower but better results)

확실히 다른것이 아니면 모두 같다고 생각한다.

Pessimistic Global Value Numbering

Comparisons 

Constant propagation 또는 ( partial)  redundancy elimination은 두개의 expression이 동일하다면,그것이 constant인지 아닌지 결정 할 수 없다.

read a 이런게 있으면 불가능 하다.

Constant propagation은 b와 d가 7이라는 것을 알수 있다.

하지만 value numbering은 알 수 없다.

Use-Def Analysis and SSA (Static Single Assignment)

Use-Definition chains (ud chains)

Each use of a variable is linked to all assginments that reach it

Definition-Use chains (du chains)

Each assignment to a variable is linked to all uses of it

SSA (Static Single Assignment Form)

UD를 좀더 축약한 것이다.

DataFlow Analysis

대표적인 알고리즘 3개를 설명한다.

Live Variables Analysis 

정의: 현재 변수 값이 다른곳에서 사용될 것인지를 알아보는 것

아래와 같은 데이터를 모아야 함.

USE: 변수가 외부에서 사용되는 것을 말한다, 하나의 베이직 블럭에서

DEF: 하나의 베이직 블럭에서 정의되는것을 말함.

IN: 시작 포인트에서의 변수들이 살아 있는지를 말한다.

OUT: 변수들이 살아 있는지를 말한다.

Reaching Definition Analysis 

정의: 어떤 변수의 정의가 특정 위치까지 도달 하는지를 분석함. 

이것의 개념은 최적화 뿐만아니라, 각종 분석에 많이 사용되는 개념임.

요약: 

Forward 방식

Inner Analysis

GEN - 해당 BB에서 생성되는 정의들의 집합

KILL - 모든 BB에서 해당 GEN에 의해서 사라지는 정의들의 집합

Outer Analysis

IN - 모든 이전의 OUT들을 더함

OUT - GEN + ( IN - KILL )

Available Expressions 

정의: 이미 계산된 expression을 재사용 하자.

E_GEN의 생성은 G + (E_GEN(X) - K) 이다.