Universität Paderborn - Home Universität Paderborn
Die Universität der Informationsgesellschaft

Compilation Methods SS 2013 - Assignment 2

Kastens, Pfahler, 02.05.2013

Exercise 1 (Control-Flow Graph)

   0:   iconst_1
   1:   istore_1
   2:   iconst_1
   3:   istore_2
   4:   iload_2
   5:   bipush  32
   7:   if_icmpge 28
   10:  iload_1
   11:  sipush  10000              
   14:  if_icmpge 21
   17:  iconst_2
   18:  iload_1
   19:  imul
   20:  istore_1
   21:  iload_2
   22:  iconst_1
   23:  iadd
   24:  istore_2
   25:  goto    4
   28:  return
a)
Construct a graphical representation of the control flow graph.
b)
Compute the dominator relation and draw the idom tree.
c)
Find the back edge and compute its natural loop.
d)
HOMEWORK:
Reconstruct the Java source code. Embed it into the following class structure:
   class WhatEver { 
       public static void main(String[] args) {


       }
   }
Compile the Java source, extract the byte code using (javap -c ), and compare it to the byte code given above.

Exercise 2 ( Control-Flow Graph)

a)
Write a Java method that matches the following control-flow graph

b)
Compute the dominator relation and draw the idom tree.
c)
Compute the natural loop for each back edge.

Exercise 3 ( Dominator Relation, Loop Recognition)

a)
Determine the dominator relation.
b)
Determine all back edges.
c)
Determine all natural loops.

Exercise 4 (Loop invariant computations, induction variables)

  i = 1;
  do j = i + 1;
     do a[i, j] = 10 * n - 3 * i + j;
        j = j + 1;
     while (j < n);
     i = i + 1;
  while (i < n)
a)
Draw the control-flow graph.
b)
Determine all back edges and their natural loops
c)
Move all loop invariant computations to pre-headers. Do you need to insert new blocks to act as pre-headers?
d)
Determine all induction variables. Simplify computations using induction variables.

Exercise 5 ( Loop invariant computations, induction variables)

  i = 1;
  while (i < n) {
    a[i] = i * 3.14 / (n * 100);
    i = i + 1;
  }
a)
Draw the control-flow graph.
b)
Determine all back edges and their natural loops
c)
Move all loop invariant computations to pre-headers. Do you need to insert new blocks to act as pre-headers?
d)
Simplify computations using induction variables.

Generiert mit Camelot | Probleme mit Camelot? | Geändert am: 13.06.2017