package org.simantics.scl.compiler.internal.codegen.analysis;

public abstract class Dominance {

    int[] idom;
    
    public Dominance(int size) {
        idom = new int[size];
        idom[0] = 0;
        for(int i=1;i<size;++i)
            idom[i] = -1;
    }
    
    public void compute() {
        boolean changed;
        do {
            changed = true;
            for(int i=1;i<idom.length;++i) {
                int curDom = -1;
                for(int pred : predecessors(i)) {
                    int dom = idom[pred];
                    if(dom >= 0) {
                        if(curDom < 0)
                            curDom = dom;
                        else
                            curDom = intersect(dom, curDom);
                    }
                }
                if(idom[i] != curDom) {
                    idom[i] = curDom;
                    changed = true;
                }
            }
        } while(changed);
    }
    
    private int intersect(int a, int b) {
        while(a != b) {
            if(a < b)
                b = idom[b];
            else
                a = idom[a];
        }
        return a;
    }

    protected abstract int[] predecessors(int i);
    
}