Go to the previous, next section.

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.

Go to the previous, next section.