[NewGVN] Use PredicateInfo info when previously used for the same ssa.coy intrinsic

[asbirlea]

Summary

Symbolic execution using PredicateInfo is only done for the ssa.copy
intrinsic. It's using two potential sources for building the expression:

1. the Value of the instruction for which the instruction is a copy of, and
2. the Value from the contraint in PredicateInfo

It's possible to get into an infinite loop when choosing between these
two, as described in PR31613.

This patch proposes performing swapping of the two values (i.e. choosing
the second one for the expression), if that same second value was chosen
before; this breaks the cycle.

In the testcases provided, where there is a contradiction between the
value from symbolic execution and assume instruction, NewGVN reduces the
assume to assume(false).

Resolves PR31613.

llvm/lib/Transforms/Scalar/NewGVN.cpp

class NewGVN {
   // SmallPtrSet or DenseSet, for some functions, we spent >20% of all
   // the time in GVN just managing this list.  The bitvector, on the
   // other hand, efficiently supports test/set/clear of both
   // individual and ranges, as well as "find next element" This
   // enables us to use it as a worklist with essentially 0 cost.
   BitVector TouchedInstructions;
 
   DenseMap<const BasicBlock *, std::pair<unsigned, unsigned>> BlockInstRange;
+  mutable DenseMap<const IntrinsicInst *, const Value *> IntrinsicInstPred;
 
 #ifndef NDEBUG
   // Debugging for how many times each block and instruction got processed.
   DenseMap<const Value *, unsigned> ProcessedCount;
 #endif
 
   // DFS info.
   // This contains a mapping from Instructions to DFS numbers.
private:
   const Expression *performSymbolicStoreEvaluation(Instruction *) const;
   ExprResult performSymbolicCallEvaluation(Instruction *) const;
   void sortPHIOps(MutableArrayRef<ValPair> Ops) const;
   const Expression *performSymbolicPHIEvaluation(ArrayRef<ValPair>,
                                                  Instruction *I,
                                                  BasicBlock *PHIBlock) const;
   const Expression *performSymbolicAggrValueEvaluation(Instruction *) const;
   ExprResult performSymbolicCmpEvaluation(Instruction *) const;
-  ExprResult performSymbolicPredicateInfoEvaluation(Instruction *) const;
+  ExprResult performSymbolicPredicateInfoEvaluation(IntrinsicInst *) const;
 
   // Congruence finding.
   bool someEquivalentDominates(const Instruction *, const Instruction *) const;
   Value *lookupOperandLeader(Value *) const;
   CongruenceClass *getClassForExpression(const Expression *E) const;
   void performCongruenceFinding(Instruction *, const Expression *);
   void moveValueToNewCongruenceClass(Instruction *, const Expression *,
                                      CongruenceClass *, CongruenceClass *);
   void moveMemoryToNewCongruenceClass(Instruction *, MemoryAccess *,
                                       CongruenceClass *, CongruenceClass *);
   Value *getNextValueLeader(CongruenceClass *) const;
   const MemoryAccess *getNextMemoryLeader(CongruenceClass *) const;
   bool setMemoryClass(const MemoryAccess *From, CongruenceClass *To);
   CongruenceClass *getMemoryClass(const MemoryAccess *MA) const;
   const MemoryAccess *lookupMemoryLeader(const MemoryAccess *) const;
   bool isMemoryAccessTOP(const MemoryAccess *) const;
 
   // Ranking
   unsigned int getRank(const Value *) const;
   bool shouldSwapOperands(const Value *, const Value *) const;
+  bool shouldSwapOperandsForIntrinsic(const Value *, const Value *,
+                                      const IntrinsicInst *I) const;
 
   // Reachability handling.
   void updateReachableEdge(BasicBlock *, BasicBlock *);
   void processOutgoingEdges(Instruction *, BasicBlock *);
   Value *findConditionEquivalence(Value *) const;
 
   // Elimination.
   struct ValueDFS;
const Expression *NewGVN::performSymbolicLoadEvaluation(Instruction *I) const {
   // If our MemoryLeader is not our defining access, add a use to the
   // MemoryLeader, so that we get reprocessed when it changes.
   if (LE->getMemoryLeader() != DefiningAccess)
     addMemoryUsers(LE->getMemoryLeader(), OriginalAccess);
   return LE;
 }
 
 NewGVN::ExprResult
-NewGVN::performSymbolicPredicateInfoEvaluation(Instruction *I) const {
+NewGVN::performSymbolicPredicateInfoEvaluation(IntrinsicInst *I) const {
   auto *PI = PredInfo->getPredicateInfoFor(I);
   if (!PI)
     return ExprResult::none();
 
   LLVM_DEBUG(dbgs() << "Found predicate info from instruction !\n");
 
   const Optional<PredicateConstraint> &Constraint = PI->getConstraint();
   if (!Constraint)
     return ExprResult::none();
 
   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)) {
+  if (shouldSwapOperandsForIntrinsic(FirstOp, SecondOp, I)) {
     std::swap(FirstOp, SecondOp);
     Predicate = CmpInst::getSwappedPredicate(Predicate);
     AdditionallyUsedValue = CmpOp1;
   }
 
   if (Predicate == CmpInst::ICMP_EQ)
     return ExprResult::some(createVariableOrConstant(FirstOp),
                             AdditionallyUsedValue, PI);

 
 // Evaluate read only and pure calls, and create an expression result.
 NewGVN::ExprResult 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.
     if (auto *ReturnedValue = II->getReturnedArgOperand()) {
       if (II->getIntrinsicID() == Intrinsic::ssa_copy)
-        if (auto Res = performSymbolicPredicateInfoEvaluation(I))
+        if (auto Res = performSymbolicPredicateInfoEvaluation(II))
           return Res;
       return ExprResult::some(createVariableOrConstant(ReturnedValue));
     }
   }
   if (AA->doesNotAccessMemory(CI)) {
     return ExprResult::some(
         createCallExpression(CI, TOPClass->getMemoryLeader()));
   } else if (AA->onlyReadsMemory(CI)) {
#endif
   InstructionsToErase.clear();
   DFSToInstr.clear();
   BlockInstRange.clear();
   TouchedInstructions.clear();
   MemoryAccessToClass.clear();
   PredicateToUsers.clear();
   MemoryToUsers.clear();
   RevisitOnReachabilityChange.clear();
+  IntrinsicInstPred.clear();
 }
 
 // Assign local DFS number mapping to instructions, and leave space for Value
 // PHI's.
 std::pair<unsigned, unsigned> NewGVN::assignDFSNumbers(BasicBlock *B,
                                                        unsigned Start) {
   unsigned End = Start;
   if (MemoryAccess *MemPhi = getMemoryAccess(B)) {

 // have their order swapped when canonicalizing.
 bool NewGVN::shouldSwapOperands(const Value *A, const Value *B) const {
   // Because we only care about a total ordering, and don't rewrite expressions
   // in this order, we order by rank, which will give a strict weak ordering to
   // everything but constants, and then we order by pointer address.
   return std::make_pair(getRank(A), A) > std::make_pair(getRank(B), B);
 }
 
+bool NewGVN::shouldSwapOperandsForIntrinsic(const Value *A, const Value *B,
+                                            const IntrinsicInst *I) const {
+  auto LookupResult = IntrinsicInstPred.find(I);
+  if (shouldSwapOperands(A, B)) {
+    if (LookupResult == IntrinsicInstPred.end())
+      IntrinsicInstPred.insert({I, B});
+    else
+      LookupResult->second = B;
+    return true;
+  }
+
+  if (LookupResult != IntrinsicInstPred.end()) {
+    auto *SeenPredicate = LookupResult->second;
+    if (SeenPredicate) {
+      if (SeenPredicate == B)
+        return true;
+      else
+        LookupResult->second = nullptr;
+    }
+  }
+  return false;
+}
+
 namespace {
 
 class NewGVNLegacyPass : public FunctionPass {
 public:
   // Pass identification, replacement for typeid.
   static char ID;
 
   NewGVNLegacyPass() : FunctionPass(ID) {

llvm/test/Transforms/NewGVN/pr31613_2.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt < %s -passes=newgvn -S | FileCheck %s
+; REQUIRES: asserts
+
+target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-grtev4-linux-gnu"
+
+define hidden void @barrier() align 2 {
+; CHECK-LABEL: @barrier(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[CALLG:%.*]] = tail call i64 @g()
+; CHECK-NEXT:    [[SEL:%.*]] = select i1 undef, i64 0, i64 [[CALLG]]
+; CHECK-NEXT:    [[LOADED:%.*]] = load i64, i64* null, align 8
+; CHECK-NEXT:    [[ADD:%.*]] = add i64 [[LOADED]], 1
+; CHECK-NEXT:    [[SHR17:%.*]] = lshr i64 [[ADD]], 1
+; CHECK-NEXT:    [[SUB:%.*]] = add nsw i64 [[SHR17]], -1
+; CHECK-NEXT:    br label [[FIRST:%.*]]
+; CHECK:       first:
+; CHECK-NEXT:    [[PHI_ONE:%.*]] = phi i64 [ [[SEL]], [[ENTRY:%.*]] ], [ 0, [[FIRST]] ], [ 0, [[THIRD:%.*]] ]
+; CHECK-NEXT:    [[CMP_PHI1_SUB:%.*]] = icmp eq i64 [[PHI_ONE]], [[SUB]]
+; CHECK-NEXT:    br i1 [[CMP_PHI1_SUB]], label [[SECOND:%.*]], label [[FIRST]]
+; CHECK:       second:
+; CHECK-NEXT:    br label [[THIRD]]
+; CHECK:       third:
+; CHECK-NEXT:    br i1 false, label [[SECOND]], label [[FIRST]]
+;
+entry:
+  %callg = tail call i64 @g()
+  %sel = select i1 undef, i64 0, i64 %callg
+
+  %loaded = load i64, i64* null, align 8
+  %add = add i64 %loaded, 1
+  %shr17 = lshr i64 %add, 1
+  %sub = add nsw i64 %shr17, -1
+
+  br label %first
+
+first:
+  %phi_one = phi i64 [ %sel, %entry ], [ 0, %first ], [ 0, %third ]
+  %cmp_phi1_sub = icmp eq i64 %phi_one, %sub
+  br i1 %cmp_phi1_sub, label %second, label %first
+
+second:
+  %phi_two = phi i64 [ %inc, %third ], [ %phi_one, %first ]
+  br label %third
+
+third:
+  %inc = add i64 %phi_two, 1
+  %cmp_inc_sub = icmp eq i64 %inc, %sub
+  br i1 %cmp_inc_sub, label %second, label %first
+}
+
+define hidden void @barrier2() align 2 {
+; CHECK-LABEL: @barrier2(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TMP0:%.*]] = load i64, i64* null, align 8
+; CHECK-NEXT:    [[CALL9:%.*]] = tail call i64 @g()
+; CHECK-NEXT:    [[REM:%.*]] = select i1 undef, i64 0, i64 [[CALL9]]
+; CHECK-NEXT:    [[ADD:%.*]] = add i64 [[TMP0]], 1
+; CHECK-NEXT:    [[SHR17:%.*]] = lshr i64 [[ADD]], 1
+; CHECK-NEXT:    [[SUB:%.*]] = add nsw i64 [[SHR17]], -1
+; CHECK-NEXT:    br label [[MAINLOOP:%.*]]
+; CHECK:       second.exit:
+; CHECK-NEXT:    br label [[FIRST_EXIT:%.*]]
+; CHECK:       first.exit:
+; CHECK-NEXT:    br label [[MAINLOOP]]
+; CHECK:       mainloop:
+; CHECK-NEXT:    [[FIRSTPHI:%.*]] = phi i64 [ [[REM]], [[ENTRY:%.*]] ], [ 0, [[FIRST_EXIT]] ]
+; CHECK-NEXT:    [[FIRSTCMP:%.*]] = icmp eq i64 [[FIRSTPHI]], [[SUB]]
+; CHECK-NEXT:    br i1 [[FIRSTCMP]], label [[SECOND_PREHEADER:%.*]], label [[FIRST_EXIT]]
+; CHECK:       second.preheader:
+; CHECK-NEXT:    br label [[INNERLOOP:%.*]]
+; CHECK:       innerloop:
+; CHECK-NEXT:    br label [[CLEANUP:%.*]]
+; CHECK:       cleanup:
+; CHECK-NEXT:    br i1 false, label [[INNERLOOP]], label [[SECOND_EXIT:%.*]]
+;
+entry:
+  %0 = load i64, i64* null, align 8
+  %call9 = tail call i64 @g()
+  %rem = select i1 undef, i64 0, i64 %call9
+  %add = add i64 %0, 1
+  %shr17 = lshr i64 %add, 1
+  %sub = add nsw i64 %shr17, -1
+  br label %mainloop
+
+second.exit:                       ; preds = %cleanup
+  br label %first.exit
+
+first.exit:                                ; preds = %mainloop, %second.exit
+  br label %mainloop
+
+mainloop:                                         ; preds = %first.exit, %entry
+  %firstphi = phi i64 [ %rem, %entry ], [ 0, %first.exit ]
+  %firstcmp = icmp eq i64 %firstphi, %sub
+  br i1 %firstcmp, label %second.preheader, label %first.exit
+
+second.preheader:                          ; preds = %mainloop
+  br label %innerloop
+
+innerloop:                                    ; preds = %cleanup, %second.preheader
+  %secondphi = phi i64 [ %inc, %cleanup ], [ %firstphi, %second.preheader ]
+  br label %cleanup
+
+cleanup:                                     ; preds = %innerloop
+  %inc = add i64 %secondphi, 1
+  %secondcmp = icmp eq i64 %inc, %sub
+  br i1 %secondcmp, label %innerloop, label %second.exit
+}
+
+declare hidden i64 @g() local_unnamed_addr align 2
+
+define void @barrier3(i64 %arg) {
+; CHECK-LABEL: @barrier3(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br label [[FIRSTLOOP:%.*]]
+; CHECK:       firstloop:
+; CHECK-NEXT:    [[PHI1:%.*]] = phi i64 [ [[ARG:%.*]], [[ENTRY:%.*]] ], [ 0, [[FIRSTLOOP]] ]
+; CHECK-NEXT:    [[CMP1:%.*]] = icmp eq i64 [[PHI1]], -1
+; CHECK-NEXT:    br i1 [[CMP1]], label [[SECONDLOOP:%.*]], label [[FIRSTLOOP]]
+; CHECK:       secondloop:
+; CHECK-NEXT:    call void @llvm.assume(i1 false)
+; CHECK-NEXT:    br label [[SECONDLOOP]]
+;
+entry:
+  br label %firstloop
+
+firstloop:
+  %phi1 = phi i64 [ %arg, %entry ], [ 0, %firstloop ]
+  %cmp1 = icmp eq i64 %phi1, -1
+  br i1 %cmp1, label %secondloop, label %firstloop
+
+secondloop:
+  %phi2 = phi i64 [ %inc, %secondloop ], [ %phi1, %firstloop ]
+  %inc = add i64 %phi2, 1
+  %cmp2 = icmp eq i64 %inc, -1
+  call void @llvm.assume(i1 %cmp2)
+  br label %secondloop
+}
+
+declare void @llvm.assume(i1)