[MemorySSA] Remove PerformedPhiTranslation flag

[nikic]

Summary

I believe this is no longer necessary, as the underlying problem has been fixed in a different way: Nowadays, we will adjust the location size to beforeOrAfterPointer() if the pointer is not loop invariant. This makes merging results translated across loop backedges safe.

The two tests in phi-translation.ll show an improvement while still being correct: The loads in the loop no longer alias with noalias pointers, but still alias with the store in the entry block (which they originally did not -- this is the bug that PerformedPhiTranslation originally fixed).

[nikic]

ping

[nikic]

ping :)

[asbirlea]

I believe this is correct.

[asbirlea]

Conversely, please consider if this makes sense to keep for: https://reviews.llvm.org/D134161.

llvm/include/llvm/Analysis/MemorySSA.h

 /// memory location through phi nodes for the user.
 class upward_defs_iterator
     : public iterator_facade_base<upward_defs_iterator,
                                   std::forward_iterator_tag,
                                   const MemoryAccessPair> {
   using BaseT = upward_defs_iterator::iterator_facade_base;
 
 public:
-  upward_defs_iterator(const MemoryAccessPair &Info, DominatorTree *DT,
-                       bool *PerformedPhiTranslation = nullptr)
+  upward_defs_iterator(const MemoryAccessPair &Info, DominatorTree *DT)
       : DefIterator(Info.first), Location(Info.second),
-        OriginalAccess(Info.first), DT(DT),
-        PerformedPhiTranslation(PerformedPhiTranslation) {
+        OriginalAccess(Info.first), DT(DT) {
     CurrentPair.first = nullptr;
 
     WalkingPhi = Info.first && isa<MemoryPhi>(Info.first);
     fillInCurrentPair();
   }
 
   upward_defs_iterator() { CurrentPair.first = nullptr; }
 
if (WalkingPhi && Location.Ptr) {
         Value *TransAddr = Translator.getAddr();
         if (TransAddr != Location.Ptr) {
           CurrentPair.second = CurrentPair.second.getWithNewPtr(TransAddr);
 
           if (TransAddr &&
               !IsGuaranteedLoopInvariant(TransAddr))
             CurrentPair.second = CurrentPair.second.getWithNewSize(
                 LocationSize::beforeOrAfterPointer());
-
-          if (PerformedPhiTranslation)
-            *PerformedPhiTranslation = true;
         }
       }
     }
   }
 
   MemoryAccessPair CurrentPair;
   memoryaccess_def_iterator DefIterator;
   MemoryLocation Location;
   MemoryAccess *OriginalAccess = nullptr;
   DominatorTree *DT = nullptr;
   bool WalkingPhi = false;
-  bool *PerformedPhiTranslation = nullptr;
 };
 
 inline upward_defs_iterator
-upward_defs_begin(const MemoryAccessPair &Pair, DominatorTree &DT,
-                  bool *PerformedPhiTranslation = nullptr) {
-  return upward_defs_iterator(Pair, &DT, PerformedPhiTranslation);
+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(); }
 
 inline iterator_range<upward_defs_iterator>
 upward_defs(const MemoryAccessPair &Pair, DominatorTree &DT) {
   return make_range(upward_defs_begin(Pair, DT), upward_defs_end());
 }

llvm/lib/Analysis/MemorySSA.cpp

template <class AliasAnalysisType> class ClobberWalker {
   unsigned *UpwardWalkLimit;
 
   // 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. Context in PR46156.
-  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};
   }
 
   void addSearches(MemoryPhi *Phi, SmallVectorImpl<ListIndex> &PausedSearches,
                    ListIndex PriorNode) {
-    auto UpwardDefsBegin = upward_defs_begin({Phi, Paths[PriorNode].Loc}, DT,
-                                             &PerformedPhiTranslation);
+    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);
     }
   }
 
   /// Represents a search that terminated after finding a clobber. This clobber
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 (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;
-        }
+      if (!VisitedPhis.insert({Node.Last, Node.Loc}).second)
         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() && !PerformedPhiTranslation &&
+    assert(Paths.empty() && VisitedPhis.empty() &&
            "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

 
 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)
+; NOLIMIT:     ; MemoryUse(1)
+; LIMIT:       ; MemoryUse(4)
 ; 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

 
 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)
+; NOLIMIT:     ; MemoryUse(1)
+; LIMIT:       ; MemoryUse(7)
 ; 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