[IPSCCP] Add lattice value for != constant

[fhahn]

Summary

This patch extends IPSCCP's lattice to represent val != Constant which is used to propagate
facts for the 'false' BB following an X == Const condition.

Currently there is not measurable impact on performance or code size and a very small
increase in number of constant propagated with -flto.

The main reason for adding this patch is that it brings us closer to using ValueLatticeElement
as general lattice in SCCP, which which will enable range based analysis. With integer range
support, propagating information from conditions becomes much more powerful.

[xbolva00]

Does this patch + https://reviews.llvm.org/D50039 optimizes following code?

int l = strlen(s);
if (!s) <-- remove this condition

return -1;

return len;

[fhahn]

In D51431#1217705, @xbolva00 wrote:

Does this patch + https://reviews.llvm.org/D50039 optimizes following code?

int l = strlen(s);
if (!s) <-- remove this condition

return -1;

return len;

Nope, this patch would add nonnull to the argument in this case

if (!s) {
   return -1:
} else {
  return strlen(s)
}

Once we have a notconst lattice value, we could however eliminate the condition in with some more work:

1. for call sites with nonnull arguments, we could create a ssa copy of the argument and mark it as not null. (The copy ensures we only use the fact in places dominated by the call site. Not sure if inserting copies for that will have an impact on the runtime, so it might not work overall)
2. deduce false for "x == null" with x not null

[efriedma]

lib/Transforms/Scalar/SCCP.cpp

843

I guess you could try to resolve a PHI to NotConstant...? Not sure how important that is.

1798

I'm not sure this is right: nonnull is UB if the value is null, but SCCP can merge an "Undef" into a NotConstant.

[fhahn]

lib/Transforms/Scalar/SCCP.cpp

843

Yep, there should be a TODO here (and in other places)

1798

I think I am missing something. tryToAddNonNull is used after we finished solving and a lattice value of notconstant(Null) should mean "we proved that the value is != null". If we merge an undef into a NotConstant, isn't that similar to when we merge an undef into a Constant, where it is safe to use the constant after solving?

[efriedma]

lib/Transforms/Scalar/SCCP.cpp

1798

The difference is how we're using the result. If we take a value that's undef and replace it with a constant, that's fine; the undef might have resolved to that constant anyway. If we take a value that's undef and assert it's nonnull, that will explode if the undef actually resolves to null.

Note this is specifically a problem with our weird handling of IR "undef" values; if we treated "undef" as overdefined or constant, the lattice represents what you want it to represent. It's possible that nonnull optimization is important enough that it's better to just kill off all the undef special-case optimizations to make this legal.

[fhahn]

lib/Transforms/Scalar/SCCP.cpp

1798

Right, thanks Eli! I'll see if it is feasible to go to overdefined when merging undef into notconstan to start with.

[fhahn]

In D51431#1217705, @xbolva00 wrote:

Does this patch + https://reviews.llvm.org/D50039 optimizes following code?

int l = strlen(s);
if (!s) <-- remove this condition

return -1;

return len;

I've put together another POC patch based on this one to optimize the code you mentioned: D51505. It's not really ready for being reviewed, but it should give an idea how we might be able to handle this. Do you have any motivating benchmarks/use cases for this in particular?

[fhahn]

updated merging of unknown and notconstant values to go to overdefined

[fhahn]

lib/Transforms/Scalar/SCCP.cpp

1798

I've updated mergeInValue to go to overdefined when merging unknown and notconstant. I think that should cover the cases where we combine 2 values of unknown/notconstant to notconstant.

I've also added a test case that should be an instance where we cannot infer nonnull. What do you think?

[fhahn]

lib/Transforms/Scalar/SCCP.cpp

1798

Eli, do you think the change is enough to be correct?

[fhahn]

ping

[fhahn]

ping

[fhahn]

ping :) Eli do you think it is safe after the latest update or do you think there still are potential problems?

[efriedma]

You're making the lattice really confusing. Essentially, there are now two different merging rules: one is used if the caller calls mergeInValue, and a different one is used if the caller calls markNotConstant etc. So it's not obvious what the lattice actually represents.

---

And actually, thinking about it a bit more, there's a more fundamental problem with proving a value is non-null. Given that a value is possibly-undef, it could be null even for code dominated by a null-check. So the entire proposed transform is unsound unless you freeze the pointer.

This doesn't normally cause a problem for existing SCCP analysis because the only transform SCCP usually performs is refining an value to a specific constant. (It also erases dead code, but that isn't really relevant here.) Along a path where x==null is true, it's possible for x to evaluate to some non-null value. but it's still okay for SCCP to replace x with null.

[fhahn]

In D51431#1262979, @efriedma wrote:

You're making the lattice really confusing. Essentially, there are now two different merging rules: one is used if the caller calls mergeInValue, and a different one is used if the caller calls markNotConstant etc. So it's not obvious what the lattice actually represents.

---

And actually, thinking about it a bit more, there's a more fundamental problem with proving a value is non-null. Given that a value is possibly-undef, it could be null even for code dominated by a null-check. So the entire proposed transform is unsound unless you freeze the pointer.

Right, thanks Eli! I think we would have to same problem when we would use conditions to derive constant ranges. I am not sure what you mean by freezing the pointer I am afraid. In case you are at the dev meeting, is that something you would be interested to talk about briefly?

This doesn't normally cause a problem for existing SCCP analysis because the only transform SCCP usually performs is refining an value to a specific constant. (It also erases dead code, but that isn't really relevant here.) Along a path where x==null is true, it's possible for x to evaluate to some non-null value. but it's still okay for SCCP to replace x with null.

[efriedma]

I am not sure what you mean by freezing the pointer I am afraid.

I mean replace all the relevant uses of the pointer with a "freeze" instruction (as in https://reviews.llvm.org/D29011) on that pointer.

In case you are at the dev meeting, is that something you would be interested to talk about briefly?

I won't be at the dev meeting this year.

[fhahn]

In D51431#1267070, @efriedma wrote:

I am not sure what you mean by freezing the pointer I am afraid.

I mean replace all the relevant uses of the pointer with a "freeze" instruction (as in https://reviews.llvm.org/D29011) on that pointer.

Ah yes, thank you very much for pointing me to D29011, this sounds exactly like what we would need!

In case you are at the dev meeting, is that something you would be interested to talk about briefly?

I won't be at the dev meeting this year.

[fhahn]

I stripped adding nonnull for now. Even with freeze, we have to be far too conservative about the merging rules. This patch is now more an enabler to make it easier to use ValueLAtticeElement, with range support. What do you think?

[fhahn]

ping.

[fhahn]

ping

[fhahn]

ping :)

[fhahn]

I plan to add this on top of the integer range support patches, abandoning this for now

lib/Transforms/Scalar/SCCP.cpp

enum LatticeValueTy {
     constant,
 
     /// forcedconstant - This LLVM Value was thought to be undef until
     /// ResolvedUndefsIn.  This is treated just like 'constant', but if merged
     /// with another (different) constant, it goes to overdefined, instead of
     /// asserting.
     forcedconstant,
 
+    /// This Value is known to not have the specified value.
+    notconstant,
+
     /// overdefined - This instruction is not known to be constant, and we know
     /// it has a value.
     overdefined
   };
 
   /// Val: This stores the current lattice value along with the Constant* for
   /// the constant if this is a 'constant' or 'forcedconstant' value.
-  PointerIntPair<Constant *, 2, LatticeValueTy> Val;
+  PointerIntPair<Constant *, 3, LatticeValueTy> Val;
 
   LatticeValueTy getLatticeValue() const {
     return Val.getInt();
   }
 
 public:
   LatticeVal() : Val(nullptr, unknown) {}
 
   bool isUnknown() const { return getLatticeValue() == unknown; }
 
   bool isConstant() const {
     return getLatticeValue() == constant || getLatticeValue() == forcedconstant;
   }
 
+  bool isNotConstant() const { return getLatticeValue() == notconstant; }
+
   bool isOverdefined() const { return getLatticeValue() == overdefined; }
 
   Constant *getConstant() const {
     assert(isConstant() && "Cannot get the constant of a non-constant!");
     return Val.getPointer();
   }
 
   /// markOverdefined - Return true if this is a change in status.
if (isUnknown()) {
       // Otherwise, we go to overdefined.  Assumptions made based on the
       // forced value are possibly wrong.  Assuming this is another constant
       // could expose a contradiction.
       Val.setInt(overdefined);
     }
     return true;
   }
 
+  bool markNotConstant(Constant *V) {
+    assert(V && "Marking constant with NULL");
+    if (isa<UndefValue>(V))
+      return false;
+
+    assert((!isNotConstant() || getNotConstant() == V) &&
+           "Marking !constant with different value");
+    assert(isUnknown() || isNotConstant());
+    Val.setPointer(V);
+    Val.setInt(notconstant);
+    return true;
+  }
+
   /// getConstantInt - If this is a constant with a ConstantInt value, return it
   /// otherwise return null.
   ConstantInt *getConstantInt() const {
     if (isConstant())
       return dyn_cast<ConstantInt>(getConstant());
     return nullptr;
   }
 
+  Constant *getNotConstant() const {
+    assert(isNotConstant() && "Cannot get the constant of a non-notconstant!");
+    return Val.getPointer();
+  }
+
   /// getBlockAddress - If this is a constant with a BlockAddress value, return
   /// it, otherwise return null.
   BlockAddress *getBlockAddress() const {
     if (isConstant())
       return dyn_cast<BlockAddress>(getConstant());
     return nullptr;
   }
 
   void markForcedConstant(Constant *V) {
     assert(isUnknown() && "Can't force a defined value!");
     Val.setInt(forcedconstant);
     Val.setPointer(V);
   }
 
   ValueLatticeElement toValueLattice() const {
     if (isOverdefined())
       return ValueLatticeElement::getOverdefined();
     if (isConstant())
       return ValueLatticeElement::get(getConstant());
+    if (isNotConstant())
+      return ValueLatticeElement::getNot(getNotConstant());
     return ValueLatticeElement();
   }
 };
 
 //===----------------------------------------------------------------------===//
 //
 /// SCCPSolver - This class is a general purpose solver for Sparse Conditional
 /// Constant Propagation.
private:
   void markForcedConstant(Value *V, Constant *C) {
     assert(!V->getType()->isStructTy() && "structs should use mergeInValue");
     LatticeVal &IV = ValueState[V];
     IV.markForcedConstant(C);
     LLVM_DEBUG(dbgs() << "markForcedConstant: " << *C << ": " << *V << '\n');
     pushToWorkList(IV, V);
   }
 
+  bool markNotConstant(LatticeVal &IV, Value *V, Constant *C) {
+    if (!IV.markNotConstant(C))
+      return false;
+    LLVM_DEBUG(dbgs() << "markNotConstant: " << *C << ": " << *V << '\n');
+    pushToWorkList(IV, V);
+    return true;
+  }
+
   // markOverdefined - Make a value be marked as "overdefined". If the
   // value is not already overdefined, add it to the overdefined instruction
   // work list so that the users of the instruction are updated later.
   bool markOverdefined(LatticeVal &IV, Value *V) {
     if (!IV.markOverdefined()) return false;
 
     LLVM_DEBUG(dbgs() << "markOverdefined: ";
                if (auto *F = dyn_cast<Function>(V)) dbgs()
                << "Function '" << F->getName() << "'\n";
                else dbgs() << *V << '\n');
     // Only instructions go on the work list
     pushToWorkList(IV, V);
     return true;
   }
 
   bool mergeInValue(LatticeVal &IV, Value *V, LatticeVal MergeWithV) {
     if (IV.isOverdefined() || MergeWithV.isUnknown())
       return false; // Noop.
     if (MergeWithV.isOverdefined())
       return markOverdefined(IV, V);
-    if (IV.isUnknown())
+
+    if (IV.isUnknown()) {
+      if (MergeWithV.isNotConstant())
+        return markNotConstant(IV, V, MergeWithV.getNotConstant());
+      else {
+        assert(MergeWithV.isConstant() && "Unexpected lattice value type");
         return markConstant(IV, V, MergeWithV.getConstant());
-    if (IV.getConstant() != MergeWithV.getConstant())
+      }
+    }
+
+    if (IV.isNotConstant()) {
+      if (MergeWithV.isNotConstant() &&
+          IV.getNotConstant() == MergeWithV.getNotConstant())
+        return false;
       return markOverdefined(IV, V);
+    }
+
+    if (IV.isConstant()) {
+      if (MergeWithV.isConstant() &&
+          IV.getConstant() == MergeWithV.getConstant())
         return false;
+      return markOverdefined(IV, V);
+    }
   }
 
   bool mergeInValue(Value *V, LatticeVal MergeWithV) {
     assert(!V->getType()->isStructTy() &&
            "non-structs should use markConstant");
     return mergeInValue(ValueState[V], V, MergeWithV);
   }
 
for (unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i) {
     if (IV.isUnknown()) continue;  // Doesn't influence PHI node.
 
     if (!isEdgeFeasible(PN.getIncomingBlock(i), PN.getParent()))
       continue;
 
     if (IV.isOverdefined())    // PHI node becomes overdefined!
       return (void)markOverdefined(&PN);
 
+    if (IV.isNotConstant())
+      return (void)markOverdefined(&PN);
+
     if (!OperandVal) {   // Grab the first value.
       OperandVal = IV.getConstant();
       continue;
     }
 
     // There is already a reachable operand.  If we conflict with it,
     // then the PHI node becomes overdefined.  If we agree with it, we
     // can continue on.
void SCCPSolver::visitTerminator(Instruction &TI) {
   // Mark all feasible successors executable.
   for (unsigned i = 0, e = SuccFeasible.size(); i != e; ++i)
     if (SuccFeasible[i])
       markEdgeExecutable(BB, TI.getSuccessor(i));
 }
 
 void SCCPSolver::visitCastInst(CastInst &I) {
   LatticeVal OpSt = getValueState(I.getOperand(0));
-  if (OpSt.isOverdefined())          // Inherit overdefinedness of operand
+  if (OpSt.isOverdefined() ||
+      OpSt.isNotConstant()) // Inherit overdefinedness of operand
     markOverdefined(&I);
   else if (OpSt.isConstant()) {
     // Fold the constant as we build.
     Constant *C = ConstantFoldCastOperand(I.getOpcode(), OpSt.getConstant(),
                                           I.getType(), DL);
     if (isa<UndefValue>(C))
       return;
     // Propagate constant value

 // Handle Binary Operators.
 void SCCPSolver::visitBinaryOperator(Instruction &I) {
   LatticeVal V1State = getValueState(I.getOperand(0));
   LatticeVal V2State = getValueState(I.getOperand(1));
 
   LatticeVal &IV = ValueState[&I];
   if (IV.isOverdefined()) return;
 
+  // TODO: could do better than that in some cases.
+  if (V1State.isNotConstant() || V2State.isNotConstant())
+    return (void)markOverdefined(&I);
+
   if (V1State.isConstant() && V2State.isConstant()) {
     Constant *C = ConstantExpr::get(I.getOpcode(), V1State.getConstant(),
                                     V2State.getConstant());
     // X op Y -> undef.
     if (isa<UndefValue>(C))
       return;
     return (void)markConstant(IV, &I, C);
   }
void SCCPSolver::visitBinaryOperator(Instruction &I) {
 
   // If this is:
   // -> AND/MUL with 0
   // -> OR with -1
   // it doesn't matter that the other operand is overdefined.
   if (I.getOpcode() == Instruction::And || I.getOpcode() == Instruction::Mul ||
       I.getOpcode() == Instruction::Or) {
     LatticeVal *NonOverdefVal = nullptr;
-    if (!V1State.isOverdefined())
+    if (!V1State.isOverdefined() && !V1State.isNotConstant())
       NonOverdefVal = &V1State;
-    else if (!V2State.isOverdefined())
+    else if (!V2State.isOverdefined() && !V2State.isNotConstant())
       NonOverdefVal = &V2State;
 
     if (NonOverdefVal) {
       if (NonOverdefVal->isUnknown())
         return;
 
       if (I.getOpcode() == Instruction::And ||
           I.getOpcode() == Instruction::Mul) {
void SCCPSolver::visitGetElementPtrInst(GetElementPtrInst &I) {
   SmallVector<Constant*, 8> Operands;
   Operands.reserve(I.getNumOperands());
 
   for (unsigned i = 0, e = I.getNumOperands(); i != e; ++i) {
     LatticeVal State = getValueState(I.getOperand(i));
     if (State.isUnknown())
       return;  // Operands are not resolved yet.
 
-    if (State.isOverdefined())
+    if (State.isOverdefined() || State.isNotConstant())
       return (void)markOverdefined(&I);
 
     assert(State.isConstant() && "Unknown state!");
     Operands.push_back(State.getConstant());
   }
 
   Constant *Ptr = Operands[0];
   auto Indices = makeArrayRef(Operands.begin() + 1, Operands.end());
if (II->getIntrinsicID() == Intrinsic::ssa_copy) {
       }
 
       if (CmpOp0 != CopyOf)
         std::swap(CmpOp0, CmpOp1);
 
       LatticeVal OriginalVal = getValueState(CopyOf);
       LatticeVal EqVal = getValueState(CmpOp1);
       LatticeVal &IV = ValueState[I];
-      if (PBranch->TrueEdge && Cmp->getPredicate() == CmpInst::ICMP_EQ) {
-        addAdditionalUser(CmpOp1, I);
-        if (OriginalVal.isConstant())
-          mergeInValue(IV, I, OriginalVal);
-        else
+      if (OriginalVal.isConstant()) {
+        return;
+      }
+
+      if (Cmp->getPredicate() == CmpInst::ICMP_EQ) {
+        if (PBranch->TrueEdge) {
+          addAdditionalUser(CmpOp1, I);
           mergeInValue(IV, I, EqVal);
           return;
+        } else {
+          if (EqVal.isConstant() &&
+              (IV.isUnknown() ||
+               (IV.isNotConstant() &&
+                IV.getNotConstant() == EqVal.getConstant()))) {
+            addAdditionalUser(CmpOp1, I);
+            markNotConstant(IV, I, EqVal.getConstant());
+            return;
+          }
         }
-      if (!PBranch->TrueEdge && Cmp->getPredicate() == CmpInst::ICMP_NE) {
+      } else if (Cmp->getPredicate() == CmpInst::ICMP_NE) {
+        if (!PBranch->TrueEdge) {
           addAdditionalUser(CmpOp1, I);
-        if (OriginalVal.isConstant())
-          mergeInValue(IV, I, OriginalVal);
-        else
           mergeInValue(IV, I, EqVal);
           return;
+        } else {
+          if (EqVal.isConstant() &&
+              (IV.isUnknown() ||
+               (IV.isNotConstant() &&
+                IV.getNotConstant() == EqVal.getConstant()))) {
+            addAdditionalUser(CmpOp1, I);
+            markNotConstant(IV, I, EqVal.getConstant());
+            return;
+          }
+        }
       }
 
       return (void)mergeInValue(IV, I, getValueState(PBranch->OriginalOp));
     }
   }
 
   // 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
if (F && F->isDeclaration() && !I->getType()->isStructTy() &&
       for (CallSite::arg_iterator AI = CS.arg_begin(), E = CS.arg_end();
            AI != E; ++AI) {
         if (AI->get()->getType()->isStructTy())
           return markOverdefined(I); // Can't handle struct args.
         LatticeVal State = getValueState(*AI);
 
         if (State.isUnknown())
           return;  // Operands are not resolved yet.
-        if (State.isOverdefined())
+        if (State.isOverdefined() || State.isNotConstant())
           return (void)markOverdefined(I);
-        assert(State.isConstant() && "Unknown state!");
+        assert(State.isConstant());
         Operands.push_back(State.getConstant());
       }
 
       if (getValueState(I).isOverdefined())
         return;
 
       // If we can constant fold this, mark the result of the call as a
       // constant.
bool SCCPSolver::ResolvedUndefsIn(Function &F) {
 
   return false;
 }
 
 static bool tryToReplaceWithConstant(SCCPSolver &Solver, Value *V) {
   Constant *Const = nullptr;
   if (V->getType()->isStructTy()) {
     std::vector<LatticeVal> IVs = Solver.getStructLatticeValueFor(V);
-    if (llvm::any_of(IVs,
-                     [](const LatticeVal &LV) { return LV.isOverdefined(); }))
+    if (llvm::any_of(IVs, [](const LatticeVal &LV) {
+          return LV.isOverdefined() || LV.isNotConstant();
+        }))
       return false;
     std::vector<Constant *> ConstVals;
     auto *ST = dyn_cast<StructType>(V->getType());
     for (unsigned i = 0, e = ST->getNumElements(); i != e; ++i) {
       LatticeVal V = IVs[i];
       ConstVals.push_back(V.isConstant()
                               ? V.getConstant()
                               : UndefValue::get(ST->getElementType(i)));
     }
     Const = ConstantStruct::get(ST, ConstVals);
   } else {
     const LatticeVal &IV = Solver.getLatticeValueFor(V);
-    if (IV.isOverdefined())
+    if (IV.isOverdefined() || IV.isNotConstant())
       return false;
 
     Const = IV.isConstant() ? IV.getConstant() : UndefValue::get(V->getType());
   }
   assert(Const && "Constant is nullptr here!");
 
   // Replacing `musttail` instructions with constant breaks `musttail` invariant
   // unless the call itself can be removed
bool llvm::runIPSCCP(
   // if the address of the function isn't taken.  In cases where a return is the
   // last use of a function, the order of processing functions would affect
   // whether other functions are optimizable.
   SmallVector<ReturnInst*, 8> ReturnsToZap;
 
   const DenseMap<Function*, LatticeVal> &RV = Solver.getTrackedRetVals();
   for (const auto &I : RV) {
     Function *F = I.first;
-    if (I.second.isOverdefined() || F->getReturnType()->isVoidTy())
+    if (!(I.second.isUnknown() || I.second.isConstant()) ||
+        F->getReturnType()->isVoidTy())
       continue;
     findReturnsToZap(*F, ReturnsToZap, Solver);
   }
 
   for (const auto &F : Solver.getMRVFunctionsTracked()) {
     assert(F->getReturnType()->isStructTy() &&
            "The return type should be a struct");
     StructType *STy = cast<StructType>(F->getReturnType());

test/Transforms/SCCP/ipsccp-notnull.ll

+; RUN: opt < %s -ipsccp -S | FileCheck %s
+
+; CHECK-LABEL: @test3
+; CHECK-LABEL: if.else:
+; CHECK: ret i1 true
+define internal i1 @test3(i32 %a, i32 %b) {
+entry:
+  %cond = icmp eq i32 %a, %b
+  br i1 %cond, label %if.then, label %if.else
+
+if.then:                                          ; preds = %entry
+  ret i1 %cond
+
+if.else:                                           ; preds = %if.then, %entry
+  %s = select i1 undef, i32 undef, i32 %b
+  %c = icmp ne i32 %a, %s
+  ret i1 %c
+}
+
+; CHECK-LABEL: @test5
+; CHECK-LABEL: if.else:
+; CHECK: ret i1 true
+define internal i1 @test5(i32 %a, i32 %b) {
+entry:
+  %cond = icmp eq i32 %a, 4
+  br i1 %cond, label %if.then, label %if.else
+
+if.then:                                          ; preds = %entry
+  ret i1 %cond
+
+if.else:                                           ; preds = %if.then, %entry
+  %r1 = add i32 %b, %b
+  %c = icmp ne i32 %a, %r1
+  ret i1 %c
+}
+
+define i1 @main(i32 %a) {
+  %v1 = call i1 @test3(i32 %a, i32 1)
+  %v2 = call i1 @test5(i32 %a, i32 2)
+  %v3 = and i1 %v1, %v2
+  ret i1 %v3
+}
+
+; Make sure we do not zap return values marked as not-constant.
+define i64 @caller_zap(i64 %n) {
+entry:
+  %call = call i64 @callee_zap(i64 %n)
+  ret i64 %call
+}
+
+; CHECK-LABEL: @callee_zap
+; CHECK-LABEL: if.end:
+; CHECK-NEXT: ret i64 %num
+define internal i64 @callee_zap(i64 %num) {
+entry:
+  %cond = icmp eq i64 %num, 16
+  br i1 %cond, label %if.then, label %if.end
+
+if.then:                                          ; preds = %entry
+  unreachable
+
+if.end:                                           ; preds = %entry
+  ret i64 %num
+}