Re: [Tinycc-devel] Proposal for handling alloca(). Anyone see a problem with it?

[David A. Wheeler]

Philippe Ribet:
>I'm sorry to ask this question so late, but I still didn't understood how 
>alloca *could* work on the stack with single pass compiler... I'm asking from 
>a pure theorical point of view.

It's a single pass compiler, but any single-pass compiler can still backpatch 
values and use the linker to fill in values that were determined later on. This 
approach only works for fixed-width data, which is why it's harder to eliminate 
dead code in tcc, but that's enough for this task.

On function entry, local variable space is allocated for ALL local values by 
tcc, including all of variables in the subblocks (transitively).  Tcc counts up 
the total need (including all nested blocks) while it compiles, and then it 
arranges to have the "amount to reserve" value set to that need.  Tcc could be 
a lot smarter; it doesn't reuse block space when it could... but you don't HAVE 
to reuse space to have the semantics work.

You said: "this closes block 1 thus freeing local variable 2, but alloca memory 
should be kept (until the function returns). How to do that?"  The short 
answer: Don't.  All local variables, including those nested inside blocks, are 
not REALLY freed until the entire function returns.  Since the stack pointer is 
AFTER all local variables - even ones in blocks not yet run - there's no issue. 
 Tcc could reuse the local variable space more smartly though.

I've put below your sample program (modified so it compiles), and the resulting 
asm code from tcc. I think that should reveal how it works.

--- David A. Wheeler

=============== File imagine.c ==============================
extern int g(), h(), j();

f() {
    int variable1; //on the stack
    int x; //on the stack
    { // new block 1
       int variable2; // on the stack
       { // new block 2
          int variable1 = alloca(4);  // (Note overload of name)
          // this will be pushed on the stack after variable 2, because it's a 
single pass compiler
          int variable2 = h(g()+j()+3, alloca(variable1), j()*g()*4);  // 
Nested calls work
       }
    } // this closes block 1 thus freeing local variable 2, but alloca memory 
should be kept (until the function returns). How to do that?
    x = variable1;
}


=============== To create assembly list ==============================
$ ./tcc -B. -I. -g -c imagine.c
$ objdump -S -x imagine.o
=============== Listing ==============================


imagine.o:     file format elf32-i386
imagine.o
architecture: i386, flags 0x00000011:
HAS_RELOC, HAS_SYMS
start address 0x00000000

Sections:
Idx Name          Size      VMA       LMA       File off  Algn
  0 .text         00000073  00000000  00000000  00000040  2**5
                  CONTENTS, ALLOC, LOAD, RELOC, READONLY, CODE
  1 .data         00000000  00000000  00000000  000000c0  2**5
                  CONTENTS, ALLOC, LOAD, DATA
  2 .bss          00000000  00000000  00000000  000000c0  2**5
                  ALLOC
  3 .stab         00000078  00000000  00000000  00000160  2**5
                  CONTENTS, RELOC, READONLY, DEBUGGING
  4 .stabstr      00000041  00000000  00000000  000001d8  2**0
                  CONTENTS, READONLY, DEBUGGING
SYMBOL TABLE:
00000000 l    d  .text  00000000 .text
00000000 l    df *ABS*  00000000 imagine.c
00000000 g     F .text  00000073 f
00000000       F *UND*  00000000 alloca
00000000       F *UND*  00000000 g
00000000       F *UND*  00000000 j
00000000       F *UND*  00000000 h


Disassembly of section .text:

00000000 <f>:
extern int g(), h(), j();

f() {
   0:   55                      push   %ebp
   1:   89 e5                   mov    %esp,%ebp
   3:   81 ec 24 00 00 00       sub    $0x24,%esp
    int variable1; //on the stack
    int x; //on the stack
    { // new block 1
       int variable2; // on the stack
       { // new block 2
   9:   b8 04 00 00 00          mov    $0x4,%eax
   e:   50                      push   %eax
   f:   e8 fc ff ff ff          call   10 <f+0x10>
                        10: R_386_PC32  alloca
  14:   83 c4 04                add    $0x4,%esp
  17:   89 45 f0                mov    %eax,0xfffffff0(%ebp)
  1a:   e8 fc ff ff ff          call   1b <f+0x1b>
                        1b: R_386_PC32  g
  1f:   89 45 e8                mov    %eax,0xffffffe8(%ebp)
  22:   e8 fc ff ff ff          call   23 <f+0x23>
                        23: R_386_PC32  j
  27:   8b 4d e8                mov    0xffffffe8(%ebp),%ecx
  2a:   01 c1                   add    %eax,%ecx
  2c:   83 c1 03                add    $0x3,%ecx
  2f:   8b 45 f0                mov    0xfffffff0(%ebp),%eax
  32:   50                      push   %eax
  33:   89 4d e4                mov    %ecx,0xffffffe4(%ebp)
  36:   e8 fc ff ff ff          call   37 <f+0x37>
                        37: R_386_PC32  alloca
  3b:   83 c4 04                add    $0x4,%esp
  3e:   89 45 e0                mov    %eax,0xffffffe0(%ebp)
  41:   e8 fc ff ff ff          call   42 <f+0x42>
                        42: R_386_PC32  j
  46:   89 45 dc                mov    %eax,0xffffffdc(%ebp)
  49:   e8 fc ff ff ff          call   4a <f+0x4a>
                        4a: R_386_PC32  g
  4e:   8b 4d dc                mov    0xffffffdc(%ebp),%ecx
  51:   0f af c8                imul   %eax,%ecx
  54:   c1 e1 02                shl    $0x2,%ecx
  57:   51                      push   %ecx
  58:   8b 45 e0                mov    0xffffffe0(%ebp),%eax
  5b:   50                      push   %eax
  5c:   8b 45 e4                mov    0xffffffe4(%ebp),%eax
  5f:   50                      push   %eax
  60:   e8 fc ff ff ff          call   61 <f+0x61>
                        61: R_386_PC32  h
  65:   83 c4 0c                add    $0xc,%esp
  68:   89 45 ec                mov    %eax,0xffffffec(%ebp)
          int variable1 = alloca(4);  // (Note overload of name)
          // this will be pushed on the stack after variable 2, because it's a 
single pass compiler
          int variable2 = h(g()+j()+3, alloca(variable1), j()*g()*4);  // 
Nested calls work
       }
    } // this closes block 1 thus freeing local variable 2, but alloca memory 
should be kept (until the function returns). How to do that?
    x = variable1;
  6b:   8b 45 fc                mov    0xfffffffc(%ebp),%eax
  6e:   89 45 f8                mov    %eax,0xfffffff8(%ebp)
  71:   c9                      leave  
  72:   c3                      ret