Home | History | Annotate | Download | only in PowerPC 
      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     MachineFunctionProperties getRequiredProperties() const override {
     50       return MachineFunctionProperties().set(
     51           MachineFunctionProperties::Property::AllVRegsAllocated);
     52     }
     53 
     54     const char *getPassName() const override {
     55       return "PowerPC Branch Selector";
     56     }
     57   };
     58   char PPCBSel::ID = 0;
     59 }
     60 
     61 INITIALIZE_PASS(PPCBSel, "ppc-branch-select", "PowerPC Branch Selector",
     62                 false, false)
     63 
     64 /// createPPCBranchSelectionPass - returns an instance of the Branch Selection
     65 /// Pass
     66 ///
     67 FunctionPass *llvm::createPPCBranchSelectionPass() {
     68   return new PPCBSel();
     69 }
     70 
     71 bool PPCBSel::runOnMachineFunction(MachineFunction &Fn) {
     72   const PPCInstrInfo *TII =
     73       static_cast<const PPCInstrInfo *>(Fn.getSubtarget().getInstrInfo());
     74   // Give the blocks of the function a dense, in-order, numbering.
     75   Fn.RenumberBlocks();
     76   BlockSizes.resize(Fn.getNumBlockIDs());
     77 
     78   auto GetAlignmentAdjustment =
     79     [TII](MachineBasicBlock &MBB, unsigned Offset) -> unsigned {
     80     unsigned Align = MBB.getAlignment();
     81     if (!Align)
     82       return 0;
     83 
     84     unsigned AlignAmt = 1 << Align;
     85     unsigned ParentAlign = MBB.getParent()->getAlignment();
     86 
     87     if (Align <= ParentAlign)
     88       return OffsetToAlignment(Offset, AlignAmt);
     89 
     90     // The alignment of this MBB is larger than the function's alignment, so we
     91     // can't tell whether or not it will insert nops. Assume that it will.
     92     return AlignAmt + OffsetToAlignment(Offset, AlignAmt);
     93   };
     94 
     95   // Measure each MBB and compute a size for the entire function.
     96   unsigned FuncSize = 0;
     97   for (MachineFunction::iterator MFI = Fn.begin(), E = Fn.end(); MFI != E;
     98        ++MFI) {
     99     MachineBasicBlock *MBB = &*MFI;
    100 
    101     // The end of the previous block may have extra nops if this block has an
    102     // alignment requirement.
    103     if (MBB->getNumber() > 0) {
    104       unsigned AlignExtra = GetAlignmentAdjustment(*MBB, FuncSize);
    105       BlockSizes[MBB->getNumber()-1] += AlignExtra;
    106       FuncSize += AlignExtra;
    107     }
    108 
    109     unsigned BlockSize = 0;
    110     for (MachineInstr &MI : *MBB)
    111       BlockSize += TII->GetInstSizeInBytes(MI);
    112 
    113     BlockSizes[MBB->getNumber()] = BlockSize;
    114     FuncSize += BlockSize;
    115   }
    116 
    117   // If the entire function is smaller than the displacement of a branch field,
    118   // we know we don't need to shrink any branches in this function.  This is a
    119   // common case.
    120   if (FuncSize < (1 << 15)) {
    121     BlockSizes.clear();
    122     return false;
    123   }
    124 
    125   // For each conditional branch, if the offset to its destination is larger
    126   // than the offset field allows, transform it into a long branch sequence
    127   // like this:
    128   //   short branch:
    129   //     bCC MBB
    130   //   long branch:
    131   //     b!CC $PC+8
    132   //     b MBB
    133   //
    134   bool MadeChange = true;
    135   bool EverMadeChange = false;
    136   while (MadeChange) {
    137     // Iteratively expand branches until we reach a fixed point.
    138     MadeChange = false;
    139 
    140     for (MachineFunction::iterator MFI = Fn.begin(), E = Fn.end(); MFI != E;
    141          ++MFI) {
    142       MachineBasicBlock &MBB = *MFI;
    143       unsigned MBBStartOffset = 0;
    144       for (MachineBasicBlock::iterator I = MBB.begin(), E = MBB.end();
    145            I != E; ++I) {
    146         MachineBasicBlock *Dest = nullptr;
    147         if (I->getOpcode() == PPC::BCC && !I->getOperand(2).isImm())
    148           Dest = I->getOperand(2).getMBB();
    149         else if ((I->getOpcode() == PPC::BC || I->getOpcode() == PPC::BCn) &&
    150                  !I->getOperand(1).isImm())
    151           Dest = I->getOperand(1).getMBB();
    152         else if ((I->getOpcode() == PPC::BDNZ8 || I->getOpcode() == PPC::BDNZ ||
    153                   I->getOpcode() == PPC::BDZ8  || I->getOpcode() == PPC::BDZ) &&
    154                  !I->getOperand(0).isImm())
    155           Dest = I->getOperand(0).getMBB();
    156 
    157         if (!Dest) {
    158           MBBStartOffset += TII->GetInstSizeInBytes(*I);
    159           continue;
    160         }
    161 
    162         // Determine the offset from the current branch to the destination
    163         // block.
    164         int BranchSize;
    165         if (Dest->getNumber() <= MBB.getNumber()) {
    166           // If this is a backwards branch, the delta is the offset from the
    167           // start of this block to this branch, plus the sizes of all blocks
    168           // from this block to the dest.
    169           BranchSize = MBBStartOffset;
    170 
    171           for (unsigned i = Dest->getNumber(), e = MBB.getNumber(); i != e; ++i)
    172             BranchSize += BlockSizes[i];
    173         } else {
    174           // Otherwise, add the size of the blocks between this block and the
    175           // dest to the number of bytes left in this block.
    176           BranchSize = -MBBStartOffset;
    177 
    178           for (unsigned i = MBB.getNumber(), e = Dest->getNumber(); i != e; ++i)
    179             BranchSize += BlockSizes[i];
    180         }
    181 
    182         // If this branch is in range, ignore it.
    183         if (isInt<16>(BranchSize)) {
    184           MBBStartOffset += 4;
    185           continue;
    186         }
    187 
    188         // Otherwise, we have to expand it to a long branch.
    189         MachineInstr *OldBranch = I;
    190         DebugLoc dl = OldBranch->getDebugLoc();
    191 
    192         if (I->getOpcode() == PPC::BCC) {
    193           // The BCC operands are:
    194           // 0. PPC branch predicate
    195           // 1. CR register
    196           // 2. Target MBB
    197           PPC::Predicate Pred = (PPC::Predicate)I->getOperand(0).getImm();
    198           unsigned CRReg = I->getOperand(1).getReg();
    199 
    200           // Jump over the uncond branch inst (i.e. $PC+8) on opposite condition.
    201           BuildMI(MBB, I, dl, TII->get(PPC::BCC))
    202             .addImm(PPC::InvertPredicate(Pred)).addReg(CRReg).addImm(2);
    203         } else if (I->getOpcode() == PPC::BC) {
    204           unsigned CRBit = I->getOperand(0).getReg();
    205           BuildMI(MBB, I, dl, TII->get(PPC::BCn)).addReg(CRBit).addImm(2);
    206         } else if (I->getOpcode() == PPC::BCn) {
    207           unsigned CRBit = I->getOperand(0).getReg();
    208           BuildMI(MBB, I, dl, TII->get(PPC::BC)).addReg(CRBit).addImm(2);
    209         } else if (I->getOpcode() == PPC::BDNZ) {
    210           BuildMI(MBB, I, dl, TII->get(PPC::BDZ)).addImm(2);
    211         } else if (I->getOpcode() == PPC::BDNZ8) {
    212           BuildMI(MBB, I, dl, TII->get(PPC::BDZ8)).addImm(2);
    213         } else if (I->getOpcode() == PPC::BDZ) {
    214           BuildMI(MBB, I, dl, TII->get(PPC::BDNZ)).addImm(2);
    215         } else if (I->getOpcode() == PPC::BDZ8) {
    216           BuildMI(MBB, I, dl, TII->get(PPC::BDNZ8)).addImm(2);
    217         } else {
    218            llvm_unreachable("Unhandled branch type!");
    219         }
    220 
    221         // Uncond branch to the real destination.
    222         I = BuildMI(MBB, I, dl, TII->get(PPC::B)).addMBB(Dest);
    223 
    224         // Remove the old branch from the function.
    225         OldBranch->eraseFromParent();
    226 
    227         // Remember that this instruction is 8-bytes, increase the size of the
    228         // block by 4, remember to iterate.
    229         BlockSizes[MBB.getNumber()] += 4;
    230         MBBStartOffset += 8;
    231         ++NumExpanded;
    232         MadeChange = true;
    233       }
    234     }
    235     EverMadeChange |= MadeChange;
    236   }
    237 
    238   BlockSizes.clear();
    239   return true;
    240 }
    241