Program FindCopiesDriver

Input. a C program, P
Output. a datafile 
 generate CFG(P) with PAF:an analysis framework
 perform FindCopies on CFG
 write C_R: a collection of copies and associated
 references

end Program FindCopiesDriver


algorithm FindCopies

Input.  CFG :  A control flow graph

Output. C : A collection of Copies : 
            node_number : CFG node number of copy
            rhs_var : variable on right-hand side of copy
            ref_list : list of Refs : 
               node_number : CFG node of reference
               ref_type : type of reference (definition, use,
                      undefinition)

Declare.Gen[N], Kill[N] : gen and kill sets for Copies
        In{N], Out[N] : sets of Copies
        Def(N), Use(N) : returns variable defined, used at N
        Change : boolean used to control iteration
        Oldout : temporary, set of Copies

Method.
begin FindCopies

   /* Compute Gen[N] for each node N in CFG */ 
   foreach node N in CFG do
      if N contains a simple copy then
         Create record R for N 
         Add R to C
      endif
   endfor

   /* Compute Kill[N] for each node N in CCFG */
   foreach node N in CFG do
      foreach R in C do
         if Def(N) = R.rhs_var or Use(N) = R.rhs_var or
	 if Def(alias of N) = R.rhs_var or Use(alias of N) = r.rhs_var then
            Add R to Kill[N}  
         endif
      endfor
   endfor

   /* Initialize Out sets */
   foreach node N in CFG in order do
      Out[N] := Gen[N]
   endfor

   /* Now propagate copies */
   Change = true
   while Change do
      Change = false
      foreach node N in CFG do
         In[N] := union Out[P], where P is an immediate predecessor of N
         OldOut := Out[N}
         Out[N] := Gen[N] union (In[N] - Kill[N])
         if Out[N] not equal OldOut then
            Change := true
         endif
      endfor
   endwhile

   /* Now create ref_lists for each copy */
   foreach node N in CFG do
      foreach R in IN[N] do /* each R is a copy that reaches N */
         v := R.rhs_var
         if Def(N)= v or Use(N) = v or N is "exit node" then
            Create record Ref for N
            Add Ref to R.ref_list
         endif
      endfor
   endfor

end FindCopies