Parameter Passing, Optimization

Parameter Passing

 

Parameter: actual parameter, formal parameter

● 실 매개변수와 형식 매개변수는 서로 값을 주고받는다 (parameter passing)

● 여러 가지 parameter passing 방법이 있음

      ○ 참조 호출(Call by reference): 포트란77

      ○ 값 호출 (Call by value): C

 

예시) a[i] = a[j]

● 산술식 a[j]는 값을 나타내는 r-값(right value)

● a[i]는 a[j]의 값이 있는 메모리의 위치인 l-value(left value, location value)을 나타낸다.

      ○ l-value: 산술식이 나타내는 기억 위치

      ○ r-value: 메모리에 저장될 값

 

 

Call by Value

 

값 호출(call by value)은 매개변수를 전달하는 가장 일반적인 방법

● C, 파스칼, 에이다에서 사용

● Actual parameter와는 별도로 Formal parameter에 대한 메모리를 할당

● Formal parameter는 local 변수처럼 다뤄지고, 호출자는 Formal parameter에 대한 메모리에

      actual parameter의 r-value를 복사하는 방법으로 구현

● Formal parameter에 대한 연산이 호출자 활성 레코드 안의 값에는 아무런 영향을 미치지 않는다

 

 

3행에 있는 var를 없애면 이 프로그램은 값 호출 방법이다.

이 경우, 12행에 있는 swap(a, b)은 a와 b 값을 변화시키지 않는다.

 

● 12행에서 swap(a, b)를 호출하면 actual parameter a와 b는 a:=1, b:=2이 므로 swap(1, 2)가 되고

      3행에 있는 swap 프로시저를 실행한다.

● formal parameter는 x와 y이다.

      따라서 formal parameter에 대한 메모리를 별도로 할당하고 x에는 1을, y에는 2를 할당한다.

● 그런 다음 지역 변수 temp에 대한 메모리를 할당하고 6행을 실행한다.

      temp에는 1, x에는 2가 할당되고, y에는 다시 temp의 값 1이 할당된다.

      따라서 x = 2, y = 1이 할당되어 x와 y의 값이 서로 교환되었다.

● 하지만 제어가 호출자로 반환되고 swap에 대한 활성 레코드가 해체될 때 지역 변수인 x, y, temp에 대한

     메모리를 삭제하기 때문에 호출자의 활성 레코드에는 아무 영향을 주지 못한다.

 

Call by value 프로시저는 non-local 변수나 포인터로 전달되는 값을 통해 호출자에 영향을 줄 수 있다.

또는 호출된 프로그램에서 값을 리턴하는 방법을 선택할 수 있다.

 

 

Call by Reference

 

참조 호출(call by reference, call by address)

● Parameter가 전달될 때 호출자가 피호출자에게 실 매개변수의 메모리에 대한 주소를 가리키는 포인터를 전달한다.

      ○ 포트란 77에서 매개변수 전달 방법은 참조 호출밖에 없다.

      ○ 파스칼에서 참조 호출은 var 키워드의 사용으로 가능

      ○ C++에서는 매개변수 선언 시 특수 기호 &의 사용으로 가능

 

Call by reference는 만약 actual parameter가 l-값을 가지고 있는 산술식이거나 변수라면 그 l-값 자신을 전달한다.

그러나 actual parameter가 b + c나 5와 같이 l-값을 가지지 않는다면 호출자 활성 레코드 내의 새로운 위치의

주소를 전달한다.

 

Example: Call-by-Reference swap(a, b)가 작동하는 과정을 설명해보자.

 

swap(a, b) 호출 시 swap 함수에서 x = &a, y = &b 와 같은 과정을 거친다. (실 매개변수의 메모리에 대한 주소를

가리키는 포인터를 전달)

swap() 함수 내에서 x = 1, y = 2 이고 temp 변수를 통해 x와 y의 스왑이 일어난다.

즉, a = 2, b = 1 이 되며 함수가 종료되도 여전히 a = 2, b = 1 이 된다.

 

 

Call by Name

 

Formal parameter의 name이 사용될 때마다 그에 대응하는 actual parameter 자체가 사용된 것 처럼

매번 다시 계산 및 시행된다.

 

Example) Call-by-Name swap(a, b)가 작동하는 과정을 설명해보자.

 

 

swap(a, b) 함수를 호출하는 순간 x = a, y = b 가 되며 x, y가 스왑되면 결국 x = b, y = a 가 된다.

즉,  a, b에 대한 스왑이 일어났으므로 swap 함수가 끝나면 a = 2, b = 1 가 된다.

 

 

Example

다음과 같은 PL/I 형태의 프로그램에서 call by value, call by reference, call by name 각 경우의 결과 값을

구해보자.

P: PROCEDURE;

     DECLARE A(3), I;

     I=1; A(1)=2; A(2)=4;

    CALL Q(A(I));         => A(I) : actual parameter

Q: PROCEDURE(B) => B : formal parameter

      A(1)=3; I=2; PUT LIST(B);

      END Q;

      END P; 

 

1. call by value

처음에 I = 1, A(1) = 2, A(2) = 4 으로 초기화하고 Q(A(I)) 를 호출한다.

A(I) = 2 가 되므로 B = A(I) = 2 가 되며 LIST(2) 를 출력하고 끝난다.

 

2. call by reference

I = 1, A(1) = 2, A(2) = 4 으로 초기화하고 A(1) 의 포인터는 Q 호출자에게 전달한다.

그러면 B 는 A(1)의 주소를 가르키고 있으며 A(1) = 3 으로 변경되었어므로 PUT LIST(B) 는 3을 호출한다.

 

3. call by Name

B = A(I) 에서 I = 2 로 변경 되었으므로 PUT LIST(B) => PUT LIST(A(I)) => PUT LIST(A(2)) => 4를 출력한다.

 

 

Code Optimization

 

최적화: 주어진 코드에 대해 동등한 의미를 가지면서

● 실행 시간을 줄이거나

● 메모리를 줄이는 것

 

코드 최적화는 프로그램 전체에서 이뤄질 수 있다.

 

 

 

코드 최적화의 분류

● 최적화가 적용되는 프로그램의 영역

      ○ 지역 최적화(local optimization),

      ○ 전역 최적화(global optimization, intra-procedural optimization),

      ○ 프로시저 간 최적화(inter-procedural optimization)

● 기능적인 측면

      ○ 실행 시간 최적화와 메모리 최적화

      ○ 최적화가 많이 이뤄지는 부분

      ○ 루프(혹은 반복문) 최적화와 단일문 최적화

● 목적 기계의 의존성

      ○ 기계 독립적 최적화(machine independent optimization)

      ○ 기계 종속적 최적화(machine dependent optimization)

 

 

Machine Independent Optimization

 

프로그램의 범위에 따라

● 핍홀 최적화(peephole optimization): 일반적으로 목적 코드가 생성된 다음 수행.

      ○ 몇 개의 연속적인 명령어를 하나의 명령어나 더 짧은 명령어로 변환하는 것으로 중복(redundant)

           명령어 제거, 도달 불가능한 코드(unreachable code) 제거, 제어 흐름 최적화(flow of control optimization),

           대수학적 간소화(algebraic simplification), 세기 감축(strength reduction), 하드웨어 명령어 사용(use of

          machine idioms) 등이 있다.

● 지역 최적화: 부분적인 관점에서 좀 더 효율적인 코드로 만드는 방법

      ○ 코드가 분기해 나가거나 분기해 들어오는 부분이 없는 기본 블록(basic block) 내에서 최적화를 수행하기

           때문에 상대적으로 쉽게 수행할 수 있다.

      ○ 기본 블록은 어떠한 제어 흐름도 가지지 않으므로 분석이 거의 필요 없다. 지역 최적화 기법에는 공통

           부분식 제거(common subexpression elimination), 복사 전파(copy propagation), 죽은 코드 제거

           (dead-code elimination), 상수 폴딩(constant folding), 대수학적 간소화 등이 있다.

 

프로그램의 범위에 따라

● 전역 최적화: 하나의 프로시저 내에서 좀 더 효율적인 코드로 만드는 방법

      ○ 지역 최적화보다 더 많은 정보와 비용이 필요하므로 수행하기가 어렵지만 지역 최적화보다 효과가 훨씬 좋다.

      ○ 전역 최적화에는 일반적으로 자료 흐름 분석(data flow analysis)이라는 기법을 사용하는데, 이는 프로그램

           안에서 사용되는 변수의 통로(path)에 관한 정보를 수집해서 처리하는 과정이다. 전역 최적화 기법에는 전역적

           공통 부분식 제거, 상수 폴딩, 도달 불가능한 코드 제거 등이 있다.

● 루프 최적화: 한 루프 안에서의 최적화 기법

      ○ 루프는 실행 시간의 90%를 차지하는 부분이므로 품질 좋은 코드를 생성하는 것은 특히 중요

      ○ 루프 내부(inner loop)의 코드에 대해 계산의 복잡도를 줄이는 것을 목표로 한다.

           많은 코드 변환 기법은 흐름 그래프(flow graph)에서 루프를 찾는 데 집중한다.

      ○ 루프 최적화 기법에는 코드 이동(code motion), 세기 감축, 귀납 변수(induction variable) 최적화,

           루프 융합(loop fusion), 루프 교환(loop interchange), 루프 전개(loop unrolling) 등이 있다.

 

프로그램의 범위에 따라

● 프로시저 간 최적화: 전체 프로그램에 적용되는 최적화를 말한다.

      ○ 이 기법에는 다양한 매개변수 전달 방법, 비지역 변수의 참조, 서로 호출 가능한 모든 프로시저 정보를 동시에

           구하는 작업 등이 관련되기 때문에 구현하기가 더욱 어렵다. 따라서 많은 컴파일 러에서는 극히 기본적인

           프로시저 간 최적화만 수행하거나 프로시저 간 최적화를 전혀 수행하지 않는다.

 

 

Machine Dependent Optimization

 

● 기계의 특성에 따라 아주 달라질 수 있다.

● 중복된 LOAD 명령어 제거, 효율적인 명령어 선택(instruction selection), 레지스터 할당(register allocation)

     과 레지스터 배정(register assignment )등

 

 

Basic Blocks and Flow Graph

 

지역 최적화, 전역 최적화, 프로시저 간 최적화, 루프 최적화 기법에서는

● 최적화를 수행하기 위해 전체 프로그램을 기본 블록 단위로 분할하여 최적화

 

지역 최적화:

● 기본 블록 안에서 최적화를 수행.

전역 최적화, 프로시저 간 최적화, 루프 최적화

● 기본 블록을 노드로 가진 flow graph를 만들고 흐름 그래프에서 자료의 흐름을 분석

 

기본 블록

지역 최적화의 기본 단위

제어가 시작점으로 들어와서 끝점으로 나갈 때까지 정지(halt)나 분기의 가능성이 없는 연속적인 코드들의 집합

 

 

Basic Blocks 

 

지역 최적화의 기본 단위 제어가 시작점으로 들어와서 끝점으로 나갈 때까지 정지(halt)나 분기의 가능성이 없는

연속적인 코드들의 집합

 

 

Leader

 

[정의] 리더Leader

(1) 프로그램의 시작 문장

(2) 조건부 분기 또는 무조건 분기의 목적지에 있는 문장

(3) 조건부 분기 바로 다음에 위치하는 문장

 

기본 블록은 리더와 다음 리더 이전에 나타나는 모든 코드로 구성되기 때문에 먼저 리더를 찾아야 한다.

 

 

Leader (2) 다음 예는 n 값을 읽어 들여 1부터 n까지의 곱을 구하는 C 프로그램이다.

 

Example) 리더 찾기

 

 

 

Basic Blocks

 

[알고리즘] 3- 주소 코드로부터 기본 블록을 구하는 방법

● [입력] 3-주소 코드

● [출력] 기본 블록의 리스트

● [방법] 리더와 다음 리더 사이에 있는 모든 코드

 

 

Example 다음 그림에 대해 [알고리즘]을 적용하여 기본 블록을 구해보자.

 

 

위 예제를 4개의 블록으로 나눠서 위와 같이 표현 가능하다.

 

 

Flow Graph and DAG Flow graph:

● 기본 블록의 집합에 제어 흐름에 관한 정보를 추가해서 만든 directed graph

● 노드는 기본 블록이고 edge는 조건 분기와 무조건 분기를 나타낸다.

● 모든 제어 흐름의 정보를 포함하며, 수집된 정보는 전역 최적화를 수행하는데 필요

 

흐름 그래프에서 기본 블록 B에서 기본 블록 C로의 edge를 추가할 수 있는 조건

● B의 마지막 문장에서 C의 첫 번째 문장으로 조건 분기 혹은 무조건 분기가 존재한다.

● 프로그램의 실행 순서상 B 바로 다음에 C가 나타나며, 이때 B의 마지막 문장이 무 조건 분기로 끝나지 않는다.

 

이와 같은 경우에 B는 C의 predecessor라 하고, C는 B의 successor라 한다. 마지막으로 진입 노드(entry node)와

진출 노드(exit node)라 불리는 2개의 노드를 추가한다.

 

 

Example 3-주소 코드, 리더, 기본 블록을 구하고 흐름 그래프를 그려보자.

 

for(i = 1; i ＜ n; i++)

      S1;

S2; 

 

1. 3-주소 코드는 다음과 같다.

i = 1;

GOTO L2;

L1: S1;

       i++;

L2:  if(i < n) goto L1;

        S2;

 

2. 리더를 구한다.

leader 1 : i = 1 (시작지점)

leader 2 : L1: S1; (조건부 분기 바로 다음에 위치하는 문장)

leader 3 : L2: if(i < n) goto L1; (조건부 분기)

leader 4 : S2; (조건부 분기 바로 다음에 위치하는 문장)

 

3. 기본 블록을 구한다.

 

 

4. 흐름 그래프를 그린다.

 

 

 

흐름 그래프에서 루프는 무엇인가? 그리고 모든 루프는 어떻게 찾을 수 있는가?

 

[정의] 루프

다음 조건을 만족하면 루프(loop)라고 한다.

● 루프는 입구(entry)가 단 하나이다.

● 루프 밖에서 루프 안으로 도달하기 위해 항상 먼저 지나는 노드가 입구이며, 하나의 입구만 존재한다.

● 루프 안의 모든 노드는 강하게 연결되어 있다

      ○ 어느 한 노드에서 다른 어떤 노드로 갈 수 있는 경로가 존재한다

 

내부 루프 : 다른 루프를 포함하지 않는 루프를 흐름 그래프의 시작 노드(initial node)에서 어떤 노드 n에 이르는

모든 통로가 노드 d를 통과하는 경우, 노드 d는 노드 n을 dominate하고, 이를 d dom n으로 표현한다.

● 모든 노드는 자기 자신을 dominate한다.

● 루프의 진입 노드(입구)는 그 루프의 모든 노드를 dominate한다.

 

Example Dominator 찾기

 

 

1 : 모든 node를 dominate 한다.

2 : 자기 자신만을 dominate 한다.

3 : 1, 2 를 제외한 모든 node를 dominate 한다.

4 : 1, 2, 3 를 제외한 모든 node를 dominate 한다.

5, 6 : 자기 자신만을 dominate 한다.

7 : 7, 8, 9, 10 node를 dominate 한다.

8 : 8, 9, 10 node를 dominate 한다.

9, 10 : 자기 자신만을 dominate 한다.

 

 

Dominator Tree Dominator

 

정보를 나타내는 트리: