// $Id: FixedPointAlgorithm.java,v 1.1.1.1 1999/12/05 22:19:51 mpp Exp $

package IR2;

import java.util.Hashtable;
import java.util.Enumeration;

public abstract class FixedPointAlgorithm {

  // Return vals from direction()
  protected final static int FORWARD = 1;
  protected final static int BACKWARD = 2;

  protected BasicBlock entry, exit;

  // Used for storing sets for each block
  private Hashtable in_table, out_table;
  // Constructor
  public FixedPointAlgorithm(BasicBlock entry, BasicBlock exit) {
    this.entry = entry;
    this.exit = exit;

    in_table = new Hashtable();
    out_table = new Hashtable();
  } 

  // Routines for retrieving the in and out sets

  // get IN set for block -- must be mutable
  protected Set in(BasicBlock b) {   
    return get_or_add(in_table, b);
  }

  // get OUT set for block -- must be mutable
  protected Set out(BasicBlock b) {
    return get_or_add(out_table, b);
  }

  private Set get_or_add(Hashtable table, Object key) {
    Set returnval = (Set)table.get(key);
    if (returnval == null) {
      returnval = new Set();
      table.put(key, returnval);
    }
    return returnval;
  }

  // Routines which must be implemented by subclasses
  abstract protected int direction();    // Return is BACKWARD or FORWARD
  abstract protected int confluence();   // Return is a constant from Set class

  abstract protected Set all_elements(); // Set of all elements.

  abstract protected Set generate(BasicBlock b); // compute generate bitset
  abstract protected Set kill(BasicBlock b);     // compute kill bitset

  abstract protected void optimize(); // Mutate Blocks to get optimization

  abstract protected void set_initial_conditions(); // Setup initial conds

  // Here we go.... DTRT!
  public void computeFixedPoint() {
    Enumeration e;
    // STEP ONE: Setup initial conditions via set_initial_conditions();
    set_initial_conditions();

    // STEP TWO: Determine direction via direction()
    int direction = direction();

    // STEP THREE: Determine confluence/meet operator via confluence()
    int confluence = confluence();

    //  STEP FOUR: For each basic block, compute generate and kill,
    //  via generate() and kill(); Will be stored in this class, and
    //  need not be in the BasicBlock. We are storing it here to avoid
    //  repeatedly recomputing gen/kill.
    Hashtable generate_table = new Hashtable();
    Hashtable kill_table = new Hashtable();
    Set changed=new Set();
    BasicBlock b;
    for (e = entry.self_and_all_successors(); e.hasMoreElements(); ) {
      // Add generate and kill sets to tables
      b = (BasicBlock)e.nextElement();
      generate_table.put(b, generate(b));
      kill_table.put(b, kill(b));

      // Add this to the changed set for later
      changed.addElement(b);
    }

    if (direction == FORWARD) {
      in(entry).clear();
      out(entry).copy(generate(entry));
    } else {
      //in(exit).copy(generate(exit));
      //out(exit).clear();
      ;
    }

    // STEP FIVE: Do the algorithm. This will modify in and out for
    // each BasicBlock. 

    // 5a. Changed set is initially all basic blocks except entry or exit
    // depending on direction.
    Set current, complement, old;
    changed.remove((direction == FORWARD) ? entry : exit);
    
    // 5b iterate til nothing is changed
    while (!changed.isEmpty()) {
      // Yank an element out.
      b = (BasicBlock)changed.first_element(); changed.removeElement(b);

      // Set either in or out to empty set, depending on which way we are going
      current = (direction == FORWARD) ? in(b) : out(b);

      if (confluence == Set.INTERSECTION)
        current.copy(all_elements());
      else if (confluence == Set.UNION) {
        current.clear();
      } else 
        /* No!  Don't use difference for confluence! */;

      // Handle 'meets', either forwards or backwards
      if (direction == FORWARD)
        for (e = b.get_predecessors(); e.hasMoreElements(); )
          current.perform_op(confluence, out((BasicBlock)e.nextElement()));
      else
        for (e = b.get_successors(); e.hasMoreElements(); )
          current.perform_op(confluence,  in((BasicBlock)e.nextElement()));

//System.err.println("    " + new Set(b.get_predecessors()));

      // Now, see if the old out/in (opposite of what we chose for current)
      // currently includes all the right things. If not, then there are
      // changes to propagate.
      // FORWARD:  out[b] = gen[b] U (in[b] - kill[b])
      // BACKWARD: in[b] = gen[b] U (out[b] - kill[b])
      complement = (direction == FORWARD) ? out(b) : in(b);
      old = new Set(complement);
      complement.copy(current);
      complement.difference((Set)kill_table.get(b));
      complement.union((Set)generate_table.get(b));
      
      // Changes to propagate? Add those nodes!
//System.err.println("CHANGED " + !complement.equals(old) + " " + b.get_first());
//System.err.println("        " + changed);
      if (!complement.equals(old)) {
        if (direction == FORWARD) {
          changed.add(b.get_successors());
        } else {
          changed.add(b.get_predecessors());
        }
      }
    }

    // STEP FOUR: call optimize() to muck stuff around with the
    // given in and out data.
    optimize();
  }
}