TC-5 Optimizing Static Links

Note

This optimization is difficult to do perfectly.

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.

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

$ tc -XEA fact.tig
/* == Abstract Syntax Tree. == */

function _main() =
  (
    let
      function fact(/* escaping */ n : int) : int =
        if (n = 0)
          then 1
          else n * fact((n - 1))
    in
      fact(10)
    end;
    ()
  )
$ echo $?
0

tc -XeEA fact.tig

$ 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;
    ()
  )
$ echo $?
0

3. Adjust your call and progFrag prologues.

4. Improve your computation so that non escaping static links are detected.

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

$ tc -XeEA escaping-sl.tig
/* == Abstract Syntax Tree. == */

function _main() =
  (
    let
      var /* escaping */ toto := 1
      function outer() : int =
        let
          function inner() : int =
            toto
        in
          inner()
        end
    in
      outer()
    end;
    ()
  )
$ echo $?
0

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