Kilim源码分析之三 ---- 织入之构造/合并BasicBlock

        上一篇分析了可织入判断的代码，本篇继续分析织入部分的构造/合并BasicBlock。

        首先看下分析方法kilim.analysis.MethodFlow.analyze()包含的功能：

    //织入逻辑 
    public void analyze() throws KilimException {
        buildBasicBlocks();//构造BasicBlock，异常代码怎么构建成块的？
        if (basicBlocks.size() == 0) return;
        consolidateBasicBlocks();//这里会合并一些在逻辑上不需要独立开来的块
        assignCatchHandlers();//把tryCatchBlocks块构造成Handler，然后根据handler的块的起始位置和块的起始位置，给块分配handler，即tryCatch块会catch这个bb的某个类型的异常；tryCatchBlock开始pos会跟代码bb的开始位置重合，会在bb的start和end pos之间么？consolidate合并块导致？
        inlineSubroutines();//这里只是把小于1.5编译级别所产生的jsr指令做了处理；finally块中有pausable则会被拷贝一份；finally块中有pausable则会把jsr/ret指令都替换为goto指令，但是并没有像1.5及以后编译级别那样，拷贝一份代码try/catch代码块编译后的指令块中
        doLiveVarAnalysis();//变量活动性分析
        dataFlow();//数据流分析
        this.labelToBBMap = null; // we don't need this mapping anymore
    }

         来看buildBasicBlock方法及调用的相关方法的实现逻辑：

    //构造BasicBlock
    void buildBasicBlocks() {
        // preparatory phase
        int numInstructions = instructions.size(); 
        basicBlocks = new BBList();//Basic Block 列表
        // Note: i modified within the loop
        for (int i = 0; i < numInstructions; i++) {
            Label l = getOrCreateLabelAtPos(i);//在当前指令位置创建一个Label，这里i并不是连续的，即并非每个位置都会创建一条指令
            BasicBlock bb = getOrCreateBasicBlock(l);//为每个Label创建一个BasicBlock
            i = bb.initialize(i); // i now points to the last instruction in bb.在bb.initialize(i)里，i会增加的 
            basicBlocks.add(bb);//放到bb列表
        }
    }


    Label getOrCreateLabelAtPos(int pos) {
        Label ret = null;
        if (pos < posToLabelMap.size()) {
            ret = posToLabelMap.get(pos);//这是一个List，不是一个Map的
        }
        if (ret == null) {
            ret = new Label();
            setLabel(pos, ret);//为位置pos创建一个Label
        }
        return ret;
    }
    void setLabel(int pos, Label l) {
        //在posToLabelMap后边添加pos - posToLabelMap.size() + 1个null，还是为了做到每条指令都对应一个位置，存储值为null或Label
        for (int i = pos - posToLabelMap.size() + 1; i >= 0; i--) {
            //pad with nulls ala perl
            posToLabelMap.add(null);
        }
        assert posToLabelMap.get(pos) == null;
        posToLabelMap.set(pos, l);//把pos位置上放一个Label
        labelToPosMap.put(l, pos);//Label和位置的映射关系
    }

         下边着重分析下BasicBlock的initialize，分析前先介绍两个概念，BasicBlock是一个指令集合，这些指令集合也叫做一个节点，是必须按照顺序执行的一堆指令，中间不存在跳转。如果按照顺序执行指令，执行当前节点的最后一条指令，与接下来要执行的下一个节点的第一条指令之间是物理相邻的，那么下一个节点就是当前节点的follower。从一个块可以通过跳转或者非跳转指令直接到达的节点，叫做当前节点的后继节点successor，当前节点也叫做后继结点的前驱节点predecessor。

   /**
     * Absorb as many instructions until the next label or the next transfer of
     * control instruction. In the first pass we may end up creating many many
     * BBs because there may be a lot of non-target labels (esp. when debug
     * information is available). The constraints are as follows:   
     * 读取尽量多的指令，直到下一个目标指令或者下一个跳转指令。第一pass，我们创建尽可能多的bbs，因为这里有很多非目标label（比如调试信息）
     *   1. A transfer of control instruction must be the last instruction. It 
     *      may also be the first (and only) instruction. 控制流的跳转指令必须是BasicBlock的最后一条指令
     *   2. A labeled instruction must be the first instruction in a BB. It
     *      may optionally be the last (and only) instruction. 目标指令必须是BasicBlock的第一条指令
     *   3. A pausable method is treated like a labeled instruction, and is 
     *      given a label if there isn't one already. Constraint 2 applies. Pausable方法被当目标指令
     */
    @SuppressWarnings("unchecked")
    int initialize(int pos) {
        AbstractInsnNode ain;
        startPos = pos;
        BasicBlock bb;
        boolean endOfBB = false;
        boolean hasFollower = true;//是否有后继节点
        int size = flow.instructions.size();
        for (; pos < size; pos++) {//从当前位置开始，一条一条指令走起
            if (pos > startPos && flow.getLabelAt(pos) != null) {//如果某条指令已经有对应的Label了
                pos--;//回退一位
                hasFollower = true;//有后继节点
                endOfBB = true;//BasicBlock的末尾
                break;
            }
            ain = getInstruction(pos);//当前位置的指令
            int opcode = ain.getOpcode();//指令操作码
            switch (opcode) {
                case ALOAD:
                case ILOAD:
                case LLOAD:
                case FLOAD:
                case DLOAD:
                    usage.read(((VarInsnNode) ain).var);//load类型指令，把局部变量索引标记为读
                    break;
                case ISTORE:
                case LSTORE:
                case FSTORE:
                case DSTORE:
                case ASTORE:
                    usage.write(((VarInsnNode) ain).var);//store类型指令，把对应局部变量索引标记为写
                    break;
                    
                case IINC:
                    int v = ((IincInsnNode)ain).var;
                    usage.read(v);
                    usage.write(v);//iinc 既读又写
                    break;
                case IFEQ:
                case IFNE:
                case IFLT:
                case IFGE:
                case IFGT:
                case IFLE:
                case IFNULL:
                case IFNONNULL:
                case IF_ICMPEQ:
                case IF_ICMPNE:
                case IF_ICMPLT:
                case IF_ICMPGE:
                case IF_ICMPGT:
                case IF_ICMPLE:
                case IF_ACMPEQ:
                case IF_ACMPNE:
                case JSR:
                case GOTO://if类、jsr、goto类型指令
                    Label l = ((JumpInsnNode) ain).label;//这些指令的目标地址上都创建了label
                    bb = flow.getOrCreateBasicBlock(l);//跳转指令目标地址上创建一个Label
                    if (opcode == JSR) {//jsr指令，标示为IS_SUBROUTINE
                        bb.setFlag(IS_SUBROUTINE);
                        hasFollower = false;//以jsr指令结束的bb没有follower节点
                    }
                    addSuccessor(bb);//给当前BasicBlock添加后继节点，后继节点的前驱节点数也会加1
                    if (opcode == GOTO) {//以goto指令结束的bb没有follower节点
                        hasFollower = false;
                    }
                    endOfBB = true;//bb结束
                    break;
                case RET://finally块的返回指令
                case IRETURN:
                case LRETURN:
                case FRETURN:
                case DRETURN:
                case ARETURN:
                case RETURN:
                case ATHROW://以return、throw类型指令和抛异常指令结束的bb没有follower，没有successor
                    hasFollower = false;
                    endOfBB = true;//bb结束
                    break;
                case TABLESWITCH:
                case LOOKUPSWITCH://switch指令
                    Label defaultLabel;//default跳转的目标位置的label
                    List<Label> otherLabels;//非default跳转的labels
                    if (opcode == TABLESWITCH) {
                        defaultLabel = ((TableSwitchInsnNode) ain).dflt;
                        otherLabels = ((TableSwitchInsnNode) ain).labels;
                    } else {
                        defaultLabel = ((LookupSwitchInsnNode) ain).dflt;
                        otherLabels = ((LookupSwitchInsnNode) ain).labels;
                    }
                    //switch指令的默认和非默认跳转目标地址开始的Label都作为当前bb的后继节点
                    for (Iterator<Label> it = otherLabels.iterator(); it.hasNext();) {
                        l = (Label) it.next();
                        addSuccessor(flow.getOrCreateBasicBlock(l));
                    }
                    addSuccessor(flow.getOrCreateBasicBlock(defaultLabel));
                    endOfBB = true;
                    hasFollower = false;
                    break;
                case INVOKEVIRTUAL:
                case INVOKESTATIC:
                case INVOKEINTERFACE:
                case INVOKESPECIAL://方法调用指令
                    if (flow.isPausableMethodInsn((MethodInsnNode) ain)) {//调用的Pausable的方法
                        if (pos == startPos) {//当前块的第一条指令，那么当前块就是一个pausable块
                            setFlag(PAUSABLE);
                        } else {//否则，当前块结束，为pausable方法指令创建新块和bb
                            l = flow.getOrCreateLabelAtPos(pos);
                            bb = flow.getOrCreateBasicBlock(l);
                            bb.setFlag(PAUSABLE);
                            addSuccessor(bb);//当前bb的后继节点
                            pos--; // don't consume this instruction
                            hasFollower = true;//有follower
                            endOfBB = true;//块结束
                        }
                    }
                    break;
                default:
                if (opcode >= 26 && opcode <= 45)
                    throw new IllegalStateException("instruction variants not expected here");
                
                    break;
            }
            if (endOfBB) break;
        }
        endPos = pos;
        //添加follower，当前bb最后一条指令的下一条指令是follower的第一条指令
        if (hasFollower && (pos + 1) < flow.instructions.size()) {
            // add the following basic block as a successor
            Label l = flow.getOrCreateLabelAtPos(pos + 1);
            bb = flow.getOrCreateBasicBlock(l);
            addFollower(bb);//follower也是一个后继节点的
        }
        return pos;
    }

         整理下以上代码，以jsr、goto、return、throw、switch这些类型指令结束的BasicBlock是没有follower的；以if或者pausable方法的方法调用指令结束的BasicBloc是有follower的，以if、jsr、goto、return、throw、switch、pausable方法的方法调用指令的上一条指令结束的bb是会有后继结点。

    asm框架分析出来的其他Label：（都包括啥？）

   /**
     * In the first pass (buildBasicBlocks()), we create BBs whenever we
     * encounter a label. We don't really know until we are done with that
     * pass whether a label is the target of a branch instruction or it is
     * there because of an exception handler. See coalesceWithFollowingBlock()
     * for more detail.   合并bb
     */
    private void consolidateBasicBlocks() {
        BBList newBBs = new BBList(basicBlocks.size());
        int pos = 0;
        for (BasicBlock bb: basicBlocks) {
            if (!bb.hasFlag(COALESCED)) {
                bb.coalesceTrivialFollowers();//合并
                // The original bb's followers should have been marked as processed.
                bb.setId(pos++);  
                newBBs.add(bb);
            }
        }
        basicBlocks = newBBs;
        assert checkNoBasicBlockLeftBehind();//校验所有bb都正确构造，指令起始位置正确
    }

   
    /**
     * Blocks connected by an edge are candidates for coalescing if: <dl> <li>
     * There is a single edge between the two and neither has any other edges.
     * </li>
     * 
     * <li> The edge connecting the two is not because of a GOTO. We only want
     * those where one block falls into the other. The reason is that each block
     * marks out a *contiguous* range of instructions. Most compilers would have
     * gotten rid of this unnecessary jump anyway. </li>
     * 
     * <li> The successor block doesn't begin with a method call that we are
     * interested in (like pausable methods). This is a boundary we are
     * interested in maintaining in subsequent processing. </li>
     * 什么label隔开的bb可以合并？
     * </dl>
     */
    void coalesceTrivialFollowers() {
        while (true) {
            if (successors.size() == 1) {//当前节点的后继结点只有一个
                BasicBlock succ = successors.get(0);
                if (succ.numPredecessors == 1 && lastInstruction() != GOTO && lastInstruction() != JSR
                        && !succ.isPausable()) {//后继节点的前驱节点也只有一个，当前节点的最后一条指令不是goto/jsr，后继节点第一条指令不是pausable方法调用
                    // successor can be merged
                    // absorb succesors and usage mask
                    this.successors = succ.successors;
                    this.follower = succ.follower;
                    this.usage.absorb(succ.usage);//usage也合并
                    this.endPos = succ.endPos;
                    succ.setFlag(COALESCED);//后继节点是coalesced
                    // mark succ so it doesn't get visited. This block's merk remains 0. We'll let the outer driver
                    // loop to revisit this block and its new successors
                    continue;
                }
            }
            break;
        }
    }