Typos in comments. Couldn't resist.

[suif.git] / info / suif1.info-2

This is Info file suif1.info, produced by Makeinfo version 1.68 from
the input file suif1.texi.

   This file documents the SUIF library.

   Copyright (C) 1994 Stanford University.  All rights reserved.

   Permission is given to use, copy, and modify this documentation for
any non-commercial purpose as long as this copyright notice is not
removed.  All other uses, including redistribution in whole or in part,
are forbidden without prior written permission.

\x1f
File: suif1.info,  Node: For Nodes,  Next: Block Nodes,  Prev: Loop Nodes,  Up: Tree Nodes

For Nodes
---------

   Many of our compiler passes are designed to work with Fortran `DO'
loops because they are relatively easy to analyze.  A `DO' loop has a
single index variable that is incremented or decremented on every
iteration and varies from an initial to a final value.  SUIF uses
`tree_for' nodes to represent well-structured `DO' loops.  The exact
conditions that a loop must meet to be represented as a `tree_for' in
SUIF are described below.  The expander's cleanup pass, which is run
immediately after the front-end, converts `tree_for' nodes that violate
any of these conditions into `tree_loop' nodes (*note Loop Nodes::.).
Even though they are primarily intended for Fortran code, `tree_for'
nodes may also be used for C loops that meet the same conditions.

   The index variable of a `tree_for' can be accessed using the `index'
method and set using the `set_index' method.  The index variable must
be a scalar variable that is defined in the scope of the `tree_for'
node.  It may not be modified anywhere within the loop body.  This
applies across procedures as well.  If the loop body contains a call to
another procedure that modifies the index variable, then the loop
cannot be represented by a `tree_for' node.  Moreover, if you are using
Fortran form, the index variable may not be a call-by-reference
parameter.  *Note Fortran::.

   The range of values for the index variable is specified by three
`operand' fields.  *Note Operands::.  The lower and upper bounds and
the step value can be accessed by the `lb_op', `ub_op', and `step_op'
methods.  The `set_lb_op', `set_ub_op', and `set_step_op' methods are
provided to change them.  These operands are expressions that are
evaluated once at the beginning of the loop.  The index variable is
initially assigned the lower bound value and then incremented by the
step value on every iteration until it reaches the upper bound value;
the code to do this is automatically created when the `tree_for' is
expanded to low-SUIF code.

   Most users will always use `tree_for' nodes in conjunction with
expression trees.  Flat lists of instructions are typically used only in
the library and with back-end passes where the `tree_for' nodes have
been dismantled.  It is possible to use `tree_for' nodes without
expression trees, but the bounds and step values cannot be treated as
operands.  In fact, even with expression trees those operands are
actually stored on tree node lists.  If necessary, these lists can be
accessed directly using the `lb_list', `ub_list', and `step_list'
methods.  Each list is required to contain a single expression with a
dummy copy instruction at the root.  The destination of the dummy copy
must be a null operand.  Methods are provided in the tree node list
class to extract the operands from the tree node lists (*note Tree Node
Lists::.).

   The `tree_for' must also specify the comparison operator used to
determine when the index variable has reached the upper bound value.
The possible comparison operators are members of the `tree_for_test'
enumerated type.  The `test' and `set_test' methods are used to access
and modify the comparison operator for a `tree_for' node.  The
`tree_for_test' enumeration includes quite a few comparison operators,
but some of them are only used by the front-end.  Both signed and
unsigned versions are available for most of the comparison operators,
as indicated by the letters "`S'" and "`U'" in their names.

`FOR_SLT'

`FOR_ULT'
     Less than.  Repeat as long as the index is strictly less than the
     upper bound.

`FOR_SLTE'

`FOR_ULTE'
     Less than or equal.  Repeat as long as the index is less than or
     equal to the upper bound.

`FOR_SGT'

`FOR_UGT'
     Greater than.  Repeat as long as the index is strictly greater
     than the upper bound.  Sometimes `DO' loops go backwards, using a
     negative step value.  For those loops, the comparison operator
     must also be reversed.

`FOR_SGTE'

`FOR_UGTE'
     Greater than or equal.  Repeat as long as the index is greater
     than or equal to the upper bound.  Again, this may be used when
     the step value is negative.

`FOR_SGELE'

`FOR_UGELE'
     These comparisons are only used by the front-end.  In FORTRAN, it
     may not be possible to determine the direction of a loop at
     compile time.  For example, if the step value is not a constant,
     it could be either positive or negative.  These comparison
     operators indicate that the loop test may be either "greater than
     or equal" or "less than or equal", depending on the sign of the
     step value.  The expander's cleanup pass converts any `tree_for'
     nodes with these tests to two `tree_for' nodes and a `tree_if'
     node to decide between them.  Thus, these comparison operators
     should never be encountered in most SUIF code.

`FOR_EQ'

`FOR_NEQ'
     Equal and not equal.  These comparisons are only used by the
     front-end.  The expander's cleanup pass dismantles `tree_for'
     nodes that use these comparisons.

   The body of a `tree_for' loop is stored in a tree node list.  The
methods to get and set the loop body are `body' and `set_body',
respectively.  The `body' list contains only the instructions
corresponding to the body of the loop in the source program.  The
instructions to compare the index variable with the upper bound,
increment it, and branch back to the beginning of the body are not
included as part of the body; they are created when the `tree_for' is
expanded to low-SUIF code.

   Besides the loop body, a `tree_for' node has an additional tree node
list called the `landing_pad'.  The code in the landing pad is executed
if and only if the loop body is executed at least one time, but the
`landing_pad' is executed only once, unlike the body which is usually
executed many times.  The `landing_pad' is executed immediately before
the first time through the loop body.  The landing pad thus provides a
place to move loop-invariant code.

   Two labels are associated with a `tree_for': `contlab' and `brklab'.
A "continue" statement in the loop body requires a jump over the rest
of the body to the code that increments the index and continues with
the next iteration.  This can be implemented with a jump to the
`contlab' label, which is implicitly located at the end of the `body'
list.  Similarly, a "break" statement in the loop is translated to a
jump to the `brklab' label which is located immediately after the loop.
These two labels must be defined in the scope of the `tree_for' node,
but the label instructions that mark their locations are not inserted
into the tree node lists until the `tree_for' node is expanded into
low-SUIF form.

   In summary, the semantics of a `tree_for' node are as follows.  The
lower bound, upper bound, and step operands are evaluated once at the
beginning of the loop (1).  The lower bound is compared to the upper
bound.  If the test fails, the loop does not execute.  Otherwise, the
lower bound is assigned to the index variable, and any code in the
landing pad list is executed.  After that, the body is executed
repeatedly and the index variable is incremented by the step value on
every iteration, until the index variable fails the test with the upper
bound value.

   As an example, the following C code could be translated into the SUIF
code shown in a simplified form below:

     for (i = 100; i >= 0; i--) {
         A[i] = i;
     }

     FOR (Index=i Test=SGTE Cont=L:__L1 Brk=L:__L2)
     FOR LB
         ldc 100
     FOR UB
         ldc 0
     FOR STEP
         ldc -1
     FOR LANDING PAD
     FOR BODY
         str e1 = i
           e1: array e2+0, size(32), index(i), bound(e3)
             e2: ldc <A,0>
               e3: ldc 101
     FOR END

   ---------- Footnotes ----------

   (1) The code produced directly by the C front-end assumes that the
upper bound and step operands are reevaluated on every iteration.  The
expander's cleanup pass dismantles any `tree_for' nodes for which it
cannot guarantee that these semantics are equivalent.

\x1f
File: suif1.info,  Node: Block Nodes,  Next: Procedure Nodes,  Prev: For Nodes,  Up: Tree Nodes

Block Nodes
-----------

   A `tree_block' node introduces a new scope.  Nested scopes are
useful for retaining scope information from source programs and for
debugging purposes.  They are also very useful for implementing code
transformations.  For example, name conflicts are easily avoided by
introducing new scopes.

   A `tree_block' node contains a `block_symtab' symbol table and a
tree node list for the body.  The symbol table is accessed with the
`symtab' and `set_symtab' methods.  The `body' and `set_body' methods
are used to get and set the list of tree nodes inside the block.

   There is a one-to-one correspondence between a `tree_block' and its
symbol table, and the hierarchy of symbol tables within a procedure must
parallel the hierarchy of `tree_block' nodes.  When inserting a
`tree_block' into an AST, the new block's symbol table must be inserted
in the appropriate place in the symbol table hierarchy.  When a
`tree_block' is destroyed, the associated symbol table is detached from
its parent table and destroyed.  However, the converse is not
true--when a `block_symtab' is deleted, the corresponding `tree_block'
node is not deleted.

   The entries in a block's symbol table may not be referenced from
outside the block.  There are no other restrictions on `tree_block'
nodes.  The bodies may be empty or contain any kinds of tree nodes.
Blocks are usually entered from the beginning but that is not required;
unlike other AST nodes, branches into the middle of a block are allowed.

   As an example, the following code creates a new `tree_block' and its
associated symbol table.  It then adds the new block to the body of an
existing block node:

     block_symtab *new_symtab = new block_symtab("my_symtab");
     cur_block->symtab()->add_child(new_symtab);
     tree_node_list *tl = new tree_node_list;
     tree_block *new_block = new tree_block(tl, new_symtab);
     cur_block->body()->append(new_block);

\x1f
File: suif1.info,  Node: Procedure Nodes,  Prev: Block Nodes,  Up: Tree Nodes

Procedure Nodes
---------------

   A special kind of block node is used as the root of each AST.  These
`tree_proc' nodes are derived from the `tree_block' class.  They are
essentially the same as other block nodes, but they include a few extra
methods and have a slightly different kind of symbol table.  SUIF does
not support nested procedures, so `tree_proc' nodes may only be used at
the roots of ASTs.

   A procedure node's symbol table must be a `proc_symtab' instead of
just an ordinary `block_symtab'.  The `proc_syms' method is provided to
cast the symbol table pointer to be a `proc_symtab'.  A `tree_proc'
node also has a pointer to the symbol of the corresponding procedure.
This pointer is set automatically when a `tree_proc' is attached to the
procedure symbol.  For any tree node in an AST, the `proc' method
retrieves this procedure symbol from the `tree_proc' at the root of the
tree.

   Because `tree_proc' nodes are always at the roots of the ASTs, their
`parent' list pointers (*note Other Node Features::.) are always `NULL'.

\x1f
File: suif1.info,  Node: Tree Node Lists,  Next: Mapping Subtrees,  Prev: Tree Nodes,  Up: Trees

Tree Node Lists
===============

   A `tree_node_list' is a doubly-linked list of tree nodes, derived
from the `dlist' class.  *Note Doubly-Linked Lists::.  Most nodes in an
AST have their children recorded in tree node lists.  For example, the
body of a block node is a tree node list.  Besides the standard list
features, each tree node list includes a back-pointer to its parent tree
node.  These pointers are maintained automatically by the SUIF library
and can be accessed using the `parent' method.  In addition, each node
on a tree node list contains pointers back to the list and the list
element.  *Note Other Node Features::.  These pointers are set by the
`set_elem' method (*note Generic Lists::.) which is automatically
called every time an element is added to the list.

   In a `tree_for' node, the lower bound, upper bound, and step value
are usually treated as operands; however, the operands are actually
stored as tree node lists.  *Note For Nodes::.  Each of these lists is
required to contain a single expression with a dummy copy instruction at
the root.  The destination of the dummy copy must be a null operand.
The `tree_node_list' class includes several methods to handle these
special lists.  The `is_op' method checks if the list consists of a
single copy instruction with a null destination.  The `op' method
retrieves the operand stored in the list.  If after converting the list
to expression tree form, the `is_op' method returns `TRUE', the `op'
method returns the source operand of the dummy copy instruction;
otherwise, an error occurs.  The `set_op' method is used to set the
contents of the tree node list to a dummy copy instruction with the
specified operand as its source.  The list must either be empty or
already contain the dummy copy.  Finally, the `op_is_intconst' method
checks if the operand in the tree node list is a constant integer, and
if so, returns the value.

   Tree node lists can easily be printed out as text.  The `print'
method simply iterates through the list and calls the `print' method
for each tree node.  The optional `depth' parameter specifies the
indentation level to be used.  A separate method is used to print tree
node lists that hold `tree_for' operands.  If the `is_op' method for
one of these lists returns `TRUE', the `print_expr' method prints the
operand directly.  Otherwise, it prints the list as usual.

\x1f
File: suif1.info,  Node: Mapping Subtrees,  Prev: Tree Node Lists,  Up: Trees

Mapping Functions Over Subtrees
===============================

   Many SUIF programs contain code that visits all of the nodes in an
AST to perform various operations.  Rather than having every programmer
duplicate the code for this traversal, the SUIF library includes methods
to map functions over ASTs.  The `tree_node' and `tree_node_list'
classes both provide these `map' methods.

   The function to be mapped must be of type `tree_map_f'.  For a tree
node, the `map' method applies the function to the tree node and all of
its children.  The `preorder' parameter is used to select either
preorder or postorder traversals; the default is preorder.  For
preorder traversals, the function is applied to the tree node before it
is applied to the children.  For postorder, the function is first
applied to the tree_node's children and descendants and then last
applied to the tree node itself.

   The `map' method for a tree node list calls `map' for each node in
the list.  The nodes are visited in order from first to last regardless
of the `preorder' parameter.  The `tree_node_list' version of the `map'
method has an extra optional parameter that allows you to only map the
function over the entries in the list without recursively visiting
their children.

   The `tree_map_f' functions have two parameters: a pointer to the
tree node and a `void*' value passed on from the `map' method.
Additional parameters can be passed by making the `void*' value a
pointer to a structure containing the parameters.  For example, the
following code counts the number of `tree_for' and `tree_loop' nodes in
a procedure:

     struct count_result {
         int num_fors;
         int num_loops;
     };
     
     void count_loops (tree_node *t, void *x)
     {
         count_result *results = (count_result *)x;
     
         if (t->kind() == TREE_FOR) results->num_fors++;
         else if (t->kind() == TREE_LOOP) results->num_loops++;
     }
     
     /*
      *  Return the number of tree_fors and tree_loops in the procedure.
      */
     
     void counter (tree_proc *p, int *for_count, int *loop_count)
     {
         count_result results;
         results.num_fors = 0;
         results.num_loops = 0;
     
         p->map(count_loops, (void *)&results);
     
         *for_count =  results.num_fors;
         *loop_count = results.num_loops;
     }

\x1f
File: suif1.info,  Node: Instructions,  Next: Symbols,  Prev: Trees,  Up: Top

Instructions and Expression Trees
*********************************

   At the leaves of the abstract syntax trees, the `tree_instr' nodes
(*note Instruction Nodes::.) hold SUIF instructions.  Each instruction
performs a single operation, specified by its opcode.  With just a few
exceptions, the opcodes are simple and straightforward, similar to the
instruction set of a typical RISC processor.  The instructions include
arithmetic, data transfer, and control flow operations.

   SUIF instructions may be used in two ways.  Most high-level passes
use expression trees, where the instructions are grouped together in
trees that correspond to the expressions in the source programs.
Back-end optimization passes have traditionally worked with flat lists
of instructions, and SUIF supports that representation as well.

   The files `instruction.h' and `instruction.cc' contain the code for
the SUIF instruction classes.

* Menu:

* Basic Features::              Features shared by all kinds of instructions.
* Operands::                    Instruction operands.
* Expression Trees::            How to use expression trees.
* Three Operand Instructions::  The `in_rrr' class (most instructions).
* Branch and Jump Instructions::  The `in_bj' class.
* Load Constant Instructions::  The `in_ldc' class.
* Call Instructions::           The `in_cal' class.
* Array Instructions::          The `in_array' class.
* Multi-way Branch Instructions::  The `in_mbr' class.
* Label Instructions::          The `in_lab' class.
* Generic Instructions::        The `in_gen' class (non-standard).

\x1f
File: suif1.info,  Node: Basic Features,  Next: Operands,  Up: Instructions

Basic Instruction Features
==========================

   All instructions share some basic features.  This section describes
the fields in the base `instruction' class.  Other classes are derived
from the `instruction' class to include fields that are specific to the
different instruction formats.

   Besides the features below, the instructions have ID numbers that
can be used to identify them across passes of the compiler.  This is
discussed in detail elsewhere.  *Note ID Numbers::.

   The SUIF library also declares an `instruction_list' class for
working with lists of pointers to instructions.  This class is not used
much within the library itself because SUIF does not store instructions
directly on lists.  Even with the flat list form, the instructions are
contained in `tree_instr' nodes, which in turn are stored in lists.
However, it may sometimes be convenient to work with lists of
instruction pointers even if those instructions are actually stored in
`tree_instr' nodes.

* Menu:

* Opcodes and Formats::         Description of opcode and format enumerations.
* Destination Operands::        Conventions for the destination operands.
* Result Types::                Specifying the types of the result values.
* Parent Tree Nodes::           Back-pointers to the `tree_instr' nodes.
* Source Operands::             Standard methods for accessing sources.
* Printing Methods::            Printing instructions and operands as text.

\x1f
File: suif1.info,  Node: Opcodes and Formats,  Next: Destination Operands,  Up: Basic Features

Opcodes and Formats
-------------------

   The `opcode' and `set_opcode' methods may be used to access the
opcode field in an instruction.  These opcodes are members of the
`if_ops' enumerated type.  The internal names for the opcodes all begin
with `io_', but that prefix is omitted in this documentation.  The
`if_ops_name' function takes an opcode and returns a character string
holding the opcode name (without the `io_' prefix).  This is used by
the library when it prints out instructions, but you may also call it
directly.

   Each opcode is associated with a particular instruction format.  The
formats are specified by members of the `inst_format' enumeration.  The
`format' method may be used to retrieve the format for a particular
instruction.  Alternatively, the `which_format' function takes an
opcode and returns its format without reference to any particular
instruction.  Each format corresponds to a particular derived
instruction class:

`inf_rrr'
     Three operand instructions use the `in_rrr' class.

`inf_bj'
     Branch and jump instructions use the `in_bj' class.

`inf_ldc'
     The load constant instruction uses the `in_ldc' class.

`inf_cal'
     The call instruction uses the `in_cal' class.

`inf_array'
     The array instruction uses the `in_array' class.

`inf_mbr'
     The multi-way branch instruction uses the `in_mbr' class.

`inf_lab'
     The label instruction uses the `in_lab' class.

`inf_gen'
     Generic instructions use the `in_gen' class.

   The `format' method is often used in `switch' statements for dealing
with different kinds of instructions.  For example, the following code
computes the number of source operands in an instruction (instead of
using the `num_srcs' method):

     instruction *i;
     switch (i->format()) {
         case inf_rrr: {
             n += 2;
             break;
         }
         case inf_bj: {
             n += 1;
             break;
         }
         case inf_cal: {
             in_cal *cali = (in_cal *)i;
             n += 1 + cali->num_args();
             break;
         }
         case inf_array: {
             in_array *arri = (in_array *)i;
             n += 2 + 2 * arri->dims();
             break;
         }
         case inf_mbr: {
             n += 1;
             break;
         }
         case inf_gen: {
             in_gen *geni = (in_gen *)i;
             n += geni->num_srcs();
             break;
         }
         default: {
             /* other formats (inf_ldc and inf_lab) have no source operands */
             break;
         }
     }

   The opcodes and instruction formats are defined in the `opcodes.h'
and `opcodes.cc' files.

\x1f
File: suif1.info,  Node: Destination Operands,  Next: Result Types,  Prev: Opcodes and Formats,  Up: Basic Features

Destination Operands
--------------------

   The base `instruction' class includes a field for the destination
operand, even though not all instructions use it.  The `dst_op' method
returns the value of this operand.  If an instruction does not produce
a result, the destination operand should always be a null operand.
Moreover, the destination may be null even if an instruction does
produce a result.  In that case, the result value is computed and then
discarded.

   If the destination operand is a variable, its type must be compatible
with the result type of the instruction.

   If the result of an instruction is a temporary value, the destination
operand is a pointer to the instruction where the value is used.  Note
that this is different than an instruction pointer in a source operand.
The source operands of an instruction point to the children in an
expression tree, while the destination operand points to the parent
instruction.

   The `set_dst' method may be used to set the destination operand for
an instruction.  However, there are some important restrictions on using
this method:

   * For derived classes with instructions that never produce result
     values, it is illegal to call `set_dst'.  This allows the library
     to ensure that the destination will always be a null operand (1).
     Trying to use `set_dst' for one of these instructions will cause an
     error.

   * You may not set the destination operand to point to another
     instruction; trying to do so will cause an error.  This is to
     prevent inconsistent pointers.  The destination should only point
     to another instruction if that other instruction has a source
     operand that points back to it.  Thus, the library automatically
     sets the destination operand when an instruction is used as a
     source operand.

   * If the destination operand already contains a pointer to another
     instruction, you cannot use `set_dst' to overwrite it.  This also
     causes a run-time error.  As in the previous case, this is to
     prevent inconsistent pointers.  Instead, you must first call the
     instruction's `remove' method to clear the destination operand.
     *Note Source Operands::.

   ---------- Footnotes ----------

   (1) Note that for other classes it is your responsibility to make
sure that the destination is null if the instruction does not produce a
result.

\x1f
File: suif1.info,  Node: Result Types,  Next: Parent Tree Nodes,  Prev: Destination Operands,  Up: Basic Features

Result Types
------------

   Each instruction also has a field to specify the result type.  The
`result_type' and `set_result_type' methods may be used to access this
field.  If an instruction produces a result value (regardless of
whether the result is actually used), the type of the result must be
indicated.  Otherwise, the result type should be the SUIF `void' type.

   If the instruction produces a value, the result type must be an
object type (i.e. not a function type) with non-zero size and that size
must be known at compile time.  This restriction is to exclude arrays
with unknown or symbolic bounds, the only types without known sizes.

\x1f
File: suif1.info,  Node: Parent Tree Nodes,  Next: Source Operands,  Prev: Result Types,  Up: Basic Features

Parent Tree Nodes
-----------------

   Each instruction automatically records the `tree_instr' node to
which it is attached.  The `parent' method retrieves this pointer.  In
an expression tree, all of the instructions share the same parent
`tree_instr' node, so an instruction may not be directly connected to
its parent node.

   The `owner' method is identical to the `parent' method except for
instructions that are used as operands of `tree_for' nodes.  Those
operands are actually attached to dummy copy instructions on lists
attached to the `tree_for' nodes (*note For Nodes::.), but many users
will want to treat them as if they are directly attached to the
`tree_for' nodes.  Thus, for an instruction in a `tree_for' operand,
the `owner' method will return a pointer to the `tree_for' node instead
of returning the actual parent `tree_instr'.  This only works if the
`tree_for' operand list contains a single expression (not a flat list);
otherwise, the actual `tree_instr' parent is returned.

\x1f
File: suif1.info,  Node: Source Operands,  Next: Printing Methods,  Prev: Parent Tree Nodes,  Up: Basic Features

Source Operands
---------------

   Even though the base `instruction' class does not contain any source
operand fields, it does provide several methods to access the source
operands in derived classes.  First, the `num_srcs' method returns the
number of source operands in a particular instruction.  Once you know
the number of sources, you can access them by number.  This is
frequently useful when you need to visit all of the source operands
without concern for how they are used in the instruction.  The `src_op'
and `set_src_op' methods provide this access.  The operands are
numbered beginning from zero (like arrays in C).  Specifying an operand
number that does not exist will cause an error.  Do not use these
methods to access a particular operand field in an instruction; the
operand numbering used here is implementation-defined and subject to
change.

   The `src_map' method provides an alternate way to visit all of the
source operands.  It applies a function that you specify to all of the
source operands.  This can be used to implement recursive descents of
expression trees by making the mapped function call `src_map' if the
operand is an instruction.  This is similar to what the `instr_map'
method in the `tree_instr' class does.  *Note Instruction Nodes::.  The
mapped function must match the `src_map_f' type which has three
parameters: a pointer to the instruction, a pointer to a copy of the
operand, and a `void*' value used to pass any other information needed
by the function.  If the function returns `TRUE', the copy of the
operand will be assigned to the actual operand field within the
instruction.  If it returns `FALSE', the source operand field is not
modified.

   The SUIF library requires that instruction pointers in operands be
consistent.  That is, a source operand may only point to an instruction
if the destination of that instruction points back to where the result
value is used.  Because of this, you cannot simply overwrite a source
operand that contains an instruction pointer.  Doing so would leave the
other instruction with an inconsistent destination operand.  Instead,
you must first use the source operand's `remove' method.  This clears
the instruction pointers in both the source and destination operands.
If the source instruction was part of an expression tree (i.e. it
didn't have its own parent `tree_instr' node), `remove' also clears its
`parent' pointer by calling the parent's `remove_instr' method (*note
Instruction Nodes::.).  If the source operand is not an instruction,
the `remove' method does nothing so it is always safe to use it.  The
`instruction' class also has a `remove' method which does the same
thing.

   As an example, the following code clears all of the source operands
in an instruction:

     for (int n = 0; n < i->num_srcs(); n++) {
         i->src_op(n).remove();
         i->set_src_op(n, operand());
     }

\x1f
File: suif1.info,  Node: Printing Methods,  Prev: Source Operands,  Up: Basic Features

Printing Methods
----------------

   Instructions can be printed out as text using the `print' method.
The optional `depth' parameter specifies the indentation level for the
output.  The `elab' and `en' parameters are also optional and are only
used when printing sub-expressions.  Most users should never need to
worry about these extra parameters.  The `elab' parameter is the number
for the label attached to the instruction, and the `en' parameter is
the next number to be used for labeling subexpressions.

\x1f
File: suif1.info,  Node: Operands,  Next: Expression Trees,  Prev: Basic Features,  Up: Instructions

Operands
========

   Most SUIF instructions have operands that are represented by objects
of the `operand' class, which is implemented in the files `operand.h'
and `operand.cc'.  An operand may have three different kinds of values:

   * It may be a null operand.  The `is_null' method tests for this
     case.  Null operands occur when an operand field in an instruction
     is unused.

   * An operand may refer directly to the symbol for a variable.  The
     `is_symbol' method tests for this case.  The `symbol' and
     `set_symbol' methods access the symbol field.  A variable in a
     source operand indicates that the contents of the variable are
     used.  In a destination operand, a variable is assigned the result
     of the instruction.

   * An operand may also point to another instruction.  The `is_instr'
     method tests for this, and the `instr' and `set_instr' methods
     access the pointer field.  This is used to implement expression
     trees and, in low-SUIF, to refer to the results of other
     instructions in a flat list.  An instruction pointer in a source
     operand means that the result of that instruction is used as the
     operand.  Conversely, an instruction pointer in a destination
     operand indicates that the result value is used by that
     instruction.

   The `is_expr' method is very similar to `is_instr'.  Besides
checking if the operand holds an instruction pointer, it also tests if
that instruction is a subexpression that is not contained in a separate
`tree_instr' node (i.e. it's not in a flat list).  This method should
not be used for destination operands.

   Before changing a source operand from an instruction pointer to some
other value, the instruction must be removed.  The `remove' method
checks if the operand is an instruction, and if so, calls the
instruction's `remove' method.  *Note Source Operands::.

   The operand class includes several methods to simplify common
operations.  One frequently needs to know the type of a particular
operand.  This can be determined from the variable's type or the
instruction's result type, but checking for these different kinds of
operands and then extracting the type is cumbersome.  Instead, you can
use the `type' method which performs this operation for you.  It
returns the SUIF `void' type for null operands.  Another common
operation is testing an operand to see if it contains an integer
constant from a load constant instruction.  The `is_const_int' method
checks if this is the case, and if so, it also returns the value of the
constant.

   Operands have two different methods for printing themselves out to a
file as text.  The `print' method is used by the library when printing
instructions.  Because source and destination operands are handled
differently, `print' requires that you specify the instruction that
contains the operand so that it can determine how the operand is being
used.  However, when debugging a program, you may not know which
instruction contains an operand.  If you do know that it is used as a
source operand, you can use the `print_source' method to print it
without specifying the instruction.

\x1f
File: suif1.info,  Node: Expression Trees,  Next: Three Operand Instructions,  Prev: Operands,  Up: Instructions

Expression Trees
================

   SUIF supports both expression trees and flat lists of instructions.
Procedures are always written out as flat lists.  After a procedure body
has been read from an input file, it can be converted to expression tree
form.  The `read_proc' method for the procedure symbol has a flag that
allows you to specify this; by default it builds the expression trees.
You may also do the conversion manually as described below.  When the
procedure body is written out, it is automatically converted back to
the flat list form.

   In the flat list form, each SUIF instruction has its own
`tree_instr' node.  With expression trees, the only change is that all
of the instructions within an expression are grouped under the same
`tree_instr' node.  The instruction pointers in the operand fields do
not change.

   Up to now we have implied that high-SUIF uses expression trees and
that low-SUIF uses the flat list representation, but the decision to use
expression trees is actually independent from the structure of the ASTs.
SUIF allows expressions trees to be used even if all of the high-level
control structures have been removed, and conversely the flat list
representation works with all kinds of AST nodes (although accessing the
`tree_for' operands is a little awkward).  In fact, the two
representations can even be mixed in the same procedure!

   Some caution is needed here.  These two representations are not
equivalent.  An expression tree only specifies a partial order for the
evaluation of the instructions in the tree, whereas a flat list is a
total ordering.  Similarly, while flat lists allow you to intermix the
instructions from different expressions, with expression trees each
expression must be completely evaluated before proceeding to execute the
instructions for the next expression.  Thus, flat lists give you precise
control of the execution order for the instructions.  Because of this,
if you reorder the instructions in a flat list and then try to convert
to expression trees, the library may complain and promote temporaries to
variables in order to maintain the equivalent semantics.

   Methods are provided in the `tree_node_list' class to convert back
and forth between expression trees and flat lists.  The `flatten'
method converts all of the expression trees in the list and its child
lists to flat lists of instructions.  This is simply a matter of
creating new `tree_instr' nodes to hold the subexpressions and
inserting them into the lists.

   The `cvt_to_trees' method converts a tree node list to expression
tree form.  This does not actually change the instructions, but rather
collects the instructions within an expression under a single
`tree_instr' node.  Only contiguous instructions can be converted into
an expression tree.  If other instructions from outside the expression
are intermixed, building the expression tree may change the behavior of
the code.  Thus, if this occurs, the library will print a warning
message and split up the expression tree so that the original semantics
are preserved.

\x1f
File: suif1.info,  Node: Three Operand Instructions,  Next: Branch and Jump Instructions,  Prev: Expression Trees,  Up: Instructions

Three Operand Instructions
==========================

   The vast majority of SUIF instructions are represented by the
`in_rrr' class which includes fields for two source operands.  Not all
of the operands have to be used.  For example, `nop' instructions don't
use any operands at all.

   The `src1_op' and `src2_op' methods retrieve the source operands,
and the `set_src1' and `set_src2' methods assign new operands.  Besides
the methods to directly access the two source operands, other methods
are provided to refer to these sources according to their uses with
specific opcodes:

   * Shift and rotate instructions (`asr', `lsl', `lsr', and `rot') may
     use the `shift_cnt_op' and `set_shift_cnt_op' methods to access
     the operand that specifies the numbers of bits to shift or rotate.
     The other source operand may be accessed with the `src_op' and
     `set_src' methods.

   * Store (`str') and memory copy (`memcpy') instructions may use the
     `dst_addr_op' and `set_dst_addr_op' methods to access the source
     operand that holds the destination address for the memory
     reference.

   * Load (`lod') and memory copy (`memcpy') instructions may use the
     `src_addr_op' and `set_src_addr_op' methods to access the operand
     that specifies the source address for the memory reference.  Note
     that the actual operand field that is used is different for these
     two opcodes.

   * Instructions that only use one of the source operands may use the
     `src_op' and `set_src' methods without specifying whether the
     first or second operand field is used.  In addition, a store
     (`str') instruction may use these methods to refer to the operand
     holding the value to be stored.  They are also used by shift and
     rotate instructions as described above.

Using these opcode-specific methods with the wrong opcodes will cause
errors.

   For your convenience, the `in_rrr' class provides a method,
`is_unary', to determine if an instruction produces a result value
using only one of the source operands.  It does not consider return
(`ret') instructions to be unary because they do not produce result
values.  Although load (`lod') instructions fit the pattern, they are a
special case and are not considered to be unary.

   The `is_commutative' method checks the opcode of an instruction to
determine if it is a commutative operation.  If so, the two source
operands should be interchangeable.

   Some of the arithmetic instructions may generate run-time exceptions
if the appropriate class of exceptions is enabled (*note Miscellaneous
Annotes::.).  If the exceptions are not enabled, the rules for ANSI C
are used to determine the result.

   The following table lists all of the three operand SUIF instructions.
Each entry describes the operands used with that opcode and includes any
restrictions on the operand and result types.

`nop'
     Do nothing at all.  All of the operands for these instructions
     should be null, and the result type should be the SUIF `void' type.

`lod'
     Load the value at the address contained in the `src1' operand and
     put it in the `dst' operand.  The result type indicates the type
     of the value being loaded and may be any type, subject to the usual
     restrictions on a result type (*note Result Types::.).  The type
     of the expression in `src1' must be a pointer to the result type.
     The `src2' operand is not used.

`str'
     Store the value in the `src2' operand at the address contained in
     the `src1' operand.  Both operands must be specified.  There is no
     special restriction on the type of the `src2' operand, though the
     restrictions on instruction result types (*note Result Types::.)
     and variables (*note Variable Symbols::.) guarantee it will have a
     known, non-zero size.  The `src1' operand should contain an
     expression that is a pointer to the type of the operand being
     stored.  The `dst' operand is not used.

`memcpy'
     Memory to memory copy.  Load the value from the address in the
     `src2' operand and store it at the address in the `src1' operand.
     The type of the object to be copied is subject to the same
     conditions as the result type of an instruction (*note Result
     Types::.), so it must have known, non-zero size.  Both of the
     source operands must be pointers to this object type.  The `dst'
     operand is not used.

`cpy'
     Copy the `src1' operand to the `dst' operand.  The `src2' operand
     is not used.  The result type must be the same as the type of the
     source operand.  The restrictions on instruction result types
     (*note Result Types::.) guarantee that the object being copied has
     known, non-zero size.

`cvt'
     Convert the `src1' operand to the result type and put it in the
     `dst' operand.  The `src2' operand is not used.  Nothing can can
     be converted to or from a `struct', `union', `array', or `void'
     type.  Pointer types can only be converted to and from integer
     types and other pointer types.

`neg'
     Negation.  Change the sign of the value in the `src1' operand and
     put the result in the `dst' operand.  The `src2' operand is
     unused.  The result type and the type of the operand must be the
     same signed integer or floating-point type.

`add'
     Add the values in the `src1' and `src2' operands and put the
     result in the `dst' operand.  Except for pointer additions, the
     result type and the types of the operands must be the same integer
     or floating-point types.  Pointer addition is a special case.  One
     of the source operands may have a pointer type, as long as the
     other source operand has signed or unsigned integer type of any
     size; the result type must also be a pointer type, but need not be
     the same as the source pointer type.

`sub'
     Subtract the value in the `src2' operand from the value in the
     `src1' operand and put the result in the `dst' operand.  Except
     for pointer subtractions, the result type and the types of the
     operands must be the same integer or floating-point types.  There
     are two special cases for pointer subtractions.  In either case,
     the `src1' operand must have a pointer type.  First, the `src2'
     operand may have any integer type, in which case the result type
     may be any pointer type, not necessarily the same as the source
     pointer type.  Second, the `src2' operand's type may be another
     pointer, in which case the result type must be type_ptr_diff.

`mul'
`div'
     Multiply or divide the value in the `src1' operand by the value in
     the `src2' operand and put the result in the `dst' operand.  The
     result type and the types of the operands must be the same integer
     or floating-point type.  Integer multiplication and division are
     defined according to the rules for ANSI C.

`rem'
`mod'
     Remainder and modulus.  These two instructions are very similar.
     Both divide the value in the `src1' operand by the value in the
     `src2' operand to find the remainder or modulus.  The `rem'
     instruction is identical to the modulus operator in ANSI C.  That
     is, if either source operand is negative, the sign of the result is
     undefined and depends on the semantics of integer division.  The
     `mod' instruction is the same except that its result is always
     guaranteed to be positive.  The result type and the types of the
     destination and source operands must be the same integer type.

`not'
     Bit-wise inversion.  Compute the one's complement negation of the
     value in the `src1' operand and put the result in the `dst'
     operand.  The `src2' operand is not used.  The result type and the
     types of the operand must be the same unsigned integer type.

`and'
`ior'
`xor'
     Compute the bit-wise AND, inclusive OR, or exclusive OR of the
     values in the `src1' and `src2' operands and put the result in the
     `dst' operand.  The result type and the type of the operands must
     be the same unsigned integer type.

`asr'
`lsr'
`lsl'
     Shift the value in the `src1' operand right or left by the amount
     specified in the `src2' operand.  The variable in the `src2'
     operand must always have an unsigned integer type.  The `asr'
     instruction performs sign extension and requires that the result
     type and the type `src1' operand be the same signed integer type.
     The `lsr' instructions does not perform sign extension and requires
     that the result type and type of the `src1' operand be the same
     unsigned integer type.  Sign extension is not an issue for left
     shifts, so the `lsl' instruction only requires that the result
     type and the type of the `src1' operand be the same integer type.

`divfloor'
`divceil'
     Division combined with floor and ceiling operations.  The
     `divfloor' opcode means take the rational quotient of the `src1'
     operand by the `src2' operand and apply the floor operation (i.e.
     round to the nearest integer less than or equal to the quotient).
     The `divceil' opcode means take the rational quotient of the
     `src1' operand by the `src2' operand and apply the ceiling
     operation (i.e. round to the nearest integer greater than or equal
     to the quotient).  The result type and the operand types must be
     the same integer type.

`min'
`max'
     Minimum and maximum.  The result value is the minimum or maximum,
     respectively, of the two source operands.  The result type and the
     operand types must be the same integer or floating-point types.

`abs'
     Absolute value.  Compute the absolute value of the `src1' operand.
     The `src2' operand is unused.  The result type and the source
     operand type must be the same integer or floating-point type.

`rot'
     Rotate the value in the `src1' operand left or right by the amount
     specified in the `src2' operand.  The variable in the `src2'
     operand must always have a signed integer type.  If the shift
     amount is positive, the value is rotated to the left (toward the
     most-significant bit); if it is negative, the value is rotated to
     the right.  The result type and the type of the `src1' operand must
     be the same integer type.

`seq'
`sne'
`sl'
`sle'
     Comparison instructions.  If the `src1' operand is equal, not
     equal, less than, or less than or equal, respectively, to the
     `src2' operand, assign the integer value one to the `dst' operand.
     Otherwise, set the `dst' operand to zero.  The result type must
     always be a signed integer type.  The source operands must have
     integer, enumerated, floating point, or pointer type.

`ret'
     Return from a procedure.  Only the `src1' operand is used and it
     is optional.  If specified, it is the return value and may contain
     an operand of any type except array or function types.  If the
     procedure's function type has void return type, the operand must be
     null; otherwise the operand must not be null and must have the same
     type as the return type of the procedure.

`mrk'
     This pseudo-instruction only marks a position in the program and
     is used to hold miscellaneous annotations such as line numbers.
     It is functionally equivalent to a `nop' instruction.  All of the
     operands for these instructions should be null, and the result type
     should be the SUIF `void' type.

\x1f
File: suif1.info,  Node: Branch and Jump Instructions,  Next: Load Constant Instructions,  Prev: Three Operand Instructions,  Up: Instructions

Branch and Jump Instructions
============================

   The `in_bj' class is used to hold branch and jump instructions.
This class includes a field to specify the label symbol at the branch
target and an optional source operand that is used for conditional
branches.  The `target' and `set_target' methods are used to access the
label symbol for the branch target.  This label must be defined in the
scope where the branch occurs, and it must be within the same
procedure.  The `src_op' and `set_src_op' methods access the optional
source operand field.  The `dst' operand is unused for all branch and
jump instructions and the result type should always be the SUIF `void'
type.  The branch and jump opcodes are described below:

`jmp'
     Unconditional jump.  The source operand is unused.  The flow of
     control is unconditionally transferred to the code at the target
     label.

`btrue'
     Branch if true.  If the source operand, which must have an signed
     integer type, contains a true (non-zero) value, the flow of
     control is transferred to the code at the target label.
     Otherwise, it continues with the next instruction in sequential
     order.

`bfalse'
     Branch if false.  If the source operand contains a false (zero)
     value, the flow of control is transferred to the code at the
     target label.  Otherwise, it continues with the next instruction
     in sequential order.  The source operand must have an signed
     integer type.