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 (auto &MBB : *MF) { 467 MachineInstr *MI = MBB.getFirstTerminator(); 468 if (isConditionalBranch(MI->getOpcode()) && 469 !isBlockInRange(MI, getDestBlock(MI), 470 getBranchDisplacementBits(MI->getOpcode()))) { 471 fixupConditionalBranch(MI); 472 ++NumRelaxed; 473 Changed = true; 474 } 475 } 476 return Changed; 477 } 478 479 bool AArch64BranchRelaxation::runOnMachineFunction(MachineFunction &mf) { 480 MF = &mf; 481 482 // If the pass is disabled, just bail early. 483 if (!BranchRelaxation) 484 return false; 485 486 DEBUG(dbgs() << "***** AArch64BranchRelaxation *****\n"); 487 488 TII = (const AArch64InstrInfo *)MF->getSubtarget().getInstrInfo(); 489 490 // Renumber all of the machine basic blocks in the function, guaranteeing that 491 // the numbers agree with the position of the block in the function. 492 MF->RenumberBlocks(); 493 494 // Do the initial scan of the function, building up information about the 495 // sizes of each block. 496 scanFunction(); 497 498 DEBUG(dbgs() << " Basic blocks before relaxation\n"); 499 DEBUG(dumpBBs()); 500 501 bool MadeChange = false; 502 while (relaxBranchInstructions()) 503 MadeChange = true; 504 505 // After a while, this might be made debug-only, but it is not expensive. 506 verify(); 507 508 DEBUG(dbgs() << " Basic blocks after relaxation\n"); 509 DEBUG(dbgs() << '\n'; dumpBBs()); 510 511 BlockInfo.clear(); 512 513 return MadeChange; 514 } 515 516 /// createAArch64BranchRelaxation - returns an instance of the constpool 517 /// island pass. 518 FunctionPass *llvm::createAArch64BranchRelaxation() { 519 return new AArch64BranchRelaxation(); 520 } 521