[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

106

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 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;
   }
 
+  /// Fetch the predicate constraint in the form "cmp Pred Op, OtherOp",
+  /// where Op is the ssa.copy() result. Returns true and populates
+  /// Pred/OtherOp if successful, otherwise returns false.
+  bool getAsCmp(CmpInst::Predicate &Pred, Value *&OtherOp) const;
+
 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.

llvm/lib/Transforms/Scalar/NewGVN.cpp

if (!PI)
     return nullptr;
 
   LLVM_DEBUG(dbgs() << "Found predicate info from instruction !\n");
 
   auto *PWC = dyn_cast<PredicateWithCondition>(PI);
   if (!PWC)
     return nullptr;
 
-  auto *CopyOf = I->getOperand(0);
-  auto *Cond = PWC->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)
+  CmpInst::Predicate Predicate;
+  Value *CmpOp0 = I->getOperand(0);
+  Value *CmpOp1;
+  if (!PWC->getAsCmp(Predicate, CmpOp1))
     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;
+  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

void SCCPSolver::handleCallResult(CallBase &CB) {
 
   if (auto *II = dyn_cast<IntrinsicInst>(&CB)) {
     if (II->getIntrinsicID() == Intrinsic::ssa_copy) {
       if (ValueState[&CB].isOverdefined())
         return;
 
       Value *CopyOf = CB.getOperand(0);
       ValueLatticeElement CopyOfVal = getValueState(CopyOf);
-      auto *PI = getPredicateInfoFor(&CB);
+      auto *PI = cast<PredicateWithCondition>(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) {
+      CmpInst::Predicate Pred;
+      Value *OtherOp;
+      if (!PI->getAsCmp(Pred, OtherOp)) {
         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));
+      // Wait until OtherOp is resolved.
+      if (getValueState(OtherOp).isUnknown()) {
+        addAdditionalUser(OtherOp, &CB);
         return;
       }
 
-      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);
-        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();
   }
 }
 
+bool PredicateWithCondition::getAsCmp(CmpInst::Predicate &Pred,
+                                      Value *&OtherOp) 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) {
+      Pred = CmpInst::ICMP_EQ;
+      OtherOp = TrueEdge
+          ? ConstantInt::getTrue(Condition->getType())
+          : ConstantInt::getFalse(Condition->getType());
+      return true;
+    }
+
+    CmpInst *Cmp = dyn_cast<CmpInst>(Condition);
+    assert(Cmp && "Condition should be a CmpInst");
+
+    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 false;
+    }
+
+    // Invert predicate along false edge.
+    if (!TrueEdge)
+      Pred = CmpInst::getInversePredicate(Pred);
+
+    return true;
+  }
+  case PT_Switch:
+    if (Condition != RenamedOp) {
+      // TODO: Make this an assertion once RenamedOp is fully accurate.
+      return false;
+    }
+
+    Pred = CmpInst::ICMP_EQ;
+    OtherOp = cast<PredicateSwitch>(this)->CaseValue;
+    return true;
+  }
+  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: