OptimizeCompile - Revision history

Maintenance script: Repair batch-0003 pages from live compare

2026-03-27T00:29:03Z

Repair batch-0003 pages from live compare

← Older revision		Revision as of 00:29, 27 March 2026
Line 2:		Line 2:

	==== Topology ====		==== Topology ====
	현재 프로세서의 속도는 [[무어의 ~~법칙]]에~~ 따라 극한으로 속도가 증가하고 있다. 이러한 상황에서는 예전처럼 [[CPU]] 의 속도 에 프로그램의 실행속도가 크게 영향 받지는 않으므로, 컴파일러의 최적화 작업도 더이상 연산(computation)을 줄이는 것 만이 목적이 되는 것이 아니라, 좀 더 메모리 계층구조를 효율적으로 사용하는 것에 관심이 기울여지게 된다.		현재 프로세서의 속도는 무어의 법칙에 따라 극한으로 속도가 증가하고 있다. 이러한 상황에서는 예전처럼 CPU 의 속도 에 프로그램의 실행속도가 크게 영향 받지는 않으므로, 컴파일러의 최적화 작업도 더이상 연산(computation)을 줄이는 것 만이 목적이 되는 것이 아니라, 좀 더 메모리 계층구조를 효율적으로 사용하는 것에 관심이 기울여지게 된다.


Line 69:		Line 69:

	배열의 참조 연산 또한 좋은 예가 될 수 있다. a[i] 와 같은 표현식에서 a[i]의 주소는 배열 a 의 시작주소로부터 a의 타입 크기 * i 만큼 떨어진 곳이 된다.		배열의 참조 연산 또한 좋은 예가 될 수 있다. a[i] 와 같은 표현식에서 a[i]의 주소는 배열 a 의 시작주소로부터 a의 타입 크기 * i 만큼 떨어진 곳이 된다.
	double a[ARRSIZE], b[ARRSIZE];		double a[ARRSIZE], b[ARRSIZE];
	for (i = 0; i < ARRSIZE; i++)		for (i = 0; i < ARRSIZE; i++)
	a[i] = b[i];		a[i] = b[i];
	와 같은 코드에서 a[i] 의 주소는 루프가 진행됨에 따라 계속 evaluate 된다. 그럼 a + (i * 8) 이 매번 반복되게 된다. 이러한 연산은 단순히 루프가 진행되며 a 의 주소에 8 씩을 더해주는 것으로 해결될 수 있다.		와 같은 코드에서 a[i] 의 주소는 루프가 진행됨에 따라 계속 evaluate 된다. 그럼 a + (i * 8) 이 매번 반복되게 된다. 이러한 연산은 단순히 루프가 진행되며 a 의 주소에 8 씩을 더해주는 것으로 해결될 수 있다.

Line 118:		Line 118:
	----		----
	see also [[zennith/MemoryHierarchy]]		see also [[zennith/MemoryHierarchy]]

imported>qa22ahj at 16:41, 14 November 2013

2013-11-14T16:41:12Z

← Older revision		Revision as of 16:41, 14 November 2013
Line 42:		Line 42:
	a = x + y;		a = x + y;
	b = x + y;		b = x + y;
	~~{{{~~		temp = x + y;
	temp = x + y;
			a = temp;
	a = temp;
			b = temp;
	b = temp;		''' Partial redundancy analysis'''

	~~}}}~~''' Partial redundancy analysis'''

	'''Removing loop invariant code'''		'''Removing loop invariant code'''

imported>qa22ahj at 16:40, 14 November 2013

2013-11-14T16:40:49Z

← Older revision		Revision as of 16:40, 14 November 2013
Line 14:		Line 14:
	실행 시간(run time) 중의 계산을 줄이는 것이 목적이다. 이 최적화는 '미리 컴파일 시간에 계산(precomputaion in compile time)' 할 수 있거나, '미리 계산된 값을 재사용(reuse a previously computated value)' 할 수 있는 상황에서 적용된다.		실행 시간(run time) 중의 계산을 줄이는 것이 목적이다. 이 최적화는 '미리 컴파일 시간에 계산(precomputaion in compile time)' 할 수 있거나, '미리 계산된 값을 재사용(reuse a previously computated value)' 할 수 있는 상황에서 적용된다.

	'''Constant propagation'''		'''Constant propagation'''

	변수가 값을 할당 받아서, 다시 새로운 값으로 할당 받기 전까지, 그 변수는 일종의 constant 라고 볼 수 있다. 컴파일러는 이를 감지해서 최적화를 수행하게 된다.		변수가 값을 할당 받아서, 다시 새로운 값으로 할당 받기 전까지, 그 변수는 일종의 constant 라고 볼 수 있다. 컴파일러는 이를 감지해서 최적화를 수행하게 된다.
	PI = 3.14159;		PI = 3.14159;
Line 25:		Line 26:
	와 같이 바뀔 수 있다.		와 같이 바뀔 수 있다.

	'''Constant folding'''		''' Constant folding'''

	연산에서 두개 이상의 constant 들은, 미리 계산되어 하나의 constant 값으로 바꿀 수 있다. 위의 예에 적용하자면		연산에서 두개 이상의 constant 들은, 미리 계산되어 하나의 constant 값으로 바꿀 수 있다. 위의 예에 적용하자면
	PI = 3.14159;		PI = 3.14159;
Line 34:		Line 36:
	컴파일러는 constant propagation 과 constant folding 을 반복하여 수행한다. 각각 서로의 가능성을 만들어 줄 수 있으므로, 더이상 진행 할 수 없을 때까지 진행한다.		컴파일러는 constant propagation 과 constant folding 을 반복하여 수행한다. 각각 서로의 가능성을 만들어 줄 수 있으므로, 더이상 진행 할 수 없을 때까지 진행한다.

	'''Copy propagation'''		''' Copy propagation'''


	'''Common subexpression elimination'''		'''Common subexpression elimination'''
	a = x + y;		a = x + y;
	b = x + y;		b = x + y;
	temp = x + y;		{{{
	a ~~= temp;~~		temp = x + y;
	b = temp;
			a = temp;

	~~'''Partial redundancy analysis'''~~		b = temp;

	'''~~Removing loop invariant code~~'''		}}}''' Partial redundancy analysis'''

			'''Removing loop invariant code'''
	==== Reduction of space consumption ====		==== Reduction of space consumption ====

imported>qa22ahj at 16:38, 14 November 2013

2013-11-14T16:38:38Z

New page

=== 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)

으로 바꿀 수 있다.

배열의 참조 연산 또한 좋은 예가 될 수 있다. a[i] 와 같은 표현식에서 a[i]의 주소는 배열 a 의 시작주소로부터 a의 타입 크기 * i 만큼 떨어진 곳이 된다.
double a[ARRSIZE], b[ARRSIZE];
for (i = 0; i < ARRSIZE; i++)
a[i] = b[i];
와 같은 코드에서 a[i] 의 주소는 루프가 진행됨에 따라 계속 evaluate 된다. 그럼 a + (i * 8) 이 매번 반복되게 된다. 이러한 연산은 단순히 루프가 진행되며 a 의 주소에 8 씩을 더해주는 것으로 해결될 수 있다.

'''Algebraic simplification'''

수학적으로 같은 값을 가지는 수로 대치하는 것이 바로 algebraic simplification 이다.

e.g.
{| class="wikitable"
|-
| 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.

----
see also [[zennith/MemoryHierarchy]]