[AAPointerInfo] fix assertion at the pass-through use of a pointer

[sameerds]

Summary

HandlePassthroughUser may sometimes create a new entry for the OffsetInfo of a
user in the OffsetInfoMap. This can invalidate outstanding references into the
map, including the one which needs to be copied into the new entry. This
produces invalid offset info that can trigger assertions.

Fixed this by not using references at this point. The bug was originally
introduced in commit ID 0dc0a441323d41b4860668f38d290579e0de130c.

[arsenm]

Testcase?

[sameerds]

In D140837#4021788, @arsenm wrote:

Testcase?

I am not sure how to go about writing a reliable test for an invalidated reference into a container, especially a map. It would have to depend on possibly adding enough entries to cause a reallocation, or inserting keys in an order that causes earlier keys to be moved around. What would such a test actually check? That the invalidation "never" happens?

[arsenm]

In D140837#4021833, @sameerds wrote:

In D140837#4021788, @arsenm wrote:

Testcase?

I am not sure how to go about writing a reliable test for an invalidated reference into a container, especially a map. It would have to depend on possibly adding enough entries to cause a reallocation, or inserting keys in an order that causes earlier keys to be moved around. What would such a test actually check? That the invalidation "never" happens?

What does llvm-reduce give you if you just feed your original testcase to it?

[sameerds]

Actually fix the root cause. The previous change was cleaned up too hastily and completely missed the point of the fix.

[ronlieb]

lgtm, passed the 5 internal tests that failed.

[sameerds]

In D140837#4021892, @arsenm wrote:

In D140837#4021833, @sameerds wrote:

In D140837#4021788, @arsenm wrote:

Testcase?

I am not sure how to go about writing a reliable test for an invalidated reference into a container, especially a map. It would have to depend on possibly adding enough entries to cause a reallocation, or inserting keys in an order that causes earlier keys to be moved around. What would such a test actually check? That the invalidation "never" happens?

What does llvm-reduce give you if you just feed your original testcase to it?

It did produce a pretty small testcase, but it was not convincing. The crash only happens with "opt -O3", at the point where a specific pass OpenMPOptCGSCC runs. All optimizations up to that point have no effect on the test IR, but running only that pass does not produce a crash. It's basically a very fragile situation where all the earlier passes produce an application state that just happens to produce the right invalidation inside the map. That's not very robust.

llvm/lib/Transforms/IPO/AttributorAttributes.cpp

ChangeStatus AAPointerInfoFloating::updateImpl(Attributor &A) {
   using namespace AA::PointerInfo;
   ChangeStatus Changed = ChangeStatus::UNCHANGED;
   const DataLayout &DL = A.getDataLayout();
   Value &AssociatedValue = getAssociatedValue();
 
   DenseMap<Value *, OffsetInfo> OffsetInfoMap;
   OffsetInfoMap[&AssociatedValue].insert(0);
 
-  auto HandlePassthroughUser = [&](Value *Usr, const OffsetInfo &PtrOI,
-                                   bool &Follow) {
+  auto HandlePassthroughUser = [&](Value *Usr, Value *CurPtr, bool &Follow) {
+    // One does not simply walk into a map and assign a reference to a possibly
+    // new location. That can cause an invalidation before the assignment
+    // happens, like so:
+    //
+    //   OffsetInfoMap[Usr] = OffsetInfoMap[CurPtr]; /* bad idea! */
+    //
+    // The RHS is a reference that may be invalidated by an insertion caused by
+    // the LHS. So we ensure that the side-effect of the LHS happens first.
+    auto &UsrOI = OffsetInfoMap[Usr];
+    auto &PtrOI = OffsetInfoMap[CurPtr];
     assert(!PtrOI.isUnassigned() &&
            "Cannot pass through if the input Ptr was not visited!");
-    OffsetInfoMap[Usr] = PtrOI;
+    UsrOI = PtrOI;
     Follow = true;
     return true;
   };
 
   const auto *F = getAnchorScope();
   const auto *CI =
       F ? A.getInfoCache().getAnalysisResultForFunction<CycleAnalysis>(*F)
         : nullptr;
   const auto *TLI =
       F ? A.getInfoCache().getTargetLibraryInfoForFunction(*F) : nullptr;
 
   auto UsePred = [&](const Use &U, bool &Follow) -> bool {
     Value *CurPtr = U.get();
     User *Usr = U.getUser();
     LLVM_DEBUG(dbgs() << "[AAPointerInfo] Analyze " << *CurPtr << " in " << *Usr
                       << "\n");
     assert(OffsetInfoMap.count(CurPtr) &&
            "The current pointer offset should have been seeded!");
 
     if (ConstantExpr *CE = dyn_cast<ConstantExpr>(Usr)) {
       if (CE->isCast())
-        return HandlePassthroughUser(Usr, OffsetInfoMap[CurPtr], Follow);
+        return HandlePassthroughUser(Usr, CurPtr, Follow);
       if (CE->isCompare())
         return true;
       if (!isa<GEPOperator>(CE)) {
         LLVM_DEBUG(dbgs() << "[AAPointerInfo] Unhandled constant user " << *CE
                           << "\n");
         return false;
       }
     }
if (auto *GEP = dyn_cast<GEPOperator>(Usr)) {
       }
 
       Follow = collectConstantsForGEP(A, DL, UsrOI, PtrOI, GEP);
       return true;
     }
     if (isa<PtrToIntInst>(Usr))
       return false;
     if (isa<CastInst>(Usr) || isa<SelectInst>(Usr) || isa<ReturnInst>(Usr))
-      return HandlePassthroughUser(Usr, OffsetInfoMap[CurPtr], Follow);
+      return HandlePassthroughUser(Usr, CurPtr, Follow);
 
     // For PHIs we need to take care of the recurrence explicitly as the value
     // might change while we iterate through a loop. For now, we give up if
     // the PHI is not invariant.
     if (isa<PHINode>(Usr)) {
       // Note the order here, the Usr access might change the map, CurPtr is
       // already in it though.
       bool IsFirstPHIUser = !OffsetInfoMap.count(Usr);
if (isa<PHINode>(Usr)) {
       // every Cycle header; if such a node is marked unknown, this will
       // eventually propagate through the whole net of PHIs in the recurrence.
       if (mayBeInCycleHeader(CI, cast<Instruction>(Usr))) {
         auto BaseOI = It->getSecond();
         BaseOI.addToAll(Offset.getZExtValue());
         if (IsFirstPHIUser || BaseOI == UsrOI) {
           LLVM_DEBUG(dbgs() << "[AAPointerInfo] PHI is invariant " << *CurPtr
                             << " in " << *Usr << "\n");
-          return HandlePassthroughUser(Usr, PtrOI, Follow);
+          return HandlePassthroughUser(Usr, CurPtr, Follow);
         }
 
         LLVM_DEBUG(
             dbgs() << "[AAPointerInfo] PHI operand pointer offset mismatch "
                    << *CurPtr << " in " << *Usr << "\n");
         UsrOI.setUnknown();
         Follow = true;
         return true;