[X86] Fix `FindSingleBitChange` to handle NOT(V) where V is not an Instruction

[goldstein.w.n]

Summary

Was previously buggy to assume that NOT'd Value was always an
instruction. If the NOT'd value is not an Instruction, we should just
return as its either a constant, in which can we will re-run the logic
after constant-folding, or its a type we can't evaluate anyways.

This is a follow up to: D140939

[goldstein.w.n]

1. Verified that all the tests failed before this commit (and pass afterwards).
2. Is revert of D140939 and D142166 preferable? I've already swung and missed so LMK if it's better.

[pengfei]

Thanks for the fix! I think you can quick land this to solve the problem. I don't see any difference if revert the previous patch and then reland with this diff.

[RKSimon]

LGTM

[goldstein.w.n]

In D142339#4072774, @pengfei wrote:

Thanks for the fix! I think you can quick land this to solve the problem. I don't see any difference if revert the previous patch and then reland with this diff.

Thanks, will push shortly.

llvm/lib/Target/X86/X86ISelLowering.cpp

static std::pair<Value *, BitTestKind> FindSingleBitChange(Value *V) {
   if (I) {
     bool Not = false;
     // Check if we have a NOT
     Value *PeekI;
     if (match(I, m_c_Xor(m_Value(PeekI), m_AllOnes())) ||
         match(I, m_Sub(m_AllOnes(), m_Value(PeekI)))) {
       Not = true;
       I = dyn_cast<Instruction>(PeekI);
-      assert(I != nullptr);
+
+      // If I is constant, it will fold and we can evaluate later. If its an
+      // argument or something of that nature, we can't analyze.
+      if (I == nullptr)
+        return {nullptr, UndefBit};
     }
     // We can only use 1 << X without more sophisticated analysis. C << X where
     // C is a power of 2 but not 1 can result in zero which cannot be translated
     // to bittest. Likewise any C >> X (either arith or logical) can be zero.
     if (I->getOpcode() == Instruction::Shl) {
       // Todo(1): The cmpxchg case is pretty costly so matching `BLSI(X)`, `X &
       // -X` and some other provable power of 2 patterns that we can use CTZ on
       // may be profitable.

llvm/test/CodeGen/X86/atomic-rm-bit-test-64.ll

if.then:                                          ; preds = %entry
   %arrayidx = getelementptr inbounds i64, ptr %v, i64 4
   %1 = load i64, ptr %arrayidx, align 8
   br label %return
 
 return:                                           ; preds = %entry, %if.then
   %retval.0 = phi i64 [ %1, %if.then ], [ 123, %entry ]
   ret i64 %retval.0
 }
+
+define i64 @atomic_and_with_not_arg(ptr %v, i64 %c) nounwind {
+; CHECK-LABEL: atomic_and_with_not_arg:
+; CHECK:       # %bb.0: # %entry
+; CHECK-NEXT:    movq $-1, %rcx
+; CHECK-NEXT:    movq (%rdi), %rax
+; CHECK-NEXT:    .p2align 4, 0x90
+; CHECK-NEXT:  .LBB54_1: # %atomicrmw.start
+; CHECK-NEXT:    # =>This Inner Loop Header: Depth=1
+; CHECK-NEXT:    movq %rax, %rdx
+; CHECK-NEXT:    orq %rcx, %rdx
+; CHECK-NEXT:    lock cmpxchgq %rdx, (%rdi)
+; CHECK-NEXT:    jne .LBB54_1
+; CHECK-NEXT:  # %bb.2: # %atomicrmw.end
+; CHECK-NEXT:    retq
+  entry:
+  %0 = xor i64 0, -1
+  %1 = atomicrmw or ptr %v, i64 %0 monotonic, align 8
+  ret i64 %1
+}

llvm/test/CodeGen/X86/atomic-rm-bit-test.ll

 entry:
   %0 = and i32 %c, 7
   %shl = shl nuw nsw i32 1, %0
   %1 = atomicrmw xor ptr %v, i32 %shl monotonic, align 4
   %and = and i32 %1, %1
   %and1 = and i32 %and, %shl
   ret i32 %and1
 }
+
+define i32 @atomic_xor_with_not_arg(ptr %v, i32 %c) nounwind {
+; X86-LABEL: atomic_xor_with_not_arg:
+; X86:       # %bb.0: # %entry
+; X86-NEXT:    pushl %esi
+; X86-NEXT:    movl {{[0-9]+}}(%esp), %ecx
+; X86-NEXT:    movl {{[0-9]+}}(%esp), %edx
+; X86-NEXT:    notl %edx
+; X86-NEXT:    movl (%ecx), %eax
+; X86-NEXT:    .p2align 4, 0x90
+; X86-NEXT:  .LBB123_1: # %atomicrmw.start
+; X86-NEXT:    # =>This Inner Loop Header: Depth=1
+; X86-NEXT:    movl %eax, %esi
+; X86-NEXT:    xorl %edx, %esi
+; X86-NEXT:    lock cmpxchgl %esi, (%ecx)
+; X86-NEXT:    jne .LBB123_1
+; X86-NEXT:  # %bb.2: # %atomicrmw.end
+; X86-NEXT:    popl %esi
+; X86-NEXT:    retl
+;
+; X64-LABEL: atomic_xor_with_not_arg:
+; X64:       # %bb.0: # %entry
+; X64-NEXT:    notl %esi
+; X64-NEXT:    movl (%rdi), %eax
+; X64-NEXT:    .p2align 4, 0x90
+; X64-NEXT:  .LBB123_1: # %atomicrmw.start
+; X64-NEXT:    # =>This Inner Loop Header: Depth=1
+; X64-NEXT:    movl %eax, %ecx
+; X64-NEXT:    xorl %esi, %ecx
+; X64-NEXT:    lock cmpxchgl %ecx, (%rdi)
+; X64-NEXT:    jne .LBB123_1
+; X64-NEXT:  # %bb.2: # %atomicrmw.end
+; X64-NEXT:    retq
+entry:
+  %0 = xor i32 %c, -1
+  %1 = atomicrmw xor ptr %v, i32 %0 monotonic, align 4
+  ret i32 %1
+}
+
+define i16 @atomic_or_with_not_arg(ptr %v, i16 %c) nounwind {
+; X86-LABEL: atomic_or_with_not_arg:
+; X86:       # %bb.0: # %entry
+; X86-NEXT:    pushl %esi
+; X86-NEXT:    movl {{[0-9]+}}(%esp), %ecx
+; X86-NEXT:    movl {{[0-9]+}}(%esp), %edx
+; X86-NEXT:    notl %edx
+; X86-NEXT:    movzwl (%ecx), %eax
+; X86-NEXT:    .p2align 4, 0x90
+; X86-NEXT:  .LBB124_1: # %atomicrmw.start
+; X86-NEXT:    # =>This Inner Loop Header: Depth=1
+; X86-NEXT:    movl %eax, %esi
+; X86-NEXT:    orl %edx, %esi
+; X86-NEXT:    # kill: def $ax killed $ax killed $eax
+; X86-NEXT:    lock cmpxchgw %si, (%ecx)
+; X86-NEXT:    # kill: def $ax killed $ax def $eax
+; X86-NEXT:    jne .LBB124_1
+; X86-NEXT:  # %bb.2: # %atomicrmw.end
+; X86-NEXT:    # kill: def $ax killed $ax killed $eax
+; X86-NEXT:    popl %esi
+; X86-NEXT:    retl
+;
+; X64-LABEL: atomic_or_with_not_arg:
+; X64:       # %bb.0: # %entry
+; X64-NEXT:    notl %esi
+; X64-NEXT:    movzwl (%rdi), %eax
+; X64-NEXT:    .p2align 4, 0x90
+; X64-NEXT:  .LBB124_1: # %atomicrmw.start
+; X64-NEXT:    # =>This Inner Loop Header: Depth=1
+; X64-NEXT:    movl %eax, %ecx
+; X64-NEXT:    orl %esi, %ecx
+; X64-NEXT:    # kill: def $ax killed $ax killed $eax
+; X64-NEXT:    lock cmpxchgw %cx, (%rdi)
+; X64-NEXT:    # kill: def $ax killed $ax def $eax
+; X64-NEXT:    jne .LBB124_1
+; X64-NEXT:  # %bb.2: # %atomicrmw.end
+; X64-NEXT:    # kill: def $ax killed $ax killed $eax
+; X64-NEXT:    retq
+entry:
+  %0 = xor i16 %c, -1
+  %1 = atomicrmw or ptr %v, i16 %0 monotonic, align 2
+  ret i16 %1
+}
+
+define i8 @atomic_and_with_not_arg(ptr %v, i8 %c) nounwind {
+; X86-LABEL: atomic_and_with_not_arg:
+; X86:       # %bb.0: # %entry
+; X86-NEXT:    movl {{[0-9]+}}(%esp), %ecx
+; X86-NEXT:    movzbl {{[0-9]+}}(%esp), %edx
+; X86-NEXT:    notb %dl
+; X86-NEXT:    movzbl (%ecx), %eax
+; X86-NEXT:    .p2align 4, 0x90
+; X86-NEXT:  .LBB125_1: # %atomicrmw.start
+; X86-NEXT:    # =>This Inner Loop Header: Depth=1
+; X86-NEXT:    movb %al, %ah
+; X86-NEXT:    orb %dl, %ah
+; X86-NEXT:    lock cmpxchgb %ah, (%ecx)
+; X86-NEXT:    jne .LBB125_1
+; X86-NEXT:  # %bb.2: # %atomicrmw.end
+; X86-NEXT:    retl
+;
+; X64-LABEL: atomic_and_with_not_arg:
+; X64:       # %bb.0: # %entry
+; X64-NEXT:    notb %sil
+; X64-NEXT:    movzbl (%rdi), %eax
+; X64-NEXT:    .p2align 4, 0x90
+; X64-NEXT:  .LBB125_1: # %atomicrmw.start
+; X64-NEXT:    # =>This Inner Loop Header: Depth=1
+; X64-NEXT:    movl %eax, %ecx
+; X64-NEXT:    orb %sil, %cl
+; X64-NEXT:    lock cmpxchgb %cl, (%rdi)
+; X64-NEXT:    jne .LBB125_1
+; X64-NEXT:  # %bb.2: # %atomicrmw.end
+; X64-NEXT:    retq
+entry:
+  %0 = xor i8 %c, -1
+  %1 = atomicrmw or ptr %v, i8 %0 monotonic, align 1
+  ret i8 %1
+}
+
+define weak_odr void @atomic_and_with_not_const() nounwind {
+; X86-LABEL: atomic_and_with_not_const:
+; X86:       # %bb.0: # %entry
+; X86-NEXT:    retl
+;
+; X64-LABEL: atomic_and_with_not_const:
+; X64:       # %bb.0: # %entry
+; X64-NEXT:    retq
+  entry:
+  br label %if.end19
+cont11:  ; No predecessors!
+  %not = xor i32 0, -1
+  %0 = atomicrmw and ptr null, i32 %not monotonic, align 4
+  %and13 = and i32 %0, 0
+  br label %if.end19
+if.end19:  ; preds = %cont11, %entry
+  ret void
+}