[DSE] Improve handling of `strncpy` in Dead Store Elimination

[fwolff]

Summary

Fixes PR#52062 and one of the remaining cases of PR#47644.

[lebedev.ri]

llvm/test/Transforms/DeadStoreElimination/memset-and-strncpy.ll

2 ↗

(On Diff #387760)

Tests for passes should only test that particular pass, not the whole optimization pipeline.

[xbolva00]

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

1067

Use LLVM_FALLTHROUGH;

1375

Code comment please. Maybe use switch if there are more libcalls which could be added here?

[xbolva00]

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

216

Same here

[fhahn]

Is there a way to add the right attributes to strncpy to avoid needing to special case it in DSE?

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

223

Are we missing a return MemoryLocation::getAfter(CB->getArgOperand(0)) here to preserve the existing behavior if *CB is not a libfunc (or not available)?

1372

having this logic here makes the code harder to read. Can this be moved to isReadClobber? Or into BasicAAResult::getModRefInfo directly?

[xbolva00]

In D114035#3139813, @fhahn wrote:

Is there a way to add the right attributes to strncpy to avoid needing to special case it in DSE?

It would be great to somehow connect write_only/read_only with size arg but I dont think this is possible now. GCC’s access attribute is more poweful and it can be used in this way.

Maybe good idea for GSoC?

[fhahn]

In D114035#3139988, @xbolva00 wrote:

In D114035#3139813, @fhahn wrote:

Is there a way to add the right attributes to strncpy to avoid needing to special case it in DSE?

It would be great to somehow connect write_only/read_only with size arg but I dont think this is possible now. GCC’s access attribute is more poweful and it can be used in this way.

Yeah, but I was actually thinking about the special handling for isReadClobber (see inline comments). I don't think the special handling there is needed, because should strncpy already have the required attributes to determine it is not a read clobber.

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

1372

Actually this should not be needed, because strncpy already *has* the correct attributes (first arg write only, second arg readonly and function argmemonly), right?

[xbolva00]

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

1372

According to BuildLibCalls, yes, right.

[fhahn]

Thanks for the latest updates!

We already have tests with other library calls in llvm/test/Transforms/DeadStoreElimination/libcalls.ll. It might good to move the tests from llvm/test/Transforms/DeadStoreElimination/memset-and-strncpy.ll to that file and recommit the changes.

Are you planning on also adding support for other *n* variants of library calls?

[fhahn]

I think the patch also needs a rebase after some recent changes on main.

[fwolff]

@fhahn Fixed and rebased, thanks for the review! (And I'll need someone to commit this for me. You can use name and email as in commit 6259016361345e09f0607ef4e037e00bcbe4bd40 for attribution. Thanks!)

Are you planning on also adding support for other *n* variants of library calls?

Which ones are you thinking of in particular? strncpy is the "easy" one because it always writes exactly n bytes, but I can have a look at some others as well.

[fhahn]

In D114035#3142607, @fwolff wrote:

@fhahn Fixed and rebased, thanks for the review! (And I'll need someone to commit this for me. You can use name and email as in commit 6259016361345e09f0607ef4e037e00bcbe4bd40 for attribution. Thanks!)

Are you planning on also adding support for other *n* variants of library calls?

Which ones are you thinking of in particular? strncpy is the "easy" one because it always writes exactly n bytes, but I can have a look at some others as well.

I committed the tests separately in ffe1741b5ccab07cbf45fe99033e4119688eb5a5. Could you rebase the patch on top of that change?

[fhahn]

LGTM, thanks! I'll land the change shortly.

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

 /// If the value of this instruction and the memory it writes to is unused, may
 /// we delete this instruction?
 static bool isRemovable(Instruction *I) {
   // Don't remove volatile/atomic stores.
   if (StoreInst *SI = dyn_cast<StoreInst>(I))
     return SI->isUnordered();
 
   if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) {
     switch (II->getIntrinsicID()) {
     default: llvm_unreachable("doesn't pass 'hasAnalyzableMemoryWrite' predicate");
     case Intrinsic::lifetime_end:
       // Never remove dead lifetime_end's, e.g. because it is followed by a
       // free.
       return false;
     case Intrinsic::init_trampoline:
       // Always safe to remove init_trampoline.
       return true;
     case Intrinsic::memset:
     case Intrinsic::memmove:
     case Intrinsic::memcpy:
     case Intrinsic::memcpy_inline:
       // Don't remove volatile memory intrinsics.
       return !cast<MemIntrinsic>(II)->isVolatile();
     case Intrinsic::memcpy_element_unordered_atomic:
if (auto *CB = dyn_cast<CallBase>(I)) {
       // If the functions may write to memory we do not know about, bail out.
       if (!CB->onlyAccessesArgMemory() &&
           !CB->onlyAccessesInaccessibleMemOrArgMem())
         return None;
 
       LibFunc LF;
       if (TLI.getLibFunc(*CB, LF) && TLI.has(LF)) {
         switch (LF) {
-        case LibFunc_strcpy:
         case LibFunc_strncpy:
+          if (const auto *Len = dyn_cast<ConstantInt>(CB->getArgOperand(2)))
+            return MemoryLocation(CB->getArgOperand(0),
+                                  LocationSize::precise(Len->getZExtValue()),
+                                  CB->getAAMetadata());
+          LLVM_FALLTHROUGH;
+        case LibFunc_strcpy:
         case LibFunc_strcat:
         case LibFunc_strncat:
           return {MemoryLocation::getAfter(CB->getArgOperand(0))};
         default:
           break;
         }
       }
       switch (CB->getIntrinsicID()) {
for (;; Current = cast<MemoryDef>(Current)->getDefiningAccess()) {
 
       // If Current is known to be on path that reads DefLoc or is a read
       // clobber, bail out, as the path is not profitable. We skip this check
       // for intrinsic calls, because the code knows how to handle memcpy
       // intrinsics.
       if (!isa<IntrinsicInst>(CurrentI) && isReadClobber(KillingLoc, CurrentI))
         return None;
 
       // Quick check if there are direct uses that are read-clobbers.
       if (any_of(Current->uses(), [this, &KillingLoc, StartAccess](Use &U) {
             if (auto *UseOrDef = dyn_cast<MemoryUseOrDef>(U.getUser()))
               return !MSSA.dominates(StartAccess, UseOrDef) &&
                      isReadClobber(KillingLoc, UseOrDef->getMemoryInst());
             return false;
           })) {
         LLVM_DEBUG(dbgs() << "   ...  found a read clobber\n");
         return None;
       }
 
       // If Current cannot be analyzed or is not removable, check the next

llvm/test/Transforms/DeadStoreElimination/libcalls.ll

 
 declare void @llvm.memset.p0i8.i64(i8* nocapture, i8, i64, i1) nounwind
 
 ; Test that strncpy/memset overwriting each other is optimized out
 
 ; strncpy -> memset, full overwrite
 define void @dse_strncpy_test1(i8* noalias %out, i8* noalias %in) {
 ; CHECK-LABEL: @dse_strncpy_test1(
-; CHECK-NEXT:    [[CALL:%.*]] = tail call i8* @strncpy(i8* [[OUT:%.*]], i8* [[IN:%.*]], i64 100)
-; CHECK-NEXT:    tail call void @llvm.memset.p0i8.i64(i8* [[OUT]], i8 42, i64 100, i1 false)
+; CHECK-NEXT:    tail call void @llvm.memset.p0i8.i64(i8* [[OUT:%.*]], i8 42, i64 100, i1 false)
 ; CHECK-NEXT:    ret void
 ;
   %call = tail call i8* @strncpy(i8* %out, i8* %in, i64 100)
   tail call void @llvm.memset.p0i8.i64(i8* %out, i8 42, i64 100, i1 false)
   ret void
 }
 
 ; strncpy -> memset, partial overwrite
;
   tail call void @llvm.memset.p0i8.i64(i8* %out2, i8 42, i64 100, i1 false)
   ret void
 }
 
 
 ; memset -> strncpy, full overwrite
 define void @dse_strncpy_test4(i8* noalias %out, i8* noalias %in) {
 ; CHECK-LABEL: @dse_strncpy_test4(
-; CHECK-NEXT:    tail call void @llvm.memset.p0i8.i64(i8* [[OUT:%.*]], i8 42, i64 100, i1 false)
-; CHECK-NEXT:    [[CALL:%.*]] = tail call i8* @strncpy(i8* [[OUT]], i8* [[IN:%.*]], i64 100)
+; CHECK-NEXT:    [[CALL:%.*]] = tail call i8* @strncpy(i8* [[OUT:%.*]], i8* [[IN:%.*]], i64 100)
 ; CHECK-NEXT:    ret void
 ;
   tail call void @llvm.memset.p0i8.i64(i8* %out, i8 42, i64 100, i1 false)
   %call = tail call i8* @strncpy(i8* %out, i8* %in, i64 100)
   ret void
 }
 
 ; memset -> strncpy, partial overwrite
 define void @dse_strncpy_test5(i8* noalias %out, i8* noalias %in) {
 ; CHECK-LABEL: @dse_strncpy_test5(
-; CHECK-NEXT:    tail call void @llvm.memset.p0i8.i64(i8* [[OUT:%.*]], i8 42, i64 100, i1 false)
+; CHECK-NEXT:    [[TMP1:%.*]] = getelementptr inbounds i8, i8* [[OUT:%.*]], i64 99
+; CHECK-NEXT:    tail call void @llvm.memset.p0i8.i64(i8* align 1 [[TMP1]], i8 42, i64 1, i1 false)
 ; CHECK-NEXT:    [[CALL:%.*]] = tail call i8* @strncpy(i8* [[OUT]], i8* [[IN:%.*]], i64 99)
 ; CHECK-NEXT:    ret void
 ;
   tail call void @llvm.memset.p0i8.i64(i8* %out, i8 42, i64 100, i1 false)
   %call = tail call i8* @strncpy(i8* %out, i8* %in, i64 99)
   ret void
 }