PT Course

Lab

Contact

Center for ST

Center

Page

Web

Wiki

Log In or Register

Assignment Scoped Dynamic Rewrite Rules

Pt

Tiger Profiler

In this assignment you will implement a transformation that instruments a Tiger program with statements to gather profile information at runtime and print this information to standard output. You should use strategies, rewrite rules, dynamic rewrite rules, and concrete syntax in this exercise.

Introduction to Profiling

A profiler tracks the performance of a computer program in order that the bottle necks in the program are found. Different metrics can be used to measure properties of a program that might, or might not, be related to the performance of the program.

Profiler tools can be implemented to be applied at runtime, compile-time, or both. The Java Virtual Machine for example allows an -Xprof argument. The JVM will output profiling information to standard output if this argument is supplied. GCC (the GNU Compiler Collection), of which the C compiler used on typical GNU/Linux systems is a part, takes a -pg argument, which instructs the compiler to add extra code that writes profile information. The program must also be linked with the runtime part of the profiler. During an execution profile information is produced, which can be analyzed with the GNU Profiler, gprof.

A possible metric is the number of times a function is called during the execution of a program. Functions in a program might be called more (or less) often then you expected. This profile information can be collected by instrumenting the original program with statements to keep track of the calls to a function.

Take for example the following Tiger program: 

  let function fact(n : int) : int =
        if n < 1 then 1 else (n * fact(n - 1))
   in printint(fact(10))
  end

This program can be instrumented with an additional variable to count the number of times the function 'fact' is called. This is illustrated in the following Tiger program: 

  let var fact := 0
   in let function fact(n : int) : int =
          ( fact := fact + 1
          ; if n < 1 then 1 else (n * fact(n - 1))
          )
       in printint(fact(10))
      end
    ; print("\nfact: ")
    ; printint(fact)
  end

Running this instrumented program results in the following output: 

  3628800
  fact: 11

As you can see in this example, function declarations are instrumented with an additional statement to increment the counter for the function that is declared.

In this example the program just keeps track of the number of times functions are called. There is no information where these calls originated from. If we want more detailed information on the function calls in a program, the instrumentation shown above will no longer work: there is no way to find out who the caller is as soon as the execution has arrived in the callee.

This information can be obtained by not instrumenting function declarations, but function calls. At the location of a function call, it is possible to determine what function is being called (the callee), and who is calling the function (the caller). The counter for this function pair can be increased at the location of the function call.

The following Tiger program shows how the previous example might be extended to collect this profile information. 

  let var  top_fact := 0
      var fact_fact := 0
   in let function fact(n : int) : int =
          if n < 1
          then 1
          else
            (n * (
              fact_fact := fact_fact + 1
            ; fact(n - 1))
            )
       in printint(
          ( top_fact := top_fact + 1
          ; fact(10))
          )
      end

    ; print("\ntop to fact: ")
    ; printint(top_fact)

    ; print("\nfact to fact: ")
    ; printint(fact_fact)
  end

Execution of this program produces the following output: 

  3628800
  top to fact: 1
  fact to fact: 10

Assignment

Implement a module called tiger-profile that performs a transformation from Tiger AST (tas) to Tiger AST. This module must extend the input program with statements to output detailed information on the number of function calls.

The output program must on execution output information on the number of calls for each caller, callee pair. For this you have to instrument function calls in a Tiger program. At a function call you need context information to increase the correct counter: what function is the caller and what function is being called? Your implementation must use dynamic rewrite rules to generate the instrumenting rewrite rules at the locations where the information is available.

Your implementation must be able to distinguish local redeclarations of functions, and in general function declarations with the same name. Applying Tiger-Rename to solve this problem is not allowed: the function names must not be obfuscated. Providing more detailed information the location of the caller and callee in the presentation is an optional challenge.

Apply your tiger-profile module in the following pipeline of Tiger transformation tools: 

  parse-tiger -i $< \
  | Tiger-Desugar \
  | ./tiger-profile \
  | Tiger-Ensugar \
  | pp-tiger -o $@
The resulting program is to be executed with the Tiger interpreter, run-tiger.

Tips and issues

See the Tiger Language topic if you need information on Tiger.

In a Tiger program multiple declarations of functions with a certain name can occur. The function name is thus not an unique identification of a function declaration. To obtain a unique identifier of a function declaration, the function declarations in the Tiger program could be annotated with such an identifier. Remember that unique identifiers can be generated with the new strategy. You can find more information on the usage of annotations at the Term Annotations topic. You can also take a look at annotations-test.str in the SSL. This module defines unit tests for annotations and is thus a good example of the various constructs.

Unfortunately there are some problems with including newlines (and other escape sequences) in generated Tiger code. You should escape the \ in an escape sequence: \\n . This problem is caused by the application of Stratego desugarings to concrete syntax sections.

Syntax Definitions

Syntax of Tiger

The syntax definition of Tiger is defined in the following modules:

Lexical syntax

Desugaring turns operators into generic BinOps and RelOps:

Tiger in Stratego

The full syntax of the embedding of Tiger in Stratego is defined in the following modules.