package IR2;

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

// CONTROL FLOW GRAPH

public class CFG {
  private DelocalizedInstruction start=null, last=null;
  private LowInstruction labeled_instr=null;
  public boolean debug;

  // Doubly linked list insertion (well it's a graph actually)
  // Returns: current
  public DelocalizedInstruction addElement(DelocalizedInstruction current, 
                                           DelocalizedInstruction previous) {
    if (current == null) {
      if (debug) System.err.println("Trying to add a null element. Denied!");
      return previous;
    }

    if (start == null) 
      start = current;
    
    current.add_prev_instr(previous);
    if (previous != null)
      previous.add_next_instr(current);

    last = current;

    // Should be labeled?
    if (labeled_instr != null) {
      current.set_label(labeled_instr.get_label().get_name());
      labeled_instr.set_deloc_instr(current);
      labeled_instr = null;
    }

    return current;
  }
  
  // We let the L/RValue sequences use this, since we know they chain
  // together. This, combined with set_last(), is arguably better than
  // being forced to pass prev() around all over the place, *shrug*. Currently
  // needed for R/LValue asm code production
  public void addElement(DelocalizedInstruction current) {
    addElement(current, last);
  }

  // Set last thing added
  public void set_last(DelocalizedInstruction di) { last = di; }

  // Return last thing added.
  public DelocalizedInstruction last() {
    return last;
  }

  public void set_next_label_source(LowInstruction li) {
    labeled_instr = li;
  }


  // Create BasicBlocks graph. Don't use a Traversal this time. Cleaner.
  private Hashtable first_instructions;
  public BasicBlock generate_basicblocks() {
    first_instructions = new Hashtable();
    enter_block = generate_basicblocks(start);
    
    if (debug) {
      System.err.println("BasicBlock graph:");
      Traversal tr = new Traversal() {

        public boolean visit(Traversable t) { 
          BasicBlock b = (BasicBlock) t; 
          DelocalizedInstruction i = b.get_first();
          System.err.println(i);
          i = b.next_instr(i);
          while (i != null) {
            System.err.println(i);
            i = b.next_instr(i);
          }
          
          for (Enumeration e = b.get_successors(); e.hasMoreElements(); )
            System.err.println(" s " +
                               ((BasicBlock)e.nextElement()).get_first()); 
          for (Enumeration e = b.get_predecessors(); e.hasMoreElements(); )
            System.err.println(" p " +
                               ((BasicBlock)e.nextElement()).get_first()); 
          return true; 
        }
      };
      tr.traverse(enter_block);
      for (int i = 0; i < 4; i++)
        System.err.println();
    }

    return enter_block;
  }


  private BasicBlock enter_block = null, exit_block = null;
  public BasicBlock get_enter_block() { return enter_block; }
  public BasicBlock get_exit_block()  { return exit_block; }

  private BasicBlock generate_basicblocks(DelocalizedInstruction inst) {
    // Cycle?
    Object o = first_instructions.get(inst);
    if (o != null) return (BasicBlock)o;

    BasicBlock current = new BasicBlock();
    first_instructions.put(inst, current);
    
    // Keep going until either node has multiple previous's or multiple nexts,
    // or we're done.
    while (inst != null && inst.num_next() <= 1 && 
           (inst.num_prev() <= 1 || current.get_first() == null)) {
      current.add_instruction(inst);
      inst = inst.next_instr();
    }
    
    // How did we terminate?
    if (inst != null) {
      if (inst.num_prev() > 1 && current.get_first() != null) {
        BasicBlock rest = generate_basicblocks(inst);
        rest.add_predecessor(current);
        current.add_successor(rest);
      } else if (inst.num_next() > 1) {
	current.add_instruction(inst);
	BasicBlock rest;
	for (Enumeration e = inst.next(); e.hasMoreElements(); ) {
	  rest = generate_basicblocks((DelocalizedInstruction)e.nextElement());
	  rest.add_predecessor(current);
	  current.add_successor(rest);
        }
      }
    } else {
      // Only DelocalizedExitInstructions have no next instruction,
      // so the current block is the exit block.
      exit_block = current;
    }
	
    return current;
  }

  // Linearize me baby!
  public DelocalizedInstructionSequence linearize() {
    final DelocalizedInstructionSequence asm_seq = 
      new DelocalizedInstructionSequence();
    
    Traversal linearization_traversal = new Traversal() {
      
      // Everytime you visit a node, add it to the Sequence
      public boolean visit(Traversable t) {
	if (debug) System.out.print("Visiting: ");
	
	if (((DelocalizedInstruction)t).num_labels() != 0) {
          for (Enumeration e = ((DelocalizedInstruction)t).get_labels(); 
               e.hasMoreElements(); ) {
                 String label = (String)e.nextElement();
                 if (debug) System.out.print("[" + label + "] ");
                 asm_seq.addElement(new DelocalizedLabelInstruction(label));
               }
	}
	
	if (debug) System.out.println(t.toString());
	
        asm_seq.addElement(t);
        return true;
      }
      
      // Already been here? Then dump down a Branch to this. (It should
      // be a label, or has a label. If not, uh....)
      public void already_seen(Traversable t) {
        String label;

	if (((DelocalizedInstruction)t).num_labels()==0) 
	    throw new Error("Internal compiler error: Revisited labeless " +
			    "node " + t);
	
	if (debug) { 
          System.out.print("Already seen: " + t + " / ");
          for (Enumeration e = ((DelocalizedInstruction)t).get_labels(); 
               e.hasMoreElements(); ) {
                 label = (String)e.nextElement();
                 System.out.print(" " + label + " ");
               }
          System.out.println("");
        }

	// This general method could be put in DelocInstrSeq if we thought
	// we add unreachable code in other situations also.
	Object o = asm_seq.lastElement();
	if (!(o instanceof DelocalizedBranchInstruction) || 
	    (o instanceof DelocalizedCondBranchInstruction)) {
              label = 
                (String)((DelocalizedInstruction)t).get_labels().nextElement();
              asm_seq.addElement(new DelocalizedBranchInstruction(label));
            }
      }

    };
    
    // Do it!
    linearization_traversal.traverse(start);

    return asm_seq;
  }
}