Code Optimization | Compiler Design

Constant folding
Constant folding is the process of recognizing and evaluating constant expressions at compile time rather than computing them at runtime. Terms in constant expressions are typically simple literals, such as the integer literal 2, but they may also be variables whose values are known at compile time. Consider the statement:

i = 320 * 200 * 32;

Most compilers would not actually generate two multiply instructions and a store for this statement. Instead, they identify constructs such as these and substitute the computed values at compile time (in this case, 2,048,000).

Constant folding can make use of arithmetic identities. If x is numeric, the value of 0 * x is zero even if the compiler does not know the value of x (note that this is not valid for IEEE floats since x could be Infinity or NotANumber. Still, some languages that favor performance such as GLSL allow this for constants, which can occasionally cause bugs).

Constant folding may apply to more than just numbers. Concatenation of string literals and constant strings can be constant folded. Code such as "abc" + "def" may be replaced with "abcdef".

Simple Example:

In the code fragment The below expression (3 + 5) can be evaluated at compile time and replaced with the constant 8.

int f (void)
{
return 3 + 5;
}
Below is the code fragment after constant folding.
int f (void)
{
return 8;
}

Loop Optimization
Loop Optimization is the process of increasing execution speed and reducing the overheads associated with loops
Decreasing the number of instructions in an inner loop improves the running time of a program even if the amount of code outside that loop is increased.

Loop Optimization Techniques -

1. Frequency Reduction (Code Motion)
2. Loop Unrolling:
3. Loop Jamming

 

According to Aho Ullman book : 
PeepHole Optimization is done by examining a sliding window of target instructions(called the peephole) and replacing instruction sequences within the peephole by a faster sequence or shorter.
It can be applied directly after Intermediate Code Generation to improve the intermediate representation.
The code in the peephole need not be contiguous , although some implementations do require this.

So, options(A), option(B) and option(C) are true. Only option(D) is false.

Compilers translate the C language into machine code, which can be executed by the CPU. It's often easy to see which bytes of machine code correspond to which statements in your C code. Debuggers use this correspondence when showing how your C code runs.

So the meaning of "a declaration is not an executable statement" is that no machine code corresponds to a declaration. This also means that:

CPU doesn't spend any time to "run" the declaration (but the compiler does spend time to examine it) A visual debugger will "skip" the declaration when running your program step by step

Peephole optimization is a form of optimization that is done on a segment of generated code.
So, Peephole optimization is form of Local optimization

Constant folding

Constant folding is the process of recognizing and evaluating constant expressions at compile time rather than computing them at runtime. Terms in constant expressions are typically simple literals, such as the integer literal 2, but they may also be variables whose values are known at compile time. Consider the statement:

i = 320 * 200 * 32;

Most compilers would not actually generate two multiply instructions and a store for this statement. Instead, they identify constructs such as these and substitute the computed values at compile time (in this case, 2,048,000).

Constant folding can make use of arithmetic identities. If x is numeric, the value of 0 * x is zero even if the compiler does not know the value of x (note that this is not valid for IEEE floats since x could be Infinity or NotANumber. Still, some languages that favor performance such as GLSL allow this for constants, which can occasionally cause bugs).

Constant folding may apply to more than just numbers. Concatenation of string literals and constant strings can be constant folded. Code such as "abc" + "def" may be replaced with "abcdef".

Simple Example:

In the code fragment The below expression (3 + 5) can be evaluated at compile time and replaced with the constant 8.

int f (void)
{
return 3 + 5;
}
Below is the code fragment after constant folding.
int f (void)
{
return 8;
}

In compiler construction, strength reduction is a compiler optimization where expensive operations are replaced with equivalent but less expensive operations. The classic example of strength reduction converts "strong" multiplications inside a loop into "weaker" additions – something that frequently occurs in array addressing.

Other Examples of strength reduction include:

• Replacing a multiplication within a loop with an addition
• Replacing an exponentiation within a loop with a multiplication

Let take an Example:
Exponentiation is replaced by multiplication and multiplication is in return replaced by addition.
The below code is having multiplication operator:

a = 10;
for (j=0; j < X; j++)
{
 Z[j] = a * j;
}

This code can be replaced by the following code by replacing the multiplication with addition.

a = 10;
k = 0;
for (j=0; j < X; j++)
{
 Z[j] = k;
 k = k + a;
}

In peephole optimization a small portion of code need not be contiguous  and it is replaced by another which is expected to be better performing.
This is often applied repeatedly. So, all given options are true in this question.

Refer this link : http://www.cse.iitm.ac.in/~krishna/cs3300/pm-lecture3.pdf

Basic Blocks

Basic block is a set of statements that always executes in a sequence one after the other.

The characteristics of basic blocks are :

• They do not contain any kind of jump statements in them.
• There is no possibility of branching or getting halt in the middle.
• All the statements execute in the same order they appear.
• They do not lose lose the flow control of the program.

Flow Graphs

• A flow graph is a directed graph with flow control information added to the basic blocks.
• The basic blocks serve as nodes of the flow graph.
• There is a directed edge from block B1 to block B2 if B2 appears immediately after B1 in the code

Strength Reduction : Replace expensive operations with less expensive but equivalent operations.
For Example : Multiplication is more expensive operation than addition.
Shift operation is less expensive operation than Multiplication/Division.

In option (B), Multiplication operation is replaced with Shift Operator . It reduce the operator strength because shift operator is less expensive than multiplication operation.
Here, most suitable option is 2) Replace P × 32 by P ≪ 5

In loop jamming, the bodies of the two loops are merged together to form a single loop provided that they do not make any references to each other. It reduces the time taken to compile the many number of loops.

Example:

Initial Code:

for(int i=0; i<5; i++)
  a = i + 5;
for(int i=0; i<5; i++)
  b = i + 10;

Using Loop jamming above code converted into below Optimized code :

for(int i=0; i<5; i++)
{
  a = i + 5;
  b = i + 10;
}

Loop unrolling

• Loop unrolling is a loop transformation technique that helps to optimize the execution time of a program.
• Loop unrolling basically remove or reduce iterations.
• Loop unrolling increases the program’s speed by eliminating loop control instruction and loop test instructions.

Let us consider an example :
Program 1 without loop unrolling:

#include
int main(void)
{
 for (int i=0; i<5; i++)
  printf("Hello\n"); //print hello 5 times
 return 0;
}

Output :

1. Hello
2. Hello
3. Hello
4. Hello
5. Hello

This program uses loop unrolling.

#include
int main(void)
{
 // unrolled the for loop in program 1
 printf("Hello\n");
 printf("Hello\n");
 printf("Hello\n");
 printf("Hello\n");
 printf("Hello\n");
 return 0;
}

Output :

1. Hello
2. Hello
3. Hello
4. Hello
5. Hello

• Code optimization is responsibility of System Programmers
• Optimization can be performed by automatic optimizers, or programmers.
• An optimizer is either a specialized software tool or a built-in unit of a compiler (the so-called optimizing compiler).
• Modern processors can also optimize the execution order of code instructions.

Peephole optimization is a form of optimization that is done on a segment of generated code.
So, Peephole optimization is form of Local optimization
**Local optimization is correct answer**

• Dead code elimination is a compiler optimization to remove code which does not affect the program results.
• Removing such code has several benefits: it shrinks program size, an important consideration in some contexts, and it allows the running program to avoid executing irrelevant operations, which reduces its running time.
• It can also enable further optimizations by simplifying program structure. Dead code includes code that can never be executed (unreachable code), and code that only affects dead variables (written to, but never read again), that is, irrelevant to the program.

In compiler construction, strength reduction is a compiler optimization where expensive operations are replaced with equivalent but less expensive operations. The classic example of strength reduction converts "strong" multiplications inside a loop into "weaker" additions – something that frequently occurs in array addressing.

Other Examples of strength reduction include:

• Replacing a multiplication within a loop with an addition
• Replacing an exponentiation within a loop with a multiplication

Let take an Example:
Exponentiation is replaced by multiplication and multiplication is in return replaced by addition.
The below code is having multiplication operator:

a = 10;
for (j=0; j < X; j++)
{
 Z[j] = a * j;
}

This code can be replaced by the following code by replacing the multiplication with addition.

a = 10;
k = 0;
for (j=0; j < X; j++)
{
 Z[j] = k;
 k = k + a;
}