[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/gep-custom-dl.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -instcombine -S | FileCheck %s
 
 target datalayout = "e-m:m-p:40:64:64:32-i32:32-i16:16-i8:8-n32"
 
 %struct.B = type { double }
 %struct.A = type { %struct.B, i32, i32 }
 %struct.C = type { [7 x i8] }
 
 
-@Global = constant [10 x i8] c"helloworld"
-
+@Global = external global [10 x i8]
 
 ; Test that two array indexing geps fold
 define i32* @test1(i32* %I) {
 ; CHECK-LABEL: @test1(
 ; CHECK-NEXT:    [[B:%.*]] = getelementptr i32, i32* [[I:%.*]], i32 21
 ; CHECK-NEXT:    ret i32* [[B]]
 ;
   %A = getelementptr i32, i32* %I, i8 17

test/Transforms/InstCombine/getelementptr.ll

 ; RUN: opt < %s -instcombine -S | FileCheck %s
 
 target datalayout = "e-p:64:64-p1:16:16-p2:32:32:32-p3:64:64:64"
 
 %intstruct = type { i32 }
 %pair = type { i32, i32 }
 %struct.B = type { double }
 %struct.A = type { %struct.B, i32, i32 }
 %struct.C = type { [7 x i8] }
 
 
-@Global = constant [10 x i8] c"helloworld"
-@Global_as1 = addrspace(1) constant [10 x i8] c"helloworld"
+@Global = external global [10 x i8]
+@Global_as1 = external addrspace(1) global [10 x i8]
 
 ; Test noop elimination
 define i32* @test1(i32* %I) {
         %A = getelementptr i32, i32* %I, i64 0
         ret i32* %A
 ; CHECK-LABEL: @test1(
 ; CHECK: ret i32* %I
 }

test/Transforms/InstCombine/memcpy.ll

 ; CHECK-LABEL: @test3(
 ; CHECK-NEXT:    tail call void @llvm.memcpy.p0i8.p0i8.i64(i8* align 4 %d, i8* align 4 %s, i64 17179869184, i1 false)
 ; CHECK-NEXT:    ret void
 ;
   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 i8
+
+define void @memmove_to_constant(i8* %src) {
+  call void @llvm.memcpy.p0i8.p0i8.i32(i8* @UnknownConstant, i8* %src, i32 1, i1 false)
+  ret void
+}

test/Transforms/InstCombine/memmove.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; This test makes sure that memmove instructions are properly eliminated.
 ;
 ; RUN: opt < %s -instcombine -S | FileCheck %s
 
 @S = internal constant [33 x i8] c"panic: restorelist inconsistency\00"    ; <[33 x i8]*> [#uses=1]
 @h = constant [2 x i8] c"h\00"    ; <[2 x i8]*> [#uses=1]
 @hel = constant [4 x i8] c"hel\00"    ; <[4 x i8]*> [#uses=1]
 @hello_u = constant [8 x i8] c"hello_u\00"    ; <[8 x i8]*> [#uses=1]
 
 define void @test1(i8* %A, i8* %B, i32 %N) {
-  ;; CHECK-LABEL: test1
-  ;; CHECK-NEXT: ret void
+; CHECK-LABEL: @test1(
+; CHECK-NEXT:    ret void
+;
   call void @llvm.memmove.p0i8.p0i8.i32(i8* %A, i8* %B, i32 0, i1 false)
   ret void
 }
 
 define void @test2(i8* %A, i32 %N) {
   ;; dest can't alias source since we can't write to source!
-  ;; CHECK-LABEL: test2
-  ;; CHECK-NEXT: call void @llvm.memcpy.p0i8.p0i8.i32(i8* align 1 %A, i8* align 16 getelementptr inbounds ([33 x i8], [33 x i8]* @S, i{{32|64}} 0, i{{32|64}} 0), i32 %N, i1 false)
-  ;; CHECK-NEXT: ret void
+; CHECK-LABEL: @test2(
+; CHECK-NEXT:    call void @llvm.memcpy.p0i8.p0i8.i32(i8* align 1 [[A:%.*]], i8* align 16 getelementptr inbounds ([33 x i8], [33 x i8]* @S, i64 0, i64 0), i32 [[N:%.*]], i1 false)
+; CHECK-NEXT:    ret void
+;
   call void @llvm.memmove.p0i8.p0i8.i32(i8* %A, i8* getelementptr inbounds ([33 x i8], [33 x i8]* @S, i32 0, i32 0), i32 %N, i1 false)
   ret void
 }
 
 define i32 @test3([1024 x i8]* %target) { ; arg: [1024 x i8]*> [#uses=1]
-  ;; CHECK-LABEL: test3
-  ;; CHECK-NEXT: [[P1:%[^\s]+]] = bitcast [1024 x i8]* %target to i16*
-  ;; CHECK-NEXT: store i16 104, i16* [[P1]], align 2
-  ;; CHECK-NEXT: [[P2:%[^\s]+]] = bitcast [1024 x i8]* %target to i32*
-  ;; CHECK-NEXT: store i32 7103848, i32* [[P2]], align 4
-  ;; CHECK-NEXT: [[P3:%[^\s]+]] = bitcast [1024 x i8]* %target to i64*
-  ;; CHECK-NEXT: store i64 33037504440198504, i64* [[P3]], align 8
-  ;; CHECK-NEXT: ret i32 0
+; CHECK-LABEL: @test3(
+; CHECK-NEXT:    [[TMP1:%.*]] = bitcast [1024 x i8]* [[TARGET:%.*]] to i16*
+; CHECK-NEXT:    store i16 104, i16* [[TMP1]], align 2
+; CHECK-NEXT:    [[TMP2:%.*]] = bitcast [1024 x i8]* [[TARGET]] to i32*
+; CHECK-NEXT:    store i32 7103848, i32* [[TMP2]], align 4
+; CHECK-NEXT:    [[TMP3:%.*]] = bitcast [1024 x i8]* [[TARGET]] to i64*
+; CHECK-NEXT:    store i64 33037504440198504, i64* [[TMP3]], align 8
+; CHECK-NEXT:    ret i32 0
+;
   %h_p = getelementptr [2 x i8], [2 x i8]* @h, i32 0, i32 0    ; <i8*> [#uses=1]
   %hel_p = getelementptr [4 x i8], [4 x i8]* @hel, i32 0, i32 0    ; <i8*> [#uses=1]
   %hello_u_p = getelementptr [8 x i8], [8 x i8]* @hello_u, i32 0, i32 0    ; <i8*> [#uses=1]
   %target_p = getelementptr [1024 x i8], [1024 x i8]* %target, i32 0, i32 0    ; <i8*> [#uses=3]
   call void @llvm.memmove.p0i8.p0i8.i32(i8* align 2 %target_p, i8* align 2 %h_p, i32 2, i1 false)
   call void @llvm.memmove.p0i8.p0i8.i32(i8* align 4 %target_p, i8* align 4 %hel_p, i32 4, i1 false)
   call void @llvm.memmove.p0i8.p0i8.i32(i8* align 8 %target_p, i8* align 8 %hello_u_p, i32 8, i1 false)
   ret i32 0
 }
 
 ; PR2370
 define void @test4(i8* %a) {
-  ;; CHECK-LABEL: test4
-  ;; CHECK-NEXT: ret void
+; CHECK-LABEL: @test4(
+; CHECK-NEXT:    ret void
+;
   tail call void @llvm.memmove.p0i8.p0i8.i32(i8* %a, i8* %a, i32 100, i1 false)
   ret void
 }
 
+@UnknownConstant = external constant i8
+
+define void @memmove_to_constant(i8* %src) {
+; CHECK-LABEL: @memmove_to_constant(
+; CHECK-NEXT:    ret void
+;
+  call void @llvm.memmove.p0i8.p0i8.i32(i8* @UnknownConstant, i8* %src, i32 1, 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

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -instcombine -S | FileCheck %s
 
 define i32 @test([1024 x i8]* %target) {
-  ;; CHECK-LABEL: test
-  ;; CHECK-NEXT: [[P1:%[^\s]+]] = getelementptr inbounds [1024 x i8], [1024 x i8]* %target, i64 0, i64 0
-  ;; CHECK-NEXT: store i8 1, i8* [[P1]], align 1
-  ;; CHECK-NEXT: [[P2:%[^\s]+]] = bitcast [1024 x i8]* %target to i16*
-  ;; CHECK-NEXT: store i16 257, i16* [[P2]], align 2
-  ;; CHECK-NEXT: [[P3:%[^\s]+]] = bitcast [1024 x i8]* %target to i32*
-  ;; CHECK-NEXT: store i32 16843009, i32* [[P3]], align 4
-  ;; CHECK-NEXT: [[P4:%[^\s]+]] = bitcast [1024 x i8]* %target to i64*
-  ;; CHECK-NEXT: store i64 72340172838076673, i64* [[P4]], align 8
-  ;; CHECK-NEXT: ret i32 0
+; CHECK-LABEL: @test(
+; CHECK-NEXT:    [[TMP1:%.*]] = getelementptr inbounds [1024 x i8], [1024 x i8]* [[TARGET:%.*]], i64 0, i64 0
+; CHECK-NEXT:    store i8 1, i8* [[TMP1]], align 1
+; CHECK-NEXT:    [[TMP2:%.*]] = bitcast [1024 x i8]* [[TARGET]] to i16*
+; CHECK-NEXT:    store i16 257, i16* [[TMP2]], align 2
+; CHECK-NEXT:    [[TMP3:%.*]] = bitcast [1024 x i8]* [[TARGET]] to i32*
+; CHECK-NEXT:    store i32 16843009, i32* [[TMP3]], align 4
+; CHECK-NEXT:    [[TMP4:%.*]] = bitcast [1024 x i8]* [[TARGET]] to i64*
+; CHECK-NEXT:    store i64 72340172838076673, i64* [[TMP4]], align 8
+; CHECK-NEXT:    ret i32 0
+;
   %target_p = getelementptr [1024 x i8], [1024 x i8]* %target, i32 0, i32 0
   call void @llvm.memset.p0i8.i32(i8* %target_p, i8 1, i32 0, i1 false)
   call void @llvm.memset.p0i8.i32(i8* %target_p, i8 1, i32 1, i1 false)
   call void @llvm.memset.p0i8.i32(i8* align 2 %target_p, i8 1, i32 2, i1 false)
   call void @llvm.memset.p0i8.i32(i8* align 4 %target_p, i8 1, i32 4, i1 false)
   call void @llvm.memset.p0i8.i32(i8* align 8 %target_p, i8 1, i32 8, i1 false)
   ret i32 0
 }
 
+@Unknown = external constant i32
+
+define void @memset_to_constant() {
+; CHECK-LABEL: @memset_to_constant(
+; CHECK-NEXT:    ret void
+;
+  %p = bitcast i32* @Unknown to i8*
+  call void @llvm.memset.p0i8.i32(i8* %p, i8 0, i32 5, i1 false)
+  ret void
+}
+
 declare void @llvm.memset.p0i8.i32(i8* nocapture writeonly, i8, i32, i1) argmemonly nounwind

test/Transforms/InstCombine/store.ll

 ; CHECK-NEXT:    [[V:%.*]] = load atomic volatile i32, i32* [[P:%.*]] seq_cst, align 4
 ; CHECK-NEXT:    ret void
 ;
   %v = load atomic volatile i32, i32* %p seq_cst, align 4
   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:    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}