Course Content

Other Courses

Tribhuvan university > CSIT - 2065 Syllabus > Compiler Design and Construction > Old Questions > 2069

Compiler Design and Construction - Old Questions

Syllabus Notes Old Questions Unit Wise Questions Question Bank

10.  How next-use information is useful in code-generation? Explain the steps involved on computing next-use information.

6 marks | Asked in 2069

Next-use information is needed for dead-code elimination and register allocation. Next-use is computed by a backward scan of a basic block. The next-use information will indicate the statement number at which a particular variable that is defined in the current position will be reused.

The following are the steps involved in generating next-use information: 

Input: Basic block B of three-address statements

Output: At each statement i: x= y op z, we attach to i the liveliness and next-uses of x, y and z.

Method: We start at the last statement of B and scan backwards.

    1. Attach to statement i the information currently found in the symbol table regarding the next-use and liveliness of x, y and z.

    2.   In the symbol table, set x to “not live” and “no next use”.

    3. In the symbol table, set y and z to "live", and next-uses of y and Z to i.

  

Example live and nextuse() computation

i: a := b + c

j: t := a + b

Statement number

Instruction

Liveness and nextuse initialized

Modified liveness and nextuse after statement ‘j’

Modified liveness and nextuse after statement ‘i’

Comments

i

a := b + c

live(a) = true, live(b) = true, live(t) = true, nextuse(a)=none,

nextuse(b)=none,

nextuse(t)=none

live(a) = true,    nextuse(a) = j,  live(b) = true,  nextuse(b) = j,  live(t) = false,  nextuse(t)=none

live(a) = false,    nextuse(a)=none,  live(b)=true,  nextuse(b) = i,  live(c) = true,  nextuse(c) = i,    live(t) = false,  nextuse(t)=none

‘a’ is said to false and no nextuse. ‘b’ and ‘c’ are said to live at statement ‘i’ and their next use is at ‘i’ . ‘t’’sliveness and nextuse remains as it is computed in statement ‘j’

j

t := a + b

live(a) = true, live(b) = true, live(t) = true, nextuse(a)=none,

nextuse(b)=none,

nextuse(t =none

live(a) = true,    nextuse(a) = j,  live(b) = true, nextuse(b) = j,  live(t) = false,  nextuse(t)=none

live(a) = true,    nextuse(a) = j,  live(b) = true,  nextuse(b) = j,  live(t) = false,  nextuse(t)=none

‘a’ and ‘b’ are used here and hence their nextuse is at ‘j’ and they are said to be live. ‘t’ is computed and hence nextuse is none and live information is false