title: alloca() in caller's space
body: <p>Thinking about returning dynamic or automatic arrays. Not really C-related.</p>
  
  <p>The usual technique to return an array is: A) callee allocates on heap and returns, B) caller allocates on stack and passes to callee.</p>
  
  <pre><code>// A
  void caller(void) {
      int *a = callee();
      free(a);
  }
  int *callee(void) {
      int *a = malloc(10 * sizeof(*a));
      return a;
  }
  
  // B
  void caller(void) {
      int a[10]; callee(a, sizeof(a) / sizeof(a[0]));
  }
  void callee(int *a, size_t n) {
      //
  }
  </code></pre>
  
  <p>Case A may lead to unnecessary allocate-free cycle, while case B requires syntactic garbage in caller. In B we also can't compute <code>n</code> in callee, because it comes predefined. We also can't return automatic storage because it will be destroyed on return (accessing it is UB in general).</p>
  
  <p>But what if we introduce new <code>return_auto</code> operator that will return from callee, but leave it's stack frame intact, as if caller did all the job on it's own stack?</p>
  
  <pre><code>// C
  void caller(void) {
      int *a = callee();
  }
  int *callee() {
      int a[compute_n()];
      return_auto a;
  }
  </code></pre>
  
  <p>I mean, caller could inherit callee's stack frame and all issues disappear. It's stack frame would look like this after return_auto:</p>
  
  <pre><code>[caller frame]
    arguments
    ret-pointer
    locals
      int *a = callee.a
  
    [callee frame] (defunct)
      arguments
      ret-pointer
      locals
        int a[n] (still alive)
    [end-of-callee-frame]
  
  [end-of-caller-frame]
  </code></pre>
  
  <p>In machine code (x86 at least) this may be implemented by jumping to ret-pointer at <code>ss:ebp</code> instead of <code>mov esp, ebp / ret n</code>. We already have VLAs in modern C, and this looks very similar but slightly complex.</p>
  
  <p>Of course that should be used with care, because series of return_auto's would leave pretty huge dump on stack, that will be "collected" only when outermost caller returns (normally). But stack allocations are insanely cheap, and in theory some algorithms could benefit from not calling malloc/free at all. This is also interesting in code structuring perspective, not just performance.</p>
  
  <p>Does anyone know where this technique is implemented / stack frames joined?
  (C is just an example here)</p>
  
  <hr>
  
  <p>Okay, it needs a simple example.</p>
  
  <pre><code>void caller(Context *ct) {
      char *s = make_s(ct);
      printf("%s\n", s);
  }
  
  void make_s(Context *ct) {
      const char *tag = "?", *name = "*";
  
      if (ct-&gt;use_tag) tag = ct-&gt;tag;
      else if (ct-&gt;app) tag = ct-&gt;app-&gt;tag;
      if (ct-&gt;app) name = ct-&gt;app-&gt;name;
  
      char s[strlen(tag)+strlen(name)+10];
      snprintf(s, len, "%s.object(%s)", name, tag);
      return_auto s;
  }
  </code></pre>
  
  <p>Obviously, for now we need to explode that in caller's body (probably via macro to feel all caveats) or do <code>asprintf/malloc</code> in callee and <code>free</code> in caller.</p>