CD Notes
Guide to triples as a compact intermediate code representation covering structure, position-based referencing, comparison with quadruples, and optimization challenges.
Definition
Triples are a compact representation of three-address code that eliminates the explicit result field by using the position (index) of the instruction as an implicit reference to its result. Each triple is a 3-tuple: (operator, arg1, arg2), and other instructions refer to its result using the triple's index number.
Structure
| op | arg1 | arg2 | result | # | op | arg1 | arg2 | |
|---|---|---|---|---|---|---|---|---|
| + | a | b | t1 | 0 | + | a | b | |
| - | c | d | t2 | 1 | - | c | d | |
| * | t1 | t2 | t3 | 2 | * | (0) | (1) | |
| = | t3 | x | 3 | = | x | (2) |
Detailed Example
| # | op | arg1 | arg2 |
|---|---|---|---|
| 0 | * | b | c |
| 1 | + | (0) | d |
| 2 | = | a | (1) |
| 4 | = | e | (3) |
Types of Instructions in Triple Form
| Binary | (op, arg1, arg2) e.g., (+, a, b) |
| Unary | (op, arg1, _) e.g., (uminus, a, _) |
| Copy | (=, x, (n)) e.g., (=, x, (2)) |
| Goto | (goto, _, L) e.g., (goto, _, 8) |
| Conditional | (if<, a, b) followed by goto |
| Param | (param, _, x) e.g., (param, _, a) |
| Call | (call, f, n) e.g., (call, max, 2) |
| Return | (return, _, x) e.g., (return, _, a) |
| Index | ([]=, a, i) meaning: a[i] |
Advantages and Disadvantages
Advantages
+ More compact than quadruples (no result field)
+ No temporary variable names needed
+ Natural representation for expression DAGs
+ Saves memory for large programs
Disadvantages
- Difficult to rearrange instructions (position-dependent!)
- Optimization that moves/deletes triples requires updating ALL references
- Not suitable for optimization-heavy compilers
Problem example - deleting triple 1
Before: After deleting triple 1:
0: (*, b, c) 0: (*, b, c)
1: (+, a, (0)) 1: (-, d, (0)) ← was triple 2, now at 1
2: (-, d, (0)) 2: (/, (0), (1)) ← references must change!
3: (/, (0), (2)) ALL (2) refs become (1), (3) refs become (2)...
Ternary Operations
| 0 | > | a | b |
|---|---|---|---|
| 2 | = | result | c |
| 3 | goto | 5 | |
| 4 | = | result | d |
| 5 | ... |
Comparison: Quadruples, Triples, Indirect Triples
| * | c | d | t1 | 0 | * | c | d | |
|---|---|---|---|---|---|---|---|---|
| + | b | t1 | t2 | 1 | + | b | (0) | |
| = | t2 | a | 2 | = | a | (1) |
Interview Questions
- Q: Why do triples use position numbers instead of temporary names?
A: To save space. Temporary names in quadruples consume memory for storage and lookup. Triples implicitly number results by position, eliminating temp name allocation and reducing the record size from 4 to 3 fields. For large programs, this memory savings is significant.
- Q: What makes triples difficult to optimize?
A: Optimization often involves reordering, inserting, or deleting instructions. In triples, all result references are positional — moving triple #5 to position #3 means every instruction referencing (5) must be updated to (3). This makes code motion and instruction scheduling cumbersome.
- Q: When would you choose triples over quadruples?
A: When memory is constrained and the code will not be heavily optimized (e.g., quick compilation for debugging). Also when the IR is consumed sequentially without rearrangement. Interpreters that evaluate triples in order work well since positions are stable during interpretation.
- Q: How does CSE work with triples?
A: Detect identical triples (same op, same args pointing to same sources). When found, later triples referencing the duplicate can reference the original instead. The duplicate triple becomes dead and can be eliminated — though this shifts positions and requires careful reference updating.
- Q: What is the relationship between triples and expression trees?
A: Each triple corresponds to an internal node in the expression tree. The position references (0), (1), etc. correspond to edges in the tree. A triple list is essentially a linearized (topologically sorted) expression tree, with shared references creating a DAG.
Exam Focus
Revise definitions, diagrams, examples, and short-answer points for Triples Representation in Compiler Design.
Interview Use
Prepare one clear explanation, one practical example, and one common mistake for this Compiler Design topic.
Search Terms
compiler-design, compiler design, compiler, design, intermediate, code, generation, triples
Related Compiler Design Topics