Indirect Triples

Indirect triples represent a program as a list of pointers to triples — the instruction array — kept separately from the triple table itself. The order of execution is given by the pointer list, not by the triples' own positions.

Plain triples number each operation by its position in the table and refer to a result through that position (n). The trouble is that the position is the identity: move a triple and every (n) reference must be renumbered.

Indirect triples add one level of indirection. The triples are stored once, with fixed numbers, and a short array of pointers names them in program order. To change the program order you rearrange the pointers; the triples never move.

We translate the same assignment used throughout the chapter.

This compiles to four triples. Each triple holds an operator and two arguments; a result is referenced by the triple's own position (n).

Triple table

With indirect triples we keep that table and add an instruction array of pointers giving the program order. (The instruction array is shown starting at address 35 to stress that its own indices are unrelated to the triple numbers.)

Execution walks the instruction array top to bottom: positions 35, 36, 37, 38, which point to triples (0), (1), (2), (3). So the program still runs a + b, then c - d, then the multiply, then the assignment — the indirection changes how order is stored, not the computation.

An optimizer constantly reorders, inserts, and deletes statements. With indirect triples it does this by editing only the short pointer list; the triples keep their original numbers, so every (n) reference stays valid.

Reordering — one line. Suppose we want statement (3) to run earlier. We just permute the instruction array:

The triple table is untouched — (2) still says \* (0) (1), and (3) still says = x (2). With plain triples, moving an operation would shift its position and force every reference to it to be renumbered.

Sharing identical triples. If the same subexpression is computed twice, both occurrences can be two pointers to the same triple. The triple exists once; the instruction array references it wherever needed — direct support for common-subexpression reuse.

All three encode three-address code; they differ in how a result is named and how easily code can be rearranged.

Quadruples buy easy reordering by spending a result field on every line; indirect triples get the same flexibility by paying for one small pointer array instead, while the triples stay compact and stable.

• Two structures. Indirect triples = a triple table plus an instruction (pointer) array that lists triples in execution order.
• Order lives in the pointers. The program runs in the order of the pointer array, not the order triples sit in the table.
• No renumbering. Reorder, insert, or delete by editing the pointer array; triple numbers (n) stay fixed, so references never break.
• Sharing. Identical triples can be pointed to from several instructions — built-in common-subexpression reuse.
• Cost. One extra O(n) array of pointers, in exchange for cheap reordering — unlike plain triples, which are compact but painful to optimize.