lib/CodeGen/BreakCriticalMachineEdges.cpp

   1 //===----------- BreakCriticalMachineEdges - Break critical edges ---------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file was developed by Fernando Pereira and is distributed under
   6 // the University of Illinois Open Source License. See LICENSE.TXT for details.
   7 //
   8 //===---------------------------------------------------------------------===//
   9 //
  10 // Break all of the critical edges in the CFG by inserting a dummy basic block.
  11 // This pass may be "required" by passes that cannot deal with critical edges.
  12 // Notice that this pass invalidates the CFG, because the same BasicBlock is
  13 // used as parameter for the src MachineBasicBlock and the new dummy
  14 // MachineBasicBlock.
  15 //
  16 //===---------------------------------------------------------------------===//
  17
  18 #include "llvm/CodeGen/Passes.h"
  19 #include "llvm/CodeGen/MachineFunctionPass.h"
  20 #include "llvm/CodeGen/MachineInstr.h"
  21 #include "llvm/CodeGen/MachineJumpTableInfo.h"
  22 #include "llvm/Target/TargetInstrInfo.h"
  23 #include "llvm/Target/TargetMachine.h"
  24 #include "llvm/ADT/Statistic.h"
  25 #include "llvm/Support/Compiler.h"
  26
  27 using namespace llvm;
  28
  29 namespace {
  30   struct VISIBILITY_HIDDEN BreakCriticalMachineEdges :
  31                            public MachineFunctionPass {
  32     static char ID; // Pass identification
  33     BreakCriticalMachineEdges() : MachineFunctionPass((intptr_t)&ID) {}
  34
  35     bool runOnMachineFunction(MachineFunction& Fn);
  36     void splitCriticalEdge(MachineBasicBlock* A, MachineBasicBlock* B);
  37   };
  38
  39   char BreakCriticalMachineEdges::ID = 0;
  40   RegisterPass<BreakCriticalMachineEdges> X("critical-machine-edges",
  41                                             "Break critical machine code edges");
  42 }
  43
  44 //const PassInfo *llvm::BreakCriticalMachineEdgesID = X.getPassInfo();
  45
  46 void BreakCriticalMachineEdges::splitCriticalEdge(MachineBasicBlock* src,
  47                                                   MachineBasicBlock* dst) {
  48   const BasicBlock* srcBB = src->getBasicBlock();
  49
  50   MachineBasicBlock* crit_mbb = new MachineBasicBlock(srcBB);
  51
  52   // modify the llvm control flow graph
  53   src->removeSuccessor(dst);
  54   src->addSuccessor(crit_mbb);
  55   crit_mbb->addSuccessor(dst);
  56
  57   // insert the new block into the machine function.
  58   src->getParent()->getBasicBlockList().insert(src->getParent()->end(),
  59                                                crit_mbb);
  60
  61   // insert a unconditional branch linking the new block to dst
  62   const TargetMachine& TM = src->getParent()->getTarget();
  63   const TargetInstrInfo* TII = TM.getInstrInfo();
  64   std::vector<MachineOperand> emptyConditions;
  65   TII->InsertBranch(*crit_mbb, dst, (MachineBasicBlock*)0, emptyConditions);
  66
  67   // modify every branch in src that points to dst to point to the new
  68   // machine basic block instead:
  69   MachineBasicBlock::iterator mii = src->end();
  70   bool found_branch = false;
  71   while (mii != src->begin()) {
  72     mii--;
  73     // if there are no more branches, finish the loop
  74     if (!TII->isTerminatorInstr(mii->getOpcode())) {
  75       break;
  76     }
  77
  78     // Scan the operands of this branch, replacing any uses of dst with
  79     // crit_mbb.
  80     for (unsigned i = 0, e = mii->getNumOperands(); i != e; ++i) {
  81       MachineOperand & mo = mii->getOperand(i);
  82       if (mo.isMachineBasicBlock() &&
  83           mo.getMachineBasicBlock() == dst) {
  84         found_branch = true;
  85         mo.setMachineBasicBlock(crit_mbb);
  86       }
  87     }
  88   }
  89
  90   // TODO: This is tentative. It may be necessary to fix this code. Maybe
  91   // I am inserting too many gotos, but I am trusting that the asm printer
  92   // will optimize the unnecessary gotos.
  93   if(!found_branch) {
  94     TII->InsertBranch(*src, crit_mbb, (MachineBasicBlock*)0, emptyConditions);
  95   }
  96
  97   /// Change all the phi functions in dst, so that the incoming block be
  98   /// crit_mbb, instead of src
  99   for(mii = dst->begin(); mii != dst->end(); mii++) {
 100     /// the first instructions are always phi functions.
 101     if(mii->getOpcode() != TargetInstrInfo::PHI)
 102       break;
 103
 104     for (unsigned u = 0; u != mii->getNumOperands(); ++u)
 105       if (mii->getOperand(u).isMachineBasicBlock() &&
 106           mii->getOperand(u).getMachineBasicBlock() == src)
 107         mii->getOperand(u).setMachineBasicBlock(crit_mbb);
 108   }
 109 }
 110
 111 bool BreakCriticalMachineEdges::runOnMachineFunction(MachineFunction& F) {
 112   std::vector<MachineBasicBlock *> SourceBlocks;
 113   std::vector<MachineBasicBlock *> DestBlocks;
 114
 115   for(MachineFunction::iterator FI = F.begin(), FE = F.end(); FI != FE; ++FI) {
 116     for(MachineBasicBlock::succ_iterator SI = FI->succ_begin(),
 117         SE = FI->succ_end(); SI != SE; ++SI) {
 118       // predecessor with multiple successors, successor with multiple
 119       // predecessors.
 120       if (FI->succ_size() > 1 && (*SI)->pred_size() > 1) {
 121         SourceBlocks.push_back(FI);
 122         DestBlocks.push_back(*SI);
 123       }
 124     }
 125   }
 126
 127   for(unsigned u = 0; u < SourceBlocks.size() > 0; u++)
 128     splitCriticalEdge(SourceBlocks[u], DestBlocks[u]);
 129
 130   return false;
 131 }