[MemorySSA] Restrict optimizations after a PhiTranslation.

[asbirlea]

Summary

Merging alias results from different paths, when a path did phi
translation is not necesarily correct. Conservatively terminate such paths.
Aimed to fix PR46156.

[fhahn]

llvm/lib/Analysis/MemorySSA.cpp

528

might be worth adding a comment, describing what it means (and when it will be reset).

Also, would it make sense to move this to a datastructure already tied to a set of paths that are explored together, e.g. the UpwardsMemoryQuery? The current approach seems fine to me, I am just wondering if we could reduce the scope of the variable a bit (and avoid relying on the reset calls).

[asbirlea]

llvm/lib/Analysis/MemorySSA.cpp

528

I believe the current approach does narrow the scope. It's reseting the state after optimizing towards a phi, which is the join point where we need to stop optimizing in the presence of a phi translation. The UpwardsMemoryQuery contains info about the query itself, and it is set at the start of the search (in findClobber). The scope of the bool needs to be similar to that of VisitedPhis, that of internal bookkeeping for a search, and very much related to phi optimization.

I'll add a comment to clarify.

[asbirlea]

Add comments.

[fhahn]

LGTM, thanks for adding he comments.

llvm/lib/Analysis/MemorySSA.cpp

528

Thanks, agreed it seems in line with the way caching/invalidation is done throughout here and changing that would require bigger changes without obvious benefit.

[george.burgess.iv]

lgtm with a few tiny nits. thanks for working on this!

llvm/include/llvm/Analysis/MemorySSA.h

1246

super tiny nit: can we bring this field below DT so we save padding in this struct's layout?

llvm/lib/Analysis/MemorySSA.cpp

530

nit: referencing the PR might help add useful context

[asbirlea]

Address comments.

[fhahn]

llvm/lib/Analysis/MemorySSA.cpp

612

I think currently we only set PerfomedPhiTranslation to true if we preformed phi translation for the first visited upwards def (we only check the status for the iterator of the first def, which will be copied and only the copies will be updated). But we could also perform phi translation for other defs we visit in with the iterator.

I think this is causing https://bugs.llvm.org/show_bug.cgi?id=47498 and I think we should set PerfomedPhiTranslation to true, if we do phi translations for any def visited in the iterator. I went ahead and pushed c4f1b3144184e4c276a7e7c801cbcd4ac3c573ba which changes the iterator to update a pointer to a bool to unblock a test-suite failure on PPC. I would appreciate if you could take a quick look to confirm this is indeed the expected behavior and I did not miss anything. Thanks!

[asbirlea]

llvm/lib/Analysis/MemorySSA.cpp

612

You're right, this was missing the bools set by the internal iterations. Thank you for the fix.

llvm/include/llvm/Analysis/MemorySSA.h

upward_defs_iterator &operator++() {
     ++DefIterator;
     if (DefIterator != OriginalAccess->defs_end())
       fillInCurrentPair();
     return *this;
   }
 
   BasicBlock *getPhiArgBlock() const { return DefIterator.getPhiArgBlock(); }
 
+  bool performedPhiTranslation() const { return PerformedPhiTranslation; }
+
 private:
   void fillInCurrentPair() {
     CurrentPair.first = *DefIterator;
     if (WalkingPhi && Location.Ptr) {
       PHITransAddr Translator(
           const_cast<Value *>(Location.Ptr),
           OriginalAccess->getBlock()->getModule()->getDataLayout(), nullptr);
       if (!Translator.PHITranslateValue(OriginalAccess->getBlock(),
                                         DefIterator.getPhiArgBlock(), DT,
                                         false)) {
         if (Translator.getAddr() != Location.Ptr) {
           CurrentPair.second = Location.getWithNewPtr(Translator.getAddr());
+          PerformedPhiTranslation = true;
           return;
         }
       } else {
         CurrentPair.second = Location.getWithNewSize(LocationSize::unknown());
         return;
       }
     }
     CurrentPair.second = Location;
   }
 
   MemoryAccessPair CurrentPair;
   memoryaccess_def_iterator DefIterator;
   MemoryLocation Location;
   MemoryAccess *OriginalAccess = nullptr;
   bool WalkingPhi = false;
   DominatorTree *DT = nullptr;
+  bool PerformedPhiTranslation = false;
 };
 
 inline upward_defs_iterator upward_defs_begin(const MemoryAccessPair &Pair,
                                               DominatorTree &DT) {
   return upward_defs_iterator(Pair, &DT);
 }
 
 inline upward_defs_iterator upward_defs_end() { return upward_defs_iterator(); }

llvm/lib/Analysis/MemorySSA.cpp

template <class AliasAnalysisType> class ClobberWalker {
   };
 
   const MemorySSA &MSSA;
   AliasAnalysisType &AA;
   DominatorTree &DT;
   UpwardsMemoryQuery *Query;
   unsigned *UpwardWalkLimit;
 
-  // Phi optimization bookkeeping
+  // Phi optimization bookkeeping:
+  // List of DefPath to process during the current phi optimization walk.
   SmallVector<DefPath, 32> Paths;
+  // List of visited <Access, Location> pairs; we can skip paths already
+  // visited with the same memory location.
   DenseSet<ConstMemoryAccessPair> VisitedPhis;
+  // Record if phi translation has been performed during the current phi
+  // optimization walk, as merging alias results after phi translation can
+  // yield incorrect results.
+  bool PerformedPhiTranslation = false;
 
   /// Find the nearest def or phi that `From` can legally be optimized to.
   const MemoryAccess *getWalkTarget(const MemoryPhi *From) const {
     assert(From->getNumOperands() && "Phi with no operands?");
 
     BasicBlock *BB = From->getBlock();
     MemoryAccess *Result = MSSA.getLiveOnEntryDef();
     DomTreeNode *Node = DT.getNode(BB);
walkToPhiOrClobber(DefPath &Desc, const MemoryAccess *StopAt = nullptr,
 
     assert(isa<MemoryPhi>(Desc.Last) &&
            "Ended at a non-clobber that's not a phi?");
     return {Desc.Last, false, MayAlias};
   }
 
   void addSearches(MemoryPhi *Phi, SmallVectorImpl<ListIndex> &PausedSearches,
                    ListIndex PriorNode) {
-    auto UpwardDefs = make_range(
-        upward_defs_begin({Phi, Paths[PriorNode].Loc}, DT), upward_defs_end());
+    auto UpwardDefsBegin = upward_defs_begin({Phi, Paths[PriorNode].Loc}, DT);
+    auto UpwardDefs = make_range(UpwardDefsBegin, upward_defs_end());
     for (const MemoryAccessPair &P : UpwardDefs) {
       PausedSearches.push_back(Paths.size());
       Paths.emplace_back(P.second, P.first, PriorNode);
     }
+    PerformedPhiTranslation |= UpwardDefsBegin.performedPhiTranslation();
   }
 
   /// Represents a search that terminated after finding a clobber. This clobber
   /// may or may not be present in the path of defs from LastNode..SearchStart,
   /// since it may have been retrieved from cache.
   struct TerminatedPath {
     MemoryAccess *Clobber;
     ListIndex LastNode;
while (!PausedSearches.empty()) {
       // optimization for A, B, and D; C will be skipped because it dies here.
       // This arguably isn't the worst thing ever, since:
       //   - We generally query things in a top-down order, so if we got below D
       //     without needing cache entries for {C, MemLoc}, then chances are
       //     that those cache entries would end up ultimately unused.
       //   - We still cache things for A, so C only needs to walk up a bit.
       // If this behavior becomes problematic, we can fix without a ton of extra
       // work.
-      if (!VisitedPhis.insert({Node.Last, Node.Loc}).second)
+      if (!VisitedPhis.insert({Node.Last, Node.Loc}).second) {
+        if (PerformedPhiTranslation) {
+          // If visiting this path performed Phi translation, don't continue,
+          // since it may not be correct to merge results from two paths if one
+          // relies on the phi translation.
+          TerminatedPath Term{Node.Last, PathIndex};
+          return Term;
+        }
         continue;
+      }
 
       const MemoryAccess *SkipStopWhere = nullptr;
       if (Query->SkipSelfAccess && Node.Loc == Query->StartingLoc) {
         assert(isa<MemoryDef>(Query->OriginalAccess));
         SkipStopWhere = Query->OriginalAccess;
       }
 
       UpwardsWalkResult Res = walkToPhiOrClobber(Node,
template <class AliasAnalysisType> class ClobberWalker {
   ///     - Otherwise, walk from A to another clobber or phi, A'.
   ///       - If A' is a def, we're done.
   ///       - If A' is a phi, try to optimize it.
   ///
   /// A path is a series of {MemoryAccess, MemoryLocation} pairs. A path
   /// terminates when a MemoryAccess that clobbers said MemoryLocation is found.
   OptznResult tryOptimizePhi(MemoryPhi *Phi, MemoryAccess *Start,
                              const MemoryLocation &Loc) {
-    assert(Paths.empty() && VisitedPhis.empty() &&
+    assert(Paths.empty() && VisitedPhis.empty() && !PerformedPhiTranslation &&
            "Reset the optimization state.");
 
     Paths.emplace_back(Loc, Start, Phi, None);
     // Stores how many "valid" optimization nodes we had prior to calling
     // addSearches/getBlockingAccess. Necessary for caching if we had a blocker.
     auto PriorPathsSize = Paths.size();
 
     SmallVector<ListIndex, 16> PausedSearches;
void verifyOptResult(const OptznResult &R) const {
     assert(all_of(R.OtherClobbers, [&](const TerminatedPath &P) {
       return MSSA.dominates(P.Clobber, R.PrimaryClobber.Clobber);
     }));
   }
 
   void resetPhiOptznState() {
     Paths.clear();
     VisitedPhis.clear();
+    PerformedPhiTranslation = false;
   }
 
 public:
   ClobberWalker(const MemorySSA &MSSA, AliasAnalysisType &AA, DominatorTree &DT)
       : MSSA(MSSA), AA(AA), DT(DT) {}
 
   AliasAnalysisType *getAA() { return &AA; }
   /// Finds the nearest clobber for the given query, optimizing phis if

llvm/test/Analysis/MemorySSA/phi-translation.ll

 ; CHECK-NEXT: store i64 %mul206, i64* %arrayidx.i571, align 8
   store i64 %mul206, i64* %arrayidx.i571, align 8
   br label %for.main.body
 
 the.end:                            ; preds = %for.main.body
   ret void
 
 }
+
+
+@c = local_unnamed_addr global [2 x i16] zeroinitializer, align 2
+
+define i32 @dont_merge_noalias_simple(i32* noalias %ptr) {
+; CHECK-LABEL: define i32 @dont_merge_noalias_simple
+; CHECK-LABEL: entry:
+; CHECK:       ; 1 = MemoryDef(liveOnEntry)
+; CHECK-NEXT:  store i16 1, i16* %s1.ptr, align 2
+
+; CHECK-LABEL: %for.body
+; CHECK:       ; MemoryUse(4) MayAlias
+; CHECK-NEXT:    %lv = load i16, i16* %arrayidx, align 2
+
+entry:
+  %s1.ptr = getelementptr inbounds [2 x i16], [2 x i16]* @c, i64 0, i64 0
+  store i16 1, i16* %s1.ptr, align 2
+  br label %for.body
+
+for.body:                                         ; preds = %for.body, %entry
+  %storemerge2 = phi i32 [ 1, %entry ], [ %dec, %for.body ]
+  %idxprom1 = zext i32 %storemerge2 to i64
+  %arrayidx = getelementptr inbounds [2 x i16], [2 x i16]* @c, i64 0, i64 %idxprom1
+  %lv = load i16, i16* %arrayidx, align 2
+  %conv = sext i16 %lv to i32
+  store i32 %conv, i32* %ptr, align 4
+  %dec = add nsw i32 %storemerge2, -1
+  %cmp = icmp sgt i32 %storemerge2, 0
+  br i1 %cmp, label %for.body, label %for.end
+
+for.end:                                          ; preds = %for.body
+  %s2.ptr = getelementptr inbounds [2 x i16], [2 x i16]* @c, i64 0, i64 0
+  store i16 0, i16* %s2.ptr, align 2
+  ret i32 0
+}
+
+
+define i32 @dont_merge_noalias_complex(i32* noalias %ptr, i32* noalias %another) {
+; CHECK-LABEL: define i32 @dont_merge_noalias_complex
+; CHECK-LABEL: entry:
+; CHECK:       ; 1 = MemoryDef(liveOnEntry)
+; CHECK-NEXT:  store i16 1, i16* %s1.ptr, align 2
+
+; CHECK-LABEL: %for.body
+; CHECK:       ; MemoryUse(7) MayAlias
+; CHECK-NEXT:    %lv = load i16, i16* %arrayidx, align 2
+
+entry:
+  %s1.ptr = getelementptr inbounds [2 x i16], [2 x i16]* @c, i64 0, i64 0
+  store i16 1, i16* %s1.ptr, align 2
+  br label %for.body
+
+for.body:                                         ; preds = %for.body, %entry
+  %storemerge2 = phi i32 [ 1, %entry ], [ %dec, %merge.body ]
+  %idxprom1 = zext i32 %storemerge2 to i64
+  %arrayidx = getelementptr inbounds [2 x i16], [2 x i16]* @c, i64 0, i64 %idxprom1
+  %lv = load i16, i16* %arrayidx, align 2
+  %conv = sext i16 %lv to i32
+  store i32 %conv, i32* %ptr, align 4
+  %dec = add nsw i32 %storemerge2, -1
+
+  %cmpif = icmp sgt i32 %storemerge2, 1
+  br i1 %cmpif, label %if.body, label %else.body
+
+if.body:
+  store i32 %conv, i32* %another, align 4
+  br label %merge.body
+
+else.body:
+  store i32 %conv, i32* %another, align 4
+  br label %merge.body
+
+merge.body:
+  %cmp = icmp sgt i32 %storemerge2, 0
+  br i1 %cmp, label %for.body, label %for.end
+
+for.end:                                          ; preds = %for.body
+  %s2.ptr = getelementptr inbounds [2 x i16], [2 x i16]* @c, i64 0, i64 0
+  store i16 0, i16* %s2.ptr, align 2
+  ret i32 0
+}
+