next up previous
Next: About this document ... Up: Final-2003 Previous: Exercise 9.

Exercise 10.

Consider the following three-address code program.
L0 n := 10
  s := 0
  i := 0
L1 if i > n goto L6
  j := i
  m := n
  p := m
  f := 1
L2 if p = 1 goto L3
  f := f * p
  p := p - 1
  goto L2
L3 a := f
  p := m - j
  f := 1
L4 if p = 1 goto L5
  f := f * p
  p := p - 1
  goto L4
L5 b := f
  c := a quo b
  s := s + c
  i := i - 1
  goto L1
L6
  1. Give the flow graph of this program.
  2. Identify the back edges and the loops.
  3. For each basic block B compute the data-flow sets gen(B) and kill (B) of the generated and killed variable definitions.
  4. Deduce from this study a significant optimization for the above code.

Answer 10  
\fbox{
\begin{minipage}{12 cm}
\mbox{ } \\
\mbox{ } \\
\mbox{ } \\
\mbox{ } \...
...\mbox{ } \\
\mbox{ } \\
\mbox{ } \\
\mbox{ } \\
\mbox{ } \\
\end{minipage}}


\fbox{
\begin{minipage}{12 cm}
\mbox{ } \\
\mbox{ } \\
\mbox{ } \\
\mbox{ } \...
...\mbox{ } \\
\mbox{ } \\
\mbox{ } \\
\mbox{ } \\
\mbox{ } \\
\end{minipage}}


next up previous
Next: About this document ... Up: Final-2003 Previous: Exercise 9.
Marc Moreno Maza
2004-12-02