Home | History | Annotate | Download | only in AArch64 
      1 //===-- AArch64BranchRelaxation.cpp - AArch64 branch relaxation -----------===//
      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 //===----------------------------------------------------------------------===//
     11 
     12 #include "AArch64.h"
     13 #include "AArch64InstrInfo.h"
     14 #include "AArch64MachineFunctionInfo.h"
     15 #include "AArch64Subtarget.h"
     16 #include "llvm/ADT/SmallVector.h"
     17 #include "llvm/ADT/Statistic.h"
     18 #include "llvm/CodeGen/MachineFunctionPass.h"
     19 #include "llvm/CodeGen/MachineInstrBuilder.h"
     20 #include "llvm/Support/CommandLine.h"
     21 #include "llvm/Support/Debug.h"
     22 #include "llvm/Support/ErrorHandling.h"
     23 #include "llvm/Support/Format.h"
     24 #include "llvm/Support/raw_ostream.h"
     25 using namespace llvm;
     26 
     27 #define DEBUG_TYPE "aarch64-branch-relax"
     28 
     29 static cl::opt<bool>
     30 BranchRelaxation("aarch64-branch-relax", cl::Hidden, cl::init(true),
     31                  cl::desc("Relax out of range conditional branches"));
     32 
     33 static cl::opt<unsigned>
     34 TBZDisplacementBits("aarch64-tbz-offset-bits", cl::Hidden, cl::init(14),
     35                     cl::desc("Restrict range of TB[N]Z instructions (DEBUG)"));
     36 
     37 static cl::opt<unsigned>
     38 CBZDisplacementBits("aarch64-cbz-offset-bits", cl::Hidden, cl::init(19),
     39                     cl::desc("Restrict range of CB[N]Z instructions (DEBUG)"));
     40 
     41 static cl::opt<unsigned>
     42 BCCDisplacementBits("aarch64-bcc-offset-bits", cl::Hidden, cl::init(19),
     43                     cl::desc("Restrict range of Bcc instructions (DEBUG)"));
     44 
     45 STATISTIC(NumSplit, "Number of basic blocks split");
     46 STATISTIC(NumRelaxed, "Number of conditional branches relaxed");
     47 
     48 namespace llvm {
     49 void initializeAArch64BranchRelaxationPass(PassRegistry &);
     50 }
     51 
     52 #define AARCH64_BR_RELAX_NAME "AArch64 branch relaxation pass"
     53 
     54 namespace {
     55 class AArch64BranchRelaxation : public MachineFunctionPass {
     56   /// BasicBlockInfo - Information about the offset and size of a single
     57   /// basic block.
     58   struct BasicBlockInfo {
     59     /// Offset - Distance from the beginning of the function to the beginning
     60     /// of this basic block.
     61     ///
     62     /// The offset is always aligned as required by the basic block.
     63     unsigned Offset;
     64 
     65     /// Size - Size of the basic block in bytes.  If the block contains
     66     /// inline assembly, this is a worst case estimate.
     67     ///
     68     /// The size does not include any alignment padding whether from the
     69     /// beginning of the block, or from an aligned jump table at the end.
     70     unsigned Size;
     71 
     72     BasicBlockInfo() : Offset(0), Size(0) {}
     73 
     74     /// Compute the offset immediately following this block.  If LogAlign is
     75     /// specified, return the offset the successor block will get if it has
     76     /// this alignment.
     77     unsigned postOffset(unsigned LogAlign = 0) const {
     78       unsigned PO = Offset + Size;
     79       unsigned Align = 1 << LogAlign;
     80       return (PO + Align - 1) / Align * Align;
     81     }
     82   };
     83 
     84   SmallVector<BasicBlockInfo, 16> BlockInfo;
     85 
     86   MachineFunction *MF;
     87   const AArch64InstrInfo *TII;
     88 
     89   bool relaxBranchInstructions();
     90   void scanFunction();
     91   MachineBasicBlock *splitBlockBeforeInstr(MachineInstr *MI);
     92   void adjustBlockOffsets(MachineBasicBlock &MBB);
     93   bool isBlockInRange(MachineInstr *MI, MachineBasicBlock *BB, unsigned Disp);
     94   bool fixupConditionalBranch(MachineInstr *MI);
     95   void computeBlockSize(const MachineBasicBlock &MBB);
     96   unsigned getInstrOffset(MachineInstr *MI) const;
     97   void dumpBBs();
     98   void verify();
     99 
    100 public:
    101   static char ID;
    102   AArch64BranchRelaxation() : MachineFunctionPass(ID) {
    103     initializeAArch64BranchRelaxationPass(*PassRegistry::getPassRegistry());
    104   }
    105 
    106   bool runOnMachineFunction(MachineFunction &MF) override;
    107 
    108   const char *getPassName() const override {
    109     return AARCH64_BR_RELAX_NAME;
    110   }
    111 };
    112 char AArch64BranchRelaxation::ID = 0;
    113 }
    114 
    115 INITIALIZE_PASS(AArch64BranchRelaxation, "aarch64-branch-relax",
    116                 AARCH64_BR_RELAX_NAME, false, false)
    117 
    118 /// verify - check BBOffsets, BBSizes, alignment of islands
    119 void AArch64BranchRelaxation::verify() {
    120 #ifndef NDEBUG
    121   unsigned PrevNum = MF->begin()->getNumber();
    122   for (MachineBasicBlock &MBB : *MF) {
    123     unsigned Align = MBB.getAlignment();
    124     unsigned Num = MBB.getNumber();
    125     assert(BlockInfo[Num].Offset % (1u << Align) == 0);
    126     assert(!Num || BlockInfo[PrevNum].postOffset() <= BlockInfo[Num].Offset);
    127     PrevNum = Num;
    128   }
    129 #endif
    130 }
    131 
    132 /// print block size and offset information - debugging
    133 void AArch64BranchRelaxation::dumpBBs() {
    134   for (auto &MBB : *MF) {
    135     const BasicBlockInfo &BBI = BlockInfo[MBB.getNumber()];
    136     dbgs() << format("BB#%u\toffset=%08x\t", MBB.getNumber(), BBI.Offset)
    137            << format("size=%#x\n", BBI.Size);
    138   }
    139 }
    140 
    141 /// BBHasFallthrough - Return true if the specified basic block can fallthrough
    142 /// into the block immediately after it.
    143 static bool BBHasFallthrough(MachineBasicBlock *MBB) {
    144   // Get the next machine basic block in the function.
    145   MachineFunction::iterator MBBI(MBB);
    146   // Can't fall off end of function.
    147   auto NextBB = std::next(MBBI);
    148   if (NextBB == MBB->getParent()->end())
    149     return false;
    150 
    151   for (MachineBasicBlock *S : MBB->successors())
    152     if (S == &*NextBB)
    153       return true;
    154 
    155   return false;
    156 }
    157 
    158 /// scanFunction - Do the initial scan of the function, building up
    159 /// information about each block.
    160 void AArch64BranchRelaxation::scanFunction() {
    161   BlockInfo.clear();
    162   BlockInfo.resize(MF->getNumBlockIDs());
    163 
    164   // First thing, compute the size of all basic blocks, and see if the function
    165   // has any inline assembly in it. If so, we have to be conservative about
    166   // alignment assumptions, as we don't know for sure the size of any
    167   // instructions in the inline assembly.
    168   for (MachineBasicBlock &MBB : *MF)
    169     computeBlockSize(MBB);
    170 
    171   // Compute block offsets and known bits.
    172   adjustBlockOffsets(*MF->begin());
    173 }
    174 
    175 /// computeBlockSize - Compute the size for MBB.
    176 /// This function updates BlockInfo directly.
    177 void AArch64BranchRelaxation::computeBlockSize(const MachineBasicBlock &MBB) {
    178   unsigned Size = 0;
    179   for (const MachineInstr &MI : MBB)
    180     Size += TII->GetInstSizeInBytes(MI);
    181   BlockInfo[MBB.getNumber()].Size = Size;
    182 }
    183 
    184 /// getInstrOffset - Return the current offset of the specified machine
    185 /// instruction from the start of the function.  This offset changes as stuff is
    186 /// moved around inside the function.
    187 unsigned AArch64BranchRelaxation::getInstrOffset(MachineInstr *MI) const {
    188   MachineBasicBlock *MBB = MI->getParent();
    189 
    190   // The offset is composed of two things: the sum of the sizes of all MBB's
    191   // before this instruction's block, and the offset from the start of the block
    192   // it is in.
    193   unsigned Offset = BlockInfo[MBB->getNumber()].Offset;
    194 
    195   // Sum instructions before MI in MBB.
    196   for (MachineBasicBlock::iterator I = MBB->begin(); &*I != MI; ++I) {
    197     assert(I != MBB->end() && "Didn't find MI in its own basic block?");
    198     Offset += TII->GetInstSizeInBytes(*I);
    199   }
    200   return Offset;
    201 }
    202 
    203 void AArch64BranchRelaxation::adjustBlockOffsets(MachineBasicBlock &Start) {
    204   unsigned PrevNum = Start.getNumber();
    205   for (auto &MBB : make_range(MachineFunction::iterator(Start), MF->end())) {
    206     unsigned Num = MBB.getNumber();
    207     if (!Num) // block zero is never changed from offset zero.
    208       continue;
    209     // Get the offset and known bits at the end of the layout predecessor.
    210     // Include the alignment of the current block.
    211     unsigned LogAlign = MBB.getAlignment();
    212     BlockInfo[Num].Offset = BlockInfo[PrevNum].postOffset(LogAlign);
    213     PrevNum = Num;
    214   }
    215 }
    216 
    217 /// Split the basic block containing MI into two blocks, which are joined by
    218 /// an unconditional branch.  Update data structures and renumber blocks to
    219 /// account for this change and returns the newly created block.
    220 /// NOTE: Successor list of the original BB is out of date after this function,
    221 /// and must be updated by the caller! Other transforms follow using this
    222 /// utility function, so no point updating now rather than waiting.
    223 MachineBasicBlock *
    224 AArch64BranchRelaxation::splitBlockBeforeInstr(MachineInstr *MI) {
    225   MachineBasicBlock *OrigBB = MI->getParent();
    226 
    227   // Create a new MBB for the code after the OrigBB.
    228   MachineBasicBlock *NewBB =
    229       MF->CreateMachineBasicBlock(OrigBB->getBasicBlock());
    230   MF->insert(++OrigBB->getIterator(), NewBB);
    231 
    232   // Splice the instructions starting with MI over to NewBB.
    233   NewBB->splice(NewBB->end(), OrigBB, MI, OrigBB->end());
    234 
    235   // Add an unconditional branch from OrigBB to NewBB.
    236   // Note the new unconditional branch is not being recorded.
    237   // There doesn't seem to be meaningful DebugInfo available; this doesn't
    238   // correspond to anything in the source.
    239   BuildMI(OrigBB, DebugLoc(), TII->get(AArch64::B)).addMBB(NewBB);
    240 
    241   // Insert an entry into BlockInfo to align it properly with the block numbers.
    242   BlockInfo.insert(BlockInfo.begin() + NewBB->getNumber(), BasicBlockInfo());
    243 
    244   // Figure out how large the OrigBB is.  As the first half of the original
    245   // block, it cannot contain a tablejump.  The size includes
    246   // the new jump we added.  (It should be possible to do this without
    247   // recounting everything, but it's very confusing, and this is rarely
    248   // executed.)
    249   computeBlockSize(*OrigBB);
    250 
    251   // Figure out how large the NewMBB is.  As the second half of the original
    252   // block, it may contain a tablejump.
    253   computeBlockSize(*NewBB);
    254 
    255   // All BBOffsets following these blocks must be modified.
    256   adjustBlockOffsets(*OrigBB);
    257 
    258   ++NumSplit;
    259 
    260   return NewBB;
    261 }
    262 
    263 /// isBlockInRange - Returns true if the distance between specific MI and
    264 /// specific BB can fit in MI's displacement field.
    265 bool AArch64BranchRelaxation::isBlockInRange(MachineInstr *MI,
    266                                              MachineBasicBlock *DestBB,
    267                                              unsigned Bits) {
    268   unsigned MaxOffs = ((1 << (Bits - 1)) - 1) << 2;
    269   unsigned BrOffset = getInstrOffset(MI);
    270   unsigned DestOffset = BlockInfo[DestBB->getNumber()].Offset;
    271 
    272   DEBUG(dbgs() << "Branch of destination BB#" << DestBB->getNumber()
    273                << " from BB#" << MI->getParent()->getNumber()
    274                << " max delta=" << MaxOffs << " from " << getInstrOffset(MI)
    275                << " to " << DestOffset << " offset "
    276                << int(DestOffset - BrOffset) << "\t" << *MI);
    277 
    278   // Branch before the Dest.
    279   if (BrOffset <= DestOffset)
    280     return (DestOffset - BrOffset <= MaxOffs);
    281   return (BrOffset - DestOffset <= MaxOffs);
    282 }
    283 
    284 static bool isConditionalBranch(unsigned Opc) {
    285   switch (Opc) {
    286   default:
    287     return false;
    288   case AArch64::TBZW:
    289   case AArch64::TBNZW:
    290   case AArch64::TBZX:
    291   case AArch64::TBNZX:
    292   case AArch64::CBZW:
    293   case AArch64::CBNZW:
    294   case AArch64::CBZX:
    295   case AArch64::CBNZX:
    296   case AArch64::Bcc:
    297     return true;
    298   }
    299 }
    300 
    301 static MachineBasicBlock *getDestBlock(MachineInstr *MI) {
    302   switch (MI->getOpcode()) {
    303   default:
    304     llvm_unreachable("unexpected opcode!");
    305   case AArch64::TBZW:
    306   case AArch64::TBNZW:
    307   case AArch64::TBZX:
    308   case AArch64::TBNZX:
    309     return MI->getOperand(2).getMBB();
    310   case AArch64::CBZW:
    311   case AArch64::CBNZW:
    312   case AArch64::CBZX:
    313   case AArch64::CBNZX:
    314   case AArch64::Bcc:
    315     return MI->getOperand(1).getMBB();
    316   }
    317 }
    318 
    319 static unsigned getOppositeConditionOpcode(unsigned Opc) {
    320   switch (Opc) {
    321   default:
    322     llvm_unreachable("unexpected opcode!");
    323   case AArch64::TBNZW:   return AArch64::TBZW;
    324   case AArch64::TBNZX:   return AArch64::TBZX;
    325   case AArch64::TBZW:    return AArch64::TBNZW;
    326   case AArch64::TBZX:    return AArch64::TBNZX;
    327   case AArch64::CBNZW:   return AArch64::CBZW;
    328   case AArch64::CBNZX:   return AArch64::CBZX;
    329   case AArch64::CBZW:    return AArch64::CBNZW;
    330   case AArch64::CBZX:    return AArch64::CBNZX;
    331   case AArch64::Bcc:     return AArch64::Bcc; // Condition is an operand for Bcc.
    332   }
    333 }
    334 
    335 static unsigned getBranchDisplacementBits(unsigned Opc) {
    336   switch (Opc) {
    337   default:
    338     llvm_unreachable("unexpected opcode!");
    339   case AArch64::TBNZW:
    340   case AArch64::TBZW:
    341   case AArch64::TBNZX:
    342   case AArch64::TBZX:
    343     return TBZDisplacementBits;
    344   case AArch64::CBNZW:
    345   case AArch64::CBZW:
    346   case AArch64::CBNZX:
    347   case AArch64::CBZX:
    348     return CBZDisplacementBits;
    349   case AArch64::Bcc:
    350     return BCCDisplacementBits;
    351   }
    352 }
    353 
    354 static inline void invertBccCondition(MachineInstr *MI) {
    355   assert(MI->getOpcode() == AArch64::Bcc && "Unexpected opcode!");
    356   AArch64CC::CondCode CC = (AArch64CC::CondCode)MI->getOperand(0).getImm();
    357   CC = AArch64CC::getInvertedCondCode(CC);
    358   MI->getOperand(0).setImm((int64_t)CC);
    359 }
    360 
    361 /// fixupConditionalBranch - Fix up a conditional branch whose destination is
    362 /// too far away to fit in its displacement field. It is converted to an inverse
    363 /// conditional branch + an unconditional branch to the destination.
    364 bool AArch64BranchRelaxation::fixupConditionalBranch(MachineInstr *MI) {
    365   MachineBasicBlock *DestBB = getDestBlock(MI);
    366 
    367   // Add an unconditional branch to the destination and invert the branch
    368   // condition to jump over it:
    369   // tbz L1
    370   // =>
    371   // tbnz L2
    372   // b   L1
    373   // L2:
    374 
    375   // If the branch is at the end of its MBB and that has a fall-through block,
    376   // direct the updated conditional branch to the fall-through block. Otherwise,
    377   // split the MBB before the next instruction.
    378   MachineBasicBlock *MBB = MI->getParent();
    379   MachineInstr *BMI = &MBB->back();
    380   bool NeedSplit = (BMI != MI) || !BBHasFallthrough(MBB);
    381 
    382   if (BMI != MI) {
    383     if (std::next(MachineBasicBlock::iterator(MI)) ==
    384             std::prev(MBB->getLastNonDebugInstr()) &&
    385         BMI->getOpcode() == AArch64::B) {
    386       // Last MI in the BB is an unconditional branch. Can we simply invert the
    387       // condition and swap destinations:
    388       // beq L1
    389       // b   L2
    390       // =>
    391       // bne L2
    392       // b   L1
    393       MachineBasicBlock *NewDest = BMI->getOperand(0).getMBB();
    394       if (isBlockInRange(MI, NewDest,
    395                          getBranchDisplacementBits(MI->getOpcode()))) {
    396         DEBUG(dbgs() << "  Invert condition and swap its destination with "
    397                      << *BMI);
    398         BMI->getOperand(0).setMBB(DestBB);
    399         unsigned OpNum = (MI->getOpcode() == AArch64::TBZW ||
    400                           MI->getOpcode() == AArch64::TBNZW ||
    401                           MI->getOpcode() == AArch64::TBZX ||
    402                           MI->getOpcode() == AArch64::TBNZX)
    403                              ? 2
    404                              : 1;
    405         MI->getOperand(OpNum).setMBB(NewDest);
    406         MI->setDesc(TII->get(getOppositeConditionOpcode(MI->getOpcode())));
    407         if (MI->getOpcode() == AArch64::Bcc)
    408           invertBccCondition(MI);
    409         return true;
    410       }
    411     }
    412   }
    413 
    414   if (NeedSplit) {
    415     // Analyze the branch so we know how to update the successor lists.
    416     MachineBasicBlock *TBB, *FBB;
    417     SmallVector<MachineOperand, 2> Cond;
    418     TII->analyzeBranch(*MBB, TBB, FBB, Cond, false);
    419 
    420     MachineBasicBlock *NewBB = splitBlockBeforeInstr(MI);
    421     // No need for the branch to the next block. We're adding an unconditional
    422     // branch to the destination.
    423     int delta = TII->GetInstSizeInBytes(MBB->back());
    424     BlockInfo[MBB->getNumber()].Size -= delta;
    425     MBB->back().eraseFromParent();
    426     // BlockInfo[SplitBB].Offset is wrong temporarily, fixed below
    427 
    428     // Update the successor lists according to the transformation to follow.
    429     // Do it here since if there's no split, no update is needed.
    430     MBB->replaceSuccessor(FBB, NewBB);
    431     NewBB->addSuccessor(FBB);
    432   }
    433   MachineBasicBlock *NextBB = &*std::next(MachineFunction::iterator(MBB));
    434 
    435   DEBUG(dbgs() << "  Insert B to BB#" << DestBB->getNumber()
    436                << ", invert condition and change dest. to BB#"
    437                << NextBB->getNumber() << "\n");
    438 
    439   // Insert a new conditional branch and a new unconditional branch.
    440   MachineInstrBuilder MIB = BuildMI(
    441       MBB, DebugLoc(), TII->get(getOppositeConditionOpcode(MI->getOpcode())))
    442                                 .addOperand(MI->getOperand(0));
    443   if (MI->getOpcode() == AArch64::TBZW || MI->getOpcode() == AArch64::TBNZW ||
    444       MI->getOpcode() == AArch64::TBZX || MI->getOpcode() == AArch64::TBNZX)
    445     MIB.addOperand(MI->getOperand(1));
    446   if (MI->getOpcode() == AArch64::Bcc)
    447     invertBccCondition(MIB);
    448   MIB.addMBB(NextBB);
    449   BlockInfo[MBB->getNumber()].Size += TII->GetInstSizeInBytes(MBB->back());
    450   BuildMI(MBB, DebugLoc(), TII->get(AArch64::B)).addMBB(DestBB);
    451   BlockInfo[MBB->getNumber()].Size += TII->GetInstSizeInBytes(MBB->back());
    452 
    453   // Remove the old conditional branch.  It may or may not still be in MBB.
    454   BlockInfo[MI->getParent()->getNumber()].Size -= TII->GetInstSizeInBytes(*MI);
    455   MI->eraseFromParent();
    456 
    457   // Finally, keep the block offsets up to date.
    458   adjustBlockOffsets(*MBB);
    459   return true;
    460 }
    461 
    462 bool AArch64BranchRelaxation::relaxBranchInstructions() {
    463   bool Changed = false;
    464   // Relaxing branches involves creating new basic blocks, so re-eval
    465   // end() for termination.
    466   for (MachineFunction::iterator I = MF->begin(); I != MF->end(); ++I) {
    467     MachineBasicBlock &MBB = *I;
    468     MachineInstr &MI = *MBB.getFirstTerminator();
    469     if (isConditionalBranch(MI.getOpcode()) &&
    470         !isBlockInRange(&MI, getDestBlock(&MI),
    471                         getBranchDisplacementBits(MI.getOpcode()))) {
    472       fixupConditionalBranch(&MI);
    473       ++NumRelaxed;
    474       Changed = true;
    475     }
    476   }
    477   return Changed;
    478 }
    479 
    480 bool AArch64BranchRelaxation::runOnMachineFunction(MachineFunction &mf) {
    481   MF = &mf;
    482 
    483   // If the pass is disabled, just bail early.
    484   if (!BranchRelaxation)
    485     return false;
    486 
    487   DEBUG(dbgs() << "***** AArch64BranchRelaxation *****\n");
    488 
    489   TII = (const AArch64InstrInfo *)MF->getSubtarget().getInstrInfo();
    490 
    491   // Renumber all of the machine basic blocks in the function, guaranteeing that
    492   // the numbers agree with the position of the block in the function.
    493   MF->RenumberBlocks();
    494 
    495   // Do the initial scan of the function, building up information about the
    496   // sizes of each block.
    497   scanFunction();
    498 
    499   DEBUG(dbgs() << "  Basic blocks before relaxation\n");
    500   DEBUG(dumpBBs());
    501 
    502   bool MadeChange = false;
    503   while (relaxBranchInstructions())
    504     MadeChange = true;
    505 
    506   // After a while, this might be made debug-only, but it is not expensive.
    507   verify();
    508 
    509   DEBUG(dbgs() << "  Basic blocks after relaxation\n");
    510   DEBUG(dbgs() << '\n'; dumpBBs());
    511 
    512   BlockInfo.clear();
    513 
    514   return MadeChange;
    515 }
    516 
    517 /// Returns an instance of the AArch64 Branch Relaxation pass.
    518 FunctionPass *llvm::createAArch64BranchRelaxation() {
    519   return new AArch64BranchRelaxation();
    520 }
    521