[GCC] __builtin_constant_p 정리

GCC에서는 다양한 builtin function을 제공하는데 이번 포스트에서 다룰 것은 __builtin_constant_p 함수이다. 해당 함수는 아래와 같이 Linux Kernel kmalloc에서 사용하는 모습을 살펴볼 수 있다. 얼핏 봐서는 왜 이 함수를 사용하는지 알기 힘들기 때문에 몇 가지 간단한 예제를 통해 구체적으로 사용 예를 살펴보도록 하겠다.

<include/linux/slab.h>

GCC 문서에 따르면 "해당 함수는 함수의 인자가 compile time에 결정되는 값인지, 즉 상수인지 판단한다, 따라서 GCC는 constant folding을 수행할 수 있다." 라고 한다.

설명에 따르면 constant folding이라는 term이 나온다. 따라서 해당 용어가 어떤 의미를 가지고 있는지 먼저 살펴보도록 한다.

Constant folding

Constant folding은 modern compiler에서 사용하는 최적화 기능이다. 해당 기능은 compile time에 constant expression을 recognize, evaluating한다.

만약 아래와 같이 statement가 있다고 하자. 해당 구문은 변수 320 * 200 * 32을 계산하기 위해 2번의 곱셈을 수행한다.

컴파일러에서는 해당 statement가 compile time에 결정될 수 있는 것을 인식하고, 계산된 값으로 대체한다. 따라서 대체된 값 2048000을 i에 대입하는 것으로 최적화한다.

또 다른 예시로 아래와 같은 여러 분기문으로 구성된 코드가 있다고 하자. 해당 코드는 변수 i에 따라 개별적인 함수를 실행한다.

만약 i가 compile time에 1로 결정된다면 위의 코드는 아래와 같이 최적화될 수 있다.

__builtin_constant_p

해당 함수의 인자가 compile time에 결정되는 상수인지 조사하며 만약 그렇다면 1을 반환하고 그렇지 않다면 0을 반환한다.

0을 반환하는 것은 그 값이 반드시 상수가 아니라는 말은 아니다. 단지, GCC가 주어진 최적화 옵션에서 해당 값이 상수인지 판단할 수 없다는 것을 의미한다.

만약 복잡한 계산을 수행해야 하는데 상수로 인자가 들어올 때는 그 계산을 constant folding하고 그렇지 않다면 계산 함수를 호출하고 싶을 수 있다. 그러한 경우에 아래 예제와 같이 매크로를 정의하면 된다.

해당 매크로를 이용하여 간단한 예제 프로그램을 작성해보도록 한다.

첫 4개의 Scale_Value의 인자가 상수(integer literal)이고, 그 뒤에 Scale_Value의 인자는 변수이다. 해당 코드를 아래의 커맨드와 같이 빌드한다.

$ gcc -o scalar_value scalar_value.c

빌드한 바이너리 파일을 objdump를 통해 어떤 식으로 컴파일이 되었는지 살펴보도록 하자.

17, 21, 25, 29 라인에서 constant folding 된 값들(8, 10, 12 ,14)을 바로 사용하는 것을 관찰할 수 있다. 그에 반해 for 문에서는 38번 라인에서 볼 수 있듯이 Scale 함수를 통해 값을 계산하는 것을 살펴볼 수 있다.

만약 해당 매크로를 사용하지 않았다면 미리 계산된 값을 사용하는 것이 아니라 아래와 같이 Scale 함수를 호출한다.

해당 예제에서 더 적극적인 최적화 옵션을 사용하면 위의 결과와는 다른 결과가 나올 수 있다. -O1을 적용시켰을 때는, loop unrolloing이 되어 constant folding이 된 것으로 추측된다.

해당 builtin function을 inline 함수에서도 사용하고 싶을 수 있다. 만약 inline 함수의 argument를 이 함수의 인자로 넘긴다면, GCC는 문자열 literal 또는 compound literal이 아니라면 1을 반환하지 않는다. 또한 최적화 옵션(-O)을 지정하지 않으면 상수를 전달해도 1을 반환하지 않는다.

간단한 예제를 통해 실제 동작을 살펴보자.

해당 예제에서 target 함수는 인자가 compile time에 결정되는 값인지 아닌 지에 따라 흐름을 제어하는 if/else 구문이 있다. if와 else 구문은 8, 19번 라인을 제외하면 동일한 일을 수행한다. main 함수에서는 target 함수의 인자를 integer literal로 호출하고, 변수를 통해 호출한다.

위 코드를 아래와 같이 -O1 옵션으로 최적화를 설정하고 빌드한다.

$ gcc -fno-pie -static -o builtin_constant_p builtin_constant_p.c -O1

instructino을 조금 보기 쉽게 하기 위해 -fno-pie와 -static 옵션을 사용했다. 사용하지 않아도 상관없다.

빌드된 바이너리를 실행하면 아래와 같은 결과를 얻는다.

설명에 나온 대로 integer literal을 인자로 넣었을 때는 if 구문으로 진행되고, 변수를 인자로 전달하였을 때는 else 구문으로 실행되었다. 이제 바이너리 파일을 살펴보며 어떻게 inline 되었는지 살펴보도록 하겠다.

0x401915~0x40196a 주소의 instruction들은 입력 인자로 integer literal을 넣은 코드에 해당한다. 살펴보면 많은 부분이 constant folding 되어 target 함수는 단순히 2개의 printf를 호출하도록 최적화되었다.

위 instruction들은 for 구문에서 taget 함수의 인자를 변수로 주는 코드에 해당한다. 우선 0x401979에서 0x4019a8로 점프하며 "I'm not constant!"를 출력한다. 그 다음으로는 여러 개의 branch instruction을 통해 실행할 코드를 결정한다.

앞에서 입력을 integer literal을 줬을 때와 비교하면, 여러 branch, jump instruction이 실행되며 따라서 더 많은 clock을 필요로 할 것이다.

Kmalloc

kmalloc도 위의 예제와 같은 방식으로 최적화된 코드 구성을 가진다.

• fast path: size가 compile time에 결정되는 상수라면, size에 대응하는 index가 계산되어 constant folding되고 곧 바로 kmeme_cache_alloc_trace를 호출할 것이다.

• slow path: size가 compile time에 결정되지 않는다면, __kmalloc을 호출한다. 내부적으로는 size를 인덱스로 변환하는 함수를 호출할 것이다.

실제로 그렇게 되는지 간단한 모듈을 통해 알아보자.

해당 모듈을 빌드하고, 생성된 오브젝트 파일을 덤프하면 아래와 같은 내용을 살펴볼 수 있다.

덤프된 instruction들과 relocation 정보를 보면, kmalloc을 호출할 때 size를 integer literal로 준 경우는 constant folding을 통해 size에 대응하는 index가 compile time에 계산된다. 그리고 그것을 이용하여 곧바로 kmem_cache_alloc_trace 함수를 호출하는 것을 확인할 수 없다. 또한 size를 변수로 전달하면 __kmalloc을 호출하는 것도 확인할 수 있다.

Opinion

런타임 계산 후 변경되지 않는 size가 있다면, 이를 반영하여 최적화된 instruction으로 교체하는 것은 어떨까? Static key와 비슷하게 Runtime size optimized된 코드 개념.