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