1 //===- BranchRelaxation.cpp -----------------------------------------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8
9 #include "llvm/ADT/SmallVector.h"
10 #include "llvm/ADT/Statistic.h"
11 #include "llvm/CodeGen/LivePhysRegs.h"
12 #include "llvm/CodeGen/MachineBasicBlock.h"
13 #include "llvm/CodeGen/MachineFunction.h"
14 #include "llvm/CodeGen/MachineFunctionPass.h"
15 #include "llvm/CodeGen/MachineInstr.h"
16 #include "llvm/CodeGen/RegisterScavenging.h"
17 #include "llvm/CodeGen/TargetInstrInfo.h"
18 #include "llvm/CodeGen/TargetRegisterInfo.h"
19 #include "llvm/CodeGen/TargetSubtargetInfo.h"
20 #include "llvm/Config/llvm-config.h"
21 #include "llvm/IR/DebugLoc.h"
22 #include "llvm/InitializePasses.h"
23 #include "llvm/Pass.h"
24 #include "llvm/Support/Compiler.h"
25 #include "llvm/Support/Debug.h"
26 #include "llvm/Support/Format.h"
27 #include "llvm/Support/MathExtras.h"
28 #include "llvm/Support/raw_ostream.h"
29 #include <cassert>
30 #include <cstdint>
31 #include <iterator>
32 #include <memory>
33
34 using namespace llvm;
35
36 #define DEBUG_TYPE "branch-relaxation"
37
38 STATISTIC(NumSplit, "Number of basic blocks split");
39 STATISTIC(NumConditionalRelaxed, "Number of conditional branches relaxed");
40 STATISTIC(NumUnconditionalRelaxed, "Number of unconditional branches relaxed");
41
42 #define BRANCH_RELAX_NAME "Branch relaxation pass"
43
44 namespace {
45
46 class BranchRelaxation : public MachineFunctionPass {
47 /// BasicBlockInfo - Information about the offset and size of a single
48 /// basic block.
49 struct BasicBlockInfo {
50 /// Offset - Distance from the beginning of the function to the beginning
51 /// of this basic block.
52 ///
53 /// The offset is always aligned as required by the basic block.
54 unsigned Offset = 0;
55
56 /// Size - Size of the basic block in bytes. If the block contains
57 /// inline assembly, this is a worst case estimate.
58 ///
59 /// The size does not include any alignment padding whether from the
60 /// beginning of the block, or from an aligned jump table at the end.
61 unsigned Size = 0;
62
63 BasicBlockInfo() = default;
64
65 /// Compute the offset immediately following this block. \p MBB is the next
66 /// block.
postOffset__anonb94e3bc70111::BranchRelaxation::BasicBlockInfo67 unsigned postOffset(const MachineBasicBlock &MBB) const {
68 const unsigned PO = Offset + Size;
69 const Align Alignment = MBB.getAlignment();
70 const Align ParentAlign = MBB.getParent()->getAlignment();
71 if (Alignment <= ParentAlign)
72 return alignTo(PO, Alignment);
73
74 // The alignment of this MBB is larger than the function's alignment, so we
75 // can't tell whether or not it will insert nops. Assume that it will.
76 return alignTo(PO, Alignment) + Alignment.value() - ParentAlign.value();
77 }
78 };
79
80 SmallVector<BasicBlockInfo, 16> BlockInfo;
81 std::unique_ptr<RegScavenger> RS;
82 LivePhysRegs LiveRegs;
83
84 MachineFunction *MF;
85 const TargetRegisterInfo *TRI;
86 const TargetInstrInfo *TII;
87
88 bool relaxBranchInstructions();
89 void scanFunction();
90
91 MachineBasicBlock *createNewBlockAfter(MachineBasicBlock &BB);
92
93 MachineBasicBlock *splitBlockBeforeInstr(MachineInstr &MI,
94 MachineBasicBlock *DestBB);
95 void adjustBlockOffsets(MachineBasicBlock &Start);
96 bool isBlockInRange(const MachineInstr &MI, const MachineBasicBlock &BB) const;
97
98 bool fixupConditionalBranch(MachineInstr &MI);
99 bool fixupUnconditionalBranch(MachineInstr &MI);
100 uint64_t computeBlockSize(const MachineBasicBlock &MBB) const;
101 unsigned getInstrOffset(const MachineInstr &MI) const;
102 void dumpBBs();
103 void verify();
104
105 public:
106 static char ID;
107
BranchRelaxation()108 BranchRelaxation() : MachineFunctionPass(ID) {}
109
110 bool runOnMachineFunction(MachineFunction &MF) override;
111
getPassName() const112 StringRef getPassName() const override { return BRANCH_RELAX_NAME; }
113 };
114
115 } // end anonymous namespace
116
117 char BranchRelaxation::ID = 0;
118
119 char &llvm::BranchRelaxationPassID = BranchRelaxation::ID;
120
INITIALIZE_PASS(BranchRelaxation,DEBUG_TYPE,BRANCH_RELAX_NAME,false,false)121 INITIALIZE_PASS(BranchRelaxation, DEBUG_TYPE, BRANCH_RELAX_NAME, false, false)
122
123 /// verify - check BBOffsets, BBSizes, alignment of islands
124 void BranchRelaxation::verify() {
125 #ifndef NDEBUG
126 unsigned PrevNum = MF->begin()->getNumber();
127 for (MachineBasicBlock &MBB : *MF) {
128 const unsigned Num = MBB.getNumber();
129 assert(!Num || BlockInfo[PrevNum].postOffset(MBB) <= BlockInfo[Num].Offset);
130 assert(BlockInfo[Num].Size == computeBlockSize(MBB));
131 PrevNum = Num;
132 }
133 #endif
134 }
135
136 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
137 /// print block size and offset information - debugging
dumpBBs()138 LLVM_DUMP_METHOD void BranchRelaxation::dumpBBs() {
139 for (auto &MBB : *MF) {
140 const BasicBlockInfo &BBI = BlockInfo[MBB.getNumber()];
141 dbgs() << format("%%bb.%u\toffset=%08x\t", MBB.getNumber(), BBI.Offset)
142 << format("size=%#x\n", BBI.Size);
143 }
144 }
145 #endif
146
147 /// scanFunction - Do the initial scan of the function, building up
148 /// information about each block.
scanFunction()149 void BranchRelaxation::scanFunction() {
150 BlockInfo.clear();
151 BlockInfo.resize(MF->getNumBlockIDs());
152
153 // First thing, compute the size of all basic blocks, and see if the function
154 // has any inline assembly in it. If so, we have to be conservative about
155 // alignment assumptions, as we don't know for sure the size of any
156 // instructions in the inline assembly.
157 for (MachineBasicBlock &MBB : *MF)
158 BlockInfo[MBB.getNumber()].Size = computeBlockSize(MBB);
159
160 // Compute block offsets and known bits.
161 adjustBlockOffsets(*MF->begin());
162 }
163
164 /// computeBlockSize - Compute the size for MBB.
computeBlockSize(const MachineBasicBlock & MBB) const165 uint64_t BranchRelaxation::computeBlockSize(const MachineBasicBlock &MBB) const {
166 uint64_t Size = 0;
167 for (const MachineInstr &MI : MBB)
168 Size += TII->getInstSizeInBytes(MI);
169 return Size;
170 }
171
172 /// getInstrOffset - Return the current offset of the specified machine
173 /// instruction from the start of the function. This offset changes as stuff is
174 /// moved around inside the function.
getInstrOffset(const MachineInstr & MI) const175 unsigned BranchRelaxation::getInstrOffset(const MachineInstr &MI) const {
176 const MachineBasicBlock *MBB = MI.getParent();
177
178 // The offset is composed of two things: the sum of the sizes of all MBB's
179 // before this instruction's block, and the offset from the start of the block
180 // it is in.
181 unsigned Offset = BlockInfo[MBB->getNumber()].Offset;
182
183 // Sum instructions before MI in MBB.
184 for (MachineBasicBlock::const_iterator I = MBB->begin(); &*I != &MI; ++I) {
185 assert(I != MBB->end() && "Didn't find MI in its own basic block?");
186 Offset += TII->getInstSizeInBytes(*I);
187 }
188
189 return Offset;
190 }
191
adjustBlockOffsets(MachineBasicBlock & Start)192 void BranchRelaxation::adjustBlockOffsets(MachineBasicBlock &Start) {
193 unsigned PrevNum = Start.getNumber();
194 for (auto &MBB :
195 make_range(std::next(MachineFunction::iterator(Start)), MF->end())) {
196 unsigned Num = MBB.getNumber();
197 // Get the offset and known bits at the end of the layout predecessor.
198 // Include the alignment of the current block.
199 BlockInfo[Num].Offset = BlockInfo[PrevNum].postOffset(MBB);
200
201 PrevNum = Num;
202 }
203 }
204
205 /// Insert a new empty basic block and insert it after \BB
createNewBlockAfter(MachineBasicBlock & BB)206 MachineBasicBlock *BranchRelaxation::createNewBlockAfter(MachineBasicBlock &BB) {
207 // Create a new MBB for the code after the OrigBB.
208 MachineBasicBlock *NewBB =
209 MF->CreateMachineBasicBlock(BB.getBasicBlock());
210 MF->insert(++BB.getIterator(), NewBB);
211
212 // Insert an entry into BlockInfo to align it properly with the block numbers.
213 BlockInfo.insert(BlockInfo.begin() + NewBB->getNumber(), BasicBlockInfo());
214
215 return NewBB;
216 }
217
218 /// Split the basic block containing MI into two blocks, which are joined by
219 /// an unconditional branch. Update data structures and renumber blocks to
220 /// account for this change and returns the newly created block.
splitBlockBeforeInstr(MachineInstr & MI,MachineBasicBlock * DestBB)221 MachineBasicBlock *BranchRelaxation::splitBlockBeforeInstr(MachineInstr &MI,
222 MachineBasicBlock *DestBB) {
223 MachineBasicBlock *OrigBB = MI.getParent();
224
225 // Create a new MBB for the code after the OrigBB.
226 MachineBasicBlock *NewBB =
227 MF->CreateMachineBasicBlock(OrigBB->getBasicBlock());
228 MF->insert(++OrigBB->getIterator(), NewBB);
229
230 // Splice the instructions starting with MI over to NewBB.
231 NewBB->splice(NewBB->end(), OrigBB, MI.getIterator(), OrigBB->end());
232
233 // Add an unconditional branch from OrigBB to NewBB.
234 // Note the new unconditional branch is not being recorded.
235 // There doesn't seem to be meaningful DebugInfo available; this doesn't
236 // correspond to anything in the source.
237 TII->insertUnconditionalBranch(*OrigBB, NewBB, DebugLoc());
238
239 // Insert an entry into BlockInfo to align it properly with the block numbers.
240 BlockInfo.insert(BlockInfo.begin() + NewBB->getNumber(), BasicBlockInfo());
241
242 NewBB->transferSuccessors(OrigBB);
243 OrigBB->addSuccessor(NewBB);
244 OrigBB->addSuccessor(DestBB);
245
246 // Cleanup potential unconditional branch to successor block.
247 // Note that updateTerminator may change the size of the blocks.
248 OrigBB->updateTerminator(NewBB);
249
250 // Figure out how large the OrigBB is. As the first half of the original
251 // block, it cannot contain a tablejump. The size includes
252 // the new jump we added. (It should be possible to do this without
253 // recounting everything, but it's very confusing, and this is rarely
254 // executed.)
255 BlockInfo[OrigBB->getNumber()].Size = computeBlockSize(*OrigBB);
256
257 // Figure out how large the NewMBB is. As the second half of the original
258 // block, it may contain a tablejump.
259 BlockInfo[NewBB->getNumber()].Size = computeBlockSize(*NewBB);
260
261 // All BBOffsets following these blocks must be modified.
262 adjustBlockOffsets(*OrigBB);
263
264 // Need to fix live-in lists if we track liveness.
265 if (TRI->trackLivenessAfterRegAlloc(*MF))
266 computeAndAddLiveIns(LiveRegs, *NewBB);
267
268 ++NumSplit;
269
270 return NewBB;
271 }
272
273 /// isBlockInRange - Returns true if the distance between specific MI and
274 /// specific BB can fit in MI's displacement field.
isBlockInRange(const MachineInstr & MI,const MachineBasicBlock & DestBB) const275 bool BranchRelaxation::isBlockInRange(
276 const MachineInstr &MI, const MachineBasicBlock &DestBB) const {
277 int64_t BrOffset = getInstrOffset(MI);
278 int64_t DestOffset = BlockInfo[DestBB.getNumber()].Offset;
279
280 if (TII->isBranchOffsetInRange(MI.getOpcode(), DestOffset - BrOffset))
281 return true;
282
283 LLVM_DEBUG(dbgs() << "Out of range branch to destination "
284 << printMBBReference(DestBB) << " from "
285 << printMBBReference(*MI.getParent()) << " to "
286 << DestOffset << " offset " << DestOffset - BrOffset << '\t'
287 << MI);
288
289 return false;
290 }
291
292 /// fixupConditionalBranch - Fix up a conditional branch whose destination is
293 /// too far away to fit in its displacement field. It is converted to an inverse
294 /// conditional branch + an unconditional branch to the destination.
fixupConditionalBranch(MachineInstr & MI)295 bool BranchRelaxation::fixupConditionalBranch(MachineInstr &MI) {
296 DebugLoc DL = MI.getDebugLoc();
297 MachineBasicBlock *MBB = MI.getParent();
298 MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
299 MachineBasicBlock *NewBB = nullptr;
300 SmallVector<MachineOperand, 4> Cond;
301
302 auto insertUncondBranch = [&](MachineBasicBlock *MBB,
303 MachineBasicBlock *DestBB) {
304 unsigned &BBSize = BlockInfo[MBB->getNumber()].Size;
305 int NewBrSize = 0;
306 TII->insertUnconditionalBranch(*MBB, DestBB, DL, &NewBrSize);
307 BBSize += NewBrSize;
308 };
309 auto insertBranch = [&](MachineBasicBlock *MBB, MachineBasicBlock *TBB,
310 MachineBasicBlock *FBB,
311 SmallVectorImpl<MachineOperand>& Cond) {
312 unsigned &BBSize = BlockInfo[MBB->getNumber()].Size;
313 int NewBrSize = 0;
314 TII->insertBranch(*MBB, TBB, FBB, Cond, DL, &NewBrSize);
315 BBSize += NewBrSize;
316 };
317 auto removeBranch = [&](MachineBasicBlock *MBB) {
318 unsigned &BBSize = BlockInfo[MBB->getNumber()].Size;
319 int RemovedSize = 0;
320 TII->removeBranch(*MBB, &RemovedSize);
321 BBSize -= RemovedSize;
322 };
323
324 auto finalizeBlockChanges = [&](MachineBasicBlock *MBB,
325 MachineBasicBlock *NewBB) {
326 // Keep the block offsets up to date.
327 adjustBlockOffsets(*MBB);
328
329 // Need to fix live-in lists if we track liveness.
330 if (NewBB && TRI->trackLivenessAfterRegAlloc(*MF))
331 computeAndAddLiveIns(LiveRegs, *NewBB);
332 };
333
334 bool Fail = TII->analyzeBranch(*MBB, TBB, FBB, Cond);
335 assert(!Fail && "branches to be relaxed must be analyzable");
336 (void)Fail;
337
338 // Add an unconditional branch to the destination and invert the branch
339 // condition to jump over it:
340 // tbz L1
341 // =>
342 // tbnz L2
343 // b L1
344 // L2:
345
346 bool ReversedCond = !TII->reverseBranchCondition(Cond);
347 if (ReversedCond) {
348 if (FBB && isBlockInRange(MI, *FBB)) {
349 // Last MI in the BB is an unconditional branch. We can simply invert the
350 // condition and swap destinations:
351 // beq L1
352 // b L2
353 // =>
354 // bne L2
355 // b L1
356 LLVM_DEBUG(dbgs() << " Invert condition and swap "
357 "its destination with "
358 << MBB->back());
359
360 removeBranch(MBB);
361 insertBranch(MBB, FBB, TBB, Cond);
362 finalizeBlockChanges(MBB, nullptr);
363 return true;
364 }
365 if (FBB) {
366 // We need to split the basic block here to obtain two long-range
367 // unconditional branches.
368 NewBB = createNewBlockAfter(*MBB);
369
370 insertUncondBranch(NewBB, FBB);
371 // Update the succesor lists according to the transformation to follow.
372 // Do it here since if there's no split, no update is needed.
373 MBB->replaceSuccessor(FBB, NewBB);
374 NewBB->addSuccessor(FBB);
375 }
376
377 // We now have an appropriate fall-through block in place (either naturally or
378 // just created), so we can use the inverted the condition.
379 MachineBasicBlock &NextBB = *std::next(MachineFunction::iterator(MBB));
380
381 LLVM_DEBUG(dbgs() << " Insert B to " << printMBBReference(*TBB)
382 << ", invert condition and change dest. to "
383 << printMBBReference(NextBB) << '\n');
384
385 removeBranch(MBB);
386 // Insert a new conditional branch and a new unconditional branch.
387 insertBranch(MBB, &NextBB, TBB, Cond);
388
389 finalizeBlockChanges(MBB, NewBB);
390 return true;
391 }
392 // Branch cond can't be inverted.
393 // In this case we always add a block after the MBB.
394 LLVM_DEBUG(dbgs() << " The branch condition can't be inverted. "
395 << " Insert a new BB after " << MBB->back());
396
397 if (!FBB)
398 FBB = &(*std::next(MachineFunction::iterator(MBB)));
399
400 // This is the block with cond. branch and the distance to TBB is too long.
401 // beq L1
402 // L2:
403
404 // We do the following transformation:
405 // beq NewBB
406 // b L2
407 // NewBB:
408 // b L1
409 // L2:
410
411 NewBB = createNewBlockAfter(*MBB);
412 insertUncondBranch(NewBB, TBB);
413
414 LLVM_DEBUG(dbgs() << " Insert cond B to the new BB "
415 << printMBBReference(*NewBB)
416 << " Keep the exiting condition.\n"
417 << " Insert B to " << printMBBReference(*FBB) << ".\n"
418 << " In the new BB: Insert B to "
419 << printMBBReference(*TBB) << ".\n");
420
421 // Update the successor lists according to the transformation to follow.
422 MBB->replaceSuccessor(TBB, NewBB);
423 NewBB->addSuccessor(TBB);
424
425 // Replace branch in the current (MBB) block.
426 removeBranch(MBB);
427 insertBranch(MBB, NewBB, FBB, Cond);
428
429 finalizeBlockChanges(MBB, NewBB);
430 return true;
431 }
432
fixupUnconditionalBranch(MachineInstr & MI)433 bool BranchRelaxation::fixupUnconditionalBranch(MachineInstr &MI) {
434 MachineBasicBlock *MBB = MI.getParent();
435
436 unsigned OldBrSize = TII->getInstSizeInBytes(MI);
437 MachineBasicBlock *DestBB = TII->getBranchDestBlock(MI);
438
439 int64_t DestOffset = BlockInfo[DestBB->getNumber()].Offset;
440 int64_t SrcOffset = getInstrOffset(MI);
441
442 assert(!TII->isBranchOffsetInRange(MI.getOpcode(), DestOffset - SrcOffset));
443
444 BlockInfo[MBB->getNumber()].Size -= OldBrSize;
445
446 MachineBasicBlock *BranchBB = MBB;
447
448 // If this was an expanded conditional branch, there is already a single
449 // unconditional branch in a block.
450 if (!MBB->empty()) {
451 BranchBB = createNewBlockAfter(*MBB);
452
453 // Add live outs.
454 for (const MachineBasicBlock *Succ : MBB->successors()) {
455 for (const MachineBasicBlock::RegisterMaskPair &LiveIn : Succ->liveins())
456 BranchBB->addLiveIn(LiveIn);
457 }
458
459 BranchBB->sortUniqueLiveIns();
460 BranchBB->addSuccessor(DestBB);
461 MBB->replaceSuccessor(DestBB, BranchBB);
462 }
463
464 DebugLoc DL = MI.getDebugLoc();
465 MI.eraseFromParent();
466 BlockInfo[BranchBB->getNumber()].Size += TII->insertIndirectBranch(
467 *BranchBB, *DestBB, DL, DestOffset - SrcOffset, RS.get());
468
469 adjustBlockOffsets(*MBB);
470 return true;
471 }
472
relaxBranchInstructions()473 bool BranchRelaxation::relaxBranchInstructions() {
474 bool Changed = false;
475
476 // Relaxing branches involves creating new basic blocks, so re-eval
477 // end() for termination.
478 for (MachineFunction::iterator I = MF->begin(); I != MF->end(); ++I) {
479 MachineBasicBlock &MBB = *I;
480
481 // Empty block?
482 MachineBasicBlock::iterator Last = MBB.getLastNonDebugInstr();
483 if (Last == MBB.end())
484 continue;
485
486 // Expand the unconditional branch first if necessary. If there is a
487 // conditional branch, this will end up changing the branch destination of
488 // it to be over the newly inserted indirect branch block, which may avoid
489 // the need to try expanding the conditional branch first, saving an extra
490 // jump.
491 if (Last->isUnconditionalBranch()) {
492 // Unconditional branch destination might be unanalyzable, assume these
493 // are OK.
494 if (MachineBasicBlock *DestBB = TII->getBranchDestBlock(*Last)) {
495 if (!isBlockInRange(*Last, *DestBB)) {
496 fixupUnconditionalBranch(*Last);
497 ++NumUnconditionalRelaxed;
498 Changed = true;
499 }
500 }
501 }
502
503 // Loop over the conditional branches.
504 MachineBasicBlock::iterator Next;
505 for (MachineBasicBlock::iterator J = MBB.getFirstTerminator();
506 J != MBB.end(); J = Next) {
507 Next = std::next(J);
508 MachineInstr &MI = *J;
509
510 if (MI.isConditionalBranch()) {
511 MachineBasicBlock *DestBB = TII->getBranchDestBlock(MI);
512 if (!isBlockInRange(MI, *DestBB)) {
513 if (Next != MBB.end() && Next->isConditionalBranch()) {
514 // If there are multiple conditional branches, this isn't an
515 // analyzable block. Split later terminators into a new block so
516 // each one will be analyzable.
517
518 splitBlockBeforeInstr(*Next, DestBB);
519 } else {
520 fixupConditionalBranch(MI);
521 ++NumConditionalRelaxed;
522 }
523
524 Changed = true;
525
526 // This may have modified all of the terminators, so start over.
527 Next = MBB.getFirstTerminator();
528 }
529 }
530 }
531 }
532
533 return Changed;
534 }
535
runOnMachineFunction(MachineFunction & mf)536 bool BranchRelaxation::runOnMachineFunction(MachineFunction &mf) {
537 MF = &mf;
538
539 LLVM_DEBUG(dbgs() << "***** BranchRelaxation *****\n");
540
541 const TargetSubtargetInfo &ST = MF->getSubtarget();
542 TII = ST.getInstrInfo();
543
544 TRI = ST.getRegisterInfo();
545 if (TRI->trackLivenessAfterRegAlloc(*MF))
546 RS.reset(new RegScavenger());
547
548 // Renumber all of the machine basic blocks in the function, guaranteeing that
549 // the numbers agree with the position of the block in the function.
550 MF->RenumberBlocks();
551
552 // Do the initial scan of the function, building up information about the
553 // sizes of each block.
554 scanFunction();
555
556 LLVM_DEBUG(dbgs() << " Basic blocks before relaxation\n"; dumpBBs(););
557
558 bool MadeChange = false;
559 while (relaxBranchInstructions())
560 MadeChange = true;
561
562 // After a while, this might be made debug-only, but it is not expensive.
563 verify();
564
565 LLVM_DEBUG(dbgs() << " Basic blocks after relaxation\n\n"; dumpBBs());
566
567 BlockInfo.clear();
568
569 return MadeChange;
570 }
571