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