This is an archive of the discontinued LLVM Phabricator instance.

Differential D7226

[X86] Use single add/sub for large stack offsets
ClosedPublic

Authored by rob.lougher on Jan 28 2015, 8:29 AM.

Details

Reviewers
grosbach
Commits
rGc69cfeeafa16: [X86] Use single add/sub for large stack offsets
rL227458: [X86] Use single add/sub for large stack offsets
Summary

The following code generates an object file which is over 30 MB in size:

void bar(char *a);
void foo (void) {
    char b[5000000000000000];
    bar(b);
}

The reason is that the code to push the space on the stack consists of over 2 million subtract
instructions of the form:

subq    $2147483647, %rsp       # imm = 0x7FFFFFFF

Instead of doing multiple immediate mode subtracts, the compiler should place the final amount to
be subtracted into a register and do a single subtraction.

Diff Detail

Event Timeline

rob.lougher updated this revision to Diff 18891.Jan 28 2015, 8:29 AM
rob.lougher retitled this revision from to [X86] Use single add/sub for large stack offsets.
rob.lougher updated this object.
rob.lougher edited the test plan for this revision. (Show Details)
rob.lougher added a reviewer: grosbach.
rob.lougher added a subscriber: Unknown Object (MLST).
asl added a subscriber: asl.Jan 28 2015, 9:07 AM
asl added inline comments.
lib/Target/X86/X86FrameLowering.cpp
214

This clobbers rax/eax w/o checking whether it's a livein or not. This may be a problem for functions with inreg attributes. I believe the code should always use findDeadCallerSavedReg().

rob.lougher added inline comments.Jan 28 2015, 9:53 AM
lib/Target/X86/X86FrameLowering.cpp
214

I copied that from the code that generates a push/pop (lines 223-225), so the existing code always uses rax/eax in the prologue for a push. If this is a problem for inreg attributes, this code will also need to be fixed.

asl added inline comments.Jan 28 2015, 9:57 AM
lib/Target/X86/X86FrameLowering.cpp
214

It's not a problem for push below, because we just need to put something on stack (we can use any register for this). For pop'ing stuff we need to find free register, since we're going to clobber it.

Situation here is completely different, because the code in the patch materializes a constant in the register thus clobbering it always.

rob.lougher added inline comments.Jan 28 2015, 10:29 AM
lib/Target/X86/X86FrameLowering.cpp
214

OK, point taken - in the push case it's pushing whatever value is in rax/eax (as it's just making space, the value doesn't matter). I tried changing the code to always use findDeadCallerSavedReg(), but it returns zero when used in the prologue, so we fall back to using multiple instructions (as before). I need to do some more investigation.

rob.lougher updated this revision to Diff 18956.Jan 29 2015, 7:10 AM

I have uploaded a new diff which hopefully addresses the inreg attribute issue. I have also updated the tests to include a test for it.

asl added a comment.Jan 29 2015, 7:17 AM

LGTM after the fix of the test.

test/CodeGen/X86/huge-stack-offset.ll
15

Typo? Should be CHECK-32-LABEL as I can see.

Closed by commit rL227458: [X86] Use single add/sub for large stack offsets (authored by rlougher). · Explain WhyJan 29 2015, 8:20 AM
This revision was automatically updated to reflect the committed changes.
rob.lougher added a comment.Jan 29 2015, 8:23 AM

Thanks for the review! Typo fixed, and committed in r227458.

Revision Contents

PathSize
lib/
Target/
X86/
59 lines
test/
CodeGen/
X86/
59 lines

Diff 18956

lib/Target/X86/X86FrameLowering.cpp

Show First 20 Lines • Show All 76 Lines • ▼ Show 20 Lines if (IsLP64) {
return X86::ADD64ri32; return X86::ADD64ri32;
} else { } else {
if (isInt<8>(Imm)) if (isInt<8>(Imm))
return X86::ADD32ri8; return X86::ADD32ri8;
return X86::ADD32ri; return X86::ADD32ri;
} }
} }
static unsigned getSUBrrOpcode(unsigned isLP64) {
return isLP64 ? X86::SUB64rr : X86::SUB32rr;
}
static unsigned getADDrrOpcode(unsigned isLP64) {
return isLP64 ? X86::ADD64rr : X86::ADD32rr;
}
static unsigned getANDriOpcode(bool IsLP64, int64_t Imm) { static unsigned getANDriOpcode(bool IsLP64, int64_t Imm) {
if (IsLP64) { if (IsLP64) {
if (isInt<8>(Imm)) if (isInt<8>(Imm))
return X86::AND64ri8; return X86::AND64ri8;
return X86::AND64ri32; return X86::AND64ri32;
} }
if (isInt<8>(Imm)) if (isInt<8>(Imm))
return X86::AND32ri8; return X86::AND32ri8;
▲ Show 20 Lines • Show All 67 Lines • ▼ Show 20 Lines for (; *CS; ++CS)
if (!Uses.count(*CS)) if (!Uses.count(*CS))
return *CS; return *CS;
} }
} }
return 0; return 0;
} }
static bool isEAXLiveIn(MachineFunction &MF) {
for (MachineRegisterInfo::livein_iterator II = MF.getRegInfo().livein_begin(),
EE = MF.getRegInfo().livein_end(); II != EE; ++II) {
unsigned Reg = II->first;
if (Reg == X86::RAX || Reg == X86::EAX || Reg == X86::AX ||
Reg == X86::AH || Reg == X86::AL)
return true;
}
return false;
}
/// emitSPUpdate - Emit a series of instructions to increment / decrement the /// emitSPUpdate - Emit a series of instructions to increment / decrement the
/// stack pointer by a constant value. /// stack pointer by a constant value.
static static
void emitSPUpdate(MachineBasicBlock &MBB, MachineBasicBlock::iterator &MBBI, void emitSPUpdate(MachineBasicBlock &MBB, MachineBasicBlock::iterator &MBBI,
unsigned StackPtr, int64_t NumBytes, unsigned StackPtr, int64_t NumBytes,
bool Is64BitTarget, bool Is64BitStackPtr, bool UseLEA, bool Is64BitTarget, bool Is64BitStackPtr, bool UseLEA,
const TargetInstrInfo &TII, const TargetRegisterInfo &TRI) { const TargetInstrInfo &TII, const TargetRegisterInfo &TRI) {
bool isSub = NumBytes < 0; bool isSub = NumBytes < 0;
uint64_t Offset = isSub ? -NumBytes : NumBytes; uint64_t Offset = isSub ? -NumBytes : NumBytes;
unsigned Opc; unsigned Opc;
if (UseLEA) if (UseLEA)
Opc = getLEArOpcode(Is64BitStackPtr); Opc = getLEArOpcode(Is64BitStackPtr);
else else
Opc = isSub Opc = isSub
? getSUBriOpcode(Is64BitStackPtr, Offset) ? getSUBriOpcode(Is64BitStackPtr, Offset)
: getADDriOpcode(Is64BitStackPtr, Offset); : getADDriOpcode(Is64BitStackPtr, Offset);
uint64_t Chunk = (1LL << 31) - 1; uint64_t Chunk = (1LL << 31) - 1;
DebugLoc DL = MBB.findDebugLoc(MBBI); DebugLoc DL = MBB.findDebugLoc(MBBI);
while (Offset) { while (Offset) {
if (Offset > Chunk) {
// Rather than emit a long series of instructions for large offsets,
// load the offset into a register and do one sub/add
unsigned Reg = 0;
aslUnsubmitted
Not Done
ReplyInline Actions

This clobbers rax/eax w/o checking whether it's a livein or not. This may be a problem for functions with inreg attributes. I believe the code should always use findDeadCallerSavedReg().

asl: This clobbers rax/eax w/o checking whether it's a livein or not. This may be a problem for…
rob.lougherAuthorUnsubmitted
Not Done
ReplyInline Actions

I copied that from the code that generates a push/pop (lines 223-225), so the existing code always uses rax/eax in the prologue for a push. If this is a problem for inreg attributes, this code will also need to be fixed.

rob.lougher: I copied that from the code that generates a push/pop (lines 223-225), so the existing code…
aslUnsubmitted
Not Done
ReplyInline Actions

It's not a problem for push below, because we just need to put something on stack (we can use any register for this). For pop'ing stuff we need to find free register, since we're going to clobber it.

Situation here is completely different, because the code in the patch materializes a constant in the register thus clobbering it always.

asl: It's not a problem for push below, because we just need to put something on stack (we can use…
rob.lougherAuthorUnsubmitted
Not Done
ReplyInline Actions

OK, point taken - in the push case it's pushing whatever value is in rax/eax (as it's just making space, the value doesn't matter). I tried changing the code to always use findDeadCallerSavedReg(), but it returns zero when used in the prologue, so we fall back to using multiple instructions (as before). I need to do some more investigation.

rob.lougher: OK, point taken - in the push case it's pushing whatever value is in rax/eax (as it's just…
if (isSub && !isEAXLiveIn(*MBB.getParent()))
Reg = (unsigned)(Is64BitTarget ? X86::RAX : X86::EAX)
else
Reg = findDeadCallerSavedReg(MBB, MBBI, TRI, Is64BitTarget);
if (Reg) {
Opc = Is64BitTarget ? X86::MOV64ri : X86::MOV32ri;
BuildMI(MBB, MBBI, DL, TII.get(Opc), Reg)
.addImm(Offset);
Opc = isSub
? getSUBrrOpcode(Is64BitTarget)
: getADDrrOpcode(Is64BitTarget);
MachineInstr *MI = BuildMI(MBB, MBBI, DL, TII.get(Opc), StackPtr)
.addReg(StackPtr)
.addReg(Reg);
MI->getOperand(3).setIsDead(); // The EFLAGS implicit def is dead.
Offset = 0;
continue;
}
}
uint64_t ThisVal = (Offset > Chunk) ? Chunk : Offset; uint64_t ThisVal = (Offset > Chunk) ? Chunk : Offset;
if (ThisVal == (Is64BitTarget ? 8 : 4)) { if (ThisVal == (Is64BitTarget ? 8 : 4)) {
// Use push / pop instead. // Use push / pop instead.
unsigned Reg = isSub unsigned Reg = isSub
? (unsigned)(Is64BitTarget ? X86::RAX : X86::EAX) ? (unsigned)(Is64BitTarget ? X86::RAX : X86::EAX)
: findDeadCallerSavedReg(MBB, MBBI, TRI, Is64BitTarget); : findDeadCallerSavedReg(MBB, MBBI, TRI, Is64BitTarget);
if (Reg) { if (Reg) {
Opc = isSub Opc = isSub
▲ Show 20 Lines • Show All 113 Lines • ▼ Show 20 Lines if ((Opc == X86::ADD64ri32 || Opc == X86::ADD64ri8 ||
Offset -= PI->getOperand(2).getImm(); Offset -= PI->getOperand(2).getImm();
MBB.erase(PI); MBB.erase(PI);
if (!doMergeWithPrevious) MBBI = NI; if (!doMergeWithPrevious) MBBI = NI;
} }
return Offset; return Offset;
} }
static bool isEAXLiveIn(MachineFunction &MF) {
for (MachineRegisterInfo::livein_iterator II = MF.getRegInfo().livein_begin(),
EE = MF.getRegInfo().livein_end(); II != EE; ++II) {
unsigned Reg = II->first;
if (Reg == X86::EAX || Reg == X86::AX ||
Reg == X86::AH || Reg == X86::AL)
return true;
}
return false;
}
void void
X86FrameLowering::emitCalleeSavedFrameMoves(MachineBasicBlock &MBB, X86FrameLowering::emitCalleeSavedFrameMoves(MachineBasicBlock &MBB,
MachineBasicBlock::iterator MBBI, MachineBasicBlock::iterator MBBI,
DebugLoc DL) const { DebugLoc DL) const {
MachineFunction &MF = *MBB.getParent(); MachineFunction &MF = *MBB.getParent();
MachineFrameInfo *MFI = MF.getFrameInfo(); MachineFrameInfo *MFI = MF.getFrameInfo();
MachineModuleInfo &MMI = MF.getMMI(); MachineModuleInfo &MMI = MF.getMMI();
const MCRegisterInfo *MRI = MMI.getContext().getRegisterInfo(); const MCRegisterInfo *MRI = MMI.getContext().getRegisterInfo();
▲ Show 20 Lines • Show All 1,695 Lines • Show Last 20 Lines

test/CodeGen/X86/huge-stack-offset.ll

; RUN: llc < %s -mtriple=x86_64-linux-unknown | FileCheck %s --check-prefix=CHECK-64
; RUN: llc < %s -mtriple=i386-linux-unknown | FileCheck %s --check-prefix=CHECK-32
; Test that a large stack offset uses a single add/sub instruction to
; adjust the stack pointer.
define void @foo() nounwind {
; CHECK-64-LABEL: foo:
; CHECK-64: movabsq $50000000{{..}}, %rax
; CHECK-64-NEXT: subq %rax, %rsp
; CHECK-64-NOT: subq $2147483647, %rsp
; CHECK-64: movabsq $50000000{{..}}, [[RAX:%r..]]
; CHECK-64-NEXT: addq [[RAX]], %rsp
; CHECK=32-LABEL: foo:
aslUnsubmitted
Not Done
ReplyInline Actions

Typo? Should be CHECK-32-LABEL as I can see.

asl: Typo? Should be CHECK-32-LABEL as I can see.
; CHECK-32: movl $50000000{{..}}, %eax
; CHECK-32-NEXT: subl %eax, %esp
; CHECK-32-NOT: subl $2147483647, %esp
; CHECK-32: movl $50000000{{..}}, [[EAX:%e..]]
; CHECK-32-NEXT: addl [[EAX]], %esp
%1 = alloca [5000000000 x i8], align 16
%2 = getelementptr inbounds [5000000000 x i8]* %1, i32 0, i32 0
call void @bar(i8* %2)
ret void
}
; Verify that we do not clobber the return value.
define i32 @foo2() nounwind {
; CHECK-64-LABEL: foo2:
; CHECK-64: movl $10, %eax
; CHECK-64-NOT: movabsq ${{.*}}, %rax
; CHECK-32-LABEL: foo2:
; CHECK-32: movl $10, %eax
; CHECK-32-NOT: movl ${{.*}}, %eax
%1 = alloca [5000000000 x i8], align 16
%2 = getelementptr inbounds [5000000000 x i8]* %1, i32 0, i32 0
call void @bar(i8* %2)
ret i32 10
}
; Verify that we do not clobber EAX when using inreg attribute
define i32 @foo3(i32 inreg %x) nounwind {
; CHECK-64-LABEL: foo3:
; CHECK-64: movabsq $50000000{{..}}, %rax
; CHECK-64-NEXT: subq %rax, %rsp
; CHECK-32-LABEL: foo3:
; CHECK-32: subl $2147483647, %esp
; CHECK-32-NOT: movl ${{.*}}, %eax
%1 = alloca [5000000000 x i8], align 16
%2 = getelementptr inbounds [5000000000 x i8]* %1, i32 0, i32 0
call void @bar(i8* %2)
ret i32 %x
}
declare void @bar(i8*)