# Code Optimization | Compiler Design

 Question 1
The identification of common sub-expression and replacement of run time computations by compile-time computations is:
 A Local optimization B Constant folding C Loop Optimization D Data flow analysis
Question 1 Explanation:
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

There is 1 question to complete.
 Question 1
Which of the following comment about peephole optimization is true?
 A It is applied to a small part of the code and applied repeatedly B It can be used to optimize intermediate code C It can be applied to a portion of the code that is not contiguous D It is applied in the symbol table to optimize the memory requirements.
Question 1 Explanation:
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.
 Question 2
Which of the following class of statement usually produces no executable code when compiled?
 A Declaration B Assignment statements C Input and output statements D Structural statements
Question 2 Explanation:
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
 Question 3
Peephole optimization is a form of
 A Loop optimization B Local optimization C Constant folding D Data flow analysis
Question 3 Explanation:
Peephole optimization is a form of optimization that is done on a segment of generated code.
So, Peephole optimization is form of Local optimization
 Question 4
Substitution of values for names (whose values are constants) is done in
 A Local optimization B Loop optimization C Constant folding D Strength reduction
Question 4 Explanation:
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;`
`}`
 Question 5
In compiler terminology reduction in strength means
 A Replacing run time computation by compile time computation B Removing loop invariant computation C Removing common subexpressions D Replacing a costly operation by a relatively cheaper one
Question 5 Explanation:
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;
}```
 Question 6
Which of the following statements about peephole optimization is False?
 A It is applied to a small part of the code B It can be used to optimize intermediate code C To get the best out of this, it has to be applied repeatedly D It can be applied to the portion of the code that is not contiguous
Question 6 Explanation:
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
 Question 7
The graph that shows basic blocks and their successor relationship is called:
 A DAG B Control graph C Flow graph D Hamiltonian graph
Question 7 Explanation:
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
 Question 8
In compiler optimization, operator strength reduction uses mathematical identities to replace slow math operations with faster operations. Which of the following code replacements is an illustration of operator strength reduction ?
 A Replace P + P by 2 * P or Replace 3 + 4 by 7. B Replace P * 32 by P << 5 C Replace P * 0 by 0 D Replace (P << 4) – P by P * 15
Question 8 Explanation:
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
 Question 9
In _______, 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.
 A Loop unrolling B Strength reduction C Loop concatenation D Loop jamming
Question 9 Explanation:
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;
}```
 Question 10
Loop unrolling is a code optimization technique:
 A That avoids tests at every iteration of the loop. B That improves performance by decreasing the number of instructions in a basic block. C That exchanges inner loops with outer loops D That reorders operations to allow multiple computations to happen in parallel
Question 10 Explanation:
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
 Question 11
Code optimization is responsibility of :
 A Application programmer B System programmer C Operating system D All of the above
Question 11 Explanation:
• 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.
 Question 12
Peer-hole optimization is a form of :
 A Loop optimization B Local optimization C Constant folding D Data flow analysis
Question 12 Explanation:
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**
 Question 13
Dead-code elimination in machine code optimization refers to :
 A Removal of all labels. B Removal of values that never get used. C Removal of function which are not involved. D Removal of a module after its use.
Question 13 Explanation:
• 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.
 Question 14
In the context of compiler design, “reduction in strength” refers to :
 A Code optimization obtained by the use of cheaper machine instructions B Reduction in accuracy of the output C Reduction in the range of values of input variables D Reduction in efficiency of the program
Question 14 Explanation:
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;
}```
There are 14 questions to complete.