// Mike Maxim
// Canon trace scheduler

package edu.cmu.cs.l3.canon;

import edu.cmu.cs.l3.tree.*;
import edu.cmu.cs.l3.temp.*;
import java.util.*;

public class TraceScheduler {

    public TraceScheduler() {

    }

    public Vector getTraces() {
	return m_traces;
    }

    public void formTraces(BasicBlocker blocker) {

	int i;
	Vector blocks = blocker.getBlocks();
	Block curblock=null,nextblock=null;
	Trace curtrace;

	initBlockTable(blocks);
	for (i = 0; i < blocks.size(); i++) {
	    curtrace = new Trace();
	    curblock = (Block) blocks.elementAt(i);
	    while (!curblock.isMarked()) {
		curblock.mark();
		curtrace.addBlock(curblock);

		nextblock = getNextBlock(curblock.getJump());
		if (nextblock != null) {
		    curblock = nextblock;
		}
	    }

	    m_traces.addElement(curtrace);
	}

    }

    private Block getNextBlock(IRStatement jump) {

	Block tblock=null,fblock=null;

	if (jump.getClassName().equals("IRJump")) {
	    tblock = (Block)m_blocklookup.get(((IRJump)jump).getTarget());
	    if (tblock == null || tblock.isMarked()) {
		return null;
	    }
	    else {
		return tblock;
	    }
	}
	else {
	    tblock = (Block)m_blocklookup.get(((IRCJump)jump).getTrueLabel().getLabel());
	    fblock = (Block)m_blocklookup.get(((IRCJump)jump).getFalseLabel().getLabel());

	    if (!tblock.isMarked()) {
		return tblock;
	    }
	    else if (!fblock.isMarked()) {
		return fblock;
	    }
	    else {
		return null;
	    }
	}
    }

    public IRStatementList flattenTraces(Vector traces) {

	int i,j;
	Vector blocks;
	Block curblock,nextblock;
	IRStatementList stms = new IRStatementList();
	IRStatement jump;
	IRCJump cjump;

	blocks = linearizeTraces(traces);
	for (i = 0; i < blocks.size()-1; i++) {
	    curblock = (Block) blocks.elementAt(i);
	    nextblock = (Block) blocks.elementAt(i+1);

	    addLabelAndBody(stms,curblock);
	    procJump(stms,curblock,nextblock);
	}

	curblock = (Block) blocks.elementAt(i);
	jump = curblock.getJump();
	addLabelAndBody(stms,curblock);
	if (jump.getClassName().equals("IRJump")) {
	    stms.append_imp(jump);
	}
	else {
	    cjump = (IRCJump) jump;
	    IRLabel faketrue = new IRLabel(new Label());
	    stms.append_imp(new IRCJump(cjump.getRelationOperator(),cjump.getLeft(),cjump.getRight(),faketrue,cjump.getFalseLabel()));
	    stms.append_imp(faketrue);
	    stms.append_imp(new IRJump(cjump.getTrueLabel()));
	}

	return stms;
    }

    private void procJump(IRStatementList stms, Block curblock, Block nextblock) {

	IRStatement jump;
	IRCJump cjump;

	jump = curblock.getJump();
	if (jump.getClassName().equals("IRJump")) {
	    if ( ((IRJump)jump).getTarget().getLabel() != nextblock.getLabel().getLabel() ) {
		stms.append_imp(jump);
	    }
	}
	else {
	    cjump = (IRCJump) jump;
	    if ( cjump.getFalseLabel().getLabel() == nextblock.getLabel().getLabel() ) {
		switch (cjump.getRelationOperator()) {
		    case IRCJump.EQ:
			stms.append_imp(new IRCJump(IRCJump.NE,cjump.getLeft(),cjump.getRight(),cjump.getFalseLabel(),cjump.getTrueLabel()));
			break;
		    case IRCJump.NE:
			stms.append_imp(new IRCJump(IRCJump.EQ,cjump.getLeft(),cjump.getRight(),cjump.getFalseLabel(),cjump.getTrueLabel()));
			break;
		    case IRCJump.GT:
			stms.append_imp(new IRCJump(IRCJump.LE,cjump.getLeft(),cjump.getRight(),cjump.getFalseLabel(),cjump.getTrueLabel()));
			break;
		    case IRCJump.GE:
			stms.append_imp(new IRCJump(IRCJump.LT,cjump.getLeft(),cjump.getRight(),cjump.getFalseLabel(),cjump.getTrueLabel()));
			break;
		    case IRCJump.LE:
			stms.append_imp(new IRCJump(IRCJump.GT,cjump.getLeft(),cjump.getRight(),cjump.getFalseLabel(),cjump.getTrueLabel()));
			break;
		    case IRCJump.LT:
			stms.append_imp(new IRCJump(IRCJump.GE,cjump.getLeft(),cjump.getRight(),cjump.getFalseLabel(),cjump.getTrueLabel()));
			break;
		}
	    }
	    else if (cjump.getFalseLabel().getLabel() != nextblock.getLabel().getLabel() &&
		     cjump.getTrueLabel().getLabel() != nextblock.getLabel().getLabel()) {

		IRLabel faketrue = new IRLabel(new Label());
		stms.append_imp(new IRCJump(cjump.getRelationOperator(),cjump.getLeft(),cjump.getRight(),faketrue,cjump.getFalseLabel()));
		stms.append_imp(faketrue);
		stms.append_imp(new IRJump(cjump.getTrueLabel()));

	    }
	    else {
		stms.append_imp(cjump);
	    }
	}

    }

    private void addLabelAndBody(IRStatementList stms, Block block) {

	int i;
	stms.append_imp(block.getLabel());
	for (i = 0; i < block.getBody().getSize()-1; i++) {
	    stms.append_imp(block.getBody().getStatement(i));
	}
    }

    private Vector linearizeTraces(Vector traces) {

	Vector lin = new Vector();
	int i;

	for (i = 0; i < traces.size(); i++) {
	    lin.addAll(((Trace)traces.elementAt(i)).getBlocks());
	}

	return lin;
    }

    private void initBlockTable(Vector blocks) {
	int i;
	Block block;
	for (i = 0; i < blocks.size(); i++) {
	    block = (Block)blocks.elementAt(i);
	    block.unmark();
	    m_blocklookup.put(block.getLabel().getLabel(),block);
	}
    }

    private Vector m_traces = new Vector();
    private Hashtable m_blocklookup = new Hashtable();
}
