[MemCpyOpt] Optimize MemoryDef insertion

[nikic]

Summary

When converting a store into a memset, we currently insert the new MemoryDef after the store MemoryDef, which requires all uses to be renamed to the new def using a whole block scan. Instead, we can insert the new MemoryDef before the store and not rename uses, because we know that the location is immediately overwritten, so all uses should still refer to the old MemoryDef. Those uses will get renamed when the old MemoryDef is actually dropped, which is efficient.

I expect something similar can be done for some of the other MSSA updates in MemCpyOpt. This may be an alternative to D107513, at least for this particular case.

[aeubanks]

this does make memcpyopt not insanely slow for large functions

import sys

count = int(sys.argv[1])

with open(sys.argv[2], 'w') as f:
    for i in xrange(count):
        f.write('@g{} = global [2 x i64] zeroinitializer\n'.format(i))
    f.write('define void @a() {\n')
    for i in xrange(count):
        f.write('  store [2 x i64] zeroinitializer, [2 x i64]* @g{}\n'.format(i))
    f.write('  ret void\n')
    f.write('}\n')

$ python /tmp/a.py 100000 /tmp/a.ll
$ opt -passes=memcpyopt -disable-output /tmp/a.ll

for a function with 100000 stores, it previously took 88s, with this patch it takes 1s

[asbirlea]

Thanks, this LGTM, and it does resolve the efficiency case.

llvm/lib/Transforms/Scalar/MemCpyOptimizer.cpp

if (Value *ByteVal = isBytewiseValue(V, DL)) {
     if (T->isAggregateType()) {
       uint64_t Size = DL.getTypeStoreSize(T);
       IRBuilder<> Builder(SI);
       auto *M = Builder.CreateMemSet(SI->getPointerOperand(), ByteVal, Size,
                                      SI->getAlign());
 
       LLVM_DEBUG(dbgs() << "Promoting " << *SI << " to " << *M << "\n");
 
-      assert(isa<MemoryDef>(MSSAU->getMemorySSA()->getMemoryAccess(SI)));
-      auto *LastDef =
-          cast<MemoryDef>(MSSAU->getMemorySSA()->getMemoryAccess(SI));
-      auto *NewAccess = MSSAU->createMemoryAccessAfter(M, LastDef, LastDef);
-      MSSAU->insertDef(cast<MemoryDef>(NewAccess), /*RenameUses=*/true);
+      // The newly inserted memset is immediately overwritten by the original
+      // store, so we do not need to rename uses.
+      auto *StoreDef = cast<MemoryDef>(MSSA->getMemoryAccess(SI));
+      auto *NewAccess = MSSAU->createMemoryAccessBefore(
+          M, StoreDef->getDefiningAccess(), StoreDef);
+      MSSAU->insertDef(cast<MemoryDef>(NewAccess), /*RenameUses=*/false);
 
       eraseInstruction(SI);
       NumMemSetInfer++;
 
       // Make sure we do not invalidate the iterator.
       BBI = M->getIterator();
       return true;
     }