// $Id: CopyPropagation.java,v 1.2 1999/12/07 06:34:50 golem Exp $

package IR2;

import java.util.*;

public class CopyPropagation extends FixedPointAlgorithm {

  private class Copy implements CopyInstruction {
    public DelocalizedLValue dest;
    public DelocalizedRValue src;
    public Copy(CopyInstruction insn) {
      dest = insn.copy_destination();
      src = insn.copy_source();
    }
    public DelocalizedLValue copy_destination() { return dest; }
    public DelocalizedRValue copy_source()      { return src; }
    public boolean equals(Object obj) {
      if (!(obj instanceof Copy))
        return false;
      Copy other = (Copy) obj;
      return dest.equals(other.dest) && src.equals(other.src);
    }
    public int hashCode() { return dest.hashCode() ^ src.hashCode(); }
    public String toString() { return "Copy: " + dest + " <- " + src; }
  }

  public CopyPropagation(BasicBlock entry, BasicBlock exit) {
    super(entry, exit);
  }

  protected int direction() {
    return FORWARD;
  }

  protected int confluence() {
    return Set.INTERSECTION;
  }

  Set all_copies;
  protected Set all_elements() { return all_copies; }

  protected void set_initial_conditions() {
    // Collect the set of all "copies".
    all_copies = new Set();

    Enumeration e = entry.self_and_all_successors();
    while (e.hasMoreElements()) {
      BasicBlock b = (BasicBlock) e.nextElement();
      for (DelocalizedInstruction insn = b.get_first();
           insn != null;
           insn = b.next_instr(insn)) {
        if (insn instanceof CopyInstruction) {
          Copy copy = new Copy((CopyInstruction) insn);
          all_copies.add(copy);
        }
      }
    }
  }

  protected Set generate(BasicBlock b) {
    Set gen = new Set();
    for (DelocalizedInstruction insn = b.get_first();
         insn != null;
         insn = b.next_instr(insn)) {
      Enumeration e = all_copies.elements();
      while (e.hasMoreElements()) {
        Copy copy = (Copy) e.nextElement();
        if (insn.kills_copy(copy))
          gen.remove(copy);
      }
      if (insn instanceof CopyInstruction)
        gen.add(new Copy((CopyInstruction) insn));
    }
    return gen;
  }

  protected Set kill(BasicBlock b) {
    Set kill = new Set();
    for (DelocalizedInstruction insn = b.get_first();
         insn != null;
         insn = b.next_instr(insn)) {
      Enumeration e = all_copies.elements();
      while (e.hasMoreElements()) {
        Copy copy = (Copy) e.nextElement();
        if (insn.kills_copy(copy))
          kill.add(copy);
      }
      // This is suspect, try commenting out if algorithm doesn't work.
      if (insn instanceof CopyInstruction)
        kill.remove(new Copy((CopyInstruction) insn));
    }
    return kill;
  }


  protected void optimize() {
//System.err.println("all_copies " + all_copies);

    // Now mutate the copy instructions.
    Enumeration e = entry.self_and_all_successors();
    while (e.hasMoreElements()) {
      BasicBlock b = (BasicBlock) e.nextElement();
//System.err.println(b + " " + b.get_first());
      // Fulfills role of "tmp to var" in notes.
      // Recursively searches --- I hope this is ok.
      Bucket var_to_copy = new Bucket() {
        public synchronized Object get(Object key) {
          while (true) {
            Object value = super.get(key);
            if (!containsKey(value))
              return value;
            key = value;
          }
        }
      };

//System.err.println("        IN:  " + new Set(in(b)));
//System.err.println("        OUT: " + new Set(out(b)));

      Enumeration ein = in(b).elements();
      while (ein.hasMoreElements()) {
        Copy copy = (Copy) ein.nextElement();
        var_to_copy.put(copy.copy_destination(), copy.copy_source());
      }

      for (DelocalizedInstruction insn = b.get_first();
           insn != null;
           insn = b.next_instr(insn)) {

//System.err.println(var_to_copy);

        insn.substitute_copies(var_to_copy);

        Enumeration ecopies = all_copies.elements();
        while (ecopies.hasMoreElements()) {
          Copy copy = (Copy) ecopies.nextElement();
          if (insn.kills_copy(copy)) {
            Object dest = copy.copy_destination();
            if (var_to_copy.containsKey(dest)
                && var_to_copy.get(dest) == copy.copy_source()) {
              var_to_copy.remove(copy.copy_destination());
            }
          }
        }
        if (insn instanceof CopyInstruction) {
          CopyInstruction copy_insn = (CopyInstruction) insn;
          var_to_copy.put(copy_insn.copy_destination(),
                          copy_insn.copy_source());
        }
//System.err.println(var_to_copy);

      }
    }

  }

}