GATE CSE 2014 | Set 1 | Question: 17

Question

Which one of the following is FALSE?

• A. A basic block is a sequence of instructions where control enters the sequence at the beginning and exits at the end. 
• B. Available expression analysis can be used for common subexpression elimination.
• C. Live variable analysis can be used for dead code elimination.
• D. $x=4*5 \Rightarrow x=20$ is an example of common subexpression elimination.

Comments

Liveness analysis checks if a variable is still needed in the future, while available analysis checks if a result is already ready to use.

---

Constant Folding : whenever we have constants we can fold them to save time and space at runtime.

Example:-   $\text{x = }\textcolor{red}{2 * 3}\text{ + y;   ⇛   x = }\textcolor{red}{6}\text{ + y;    [ replace }\textcolor{red}{2 * 3}\text{ with }\textcolor{red}{6}\text{ ]}$

Constant Propagation:  process of replacing the constant value of variables in the expression.

Example:- $\text{ x = }\textcolor{red}{2}\text{;  y = }\textcolor{red}{x}\text{ * a; ⇛  y = }\textcolor{red}{2}\text{ * a;     [ replace }\textcolor{red}{x}\text{ with }\textcolor{red}{2}\text{ ]}$

---

is constant propagation in syllabus?

Answer 1

• A. A basic block is a sequence of instructions where control enters the sequence at the beginning and exits at the end, which is TRUE.
   
• B. Available expression analysis can be used for common subexpression elimination is TRUE. Available expressions is an analysis algorithm that determines for each point in the program the set of expressions that need not be recomputed. Available expression analysis is used to do global common subexpression elimination (CSE). If an expression is available at a point, there is no need to re-evaluate it.
   
• C. Live variable analysis can be used for dead code elimination is TRUE.
   
• D. $x = 4 ∗ 5 \Rightarrow x = 20$ is an example of common subexpression elimination is FALSE. Common subexpression elimination (CSE) refers to compiler optimization replaces identical expressions (i.e., they all evaluate to the same value) with a single variable holding the computed value when it is worthwhile to do so Source: Geeksforgeeks

Correct Answer: $D$

 

Comments

@madhes23 

“Liveliness Analysis consists of a specified technique that is implemented to optimize register space allocation, for a given piece of code and facilitate the procedure for dead-code elimination.”

Source:- Liveliness Analysis in Compiler Design - GeeksforGeeks

 

---

Adding info to @Shashwat21225 ‘s comment:-

Constant folding vs. Constant propagation

The difference is that constant propagation is not saving a variable to the stack, because we know its a constant (like x = 10;) and can simply plug it in everywhere (say if you had an expression y = x + x + x => y = 10 + 10 + 10) it is used in machine code. Whereas, constant folding is simply evaluating expressions that use constants and substituting the result into the machine code (like y = 10 + 10 + 10; => y = 30;)

---

• Constant folding can be seen as a prerequisite or a component of constant propagation.
• Constant propagation can use the results of constant folding to perform its substitution.

Answer 2

Right option is D