1 //===-- AArch64BranchRelaxation.cpp - AArch64 branch relaxation -----------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 //===----------------------------------------------------------------------===//
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"
27 #define DEBUG_TYPE "aarch64-branch-relax"
30 BranchRelaxation("aarch64-branch-relax", cl::Hidden, cl::init(true),
31 cl::desc("Relax out of range conditional branches"));
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)"));
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)"));
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)"));
45 STATISTIC(NumSplit, "Number of basic blocks split");
46 STATISTIC(NumRelaxed, "Number of conditional branches relaxed");
49 void initializeAArch64BranchRelaxationPass(PassRegistry &);
52 #define AARCH64_BR_RELAX_NAME "AArch64 branch relaxation pass"
55 class AArch64BranchRelaxation : public MachineFunctionPass {
56 /// BasicBlockInfo - Information about the offset and size of a single
58 struct BasicBlockInfo {
59 /// Offset - Distance from the beginning of the function to the beginning
60 /// of this basic block.
62 /// The offset is always aligned as required by the basic block.
65 /// Size - Size of the basic block in bytes. If the block contains
66 /// inline assembly, this is a worst case estimate.
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.
72 BasicBlockInfo() : Offset(0), Size(0) {}
74 /// Compute the offset immediately following this block. If LogAlign is
75 /// specified, return the offset the successor block will get if it has
77 unsigned postOffset(unsigned LogAlign = 0) const {
78 unsigned PO = Offset + Size;
79 unsigned Align = 1 << LogAlign;
80 return (PO + Align - 1) / Align * Align;
84 SmallVector<BasicBlockInfo, 16> BlockInfo;
87 const AArch64InstrInfo *TII;
89 bool relaxBranchInstructions();
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;
102 AArch64BranchRelaxation() : MachineFunctionPass(ID) {
103 initializeAArch64BranchRelaxationPass(*PassRegistry::getPassRegistry());
106 bool runOnMachineFunction(MachineFunction &MF) override;
108 const char *getPassName() const override {
109 return AARCH64_BR_RELAX_NAME;
112 char AArch64BranchRelaxation::ID = 0;
115 INITIALIZE_PASS(AArch64BranchRelaxation, "aarch64-branch-relax",
116 AARCH64_BR_RELAX_NAME, false, false)
118 /// verify - check BBOffsets, BBSizes, alignment of islands
119 void AArch64BranchRelaxation::verify() {
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);
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);
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())
151 for (MachineBasicBlock *S : MBB->successors())
158 /// scanFunction - Do the initial scan of the function, building up
159 /// information about each block.
160 void AArch64BranchRelaxation::scanFunction() {
162 BlockInfo.resize(MF->getNumBlockIDs());
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);
171 // Compute block offsets and known bits.
172 adjustBlockOffsets(*MF->begin());
175 /// computeBlockSize - Compute the size for MBB.
176 /// This function updates BlockInfo directly.
177 void AArch64BranchRelaxation::computeBlockSize(const MachineBasicBlock &MBB) {
179 for (const MachineInstr &MI : MBB)
180 Size += TII->GetInstSizeInBytes(&MI);
181 BlockInfo[MBB.getNumber()].Size = Size;
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();
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
193 unsigned Offset = BlockInfo[MBB->getNumber()].Offset;
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);
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.
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);
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.
224 AArch64BranchRelaxation::splitBlockBeforeInstr(MachineInstr *MI) {
225 MachineBasicBlock *OrigBB = MI->getParent();
227 // Create a new MBB for the code after the OrigBB.
228 MachineBasicBlock *NewBB =
229 MF->CreateMachineBasicBlock(OrigBB->getBasicBlock());
230 MachineFunction::iterator MBBI = OrigBB;
232 MF->insert(MBBI, NewBB);
234 // Splice the instructions starting with MI over to NewBB.
235 NewBB->splice(NewBB->end(), OrigBB, MI, OrigBB->end());
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);
243 // Insert an entry into BlockInfo to align it properly with the block numbers.
244 BlockInfo.insert(BlockInfo.begin() + NewBB->getNumber(), BasicBlockInfo());
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
251 computeBlockSize(*OrigBB);
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);
257 // All BBOffsets following these blocks must be modified.
258 adjustBlockOffsets(*OrigBB);
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,
270 unsigned MaxOffs = ((1 << (Bits - 1)) - 1) << 2;
271 unsigned BrOffset = getInstrOffset(MI);
272 unsigned DestOffset = BlockInfo[DestBB->getNumber()].Offset;
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);
280 // Branch before the Dest.
281 if (BrOffset <= DestOffset)
282 return (DestOffset - BrOffset <= MaxOffs);
283 return (BrOffset - DestOffset <= MaxOffs);
286 static bool isConditionalBranch(unsigned Opc) {
303 static MachineBasicBlock *getDestBlock(MachineInstr *MI) {
304 switch (MI->getOpcode()) {
306 llvm_unreachable("unexpected opcode!");
311 return MI->getOperand(2).getMBB();
317 return MI->getOperand(1).getMBB();
321 static unsigned getOppositeConditionOpcode(unsigned Opc) {
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.
337 static unsigned getBranchDisplacementBits(unsigned Opc) {
340 llvm_unreachable("unexpected opcode!");
345 return TBZDisplacementBits;
350 return CBZDisplacementBits;
352 return BCCDisplacementBits;
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);
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);
369 // Add an unconditional branch to the destination and invert the branch
370 // condition to jump over it:
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);
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:
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 "
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)
407 MI->getOperand(OpNum).setMBB(NewDest);
408 MI->setDesc(TII->get(getOppositeConditionOpcode(MI->getOpcode())));
409 if (MI->getOpcode() == AArch64::Bcc)
410 invertBccCondition(MI);
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);
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
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);
435 MachineBasicBlock *NextBB = std::next(MachineFunction::iterator(MBB));
437 DEBUG(dbgs() << " Insert B to BB#" << DestBB->getNumber()
438 << ", invert condition and change dest. to BB#"
439 << NextBB->getNumber() << "\n");
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);
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());
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();
459 // Finally, keep the block offsets up to date.
460 adjustBlockOffsets(*MBB);
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);
481 bool AArch64BranchRelaxation::runOnMachineFunction(MachineFunction &mf) {
484 // If the pass is disabled, just bail early.
485 if (!BranchRelaxation)
488 DEBUG(dbgs() << "***** AArch64BranchRelaxation *****\n");
490 TII = (const AArch64InstrInfo *)MF->getSubtarget().getInstrInfo();
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();
496 // Do the initial scan of the function, building up information about the
497 // sizes of each block.
500 DEBUG(dbgs() << " Basic blocks before relaxation\n");
503 bool MadeChange = false;
504 while (relaxBranchInstructions())
507 // After a while, this might be made debug-only, but it is not expensive.
510 DEBUG(dbgs() << " Basic blocks after relaxation\n");
511 DEBUG(dbgs() << '\n'; dumpBBs());
518 /// createAArch64BranchRelaxation - returns an instance of the constpool
520 FunctionPass *llvm::createAArch64BranchRelaxation() {
521 return new AArch64BranchRelaxation();