[DSE,MSSA] Cache accesses with/without reachable read-clobbers.

[fhahn]

Summary

Currently we repeatedly check the same uses for read clobbers in some
cases. We can avoid unnecessary checks by keeping track of the memory
accesses we already found read clobbers for. To do so, we just add
memory access causing read-clobbers to a set. Note that marking all
visited accesses as read-clobbers would be to pessimistic, as that might
include accesses not on any path to the actual read clobber.

If we do not find any read-clobbers, we can add all visited instructions
to another set and use that to skip the same accesses in the next call.

I did not yet measure compile-time, but below is the impact on the
number of iterations in getDomMemoryDef:

Metric: dse.NumDomMemDefChecks

Program base patch diff
test-suite...000/183.equake/183.equake.test 132580.00 26961.00 -79.7%
test-suite...T95/147.vortex/147.vortex.test 881946.00 297521.00 -66.3%
test-suite...000/255.vortex/255.vortex.test 882090.00 297594.00 -66.3%
test-suite...T2006/445.gobmk/445.gobmk.test 700940.00 247624.00 -64.7%
test-suite...ications/JM/ldecod/ldecod.test 990956.00 357584.00 -63.9%
test-suite...C/CFP2000/179.art/179.art.test 23014.00 8364.00 -63.7%
test-suite...marks/SciMark2-C/scimark2.test 20939.00 8230.00 -60.7%
test-suite.../CINT2006/403.gcc/403.gcc.test 2412386.00 951674.00 -60.6%
test-suite...006/447.dealII/447.dealII.test 1850445.00 796042.00 -57.0%
test-suite...006/453.povray/453.povray.test 1735262.00 753271.00 -56.6%
test-suite...ProxyApps-C++/CLAMR/CLAMR.test 393888.00 172514.00 -56.2%
test-suite...ProxyApps-C++/HPCCG/HPCCG.test 42350.00 18931.00 -55.3%
test-suite...000/186.crafty/186.crafty.test 371608.00 167669.00 -54.9%
test-suite...langs-C/unix-tbl/unix-tbl.test 10263.00 4763.00 -53.6%
test-suite.../CINT2000/176.gcc/176.gcc.test 1641688.00 763696.00 -53.5%
test-suite...ications/JM/lencod/lencod.test 1459213.00 679907.00 -53.4%
test-suite...FreeBench/distray/distray.test 10477.00 5113.00 -51.2%
test-suite.../Trimaran/enc-md5/enc-md5.test 2651.00 1295.00 -51.2%
test-suite...s/Rodinia/hotspot/hotspot.test 4031.00 1989.00 -50.7%
test-suite...T2006/401.bzip2/401.bzip2.test 171479.00 85496.00 -50.1%
test-suite...lowfish/security-blowfish.test 6217.00 3143.00 -49.4%
test-suite...rks/FreeBench/mason/mason.test 1386.00 712.00 -48.6%
test-suite...yApps-C++/PENNANT/PENNANT.test 135316.00 71201.00 -47.4%
test-suite...ks/McCat/04-bisect/bisect.test 3353.00 1801.00 -46.3%
test-suite...6/464.h264ref/464.h264ref.test 1500143.00 810226.00 -46.0%
test-suite...marks/7zip/7zip-benchmark.test 1278779.00 711387.00 -44.4%
test-suite...lications/viterbi/viterbi.test 11564.00 6497.00 -43.8%
test-suite...plications/d/make_dparser.test 54338.00 31158.00 -42.7%
test-suite...ternal/HMMER/hmmcalibrate.test 75317.00 43258.00 -42.6%
test-suite...lications/ClamAV/clamscan.test 447833.00 258126.00 -42.4%
test-suite...lications/SIBsim4/SIBsim4.test 32896.00 19381.00 -41.1%
test-suite...6/482.sphinx3/482.sphinx3.test 62177.00 37137.00 -40.3%
test-suite...nia/pathfinder/pathfinder.test 1322.00 795.00 -39.9%
test-suite...math/automotive-basicmath.test 146.00 88.00 -39.7%
test-suite...ngs-C/simulator/simulator.test 18187.00 10982.00 -39.6%
test-suite...s/ASC_Sequoia/IRSmk/IRSmk.test 3040.00 1839.00 -39.5%
test-suite...T2006/473.astar/473.astar.test 37795.00 22910.00 -39.4%
test-suite...CFP2006/444.namd/444.namd.test 97627.00 59229.00 -39.3%
test-suite...-typeset/consumer-typeset.test 802759.00 488393.00 -39.2%
test-suite...T2006/456.hmmer/456.hmmer.test 96748.00 58957.00 -39.1%
test-suite...quoia/CrystalMk/CrystalMk.test 9157.00 5669.00 -38.1%
test-suite.../Benchmarks/Olden/mst/mst.test 1054.00 653.00 -38.0%
test-suite :: External/Nurbs/nurbs.test 14763.00 9177.00 -37.8%
test-suite...CFP2000/188.ammp/188.ammp.test 84072.00 53009.00 -36.9%
test-suite...chmarks/MallocBench/gs/gs.test 98221.00 61993.00 -36.9%
test-suite...rks/FreeBench/pifft/pifft.test 15560.00 9888.00 -36.5%
test-suite...ks/McCat/01-qbsort/qbsort.test 497.00 323.00 -35.0%
test-suite...INT2000/164.gzip/164.gzip.test 30328.00 19767.00 -34.8%
test-suite...lications/obsequi/Obsequi.test 44239.00 29195.00 -34.0%
test-suite.../CINT2000/252.eon/252.eon.test 340333.00 224748.00 -34.0%
test-suite.../Prolangs-C++/trees/trees.test 2573.00 1715.00 -33.3%
test-suite...TimberWolfMC/timberwolfmc.test 190315.00 126890.00 -33.3%
test-suite...nch/fourinarow/fourinarow.test 1487.00 994.00 -33.2%
test-suite...SPEC/CINT95/099.go/099.go.test 256287.00 173249.00 -32.4%
test-suite...s-C/Pathfinder/PathFinder.test 8366.00 5708.00 -31.8%
test-suite...5/124.m88ksim/124.m88ksim.test 62116.00 42425.00 -31.7%
test-suite...arks/McCat/17-bintr/bintr.test 154.00 107.00 -30.5%
test-suite...langs-C/football/football.test 17864.00 12416.00 -30.5%
test-suite...lications/minisat/minisat.test 9504.00 6676.00 -29.8%
test-suite...rks/tramp3d-v4/tramp3d-v4.test 1275472.00 896318.00 -29.7%
test-suite...s/FreeBench/neural/neural.test 1534.00 1087.00 -29.1%
test-suite...arks/mafft/pairlocalalign.test 259748.00 185421.00 -28.6%
test-suite...comm-adpcm/telecomm-adpcm.test 53.00 38.00 -28.3%
test-suite...adpcm/rawdaudio/rawdaudio.test 53.00 38.00 -28.3%
test-suite.../Benchmarks/Olden/tsp/tsp.test 2522.00 1834.00 -27.3%
test-suite...:: External/Povray/povray.test 650268.00 476041.00 -26.8%

In some cases this also increase the number of eliminated stores,
because we can explore further. Note that there is a small regression
which I should track down.

Metric: dse.NumFastStores

Program base patch diff
test-suite...T2006/445.gobmk/445.gobmk.test 82.00 123.00 50.0%
test-suite...C/CFP2000/179.art/179.art.test 6.00 7.00 16.7%
test-suite...math/automotive-basicmath.test 7.00 8.00 14.3%
test-suite...ngs-C/assembler/assembler.test 8.00 9.00 12.5%
test-suite...ks/Prolangs-C/gnugo/gnugo.test 9.00 10.00 11.1%
test-suite...INT95/132.ijpeg/132.ijpeg.test 18.00 20.00 11.1%
test-suite...langs-C/football/football.test 10.00 11.00 10.0%
test-suite...ce/Benchmarks/Olden/bh/bh.test 13.00 14.00 7.7%
test-suite...ications/JM/ldecod/ldecod.test 382.00 402.00 5.2%
test-suite...000/183.equake/183.equake.test 40.00 38.00 -5.0%
test-suite...6/482.sphinx3/482.sphinx3.test 22.00 23.00 4.5%
test-suite...T95/147.vortex/147.vortex.test 215.00 224.00 4.2%
test-suite...000/255.vortex/255.vortex.test 217.00 226.00 4.1%
test-suite...SPEC/CINT95/099.go/099.go.test 63.00 65.00 3.2%
test-suite.../Benchmarks/nbench/nbench.test 76.00 78.00 2.6%
test-suite...lications/sqlite3/sqlite3.test 153.00 157.00 2.6%
test-suite...INT2000/164.gzip/164.gzip.test 39.00 40.00 2.6%
test-suite...ications/JM/lencod/lencod.test 840.00 854.00 1.7%
test-suite...marks/7zip/7zip-benchmark.test 1211.00 1231.00 1.7%
test-suite...6/464.h264ref/464.h264ref.test 730.00 741.00 1.5%
test-suite...006/453.povray/453.povray.test 1417.00 1437.00 1.4%
test-suite...lications/ClamAV/clamscan.test 230.00 233.00 1.3%
test-suite.../Applications/SPASS/SPASS.test 156.00 158.00 1.3%
test-suite...0.perlbench/400.perlbench.test 861.00 871.00 1.2%
test-suite.../CINT2000/176.gcc/176.gcc.test 879.00 889.00 1.1%
test-suite...nsumer-lame/consumer-lame.test 100.00 101.00 1.0%
test-suite...:: External/Povray/povray.test 1220.00 1231.00 0.9%
test-suite...ocBench/espresso/espresso.test 115.00 116.00 0.9%
test-suite...chmarks/MallocBench/gs/gs.test 116.00 117.00 0.9%
test-suite...5/124.m88ksim/124.m88ksim.test 116.00 117.00 0.9%
test-suite...CI_Purple/SMG2000/smg2000.test 158.00 159.00 0.6%
test-suite...000/186.crafty/186.crafty.test 158.00 159.00 0.6%
test-suite...0/253.perlbmk/253.perlbmk.test 500.00 503.00 0.6%
test-suite.../CINT2006/403.gcc/403.gcc.test 1178.00 1185.00 0.6%
test-suite...CFP2000/188.ammp/188.ammp.test 181.00 182.00 0.6%
test-suite.../CINT2000/252.eon/252.eon.test 2672.00 2685.00 0.5%
test-suite...006/447.dealII/447.dealII.test 2117.00 2127.00 0.5%
test-suite...-typeset/consumer-typeset.test 1047.00 1051.00 0.4%
test-suite...rks/tramp3d-v4/tramp3d-v4.test 814.00 816.00 0.2%
test-suite...3.xalancbmk/483.xalancbmk.test 1265.00 1267.00 0.2%
test-suite.../Prolangs-C++/vcirc/vcirc.test 11.00 11.00 0.0%

[fhahn]

Fix default value for EnableMemorySSA.

[xbolva00]

https://llvm-compile-time-tracker.com/compare.php?from=d545286b861cc6c460e36543ffd2771166847fa0&to=9e46fcc34c01386e5142e1630ad02e1284c49c67&stat=instructions

Looks great :) With some huge improvements for LTO.

[fhahn]

In D75025#2216000, @xbolva00 wrote:

https://llvm-compile-time-tracker.com/compare.php?from=d545286b861cc6c460e36543ffd2771166847fa0&to=9e46fcc34c01386e5142e1630ad02e1284c49c67&stat=instructions

Looks great :) With some huge improvements for LTO.

Unfortunately the improvements are against a large regression over legacy DSE. But I've been working on a further set of patches, which includes this one, to limit the gap between legacy DSE & MemorySSA-backed DSE, hopefully to a point where it is acceptable to switch (and improve compile-time further afterwards). Numbers: http://llvm-compile-time-tracker.com/compare.php?from=4cc20aa74339812c3e4daa4138ed40cb98521bfc&to=504153dc6efd29ad37ffb6ffb2e80d4101b56e5b&stat=instructions

More details: http://llvm-compile-time-tracker.com/compare.php?from=4cc20aa74339812c3e4daa4138ed40cb98521bfc&to=504153dc6efd29ad37ffb6ffb2e80d4101b56e5b&stat=instructions

[fhahn]

Rebase and ping.

This improves compile time, while also improving the number of removed stores in some cases (due to cutting off bad candidates earlier, rather than spending time and scan limit on them).

Improves geoman -O3 -0.15% ReleaseThinLTO -0.29%, ReleaseThinLTO (link only) -0.37%

http://llvm-compile-time-tracker.com/compare.php?from=dbab061a49f82c7d3bce4b3d601742d17df3daee&to=13e39ded7f8f772f9fd0d53aff8849e0a449509b&stat=instructions

[asbirlea]

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

1740

Delete "we".

1762

Remove "is"

[fhahn]

Rebase, address comments, thanks!

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

 
 #define DEBUG_TYPE "dse"
 
 STATISTIC(NumRedundantStores, "Number of redundant stores deleted");
 STATISTIC(NumFastStores, "Number of stores deleted");
 STATISTIC(NumFastOther, "Number of other instrs removed");
 STATISTIC(NumCompletePartials, "Number of stores dead by later partials");
 STATISTIC(NumModifiedStores, "Number of stores modified");
+STATISTIC(NumDomMemDefChecks, "Number of iterations in getDomMemoryDef");
 
 DEBUG_COUNTER(MemorySSACounter, "dse-memoryssa",
               "Controls which MemoryDefs are eliminated.");
 
 static cl::opt<bool>
 EnablePartialOverwriteTracking("enable-dse-partial-overwrite-tracking",
   cl::init(true), cl::Hidden,
   cl::desc("Enable partial-overwrite tracking in DSE"));
 
 static cl::opt<bool>
 EnablePartialStoreMerging("enable-dse-partial-store-merging",
   cl::init(true), cl::Hidden,
   cl::desc("Enable partial store merging in DSE"));
 
 static cl::opt<bool>
-    EnableMemorySSA("enable-dse-memoryssa", cl::init(false), cl::Hidden,
+    EnableMemorySSA("enable-dse-memoryssa", cl::init(true), cl::Hidden,
                     cl::desc("Use the new MemorySSA-backed DSE."));
 
 static cl::opt<unsigned>
     MemorySSAScanLimit("dse-memoryssa-scanlimit", cl::init(100), cl::Hidden,
                        cl::desc("The number of memory instructions to scan for "
                                 "dead store elimination (default = 100)"));
 
 static cl::opt<unsigned> MemorySSADefsPerBlockLimit(
struct DSEState {
   DenseMap<BasicBlock *, unsigned> PostOrderNumbers;
 
   /// Keep track of instructions (partly) overlapping with killing MemoryDefs per
   /// basic block.
   DenseMap<BasicBlock *, InstOverlapIntervalsTy> IOLs;
 
   Function *ExitUseFn;
 
+  struct CheckCache {
+    SmallPtrSet<MemoryAccess *, 16> KnownNoReads;
+    SmallPtrSet<MemoryAccess *, 16> KnownReads;
+
+    bool isKnownNoRead(MemoryAccess *A) const {
+      return KnownNoReads.find(A) != KnownNoReads.end();
+    }
+    bool isKnownRead(MemoryAccess *A) const {
+      return KnownReads.find(A) != KnownReads.end();
+    }
+  };
+
   DSEState(Function &F, AliasAnalysis &AA, MemorySSA &MSSA, DominatorTree &DT,
            PostDominatorTree &PDT, const TargetLibraryInfo &TLI)
       : F(F), AA(AA), MSSA(MSSA), DT(DT), PDT(PDT), TLI(TLI) {}
 
   static DSEState get(Function &F, AliasAnalysis &AA, MemorySSA &MSSA,
                       DominatorTree &DT, PostDominatorTree &PDT,
                       const TargetLibraryInfo &TLI) {
     DSEState State(F, AA, MSSA, DT, PDT, TLI);
struct DSEState {
   }
 
   // Find a MemoryDef writing to \p DefLoc and dominating \p Current, with no
   // read access in between or return None otherwise. The returned value may not
   // (completely) overwrite \p DefLoc. Currently we bail out when we encounter
   // any of the following
   //  * An aliasing MemoryUse (read).
   //  * A MemoryPHI.
-  Optional<MemoryAccess *> getDomMemoryDef(MemoryDef *KillingDef,
-                                           MemoryAccess *Current,
-                                           MemoryLocation DefLoc,
-                                           bool DefVisibleToCaller,
-                                           int &ScanLimit) const {
+  Optional<MemoryAccess *>
+  getDomMemoryDef(MemoryDef *KillingDef, MemoryAccess *Current,
+                  MemoryLocation DefLoc, bool DefVisibleToCaller,
+                  CheckCache &Cache, int &ScanLimit) const {
     MemoryAccess *DomAccess;
     bool StepAgain;
     LLVM_DEBUG(dbgs() << "  trying to get dominating access for " << *Current
                       << "\n");
     // Find the next clobbering Mod access for DefLoc, starting at Current.
     do {
       StepAgain = false;
       // Reached TOP.
getDomMemoryDef(MemoryDef *KillingDef, MemoryAccess *Current,
 
     SmallSetVector<MemoryAccess *, 32> WorkList;
     auto PushMemUses = [&WorkList](MemoryAccess *Acc) {
       for (Use &U : Acc->uses())
         WorkList.insert(cast<MemoryAccess>(U.getUser()));
     };
     PushMemUses(DomAccess);
 
+    // Optimistically collect all accesses we for reads. If we do not find any
+    // read clobbers, add them to the cache.
+    SmallPtrSet<MemoryAccess *, 16> KnownNoReads;
     // Check if DomDef may be read.
     for (unsigned I = 0; I < WorkList.size(); I++) {
       MemoryAccess *UseAccess = WorkList[I];
-
+      NumDomMemDefChecks++;
       LLVM_DEBUG(dbgs() << "   Checking use " << *UseAccess);
       if (--ScanLimit == 0) {
         LLVM_DEBUG(dbgs() << "  ...  hit scan limit\n");
         return None;
       }
 
+      // Check if we already visited this access.
+      if (Cache.isKnownNoRead(UseAccess)) {
+        LLVM_DEBUG(dbgs() << " ... skip, discovered that " << *UseAccess
+                          << " is safe earlier.\n");
+        continue;
+      }
+      if (Cache.isKnownRead(UseAccess)) {
+        LLVM_DEBUG(dbgs() << " ... bail out, discovered that " << *UseAccess
+                          << " is has a read-clobber earlier.\n");
+        return None;
+      }
+      KnownNoReads.insert(UseAccess);
+
       if (isa<MemoryPhi>(UseAccess)) {
         PushMemUses(UseAccess);
         continue;
       }
 
       Instruction *UseInst = cast<MemoryUseOrDef>(UseAccess)->getMemoryInst();
       LLVM_DEBUG(dbgs() << " (" << *UseInst << ")\n");
 
       if (isNoopIntrinsic(cast<MemoryUseOrDef>(UseAccess))) {
         PushMemUses(UseAccess);
         continue;
       }
 
       // A memory terminator kills all preceeding MemoryDefs and all succeeding
       // MemoryAccesses. We do not have to check it's users.
       if (isMemTerminator(DefLoc, UseInst))
         continue;
 
       // Uses which may read the original MemoryDef mean we cannot eliminate the
       // original MD. Stop walk.
       if (isReadClobber(DefLoc, UseInst)) {
         LLVM_DEBUG(dbgs() << "  ... found read clobber\n");
+        Cache.KnownReads.insert(UseAccess);
+        Cache.KnownReads.insert(Current);
         return None;
       }
 
       // For the KillingDef we only have to check if it reads the memory
       // location.
       // TODO: It would probably be better to check for self-reads before
       // calling the function.
       if (KillingDef == UseAccess)
for (unsigned I = 0; I < WorkList.size(); I++) {
              isOverwrite(DefLoc, *CC, DL, TLI, DepWriteOffset, InstWriteOffset,
                          UseInst, IOL, AA, &F) != OW_Complete)) {
           LLVM_DEBUG(dbgs() << "  ... found non-aliasing MemoryDef\n");
           PushMemUses(UseDef);
         }
       }
     }
 
+    Cache.KnownNoReads.insert(KnownNoReads.begin(), KnownNoReads.end());
     // No aliasing MemoryUses of DomAccess found, DomAccess is potentially dead.
     return {DomAccess};
   }
 
   // Delete dead memory defs
   void deleteDeadInstruction(Instruction *SI) {
     MemorySSAUpdater Updater(&MSSA);
     SmallVector<Instruction *, 32> NowDeadInsts;
for (unsigned I = 0; I < State.MemDefs.size(); I++) {
     LLVM_DEBUG(dbgs() << "Trying to eliminate MemoryDefs killed by "
                       << *KillingDef << " (" << *SI << ")\n");
 
     int ScanLimit = MemorySSAScanLimit;
     // Worklist of MemoryAccesses that may be killed by KillingDef.
     SetVector<MemoryAccess *> ToCheck;
     ToCheck.insert(KillingDef->getDefiningAccess());
 
+    DSEState::CheckCache Cache;
     // Check if MemoryAccesses in the worklist are killed by KillingDef.
     for (unsigned I = 0; I < ToCheck.size(); I++) {
       Current = ToCheck[I];
       if (State.SkipStores.count(Current))
         continue;
 
       Optional<MemoryAccess *> Next = State.getDomMemoryDef(
-          KillingDef, Current, SILoc, DefVisibleToCaller, ScanLimit);
+          KillingDef, Current, SILoc, DefVisibleToCaller, Cache, ScanLimit);
 
       if (!Next) {
         LLVM_DEBUG(dbgs() << "  finished walk\n");
         continue;
       }
 
       MemoryAccess *DomAccess = *Next;
       LLVM_DEBUG(dbgs() << " Checking if we can kill " << *DomAccess << "\n");

llvm/test/Transforms/DeadStoreElimination/MSSA/combined-partial-overwrites.ll

 }
 
 define signext i8 @test5(i32 *%ptr) {
 ; CHECK-LABEL: @test5(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[BPTR:%.*]] = bitcast i32* [[PTR:%.*]] to i8*
 ; CHECK-NEXT:    [[BPTR1:%.*]] = getelementptr inbounds i8, i8* [[BPTR]], i64 1
 ; CHECK-NEXT:    [[BPTR2:%.*]] = getelementptr inbounds i8, i8* [[BPTR]], i64 2
+; CHECK-NEXT:    [[BPTR3:%.*]] = getelementptr inbounds i8, i8* [[BPTR]], i64 3
 ; CHECK-NEXT:    [[WPTR:%.*]] = bitcast i8* [[BPTR]] to i16*
 ; CHECK-NEXT:    [[WPTR1:%.*]] = bitcast i8* [[BPTR1]] to i16*
 ; CHECK-NEXT:    [[WPTR2:%.*]] = bitcast i8* [[BPTR2]] to i16*
 ; CHECK-NEXT:    store i16 -1, i16* [[WPTR2]], align 1
 ; CHECK-NEXT:    store i16 1456, i16* [[WPTR1]], align 1
 ; CHECK-NEXT:    store i16 1346, i16* [[WPTR]], align 1
 ; CHECK-NEXT:    ret i8 0
 ;