Compilers

Which describes applying common subexpression elimination to the code above?

x = (a + b) * c;
y = (a + b) * d;
  1. ACompute a + b once into a temporary and reuse it in both expressions
  2. BSince x and y are similar, delete the computation of one of them
  3. CReplace the multiplications with additions to make the computation cheaper
Show answer and explanation

Answer: A. Compute a + b once into a temporary and reuse it in both expressions

Common subexpression elimination computes a repeatedly evaluated expression once and reuses the result. Here, computing t = a + b and then x = t * c and y = t * d saves one addition. It must be confirmed that a and b are not modified between the two expressions. x and y are different values, so neither can be deleted. Replacing multiplication with cheaper operations is a different optimization, strength reduction.

  • A. Correct. The shared expression is computed once and reused.
  • B. x and y have different values, so both are needed.
  • C. Making expensive operations cheaper is strength reduction.
Practice this topic Back to topic

More Compilers questions

  1. What does dead-code elimination remove?
  2. Which pair gives the advantage and drawback of function inlining?
  3. What is the main effect of loop unrolling?
  4. In the loop above, which computation is a candidate for loop-invariant code motion (hoisting out of the loop)? (Assume x and y are not modified in the loop.)
  5. In the loop above, which transformation applies strength reduction to the index computation i * 4?