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