lib/Target/PowerPC/PPCBranchSelector.cpp

   1 //===-- PPCBranchSelector.cpp - Emit long conditional branches ------------===//
   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 contains a pass that scans a machine function to determine which
  11 // conditional branches need more than 16 bits of displacement to reach their
  12 // target basic block.  It does this in two passes; a calculation of basic block
  13 // positions pass, and a branch pseudo op to machine branch opcode pass.  This
  14 // pass should be run last, just before the assembly printer.
  15 //
  16 //===----------------------------------------------------------------------===//
  17
  18 #include "PPC.h"
  19 #include "MCTargetDesc/PPCPredicates.h"
  20 #include "PPCInstrBuilder.h"
  21 #include "PPCInstrInfo.h"
  22 #include "llvm/ADT/Statistic.h"
  23 #include "llvm/CodeGen/MachineFunctionPass.h"
  24 #include "llvm/Support/MathExtras.h"
  25 #include "llvm/Target/TargetMachine.h"
  26 #include "llvm/Target/TargetSubtargetInfo.h"
  27 using namespace llvm;
  28
  29 #define DEBUG_TYPE "ppc-branch-select"
  30
  31 STATISTIC(NumExpanded, "Number of branches expanded to long format");
  32
  33 namespace llvm {
  34   void initializePPCBSelPass(PassRegistry&);
  35 }
  36
  37 namespace {
  38   struct PPCBSel : public MachineFunctionPass {
  39     static char ID;
  40     PPCBSel() : MachineFunctionPass(ID) {
  41       initializePPCBSelPass(*PassRegistry::getPassRegistry());
  42     }
  43
  44     /// BlockSizes - The sizes of the basic blocks in the function.
  45     std::vector<unsigned> BlockSizes;
  46
  47     bool runOnMachineFunction(MachineFunction &Fn) override;
  48
  49     const char *getPassName() const override {
  50       return "PowerPC Branch Selector";
  51     }
  52   };
  53   char PPCBSel::ID = 0;
  54 }
  55
  56 INITIALIZE_PASS(PPCBSel, "ppc-branch-select", "PowerPC Branch Selector",
  57                 false, false)
  58
  59 /// createPPCBranchSelectionPass - returns an instance of the Branch Selection
  60 /// Pass
  61 ///
  62 FunctionPass *llvm::createPPCBranchSelectionPass() {
  63   return new PPCBSel();
  64 }
  65
  66 bool PPCBSel::runOnMachineFunction(MachineFunction &Fn) {
  67   const PPCInstrInfo *TII =
  68       static_cast<const PPCInstrInfo *>(Fn.getSubtarget().getInstrInfo());
  69   // Give the blocks of the function a dense, in-order, numbering.
  70   Fn.RenumberBlocks();
  71   BlockSizes.resize(Fn.getNumBlockIDs());
  72
  73   auto GetAlignmentAdjustment =
  74     [TII](MachineBasicBlock &MBB, unsigned Offset) -> unsigned {
  75     unsigned Align = MBB.getAlignment();
  76     if (!Align)
  77       return 0;
  78
  79     unsigned AlignAmt = 1 << Align;
  80     unsigned ParentAlign = MBB.getParent()->getAlignment();
  81
  82     if (Align <= ParentAlign)
  83       return OffsetToAlignment(Offset, AlignAmt);
  84
  85     // The alignment of this MBB is larger than the function's alignment, so we
  86     // can't tell whether or not it will insert nops. Assume that it will.
  87     return AlignAmt + OffsetToAlignment(Offset, AlignAmt);
  88   };
  89
  90   // Measure each MBB and compute a size for the entire function.
  91   unsigned FuncSize = 0;
  92   for (MachineFunction::iterator MFI = Fn.begin(), E = Fn.end(); MFI != E;
  93        ++MFI) {
  94     MachineBasicBlock *MBB = &*MFI;
  95
  96     // The end of the previous block may have extra nops if this block has an
  97     // alignment requirement.
  98     if (MBB->getNumber() > 0) {
  99       unsigned AlignExtra = GetAlignmentAdjustment(*MBB, FuncSize);
 100       BlockSizes[MBB->getNumber()-1] += AlignExtra;
 101       FuncSize += AlignExtra;
 102     }
 103
 104     unsigned BlockSize = 0;
 105     for (MachineBasicBlock::iterator MBBI = MBB->begin(), EE = MBB->end();
 106          MBBI != EE; ++MBBI)
 107       BlockSize += TII->GetInstSizeInBytes(MBBI);
 108
 109     BlockSizes[MBB->getNumber()] = BlockSize;
 110     FuncSize += BlockSize;
 111   }
 112
 113   // If the entire function is smaller than the displacement of a branch field,
 114   // we know we don't need to shrink any branches in this function.  This is a
 115   // common case.
 116   if (FuncSize < (1 << 15)) {
 117     BlockSizes.clear();
 118     return false;
 119   }
 120
 121   // For each conditional branch, if the offset to its destination is larger
 122   // than the offset field allows, transform it into a long branch sequence
 123   // like this:
 124   //   short branch:
 125   //     bCC MBB
 126   //   long branch:
 127   //     b!CC $PC+8
 128   //     b MBB
 129   //
 130   bool MadeChange = true;
 131   bool EverMadeChange = false;
 132   while (MadeChange) {
 133     // Iteratively expand branches until we reach a fixed point.
 134     MadeChange = false;
 135
 136     for (MachineFunction::iterator MFI = Fn.begin(), E = Fn.end(); MFI != E;
 137          ++MFI) {
 138       MachineBasicBlock &MBB = *MFI;
 139       unsigned MBBStartOffset = 0;
 140       for (MachineBasicBlock::iterator I = MBB.begin(), E = MBB.end();
 141            I != E; ++I) {
 142         MachineBasicBlock *Dest = nullptr;
 143         if (I->getOpcode() == PPC::BCC && !I->getOperand(2).isImm())
 144           Dest = I->getOperand(2).getMBB();
 145         else if ((I->getOpcode() == PPC::BC || I->getOpcode() == PPC::BCn) &&
 146                  !I->getOperand(1).isImm())
 147           Dest = I->getOperand(1).getMBB();
 148         else if ((I->getOpcode() == PPC::BDNZ8 || I->getOpcode() == PPC::BDNZ ||
 149                   I->getOpcode() == PPC::BDZ8  || I->getOpcode() == PPC::BDZ) &&
 150                  !I->getOperand(0).isImm())
 151           Dest = I->getOperand(0).getMBB();
 152
 153         if (!Dest) {
 154           MBBStartOffset += TII->GetInstSizeInBytes(I);
 155           continue;
 156         }
 157
 158         // Determine the offset from the current branch to the destination
 159         // block.
 160         int BranchSize;
 161         if (Dest->getNumber() <= MBB.getNumber()) {
 162           // If this is a backwards branch, the delta is the offset from the
 163           // start of this block to this branch, plus the sizes of all blocks
 164           // from this block to the dest.
 165           BranchSize = MBBStartOffset;
 166
 167           for (unsigned i = Dest->getNumber(), e = MBB.getNumber(); i != e; ++i)
 168             BranchSize += BlockSizes[i];
 169         } else {
 170           // Otherwise, add the size of the blocks between this block and the
 171           // dest to the number of bytes left in this block.
 172           BranchSize = -MBBStartOffset;
 173
 174           for (unsigned i = MBB.getNumber(), e = Dest->getNumber(); i != e; ++i)
 175             BranchSize += BlockSizes[i];
 176         }
 177
 178         // If this branch is in range, ignore it.
 179         if (isInt<16>(BranchSize)) {
 180           MBBStartOffset += 4;
 181           continue;
 182         }
 183
 184         // Otherwise, we have to expand it to a long branch.
 185         MachineInstr *OldBranch = I;
 186         DebugLoc dl = OldBranch->getDebugLoc();
 187
 188         if (I->getOpcode() == PPC::BCC) {
 189           // The BCC operands are:
 190           // 0. PPC branch predicate
 191           // 1. CR register
 192           // 2. Target MBB
 193           PPC::Predicate Pred = (PPC::Predicate)I->getOperand(0).getImm();
 194           unsigned CRReg = I->getOperand(1).getReg();
 195
 196           // Jump over the uncond branch inst (i.e. $PC+8) on opposite condition.
 197           BuildMI(MBB, I, dl, TII->get(PPC::BCC))
 198             .addImm(PPC::InvertPredicate(Pred)).addReg(CRReg).addImm(2);
 199         } else if (I->getOpcode() == PPC::BC) {
 200           unsigned CRBit = I->getOperand(0).getReg();
 201           BuildMI(MBB, I, dl, TII->get(PPC::BCn)).addReg(CRBit).addImm(2);
 202         } else if (I->getOpcode() == PPC::BCn) {
 203           unsigned CRBit = I->getOperand(0).getReg();
 204           BuildMI(MBB, I, dl, TII->get(PPC::BC)).addReg(CRBit).addImm(2);
 205         } else if (I->getOpcode() == PPC::BDNZ) {
 206           BuildMI(MBB, I, dl, TII->get(PPC::BDZ)).addImm(2);
 207         } else if (I->getOpcode() == PPC::BDNZ8) {
 208           BuildMI(MBB, I, dl, TII->get(PPC::BDZ8)).addImm(2);
 209         } else if (I->getOpcode() == PPC::BDZ) {
 210           BuildMI(MBB, I, dl, TII->get(PPC::BDNZ)).addImm(2);
 211         } else if (I->getOpcode() == PPC::BDZ8) {
 212           BuildMI(MBB, I, dl, TII->get(PPC::BDNZ8)).addImm(2);
 213         } else {
 214            llvm_unreachable("Unhandled branch type!");
 215         }
 216
 217         // Uncond branch to the real destination.
 218         I = BuildMI(MBB, I, dl, TII->get(PPC::B)).addMBB(Dest);
 219
 220         // Remove the old branch from the function.
 221         OldBranch->eraseFromParent();
 222
 223         // Remember that this instruction is 8-bytes, increase the size of the
 224         // block by 4, remember to iterate.
 225         BlockSizes[MBB.getNumber()] += 4;
 226         MBBStartOffset += 8;
 227         ++NumExpanded;
 228         MadeChange = true;
 229       }
 230     }
 231     EverMadeChange |= MadeChange;
 232   }
 233
 234   BlockSizes.clear();
 235   return true;
 236 }
 237