// Mike Maxim
// Liveness analysis module
// TODO: Sort vertices backward

package edu.cmu.cs.l3.analysis;

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

public class Liveness {

    public Liveness() {

    }

    public void analyze(FlowGraph fg) throws GraphException {

        int i,j,numverts,reps=0,dups;
        boolean fixed = false;
        BitSet in,out,inprime,outprime;

        numverts = fg.getNumVertices();
        m_insets = new BitSet[numverts];
        m_outsets = new BitSet[numverts];

        List vertices = fg.getDFSTrace(fg.getExitNode(), false);
        for (i = 0; i < numverts; i++) {
            m_insets[i] = new BitSet(Temp.count());
            m_outsets[i] = new BitSet(Temp.count());
        }
        while (!fixed) {
          //  System.out.println("REPS: " + ++reps + " MAXREPS: " + 2*numverts*numverts);
            fixed = true; dups=0;
            for (i = 0; i < vertices.size(); i++) {

                FlowVertex v = ((FlowVertex)vertices.get(i));

                in = m_insets[v.getID()]; out = m_outsets[v.getID()];
                inprime = (BitSet)in.clone(); outprime = (BitSet)out.clone();

                //Outset calculation
                List succs = fg.getChildren(v);
                BitSet union = new BitSet(Temp.count());
                for (j = 0; j < succs.size(); j++) {
                    FlowVertex u = (FlowVertex) succs.get(j);
                    union.or(m_insets[u.getID()]);
                }
                out.clear(); out.or(union);

                // Inset calculation
                in.clear();
                BitSet useset = (BitSet)v.getUses().clone();
                BitSet defset = (BitSet)v.getDefines();
                BitSet outset = (BitSet)out.clone();
                outset.andNot(defset);
                useset.or(outset);
                in.or(useset);

                // Fixed Point check
                if (!in.equals(inprime) || !out.equals(outprime)) {
                    dups++;
                    fixed = false;
                }
            }
        }
    }

    public BitSet getInSet(Vertex v) {
        return m_insets[v.getID()];
    }

    public BitSet getOutSet(Vertex v) {
        return m_outsets[v.getID()];
    }

    private BitSet[] m_insets,m_outsets;
}