[DSE] Eliminate stores by terminators (free,lifetime.end).

[fhahn]

Summary

This patch adds support for eliminating stores by free & lifetime.end
calls. We can remove stores that are not read before calling a memory
terminator and we can eliminate all stores after a memory terminator
until we see a new lifetime.start. The second case seems to not really
trigger much in practice though.

[merge_guards_bot]

Unit tests: unknown.

clang-tidy: unknown.

clang-format: unknown.

Build artifacts: diff.json, console-log.txt

[fhahn]

rebase

[merge_guards_bot]

Unit tests: unknown.

clang-tidy: unknown.

clang-format: unknown.

Build artifacts: diff.json, console-log.txt

[fhahn]

Needs updating to work bottom-up.

[fhahn]

Ping. Rebased after D72700 landed.

[fhahn]

ping

[fhahn]

Ping :) Rebased after recent changes.

[fhahn]

ping :)

[asbirlea]

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

1705

I'm not sure how expensive the isFreeCall is, but the check is already done inside the call to getLocForTerminator. You could add a bool optional, or return a pair, if worth eliminating the repeated check.

2268

I don't understand how this change is related.

[fhahn]

Addressed comments, thanks! I updated getLocForTerminator to return an optional pair and removed the unnecessary ToCheck.insert calls.

[fhahn]

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

1705

Done, thanks!

2268

It looks like this was a leftover from an earlier rebase. I removed it. It should not be required as it is already added around line 2205.

[asbirlea]

Thanks you, LGTM.

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

 #include "llvm/IR/InstrTypes.h"
 #include "llvm/IR/Instruction.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/IntrinsicInst.h"
 #include "llvm/IR/Intrinsics.h"
 #include "llvm/IR/LLVMContext.h"
 #include "llvm/IR/Module.h"
 #include "llvm/IR/PassManager.h"
+#include "llvm/IR/PatternMatch.h"
 #include "llvm/IR/Value.h"
 #include "llvm/InitializePasses.h"
 #include "llvm/Pass.h"
 #include "llvm/Support/Casting.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/DebugCounter.h"
 #include "llvm/Support/ErrorHandling.h"
 #include "llvm/Support/MathExtras.h"
 #include "llvm/Support/raw_ostream.h"
 #include "llvm/Transforms/Scalar.h"
 #include "llvm/Transforms/Utils/AssumeBundleBuilder.h"
 #include "llvm/Transforms/Utils/Local.h"
 #include <algorithm>
 #include <cassert>
 #include <cstddef>
 #include <cstdint>
 #include <iterator>
 #include <map>
 #include <utility>
 
 using namespace llvm;
+using namespace PatternMatch;
 
 #define DEBUG_TYPE "dse"
 
 STATISTIC(NumRemainingStores, "Number of stores remaining after 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");
for (BasicBlock *BB : post_order(&F)) {
       State.PostOrderNumbers[BB] = PO++;
       for (Instruction &I : *BB) {
         MemoryAccess *MA = MSSA.getMemoryAccess(&I);
         if (I.mayThrow() && !MA)
           State.ThrowingBlocks.insert(I.getParent());
 
         auto *MD = dyn_cast_or_null<MemoryDef>(MA);
         if (MD && State.MemDefs.size() < MemorySSADefsPerBlockLimit &&
-            State.getLocForWriteEx(&I))
+            (State.getLocForWriteEx(&I) || State.isMemTerminatorInst(&I)))
           State.MemDefs.push_back(MD);
 
         // Track whether alloca and alloca-like objects are visible in the
         // caller before and after the function returns. Alloca objects are
         // invalid in the caller, so they are neither visible before or after
         // the function returns.
         if (isa<AllocaInst>(&I)) {
           State.InvisibleToCallerBeforeRet.insert(&I);
for (unsigned I = 0; I < WorkList.size(); I++) {
       }
 
       if (MemoryDef *UseDef = dyn_cast<MemoryDef>(UseAccess))
         PushMemUses(UseDef);
     }
     return true;
   }
 
+  /// If \p I is a memory  terminator like llvm.lifetime.end or free, return a
+  /// pair with the MemoryLocation terminated by \p I and a boolean flag
+  /// indicating whether \p I is a free-like call.
+  Optional<std::pair<MemoryLocation, bool>>
+  getLocForTerminator(Instruction *I) const {
+    uint64_t Len;
+    Value *Ptr;
+    if (match(I, m_Intrinsic<Intrinsic::lifetime_end>(m_ConstantInt(Len),
+                                                      m_Value(Ptr))))
+      return {std::make_pair(MemoryLocation(Ptr, Len), false)};
+
+    if (auto *CB = dyn_cast<CallBase>(I)) {
+      if (isFreeCall(I, &TLI))
+        return {std::make_pair(MemoryLocation(CB->getArgOperand(0)), true)};
+    }
+
+    return None;
+  }
+
+  /// Returns true if \p I is a memory terminator instruction like
+  /// llvm.lifetime.end or free.
+  bool isMemTerminatorInst(Instruction *I) const {
+    IntrinsicInst *II = dyn_cast<IntrinsicInst>(I);
+    return (II && II->getIntrinsicID() == Intrinsic::lifetime_end) ||
+           isFreeCall(I, &TLI);
+  }
+
+  /// Returns true if \p MaybeTerm is a memory terminator for the same
+  /// underlying object as \p DefLoc.
+  bool isMemTerminator(MemoryLocation DefLoc, Instruction *MaybeTerm) const {
+    Optional<std::pair<MemoryLocation, bool>> MaybeTermLoc =
+        getLocForTerminator(MaybeTerm);
+
+    if (!MaybeTermLoc)
+      return false;
+
+    // If the terminator is a free-like call, all accesses to the underlying
+    // object can be considered terminated.
+    if (MaybeTermLoc->second) {
+      DataLayout DL = MaybeTerm->getParent()->getModule()->getDataLayout();
+      DefLoc = MemoryLocation(GetUnderlyingObject(DefLoc.Ptr, DL));
+    }
+    return AA.isMustAlias(MaybeTermLoc->first, DefLoc);
+  }
+
   // Returns true if \p Use may read from \p DefLoc.
   bool isReadClobber(MemoryLocation DefLoc, Instruction *UseInst) const {
     if (!UseInst->mayReadFromMemory())
       return false;
 
     if (auto *CB = dyn_cast<CallBase>(UseInst))
       if (CB->onlyAccessesInaccessibleMemory())
         return false;
for (unsigned I = 0; I < WorkList.size(); I++) {
       LLVM_DEBUG(dbgs() << " (" << *UseInst << ")\n");
 
       if (isNoopIntrinsic(cast<MemoryUseOrDef>(UseAccess))) {
         LLVM_DEBUG(dbgs() << "    ... adding uses of intrinsic\n");
         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");
         return None;
       }
 
       // For the KillingDef and DomAccess we only have to check if it reads the
bool eliminateDeadStoresMemorySSA(Function &F, AliasAnalysis &AA,
   // For each store:
   for (unsigned I = 0; I < State.MemDefs.size(); I++) {
     MemoryDef *KillingDef = State.MemDefs[I];
     if (State.SkipStores.count(KillingDef))
       continue;
     Instruction *SI = KillingDef->getMemoryInst();
 
     auto MaybeSILoc = State.getLocForWriteEx(SI);
+    if (State.isMemTerminatorInst(SI))
+      MaybeSILoc = State.getLocForTerminator(SI).map(
+          [](const std::pair<MemoryLocation, bool> &P) { return P.first; });
+    else
+      MaybeSILoc = State.getLocForWriteEx(SI);
+
     if (!MaybeSILoc) {
       LLVM_DEBUG(dbgs() << "Failed to find analyzable write location for "
                         << *SI << "\n");
       continue;
     }
     MemoryLocation SILoc = *MaybeSILoc;
     assert(SILoc.Ptr && "SILoc should not be null");
     const Value *SILocUnd = GetUnderlyingObject(SILoc.Ptr, DL);
for (unsigned I = 0; I < ToCheck.size(); I++) {
         LLVM_DEBUG(dbgs() << "  ... skip, cannot remove def\n");
         continue;
       }
 
       if (!DebugCounter::shouldExecute(MemorySSACounter))
         continue;
 
       MemoryLocation NILoc = *State.getLocForWriteEx(NI);
+
+      if (State.isMemTerminatorInst(SI)) {
+        const Value *NIUnd = GetUnderlyingObject(NILoc.Ptr, DL);
+        if (!SILocUnd || SILocUnd != NIUnd)
+          continue;
+        LLVM_DEBUG(dbgs() << "DSE: Remove Dead Store:\n  DEAD: " << *NI
+                          << "\n  KILLER: " << *SI << '\n');
+        State.deleteDeadInstruction(NI);
+        ++NumFastStores;
+        MadeChange = true;
+      } else {
         // Check if NI overwrites SI.
         int64_t InstWriteOffset, DepWriteOffset;
         auto Iter = State.IOLs.insert(
             std::make_pair<BasicBlock *, InstOverlapIntervalsTy>(
                 NI->getParent(), InstOverlapIntervalsTy()));
         auto &IOL = Iter.first->second;
         OverwriteResult OR = isOverwrite(SILoc, NILoc, DL, TLI, DepWriteOffset,
                                          InstWriteOffset, NI, IOL, AA, &F);
 
         if (EnablePartialStoreMerging && OR == OW_PartialEarlierWithFullLater) {
           auto *Earlier = dyn_cast<StoreInst>(NI);
           auto *Later = dyn_cast<StoreInst>(SI);
           if (Constant *Merged = tryToMergePartialOverlappingStores(
                   Earlier, Later, InstWriteOffset, DepWriteOffset, DL, &AA,
                   &DT)) {
 
             // Update stored value of earlier store to merged constant.
             Earlier->setOperand(0, Merged);
             ++NumModifiedStores;
             MadeChange = true;
 
-          // Remove later store and remove any outstanding overlap intervals for
-          // the updated store.
+            // Remove later store and remove any outstanding overlap intervals
+            // for the updated store.
             State.deleteDeadInstruction(Later);
             auto I = State.IOLs.find(Earlier->getParent());
             if (I != State.IOLs.end())
               I->second.erase(Earlier);
             break;
           }
         }
 
         if (OR == OW_Complete) {
           LLVM_DEBUG(dbgs() << "DSE: Remove Dead Store:\n  DEAD: " << *NI
                             << "\n  KILLER: " << *SI << '\n');
           State.deleteDeadInstruction(NI);
           ++NumFastStores;
           MadeChange = true;
         }
       }
     }
+  }
 
   if (EnablePartialOverwriteTracking)
     for (auto &KV : State.IOLs)
       MadeChange |= removePartiallyOverlappedStores(&AA, DL, KV.second);
 
   MadeChange |= State.eliminateDeadWritesAtEndOfFunction();
   return MadeChange;
 }

llvm/test/Transforms/DeadStoreElimination/MSSA/2016-07-17-UseAfterFree.ll

-; XFAIL: *
-; RUN: opt < %s -basic-aa -dse-enable-dse-memoryssa  -S -enable-dse-partial-overwrite-tracking | FileCheck %s
+; RUN: opt < %s -basic-aa -dse -enable-dse-memoryssa  -S -enable-dse-partial-overwrite-tracking | FileCheck %s
 ; PR28588
 
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 target triple = "x86_64-unknown-linux-gnu"
 
 ; Function Attrs: nounwind
 define void @_UPT_destroy(i8* nocapture %ptr) local_unnamed_addr #0 {
 entry:

llvm/test/Transforms/DeadStoreElimination/MSSA/free.ll

-; XFAIL: *
-
 ; RUN: opt < %s -basic-aa -dse -enable-dse-memoryssa -S | FileCheck %s
 
 target datalayout = "e-p:64:64:64"
 
 declare void @free(i8* nocapture)
 declare noalias i8* @malloc(i64)
 
 ; CHECK-LABEL: @test(

llvm/test/Transforms/DeadStoreElimination/MSSA/lifetime.ll

-; XFAIL: *
-
 ; RUN: opt -S -basic-aa -dse -enable-dse-memoryssa < %s | FileCheck %s
 
 target datalayout = "E-p:64:64:64-a0:0:8-f32:32:32-f64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:32:64-v64:64:64-v128:128:128"
 
 declare void @llvm.lifetime.start.p0i8(i64, i8* nocapture) nounwind
 declare void @llvm.lifetime.end.p0i8(i64, i8* nocapture) nounwind
 declare void @llvm.memset.p0i8.i8(i8* nocapture, i8, i8, i1) nounwind
 
; CHECK: test2
   call void @llvm.lifetime.start.p0i8(i64 4, i8* %R)
 ; CHECK: lifetime.start
   store i32 0, i32* %Q  ;; This store is dead.
 ; CHECK-NOT: store
   call void @llvm.lifetime.end.p0i8(i64 4, i8* %R)
 ; CHECK: lifetime.end
   ret void
 }
-
-

llvm/test/Transforms/DeadStoreElimination/MSSA/memset-missing-debugloc.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; Test that the getelementptr generated when the dse pass determines that
 ; a memset can be shortened has the debugloc carried over from the memset.
 
 ; RUN: opt -S -march=native -dse -enable-dse-memoryssa < %s| FileCheck %s
 ; CHECK: bitcast [5 x i64]* %{{[a-zA-Z_][a-zA-Z0-9_]*}} to i8*, !dbg
 ; CHECK-NEXT: %{{[0-9]+}} = getelementptr inbounds i8, i8* %0, i64 32, !dbg ![[DBG:[0-9]+]]
 ; CHECK-NEXT: call void @llvm.memset.p0i8.i64(i8* align 16 %1, i8 0, i64 8, i1 false), !dbg ![[DBG:[0-9]+]]
 ; CHECK: ![[DBG]] = !DILocation(line: 2,

llvm/test/Transforms/DeadStoreElimination/MSSA/multiblock-captures.ll

;
   call void @may_throw()
   br label %exit
 
 exit:
   store i8 1, i8* %m
   call void @capture(i8* %m)
   ret i8* %m
 }
+
 ; Stores to stack objects can be eliminated if they are not captured inside the function.
 define void @test_alloca_nocapture_1() {
 ; CHECK-LABEL: @test_alloca_nocapture_1(
 ; CHECK-NEXT:    call void @foo()
 ; CHECK-NEXT:    br label [[EXIT:%.*]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    ret void
 ;

llvm/test/Transforms/DeadStoreElimination/MSSA/multiblock-malloc-free.ll

 declare noalias i8* @calloc(i64, i64) #5
 declare noalias i8* @malloc(i64) #0
 declare noalias i8* @strdup(i8* nocapture readonly) #1
 declare void @free(i8* nocapture) #2
 
 define void @test16(i32* noalias %P) {
 ; CHECK-LABEL: @test16(
 ; CHECK-NEXT:    [[P2:%.*]] = bitcast i32* [[P:%.*]] to i8*
-; CHECK-NEXT:    store i32 1, i32* [[P]]
 ; CHECK-NEXT:    br i1 true, label [[BB1:%.*]], label [[BB3:%.*]]
 ; CHECK:       bb1:
-; CHECK-NEXT:    store i32 1, i32* [[P]]
 ; CHECK-NEXT:    br label [[BB3]]
 ; CHECK:       bb3:
 ; CHECK-NEXT:    call void @free(i8* [[P2]])
+; CHECK-NEXT:    store i32 1, i32* [[P]]
 ; CHECK-NEXT:    ret void
 ;
   %P2 = bitcast i32* %P to i8*
   store i32 1, i32* %P
   br i1 true, label %bb1, label %bb3
 bb1:
   store i32 1, i32* %P
   br label %bb3
 bb3:
   call void @free(i8* %P2)
+  store i32 1, i32* %P
   ret void
 }
 
 
 define void @test17(i32* noalias %P) {
 ; CHECK-LABEL: @test17(
 ; CHECK-NEXT:    [[P2:%.*]] = bitcast i32* [[P:%.*]] to i8*
-; CHECK-NEXT:    store i32 1, i32* [[P]]
 ; CHECK-NEXT:    br i1 true, label [[BB1:%.*]], label [[BB3:%.*]]
 ; CHECK:       bb1:
 ; CHECK-NEXT:    call void @unknown_func()
-; CHECK-NEXT:    store i32 1, i32* [[P]]
 ; CHECK-NEXT:    br label [[BB3]]
 ; CHECK:       bb3:
 ; CHECK-NEXT:    call void @free(i8* [[P2]])
 ; CHECK-NEXT:    ret void
 ;
   %P2 = bitcast i32* %P to i8*
   store i32 1, i32* %P
   br i1 true, label %bb1, label %bb3
 bb1:
   call void @unknown_func()
   store i32 1, i32* %P
   br label %bb3
 bb3:
   call void @free(i8* %P2)
   ret void
 }
 
+define void @test17_read_after_free(i32* noalias %P) {
+; CHECK-LABEL: @test17_read_after_free(
+; CHECK-NEXT:    [[P2:%.*]] = bitcast i32* [[P:%.*]] to i8*
+; CHECK-NEXT:    br i1 true, label [[BB1:%.*]], label [[BB3:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    br label [[BB3]]
+; CHECK:       bb3:
+; CHECK-NEXT:    call void @free(i8* [[P2]])
+; CHECK-NEXT:    [[LV:%.*]] = load i8, i8* [[P2]]
+; CHECK-NEXT:    ret void
+;
+  %P2 = bitcast i32* %P to i8*
+  store i32 1, i32* %P
+  br i1 true, label %bb1, label %bb3
+bb1:
+  store i32 1, i32* %P
+  br label %bb3
+bb3:
+  call void @free(i8* %P2)
+  %lv = load i8, i8* %P2
+  ret void
+}
+
+
 define void @test6(i32* noalias %P) {
 ; CHECK-LABEL: @test6(
 ; CHECK-NEXT:    br i1 true, label [[BB1:%.*]], label [[BB2:%.*]]
 ; CHECK:       bb1:
 ; CHECK-NEXT:    br label [[BB3:%.*]]
 ; CHECK:       bb2:
 ; CHECK-NEXT:    call void @unknown_func()
 ; CHECK-NEXT:    br label [[BB3]]

llvm/test/Transforms/DeadStoreElimination/MSSA/simple.ll

 ; I think this case is currently handled incorrectly by memdeps dse
 ; throwing should leave store i32 1, not remove from the free.
 declare void @free(i8* nocapture)
 define void @test41(i32* noalias %P) {
 ; CHECK-LABEL: @test41(
 ; CHECK-NEXT:    [[P2:%.*]] = bitcast i32* [[P:%.*]] to i8*
 ; CHECK-NEXT:    store i32 1, i32* [[P]], align 4
 ; CHECK-NEXT:    call void @unknown_func()
-; CHECK-NEXT:    store i32 2, i32* [[P]], align 4
 ; CHECK-NEXT:    call void @free(i8* [[P2]])
 ; CHECK-NEXT:    ret void
 ;
   %P2 = bitcast i32* %P to i8*
   store i32 1, i32* %P
   call void @unknown_func()
   store i32 2, i32* %P
   call void @free(i8* %P2)