Canonicalize Intermediate Representation

Canonicalization

Implement the IRCanonicalize component that transforms IntermediateRepresentation expressions into canonical form. The component can be found in directory ir/ of the TigerTrans package. The component can be invoked using the %.cir target in the make-rules.

Lifting Functions

During translation nested function declarations where left in place and translated to the LET construct. Since addition of static links to functions makes functions independent of their static position, their declarations can be lifted to top-level.

Lifting can be done nicely using collect-split. See module list-set in the StrategoLibrary^?.

Linearize Expressions

Extend module IRCanonicalize with transformation rules for linearizing an IntermediateRepresentation expression and define a strategy to apply the linearization rules. The result of linearization is a flat list of statements.

Beware for non-termination of CALL lifting. What is a good strategy?

By first simplifying expressions using simple constant folding rules, better results can sometimes be obtained. Be aware that no side effects should be removed or reordered by simplification.

Basic Blocks

Divide the list of statements of a PROC into a list of basic blocks.

• BasicBlockPositioning

Traces

Reorder the basic blocks into traces.

Make sure that each conditional jump (CJUMP) is followed by its false label. If necessary rephrase the condition such that this is the case.

Call Space

After canonicalization compute the call space, i.e., the maximum number of arguments of any function called (directly) within the body of a function. This number is needed to compute the size of the stack frame. The number should be stored in the CALL parameter of the PROC fragment of the function. (Use collect

Format Checker

In order to check the result of canonicalization, define a FormatChecker (using RecursivePattern) that describes intermediate representation expressions in canonical form in module CIRFormat.