[ValueTracking] recognize a 'not' of an assumed condition as false

[spatel]

Summary

I think this is a logical extension of the current checks in computeKnownBitsFromAssume(). Ie, it has negligible cost for the added functionality. But let me know if we need to re-think the whole approach.

This is the reason I didn't have the canonical xor-form of 'not' in the test case for D28337 - it doesn't work without this change.

[majnemer]

lib/Analysis/ValueTracking.cpp

550–551 ↗

(On Diff #83704)

I don't think you want to use the uint64_t constructor here., you probably want to use clearAllBits and setAllBits on the two APInts as needed.

[spatel]

Patch updated:
Use clearAllBits/setAllBits as suggested by David.

[hfinkel]

LGTM

[hfinkel]

You'll also need a corresponding update to AssumptionCache::updateAffectedValues.

[spatel]

In D28485#648132, @hfinkel wrote:

You'll also need a corresponding update to AssumptionCache::updateAffectedValues.

Thanks! I'll update that part, add the select test diff from D28337, and check it in.

llvm/trunk/lib/Analysis/AssumptionCache.cpp

void AssumptionCache::updateAffectedValues(CallInst *CI) {
 
   SmallVector<Value *, 16> Affected;
   auto AddAffected = [&Affected](Value *V) {
     if (isa<Argument>(V)) {
       Affected.push_back(V);
     } else if (auto *I = dyn_cast<Instruction>(V)) {
       Affected.push_back(I);
 
-      if (I->getOpcode() == Instruction::BitCast ||
-          I->getOpcode() == Instruction::PtrToInt) {
-        auto *Op = I->getOperand(0);
+      // Peek through unary operators to find the source of the condition.
+      Value *Op;
+      if (match(I, m_BitCast(m_Value(Op))) ||
+          match(I, m_PtrToInt(m_Value(Op))) ||
+          match(I, m_Not(m_Value(Op)))) {
         if (isa<Instruction>(Op) || isa<Argument>(Op))
           Affected.push_back(Op);
       }
     }
   };
 
   Value *Cond = CI->getArgOperand(0), *A, *B;
   AddAffected(Cond);

llvm/trunk/lib/Analysis/ValueTracking.cpp

for (auto &AssumeVH : Q.AC->assumptionsFor(V)) {
     Value *Arg = I->getArgOperand(0);
 
     if (Arg == V && isValidAssumeForContext(I, Q.CxtI, Q.DT)) {
       assert(BitWidth == 1 && "assume operand is not i1?");
       KnownZero.clearAllBits();
       KnownOne.setAllBits();
       return;
     }
+    if (match(Arg, m_Not(m_Specific(V))) &&
+        isValidAssumeForContext(I, Q.CxtI, Q.DT)) {
+      assert(BitWidth == 1 && "assume operand is not i1?");
+      KnownZero.setAllBits();
+      KnownOne.clearAllBits();
+      return;
+    }
 
     // The remaining tests are all recursive, so bail out if we hit the limit.
     if (Depth == MaxDepth)
       continue;
 
     Value *A, *B;
     auto m_V = m_CombineOr(m_Specific(V),
                            m_CombineOr(m_PtrToInt(m_Specific(V)),

llvm/trunk/test/Transforms/InstCombine/assume.ll

 ;
   %cmp = icmp sgt i32 %a, 5
   tail call void @llvm.assume(i1 %cmp)
   %t0 = zext i1 %cmp to i32
   %lnot.ext = xor i32 %t0, 1
   ret i32 %lnot.ext
 }
 
-; FIXME: If the 'not' of a condition is known true, then the condition must be false. 
+; If the 'not' of a condition is known true, then the condition must be false.
 
 define i1 @assume_not(i1 %cond) {
 ; CHECK-LABEL: @assume_not(
 ; CHECK-NEXT:    [[NOTCOND:%.*]] = xor i1 [[COND:%.*]], true
 ; CHECK-NEXT:    call void @llvm.assume(i1 [[NOTCOND]])
-; CHECK-NEXT:    ret i1 [[COND]]
+; CHECK-NEXT:    ret i1 false
 ;
   %notcond = xor i1 %cond, true
   call void @llvm.assume(i1 %notcond)
   ret i1 %cond
 }
 
 declare void @escape(i32* %a)
 

llvm/trunk/test/Transforms/InstCombine/select.ll

 ; CHECK-NEXT:    call void @llvm.assume(i1 %cond)
 ; CHECK-NEXT:    ret i8 %x
 ;
   call void @llvm.assume(i1 %cond)
   %sel = select i1 %cond, i8 %x, i8 %y
   ret i8 %sel
 }
 
-; FIXME: computeKnownBitsFromAssume() should understand the 'not' of an assumed condition.
+; computeKnownBitsFromAssume() understands the 'not' of an assumed condition.
 
 define i8 @assume_cond_false(i1 %cond, i8 %x, i8 %y) {
 ; CHECK-LABEL: @assume_cond_false(
 ; CHECK-NEXT:    [[NOTCOND:%.*]] = xor i1 %cond, true
 ; CHECK-NEXT:    call void @llvm.assume(i1 [[NOTCOND]])
-; CHECK-NEXT:    [[SEL:%.*]] = select i1 %cond, i8 %x, i8 %y
-; CHECK-NEXT:    ret i8 [[SEL]]
+; CHECK-NEXT:    ret i8 %y
 ;
   %notcond = xor i1 %cond, true
   call void @llvm.assume(i1 %notcond)
   %sel = select i1 %cond, i8 %x, i8 %y
   ret i8 %sel
 }