Egloos | Log-in
F/OSS study
F/OSS study
태그 : x86
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
태그
awk C vcs linux kernel blktrace x86 sed binutils build synchronization block-layer glibc computer-architecture gcc script scm perf CAaQA3 documentation memory SMP git bash emacs elf CARM patch compiler algorithm
전체보기
이글루 파인더

최근 등록된 덧글
informsi yang bagus dan be..
by pordanaia at 08/05
Informsi yang bagus dan b..
by jamalsu at 08/01
as inforasi yang menarik http..
by jamalsu at 07/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