include/llvm/CodeGen/BreakCriticalMachineEdge.h

   1 //===--------- BreakCriticalMachineEdges.h - Break critical edges ---------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===---------------------------------------------------------------------===//
   9 //
  10 // Helper function to break a critical machine edge.
  11 //
  12 //===---------------------------------------------------------------------===//
  13
  14 #ifndef LLVM_CODEGEN_ASMPRINTER_H
  15 #define LLVM_CODEGEN_ASMPRINTER_H
  16
  17 #include "llvm/CodeGen/MachineJumpTableInfo.h"
  18 #include "llvm/Target/TargetInstrInfo.h"
  19 #include "llvm/Target/TargetMachine.h"
  20
  21 namespace llvm {
  22
  23 MachineBasicBlock* SplitCriticalMachineEdge(MachineBasicBlock* src,
  24                                             MachineBasicBlock* dst) {
  25   const BasicBlock* srcBB = src->getBasicBlock();
  26
  27   MachineBasicBlock* crit_mbb = new MachineBasicBlock(srcBB);
  28
  29   // modify the llvm control flow graph
  30   src->removeSuccessor(dst);
  31   src->addSuccessor(crit_mbb);
  32   crit_mbb->addSuccessor(dst);
  33
  34   // insert the new block into the machine function.
  35   src->getParent()->getBasicBlockList().insert(src->getParent()->end(),
  36                                                  crit_mbb);
  37
  38   // insert a unconditional branch linking the new block to dst
  39   const TargetMachine& TM = src->getParent()->getTarget();
  40   const TargetInstrInfo* TII = TM.getInstrInfo();
  41   std::vector<MachineOperand> emptyConditions;
  42   TII->InsertBranch(*crit_mbb, dst, (MachineBasicBlock*)0,
  43                     emptyConditions);
  44
  45   // modify every branch in src that points to dst to point to the new
  46   // machine basic block instead:
  47   MachineBasicBlock::iterator mii = src->end();
  48   bool found_branch = false;
  49   while (mii != src->begin()) {
  50     mii--;
  51     // if there are no more branches, finish the loop
  52     if (!mii->getDesc().isTerminator()) {
  53       break;
  54     }
  55
  56     // Scan the operands of this branch, replacing any uses of dst with
  57     // crit_mbb.
  58     for (unsigned i = 0, e = mii->getNumOperands(); i != e; ++i) {
  59       MachineOperand & mo = mii->getOperand(i);
  60       if (mo.isMachineBasicBlock() &&
  61           mo.getMBB() == dst) {
  62         found_branch = true;
  63         mo.setMBB(crit_mbb);
  64       }
  65     }
  66   }
  67
  68   // TODO: This is tentative. It may be necessary to fix this code. Maybe
  69   // I am inserting too many gotos, but I am trusting that the asm printer
  70   // will optimize the unnecessary gotos.
  71   if(!found_branch) {
  72     TII->InsertBranch(*src, crit_mbb, (MachineBasicBlock*)0,
  73                       emptyConditions);
  74   }
  75
  76   /// Change all the phi functions in dst, so that the incoming block be
  77   /// crit_mbb, instead of src
  78   for(mii = dst->begin(); mii != dst->end(); mii++) {
  79     /// the first instructions are always phi functions.
  80     if(mii->getOpcode() != TargetInstrInfo::PHI)
  81       break;
  82
  83     // Find the operands corresponding to the source block
  84     std::vector<unsigned> toRemove;
  85     unsigned reg = 0;
  86     for (unsigned u = 0; u != mii->getNumOperands(); ++u)
  87       if (mii->getOperand(u).isMachineBasicBlock() &&
  88           mii->getOperand(u).getMBB() == src) {
  89         reg = mii->getOperand(u-1).getReg();
  90         toRemove.push_back(u-1);
  91       }
  92     // Remove all uses of this MBB
  93     for (std::vector<unsigned>::reverse_iterator I = toRemove.rbegin(),
  94          E = toRemove.rend(); I != E; ++I) {
  95       mii->RemoveOperand(*I+1);
  96       mii->RemoveOperand(*I);
  97     }
  98
  99     // Add a single use corresponding to the new MBB
 100     mii->addOperand(MachineOperand::CreateReg(reg, false));
 101     mii->addOperand(MachineOperand::CreateMBB(crit_mbb));
 102   }
 103
 104   return crit_mbb;
 105 }
 106
 107 }
 108
 109 #endif