MBB Critical edges


This pass is similar to the one in BreakCriticalEdges.cpp, but it works for MachineFunction's, instead of Functions. The existence of critical edges complicates many optimizations. When doing register allocation, you don't necessarily have to remove critical edges (you can use conventional SSA-form, for instance. See "Translating Out of Static Single Assignment Form. SAS 1999"), yet, to remove them should be easy.

I can send a patch if you think the code is ok. I am sending you the code.



CriticalEdgeRemoval_Fer.cpp (7.39 KB)

Sorry I have completely dropped the ball on this. Some comments:

  1. Please try using SmallVector instead of std::vector. It may be offer some compile time benefit unless the vector grows too large.
  2. Please try to make coding style of existing code. For example, need a space between for and ‘(’, also if and ‘(’. Also please set indentation level to 2.
  3. Please don’t include iostream. Use llvm/Support/Streams.h and DOUT instead.
  4. Please don’t include Dominators.h if it’s not used. Also MRegisterInfo.h
  5. mf.getBasicBlockList().insert(mf.end(), crit_mbb);
    Just a nit pick, please use push_back(crit_mbb).
  6. This chunk of code:

/// modify every branch in src that points to dst to point to the new
/// machine basic block instead:
MachineBasicBlock::iterator mii = src.end();
bool found_branch = false;
bool isJumpTable = false;
while (mii != src.begin()) {
// if there are no more branches, finish the loop
if (!tii->isTerminatorInstr(mii->getOpcode())) {
} else if (tii->isIndirectJump(mii->getOpcode())) {
isJumpTable = true;
// Scan the operands of this branch, replacing any uses of dst with
// crit_mbb.
for (unsigned i = 0, e = mii->getNumOperands(); i != e; ++i) {
MachineOperand & mo = mii->getOperand(i);
if (mo.isMachineBasicBlock() &&
mo.getMachineBasicBlock() == & dst) {
found_branch = true;

This is almost identical to ReplaceUsesOfBlockWith(). It’s probably better to update ReplaceUsesOfBlockWith() to include the jumptable updating code and use that instead. Also note it also updates successor list.

// TODO: This is tentative. It may be necessary to fix this code. Maybe
// I am inserting too many gotos, but I am trusting that the asm printer
// will optimize the unnecessary gotos.
Asm printer won’t optimize them away but branch folding pass might. :slight_smile:

  1. I am not sure if any existing pass will benefit from this. But it may be handy. But does it need to be a pass? Can it be a member function of MachineFunction?