20

I would like to understand historical roots of the quirk in the SysV calling convention for the 32-bit x86, which was inherited by the ELF standard, and so remains used on Linux to this day. Consider this example:

struct S {
    int i;
};

struct S f(int a)
{
    struct S r = { a };
    return r;
}

Optimized assembly output for i386 ELF target will be, in Intel syntax:

f:
        mov     eax, DWORD PTR [esp+4]
        mov     edx, DWORD PTR [esp+8]
        mov     DWORD PTR [eax], edx
        ret     4

The return address of the function is at [esp], and the argument a is at [esp+8], which is retrieved into edx by the second instruction. The first instruction reads the 'hidden' extra argument at [esp+4] into eax.

The hidden argument is set up by the caller to indicate where the returned struct must be stored (it will be a location on the caller's stack). The third instruction writes a into that location, and the last instruction, ret 4, returns to the caller and also pops the hidden argument off the stack (i.e. it pops two words, the return address, and the extra argument, increasing esp by 8 in total). This is the only instance where the use of return-with-immediate instruction is required by the i386 ELF psABI.

Essentially, the function is compiled as if it was internally transformed into

struct S *f(struct S *r, int a)
{
    r->i = a;
    return r;
}

... except for the automagic popping of the implicit first argument.

Before Linux adopted ELF, GCC's original calling convention (now known as the a.out format) used a more natural approach where the caller was responsible for popping the implicit argument together with the rest, and short structures like in this example would be returned on registers. The calling convention for 64-bit x86 is efficient as well.

So, modern GCC ended up with an inefficient convention for struct return on 32-bit x86 because that's what was set in stone by the i386 processor supplement of the ELF standard. And the psABI document, presumably, documented how one of the important UNIX compilers of that time behaved. Was that the AT&T compiler? And why did it behave that way? What is the lineage of the compiler(s) that influenced the ELF standardization?

My speculation: it was not a deliberate decision, the i386 port of the AT&T compiler inherited that quirk from an older port, and nobody bothered to correct it. And that older port, in turn, evolved in a way where initially structures were returned via static locations rather than on stack, and the trick with popping a hidden argument allowed to bridge old and new code when the stack-based returning was implemented.

6
  • 4
    I love a question like this that explains things clearly and teaches me possibly more than the answer will. Jan 7 at 17:28
  • I fail to see why you call it 'inefficient'. If the struct is returned, it ends up being put to the memory anyway -- no matter whether it is done by caller or callee. Here the callee does that, in amd64 the caller would do.
    – lvd
    Jan 8 at 19:35
  • @lvd although I wouldn't mind editing the question to say something like 'unnatural' rather than 'inefficient', the reason for that is twofold: the stack pointer ends up adjusted twice (the caller pops the remaining arguments), and there's no provision for returning short structs on registers (like on legacy a.out or amd64, where edx:eax register pair can be used to return a struct that fits in two machine words); I don't understand what 'the caller would do' in your statement
    – amonakov
    Jan 8 at 20:32
  • Note that adjusting the stack pointer twice is not inefficient: on an 80386 and 80486 (the only 32-bit x86 processors available or due to be released in the near future at the time the standard was written) ret and ret n take exactly the same number of cycles. Also note that in the case where there are no other arguments, the caller will not need to adjust the stack, so it is more efficient in this instance.
    – occipita
    Mar 11 at 19:33
  • Returning small structs in memory is terrible regardless of ret vs. ret 4, compared to returning in EDX:EAX (or just EAX if narrow enough), as your example demonstrates, especially for the common case where the member(s) are 32-bit. x86-64 SysV returns structs up to 16 bytes in RDX:RAX, ready for the caller to store if it wants, or unpack with shifts. (Unfortunately x86 doesn't have very good bit-manipulation, not able to shift-and-mask in a single instruction to extract a bitfield, so it can get inefficient with multiple small members.) Mar 17 at 22:26

2 Answers 2

11

The GNU compiler calls the hidden parameter and memory based struct return "pcc-struct-return". PCC was the "Portable C compiler" that appeared in V7 Unix (although I don't see struct return in that version).

On the Intel side the SYS5 Unix standard binary ABI was iBCS and then iBCS2. That has a book which might give some insights. Its origins are from Intel, AT&T and SCO which would imply pcc influenced. iBCS covered 32bit Intel 80x86 only.

Digging into the archives by 3BSD the pcc/local2.c has struct returns by allocating space on the stack and passing a hidden argument indicating where the return is to go.

That PCC behaviour was present by 1979 so the standard struct return behaviour most people use was established well before the '286, and possibly with further archive spelunking before the 8086.

As an aside it was very normal for early compilers to keep working stuff on the stack because many of them didn't have many registers. Thus it was common to have helpers for things like long types that popped four words off the stack, added them and pushed the resulting two back. In that context the struct return makes total sense.

3
  • Thanks. To clarify, my main question is about the ret 4 vs. ret, i.e. popping the invisible pointer on the callee side, not about passing even small structs on the stack. Do you think use of ret 4 on x86 is related to how struct return was compiled for other targets (i.e. if everywhere else the invisible pointer was passed on a register, there would be no difference in how much the caller would need to pop, and in that light the x86 hack starts making sense to me).
    – amonakov
    Mar 8 at 21:53
  • Most targets the source code isn't available (pcc was extensively licensed but only some of the unix code is public). Very few targets could afford to waste a whole register on a hidden struct return. I don't see any fundamental reason a given pcc target couldn't have done it either way - the information appears to be present where needed. On the 80x86 side RET and RET n are both the same number of clocks before the 386
    – Alan Cox
    Mar 9 at 0:26
  • Michal Necasek kindly answered me on the os2museum blog regarding what the iBCS2 book says about the matter. I quite agree with his "The scheme seems frankly a bit bizarre."
    – amonakov
    Apr 19 at 17:18
2

This is speculative, but it will probably be too long to put into a comment.

Your reasoning seems logical but, putting myself into the shoes of compiler designers in the late 80's/early 90's I think I can justify the decisions taken. What you need to think about is that your example is atypical in two ways:

  1. you have a struct containing only one member - an int.
  2. you have a function that merely wraps an int in a struct.

I would not expect either of these conditions to be true of nearly all C code that you might come across.

Let's examine this statement:

Before Linux adopted ELF, GCC's original calling convention (now known as the a.out format) used a more natural approach where the caller was responsible for popping the implicit argument together with the rest, and short structures like in this example would be returned on registers.

Firstly, returning in registers: if you have a struct that is more than four bytes, returning in registers becomes problematic on a 386 because you don't have that many registers. The method actually chosen works well for any sized struct. The designers might have thought "shall we write some code for the special case of a struct that will fit in registers" and then discarded the idea because the use-case of a four-byte struct is pretty rare. The optimisation will almost never benefit user code.

As for this ret 4 thing, it does seem a bit odd, but the thinking is probably "this is a return value not a parameter: we'll clean it up in the callee". Were it not for the fact that C allows a function call with an indeterminate number of parameters, it would also be sensible for the callee to clean up the parameters. This is because you could then avoid having the clean up code in every single caller.

So I disagree with your characterisation of this as a quirk - the decisions made have a rational basis. And once made are set in stone, because all C compilers have to agree on calling conventions so that they can link code compiled by other C compilers.

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .