Doubt in Compilers

Question

Which of the following optimization techniques are typically applied on loops?
(a) Removal of invariant computation (b) Elimination of induction variables
(c) Peephole optimization (d) Constant folding

Answer 1

A.

"In computer programming, loop-invariant code consists of statements or expressions (in an imperative programming language) which can be moved outside the body of a loop without affecting the semantics of the program. Loop-invariant code motion (also called hoisting or scalar promotion) is a compiler optimization which performs this movement automatically."

Source: Wikipedia

Answer 2

option A and B both are correct.

A. loop invariant computation is one that computes the same value every time a loop is executed.so,moving such a computation outside the loop leads to a reduction in the execution time.

B.Induction variables are those variables used in a loop; their values are in lock-step, and hence, it may be possible to eliminate all except one.

for Ex:

Before Elimination of induction variables

int Y[SIZE];
int Z[SIZE];
void fun (void)
{
  int x1, x2, x3;

  for (x1 = 0, x2 = 0, x3 = 0; x1 < SIZE; x1++)
    Y[x2++] = Z[x3++];
  return;
}

After Elimination of induction variables

int Y[SIZE];
int Z[SIZE];
void fun (void)
{
  int x1;

  for (x1 = 0; x1 < SIZE; x1++)
    Y[x1++] = Z[x1++];
  return;
}