[PredicateInfo] Add a common method to interpret predicate as cmp constraint

[nikic]

Summary

Both users of predicteinfo (NewGVN and SCCP) are interested in getting a cmp constraint on the predicated value. They currently implement separate logic for this. This patch adds a common method for this in PredicateWithCondition (it would be nice to drop the PredicateBase/PredicateWithCondition split ... I saw you had a patch for that).

This enables a missing bit of PredicateInfo handling in SCCP: Now the predicate on the condition itself is also used. For switches it means we know that the switched-on value is the same as the case value. For assumes/branches we know that the condition is true or false.

[nikic]

Relax assertion. RenamedOp may not be accurate due to https://reviews.llvm.org/D78133#2145094, so don't assert this for now.

[fhahn]

LGTM, thanks!

(it would be nice to drop the PredicateBase/PredicateWithCondition split ... I saw you had a patch for that).

Yes, I have to dig it up again...

llvm/include/llvm/Transforms/Utils/PredicateInfo.h

108

How about returning Optional<std::pair<CmpInst::Predicate &, Value *>>? That would seem more explicit to me , but its mostly personal preference I think :)

[nikic]

Return Optional<PredicateConstraint>.

What do you think about this variant? Something I have in mind here as a possible followup is to change the way we represent predicates away from storing the raw condition, which has renaming issues we only partially mitigated with RenamedOp, towards storing the PredicateConstraint introduced here directly. This makes sure that we cannot go out of sync between the PredicateInfo construction logic and the retrieval of the condition. (For now all conditions have the form of "cmp", but if needed this could be made polymorphic in the future.)

[nikic]

Rebase

[fhahn]

In D83640#2159284, @nikic wrote:

Return Optional<PredicateConstraint>.

What do you think about this variant? Something I have in mind here as a possible followup is to change the way we represent predicates away from storing the raw condition, which has renaming issues we only partially mitigated with RenamedOp, towards storing the PredicateConstraint introduced here directly. This makes sure that we cannot go out of sync between the PredicateInfo construction logic and the retrieval of the condition. (For now all conditions have the form of "cmp", but if needed this could be made polymorphic in the future.)

Thanks, that looks good.

Just referring to a condition in the IR makes things more flexible in theory I think, e.g. if the OtherOp part of the condition is modified after PredicateInfo construction. The current users (NewGVN, SCCP) only do modifications after all analysis is finished, so that would not matter for them. If there are clients in the future that really need this, it's probably fine to think about it then.

llvm/include/llvm/Transforms/Utils/PredicateInfo.h

 class AssumptionCache;
 class DominatorTree;
 class Function;
 class IntrinsicInst;
 class raw_ostream;
 
 enum PredicateType { PT_Branch, PT_Assume, PT_Switch };
 
+/// Constraint for a predicate of the form "cmp Pred Op, OtherOp", where Op
+/// is the value the constraint applies to (the ssa.copy result).
+struct PredicateConstraint {
+  CmpInst::Predicate Predicate;
+  Value *OtherOp;
+};
+
 // 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.
public:
   PredicateBase &operator=(const PredicateBase &) = delete;
   PredicateBase() = delete;
   virtual ~PredicateBase() = default;
   static bool classof(const PredicateBase *PB) {
     return PB->Type == PT_Assume || PB->Type == PT_Branch ||
            PB->Type == PT_Switch;
   }
 
+  /// Fetch condition in the form of PredicateConstraint, if possible.
+  Optional<PredicateConstraint> getConstraint() const;
+
 protected:
   PredicateBase(PredicateType PT, Value *Op, Value *Condition)
       : Type(PT), OriginalOp(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 PredicateBase {

llvm/lib/Transforms/Scalar/NewGVN.cpp

 const Expression *
 NewGVN::performSymbolicPredicateInfoEvaluation(Instruction *I) const {
   auto *PI = PredInfo->getPredicateInfoFor(I);
   if (!PI)
     return nullptr;
 
   LLVM_DEBUG(dbgs() << "Found predicate info from instruction !\n");
 
-  auto *CopyOf = I->getOperand(0);
-  auto *Cond = PI->Condition;
-
-  // If this a copy of the condition, it must be either true or false depending
-  // on the predicate info type and edge.
-  if (CopyOf == Cond) {
-    // We should not need to add predicate users because the predicate info is
-    // already a use of this operand.
-    if (isa<PredicateAssume>(PI))
-      return createConstantExpression(ConstantInt::getTrue(Cond->getType()));
-    if (auto *PBranch = dyn_cast<PredicateBranch>(PI)) {
-      if (PBranch->TrueEdge)
-        return createConstantExpression(ConstantInt::getTrue(Cond->getType()));
-      return createConstantExpression(ConstantInt::getFalse(Cond->getType()));
-    }
-    if (auto *PSwitch = dyn_cast<PredicateSwitch>(PI))
-      return createConstantExpression(cast<Constant>(PSwitch->CaseValue));
-  }
-
-  // Not a copy of the condition, so see what the predicates tell us about this
-  // value.  First, though, we check to make sure the value is actually a copy
-  // of one of the condition operands. It's possible, in certain cases, for it
-  // to be a copy of a predicateinfo copy. In particular, if two branch
-  // operations use the same condition, and one branch dominates the other, we
-  // will end up with a copy of a copy.  This is currently a small deficiency in
-  // predicateinfo.  What will end up happening here is that we will value
-  // number both copies the same anyway.
-
-  // Everything below relies on the condition being a comparison.
-  auto *Cmp = dyn_cast<CmpInst>(Cond);
-  if (!Cmp)
+  const Optional<PredicateConstraint> &Constraint = PI->getConstraint();
+  if (!Constraint)
     return nullptr;
 
-  if (CopyOf != Cmp->getOperand(0) && CopyOf != Cmp->getOperand(1)) {
-    LLVM_DEBUG(dbgs() << "Copy is not of any condition operands!\n");
-    return nullptr;
-  }
-  Value *FirstOp = lookupOperandLeader(Cmp->getOperand(0));
-  Value *SecondOp = lookupOperandLeader(Cmp->getOperand(1));
-  bool SwappedOps = false;
+  CmpInst::Predicate Predicate = Constraint->Predicate;
+  Value *CmpOp0 = I->getOperand(0);
+  Value *CmpOp1 = Constraint->OtherOp;
+
+  Value *FirstOp = lookupOperandLeader(CmpOp0);
+  Value *SecondOp = lookupOperandLeader(CmpOp1);
+  Value *AdditionallyUsedValue = CmpOp0;
+
   // Sort the ops.
   if (shouldSwapOperands(FirstOp, SecondOp)) {
     std::swap(FirstOp, SecondOp);
-    SwappedOps = true;
+    Predicate = CmpInst::getSwappedPredicate(Predicate);
+    AdditionallyUsedValue = CmpOp1;
   }
-  CmpInst::Predicate Predicate =
-      SwappedOps ? Cmp->getSwappedPredicate() : Cmp->getPredicate();
 
-  if (isa<PredicateAssume>(PI)) {
-    // If we assume the operands are equal, then they are equal.
-    if (Predicate == CmpInst::ICMP_EQ) {
-      addPredicateUsers(PI, I);
-      addAdditionalUsers(SwappedOps ? Cmp->getOperand(1) : Cmp->getOperand(0),
-                         I);
-      return createVariableOrConstant(FirstOp);
-    }
-  }
-  if (const auto *PBranch = dyn_cast<PredicateBranch>(PI)) {
-    // If we are *not* a copy of the comparison, we may equal to the other
-    // operand when the predicate implies something about equality of
-    // operations.  In particular, if the comparison is true/false when the
-    // operands are equal, and we are on the right edge, we know this operation
-    // is equal to something.
-    if ((PBranch->TrueEdge && Predicate == CmpInst::ICMP_EQ) ||
-        (!PBranch->TrueEdge && Predicate == CmpInst::ICMP_NE)) {
-      addPredicateUsers(PI, I);
-      addAdditionalUsers(SwappedOps ? Cmp->getOperand(1) : Cmp->getOperand(0),
-                         I);
-      return createVariableOrConstant(FirstOp);
-    }
-    // Handle the special case of floating point.
-    if (((PBranch->TrueEdge && Predicate == CmpInst::FCMP_OEQ) ||
-         (!PBranch->TrueEdge && Predicate == CmpInst::FCMP_UNE)) &&
-        isa<ConstantFP>(FirstOp) && !cast<ConstantFP>(FirstOp)->isZero()) {
-      addPredicateUsers(PI, I);
-      addAdditionalUsers(SwappedOps ? Cmp->getOperand(1) : Cmp->getOperand(0),
-                         I);
-      return createConstantExpression(cast<Constant>(FirstOp));
-    }
-  }
+    addAdditionalUsers(AdditionallyUsedValue, I);
+
+  if (Predicate == CmpInst::FCMP_OEQ && isa<ConstantFP>(FirstOp) &&
+      !cast<ConstantFP>(FirstOp)->isZero()) {
+    addAdditionalUsers(AdditionallyUsedValue, I);
+
   return nullptr;
 }
 
 // Evaluate read only and pure calls, and create an expression result.
 const Expression *NewGVN::performSymbolicCallEvaluation(Instruction *I) const {
   auto *CI = cast<CallInst>(I);
   if (auto *II = dyn_cast<IntrinsicInst>(I)) {
     // Intrinsics with the returned attribute are copies of arguments.

llvm/lib/Transforms/Scalar/SCCP.cpp

if (II->getIntrinsicID() == Intrinsic::ssa_copy) {
       if (ValueState[&CB].isOverdefined())
         return;
 
       Value *CopyOf = CB.getOperand(0);
       ValueLatticeElement CopyOfVal = getValueState(CopyOf);
       auto *PI = getPredicateInfoFor(&CB);
       assert(PI && "Missing predicate info for ssa.copy");
 
-      CmpInst *Cmp;
-      bool TrueEdge;
-      if (auto *PBranch = dyn_cast<PredicateBranch>(PI)) {
-        Cmp = dyn_cast<CmpInst>(PBranch->Condition);
-        TrueEdge = PBranch->TrueEdge;
-      } else if (auto *PAssume = dyn_cast<PredicateAssume>(PI)) {
-        Cmp = dyn_cast<CmpInst>(PAssume->Condition);
-        TrueEdge = true;
-      } else {
-        mergeInValue(ValueState[&CB], &CB, CopyOfVal);
-        return;
-      }
-
-      // Everything below relies on the condition being a comparison.
-      if (!Cmp) {
+      const Optional<PredicateConstraint> &Constraint = PI->getConstraint();
+      if (!Constraint) {
         mergeInValue(ValueState[&CB], &CB, CopyOfVal);
         return;
       }
 
-      Value *RenamedOp = PI->RenamedOp;
-      Value *CmpOp0 = Cmp->getOperand(0);
-      Value *CmpOp1 = Cmp->getOperand(1);
-      // Bail out if neither of the operands matches RenamedOp.
-      if (CmpOp0 != RenamedOp && CmpOp1 != RenamedOp) {
-        mergeInValue(ValueState[&CB], &CB, getValueState(CopyOf));
-        return;
-      }
+      CmpInst::Predicate Pred = Constraint->Predicate;
+      Value *OtherOp = Constraint->OtherOp;
 
-      auto Pred = Cmp->getPredicate();
-      if (CmpOp1 == RenamedOp) {
-        std::swap(CmpOp0, CmpOp1);
-        Pred = Cmp->getSwappedPredicate();
-      }
-
-      // Wait until CmpOp1 is resolved.
-      if (getValueState(CmpOp1).isUnknown()) {
-        addAdditionalUser(CmpOp1, &CB);
+      // Wait until OtherOp is resolved.
+      if (getValueState(OtherOp).isUnknown()) {
+        addAdditionalUser(OtherOp, &CB);
         return;
       }
 
-      // The code below relies on PredicateInfo only inserting copies for the
-      // true branch when the branch condition is an AND and only inserting
-      // copies for the false branch when the branch condition is an OR. This
-      // ensures we can intersect the range from the condition with the range of
-      // CopyOf.
-      if (!TrueEdge)
-        Pred = CmpInst::getInversePredicate(Pred);
-
-      ValueLatticeElement CondVal = getValueState(CmpOp1);
+      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())
           ImposedCR = ConstantRange::makeAllowedICmpRegion(
               Pred, CondVal.getConstantRange());
 
         // Combine range info for the original value with the new range from the
         // condition.
         auto CopyOfCR = CopyOfVal.isConstantRange()
                             ? CopyOfVal.getConstantRange()
                             : ConstantRange::getFull(
                                   DL.getTypeSizeInBits(CopyOf->getType()));
         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(CmpOp1, &CB);
+        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));
         return;
       } else if (Pred == CmpInst::ICMP_EQ && CondVal.isConstant()) {
         // For non-integer values or integer constant expressions, only
         // propagate equal constants.
-        addAdditionalUser(CmpOp1, &CB);
+        addAdditionalUser(OtherOp, &CB);
         mergeInValue(IV, &CB, CondVal);
         return;
       }
 
       return (void)mergeInValue(IV, &CB, CopyOfVal);
     }
   }
 

llvm/lib/Transforms/Utils/PredicateInfo.cpp

PredicateInfo::~PredicateInfo() {
 
   for (Function *F : FunctionPtrs) {
     assert(F->user_begin() == F->user_end() &&
            "PredicateInfo consumer did not remove all SSA copies.");
     F->eraseFromParent();
   }
 }
 
+Optional<PredicateConstraint> PredicateBase::getConstraint() const {
+  switch (Type) {
+  case PT_Assume:
+  case PT_Branch: {
+    bool TrueEdge = true;
+    if (auto *PBranch = dyn_cast<PredicateBranch>(this))
+      TrueEdge = PBranch->TrueEdge;
+
+    if (Condition == RenamedOp) {
+      return {{CmpInst::ICMP_EQ,
+               TrueEdge ? ConstantInt::getTrue(Condition->getType())
+                        : ConstantInt::getFalse(Condition->getType())}};
+    }
+
+    CmpInst *Cmp = dyn_cast<CmpInst>(Condition);
+    assert(Cmp && "Condition should be a CmpInst");
+
+    CmpInst::Predicate Pred;
+    Value *OtherOp;
+    if (Cmp->getOperand(0) == RenamedOp) {
+      Pred = Cmp->getPredicate();
+      OtherOp = Cmp->getOperand(1);
+    } else if (Cmp->getOperand(1) == RenamedOp) {
+      Pred = Cmp->getSwappedPredicate();
+      OtherOp = Cmp->getOperand(0);
+    } else {
+      // TODO: Make this an assertion once RenamedOp is fully accurate.
+      return None;
+    }
+
+    // Invert predicate along false edge.
+    if (!TrueEdge)
+      Pred = CmpInst::getInversePredicate(Pred);
+
+    return {{Pred, OtherOp}};
+  }
+  case PT_Switch:
+    if (Condition != RenamedOp) {
+      // TODO: Make this an assertion once RenamedOp is fully accurate.
+      return None;
+    }
+
+    return {{CmpInst::ICMP_EQ, cast<PredicateSwitch>(this)->CaseValue}};
+  }
+  llvm_unreachable("Unknown predicate type");
+}
+
 void PredicateInfo::verifyPredicateInfo() const {}
 
 char PredicateInfoPrinterLegacyPass::ID = 0;
 
 PredicateInfoPrinterLegacyPass::PredicateInfoPrinterLegacyPass()
     : FunctionPass(ID) {
   initializePredicateInfoPrinterLegacyPassPass(
       *PassRegistry::getPassRegistry());

llvm/test/Transforms/SCCP/predicateinfo-cond.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -S -ipsccp < %s | FileCheck %s
 
 ; Test that information about the true/false value of conditions themselves
 ; is also used, not information implied by comparisions.
 
 define i32 @switch(i32 %x) {
 ; CHECK-LABEL: @switch(
 ; CHECK-NEXT:    switch i32 [[X:%.*]], label [[CASE_DEFAULT:%.*]] [
 ; CHECK-NEXT:    i32 0, label [[CASE_0:%.*]]
 ; CHECK-NEXT:    i32 2, label [[CASE_2:%.*]]
 ; CHECK-NEXT:    ]
 ; CHECK:       case.0:
-; CHECK-NEXT:    [[ADD:%.*]] = add i32 [[X]], 1
 ; CHECK-NEXT:    br label [[END:%.*]]
 ; CHECK:       case.2:
-; CHECK-NEXT:    [[SUB:%.*]] = sub i32 [[X]], 1
 ; CHECK-NEXT:    br label [[END]]
 ; CHECK:       case.default:
 ; CHECK-NEXT:    br label [[END]]
 ; CHECK:       end:
-; CHECK-NEXT:    [[PHI:%.*]] = phi i32 [ [[ADD]], [[CASE_0]] ], [ [[SUB]], [[CASE_2]] ], [ 1, [[CASE_DEFAULT]] ]
-; CHECK-NEXT:    ret i32 [[PHI]]
+; CHECK-NEXT:    ret i32 1
 ;
   switch i32 %x, label %case.default [
   i32 0, label %case.0
   i32 2, label %case.2
   ]
 
 case.0:
   %add = add i32 %x, 1
end:
   %phi = phi i32 [ %add, %case.0 ], [ %sub, %case.2 ], [ 1, %case.default]
   ret i32 %phi
 }
 
 define i1 @assume(i32 %x) {
 ; CHECK-LABEL: @assume(
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp sge i32 [[X:%.*]], 0
 ; CHECK-NEXT:    call void @llvm.assume(i1 [[CMP]])
-; CHECK-NEXT:    ret i1 [[CMP]]
+; CHECK-NEXT:    ret i1 true
 ;
   %cmp = icmp sge i32 %x, 0
   call void @llvm.assume(i1 %cmp)
   ret i1 %cmp
 }
 
 define i32 @branch(i32 %x) {
 ; CHECK-LABEL: @branch(
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp sge i32 [[X:%.*]], 0
 ; CHECK-NEXT:    br i1 [[CMP]], label [[IF_THEN1:%.*]], label [[IF_THEN2:%.*]]
 ; CHECK:       if.then1:
-; CHECK-NEXT:    br i1 [[CMP]], label [[IF2_THEN1:%.*]], label [[IF2_THEN2:%.*]]
+; CHECK-NEXT:    br label [[IF2_THEN1:%.*]]
 ; CHECK:       if2.then1:
 ; CHECK-NEXT:    br label [[IF2_END:%.*]]
-; CHECK:       if2.then2:
-; CHECK-NEXT:    br label [[IF2_END]]
 ; CHECK:       if2.end:
-; CHECK-NEXT:    [[PHI:%.*]] = phi i32 [ 0, [[IF2_THEN1]] ], [ 1, [[IF2_THEN2]] ]
-; CHECK-NEXT:    ret i32 [[PHI]]
+; CHECK-NEXT:    ret i32 0
 ; CHECK:       if.then2:
-; CHECK-NEXT:    br i1 [[CMP]], label [[IF3_THEN1:%.*]], label [[IF3_THEN2:%.*]]
-; CHECK:       if3.then1:
-; CHECK-NEXT:    br label [[IF3_END:%.*]]
+; CHECK-NEXT:    br label [[IF3_THEN2:%.*]]
 ; CHECK:       if3.then2:
-; CHECK-NEXT:    br label [[IF3_END]]
+; CHECK-NEXT:    br label [[IF3_END:%.*]]
 ; CHECK:       if3.end:
-; CHECK-NEXT:    [[PHI2:%.*]] = phi i32 [ 0, [[IF3_THEN1]] ], [ 1, [[IF3_THEN2]] ]
-; CHECK-NEXT:    ret i32 [[PHI2]]
+; CHECK-NEXT:    ret i32 1
 ;
   %cmp = icmp sge i32 %x, 0
   br i1 %cmp, label %if.then1, label %if.then2
 
 if.then1:
   br i1 %cmp, label %if2.then1, label %if2.then2
 
 if2.then1: