Correctly report modified status for LoopIdiomRecognize

[serge-sans-paille]

Summary

Related to https://reviews.llvm.org/D80916

[foad]

I don't particularly like all the code duplication. Is there a better way to arrange processLoopStoreOfLoopLoad?

[asbirlea]

Any chance of adding a test for this?

llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp

1109

Merge conditions to avoid the code duplication?

if (mayLoopAccessLocation(...) || 
    avoidLIRForMultiBlockLoop) {

1130–1131

Similarly, merge conditions and comment appropriately.

[nikic]

llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp

1130–1131

This is actually dead code, I've dropped it in bff94a8e2bb93267a561ca96287f570af499b090.

[serge-sans-paille]

Introduce an helper class to aggregate the cleanup in case of rollback.

[efriedma]

I'd prefer to conservatively return true, rather than worry about whether calling expandCodeFor and cleaning it up is actually a pure no-op in terms of use-lists etc.

[serge-sans-paille]

In D81230#2081245, @efriedma wrote:

I'd prefer to conservatively return true, rather than worry about whether calling expandCodeFor and cleaning it up is actually a pure no-op in terms of use-lists etc.

I'm curious about the motivation behind that statement. Existing code already tries to tidy up the code (e.g. line 1084), so I feel I'm just syndicating that code in one place.

[efriedma]

Existing code already tries to tidy up the code (e.g. line 1084), so I feel I'm just syndicating that code in one place.

I'm not against trying to clean up the code; I'm just against asserting that we successfully managed to clean up the memory representation to exactly the same form it was in before we called expandCodeFor.

[serge-sans-paille]

I'm not against trying to clean up the code; I'm just against asserting that we successfully managed to clean up the memory representation to exactly the same form it was in before we called expandCodeFor.

https://reviews.llvm.org/D80707 should guarentee that this assertion actually holds, right?

[efriedma]

I don't trust that analysis passes verifying themselves will catch all the issues. At best, that only proves that we didn't invalidate any analysis that happened to be live at the time LoopIdiomRecognize runs.

[nikic]

@efriedma I believe @serge-sans-paille had D80916 in mind here, which provides a stronger guarantee, or at least has the potential to provide it. Of course, just returning true would be more conservative, and make little difference in practice.

llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp

1030

Rather than explicitly calling clean() in all early-return paths, maybe do this in ~ExpandedValueCleaner() automatically, and add a commit() method or so for the single success path, that clears the vector?

[serge-sans-paille]

Use destructor to syndicate cleanup code, as suggested in the review.

[serge-sans-paille]

@efriedma I believe @serge-sans-paille had D80916 in mind here

correct :-)

[nikic]

LG

llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp

1014

New line here seems unusual?

[foad]

llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp

1066

How does this work? I thought brace initialization was only for structs with public fields (but I'm clearly not an expert). And even if it does work, wouldn't parentheses be a bit more "normal" than braces?

[serge-sans-paille]

Final comments addressed in the actual commit.

llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp

1066

That's a list-initialization falling back to constructor call, as described in https://en.cppreference.com/w/cpp/language/list_initialization

grep for

Otherwise, the constructors of T are considered, in two phases:

I've updated the code to use classic constructor, it's less ambiguous for the reader :-)

llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp

for (auto *I : Stores) {
     deleteDeadInstruction(I);
   }
   if (MSSAU && VerifyMemorySSA)
     MSSAU->getMemorySSA()->verifyMemorySSA();
   ++NumMemSet;
   return true;
 }
 
+class ExpandedValuesCleaner {
+  SCEVExpander &Expander;
+  TargetLibraryInfo *TLI;
+  SmallVector<Value *, 4> ExpandedValues;
+  bool Commit = false;
+
+public:
+  ExpandedValuesCleaner(SCEVExpander &Expander, TargetLibraryInfo *TLI)
+      : Expander(Expander), TLI(TLI) {}
+
+  void add(Value *V) { ExpandedValues.push_back(V); }
+
+  void commit() { Commit = true; }
+
+  ~ExpandedValuesCleaner() {
+    if (!Commit) {
+      Expander.clear();
+      for (auto *V : ExpandedValues)
+        RecursivelyDeleteTriviallyDeadInstructions(V, TLI);
+    }
+  }
+};
+
 /// If the stored value is a strided load in the same loop with the same stride
 /// this may be transformable into a memcpy.  This kicks in for stuff like
 /// for (i) A[i] = B[i];
 bool LoopIdiomRecognize::processLoopStoreOfLoopLoad(StoreInst *SI,
                                                     const SCEV *BECount) {
   assert(SI->isUnordered() && "Expected only non-volatile non-ordered stores.");
 
   Value *StorePtr = SI->getPointerOperand();
bool LoopIdiomRecognize::processLoopStoreOfLoopLoad(StoreInst *SI,
 
   // The trip count of the loop and the base pointer of the addrec SCEV is
   // guaranteed to be loop invariant, which means that it should dominate the
   // header.  This allows us to insert code for it in the preheader.
   BasicBlock *Preheader = CurLoop->getLoopPreheader();
   IRBuilder<> Builder(Preheader->getTerminator());
   SCEVExpander Expander(*SE, *DL, "loop-idiom");
 
+  ExpandedValuesCleaner EVC(Expander, TLI);
+
   const SCEV *StrStart = StoreEv->getStart();
   unsigned StrAS = SI->getPointerAddressSpace();
   Type *IntIdxTy = Builder.getIntNTy(DL->getIndexSizeInBits(StrAS));
 
   // Handle negative strided loops.
   if (NegStride)
     StrStart = getStartForNegStride(StrStart, BECount, IntIdxTy, StoreSize, SE);
 
   // Okay, we have a strided store "p[i]" of a loaded value.  We can turn
   // this into a memcpy in the loop preheader now if we want.  However, this
   // would be unsafe to do if there is anything else in the loop that may read
   // or write the memory region we're storing to.  This includes the load that
   // feeds the stores.  Check for an alias by generating the base address and
   // checking everything.
   Value *StoreBasePtr = Expander.expandCodeFor(
       StrStart, Builder.getInt8PtrTy(StrAS), Preheader->getTerminator());
+  EVC.add(StoreBasePtr);
 
   SmallPtrSet<Instruction *, 1> Stores;
   Stores.insert(SI);
   if (mayLoopAccessLocation(StoreBasePtr, ModRefInfo::ModRef, CurLoop, BECount,
-                            StoreSize, *AA, Stores)) {
-    Expander.clear();
-    // If we generated new code for the base pointer, clean up.
-    RecursivelyDeleteTriviallyDeadInstructions(StoreBasePtr, TLI);
+                            StoreSize, *AA, Stores))
     return false;
-  }
 
   const SCEV *LdStart = LoadEv->getStart();
   unsigned LdAS = LI->getPointerAddressSpace();
 
   // Handle negative strided loops.
   if (NegStride)
     LdStart = getStartForNegStride(LdStart, BECount, IntIdxTy, StoreSize, SE);
 
   // For a memcpy, we have to make sure that the input array is not being
   // mutated by the loop.
   Value *LoadBasePtr = Expander.expandCodeFor(
       LdStart, Builder.getInt8PtrTy(LdAS), Preheader->getTerminator());
+  EVC.add(LoadBasePtr);
 
   if (mayLoopAccessLocation(LoadBasePtr, ModRefInfo::Mod, CurLoop, BECount,
-                            StoreSize, *AA, Stores)) {
-    Expander.clear();
-    // If we generated new code for the base pointer, clean up.
-    RecursivelyDeleteTriviallyDeadInstructions(LoadBasePtr, TLI);
-    RecursivelyDeleteTriviallyDeadInstructions(StoreBasePtr, TLI);
+                            StoreSize, *AA, Stores))
     return false;
-  }
 
   if (avoidLIRForMultiBlockLoop())
     return false;
 
   // Okay, everything is safe, we can transform this!
 
   const SCEV *NumBytesS =
       getNumBytes(BECount, IntIdxTy, StoreSize, CurLoop, DL, SE);
 
   Value *NumBytes =
       Expander.expandCodeFor(NumBytesS, IntIdxTy, Preheader->getTerminator());
+  EVC.add(NumBytes);
 
   CallInst *NewCall = nullptr;
   // Check whether to generate an unordered atomic memcpy:
   //  If the load or store are atomic, then they must necessarily be unordered
   //  by previous checks.
   if (!SI->isAtomic() && !LI->isAtomic())
     NewCall = Builder.CreateMemCpy(StoreBasePtr, SI->getAlign(), LoadBasePtr,
                                    LI->getAlign(), NumBytes);
   else {
     // We cannot allow unaligned ops for unordered load/store, so reject
     // anything where the alignment isn't at least the element size.
     const Align StoreAlign = SI->getAlign();
     const Align LoadAlign = LI->getAlign();
     if (StoreAlign < StoreSize || LoadAlign < StoreSize)
       return false;
 
     // If the element.atomic memcpy is not lowered into explicit
     // loads/stores later, then it will be lowered into an element-size
     // specific lib call. If the lib call doesn't exist for our store size, then
     // we shouldn't generate the memcpy.
bool LoopIdiomRecognize::processLoopStoreOfLoopLoad(StoreInst *SI,
   // Okay, the memcpy has been formed.  Zap the original store and anything that
   // feeds into it.
   if (MSSAU)
     MSSAU->removeMemoryAccess(SI, true);
   deleteDeadInstruction(SI);
   if (MSSAU && VerifyMemorySSA)
     MSSAU->getMemorySSA()->verifyMemorySSA();
   ++NumMemCpy;
+  EVC.commit();
   return true;
 }
 
 // When compiling for codesize we avoid idiom recognition for a multi-block loop
 // unless it is a loop_memset idiom or a memset/memcpy idiom in a nested loop.
 //
 bool LoopIdiomRecognize::avoidLIRForMultiBlockLoop(bool IsMemset,
                                                    bool IsLoopMemset) {