Indirect Triples in Compiler Design

Definition

Indirect triples combine the compactness of triples with the reordering flexibility of quadruples. Instead of executing triples in array order, an additional array of pointers specifies the execution sequence. Rearranging code requires only reordering the pointer array, not moving the triples themselves.

Structure

Reordering Example

Complete Example

Comparison of All Three Representations

When to Use Indirect Triples

Implementation

Interview Questions

1. Q: What problem do indirect triples solve that regular triples have?

A: Regular triples cannot be reordered without updating all positional references, making optimization difficult. Indirect triples add an indirection layer — reordering only changes the statement pointer array, while triple references remain stable. This gives near-quadruple flexibility with near-triple compactness.

1. Q: Is the extra indirection array worth the overhead?

A: For compilers that perform code scheduling or instruction reordering, yes. The pointer array is small (one integer per instruction). Without it, every optimization pass that moves code would need to renumber all references — an error-prone O(n) operation per move. With indirection, moves are O(1).

1. Q: How does CSE work with indirect triples?

A: When a duplicate triple is detected (same op, same args), instead of creating a new triple, the statement array simply points to the existing one. Multiple statement entries can reference the same triple, naturally representing shared computations without additional mechanisms.

1. Q: Can indirect triples represent DAGs?

A: Yes, naturally. When multiple instructions reference the same triple (shared node), the structure forms a DAG. The triple pool contains unique computations, and the statement/reference structure captures sharing. This makes indirect triples well-suited for DAG-based basic block optimization.

1. Q: In modern compilers, are triples or indirect triples still used?

A: Rarely in their pure form. Modern compilers (LLVM, GCC) use SSA-based IRs that combine the benefits of explicit naming (like quadruples) with efficient def-use chains. However, the concepts from triples (positional references, sharing) influence internal data structures used in instruction selection and scheduling passes.