title: At which stage should I implement tail call optimization for my compiler
body: <p>I wrote a small compiler in Racket for a scheme-like language. Now I want to implement TCO for my compiler.</p>
  
  <p>My idea is: I need to detect tail calls before transform them into intermedia representation. But from this <a href="https://en.wikipedia.org/wiki/Tail_call" rel="nofollow">page</a>, it seems like TCO is usually done at assembly level by changing <code>call</code> to <code>jmp</code>. I am kinda stuck at here.</p>
  
  <p>Any suggestions would be appreciated. </p>
  
  <p><strong>EDIT</strong>: My target is x86 assembly code. The IR I used is three address code. </p>
  
  <p>And here are the 12 passes for my compiler, the flatten pass is where i transform source code to IR</p>
  
  <pre><code>(define test-passes
  (list
   `("uniquify"                ,(uniquify '())                                   ,interp-scheme)
   `("reveal-functions"        ,(reveal-functions '())                           ,interp-F)
   `("convert-to-closures"     ,convert-to-closure                               ,interp-F)
   `("expose allocation"       ,expose-allocation                                ,interp-F)
   `("flatten"                 ,(flatten #f)                                     ,interp-C)
   `("instruction selection"   ,select-instructions                              ,interp-x86)
   `("liveness analysis"       ,(uncover-live (void))                            ,interp-x86)
   `("build interference"      ,(build-interference (void) (void) (void) (void)) ,interp-x86)
   `("allocate register"       ,allocate-registers                               ,interp-x86) 
   `("lower-conditionals"      ,lower-conditionals                               ,interp-x86)
   `("patch-instructions"      ,patch-instructions                               ,interp-x86)
   `("x86"                     ,print-x86                                        #f)
   ))
  </code></pre>