[DSE] Eliminate store after calloc (PR50143)

[fhahn]

llvm/lib/Analysis/AliasAnalysis.cpp

241

From this workaround, it seems like how inaccessiblememonly is used for calloc does not completely match AA's interpretation. Are there other cases in the code base? I'm not sure if special casing calloc here is ideal.

I think we should probably treat the AA change as a separate patch, with an AA only test as well, perhaps llvm/test/Analysis/BasicAA/libfuncs.ll?

[xbolva00]

llvm/lib/Analysis/AliasAnalysis.cpp

241

Not only calloc, all alloc (calloc, malloc, aligned_alloc) fns have inaccessiblememonly. inaccessiblememonly was introduced long time ago but this attribute was basically dead, no libfunc used it until recently.

Sadly, inaccessiblememonly is somehow broken nowdays as the code assumes that such call does not write or read memory, but of course it returns memory.

This AA change can be separated patch (but this DSE needs it as a prerequisite)

Another solution is removal of inaccessiblememonly from alloc fns, as it caused more harm then improvements.

[nikic]

llvm/lib/Analysis/AliasAnalysis.cpp

241

Your new implementation claims that inaccessiblememonly alloc-like fns mod all locations -- if that's what you want, just drop the attribute from the functions entirely. That will have about the same effect.

I think inaccessiblememonly is fine for modeling malloc behavior (or do you see any issues there as well?), the problem is with calloc which combines malloc (inaccessiblememonly) with a write to the location (accessible). As @jdoerfert already pointed out on the PR, properly modelling this would require "inaccessible_or_returned_memonly".

While I'm somewhat open to DSE hacks, I don't think making this change on the AA layer is acceptable. I think dropping inaccessiblememonly inference for calloc() specifically would be the right thing to do in the meantime.

[xbolva00]

llvm/lib/Analysis/AliasAnalysis.cpp

241

Yeah, I will just drop it from calloc.

[xbolva00]

llvm/lib/Analysis/AliasAnalysis.cpp

241

I think inaccessiblememonly is fine for modeling malloc behavior (or do you see any issues there as well?)

Just found one I think.

Imagine you want to change malloc+memset combo to calloc

auto *UnderlyingDef =
     cast<MemoryDef>(MSSA.getMemoryAccess(MallocInst));
 // If UnderlyingDef is the clobbering access of Def, no instructions
 // between them can modify the memory location.
 auto *ClobberDef =
     MSSA.getSkipSelfWalker()->getClobberingMemoryAccess(MemsetDef);
 return UnderlyingDef == ClobberDef;

This will fail.

[xbolva00]

llvm/lib/Analysis/AliasAnalysis.cpp

241

I am wondering whether there is other solution or should I just remove inaccessiblememonly from malloc too?

@jdoerfert @fhahn

I tried also to use memoryIsNotModifiedBetween but
MemoryLocation MemLoc = MemoryLocation::get(MemsetInst)

MemLoc is None

[yurai007]

llvm/lib/Analysis/AliasAnalysis.cpp

241

@xbolva00:
For MemsetInst getForDest(MemSet) gives correct MemLoc.
Then DT.dominates + memoryIsNotModifiedBetween combination do the job: https://pastebin.com/iBvpdQAh
It seems to be enough to teach DSE how eliminate malloc+memset and emit calloc (I checked couple of UTs and it works).
Removing inaccessiblememonly attribute in malloc or touching AA machinery is not needed.

[xbolva00]

llvm/lib/Analysis/AliasAnalysis.cpp

241

Great! Please post new patch :)

[yurai007]

llvm/lib/Analysis/AliasAnalysis.cpp

241

Sure. I cannot uploaded diff to this one so created new instead: https://reviews.llvm.org/D103009

llvm/lib/Analysis/AliasAnalysis.cpp

 
 #include "llvm/Analysis/AliasAnalysis.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/BasicAliasAnalysis.h"
 #include "llvm/Analysis/CFLAndersAliasAnalysis.h"
 #include "llvm/Analysis/CFLSteensAliasAnalysis.h"
 #include "llvm/Analysis/CaptureTracking.h"
 #include "llvm/Analysis/GlobalsModRef.h"
+#include "llvm/Analysis/MemoryBuiltins.h"
 #include "llvm/Analysis/MemoryLocation.h"
 #include "llvm/Analysis/ObjCARCAliasAnalysis.h"
 #include "llvm/Analysis/ScalarEvolutionAliasAnalysis.h"
 #include "llvm/Analysis/ScopedNoAliasAA.h"
 #include "llvm/Analysis/TargetLibraryInfo.h"
 #include "llvm/Analysis/TypeBasedAliasAnalysis.h"
 #include "llvm/Analysis/ValueTracking.h"
 #include "llvm/IR/Argument.h"
for (const auto &AA : AAs) {
     if (isNoModRef(Result))
       return ModRefInfo::NoModRef;
   }
 
   // Try to refine the mod-ref info further using other API entry points to the
   // aggregate set of AA results.
   auto MRB = getModRefBehavior(Call);
   if (onlyAccessesInaccessibleMem(MRB))
-    return ModRefInfo::NoModRef;
+    return isAllocLikeFn(Call, &TLI) ? ModRefInfo::Mod : ModRefInfo::NoModRef;
 
   if (onlyReadsMemory(MRB))
     Result = clearMod(Result);
   else if (doesNotReadMemory(MRB))
     Result = clearRef(Result);
 
   if (onlyAccessesArgPointees(MRB) || onlyAccessesInaccessibleOrArgMem(MRB)) {
     bool IsMustAlias = true;

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

if (const IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) {
     default:
       return false;
     }
   }
   return false;
 }
 
 // Check if we can ignore \p D for DSE.
-bool canSkipDef(MemoryDef *D, bool DefVisibleToCaller) {
+bool canSkipDef(MemoryDef *D, bool DefVisibleToCaller,
+                const TargetLibraryInfo &TLI) {
   Instruction *DI = D->getMemoryInst();
   // Calls that only access inaccessible memory cannot read or write any memory
   // locations we consider for elimination.
   if (auto *CB = dyn_cast<CallBase>(DI))
-    if (CB->onlyAccessesInaccessibleMemory())
+    if (CB->onlyAccessesInaccessibleMemory()) {
+      if (isAllocLikeFn(DI, &TLI))
+        return false;
       return true;
+    }
 
   // We can eliminate stores to locations not visible to the caller across
   // throwing instructions.
   if (DI->mayThrow() && !DefVisibleToCaller)
     return true;
 
   // We can remove the dead stores, irrespective of the fence and its ordering
   // (release/acquire/seq_cst). Fences only constraints the ordering of
   // already visible stores, it does not make a store visible to other
   // threads. So, skipping over a fence does not change a store from being
   // dead.
   if (isa<FenceInst>(DI))
     return true;
 
   // Skip intrinsics that do not really read or modify memory.
-  if (isNoopIntrinsic(D->getMemoryInst()))
+  if (isNoopIntrinsic(DI))
     return true;
 
   return false;
 }
 
 struct DSEState {
   Function &F;
   AliasAnalysis &AA;
do {
         return Current;
       }
 
       // Below, check if CurrentDef is a valid candidate to be eliminated by
       // KillingDef. If it is not, check the next candidate.
       MemoryDef *CurrentDef = cast<MemoryDef>(Current);
       Instruction *CurrentI = CurrentDef->getMemoryInst();
 
-      if (canSkipDef(CurrentDef, !isInvisibleToCallerBeforeRet(DefUO))) {
+      if (canSkipDef(CurrentDef, !isInvisibleToCallerBeforeRet(DefUO), TLI)) {
         StepAgain = true;
         Current = CurrentDef->getDefiningAccess();
         continue;
       }
 
       // Before we try to remove anything, check for any extra throwing
       // instructions that block us from DSEing
       if (mayThrowBetween(KillingI, CurrentI, DefUO)) {

llvm/test/Transforms/DeadStoreElimination/noop-stores.ll

entry:
   store i32 %lv, i32* %x, align 4
   ret void
 }
 
 ; PR50143
 define i8* @store_zero_after_calloc_inaccessiblememonly() {
 ; CHECK-LABEL: @store_zero_after_calloc_inaccessiblememonly(
 ; CHECK-NEXT:    [[CALL:%.*]] = tail call i8* @calloc(i64 1, i64 10) #[[ATTR6:[0-9]+]]
-; CHECK-NEXT:    store i8 0, i8* [[CALL]], align 1
 ; CHECK-NEXT:    ret i8* [[CALL]]
 ;
   %call = tail call i8* @calloc(i64 1, i64 10)  inaccessiblememonly
   store i8 0, i8* %call
   ret i8* %call
 }
 
 define i8* @zero_memset_after_calloc()  {
;
   store i8 %v, i8* %gep
   call void @llvm.memset.p0i8.i64(i8* %call, i8 0, i64 20, i1 false)
   ret i8* %call
 }
 
 define i8* @zero_memset_after_calloc_inaccessiblememonly()  {
 ; CHECK-LABEL: @zero_memset_after_calloc_inaccessiblememonly(
 ; CHECK-NEXT:    [[CALL:%.*]] = tail call i8* @calloc(i64 10000, i64 4) #[[ATTR6]]
-; CHECK-NEXT:    call void @llvm.memset.p0i8.i64(i8* [[CALL]], i8 0, i64 40000, i1 false)
 ; CHECK-NEXT:    ret i8* [[CALL]]
 ;
   %call = tail call i8* @calloc(i64 10000, i64 4) inaccessiblememonly
   call void @llvm.memset.p0i8.i64(i8* %call, i8 0, i64 40000, i1 false)
   ret i8* %call
 }
 
 define i8* @cst_nonzero_memset_after_calloc() {