/**
 * Copyright (c) 2005 by Kevin Bierhoff
 */
package edu.cmu.cs.l3.canon;

import java.util.ArrayList;
import java.util.BitSet;
import java.util.Iterator;
import java.util.Set;
import java.util.Vector;

import edu.cmu.cs.l3.temp.Label;
import edu.cmu.cs.l3.tree.IRCJump;
import edu.cmu.cs.l3.tree.IRJump;
import edu.cmu.cs.l3.tree.IRLabel;
import edu.cmu.cs.l3.tree.IRStatementList;

/**
 * Encapsulation of a dominator tree for a list of blocks. <b>The dominator tree is invalid if the list
 * of blocks is modified after the construction of the tree!</b> A block dominates another block, a dom b, 
 * if all paths from the entry block to b go through a. The immediate dominator of a block is unique and can
 * be retrieved through {@link #getImmediateDominatorOf(int)}. {@link #getDominatorsOf(int)} returns all
 * dominators of b, i.e. the set of all a such that a dom b. Dominator sets are managed as bit sets
 * where bit indices correspond to block indices. 
 * 
 * @author Kevin
 */
public class DominatorTree extends BlockFlowGraph {

	/** The bit set of dominators for each block in <code>blocks</code>. */
	private ArrayList dominators;
	/** The unique immediate dominator for each block or -1. */
	private int[] idom;

	/**
	 * Creates a dominator tree for a given list of blocks.
	 * @param blocks
	 */
	public DominatorTree(Vector blocks) {
		super(blocks);
		computeDominators();
		buildDominatorTree();
	}

	/**
	 * Returns the dominators of a given block. <b>Do not change the result!</b>
	 * @param blockIndex The block in question.
	 * @return The dominators of a given block as <code>true</code> bits in a bit set.
	 */
	public BitSet getDominatorsOf(int blockIndex) {
		return (BitSet) dominators.get(blockIndex);
	}
	
	/**
	 * Returns the idom of a given block.
	 * @param blockIndex The block we want the idom for.
	 * @return The block number of the immediate dominator or -1 if no dominator exists.
	 */
	public int getImmediateDominatorOf(int blockIndex) {
		return idom[blockIndex];
	}
	
	/**
	 * Identifies or creates a unique pre-header block of a given block. The pre-header has the given
	 * block as its only successor, and the given block dominates all other predecessors (i.e. the
	 * other predecessors are part of a loop).
	 * @param blockIndex
	 * @return
	 */
	public int findPreHeader(int blockIndex) {
		Block b = (Block) blocks.get(blockIndex);

		int result = getImmediateDominatorOf(blockIndex);
		
		preHeaderTest:
		if(result >= 0) { 
			Set rsuccs = getSuccs(getBlock(result));
			if(rsuccs.size() == 1 && rsuccs.contains(new Integer(blockIndex))) {
				for(Iterator it = getPreds(getBlock(blockIndex)).iterator(); it.hasNext(); ) {
					int pred = ((Integer) it.next()).intValue();
					if(pred != result && !getDominatorsOf(pred).get(blockIndex))
						break;
				}
				return result;
			}
		}
		return insertPreHeader(b);
	}
	
	protected void recompute() {
		super.recompute();
		computeDominators();
		buildDominatorTree();
	}

	/**
	 * Computes dominator sets.
	 */
	private void computeDominators() {
		dominators = new ArrayList();
		idom = null;
		
		// entry block
		BitSet entryDoms = new BitSet(blocks.size());
		entryDoms.set(0);
		dominators.add(0, entryDoms);
		
		// initialize all other blocks with all blocks dominating them (we later intersect...)
		for(int i = 1; i < blocks.size(); i++) {
			BitSet initialValue = new BitSet(blocks.size());
			initialValue.set(0, blocks.size());
			dominators.add(i, initialValue);
		}
		
		// iterate over all blocks until fixpoint is reached
		boolean changed = true;
		while(changed) {
			changed = false;
			for(int i = 1; i < blocks.size(); i++) {
				Set ipreds = getPreds((Block) blocks.get(i));
				BitSet newDoms = new BitSet(blocks.size());

				// build intersection of predecessor sets, IF ANY
				if(!ipreds.isEmpty()) {
					newDoms.set(0, blocks.size());
					for(Iterator it = ipreds.iterator(); it.hasNext(); ) {
						newDoms.and((BitSet) dominators.get(((Integer) it.next()).intValue()));
					}
				}
				
				// all blocks dominate themselves
				newDoms.set(i);
				
				// compare to previous result
				if(!newDoms.equals(dominators.get(i))) {
					dominators.set(i, newDoms);
					changed = true;
				}
			}
		}
		
	}

	/**
	 * Computes immediate dominators.
	 */
	private void buildDominatorTree() {
		idom = new int[blocks.size()];
		for(int i = 0; i < blocks.size(); i++) {
			// derive sdom from dom
			BitSet pivot = (BitSet) getDominatorsOf(i).clone();
			pivot.clear(i);
			
			// go through all x sdom i
			for(int x=pivot.nextSetBit(0); x>=0; x=pivot.nextSetBit(x+1)) {
				BitSet sdomx = getDominatorsOf(x);
				// all y sdom i st. y sdom x cannot be y idom i 
				for(int y=pivot.nextSetBit(0); y>=0; y=pivot.nextSetBit(y+1)) {
					if(x == y) continue;
					if(sdomx.get(y)) {
						pivot.clear(y);
					}
				}
			}
			
			// the only set bit is the idom of i
			int result = pivot.nextSetBit(0);
			idom[i] = result;
			
			// if no idom for i then i has to be an entry node
			if(result == -1) {
				if(!getPreds((Block) blocks.get(i)).isEmpty()) {
					System.out.println("Block " + i + " has predecessors but no idom!");
				}
				continue;
			}
			
			// idom is unique --> there shouldn't be any other bits set
			if(pivot.nextSetBit(result + 1) >= 0) {
				System.out.println("Identified more than one idom for block " + i);
			}
			
		}
	}
	
	/**
	 * This method inserts a pre-header block before a given block. The pre-header will be inserted
	 * between the given block and its predecessors except predecessors that are dominated by the given
	 * block. In that way, back edges from loop bodies keep pointing at the given block, while edges
	 * from outside the loop now point to the pre-header. <b>This operation will recompute the
	 * flow graph and dominator information.</b>
	 * @param b
	 * @return The index of the inserted block.
	 */
	private int insertPreHeader(Block b) {
		// label for new block
		Label lab = new Label();
		// statement list that contains only a jump to b
		IRStatementList justTheJump = new IRStatementList(new IRJump(new IRLabel(b.getLabel().getLabel())));
		// the new block
		Block preHeader = new Block(new IRLabel(lab), justTheJump);
		// we append it to the end of the list of blocks
		int result = blocks.size();
		blocks.add(preHeader);
		labelsToBlocks.put(preHeader.getLabel().toString(), new Integer(result));
		
		Set bpreds = getPreds(b);
		// update b's predecessors to jump to new block
		String targetName = b.getLabel().toString();
		int targetIndex = getBlockIndex(targetName);
		for(Iterator it = bpreds.iterator(); it.hasNext(); ) {
			int curIndex = ((Integer) it.next()).intValue();
			
			// if this block is dominated by b, the block is within a loop with header b
			// the pre-header should not be included in the loop
			if(getDominatorsOf(curIndex).get(targetIndex)) {
				continue;
			}
			
			Block cur = (Block) blocks.get(curIndex);
			
			if(cur.getJump() instanceof IRJump) {
				IRJump jump = (IRJump) cur.getJump();
				if(jump.getTarget().toString().equals(targetName))
					jump.setTarget(new IRLabel(lab));
				else
					System.out.println("" + cur.getLabel() + " should jump to " + targetName);
			}
			if(cur.getJump() instanceof IRCJump) {
				IRCJump cjump = (IRCJump) cur.getJump();
				boolean changed = false;
				if(cjump.getFalseLabel().toString().equals(targetName)) { 
					cjump.setFalseLabel(new IRLabel(lab));
					changed = true;
				}
				if(cjump.getTrueLabel().toString().equals(targetName)) { 
					cjump.setTrueLabel(new IRLabel(lab));
					changed = true;
				}
				if(!changed)
					System.out.println("" + cur.getLabel() + " should jump to " + targetName);
			}
			
			/* // update cur's successor set to exclude b ...
			if(!getSuccs(cur).remove(new Integer(targetIndex))) {
				System.out.println("Succs of " + cur.getLabel() + " should contain " + targetName);
			}
			// .. and include result
			getSuccs(cur).add(new Integer(result)); */
		}
		
		/* // the new block is b's only predecessor now
		HashSet pivot = new HashSet();
		pivot.add(new Integer(result));
		preds.put(b, pivot);
		
		// result's predecessors used to be b's
		preds.put(preHeader, bpreds);
		
		// b is result's only successor
		pivot = new HashSet();
		pivot.add(new Integer(targetIndex));
		succs.put(preHeader, pivot); */
		
		// fix up data structures
		recompute();

		return result;
	}
	
	public String toString() {
		StringBuffer result = new StringBuffer("Dominator tree:\n");
		for(int i = 0; i < idom.length; i++) {
			if(idom[i] >= 0) {
				result.append(((Block) blocks.get(idom[i])).getLabel());
				result.append(" idom "); 
				result.append(((Block) blocks.get(i)).getLabel());
				result.append('\n');
			}
			else
				result.append(((Block) blocks.get(i)).getLabel() + " has no dominators.\n");
		}
		return result.toString();
	}

	/**
	 * @param dominatorIndex
	 * @param blockIndex
	 * @return
	 */
	public boolean dominates(int dominatorIndex, int blockIndex) {
		return getDominatorsOf(blockIndex).get(dominatorIndex);
	}

}
