분기 없는 코드에 끼어드는 조건 분기

AI 요약

비트 연산만 쓴 코드도 컴파일러가 조건 분기로 바꿀 수 있습니다. 00f.net의 글은 128비트 덧셈과 상수 시간 선택 함수를 여러 아키텍처에서 컴파일해, 소스 코드만 보고 데이터 의존 분기가 없다고 판단하기 어렵다는 점을 보여줍니다.

128비트 덧셈에서 생기는 분기

예제는 부호 없는 128비트 정수 두 개를 더합니다. 32비트 RISC-V(RV32)에는 32비트 레지스터만 있으므로 LLVM은 덧셈을 네 개의 32비트 단어 연산으로 나누고, 각 단어 사이에 자리올림(carry)을 전달합니다. 둘째 단어의 합이 입력 단어와 같은지 확인한 뒤 조건 분기를 내보내는 코드가 생성됩니다. 이 분기는 덧셈 과정에서 필요한 자리올림을 결정합니다.

x86과 AArch64에는 조건부 이동(conditional move) 명령어가 있어 분기 없이 자리올림을 처리할 수 있습니다. 반면 RV32에서는 64비트 비교조차 조건 분기를 만들 수 있습니다. 따라서 정수 연산 자체가 분기를 쓰지 않는 것처럼 보여도, 더 넓은 정수 연산을 작은 단어로 쪼개는 과정에서 분기가 들어갈 수 있습니다.

비트 마스크 선택도 안전을 보장하지 않습니다

상수 시간 코드에서 흔히 쓰는 선택 함수는 비트의 최하위 비트로 마스크를 만들고, 두 값에 AND와 OR를 적용합니다. 마스크가 모두 1이면 첫 번째 값을, 0이면 두 번째 값을 고르는 구조입니다. 하지만 Clang 23은 RV32와 RV64에서 이 코드를 분기 명령으로 바꿉니다. Clang 15에서도 분기가 있었고 16·17에서는 사라졌다가 18부터 23까지 다시 나타났습니다. 컴파일러 버전만 바뀌어도 결과가 달라집니다.

같은 현상은 Zig에서도 관찰됐고, 글은 Rust에도 같은 문제가 있다고 설명합니다. GCC 16.1은 기본 비트 마스크 선택과 예제의 128비트 덧셈을 RISC-V에서 분기 없이 컴파일했습니다. 그러나 마스크를 x < y 비교로 만들면 RV32와 RV64 모두 조건 분기를 생성했습니다. 같은 선택 로직이라도 컴파일러가 값을 얻는 방식에 따라 코드가 달라집니다.

아키텍처별 컴파일 결과

Clang 23의 -O2 결과를 비교하면 x86_64·x86, AArch64·32비트 ARM·Cortex-M3, MIPS32, LoongArch64, WebAssembly에서는 덧셈, 비트 마스크 선택, 64비트 비교에 조건 분기가 나오지 않았습니다. Cortex-M0에서는 선택과 비교에 각각 한 개씩, 32비트 PowerPC에서는 선택에 한 개와 비교에 두 개가 나왔습니다. RV32에서는 세 예제 모두 분기가 하나씩 생겼고, RV64에서는 선택에만 하나가 생겼습니다. RV32와 RV64 모두 Zicond를 켜면 세 예제에서 분기가 사라졌습니다.

WebAssembly에는 select 명령어가 있지만, 글은 이것만으로 최종 실행 코드의 분기 여부까지 보장하지 않는다고 짚습니다. WebAssembly 컴파일러가 실제 하드웨어용 코드로 바꾸는 과정에서 점프를 만들 수도 있습니다.

우회 방법과 한계

비트 마스크를 빈 인라인 어셈블리 구문에 통과시키면 컴파일러가 해당 값을 바꿀 수 있다고 판단합니다. 이 방법은 마스크 선택을 RV32와 RV64에서 분기 없이 컴파일하게 했습니다. 128비트 덧셈에서는 입력을 메모리 장벽 뒤에 두는 방식으로 분기가 사라지지 않았습니다. 각 32비트 단어에 레지스터 장벽을 적용하면 자리올림이 sltu 명령어로 처리됐지만, 글쓴이는 이 장벽 실험을 해결책으로 신뢰하지 말라고 경고합니다.

비밀값을 다루는 산술에서는 두 레지스터보다 넓은 정수형을 피하고, RV32라면 32비트 단어 단위로 자리올림을 직접 작성하는 편을 권합니다. 손으로 쓴 자리올림 코드도 이후 컴파일러 버전에서 달라질 수 있으므로, 컴파일러 버전이나 옵션을 바꿀 때마다 생성 어셈블리를 다시 검토해야 합니다.

Zicond와 시간 독립성

RISC-V의 Zicond 확장은 czero.eqz와 czero.nez 명령어를 추가합니다. 이 명령어로 조건에 따라 레지스터 값을 0으로 만들면 분기 없이 값을 선택할 수 있습니다. Zicond는 RVA23 프로파일에 포함되지만, 특히 마이크로컨트롤러를 포함해 현재 사용 중인 많은 코어에는 구현되지 않았습니다. 또 Zicond 명세는 Zkt 확장도 구현한 경우에만 해당 명령어의 실행 시간이 데이터와 무관하다고 보장합니다. 분기가 없는 코드와 시간 독립성이 보장된 코드는 같은 뜻이 아닙니다.

원문: 00f.net / 번역·요약: Trawling