3.3 The iterative worklist algorithm

The simple work-list algorithm allows to perform data-flow analyses, very simply, even its performance is not very high. Informally, it can be described as follows:

// initialization
for every n: in(n) = INIT
for every n: insert(n, worklist) 

// main cycle
while not empty(worklist) do
     x = extract(worklist)
     old = in(x)
     if FORWARD
          new = MEET(all p in fathers(n)) (TRASF(in(p))) 
          if old <> new 
               for every f in children(n): insert(f, worklist); 
               in(n) = new
     else 
          new = MEET(all p in children(n)) (TRASF(in(p))) 
          if old <> new 
               for every f in fathers(n): insert(f, worklist); 
               in(n) = new   
enddo

The algorithm is very general. Every analysis has just to define the carrier data type, INIT, TRASF and MEET fucntions, choose the direction (FORWARD or BACKWARD). Ocaml implementation follows closely this scheme.