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

std::any_of?

584

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

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

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

540

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

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"
bool MemCpyOpt::processStore(StoreInst *SI, BasicBlock::iterator &BBI) {
   // 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
   // store instructions (effectively undoing the merging).
   if (SI->getMetadata(LLVMContext::MD_nontemporal))
     return false;
 
   const DataLayout &DL = SI->getModule()->getDataLayout();
 
   // Load to store forwarding can be interpreted as memcpy.
   if (LoadInst *LI = dyn_cast<LoadInst>(SI->getOperand(0))) {
     if (LI->isSimple() && LI->hasOneUse() &&
         LI->getParent() == SI->getParent()) {
 
       auto *T = LI->getType();
       if (T->isAggregateType()) {
         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();
+        for (auto I = ++LI->getIterator(), E = SI->getIterator();
              I != E; ++I) {
           if (!(AA.getModRefInfo(&*I, LoadLoc) & MRI_Mod))
             continue;
 
-          // 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 = &*I;
+        }
+
+        if (P && P != SI) {
+          // If the store alias this position, early bail out.
+          if (AA.getModRefInfo(P, StoreLoc) != MRI_NoModRef)
+            P = nullptr;
+          else {
+            // Keep track of the store's argument so that we move them up
+            // as well if possible and necessary.
+            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) {
+                for (auto ML : MemLocs) {
+                  if (AA.getModRefInfo(C, ML)) {
+                    NeedLift = true;
+                    break;
+                  }
+                }
+
+                if (!NeedLift)
+                  for (auto CS : CallSites) {
+                    if (AA.getModRefInfo(C, CS)) {
+                      NeedLift = true;
+                      break;
+                    }
+                  }
+              }
+
+              if (NeedLift) {
+                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) {
                       P = nullptr;
                       break;
                     }
+
+                    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) {
+                      P = nullptr;
+                      break;
                     }
 
+                    MemLocs.push_back(ML);
+                  } else {
+                    // We don't know how to lift this instruction.
+                    P = nullptr;
                     break;
                   }
+                }
+
+                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
+            if (P) {
+              for (auto *I : reverse(ToLift)) {
+                DEBUG(dbgs() << "Lifting " << *I << " before " << *P << "\n");
+                I->moveBefore(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.
           bool UseMemMove = false;

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
+}