[LLVMdev] Critical edges

[Fernando Magno Quintao Pereira]

> If you don't want critical edges in the machine code CFG, you're going to
> have to write a machine code CFG critical edge splitting pass: LLVM
> doesn't currently have one.
>
> -Chris

Hey guys,

    I've coded a pass to break the critical edges of the machine
control flow graph. The program works fine, but I am sure it is not
the right way of implementing it. There are two problems:

error for sure: I am not inserting a branch instruction at the
end of the newly created block, nor updating the branch in the
end of the old source block. How do I do this?

error almost for sure: I cannot create a new BasicBlock and
add it to the function, because it is a MachineFunctionPass. But it
seems to work in the way that I am doing: I get the basic block of
the origin of the critical edge, and use it to create the new
MachineBasicBlock. I know this seems wrong, but how to get around this?
But, before running my pass, I am using LLVM function pass to break
critical edges; thus, I only have to deal with critical edges inserted
during the instruction selection phase, and both, origin and destiny of
these critical edges contain the same BasicBlock.

The code is small. Could someone read it, and tell me if it is likely
to generate incorrect code (besides the problem of not inserting
branch instructions)?

Thanks a lot,

Fernando

Code ---------------------------------------------------------------

void CriticalEdgeRemoval_Fer::getAnalysisUsage
(AnalysisUsage & AU) const {
    AU.addPreserved<ETForest>();
    AU.addPreserved<DominatorSet>();
    AU.addPreserved<ImmediateDominators>();
    AU.addPreserved<DominatorTree>();
    AU.addPreserved<DominanceFrontier>();
    AU.addPreserved<LoopInfo>();
    AU.addPreservedID(LoopSimplifyID);
}


bool CriticalEdgeRemoval_Fer::runOnMachineFunction
(MachineFunction & mf) {
    std::vector<MachineBasicBlock *> src_blocks;
    std::vector<MachineBasicBlock *> dst_blocks;

    // first, only find the critical edges:
    for(unsigned u = 0; u < mf.size(); u++) {
        MachineBasicBlock * mbb = mf.getBlockNumbered(u);
        for(MachineBasicBlock::succ_iterator succ = mbb->succ_begin();
                                      succ != mbb->succ_end(); succ++) {
            MachineBasicBlock * mbb_succ = *succ;
            if(is_critical_edge(*mbb, *mbb_succ)) {
                src_blocks.push_back(mbb);
                dst_blocks.push_back(mbb_succ);
            }
        }
    }

    // second, break the critical edges:
    for(unsigned u = 0; u < src_blocks.size() > 0; u++) {
        MachineBasicBlock * src = src_blocks[u];
        MachineBasicBlock * dst = dst_blocks[u];
        split_critical_edge(*src, *dst, mf);
    }
    return src_blocks.size() > 0;
}


bool CriticalEdgeRemoval_Fer::is_critical_edge
(const MachineBasicBlock & src, const MachineBasicBlock & dst) {

    unsigned num_succ = 0;
    unsigned num_pred = 0;
    bool src_has_many_succ = false;
    bool dst_has_many_pred = false;

    for(MachineBasicBlock::const_succ_iterator succ = src.succ_begin();
                                      succ != src.succ_end(); succ++)  {
        num_succ++;
        if(num_succ > 1) {
            src_has_many_succ = true;
            break;
        }
    }
    for(MachineBasicBlock::const_pred_iterator pred = dst.pred_begin();
                                      pred != dst.pred_end(); pred++)  {
        num_pred++;
        if(num_pred > 1) {
            dst_has_many_pred = true;
            break;
        }
    }
    return src_has_many_succ && dst_has_many_pred;
}


void CriticalEdgeRemoval_Fer::split_critical_edge
(MachineBasicBlock & src, MachineBasicBlock & dst, MachineFunction & mf) {

    const BasicBlock * src_bb = src.getBasicBlock();
    const BasicBlock * dst_bb = dst.getBasicBlock();

    MachineBasicBlock * crit_mbb = new MachineBasicBlock(src_bb);

    src.addSuccessor(crit_mbb);
    crit_mbb->addSuccessor(& dst);
    src.removeSuccessor(& dst);

    ilist<MachineBasicBlock>::iterator mbb_it = mf.getLastBlock();
    ++mbb_it;
    mf.getBasicBlockList().insert(mbb_it, crit_mbb);

}