Code Optimization Mistakes in Compiler Design: How to Avoid Losing GATE Marks

Code-optimization questions often go wrong because a valid rewrite is applied after an operand changes, across the wrong control-flow boundary, or without checking an edge case. The governing principle is simple: an optimization is correct only when the transformed program preserves the original meaning for every relevant input and execution path. These six traceable mistakes, followed by a quick checking routine, will help you catch unsafe answers. Use the Compiler Design blog for connected Compiler Design notes and guides.

1. Reusing a common expression after an operand changes

Consider this three-address code, with entry values a = 4 and b = 7:

t1 = a + b
a = a + 1
t2 = a + b

The correct trace is:

1. t1 = 4 + 7 = 11

2. a = 4 + 1 = 5

3. t2 = 5 + 7 = 12

Replacing the last statement with t2 = t1 produces 11, not 12. The assignment to a kills every available expression containing a. Before reusing an expression, check that every operand has the same reaching definition and that nothing between the two computations can change its value. See the full worked code-optimization trace for the complete method.

2. Treating a copy as a permanent alias

Suppose entry value y = 4 and the code is:

x = y
y = 9
z = x + 1

After the first statement, write a small note: copy fact: x holds old y = 4. The states are x = 4, then y = 9, then z = 4 + 1 = 5. If you replace x by the current y, you get z = 9 + 1 = 10, which is wrong.

The safe rule is precise. Replace a use of x by y only while x = y reaches that use and no relevant kill changes the value represented by the copy. A copy records a value, not a permanent alias.

3. Applying algebraic identities without their preconditions

The rewrite q = x / x to q = 1 is not universally valid. It requires x to be non-zero and division to be safe. At x = 0, the original expression is not an ordinary value-producing division, so replacing it by 1 changes behaviour.

Reassociation can also fail in finite-precision floating-point arithmetic. Let a = 1e20, b = -1e20, and c = 3.14.

• (a + b) + c = 0 + 3.14 = 3.14

• In a + (b + c), the 3.14 can be lost while forming b + c, leaving approximately -1e20. The result then becomes 1e20 + (-1e20) = 0.

The checking rule is: state the numeric domain and precondition first, then apply the identity.

4. Deleting an assignment after checking only the next line

Consider this control flow:

x = 4
if p goto L1
x = 9
L1: print(x)

If p = true, the jump skips x = 9, so the program prints 4. If p = false, it executes x = 9 and prints 9. Removing x = 4 leaves the true path without the required value.

An assignment is dead only when its value is not live on any successor path. An apparently unused result such as t = f() cannot automatically be removed if f() may produce an observable effect or fault. Mark uses and successor edges before crossing out a definition.

5. Moving or reducing loop work one step out of phase

Trace this loop:

s = 0
for i = 0 to 4:
    t = i * 8
    s = s + t

The t sequence is 0, 8, 16, 24, 32, and s = 0 + 8 + 16 + 24 + 32 = 80. The correct reduced form initializes t = 0, adds the current t to s, and then executes t = t + 8. Starting at 8, or incrementing before use, produces 8, 16, 24, 32, 40, whose sum is 120.

With entry p = 2:

for i = 0 to 2:
    p = p + 1
    t = p * 5

The values of t are 15, 20, 25. The expression cannot be hoisted because p changes. Before moving code, confirm that every operand is unchanged in the loop, evaluation is safe even if the loop runs zero times, and the moved definition still reaches every intended use.

6. Building one local DAG across multiple basic blocks

Mark leaders and branches first:

B1: t1 = a + b
    c = t1 * 2
    if c > 20 goto L1
B2: a = a + 1
    t2 = a + b
B3 at L1: d = a + b

For Run A, a = 6, b = 5, so t1 = 11 and c = 22. The branch is true, B2 is skipped, and d = 11. For Run B, a = 4, b = 5, so t1 = 9 and c = 18. The false edge enters B2, where a becomes 5 and t2 = 10; B3 must therefore compute d = 10.

Replacing d = a + b with d = t1 works in Run A but gives 9 instead of 10 in Run B. Build one local DAG per block. Reuse across blocks requires available-expression facts and compatible reaching definitions on every predecessor path.

7. The 60-second check before accepting an optimization

Use this order:

1. Mark basic-block leaders and every successor path.

2. Write the reaching value or definition beside each operand.

3. Cross out facts killed by assignments.

4. Compare original and optimized code on every branch, plus edge cases such as zero and the first loop iteration.

5. Count operations only after proving semantic equality.

The incorrect strength-reduced loop uses fewer multiplications, yet it fails because it produces 120 instead of 80.

The short version

Preserve the same meaning first. Reduce operations second. To place this topic in the larger subject sequence, review where code optimization fits in Compiler Design preparation.

Use the Compiler Design course when you want the topic taught in a structured sequence. Use the GATE Test Series when you are ready to practise these checks under timed conditions.