The Gateway to Computer Science Excellence

+107 votes

Best answer

Answer is $8$.

In compiler design, **static single assignment form** (often abbreviated as **SSA form** or simply **SSA**) is a property of an intermediate representation (IR), which requires that each variable is assigned exactly once, and every variable is defined before it is used. Existing variables in the original IR are split into *versions*, new variables.

We will need a temporary variable for storing the result of each binary operation as SSA (Static Single Assignment) implies the variable cannot be repeated on LHS of assignment.

$q + r / 3 + s - t * 5 + u * v/w $

$t1 = r/3;$

$t2 = t*5;$

$t3 = u*v;$

$t4 = t3/w;$

$t5 = q + t1;$

$t6 = t5 + s;$

$t7 = t6 - t2;$

$t8 = t7 + t4$

http://web.stanford.edu/class/archive/cs/cs143/cs143.1128/handouts/240%20TAC%20Examples.pdf

+8

They are "variables" which are defined (hence no longer temporary). In the 2016 question they asked explicitly for "total variables".

+5

in 2016 if they had asked for temporary variables then answer is 5?? All the variables which will be mentioned in expression will be taken as defined??

0

All the variables mentioned in the expression will be taken as defined and defined means they all are assigned memory and treated as variables. Right??

+1

@Arjun , @sushmita , In normal 3 address code representation, we could reuse the temporaries at the LHS right (or LHS can be repeated)?

0

@arjun Sir why the temporary variables will be 5. If we do like this then they will be 3.

x=u-t

y=x*v

t1=y+w

t2=t-z

t3=t1*t2

x=u-t

y=x*v

t1=y+w

t2=t-z

t3=t1*t2

+4

@arjun sir, This was gate 2016 question.

Consider the following code segment.

x = u - t; y = x * v; x = y + w; y = t - z; y = x * y;

The minimum number of total variables required to convert the above code segment to static single assignment form is ___.

I want to ask the number of minimum temporary variables required to do so.

+14

temp1 = u - t; temp2 = temp1 * v; temp3 = temp2 + w; temp4 = t - z; temp5 = temp3 * temp4;

5 are needed. Use temporary variable just to store the result not for variables and just see dependancy.

Since it is single static assignment , so use different temporary variable every time when u find new result.

+1

@arjun sir @prashant. Why have you used temp1 and temp2? We can use a variable on LHS atmost once in SSA. Why can't we use x and y on LHS to store the results?

x = u - t; y = x * v; temp1 = y + w; temp2 = t - z; temp3 = temp1 * temp2;

Why is it necessary to store the result in a temporary variable when we have a permanent variable for it?

+12

one resoning is how u know x is used in next instruction when you executing first instruction. like variable t is always used as input not as output.

so we used a temporary variable just for those variables who are updated.

Second point :

x = u - t; y = x * v;

if at all 2nd instruction executing 1st before x is actualy updated then 2nd instruction will take old value of x not new. so compiler remove these conflicts by using temporary variables.

0

Won't the DMAS Rule be applicable in

t3 = u*v;

t4 = t3/w?

I mean Division should be performed before Multiplication?

t3 = u*v;

t4 = t3/w?

I mean Division should be performed before Multiplication?

+8 votes

The given expression is

q + r / 3 + s - t * 5 + u * v/w

To store result of each binary operation , we need a temporary variable. Three Address Code (TAC) and Static Single Assignment form (SSA) implies the variable cannot be repeated.

So,

t1 = r/3;

t2 = t*5;

t3 = u*v;

t4 = t3/w;

t5 = q + t1;

t6 = t5 + s;

t7 = t5 - t2;

t8 = t7 + t4

There should be at least 8 temporary variables required to create TAC.

+3 votes

Temporary variable 8

Total variable= 8+7=15

* / Have same precedence and left associative same as +,- and left associative

–3 votes

–2

http://nptel.ac.in/courses/Webcourse-contents/IIT-KANPUR/compiler-desing/ui/Course_home-9.htm..

Check this out...u will find solution

Check this out...u will find solution

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.4k
- Admissions 595
- Exam Queries 573
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,737 questions

57,258 answers

198,087 comments

104,735 users