improve bitfield arithmetic #33784

 

https://github.com/llvm/llvm-project/issues/33874

Improve bitfield arithmetic · Issue #33874 · llvm/llvm-project

 

패치목적

 

// 기존에 생성되던 IR

define dso_local i8 @AddCounters(Counters, Counters)(i8 %x.coerce, i8 %y.coerce) local_unnamed_addr {

entry:

%narrow = add i8 %y.coerce, %x.coerce

%bf.value = and i8 %narrow, 7

%bf.lshr = and i8 %x.coerce, 24

%bf.lshr1244 = add i8 %bf.lshr, %y.coerce

%bf.shl = and i8 %bf.lshr1244, 24

%bf.set20 = or disjoint i8 %bf.value, %bf.shl

%bf.lshr22 = and i8 %x.coerce, -32

%bf.lshr2547 = add i8 %bf.lshr22, %y.coerce

%bf.value30 = and i8 %bf.lshr2547, -32

%bf.set33 = or disjoint i8 %bf.set20, %bf.value30

ret i8 %bf.set33

}

 

 

 

 

 

// 최적화 IR

define dso_local i8 @AddCounters_Opt(Counters, Counters)(i8 %x.coerce, i8 %y.coerce) local_unnamed_addr {

entry:

%and = and i8 %x.coerce, 107

%and7 = and i8 %y.coerce, 107

%add = add nuw i8 %and7, %and

%xor = xor i8 %y.coerce, %x.coerce

%and11 = and i8 %xor, -108

%xor12 = xor i8 %add, %and11

ret i8 %xor12

}

 

struct Counters {

BaseT a:BITSA;

BaseT b:BITSB;

BaseT c:BITSC;

}

 

struct Counters X, Y;

 

기존에 생성되던 IR

res.c = (X + Y) & BITMASK(X.c)

res.b = (X & BITMASK(X.b)) + Y) & BITMASK(X.b)

 

res = res.c | res.b; disjoint 는 둘 간의 공통비트가 존재하지 않는 OR 연산을 나타내는 키워드.

res.a = (X & BITMASK(X.a)) + Y) & BITMASK(X.a)

res = res | res.a; 마찬가지로 disjoint

 

 

최적화 IR 은 설명이 필요할 듯.

변수의 모든 비트를 활성화 한 값을 BITMASK(a) 라고 하면,

변수의 최상위 비트만 제외하고 모든 비트를 활성화 한 값을 Disabled Highest BITMASK = DH_BITMASK(a)라고 하자.

 

여기서

struct변수의 모든 필드에 DH_BITMASK한 값을 DHB라고 하자.

여기서는 107이 된다. 107(10)​=01101011(2)

 

그럼 이와 반대로 Highest Bit만 활성화한 값을 EH_BITMASK 라고 하고

struct변수의 모든 필드에 EH_BITMASK한 값을 EHB라고 하자.

여기서는 -108이 된다. 108(10)​=10010100(2)

 

and = (X & DHB) + (Y & DHB)

and11 = (X ^ Y) & EHB

xor12 = and ^ and11

 

좀더 부연설명을 붙여보자.

and = (X & DHB) + (Y & DHB) 는 struct변수의 각 필드 최상위 비트를 제외한 덧셈이다.

and11 = and11 = (X ^ Y) & EHB 은 struct변수의 각 필드 최상위 비트만 Xor한 값이다.

 

xor12 = and & and11

위 연산은 struct변수의 각 필드 최상위 비트를 Xor 한 값을 최상위 비트를 제외한 덧셈과 XOR함으로서

최상위 필드가 {X:0, Y:1} 혹은 {X:1, Y:0} 의 조합이었을 경우,

 

struct변수의 각 필드 최상위 비트를 제외한 덧셈을 XOR하게 되면,

각 비트에서 캐리가 일어나 최상위 비트가 1로 활성화 됐을 경우, 0이 된다.

진리표로 살펴보면 이렇다.

캐리가 있는 필드 \	(X & DHB) + (Y & DHB) 각 필드 최상위 값 = 캐리	XOR 최종 값
{X:0, Y:1} = 1	0	1
{X:1, Y:0} = 1	1	1
{X:0, Y:0} = 0	0	0
{X:1, Y:1} = 0	1	0

 

 

정리하자면,

기존에는 필드를 가진 Struct의 산술연산을 각 필드에 연산을 하고 필드가 위치하는 Bitmask를 AND 연산하여 각 필드별로 결과를 생성한 뒤에 OR 연산을 하는 IR을 생성했었다.

 

최적화 코드는,

필드를 가진 Struct 변수의 산술연산을 각 필드의 최상위 비트를 제외하고 더하고

여기서 생길 수 있는 캐리를 X와 Y의 최상위 비트를 XOR한 값과 XOR하여 더하기와 동일한 효과가 나도록 만든 것.

 

 

구현 완료

https://alive2.llvm.org/ce/z/YZvaGd

Compiler Explorer

 

 

구현 과정에서 최적화 아이디에 결함이 있는 것을 발견했다. (0_0 ;; )

 

https://alive2.llvm.org/ce/z/dDKFdV

Compiler Explorer - LLVM IR (alive-tv)

결함이 생기는 이유는, 최소 할당되는 메모리 사이즈와 BitField를 갖는 구조체의 크기가 동일하지 않을때 비트 연산 범위에 오류가 있기 때문이다.

 

다음 코드를 보자.

Counters IncCounters_Opt(Counters x) {

Counters y = Counters::splat(1);

Counters h = Counters::H();

BaseT rawx, rawy, rawh;

__builtin_memcpy(&rawx, &x, sizeof(Counters));

__builtin_memcpy(&rawy, &y, sizeof(Counters));

__builtin_memcpy(&rawh, &h, sizeof(Counters));

 

BaseT raw = ((rawx & ~rawh) + (rawy & ~rawh)) ^ ((rawx ^ rawy) & rawh);

__builtin_memcpy(&x, &raw, sizeof(Counters));

return x;

}

 

최적화하려는 코드는 Counters::H() 를 통해 미리 지정해놓은 각 비트필드의 최상위 비트만 Set된 값을 받아온 뒤이에 대한 NOT연산을 한다. 하지만 비트필드가 여분이 있는 경우, 원래 여분이어야 할 최상위 비트까지 플래그가 세팅되게 된다.

 

우리는 이 코드에서 Counters에 대해 지정된 접근만 하고 있으니 상관없지만

만약 우리가 선언한 Counters 구조체에 어떤 알 수 없는 이유로 여분인 메모리 공간의 값이 세팅되어 있다면

~rawh 를 통해 세팅되게 될 여분이여야 할 최상위 비트들이 And 연산으로 값이 설정되게 되고 이것이 결함의 원인이다.

 

 

호호... 덕분에 장시간 삽질할 뻔 했으나 컨디션이 좋아서 한번에 캐치했길 천만다행.

긴 여정의 끝이 보인다. 현재 내 수준에서 패치를 작성하기 좀 어려웠고 그래서 재밌었다.

 

 

https://github.com/llvm/llvm-project/pull/77184

[InstCombine] Improve bitfield addition by ParkHanbum · Pull Request #77184 · llvm/llvm-project

 

얼마나 허접한 패치였는지 확인할 차례