# GATE2014-1-17

26 votes
5k views

Which one of the following is FALSE?

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

retagged
1

Constant propagation is the process of substituting the values of known constants in expressions at compile time.
(D) is an example of constant propagation, note that it's not constant folding.

1
I think this topic comes under Optimization and its not in syllabus right from GATE 2015?

## 2 Answers

27 votes

Best answer
1. A basic block is a sequence of instructions where control enters the sequence at the beginning and exits at the end is TRUE.

2. 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.

3. Live variable analysis can be used for dead code elimination is TRUE.

4. $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$

edited
21
Option D is called constant folding

https://en.wikipedia.org/wiki/Constant_folding
0
@ryan it's not constant folding, but it is constant propagation.
6
it is constant folding
0
What is difference between constant propagation and constant foldingg
13

Constant propagation refers to the act of replacing a bound variable with the constant it is bound to. Ex- x=10; y=x+x+x; that means x is bound to 10, then constant propagation will result into y=10+10+10;

Constant folding is simply evaluation of expression where all inputs are compile time constant. Ex- y=10+10+10; results into y=30;

I hope it helps.

0 votes
answer - D
Answer:

## Related questions

32 votes
5 answers
1
8.6k views
A canonical set of items is given below $S \to L .> R$ $Q \to R.$ On input symbol $<$ the set has a shift-reduce conflict and a reduce-reduce conflict. a shift-reduce conflict but not a reduce-reduce conflict. a reduce-reduce conflict but not a shift-reduce conflict. neither a shift-reduce nor a reduce-reduce conflict.
51 votes
5 answers
2
16.1k views
Consider the basic block given below. a = b + c c = a + d d = b + c e = d - b a = e + b The minimum number of nodes and edges present in the DAG representation of the above basic block respectively are $6$ and $6$ $8$ and $10$ $9$ and $12$ $4$ and $4$
44 votes
7 answers
3
8.9k views
The minimum number of arithmetic operations required to evaluate the polynomial $P(X) = X^5+4X^3+6X+5$ for a given value of $X$, using only one temporary variable is ______.
15 votes
3 answers
4
3.4k views
The following code segment is executed on a processor which allows only register operands in its instructions. Each instruction can have atmost two source operands and one destination operand. Assume that all variables are dead after this code segment. c = a + b; d ... this code segment without any spill to memory? Do not apply any optimization other than optimizing register allocation. 3 4 5 6