[SimpifyCFG] Speculate a store preceded by a local non-escaping load

[chill]

Summary

In SimplifyCFG we may simplify the CFG by speculatively executing
certain stores, when they are preceded by a store to the same
location. This patch allows such speculation also when the stores are
similarly preceded by a load.

In order for this transformation to be correct we need to ensure that
the memory location is writable and the store in the new location does
not introduce a data race.

Local objects (created by an alloca instruction) are always
writable, so once we are past a read from a location it is valid to
also write to that same location.

Seeing just a load does not guarantee absence of a data race (unlike
if we see a store) - the load may still be part of a race, just not
causing undefined behaviour
(cf. https://llvm.org/docs/Atomics.html#optimization-outside-atomic).

In the original program, a data race might have been prevented by the
condition, but once we move the store outside the condition, we must
be sure a data race wasn't possible anyway, no matter what the
condition evaluates to.

One way to be sure that a local object is never concurrently
read/written is check that its address never escapes the function.

Hence this transformation is restricted to local, non-escaping
objects.

[nikic]

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

2196

Why does this not use PointerMayBeCaptured or similar?

[chill]

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

2196

Thanks, I'll look at it.

[lebedev.ri]

Please add a negative test that you believe showcases the problem the PointerMayBeCaptured() is solving.

[SjoerdMeijer]

On the profitability of this transform, it looks like this is now always profitable given the restrictions and limiations of isSafeToSpeculateStore? Its description of says:

/// Determine if we can hoist sink a sole store instruction out of a
/// conditional block.

and looking where this was checked I found:

++SpeculatedInstructions;
  if (SpeculatedInstructions > 1)

But perhaps it's good to check this and have another (negative) case for that.

Just checking if we haven't missed anything, did you ran benchmarks and didn't find any regressions related to this?

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

2232

Unrelated, but nice magic number here.

2261

The description of PointerMayBeCaptured says its an expensive function, but with magic number 9 that MaxNumInstToLookAt is set to that doesn't seem to be an issue.

[chill]

In D107281#2921731, @lebedev.ri wrote:

Please add a negative test that you believe showcases the problem the PointerMayBeCaptured() is solving.

Will do.

In D107281#2921750, @SjoerdMeijer wrote:

On the profitability of this transform, it looks like this is now always profitable given the restrictions and limiations of isSafeToSpeculateStore? Its description of says:

/// Determine if we can hoist sink a sole store instruction out of a
/// conditional block.

and looking where this was checked I found:

++SpeculatedInstructions;
  if (SpeculatedInstructions > 1)

But perhaps it's good to check this and have another (negative) case for that.

OK.

Just checking if we haven't missed anything, did you ran benchmarks and didn't find any regressions related to this?

I've got these results (1 - Time_new/Time_old, higher is better):

500.perlbench_r	-0.19%
502.gcc_r	0.26%
505.mcf_r	0.21%
520.omnetpp_r	0.73%
523.xalancbmk_r	0.29%
525.x264_r	0.00%
531.deepsjeng_r	0.00%
541.leela_r	4.50%
557.xz_r	-0.19%

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

2261

That and also the third parameter to PointerMayBeCaptured which limits the number of uses of the alloca to explore to no more than 20.

[chill]

Added a couple of negative tests: for a store to an address that escapes and for more than one instruction in the block.

[xbolva00]

Nice speedup for leela! And probably motivation case, right? I remember gcc’s:

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=89430

[lebedev.ri]

I'm afraid i'm not seeing why @load_before_store_escape must not be transformed.
Alive2 says it's fine: https://alive2.llvm.org/ce/z/F7ctum
I'm not seeing any syncronization primitives, so i'm not really seeing yet why we'd be introducing a race?

[chill]

In D107281#2922685, @lebedev.ri wrote:

I'm afraid i'm not seeing why @load_before_store_escape must not be transformed.
Alive2 says it's fine: https://alive2.llvm.org/ce/z/F7ctum
I'm not seeing any syncronization primitives, so i'm not really seeing yet why we'd be introducing a race?

Once we've made the address of the local variable visible to other functions, we cannot discard the possibility that those other functions may spawn threads
that write to the variable. In the original program, a data race might have been prevented by the condition, but once we move the store outside the
condition, we must be sure a data race wasn't possible anyway, no matter what the condition evaluates to.

Seeing just a load does not guarantee absence of a data race (unlike if we see a store) - the load may still be a part of a race, just not being UB (cf. https://llvm.org/docs/Atomics.html#optimization-outside-atomic)

[lebedev.ri]

Posted https://github.com/AliveToolkit/alive2/issues/735,
but i guess this LG to me. Unless there are other comments.

[nikic]

LG to me as well.

[lebedev.ri]

In D107281#2922901, @chill wrote:

In D107281#2922685, @lebedev.ri wrote:

I'm afraid i'm not seeing why @load_before_store_escape must not be transformed.
Alive2 says it's fine: https://alive2.llvm.org/ce/z/F7ctum
I'm not seeing any syncronization primitives, so i'm not really seeing yet why we'd be introducing a race?

Once we've made the address of the local variable visible to other functions, we cannot discard the possibility that those other functions may spawn threads
that write to the variable. In the original program, a data race might have been prevented by the condition, but once we move the store outside the
condition, we must be sure a data race wasn't possible anyway, no matter what the condition evaluates to.

Seeing just a load does not guarantee absence of a data race (unlike if we see a store) - the load may still be a part of a race, just not being UB (cf. https://llvm.org/docs/Atomics.html#optimization-outside-atomic)

Forgot to say, please add something along those lines at least into the patch description.

[chill]

Updated description and comments.

[chill]

Thanks for the comments and the reviews, much appreciated!

[nickdesaulniers]

Looks like some boot failures on Android are bisecting to this change. See https://bugs.llvm.org/show_bug.cgi?id=52390 for more info.

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

 #include "llvm/ADT/Sequence.h"
 #include "llvm/ADT/SetOperations.h"
 #include "llvm/ADT/SetVector.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/Analysis/AssumptionCache.h"
+#include "llvm/Analysis/CaptureTracking.h"
 #include "llvm/Analysis/ConstantFolding.h"
 #include "llvm/Analysis/EHPersonalities.h"
 #include "llvm/Analysis/GuardUtils.h"
 #include "llvm/Analysis/InstructionSimplify.h"
 #include "llvm/Analysis/MemorySSA.h"
 #include "llvm/Analysis/MemorySSAUpdater.h"
 #include "llvm/Analysis/TargetTransformInfo.h"
 #include "llvm/Analysis/ValueTracking.h"
if (SinkIdx != 0)
     ++NumSinkCommonCode;
   return Changed;
 }
 
 /// Determine if we can hoist sink a sole store instruction out of a
 /// conditional block.
 ///
 /// We are looking for code like the following:
 ///   BrBB:
 ///     store i32 %add, i32* %arrayidx2
 ///     ... // No other stores or function calls (we could be calling a memory
 ///     ... // function).
 ///     %cmp = icmp ult %x, %y
 ///     br i1 %cmp, label %EndBB, label %ThenBB
 ///   ThenBB:
 ///     store i32 %add5, i32* %arrayidx2
 ///     br label EndBB
static Value *isSafeToSpeculateStore(Instruction *I, BasicBlock *BrBB,
   // Volatile or atomic.
   if (!StoreToHoist->isSimple())
     return nullptr;
 
   Value *StorePtr = StoreToHoist->getPointerOperand();
   Type *StoreTy = StoreToHoist->getValueOperand()->getType();
 
   // Look for a store to the same pointer in BrBB.
   unsigned MaxNumInstToLookAt = 9;
   // Skip pseudo probe intrinsic calls which are not really killing any memory
   // accesses.
   for (Instruction &CurI : reverse(BrBB->instructionsWithoutDebug(true))) {
     if (!MaxNumInstToLookAt)
       break;
     --MaxNumInstToLookAt;
 
     // Could be calling an instruction that affects memory like free().
     if (CurI.mayWriteToMemory() && !isa<StoreInst>(CurI))
       return nullptr;
 
     if (auto *SI = dyn_cast<StoreInst>(&CurI)) {
       // Found the previous store to same location and type. Make sure it is
       // simple, to avoid introducing a spurious non-atomic write after an
       // atomic write.
       if (SI->getPointerOperand() == StorePtr &&
           SI->getValueOperand()->getType() == StoreTy && SI->isSimple())
         // Found the previous store, return its value operand.
         return SI->getValueOperand();
       return nullptr; // Unknown store.
     }
+
+    if (auto *LI = dyn_cast<LoadInst>(&CurI)) {
+      if (LI->getPointerOperand() == StorePtr && LI->getType() == StoreTy &&
+          LI->isSimple()) {
+        // Local objects (created by an `alloca` instruction) are always
+        // writable, so once we are past a read from a location it is valid to
+        // also write to that same location.
+        // If the address of the local object never escapes the function, that
+        // means it's never concurrently read or written, hence moving the store
+        // from under the condition will not introduce a data race.
+        auto *AI = dyn_cast<AllocaInst>(getUnderlyingObject(StorePtr));
+        if (AI && !PointerMayBeCaptured(AI, false, true))
+          // Found a previous load, return it.
+          return LI;
+      }
+      // The load didn't work out, but we may still find a store.
+    }
   }
 
   return nullptr;
 }
 
 /// Estimate the cost of the insertion(s) and check that the PHI nodes can be
 /// converted to selects.
 static bool validateAndCostRequiredSelects(BasicBlock *BB, BasicBlock *ThenBB,

llvm/test/Transforms/SimplifyCFG/speculate-store.ll

 if.then:
   store i32 1, ptr %ptr
   br label %ret.end
 
 ret.end:
   ret void
 }
 
+;; Speculate a store, preceded by a local, non-escaping load
+define i32 @load_before_store_noescape(i64 %i, i32 %b)  {
+; CHECK-LABEL: @load_before_store_noescape(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[A:%.*]] = alloca [2 x i32], align 8
+; CHECK-NEXT:    [[TMP0:%.*]] = bitcast [2 x i32]* [[A]] to i64*
+; CHECK-NEXT:    store i64 4294967296, i64* [[TMP0]], align 8
+; CHECK-NEXT:    [[ARRAYIDX:%.*]] = getelementptr inbounds [2 x i32], [2 x i32]* [[A]], i64 0, i64 [[I:%.*]]
+; CHECK-NEXT:    [[TMP1:%.*]] = load i32, i32* [[ARRAYIDX]], align 4
+; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i32 [[TMP1]], [[B:%.*]]
+; CHECK-NEXT:    [[SPEC_STORE_SELECT:%.*]] = select i1 [[CMP]], i32 [[B]], i32 [[TMP1]]
+; CHECK-NEXT:    store i32 [[SPEC_STORE_SELECT]], i32* [[ARRAYIDX]], align 4
+; CHECK-NEXT:    [[ARRAYIDX1:%.*]] = getelementptr inbounds [2 x i32], [2 x i32]* [[A]], i64 0, i64 0
+; CHECK-NEXT:    [[TMP2:%.*]] = load i32, i32* [[ARRAYIDX1]], align 4
+; CHECK-NEXT:    [[ARRAYIDX2:%.*]] = getelementptr inbounds [2 x i32], [2 x i32]* [[A]], i64 0, i64 1
+; CHECK-NEXT:    [[TMP3:%.*]] = load i32, i32* [[ARRAYIDX2]], align 4
+; CHECK-NEXT:    [[ADD:%.*]] = add nsw i32 [[TMP2]], [[TMP3]]
+; CHECK-NEXT:    ret i32 [[ADD]]
+;
+entry:
+  %a = alloca [2 x i32], align 8
+  %0 = bitcast [2 x i32]* %a to i64*
+  store i64 4294967296, i64* %0, align 8
+  %arrayidx = getelementptr inbounds [2 x i32], [2 x i32]* %a, i64 0, i64 %i
+  %1 = load i32, i32* %arrayidx, align 4
+  %cmp = icmp slt i32 %1, %b
+  br i1 %cmp, label %if.then, label %if.end
+
+if.then:
+  store i32 %b, i32* %arrayidx, align 4
+  br label %if.end
+
+if.end:
+  %arrayidx1 = getelementptr inbounds [2 x i32], [2 x i32]* %a, i64 0, i64 0
+  %2 = load i32, i32* %arrayidx1, align 4
+  %arrayidx2 = getelementptr inbounds [2 x i32], [2 x i32]* %a, i64 0, i64 1
+  %3 = load i32, i32* %arrayidx2, align 4
+  %add = add nsw i32 %2, %3
+  ret i32 %add
+}
+
+;; Don't speculate a store, preceded by a local, escaping load
+define i32 @load_before_store_escape(i64 %i, i32 %b)  {
+; CHECK-LABEL: @load_before_store_escape(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[A:%.*]] = alloca [2 x i32], align 8
+; CHECK-NEXT:    [[TMP0:%.*]] = bitcast [2 x i32]* [[A]] to i64*
+; CHECK-NEXT:    store i64 4294967296, i64* [[TMP0]], align 8
+; CHECK-NEXT:    call void @fork_some_threads([2 x i32]* [[A]])
+; CHECK-NEXT:    [[ARRAYIDX:%.*]] = getelementptr inbounds [2 x i32], [2 x i32]* [[A]], i64 0, i64 [[I:%.*]]
+; CHECK-NEXT:    [[TMP1:%.*]] = load i32, i32* [[ARRAYIDX]], align 4
+; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i32 [[TMP1]], [[B:%.*]]
+; CHECK-NEXT:    br i1 [[CMP]], label [[IF_THEN:%.*]], label [[IF_END:%.*]]
+; CHECK:       if.then:
+; CHECK-NEXT:    store i32 [[B]], i32* [[ARRAYIDX]], align 4
+; CHECK-NEXT:    br label [[IF_END]]
+; CHECK:       if.end:
+; CHECK-NEXT:    [[ARRAYIDX1:%.*]] = getelementptr inbounds [2 x i32], [2 x i32]* [[A]], i64 0, i64 0
+; CHECK-NEXT:    [[TMP2:%.*]] = load i32, i32* [[ARRAYIDX1]], align 4
+; CHECK-NEXT:    [[ARRAYIDX2:%.*]] = getelementptr inbounds [2 x i32], [2 x i32]* [[A]], i64 0, i64 1
+; CHECK-NEXT:    [[TMP3:%.*]] = load i32, i32* [[ARRAYIDX2]], align 4
+; CHECK-NEXT:    [[ADD:%.*]] = add nsw i32 [[TMP2]], [[TMP3]]
+; CHECK-NEXT:    call void @join_some_threads()
+; CHECK-NEXT:    ret i32 [[ADD]]
+;
+entry:
+  %a = alloca [2 x i32], align 8
+  %0 = bitcast [2 x i32]* %a to i64*
+  store i64 4294967296, i64* %0, align 8
+  call void @fork_some_threads([2 x i32]* %a)
+  %arrayidx = getelementptr inbounds [2 x i32], [2 x i32]* %a, i64 0, i64 %i
+  %1 = load i32, i32* %arrayidx, align 4
+  %cmp = icmp slt i32 %1, %b
+  br i1 %cmp, label %if.then, label %if.end
+
+if.then:
+  store i32 %b, i32* %arrayidx, align 4
+  br label %if.end
+
+if.end:
+  %arrayidx1 = getelementptr inbounds [2 x i32], [2 x i32]* %a, i64 0, i64 0
+  %2 = load i32, i32* %arrayidx1, align 4
+  %arrayidx2 = getelementptr inbounds [2 x i32], [2 x i32]* %a, i64 0, i64 1
+  %3 = load i32, i32* %arrayidx2, align 4
+  %add = add nsw i32 %2, %3
+  call void @join_some_threads()
+  ret i32 %add
+}
+
+declare void @fork_some_threads([2 x i32] *);
+declare void @join_some_threads();
+
+; Don't speculate if it's not the only instruction in the block (not counting
+; the terminator)
+define i32 @not_alone_in_block(i64 %i, i32 %b)  {
+; CHECK-LABEL: @not_alone_in_block(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[A:%.*]] = alloca [2 x i32], align 8
+; CHECK-NEXT:    [[TMP0:%.*]] = bitcast [2 x i32]* [[A]] to i64*
+; CHECK-NEXT:    store i64 4294967296, i64* [[TMP0]], align 8
+; CHECK-NEXT:    [[ARRAYIDX:%.*]] = getelementptr inbounds [2 x i32], [2 x i32]* [[A]], i64 0, i64 [[I:%.*]]
+; CHECK-NEXT:    [[ARRAYIDX1:%.*]] = getelementptr inbounds [2 x i32], [2 x i32]* [[A]], i64 0, i64 0
+; CHECK-NEXT:    [[TMP1:%.*]] = load i32, i32* [[ARRAYIDX]], align 4
+; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i32 [[TMP1]], [[B:%.*]]
+; CHECK-NEXT:    br i1 [[CMP]], label [[IF_THEN:%.*]], label [[IF_END:%.*]]
+; CHECK:       if.then:
+; CHECK-NEXT:    store i32 [[B]], i32* [[ARRAYIDX]], align 4
+; CHECK-NEXT:    store i32 [[B]], i32* [[ARRAYIDX1]], align 4
+; CHECK-NEXT:    br label [[IF_END]]
+; CHECK:       if.end:
+; CHECK-NEXT:    [[TMP2:%.*]] = load i32, i32* [[ARRAYIDX1]], align 4
+; CHECK-NEXT:    [[ARRAYIDX2:%.*]] = getelementptr inbounds [2 x i32], [2 x i32]* [[A]], i64 0, i64 1
+; CHECK-NEXT:    [[TMP3:%.*]] = load i32, i32* [[ARRAYIDX2]], align 4
+; CHECK-NEXT:    [[ADD:%.*]] = add nsw i32 [[TMP2]], [[TMP3]]
+; CHECK-NEXT:    ret i32 [[ADD]]
+;
+entry:
+  %a = alloca [2 x i32], align 8
+  %0 = bitcast [2 x i32]* %a to i64*
+  store i64 4294967296, i64* %0, align 8
+  %arrayidx = getelementptr inbounds [2 x i32], [2 x i32]* %a, i64 0, i64 %i
+  %arrayidx1 = getelementptr inbounds [2 x i32], [2 x i32]* %a, i64 0, i64 0
+  %1 = load i32, i32* %arrayidx, align 4
+  %cmp = icmp slt i32 %1, %b
+  br i1 %cmp, label %if.then, label %if.end
+
+if.then:
+  store i32 %b, i32* %arrayidx, align 4
+  store i32 %b, i32* %arrayidx1, align 4
+  br label %if.end
+
+if.end:
+  %2 = load i32, i32* %arrayidx1, align 4
+  %arrayidx2 = getelementptr inbounds [2 x i32], [2 x i32]* %a, i64 0, i64 1
+  %3 = load i32, i32* %arrayidx2, align 4
+  %add = add nsw i32 %2, %3
+  ret i32 %add
+}
+
 ; CHECK: !0 = !{!"branch_weights", i32 3, i32 5}
 !0 = !{!"branch_weights", i32 3, i32 5}