PPCBranchCoalescing.cpp Source File (original) (raw)

28using namespace llvm;

30#define DEBUG_TYPE "ppc-branch-coalescing"

32 STATISTIC(NumBlocksCoalesced, "Number of blocks coalesced");

33 STATISTIC(NumPHINotMoved, "Number of PHI Nodes that cannot be merged");

34 STATISTIC(NumBlocksNotCoalesced, "Number of blocks not coalesced");

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133namespace {

134

136 struct CoalescingCandidateInfo {

139 MachineBasicBlock *FallThroughBlock;

141 bool MustMoveDown;

142 bool MustMoveUp;

143

144 CoalescingCandidateInfo();

145 void clear();

146 };

147

148 MachineDominatorTree *MDT;

149 MachinePostDominatorTree *MPDT;

150 const TargetInstrInfo *TII;

151 MachineRegisterInfo *MRI;

152

154 bool canCoalesceBranch(CoalescingCandidateInfo &Cand);

157 bool validateCandidates(CoalescingCandidateInfo &SourceRegion,

158 CoalescingCandidateInfo &TargetRegion) const;

159

160public:

161 static char ID;

162

163 PPCBranchCoalescing() : MachineFunctionPass(ID) {}

164

165 void getAnalysisUsage(AnalysisUsage &AU) const override {

166 AU.addRequired();

167 AU.addRequired();

169 }

170

171 StringRef getPassName() const override { return "Branch Coalescing"; }

172

173 bool mergeCandidates(CoalescingCandidateInfo &SourceRegion,

174 CoalescingCandidateInfo &TargetRegion);

175 bool canMoveToBeginning(const MachineInstr &MI,

176 const MachineBasicBlock &MBB) const;

177 bool canMoveToEnd(const MachineInstr &MI,

178 const MachineBasicBlock &MBB) const;

179 bool canMerge(CoalescingCandidateInfo &SourceRegion,

180 CoalescingCandidateInfo &TargetRegion) const;

181 void moveAndUpdatePHIs(MachineBasicBlock *SourceRegionMBB,

182 MachineBasicBlock *TargetRegionMBB);

183 bool runOnMachineFunction(MachineFunction &MF) override;

184};

185}

186

187char PPCBranchCoalescing::ID = 0;

188

189

191 return new PPCBranchCoalescing();

192}

193

195 "Branch Coalescing", false, false)

200

201PPCBranchCoalescing::CoalescingCandidateInfo::CoalescingCandidateInfo()

202 : BranchBlock(nullptr), BranchTargetBlock(nullptr),

203 FallThroughBlock(nullptr), MustMoveDown(false), MustMoveUp(false) {}

204

205void PPCBranchCoalescing::CoalescingCandidateInfo::clear() {

206 BranchBlock = nullptr;

207 BranchTargetBlock = nullptr;

208 FallThroughBlock = nullptr;

210 MustMoveDown = false;

211 MustMoveUp = false;

212}

213

214void PPCBranchCoalescing::initialize(MachineFunction &MF) {

215 MDT = &getAnalysis().getDomTree();

216 MPDT = &getAnalysis().getPostDomTree();

219}

220

221

222

223

224

225

226

227

228

229

230

231bool PPCBranchCoalescing::canCoalesceBranch(CoalescingCandidateInfo &Cand) {

233 << Cand.BranchBlock->getNumber() << " can be coalesced:");

234 MachineBasicBlock *FalseMBB = nullptr;

235

236 if (TII->analyzeBranch(*Cand.BranchBlock, Cand.BranchTargetBlock, FalseMBB,

237 Cand.Cond)) {

238 LLVM_DEBUG(dbgs() << "TII unable to Analyze Branch - skip\n");

239 return false;

240 }

241

242 for (auto &I : Cand.BranchBlock->terminators()) {

243 LLVM_DEBUG(dbgs() << "Looking at terminator : " << I << "\n");

244 if (.isBranch())

245 continue;

246

247

248

249

250

251

252

253

254

255

256

257

258

259

260 if (I.getNumOperands() != I.getNumExplicitOperands()) {

261 LLVM_DEBUG(dbgs() << "Terminator contains implicit operands - skip : "

262 << I << "\n");

263 return false;

264 }

265 }

266

267 if (Cand.BranchBlock->isEHPad() || Cand.BranchBlock->hasEHPadSuccessor()) {

269 return false;

270 }

271

272 if (Cand.BranchBlock->mayHaveInlineAsmBr()) {

274 return false;

275 }

276

277

278

279 if (!Cand.BranchTargetBlock || FalseMBB ||

280 !Cand.BranchBlock->isSuccessor(Cand.BranchTargetBlock)) {

281 LLVM_DEBUG(dbgs() << "Does not form a triangle - skip\n");

282 return false;

283 }

284

285

286 if (Cand.BranchBlock->succ_size() != 2) {

287 LLVM_DEBUG(dbgs() << "Does not have 2 successors - skip\n");

288 return false;

289 }

290

291

292 assert(Cand.BranchBlock->canFallThrough() &&

293 "Expecting the block to fall through!");

294

295

296

297

298 MachineBasicBlock *Succ =

299 (*Cand.BranchBlock->succ_begin() == Cand.BranchTargetBlock)

300 ? *Cand.BranchBlock->succ_rbegin()

301 : *Cand.BranchBlock->succ_begin();

302

303 assert(Succ && "Expecting a valid fall-through block\n");

304

305 if (!Succ->empty()) {

306 LLVM_DEBUG(dbgs() << "Fall-through block contains code -- skip\n");

307 return false;

308 }

309

310 if (!Succ->isSuccessor(Cand.BranchTargetBlock)) {

313 << "Successor of fall through block is not branch taken block\n");

314 return false;

315 }

316

317 Cand.FallThroughBlock = Succ;

319 return true;

320}

321

322

323

324

325

326

327

328

329bool PPCBranchCoalescing::identicalOperands(

331

332 if (OpList1.size() != OpList2.size()) {

333 LLVM_DEBUG(dbgs() << "Operand list is different size\n");

334 return false;

335 }

336

337 for (unsigned i = 0; i < OpList1.size(); ++i) {

338 const MachineOperand &Op1 = OpList1[i];

339 const MachineOperand &Op2 = OpList2[i];

340

342 << "Op2: " << Op2 << "\n");

343

345

347

348

349 && !(Op1.isUse() && MRI->isConstantPhysReg(Op1.getReg()))) {

350 LLVM_DEBUG(dbgs() << "The operands are not provably identical.\n");

351 return false;

352 }

353 LLVM_DEBUG(dbgs() << "Op1 and Op2 are identical!\n");

354 continue;

355 }

356

357

358

359

362 MachineInstr *Op1Def = MRI->getVRegDef(Op1.getReg());

363 MachineInstr *Op2Def = MRI->getVRegDef(Op2.getReg());

365 LLVM_DEBUG(dbgs() << "Op1Def: " << *Op1Def << " and " << *Op2Def

366 << " produce the same value!\n");

367 } else {

368 LLVM_DEBUG(dbgs() << "Operands produce different values\n");

369 return false;

370 }

371 } else {

372 LLVM_DEBUG(dbgs() << "The operands are not provably identical.\n");

373 return false;

374 }

375 }

376

377 return true;

378}

379

380

381

382

383

384

385

386

387

388

389void PPCBranchCoalescing::moveAndUpdatePHIs(MachineBasicBlock *SourceMBB,

390 MachineBasicBlock *TargetMBB) {

391

394

395 if (MI == ME) {

396 LLVM_DEBUG(dbgs() << "SourceMBB contains no PHI instructions.\n");

397 return;

398 }

399

400

402 MachineInstr &PHIInst = *Iter;

403 for (unsigned i = 2, e = PHIInst.getNumOperands() + 1; i != e; i += 2) {

404 MachineOperand &MO = PHIInst.getOperand(i);

405 if (MO.getMBB() == SourceMBB)

406 MO.setMBB(TargetMBB);

407 }

408 }

409 TargetMBB->splice(TargetMBB->begin(), SourceMBB, MI, ME);

410}

411

412

413

414

415

416

417

418

419

420

421

422bool PPCBranchCoalescing::canMoveToBeginning(const MachineInstr &MI,

423 const MachineBasicBlock &TargetMBB

424 ) const {

425

426 LLVM_DEBUG(dbgs() << "Checking if " << MI << " can move to beginning of "

427 << TargetMBB.getNumber() << "\n");

428

429 for (auto &Def : MI.defs()) {

430 for (auto &Use : MRI->use_instructions(Def.getReg())) {

431 if (Use.isPHI() && Use.getParent() == &TargetMBB) {

432 LLVM_DEBUG(dbgs() << " *** used in a PHI -- cannot move ***\n");

433 return false;

434 }

435 }

436 }

437

438 LLVM_DEBUG(dbgs() << " Safe to move to the beginning.\n");

439 return true;

440}

441

442

443

444

445

446

447

448

449

450

451

452

453bool PPCBranchCoalescing::canMoveToEnd(const MachineInstr &MI,

454 const MachineBasicBlock &TargetMBB

455 ) const {

456

457 LLVM_DEBUG(dbgs() << "Checking if " << MI << " can move to end of "

458 << TargetMBB.getNumber() << "\n");

459

460 for (auto &Use : MI.uses()) {

461 if (Use.isReg() && Use.getReg().isVirtual()) {

462 MachineInstr *DefInst = MRI->getVRegDef(Use.getReg());

463 if (DefInst->isPHI() && DefInst->getParent() == MI.getParent()) {

464 LLVM_DEBUG(dbgs() << " *** Cannot move this instruction ***\n");

465 return false;

466 } else {

468 dbgs() << " *** def is in another block -- safe to move!\n");

469 }

470 }

471 }

472

474 return true;

475}

476

477

478

479

480

481

482

483

484

485

486bool PPCBranchCoalescing::validateCandidates(

487 CoalescingCandidateInfo &SourceRegion,

488 CoalescingCandidateInfo &TargetRegion) const {

489

490 if (TargetRegion.BranchTargetBlock != SourceRegion.BranchBlock)

491 llvm_unreachable("Expecting SourceRegion to immediately follow TargetRegion");

492 else if (!MDT->dominates(TargetRegion.BranchBlock, SourceRegion.BranchBlock))

493 llvm_unreachable("Expecting TargetRegion to dominate SourceRegion");

494 else if (!MPDT->dominates(SourceRegion.BranchBlock, TargetRegion.BranchBlock))

495 llvm_unreachable("Expecting SourceRegion to post-dominate TargetRegion");

496 else if (!TargetRegion.FallThroughBlock->empty() ||

497 !SourceRegion.FallThroughBlock->empty())

498 llvm_unreachable("Expecting fall-through blocks to be empty");

499

500 return true;

501}

502

503

504

505

506

507

508

509

510

511

512

513

514

515

516

517

518

519

520

521

522

523

524

525

526

527

528

529bool PPCBranchCoalescing::canMerge(CoalescingCandidateInfo &SourceRegion,

530 CoalescingCandidateInfo &TargetRegion) const {

531 if (!validateCandidates(SourceRegion, TargetRegion))

532 return false;

533

534

535

537 I = SourceRegion.BranchBlock->instr_begin(),

538 E = SourceRegion.BranchBlock->getFirstNonPHI();

539 I != E; ++I) {

540 for (auto &Def : I->defs())

541 for (auto &Use : MRI->use_instructions(Def.getReg())) {

542 if (Use.isPHI() && Use.getParent() == SourceRegion.BranchTargetBlock) {

544 << "PHI " << *I

545 << " defines register used in another "

546 "PHI within branch target block -- can't merge\n");

547 NumPHINotMoved++;

548 return false;

549 }

550 if (Use.getParent() == SourceRegion.BranchBlock) {

552 << " defines register used in this "

553 "block -- all must move down\n");

554 SourceRegion.MustMoveDown = true;

555 }

556 }

557 }

558

559

560

562 I = SourceRegion.BranchBlock->getFirstNonPHI(),

563 E = SourceRegion.BranchBlock->end();

564 I != E; ++I) {

565 if (!canMoveToBeginning(*I, *SourceRegion.BranchTargetBlock)) {

567 << " cannot move down - must move up!\n");

568 SourceRegion.MustMoveUp = true;

569 }

570 if (!canMoveToEnd(*I, *TargetRegion.BranchBlock)) {

572 << " cannot move up - must move down!\n");

573 SourceRegion.MustMoveDown = true;

574 }

575 }

576

577 return (SourceRegion.MustMoveUp && SourceRegion.MustMoveDown) ? false : true;

578}

579

580

581

582

583

584

585

586

587

588

589

590

591

592

593

594

595

596

597

598

599

600

601

602

603

604

605

606

607

608

609

610

611

612

613

614

615

616

617

618

619

620

621

622

623

624

625

626

627

628

629

630

631

632

633

634

635

636bool PPCBranchCoalescing::mergeCandidates(CoalescingCandidateInfo &SourceRegion,

637 CoalescingCandidateInfo &TargetRegion) {

638

639 if (SourceRegion.MustMoveUp && SourceRegion.MustMoveDown) {

640 llvm_unreachable("Cannot have both MustMoveDown and MustMoveUp set!");

641 return false;

642 }

643

644 if (!validateCandidates(SourceRegion, TargetRegion))

645 return false;

646

647

648

649 moveAndUpdatePHIs(SourceRegion.BranchBlock, SourceRegion.BranchTargetBlock);

650

651

652

654 SourceRegion.BranchBlock->getFirstNonPHI();

656 SourceRegion.BranchBlock->getFirstTerminator();

657

658 MachineBasicBlock *Source = SourceRegion.MustMoveDown

659 ? SourceRegion.BranchTargetBlock

660 : TargetRegion.BranchBlock;

661

663 SourceRegion.MustMoveDown

664 ? SourceRegion.BranchTargetBlock->getFirstNonPHI()

665 : TargetRegion.BranchBlock->getFirstTerminator();

666

667 Source->splice(Target, SourceRegion.BranchBlock, firstInstr, lastInstr);

668

669

670

671

672

673

674 SourceRegion.BranchBlock->removeSuccessor(SourceRegion.FallThroughBlock);

675 TargetRegion.BranchBlock->transferSuccessorsAndUpdatePHIs(

676 SourceRegion.BranchBlock);

677

678

679

680 TargetRegion.BranchBlock->ReplaceUsesOfBlockWith(

681 SourceRegion.BranchBlock, SourceRegion.BranchTargetBlock);

682

684 SourceRegion.BranchBlock->terminators().begin();

685 while (I != SourceRegion.BranchBlock->terminators().end()) {

686 MachineInstr &CurrInst = *I;

687 ++I;

690 }

691

692

693

694 assert(TargetRegion.FallThroughBlock->empty() &&

695 "FallThroughBlocks should be empty!");

696

697

698

699 TargetRegion.FallThroughBlock->transferSuccessorsAndUpdatePHIs(

700 SourceRegion.FallThroughBlock);

701 TargetRegion.FallThroughBlock->removeSuccessor(SourceRegion.BranchBlock);

702 TargetRegion.FallThroughBlock->normalizeSuccProbs();

703

704

705 assert(SourceRegion.BranchBlock->empty() &&

706 "Expecting branch block to be empty!");

707 SourceRegion.BranchBlock->eraseFromParent();

708

709 assert(SourceRegion.FallThroughBlock->empty() &&

710 "Expecting fall-through block to be empty!\n");

711 SourceRegion.FallThroughBlock->eraseFromParent();

712

713 NumBlocksCoalesced++;

714 return true;

715}

716

717bool PPCBranchCoalescing::runOnMachineFunction(MachineFunction &MF) {

718

720 return false;

721

722 bool didSomething = false;

723

724 LLVM_DEBUG(dbgs() << "******** Branch Coalescing ********\n");

726

728

729 CoalescingCandidateInfo Cand1, Cand2;

730

731

732

733 for (MachineBasicBlock &MBB : MF) {

734 bool MergedCandidates = false;

735 do {

736 MergedCandidates = false;

737 Cand1.clear();

738 Cand2.clear();

739

740 Cand1.BranchBlock = &MBB;

741

742

743 if (!canCoalesceBranch(Cand1))

744 break;

745

746 Cand2.BranchBlock = Cand1.BranchTargetBlock;

747 if (!canCoalesceBranch(Cand2))

748 break;

749

750

751

752 assert(MPDT->dominates(Cand2.BranchTargetBlock, Cand1.BranchBlock) &&

753 "Branch-taken block should post-dominate first candidate");

754

755 if (!identicalOperands(Cand1.Cond, Cand2.Cond)) {

756 LLVM_DEBUG(dbgs() << "Blocks " << Cand1.BranchBlock->getNumber()

757 << " and " << Cand2.BranchBlock->getNumber()

758 << " have different branches\n");

759 break;

760 }

761 if (!canMerge(Cand2, Cand1)) {

763 << Cand1.BranchBlock->getNumber() << " and "

764 << Cand2.BranchBlock->getNumber() << "\n");

765 NumBlocksNotCoalesced++;

766 continue;

767 }

768 LLVM_DEBUG(dbgs() << "Merging blocks " << Cand1.BranchBlock->getNumber()

769 << " and " << Cand1.BranchTargetBlock->getNumber()

770 << "\n");

771 MergedCandidates = mergeCandidates(Cand2, Cand1);

772 if (MergedCandidates)

773 didSomething = true;

774

775 LLVM_DEBUG(dbgs() << "Function after merging: "; MF.dump();

776 dbgs() << "\n");

777 } while (MergedCandidates);

778 }

779

780#ifndef NDEBUG

781

782 if (didSomething)

783 MF.verify(nullptr, "Error in code produced by branch coalescing");

784#endif

785

786 LLVM_DEBUG(dbgs() << "Finished Branch Coalescing\n");

787 return didSomething;

788}

unsigned const MachineRegisterInfo * MRI

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

const TargetInstrInfo & TII

Function Alias Analysis false

static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")

#define INITIALIZE_PASS_DEPENDENCY(depName)

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

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

const SmallVectorImpl< MachineOperand > & Cond

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

#define STATISTIC(VARNAME, DESC)

static void initialize(TargetLibraryInfoImpl &TLI, const Triple &T, const llvm::StringTable &StandardNames, VectorLibrary VecLib)

Initialize the set of available library functions based on the specified target triple.

AnalysisUsage & addRequired()

size_t size() const

size - Get the array size.

bool dominates(const DomTreeNodeBase< NodeT > *A, const DomTreeNodeBase< NodeT > *B) const

dominates - Returns true iff A dominates B.

FunctionPass class - This class is used to implement most global optimizations.

int getNumber() const

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

LLVM_ABI iterator getFirstNonPHI()

Returns a pointer to the first instruction in this block that is not a PHINode instruction.

LLVM_ABI bool isSuccessor(const MachineBasicBlock *MBB) const

Return true if the specified MBB is a successor of this block.

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 '...

MachineInstrBundleIterator< MachineInstr > iterator

Analysis pass which computes a MachineDominatorTree.

bool dominates(const MachineInstr *A, const MachineInstr *B) const

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

void getAnalysisUsage(AnalysisUsage &AU) const override

getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.

const TargetSubtargetInfo & getSubtarget() const

getSubtarget - Return the subtarget for which this machine code is being compiled.

void dump() const

dump - Print the current MachineFunction to cerr, useful for debugger use.

MachineRegisterInfo & getRegInfo()

getRegInfo - Return information about the registers currently in use.

Function & getFunction()

Return the LLVM function that this machine code represents.

const MachineBasicBlock * getParent() const

unsigned getNumOperands() const

Retuns the total number of operands.

bool isBranch(QueryType Type=AnyInBundle) const

Returns true if this is a conditional, unconditional, or indirect branch.

LLVM_ABI void eraseFromParent()

Unlink 'this' from the containing basic block and delete it.

const MachineOperand & getOperand(unsigned i) const

bool isReg() const

isReg - Tests if this is a MO_Register operand.

MachineBasicBlock * getMBB() const

void setMBB(MachineBasicBlock *MBB)

getReg - Returns the register number.

LLVM_ABI bool isIdenticalTo(const MachineOperand &Other) const

Returns true if this operand is identical to the specified operand except for liveness related flags ...

constexpr bool isVirtual() const

Return true if the specified register number is in the virtual register namespace.

constexpr bool isPhysical() const

Return true if the specified register number is in the physical register namespace.

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

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 bool produceSameValue(const MachineInstr &MI0, const MachineInstr &MI1, const MachineRegisterInfo *MRI=nullptr) const

Return true if two machine instructions would produce identical values.

virtual const TargetInstrInfo * getInstrInfo() const

#define llvm_unreachable(msg)

Marks that the current location is not supposed to be reachable.

NodeAddr< DefNode * > Def

NodeAddr< UseNode * > Use

This is an optimization pass for GlobalISel generic memory operations.

LLVM_ABI raw_ostream & dbgs()

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

FunctionPass * createPPCBranchCoalescingPass()

createPPCBranchCoalescingPass - returns an instance of the Branch Coalescing Pass

Definition PPCBranchCoalescing.cpp:190

ArrayRef(const T &OneElt) -> ArrayRef< T >