[SLPVectorizer] Do Not Move Loads/Stores Beyond Stacksave/Stackrestore Boundaries

[qiongsiwu1]

Summary

If left unchecked, the SLPVecrtorizer can move loads/stores below a stackrestore. The move can cause issues if the loads/stores have pointer operands from allocas that are reset by the stackrestores. This patch adds the dependency check.

The check is conservative, in that it does not check if the pointer operands of the loads/stores are actually from allocas that may be reset. We did not observe any SPECCPU2017 performance degradation so this simple fix seems sufficient.

The test could have been added to llvm/test/Transforms/SLPVectorizer/X86/stacksave-dependence.ll, but that test has not been updated to use opaque pointers. I am not inclined to add tests that still use typed pointers, or to refactor llvm/test/Transforms/SLPVectorizer/X86/stacksave-dependence.ll to use opaque pointers in this patch. If desired, I will open a different patch to refactor and consolidate the tests.

[qiongsiwu1]

Updating code comment.

[qiongsiwu1]

Ping for review. @reames could you also let me know if I should tag anyone else for a review? Thanks so much!

[ABataev]

Thanks! I think it is good enough for now, later we can try to tweak, if required.

[qiongsiwu1]

@ABataev Thanks so much for the fast review! I will land the patch in a moment.

[reames]

Can you explain why memory dependence wasn't enough to prevent the problematic reordering? I'm a bit fuzzy on the details - it's been a while - but I though that stacksave and stackrestore were modeled as modifying all memory to prevent this reordering?

[ABataev]

In D138585#3953869, @reames wrote:

Can you explain why memory dependence wasn't enough to prevent the problematic reordering? I'm a bit fuzzy on the details - it's been a while - but I though that stacksave and stackrestore were modeled as modifying all memory to prevent this reordering?

Did a quick search - looks like it does not work for static allocas, only for dynamic

[qiongsiwu1]

In D138585#3953869, @reames wrote:

Can you explain why memory dependence wasn't enough to prevent the problematic reordering? I'm a bit fuzzy on the details - it's been a while - but I though that stacksave and stackrestore were modeled as modifying all memory to prevent this reordering?

I took a closer look at the new test case, and it seems that the vectorizer never added the four loads that concerns us to the memory dependency list of the stackrestore. It seemed that for some reason the loads memory locations were never treated as aliasing the stackrestore, hence the condition here was never true for the loads when the DepDest was the stackrestore. If I hardcode the result of isAliased to true as long as inst2 is a stackrestore (here), the new test passed without the fix included in this patch. I have not looked at BatchedAA closely to see what exactly is going on. I will do so if fixing BatchedAA is more desirable.

In D138585#3953978, @ABataev wrote:

Did a quick search - looks like it does not work for static allocas, only for dynamic

Ah thanks so much for the fast reply! Maybe it is the alias analysis that is causing static allocas to fail, as stated above? BTW, by static alloca, do we mean the allocas that are defined in the entry block of a function and of a fixed size, as documented here? In the original test case where this issue was observed, the alloca was not defined in the entry block, but was of a known and fixed size (the alloca definition itself was nearly identical to this one).

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

for (ScheduleData *BundleMember = SD; BundleMember;
               continue;
 
             // Add the dependency
             makeControlDependent(I);
           }
         }
 
         // In addition to the cases handle just above, we need to prevent
-        // allocas from moving below a stacksave.  The stackrestore case
-        // is currently thought to be conservatism.
-        if (isa<AllocaInst>(BundleMember->Inst)) {
+        // allocas and loads/stores from moving below a stacksave or a
+        // stackrestore. Avoiding moving allocas below stackrestore is currently
+        // thought to be conservatism. Moving loads/stores below a stackrestore
+        // can lead to incorrect code.
+        if (isa<AllocaInst>(BundleMember->Inst) ||
+            BundleMember->Inst->mayReadOrWriteMemory()) {
           for (Instruction *I = BundleMember->Inst->getNextNode();
                I != ScheduleEnd; I = I->getNextNode()) {
             if (!match(I, m_Intrinsic<Intrinsic::stacksave>()) &&
                 !match(I, m_Intrinsic<Intrinsic::stackrestore>()))
               continue;
 
             // Add the dependency
             makeControlDependent(I);

llvm/test/Transforms/SLPVectorizer/X86/stackrestore-dependence.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt -passes=slp-vectorizer -slp-threshold=-999 -mtriple=x86_64-unknown-linux-gnu -mcpu=skylake -S < %s | FileCheck %s
+
+; The test checks that loads should not be moved below a stackrestore boundary.
+define void @stackrestore1(ptr %out) {
+; CHECK-LABEL: @stackrestore1(
+; CHECK-NEXT:    [[STACK:%.*]] = call ptr @llvm.stacksave()
+; CHECK-NEXT:    [[LOCAL_ALLOCA:%.*]] = alloca [16 x i8], align 4
+; CHECK-NEXT:    store <4 x float> <float 0x3FF3333340000000, float 0x3FF3333340000000, float 0x3FF3333340000000, float 0x3FF3333340000000>, ptr [[LOCAL_ALLOCA]], align 4
+; CHECK-NEXT:    [[TMP1:%.*]] = load <4 x float>, ptr [[LOCAL_ALLOCA]], align 4
+; CHECK-NEXT:    call void @llvm.stackrestore(ptr [[STACK]])
+; CHECK-NEXT:    [[SHUFFLE:%.*]] = shufflevector <4 x float> [[TMP1]], <4 x float> poison, <4 x i32> <i32 2, i32 3, i32 0, i32 1>
+; CHECK-NEXT:    store <4 x float> [[SHUFFLE]], ptr [[OUT:%.*]], align 4
+; CHECK-NEXT:    ret void
+;
+  %stack = call ptr @llvm.stacksave()
+  %local_alloca = alloca [16 x i8], align 4
+  store float 0x3FF3333340000000, ptr %local_alloca, align 4
+  %addr1 = getelementptr inbounds i8, ptr %local_alloca, i64 4
+  store float 0x3FF3333340000000, ptr %addr1, align 4
+  %addr2 = getelementptr inbounds i8, ptr %local_alloca, i64 8
+  store float 0x3FF3333340000000, ptr %addr2, align 4
+  %addr3 = getelementptr inbounds i8, ptr %local_alloca, i64 12
+  store float 0x3FF3333340000000, ptr %addr3, align 4
+  %val0 = load float, ptr %local_alloca, align 4
+  %val1 = load float, ptr %addr1, align 4
+  %val2 = load float, ptr %addr2, align 4
+  %val3 = load float, ptr %addr3, align 4
+  call void @llvm.stackrestore(i8* %stack)
+  %outaddr2 = getelementptr inbounds float, ptr %out, i64 2
+  store float %val0, ptr %outaddr2, align 4
+  %outaddr3 = getelementptr inbounds float, ptr %out, i64 3
+  store float %val1, ptr %outaddr3, align 4
+  store float %val2, ptr %out
+  %outaddr1 = getelementptr inbounds float, ptr %out, i64 1
+  store float %val3, ptr %outaddr1, align 4
+  ret void
+}
+
+declare i8* @llvm.stacksave()
+declare void @llvm.stackrestore(i8*)