Compiler Design (AD-604 (C)) - Unit 5 Short Notes

How unit 5 is examined

This unit covers the sources of optimization (function-preserving transformations, basic blocks and loops), the code-improving transformations (common subexpressions, dead code, loop optimization, strength reduction, constant folding) with global data flow analysis, and debugging of optimized code; the transformations topic carries almost all the marks.

Introduction to code optimization: sources of optimization of basic blocks, loops in flow graphs

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Low weight</span>

Definition. <mark>Code optimization is the compiler phase that transforms intermediate code into equivalent code that runs faster or uses less memory, without changing the meaning of the program.</mark>

Key points.

1. An optimization must be correct (the optimized program gives the same output for every input), must give a real improvement in time or space, and must be worth the compile-time effort spent on it.
2. Function-preserving transformations improve the code without altering what it computes: common subexpression elimination, copy propagation, dead code elimination and constant folding.
3. Common subexpression elimination reuses a value already computed, so t1 = 4*i followed later by t2 = 4*i becomes t2 = t1; copy propagation replaces x by y after x = y; constant folding turns x = 3*4 into x = 12 at compile time.
4. Machine-independent optimization works on intermediate code (redundancy, loops), whereas machine-dependent optimization uses target features such as registers and cheaper instructions (peephole, register allocation).
5. Optimization is applied locally inside a basic block (straight-line code with one entry and one exit) and globally over the flow graph, whose loops (a header node with a back edge) are the most profitable place because programs spend most of their time there.

Asked: [8 marks] (May 2024) Define code optimization. Explain function preserving code optimization.

Dead code elimination, loop optimization, global data flow analysis, code improving transformations

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">High weight</span>

Definition. <mark>Code-improving transformations are semantics-preserving changes to the program, applied to intermediate code, that reduce its running time or its size.</mark>

Key points.

1. Common subexpression elimination computes an expression once and reuses it: a = b+c; d = b+c becomes a = b+c; d = a, valid only while b and c are not reassigned in between.
2. Copy propagation replaces x by y after the copy x = y, which often leaves the copy statement dead so that it can be removed.
3. Dead code elimination deletes statements whose result is never used or that can never be executed (for example code after a return, or if (0) branches).
4. Constant folding evaluates constant expressions at compile time, so x = 2*3.14 becomes x = 6.28 and the multiplication costs nothing at run time.
5. Loop optimization moves or simplifies work inside loops, since inner loops run many times; it has three techniques: code motion, strength reduction and induction variable elimination.
6. Code motion (loop-invariant computation) moves an expression whose value does not change in the loop to before the loop: while (i < n-2) becomes t = n-2; while (i < t).
7. Strength reduction replaces an expensive operation by a cheaper one: x = 2*i becomes x = i+i, and inside a loop t = 4*j becomes t = t+4.
8. Induction variable elimination removes variables that change in step with another one (j = 4*i while i grows by 1), keeping just one of them.
9. Global data flow analysis collects facts over the whole flow graph (reaching definitions, live variables, available expressions) and tells the compiler when the above transformations are safe.

Diagram. <figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u5-01" viewBox="0 0 467 80" width="467" height="80" role="img" aria-label="Flow graph of a loop: B1 pre-header, B2 header, B3 body (back edge B3 to B2), B4 exit"><style>#dsfig-u5-01 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u5-01 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u5-01 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u5-01 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u5-01 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u5-01 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u5-01 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u5-01 .t{fill:#16181D;font-weight:500}#dsfig-u5-01 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u5-01 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u5-01 .dot{fill:#16181D}#dsfig-u5-01 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u5-01 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u5-01 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u5-01 .ah{fill:#454C5A}#dsfig-u5-01 .ah.hi{fill:#2340B8}#dsfig-u5-01 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u5-01 .wl .t{font-size:12px;font-weight:700}#dsfig-u5-01 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u5-01 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u5-01 .e{stroke:#B1B7C3}html.dark #dsfig-u5-01 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u5-01 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u5-01 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u5-01 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u5-01 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u5-01 .t{fill:#E6E8ED}html.dark #dsfig-u5-01 .t.inv{fill:#0F1115}html.dark #dsfig-u5-01 .kd{stroke:#E6E8ED}html.dark #dsfig-u5-01 .dot{fill:#E6E8ED}html.dark #dsfig-u5-01 .ann{fill:#8FA3FF}html.dark #dsfig-u5-01 .lbl{fill:#858D9C}html.dark #dsfig-u5-01 .ptr{fill:#8FA3FF}html.dark #dsfig-u5-01 .ah{fill:#B1B7C3}html.dark #dsfig-u5-01 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u5-01 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u5-01 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u5-01 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah8" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah" d="M0,1 L9,5 L0,9 z"/></marker><marker id="ahh8" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah hi" d="M0,1 L9,5 L0,9 z"/></marker></defs><path class="e" d="M59,40 L148,40" marker-end="url(#ah8)"/><path class="e" d="M186,48.4 Q233.5,72 279.2,49.3" marker-end="url(#ah8)"/><path class="e" d="M281,31.6 Q233.5,8 187.8,30.7" marker-end="url(#ah8)"/><path class="e" d="M188,40 L406,40" marker-end="url(#ah8)"/><g class="wl"><rect x="213.5" y="10.6" width="40.8" height="18" rx="9"/><text class="t" x="233.9" y="19.6" dy=".35em" text-anchor="middle">back</text></g><circle class="n" cx="40" cy="40" r="18"/><text class="t" x="40" y="40" dy=".35em" text-anchor="middle">B1</text><circle class="n" cx="169" cy="40" r="18"/><text class="t" x="169" y="40" dy=".35em" text-anchor="middle">B2</text><circle class="n" cx="298" cy="40" r="18"/><text class="t" x="298" y="40" dy=".35em" text-anchor="middle">B3</text><circle class="n" cx="427" cy="40" r="18"/><text class="t" x="427" y="40" dy=".35em" text-anchor="middle">B4</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">Flow graph of a loop: B1 pre-header, B2 header, B3 body (back edge B3 to B2), B4 exit</figcaption></figure>

Example.

Symbol table. A symbol table is a data structure holding, for each identifier, its name, type, scope, size and address. Its operations are insert, lookup, delete, and enter or exit a scope; it is usually implemented as a hash table for fast lookup.

Type checking. Type checking verifies that each operation is applied to operands of permitted types, using type expressions such as int, array(10, int) and int -> int. A mismatch such as adding an int to a string is reported as a type error.

Constant folding. Constant folding evaluates an expression made only of constants during compilation, e.g. area = 22/7 * 5 * 5 is replaced by one constant, so no run-time computation is needed.

Answer frame. For the 6-mark question, open with the definition; write each transformation with a one-line before and after example in the order common subexpression, copy propagation, dead code, constant folding, loop optimization, strength reduction; close by saying they reduce time and space without changing meaning. For the 14-mark note, give four short parts a) to d) of 3-4 sentences each, using the Symbol table, Type checking and Constant folding paragraphs, and points 5-8 with the loop diagram for c).

Pitfall: Do not confuse code motion (moves invariant code out of the loop) with strength reduction (replaces an operation by a cheaper one); write the example for each.

Asked: [6 marks] (May 2024) Explain different code improving transformation. Asked: [14 marks] (May 2024) Write a short note on: a) Symbol table b) Type checking c) Loop optimization d) Constant folding

Data flow analysis of structure flow graph, symbolic debugging of optimized code

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Not asked since 2022</span>

Definition. ==Data flow analysis computes, at each point of the flow graph, how data values flow, using the equation $out[B] = gen[B] \cup (in[B] - kill[B])$.==

Key points.

1. For a structured (reducible) flow graph the equations are solved over its regions, such as if and while, in a small number of passes.
2. Typical problems are reaching definitions, live variables and available expressions.
3. Symbolic debugging of optimized code is hard because optimization reorders, removes or merges statements, so source variables and lines no longer match the running code.
4. The compiler therefore records where each variable's value lives so that the debugger reports values in terms of the source program.

Last-minute revision

• Code optimization gives equivalent code that is faster or smaller, with the meaning unchanged.
• Function-preserving transformations: common subexpression elimination, copy propagation, dead code elimination, constant folding.
• Machine-independent optimization works on intermediate code; machine-dependent on target code.
• A basic block has one entry and one exit; a loop has a header and a back edge.
• Loop optimizations: code motion, strength reduction, induction variable elimination.
• Constant folding happens at compile time: 2*3.14 becomes 6.28.
• Dead code: result never used, or code unreachable.
• Strength reduction: 2*i becomes i+i, 4*j becomes t = t+4.
• Data flow equation: $out = gen \cup (in - kill)$.
• Global analyses: reaching definitions, live variables, available expressions.
• Symbol table operations: insert, lookup, delete, scope enter and exit.
• Type checking uses type expressions like array(10, int) and int -> int.

Memory hooks

• Loop trio "MRE": Move (code motion), Reduce (strength), Eliminate (induction variable).
• Function-preserving four "C-C-D-F": CSE, Copy, Dead, Fold.
• Fold at compile time, compute at run time.
• Data flow: "gen adds, kill removes".

Coverage checklist

• Introduction to Code optimization: sources of optimization of basic blocks, loops in flow graphs: 8-mark definition of code optimization and function-preserving optimization (May 2024).
• dead code elimination, loop optimization, Introduction to global data flow analysis, Code Improving transformations: 6-mark code improving transformations and 14-mark short note on symbol table, type checking, loop optimization, constant folding (May 2024).
• Data flow analysis of structure flow graph Symbolic debugging of optimized code: not asked recently, covered by the definition and key points.