X86: Fix X86CallFrameOptimization to search for the COPY StackPointer

[zvi]

Summary

SelectionDAG inserts a copy of ESP into a virtual register.
X86CallFrameOptimization assumed that the COPY, if present, is always
right after the call-frame setup instruction (ADJCALLSTACKDOWN). This was a
wrong assumption as the COPY can be located anywhere between the call-frame setup
instruction and its first use. If the COPY happened to be located in a different
location than what X86CallFrameOptimization assumed, visiting it while
processing the call chain would lead to a conservative bail-out.

The fix is quite straightfoward, scan ahead for the stack-pointer copy and make note
of it so it can be ignored while processing the call chain.

Fixes pr34903

[zvi]

test/CodeGen/X86/movtopush.ll

231 ↗

(On Diff #118383)

Overall code size reduced by 15 bytes

297 ↗

(On Diff #118383)

The check's don't show the issue at hand, so i will explain:
With the fix, the pass now fires and replacing mov's with push's results in the following

1. Overall code size reduced by ~60 bytes
2. There is an extra overhead of resetting (with an add instruction) the frame after each call (but we still win overall in code size)

314 ↗

(On Diff #118383)

Overall code size reduced by 24 bytes

[rnk]

Thanks, looks good to me!

[zvi]

ping

[rnk]

I've already said I think this looks good, but I wasn't listed as a reviewer. Were you waiting for me or someone else on the reviewer list?

[DavidKreitzer]

Just one minor suggestion. Otherwise, this LGTM also.

lib/Target/X86/X86CallFrameOptimization.cpp

382 ↗

(On Diff #118383)

The indentation is off here, which is particularly confusing since the closing brace is aligned with the 'for'.

[zvi]

lib/Target/X86/X86CallFrameOptimization.cpp

382 ↗

(On Diff #118383)

Good catch. Will fix at commit-time.

[DavidKreitzer]

llvm/trunk/lib/Target/X86/X86CallFrameOptimization.cpp

393

I think there is a potential problem with this new loop structure. If the loop terminates by reaching MBB.end(), the code will attempt to advance the iterator beyond MBB.end(). Having the loop terminate by reaching MBB.end() is probably not an expected situation, but it seems like we should fix this regardless (unless I'm misunderstanding something).

[zvi]

llvm/trunk/lib/Target/X86/X86CallFrameOptimization.cpp

393

In general, your concern is valid as it is possible that the frame-setup,call,frame-destroy instructions be located in exclusive BB's. FWIW, MachineVerifier::verifyStackFrame checks for a weaker requirement.
However, in this pass, X86CallFrameOptimization::isLegal requires that the entire call chain be located in a single BB. See the comment starting with "You would expect straight-line code...".
I came across this dilemma when adding the loop in line 375. That code assumes we meet the call instruction before end of the BB, which is only correct under the assumption of all-in-same-BB
I made a note to do some clean-up on this pass of removing overly-conservative checks of reaching end of BB. And of course, we should consider improving this pass to handle the multi-BB call chains.

llvm/trunk/lib/Target/X86/X86CallFrameOptimization.cpp

void X86CallFrameOptimization::collectCallInfo(MachineFunction &MF,
 
   // Skip over DEBUG_VALUE.
   // For globals in PIC mode, we can have some LEAs here. Skip them as well.
   // TODO: Extend this to something that covers more cases.
   while (I->getOpcode() == X86::LEA32r || I->isDebugValue())
     ++I;
 
   unsigned StackPtr = RegInfo.getStackRegister();
+  auto StackPtrCopyInst = MBB.end();
   // SelectionDAG (but not FastISel) inserts a copy of ESP into a virtual
-  // register here.  If it's there, use that virtual register as stack pointer
-  // instead.
-  if (I->isCopy() && I->getOperand(0).isReg() && I->getOperand(1).isReg() &&
-      I->getOperand(1).getReg() == StackPtr) {
-    Context.SPCopy = &*I++;
+  // register.  If it's there, use that virtual register as stack pointer
+  // instead. Also, we need to locate this instruction so that we can later
+  // safely ignore it while doing the conservative processing of the call chain.
+  // The COPY can be located anywhere between the call-frame setup
+  // instruction and its first use. We use the call instruction as a boundary
+  // because it is usually cheaper to check if an instruction is a call than
+  // checking if an instruction uses a register.
+  for (auto J = I; !J->isCall(); ++J)
+    if (J->isCopy() && J->getOperand(0).isReg() && J->getOperand(1).isReg() &&
+        J->getOperand(1).getReg() == StackPtr) {
+      StackPtrCopyInst = J;
+      Context.SPCopy = &*J++;
       StackPtr = Context.SPCopy->getOperand(0).getReg();
+      break;
     }
 
   // Scan the call setup sequence for the pattern we're looking for.
   // We only handle a simple case - a sequence of store instructions that
   // push a sequence of stack-slot-aligned values onto the stack, with
   // no gaps between them.
   if (MaxAdjust > 4)
     Context.MovVector.resize(MaxAdjust, nullptr);
 
-  InstClassification Classification;
   DenseSet<unsigned int> UsedRegs;
 
-  while ((Classification = classifyInstruction(MBB, I, RegInfo, UsedRegs)) !=
-         Exit) {
-    if (Classification == Skip) {
-      ++I;
+  for (InstClassification Classification = Skip; Classification != Exit; ++I) {
+    // If this is the COPY of the stack pointer, it's ok to ignore.
+    if (I == StackPtrCopyInst)
+      continue;
+    Classification = classifyInstruction(MBB, I, RegInfo, UsedRegs);
+    if (Classification != Convert)
       continue;
-    }
-
     // We know the instruction has a supported store opcode.
     // We only want movs of the form:
     // mov imm/reg, k(%StackPtr)
     // If we run into something else, bail.
     // Note that AddrBaseReg may, counter to its name, not be a register,
     // but rather a frame index.
     // TODO: Support the fi case. This should probably work now that we
     // have the infrastructure to track the stack pointer within a call
for (InstClassification Classification = Skip; Classification != Exit; ++I) {
 
     for (const MachineOperand &MO : I->uses()) {
       if (!MO.isReg())
         continue;
       unsigned int Reg = MO.getReg();
       if (RegInfo.isPhysicalRegister(Reg))
         UsedRegs.insert(Reg);
     }
-
-    ++I;
   }
 
+  --I;
+
   // We now expect the end of the sequence. If we stopped early,
   // or reached the end of the block without finding a call, bail.
   if (I == MBB.end() || !I->isCall())
     return;
 
   Context.Call = &*I;
   if ((++I)->getOpcode() != TII->getCallFrameDestroyOpcode())
     return;

llvm/trunk/test/CodeGen/X86/cmpxchg-clobber-flags.ll

 ; i386-NEXT: pushl %eax
 ; i386-NEXT: calll bar
 ; i386-NEXT: addl $16, %esp
 ; i386-NEXT: movl [[FLAGS]], %eax
 ; i386-NEXT: addb $127, %al
 ; i386-NEXT: sahf
 ; i386-NEXT: jne
 
+; In the following case we get a long chain of EFLAGS save/restore due to
+; a sequence of:
+; cmpxchg8b (implicit-def eflags)
+; eax = copy eflags
+; adjcallstackdown32
+; ...
+; use of eax
+; During PEI the adjcallstackdown32 is replaced with the subl which
+; clobbers eflags, effectively interfering in the liveness interval.
+; Is this a case we care about? Maybe no, considering this issue
+; happens with the fast pre-regalloc scheduler enforced. A more
+; performant scheduler would move the adjcallstackdown32 out of the
+; eflags liveness interval.
+
 ; i386f-LABEL: test_intervening_call:
 ; i386f: cmpxchg8b
-; i386f-NEXT: movl %eax, (%esp)
-; i386f-NEXT: movl %edx, 4(%esp)
-; i386f-NEXT: seto %al
+; i386f-NEXT: pushl  %eax
+; i386f-NEXT: seto  %al
 ; i386f-NEXT: lahf
-; i386f-NEXT: movl %eax, [[FLAGS:%.*]]
-; i386f-NEXT: calll bar
-; i386f-NEXT: movl [[FLAGS]], %eax
-; i386f-NEXT: addb $127, %al
+; i386f-NEXT: movl  %eax, [[FLAGS:%.*]]
+; i386f-NEXT: popl  %eax
+; i386f-NEXT: subl  $8, %esp
+; i386f-NEXT: pushl  %eax
+; i386f-NEXT: movl  %ecx, %eax
+; i386f-NEXT: addb  $127, %al
 ; i386f-NEXT: sahf
-; i386f-NEXT: jne
+; i386f-NEXT: popl  %eax
+; i386f-NEXT: pushl  %eax
+; i386f-NEXT: seto  %al
+; i386f-NEXT: lahf
+; i386f-NEXT: movl  %eax, %esi
+; i386f-NEXT: popl  %eax
+; i386f-NEXT: pushl  %edx
+; i386f-NEXT: pushl  %eax
+; i386f-NEXT: calll  bar
+; i386f-NEXT: addl  $16, %esp
+; i386f-NEXT: movl  %esi, %eax
+; i386f-NEXT: addb  $127, %al
 
 ; x8664-LABEL: test_intervening_call:
 ; x8664: cmpxchgq
 ; x8664: pushfq
 ; x8664-NEXT: popq [[FLAGS:%.*]]
 ; x8664-NEXT: movq %rax, %rdi
 ; x8664-NEXT: callq bar
 ; x8664-NEXT: pushq [[FLAGS]]

llvm/trunk/test/CodeGen/X86/movtopush.ll

 ; these references correctly.
 ; NORMAL-LABEL: test9:
 ; NORMAL-NOT: leal (%esp), 
 ; NORMAL: pushl $4
 ; NORMAL-NEXT: pushl $3
 ; NORMAL-NEXT: pushl $2
 ; NORMAL-NEXT: pushl $1
 ; NORMAL-NEXT: call
-; NORMAL-NEXT: subl $4, %esp
-; NORMAL-NEXT: movl 20(%esp), [[E1:%e..]]
-; NORMAL-NEXT: movl 24(%esp), [[E2:%e..]]
-; NORMAL-NEXT: movl    [[E2]], 4(%esp)
-; NORMAL-NEXT: movl    [[E1]], (%esp)
-; NORMAL-NEXT: leal 32(%esp), [[E3:%e..]]
-; NORMAL-NEXT: movl    [[E3]], 16(%esp)
-; NORMAL-NEXT: leal 28(%esp), [[E4:%e..]]
-; NORMAL-NEXT: movl    [[E4]], 12(%esp)
-; NORMAL-NEXT: movl    $6, 8(%esp)
+; NORMAL-NEXT: addl $16, %esp
+; NORMAL-NEXT: movl (%esp), [[E1:%e..]]
+; NORMAL-NEXT: movl 4(%esp), [[E2:%e..]]
+; NORMAL-NEXT: leal 16(%esp), [[E3:%e..]]
+; NORMAL-NEXT: leal 12(%esp), [[E4:%e..]]
+; NORMAL-NEXT: pushl   [[E3]]
+; NORMAL-NEXT: pushl   [[E4]]
+; NORMAL-NEXT: pushl   $6
+; NORMAL-NEXT: pushl   [[E2]]
+; NORMAL-NEXT: pushl   [[E1]]
 ; NORMAL-NEXT: call
 ; NORMAL-NEXT: addl $20, %esp
 define void @test9() optsize {
 entry:
   %p = alloca i32, align 4
   %q = alloca i32, align 4
   %s = alloca %struct.s, align 4  
   call void @good(i32 1, i32 2, i32 3, i32 4)
define void @test11() optsize {
   store i32 42, i32* @the_global
   call void @good(i32 %myload, i32 2, i32 3, i32 4)
   ret void
 }
 
 ; Converting one mov into a push isn't worth it when 
 ; doing so forces too much overhead for other calls.
 ; NORMAL-LABEL: test12:
-; NORMAL: movl    $8, 12(%esp)
-; NORMAL-NEXT: movl    $7, 8(%esp)
-; NORMAL-NEXT: movl    $6, 4(%esp)
-; NORMAL-NEXT: movl    $5, (%esp)
+; NORMAL:       pushl  $8
+; NORMAL-NEXT:  pushl  $7
+; NORMAL-NEXT:  pushl  $6
+; NORMAL-NEXT:  pushl  $5
 ; NORMAL-NEXT: calll _good
 define void @test12() optsize {
 entry:
   %s = alloca %struct.s, align 4  
   call void @struct(%struct.s* %s, i32 2, i32 3, i32 4)
   call void @good(i32 5, i32 6, i32 7, i32 8)
   call void @struct(%struct.s* %s, i32 10, i32 11, i32 12)
   ret void
 }
 
 ; But if the gains outweigh the overhead, we should do it
 ; NORMAL-LABEL: test12b:
 ; NORMAL: pushl    $4
 ; NORMAL-NEXT: pushl    $3
 ; NORMAL-NEXT: pushl    $2
 ; NORMAL-NEXT: pushl    $1
 ; NORMAL-NEXT: calll _good
-; NORMAL-NEXT: subl    $4, %esp
-; NORMAL: movl    $8, 16(%esp)
-; NORMAL-NEXT: movl    $7, 12(%esp)
-; NORMAL-NEXT: movl    $6, 8(%esp)
-; NORMAL-NEXT: calll _struct
-; NORMAL-NEXT: addl    $20, %esp
-; NORMAL-NEXT: pushl    $12
-; NORMAL-NEXT: pushl    $11
-; NORMAL-NEXT: pushl    $10
-; NORMAL-NEXT: pushl    $9
-; NORMAL-NEXT: calll _good
-; NORMAL-NEXT: addl $16, %esp
+; NORMAL-NEXT: addl    $16, %esp
+; NORMAL=NEXT: movl  (%esp), %eax
+; NORMAL=NEXT: movl  4(%esp), %ecx
+; NORMAL=NEXT: pushl  $8
+; NORMAL=NEXT: pushl  $7
+; NORMAL=NEXT: pushl  $6
+; NORMAL=NEXT: pushl  %ecx
+; NORMAL=NEXT: pushl  %eax
+; NORMAL=NEXT: calll  _struct
+; NORMAL=NEXT: addl  $20, %esp
+; NORMAL=NEXT: pushl  $12
+; NORMAL=NEXT: pushl  $11
+; NORMAL=NEXT: pushl  $10
+; NORMAL=NEXT: pushl  $9
+; NORMAL=NEXT: calll  _good
+; NORMAL=NEXT: addl  $16, %esp
 define void @test12b() optsize {
 entry:
   %s = alloca %struct.s, align 4  
   call void @good(i32 1, i32 2, i32 3, i32 4)  
   call void @struct(%struct.s* %s, i32 6, i32 7, i32 8)
   call void @good(i32 9, i32 10, i32 11, i32 12)
   ret void
 }

llvm/trunk/test/CodeGen/X86/movtopush.mir

 # RUN: llc -mtriple=i686-windows --run-pass="x86-cf-opt" %s -o - | FileCheck %s
 
+# PR34903
 --- |
   target datalayout = "e-m:x-p:32:32-i64:64-f80:32-n8:16:32-a:0:32-S32"
   target triple = "i686--windows-msvc"
 
   %struct.s = type { i64 }
 
   declare void @good(i32, i32, i32, i32)
 

 # CHECK-LABEL: test9
 # CHECK:      ADJCALLSTACKDOWN32 16, 0, 16, implicit-def dead %esp, implicit-def dead %eflags, implicit %esp
 # CHECK-NEXT: PUSH32i8 4, implicit-def %esp, implicit %esp
 # CHECK-NEXT: PUSH32i8 3, implicit-def %esp, implicit %esp
 # CHECK-NEXT: PUSH32i8 2, implicit-def %esp, implicit %esp
 # CHECK-NEXT: PUSH32i8 1, implicit-def %esp, implicit %esp
 # CHECK-NEXT: CALLpcrel32 @good, csr_32, implicit %esp, implicit-def %esp
 # CHECK-NEXT: ADJCALLSTACKUP32 16, 0, implicit-def dead %esp, implicit-def dead %eflags, implicit %esp
-# CHECK-NEXT: ADJCALLSTACKDOWN32 20, 0, 0, implicit-def dead %esp, implicit-def dead %eflags, implicit %esp
+# CHECK-NEXT: ADJCALLSTACKDOWN32 20, 0, 20, implicit-def dead %esp, implicit-def dead %eflags, implicit %esp
 # CHECK-NEXT: %1 = MOV32rm %stack.2.s, 1, _, 0, _ :: (load 4 from %stack.2.s, align 8)
 # CHECK-NEXT: %2 = MOV32rm %stack.2.s, 1, _, 4, _ :: (load 4 from %stack.2.s + 4)
-# CHECK-NEXT: %3 = COPY %esp
-# CHECK-NEXT: MOV32mr %3, 1, _, 4, _, killed %2 :: (store 4)
-# CHECK-NEXT: MOV32mr %3, 1, _, 0, _, killed %1 :: (store 4)
 # CHECK-NEXT: %4 = LEA32r %stack.0.p, 1, _, 0, _
-# CHECK-NEXT: MOV32mr %3, 1, _, 16, _, killed %4 :: (store 4 into stack + 16)
 # CHECK-NEXT: %5 = LEA32r %stack.1.q, 1, _, 0, _
-# CHECK-NEXT: MOV32mr %3, 1, _, 12, _, killed %5 :: (store 4 into stack + 12)
-# CHECK-NEXT: MOV32mi %3, 1, _, 8, _, 6 :: (store 4 into stack + 8)
+# CHECK-NEXT: PUSH32r %4, implicit-def %esp, implicit %esp
+# CHECK-NEXT: PUSH32r %5, implicit-def %esp, implicit %esp
+# CHECK-NEXT: PUSH32i8 6, implicit-def %esp, implicit %esp
+# CHECK-NEXT: PUSH32r %2, implicit-def %esp, implicit %esp
+# CHECK-NEXT: PUSH32r %1, implicit-def %esp, implicit %esp
 # CHECK-NEXT: CALLpcrel32 @struct, csr_32, implicit %esp, implicit-def %esp
 # CHECK-NEXT: ADJCALLSTACKUP32 20, 0, implicit-def dead %esp, implicit-def dead %eflags, implicit %esp
 # CHECK-NEXT: RET 0
 name:            test9
 alignment:       0
 exposesReturnsTwice: false
 legalized:       false
 regBankSelected: false