Kilim源码分析之5 - 织入之变量活跃性分析

    /**
     * In live var analysis a BB asks its successor (in essence) about which
     * vars are live, mixes it with its own uses and defs and passes on a
     * new list of live vars to its predecessors. Since the information
     * bubbles up the chain, we iterate the list in reverse order, for
     * efficiency. We could order the list topologically or do a depth-first
     * spanning tree, but it seems like overkill for most bytecode
     * procedures. The order of computation doesn't affect the correctness;
     * it merely changes the number of iterations to reach a fixpoint. 
     * 变量活跃性分析，按照物理顺序，从最后一个块向前分析；把当前块及其物理后续块变量的活动性信息传递到下一个块（物理顺序前一块）进行分析。
     * 如果一个变量只在当前块中有访问，而在物理后续块中没有，则说明此变量活动范围到当前块结束。
     */
    private void doLiveVarAnalysis() {
        ArrayList<BasicBlock> bbs = getBasicBlocks();//所有bb
        Collections.sort(bbs); // sorts in increasing startPos order
        
        boolean changed;
        do {
            changed = false;
            for (int i = bbs.size() - 1; i >= 0; i--) {//从后向前分析
                changed = bbs.get(i).flowVarUsage() || changed;//一块块的分析
            }
        } while (changed);//如果changed不为false，while内部循环可能走多次，这什么算法？因为successor每次都是不一样的in可能每次在变的
    }
    
    //来看看BasicBlock.flowVarUsage的实现：
    public boolean flowVarUsage() {
        // for live var analysis, treat catch handlers as successors too.
        if (succUsage == null) {//catch handler里用到的变量也做分析
            succUsage = new ArrayList<Usage>(successors.size()
                    + handlers.size());
            for (BasicBlock succ : successors) {
                succUsage.add(succ.usage);
            }
            for (Handler h : handlers) {
                succUsage.add(h.catchBB.usage);
            }
        }
        return usage.evalLiveIn(succUsage);//把当前bb中访问到的变量跟所有后继节点&catch handler中变量使用情况进行分析
    }
 
    /**
     * This is the standard liveness calculation (Dragon Book, section 10.6). At each BB (and its
     * corresponding usage), we evaluate "in" using use and def. in = use U (out \ def) where out =
     * U succ.in, for all successors 
     * 活跃变量分析，每个bb的in变量用use和def来表示，in = use 与 (out - def)的并集, out = successor.in的并集     * 目的何在？
     */
    public boolean evalLiveIn(ArrayList<Usage> succUsage) {
        BitSet out = new BitSet(nLocals);//方法的maxLocals个bit
        BitSet old_in = (BitSet) in.clone();
        if (succUsage.size() == 0) {
            in = use;//没有后继结点，in的就是当前bb use的
        } else {
            // calculate out = U succ.in
            out = (BitSet) succUsage.get(0).in.clone();
            for (int i = 1; i < succUsage.size(); i++) {
                out.or(succUsage.get(i).in);
            }
            // calc out \ def == out & ~def == ~(out | def)
            BitSet def1 = (BitSet) def.clone();
            def1.flip(0, nLocals);
            out.and(def1);
            out.or(use);
            in = out;
        }
        return !(in.equals(old_in));//如果跟后继结点
    }