1 //===-- BranchRelaxation.cpp ----------------------------------------------===//
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 #include "llvm/CodeGen/Passes.h"
11 #include "llvm/ADT/SmallVector.h"
12 #include "llvm/ADT/Statistic.h"
13 #include "llvm/CodeGen/LivePhysRegs.h"
14 #include "llvm/CodeGen/MachineFunctionPass.h"
15 #include "llvm/CodeGen/RegisterScavenging.h"
16 #include "llvm/Target/TargetInstrInfo.h"
17 #include "llvm/Target/TargetSubtargetInfo.h"
18 #include "llvm/Support/Debug.h"
19 #include "llvm/Support/Format.h"
20 #include "llvm/Support/raw_ostream.h"
24 #define DEBUG_TYPE "branch-relaxation"
26 STATISTIC(NumSplit, "Number of basic blocks split");
27 STATISTIC(NumConditionalRelaxed, "Number of conditional branches relaxed");
28 STATISTIC(NumUnconditionalRelaxed, "Number of unconditional branches relaxed");
30 #define BRANCH_RELAX_NAME "Branch relaxation pass"
33 class BranchRelaxation : public MachineFunctionPass {
34 /// BasicBlockInfo - Information about the offset and size of a single
36 struct BasicBlockInfo {
37 /// Offset - Distance from the beginning of the function to the beginning
38 /// of this basic block.
40 /// The offset is always aligned as required by the basic block.
43 /// Size - Size of the basic block in bytes. If the block contains
44 /// inline assembly, this is a worst case estimate.
46 /// The size does not include any alignment padding whether from the
47 /// beginning of the block, or from an aligned jump table at the end.
50 BasicBlockInfo() : Offset(0), Size(0) {}
52 /// Compute the offset immediately following this block. \p MBB is the next
54 unsigned postOffset(const MachineBasicBlock &MBB) const {
55 unsigned PO = Offset + Size;
56 unsigned Align = MBB.getAlignment();
60 unsigned AlignAmt = 1 << Align;
61 unsigned ParentAlign = MBB.getParent()->getAlignment();
62 if (Align <= ParentAlign)
63 return PO + OffsetToAlignment(PO, AlignAmt);
65 // The alignment of this MBB is larger than the function's alignment, so we
66 // can't tell whether or not it will insert nops. Assume that it will.
67 return PO + AlignAmt + OffsetToAlignment(PO, AlignAmt);
71 SmallVector<BasicBlockInfo, 16> BlockInfo;
72 std::unique_ptr<RegScavenger> RS;
73 LivePhysRegs LiveRegs;
76 const TargetRegisterInfo *TRI;
77 const TargetInstrInfo *TII;
79 bool relaxBranchInstructions();
82 MachineBasicBlock *createNewBlockAfter(MachineBasicBlock &BB);
84 MachineBasicBlock *splitBlockBeforeInstr(MachineInstr &MI,
85 MachineBasicBlock *DestBB);
86 void adjustBlockOffsets(MachineBasicBlock &MBB);
87 bool isBlockInRange(const MachineInstr &MI, const MachineBasicBlock &BB) const;
89 bool fixupConditionalBranch(MachineInstr &MI);
90 bool fixupUnconditionalBranch(MachineInstr &MI);
91 uint64_t computeBlockSize(const MachineBasicBlock &MBB) const;
92 unsigned getInstrOffset(const MachineInstr &MI) const;
98 BranchRelaxation() : MachineFunctionPass(ID) { }
100 bool runOnMachineFunction(MachineFunction &MF) override;
102 StringRef getPassName() const override {
103 return BRANCH_RELAX_NAME;
109 char BranchRelaxation::ID = 0;
110 char &llvm::BranchRelaxationPassID = BranchRelaxation::ID;
112 INITIALIZE_PASS(BranchRelaxation, DEBUG_TYPE, BRANCH_RELAX_NAME, false, false)
114 /// verify - check BBOffsets, BBSizes, alignment of islands
115 void BranchRelaxation::verify() {
117 unsigned PrevNum = MF->begin()->getNumber();
118 for (MachineBasicBlock &MBB : *MF) {
119 unsigned Align = MBB.getAlignment();
120 unsigned Num = MBB.getNumber();
121 assert(BlockInfo[Num].Offset % (1u << Align) == 0);
122 assert(!Num || BlockInfo[PrevNum].postOffset(MBB) <= BlockInfo[Num].Offset);
123 assert(BlockInfo[Num].Size == computeBlockSize(MBB));
129 /// print block size and offset information - debugging
130 void BranchRelaxation::dumpBBs() {
131 for (auto &MBB : *MF) {
132 const BasicBlockInfo &BBI = BlockInfo[MBB.getNumber()];
133 dbgs() << format("BB#%u\toffset=%08x\t", MBB.getNumber(), BBI.Offset)
134 << format("size=%#x\n", BBI.Size);
138 /// scanFunction - Do the initial scan of the function, building up
139 /// information about each block.
140 void BranchRelaxation::scanFunction() {
142 BlockInfo.resize(MF->getNumBlockIDs());
144 // First thing, compute the size of all basic blocks, and see if the function
145 // has any inline assembly in it. If so, we have to be conservative about
146 // alignment assumptions, as we don't know for sure the size of any
147 // instructions in the inline assembly.
148 for (MachineBasicBlock &MBB : *MF)
149 BlockInfo[MBB.getNumber()].Size = computeBlockSize(MBB);
151 // Compute block offsets and known bits.
152 adjustBlockOffsets(*MF->begin());
155 /// computeBlockSize - Compute the size for MBB.
156 uint64_t BranchRelaxation::computeBlockSize(const MachineBasicBlock &MBB) const {
158 for (const MachineInstr &MI : MBB)
159 Size += TII->getInstSizeInBytes(MI);
163 /// getInstrOffset - Return the current offset of the specified machine
164 /// instruction from the start of the function. This offset changes as stuff is
165 /// moved around inside the function.
166 unsigned BranchRelaxation::getInstrOffset(const MachineInstr &MI) const {
167 const MachineBasicBlock *MBB = MI.getParent();
169 // The offset is composed of two things: the sum of the sizes of all MBB's
170 // before this instruction's block, and the offset from the start of the block
172 unsigned Offset = BlockInfo[MBB->getNumber()].Offset;
174 // Sum instructions before MI in MBB.
175 for (MachineBasicBlock::const_iterator I = MBB->begin(); &*I != &MI; ++I) {
176 assert(I != MBB->end() && "Didn't find MI in its own basic block?");
177 Offset += TII->getInstSizeInBytes(*I);
183 void BranchRelaxation::adjustBlockOffsets(MachineBasicBlock &Start) {
184 unsigned PrevNum = Start.getNumber();
185 for (auto &MBB : make_range(MachineFunction::iterator(Start), MF->end())) {
186 unsigned Num = MBB.getNumber();
187 if (!Num) // block zero is never changed from offset zero.
189 // Get the offset and known bits at the end of the layout predecessor.
190 // Include the alignment of the current block.
191 BlockInfo[Num].Offset = BlockInfo[PrevNum].postOffset(MBB);
197 /// Insert a new empty basic block and insert it after \BB
198 MachineBasicBlock *BranchRelaxation::createNewBlockAfter(MachineBasicBlock &BB) {
199 // Create a new MBB for the code after the OrigBB.
200 MachineBasicBlock *NewBB =
201 MF->CreateMachineBasicBlock(BB.getBasicBlock());
202 MF->insert(++BB.getIterator(), NewBB);
204 // Insert an entry into BlockInfo to align it properly with the block numbers.
205 BlockInfo.insert(BlockInfo.begin() + NewBB->getNumber(), BasicBlockInfo());
210 /// Split the basic block containing MI into two blocks, which are joined by
211 /// an unconditional branch. Update data structures and renumber blocks to
212 /// account for this change and returns the newly created block.
213 MachineBasicBlock *BranchRelaxation::splitBlockBeforeInstr(MachineInstr &MI,
214 MachineBasicBlock *DestBB) {
215 MachineBasicBlock *OrigBB = MI.getParent();
217 // Create a new MBB for the code after the OrigBB.
218 MachineBasicBlock *NewBB =
219 MF->CreateMachineBasicBlock(OrigBB->getBasicBlock());
220 MF->insert(++OrigBB->getIterator(), NewBB);
222 // Splice the instructions starting with MI over to NewBB.
223 NewBB->splice(NewBB->end(), OrigBB, MI.getIterator(), OrigBB->end());
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 TII->insertUnconditionalBranch(*OrigBB, NewBB, DebugLoc());
231 // Insert an entry into BlockInfo to align it properly with the block numbers.
232 BlockInfo.insert(BlockInfo.begin() + NewBB->getNumber(), BasicBlockInfo());
235 NewBB->transferSuccessors(OrigBB);
236 OrigBB->addSuccessor(NewBB);
237 OrigBB->addSuccessor(DestBB);
239 // Cleanup potential unconditional branch to successor block.
240 // Note that updateTerminator may change the size of the blocks.
241 NewBB->updateTerminator();
242 OrigBB->updateTerminator();
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
249 BlockInfo[OrigBB->getNumber()].Size = computeBlockSize(*OrigBB);
251 // Figure out how large the NewMBB is. As the second half of the original
252 // block, it may contain a tablejump.
253 BlockInfo[NewBB->getNumber()].Size = computeBlockSize(*NewBB);
255 // All BBOffsets following these blocks must be modified.
256 adjustBlockOffsets(*OrigBB);
258 // Need to fix live-in lists if we track liveness.
259 if (TRI->trackLivenessAfterRegAlloc(*MF))
260 computeLiveIns(LiveRegs, *TRI, *NewBB);
267 /// isBlockInRange - Returns true if the distance between specific MI and
268 /// specific BB can fit in MI's displacement field.
269 bool BranchRelaxation::isBlockInRange(
270 const MachineInstr &MI, const MachineBasicBlock &DestBB) const {
271 int64_t BrOffset = getInstrOffset(MI);
272 int64_t DestOffset = BlockInfo[DestBB.getNumber()].Offset;
274 if (TII->isBranchOffsetInRange(MI.getOpcode(), DestOffset - BrOffset))
278 dbgs() << "Out of range branch to destination BB#" << DestBB.getNumber()
279 << " from BB#" << MI.getParent()->getNumber()
280 << " to " << DestOffset
281 << " offset " << DestOffset - BrOffset
288 /// fixupConditionalBranch - Fix up a conditional branch whose destination is
289 /// too far away to fit in its displacement field. It is converted to an inverse
290 /// conditional branch + an unconditional branch to the destination.
291 bool BranchRelaxation::fixupConditionalBranch(MachineInstr &MI) {
292 DebugLoc DL = MI.getDebugLoc();
293 MachineBasicBlock *MBB = MI.getParent();
294 MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
295 SmallVector<MachineOperand, 4> Cond;
297 bool Fail = TII->analyzeBranch(*MBB, TBB, FBB, Cond);
298 assert(!Fail && "branches to be relaxed must be analyzable");
301 // Add an unconditional branch to the destination and invert the branch
302 // condition to jump over it:
309 if (FBB && isBlockInRange(MI, *FBB)) {
310 // Last MI in the BB is an unconditional branch. We can simply invert the
311 // condition and swap destinations:
317 DEBUG(dbgs() << " Invert condition and swap "
318 "its destination with " << MBB->back());
320 TII->reverseBranchCondition(Cond);
321 int OldSize = 0, NewSize = 0;
322 TII->removeBranch(*MBB, &OldSize);
323 TII->insertBranch(*MBB, FBB, TBB, Cond, DL, &NewSize);
325 BlockInfo[MBB->getNumber()].Size += (NewSize - OldSize);
328 // We need to split the basic block here to obtain two long-range
329 // unconditional branches.
330 auto &NewBB = *MF->CreateMachineBasicBlock(MBB->getBasicBlock());
331 MF->insert(++MBB->getIterator(), &NewBB);
333 // Insert an entry into BlockInfo to align it properly with the block
335 BlockInfo.insert(BlockInfo.begin() + NewBB.getNumber(), BasicBlockInfo());
337 unsigned &NewBBSize = BlockInfo[NewBB.getNumber()].Size;
339 TII->insertUnconditionalBranch(NewBB, FBB, DL, &NewBrSize);
340 NewBBSize += NewBrSize;
342 // Update the successor lists according to the transformation to follow.
343 // Do it here since if there's no split, no update is needed.
344 MBB->replaceSuccessor(FBB, &NewBB);
345 NewBB.addSuccessor(FBB);
348 // We now have an appropriate fall-through block in place (either naturally or
349 // just created), so we can invert the condition.
350 MachineBasicBlock &NextBB = *std::next(MachineFunction::iterator(MBB));
352 DEBUG(dbgs() << " Insert B to BB#" << TBB->getNumber()
353 << ", invert condition and change dest. to BB#"
354 << NextBB.getNumber() << '\n');
356 unsigned &MBBSize = BlockInfo[MBB->getNumber()].Size;
358 // Insert a new conditional branch and a new unconditional branch.
360 TII->reverseBranchCondition(Cond);
361 TII->removeBranch(*MBB, &RemovedSize);
362 MBBSize -= RemovedSize;
365 TII->insertBranch(*MBB, &NextBB, TBB, Cond, DL, &AddedSize);
366 MBBSize += AddedSize;
368 // Finally, keep the block offsets up to date.
369 adjustBlockOffsets(*MBB);
373 bool BranchRelaxation::fixupUnconditionalBranch(MachineInstr &MI) {
374 MachineBasicBlock *MBB = MI.getParent();
376 unsigned OldBrSize = TII->getInstSizeInBytes(MI);
377 MachineBasicBlock *DestBB = TII->getBranchDestBlock(MI);
379 int64_t DestOffset = BlockInfo[DestBB->getNumber()].Offset;
380 int64_t SrcOffset = getInstrOffset(MI);
382 assert(!TII->isBranchOffsetInRange(MI.getOpcode(), DestOffset - SrcOffset));
384 BlockInfo[MBB->getNumber()].Size -= OldBrSize;
386 MachineBasicBlock *BranchBB = MBB;
388 // If this was an expanded conditional branch, there is already a single
389 // unconditional branch in a block.
391 BranchBB = createNewBlockAfter(*MBB);
394 for (const MachineBasicBlock *Succ : MBB->successors()) {
395 for (const MachineBasicBlock::RegisterMaskPair &LiveIn : Succ->liveins())
396 BranchBB->addLiveIn(LiveIn);
399 BranchBB->sortUniqueLiveIns();
400 BranchBB->addSuccessor(DestBB);
401 MBB->replaceSuccessor(DestBB, BranchBB);
404 DebugLoc DL = MI.getDebugLoc();
405 MI.eraseFromParent();
406 BlockInfo[BranchBB->getNumber()].Size += TII->insertIndirectBranch(
407 *BranchBB, *DestBB, DL, DestOffset - SrcOffset, RS.get());
409 adjustBlockOffsets(*MBB);
413 bool BranchRelaxation::relaxBranchInstructions() {
414 bool Changed = false;
416 // Relaxing branches involves creating new basic blocks, so re-eval
417 // end() for termination.
418 for (MachineFunction::iterator I = MF->begin(); I != MF->end(); ++I) {
419 MachineBasicBlock &MBB = *I;
422 MachineBasicBlock::iterator Last = MBB.getLastNonDebugInstr();
423 if (Last == MBB.end())
426 // Expand the unconditional branch first if necessary. If there is a
427 // conditional branch, this will end up changing the branch destination of
428 // it to be over the newly inserted indirect branch block, which may avoid
429 // the need to try expanding the conditional branch first, saving an extra
431 if (Last->isUnconditionalBranch()) {
432 // Unconditional branch destination might be unanalyzable, assume these
434 if (MachineBasicBlock *DestBB = TII->getBranchDestBlock(*Last)) {
435 if (!isBlockInRange(*Last, *DestBB)) {
436 fixupUnconditionalBranch(*Last);
437 ++NumUnconditionalRelaxed;
443 // Loop over the conditional branches.
444 MachineBasicBlock::iterator Next;
445 for (MachineBasicBlock::iterator J = MBB.getFirstTerminator();
446 J != MBB.end(); J = Next) {
448 MachineInstr &MI = *J;
450 if (MI.isConditionalBranch()) {
451 MachineBasicBlock *DestBB = TII->getBranchDestBlock(MI);
452 if (!isBlockInRange(MI, *DestBB)) {
453 if (Next != MBB.end() && Next->isConditionalBranch()) {
454 // If there are multiple conditional branches, this isn't an
455 // analyzable block. Split later terminators into a new block so
456 // each one will be analyzable.
458 splitBlockBeforeInstr(*Next, DestBB);
460 fixupConditionalBranch(MI);
461 ++NumConditionalRelaxed;
466 // This may have modified all of the terminators, so start over.
467 Next = MBB.getFirstTerminator();
476 bool BranchRelaxation::runOnMachineFunction(MachineFunction &mf) {
479 DEBUG(dbgs() << "***** BranchRelaxation *****\n");
481 const TargetSubtargetInfo &ST = MF->getSubtarget();
482 TII = ST.getInstrInfo();
484 TRI = ST.getRegisterInfo();
485 if (TRI->trackLivenessAfterRegAlloc(*MF))
486 RS.reset(new RegScavenger());
488 // Renumber all of the machine basic blocks in the function, guaranteeing that
489 // the numbers agree with the position of the block in the function.
490 MF->RenumberBlocks();
492 // Do the initial scan of the function, building up information about the
493 // sizes of each block.
496 DEBUG(dbgs() << " Basic blocks before relaxation\n"; dumpBBs(););
498 bool MadeChange = false;
499 while (relaxBranchInstructions())
502 // After a while, this might be made debug-only, but it is not expensive.
505 DEBUG(dbgs() << " Basic blocks after relaxation\n\n"; dumpBBs());