4.14.5.2 TC-5 Optimizing Static Links

Warning: this optimization is difficult to do perfectly, and therefore, expect a big bonus.

In a first and conservative extension, the compiler considers that all the functions (but the builtins!) need a static link. This is correct, but inefficient: for instance, the traditional fact function will spend almost as much time handling the static link, than its real argument.

Some functions need a static link, but don’t need to save it on the stack. For instance, in the following example:

let
  var foo := 1
  function foo() : int = foo
in
  foo()
end

the function foo does need a static link to access the variable foo, but does not need to store its static link on the stack.

It is suggested to address these problems in the following order:

1. Implement the detection of functions that do not need a static link (see exercise 6.5 in Modern Compiler Implementation), but still consider any static link escapes.
2. Adjust the output of --escapes-display to display ‘/* escaping sl */’ before the first formal argument of the functions (declarations) that need the static link:

   $ cat fact.tig
   let
      function fact(n : int) : int =
         if (n = 0)
            then 1
            else n * fact((n - 1))
   in
      fact(10)
   end
   $ tc -XEA fact.tig
   /* == Abstract Syntax Tree. == */
   
   function _main() =
     (
       let
         function fact(/* escaping sl *//* escaping */ n : int) : int =
           (if (n = 0)
             then 1
             else (n * fact((n - 1))))
       in
         fact(10)
       end;
       ()
     )
   $ tc -XeEA fact.tig
   /* == Abstract Syntax Tree. == */
   
   function _main() =
     (
       let
         function fact(n : int) : int =
           (if (n = 0)
             then 1
             else (n * fact((n - 1))))
       in
         fact(10)
       end;
       ()
     )
   

3. Adjust your call and progFrag prologues.
4. Improve your computation so that non escaping static links are detected:

   $ cat escaping-sl.tig
   let
      var toto := 1
      function outer() : int =
        let function inner() : int = toto
        in inner() end
   in
     outer()
   end
   $ tc -XeEA escaping-sl.tig
   /* == Abstract Syntax Tree. == */
   
   function _main() =
     (
       let
         var /* escaping */ toto := 1
         function outer(/* escaping sl */ ) : int =
           let
             function inner(/* sl */ ) : int =
               toto
           in
             inner()
           end
       in
         outer()
       end;
       ()
     )
   

   Here, both outer and inner need their static link (so that inner can access toto. However, outer’s static link escapes, while inner’s does not.

   Watch out, it is not trivial to find the minimum. What do you think about the static link of the function sister below?

   let
     var v := 1
     function outer() : int =
       let
         function inner() : int = v
       in
         inner()
       end
     function sister() : int = outer()
   in
     sister()
   end