Lab 2, Optimizing Compilers, EDAN75

You should try to implement as much of Lab 2 as possible before going to the lab. It is difficult to implement it all during the lab session.

1. Hints!
   • Use join_set to add something to a set.
   • To walk through a set (eg the dominance frontier of w, w->df), do as follows:

     	vertex_t**	a;
     	int	n;
     
     	...
     
     	a = set_to_array(w->df, &n);
     
     	for (i = 0; i < n; i++) {
     		use a[i] here
     	}
     
     	free(a);
     

   
   
   
2. What is the definition of dominance frontier?
   
   
3. Implement the function df in the file ssa.c, i.e. Algorithm 2.10 on page 97.
   
   
4. Implement the function rename_symbols in the file ssa.c, i.e. the procedure search in Algorithm 4.5 on page 134. Useful functions:
   • is_sym(op_t op) - op.c
   • is_label(op_t op) - op.c
   • temp() - op.c
   • defined_sym(stmt_t* stmt) - stmt.c
   
   
5. Implement the technique to do copy propagation during renaming, i.e., for an assignment:
   
   a = b;
   
   push the current value of b on the stack of a.
   
   Do not implement Algorithm 5.1 in Lab 2!
   
   Compare the values of C (clock cycles) printed by vcc with and without SSA form, and with and without copy propagation.
   
   

Requirements for the Lab