Suppose that the array `a` has bounds
`l _{1}`,

A + e * ( (i-lLet_{1}) + (j-l_{2}) * (u_{1}-l_{1}) + (k-l_{3}) * (u_{1}-l_{1}) * (u_{2}-l_{2}) )

A - e * (l_{1}+ l_{2}*d_{1}+ l_{3}*d_{1}*d_{2}) + i*e + j*e*d_{1}+ k*e*d_{1}*d_{2})

- The programmer has no knowledge of or control over these computations
- The first line is a constant that depends only on the array dimensions
`d`is a constant_{1}*d_{2}- The computation to be done at run time is
`A - C`_{0}+ i*C_{1}+ j*C_{2}+ k*C_{3} - A similar expression can be obtained if the array is stored by columns

a[i,j,k] := ( a[i-1,j,k] + a[i+1,j,k] + a[i,j-1,k] + a[i,j+1,k] + a[i,j,k-1] + a[i,j,k+1] ) / 6.0;The address of

A - C_{0}+ (i-1)*C_{1}+ j*C_{2}+ k*C_{3}= A - C_{0}- C_{1}+ i*C_{1}+ j*C_{2}+ k*C_{3}= A - C_{01}+ i*C_{1}+ j*C_{2}+ k*C_{3}

`i*C`appears in_{1}+ j*C_{2}+ k*C_{3}*every*index computation- Only the ``base address'' changes
- There is no practical way for the programmer to specify that
`i*C`should only be computed once_{1}+ j*C_{2}+ k*C_{3} - A non-optimizing compiler will translate each array access independently, thus computing this same value 7 times

- Loads a register
- Computes a value into a register from values in registers
- Stores a register
- Transfers control

- RISC machine only computes values into registers
- Operands of a computation are always registers
- Specific operations that read and write memory, and do nothing else
- Strong distinction between registers and memory

- Values computed from other values by single operations:
p: V:=E

Here`E`is an expression with exactly one operator - Value read from a variable:
p: V:=S p: V

_{1}:=S[V_{2}] - Value written to a variable:
p: S:=V p: S[V

_{1}]:=V_{2} - Conditional and unconditional control transfers:
p: Jump(L) p: JTrue(L,V) p: JFalse(L,V)

- Each action is a ``tuple'';
`p`is a ``program point'' - Distinction between
*values*and*variables* - Possibility that variable addresses are computed
- Values are identified by integers
- Distinct integers represent distinct values

p_{i}: V_{j}:=V_{m}+V_{m}p_{i+1}: V_{k}:=V_{m}*2 p_{i+2}: V_{j}:=V_{m}+V_{m}

- The same computation can appear at any number of program points
- We say that values are identical if their defining tuples are congruent
- Congruence is used because mathematical equality is undecidable in general and complicated even in decidable cases
- It's common to extend the notion of congruence to encompass some simple
identities:
`v + 0`is congruent to`v``v * 1`is congruent to`v``v`is congruent to_{2}op v_{1}`v`when_{1}op v_{2}`op`is commutative- ...

- If we see a read tuple for a variable whose value is unknown, the value delivered must be considered new -- not identical to any previous value
- Unless we can track the values of variables, we'll
*never*find identical values

- The abstract program is a sequence of trees
- There is no subtree
*all*of whose leaves are constants - Non-constant leaves must be variable references
- If
*all*variable references yield distinct values, then by induction on the tree height we will never find any congruent tuples

pIf we didn't know that the variables_{1}: V_{1}:=i p_{2}: V_{2}:=V_{1}*C_{1}p_{3}: V_{3}:=j p_{4}: V_{4}:=V_{3}*C_{2}p_{5}: V_{5}:=V_{2}+V_{4}p_{6}: V_{6}:=k p_{7}: V_{7}:=V_{6}*C_{3}p_{8}: V_{8}:=V_{5}+V_{7}p_{9}: V_{9}:=V_{8}-C_{01}p_{10}: V_{10}:=a[V_{9}]

- Need to keep track of the value of a variable
- Need to have some sort of tuple lookup to test congruence
- Writes to a variable are included in this solution
- Need to be able to reliably distinguish variables -- no aliasing

This technique for tracking the values of variables works within a single basic block. It also enables us to implement an arbitrarily complex basic block as one multiple assignment:

- Each variable used before being assigned in the block is read exactly once
- When a write tuple is encountered, the value is noted
- At the end of the basic block, write tuples are generated for all variables that were assigned
- The value assigned is the one currently shown as being the variable's value

- Theoretically interesting
- Demonstrates that all variable reads can be at the beginning of a block and all variable writes at the end
- Reads and writes are ``boundary conditions''

- Extended basic block
- A maximal tree of code sequences
- Strongly-connected region
- A collection of program points in which there is a path from every program point to every other program point
- Procedure
- A collection of program points constituting a unit of abstraction

- Our previous technique for tracking variable values still works in an extended basic block but not in any larger region
- Computations yielding fixed values within a strongly connected region should be moved out of that region
- Modularity allows procedures to be optimized independently

Here the source language statements are to the right of the box representing a basic block. The top three boxes, enclosed by the dotted line, form an extended basic block. With the addtion of the fourth basic block, the structure no longer satisfies the definition of an extended basic block.

- Variable tracking within the extended basic block
- Addition of the join block
- Congruence does not apply to read and write tuples any more
- The symbol is a key that we use to obtain the variable's value
- Our method would work if an
*new*variable name were used instead of`x`in the join block

- Every variable has exactly one value
- There may be
*no*assignment to a symbol, in which case a new value is created when the variable is accessed `phi`never has associated tuples -- it's an artifact of the analysis

- Find the places where variables are assigned (including joins) and establish the new symbol names
- Consistently rename the variables so that each use has the same symbol as the assignment that establishes its value

- Explicit assignments are easy to spot, but which variables are
arguments of
`phi`functions at joins? - Consistent renaming is a well-known compiler process, but what is the ``scope'' of an assignment?
- It turns out that these two questions are related.

The numbered nodes represent the code of the procedure.
`Entry` and `Exit` represent the entry and exit operations of
the procedure.

- Each numbered node of the graph corresponds to a basic block
- Directed edges represent the successor relation
- For the moment, the actual code is uninteresting

See A Fast Algorithm for Finding Dominators in a Flowgraph (ACM Transactions on Programming Languages and Systems 1 (1979) 121-141).

- Each node of the dominator tree is a node of the control flow graph
- Linkage among the nodes is the only difference between the dominator tree and the control flow graph
- Show that this tree really does describe strict dominance for this control flow graph

- This expansion merely emphsizes the relations among assignments and computations
- No processing algorithm will actually expand the nodes in this way, but
the expansion
*is*reflected in attributes that decorate the tree

- Defining occurrences
- Scopes
- Applied occurrence

- A use of a variable preceding any assignment establishes a value for that variable
- An assignment in a node of the dominator tree precedes all uses in nodes of the subtree
- If another assignment intervenes, the use will be in a subtree of
the node containing
*that*assignment - If there is a join, and a variable has been assigned in the blocks joined, there will be an assignment via a phi function at the beginning of the join block

Here's the expanded dominator tree:

The dotted box on the right encloses the expansion of the basic block at
the bottom of the previous figure to include the assignment to `x`
via the phi function.
(Only the non-empty elements of each expansion are shown.)

- All occurrences of
`x`have been systematically renamed in the tuples of both pictures - Notice how the scope of each variable is related to the structure of the dominator tree
`y`is still valid in the lower left block because there was no assignment to it

If there is an assignment to a variable in node `X`, then there must
be an assignment to that variable via a phi function at every node in
`DF(X)`.

Consider a node `Y` in `DF(X)`

`X`dominates a predecessor of`Y`, so there is a path from`X`to`Y``X`does not strictly dominate`Y`, so there is a path from`Entry`to`Y`that doesn't go through`X`- Therefore we can arrive at
`Y`with either of two values for the variable assigned in`X`

*Strictly*is important here because it allows a node to lie on its own dominance frontier

- The dominance frontiers must be determined from a
*combination*of the dominantor tree and the control flow graph - Notice that none of these algorithms require the tuples

- Determine the basic blocks, along with their predecessors and successors (this defines the control flow graph)
- Construct the dominator tree
- Add phi functions as necessary to the basic blocks
- Consistently rename the variables
- Generate the tuples in a depth-first, left-to-right traversal of the dominator tree

- Note that we end up with a tree representation of the program
- Consistent renaming can be combined with tuple generation
- When tuples are being generated, don't generate duplicates
*within*a basic block - Note that the whole tuple need not be stored at each program point -- the tuple identification is sufficient

waite@isa.informatik.th-darmstadt.de | Revision $Revision: 1.4 $ |