1 //===-- ARM64BranchRelaxation.cpp - ARM64 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 //===----------------------------------------------------------------------===//
12 #define DEBUG_TYPE "arm64-branch-relax"
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"
28 BranchRelaxation("arm64-branch-relax", cl::Hidden, cl::init(true),
29 cl::desc("Relax out of range conditional branches"));
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)"));
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)"));
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)"));
43 STATISTIC(NumSplit, "Number of basic blocks split");
44 STATISTIC(NumRelaxed, "Number of conditional branches relaxed");
47 class ARM64BranchRelaxation : public MachineFunctionPass {
48 /// BasicBlockInfo - Information about the offset and size of a single
50 struct BasicBlockInfo {
51 /// Offset - Distance from the beginning of the function to the beginning
52 /// of this basic block.
54 /// The offset is always aligned as required by the basic block.
57 /// Size - Size of the basic block in bytes. If the block contains
58 /// inline assembly, this is a worst case estimate.
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.
64 BasicBlockInfo() : Offset(0), Size(0) {}
66 /// Compute the offset immediately following this block. If LogAlign is
67 /// specified, return the offset the successor block will get if it has
69 unsigned postOffset(unsigned LogAlign = 0) const {
70 unsigned PO = Offset + Size;
71 unsigned Align = 1 << LogAlign;
72 return (PO + Align - 1) / Align * Align;
76 SmallVector<BasicBlockInfo, 16> BlockInfo;
79 const ARM64InstrInfo *TII;
81 bool relaxBranchInstructions();
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;
94 ARM64BranchRelaxation() : MachineFunctionPass(ID) {}
96 virtual bool runOnMachineFunction(MachineFunction &MF);
98 virtual const char *getPassName() const {
99 return "ARM64 branch relaxation pass";
102 char ARM64BranchRelaxation::ID = 0;
105 /// verify - check BBOffsets, BBSizes, alignment of islands
106 void ARM64BranchRelaxation::verify() {
108 unsigned PrevNum = MF->begin()->getNumber();
109 for (MachineFunction::iterator MBBI = MF->begin(), E = MF->end(); MBBI != E;
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);
121 /// print block size and offset information - debugging
122 void ARM64BranchRelaxation::dumpBBs() {
123 for (MachineFunction::iterator MBBI = MF->begin(), E = MF->end(); MBBI != E;
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);
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())
140 MachineBasicBlock *NextBB = std::next(MBBI);
141 for (MachineBasicBlock::succ_iterator I = MBB->succ_begin(),
150 /// scanFunction - Do the initial scan of the function, building up
151 /// information about each block.
152 void ARM64BranchRelaxation::scanFunction() {
154 BlockInfo.resize(MF->getNumBlockIDs());
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)
163 // Compute block offsets and known bits.
164 adjustBlockOffsets(MF->begin());
167 /// computeBlockSize - Compute the size for MBB.
168 /// This function updates BlockInfo directly.
169 void ARM64BranchRelaxation::computeBlockSize(MachineBasicBlock *MBB) {
171 for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end(); I != E;
173 Size += TII->GetInstSizeInBytes(I);
174 BlockInfo[MBB->getNumber()].Size = Size;
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();
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
186 unsigned Offset = BlockInfo[MBB->getNumber()].Offset;
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);
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.
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);
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.
219 ARM64BranchRelaxation::splitBlockBeforeInstr(MachineInstr *MI) {
220 MachineBasicBlock *OrigBB = MI->getParent();
222 // Create a new MBB for the code after the OrigBB.
223 MachineBasicBlock *NewBB =
224 MF->CreateMachineBasicBlock(OrigBB->getBasicBlock());
225 MachineFunction::iterator MBBI = OrigBB;
227 MF->insert(MBBI, NewBB);
229 // Splice the instructions starting with MI over to NewBB.
230 NewBB->splice(NewBB->end(), OrigBB, MI, OrigBB->end());
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);
238 // Insert an entry into BlockInfo to align it properly with the block numbers.
239 BlockInfo.insert(BlockInfo.begin() + NewBB->getNumber(), BasicBlockInfo());
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
246 computeBlockSize(OrigBB);
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);
252 // All BBOffsets following these blocks must be modified.
253 adjustBlockOffsets(OrigBB);
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,
265 unsigned MaxOffs = ((1 << (Bits - 1)) - 1) << 2;
266 unsigned BrOffset = getInstrOffset(MI);
267 unsigned DestOffset = BlockInfo[DestBB->getNumber()].Offset;
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);
275 // Branch before the Dest.
276 if (BrOffset <= DestOffset)
277 return (DestOffset - BrOffset <= MaxOffs);
278 return (BrOffset - DestOffset <= MaxOffs);
281 static bool isConditionalBranch(unsigned Opc) {
296 static MachineBasicBlock *getDestBlock(MachineInstr *MI) {
297 switch (MI->getOpcode()) {
299 assert(0 && "unexpected opcode!");
302 return MI->getOperand(2).getMBB();
308 return MI->getOperand(1).getMBB();
312 static unsigned getOppositeConditionOpcode(unsigned Opc) {
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.
326 static unsigned getBranchDisplacementBits(unsigned Opc) {
329 assert(0 && "unexpected opcode!");
332 return TBZDisplacementBits;
337 return CBZDisplacementBits;
339 return BCCDisplacementBits;
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);
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);
356 // Add an unconditional branch to the destination and invert the branch
357 // condition to jump over it:
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);
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:
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 "
387 BMI->getOperand(0).setMBB(DestBB);
389 (MI->getOpcode() == ARM64::TBZ || MI->getOpcode() == ARM64::TBNZ)
392 MI->getOperand(OpNum).setMBB(NewDest);
393 MI->setDesc(TII->get(getOppositeConditionOpcode(MI->getOpcode())));
394 if (MI->getOpcode() == ARM64::Bcc)
395 invertBccCondition(MI);
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);
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
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);
420 MachineBasicBlock *NextBB = std::next(MachineFunction::iterator(MBB));
422 DEBUG(dbgs() << " Insert B to BB#" << DestBB->getNumber()
423 << ", invert condition and change dest. to BB#"
424 << NextBB->getNumber() << "\n");
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);
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());
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();
443 // Finally, keep the block offsets up to date.
444 adjustBlockOffsets(MBB);
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);
465 bool ARM64BranchRelaxation::runOnMachineFunction(MachineFunction &mf) {
468 // If the pass is disabled, just bail early.
469 if (!BranchRelaxation)
472 DEBUG(dbgs() << "***** ARM64BranchRelaxation *****\n");
474 TII = (const ARM64InstrInfo *)MF->getTarget().getInstrInfo();
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();
480 // Do the initial scan of the function, building up information about the
481 // sizes of each block.
484 DEBUG(dbgs() << " Basic blocks before relaxation\n");
487 bool MadeChange = false;
488 while (relaxBranchInstructions())
491 // After a while, this might be made debug-only, but it is not expensive.
494 DEBUG(dbgs() << " Basic blocks after relaxation\n");
495 DEBUG(dbgs() << '\n'; dumpBBs());
502 /// createARM64BranchRelaxation - returns an instance of the constpool
504 FunctionPass *llvm::createARM64BranchRelaxation() {
505 return new ARM64BranchRelaxation();