[LICM] Don't promote store to global even in single-thread mode

[nikic]

Summary

Even if there are no thread-safety concerns, we should not promote (not guaranteed-to-execute) stores to globals: While the global may be writable, we may not have provenance to perform the write. The @promote_global_noalias test case illustrates a miscompile in the presence of a noalias pointer to the global.

Worth noting that the load-only promotion may also not be well-defined depending on precise semantics (we don't specify whether load violating noalias is poison or UB -- though I believe the general inclination is to make it poison, and only stores UB), but that's a more general issue.

This is inspired by https://github.com/llvm/llvm-project/issues/60860, which is a related issue with TBAA metadata.

[jdoerfert]

Can we make this less drastic by checking the global. If it is internal and doesn't have its address taken there are no aliasing pointers, I think/hope.

[nikic]

In D146233#4200306, @jdoerfert wrote:

Can we make this less drastic by checking the global. If it is internal and doesn't have its address taken there are no aliasing pointers, I think/hope.

I don't think there's any simple way to do this. Note that this does not actually require the address to be taken -- creating a noalias pointer does not constitute a capture.

It's probably worth pointing out that this code was only recently introduced by D130466 and only applies under -mthread-model=single. This change does not affect/regress normal LICM.

[jdoerfert]

In D146233#4200610, @nikic wrote:

In D146233#4200306, @jdoerfert wrote:

Can we make this less drastic by checking the global. If it is internal and doesn't have its address taken there are no aliasing pointers, I think/hope.

I don't think there's any simple way to do this. Note that this does not actually require the address to be taken -- creating a noalias pointer does not constitute a capture.

It's probably worth pointing out that this code was only recently introduced by D130466 and only applies under -mthread-model=single. This change does not affect/regress normal LICM.

I didn't realize the latter. I was thinking we could look at all uses, >50% of the time we probably only see loads, stores, and mem* intrinsic uses. That said, there is no need only for some non-default use case.

[efriedma]

Is the issue here actually specific to global variables? I mean, you can't mark a local variable noalias, but noalias/TBAA metadata can apply to local variables.

[nikic]

In D146233#4200982, @efriedma wrote:

Is the issue here actually specific to global variables? I mean, you can't mark a local variable noalias, but noalias/TBAA metadata can apply to local variables.

There is also an issue with AA metadata, but I think it's a bit different from this one, see https://github.com/llvm/llvm-project/issues/60860#issuecomment-1474006326. In addition to that, we also currently preserve AA metadata on the promoted loads and stores in some cases where it isn't legal.

llvm/lib/Transforms/Scalar/LICM.cpp

bool isNotVisibleOnUnwindInLoop(const Value *Object, const Loop *L,
   bool RequiresNoCaptureBeforeUnwind;
   if (!isNotVisibleOnUnwind(Object, RequiresNoCaptureBeforeUnwind))
     return false;
 
   return !RequiresNoCaptureBeforeUnwind ||
          isNotCapturedBeforeOrInLoop(Object, L, DT);
 }
 
+// We don't consider globals as writable: While the physical memory is writable,
+// we may not have provenance to perform the write.
 bool isWritableObject(const Value *Object) {
   // TODO: Alloca might not be writable after its lifetime ends.
   // See https://github.com/llvm/llvm-project/issues/51838.
   if (isa<AllocaInst>(Object))
     return true;
 
   // TODO: Also handle sret.
   if (auto *A = dyn_cast<Argument>(Object))
     return A->hasByValAttr();
 
-  if (auto *G = dyn_cast<GlobalVariable>(Object))
-    return !G->isConstant();
-
   // TODO: Noalias has nothing to do with writability, this should check for
   // an allocator function.
   return isNoAliasCall(Object);
 }
 
 bool isThreadLocalObject(const Value *Object, const Loop *L, DominatorTree *DT,
                          TargetTransformInfo *TTI) {
   // The object must be function-local to start with, and then not captured

llvm/test/Transforms/LICM/promote-single-thread.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -S -passes=licm < %s | FileCheck %s --check-prefixes=CHECK,MT
 ; RUN: opt -S -passes=licm -licm-force-thread-model-single < %s | FileCheck %s --check-prefixes=CHECK,ST
 
 @g = external global i32
 @c = external constant i32
 
 declare void @capture(ptr)
 
-; In single-thread mode both loads and stores can be promoted. In multi-thread
-; mode only loads can be promoted, as a different thread might write to the
-; global.
+; Even in single-thread mode, can only perform load-only promotion for globals,
+; because we might not have provenance to write to the global. See
+; promote_global_noalias for an example of the issue.
 define void @promote_global(i1 %c, i1 %c2) {
-; MT-LABEL: @promote_global(
-; MT-NEXT:  entry:
-; MT-NEXT:    [[G_PROMOTED:%.*]] = load i32, ptr @g, align 4
-; MT-NEXT:    br label [[LOOP:%.*]]
-; MT:       loop:
-; MT-NEXT:    [[V_INC2:%.*]] = phi i32 [ [[V_INC1:%.*]], [[LATCH:%.*]] ], [ [[G_PROMOTED]], [[ENTRY:%.*]] ]
-; MT-NEXT:    br i1 [[C:%.*]], label [[IF:%.*]], label [[LATCH]]
-; MT:       if:
-; MT-NEXT:    [[V_INC:%.*]] = add i32 [[V_INC2]], 1
-; MT-NEXT:    store i32 [[V_INC]], ptr @g, align 4
-; MT-NEXT:    br label [[LATCH]]
-; MT:       latch:
-; MT-NEXT:    [[V_INC1]] = phi i32 [ [[V_INC]], [[IF]] ], [ [[V_INC2]], [[LOOP]] ]
-; MT-NEXT:    br i1 [[C2:%.*]], label [[EXIT:%.*]], label [[LOOP]]
-; MT:       exit:
-; MT-NEXT:    ret void
-;
-; ST-LABEL: @promote_global(
-; ST-NEXT:  entry:
-; ST-NEXT:    [[G_PROMOTED:%.*]] = load i32, ptr @g, align 4
-; ST-NEXT:    br label [[LOOP:%.*]]
-; ST:       loop:
-; ST-NEXT:    [[V_INC2:%.*]] = phi i32 [ [[V_INC1:%.*]], [[LATCH:%.*]] ], [ [[G_PROMOTED]], [[ENTRY:%.*]] ]
-; ST-NEXT:    br i1 [[C:%.*]], label [[IF:%.*]], label [[LATCH]]
-; ST:       if:
-; ST-NEXT:    [[V_INC:%.*]] = add i32 [[V_INC2]], 1
-; ST-NEXT:    br label [[LATCH]]
-; ST:       latch:
-; ST-NEXT:    [[V_INC1]] = phi i32 [ [[V_INC]], [[IF]] ], [ [[V_INC2]], [[LOOP]] ]
-; ST-NEXT:    br i1 [[C2:%.*]], label [[EXIT:%.*]], label [[LOOP]]
-; ST:       exit:
-; ST-NEXT:    [[V_INC1_LCSSA:%.*]] = phi i32 [ [[V_INC1]], [[LATCH]] ]
-; ST-NEXT:    store i32 [[V_INC1_LCSSA]], ptr @g, align 4
-; ST-NEXT:    ret void
+; CHECK-LABEL: @promote_global(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[G_PROMOTED:%.*]] = load i32, ptr @g, align 4
+; CHECK-NEXT:    br label [[LOOP:%.*]]
+; CHECK:       loop:
+; CHECK-NEXT:    [[V_INC2:%.*]] = phi i32 [ [[V_INC1:%.*]], [[LATCH:%.*]] ], [ [[G_PROMOTED]], [[ENTRY:%.*]] ]
+; CHECK-NEXT:    br i1 [[C:%.*]], label [[IF:%.*]], label [[LATCH]]
+; CHECK:       if:
+; CHECK-NEXT:    [[V_INC:%.*]] = add i32 [[V_INC2]], 1
+; CHECK-NEXT:    store i32 [[V_INC]], ptr @g, align 4
+; CHECK-NEXT:    br label [[LATCH]]
+; CHECK:       latch:
+; CHECK-NEXT:    [[V_INC1]] = phi i32 [ [[V_INC]], [[IF]] ], [ [[V_INC2]], [[LOOP]] ]
+; CHECK-NEXT:    br i1 [[C2:%.*]], label [[EXIT:%.*]], label [[LOOP]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret void
 ;
 entry:
   br label %loop
 
 loop:
   br i1 %c, label %if, label %latch
 
 if:

 
 exit:
   ret void
 }
 
 ; if %c is false and %ptr == @g, then this should store 42 to the pointer.
 ; However, if we perform load+store promotion, then we would instead store the
 ; original value of the global.
-; FIXME: This is a miscompile.
 define void @promote_global_noalias(i1 %c, i1 %c2, ptr noalias %ptr) {
-; MT-LABEL: @promote_global_noalias(
-; MT-NEXT:  entry:
-; MT-NEXT:    [[G_PROMOTED:%.*]] = load i32, ptr @g, align 4
-; MT-NEXT:    br label [[LOOP:%.*]]
-; MT:       loop:
-; MT-NEXT:    [[V_INC2:%.*]] = phi i32 [ [[V_INC1:%.*]], [[LATCH:%.*]] ], [ [[G_PROMOTED]], [[ENTRY:%.*]] ]
-; MT-NEXT:    br i1 [[C:%.*]], label [[IF:%.*]], label [[ELSE:%.*]]
-; MT:       if:
-; MT-NEXT:    [[V_INC:%.*]] = add i32 [[V_INC2]], 1
-; MT-NEXT:    store i32 [[V_INC]], ptr @g, align 4
-; MT-NEXT:    br label [[LATCH]]
-; MT:       else:
-; MT-NEXT:    store i32 42, ptr [[PTR:%.*]], align 4
-; MT-NEXT:    br label [[LATCH]]
-; MT:       latch:
-; MT-NEXT:    [[V_INC1]] = phi i32 [ [[V_INC2]], [[ELSE]] ], [ [[V_INC]], [[IF]] ]
-; MT-NEXT:    br i1 [[C2:%.*]], label [[EXIT:%.*]], label [[LOOP]]
-; MT:       exit:
-; MT-NEXT:    ret void
-;
-; ST-LABEL: @promote_global_noalias(
-; ST-NEXT:  entry:
-; ST-NEXT:    [[G_PROMOTED:%.*]] = load i32, ptr @g, align 4
-; ST-NEXT:    br label [[LOOP:%.*]]
-; ST:       loop:
-; ST-NEXT:    [[V_INC2:%.*]] = phi i32 [ [[V_INC1:%.*]], [[LATCH:%.*]] ], [ [[G_PROMOTED]], [[ENTRY:%.*]] ]
-; ST-NEXT:    br i1 [[C:%.*]], label [[IF:%.*]], label [[ELSE:%.*]]
-; ST:       if:
-; ST-NEXT:    [[V_INC:%.*]] = add i32 [[V_INC2]], 1
-; ST-NEXT:    br label [[LATCH]]
-; ST:       else:
-; ST-NEXT:    store i32 42, ptr [[PTR:%.*]], align 4
-; ST-NEXT:    br label [[LATCH]]
-; ST:       latch:
-; ST-NEXT:    [[V_INC1]] = phi i32 [ [[V_INC2]], [[ELSE]] ], [ [[V_INC]], [[IF]] ]
-; ST-NEXT:    br i1 [[C2:%.*]], label [[EXIT:%.*]], label [[LOOP]]
-; ST:       exit:
-; ST-NEXT:    [[V_INC1_LCSSA:%.*]] = phi i32 [ [[V_INC1]], [[LATCH]] ]
-; ST-NEXT:    store i32 [[V_INC1_LCSSA]], ptr @g, align 4
-; ST-NEXT:    ret void
+; CHECK-LABEL: @promote_global_noalias(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[G_PROMOTED:%.*]] = load i32, ptr @g, align 4
+; CHECK-NEXT:    br label [[LOOP:%.*]]
+; CHECK:       loop:
+; CHECK-NEXT:    [[V_INC2:%.*]] = phi i32 [ [[V_INC1:%.*]], [[LATCH:%.*]] ], [ [[G_PROMOTED]], [[ENTRY:%.*]] ]
+; CHECK-NEXT:    br i1 [[C:%.*]], label [[IF:%.*]], label [[ELSE:%.*]]
+; CHECK:       if:
+; CHECK-NEXT:    [[V_INC:%.*]] = add i32 [[V_INC2]], 1
+; CHECK-NEXT:    store i32 [[V_INC]], ptr @g, align 4
+; CHECK-NEXT:    br label [[LATCH]]
+; CHECK:       else:
+; CHECK-NEXT:    store i32 42, ptr [[PTR:%.*]], align 4
+; CHECK-NEXT:    br label [[LATCH]]
+; CHECK:       latch:
+; CHECK-NEXT:    [[V_INC1]] = phi i32 [ [[V_INC2]], [[ELSE]] ], [ [[V_INC]], [[IF]] ]
+; CHECK-NEXT:    br i1 [[C2:%.*]], label [[EXIT:%.*]], label [[LOOP]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret void
 ;
 entry:
   br label %loop
 
 loop:
   br i1 %c, label %if, label %else
 
 if: