Semantic Analysis

The semantic analyzer uses the syntax tree and the information in the symbol table to check the source program for semantic consistency. It also gathers type information and saves it to the symbol table. An important part here is type checking where it checks that operators have matching operands. It might also handle coercions, i.e. transforming INT + FLOAT to FLOAT + FLOAT.

Aliasing

There is as interesting consequence of call-by-reference (references passed by value). Two formal parameters can refer to the same location, and they are alias of each other. You need to understand this in order to optimize a program, because certain optimizations may only be done if one can be sure there is no aliasing.

Synthesized Attributes

The idea of associating quantities with programming constructs can be expressed in terms of grammars. We attach rules to productions of the grammar. A syntax-directed definition associates:

1. With each grammar symbol, a set of attributes

2. With each production, a set of semantic rules for computing values of the attributes associated with the symbols appearing in the production.

An attribute is synthesized if its value at a parse-tree node N is determined from attribute values at the children of N and N itself, and can be evaluated by a single bottom-up traversal.

Abstract and Concrete Syntax

Useful starting point for creating a translator. AST resemble parse trees to an extent, but these are conceptually different. Parse trees have the interior nodes representing non-terminals, and a syntax tree represent programming constructs. Many productions represent grammar constructs, but many are just there to simplify parsing. The helpers are dropped in the syntax tree.

Removal of White Space and Comments

White space and comments can be removed by the lexer, so the parser won't have to worry.

Construction of Syntax Trees

Syntax trees can be created for any construct, not just expressions. Each construct is represented by a node, with children for the semantically meaningful components of the construct. These nodes can be represented in a class structure with an arbitrary amount of children.

Reductions

We can think of bottom-up parsing as the process of reducing a string w to the start symbol of the grammar. Each step matches a substring and replaces it with a non-terminal. By definition, a reduction is the reverse of a step in a derivation. The goal is to construct a derivation in reverse, which in fact will be a rightmost derivation.

Precedence and Associativity to Resolve Conflicts

We might alter productions to give precedence (E $\to$ E + E | E * E | (E) | id). This might not always be the optimal approach, because the parser will have more states, and it is hard to modify precedence. We can express conflicts with precedence if we have different operators, associativity when considering equal operators.

The Declarations Part

Consists of two parts, normal C declarations and declarations of grammar tokens. The grammar tokens will then be available for the second and third part. You can make the tokens available for Lex as well.

The Translation Rules Part

Put rules here, where each rule consists of grammar productions and associated semantic actions. Unquoted means non-terminals, quoted means terminals. \$\$ means the attribute value associated with the head, \$i means the ith grammar symbol.

The Supporting C-Routines Part

Must provide yylex() (might come from lex/flex) which produces tokens.

Using Yacc with Ambiguous Grammars

Some grammars might produce conflicts, and it will report so. Unless instructed otherwise, it will resolve all conflicts with following rules:

• A reduce/reduce is resolved by choosing the conflicting production listed first in the specification.

• A shift/reduce conflict is resolved in favor of shift (will resolve dangling-else ambiguity correctly).

These rules might not be what the compiler writer wants, so we can choose associativity (%left ’+’ ’-’) or force it to be non-associative. You can also force precedence.

Rules for Type Checking

Two forms, synthesis which builds up the type of an expression from the types of its sub-expressions and type inference which determines the type of a language construct from the way it is used. The latter can be used for languages that permits names to be used without declaration, but still uses type checking. void is a special type that denote the absence of a value.

Type Conversions

You have widening (preserve information) and narrowing (may lose information). If type conversions are done automatically by the compiler, it is implicit. These conversions are also known as coercions, and is normally limited to widening conversions. Two functions, max(a,b) finds the highest type in the hierarchy and widen() which widens a type.

One-Pass Code Generation using Backpatching

Backpatching can be used to generate code for boolean expressions and flow-of-control statements in one pass. We use synthesized attributes truelist and falselist to manage labels in jumping code for bool expressions.

Backpatching for Boolean Expressions

Flow-of-Control Statements

Static Versus Dynamic Storage Allocation

A storage allocation is static (compile time) if the decision can be made at looking at the text of a program. A storage allocation is dynamic if it can be decided only when the program is running. Two techniques:

• Stack

• Heap. For data that might outlive the call to the procedure that created it.

Activation Records

Procedure calls and returns are usually managed by a run-time stack (Control stack). Each live activation has an activation record (frame). Might include:

• Temporary values

• Local data

• A saved machine status

• Access link

• Control link, pointing to the activation record of the caller.

• Space for return value

• The actual parameters used by the calling procedure.

The Memory Manager

The memory manager keeps track of all the free space in heap storage at all times. Performs:

• Allocation. Must provide a memory region in requested size.

• De-allocation. For reusing space.

Tree-Translation Schemes

The input of code-generation will be a sequence of trees at the semantic level. We need to apply a sequence of tree-rewriting rules to reduce the input tree to a single node. Each rule represents the translation of a portion of the tree given by the template. The replacement is called tiling of the subtree

Code Generation by Tiling an Input Tree

Given an input tree, the templates in the tree-rewriting rules are applied to tile its subtrees. When match is found, the subtree is replaced with replacement node of a rule and action associated with the rule is done (generate code). Two issues:

• How is the tree-pattern matching to be done?

• What if we have more matches?

Must always have a match and not infinite amount of matches. You can create a postfix representation of a tree and create a grammar for it. By reduce-reduce, take largest production, by shift-reduce, shift. This is known as maximal munch[^1]. This is a good and well understood method, but it has its challenges.

Causes of redundancy

Sometimes redundancy is available at source level, but often introduced because the source is written in a high level language (array accesses will cause redundancy). By having a compiler eliminate the redundancies, we get the best of both worlds: the programs are both efficient and easy to maintain.

A Running Example: Quicksort

blabla

Semantics-Preserving Transformations

A compiler can improve a program without changing the function it computes.

Global Common Sub-expressions

An occurrence of an expression $E$ is called a common sub-expression if $E$ was previously computed and the values of the variables in $E$ have not changed since the previous computation.

Copy Propagation

A copy statement is an assignment on the form $u = v$. The idea is to use $v$ for $u$ in other statements using $u$. It may not appear to be an improvement, but dead-code elimination gives the opportunity to get rid of the copy statement.

Dead-Code Elimination

A variable is live at a point in a program if its value can be used subsequently, otherwise dead. We would like to remove dead statements. Copy propagation makes dead code elimination able to delete many copy statements.\ \ Deducing at compile time that a value of an expression is known as constant folding.

Code Motion

Loops are very important place for optimizations. Code motion takes an expression that evaluates to the same each time and lifts it out of the loop.

Induction Variables and Reduction in Strength

A variable x is said to be an induction variable if there is a positive or negative constant c such that each time x is assigned, its value increases by c. They can be computed with a single increment per loop iteration. Transforming from an expensive to a cheap operation is strength reduction, which you can do on induction variables. It’s normal to work inside-out when optimizing loops. When there are two or more induction variables in a loop, it might be possible to get rid of all but one.

The Data-Flow Abstraction

You can view the program as a series of transformations, where the states are between the statements. Control flow will go from statement to statement in single blocks, and go between blocks if there is an edge between. Execution path is the instructions executed, which there normally is an infinite number of. Different analyses may choose to abstract out different information.\ \ The definitions that may reach a program point along some path are known as reaching definitions.

The Data-Flow Analysis Schema

At each program point we associate a data-flow value which is the set of all possible program states that can be observed for that point. We denote the data-flow values before and after each statement $s$ by $IN[s]$ and $OUT[s]$, and the data-flow problem is to find a solution to a set of constraints on these definitions for all statements $s$.

Data-Flow Schemas on Basic Blocks

Going through a block is easy, just follow each statement, and we get:

$$OUT[B] = f_b(IN[B])$$

If we do constant propagation, we are interested in the sets of constants that may be assigned to a variable, then we have forward flow with union operator.

$$IN[B] = \cup_{P a predecessor of B}OUT[P]$$

No unique solution, but find the most precise that satisfies control-flow and transfer constraints.

Reaching Definitions

One of the most common and useful data-flow schemas. We say a definition $d$ reaches a point $p$ if there is a path from the point immediately following $d$ to $p$, such that $d$ is not killed along that path. We might have aliases, and that is why we must be conservative.

Live-Variable Analysis

Useful for register allocation for basic blocks (dead values need not be stored). We use backward analysis and we define:

1. $def_B$ as the set of variables defined in the block.

2. $use_B$ as the set of variables used in the block.

About the same as the reaching definitions, except opposite direction:

$$IN[B] = use_b \cup (OUT[B] - def_B)$$

Available Expressions

An expression $x + y$ is available at a point $p$ if every path from the entry node to $p$ evaluates $x + y$, and after the last such evaluation prior to reaching $p$, there are no subsequent assignments to $x$ or $y$. A block kills expression $x + y$ if it assigns (or may assign) $x$ or $y$ and does not subsequently re-compute $x + y$. A block generates an expression $x + y$ if it evaluates it and not subsequently define $x$ or $y$. The primary use of available expressions is detecting global common sub-expressions. At each step ($x = y + z$):

1. Add to $S$ the expression $y + z$.

2. Delete from $S$ any expression involving $x$.

Must be done in correct order. Data-flow can be done the same way as reaching definitions (forward analysis), but the meet operator is intersection rather than union. An expression is available at the top of a block if it is available at the end of each predecessor block.\ \ In reaching definitions, we start with a set too small and work up, in available expression, we work with a set too large and work down. We start with the assumption that everything is available everywhere, to keep the optimization conservative.

Dominators

A node d of a flow graph dominates node n, written d dom n, if every path from the entry node of the flow graph to n goes through d. Every node dominates itself. The information can be presented in a dominator tree, where entry is the root and each node dominates its descendants. The problem can be formulated as a forward data-flow analysis.

Edges in a Depth-First Spanning Tree

We can traverse it with DFS, getting following edges

• Advancing edges

• Retreating edges

• Cross edges