next up previous contents
Next: 3.4 Analyses implemented Up: 3. Data-flow analysis Previous: 3.2 Building the control-flow

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
          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   

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.