BranchRelaxation.cpp Source File (original) (raw)

21#include "llvm/Config/llvm-config.h"

31#include

32#include

33#include

34#include

36using namespace llvm;

38#define DEBUG_TYPE "branch-relaxation"

40 STATISTIC(NumSplit, "Number of basic blocks split");

41 STATISTIC(NumConditionalRelaxed, "Number of conditional branches relaxed");

42 STATISTIC(NumUnconditionalRelaxed, "Number of unconditional branches relaxed");

44#define BRANCH_RELAX_NAME "Branch relaxation pass"

46namespace {

48class BranchRelaxation {

63 unsigned Size = 0;

71 const Align Alignment = MBB.getAlignment();

72 const Align ParentAlign = MBB.getParent()->getAlignment();

73 if (Alignment <= ParentAlign)

74 return alignTo(PO, Alignment);

78 return alignTo(PO, Alignment) + Alignment.value() - ParentAlign.value();

79 }

80 };

88 RelaxedUnconditionals;

89 std::unique_ptr RS;

97 bool relaxBranchInstructions();

98 void scanFunction();

103

111

115 unsigned getInstrOffset(const MachineInstr &MI) const;

116 void dumpBBs();

118

119public:

121};

122

124public:

125 static char ID;

126

128

129 bool runOnMachineFunction(MachineFunction &MF) override {

131 }

132

134};

135

136}

137

138char BranchRelaxationLegacy::ID = 0;

139

141

143 false)

144

145

146void BranchRelaxation::verify() {

147#ifndef NDEBUG

148 unsigned PrevNum = MF->begin()->getNumber();

150 const unsigned Num = MBB.getNumber();

151 assert(!Num || BlockInfo[PrevNum].postOffset(MBB) <= BlockInfo[Num].Offset);

152 assert(BlockInfo[Num].Size == computeBlockSize(MBB));

153 PrevNum = Num;

154 }

155

158 J != MBB.end(); J = std::next(J)) {

160 if (.isConditionalBranch() && .isUnconditionalBranch())

161 continue;

162 if (MI.getOpcode() == TargetOpcode::FAULTING_OP)

163 continue;

165 assert(isBlockInRange(MI, *DestBB) ||

166 RelaxedUnconditionals.contains({&MBB, DestBB}));

167 }

168 }

169#endif

170}

171

172#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)

173

175 for (auto &MBB : *MF) {

176 const BasicBlockInfo &BBI = BlockInfo[MBB.getNumber()];

179 }

180}

181#endif

182

183

184

185void BranchRelaxation::scanFunction() {

186 BlockInfo.clear();

187 BlockInfo.resize(MF->getNumBlockIDs());

188

189 TrampolineInsertionPoint = nullptr;

190 RelaxedUnconditionals.clear();

191

192

193

194

195

196

197 for (MachineBasicBlock &MBB : *MF) {

199

201 TrampolineInsertionPoint = &MBB;

202 }

203

204

205 adjustBlockOffsets(*MF->begin());

206

207 if (TrampolineInsertionPoint == nullptr) {

208 LLVM_DEBUG(dbgs() << " No suitable trampoline insertion point found in "

209 << MF->getName() << ".\n");

210 }

211}

212

213

214uint64_t

215BranchRelaxation::computeBlockSize(const MachineBasicBlock &MBB) const {

216 uint64_t Size = 0;

217 for (const MachineInstr &MI : MBB)

220}

221

222

223

224

225unsigned BranchRelaxation::getInstrOffset(const MachineInstr &MI) const {

226 const MachineBasicBlock *MBB = MI.getParent();

227

228

229

230

232

233

235 assert(I != MBB->end() && "Didn't find MI in its own basic block?");

237 }

238

240}

241

242void BranchRelaxation::adjustBlockOffsets(MachineBasicBlock &Start) {

243 adjustBlockOffsets(Start, MF->end());

244}

245

246void BranchRelaxation::adjustBlockOffsets(MachineBasicBlock &Start,

248 unsigned PrevNum = Start.getNumber();

249 for (auto &MBB :

252

253

254 BlockInfo[Num].Offset = BlockInfo[PrevNum].postOffset(MBB);

255

256 PrevNum = Num;

257 }

258}

259

260

261MachineBasicBlock *

262BranchRelaxation::createNewBlockAfter(MachineBasicBlock &OrigBB) {

263 return createNewBlockAfter(OrigBB, OrigBB.getBasicBlock());

264}

265

266

267

268MachineBasicBlock *

269BranchRelaxation::createNewBlockAfter(MachineBasicBlock &OrigMBB,

270 const BasicBlock *BB) {

271

272 MachineBasicBlock *NewBB = MF->CreateMachineBasicBlock(BB);

273 MF->insert(++OrigMBB.getIterator(), NewBB);

274

275

279

280

281 BlockInfo.insert(BlockInfo.begin() + NewBB->getNumber(), BasicBlockInfo());

282

283 return NewBB;

284}

285

286

287

288

289MachineBasicBlock *

290BranchRelaxation::splitBlockBeforeInstr(MachineInstr &MI,

291 MachineBasicBlock *DestBB) {

292 MachineBasicBlock *OrigBB = MI.getParent();

293

294

295 MachineBasicBlock *NewBB =

296 MF->CreateMachineBasicBlock(OrigBB->getBasicBlock());

298

299

303

304

305 NewBB->splice(NewBB->end(), OrigBB, MI.getIterator(), OrigBB->end());

306

307

308

309

310

312

313

314 BlockInfo.insert(BlockInfo.begin() + NewBB->getNumber(), BasicBlockInfo());

315

319

320

321

323

324

325

326

327

328

329 BlockInfo[OrigBB->getNumber()].Size = computeBlockSize(*OrigBB);

330

331

332

333 BlockInfo[NewBB->getNumber()].Size = computeBlockSize(*NewBB);

334

335

336 adjustBlockOffsets(*OrigBB, std::next(NewBB->getIterator()));

337

338

339 if (TRI->trackLivenessAfterRegAlloc(*MF))

341

342 ++NumSplit;

343

344 return NewBB;

345}

346

347

348

349bool BranchRelaxation::isBlockInRange(const MachineInstr &MI,

350 const MachineBasicBlock &DestBB) const {

351 int64_t BrOffset = getInstrOffset(MI);

352 int64_t DestOffset = BlockInfo[DestBB.getNumber()].Offset;

353

354 const MachineBasicBlock *SrcBB = MI.getParent();

355

359 : DestOffset - BrOffset))

360 return true;

361

362 LLVM_DEBUG(dbgs() << "Out of range branch to destination "

365 << DestOffset << " offset " << DestOffset - BrOffset << '\t'

366 << MI);

367

368 return false;

369}

370

371

372

373

374bool BranchRelaxation::fixupConditionalBranch(MachineInstr &MI) {

376 MachineBasicBlock *MBB = MI.getParent();

377 MachineBasicBlock *TBB = nullptr, *FBB = nullptr;

378 MachineBasicBlock *NewBB = nullptr;

380

381 auto insertUncondBranch = [&](MachineBasicBlock *MBB,

382 MachineBasicBlock *DestBB) {

383 unsigned &BBSize = BlockInfo[MBB->getNumber()].Size;

384 int NewBrSize = 0;

386 BBSize += NewBrSize;

387 };

388 auto insertBranch = [&](MachineBasicBlock *MBB, MachineBasicBlock *TBB,

389 MachineBasicBlock *FBB,

390 SmallVectorImpl &Cond) {

391 unsigned &BBSize = BlockInfo[MBB->getNumber()].Size;

392 int NewBrSize = 0;

394 BBSize += NewBrSize;

395 };

396 auto removeBranch = [&](MachineBasicBlock *MBB) {

397 unsigned &BBSize = BlockInfo[MBB->getNumber()].Size;

398 int RemovedSize = 0;

400 BBSize -= RemovedSize;

401 };

402

403

404 auto updateOffsetAndLiveness = [&](MachineBasicBlock *NewBB) {

405 assert(NewBB != nullptr && "can't populate offset for nullptr");

406

407

408

409

410 adjustBlockOffsets(*std::prev(NewBB->getIterator()),

412

413

414 if (TRI->trackLivenessAfterRegAlloc(*MF))

416 };

417

419 assert( Fail && "branches to be relaxed must be analyzable");

421

422

423

424

425

426

427

428

429

430

431

434 TrampolineInsertionPoint != nullptr) {

435

436 NewBB =

437 createNewBlockAfter(*TrampolineInsertionPoint, MBB->getBasicBlock());

438

439 if (isBlockInRange(MI, *NewBB)) {

440 LLVM_DEBUG(dbgs() << " Retarget destination to trampoline at "

441 << NewBB->back());

442

443 insertUncondBranch(NewBB, TBB);

444

445

448

449

450 removeBranch(MBB);

451 insertBranch(MBB, NewBB, FBB, Cond);

452

453 TrampolineInsertionPoint = NewBB;

454 updateOffsetAndLiveness(NewBB);

455 return true;

456 }

457

459 dbgs() << " Trampoline insertion point out of range for Bcc from "

461 << ".\n");

463 MF->erase(NewBB);

464 NewBB = nullptr;

465 }

466

467

468

469

470

471

472

473

474

476 if (ReversedCond) {

477 if (FBB && isBlockInRange(MI, *FBB)) {

478

479

480

481

482

483

484

486 "its destination with "

488

489 removeBranch(MBB);

491 return true;

492 }

493 if (FBB) {

494

495

496

497

498

499

500

501

502

503 if (TBB == FBB) {

504 removeBranch(MBB);

505 insertUncondBranch(MBB, TBB);

506 return true;

507 }

508

509

510 NewBB = createNewBlockAfter(*MBB);

511

512 insertUncondBranch(NewBB, FBB);

513

514

517 updateOffsetAndLiveness(NewBB);

518 }

519

520

521

523

525 << ", invert condition and change dest. to "

527

528 removeBranch(MBB);

529

530 insertBranch(MBB, &NextBB, TBB, Cond);

531 return true;

532 }

533

534

535 LLVM_DEBUG(dbgs() << " The branch condition can't be inverted. "

536 << " Insert a new BB after " << MBB->back());

537

538 if (!FBB)

540

541

542

543

544

545

546

547

548

549

550

551

552 NewBB = createNewBlockAfter(*MBB);

553 insertUncondBranch(NewBB, TBB);

554

557 << " Keep the exiting condition.\n"

559 << " In the new BB: Insert B to "

561

562

565

566

567 removeBranch(MBB);

568 insertBranch(MBB, NewBB, FBB, Cond);

569

570 updateOffsetAndLiveness(NewBB);

571 return true;

572}

573

574bool BranchRelaxation::fixupUnconditionalBranch(MachineInstr &MI) {

575 MachineBasicBlock *MBB = MI.getParent();

578

579 int64_t DestOffset = BlockInfo[DestBB->getNumber()].Offset;

580 int64_t SrcOffset = getInstrOffset(MI);

581

585 : DestOffset - SrcOffset));

586

587 BlockInfo[MBB->getNumber()].Size -= OldBrSize;

588

589 MachineBasicBlock *BranchBB = MBB;

590

591

592

594 BranchBB = createNewBlockAfter(*MBB);

595

596

597 for (const MachineBasicBlock *Succ : MBB->successors()) {

598 for (const MachineBasicBlock::RegisterMaskPair &LiveIn : Succ->liveins())

600 }

601

605 if (TrampolineInsertionPoint == MBB)

606 TrampolineInsertionPoint = BranchBB;

607 }

608

610 MI.eraseFromParent();

611

612

613

614

615 MachineBasicBlock *RestoreBB =

616 createNewBlockAfter(MF->back(), DestBB->getBasicBlock());

618 ->setIsEndSection(RestoreBB->isEndSection());

620

624 : DestOffset - SrcOffset,

625 RS.get());

626

627

628

629 BlockInfo[BranchBB->getNumber()].Size = computeBlockSize(*BranchBB);

630 adjustBlockOffsets(*MBB, std::next(BranchBB->getIterator()));

631

632

633 if (!RestoreBB->empty()) {

634

635

638 MachineBasicBlock *NewBB = createNewBlockAfter(*TrampolineInsertionPoint);

640 BlockInfo[NewBB->getNumber()].Size = computeBlockSize(*NewBB);

641 adjustBlockOffsets(*TrampolineInsertionPoint,

643

644

645 TrampolineInsertionPoint = NewBB;

646

647

650

651 DestBB = NewBB;

652 }

653

654

655

656

657

658

659

661 MachineBasicBlock *PrevBB = &*std::prev(DestBB->getIterator());

662

663

665 assert(FT == DestBB);

667 BlockInfo[PrevBB->getNumber()].Size = computeBlockSize(*PrevBB);

668 }

669

671

674 if (TRI->trackLivenessAfterRegAlloc(*MF))

676

677 BlockInfo[RestoreBB->getNumber()].Size = computeBlockSize(*RestoreBB);

678

679 adjustBlockOffsets(*PrevBB, DestBB->getIterator());

680

681

685 RelaxedUnconditionals.insert({BranchBB, RestoreBB});

686 } else {

687

688 MF->erase(RestoreBB);

689 RelaxedUnconditionals.insert({BranchBB, DestBB});

690 }

691

692 return true;

693}

694

695bool BranchRelaxation::relaxBranchInstructions() {

697

698

699

700 for (MachineBasicBlock &MBB : *MF) {

701

704 continue;

705

706

707

708

709

710

711 if (Last->isUnconditionalBranch()) {

712

713

716 !RelaxedUnconditionals.contains({&MBB, DestBB})) {

717 fixupUnconditionalBranch(*Last);

718 ++NumUnconditionalRelaxed;

720 }

721 }

722 }

723

724

728 Next = std::next(J);

729 MachineInstr &MI = *J;

730

731 if (.isConditionalBranch())

732 continue;

733

734 if (MI.getOpcode() == TargetOpcode::FAULTING_OP)

735

736

737 continue;

738

740 if (!isBlockInRange(MI, *DestBB)) {

741 if (Next != MBB.end() && Next->isConditionalBranch()) {

742

743

744

745

746 splitBlockBeforeInstr(*Next, DestBB);

747 } else {

748 fixupConditionalBranch(MI);

749 ++NumConditionalRelaxed;

750 }

751

753

754

756 }

757 }

758 }

759

760

761

762

764 adjustBlockOffsets(MF->front());

765

767}

768

769PreservedAnalyses

777

779 MF = &mf;

780

781 LLVM_DEBUG(dbgs() << "***** BranchRelaxation *****\n");

782

784 TII = ST.getInstrInfo();

786

787 TRI = ST.getRegisterInfo();

788 if (TRI->trackLivenessAfterRegAlloc(*MF))

790

791

792

793 MF->RenumberBlocks();

794

795

796

797 scanFunction();

798

799 LLVM_DEBUG(dbgs() << " Basic blocks before relaxation\n"; dumpBBs(););

800

801 bool MadeChange = false;

802 while (relaxBranchInstructions())

803 MadeChange = true;

804

805

807

808 LLVM_DEBUG(dbgs() << " Basic blocks after relaxation\n\n"; dumpBBs());

809

810 BlockInfo.clear();

811 RelaxedUnconditionals.clear();

812

813 return MadeChange;

814}

assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")

const TargetInstrInfo & TII

static cl::opt< bool > BranchRelaxation("aarch64-enable-branch-relax", cl::Hidden, cl::init(true), cl::desc("Relax out of range conditional branches"))

MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL

#define BRANCH_RELAX_NAME

Definition BranchRelaxation.cpp:44

#define LLVM_DUMP_METHOD

Mark debug helper function definitions like dump() that should not be stripped from debug builds.

This file implements the LivePhysRegs utility for tracking liveness of physical registers.

#define INITIALIZE_PASS(passName, arg, name, cfg, analysis)

const SmallVectorImpl< MachineOperand > MachineBasicBlock * TBB

const SmallVectorImpl< MachineOperand > & Cond

This file declares the machine register scavenger class.

This file defines the SmallVector class.

This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...

#define STATISTIC(VARNAME, DESC)

LLVM Basic Block Representation.

PreservedAnalyses run(MachineFunction &MF, MachineFunctionAnalysisManager &MFAM)

Definition BranchRelaxation.cpp:770

A set of physical registers with utility functions to track liveness when walking backward/forward th...

void setIsEndSection(bool V=true)

MachineInstrBundleIterator< const MachineInstr > const_iterator

MachineBasicBlock * getLogicalFallThrough()

Return the fallthrough block if the block can implicitly transfer control to it's successor,...

LLVM_ABI void replaceSuccessor(MachineBasicBlock *Old, MachineBasicBlock *New)

Replace successor OLD with NEW and update probability info.

LLVM_ABI void transferSuccessors(MachineBasicBlock *FromMBB)

Transfers all the successors from MBB to this machine basic block (i.e., copies all the successors Fr...

LLVM_ABI instr_iterator insert(instr_iterator I, MachineInstr *M)

Insert MI into the instruction list before I, possibly inside a bundle.

int getNumber() const

MachineBasicBlocks are uniquely numbered at the function level, unless they're not in a MachineFuncti...

const BasicBlock * getBasicBlock() const

Return the LLVM basic block that this instance corresponded to originally.

LLVM_ABI void updateTerminator(MachineBasicBlock *PreviousLayoutSuccessor)

Update the terminator instructions in block to account for changes to block layout which may have bee...

LLVM_ABI iterator getFirstTerminator()

Returns an iterator to the first terminator instruction of this basic block.

MBBSectionID getSectionID() const

Returns the section ID of this basic block.

LLVM_ABI bool isEntryBlock() const

Returns true if this is the entry block of the function.

LLVM_ABI void addSuccessor(MachineBasicBlock *Succ, BranchProbability Prob=BranchProbability::getUnknown())

Add Succ as a successor of this MachineBasicBlock.

LLVM_ABI void sortUniqueLiveIns()

Sorts and uniques the LiveIns vector.

void setSectionID(MBBSectionID V)

Sets the section ID for this basic block.

LLVM_ABI iterator getLastNonDebugInstr(bool SkipPseudoOp=true)

Returns an iterator to the last non-debug instruction in the basic block, or end().

void addLiveIn(MCRegister PhysReg, LaneBitmask LaneMask=LaneBitmask::getAll())

Adds the specified register as a live in.

bool isBeginSection() const

Returns true if this block begins any section.

iterator_range< succ_iterator > successors()

void splice(iterator Where, MachineBasicBlock *Other, iterator From)

Take an instruction from MBB 'Other' at the position From, and insert it into this MBB right before '...

bool isEndSection() const

Returns true if this block ends any section.

MachineInstrBundleIterator< MachineInstr > iterator

void setIsBeginSection(bool V=true)

MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...

BasicBlockListType::iterator iterator

Representation of each machine instruction.

static PreservedAnalyses all()

Construct a special preserved set that preserves all passes.

Implements a dense probed hash-table based set with some number of buckets stored inline.

This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.

StringRef - Represent a constant reference to a string, i.e.

TargetInstrInfo - Interface to description of machine instruction set.

virtual bool reverseBranchCondition(SmallVectorImpl< MachineOperand > &Cond) const

Reverses the branch condition of the specified condition list, returning false on success and true if...

virtual unsigned removeBranch(MachineBasicBlock &MBB, int *BytesRemoved=nullptr) const

Remove the branching code at the end of the specific MBB.

virtual bool analyzeBranch(MachineBasicBlock &MBB, MachineBasicBlock *&TBB, MachineBasicBlock *&FBB, SmallVectorImpl< MachineOperand > &Cond, bool AllowModify=false) const

Analyze the branching code at the end of MBB, returning true if it cannot be understood (e....

virtual void insertIndirectBranch(MachineBasicBlock &MBB, MachineBasicBlock &NewDestBB, MachineBasicBlock &RestoreBB, const DebugLoc &DL, int64_t BrOffset=0, RegScavenger *RS=nullptr) const

Insert an unconditional indirect branch at the end of MBB to NewDestBB.

virtual bool isBranchOffsetInRange(unsigned BranchOpc, int64_t BrOffset) const

virtual unsigned insertBranch(MachineBasicBlock &MBB, MachineBasicBlock *TBB, MachineBasicBlock *FBB, ArrayRef< MachineOperand > Cond, const DebugLoc &DL, int *BytesAdded=nullptr) const

Insert branch code into the end of the specified MachineBasicBlock.

virtual bool isTailCall(const MachineInstr &Inst) const

Determines whether Inst is a tail call instruction.

virtual MachineBasicBlock * getBranchDestBlock(const MachineInstr &MI) const

virtual unsigned getInstSizeInBytes(const MachineInstr &MI) const

Returns the size in bytes of the specified MachineInstr, or ~0U when this function is not implemented...

unsigned insertUnconditionalBranch(MachineBasicBlock &MBB, MachineBasicBlock *DestBB, const DebugLoc &DL, int *BytesAdded=nullptr) const

Primary interface to the complete machine description for the target machine.

uint64_t getMaxCodeSize() const

Returns the maximum code size possible under the code model.

const Target & getTarget() const

TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...

TargetSubtargetInfo - Generic base class for all target subtargets.

self_iterator getIterator()

unsigned ID

LLVM IR allows to use arbitrary numbers as calling convention identifiers.

This is an optimization pass for GlobalISel generic memory operations.

iterator_range< T > make_range(T x, T y)

Convenience function for iterating over sub-ranges.

AnalysisManager< MachineFunction > MachineFunctionAnalysisManager

LLVM_ABI PreservedAnalyses getMachineFunctionPassPreservedAnalyses()

Returns the minimum set of Analyses that all machine function passes must preserve.

LLVM_ABI char & BranchRelaxationPassID

BranchRelaxation - This pass replaces branches that need to jump further than is supported by a branc...

Definition BranchRelaxation.cpp:140

LLVM_ABI raw_ostream & dbgs()

dbgs() - This returns a reference to a raw_ostream for debugging messages.

class LLVM_GSL_OWNER SmallVector

Forward declaration of SmallVector so that calculateSmallVectorDefaultInlinedElements can reference s...

format_object< Ts... > format(const char *Fmt, const Ts &... Vals)

These are helper functions used to produce formatted output.

uint64_t alignTo(uint64_t Size, Align A)

Returns a multiple of A needed to store Size bytes.

FunctionAddr VTableAddr Next

void computeAndAddLiveIns(LivePhysRegs &LiveRegs, MachineBasicBlock &MBB)

Convenience function combining computeLiveIns() and addLiveIns().

LLVM_ABI Printable printMBBReference(const MachineBasicBlock &MBB)

Prints a machine basic block reference.

This struct is a compact representation of a valid (non-zero power of two) alignment.

constexpr uint64_t value() const

This is a hole in the type system and should not be abused.

BasicBlockInfo - Information about the offset and size of a single basic block.

unsigned Size

Size - Size of the basic block in bytes.

unsigned Offset

Offset - Distance from the beginning of the function to the beginning of this basic block.

LLVM_ABI static const MBBSectionID ColdSectionID