[DSE] Use precise loc for memset_chk during overwrite checks

[fhahn]

Summary

memset_chk may not write the number of bytes specified by the third
argument, if it is larger than the destination size (specified as 4th
argument).

[efriedma]

A couple thoughts:

1. We need to be careful using the exact memset size. We could end up with an "impossible" memory location: for example, setting 100 bytes of a 50-byte buffer. That's probably okay here? But maybe not in other contexts; we need to be sure we don't treat memset_chk as UB. Maybe worth a comment describing what, exactly, we're modeling.
2. In the case where the bounds check in memset_chk fails, it just aborts the process, and there isn't any synchronization point before it does that. So I'm not sure why it matters if the pointer is visible to other threads. Another thread can't read the contents before the process abort because it would be unsynchronized, and the memory doesn't exist after the process aborts.

[fhahn]

In D115167#3174188, @efriedma wrote:

A couple thoughts:

Thanks for taking a look!

1. We need to be careful using the exact memset size. We could end up with an "impossible" memory location: for example, setting 100 bytes of a 50-byte buffer. That's probably okay here? But maybe not in other contexts; we need to be sure we don't treat memset_chk as UB. Maybe worth a comment describing what, exactly, we're modeling.

I think using an 'impossible' memory location should be fine here, we use the location to remove stores based on the fact that the memset_chk is executed and impossible locations will cause an abort. It's a bit of a shame that after all the work of moving most location reasoning from DSE to MemoryLocation we still need special logic here that doesn't fit into MemoryLocation. But as you said, it is not safe in general.

2. In the case where the bounds check in memset_chk fails, it just aborts the process, and there isn't any synchronization point before it does that. So I'm not sure why it matters if the pointer is visible to other threads. Another thread can't read the contents before the process abort because it would be unsynchronized, and the memory doesn't exist after the process aborts.

It might have been overly conservative on my side. I was thinking about cases where a failing memset_chk aborts the current thread/process but not other threads or processes that may access the same (shared) memory. But if that's not an issue the restriction can be removed.

[efriedma]

In D115167#3176652, @fhahn wrote:

It might have been overly conservative on my side. I was thinking about cases where a failing memset_chk aborts the current thread/process but not other threads or processes that may access the same (shared) memory. But if that's not an issue the restriction can be removed.

memset_chk aborts the whole process. Throwing an exception on an out-of-bounds access is a popular model in other contexts, but memset_chk is not defined that way. It's meant purely as a hardening measure.

memset_chk should not be used on memory shared with other processes. Accesses to such memory should be volatile or atomic; otherwise, weird stuff can happen for a variety of reasons...

[fhahn]

In D115167#3177439, @efriedma wrote:

In D115167#3176652, @fhahn wrote:

It might have been overly conservative on my side. I was thinking about cases where a failing memset_chk aborts the current thread/process but not other threads or processes that may access the same (shared) memory. But if that's not an issue the restriction can be removed.

memset_chk aborts the whole process. Throwing an exception on an out-of-bounds access is a popular model in other contexts, but memset_chk is not defined that way. It's meant purely as a hardening measure.

memset_chk should not be used on memory shared with other processes. Accesses to such memory should be volatile or atomic; otherwise, weird stuff can happen for a variety of reasons...

Sounds good, thanks! I remove the local-object restriction and added a comment explaining why using the precise bound is fine here.

[nikic]

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

1025 ↗

(On Diff #392782)

No longer necessary.

1041 ↗

(On Diff #392782)

This hold for AA results in general though (they are only valid under the assumption of execution), so maybe it's okay to return a precise result directly in MemoryLocation?

[fhahn]

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

1041 ↗

(On Diff #392782)

Hm, I am not sure. For AA it should be fine for the same reasons it's fine for DSE, but I am not sure about some of the other users? Grepping surfaces a couple of additional ones.

[nikic]

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

1041 ↗

(On Diff #392782)

Looking through other MemoryLocation::getForDest() users, all of them seem to be limited to handling intrinsics, not libcalls, so I don't expect issues with existing callers.

[fhahn]

Move logic to MemoryLocation, add comment about correctness limited to contexts where the call executes.

[fhahn]

llvm/lib/Analysis/MemoryLocation.cpp

256

I now moved the code, but I'm not sure how to adjust/frame the comment here.

[nikic]

llvm/lib/Analysis/MemoryLocation.cpp

256

memset_chk will either write exactly Len bytes or abort the process. If memset_chk aborts, then the partial write cannot be observed. For analysis purposes we can assume that exactly Len bytes are written.

[nikic]

llvm/lib/Analysis/MemoryLocation.cpp

256

Okay, I'm having second thoughts here, maybe we should go back to your previous version.

The main danger is that something decides that because the precise location is larger than the underlying object, the access must be UB. And indeed, this is exactly what we're doing in https://github.com/llvm/llvm-project/blob/15c8b8ad85c196df25aa3c22bca3d8458f86525a/llvm/lib/Analysis/BasicAliasAnalysis.cpp#L1604-L1613. My earlier statement that this would be fine for alias analysis was wrong.

Though I think that this may be problematic for DSE for the same reason. We pass the location to AA and it could determine that it thus doesn't alias. The saving grace here is probably that https://github.com/llvm/llvm-project/blob/3d595eccc7d5b20d9f202492bf48394ac7c078c6/llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp#L926-L935 only uses the NoAlias result if the underlying objects differ, but one could probably still get an incorrect NoAlias result here if the underlying object is hidden in a way that BasicAA understands but DSE does not (e.g. through a phi or select).

[fhahn]

Finally had some time to look at this again. I updated the patch to move the logic back to DSE and just use it for the sizes used to determine whether an object is overwritten. That should avoid any issues with AA queries.

[fhahn]

llvm/lib/Analysis/MemoryLocation.cpp

256

Great point, thanks for checking and sorry for the long delay.

Finally had some time to look at this again. I updated the patch to move the logic back to DSE and just use it for the sizes used to determine whether an object is overwritten. That should avoid any issues with AA queries.

[asbirlea]

Considering the previous reviewer comments, this lgtm.

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

886 ↗

(On Diff #477605)

nit: remove 'during'

llvm/test/Transforms/DeadStoreElimination/libcalls.ll

481

nit: rename function without 'cannot'

[fhahn]

Thanks, rebase after test update, I am planning to land this soon.

[fhahn]

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

886 ↗

(On Diff #477605)

Thanks, removed in the committed version!

llvm/test/Transforms/DeadStoreElimination/libcalls.ll

481

I updated the tests separately, thanks!

llvm/include/llvm/Analysis/MemoryLocation.h

public:
   static MemoryLocation getForSource(const AtomicMemTransferInst *MTI);
   static MemoryLocation getForSource(const AnyMemTransferInst *MTI);
 
   /// Return a location representing the destination of a memory set or
   /// transfer.
   static MemoryLocation getForDest(const MemIntrinsic *MI);
   static MemoryLocation getForDest(const AtomicMemIntrinsic *MI);
   static MemoryLocation getForDest(const AnyMemIntrinsic *MI);
+  /// The result returned is only correct in contexts where \p CI is guaranteed
+  /// to execute.
   static Optional<MemoryLocation> getForDest(const CallBase *CI,
                                              const TargetLibraryInfo &TLI);
 
   /// Return a location representing a particular argument of a call.
+  /// The result returned is only correct in contexts where \p Call is
+  /// guaranteed to execute.
   static MemoryLocation getForArgument(const CallBase *Call, unsigned ArgIdx,
                                        const TargetLibraryInfo *TLI);
   static MemoryLocation getForArgument(const CallBase *Call, unsigned ArgIdx,
                                        const TargetLibraryInfo &TLI) {
     return getForArgument(Call, ArgIdx, &TLI);
   }
 
   /// Return a location that may access any location after Ptr, while remaining

llvm/lib/Analysis/MemoryLocation.cpp

if (const IntrinsicInst *II = dyn_cast<IntrinsicInst>(CB)) {
     case Intrinsic::masked_store:
       return MemoryLocation::getForArgument(CB, 1, TLI);
     }
   }
 
   LibFunc LF;
   if (TLI.getLibFunc(*CB, LF) && TLI.has(LF)) {
     switch (LF) {
+    case LibFunc_memset_chk:
     case LibFunc_strncpy:
     case LibFunc_strcpy:
     case LibFunc_strcat:
     case LibFunc_strncat:
       return getForArgument(CB, 0, &TLI);
     default:
       break;
     }
if (TLI && TLI->getLibFunc(*Call, F) && TLI->has(F)) {
     case LibFunc_strncat:
       assert((ArgIdx == 0 || ArgIdx == 1) && "Invalid argument index for str function");
       return MemoryLocation::getAfter(Arg, AATags);
 
     case LibFunc_memset_chk: {
       assert(ArgIdx == 0 && "Invalid argument index for memset_chk");
       LocationSize Size = LocationSize::afterPointer();
       if (const auto *Len = dyn_cast<ConstantInt>(Call->getArgOperand(2))) {
         // memset_chk writes at most Len bytes. It may write less, if Len
         // exceeds the specified max size and aborts.
-        Size = LocationSize::upperBound(Len->getZExtValue());
+        Size = LocationSize::precise(Len->getZExtValue());
       }
       return MemoryLocation(Arg, Size, AATags);
     }
     case LibFunc_strncpy: {
       assert((ArgIdx == 0 || ArgIdx == 1) &&
              "Invalid argument index for strncpy");
       LocationSize Size = LocationSize::afterPointer();
       if (const auto *Len = dyn_cast<ConstantInt>(Call->getArgOperand(2))) {

llvm/test/Transforms/DeadStoreElimination/libcalls.ll

;
   ret void
 }
 
 declare i8* @__memset_chk(i8* writeonly, i32, i64, i64) argmemonly
 
 ; strncpy -> __memset_chk, full overwrite
 define void @dse_strncpy_memset_chk_test1(i8* noalias %out, i8* noalias %in, i64 %n) {
 ; CHECK-LABEL: @dse_strncpy_memset_chk_test1(
-; CHECK-NEXT:    [[CALL:%.*]] = tail call i8* @strncpy(i8* [[OUT:%.*]], i8* [[IN:%.*]], i64 100)
-; CHECK-NEXT:    [[CALL_2:%.*]] = tail call i8* @__memset_chk(i8* [[OUT]], i32 42, i64 100, i64 [[N:%.*]])
+; CHECK-NEXT:    [[CALL_2:%.*]] = tail call i8* @__memset_chk(i8* [[OUT:%.*]], i32 42, i64 100, i64 [[N:%.*]])
 ; CHECK-NEXT:    ret void
 ;
   %call = tail call i8* @strncpy(i8* %out, i8* %in, i64 100)
   %call.2 = tail call i8* @__memset_chk(i8* %out, i32 42, i64 100, i64 %n)
   ret void
 }
 
 declare void @use(i8*)
 
 define void @dse_memset_chk_cannot_eliminates_store(i8* %out, i64 %n) {
 ; CHECK-LABEL: @dse_memset_chk_cannot_eliminates_store(
-; CHECK-NEXT:    store i8 10, i8* [[OUT:%.*]], align 1
-; CHECK-NEXT:    [[CALL_2:%.*]] = tail call i8* @__memset_chk(i8* [[OUT]], i32 42, i64 100, i64 [[N:%.*]])
+; CHECK-NEXT:    [[CALL_2:%.*]] = tail call i8* @__memset_chk(i8* [[OUT:%.*]], i32 42, i64 100, i64 [[N:%.*]])
 ; CHECK-NEXT:    ret void
 ;
   store i8 10, i8* %out
   %call.2 = tail call i8* @__memset_chk(i8* %out, i32 42, i64 100, i64 %n)
   ret void
 }
 
 define void @dse_memset_chk_eliminates_store_local_object_escapes_after(i64 %n) {
 ; CHECK-LABEL: @dse_memset_chk_eliminates_store_local_object_escapes_after(
 ; CHECK-NEXT:    [[A:%.*]] = alloca [200 x i8], align 1
 ; CHECK-NEXT:    [[OUT:%.*]] = bitcast [200 x i8]* [[A]] to i8*
-; CHECK-NEXT:    store i8 10, i8* [[OUT]], align 1
 ; CHECK-NEXT:    [[OUT_100:%.*]] = getelementptr i8, i8* [[OUT]], i64 100
 ; CHECK-NEXT:    store i8 10, i8* [[OUT_100]], align 1
 ; CHECK-NEXT:    [[CALL_2:%.*]] = tail call i8* @__memset_chk(i8* [[OUT]], i32 42, i64 100, i64 [[N:%.*]])
 ; CHECK-NEXT:    call void @use(i8* [[OUT]])
 ; CHECK-NEXT:    ret void
 ;
   %a = alloca [200 x i8]
   %out = bitcast [200 x i8]* %a to i8*
   store i8 10, i8* %out
   %out.100 = getelementptr i8, i8* %out, i64 100
   store i8 10, i8* %out.100
   %call.2 = tail call i8* @__memset_chk(i8* %out, i32 42, i64 100, i64 %n)
   call void @use(i8* %out)
   ret void
 }
 
 define void @dse_memset_chk_eliminates_store_local_object_escapes_before(i64 %n) {
 ; CHECK-LABEL: @dse_memset_chk_eliminates_store_local_object_escapes_before(
 ; CHECK-NEXT:    [[A:%.*]] = alloca [200 x i8], align 1
 ; CHECK-NEXT:    [[OUT:%.*]] = bitcast [200 x i8]* [[A]] to i8*
 ; CHECK-NEXT:    call void @use(i8* [[OUT]])
-; CHECK-NEXT:    store i8 10, i8* [[OUT]], align 1
 ; CHECK-NEXT:    [[OUT_100:%.*]] = getelementptr i8, i8* [[OUT]], i64 100
 ; CHECK-NEXT:    store i8 0, i8* [[OUT_100]], align 1
 ; CHECK-NEXT:    [[CALL_2:%.*]] = tail call i8* @__memset_chk(i8* [[OUT]], i32 42, i64 100, i64 [[N:%.*]])
 ; CHECK-NEXT:    call void @use(i8* [[OUT]])
 ; CHECK-NEXT:    ret void
 ;
   %a = alloca [200 x i8]
   %out = bitcast [200 x i8]* %a to i8*