lib/Target/ARM64/ARM64BranchRelaxation.cpp

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