Win ARM64 prolog prevents use of packed unwind info

[LouisLaf]

The prolog for Win ARM64 functions allocates stacks for the parameter home area and locals with a single SUB. While this sometimes results in 1 less instruction in the prolog, it does prevent taking advantage of the packed unwind data format.

For example, for this test case:

extern void bar(int*);
int foo(int x)
{
    int z;
    bar(&z);
    return x+z;
}

LLVM emits this prolog:

sub         sp,sp,#0x20
str         x19,[sp,#0x10]
str         lr,[sp,#0x18]

This results in an unpacked unwind info record.

Emitting this prolog instead:

sub         sp,sp,#0x10
stp         x19,lr,[sp]
sub         sp,sp,#0x10

Would allow to take advantage of the packed unwind data format according to https://learn.microsoft.com/en-us/cpp/build/arm64-exception-handling

Using packed records reduce the size of the unwind information in rdata significantly and improves the speed of stack walking.

[llvmbot]

@llvm/issue-subscribers-backend-aarch64

Author: Louis Lafreniere (LouisLaf)

The prolog for Win ARM64 functions allocates stacks for the parameter home area and locals with a single SUB. While this sometimes results in 1 less instruction in the prolog, it does prevent taking advantage of the packed unwind data format.

For example, for this test case:
extern void bar(int*);

int foo(int x)
{
    int z;
    bar(&z);
    return x+z;
}

LLVM emits this prolog:

sub         sp,sp,#<!-- -->0x20
str         x19,[sp,#<!-- -->0x10]
str         lr,[sp,#<!-- -->0x18]

This results in an unpacked unwind info record.

Emitting this prolog instead:

sub         sp,sp,#<!-- -->0x10
stp         x19,lr,[sp]
sub         sp,sp,#<!-- -->0x10

Would allow to take advantage of the packed unwind data format according to https://learn.microsoft.com/en-us/cpp/build/arm64-exception-handling

Using packed records reduce the size of the unwind information in rdata significantly and improves the speed of stack walking.

[efriedma-quic]

LLVM doesn't actually understand this specific packed encoding. 7a91dad makes us decode it as INVALID!. @mstorsjo do you remember why you said "the unwinder doesn't support this"? CC @pmsjt

Assuming we fix the LLVM assembler/disassembler to actually handle this, how often does this opportunity to emit packed unwind actually come up? You need to have frame pointers disabled, and have a function which saves lr plus exactly one integer register, plus nothing else which requires xdata.

[pmsjt]

This is inaccurate. If anything there are more cases where FP-linked functions are encodable with the compact format than without (e.g the PAC case is only encodable with FP-link). Also, it is possible to save a varied amount of GP and FP registers.

[mstorsjo]

@mstorsjo do you remember why you said "the unwinder doesn't support this"? CC @pmsjt

I discussed a bunch of Windows unwinder bugs with @ThomsonTan in August-September 2020; they did confirm a couple of the other unwinder bugs that I did encounter (and said that those particular bugs were going to be fixed in upcoming versions), but I didn't actually get any feedback on this particular bug.

My testcase for the situation looks like this:

#include <windows.h>
#include <stdio.h>

#define DW(dword) (((dword) >> 0) & 0xff), (((dword) >> 8) & 0xff), (((dword) >> 16) & 0xff), (((dword) >> 24) & 0xff)

#pragma section(".text")
#pragma section(".xdata", read)
__declspec(allocate(".text"))
static const BYTE CR1_RegI1_func[] = {
    0xf3, 0x7b, 0xbf, 0xa9,   /* 00: stp x19, lr,  [sp, #-16]! */
    0xff, 0x43, 0x00, 0xd1,   /* 04: sub sp,  sp,  #16 */
    0x1f, 0x20, 0x03, 0xd5,   /* 08: nop */
    0xff, 0x43, 0x00, 0x91,   /* 0c: add sp,  sp,  #16 */
    0xf3, 0x7b, 0xc1, 0xa8,   /* 10: ldp x19, lr,  [sp], #16 */
    0xc0, 0x03, 0x5f, 0xd6,   /* 14: ret */
};

static const DWORD CR1_RegI1_info = 0x01210019; // RegF 0 RegI 1 CR 1 FrameSize 2

extern const IMAGE_DOS_HEADER __ImageBase;

static void do_unwind(const BYTE *code, const DWORD unwind_info, int offset, const char *name) {
    RUNTIME_FUNCTION runtime_function;
    runtime_function.BeginAddress = code - (PUCHAR)&__ImageBase;
    runtime_function.UnwindData = unwind_info;
    ULONG64 stack[1000];
    CONTEXT context;
    ULONG64 unset, frame;
    void *data = (void*) (UINT_PTR)0xffffffff;
    KNONVOLATILE_CONTEXT_POINTERS context_pointers;
    memset(&stack, 0x33, sizeof(stack));
    memset(&context, 0xaa, sizeof(context));
    memset(&unset, 0xaa, sizeof(unset));

    context.ContextFlags = CONTEXT_FULL;
    context.Pc = (DWORD64) (code + offset);
    context.Sp = (DWORD64) stack;

    RtlVirtualUnwind(UNW_FLAG_EHANDLER, (DWORD64)(UINT_PTR)&__ImageBase, (DWORD64)(code + offset), &runtime_function, &context, &data, &frame, &context_pointers);

    printf("%s offset 0x%x: Sp adjusted 0x%x bytes\n", name, offset, (int)(context.Sp - (DWORD64) stack));
}

int main(int argc, char **argv) {
    printf("Bug: Unwinding misses one frame of stack adjustment; should be adjusted by 0x20 bytes\n");
    do_unwind(CR1_RegI1_func, CR1_RegI1_info, 0x08, "CR1_RegI1");
    return 0;
}

Here I have a test function (defined in a BYTE array) and a corresponding packed unwind info for it, defined manually. I point RtlVirtualUnwind to this, and ask it to unwind from a specific offset in the function, and inspect how much it updates context.Sp.

Given a function like this:

func:
     stp x19, lr [sp #-16]!
     sub sp, sp, #16
     ...

This should intuitively be possible to express as packed unwind info, with CR=01, RegI=1, FrameSize=2.

However in this case, when trying to unwind this case with RtlVirtualUnwind, from an offset of 8 bytes, 2 instructions, we get Sp incremented by only 16, not 32 as would be expected. (I've re-verified this issue on 10.0.26200.6899.)

Therefore, I concluded that this combination, of CR=01, RegI=1, was buggy and probably not supported.

Also, the documentation at https://learn.microsoft.com/en-us/cpp/build/arm64-exception-handling?view=msvc-170#packed-unwind-data doesn't really mention this particular case at all. It does say:

If CR == 01 and RegI is an odd number, step 3 and the last save_reg in step 2 are merged into one save_regp.

If we have RegI > 2, then step 2 consists of 1 save_regp_x and one or more save_regp/save_reg. And for the case with CR == 01 and odd RegI, then the store of lr gets merged into the last save_reg of step 2, making it a save_lrpair unwind opcode.

Now for RegI == 1, then the instruction is stp x19, lr [sp #-16]!, so it would be an unwind opcode like save_lrpair_x, which does not exist. So this case is not expressible in the full xdata form of unwind info.

Now I'd agree that it would be the only logical thing to do, to interpret this case of packed unwind info this way anyway - but as the Windows unwinder doesn't actually seem to handle that correctly, I chose to label it as invalid/unsupported.

---

Then secondly, even if the packed unwind info format can/could express things that aren't expressible with the regular unwind opcodes, LLVM wouldn't easily end up producing such packed info anyway, because we initially emit the full set of unwind opcodes for the prologues, and then do pattern matching on top of that, if the generated prologue and set of opcodes does match a packed form.

[mstorsjo]

For example, for this test case:

extern void bar(int*);
int foo(int x)
{
    int z;
    bar(&z);
    return x+z;
}

LLVM emits this prolog:

sub         sp,sp,#0x20
str         x19,[sp,#0x10]
str         lr,[sp,#0x18]

I haven't tracked the behaviour here lately, but back when I did work on this, we did match the canonical layout for packed unwind info in a number of cases - but clearly not in this one.

Emitting this prolog instead:

sub         sp,sp,#0x10
stp         x19,lr,[sp]
sub         sp,sp,#0x10

Would allow to take advantage of the packed unwind data format according to https://learn.microsoft.com/en-us/cpp/build/arm64-exception-handling

Can you explain which form of the packed unwind info you think that this form can be expressed as? According to https://learn.microsoft.com/en-us/cpp/build/arm64-exception-handling?view=msvc-170#packed-unwind-data there's no combination of parameters that has a separate sub sp instruction before storing the callee saved registers (in step 2). We only generate packed unwind info if the instructions exactly match the canonical prologue (it's not enough that the layout in the end matches), in order for unwinding through partial prologues to be exact and correct.

Now as discussed in the other posts, this could logically match the canonical packed format if you'd make it

stp         x19,lr,[sp, #-16]!
sub         sp,sp,#0x10

for RegI=1, CR=01, FrameSize=2. But as discussed in the other comment, this combination seems buggy in Windows so we declare it invalid when dissecting such info in llvm-readobj, and it is not expressible with the full unwind opcodes, so we can't generate it (as we pass everything through full unwind opcodes before potentially making them packed in the end).

[pmsjt]

    fnent_pdata.Flag = PdataPackedUnwindFunction;
    fnent_pdata.RegF = 0;
    fnent_pdata.RegI = 1;
    fnent_pdata.H = 0;
    fnent_pdata.CR = PdataCrUnchainedSavedLr;
    fnent_pdata.FrameSize = 2;

expands to

end
alloc_s         (16)
save_lrpair     (x19)
alloc           (16)

which matches the canonical format described here:

https://learn.microsoft.com/en-us/cpp/build/arm64-exception-handling?view=msvc-170#arm64-stack-frame-layout

for the case "Only x19 saved".

    sub    sp,sp,#16                // reg save area allocation*
    stp    x19,lr,[sp]              // save x19, lr
    sub    sp,sp,#(framesz-16)      // allocate the remaining local area

Note that even in the expanded format, there is no save_lrpair_x unwind opcode - only save_lrpair. This means you can't save LR with another GP register with a register-writeback store pair.

[mstorsjo]

    fnent_pdata.Flag = PdataPackedUnwindFunction;
    fnent_pdata.RegF = 0;
    fnent_pdata.RegI = 1;
    fnent_pdata.H = 0;
    fnent_pdata.CR = PdataCrUnchainedSavedLr;
    fnent_pdata.FrameSize = 2;

expands to

end
alloc_s         (16)
save_lrpair     (x19)
alloc           (16)

which matches the canonical format described here:

https://learn.microsoft.com/en-us/cpp/build/arm64-exception-handling?view=msvc-170#arm64-stack-frame-layout

for the case "Only x19 saved".

    sub    sp,sp,#16                // reg save area allocation*
    stp    x19,lr,[sp]              // save x19, lr
    sub    sp,sp,#(framesz-16)      // allocate the remaining local area

Right - I see; I stand corrected. I guess one should see this if reading the full document from top to bottom; however when reading specifically the expansion from packed format to unwind codes, with the table at https://learn.microsoft.com/en-us/cpp/build/arm64-exception-handling?view=msvc-170#packed-unwind-data, it's not very obvious that all other cases of packed unwind info do follow that table, strictly, but this one case deviates from it. It would be very good with a footnote below that table to point out this special case.

Note that even in the expanded format, there is no save_lrpair_x unwind opcode - only save_lrpair. This means you can't save LR with another GP register with a register-writeback store pair.

Indeed, I've noted that. However, it was unclear to me whether the unwinder internally always maps everything to opcodes, or if the packed unwind info format could express things that weren't possible with the opcodes. Given the table for what packed unwind info corresponds to (without any reference to the list of canonical prologues at the top of the document), it felt more in line to expect an stp with writeback.

But now we know; I'll update llvm-readobj to print this case correctly, to correct my mistake.

I might leave updating tryARM64PackedUnwind to try to match this case for someone else. And adjusting the prolog code generation to try to strive for generating this case as well...

[pmsjt]

Thank you @mstorsjo . Yes, internally, when provided with compressed format, the unwinder will expand it first and then process the expanded unwind opcodes. There are engineering advantages to this.

The corollary is that Compressed is always a strict subset of Expanded.

[pmsjt]

... and I agree with you. I want to reorganize the documentation, so it focusses first and foremost on the Expanded format and then frames the Compact format in terms of how it expands as opposite to giving it a confusing first-class citizen stage.

[pmsjt]

I also want to point out that we (in Windows) discourage the use of non-FP-link code. There is no measurable advantage to it and it defeats proper performance work, such as profiling. It is inevitable that you'll see more focus and flexibility for FP-linked codegen than non-FP-link.