[SCCP] Propagate inequalities

[nikic]

Summary

Teach SCCP to create notconstant lattice values from inequality comparisons and nonnull metadata, and update getConstant() to make use of them. Additionally isOverdefined() needs to be changed to consider notconstant an overdefined value.

[efriedma]

llvm/lib/Transforms/Scalar/SCCP.cpp

1345

This is assuming branch on undef is UB, which other parts of LLVM still have issues with; see https://bugs.llvm.org/show_bug.cgi?id=46144 .

[nikic]

Okay, taking this off the queue for now. It should be noted though that we already perform this optimization in quite a few places (inequalities are recognized by LVI and thus optimized in JT/CVP and nonnull inequalities in particular are recognized by ValueTracking, and as such optimized all over the place.)

[nikic]

Restrict patch to MayIncludeUndef=false, which is metadata and assumes, but not comparisons. This puts the basic machinery in place, and will get fully enabled once the MayIncludeUndef flag for branches gets flipped.

[fhahn]

LGTM, thanks! I think avoiding this for branches for now should make us avoid PR46144, as we do in other places. Might be good to wait a day or so, in case Eli has further comments.

[fhahn]

I think we could also try to model dereferenced pointers as non-null with a new predicate. In particular, we could create ssa_copys for dereferenced pointers, attach a predicate and rename all dominated uses. Not sure how useful/expensive that would be though. Also, ideally we would want to rename all pointers to the same underlying object.

[efriedma]

LGTM

llvm/include/llvm/Analysis/ValueLattice.h

 //===- ValueLattice.h - Value constraint analysis ---------------*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_ANALYSIS_VALUELATTICE_H
 #define LLVM_ANALYSIS_VALUELATTICE_H
 
 #include "llvm/IR/ConstantRange.h"
 #include "llvm/IR/Constants.h"
+#include "llvm/IR/Instructions.h"
 //
 //===----------------------------------------------------------------------===//
 //                               ValueLatticeElement
 //===----------------------------------------------------------------------===//
 
 /// This class represents lattice values for constants.
 ///
 /// FIXME: This is basically just for bringup, this can be made a lot more rich
public:
   Constant *getCompare(CmpInst::Predicate Pred, Type *Ty,
                        const ValueLatticeElement &Other) const {
     if (isUnknownOrUndef() || Other.isUnknownOrUndef())
       return UndefValue::get(Ty);
 
     if (isConstant() && Other.isConstant())
       return ConstantExpr::getCompare(Pred, getConstant(), Other.getConstant());
 
+    if (ICmpInst::isEquality(Pred)) {
+      // not(C) != C => true, not(C) == C => false.
+      if ((isNotConstant() && Other.isConstant() &&
+           getNotConstant() == Other.getConstant()) ||
+          (isConstant() && Other.isNotConstant() &&
+           getConstant() == Other.getNotConstant()))
+        return Pred == ICmpInst::ICMP_NE
+            ? ConstantInt::getTrue(Ty) : ConstantInt::getFalse(Ty);
+    }
+
     // Integer constants are represented as ConstantRanges with single
     // elements.
     if (!isConstantRange() || !Other.isConstantRange())
       return nullptr;
 
     const auto &CR = getConstantRange();
     const auto &OtherCR = Other.getConstantRange();
     if (ConstantRange::makeSatisfyingICmpRegion(Pred, OtherCR).contains(CR))

llvm/lib/Transforms/Scalar/SCCP.cpp

return LV.isConstant() ||
          (LV.isConstantRange() && LV.getConstantRange().isSingleElement());
 }
 
 // Helper to check if \p LV is either overdefined or a constant range with more
 // than a single element. This should cover exactly the same cases as the old
 // ValueLatticeElement::isOverdefined() and is intended to be used in the
 // transition to ValueLatticeElement.
 bool isOverdefined(const ValueLatticeElement &LV) {
-  return LV.isOverdefined() ||
-         (LV.isConstantRange() && !LV.getConstantRange().isSingleElement());
+  return !LV.isUnknownOrUndef() && !isConstant(LV);
 }
 
 //===----------------------------------------------------------------------===//
 //
 /// SCCPSolver - This class is a general purpose solver for Sparse Conditional
 /// Constant Propagation.
 ///
 class SCCPSolver : public InstVisitor<SCCPSolver> {
if (I->second.isOverdefined())
     TrackedGlobals.erase(I);      // No need to keep tracking this!
 }
 
 static ValueLatticeElement getValueFromMetadata(const Instruction *I) {
   if (MDNode *Ranges = I->getMetadata(LLVMContext::MD_range))
     if (I->getType()->isIntegerTy())
       return ValueLatticeElement::getRange(
           getConstantRangeFromMetadata(*Ranges));
-  // TODO: Also handle MD_nonnull.
+  if (I->hasMetadata(LLVMContext::MD_nonnull))
+    return ValueLatticeElement::getNot(
+        ConstantPointerNull::get(cast<PointerType>(I->getType())));
   return ValueLatticeElement::getOverdefined();
 }
 
 // Handle load instructions.  If the operand is a constant pointer to a constant
 // global, we can replace the load with the loaded constant value!
 void SCCPSolver::visitLoadInst(LoadInst &I) {
   // If this load is of a struct or the load is volatile, just mark the result
   // as overdefined.
if (II->getIntrinsicID() == Intrinsic::ssa_copy) {
       Value *OtherOp = Constraint->OtherOp;
 
       // Wait until OtherOp is resolved.
       if (getValueState(OtherOp).isUnknown()) {
         addAdditionalUser(OtherOp, &CB);
         return;
       }
 
+      // TODO: Actually filp MayIncludeUndef for the created range to false,
+      // once most places in the optimizer respect the branches on
+      // undef/poison are UB rule. The reason why the new range cannot be
+      // undef is as follows below:
+      // The new range is based on a branch condition. That guarantees that
+      // neither of the compare operands can be undef in the branch targets,
+      // unless we have conditions that are always true/false (e.g. icmp ule
+      // i32, %a, i32_max). For the latter overdefined/empty range will be
+      // inferred, but the branch will get folded accordingly anyways.
+      bool MayIncludeUndef = !isa<PredicateAssume>(PI);
+
       ValueLatticeElement CondVal = getValueState(OtherOp);
       ValueLatticeElement &IV = ValueState[&CB];
       if (CondVal.isConstantRange() || CopyOfVal.isConstantRange()) {
         auto ImposedCR =
             ConstantRange::getFull(DL.getTypeSizeInBits(CopyOf->getType()));
 
         // Get the range imposed by the condition.
         if (CondVal.isConstantRange())
if (II->getIntrinsicID() == Intrinsic::ssa_copy) {
         auto NewCR = ImposedCR.intersectWith(CopyOfCR);
         // If the existing information is != x, do not use the information from
         // a chained predicate, as the != x information is more likely to be
         // helpful in practice.
         if (!CopyOfCR.contains(NewCR) && CopyOfCR.getSingleMissingElement())
           NewCR = CopyOfCR;
 
         addAdditionalUser(OtherOp, &CB);
-        // TODO: Actually filp MayIncludeUndef for the created range to false,
-        // once most places in the optimizer respect the branches on
-        // undef/poison are UB rule. The reason why the new range cannot be
-        // undef is as follows below:
-        // The new range is based on a branch condition. That guarantees that
-        // neither of the compare operands can be undef in the branch targets,
-        // unless we have conditions that are always true/false (e.g. icmp ule
-        // i32, %a, i32_max). For the latter overdefined/empty range will be
-        // inferred, but the branch will get folded accordingly anyways.
         mergeInValue(
             IV, &CB,
-            ValueLatticeElement::getRange(NewCR, /*MayIncludeUndef=*/true));
+            ValueLatticeElement::getRange(NewCR, MayIncludeUndef));
         return;
       } else if (Pred == CmpInst::ICMP_EQ && CondVal.isConstant()) {
         // For non-integer values or integer constant expressions, only
         // propagate equal constants.
         addAdditionalUser(OtherOp, &CB);
         mergeInValue(IV, &CB, CondVal);
         return;
+      } else if (Pred == CmpInst::ICMP_NE && CondVal.isConstant() &&
+                 !MayIncludeUndef) {
+        // Propagate inequalities.
+        addAdditionalUser(OtherOp, &CB);
+        mergeInValue(IV, &CB,
+                     ValueLatticeElement::getNot(CondVal.getConstant()));
+        return;
       }
 
       return (void)mergeInValue(IV, &CB, CopyOfVal);
     }
   }
 
   // The common case is that we aren't tracking the callee, either because we
   // are not doing interprocedural analysis or the callee is indirect, or is

llvm/test/Transforms/SCCP/assume.ll

;
   call void @use(i1 %c8)
   ret void
 }
 
 define void @nonnull(i32* %v) {
 ; CHECK-LABEL: @nonnull(
 ; CHECK-NEXT:    [[A:%.*]] = icmp ne i32* [[V:%.*]], null
 ; CHECK-NEXT:    call void @llvm.assume(i1 [[A]])
-; CHECK-NEXT:    [[C1:%.*]] = icmp eq i32* [[V]], null
-; CHECK-NEXT:    call void @use(i1 [[C1]])
-; CHECK-NEXT:    [[C2:%.*]] = icmp ne i32* [[V]], null
-; CHECK-NEXT:    call void @use(i1 [[C2]])
-; CHECK-NEXT:    [[C3:%.*]] = icmp eq i32* null, [[V]]
-; CHECK-NEXT:    call void @use(i1 [[C3]])
-; CHECK-NEXT:    [[C4:%.*]] = icmp ne i32* null, [[V]]
-; CHECK-NEXT:    call void @use(i1 [[C4]])
+; CHECK-NEXT:    call void @use(i1 false)
+; CHECK-NEXT:    call void @use(i1 true)
+; CHECK-NEXT:    call void @use(i1 false)
+; CHECK-NEXT:    call void @use(i1 true)
 ; CHECK-NEXT:    ret void
 ;
   %a = icmp ne i32* %v, null
   call void @llvm.assume(i1 %a)
   %c1 = icmp eq i32* %v, null
   call void @use(i1 %c1)
   %c2 = icmp ne i32* %v, null
   call void @use(i1 %c2)
   %c3 = icmp eq i32* null, %v
   call void @use(i1 %c3)
   %c4 = icmp ne i32* null, %v
   call void @use(i1 %c4)
   ret void
 }

llvm/test/Transforms/SCCP/metadata.ll

;
   %v = load volatile i32, i32* %p, !range !{i32 0, i32 1}
   ret i32 %v
 }
 
 define void @load_nonnull(i32** %p, i32** %p2) {
 ; CHECK-LABEL: @load_nonnull(
 ; CHECK-NEXT:    [[V:%.*]] = load i32*, i32** [[P:%.*]], align 8, !nonnull !2
 ; CHECK-NEXT:    [[V2:%.*]] = load i32*, i32** [[P2:%.*]], align 8, !nonnull !2
-; CHECK-NEXT:    [[C1:%.*]] = icmp ne i32* [[V]], null
-; CHECK-NEXT:    call void @use(i1 [[C1]])
-; CHECK-NEXT:    [[C2:%.*]] = icmp eq i32* [[V]], null
-; CHECK-NEXT:    call void @use(i1 [[C2]])
-; CHECK-NEXT:    [[C3:%.*]] = icmp ne i32* null, [[V]]
-; CHECK-NEXT:    call void @use(i1 [[C3]])
-; CHECK-NEXT:    [[C4:%.*]] = icmp eq i32* null, [[V]]
-; CHECK-NEXT:    call void @use(i1 [[C4]])
+; CHECK-NEXT:    call void @use(i1 true)
+; CHECK-NEXT:    call void @use(i1 false)
+; CHECK-NEXT:    call void @use(i1 true)
+; CHECK-NEXT:    call void @use(i1 false)
 ; CHECK-NEXT:    [[C5:%.*]] = icmp eq i32* [[V]], [[V2]]
 ; CHECK-NEXT:    call void @use(i1 [[C5]])
 ; CHECK-NEXT:    [[C6:%.*]] = icmp ne i32* [[V]], [[V2]]
 ; CHECK-NEXT:    call void @use(i1 [[C6]])
 ; CHECK-NEXT:    ret void
 ;
   %v = load i32*, i32** %p, !nonnull !{}
   %v2 = load i32*, i32** %p2, !nonnull !{}