[LVI] Look through negations when evaluating conditions

[loladiro]

Summary

This teaches LVI (and thus CVP) to extract range information
from branches whose condition is negated using (xor %c, true).
The implementation is relatively straightforward, simply computing
the inverse of the relevant lattice information.

I think the biggest question here is why this negation shows up
here at all. After all, it should always be possible for some
other pass to fold such a negation into a branch, comparison or
some other logical operation. Indeed, instcombine does just that.
However, these negations can be otherwise fairly persistent, e.g.
instsimplify is not able to exchange branch conditions from
negations. In addition, jumpthreading, which sits at the same
point in default pass pipeline also handles this pattern, which
adds further evidence that we might expect these negations to
not have been canonicalized away yet at this point in the pass
pipeline.

In the particular case I was looking at there was a bit of a
circular dependency where flags computed by cvp were needed
by instcombine, and incstombine's folding of the negation was
needed for cvp. Adding a second instombine pass would have
worked of course, but instcombine can be somewhat expensive,
so it appeared desirable to not require it to have run
before cvp (as is the case in the default pass pipeline).

[nikic]

llvm/lib/Analysis/LazyValueInfo.cpp

1197

Hm, I don't think this is correct if N is and and/or, or generally in any case where the returned lattice value does not represent the condition exactly, but is a superset. Inversion would exclude that difference between the exact set and superset. I'd suggest adding a test case for some case where getValueFromCondition() performs an approximation.

Could we instead flip isTrueDest, i.e. do something like this at the top?

Value *N;
if (match(Cond, m_Not(m_Value(N)))) {
  isTrueDest = !isTrueDest;
  Cond = N;
}

[loladiro]

llvm/lib/Analysis/LazyValueInfo.cpp

1197

Good catch, though I don't think that would be correct either, because then the caching logic is incorrect. However, I think we could just add isTrueDest to the cache key and then this should work fine. Let me do that.

[loladiro]

Updated to fix bug when lattice overapproximates a value

[nikic]

LGTM

In the particular case I was looking at there was a bit of a
circular dependency where flags computed by cvp were needed
by instcombine, and incstombine's folding of the negation was
needed for cvp

You might want to add a PhaseOrdering test to make sure your case keeps working.

llvm/lib/Analysis/LazyValueInfo.cpp

1169

interested

llvm/lib/Analysis/LazyValueInfo.cpp

static ValueLatticeElement getValueFromOverflowCondition(
 
   // If overflow is false, %x is constrained to NWR. If overflow is true, %x is
   // constrained to it's inverse (all values that might cause overflow).
   if (IsTrueDest)
     NWR = NWR.inverse();
   return ValueLatticeElement::getRange(NWR);
 }
 
-static std::optional<ValueLatticeElement>
-getValueFromConditionImpl(Value *Val, Value *Cond, bool isTrueDest,
-                          bool isRevisit,
-                          SmallDenseMap<Value *, ValueLatticeElement> &Visited,
-                          SmallVectorImpl<Value *> &Worklist) {
+// Tracks a Value * condition and whether we're interested in it or its inverse
+typedef PointerIntPair<Value *, 1, bool> CondValue;
+
+static std::optional<ValueLatticeElement> getValueFromConditionImpl(
+    Value *Val, CondValue CondVal, bool isRevisit,
+    SmallDenseMap<CondValue, ValueLatticeElement> &Visited,
+    SmallVectorImpl<CondValue> &Worklist) {
+
+  Value *Cond = CondVal.getPointer();
+  bool isTrueDest = CondVal.getInt();
   if (!isRevisit) {
     if (ICmpInst *ICI = dyn_cast<ICmpInst>(Cond))
       return getValueFromICmpCondition(Val, ICI, isTrueDest);
 
     if (auto *EVI = dyn_cast<ExtractValueInst>(Cond))
       if (auto *WO = dyn_cast<WithOverflowInst>(EVI->getAggregateOperand()))
         if (EVI->getNumIndices() == 1 && *EVI->idx_begin() == 1)
           return getValueFromOverflowCondition(Val, WO, isTrueDest);
   }
 
+  Value *N;
+  if (match(Cond, m_Not(m_Value(N)))) {
+    CondValue NKey(N, !isTrueDest);
+    auto NV = Visited.find(NKey);
+    if (NV == Visited.end()) {
+      Worklist.push_back(NKey);
+      return std::nullopt;
+    }
+    return NV->second;
+  }
+
   Value *L, *R;
   bool IsAnd;
   if (match(Cond, m_LogicalAnd(m_Value(L), m_Value(R))))
     IsAnd = true;
   else if (match(Cond, m_LogicalOr(m_Value(L), m_Value(R))))
     IsAnd = false;
   else
     return ValueLatticeElement::getOverdefined();
 
-  auto LV = Visited.find(L);
-  auto RV = Visited.find(R);
+  auto LV = Visited.find(CondValue(L, isTrueDest));
+  auto RV = Visited.find(CondValue(R, isTrueDest));
 
   // if (L && R) -> intersect L and R
-  // if (!(L || R)) -> intersect L and R
+  // if (!(L || R)) -> intersect !L and !R
   // if (L || R) -> union L and R
-  // if (!(L && R)) -> union L and R
+  // if (!(L && R)) -> union !L and !R
   if ((isTrueDest ^ IsAnd) && (LV != Visited.end())) {
     ValueLatticeElement V = LV->second;
     if (V.isOverdefined())
       return V;
     if (RV != Visited.end()) {
       V.mergeIn(RV->second);
       return V;
     }
   }
 
   if (LV == Visited.end() || RV == Visited.end()) {
     assert(!isRevisit);
     if (LV == Visited.end())
-      Worklist.push_back(L);
+      Worklist.push_back(CondValue(L, isTrueDest));
     if (RV == Visited.end())
-      Worklist.push_back(R);
+      Worklist.push_back(CondValue(R, isTrueDest));
     return std::nullopt;
   }
 
   return intersect(LV->second, RV->second);
 }
 
 ValueLatticeElement getValueFromCondition(Value *Val, Value *Cond,
                                           bool isTrueDest) {
   assert(Cond && "precondition");
-  SmallDenseMap<Value*, ValueLatticeElement> Visited;
-  SmallVector<Value *> Worklist;
+  SmallDenseMap<CondValue, ValueLatticeElement> Visited;
+  SmallVector<CondValue> Worklist;
 
-  Worklist.push_back(Cond);
+  CondValue CondKey(Cond, isTrueDest);
+  Worklist.push_back(CondKey);
   do {
-    Value *CurrentCond = Worklist.back();
+    CondValue CurrentCond = Worklist.back();
     // Insert an Overdefined placeholder into the set to prevent
     // infinite recursion if there exists IRs that use not
     // dominated by its def as in this example:
     //   "%tmp3 = or i1 undef, %tmp4"
     //   "%tmp4 = or i1 undef, %tmp3"
     auto Iter =
         Visited.try_emplace(CurrentCond, ValueLatticeElement::getOverdefined());
     bool isRevisit = !Iter.second;
     std::optional<ValueLatticeElement> Result = getValueFromConditionImpl(
-        Val, CurrentCond, isTrueDest, isRevisit, Visited, Worklist);
+        Val, CurrentCond, isRevisit, Visited, Worklist);
     if (Result) {
       Visited[CurrentCond] = *Result;
       Worklist.pop_back();
     }
   } while (!Worklist.empty());
 
-  auto Result = Visited.find(Cond);
+  auto Result = Visited.find(CondKey);
   assert(Result != Visited.end());
   return Result->second;
 }
 
 // Return true if Usr has Op as an operand, otherwise false.
 static bool usesOperand(User *Usr, Value *Op) {
   return is_contained(Usr->operands(), Op);
 }

llvm/test/Transforms/CorrelatedValuePropagation/basic.ll

;
   store i1 %c2, ptr %p
   %c3 = icmp ule i8 %xor, 175
   store i1 %c3, ptr %p
   %c4 = icmp ult i8 %xor, 175
   store i1 %c4, ptr %p
   ret void
 }
 
+define i1 @xor_neg_cond(i32 %a) {
+; CHECK-LABEL: @xor_neg_cond(
+; CHECK-NEXT:    [[CMP1:%.*]] = icmp eq i32 [[A:%.*]], 10
+; CHECK-NEXT:    [[XOR:%.*]] = xor i1 [[CMP1]], true
+; CHECK-NEXT:    br i1 [[XOR]], label [[EXIT:%.*]], label [[GUARD:%.*]]
+; CHECK:       guard:
+; CHECK-NEXT:    ret i1 true
+; CHECK:       exit:
+; CHECK-NEXT:    ret i1 false
+;
+  %cmp1 = icmp eq i32 %a, 10
+  %xor = xor i1 %cmp1, true
+  br i1 %xor, label %exit, label %guard
+
+guard:
+  %cmp2 = icmp eq i32 %a, 10
+  ret i1 %cmp2
+
+exit:
+  ret i1 false
+}
+
+define i1 @xor_approx(i32 %a) {
+; CHECK-LABEL: @xor_approx(
+; CHECK-NEXT:    [[CMP1:%.*]] = icmp ugt i32 [[A:%.*]], 2
+; CHECK-NEXT:    [[CMP2:%.*]] = icmp ult i32 [[A]], 5
+; CHECK-NEXT:    [[CMP3:%.*]] = icmp ugt i32 [[A]], 7
+; CHECK-NEXT:    [[CMP4:%.*]] = icmp ult i32 [[A]], 9
+; CHECK-NEXT:    [[AND1:%.*]] = and i1 [[CMP1]], [[CMP2]]
+; CHECK-NEXT:    [[AND2:%.*]] = and i1 [[CMP3]], [[CMP4]]
+; CHECK-NEXT:    [[OR:%.*]] = or i1 [[AND1]], [[AND2]]
+; CHECK-NEXT:    [[XOR:%.*]] = xor i1 [[OR]], true
+; CHECK-NEXT:    br i1 [[XOR]], label [[EXIT:%.*]], label [[GUARD:%.*]]
+; CHECK:       guard:
+; CHECK-NEXT:    [[CMP5:%.*]] = icmp eq i32 [[A]], 6
+; CHECK-NEXT:    ret i1 [[CMP5]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret i1 false
+;
+  %cmp1 = icmp ugt i32 %a, 2
+  %cmp2 = icmp ult i32 %a, 5
+  %cmp3 = icmp ugt i32 %a, 7
+  %cmp4 = icmp ult i32 %a, 9
+  %and1 = and i1 %cmp1, %cmp2
+  %and2 = and i1 %cmp3, %cmp4
+  %or = or i1 %and1, %and2
+  %xor = xor i1 %or, true
+  br i1 %xor, label %exit, label %guard
+
+guard:
+  %cmp5 = icmp eq i32 %a, 6
+  ret i1 %cmp5
+
+exit:
+  ret i1 false
+}
+
 declare i32 @llvm.uadd.sat.i32(i32, i32)
 declare i32 @llvm.usub.sat.i32(i32, i32)
 declare i32 @llvm.sadd.sat.i32(i32, i32)
 declare i32 @llvm.ssub.sat.i32(i32, i32)
 declare void @llvm.assume(i1)