Simplification Comparison for (a | b) ? (a ^ b) : (a & b) etc. (Clang13 vs Clang trunk

이번에 살펴볼 이슈는 이겁니다.

 

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

Simplification Comparison for `(a | b) ? (a ^ b) : (a & b)` etc. (Clang13 vs Clang trunk) · Issue #71792 · llvm/llvm-project

 

일단 스포부터 하면 문제가 발생하는 커밋은 이겁니다.

https://github.com/llvm/llvm-project/commit/f0071d43e4d30a0bc224020abb52fa77054d2520

[InstCombine] add use check to fold of bitwise logic with cast ops · llvm/llvm-project@f0071d4

 

근데 이 커밋은 설명에서 보이듯

This was shown as a potential regression in D126040.

 

이라고 되어 있습니다. (@_@?)
또 이런 커밋은 처음보기 때문에 한번 살펴보겠습니다.

 

https://reviews.llvm.org/D126040

⚙ D126040 [InstCombine] Fold a mul with bool value into and

 

위의 토의 중간에 문제가 생기는 커밋이 참조되어 있습니다.
정확한 의미는 아직 모릅니다.

 

 

다음은 분석에 관한 기록입니다.

 

 

문제가 생기는 코드

#include <stdbool.h>
bool test1(bool a, bool b)
{
    return (a | b) ? (a ^ b) : (a & b);
}

 

Clang 14 이전 버전

; Function Attrs: mustprogress nofree norecurse nosync nounwind readnone uwtable willreturn
define dso_local zeroext i1 @test1(i1 noundef zeroext %a, i1 noundef zeroext %b) local_unnamed_addr #0 {
entry:
  %xor7 = xor i1 %a, %b
  ret i1 %xor7
}

 

이후 버전

; Function Attrs: mustprogress nofree norecurse nosync nounwind willreturn memory(none)
define dso_local zeroext i1 @test1(i1 noundef zeroext %a, i1 noundef zeroext %b) local_unnamed_addr #0 {
entry:
  %conv = zext i1 %a to i32
  %conv3 = zext i1 %b to i32
  %or = or i32 %conv3, %conv
  %tobool4.not = icmp eq i32 %or, 0
  %xor = xor i32 %conv3, %conv
  %and = and i32 %conv3, %conv
  %cond = select i1 %tobool4.not, i32 %and, i32 %xor
  %tobool13 = icmp ne i32 %cond, 0
  ret i1 %tobool13
}

 

 

 

과정을 살펴보면 다음과 같습니다.

 

14 이전 버전

*** IR Dump After DeadArgumentEliminationPass on [module] ***
; ModuleID = 'p.ll'
source_filename = "p.c"
target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
target triple = "x86_64-unknown-linux-gnu"

; Function Attrs: nounwind uwtable
define dso_local zeroext i1 @test1(i1 noundef zeroext %a, i1 noundef zeroext %b) local_unnamed_addr #0 {
entry:
  %frombool = zext i1 %a to i8
  %frombool1 = zext i1 %b to i8
  %conv = zext i1 %a to i32
  %conv3 = zext i1 %b to i32
  %or = or i32 %conv, %conv3
  %tobool4 = icmp ne i32 %or, 0
  br i1 %tobool4, label %cond.true, label %cond.false

cond.true:                                        ; preds = %entry
  %xor = xor i32 %conv, %conv3
  br label %cond.end

cond.false:                                       ; preds = %entry
  %and = and i32 %conv, %conv3
  br label %cond.end

cond.end:                                         ; preds = %cond.false, %cond.true
  %cond = phi i32 [ %xor, %cond.true ], [ %and, %cond.false ]
  %tobool13 = icmp ne i32 %cond, 0
  ret i1 %tobool13
}

attributes #0 = { nounwind uwtable "frame-pointer"="none" "min-legal-vector-width"="0" "no-trapping-math"="true" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+cx8,+fxsr,+mmx,+sse,+sse2,+x87" "tune-cpu"="generic" }

!llvm.module.flags = !{!0, !1}
!llvm.ident = !{!2}

!0 = !{i32 1, !"wchar_size", i32 4}
!1 = !{i32 7, !"uwtable", i32 1}
!2 = !{!"clang version 14.0.6 (https://github.com/llvm/llvm-project.git f28c006a5895fc0e329fe15fead81e37457cb1d1)"}
*** IR Dump After InstCombinePass on test1 ***
; Function Attrs: nounwind uwtable
define dso_local zeroext i1 @test1(i1 noundef zeroext %a, i1 noundef zeroext %b) local_unnamed_addr #0 {
entry:
  %or5 = or i1 %a, %b
  br i1 %or5, label %cond.true, label %cond.false

cond.true:                                        ; preds = %entry
  %xor7 = xor i1 %a, %b
  br label %cond.end

cond.false:                                       ; preds = %entry
  %and6 = and i1 %a, %b
  br label %cond.end

cond.end:                                         ; preds = %cond.false, %cond.true
  %cond.in = phi i1 [ %xor7, %cond.true ], [ %and6, %cond.false ]
  ret i1 %cond.in
}

 

 

이후 버전

; *** IR Dump After PromotePass on test1 ***
; Function Attrs: nounwind uwtable
define dso_local zeroext i1 @test1(i1 noundef zeroext %a, i1 noundef zeroext %b) local_unnamed_addr #0 {
entry:
  %frombool = zext i1 %a to i8
  %frombool1 = zext i1 %b to i8
  %conv = zext i1 %a to i32
  %conv3 = zext i1 %b to i32
  %or = or i32 %conv, %conv3
  %tobool4 = icmp ne i32 %or, 0
  br i1 %tobool4, label %cond.true, label %cond.false

cond.true:                                        ; preds = %entry
  %xor = xor i32 %conv, %conv3
  br label %cond.end

cond.false:                                       ; preds = %entry
  %and = and i32 %conv, %conv3
  br label %cond.end

cond.end:                                         ; preds = %cond.false, %cond.true
  %cond = phi i32 [ %xor, %cond.true ], [ %and, %cond.false ]
  %tobool13 = icmp ne i32 %cond, 0
  ret i1 %tobool13
}
; *** IR Dump After InstCombinePass on test1 ***
; Function Attrs: nounwind uwtable
define dso_local zeroext i1 @test1(i1 noundef zeroext %a, i1 noundef zeroext %b) local_unnamed_addr #0 {
entry:
  %conv = zext i1 %a to i32
  %conv3 = zext i1 %b to i32
  %or = or i32 %conv, %conv3
  %tobool4.not = icmp eq i32 %or, 0
  br i1 %tobool4.not, label %cond.false, label %cond.true

cond.true:                                        ; preds = %entry
  %xor = xor i32 %conv, %conv3
  br label %cond.end

cond.false:                                       ; preds = %entry
  %and = and i32 %conv, %conv3
  br label %cond.end

cond.end:                                         ; preds = %cond.false, %cond.true
  %cond = phi i32 [ %xor, %cond.true ], [ %and, %cond.false ]
  %tobool13 = icmp ne i32 %cond, 0
  ret i1 %tobool13
}

 

 

보이는 것처럼 14이전 버전에서는

  %conv = zext i1 %a to i32
  %conv3 = zext i1 %b to i32
  %or = or i32 %conv, %conv3

 

위 부분이

  %or5 = or i1 %a, %b

 

위처럼 바뀐걸 알 수 있습니다.

 

그러나 InstCombine Pass는 특성상 Visitor 패턴으로 작성되어 선형적 코드 흐름을 만들지 않습니다. UFTRACE를 통해 코드 흐름을 비교하는 방식을 이번에는 사용할 수 없습니다. 이번에는 디버깅메시지를 같이 보도록 하겠습니다.

 

build-llvm-14/bin/opt -passes=instcombine temp.ll -debug

 

IC: DCE:   %frombool1 = zext i1 %b to i8 IC: DCE:   %frombool = zext i1 %a to i8 IC: Visiting:   %conv = zext i1 %a to i32 IC: Visiting:   %conv3 = zext i1 %b to i32 IC: Visiting:   %or = or i32 %conv, %conv3 ADD DEFERRED:   %or1 = or i1 %a, %b IC: Old =   %or = or i32 %conv, %conv3     New =   <badref> = zext i1 %or1 to i32 ADD:   %or = zext i1 %or1 to i32 IC: ERASE   %0 = or i32 %conv, %conv3 ADD DEFERRED:   %conv = zext i1 %a to i32 ADD DEFERRED:   %conv3 = zext i1 %b to i32 ADD:   %conv3 = zext i1 %b to i32 ADD:   %conv = zext i1 %a to i32 ADD:   %or1 = or i1 %a, %b IC: Visiting:   %or1 = or i1 %a, %b IC: Visiting:   %conv = zext i1 %a to i32 IC: Visiting:   %conv3 = zext i1 %b to i32 IC: Visiting:   %or = zext i1 %or1 to i32 IC: Visiting:   %tobool4 = icmp ne i32 %or, 0

IC: DCE:   %frombool1 = zext i1 %b to i8 IC: DCE:   %frombool = zext i1 %a to i8 IC: Visiting:   %conv = zext i1 %a to i32 IC: Visiting:   %conv3 = zext i1 %b to i32 IC: Visiting:   %or = or i32 %conv, %conv3 IC: Visiting:   %tobool4 = icmp ne i32 %or, 0

14이전

15이후

 

위처럼 or instruction visit 하는 과정에서 뭔가 문제가 발생했다는 것을 알 수 있죠.

 

디버거로 visitOr에 BreakPoint를 걸어 해당 구문을 만드는 지점을 찾을때까지 추적하는게 최선인 것 같습니다.

 

그러면 다음 코드에서,

  if (Instruction *CastedOr = foldCastedBitwiseLogic(I))
    return CastedOr;

 

그리고 한번 더 foldCastedBitwiseLogic 을 추적하면 다음 코드에서 차이가 생기는 것을 알 수 있습니다.

 

14 이전

  // fold logic(cast(A), cast(B)) -> cast(logic(A, B))
  if (shouldOptimizeCast(Cast0) && shouldOptimizeCast(Cast1)) {
    Value *NewOp = Builder.CreateBinOp(LogicOpc, Cast0Src, Cast1Src,
                                        I.getName());
    return CastInst::Create(CastOpcode, NewOp, DestTy);
  }

 

15 이후

  // fold logic(cast(A), cast(B)) -> cast(logic(A, B))
  if ((Cast0->hasOneUse() || Cast1->hasOneUse()) &&
      shouldOptimizeCast(Cast0) && shouldOptimizeCast(Cast1)) {

 

이 차이로 인해 문제는 발생합니다.

 

이 코드가 추가된 커밋은 글의 도입부에 링크를 걸어놨으니 추가 설명은 하지 않겠습니다.
대신 이 코드에 대한 설명을 하자면 주석처럼

%conv = zext i1 %a to i32
%conv3 = zext i1 %b to i32
%or = or i32 %conv, %conv3

 

위와 같은 코드를 다음처럼 바꿔주는 겁니다.

 %or1 = or i1 %a, %b
 %or = zext i1 %or1 to i32

 

두 번 형변을 할 것을 한 번으로 줄일 수 있죠.

 

문제를 확인하고 문제가 발생하는 이유를 이해했으니 해결책은 두 가지 정도로 생각하고 있습니다.

1. 기존의 코드를 제거한다.

2. AndOrXor 인 경우 operand가 형변일 경우 대상 변수를 먼저 연산하고 이후 형변하는 과정을 새로 만든다.

 

 

후속.

 

문제를 파악하고 이슈에 올렸듯이, 문제가 발생하기 시작한 커밋은 뚜렷한 목적 의식이 있었습니다. 해서 다음과 같이 LLVM Discourse 에 의견을 물었습니다.

https://discourse.llvm.org/t/what-means-potential-regression/74848/7

What means "potential regression"?

커밋 내용이 어찌됐든, 해당 커밋의 내용은 논리적으로 부합한다는 답변이 달렸습니다.

때문에, 약간 더 복잡하게 해결해야만 하게 됐습니다.

 

기존의 최적화는두단계로구성되어있습니다. 

and/or/xor (cast (A)) (cast (B))
-> %res =  and/or/xor A B
-> cast (%res)

1. 위처럼 형변 후 연산하는 것을, 연산 한 뒤 형변을 하여 형변 수를 줄이는 것.

 

%or5 = or i1 %a, %b
%xor7 = xor i1 %a, %b
%spec.select = select i1 %or5, i1 %xor7, i1 false
ret i1 %spec.select
-> %xor7 = xor i1 %a, %b
-> ret i1 %xor7

2. 이렇게저렇게 뚝딱뚝딱해서 결과적으로 논리적 단순화를 하는 것.

 

이 경우는 `(a | b) ? (a ^ b) : (a & b)` 이라는 연산을 단순화 하는데 i1 이기 때문에 가능한 것 입니다.

a	b	a | b	a ^ b	a & b
0	0	0	0	0
0	1	1	1	0
1	0	1	1	0
1	1	1	0	1

 

위 진리표에 따라, `(a | b) ? (a ^ b) : (a & b)`  는 `(a ^ b)` 로 단순화 할 수 있습니다.

지금의 문제는 두 번째 단계는 첫 번째 단계가 거쳐야만 발동된다는 점이고, 동시에 첫 단계는 기존처럼 논리 연산자에서 먼저 연산 후 형변을 하도록 바꿀 수 없도록 한 제약이 추가된 것 입니다.

 

그렇지 않으면 다음처럼 IR이 늘어나는 경우가 생깁니다.

%conv = zext i1 %a to i32   tail call void @use(i32 %conv)   %conv3 = zext i1 %b to i32   tail call void @use(i32 %conv3)   %or1 = and i1 %a, %b   %or = zext i1 %or1 to i32   tail call void @use(i32 %or)   %r = xor i1 %or1, true   ret i1 %r	%conv = zext i1 %a to i32   tail call void @use(i32 %conv)   %conv3 = zext i1 %b to i32   tail call void @use(i32 %conv3)   %or = and i32 %conv3, %conv   tail call void @use(i32 %or)   %r = icmp eq i32 %or, 0   ret i1 %r
15이전	15이후

 

때문에 좀더 경우의 수를 좁혀서,
'형변 전에 논리 연산을 수행하는 경우에 실익이 있는 경우'로 좁혀서,
실익이 있으면 수행을 하고, 없으면 수행을 하지 않는 방식으로 변경했습니다.

 

예를 들면 다음과 같이 최소화한 예제의 경우에서

define dso_local i1 @test1(i1 %a, i1 %b) {
entry:
%conv = zext i1 %a to i32
call void @use(i32 %conv)
%conv3 = zext i1 %b to i32
call void @use(i32 %conv3)
%or = and i32 %conv, %conv3  // icmp 단독사용
%r = icmp eq i32 %or, 0      // 변경시 이득 
ret i1 %r
}

 

다음과 같이 변경하는 것 입니다.

  %or1 = and i1 %a, %b
  %r = xor i1 %or1, true

 

이를 정리하여 다음과 같은 경우의 수 표를 작성해봅니다.

(A & B) == 0	(A & B) == 0	!(A & B)	(A & B) ^ 1
(A & B) != 1
(A & B) != 0	(A & B) == 1	(A & B)
(A & B) == 1

 

그리고 이와 같이 작성한 표 대로 변환해봤을때 정합한지를 ALIVE2로 확인할 수 있습니다.

https://alive2.llvm.org/ce/z/c-nrLX

Compiler Explorer

 

해서 구현한 코드는 다음과 같습니다.

https://github.com/ParkHanbum/mystudy/commit/d57da2c119cdbbc98fd52b5378bb84b352cb90a5

temp-patch · ParkHanbum/mystudy@d57da2c

 

위의 코드는 공부 목적으로 이런 저런 코드를 구현해 볼 수 있는 제 개인 프로젝트 입니다.

실제 llvm 에 구현을 하게 되면 매번 코드를 수정할 때마다 빌드를 하느라 시간이 너무 많이 걸립니다.
이런 방식으로 시간도 줄이고, 디버깅도 편의를 도모할 수 있습니다~

 

이것으로 1번 문제를 해결한 것 같습니다.

 

https://github.com/ParkHanbum/llvm-project/commit/5153499eca5ac7a33587e2220bdef8b3ae231ff8

[InstCombine] Simplify icmp eq/ne which has operand casted i1 · ParkHanbum/llvm-project@5153499

XOR Combine Pass

 

 

InstCombineCompares.cpp:6934

(gdb) p I.getParent()->dump()
entry:
  %conv = zext i1 %a to i32
  call void @use(i32 %conv)
  %conv3 = zext i1 %b to i32
  call void @use(i32 %conv3)
  %xor = xor i32 %conv, %conv3
  %r = icmp eq i32 %xor, 0
  ret i1 %r

(gdb) p Res->dump()
  <badref> = icmp eq i32 %conv, %conv3

 

3381         return new ICmpInst(Pred, BOp0, BOp1);
(gdb) 
0x0000555559b0b49c 3381         return new ICmpInst(Pred, BOp0, BOp1);

 

 

InstCombineCompares.cpp:7006

(gdb) p I.getParent()->dump()
entry:
  %conv = zext i1 %a to i32
  call void @use(i32 %conv)
  %conv3 = zext i1 %b to i32
  call void @use(i32 %conv3)
  %r = icmp eq i32 %conv, %conv3
  ret i1 %r

(gdb) p R->dump()
  <badref> = icmp eq i1 %a, %b

 

InstCombineCompares.cpp:6862

(gdb) p I.getParent()->dump()
entry:
  %conv = zext i1 %a to i32
  call void @use(i32 %conv)
  %conv3 = zext i1 %b to i32
  call void @use(i32 %conv3)
  %0 = xor i1 %a, %b
  %r = icmp eq i1 %a, %b
  ret i1 %r

(gdb) p Res->dump()
  <badref> = xor i1 %0, true

 

 

이제 2번 문제를 해결해 봅시다!

2번 문제를 요약하면 다음과 같습니다.

 

// (icmp eq (select i1 (and/or/xor X, Y), i1 (and/or/xor X, Y), i1 (and/or/xor X, Y)), 0/1)

 

// (icmp nq (select i1 (and/or/xor X, Y), i1 (and/or/xor X, Y), i1 (and/or/xor X, Y)), 0/1)

 

 

X, Y 가 i1 이라고 할 때 위와 같은 IR을 조합하는 것이죠.

 

Alive2 Proof 를 만들어봅니다.

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

https://alive2.llvm.org/ce/z/9jidcw

Compiler Explorer

 

위의 Proof 중이 하나의 케이스만 가져와서 설명을 해보겠습니다.

; (A^B)==1 & (A|B)
; (A^B)==0 & (A&B)
define i1 @src_select_xor1_or_and(i1 %x, i1 %y) {
  %xor = xor i1 %x, %y
  %xor1 = icmp ne i1 %xor, 0
  %or = or i1 %x, %y
  %and = and i1 %x, %y
  %cond = select i1 %xor1, i1 %or, i1 %and
  ret i1 %cond
}
define i1 @tgt_select_xor1_or_and(i1 %x, i1 %y) {
  %r = or i1 %x, %y
  ret i1 %r
}

 

주석으로 달아놓은 것처럼, 위의 IR은 A^B의 값에 따라 다음의 진리표를 갖게 됩니다.

 

	A	B	A|B
; (A^B)==1	0	1	1
	1	0	1
	A	B	A&B
; (A^B)==0	0	0	0
	1	1	1

 

정리하자면 우리는 다음과 같은 진리표를 생성할 수 있으면 됩니다.

 

	A	B
; (A^B)==1	0	1	1
	1	0	1
; (A^B)==0	0	0	0
	1	1	1

 

그리고 위의 진리표는 or 연산의 진리표와 같습니다. 고로 위 IR은 or 연산으로 대치 가능합니다.

 

https://github.com/llvm/llvm-project/commit/76af103c37a5ff18930011de4d3c05cc50193b2e

[InstCombine] Simplify select if it combinated `and/or/xor` · llvm/llvm-project@76af103

 

이런 식으로 and/or/xor 비트연산으로 구성된 select 문을 단순화 할 수 있습니다.

 

흥미롭게도 이 방식을 통하면 1번 문제를 굳이 해결할 필요 없이 목표를 달성하게 됩니다.

그러나 여전히 이런 비트연산 구성의 모음에 대한 최적화가 좋은 방향인지는 모르겠습니다.

 

 

추가.

i1 혹은 (X|Y)==0 일 때의 비트연산은 이전에도 처리해주고 있었습니다.

 

어떤 비트에서건 X | Y == 0 이면 X == 0, Y == 0 입니다. 그러므로 이런 경우에 한해 propagation을 하고 최적화를 수행할 수 있습니다.

 

   %or = or i32 %a, %b
  %or0 = icmp eq i32 %or, 0
  br i1 %or0, label %cond.true, label %cond.false

cond.true:                                        ; preds = %entry
  %xor7 = xor i32 %a, %b
  br label %cond.end

cond.false:                                       ; preds = %entry
  %and6 = and i32 %a, %b
  br label %cond.end

cond.end:                                         ; preds = %cond.false, %cond.true
  %cond.in = phi i32 [ %xor7, %cond.true ], [ %and6, %cond.false ]
  %r = icmp eq i32 %cond.in, 0
  ret i1 %r

 

위와 같은 IR 이 주어졌을 때, 우리는 X|Y==0 일 때를 다음처럼 처리할 수 있고

  %cond.in = phi i32 [ 0, %cond.true ], [ %and6, %cond.false ]

 

이를 통해 코드는 다음처럼 최적화 되게 됩니다.

  %and61 = and i1 %x, %y
  %0 = xor i1 %and61, true
  ret i1 %0

 

 

그러나 다음처럼, i1 인 경우에만 한정됩니다. i32로 바뀐 경우 최적화가 되지 않습니다.

  %or = or i32 %b, %a
  %tobool.not = icmp eq i32 %or, 0
  %xor = xor i32 %b, %a
  %and = and i32 %b, %a
  %cond = select i1 %tobool.not, i32 %and, i32 %xor
  ret i32 %cond

 

그러나 이는 말이 되지 않습니다. X|Y == 0 인 경우, 어떤 비트의 AND연산도 0이 될 수 밖에 없습니다.

X|Y == 0 인 경우, X == 0 이고 Y == 0 입니다. 여기에 의거해 최적화를 하는게 과거의 최적화 였습니다.

 

그러면 여기서 생각을 좀 더 확장해보겠습니다. 

 

(a | b) ? (a ^ b) : (a & b)

 

위의 연산을 하나의 비트 연산으로 표현하고자 한다면,
(a|b) == 0 일 때의 a^b 와 (a|b) != 0 일 때의 a&b를 모두 표현할 수 있으면 됩니다.

 

그러면 a|b != 0 이 아닐 때는 a^b가 나오면 되고, a|b가 0이면 a&b는 0 이죠.

그러므로 이 식은 a^b 로 귀결됩니다.

 

가장 설명이 쉬운 or의 경우가 이렇습니다.

그러면 and 에 대한 연산은 어떨까요?

 

int test3(int a, int b)
{
    return (a & b) ? (a | b) : (a ^ b);
}

int test4(int a, int b)
{
    return (a & b) ? (a ^ b) : (a | b);
}

 

  %and = and i32 %b, %a
  %tobool.not = icmp eq i32 %and, 0
  %xor = xor i32 %b, %a
  %or = or i32 %b, %a
  %cond = select i1 %tobool.not, i32 %or, i32 %xor
  ret i32 %cond

역시 마찬가지로 최적화 되지 않습니다.

하지만 같은 로직을 적용하면 다음처럼 최적화 할 수 있습니다.

(a & b) ? (a | b) : (a ^ b) -> a | b

(a & b) ? (a ^ b) : (a | b) -> a ^ b

 

(a & b) ? (a | b) : (a ^ b) -> a | b

true : a&b != 0, a | b  -> a|b입니다.

false : a&b == 0, a ^ b -> a!=1, b!=1 이므로 a^b은 a^b입니다.

그러므로 이 삼항연산자는 a|b로 치환 됩니다.

 

(a & b) ? (a ^ b) : (a | b) -> a ^ b

true : a&b != 0, a ^ b  -> a ^ b입니다.

false : a&b == 0, a | b -> a!=1, b!=1 이므로 a|b는 a^b와 같습니다.

그러므로 이 삼항연산자는 a ^ b로 치환 됩니다.

 

 

제가 헤깔려서 적어두지만,

이를 정방향이 아니라 역방향으로 보면 이해가 쉬울 수 있습니다.

 

정 : (a & b) != 0 ? (a ^ b) : (a | b)  ->  a ^ b

역 : a ^ b -> (a & b) != 0 ? (a ^ b) : (a | b)

a ^ b 는

a & b 가 0 이 아닌 a ^ b 이거나 -> 당연

a & b 가 0 인 a | b 이다. ->  a & b == 0  이란 조건이 a | b에서 a b 가 같은 비트를 가진 조건을 소거

때문에 a | b 가 a ^ b 로 치환 가능한 것 입니다.

 

 

https://github.com/llvm/llvm-project/pull/73362#event-12335638652

[InstCombine] Simplify select if it combinated and/or/xor by ParkHanbum · Pull Request #73362 · llvm/llvm-project

https://godbolt.org/z/hffWecddP

Compiler Explorer - C++