[LLVMdev] Critical edges

Fernando Magno Quintao Pereira fernando at CS.UCLA.EDU
Sat Jul 8 21:54:31 PDT 2006


Dear guys,

    I am having problem to split edges correctly. Mostly because the new
basic blocks are creating infinite loops. Could someone help me fixing the
code below? It is creating assembly like this one below. Block LBB1_9 was
inserted to break the critical edge between blocks LBB1_3 and LBB1_8. But
it changes the semantics of the original program, because, before, LBB1_8
was falling through LBB1_4, and now it is falling on LBB1_9.

LBB1_3: ;no_exit
        lis r4, 21845
        ori r4, r4, 21846
        mulhw r4, r2, r4
        addi r5, r2, -1
        li r6, -1
        srwi r6, r4, 31
        add r4, r4, r6
        mulli r4, r4, 3
        li r6, 1
        subf r2, r4, r2
        cmpwi cr0, r2, 0
        beq cr0, LBB1_9 ;no_exit
LBB1_7: ;no_exit
        mr r2, r6
LBB1_8: ;no_exit
        cmpwi cr0, r5, 0
        add r2, r2, r3
        bgt cr0, LBB1_5 ;no_exit.no_exit_llvm_crit_edge
LBB1_9: ;no_exit
        mr r2, r6
        b LBB1_8        ;no_exit
LBB1_4: ;no_exit.loopexit_llvm_crit_edge

The code is this one below:

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

    const BasicBlock * src_bb = src.getBasicBlock();
    MachineBasicBlock * crit_mbb = new MachineBasicBlock(src_bb);

    /// modify the llvm control flow graph
    src.addSuccessor(crit_mbb);
    crit_mbb->addSuccessor(& dst);
    src.removeSuccessor(& dst);

    /// insert the new block into the machine function.
    ilist<MachineBasicBlock>::iterator mbb_it = mf.getLastBlock();
    ++mbb_it;
    mf.getBasicBlockList().insert(mbb_it, crit_mbb);

    /// insert a unconditional branch linking the new block to dst
    const TargetMachine & tm = mf.getTarget();
    const TargetInstrInfo * tii = tm.getInstrInfo();
    tii->insertGoto(*crit_mbb, dst);

    /// modify every branch in src that points to dst to point to the new
    /// machine basic block instead:
    MachineBasicBlock::iterator mii = src.end();
    while (mii != src.begin()) {
        mii--;
        // if there is not more branches, finish the loop
        if (!tii->isTerminatorInstr(mii->getOpcode())) {
            break;
        }
        // Scan the operands of this machine instruction, replacing any
        // use of dst with crit_mbb.
        for (unsigned i = 0, e = mii->getNumOperands(); i != e; ++i) {
            if (mii->getOperand(i).isMachineBasicBlock() &&
                   mii->getOperand(i).getMachineBasicBlock() == & dst) {
                mii->getOperand(i).setMachineBasicBlock(crit_mbb);
            }
        }
    }

}



More information about the llvm-dev mailing list