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

package IR2;
import java.util.*;

public class DeadCodeElimination extends FixedPointAlgorithm {

  Set vars = new Set();
  Set initconds = new Set();

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

  protected int direction() {
    return BACKWARD;
  }

  protected int confluence() {       // Return is a constant from Set class
    return Set.UNION;
  }

  protected Set generate(BasicBlock b) {  // compute generate bitset */
    Set s = new Set();
    DelocalizedInstruction foo = b.get_last();
//      System.out.println("b: " + b);
//      System.out.println("foo: " + foo);
    if (foo != null) {
      s.addElements(foo.lsources());
      vars.addElements(foo.lsources());
//        System.out.println("Generating " + foo.lsources());
    }
    while (foo != b.get_first()) {
       foo = foo.prev_instr();
       if (foo != null) {
         Enumeration bar = foo.lsources();
         while (bar.hasMoreElements()) {
           Object baz = bar.nextElement();
           s.add(baz);
           vars.add(baz);
           //           System.out.println("Baz: " + baz);
         }
         //        System.out.println("Generating " + foo.lsources());
      }
    }
    return s;
  }

  protected Set kill(BasicBlock b) {     // compute kill bitset */
    Set s = new Set();
    DelocalizedInstruction foo = b.get_last();
    if (foo != null && foo.destination() != null) {
      s.add(foo.destination());
      vars.add(foo.destination());
      //      System.out.println("Killing " + foo.destination());
    }
    while (foo != b.get_first()) {
      foo = foo.prev_instr();
      if (foo != null && foo.destination() != null) {
        s.add(foo.destination());
        vars.add(foo.destination());
        //        System.out.println("Killing " + foo.destination());
      }
    }
    return s;
  }


  protected void optimize() {  /* Mutate Blocks to achieve desired effect */
    Enumeration blob = entry.self_and_all_successors();

    while (blob.hasMoreElements()) {
      BasicBlock curblock = (BasicBlock)blob.nextElement();

      Set needed = this.out(curblock);

      DelocalizedInstruction curinstr = curblock.get_last(), prev;
      DelocalizedLValue dest;

      while (curinstr != null) {
        // Check assignment. If destination not needed, eliminate this dead
        // code. if it is needed, remove it from the needed set.
        prev = curblock.prev_instr(curinstr);
        dest = curinstr.destination();

        if (dest != null) {
          // No punting callouts and calls eh? could have side effects
          if (!(curinstr instanceof DelocalizedCalloutInstruction) &&
              !(curinstr instanceof DelocalizedCallInstruction) && 
              !(dest instanceof DelocalizedRegister) &&
              !needed.contains(dest)) {

            // Make sure it isn't a copy from a register
            boolean okay = true;
            for (Enumeration e = curinstr.lsources(); 
                 e.hasMoreElements() && okay; ) 
              okay = !(e.nextElement() instanceof DelocalizedRegister);
            
            if (okay) {
              //              System.out.println(" REMOVED " + curinstr);
              curblock.removeElement(curinstr);
            }
          }
          else {
            // No longer neeed.
            needed.removeElement(dest);
          }
        }

        // Now parse the rvalues and see what else we will need.
        for (Enumeration e = curinstr.lsources(); e.hasMoreElements() ; ) 
          needed.addElement(e.nextElement());
        
        curinstr = prev;
      }
    }
  }  

  protected Set all_elements() {
    Set retval = new Set();
    Enumeration blob = entry.self_and_all_successors();
    while (blob.hasMoreElements()){
      BasicBlock curblock = (BasicBlock)blob.nextElement();
      //System.out.println("  Block grabbed to deal with allelements: " + curblock);
      DelocalizedInstruction foo = curblock.get_first();
      while (foo != null) {
        if (foo.destination() != null) {
          retval.add(foo.destination()); 
        }
        foo = curblock.next_instr(foo);
        //        if (foo == curblock.get_last()) {
        // foo = null;
        //} else {
        //  foo = foo.next_instr();
        //}
      }
    }
    return retval;
  }


  protected void set_initial_conditions() {
    // Step 1: Collect Underpants^Win[exit] set (global fields)
    Enumeration blob = entry.self_and_all_successors();
    while (blob.hasMoreElements()){
      BasicBlock curblock = (BasicBlock)blob.nextElement();
      //System.out.println("  Block grabbed to deal with initconds: " + curblock);
      DelocalizedInstruction foo = curblock.get_first();
      while (foo != null) {
        if (foo.destination() instanceof GlobalScalarVarDescriptor && foo != null) {
          initconds.add(foo.destination()); 
          // if something doesn't ever turn up as a destination, we're not 
          // going to optimize it out anyway.
        }
        if (foo == curblock.get_last()) {
          foo = null;
        } else {
          foo = foo.next_instr();
        }
      }
    }
    // Step 2: ???^WSet the initial conditions (in and out) of each block
    blob = entry.self_and_all_successors();
    while (blob.hasMoreElements()){
      BasicBlock curblock = (BasicBlock)blob.nextElement();
      if (curblock == exit) {
        out(curblock).copy(initconds);
        in(exit).copy(generate(exit));
        //out(curblock).clear();
      } else {
        in(curblock).clear();
        out(curblock).clear();
      }
    }
    // Step 3: Profit!
  }
}