Loading [MathJax]/extensions/MathZoom.js

LLVM 8.0.0 소스코드를 빌드해서 설치하는 방법


설치 방법은 크게 세 가지로

  • apt로 설치 (ubuntu 기준)
  • pre-buit 버전으로 다운 받기
  • 소스코드 다운후 설치

위 방법중 세 번째 방법으로 직접 소스코드를 다운받아서 설치하는 방법을 다룬다.
추후에 LLVM-cookbook 책에서 나오는 예제들을 실행 하기위해서 여타 LLVM 코드들이 필요 할 수도 있기 때문이다.

소스코드 다운후 빌드해서 설치하는 방법

소스코드를 http://releases.llvm.org/download.html#8.0.0 에서 8.0.0을 기준으로 다운 받았다.

다운로드 파일 2개

  • LLVM source code
  • Clang source code

압축해제 및 이름변경 구조화

tar xf llvm-8.0.0.src.tar.xz
tar xf cfe.8.0.0.src.tar.xz
mv llvm-8.0.0.src llvm # 반드시 이름을 llvm으로 한다.

# move to llvm/tools directory
mv cfe-8.0.0.src clang
mv clang ./llvm/tools/

# llvm 디렉터리 밖에서 llvm-objects 디렉터리 생성
mkdir llvm-objects
cmake ../llvm && make -j4 # i7 기준으로 15분정도 빌드 시간을 소모한다.

cmake -DCMAKE_INSTALL_PREFIX=../llvm-install/ -P cmake_install.cmake # 1분 내외로 빌드 성공

환경변수 설정

export LLVM_BASE_DIR=/home/jemin/development/llvm/
export LLVM_DIR=${LLVM_BASE_DIR}
export LLVM_SRC=${LLVM_BASE_DIR}/llvm
export LLVM_SRC_ROOT=${LLVM_BASE_DIR}/llvm
export LLVM_ROOT=${LLVM_BASE_DIR}/llvm
export LLVM_OBJ=${LLVM_BASE_DIR}/llvm-objects
export LLVM_OBJ_DIR=${LLVM_BASE_DIR}/llvm-objects
export LLVM_OBJ_ROOT=${LLVM_BASE_DIR}/llvm-objects
export LLVM_INSTALL_DIR=${LLVM_BASE_DIR}/llvm-install
export PATH=$LLVM_INSTALL_DIR/bin:$PATH

8.0.0 기준으로 작성된 예제들

https://github.com/leejaymin/llvm8-tutorials-jemin

기타 정보

sudo apt install llvm-8 llvm-8-dev
위 명령어로 설치 할 때 경로

  • /usr/lib/llvm-8

'Computer Science > 고급 컴파일러' 카테고리의 다른 글

19) Loop Transformations  (0) 2014.12.10
18) Loops and Data Dependence  (0) 2014.12.10
Advanced Compilers Reuse Optimization  (0) 2014.12.03
Use-Def Analysis and SSA (Static Single Assignment)  (0) 2014.11.20
Dataflow Analysis  (0) 2014.11.13

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

INC = 2

KI = 0

Do I = 1, 100

DO J = 1, 100

KI = KI + INC

U(KI) = U(KI) + W(J)

ENDDO

S(I) = U(KI)

ENDDO



KI를 제거 하자.


U(KI + INC * J) = U(KI + INC * J) + W(J)

ENDDO

KI  = KI + 100 * INC



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

INC = 2

KI = 0

Do I = 1, 100

DO J = 1, 100

U(KI + INC * J) = U(KI + INC * J) + W(J)

ENDDO

KI  = KI + 100 * INC

S(I) = U(KI)

ENDDO



INC = 2

KI = 0

Do I = 1, 100

DO J = 1, 100

U(KI + 100 * (I-1) * INC + INC * J) = U(KI + 100 * (I-1)  * INC INC * J) + W(J)

ENDDO

S(I) = U(KI + 100* I * INC)

ENDDO

KI  = KI + 100 * 100* INC



Before and after constant propagation of KI and INC


INC = 2

KI = 0

Do I = 1, 100

DO J = 1, 100

U(KI + 100 * (I-1) * INC + INC * J) = U(KI + 100 * (I-1)  * INC INC * J) + W(J)

ENDDO

S(I) = U(KI + 100* I * INC)

ENDDO

KI  = KI + 100 * 100* INC



INC = 2

KI = 0

Do I = 1, 100

DO J = 1, 100

U(200 * I - 200 + J * 2) = U(200 * I - 200 + J * 2) + W(J)

ENDDO

S(I) = U(200 * I)

ENDDO

KI  = 20000



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



Normalization Examples

The iteration space can be normalized

The normalization distorts dependences, but is is otherwise preferred to support loop analysis
How to make
Make lower bound 1 (or 0)
Make stride 1
In general,
i' = (i - lowerBound) / I(step)

for (i = 2; i <=100; i = i+3)
Z[i] = 0;
= 100 -2 / 3 = 32

for(i=0; i<=32; i = i++)

Z[ i*3+2  ] =0 



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 

Idea
중복되는 것을 제거 하자.
How do redundancies arise ?


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



Limitations of Pessimistic Approach

Considers operands before variables that depend upon it
Can't deal with code containing loops !
-> Ignore back edges or make conservative (worst case) assumption for previously unseen variables

Loop 에서 결국 문제가 발생한다.
후방 edge에 대한 고려를 전혀 하지 않게 되는 현상이 발생 한다. 이것이 문제다.



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를 좀더 축약한 것이다.

Definition: each assignment to a variable is given a unique name

All of the uses reached by that assignment are renamed


Easy for straight-line code


What about control flow? ==> X nodes



Dominator


만약 어떤 노드 x가 Entry에서 y까지 가는 모든 path에 의해서 반드시 호출 되어지는 것이라면


그것을 우리는 y의 dominator x라고 부른다.



" x dominates y " means  

x is always executed before y is executed 


▶ 특성

- 모든 노들은 그것 스스로 dominate 하다.

- 만약, x가 y를  dominate하고, y가 z를 dominate 한다면, x는 z를 dominate 한다.

(transitivity 성질을 만족함)

- x y 둘다 z를 dominate 한다면, 


Strictly dominating

x가 y의 strictly dominator 라고 한다면, x는 y를 domiante 한다 하지만 x는 y가 아니라는 것이다.




Dominance Frontiers

X 는 Y의 predecessor들중 한개를 dominate한다. 하지만, x는 y를 strictly dominate 하지 않아야 한다.]

그냥 dominate라고 보면, 자기 자신도 포함대므로, x=y를 허용하게 된다. 그러면 정의가 꼬인다.



DF(2) = {6} 이다.


풀어서 써보면,

2에 대한 Dominance Frontier를 구하는 것이다.

2는 2,3,4,5들을 dominate 한다.















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) 이다.













+ Recent posts