[ObjC][ARC] Fix non-deterministic behavior in ProvenanceAnalysis

[ahatanak]

Summary

Stop reordering the pointers passed in ProvenanceAnalysis::related based on their values. That was causing non-determinism as the call to relatedCheck(A, B) isn't guaranteed to return the same result as relatedCheck(B, A).

Revert the following three commits (except the original test case in related-check.ll):

665e47777df17db406c698d57b4f3c28d67c432e
295861514e0d1e48df2918b630dd692ac27ee0de
d877e3fe71676b0ff10410d80456b35cdd5bf796

These changes shouldn't be necessary once the call to std::swap is removed.

[ahatanak]

The downside of removing the call to std::swap is that we can no longer reuse the result of related(A, B) when related(B, A) is called, but probably that doesn't have a large impact on compile time.

We need this change because we found another case where assert(relatedCheck(B, A) == Result) in ProvenanceAnalysis::related was failing. The assertion was failing because BasicAAResult::alias(A, B)and BasicAAResult::alias(B, A) were giving different answers.

[akyrtzi]

llvm/test/Transforms/ObjCARC/related-check.ll

120

Does this need to be removed? I assume it was a non-deterministic test case.

[ahatanak]

llvm/test/Transforms/ObjCARC/related-check.ll

120

We can probably leave those test cases there, but they weren't in the original test case committed in https://reviews.llvm.org/D135376. The test cases were added in the two patches I committed later and were added only to check the assertion assert(relatedCheck(B, A) == Result) was no longer failing.

llvm/lib/Transforms/ObjCARC/ProvenanceAnalysis.cpp

 
 using namespace llvm;
 using namespace llvm::objcarc;
 
 bool ProvenanceAnalysis::relatedSelect(const SelectInst *A,
                                        const Value *B) {
   // If the values are Selects with the same condition, we can do a more precise
   // check: just check for relations between the values on corresponding arms.
-  if (const SelectInst *SB = dyn_cast<SelectInst>(B)) {
+  if (const SelectInst *SB = dyn_cast<SelectInst>(B))
     if (A->getCondition() == SB->getCondition())
       return related(A->getTrueValue(), SB->getTrueValue()) ||
              related(A->getFalseValue(), SB->getFalseValue());
 
-    // Check both arms of B individually. Return false if neither arm is related
-    // to A.
-    if (!(related(SB->getTrueValue(), A) || related(SB->getFalseValue(), A)))
-      return false;
-  }
-
   // Check both arms of the Select node individually.
   return related(A->getTrueValue(), B) || related(A->getFalseValue(), B);
 }
 
 bool ProvenanceAnalysis::relatedPHI(const PHINode *A,
                                     const Value *B) {
-
-  auto comparePHISources = [this](const PHINode *PNA, const Value *B) -> bool {
-    // Check each unique source of the PHI node against B.
-    SmallPtrSet<const Value *, 4> UniqueSrc;
-    for (Value *PV1 : PNA->incoming_values()) {
-      if (UniqueSrc.insert(PV1).second && related(PV1, B))
-        return true;
-    }
-
-    // All of the arms checked out.
-    return false;
-  };
-
-  if (const PHINode *PNB = dyn_cast<PHINode>(B)) {
-    // If the values are PHIs in the same block, we can do a more precise as
-    // well as efficient check: just check for relations between the values on
-    // corresponding edges.
+  // If the values are PHIs in the same block, we can do a more precise as well
+  // as efficient check: just check for relations between the values on
+  if (const PHINode *PNB = dyn_cast<PHINode>(B))
     if (PNB->getParent() == A->getParent()) {
       for (unsigned i = 0, e = A->getNumIncomingValues(); i != e; ++i)
         if (related(A->getIncomingValue(i),
                     PNB->getIncomingValueForBlock(A->getIncomingBlock(i))))
           return true;
       return false;
     }
 
-    if (!comparePHISources(PNB, A))
-      return false;
+  // Check each unique source of the PHI node against B.
+  SmallPtrSet<const Value *, 4> UniqueSrc;
+  for (Value *PV1 : A->incoming_values()) {
+    if (UniqueSrc.insert(PV1).second && related(PV1, B))
+      return true;
   }
 
-  return comparePHISources(A, B);
+  // All of the arms checked out.
+  return false;
 }
 
 /// Test if the value of P, or any value covered by its provenance, is ever
 /// stored within the function (not counting callees).
 static bool IsStoredObjCPointer(const Value *P) {
   SmallPtrSet<const Value *, 8> Visited;
   SmallVector<const Value *, 8> Worklist;
   Worklist.push_back(P);
bool ProvenanceAnalysis::relatedCheck(const Value *A, const Value *B) {
   case AliasResult::MayAlias:
     break;
   }
 
   bool AIsIdentified = IsObjCIdentifiedObject(A);
   bool BIsIdentified = IsObjCIdentifiedObject(B);
 
   // An ObjC-Identified object can't alias a load if it is never locally stored.
-
+  if (AIsIdentified) {
     // Check for an obvious escape.
-  if ((AIsIdentified && isa<LoadInst>(B) && !IsStoredObjCPointer(A)) ||
-      (BIsIdentified && isa<LoadInst>(A) && !IsStoredObjCPointer(B)))
-    return false;
-
-  if ((AIsIdentified && isa<LoadInst>(B)) ||
-      (BIsIdentified && isa<LoadInst>(A)))
-    return true;
-
+    if (isa<LoadInst>(B))
+      return IsStoredObjCPointer(A);
+    if (BIsIdentified) {
+      // Check for an obvious escape.
+      if (isa<LoadInst>(A))
+        return IsStoredObjCPointer(B);
       // Both pointers are identified and escapes aren't an evident problem.
-  if (AIsIdentified && BIsIdentified && !isa<LoadInst>(A) && !isa<LoadInst>(B))
       return false;
+    }
+  } else if (BIsIdentified) {
+    // Check for an obvious escape.
+    if (isa<LoadInst>(A))
+      return IsStoredObjCPointer(B);
+  }
 
    // Special handling for PHI and Select.
   if (const PHINode *PN = dyn_cast<PHINode>(A))
     return relatedPHI(PN, B);
   if (const PHINode *PN = dyn_cast<PHINode>(B))
     return relatedPHI(PN, A);
   if (const SelectInst *S = dyn_cast<SelectInst>(A))
     return relatedSelect(S, B);
bool ProvenanceAnalysis::related(const Value *A, const Value *B) {
 
   // Quick check.
   if (A == B)
     return true;
 
   // Begin by inserting a conservative value into the map. If the insertion
   // fails, we have the answer already. If it succeeds, leave it there until we
   // compute the real answer to guard against recursive queries.
-  if (A > B) std::swap(A, B);
   std::pair<CachedResultsTy::iterator, bool> Pair =
     CachedResults.insert(std::make_pair(ValuePairTy(A, B), true));
   if (!Pair.second)
     return Pair.first->second;
 
   bool Result = relatedCheck(A, B);
-  assert(relatedCheck(B, A) == Result &&
-         "relatedCheck result depending on order of parameters!");
   CachedResults[ValuePairTy(A, B)] = Result;
   return Result;
 }

llvm/test/Transforms/ObjCARC/related-check.ll

 if.end19:                                         ; preds = %if.end18, %for.body
   call void @llvm.lifetime.end.p0(i64 4, ptr nonnull %personalized) #4
   call void @llvm.lifetime.end.p0(i64 4, ptr nonnull %persistent) #4
   %inc = add nuw nsw i32 %i.032, 1
   %exitcond.not = icmp eq i32 %inc, %argc
   br i1 %exitcond.not, label %for.cond.cleanup.loopexit, label %for.body
 }
 
-; CHECK-LABEL: define ptr @foo() {
-; CHECK-NOT: @llvm.objc
-; CHECK: ret ptr %
-
-define ptr @foo() {
-  %t = alloca ptr, align 8
-  %v4 = load ptr, ptr @global1, align 8
-  %v5 = tail call ptr @llvm.objc.retain(ptr %v4)
-  store ptr %v4, ptr %t, align 8
-  %v13 = load ptr, ptr @"OBJC_CLASSLIST_REFERENCES_$_", align 8
-  %call78 = call ptr @bar(ptr %v13)
-  call void @llvm.objc.release(ptr %v4)
-  ret ptr %call78
-}
-
-; CHECK-LABEL: define void @test_select(
-; CHECK: call ptr @llvm.objc.retain(
-; CHECK: call void @llvm.objc.release(
-
-define void @test_select(i1 %c0, i1 %c1, ptr %p0, ptr %p1) {
-  %cond = select i1 %c0, ptr %p0, ptr %p1
-  %cond5 = select i1 %c0, ptr %p1, ptr %p0
-  %cond14 = select i1 %c1, ptr %cond5, ptr null
-  call ptr @llvm.objc.retain(ptr %cond14)
-  call void @llvm.objc.release(ptr %cond)
-  ret void
-}
-
-declare ptr @bar(ptr)
-
-declare ptr @llvm.objc.retain(ptr)
-
 ; Function Attrs: argmemonly mustprogress nocallback nofree nosync nounwind willreturn
 declare void @llvm.lifetime.start.p0(i64 immarg, ptr nocapture) #2
 
 ; Function Attrs: argmemonly mustprogress nocallback nofree nosync nounwind willreturn
 declare void @llvm.lifetime.end.p0(i64 immarg, ptr nocapture) #2
 
 ; Function Attrs: inaccessiblememonly mustprogress nocallback nofree nosync nounwind willreturn
 declare void @llvm.objc.clang.arc.noop.use(...) #5