[InstCombine] Eliminate stores to constant memory

[reames]

Summary

If we have a store to a piece of memory which is known constant, then we know the store must be storing back the same value. As a result, the store (or memset, or memmove) must either be down a dead path, or a noop. In either case, it is valid to simply remove the store.

The motivating case for this involves a memmove to a buffer which is constant down a path which is dynamically dead.

Note that I'm choosing to implement the less aggressive of two possible semantics here. We could simply say that the store *is undefined*, and prune the path. That seemed a bit too likely to break real code in subtle ways, so I decide to just remove the store itself.

[reames]

Rebase on top of test changes

[nicholas]

The two statements:

We could simply say that the store *is undefined*, and prune the path.

and

The motivating case for this involves a memmove to a buffer which is constant down a path which is dynamically dead.

conspire to make me think that pruning the whole path really is the right thing to do. This might be the only hint the compiler has that the path is dead code.

Why do you think a store through constant would break subtly? For most users I'd expect a store to a constant to correspond with a write to a read-only page causing a loud crash.

[reames]

In D60659#1465605, @nicholas wrote:

Why do you think a store through constant would break subtly? For most users I'd expect a store to a constant to correspond with a write to a read-only page causing a loud crash.

I assume you mean before this patch right? If so, then yes and no. It's possible the constant location is in a readonly page, but I have a lot of downstream constant locations which are intermixed with writeable data. I'm sure other frontends might have the same. Your reasoning may hold specifically for global constants though.

[nicholas]

In D60659#1466869, @reames wrote:

In D60659#1465605, @nicholas wrote:

Why do you think a store through constant would break subtly? For most users I'd expect a store to a constant to correspond with a write to a read-only page causing a loud crash.

I assume you mean before this patch right? If so, then yes and no. It's possible the constant location is in a readonly page, but I have a lot of downstream constant locations which are intermixed with writeable data. I'm sure other frontends might have the same. Your reasoning may hold specifically for global constants though.

I was just surprised at the claim that this might be a common unnoticed bug. Putting constants in read only memory is a technique decades older than UBSan and I regard anything the latest UBSan can catch is something that we're safe to optimize on.

I don't think this patch is wrong per se, I'm just quite confident it's safe to make it stronger. If you don't agree, you can leave the stronger optimization for another author in the future. Either way, separate patches would make it easier to find the cause of a regression.

[reames]

ping?

[apilipenko]

LGTM. I agree that we can leave the stronger variant for the future.

[liutianle]

hi reames, I have a question in the view of customer. If he writes deliberately to a read-only memory to expect trigger a seg fault, or if he wants to write to a memory which he does not realize it is read only. Should compiler tell him the writing is invalid, rather than treat it as a nop silently?

[reames]

In D60659#1483597, @liutianle wrote:

hi reames, I have a question in the view of customer. If he writes deliberately to a read-only memory to expect trigger a seg fault, or if he wants to write to a memory which he does not realize it is read only. Should compiler tell him the writing is invalid, rather than treat it as a nop silently?

See the discussion in the commit thread about this being undefined behaviour and possibilities for sanitization.

lib/Transforms/InstCombine/InstCombineCalls.cpp

Instruction *InstCombiner::SimplifyAnyMemTransfer(AnyMemTransferInst *MI) {
 
   unsigned SrcAlign = getKnownAlignment(MI->getRawSource(), DL, MI, &AC, &DT);
   unsigned CopySrcAlign = MI->getSourceAlignment();
   if (CopySrcAlign < SrcAlign) {
     MI->setSourceAlignment(SrcAlign);
     return MI;
   }
 
+  // If we have a store to a location which is known constant, we can conclude
+  // that the store must be storing the constant value (else the memory
+  // wouldn't be constant), and this must be a noop.
+  if (AA->pointsToConstantMemory(MI->getDest())) {
+    // Set the size of the copy to 0, it will be deleted on the next iteration.
+    MI->setLength(Constant::getNullValue(MI->getLength()->getType()));
+    return MI;
+  }
+
   // If MemCpyInst length is 1/2/4/8 bytes then replace memcpy with
   // load/store.
   ConstantInt *MemOpLength = dyn_cast<ConstantInt>(MI->getLength());
   if (!MemOpLength) return nullptr;
 
   // Source and destination pointer types are always "i8*" for intrinsic.  See
   // if the size is something we can handle with a single primitive load/store.
   // A single load+store correctly handles overlapping memory in the memmove

 
 Instruction *InstCombiner::SimplifyAnyMemSet(AnyMemSetInst *MI) {
   unsigned Alignment = getKnownAlignment(MI->getDest(), DL, MI, &AC, &DT);
   if (MI->getDestAlignment() < Alignment) {
     MI->setDestAlignment(Alignment);
     return MI;
   }
 
+  // If we have a store to a location which is known constant, we can conclude
+  // that the store must be storing the constant value (else the memory
+  // wouldn't be constant), and this must be a noop.
+  if (AA->pointsToConstantMemory(MI->getDest())) {
+    // Set the size of the copy to 0, it will be deleted on the next iteration.
+    MI->setLength(Constant::getNullValue(MI->getLength()->getType()));
+    return MI;
+  }
+
   // Extract the length and alignment and fill if they are constant.
   ConstantInt *LenC = dyn_cast<ConstantInt>(MI->getLength());
   ConstantInt *FillC = dyn_cast<ConstantInt>(MI->getValue());
   if (!LenC || !FillC || !FillC->getType()->isIntegerTy(8))
     return nullptr;
   uint64_t Len = LenC->getLimitedValue();
   Alignment = MI->getDestAlignment();
   assert(Len && "0-sized memory setting should be removed already.");

lib/Transforms/InstCombine/InstCombineLoadStoreAlloca.cpp

if (Ptr->hasOneUse()) {
     if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(Ptr)) {
       if (isa<AllocaInst>(GEP->getOperand(0))) {
         if (GEP->getOperand(0)->hasOneUse())
           return eraseInstFromFunction(SI);
       }
     }
   }
 
+  // If we have a store to a location which is known constant, we can conclude
+  // that the store must be storing the constant value (else the memory
+  // wouldn't be constant), and this must be a noop.
+  if (AA->pointsToConstantMemory(Ptr))
+    return eraseInstFromFunction(SI);
+
   // Do really simple DSE, to catch cases where there are several consecutive
   // stores to the same location, separated by a few arithmetic operations. This
   // situation often occurs with bitfield accesses.
   BasicBlock::iterator BBI(SI);
   for (unsigned ScanInsts = 6; BBI != SI.getParent()->begin() && ScanInsts;
        --ScanInsts) {
     --BBI;
     // Don't count debug info directives, lest they affect codegen,

test/Transforms/InstCombine/memcpy.ll

;
   tail call void @llvm.memcpy.p0i8.p0i8.i64(i8* align 4 %d, i8* align 4 %s, i64 17179869184, i1 false)
   ret void
 }
 
 @UnknownConstant = external constant i128
 
 define void @memcpy_to_constant(i8* %src) {
 ; CHECK-LABEL: @memcpy_to_constant(
-; CHECK-NEXT:    call void @llvm.memcpy.p0i8.p0i8.i32(i8* align 4 bitcast (i128* @UnknownConstant to i8*), i8* align 1 [[SRC:%.*]], i32 16, i1 false)
 ; CHECK-NEXT:    ret void
 ;
   %dest = bitcast i128* @UnknownConstant to i8*
   call void @llvm.memcpy.p0i8.p0i8.i32(i8* %dest, i8* %src, i32 16, i1 false)
   ret void
 }

test/Transforms/InstCombine/memmove.ll

;
   tail call void @llvm.memmove.p0i8.p0i8.i32(i8* %a, i8* %a, i32 100, i1 false)
   ret void
 }
 
 @UnknownConstant = external constant i128
 
 define void @memmove_to_constant(i8* %src) {
 ; CHECK-LABEL: @memmove_to_constant(
-; CHECK-NEXT:    call void @llvm.memmove.p0i8.p0i8.i32(i8* align 4 bitcast (i128* @UnknownConstant to i8*), i8* align 1 [[SRC:%.*]], i32 16, i1 false)
 ; CHECK-NEXT:    ret void
 ;
   %dest = bitcast i128* @UnknownConstant to i8*
   call void @llvm.memmove.p0i8.p0i8.i32(i8* %dest, i8* %src, i32 16, i1 false)
   ret void
 }
 
 
 declare void @llvm.memmove.p0i8.p0i8.i32(i8* nocapture, i8* nocapture readonly, i32, i1) argmemonly nounwind

test/Transforms/InstCombine/memset.ll

;
   call void @llvm.memset.p0i8.i32(i8* align 8 %target_p, i8 1, i32 8, i1 false)
   ret i32 0
 }
 
 @Unknown = external constant i128
 
 define void @memset_to_constant() {
 ; CHECK-LABEL: @memset_to_constant(
-; CHECK-NEXT:    call void @llvm.memset.p0i8.i32(i8* align 4 bitcast (i128* @Unknown to i8*), i8 0, i32 16, i1 false)
 ; CHECK-NEXT:    ret void
 ;
   %p = bitcast i128* @Unknown to i8*
   call void @llvm.memset.p0i8.i32(i8* %p, i8 0, i32 16, i1 false)
   ret void
 }
 
 declare void @llvm.memset.p0i8.i32(i8* nocapture writeonly, i8, i32, i1) argmemonly nounwind

test/Transforms/InstCombine/store.ll

;
   store atomic i32 %v, i32* %p unordered, align 4
   ret void
 }
 
 @Unknown = external constant i32
 
 define void @store_to_constant() {
 ; CHECK-LABEL: @store_to_constant(
-; CHECK-NEXT:    store i32 0, i32* @Unknown, align 4
 ; CHECK-NEXT:    ret void
 ;
   store i32 0, i32* @Unknown
   ret void
 }
 
 !0 = !{!4, !4, i64 0}
 !1 = !{!"omnipotent char", !2}
 !2 = !{!"Simple C/C++ TBAA"}
 !3 = !{!"float", !1}
 !4 = !{!"int", !1}