Improve load to store => memcpy

[deadalnix]

Summary

This now try to reorder instructions in order to help create the optimizable pattern.

[mehdi_amini]

I haven't looked into details, but I am a bit concerned by the number of nested level and the added length to this function, do you think it would make sense to refactor with one or multiple helper functions?

[deadalnix]

Indeed, I considered that part of this could be extract in an utility class. I wasn't really sure where to put it, but if you have a suggestion I'm taking. The TL;DR of the code is that it tries to lift an instruction + whatever depends on this instruction above another instruction in the same basic block. It needs to have alias analysis available to do it.

[deadalnix]

Ping

[mehdi_amini]

What about starting by extracting it as a static helper function and find it a better home later if any other client needs it?

lib/Transforms/Scalar/MemCpyOptimizer.cpp

575 ↗

(On Diff #45832)

std::any_of?

584 ↗

(On Diff #45832)

std::any_of?

[deadalnix]

Extract the logic to lift up the store in its own method

[deadalnix]

ping ?

[deadalnix]

ping

[deadalnix]

Ping

[deadalnix]

Use range for loops

[mehdi_amini]

Looks good to me with a few comments below.

lib/Transforms/Scalar/MemCpyOptimizer.cpp

508 ↗

(On Diff #49980)

Update the comment: according to the code, it does more than keeping only the *store* args. It contains all the instructions that needs to be placed before P to satisfy the lift.

525 ↗

(On Diff #49980)

Should be replaceable with something like: for(auto *C : reverse(make_range(P->getIterator(), --SI->getIterator())))

540 ↗

(On Diff #49980)

Minor suggestion: I think this can be written NeedList ||= std::any_of(...

[deadalnix]

Undo the range loop in moveUp as I reverse the loop direction invonlutary

[deadalnix]

Update comment to reflect what the code do accurately

llvm/trunk/lib/Transforms/Scalar/MemCpyOptimizer.cpp

 //===- MemCpyOptimizer.cpp - Optimize use of memcpy and friends -----------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 // This pass performs various transformations related to eliminating memcpy
 // calls, or transforming sets of stores into memset's.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Transforms/Scalar.h"
+#include "llvm/ADT/DenseSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/AliasAnalysis.h"
 #include "llvm/Analysis/AssumptionCache.h"
 #include "llvm/Analysis/GlobalsModRef.h"
 #include "llvm/Analysis/MemoryDependenceAnalysis.h"
 #include "llvm/Analysis/TargetLibraryInfo.h"
 #include "llvm/Analysis/ValueTracking.h"
if (!StoreAlign)
     StoreAlign = DL.getABITypeAlignment(SI->getOperand(0)->getType());
   unsigned LoadAlign = LI->getAlignment();
   if (!LoadAlign)
     LoadAlign = DL.getABITypeAlignment(LI->getType());
 
   return std::min(StoreAlign, LoadAlign);
 }
 
+// This method try to lift a store instruction before position P.
+// It will lift the store and its argument + that anything that
+// lay alias with these.
+// The method returns true if it was successful.
+static bool moveUp(AliasAnalysis &AA, StoreInst *SI, Instruction *P) {
+  // If the store alias this position, early bail out.
+  MemoryLocation StoreLoc = MemoryLocation::get(SI);
+  if (AA.getModRefInfo(P, StoreLoc) != MRI_NoModRef)
+    return false;
+
+  // Keep track of the arguments of all instruction we plan to lift
+  // so we can make sure to lift them as well if apropriate.
+  DenseSet<Instruction*> Args;
+  if (auto *Ptr = dyn_cast<Instruction>(SI->getPointerOperand()))
+    if (Ptr->getParent() == SI->getParent())
+      Args.insert(Ptr);
+
+  // Instruction to lift before P.
+  SmallVector<Instruction*, 8> ToLift;
+
+  // Memory locations of lifted instructions.
+  SmallVector<MemoryLocation, 8> MemLocs;
+  MemLocs.push_back(StoreLoc);
+
+  // Lifted callsites.
+  SmallVector<ImmutableCallSite, 8> CallSites;
+
+  for (auto I = --SI->getIterator(), E = P->getIterator(); I != E; --I) {
+    auto *C = &*I;
+
+    bool MayAlias = AA.getModRefInfo(C) != MRI_NoModRef;
+
+    bool NeedLift = false;
+    if (Args.erase(C))
+      NeedLift = true;
+    else if (MayAlias) {
+      NeedLift = std::any_of(MemLocs.begin(), MemLocs.end(),
+        [C, &AA](const MemoryLocation &ML) {
+          return AA.getModRefInfo(C, ML);
+        });
+
+      if (!NeedLift)
+        NeedLift = std::any_of(CallSites.begin(), CallSites.end(),
+          [C, &AA](const ImmutableCallSite &CS) {
+            return AA.getModRefInfo(C, CS);
+          });
+    }
+
+    if (!NeedLift)
+      continue;
+
+    if (MayAlias) {
+      if (auto CS = ImmutableCallSite(C)) {
+        // If we can't lift this before P, it's game over.
+        if (AA.getModRefInfo(P, CS) != MRI_NoModRef)
+          return false;
+
+        CallSites.push_back(CS);
+      } else if (isa<LoadInst>(C) || isa<StoreInst>(C) || isa<VAArgInst>(C)) {
+        // If we can't lift this before P, it's game over.
+        auto ML = MemoryLocation::get(C);
+        if (AA.getModRefInfo(P, ML) != MRI_NoModRef)
+          return false;
+
+        MemLocs.push_back(ML);
+      } else
+        // We don't know how to lift this instruction.
+        return false;
+    }
+
+    ToLift.push_back(C);
+    for (unsigned k = 0, e = C->getNumOperands(); k != e; ++k)
+      if (auto *A = dyn_cast<Instruction>(C->getOperand(k)))
+        if (A->getParent() == SI->getParent())
+          Args.insert(A);
+  }
+
+  // We made it, we need to lift
+  for (auto *I : reverse(ToLift)) {
+    DEBUG(dbgs() << "Lifting " << *I << " before " << *P << "\n");
+    I->moveBefore(P);
+  }
+
+  return true;
+}
+
 bool MemCpyOpt::processStore(StoreInst *SI, BasicBlock::iterator &BBI) {
   if (!SI->isSimple()) return false;
 
   // Avoid merging nontemporal stores since the resulting
   // memcpy/memset would not be able to preserve the nontemporal hint.
   // In theory we could teach how to propagate the !nontemporal metadata to
   // memset calls. However, that change would force the backend to
   // conservatively expand !nontemporal memset calls back to sequences of
if (LI->isSimple() && LI->hasOneUse() &&
         AliasAnalysis &AA = getAnalysis<AAResultsWrapperPass>().getAAResults();
         MemoryLocation LoadLoc = MemoryLocation::get(LI);
 
         // We use alias analysis to check if an instruction may store to
         // the memory we load from in between the load and the store. If
         // such an instruction is found, we try to promote there instead
         // of at the store position.
         Instruction *P = SI;
-        for (BasicBlock::iterator I = ++LI->getIterator(), E = SI->getIterator();
-             I != E; ++I) {
-          if (!(AA.getModRefInfo(&*I, LoadLoc) & MRI_Mod))
-            continue;
+        for (auto &I : make_range(++LI->getIterator(), SI->getIterator())) {
+          if (AA.getModRefInfo(&I, LoadLoc) & MRI_Mod) {
+            P = &I;
+            break;
+          }
+        }
 
-          // We found an instruction that may write to the loaded memory.
-          // We can try to promote at this position instead of the store
-          // position if nothing alias the store memory after this and the store
-          // destination is not in the range.
-          P = &*I;
-          for (; I != E; ++I) {
-            MemoryLocation StoreLoc = MemoryLocation::get(SI);
-            if (&*I == SI->getOperand(1) ||
-                AA.getModRefInfo(&*I, StoreLoc) != MRI_NoModRef) {
-              P = nullptr;
-              break;
-            }
-          }
-
-          break;
+        if (P && P != SI) {
+          if (!moveUp(AA, SI, P))
         }
 
         // If a valid insertion position is found, then we can promote
         // the load/store pair to a memcpy.
         if (P) {
           // If we load from memory that may alias the memory we store to,
           // memmove must be used to preserve semantic. If not, memcpy can
           // be used.

llvm/trunk/test/Transforms/MemCpyOpt/fca2memcpy.ll

 ; CHECK-NEXT: ret void
   %1 = load %S, %S* %src
   %2 = load %S, %S* %src
   store %S %1, %S* %dst
   store %S %2, %S* %dst
   ret void
 }
 
-
-; The GEP is present after the aliasing store, preventing to move the memcpy before
-; (without further analysis/transformation)
-define void @copyaliaswithproducerinbetween(%S* %src, %S* %dst) {
-; CHECK-LABEL: copyalias
-; CHECK-NEXT: [[LOAD:%[a-z0-9\.]+]] = load %S, %S* %src
-; CHECK-NOT: call
+; If the store address is computed ina complex manner, make
+; sure we lift the computation as well if needed and possible.
+define void @addrproducer(%S* %src, %S* %dst) {
+; CHECK-LABEL: addrproducer
+; CHECK: %dst2 = getelementptr %S, %S* %dst, i64 1
+; CHECK: call void @llvm.memmove.p0i8.p0i8.i64
+; CHECK-NEXT: store %S undef, %S* %dst
+; CHECK-NEXT: ret void
   %1 = load %S, %S* %src
   store %S undef, %S* %dst
   %dst2 = getelementptr %S , %S* %dst, i64 1
   store %S %1, %S* %dst2
   ret void
 }
+
+define void @aliasaddrproducer(%S* %src, %S* %dst, i32* %dstidptr) {
+; CHECK-LABEL: aliasaddrproducer
+  %1 = load %S, %S* %src
+  store %S undef, %S* %dst
+  %dstindex = load i32, i32* %dstidptr
+  %dst2 = getelementptr %S , %S* %dst, i32 %dstindex
+  store %S %1, %S* %dst2
+  ret void
+}
+
+define void @noaliasaddrproducer(%S* %src, %S* noalias %dst, i32* noalias %dstidptr) {
+; CHECK-LABEL: noaliasaddrproducer
+  %1 = load %S, %S* %src
+  store %S undef, %S* %src
+  %2 = load i32, i32* %dstidptr
+  %dstindex = or i32 %2, 1
+  %dst2 = getelementptr %S , %S* %dst, i32 %dstindex
+  store %S %1, %S* %dst2
+  ret void
+}