Fix dynamic probing scheme

[serge-sans-paille]

Summary

If we probe *after* each static stack allocation, we need to probe *before* each
dynamic stack allocation. Provide a scheme to describe the possible scenario.

Thanks a lot to @jonpa for motivating this fix.

[serge-sans-paille]

@craig.topper ping?

[craig.topper]

LGTM

[serge-sans-paille]

Thanks o/

llvm/lib/Target/X86/X86ISelLowering.cpp

BuildMI(testMBB, DL,
       .addReg(FinalStackPtr);
 
   BuildMI(testMBB, DL, TII->get(X86::JCC_1))
       .addMBB(tailMBB)
       .addImm(X86::COND_L);
   testMBB->addSuccessor(blockMBB);
   testMBB->addSuccessor(tailMBB);
 
-  // allocate a block and touch it
+  // Touch the block then extend it. This is done on the opposite side of
+  // static probe where we allocate then touch, to avoid the need of probing the
+  // tail of the static alloca. Possible scenarios are:
+  //
+  //       + ---- <- ------------ <- ------------- <- ------------ +
+  //       |                                                       |
+  // [free probe] -> [page alloc] -> [alloc probe] -> [tail alloc] + -> [dyn probe] -> [page alloc] -> [dyn probe] -> [tail alloc] +
+  //                                                               |                                                               |
+  //                                                               + <- ----------- <- ------------ <- ----------- <- ------------ +
+  //
+  // The property we want to enforce is to never have more than [page alloc] between two probes.
+
+  const unsigned MovMIOpc =
+      TFI.Uses64BitFramePtr ? X86::MOV64mi32 : X86::MOV32mi;
+  addRegOffset(BuildMI(blockMBB, DL, TII->get(MovMIOpc)), physSPReg, false, 0)
+      .addImm(0);
 
   BuildMI(blockMBB, DL,
           TII->get(getSUBriOpcode(TFI.Uses64BitFramePtr, ProbeSize)), physSPReg)
       .addReg(physSPReg)
       .addImm(ProbeSize);
 
-  const unsigned MovMIOpc =
-      TFI.Uses64BitFramePtr ? X86::MOV64mi32 : X86::MOV32mi;
-  addRegOffset(BuildMI(blockMBB, DL, TII->get(MovMIOpc)), physSPReg, false, 0)
-      .addImm(0);
 
   BuildMI(blockMBB, DL, TII->get(X86::JMP_1)).addMBB(testMBB);
   blockMBB->addSuccessor(testMBB);
 
   // Replace original instruction by the expected stack ptr
   BuildMI(tailMBB, DL, TII->get(TargetOpcode::COPY), MI.getOperand(0).getReg())
       .addReg(FinalStackPtr);
 

llvm/test/CodeGen/X86/stack-clash-dynamic-alloca.ll

 ; CHECK-X86-64-NEXT:    movq    %rsp, %rax
 ; CHECK-X86-64-NEXT:    movl    %edi, %ecx
 ; CHECK-X86-64-NEXT:    leaq 15(,%rcx,4), %rcx
 ; CHECK-X86-64-NEXT:    andq  $-16, %rcx
 ; CHECK-X86-64-NEXT:    subq  %rcx, %rax
 ; CHECK-X86-64-NEXT:    cmpq  %rax, %rsp
 ; CHECK-X86-64-NEXT:    jl  .LBB0_3
 ; CHECK-X86-64-NEXT:  .LBB0_2: # =>This Inner Loop Header: Depth=1
-; CHECK-X86-64-NEXT:    subq  $4096, %rsp # imm = 0x1000
 ; CHECK-X86-64-NEXT:    movq  $0, (%rsp)
+; CHECK-X86-64-NEXT:    subq  $4096, %rsp # imm = 0x1000
 ; CHECK-X86-64-NEXT:    cmpq  %rax, %rsp
 ; CHECK-X86-64-NEXT:    jge .LBB0_2
 ; CHECK-X86-64-NEXT:  .LBB0_3:
 ; CHECK-X86-64-NEXT:    movq  %rax, %rsp
 ; CHECK-X86-64-NEXT:    movl  $1, 4792(%rax)
 ; CHECK-X86-64-NEXT:    movl  (%rax), %eax
 ; CHECK-X86-64-NEXT:    movq  %rbp, %rsp
 ; CHECK-X86-64-NEXT:    popq  %rbp

 ; CHECK-X86-32-NEXT:    movl    8(%ebp), %ecx
 ; CHECK-X86-32-NEXT:    movl    %esp, %eax
 ; CHECK-X86-32-NEXT:    leal    15(,%ecx,4), %ecx
 ; CHECK-X86-32-NEXT:    andl    $-16, %ecx
 ; CHECK-X86-32-NEXT:    subl    %ecx, %eax
 ; CHECK-X86-32-NEXT:    cmpl    %eax, %esp
 ; CHECK-X86-32-NEXT:    jl  .LBB0_3
 ; CHECK-X86-32-NEXT:  .LBB0_2: # =>This Inner Loop Header: Depth=1
-; CHECK-X86-32-NEXT:    subl    $4096, %esp # imm = 0x1000
 ; CHECK-X86-32-NEXT:    movl    $0, (%esp)
+; CHECK-X86-32-NEXT:    subl    $4096, %esp # imm = 0x1000
 ; CHECK-X86-32-NEXT:    cmpl    %eax, %esp
 ; CHECK-X86-32-NEXT:    jge .LBB0_2
 ; CHECK-X86-32-NEXT:  .LBB0_3:
 ; CHECK-X86-32-NEXT:    movl    %eax, %esp
 ; CHECK-X86-32-NEXT:    movl    $1, 4792(%eax)
 ; CHECK-X86-32-NEXT:    movl    (%eax), %eax
 ; CHECK-X86-32-NEXT:    movl    %ebp, %esp
 ; CHECK-X86-32-NEXT:    popl    %ebp
 ; CHECK-X86-32-NEXT:    .cfi_def_cfa %esp, 4
 ; CHECK-X86-32-NEXT:    retl