[WIP][IPSCCP] Use PredInfo to propagate nonnull and hook it up to IPSCCP.

[fhahn]

Summary

This is a POC patch to optimize code like below

int l = strlen(s); // s has nonnull attribute at call site.
if (!s) <-- remove this condition
    return -1;
return len;

The basic idea is to treat calls with !nonnull arguments like if we had something like assume arg != null at the call site.

This patch hacks up PredicateInfo to treat nonnull arguments at call
sites similar to assumes, it inserts a ssa_copy for the argument and
replaces all uses of the argument dominated by the call with the copy.
The copy has a predicate info attached stating that the copy is non
null.

The second part of the patch extends IPSCCP to use that information and
ValueLattice::getCompare() to simplify EQ comparisons of notconstant
with constant.

The most hacky part are the changes in PredicateInfo, but they should
be enough to highlight the idea.

[fhahn]

This is not ready for review yet, I'll continue with this if D51505 is submitted.

[fhahn]

This depends on D29011 via D51505

[fhahn]

I am abandoning this for now, as I updated D51431 to avoid adding nonnull, because even with freeze it would be too restrictive.

include/llvm/Analysis/ValueLattice.h

public:
   Constant *getCompare(CmpInst::Predicate Pred, Type *Ty,
                        const ValueLatticeElement &Other) const {
     if (isUndefined() || Other.isUndefined())
       return UndefValue::get(Ty);
 
     if (isConstant() && Other.isConstant())
       return ConstantExpr::getCompare(Pred, getConstant(), Other.getConstant());
 
+    if (isNotConstant() && Other.isConstant()) {
+      if (Pred == CmpInst::ICMP_EQ && getNotConstant() == Other.getConstant())
+        return 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))

include/llvm/Transforms/Utils/PredicateInfo.h

 
 class DominatorTree;
 class Function;
 class Instruction;
 class MemoryAccess;
 class LLVMContext;
 class raw_ostream;
 
-enum PredicateType { PT_Branch, PT_Assume, PT_Switch };
+enum PredicateType { PT_Branch, PT_Assume, PT_Switch, PT_NE };
 
 // Base class for all predicate information we provide.
 // All of our predicate information has at least a comparison.
 class PredicateBase : public ilist_node<PredicateBase> {
 public:
   PredicateType Type;
   // The original operand before we renamed it.
   // This can be use by passes, when destroying predicateinfo, to know
   // whether they can just drop the intrinsic, or have to merge metadata.
   Value *OriginalOp;
   PredicateBase(const PredicateBase &) = delete;
   PredicateBase &operator=(const PredicateBase &) = delete;
   PredicateBase() = delete;
   virtual ~PredicateBase() = default;
 
 protected:
   PredicateBase(PredicateType PT, Value *Op) : Type(PT), OriginalOp(Op) {}
 };
 
 class PredicateWithCondition : public PredicateBase {
 public:
   Value *Condition;
   static bool classof(const PredicateBase *PB) {
     return PB->Type == PT_Assume || PB->Type == PT_Branch ||
-           PB->Type == PT_Switch;
+           PB->Type == PT_Switch || PB->Type == PT_NE;
   }
 
 protected:
   PredicateWithCondition(PredicateType PT, Value *Op, Value *Condition)
       : PredicateBase(PT, Op), Condition(Condition) {}
 };
 
 // Provides predicate information for assumes.  Since assumes are always true,
 // we simply provide the assume instruction, so you can tell your relative
 // position to it.
 class PredicateAssume : public PredicateWithCondition {
 public:
   IntrinsicInst *AssumeInst;
   PredicateAssume(Value *Op, IntrinsicInst *AssumeInst, Value *Condition)
       : PredicateWithCondition(PT_Assume, Op, Condition),
         AssumeInst(AssumeInst) {}
   PredicateAssume() = delete;
   static bool classof(const PredicateBase *PB) {
     return PB->Type == PT_Assume;
   }
 };
 
+// Provides predicate information for values we do know to be nonnull. We set
+// I to the instruction that implies non-nullness, so we can tell your relative
+// postition to it.
+class PredicateNonNull : public PredicateWithCondition {
+public:
+  Instruction *I;
+  PredicateNonNull(Value *Op, Instruction *I)
+      : PredicateWithCondition(PT_NE, Op, nullptr), I(I) {}
+  PredicateNonNull() = delete;
+  static bool classof(const PredicateBase *PB) { return PB->Type == PT_NE; }
+};
+
 // Mixin class for edge predicates.  The FROM block is the block where the
 // predicate originates, and the TO block is the block where the predicate is
 // valid.
 class PredicateWithEdge : public PredicateWithCondition {
 public:
   BasicBlock *From;
   BasicBlock *To;
   PredicateWithEdge() = delete;

lib/Transforms/Scalar/SCCP.cpp

if (auto *II = dyn_cast<IntrinsicInst>(I)) {
     if (II->getIntrinsicID() == Intrinsic::ssa_copy) {
       if (ValueState[I].isOverdefined())
         return;
 
       auto *PI = getPredicateInfoFor(I);
       if (!PI)
         return;
 
+      if (isa<PredicateNonNull>(getPredicateInfoFor(I))) {
+        LatticeVal OriginalVal = getValueState(PI->OriginalOp);
+        LatticeVal &IV = ValueState[I];
+
+        if (OriginalVal.isConstant()) {
+          mergeInValue(IV, I, OriginalVal);
+          return;
+        }
+
+        if (IV.isUnknown() ||
+            (IV.isNotConstant() && IV.getNotConstant()->isNullValue())) {
+          markNotConstant(
+              IV, I, ConstantPointerNull::get(cast<PointerType>(I->getType())));
+          return;
+        }
+      }
+
       auto *PBranch = dyn_cast<PredicateBranch>(getPredicateInfoFor(I));
       if (!PBranch) {
         mergeInValue(ValueState[I], I, getValueState(PI->OriginalOp));
         return;
       }
 
       Value *CopyOf = I->getOperand(0);
       Value *Cond = PBranch->Condition;

lib/Transforms/Utils/PredicateInfo.cpp

Value *getMiddleDef(const ValueDFS &VD) const {
     // numbering will say the placed predicaeinfos should go first (IE
     // LN_beginning), so we won't be in this function. For assumes, we will end
     // up here, beause we need to order the def we will place relative to the
     // assume.  So for the purpose of ordering, we pretend the def is the assume
     // because that is where we will insert the info.
     if (!VD.U) {
       assert(VD.PInfo &&
              "No def, no use, and no predicateinfo should not occur");
+      if (auto *NE = dyn_cast<PredicateNonNull>(VD.PInfo))
+        return NE->I;
+
       assert(isa<PredicateAssume>(VD.PInfo) &&
              "Middle of block should only occur for assumes");
       return cast<PredicateAssume>(VD.PInfo)->AssumeInst;
     }
     return nullptr;
   }
 
   // Return either the Def, if it's not null, or the user of the Use, if the def

 // Build predicate info for our function
 void PredicateInfo::buildPredicateInfo() {
   DT.updateDFSNumbers();
   // Collect operands to rename from all conditional branch terminators, as well
   // as assume statements.
   SmallPtrSet<Value *, 8> OpsToRename;
   for (auto DTN : depth_first(DT.getRootNode())) {
     BasicBlock *BranchBB = DTN->getBlock();
+    for (auto &I : *BranchBB) {
+      if (auto CS = CallSite(&I)) {
+        for (unsigned ArgNo = 0; ArgNo < CS.arg_size(); ArgNo++) {
+          if (CS.paramHasAttr(ArgNo, Attribute::NonNull)) {
+            auto Arg = CS.getArgOperand(ArgNo);
+            if (!Arg->getType()->isPointerTy())
+              continue;
+            auto *PA = new PredicateNonNull(Arg, &I);
+            addInfoFor(OpsToRename, Arg, PA);
+          }
+        }
+      }
+    }
     if (auto *BI = dyn_cast<BranchInst>(BranchBB->getTerminator())) {
       if (!BI->isConditional())
         continue;
       // Can't insert conditional information if they all go to the same place.
       if (BI->getSuccessor(0) == BI->getSuccessor(1))
         continue;
       processBranch(BI, BranchBB, OpsToRename);
     } else if (auto *SI = dyn_cast<SwitchInst>(BranchBB->getTerminator())) {
if (isa<PredicateWithEdge>(ValInfo)) {
       Function *IF = getCopyDeclaration(F.getParent(), Op->getType());
       if (IF->user_begin() == IF->user_end())
         CreatedDeclarations.insert(IF);
       CallInst *PIC =
           B.CreateCall(IF, Op, Op->getName() + "." + Twine(Counter++));
       PredicateMap.insert({PIC, ValInfo});
       Result.Def = PIC;
     } else {
-      auto *PAssume = dyn_cast<PredicateAssume>(ValInfo);
-      assert(PAssume &&
+      Instruction *I;
+      if (auto *PNE = dyn_cast<PredicateNonNull>(ValInfo))
+        I = PNE->I;
+      else {
+        assert(isa<PredicateAssume>(ValInfo) &&
                "Should not have gotten here without it being an assume");
-      IRBuilder<> B(PAssume->AssumeInst);
+        I = cast<PredicateAssume>(ValInfo)->AssumeInst;
+      }
+      IRBuilder<> B(I);
       Function *IF = getCopyDeclaration(F.getParent(), Op->getType());
       if (IF->user_begin() == IF->user_end())
         CreatedDeclarations.insert(IF);
       CallInst *PIC = B.CreateCall(IF, Op);
       PredicateMap.insert({PIC, ValInfo});
       Result.Def = PIC;
     }
   }
for (auto &PossibleCopy : ValueInfo.Infos) {
         VD.LocalNum = LN_Middle;
         DomTreeNode *DomNode = DT.getNode(PAssume->AssumeInst->getParent());
         if (!DomNode)
           continue;
         VD.DFSIn = DomNode->getDFSNumIn();
         VD.DFSOut = DomNode->getDFSNumOut();
         VD.PInfo = PossibleCopy;
         OrderedUses.push_back(VD);
+      } else if (const auto *PAssume =
+                     dyn_cast<PredicateNonNull>(PossibleCopy)) {
+        VD.LocalNum = LN_Middle;
+        DomTreeNode *DomNode = DT.getNode(PAssume->I->getParent());
+        if (!DomNode)
+          continue;
+        VD.DFSIn = DomNode->getDFSNumIn();
+        VD.DFSOut = DomNode->getDFSNumOut();
+        VD.PInfo = PossibleCopy;
+        OrderedUses.push_back(VD);
       } else if (isa<PredicateWithEdge>(PossibleCopy)) {
         // If we can only do phi uses, we treat it like it's in the branch
         // block, and handle it specially. We know that it goes last, and only
         // dominate phi uses.
         auto BlockEdge = getBlockEdge(PossibleCopy);
         if (EdgeUsesOnly.count(BlockEdge)) {
           VD.LocalNum = LN_Last;
           auto *DomNode = DT.getNode(BlockEdge.first);
if (const auto *PI = PredInfo->getPredicateInfoFor(I)) {
            << " Switch:" << *PS->Switch << " Edge: [";
         PS->From->printAsOperand(OS);
         OS << ",";
         PS->To->printAsOperand(OS);
         OS << "] }\n";
       } else if (const auto *PA = dyn_cast<PredicateAssume>(PI)) {
         OS << "; assume predicate info {"
            << " Comparison:" << *PA->Condition << " }\n";
+      } else if (isa<PredicateNonNull>(PI)) {
+        OS << "; assume predicate info {"
+           << " NonNull "
+           << " }\n";
       }
     }
   }
 };
 
 void PredicateInfo::print(raw_ostream &OS) const {
   PredicateInfoAnnotatedWriter Writer(this);
   F.print(OS, &Writer);

test/Transforms/SCCP/ipsccp-nonnull.ll

 
 if.then:                                          ; preds = %entry
   ret i1 true
 
 if.end:                                           ; preds = %if.then, %entry
   %call = call i1 @testf(i32* %ptr)
   ret i1 %call
 }
+
+; CHECK-LABEL: @bar2(
+; CHECK:       %call = call i1 @testf(i32* nonnull %ptr)
+; CHECK-NEXT:  br label %if.end
+define i1 @bar2(i32* %ptr) {
+entry:
+  %call = call i1 @testf(i32* nonnull %ptr)
+  %cond = icmp eq i32* %ptr, null
+  br i1 %cond, label %if.then, label %if.end
+
+if.then:                                          ; preds = %entry
+  ret i1 true
+
+if.end:                                           ; preds = %if.then, %entry
+  ret i1 %call
+}
+
+
+; CHECK-LABEL: @bar3(
+; CHECK:   br i1 %c1, label %bb1, label %bb2
+; CHECK-LABEL: bb1:
+; CHECK-NEXT:    %call = call i1 @testf(i32* nonnull %ptr)
+; CHECK-NEXT:    ret i1 %call
+; CHECK-LABEL: bb2:
+; CHECK-NEXT:    %cond = icmp eq i32* %ptr, null
+; CHECK-NEXT:    br i1 %cond, label %if.then, label %if.end
+define i1 @bar3(i1 %c1, i32* %ptr) {
+entry:
+  br i1 %c1, label %bb1, label %bb2
+
+bb1:
+  %call = call i1 @testf(i32* nonnull %ptr)
+  ret i1 %call
+
+bb2:                                          ; preds = %entry
+  %cond = icmp eq i32* %ptr, null
+  br i1 %cond, label %if.then, label %if.end
+
+if.then:
+  ret i1 false
+
+if.end:
+  ret i1 true
+}