[DSE] Consider out-of-bound writes in isOverwrite.

[fhahn]

Summary

With cross-bb DSE we need to be more careful when it comes to making
sure the writes are inside the underlying object.

If both writes are in the same basic block, there is no need to check
if the writes are fully inside the underlying object, because the
out-of-bounds access is guaranteed to execute. Note that the case when
the block is exited early due to unwinding is already handled separately
by DSE, by considering the unwinding calls as clobbers. If the writes
are not in the same block, make sure they are inside the underlying object.

Fixes PR48279.

[nikic]

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

500

Why is it guaranteed to execute? Can't you have call @infinite_loop() in between?

[nikic]

llvm/test/Transforms/DeadStoreElimination/MSSA/out-of-bounds-stores.ll

73

I'm having a hard time understanding why anything gets eliminated in this example, regardless of whether this is considered an overwrite or not. There is a codepath (for.body -> for.inc -> for.end) that goes from the first store to the load without passing through the store in for.body.1, so how can it even be relevant for DSE purposes?

[nikic]

llvm/test/Transforms/DeadStoreElimination/MSSA/out-of-bounds-stores.ll

73

Okay, I think I get it now. The problem is that we're using the MemoryLocation from the store in for.body.1 when looking for read clobbers of the store in for.body. And AA (correctly) reports it is NoAlias with the read in for.end. So we have a contract here that the isOverwrite logic in DSE and AA do not produce contradictory results.

[fhahn]

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

500

Hm, there might be potential to improve the wording. I think if any call in between does not return, we only eliminate if the call does not access the location in question, otherwise it would be clobber blocking DSE. If the call does not return, it should be legal to eliminate the earlier store, because the call does not read the location. Otherwise the second store will be executed.

Am I missing something? In that case the code might require an audit now that we have !mustprogress. I think the code was mostly written with !mustprogress assumed.

llvm/test/Transforms/DeadStoreElimination/MSSA/out-of-bounds-stores.ll

73

The problem here is that we start looking upwards with the location of the potential killing definition. So when going upwards we consider store i32 10, i32* %arrayidx, align 4 to be completely overwritten by store i32 20, i32* %arrayidx.1, align 4, which is out-of-bounds. We then check for read clobbers starting at store i32 10, i32* %arrayidx, align 4, we use the location of the killing def, which does not alias the read.

It might be beneficial to use the location of the store to eliminate for the read check for the full overwrite case at least. But I think that would be better as follow up.

[fhahn]

ping :)

[nikic]

llvm/test/Transforms/DeadStoreElimination/MSSA/out-of-bounds-stores.ll

73

It might be beneficial to use the location of the store to eliminate for the read check for the full overwrite case at least. But I think that would be better as follow up.

I think this is what we should be doing. IMHO this patch is only a workaround for the real issue, and we'd just have to revert it again once the proper location is used.

I tried a minimal patch (https://gist.github.com/nikic/83b3207c0581cbbcc7d95a5a20c23d93) but got a test-suite failure in clamscan with that, so would need further investigation.

[fhahn]

llvm/test/Transforms/DeadStoreElimination/MSSA/out-of-bounds-stores.ll

73

I think this is what we should be doing. IMHO this patch is only a workaround for the real issue, and we'd just have to revert it again once the proper location is used.

Hm, I am not sure. The issue is that isOverwrite did not have to handle this case before I think.

I tried a minimal patch (https://gist.github.com/nikic/83b3207c0581cbbcc7d95a5a20c23d93) but got a test-suite failure in clamscan with that, so would need further investigation.

Yeah, I also had a quick look and it seems there are a few more adjustments needed. I won't have time to dig too deep in the next week or 2 unfortunately. I think it would be preferable to fix the issue with this patch and then follow-up later.

[fhahn]

Ping. Any more thoughts about whether this fix is OK to go in until the isOverwrite handling is re-written?

[nikic]

Thinking about this a bit more, here is one more variation of this problem:

; opt -scoped-noalias-aa -dse
define void @test(i1 %c, i8* %p1, i8* %p2) {
  store i8 0, i8* %p1
  br i1 %c, label %if, label %else

if:
  store i8 1, i8* %p1, !noalias !2
  ret void

else:
  load i8, i8* %p2, !alias.scope !2
  store i8 2, i8* %p1
  ret void
}
  
!0 = !{!0}
!1 = !{!1, !0}
!2 = !{!1}

Let's say that %p1 == %p2 if %c == false. I believe the noalias metadata is legal in that case, as the branch claiming noalias will not be executed. However, the current DSE logic will decide that store i8 0 is dead, because the store i8 1 does not alias with the load i8 due to the alias metadata attached to them. However, the metadata used to derive that fact is not actually applicable on this branch (using metadata from the store i8 0 would be legal though, as it is a dominating store).

[fhahn]

In D92045#2458839, @nikic wrote:

Thinking about this a bit more, here is one more variation of this problem:

; opt -scoped-noalias-aa -dse
define void @test(i1 %c, i8* %p1, i8* %p2) {
  store i8 0, i8* %p1
  br i1 %c, label %if, label %else

if:
  store i8 1, i8* %p1, !noalias !2
  ret void

else:
  load i8, i8* %p2, !alias.scope !2
  store i8 2, i8* %p1
  ret void
}
  
!0 = !{!0}
!1 = !{!1, !0}
!2 = !{!1}

Let's say that %p1 == %p2 if %c == false. I believe the noalias metadata is legal in that case, as the branch claiming noalias will not be executed. However, the current DSE logic will decide that store i8 0 is dead, because the store i8 1 does not alias with the load i8 due to the alias metadata attached to them. However, the metadata used to derive that fact is not actually applicable on this branch (using metadata from the store i8 0 would be legal though, as it is a dominating store).

That's a great motivation to change the order sooner, thanks for putting up D93523!

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

isOverwrite(const Instruction *LaterI, const Instruction *EarlierI,
   // overwrites any other store to the same object.
   const Value *UO1 = getUnderlyingObject(P1), *UO2 = getUnderlyingObject(P2);
 
   // If we can't resolve the same pointers to the same object, then we can't
   // analyze them at all.
   if (UO1 != UO2)
     return OW_Unknown;
 
-  // If the "Later" store is to a recognizable object, get its size.
-  uint64_t ObjectSize = getPointerSize(UO2, DL, TLI, F);
-  if (ObjectSize != MemoryLocation::UnknownSize)
-    if (ObjectSize == LaterSize && ObjectSize >= EarlierSize)
-      return OW_Complete;
-
   // Okay, we have stores to two completely different pointers.  Try to
   // decompose the pointer into a "base + constant_offset" form.  If the base
   // pointers are equal, then we can reason about the two stores.
   EarlierOff = 0;
   LaterOff = 0;
   const Value *BP1 = GetPointerBaseWithConstantOffset(P1, EarlierOff, DL);
   const Value *BP2 = GetPointerBaseWithConstantOffset(P2, LaterOff, DL);
 
+  // If the "Later" store is to a recognizable object, get its size.
+  uint64_t ObjectSize = getPointerSize(UO2, DL, TLI, F);
+  if (ObjectSize != MemoryLocation::UnknownSize)
+    if (ObjectSize == LaterSize && ObjectSize >= EarlierSize)
+      // If both writes are in the same basic block, there is no need to check
+      // if the writes are fully inside the underlying object, because the
+      // out-of-bounds access is guaranteed to execute. Note that the case when
+      // the block is exited early due to unwinding is already handled
+      // separately by DSE, by considering the unwinding calls as clobbers. If
+      // the writes are not in the same block, make sure they are inside the
+      // underlying object.
+      if (EarlierI->getParent() == LaterI->getParent() ||
+          (EarlierOff + EarlierSize <= ObjectSize &&
+           LaterOff + LaterSize <= ObjectSize))
+        return OW_Complete;
+
   // If the base pointers still differ, we have two completely different stores.
   if (BP1 != BP2)
     return OW_Unknown;
 
   // The later access completely overlaps the earlier store if and only if
   // both start and end of the earlier one is "inside" the later one:
   //    |<->|--earlier--|<->|
   //    |-------later-------|

llvm/test/Transforms/DeadStoreElimination/MSSA/out-of-bounds-stores.ll

 ; out-of-bounds store may not be executed.
 ;
 ; Test case from PR48279. FIXME.
 define i32 @test_out_of_bounds_store_nonlocal(i1 %c) {
 ; CHECK-LABEL: @test_out_of_bounds_store_nonlocal(
 ; CHECK-NEXT:    [[D:%.*]] = alloca [1 x i32], align 4
 ; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
 ; CHECK:       for.body:
+; CHECK-NEXT:    [[ARRAYIDX:%.*]] = getelementptr inbounds [1 x i32], [1 x i32]* [[D]], i64 0, i64 0
+; CHECK-NEXT:    store i32 10, i32* [[ARRAYIDX]], align 4
 ; CHECK-NEXT:    br label [[FOR_INC:%.*]]
 ; CHECK:       for.inc:
 ; CHECK-NEXT:    br i1 [[C:%.*]], label [[FOR_BODY_1:%.*]], label [[FOR_END:%.*]]
 ; CHECK:       for.body.1:
 ; CHECK-NEXT:    ret i32 1
 ; CHECK:       for.end:
 ; CHECK-NEXT:    [[ARRAYIDX1:%.*]] = getelementptr inbounds [1 x i32], [1 x i32]* [[D]], i64 0, i64 0
 ; CHECK-NEXT:    [[LV1:%.*]] = load i32, i32* [[ARRAYIDX1]], align 4
for.body.1:                                       ; preds = %for.inc
   store i32 20, i32* %arrayidx.1, align 4
   ret i32 1
 
 for.end:                                          ; preds = %for.inc
   %arrayidx1 = getelementptr inbounds [1 x i32], [1 x i32]* %d, i64 0, i64 0
   %lv1 = load i32, i32* %arrayidx1, align 4
   call void @use(i32 %lv1)
   ret i32 0
 }