contrib/llvm/lib/Target/PowerPC/PPCMachineBasicBlockUtils.h

   1 //==-- PPCMachineBasicBlockUtils.h - Functions for common MBB operations ---==//
   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 // This file defines utility functions for commonly used operations on
  11 // MachineBasicBlock's.
  12 // NOTE: Include this file after defining DEBUG_TYPE so that the debug messages
  13 //       can be emitted for the pass that is using this.
  14 //
  15 //===----------------------------------------------------------------------===//
  16
  17 #ifndef LLVM_LIB_TARGET_PPC_MACHINE_BASIC_BLOCK_UTILS_H
  18 #define LLVM_LIB_TARGET_PPC_MACHINE_BASIC_BLOCK_UTILS_H
  19
  20 #include "PPCInstrInfo.h"
  21 #include "llvm/CodeGen/MachineInstrBuilder.h"
  22 #include "llvm/CodeGen/MachineBranchProbabilityInfo.h"
  23 #include "llvm/CodeGen/MachineRegisterInfo.h"
  24
  25 #ifndef DEBUG_TYPE
  26 #define DEBUG_TYPE "ppc-generic-mbb-utilities"
  27 #endif
  28
  29 using namespace llvm;
  30
  31 /// Given a basic block \p Successor that potentially contains PHIs, this
  32 /// function will look for any incoming values in the PHIs that are supposed to
  33 /// be coming from \p OrigMBB but whose definition is actually in \p NewMBB.
  34 /// Any such PHIs will be updated to reflect reality.
  35 static void updatePHIs(MachineBasicBlock *Successor, MachineBasicBlock *OrigMBB,
  36                        MachineBasicBlock *NewMBB, MachineRegisterInfo *MRI) {
  37   for (auto &MI : Successor->instrs()) {
  38     if (!MI.isPHI())
  39       continue;
  40     // This is a really ugly-looking loop, but it was pillaged directly from
  41     // MachineBasicBlock::transferSuccessorsAndUpdatePHIs().
  42     for (unsigned i = 2, e = MI.getNumOperands()+1; i != e; i += 2) {
  43       MachineOperand &MO = MI.getOperand(i);
  44       if (MO.getMBB() == OrigMBB) {
  45         // Check if the instruction is actualy defined in NewMBB.
  46         if (MI.getOperand(i-1).isReg()) {
  47           MachineInstr *DefMI = MRI->getVRegDef(MI.getOperand(i-1).getReg());
  48           if (DefMI->getParent() == NewMBB || !OrigMBB->isSuccessor(Successor)) {
  49             MO.setMBB(NewMBB);
  50             break;
  51           }
  52         }
  53       }
  54     }
  55   }
  56 }
  57
  58 /// Given a basic block \p Successor that potentially contains PHIs, this
  59 /// function will look for PHIs that have an incoming value from \p OrigMBB
  60 /// and will add the same incoming value from \p NewMBB.
  61 /// NOTE: This should only be used if \p NewMBB is an immediate dominator of
  62 /// \p OrigMBB.
  63 static void addIncomingValuesToPHIs(MachineBasicBlock *Successor,
  64                                     MachineBasicBlock *OrigMBB,
  65                                     MachineBasicBlock *NewMBB,
  66                                     MachineRegisterInfo *MRI) {
  67   assert(OrigMBB->isSuccessor(NewMBB) && "NewMBB must be a sucessor of OrigMBB");
  68   for (auto &MI : Successor->instrs()) {
  69     if (!MI.isPHI())
  70       continue;
  71     // This is a really ugly-looking loop, but it was pillaged directly from
  72     // MachineBasicBlock::transferSuccessorsAndUpdatePHIs().
  73     for (unsigned i = 2, e = MI.getNumOperands()+1; i != e; i += 2) {
  74       MachineOperand &MO = MI.getOperand(i);
  75       if (MO.getMBB() == OrigMBB) {
  76         MachineInstrBuilder MIB(*MI.getParent()->getParent(), &MI);
  77         MIB.addReg(MI.getOperand(i-1).getReg()).addMBB(NewMBB);
  78         break;
  79       }
  80     }
  81   }
  82 }
  83
  84 struct BlockSplitInfo {
  85   MachineInstr *OrigBranch;
  86   MachineInstr *SplitBefore;
  87   MachineInstr *SplitCond;
  88   bool InvertNewBranch;
  89   bool InvertOrigBranch;
  90   bool BranchToFallThrough;
  91   const MachineBranchProbabilityInfo *MBPI;
  92   MachineInstr *MIToDelete;
  93   MachineInstr *NewCond;
  94   bool allInstrsInSameMBB() {
  95     if (!OrigBranch || !SplitBefore || !SplitCond)
  96       return false;
  97     MachineBasicBlock *MBB = OrigBranch->getParent();
  98     if (SplitBefore->getParent() != MBB ||
  99         SplitCond->getParent() != MBB)
 100       return false;
 101     if (MIToDelete && MIToDelete->getParent() != MBB)
 102       return false;
 103     if (NewCond && NewCond->getParent() != MBB)
 104       return false;
 105     return true;
 106   }
 107 };
 108
 109 /// Splits a MachineBasicBlock to branch before \p SplitBefore. The original
 110 /// branch is \p OrigBranch. The target of the new branch can either be the same
 111 /// as the target of the original branch or the fallthrough successor of the
 112 /// original block as determined by \p BranchToFallThrough. The branch
 113 /// conditions will be inverted according to \p InvertNewBranch and
 114 /// \p InvertOrigBranch. If an instruction that previously fed the branch is to
 115 /// be deleted, it is provided in \p MIToDelete and \p NewCond will be used as
 116 /// the branch condition. The branch probabilities will be set if the
 117 /// MachineBranchProbabilityInfo isn't null.
 118 static bool splitMBB(BlockSplitInfo &BSI) {
 119   assert(BSI.allInstrsInSameMBB() &&
 120          "All instructions must be in the same block.");
 121
 122   MachineBasicBlock *ThisMBB = BSI.OrigBranch->getParent();
 123   MachineFunction *MF = ThisMBB->getParent();
 124   MachineRegisterInfo *MRI = &MF->getRegInfo();
 125   assert(MRI->isSSA() && "Can only do this while the function is in SSA form.");
 126   if (ThisMBB->succ_size() != 2) {
 127     DEBUG(dbgs() << "Don't know how to handle blocks that don't have exactly"
 128                  << " two succesors.\n");
 129     return false;
 130   }
 131
 132   const PPCInstrInfo *TII = MF->getSubtarget<PPCSubtarget>().getInstrInfo();
 133   unsigned OrigBROpcode = BSI.OrigBranch->getOpcode();
 134   unsigned InvertedOpcode =
 135     OrigBROpcode == PPC::BC ? PPC::BCn :
 136     OrigBROpcode == PPC::BCn ? PPC::BC :
 137     OrigBROpcode == PPC::BCLR ? PPC::BCLRn : PPC::BCLR;
 138   unsigned NewBROpcode = BSI.InvertNewBranch ? InvertedOpcode : OrigBROpcode;
 139   MachineBasicBlock *OrigTarget = BSI.OrigBranch->getOperand(1).getMBB();
 140   MachineBasicBlock *OrigFallThrough =
 141     OrigTarget == *ThisMBB->succ_begin() ? *ThisMBB->succ_rbegin() :
 142     *ThisMBB->succ_begin();
 143   MachineBasicBlock *NewBRTarget =
 144     BSI.BranchToFallThrough ? OrigFallThrough : OrigTarget;
 145   BranchProbability ProbToNewTarget =
 146     !BSI.MBPI ? BranchProbability::getUnknown() :
 147     BSI.MBPI->getEdgeProbability(ThisMBB, NewBRTarget);
 148
 149   // Create a new basic block.
 150   MachineBasicBlock::iterator InsertPoint = BSI.SplitBefore;
 151   const BasicBlock *LLVM_BB = ThisMBB->getBasicBlock();
 152   MachineFunction::iterator It = ThisMBB->getIterator();
 153   MachineBasicBlock *NewMBB = MF->CreateMachineBasicBlock(LLVM_BB);
 154   MF->insert(++It, NewMBB);
 155
 156   // Move everything after SplitBefore into the new block.
 157   NewMBB->splice(NewMBB->end(), ThisMBB, InsertPoint, ThisMBB->end());
 158   NewMBB->transferSuccessors(ThisMBB);
 159
 160   // Add the two successors to ThisMBB. The probabilities come from the
 161   // existing blocks if available.
 162   ThisMBB->addSuccessor(NewBRTarget, ProbToNewTarget);
 163   ThisMBB->addSuccessor(NewMBB, ProbToNewTarget.getCompl());
 164
 165   // Add the branches to ThisMBB.
 166   BuildMI(*ThisMBB, ThisMBB->end(), BSI.SplitBefore->getDebugLoc(),
 167           TII->get(NewBROpcode)).addReg(BSI.SplitCond->getOperand(0).getReg())
 168           .addMBB(NewBRTarget);
 169   BuildMI(*ThisMBB, ThisMBB->end(), BSI.SplitBefore->getDebugLoc(),
 170           TII->get(PPC::B)).addMBB(NewMBB);
 171   if (BSI.MIToDelete)
 172     BSI.MIToDelete->eraseFromParent();
 173
 174   // Change the condition on the original branch and invert it if requested.
 175   auto FirstTerminator = NewMBB->getFirstTerminator();
 176   if (BSI.NewCond) {
 177     assert(FirstTerminator->getOperand(0).isReg() &&
 178            "Can't update condition of unconditional branch.");
 179     FirstTerminator->getOperand(0).setReg(BSI.NewCond->getOperand(0).getReg());
 180   }
 181   if (BSI.InvertOrigBranch)
 182     FirstTerminator->setDesc(TII->get(InvertedOpcode));
 183
 184   // If any of the PHIs in the successors of NewMBB reference values that
 185   // now come from NewMBB, they need to be updated.
 186   for (auto *Succ : NewMBB->successors()) {
 187     updatePHIs(Succ, ThisMBB, NewMBB, MRI);
 188   }
 189   addIncomingValuesToPHIs(NewBRTarget, ThisMBB, NewMBB, MRI);
 190
 191   DEBUG(dbgs() << "After splitting, ThisMBB:\n"; ThisMBB->dump());
 192   DEBUG(dbgs() << "NewMBB:\n"; NewMBB->dump());
 193   DEBUG(dbgs() << "New branch-to block:\n"; NewBRTarget->dump());
 194   return true;
 195 }
 196
 197
 198 #endif