Go to the previous, next section.

If Nodes

Nodes from the tree_if class represent "if-then-else" structures. A tree_if contains three tree node lists: the header, the then_part, and the else_part. The header contains code to evaluate the "if" condition and branch to the jumpto label, implicitly located at the beginning of the else_part, if the condition is false. Otherwise it falls through to the then_part. The then_part implicitly ends with a jump around the else_part. The tree_if class provides methods to access all of these parts.

The jumpto label must be defined in the scope containing the tree_if node, but the label position is implicit rather than being marked by a label instruction. When the tree_if is expanded to low-SUIF form, a label instruction for jumpto is inserted at the beginning of the else_part. The jumpto label also has the restriction that it may only be used in the header list of its tree_if; it is illegal to use this label at all in the then_part or else_part, or at all outside the tree_if.

Although the tree node lists within a tree_if can hold arbitrary ASTs, certain conventions must be followed.

The header list is only allowed limited control flow. It may contain tree_instr nodes and other tree_if nodes arbitrarily nested, but it is not allowed any tree_block, tree_for, or tree_loop nodes, even in nested tree_if nodes. Label instructions may be used within the header, but jumps or branches from outside the header into it are not allowed; such a label can only be the target of branches or jumps from elsewhere in the header. Similarly, all of the branch and jump instructions are allowed within the header, but all the target labels must be within the header list with one important exception: branch and jump targets may include the jumpto label of the original tree_if node.

The idea is that the header part contains the computation to figure out whether the then_part or else_part is executed. Often this will be a single conditional branch instruction to the jumpto label. But we want to allow more complex test computations than a single SUIF expression. In particular, we want to be able to capture all the computation in a C test expression, which may contain short-circuit evaluation of && and || operators and partial evaluation of the ?: operator. The front end puts the computation of the test expression of a C if statement in the header of the tree_if it creates. With complex C expressions, it is often useful to use the structured control flow of nested tree_if nodes within the header and that's why they are allowed. It is legal to have an empty header, but any tree_if with an empty header, or even with a header that contains no branch or jump to the jumpto label is degenerate--the then_part will always be executed instead of the else_part.

The then_part and else_part have fewer restrictions. After the front end, in standard SUIF, neither is allowed to have potential jumps or branches in or out, or between the then_part and else_part. Branches or jumps anywhere within the then_part must be to labels elsewhere in the then_part and labels in the then_part may only be used as targets by branches or jumps within the then_part; the same holds separately for the else_part. Note that the symbol table containing a label may be outside the tree_if; it is the label instruction we are concerned with here. If the label instruction is within the else_part, it may only be used as a target by instructions in other sections of the else_part. Any tree_nodes can be used within the then_part and else_part with arbitrary nesting, so long as the restriction on jumps into or out of the top level else_part or then_part lists is honored.

Either or both of the then_part and else_part may be empty lists; in fact the else_part is often empty, as in C there is often an if statements without an else. There is little point in having a tree_if if both part these parts are to be empty, but this may occur if all the code is optimized away or moved elsewhere.

Here's an example. The following C code could be translated into the SUIF code shown in a simplified form below. (The real C front-end generates a more complicated tree that involves nested tree_if structures in the header.)

if ((x > y) && (x > 0)) {
    y = x;
} else {
    y = 0;

IF (Jumpto=L:__L1)
    bfalse e1, L:__L1
      e1: sl y, x
    bfalse e1, L:__L1
      e1: sl e2, x
        e2: ldc 0
    cpy y = x
    ldc y = 0

Go to the previous, next section.