package IR2;
import java.util.*;

public class InterferenceGraph {
  private Vector webs = new Vector();
  private Vector adj = new Vector();
  private boolean ig[][];


  public InterferenceGraph(Vector chains, MethodDescriptor d) {
    
    boolean working = true;
    if (chains.isEmpty()) { 
      working = false;
    }

    // Reset count on symbolic regs we are about use.
    SymbolicRegister.reset_count();

    
    while(working) {
      Web w = new Web();
      DUChain foo = (DUChain)chains.firstElement();
      w.add_DUChain(foo);
      chains.removeElement(foo);
      // step 2: exhaustively build web
      boolean flag = true;
      while (flag) {
        flag = false;
        Enumeration ec = chains.elements();
        while (ec.hasMoreElements()) {
          DUChain bar = (DUChain)ec.nextElement();
          if (w.add_DUChain(bar)) {
            flag = true;
            //            System.out.println("DUChain w/" + bar.get_def() + " added to web " + w);
            chains.removeElement(bar);
          }
        }
      }

      // step 3: web complete. Switch to symbolic register mode.
      w.substitute_symbolic_regs(d);

      // step 4: put web in webs
      webs.addElement(w);

      // step 5: check for 'no more chains'
      if (chains.isEmpty()) {
        working = false;
        //        System.out.println("We're done building webs.");
      }
    } 
  }

  public Enumeration return_webs() {
    return webs.elements();
  }

  public void build_graph() {
    
    // Our adjacency graph is not dependent on registers, so we
    // can make it once and use it many times.

    int n = webs.size();
    int i,j;

    ig = new boolean[n][];
    for (i=0; i<n; i++)
      ig[i] = new boolean[n];
    
    for (i=0; i<n; i++) {
      for (j=0; j<n; j++) {
        ig[i][j] = false;
      }
    }

    // We have no constraints as to which register to use. So we're
    // going to ignore all the whining in the book about it and just
    // have no register-specific constraints. It makes the matrix
    // a bit easier too. It's all initialized to false, now I'll
    // put things in that are interfering.
    // I'm also going to make it a full square matrix, because we honestly
    // don't care about a factor of 2 speed savings in compilation.

    //System.out.println("Building interference graph.");
    for (i=0; i<n; i++) {
      for (j=0; j<n; j++) {
        Web foo = (Web)webs.elementAt(i);
        Web bar = (Web)webs.elementAt(j);
        if (i != j)
          ig[i][j] = foo.interfere(bar);
        //System.out.print(".");
      }
    }

    // Great. we have an interference graph. 
    // now we need adjacency entries

    //System.out.println("Building adjacency entries.");
    adj = new Vector();
    for (i=0; i<n; i++) {
      Web baz = (Web)webs.elementAt(i);
      AdjacencyEntry quux = new AdjacencyEntry(baz);
      adj.insertElementAt(quux, i);
    }
    // now initialize them.

    for (i=0; i<n; i++) {
      AdjacencyEntry quux = (AdjacencyEntry)adj.elementAt(i);
      for (j=0; j<n; j++) {
        if (ig[i][j] && (i != j)) { //we found an interference!
          //System.out.println("Interference found.");
          quux.inc_nints();
          quux.add_adjnd((AdjacencyEntry)adj.elementAt(j));
        }
      }
    }

    // OK! adjacencies and nints created.

    // SPILL COSTS
    // For right now, I think a reasonable approximation to spill
    // costs can be some number (10) - the number of interferences.
    
    for (i=0; i<n; i++) {
      ((AdjacencyEntry)adj.elementAt(i)).set_spcost(10.0 - (double)(((AdjacencyEntry)adj.elementAt(i)).get_nints()));
    }

    // ATTEMPT TO COLOR
    // see color(R)
  }

  public Stack prune_graph(int R) {
    boolean success;
    int i, j;
    int dealt_with = 0;
    int nodes = adj.size();
    int spillnode;
    double spillcost;
    Stack s = new Stack();
    
    while (nodes != dealt_with) {
      boolean spill = true;
      spillnode = -1;
      // Step 1 - See if we can prune without spilling.
      for (i=0; i<adj.size(); i++) {
        AdjacencyEntry foo = (AdjacencyEntry)adj.elementAt(i);
        //        System.out.println("foo.get_nints() = " +foo.get_nints());
        if (foo.get_nints() > -1) {
          if (spillnode == -1) {
            //            System.out.println("Hello?");
            spillnode = i;
          } else {
            if (((AdjacencyEntry)adj.elementAt(spillnode)).get_spcost() >
                ((AdjacencyEntry)adj.elementAt(i)).get_spcost()) {
              spillnode = i;
            }
          }
        }
        if (foo.get_nints() > -1 && foo.get_nints() < R) { 
          // if not already on stack and degree < R
          spill = false;
          foo.set_nints(-1);
          s.push(foo);
          dealt_with++;
          Enumeration nbrs = foo.get_adjnds();
          while (nbrs.hasMoreElements()) {
            AdjacencyEntry bar = (AdjacencyEntry)nbrs.nextElement();
            bar.dec_nints();
          }
        }
      }
      // Step 2 - If we have to spill, spill.
      if (spill) {
        AdjacencyEntry foo = (AdjacencyEntry)adj.elementAt(spillnode);
        Enumeration nbrs = foo.get_adjnds();
        while (nbrs.hasMoreElements()) {
          AdjacencyEntry bar = (AdjacencyEntry)nbrs.nextElement();
          bar.rem_adjnd(foo);
          bar.dec_nints();
        }
        dealt_with++;
        foo.set_nints(-1);
        
      }
    }
    return s;
  }

  public void color(Codegen c) {
    DelocalizedRegister[] registers = c.allocatable_registers();
    int R = registers.length;
    Stack s = prune_graph(R);
    int i, j;
    //Integer k;
    
    while (!s.empty()) {
      int colors[] = new int[R];
      //Vector colors = new Vector();
      for (i=0; i<R; i++) {
        //k = new Integer(i);
        //colors.insertElementAt(k, i);
        colors[i] = i;
      }
      // colors built.
      AdjacencyEntry ae = (AdjacencyEntry)s.pop();
      Enumeration nbrs = ae.get_adjnds();
      while (nbrs.hasMoreElements()) {
        AdjacencyEntry foo = (AdjacencyEntry)nbrs.nextElement();
        if (foo.get_color() != -1) { // found something colored, frob it
          //colors.removeElement(new Integerfoo.get_color());          
          colors[foo.get_color()] = -1;
        }
      }
      // OK. We have eliminated all colors which we neighbor.
      // Our color will be the first non-negative integer we find in
      // the vector.
      boolean puke = false;
      j = 0;
      while (!puke) {
        if (colors[j] > -1) {
          ae.set_color(colors[j]);

          //          System.out.print("Colorstate: ");
          //          for (i=0; i<R; i++) {
          //            System.out.print(colors[i]);
          //          }
          //          System.out.println(" ");
          
          puke = true;
        }
        j++;
      }
    }
    set_proxies(registers);
  }

  public void set_proxies(DelocalizedRegister[] registers) {
    // this strangely-named procedure calls set_proxy on the DelocalizedLValues
    // represented by each AdjacencyEntry in adj.
    Enumeration foo = adj.elements();
    while (foo.hasMoreElements()) {
      AdjacencyEntry bar = (AdjacencyEntry)foo.nextElement();
      DelocalizedLValue baz = bar.get_lvalue();
      if (bar.get_color() > -1) {
        ((LocalScalarVarDescriptor)baz).set_proxy(registers[bar.get_color()]);
      }
      //     System.out.println("PROXY: "+baz+" Colored "+bar.get_color());
    }
  }

  public void add_web(Web w) {
    webs.addElement(w);
  }

}