[LLVMdev] MBB Critical edges

[Fernando Magno Quintao Pereira]

Hi,

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.

best,

Fernando

> Can you explain briefly what it does? What benefits do you expect?

>> At least I think I've solved it. I had to add one method to
>> TargetInstrInfo to tell me when an instruction is an indirect jump -
>> TargetInstrInfo::tii.isIndirectJump(opcode). When that is the case, I
>> update the jump table using:
>>
>>      // Change jumps to go to the new basic block:
>>      if(isJumpTable) {
>>          mf.getJumpTableInfo()->ReplaceMBBInJumpTables(& dst,
>> crit_mbb);
>>      }
>>
>> where dst was the old basic block, and crit_mbb is the new one,
>> created to
>> remove a critical edge. I think this should solve the problem. If you
>> want, I can give you the pass to break critical edges of machine
>> blocks,
>> so that you guys can see if it is worth adding to LLVM's main
>> branch. Up
>> to now, as far as I know, there is no pass to remove critical edges of
>> machine functions in LLVM.
-------------- next part --------------
//===----------- CriticalEdgeRemoval_Fer - Break critical edges ----------===//
//
//                     The LLVM Compiler Infrastructure
//
// This files was originally developed by the LLVM research group. Fernando
// at cs dot ucla dot edu has changed the file a little, so it could be used as
// a pre-register allocation pass.
//
//===---------------------------------------------------------------------===//
//
// CriticalEdgeRemoval pass - Break all of the critical edges in the CFG by
// inserting a dummy basic block.  This pass may be "required" by passes that
// cannot deal with critical edges. Notice that this pass invalidates the
// CFG, because the same BasicBlock is used as parameter for the src
// MachineBasicBlock and the new dummy MachineBasicBlock.
//
//===---------------------------------------------------------------------===//

#include <iostream>                                      // cerr

#include "llvm/Transforms/Scalar.h"
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
#include "llvm/Target/TargetData.h"
#include "llvm/CodeGen/MachineJumpTableInfo.h"
#include "llvm/Analysis/Dominators.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Function.h"
#include "llvm/Instructions.h"
#include "llvm/Type.h"
#include "llvm/Support/CFG.h"
#include "llvm/CodeGen/MachineFunctionPass.h"            // MachineBasicBlock
#include "llvm/Target/MRegisterInfo.h"
#include "llvm/Target/TargetInstrInfo.h"
#include "llvm/Target/TargetMachine.h"

#include "llvm/fernando/NeatPrint_Fer.h"
#include "llvm/fernando/CriticalEdgeRemoval_Fer.h"       // class definition

using namespace llvm;

namespace {
    RegisterPass<CriticalEdgeRemoval_Fer>
    X("rm_crit", "Critical Edge Removal - Fernando", true);
}


//===---------------------------------------------------------------------===//
// I am not sure that this pass conserves all these properties, but I am
// assuming that critical edges between BasicBlocks have already been broken
// before. So, I only have to break critical edges between basic blocks
// split due to some optimizations. If the underline BasicBlock is the same
// for both source and target of the critical edge, this pass will not
// invalidate the other passes.
//===---------------------------------------------------------------------===//
void CriticalEdgeRemoval_Fer::getAnalysisUsage(AnalysisUsage & AU) const {
    AU.setPreservesAll();
}


//===---------------------------------------------------------------------===//
// This method split all the critical edges in the machine function control
// flow graph.
//===---------------------------------------------------------------------===//
bool CriticalEdgeRemoval_Fer::runOnMachineFunction(MachineFunction & mf) {

    std::vector<MachineBasicBlock *> src_blocks;
    std::vector<MachineBasicBlock *> dst_blocks;

    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;
            // necessary and sufficient condition that characterizes a critical
            // edge: predecessor with many successors, successor with many
            // predecessors.
            if( (mbb->succ_size() > 1) && (mbb_succ->pred_size() > 1) ) {
                src_blocks.push_back(mbb);
                dst_blocks.push_back(mbb_succ);
            }
        }
    }

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


//===---------------------------------------------------------------------===//
// This method breaks the critical edge that links src to dst. It will insert
// a dummy block in between these two machine blocks. Originally, I though
// about reporting an error if the source and destiny basic block do not share
// the same underling BasicBlock. Later on, it turned out that this restriction
// was too much for the client methods, and I decided to remove it. The source
// code still has the old assertion comented. One way that the client could
// use to ensure the absence of critical edges was to call
// call PM.add(createBreakCriticalEdgesPass()); in the target machine. But
// this seems not to be enough. I've discovered this error when compiling the
// Ackermann function.
//===---------------------------------------------------------------------===//
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);

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

    /// insert the new block into the machine function.
    mf.getBasicBlockList().insert(mf.end(), 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();
    bool found_branch = false;
    bool isJumpTable = false;
    while (mii != src.begin()) {
        mii--;
        // if there are no more branches, finish the loop
        if (!tii->isTerminatorInstr(mii->getOpcode())) {
            break;
        } else if (tii->isIndirectJump(mii->getOpcode())) {
            isJumpTable = true;
            continue;
        }
        // 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;
                mo.setMachineBasicBlock(crit_mbb);
            }
        }
    }

    // Change jumps to go to the new basic block:
    if(isJumpTable) {
        mf.getJumpTableInfo()->ReplaceMBBInJumpTables(& dst, crit_mbb);
    }

    // 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.
    if(!found_branch) {
        tii->insertGoto(src, *crit_mbb);
    }

    /// Change all the phi functions in dst, so that the incoming block be
    /// crit_mbb, instead of src
    for(mii = dst.begin(); mii != dst.end(); mii++) {
        /// the first instructions are always phi functions.
        if(mii->getOpcode() != TargetInstrInfo::PHI) {
            break;
        }
        for (unsigned u = 0; u != mii->getNumOperands(); ++u) {
            if (mii->getOperand(u).isMachineBasicBlock() &&
                      mii->getOperand(u).getMachineBasicBlock() == & src) {
                mii->getOperand(u).setMachineBasicBlock(crit_mbb);
            }
        }
    }
}