[EarlyCSE] Teach about CSE'ing over invariant.start intrinsics

[anna]

Summary

Teach EarlyCSE about invariant.start intrinsic. Specifically, we can perform
store-load, load-load forwarding over this call. Also, keep in mind that we
cannot perform DSE over the call since it reads memory.

[sanjoy]

test/Transforms/EarlyCSE/invariant.start.ll

50 ↗

(On Diff #67177)

Why do you need to prevent DSE here? As written, the program is undefined (since we're changing an invariant location).

The only problematic optimization around invariant_(start|end) that I can come up with is stores floating into the invariant region. DSE seems fine, even in case like:

*ptr = 100
k = invariant_start(ptr)
;; BODY
invariant_end(k, ptr)
*ptr = 500

If BODY contains a read from ptr then we won't DSE the first store, but if not, it looks like it is fine to DSE it.

[anna]

test/Transforms/EarlyCSE/invariant.start.ll

50 ↗

(On Diff #67177)

So, DSE can take place since anyway the program would be undefined with stores following invariant.start. Also, with invariant_start/end in place, DSE will not take place since invariant_end is still read-write.

I think with the CSE optimization, stores cannot float *into* the invariant region. So, I'll remove the lastStore to nullptr and keep the DSE tests.

[sanjoy]

test/Transforms/EarlyCSE/invariant.start.ll

9 ↗

(On Diff #67177)

Btw, I think you need a space after the :.

[anna]

DSE can be done in presence of invariant.start. Add testcases

[sanjoy]

lgtm

llvm/trunk/lib/Transforms/Scalar/EarlyCSE.cpp

for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E;) {
     // they're marked as such to ensure preservation of control dependencies),
     // and this pass will not disturb any of the assumption's control
     // dependencies.
     if (match(Inst, m_Intrinsic<Intrinsic::assume>())) {
       DEBUG(dbgs() << "EarlyCSE skipping assumption: " << *Inst << '\n');
       continue;
     }
 
+    // Skip invariant.start intrinsics since they only read memory, and we can
+    // forward values across it. Also, we dont need to consume the last store
+    // since the semantics of invariant.start allow us to perform DSE of the
+    // last store, if there was a store following invariant.start. Consider:
+    //
+    // store 30, i8* p
+    // invariant.start(p)
+    // store 40, i8* p
+    // We can DSE the store to 30, since the store 40 to invariant location p
+    // causes undefined behaviour.
+    if (match(Inst, m_Intrinsic<Intrinsic::invariant_start>()))
+      continue;
+
     if (match(Inst, m_Intrinsic<Intrinsic::experimental_guard>())) {
       if (auto *CondI =
               dyn_cast<Instruction>(cast<CallInst>(Inst)->getArgOperand(0))) {
         // The condition we're on guarding here is true for all dominated
         // locations.
         if (SimpleValue::canHandle(CondI))
           AvailableValues.insert(CondI, ConstantInt::getTrue(BB->getContext()));
       }

llvm/trunk/test/Transforms/EarlyCSE/invariant.start.ll

+; RUN: opt < %s -S -early-cse | FileCheck %s
+; RUN: opt < %s -S -passes=early-cse | FileCheck %s
+
+declare {}* @llvm.invariant.start.p0i8(i64, i8* nocapture) nounwind readonly
+declare void @llvm.invariant.end.p0i8({}*, i64, i8* nocapture) nounwind
+
+; Check that we do load-load forwarding over invariant.start, since it does not
+; clobber memory
+define i8 @test1(i8 *%P) {
+  ; CHECK-LABEL: @test1(
+  ; CHECK-NEXT: %V1 = load i8, i8* %P
+  ; CHECK-NEXT: %i = call {}* @llvm.invariant.start.p0i8(i64 1, i8* %P)
+  ; CHECK-NEXT: ret i8 0
+
+
+  %V1 = load i8, i8* %P
+  %i = call {}* @llvm.invariant.start.p0i8(i64 1, i8* %P)
+  %V2 = load i8, i8* %P
+  %Diff = sub i8 %V1, %V2
+  ret i8 %Diff
+}
+
+
+; Trivial Store->load forwarding over invariant.start
+define i8 @test2(i8 *%P) {
+  ; CHECK-LABEL: @test2(
+  ; CHECK-NEXT: store i8 42, i8* %P
+  ; CHECK-NEXT: %i = call {}* @llvm.invariant.start.p0i8(i64 1, i8* %P)
+  ; CHECK-NEXT: ret i8 42
+
+
+  store i8 42, i8* %P
+  %i = call {}* @llvm.invariant.start.p0i8(i64 1, i8* %P)
+  %V1 = load i8, i8* %P
+  ret i8 %V1
+}
+
+; We can DSE over invariant.start calls, since the first store to
+; %P is valid, and the second store is actually unreachable based on semantics
+; of invariant.start.
+define void @test3(i8* %P) {
+
+; CHECK-LABEL: @test3(
+; CHECK-NEXT:  %i = call {}* @llvm.invariant.start.p0i8(i64 1, i8* %P)
+; CHECK-NEXT:  store i8 60, i8* %P
+
+
+  store i8 50, i8* %P
+  %i = call {}* @llvm.invariant.start.p0i8(i64 1, i8* %P)
+  store i8 60, i8* %P
+  ret void
+}
+
+
+; FIXME: Now the first store can actually be eliminated, since there is no read within
+; the invariant region, between start and end.
+define void @test4(i8* %P) {
+
+; CHECK-LABEL: @test4(
+; CHECK-NEXT: store i8 50, i8* %P
+; CHECK-NEXT:  %i = call {}* @llvm.invariant.start.p0i8(i64 1, i8* %P)
+; CHECK-NEXT: call void @llvm.invariant.end.p0i8({}* %i, i64 1, i8* %P)
+; CHECK-NEXT:  store i8 60, i8* %P
+
+
+  store i8 50, i8* %P
+  %i = call {}* @llvm.invariant.start.p0i8(i64 1, i8* %P)
+  call void @llvm.invariant.end.p0i8({}* %i, i64 1, i8* %P)
+  store i8 60, i8* %P
+  ret void
+}