[GlobalOpt] Perform store->dominated load forwarding for stored once globals

[aeubanks]

Summary

The initial land incorrectly optimized forwarding non-Constants in non-nosync/norecurse functions. Bail on non-Constants since norecurse should cause global -> alloca promotion anyway.

The initial land also incorrectly assumed that StoredOnceStore was the only store to the global, but it actually means that only one value other than the global initializer is stored. Add a check that there's only one store.

Compile time tracker:
https://llvm-compile-time-tracker.com/compare.php?from=c80b88ee29f34078d2149de94e27600093e6c7c0&to=ef2c2b7772424b6861a75e794f3c31b45167304a&stat=instructions

[aeubanks]

update

[nikic]

LGTM

I noticed that currently GlobalOpt invalidates all analyses if it makes any change. Can't we preserve at least all the CFG analyses, such as the domtree computed here?

llvm/lib/Transforms/IPO/GlobalOpt.cpp

1453

getValueOperand

[jdoerfert]

This breaks in the presence of synchronization.

static int X = 42;

int foo(int Arg) {
  sync();
  X = Arg;
  sync();
  return X;
}

Two threads call foo with two values of Arg and the sync will ensure they proceed "one after another":

    X = 42;
sync
T1: X = Arg1;
sync
T2: X = Arg2;
sync
T1, T2: return Arg2

Whereas replacing the load will result

T1, T2, return Arg{1,2}

Right? If foo is nosync this should work though.

[aeubanks]

bail on forwarding non-Constants in non-nosync functions

[jdoerfert]

LG, I think :)

[nikic]

llvm/lib/Transforms/IPO/GlobalOpt.cpp

1458

Possible complication here might be storing the address of a thread-local, which is Constant but not necessarily the same between two invocations. (Though that would be solved by https://reviews.llvm.org/D125291.)

[jdoerfert]

llvm/lib/Transforms/IPO/GlobalOpt.cpp

1458

Good point. Constant::isThreadDependent. Though. I don't know why we require constant in the first place. What is the motivation here?

[aeubanks]

treat thread local constants as non-constants

[jdoerfert]

I think I misread it earlier. Constant & !thread_dependent *or* nosync. This makes more sense.

[aeubanks]

remove check for thread_local global. GlobalStatus::analyzeGlobal() actually already bails if it sees a store of a thread_local variable
keep thread_local tests just to make sure

[asbirlea]

Latest diff looks good to me.

[tingwang]

It seems to me following test showed unexpected result

target datalayout = "e-m:e-i64:64-p:64:64-n32:64-S128-v256:256:256-v512:512:512"
target triple = "powerpc64le-unknown-linux-gnu"

@lwvar1 = internal global i32 0, align 4

define dso_local signext i32 @main() {
plmix5_entry:
  %T_4 = alloca i32, align 4
  %"#87" = alloca i32, align 4
  store i32 1, i32* @lwvar1, align 4
  store i32 0, i32* @lwvar1, align 4
  %_val_lwvar1_212 = load i32, i32* @lwvar1, align 4
  store i32 %_val_lwvar1_212, i32* %"#87", align 4
  unreachable
}

Tried with D128128.id438853.diff: opt -globalopt -S < %s

; ModuleID = '<stdin>'
source_filename = "<stdin>"
target datalayout = "e-m:e-i64:64-p:64:64-n32:64-S128-v256:256:256-v512:512:512"
target triple = "powerpc64le-unknown-linux-gnu"

define dso_local signext i32 @main() local_unnamed_addr {
plmix5_entry:
  %T_4 = alloca i32, align 4
  %"#87" = alloca i32, align 4
  store i32 1, i32* %"#87", align 4
  unreachable
}

[jdoerfert]

^^^ so much for stored once

[AaronLiu]

Reduced TC that fail with -O3 -flto:

int counter = 0;

struct S {
        int m;
        S(int i=0) : m(i) { }
        S(S&) { counter++; }
        S& operator=(S&) { counter++; return *this; }
} s;

int main(void)
{
        try {   
                try {   
                        throw s;
                }
                catch (...) {
                        counter = 0;
                        throw;
                }
        }
        catch (...) {
        }

        if (counter != 0) {
                return 1;
        }

        return  0;
}

[aeubanks]

turns out GlobalStatus::StoredOnce means "one store that's not the initializer but potentially other stores of the initializer"
will fix

[aeubanks]

update

[tingwang]

A quick try on B171416: Diff 439149 shows one case still fails. Please allow me some time to look into the details and reduce the error if there is any. I will update later.

[tingwang]

In D128128#3603623, @tingwang wrote:

A quick try on B171416: Diff 439149 shows one case still fails. Please allow me some time to look into the details and reduce the error if there is any. I will update later.

This time, I saw error on recursive function.

[tingwang]

target datalayout = "e-m:e-i64:64-p:64:64-n32:64-S128-v256:256:256-v512:512:512"
target triple = "powerpc64le-unknown-linux-gnu"

@j = internal unnamed_addr global i32 0, align 4

; Function Attrs: nobuiltin nofree noinline nosync
define dso_local signext i32 @recursive_sub(i32* noalias nocapture dereferenceable(4) %.i) local_unnamed_addr #4 {
recursive_sub_entry:
  %_val_i_ = load i32, i32* %.i, align 4
  %_add_tmp = sub i32 6, %_val_i_
  store i32 %_add_tmp, i32* @j, align 4
  %_add_tmp8 = add nsw i32 %_val_i_, 1
  store i32 %_add_tmp8, i32* %.i, align 4
  %0 = tail call i32 @recursive_sub(i32* nonnull %.i)
  %_val_ptr_ = load i32, i32* @j, align 4
  %_add_tmp11 = add nsw i32 %_val_ptr_, %0
  ret i32 1
}

attributes #4 = { nobuiltin nofree noinline nosync }

opt -globalopt -S < %s

; ModuleID = '<stdin>'
source_filename = "<stdin>"
target datalayout = "e-m:e-i64:64-p:64:64-n32:64-S128-v256:256:256-v512:512:512"
target triple = "powerpc64le-unknown-linux-gnu"

; Function Attrs: nobuiltin nofree noinline nosync
define dso_local signext i32 @recursive_sub(i32* noalias nocapture dereferenceable(4) %.i) local_unnamed_addr #0 {
recursive_sub_entry:
  %_val_i_ = load i32, i32* %.i, align 4
  %_add_tmp = sub i32 6, %_val_i_
  %_add_tmp8 = add nsw i32 %_val_i_, 1
  store i32 %_add_tmp8, i32* %.i, align 4
  %0 = tail call i32 @recursive_sub(i32* nonnull %.i)
  %_add_tmp11 = add nsw i32 %_add_tmp, %0
  ret i32 1
}

attributes #0 = { nobuiltin nofree noinline nosync }

[nikic]

Yeah, the non-constant case needs both nosync and norecurse.

[jdoerfert]

In D128128#3604723, @nikic wrote:

Yeah, the non-constant case needs both nosync and norecurse.

Attributor calls this "dynamically unique" and I could have thought of this before.

[aeubanks]

bail on non Constants, if we need norecurse then at that point global -> alloca promotion should kick in anyway

[aeubanks]

rebase

[nikic]

LG, fingers crossed.

llvm/lib/Transforms/IPO/GlobalOpt.cpp

for (auto *UU : UUsers) {
       UI->replaceUsesOfWith(U, NewU);
     }
     // We've replaced all the uses, so destroy the constant. (destroyConstant
     // will update value handles and metadata.)
     U->destroyConstant();
   }
 }
 
+// For a global variable with one store, if the store dominates any loads,
+// those loads will always load the stored value (as opposed to the
+// initializer), even in the presence of recursion.
+static bool forwardStoredOnceStore(
+    GlobalVariable *GV, const StoreInst *StoredOnceStore,
+    function_ref<DominatorTree &(Function &)> LookupDomTree) {
+  const Value *StoredOnceValue = StoredOnceStore->getValueOperand();
+  const Function *F = StoredOnceStore->getFunction();
+  // If the value is not a constant, there may be synchronization that causes
+  // multiple threads to observe different values stored to/loaded from the
+  // global.
+  if (!isa<Constant>(StoredOnceValue) && !F->hasNoSync())
+    return false;
+  SmallVector<LoadInst *> Loads;
+  for (User *U : GV->users()) {
+    if (auto *LI = dyn_cast<LoadInst>(U)) {
+      if (LI->getFunction() == F &&
+          LI->getType() == StoredOnceValue->getType() && LI->isSimple())
+        Loads.push_back(LI);
+    }
+  }
+  // Only compute DT if we have any loads to examine.
+  bool MadeChange = false;
+  if (!Loads.empty()) {
+    auto &DT = LookupDomTree(*const_cast<Function *>(F));
+    for (auto *LI : Loads) {
+      if (DT.dominates(StoredOnceStore, LI)) {
+        LI->replaceAllUsesWith(const_cast<Value *>(StoredOnceValue));
+        LI->eraseFromParent();
+        MadeChange = true;
+      }
+    }
+  }
+  return MadeChange;
+}
+
 /// Analyze the specified global variable and optimize
 /// it if possible.  If we make a change, return true.
 static bool
 processInternalGlobal(GlobalVariable *GV, const GlobalStatus &GS,
                       function_ref<TargetTransformInfo &(Function &)> GetTTI,
                       function_ref<TargetLibraryInfo &(Function &)> GetTLI,
                       function_ref<DominatorTree &(Function &)> LookupDomTree) {
   auto &DL = GV->getParent()->getDataLayout();
if (SOVConstant && isa<UndefValue>(GV->getInitializer()) &&
       return true;
     }
 
     // Try to optimize globals based on the knowledge that only one value
     // (besides its initializer) is ever stored to the global.
     if (optimizeOnceStoredGlobal(GV, StoredOnceValue, DL, GetTLI))
       return true;
 
+    // Try to forward the store to any loads.
+    if (forwardStoredOnceStore(GV, GS.StoredOnceStore, LookupDomTree))
+      return true;
+
     // Otherwise, if the global was not a boolean, we can shrink it to be a
     // boolean. Skip this optimization for AS that doesn't allow an initializer.
     if (SOVConstant && GS.Ordering == AtomicOrdering::NotAtomic &&
         (!isa<UndefValue>(GV->getInitializer()) ||
          CanHaveNonUndefGlobalInitializer)) {
       if (TryToShrinkGlobalToBoolean(GV, SOVConstant)) {
         ++NumShrunkToBool;
         return true;

llvm/test/Transforms/GlobalOpt/shrink-global-to-bool-check-debug.ll

 ; RUN: opt -S -passes=debugify,globalopt -f %s | FileCheck %s
 
 @foo = internal global i32 0, align 4
 
-define dso_local i32 @bar() {
+define void @store() {
 entry:
   store i32 5, i32* @foo, align 4
+  ret void
+}
+
+define i32 @bar() {
+entry:
   %0 = load i32, i32* @foo, align 4
   ret i32 %0
 }
 
 ;CHECK:      @bar
 ;CHECK-NEXT: entry:
-;CHECK-NEXT:   store i1 true, i1* @foo, align 1, !dbg ![[DbgLocStore:[0-9]+]]
 ;CHECK-NEXT:   %.b = load i1, i1* @foo, align 1, !dbg ![[DbgLocLoadSel:[0-9]+]]
 ;CHECK-NEXT:   %0 = select i1 %.b, i32 5, i32 0, !dbg ![[DbgLocLoadSel]]
 ;CHECK-NEXT:   call void @llvm.dbg.value({{.*}}), !dbg ![[DbgLocLoadSel]]
 ;CHECK-NEXT:   ret i32 %0, !dbg ![[DbgLocRet:[0-9]+]]
 
-;CHECK: ![[DbgLocStore]] = !DILocation(line: 1,
-;CHECK: ![[DbgLocLoadSel]] = !DILocation(line: 2,
-;CHECK: ![[DbgLocRet]] = !DILocation(line: 3,
+;CHECK: ![[DbgLocLoadSel]] = !DILocation(line: 3,
+;CHECK: ![[DbgLocRet]] = !DILocation(line: 4,

llvm/test/Transforms/GlobalOpt/shrink-global-to-bool.ll

 ; RUN: opt -passes=globalopt --mtriple=amdgcn-amd-amdhsa < %s -S | FileCheck %s
 ; REQUIRES: amdgpu-registered-target
 
 @gvar = internal unnamed_addr global i32 undef
 @lvar = internal unnamed_addr addrspace(3) global i32 undef
 
 ; Should optimize @gvar.
 ; CHECK-NOT: @gvar
 
 ; Negative test for AS(3). Skip shrink global to bool optimization.
 ; CHECK: @lvar = internal unnamed_addr addrspace(3) global i32 undef
 
-define void @test_global_var() {
+define void @test_global_var(i1 %i) {
 ; CHECK-LABEL: @test_global_var(
 ; CHECK:    store volatile i32 10, i32* undef, align 4
 ;
 entry:
+  br i1 %i, label %bb1, label %exit
+bb1:
   store i32 10, i32* @gvar
   br label %exit
 exit:
   %ld = load i32, i32* @gvar
   store volatile i32 %ld, i32* undef
   ret void
 }
 
-define void @test_lds_var() {
+define void @test_lds_var(i1 %i) {
 ; CHECK-LABEL: @test_lds_var(
 ; CHECK:    store i32 10, i32 addrspace(3)* @lvar, align 4
 ; CHECK:    [[LD:%.*]] = load i32, i32 addrspace(3)* @lvar, align 4
 ; CHECK:    store volatile i32 [[LD]], i32* undef, align 4
 ;
 entry:
+  br i1 %i, label %bb1, label %exit
+bb1:
   store i32 10, i32 addrspace(3)* @lvar
   br label %exit
 exit:
   %ld = load i32, i32 addrspace(3)* @lvar
   store volatile i32 %ld, i32* undef
   ret void
 }

llvm/test/Transforms/GlobalOpt/stored-once-forward-value.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -passes=globalopt -S < %s | FileCheck %s
 
 @g1 = internal unnamed_addr global i32 0
 @g2 = internal unnamed_addr global i32 0
 @g3 = internal unnamed_addr global i32 0
 @g4 = internal unnamed_addr global i32 0
 @g5 = internal unnamed_addr global i32 0
 @g6 = internal unnamed_addr global i32 0
+@g7 = internal unnamed_addr global i32 0
 
 declare void @b()
 
 define i1 @dom_const() {
 ; CHECK-LABEL: @dom_const(
-; CHECK-NEXT:    store i1 true, ptr @g1, align 1
 ; CHECK-NEXT:    call void @b()
-; CHECK-NEXT:    [[R:%.*]] = load i1, ptr @g1, align 1
-; CHECK-NEXT:    ret i1 [[R]]
+; CHECK-NEXT:    ret i1 true
 ;
   store i1 true, ptr @g1
   call void @b()
   %r = load i1, ptr @g1
   ret i1 %r
 }
 
+define i32 @dom_arg_nosync(i32 %a) nosync {
+; CHECK-LABEL: @dom_arg_nosync(
+; CHECK-NEXT:    call void @b()
+; CHECK-NEXT:    ret i32 [[A:%.*]]
+;
+  store i32 %a, ptr @g7
+  call void @b()
+  %r = load i32, ptr @g7
+  ret i32 %r
+}
+
 define i32 @dom_arg(i32 %a) {
 ; CHECK-LABEL: @dom_arg(
 ; CHECK-NEXT:    store i32 [[A:%.*]], ptr @g2, align 4
 ; CHECK-NEXT:    call void @b()
 ; CHECK-NEXT:    [[R:%.*]] = load i32, ptr @g2, align 4
 ; CHECK-NEXT:    ret i32 [[R]]
 ;
   store i32 %a, ptr @g2
end:
   %r = load i1, ptr @g4
   ret i1 %r
 }
 
 define i1 @dom_multiple_function_loads() {
 ; CHECK-LABEL: @dom_multiple_function_loads(
 ; CHECK-NEXT:    store i1 true, ptr @g5, align 1
 ; CHECK-NEXT:    call void @b()
-; CHECK-NEXT:    [[R:%.*]] = load i1, ptr @g5, align 1
-; CHECK-NEXT:    ret i1 [[R]]
+; CHECK-NEXT:    ret i1 true
 ;
   store i1 true, ptr @g5
   call void @b()
   %r = load i1, ptr @g5
   ret i1 %r
 }
 
 define i1 @other() {

llvm/test/Transforms/PhaseOrdering/recompute-globalsaa.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -passes='default<O2>' -S < %s | FileCheck %s
 @a = internal global i32 0, align 4
 @c = internal global i32** @b, align 8
 @b = internal global i32* null, align 8
 @e = internal global i32* @d, align 8
 @d = internal global i32 0, align 4
 
 define i32 @main() {
 ; CHECK-LABEL: @main(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    store i1 true, i1* @a, align 4
 ; CHECK-NEXT:    [[TMP0:%.*]] = load i32*, i32** @e, align 8
 ; CHECK-NEXT:    store i32 0, i32* [[TMP0]], align 4
 ; CHECK-NEXT:    store i32* null, i32** @e, align 8
 ; CHECK-NEXT:    ret i32 0
 ;
 entry:
   %h = alloca i32*, align 8
   %i = alloca i32*, align 8