Compile on Linux

(1) Quiz 1

* page fault : virtual memory에는 있는데, physical memory에는 없는 경우 발생.

* segmentation fault : virtual memory에도 없는 경우 발생.

< 그림 1 - 안그림 >

* PGD : 항상 연결됨.

* PTE : 항상 연결되는 것이 아님. 없으면 page fault가 발생해서 PTE에 연결시켜줌.

(2) GCC 특징

• 전처리기, C 컴파일러, 어셈블러, 링커
• gcc -v --save-temps -o hello hello.c
• Using built-in specs : 컴파일시 꼭 필요한 옵션을 저장한 파일

    * hello.c --(cc1)--> hello.i --(cc1)--> hello.s --(as)--> hello.o --(collect2)--> hello

    1. 전처리 과정 : cpp0 or cc1

    2. 컴파일 과정

• 어셈블리 소스로 컴파일 : cc1
• 최적화 과정 : O0 ~ O3
  
• 기계어 코드 생성 : as, ELF 포멧
  

    5. 링킹 과정 : collect2

* 심볼 : 메모리상의 주소를 가지는 모든 것

* 심볼 테이블 : .c 파일 내부에 사용된 심볼들의 정보가 들어있는 테이블

(3) 코드 최적화

    * 실행 파일이 수행될 때 속도와 메모리 사용측면에서 효율적으로 동작하는 코드를 생성하는  

      소프트웨어 기법

• 컴파일 후 명령어 수행 횟수를 최소화 함으로써 성능을 높임.
• 일반적으로 길이가 짧은 코드가 적은 명령어를 수행함.
• 의도상 delay를 주는 경우가 아니라면 -O3 옵션이 최적화에 큰 역할 할 수 있음.

    * 고려 사항

1. 속도
2. 메모리 요구량
3. 레지스터 사용량 - 아키텍처 의존적
4. 파이프 라이닝 - 아키텍처 의존적

    * 코드 최적화 기법

1. Loop Fusion : 루프 갯수 줄임
• 반복문은 다른 연산에 비하여 상대적으로 많은 cycle을 요구
• fusion이 가능한 반복문은 루프를 하나로 결함.
• 효과적인 cache 사용으로 인한 성능상의 이득을 얻을 수 있음.
2. Loop Unrolling : 루프 수행 횟수 줄임
• 배열의 크기가 unrolling의 양의 배수가 되도록 작성.
• for(i=0; i<ARRAY_SIZE;i++)    array_v[i];
• => for(i=0; i<ARRAY_SIZE;i++) array_v[i] = i; array_v[i+1] = i + 1;
• unrolling 갯수에 비례하지 않음.
• register 이용 개수를 고려하여 작성해야 함.
• unrolling의 깊이가 증가할수록 메모리 사용량 증가
3. Loop Invariant Code Motion : 불변 계산은 상수로 만듬.
• loop 내에 불변하는 계산들은 오버헤드를 유발함.
• loop 내에서 불변하는 계산 값이나 함수를 코드 바깥쪽으로 분리
• strlen()이 비교문에 들어가는 경우
• 변하지 않는 사칙 연산 값
• loop 내에 불변의 값을 상수 값으로 대체
• 수식이 간단하다면 loop 안에서 계산하는 것이 더 효율적일 수 있음.
• O3 옵션을 이용하면 최적화를 해줌(함수호출의 경우 O0에 대배하여 O3옵션으로 컴파일 하더라도 이득이 별로 없음.)
4. Strength Reduction
• 고비용의 연산자를 저비용의 연산자를 이용하여 연산되도록 코드 최적화
• 나머지 연산을 비트 연산으로 대체
• sin, cos, pow 등 수학함수를 호출하는 루틴 중 연산자로 계산시 간단하게 구현 가능한 부분에 대하여 연산자로 대체
• 간단한 연산의 경우 산술연산을 하는 것이 효과적
• 코드의 복잡도, 가독성, 속도 향상 등을 고려하여 최적화
5. Count up to Zero
• 루프의 종료조건을 0과 비교하는 것이 효율적
• 대부분의 아키텍처에서는 0에 도달할 때 ZERO 플래그를 재설정하게 됨.
• 변수를 0과 비교하게 되면 명시적인 비교문이 생략됨.
6. Register Allocation
• C 컴파일러가 변수를 위해 사용할 수 있는 레지스터 : r0 ~ r3, r4~r11 사용이 바람직.
• 사용가능한 변수보다 많은 변수를 사용하면 stack에 저장
• 변수들이 메모리에 저장됨(spilled)=>사실 대부분 cache에 저장될 것임.
• 자주 접근되는 변수는 레지스터에 저장
• 서브루틴 호출 시 매개변수 처리
• 4개 이하 인자를 매개변수로 받는 함수가 효율적임(그 이상 stack에 쌓임)
• 5개 이상의 매개변수를 받아야 하는 경우는 구조체를 이용하여 전달.
• 일반적으로 전역변수를 사용하여 연산을 수행하는 것은 부가적인 오버헤드를 유발
• 전역변수의 사용은 메모리 참조연산을 수반하기 때문에 전역변수를 사용하여 복잡한 연산을 하는 것은 비효율적임
• 지역변수를 이용해 연산을 수행하고 그 결과값을 전역변수에 저장하는 게 효율적
• 컴파일러에 의한 최적화 이유로 구조체를 이용한 매개변수 전달의 최적화가 상쇄될 수 있음
7. Software Pipelining
• 명령어마다 각기 다른 사이클 소요
• 아키텍처마다 다름
• ARM9TDMI
• 덧셈, 뺄셈, 논리연산과 같은 ALU연산은 한 사이클 소요
• 곱셈, 나눗셈은 오퍼랜드 값에 따라 다양한 사이클 소요
• 분기 명령은 3사이클 소요
• N개를 저장하거나 로드하는 경우 N 사이클 소요
• 1개인 경우 2사이클 소요
• PC를 로드한다면 2사이클 추가 소요
• 배열에 값을 저장한 후 그 값을 바로 다음에 연산에 이용하면 stall 발생하면서 파이프 라인이 깨져서 더 많은 사이클 소요됨. 그러므로 loop 내에서 다음 명령라인이 바로 이전 연산에 종속되지 않도록 작성하는 게 중요함.
• for(i... ... ...) ary1[i] = v1 + 1; ary12[i] = ary1[i] & 0xff00;
• => for(i... ... ...) ary1[i] = v1 + 1; ary2[i] = v2 + 1; ... ary12[i] = ary1[i] & 0xff00; ...

* GCC 옵션

• -S : .s 파일 생성, 전처리된 파일을 어셈블리 파일로 컴파일
• -c : .o 파일 생성, as에 대한 어셈블까지만 수행하고 링크는 않함.
• --save-temps : 컴파일시 중간과정 생성 파일을 현재 디렉토리에 저장
• -I : 전처리과정에서의 탐색 디렉토리 추가
• -D : 매크로를 외부에서 define할 때
• -W : 부가적인 정보 제공
• -Wall : 모든 경고 메시지 출력
• -O0 : 최적화 하지 않음
• -O2 : 최적화 기본 단위
• -O3 : 가장 높은 레벨의 최적화
• -Os : 사이즈 최적화 수행
• -g : gdb에게 제공하는 정보를 바이너리에 삽입(g0 ~ g3)
• -pg : 프로파일을 위한 코드 삽입(함수 호출 횟수나 수행 시간 분석 수행시)