E D R , A S I H C RSS
ZeroWiki

Optimize Compile

Basic of Compiler Optimization


Topology

ν˜„μž¬ ν”„λ‘œμ„Έμ„œμ˜ μ†λ„λŠ” λ¬΄μ–΄μ˜ 법칙에 따라 κ·Ήν•œμœΌλ‘œ 속도가 μ¦κ°€ν•˜κ³  μžˆλ‹€. μ΄λŸ¬ν•œ μƒν™©μ—μ„œλŠ” μ˜ˆμ „μ²˜λŸΌ CPU 의 속도 에 ν”„λ‘œκ·Έλž¨μ˜ 싀행속도가 크게 영ν–₯ λ°›μ§€λŠ” μ•ŠμœΌλ―€λ‘œ, 컴파일러의 μ΅œμ ν™” μž‘μ—…λ„ 더이상 μ—°μ‚°(computation)을 μ€„μ΄λŠ” 것 만이 λͺ©μ μ΄ λ˜λŠ” 것이 μ•„λ‹ˆλΌ, μ’€ 더 λ©”λͺ¨λ¦¬ 계측ꡬ쑰λ₯Ό 효율적으둜 μ‚¬μš©ν•˜λŠ” 것에 관심이 κΈ°μšΈμ—¬μ§€κ²Œ λœλ‹€.


Local optimization κ³Ό Global optimization.

ν”„λ‘œκ·Έλž¨(translation unit)은 진행방ν–₯이 뢄기에 μ˜ν•΄ λ³€ν•˜μ§€ μ•ŠλŠ” λΆ€λΆ„μ˜ 집합인 basic block λ“€λ‘œ λ‚˜λˆŒ 수 μžˆλŠ”λ° 이 각각의 block 에 λŒ€ν•˜μ—¬ μ΅œμ ν™” ν•˜λŠ” 것을 local optimization 이라 ν•˜κ³ , λ‘˜ μ΄μƒμ˜ block 에 λŒ€ν•˜μ—¬, ν˜Ήμ€ ν”„λ‘œκ·Έλž¨ 전체λ₯Ό μ΄κ΄„ν•˜λŠ” 뢀뢄에 λŒ€ν•˜μ—¬ μ΅œμ ν™” ν•˜λŠ” 것을 global optimization 이라고 ν•œλ‹€.

λͺ¨λ“  μ΅œμ ν™” μž‘μ—…μ€ μ‹œκ°„ νš¨μœ¨μ— λŒ€ν•˜μ—¬, ν˜Ήμ€ 곡간 νš¨μœ¨μ— λŒ€ν•˜μ—¬ μ΅œμ ν™”λ₯Ό ν•˜κ²Œ λ˜λŠ”λ°, λ°‘μ˜ 각 μ„Ήμ…˜μ— 따라 뢄리 ν•  수 μžˆλ‹€. 이 μž‘μ—…λ“€μ€ μ„œλ‘œ μƒν˜Έ λ³΄μ™„μ μœΌλ‘œ μ΄λ£¨μ–΄μ§€κ±°λ‚˜ ν˜Ήμ€ μƒν˜Έ 배제적으둜 이루어 질 수 μžˆλ‹€. (e.g. latency λ₯Ό 쀄일 경우 μ½”λ“œ 길이가 κΈΈμ–΄μ§€κ±°λ‚˜ λ³΅μž‘λ„κ°€ 증가할 수 μžˆλ‹€.)

Reduction of computation

μ‹€ν–‰ μ‹œκ°„(run time) μ€‘μ˜ 계산을 μ€„μ΄λŠ” 것이 λͺ©μ μ΄λ‹€. 이 μ΅œμ ν™”λŠ” '미리 컴파일 μ‹œκ°„μ— 계산(precomputaion in compile time)' ν•  수 μžˆκ±°λ‚˜, '미리 κ³„μ‚°λœ 값을 μž¬μ‚¬μš©(reuse a previously computated value)' ν•  수 μžˆλŠ” μƒν™©μ—μ„œ μ μš©λœλ‹€.

Constant propagation

λ³€μˆ˜κ°€ 값을 ν• λ‹Ή λ°›μ•„μ„œ, λ‹€μ‹œ μƒˆλ‘œμš΄ κ°’μœΌλ‘œ ν• λ‹Ή λ°›κΈ° μ „κΉŒμ§€, κ·Έ λ³€μˆ˜λŠ” μΌμ’…μ˜ constant 라고 λ³Ό 수 μžˆλ‹€. μ»΄νŒŒμΌλŸ¬λŠ” 이λ₯Ό κ°μ§€ν•΄μ„œ μ΅œμ ν™”λ₯Ό μˆ˜ν–‰ν•˜κ²Œ λœλ‹€.
PI = 3.14159;
...
area = 2 * PI * radius;
μœ„μ™€ 같은 λΆ€λΆ„μ—μ„œ, PI 의 값이 쀑간에 λ³€κ²½λ˜μ§€ μ•ŠλŠ”λ‹€λ©΄, μœ„μ˜ μ½”λ“œλŠ”
PI = 3.14159;
...
area = 2 * 3.14159 * radius;
와 같이 λ°”λ€” 수 μžˆλ‹€.

Constant folding

μ—°μ‚°μ—μ„œ λ‘κ°œ μ΄μƒμ˜ constant 듀은, 미리 κ³„μ‚°λ˜μ–΄ ν•˜λ‚˜μ˜ constant κ°’μœΌλ‘œ λ°”κΏ€ 수 μžˆλ‹€. μœ„μ˜ μ˜ˆμ— μ μš©ν•˜μžλ©΄
PI = 3.14159;
...
area = 6.28318 * radius;
κ°€ λœλ‹€.

μ»΄νŒŒμΌλŸ¬λŠ” constant propagation κ³Ό constant folding 을 λ°˜λ³΅ν•˜μ—¬ μˆ˜ν–‰ν•œλ‹€. 각각 μ„œλ‘œμ˜ κ°€λŠ₯성을 λ§Œλ“€μ–΄ 쀄 수 μžˆμœΌλ―€λ‘œ, 더이상 진행 ν•  수 없을 λ•ŒκΉŒμ§€ μ§„ν–‰ν•œλ‹€.

Copy propagation


Common subexpression elimination
a = x + y;
b = x + y;

temp = x + y;

a = temp;

b = temp;
Partial redundancy analysis

Removing loop invariant code

Reduction of space consumption


Reduction of code size


Reduction of complexity

Strength reduction

컴퓨터가 ν•  수 μžˆλŠ” μ—°μ‚° 듀은 각각 κ·Έ 연산이 μˆ˜ν–‰λ˜λŠ”λ° κ±Έλ¦¬λŠ” μ‹œκ°„μ˜ 차이가 μžˆλ‹€. 연산에 λ³΅μž‘λ„μ— μ˜ν•΄μ„œ μ΄λ£¨μ–΄μ§€λŠ” ν˜„μƒμΈλ°, 극단적인 예λ₯Ό λ“€μžλ©΄, shift 연산은 보톡 2 ν΄λŸ­μ— μ²˜λ¦¬λ˜λŠ” λ°˜λ©΄μ—, λ‚˜λˆ„κΈ° μ—°μ‚°μ˜ 경우 80-90 ν΄λŸ­μ„ μ†Œλͺ¨ν•˜κ²Œ λœλ‹€.(i8088자료) 이런 연산에 λŒ€ν•œ computation time 의 차이λ₯Ό μ€„μ΄λŠ” μ΅œμ ν™” 방법을 strength reduction 이라고 ν•œλ‹€.

x = y / 6

와 같은 λ¬Έμž₯이 μžˆμ„λ•Œ, λ‚˜λˆ„κΈ° 연산은 κ³±ν•˜κΈ° 연산보닀 쒀더 λ§Žμ€ μ‹œκ°„μ„ μ†Œμš”ν•˜λ―€λ‘œ μ»΄νŒŒμΌλŸ¬λŠ”

x = y * (1 / 6)

으둜 λ°”κΏ€ 수 μžˆλ‹€.


λ°°μ—΄μ˜ μ°Έμ‘° μ—°μ‚° λ˜ν•œ 쒋은 μ˜ˆκ°€ 될 수 μžˆλ‹€. ai 와 같은 ν‘œν˜„μ‹μ—μ„œ ai의 μ£Όμ†ŒλŠ” λ°°μ—΄ a 의 μ‹œμž‘μ£Όμ†Œλ‘œλΆ€ν„° a의 νƒ€μž… 크기 * i 만큼 떨어진 곳이 λœλ‹€.
~cpp 
double a[ARRSIZE], b[ARRSIZE];
for (i = 0; i < ARRSIZE; i++)
    a[i] = b[i];
와 같은 μ½”λ“œμ—μ„œ ai 의 μ£Όμ†ŒλŠ” 루프가 진행됨에 따라 계속 evaluate λœλ‹€. 그럼 a + (i * 8) 이 맀번 반볡되게 λœλ‹€. μ΄λŸ¬ν•œ 연산은 λ‹¨μˆœνžˆ 루프가 μ§„ν–‰λ˜λ©° a 의 μ£Όμ†Œμ— 8 씩을 λ”ν•΄μ£ΌλŠ” κ²ƒμœΌλ‘œ 해결될 수 μžˆλ‹€.

Algebraic simplification

μˆ˜ν•™μ μœΌλ‘œ 같은 값을 κ°€μ§€λŠ” 수둜 λŒ€μΉ˜ν•˜λŠ” 것이 λ°”λ‘œ algebraic simplification 이닀.

e.g.
Expression Equivalent expression
x + 0 x
x * 0 0
x * 1 x
x^2 x * x
x * 2 x + x
x / 1 x

Reduction of latency

cpu architecture μ°¨μ›μ—μ„œ μ§€μ›ν•œλ‹€.

e.g. instruction prefetching, branch prediction, out-of-order execution

Distribution of work

μ—­μ‹œ.. cpu μ°¨μ›μ—μ„œ...

e.g. pipelining, superscalar

More advanced mothodology of compiler optimization

coming soon.

Valid XHTML 1.0! Valid CSS! powered by MoniWiki
last modified 2021-02-07 05:23:56
Processing time 0.0651 sec