Go to the first, previous, next, last section, table of contents.
Because SUIF is used in a wide variety of projects, the representation of procedure bodies includes both high-level and low-level information. In the first stages of a compilation, the high-level structure is represented by a language-independent form of abstract syntax trees (ASTs). This format, which we call high-SUIF, is well-suited for passes such as dependence analysis and loop transformation that need the high-level structure of the code. Later in the compilation process, the ASTs are reduced to sequential lists of instructions. This form, which we call low-SUIF, works well for some scalar optimizations and for code generation. Note that SUIF still has only one intermediate representation; high-SUIF and low-SUIF are both implemented with the same tree data structures. See section Abstract Syntax Trees. They only differ in the amount of high-level information present. As long as a SUIF pass does not depend on particular features of high-SUIF or low-SUIF, it can handle either format. High-SUIF and low-SUIF may also be mixed together within the same procedure.
The leaf nodes of an AST are instruction nodes. See section Instruction Nodes. Each of these nodes contains a single instruction or expression tree. In low-SUIF code, a procedure body is reduced to a list of instruction nodes containing individual instructions. This form resembles the quadruple representation used by traditional scalar optimizers.
Block nodes represent nested scopes. See section Block Nodes. A block node contains a symbol table and a list of the AST nodes within the block. The scope of the symbols and types defined in the symbol table is restricted to the AST nodes within the block. They cannot be referenced from outside the block. The root node of an AST is a special kind of block node called a procedure node. Except for some extra methods and a slightly different kind of symbol table, a procedure node is the same as a block node.
Conditional structures may be represented by if nodes. See section If Nodes. An "if" node has three parts, each of which is a list of AST nodes. The header list contains code to evaluate the condition and either branch to the else list or fall through to the then list. Because the header can contain control flow, it is easy to implement short-circuit evaluation of conditional expressions.
SUIF has two different kinds of loops. Many optimizations only apply to
certain well-behaved types of loops, so for nodes are provided for
loops with scalar indices that vary from their initial to final values,
being incremented or decremented on every iteration, and that meet
various other requirements. Most Fortran DO loops qualify as
"for" nodes. Loops that do not meet those requirements are
represented by loop nodes, which just record the control-flow
structure of the loops and are used to represent generic "do-while"
loops.
A loop node contains two lists of AST nodes. See section Loop Nodes. The
body list comes first and holds the loop body. The test
list contains code to evaluate the "while" expression and
conditionally branch back to the beginning of the body list. The
body may contain branches to the continue and break
labels, which are implicitly located at the beginning of the test
list and the end of the loop, respectively.
A "for" node is by far the most complicated type of AST node. Besides
the loop body, it must specify the index variable and the range of
values for the index. The lower bound, upper bound, and step operands
are expressions that are evaluated once at the beginning of the loop.
The index variable is initially assigned the value of the lower bound
and then incremented by the value of the step operand on every iteration
until it reaches the upper bound; the code to do this is automatically
created when the "for" node is expanded to low-SUIF code. The "for"
node must also specify the comparison operator used to determine when
the index variable has reached the upper bound value. The optional
landing_pad part is a list of nodes to be executed once at the
beginning of the loop; this provides a place to move loop-invariant
code. As with loop nodes, the body list may contain branches to
the continue and break labels.
Go to the first, previous, next, last section, table of contents.