lib/Target/AArch64/AArch64BranchRelaxation.cpp

   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   MachineBasicBlock *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   MachineFunction::iterator MBBI = OrigBB;
 231   ++MBBI;
 232   MF->insert(MBBI, NewBB);
 233
 234   // Splice the instructions starting with MI over to NewBB.
 235   NewBB->splice(NewBB->end(), OrigBB, MI, OrigBB->end());
 236
 237   // Add an unconditional branch from OrigBB to NewBB.
 238   // Note the new unconditional branch is not being recorded.
 239   // There doesn't seem to be meaningful DebugInfo available; this doesn't
 240   // correspond to anything in the source.
 241   BuildMI(OrigBB, DebugLoc(), TII->get(AArch64::B)).addMBB(NewBB);
 242
 243   // Insert an entry into BlockInfo to align it properly with the block numbers.
 244   BlockInfo.insert(BlockInfo.begin() + NewBB->getNumber(), BasicBlockInfo());
 245
 246   // Figure out how large the OrigBB is.  As the first half of the original
 247   // block, it cannot contain a tablejump.  The size includes
 248   // the new jump we added.  (It should be possible to do this without
 249   // recounting everything, but it's very confusing, and this is rarely
 250   // executed.)
 251   computeBlockSize(*OrigBB);
 252
 253   // Figure out how large the NewMBB is.  As the second half of the original
 254   // block, it may contain a tablejump.
 255   computeBlockSize(*NewBB);
 256
 257   // All BBOffsets following these blocks must be modified.
 258   adjustBlockOffsets(*OrigBB);
 259
 260   ++NumSplit;
 261
 262   return NewBB;
 263 }
 264
 265 /// isBlockInRange - Returns true if the distance between specific MI and
 266 /// specific BB can fit in MI's displacement field.
 267 bool AArch64BranchRelaxation::isBlockInRange(MachineInstr *MI,
 268                                              MachineBasicBlock *DestBB,
 269                                              unsigned Bits) {
 270   unsigned MaxOffs = ((1 << (Bits - 1)) - 1) << 2;
 271   unsigned BrOffset = getInstrOffset(MI);
 272   unsigned DestOffset = BlockInfo[DestBB->getNumber()].Offset;
 273
 274   DEBUG(dbgs() << "Branch of destination BB#" << DestBB->getNumber()
 275                << " from BB#" << MI->getParent()->getNumber()
 276                << " max delta=" << MaxOffs << " from " << getInstrOffset(MI)
 277                << " to " << DestOffset << " offset "
 278                << int(DestOffset - BrOffset) << "\t" << *MI);
 279
 280   // Branch before the Dest.
 281   if (BrOffset <= DestOffset)
 282     return (DestOffset - BrOffset <= MaxOffs);
 283   return (BrOffset - DestOffset <= MaxOffs);
 284 }
 285
 286 static bool isConditionalBranch(unsigned Opc) {
 287   switch (Opc) {
 288   default:
 289     return false;
 290   case AArch64::TBZW:
 291   case AArch64::TBNZW:
 292   case AArch64::TBZX:
 293   case AArch64::TBNZX:
 294   case AArch64::CBZW:
 295   case AArch64::CBNZW:
 296   case AArch64::CBZX:
 297   case AArch64::CBNZX:
 298   case AArch64::Bcc:
 299     return true;
 300   }
 301 }
 302
 303 static MachineBasicBlock *getDestBlock(MachineInstr *MI) {
 304   switch (MI->getOpcode()) {
 305   default:
 306     llvm_unreachable("unexpected opcode!");
 307   case AArch64::TBZW:
 308   case AArch64::TBNZW:
 309   case AArch64::TBZX:
 310   case AArch64::TBNZX:
 311     return MI->getOperand(2).getMBB();
 312   case AArch64::CBZW:
 313   case AArch64::CBNZW:
 314   case AArch64::CBZX:
 315   case AArch64::CBNZX:
 316   case AArch64::Bcc:
 317     return MI->getOperand(1).getMBB();
 318   }
 319 }
 320
 321 static unsigned getOppositeConditionOpcode(unsigned Opc) {
 322   switch (Opc) {
 323   default:
 324     llvm_unreachable("unexpected opcode!");
 325   case AArch64::TBNZW:   return AArch64::TBZW;
 326   case AArch64::TBNZX:   return AArch64::TBZX;
 327   case AArch64::TBZW:    return AArch64::TBNZW;
 328   case AArch64::TBZX:    return AArch64::TBNZX;
 329   case AArch64::CBNZW:   return AArch64::CBZW;
 330   case AArch64::CBNZX:   return AArch64::CBZX;
 331   case AArch64::CBZW:    return AArch64::CBNZW;
 332   case AArch64::CBZX:    return AArch64::CBNZX;
 333   case AArch64::Bcc:     return AArch64::Bcc; // Condition is an operand for Bcc.
 334   }
 335 }
 336
 337 static unsigned getBranchDisplacementBits(unsigned Opc) {
 338   switch (Opc) {
 339   default:
 340     llvm_unreachable("unexpected opcode!");
 341   case AArch64::TBNZW:
 342   case AArch64::TBZW:
 343   case AArch64::TBNZX:
 344   case AArch64::TBZX:
 345     return TBZDisplacementBits;
 346   case AArch64::CBNZW:
 347   case AArch64::CBZW:
 348   case AArch64::CBNZX:
 349   case AArch64::CBZX:
 350     return CBZDisplacementBits;
 351   case AArch64::Bcc:
 352     return BCCDisplacementBits;
 353   }
 354 }
 355
 356 static inline void invertBccCondition(MachineInstr *MI) {
 357   assert(MI->getOpcode() == AArch64::Bcc && "Unexpected opcode!");
 358   AArch64CC::CondCode CC = (AArch64CC::CondCode)MI->getOperand(0).getImm();
 359   CC = AArch64CC::getInvertedCondCode(CC);
 360   MI->getOperand(0).setImm((int64_t)CC);
 361 }
 362
 363 /// fixupConditionalBranch - Fix up a conditional branch whose destination is
 364 /// too far away to fit in its displacement field. It is converted to an inverse
 365 /// conditional branch + an unconditional branch to the destination.
 366 bool AArch64BranchRelaxation::fixupConditionalBranch(MachineInstr *MI) {
 367   MachineBasicBlock *DestBB = getDestBlock(MI);
 368
 369   // Add an unconditional branch to the destination and invert the branch
 370   // condition to jump over it:
 371   // tbz L1
 372   // =>
 373   // tbnz L2
 374   // b   L1
 375   // L2:
 376
 377   // If the branch is at the end of its MBB and that has a fall-through block,
 378   // direct the updated conditional branch to the fall-through block. Otherwise,
 379   // split the MBB before the next instruction.
 380   MachineBasicBlock *MBB = MI->getParent();
 381   MachineInstr *BMI = &MBB->back();
 382   bool NeedSplit = (BMI != MI) || !BBHasFallthrough(MBB);
 383
 384   if (BMI != MI) {
 385     if (std::next(MachineBasicBlock::iterator(MI)) ==
 386             std::prev(MBB->getLastNonDebugInstr()) &&
 387         BMI->getOpcode() == AArch64::B) {
 388       // Last MI in the BB is an unconditional branch. Can we simply invert the
 389       // condition and swap destinations:
 390       // beq L1
 391       // b   L2
 392       // =>
 393       // bne L2
 394       // b   L1
 395       MachineBasicBlock *NewDest = BMI->getOperand(0).getMBB();
 396       if (isBlockInRange(MI, NewDest,
 397                          getBranchDisplacementBits(MI->getOpcode()))) {
 398         DEBUG(dbgs() << "  Invert condition and swap its destination with "
 399                      << *BMI);
 400         BMI->getOperand(0).setMBB(DestBB);
 401         unsigned OpNum = (MI->getOpcode() == AArch64::TBZW ||
 402                           MI->getOpcode() == AArch64::TBNZW ||
 403                           MI->getOpcode() == AArch64::TBZX ||
 404                           MI->getOpcode() == AArch64::TBNZX)
 405                              ? 2
 406                              : 1;
 407         MI->getOperand(OpNum).setMBB(NewDest);
 408         MI->setDesc(TII->get(getOppositeConditionOpcode(MI->getOpcode())));
 409         if (MI->getOpcode() == AArch64::Bcc)
 410           invertBccCondition(MI);
 411         return true;
 412       }
 413     }
 414   }
 415
 416   if (NeedSplit) {
 417     // Analyze the branch so we know how to update the successor lists.
 418     MachineBasicBlock *TBB, *FBB;
 419     SmallVector<MachineOperand, 2> Cond;
 420     TII->AnalyzeBranch(*MBB, TBB, FBB, Cond, false);
 421
 422     MachineBasicBlock *NewBB = splitBlockBeforeInstr(MI);
 423     // No need for the branch to the next block. We're adding an unconditional
 424     // branch to the destination.
 425     int delta = TII->GetInstSizeInBytes(&MBB->back());
 426     BlockInfo[MBB->getNumber()].Size -= delta;
 427     MBB->back().eraseFromParent();
 428     // BlockInfo[SplitBB].Offset is wrong temporarily, fixed below
 429
 430     // Update the successor lists according to the transformation to follow.
 431     // Do it here since if there's no split, no update is needed.
 432     MBB->replaceSuccessor(FBB, NewBB);
 433     NewBB->addSuccessor(FBB);
 434   }
 435   MachineBasicBlock *NextBB = std::next(MachineFunction::iterator(MBB));
 436
 437   DEBUG(dbgs() << "  Insert B to BB#" << DestBB->getNumber()
 438                << ", invert condition and change dest. to BB#"
 439                << NextBB->getNumber() << "\n");
 440
 441   // Insert a new conditional branch and a new unconditional branch.
 442   MachineInstrBuilder MIB = BuildMI(
 443       MBB, DebugLoc(), TII->get(getOppositeConditionOpcode(MI->getOpcode())))
 444                                 .addOperand(MI->getOperand(0));
 445   if (MI->getOpcode() == AArch64::TBZW || MI->getOpcode() == AArch64::TBNZW ||
 446       MI->getOpcode() == AArch64::TBZX || MI->getOpcode() == AArch64::TBNZX)
 447     MIB.addOperand(MI->getOperand(1));
 448   if (MI->getOpcode() == AArch64::Bcc)
 449     invertBccCondition(MIB);
 450   MIB.addMBB(NextBB);
 451   BlockInfo[MBB->getNumber()].Size += TII->GetInstSizeInBytes(&MBB->back());
 452   BuildMI(MBB, DebugLoc(), TII->get(AArch64::B)).addMBB(DestBB);
 453   BlockInfo[MBB->getNumber()].Size += TII->GetInstSizeInBytes(&MBB->back());
 454
 455   // Remove the old conditional branch.  It may or may not still be in MBB.
 456   BlockInfo[MI->getParent()->getNumber()].Size -= TII->GetInstSizeInBytes(MI);
 457   MI->eraseFromParent();
 458
 459   // Finally, keep the block offsets up to date.
 460   adjustBlockOffsets(*MBB);
 461   return true;
 462 }
 463
 464 bool AArch64BranchRelaxation::relaxBranchInstructions() {
 465   bool Changed = false;
 466   // Relaxing branches involves creating new basic blocks, so re-eval
 467   // end() for termination.
 468   for (auto &MBB : *MF) {
 469     MachineInstr *MI = MBB.getFirstTerminator();
 470     if (isConditionalBranch(MI->getOpcode()) &&
 471         !isBlockInRange(MI, getDestBlock(MI),
 472                         getBranchDisplacementBits(MI->getOpcode()))) {
 473       fixupConditionalBranch(MI);
 474       ++NumRelaxed;
 475       Changed = true;
 476     }
 477   }
 478   return Changed;
 479 }
 480
 481 bool AArch64BranchRelaxation::runOnMachineFunction(MachineFunction &mf) {
 482   MF = &mf;
 483
 484   // If the pass is disabled, just bail early.
 485   if (!BranchRelaxation)
 486     return false;
 487
 488   DEBUG(dbgs() << "***** AArch64BranchRelaxation *****\n");
 489
 490   TII = (const AArch64InstrInfo *)MF->getSubtarget().getInstrInfo();
 491
 492   // Renumber all of the machine basic blocks in the function, guaranteeing that
 493   // the numbers agree with the position of the block in the function.
 494   MF->RenumberBlocks();
 495
 496   // Do the initial scan of the function, building up information about the
 497   // sizes of each block.
 498   scanFunction();
 499
 500   DEBUG(dbgs() << "  Basic blocks before relaxation\n");
 501   DEBUG(dumpBBs());
 502
 503   bool MadeChange = false;
 504   while (relaxBranchInstructions())
 505     MadeChange = true;
 506
 507   // After a while, this might be made debug-only, but it is not expensive.
 508   verify();
 509
 510   DEBUG(dbgs() << "  Basic blocks after relaxation\n");
 511   DEBUG(dbgs() << '\n'; dumpBBs());
 512
 513   BlockInfo.clear();
 514
 515   return MadeChange;
 516 }
 517
 518 /// createAArch64BranchRelaxation - returns an instance of the constpool
 519 /// island pass.
 520 FunctionPass *llvm::createAArch64BranchRelaxation() {
 521   return new AArch64BranchRelaxation();
 522 }