package edu.cmu.cs.l3.regalloc;

import edu.cmu.cs.l3.analysis.*;
import edu.cmu.cs.l3.flowgraph.*;
import edu.cmu.cs.l3.graph.*;
import edu.cmu.cs.l3.temp.*;
import edu.cmu.cs.l3.assem.*;
import java.util.*;

public class LivenessIGConstructor implements IGConstructor {

    public LivenessIGConstructor() {
    }

    // Build interference graph using liveness analysis
    public InterferenceGraph build(FlowGraph fg, List precolored, List moves)
        throws GraphException {

        InterferenceGraph ig = new InterferenceGraph();
        Liveness la = new Liveness();
        List instrs = fg.getVertices();
        BitSet mtemps;
        int i, j, k;

        la.analyze(fg);
        //Add vertices for all precols
        for (i = 0; i < precolored.size(); i++) {
            Temp p = (Temp) precolored.get(i);
            ig.getIntVertex(p.num(), precolored);
        }
        for (i = 0; i < instrs.size(); i++) {

            FlowVertex v = (FlowVertex) instrs.get(i);
            BitSet live = (BitSet) la.getOutSet(v).clone();

            if (v.getInstruction() instanceof MoveInstruction) {
                MoveInstruction m = (MoveInstruction) v.getInstruction();
                boolean tmove = (m.destTemps().size() > 0 && m.sourceTemps().size() > 0
                                 && !m.isMemRelated());
                if (!m.isMemRelated()) live.andNot(v.getUses());
                mtemps = v.getDefines();
                mtemps.or(v.getUses());
                for (j = mtemps.nextSetBit(0); j >= 0;
                     j = mtemps.nextSetBit(j + 1)) {
                    Temp tj = (Temp) Temp.tempList.get(j);
                    if (tj.isSpilled() || tj.isGlobal() || tj.hasValue()) {
                        tmove = false;
                        break;
                    }
                    InterferenceVertex n = ig.getIntVertex(j, precolored);
                    if (tmove) n.getMoveList().add(m);
                }
                if (tmove) moves.add(m);
            }

            BitSet def = v.getDefines();
            live.or(def);
            for (j = def.nextSetBit(0); j >= 0; j = def.nextSetBit(j + 1)) {
                Temp tj = (Temp) Temp.tempList.get(j);
                if (tj.isSpilled() || tj.isGlobal() || tj.hasValue())
                    continue;
                for (k = live.nextSetBit(0); k >= 0; k = live.nextSetBit(k + 1)) {
                    Temp tk = (Temp) Temp.tempList.get(k);
                    if (tk.isSpilled() || tk.isGlobal() || tk.hasValue())
                        continue;
                    InterferenceVertex d = ig.getIntVertex(j, precolored);
                    InterferenceVertex l = ig.getIntVertex(k, precolored);

                    ig.createIntEdge(l, d);
                }
            }
        }

        return ig;
    }

}