Souper says:

; Function: fn3
%0:i32 = var 
%1:i32 = and 1:i32, %0
%2:i1 = eq 0:i32, %1
%3:i1 = xor 1:i1, %2
%4:i1 = ne 0:i32, %1
%5:i1 = and %3, %4
%6:i1 = or %5, %2
cand %6 1:i1

COMMAND: /home/regehr/souper/build/souper -stp-path=/usr/local/bin/stp reduce_512/foo.bc

LLVM says:

define i32 @fn1(i32 %p1) #0 {
entry:
  %cmp = icmp eq i32 %p1, 0
  br i1 %cmp, label %cond.end, label %cond.false

cond.false:                                       ; preds = %entry
  %rem = srem i32 1, %p1
  br label %cond.end

cond.end:                                         ; preds = %entry, %cond.false
  %cond = phi i32 [ %rem, %cond.false ], [ 0, %entry ]
  ret i32 %cond
}
define void @fn3() #1 {
entry:
  %0 = load i32* @a, align 4, !tbaa !1
  %and = and i32 %0, 1
  %cmp.i = icmp eq i32 %and, 0
  %phitmp = icmp ne i32 %and, 0
  %not.cond = xor i1 %cmp.i, true
  %and.cond = and i1 %phitmp, %not.cond
  %or.cond = or i1 %cmp.i, %and.cond
  %conv = zext i1 %or.cond to i32
  tail call void (i32, ...)* bitcast (void (...)* @fn2 to void (i32, ...)*)(i32 %conv) #3
  ret void
}

COMMAND: /home/regehr/souper/third_party/llvm/Debug/bin/clang -c -w -emit-llvm -O3 reduce_512/foo.c -o reduce_512/foo.bc

C source code:

int a;
int fn1(p1) { return p1 == 0 ? 0 : 1 % p1; }

void fn2();
void fn3() {
  int b = fn1(!0 & a);
  fn2(b == 0);
}

x86-64 from LLVM:

fn1:                                    # @fn1
	xorl	%eax, %eax
	testl	%edi, %edi
	je	.LBB0_2
	movl	$1, %eax
	xorl	%edx, %edx
	idivl	%edi
	movl	%edx, %eax
.LBB0_2:                                # %cond.end
	retq
fn3:                                    # @fn3
	movl	$1, %edi
	xorl	%eax, %eax
	jmp	fn2                     # TAILCALL
.Ltmp1:

COMMAND: /home/regehr/souper/third_party/llvm/Debug/bin/clang -w -O3 reduce_512/foo.c -S -o -

x86-64 from GCC:

fn1:
	xorl	%edx, %edx
	testl	%edi, %edi
	je	.L2
	movl	$1, %eax
	cltd
	idivl	%edi
.L2:
	movl	%edx, %eax
	ret
fn3:
.LFB1:
	movl	$1, %edi
	xorl	%eax, %eax
	jmp	fn2
.LFE1:

COMMAND: gcc -w -O3 reduce_512/foo.c -S -o -