Egloos | Log-in
F/OSS study
F/OSS study
태그 : gcc
2012/06/14   [gcc] 배열 초기화 코드 [3]
[gcc] 배열 초기화 코드
gcc: 4.7.0
arch: x86_64


김민장님의 블로그에서 흥미로운 글을 읽고 gcc에서도 어떻게 동작하는지 궁금하여
약간의(?) 삽질 끝에 알아낸 몇가지 사실들을 글로 남겨본다.

테스트에 사용한 코드는 원글에서와 동일하게 다음과 같다.

arrinit.c:
void foo(void)
{
    char arr1[16] = { 2, 3, 4 };
}

위 함수를 gcc로 아무런 최적화없이 (-O0) 컴파일하면 (-S) 아래와 같은 어셈블리 출력을 얻을 수 있다.
참고로 최근에 공개된 GCC explorer 웹사이트를 이용하면
웹에서 곧바로 테스트를 해 볼 수 있으므로 매우 편리하다.
(사실 gcc가 아닌 g++이긴 하지만 이 글에서는 크게 상관없는 듯 하다.)

foo:
.LFB0:
    .cfi_startproc
    pushq   %rbp
    .cfi_def_cfa_offset 16
    movq    %rsp, %rbp
    .cfi_offset 6, -16
    .cfi_def_cfa_register 6
    subq    $32, %rsp
    movq    %fs:40, %rax
    movq    %rax, -8(%rbp)
    xorl    %eax, %eax
    movq    $0, -32(%rbp)
    movq    $0, -24(%rbp)
    movb    $2, -32(%rbp)
    movb    $3, -31(%rbp)
    movb    $4, -30(%rbp)
    movq    -8(%rbp), %rax
    xorq    %fs:40, %rax
    je  .L3
    call    __stack_chk_fail
.L3:
    leave
    ret
    .cfi_endproc

여기서 불필요한 DWARF CFI 생성 코드와 (-fno-dwarf2-cfi-asm)
stack protection 코드를 제거하면 (-fno-stack-protector)
대략 다음과 같은 형태가 된다. (참고로 GCC explorer에서는
이미 CFI directive를 필터링해서 보여주므로 첫 번째 옵션은 생략해도 무방하다)

foo():
    pushq   %rbp
    movq    %rsp, %rbp
    movq    $0, -16(%rbp)
    movq    $0, -8(%rbp)
    movb    $2, -16(%rbp)
    movb    $3, -15(%rbp)
    movb    $4, -14(%rbp)
    popq    %rbp
    ret

코드는 무척 단순하게도 전체 배열을 우선 0으로 초기화한 후 각각의 초기값들을 채워주는 형태이다.
배열의 크기를 여러가지로 바꿔보면 코드가 조금 다르게 생성되는 것을 볼 수 있지만
기본적으로 전체 배열을 초기화한 후 각각의 원소를 설정하는 형식 자체는 바뀌지 않는다.

이를 좀 더 확실히 보기 위해서는 C 언어 소스를 gcc가 최적화하기 위한 형태인
gimple로 바꾸는 (gimplify) 과정에서 이 코드가 어떻게 처리되는지 보면 알 수 있다.

컴파일 시에 -fdump-tree-gimple 옵션을 추가하면 다음과 같은 파일을 얻을 수 있다.
(주석으로 처리한 부분은 -fdump-tree-gimple-raw 옵션을 주었을 때의 출력 결과이다)

$ gcc -S -fdump-tree-gimple arrinit.c
$ cat arrinit.c.004t.gimple
foo ()
{
  char arr1[16];

  arr1 = {};      // gimple_assign <constructor, arr1, {}, NULL>
  arr1[0] = 2;    // gimple_assign <integer_cst, arr1[0], 2, NULL>
  arr1[1] = 3;    // gimple_assign <integer_cst, arr1[1], 3, NULL>
  Arr1[2] = 4;    // gimple_assign <integer_cst, arr1[2], 4, NULL>
}

위에서처럼 변수 선언 시 초기값을 대입하는 형태의 식은
C 언어 파서(front-end)에서 init expression으로 분류되며
일반적인 대입 연산과 마찬가지로 gimplify_modify_expr() 함수에서 이를 처리한다.
이 때 배열의 초기화인 경우 다음과 같은 gimplify_init_constructor() 함수를 거치게 된다.
(설명을 위해 불필요한 부분과 주석은 제거하였다.)

gcc/gimplify.c:
gimplify_init_constructor (...)
{
  ...
    valid_const_initializer
      = categorize_ctor_elements (ctor, &num_nonzero_elements,
                      &num_ctor_elements, &complete_p);

    if (int_size_in_bytes (TREE_TYPE (ctor)) < 0)
      cleared = false;
    else if (!complete_p)
      cleared = true;
    else if (num_ctor_elements - num_nonzero_elements
         > CLEAR_RATIO (optimize_function_for_speed_p (cfun))
         && num_nonzero_elements < num_ctor_elements / 4)
      cleared = true;
    else
      cleared = false;

    ...

    if (cleared)
      {
        CONSTRUCTOR_ELTS (ctor) = NULL;
        TREE_SIDE_EFFECTS (ctor) = 0;
        object = unshare_expr (object);
        gimplify_stmt (expr_p, pre_p);
      }

    if (!cleared || num_nonzero_elements > 0)
      gimplify_init_ctor_eval (object, elts, pre_p, cleared);
  ...
}

먼저 categorize_ctor_elements() 함수를 통해
0이 아닌 값을 가지는 배열의 원소(element)의 수 (num_nonzero_elements)와
초기값에 명시된 원소의 수 (num_ctor_elements)를 계산하고
명시된 원소의 수가 전체 배열의 원소 수보다 작다면 complete_p 변수를 false로 설정한다.

따라서 뒤의 조건문에서 첫번째 경우 int_size_in_bytes() 함수는 배열의 크기인 16을 반환할 것이므로,
다음의 complete_p 부분에서 걸려서 cleared 변수를 true로 설정하게 된다.
따라서 아래쪽의 코드에서 초기값을 NULL로 초기화한 후
배열 전체를 0으로 초기화하는 gimple assign 문장을 생성하며
gimplify_init_ctor_eval() 함수를 통해 각각의 원소의 값을 설정하는 assign 문장이 추가된다.

만약 배열의 모든 원소에 명시적으로 초기값을 설정한 경우라면 complete_p가 true가 되며
이 때는 초기값이 0인 원소의 수가 CLEAR_RATIO 보다 크고, 초기값이 0이 아닌 원소의 수가
전체 원소의 수의 1/4 미만인 경우에만 cleared를 true로 설정한다.

CLEAR_RATIO는 x86(_64) 아키텍처의 경우 다음과 같이 정의되어 있다.

gcc/config/i386/i386.h:
#define CLEAR_RATIO(speed) ((speed) ? MIN (6, ix86_cost->move_ratio) : 2)

이 매크로는 현재 컴파일러가 (현재 함수에 대한) 코드를 생성할 때 최종 결과로 나올 바이너리가
실행 속도를 중요시하는지 아니면 파일 크기를 줄이려고 하는지에 따라 다른 값을 리턴하는데
일반적으로 -Os 최적화 옵션을 주지 않은 경우라면 optimize_function_for_speed_p 함수가
true를 리턴하게되고, 따라서 6과 ix86_cost->move_ratio 중에서 작은 값을 가지게 되는데
Intel Pentium 급 이상의 머신에서는 move_ratio가 6 이상의 값을 가지므로 보통 6이 선택된다.
(참고로 _p 형태로 끝나는 함수/매크로는 predicate을 의미하는 듯하며,
일반적으로 리턴값의 타입이 boolean이다.)

ix86_cost는 컴파일러가 코드를 생성할 때 고려할, 명령어 별 overhead(?) 정보를 저장하는
processor_costs 구조체이며 gcc/config/i386/i386.c 파일의 첫 부분에 정의되어 있고
필요에 따라 컴파일 시 -mtune (혹은 -march) 옵션을 통해 제어할 수 있게 된다.

다시 원래 함수로 돌아오면, 배열의 모든 원소에 대해 초기값이 지정되어 있고,
그 중 초기값이 0인 원소들이 6개 보다 많은 (그리고 0이 아닌 원소들이 상대적으로 적은) 경우라면
일단 전체 배열을 0으로 초기화 한 후에 나머지 (0이 아닌) 원소들을 초기화한다.

그렇지 않은 경우 (즉, 0이 아닌 초기값을 가지는 원소가 많은 경우)라면
전체 배열을 0으로 초기화하지 않고 (cleared = false) 그냥 각각의 원소를 별도로 설정하게 된다.

그러면 이제 배열 전체를 0으로 초기화하는 코드가 실제로 어떻게 생성되는지를 살펴보도록 하자.
테스트해 본 결과 6개 미만의 명령어를 이용하여 배열을 초기화할 수 있는 경우
mov 명령어를 직접 삽입하는 형태가 되며 그 이상의 명령어가 필요한 경우
rep stos 형태의 명령을 이용하는 것을 확인할 수 있었다.

rtl 코드 생성(expand) 시 gimple_assign 문장은 expand_assignment() 함수에 의해 처리되며
이 때 전체를 0으로 초기화하는 코드는 expand_constructor() 함수를 거쳐 결국
clear_storage_hints() 함수에서 다음과 같이 처리된다.

gcc/expr.c:
clear_storage_hints (...)
{
  ...
  if (CONST_INT_P (size)
      && CLEAR_BY_PIECES_P (INTVAL (size), align))
    clear_by_pieces (object, INTVAL (size), align);
  else if (set_storage_via_setmem (object, size, const0_rtx, align,
                   expected_align, expected_size))
    ;
  else if (ADDR_SPACE_GENERIC_P (MEM_ADDR_SPACE (object)))
    return set_storage_via_libcall (object, size, const0_rtx,
                    method == BLOCK_OP_TAILCALL);
  else
    gcc_unreachable ();

  return NULL;
}

먼저 배열의 크기(size)는 컴파일러가 알 수 있으므로 CONST_INT_P 매크로는 true를 리턴하고
CLEAR_BY_PIECES_P 매크로를 검사하게 된다. 이는 다음과 같이 정의되어 있다.

#define CLEAR_BY_PIECES_P(SIZE, ALIGN) \
  (move_by_pieces_ninsns (SIZE, ALIGN, STORE_MAX_PIECES + 1) \
   < (unsigned int) CLEAR_RATIO (optimize_insn_for_speed_p ()))

move_by_pieces_ninsns() 함수는 주어진 SIZE 크기의 메모리 영역을
mov 명령어를 통해 각각 설정(초기화)하는 경우 필요한 명령어의 수를 계산한다.
이 때 계산된 명령어의 개수가 CLEAR_RATIO 매크로의 리턴값 보다 작은 경우에만 true를 리턴할 것이다.
즉, 위에서 살펴본대로 6개 미만인 경우에만 mov 명령어를 통해 직접 초기화될 것이다. (clear_by_pieces)

이제 6개 이상의 mov 명령어가 필요한 경우를 고려해 보자.
이 때는 set_storage_via_setmem() 함수가 호출되는데
이 함수는 코드를 생성할 (back-end) 아키텍처에서 정의해 둔 setmem_optab 테이블을 검사하여
(비교적) 큰 영역의 메모리를 설정할 때 효율적으로 처리할 수 있는 방법이 있는지 찾는다.

gcc/config/i386/i386.md 파일에 보면 setmemsi와 setmemdi가 정의된 부분을 찾을 수 있는데
(끝에 붙은 si, di는 machine mode를 나타내는 것으로 각각 4, 8 바이트 크기의 정수형에 해당한다)
이는 모두 ix86_expand_setmem() 함수를 통해 구현됨을 알 수 있다.

이 함수는 내부적으로 decide_alg() 함수를 호출하여 현재 상황에 알맞는 알고리즘을 선택하는데
이 알고리즘의 종류는 다음과 같이 정의되어 있다.

gcc/config/i386/i386-opts.h:
enum stringop_alg
{
   no_stringop,
   libcall,
   rep_prefix_1_byte,
   rep_prefix_4_byte,
   rep_prefix_8_byte,
   loop_1_byte,
   loop,
   unrolled_loop
};

크게 보면 libcall은 memset 라이브러리 함수를 호출하는 것이고,
rep 명령어를 이용하여 코드를 생성하거나, 컴파일러가 자체적으로 루프를 만들어주는 경우가 있다.
이러한 알고리즘을 선택하기 위해서 (위에서 언급한) processor_costs 구조체 내에
다음과 같이 정의된 stringop_algs 구조체 멤버를 포함하고 있다.

gcc/config/i386/i386.h:
#define NAX_STRINGOP_ALGS 4

struct stringop_algs
{
  const enum stringop_alg unknown_size;
  const struct stringop_strategy {
    const int max;
    const enum stringop_alg alg;
  } size [NAX_STRINGOP_ALGS];
};

struct processor_costs {
  ...
  struct stringop_algs memcpy[2], memset[2];
  ...
};

memcpy와 memset의 경우를 위해 각각 32비트와 64비트 아키텍처를 구분하여
어떤 알고리즘을 사용할 지 정의할 수 있도록 하고 있다.
최근의 (64비트) CPU를 사용하고 있다면 generic64_cost가 적용될 것이다

gcc/config/i386/i386.c:
#define DUMMY_STRINGOP_ALGS {libcall, {{-1, libcall}}}

struct processor_costs generic64_cost = {
  ...
  {DUMMY_STRINGOP_ALGS,
   {libcall, {{32, loop}, {8192, rep_prefix_8_byte}, {-1, libcall}}}},
  {DUMMY_STRINGOP_ALGS,
   {libcall, {{32, loop}, {8192, rep_prefix_8_byte}, {-1, libcall}}}},
  ...
};

이 경우 memset[1]에 해당하는 것이 선택될 터이므로 맨 마지막 것을 보면 되겠다.
처음의 libcall은 unknown_size 즉, 컴파일 시점에 크기를 알 수 없는
메모리 영역을 초기화하는 경우에 사용할 알고리즘이다.
이 경우라면 memset 라이브러리를 호출하고 인자로 크기를 저장한 변수를 넘기면 될 것이다.

다음으로 메모리 영역의 크기가 32바이트 이하인 경우 loop 알고리즘을 사용하여 코드를 생성할 것이다.
(하지만 이러한 경우들은 앞서 본 clear_by_pieces() 함수에서 대부분 먼저 처리되므로
지금과 같이 배열을 초기화하는 경우에서는 거의 확인할 수 없지만
유일하게 31은 8 + 8 + 8 + 4 + 2 + 1의 6개의 명령어가 필요하므로 확인 가능하다!)
그리고 8192 바이트 이하인 경우에는 rep 명령어를 통한 반복문을 만들고
그 보다 더 큰 경우에는 memset 라이브러리 함수를 이용하도록 코드를 생성할 것이다.

마지막으로 만약 (코드 생성을 위한) 타겟 아키텍처에서 setmem_optab을 설정하지 않은 경우라면
set_storage_via_libcall() 함수를 통해 memset() 함수를 호출하는 코드를 생성하게 된다.

by namhyung | 2012/06/14 00:11 | System | 트랙백 | 덧글(3)
◀ 이전 페이지 다음 페이지 ▶

카테고리
General
Application
System
Kernel
Book
Tips
태그
perf linux build documentation x86 git vcs block-layer bash CAaQA3 CARM kernel gcc memory binutils SMP awk compiler elf computer-architecture algorithm scm script patch sed blktrace emacs C synchronization glibc
전체보기
이글루 파인더

최근 등록된 덧글
informsi yang bagus dan b..
by agen qnc at 06/22
informasi yang bagus dan b..
by agen qnc at 06/22
informasi yang bagus dan b..
by agen qnc at 06/22
최근 등록된 트랙백
Tod's Ferrari Homme
by Tods Pas Cher,Kodak did ..
Mocassin Femme
by Mocassins Homme, I got so..
natural garcinia cambogia
by
rss

skin by jiinny


X