Quadruples Representation in Compiler Design

Definition

A quadruple is a record with four fields: (operator, arg1, arg2, result). It is the most straightforward implementation of three-address code, where each instruction is stored as a 4-tuple. The result field explicitly names the temporary or variable that receives the computation's output.

Structure

Complete Example

Advantages of Quadruples

Quadruples vs Triples

Quadruples for Control Flow

Quadruples for Function Calls

Implementation in Code

Interview Questions

1. Q: Why are quadruples preferred over triples in optimizing compilers?

A: Quadruples use explicit temporary names, so instructions can be freely reordered, deleted, or moved during optimization without updating references. Triples use positional references that break when instructions move. The extra storage for the result field is a small price for optimization flexibility.

1. Q: How does backpatching work with quadruples?

A: When generating code for boolean expressions or control flow, branch targets may not be known yet. The compiler emits the quadruple with an empty target field and records its index. When the target becomes known (label defined), it patches the target field. Lists of quadruples needing the same target are maintained for efficient patching.

1. Q: How many temporary variables does a quadruple representation typically need?

A: One temporary per intermediate computation. For expression a+b*c-d: three temporaries (t1=b*c, t2=a+t1, t3=t2-d). A basic block of n operations needs at most n temporaries, though reuse analysis can reduce this to the maximum number of simultaneously live temporaries.

1. Q: How are quadruples stored in memory during compilation?

A: Typically as an array of structures (fixed-size records), with the nextQuad pointer tracking the next available position. This allows random access for backpatching and sequential access for code generation. Some implementations use linked lists for easier insertion/deletion during optimization.

1. Q: Can quadruples represent modern language features like closures or exceptions?

A: Not directly with basic quadruples. Extensions are needed: closures require instructions for environment capture and function objects, exceptions need try/catch/throw pseudo-operations that map to runtime support code. The basic quadruple framework is extended rather than replaced for these features.