llvm dev - Jul 2006 - [LLVMdev] Critical edges

On Tue, 4 Jul 2006, Fernando Magno Quintao Pereira
wrote:
> However, it does not remove all the critical edges. I am getting a very
> weird dataflow graph (even without the Break Critical edges pass). The
> dataflow generated by MachineFunction::dump() for the program below is
> given here:
> http://compilers.cs.ucla.edu/fernando/projects/soc/images/loop_no_crit2.pdf
...
> The problem is the no_exit block. I think it was changed by one of the
> optimization passes, and was split into three basic blocks. But now there
> is a phi function where both the parameters are defined in the same basic
> block. Any of you guys now which pass I should cut off if I want to avoid
> this optimization?
This is due to instruction selection.  The llvm code turns your testcase 
into something like this:

   X += cond ? 1 : -1;

This is a 'select' instruction in LLVM.

Generic PowerPC chips doesn't support integer select instructions, so it 
must be lowered to a conditional branch.  This lowering is what you're 
seeing, there is no way to disable it.

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

-- 
http://nondot.org/sabre/
http://llvm.org/

> 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);

}

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);
            }
        }
    }

}