PHIElimination.cpp Source File (original) (raw)

43#include

44#include

45#include

47using namespace llvm;

49#define DEBUG_TYPE "phi-node-elimination"

54 cl::desc("Disable critical edge splitting "

55 "during PHI elimination"));

60 cl::desc("Split all critical edges during "

61 "PHI elimination"));

65 cl::desc("Do not use an early exit if isLiveOutPastPHIs returns true."));

67namespace {

69class PHIEliminationImpl {

82 bool AllEdgesCritical);

101

102 using BBVRegPair = std::pair<unsigned, Register>;

104

105

106 VRegPHIUse VRegPHIUseCount;

107

108

110

111

112 using LoweredPHIMap =

114 LoweredPHIMap LoweredPHIs;

115

118

119public:

124 auto *MDTWrapper =

126 LV = LVWrapper ? &LVWrapper->getLV() : nullptr;

127 LIS = LISWrapper ? &LISWrapper->getLIS() : nullptr;

128 MLI = MLIWrapper ? &MLIWrapper->getLI() : nullptr;

129 MDT = MDTWrapper ? &MDTWrapper->getDomTree() : nullptr;

130 }

131

137

139};

140

142public:

143 static char ID;

144

147 }

148

150 PHIEliminationImpl Impl(this);

151 return Impl.run(MF);

152 }

153

156 MachineFunctionProperties::Property::NoPHIs);

157 }

158

160};

161

162}

163

167 PHIEliminationImpl Impl(MF, MFAM);

168 bool Changed = Impl.run(MF);

169 if (!Changed)

177 return PA;

178}

179

180 STATISTIC(NumLowered, "Number of phis lowered");

181 STATISTIC(NumCriticalEdgesSplit, "Number of critical edges split");

182 STATISTIC(NumReused, "Number of reused lowered phis");

183

184char PHIElimination::ID = 0;

185

187

189 "Eliminate PHI nodes for register allocation", false,

190 false)

194

195void PHIElimination::getAnalysisUsage(AnalysisUsage &AU) const {

203}

204

207

209 if (P) {

210 auto *MDTWrapper =

212 MDT = MDTWrapper ? &MDTWrapper->getDomTree() : nullptr;

213 } else {

215 }

217

218 bool Changed = false;

219

220

222

223

224 std::vector<SparseBitVector<>> LiveInSets;

225 if (LV) {

226 LiveInSets.resize(MF.size());

227 for (unsigned Index = 0, e = MRI->getNumVirtRegs(); Index != e; ++Index) {

228

229

233 continue;

237 while (AliveBlockItr != EndItr) {

238 unsigned BlockNum = *(AliveBlockItr++);

239 LiveInSets[BlockNum].set(Index);

240 }

241

242

244 if (VI.Kills.size() > 1 ||

245 (.Kills.empty() && VI.Kills.front()->getParent() != DefMBB))

246 for (auto *MI : VI.Kills)

247 LiveInSets[MI->getParent()->getNumber()].set(Index);

248 }

249 }

250

251 for (auto &MBB : MF)

252 Changed |=

253 SplitPHIEdges(MF, MBB, MLI, (LV ? &LiveInSets : nullptr), MDTU);

254 }

255

256

257 MRI->leaveSSA();

258

259

260 if (LV || LIS)

261 analyzePHINodes(MF);

262

263

264 for (auto &MBB : MF)

265 Changed |= EliminatePHINodes(MF, MBB);

266

267

270 if (MRI->use_nodbg_empty(DefReg)) {

271 if (LIS)

274 }

275 }

276

277

278 for (auto &I : LoweredPHIs) {

279 if (LIS)

281 MF.deleteMachineInstr(I.first);

282 }

283

284 LoweredPHIs.clear();

285 ImpDefs.clear();

286 VRegPHIUseCount.clear();

287

289

290 return Changed;

291}

292

293

294

295bool PHIEliminationImpl::EliminatePHINodes(MachineFunction &MF,

298 return false;

299

300

303

304

305

306

307

308 bool AllEdgesCritical = MBB.pred_size() >= 2;

310 if (Pred->succ_size() < 2) {

311 AllEdgesCritical = false;

312 break;

313 }

314 }

315

317 LowerPHINode(MBB, LastPHIIt, AllEdgesCritical);

318

319 return true;

320}

321

322

323

327 if (!DI.isImplicitDef())

328 return false;

329 return true;

330}

331

332

335 for (unsigned I = 1, E = MPhi.getNumOperands(); I != E; I += 2) {

338 return false;

339 }

340 return true;

341}

342

345 bool AllEdgesCritical) {

346 ++NumLowered;

347

349

350

352

357

358

360 unsigned IncomingReg = 0;

361 bool EliminateNow = true;

362 bool reusedIncoming = false;

363

364

365

366

370

371

373 TII->get(TargetOpcode::IMPLICIT_DEF), DestReg);

374 else {

375

376

377

378

379 unsigned *Entry = nullptr;

380 if (AllEdgesCritical)

381 Entry = &LoweredPHIs[MPhi];

382 if (Entry && *Entry) {

383

384 IncomingReg = *Entry;

385 reusedIncoming = true;

386 ++NumReused;

388 << *MPhi);

389 } else {

392 if (Entry) {

393 EliminateNow = false;

394 *Entry = IncomingReg;

395 }

396 }

397

398

399 PHICopy = TII->createPHIDestinationCopy(

400 MBB, AfterPHIsIt, MPhi->getDebugLoc(), IncomingReg, DestReg);

401 }

402

404

410 (void)Res;

411 }

412

413

414 if (LV) {

415 if (IncomingReg) {

417

419 bool IsPHICopyAfterOldKill = false;

420

421 if (reusedIncoming && (OldKill = VI.findKill(&MBB))) {

422

423

424

425

426

428 ++I) {

429 if (I == PHICopy)

430 break;

431

432 if (I == OldKill) {

433 IsPHICopyAfterOldKill = true;

434 break;

435 }

436 }

437 }

438

439

440

441

442 if (IsPHICopyAfterOldKill) {

443 LLVM_DEBUG(dbgs() << "Remove old kill from " << *OldKill);

444 LV->removeVirtualRegisterKilled(IncomingReg, *OldKill);

446 }

447

448

449

450

451

452

453 if (!OldKill || IsPHICopyAfterOldKill)

454 LV->addVirtualRegisterKilled(IncomingReg, *PHICopy);

455 }

456

457

458

459

460 LV->removeVirtualRegistersKilled(*MPhi);

461

462

464 LV->addVirtualRegisterDead(DestReg, *PHICopy);

465 LV->removeVirtualRegisterDead(DestReg, *MPhi);

466 }

467 }

468

469

470 if (LIS) {

472

474 if (IncomingReg) {

475

476

479 if (!IncomingVNI)

480 IncomingVNI =

483 MBBStartIndex, DestCopyIndex.getRegSlot(), IncomingVNI));

484 }

485

487 assert(!DestLI.empty() && "PHIs should have non-empty LiveIntervals.");

488

490

492 for (auto &SR : DestLI.subranges())

494

495 for (auto LR : ToUpdate) {

496 auto DestSegment = LR->find(MBBStartIndex);

497 assert(DestSegment != LR->end() &&

498 "PHI destination must be live in block");

499

500 if (LR->endIndex().isDead()) {

501

502

503

504 VNInfo *OrigDestVNI = LR->getVNInfoAt(DestSegment->start);

505 assert(OrigDestVNI && "PHI destination should be live at block entry.");

506 LR->removeSegment(DestSegment->start, DestSegment->start.getDeadSlot());

508 LR->removeValNo(OrigDestVNI);

509 continue;

510 }

511

512

513

514

515 if (DestSegment->start > NewStart) {

516 VNInfo *VNI = LR->getVNInfoAt(DestSegment->start);

517 assert(VNI && "value should be defined for known segment");

518 LR->addSegment(

520 } else if (DestSegment->start < NewStart) {

521 assert(DestSegment->start >= MBBStartIndex);

523 LR->removeSegment(DestSegment->start, NewStart);

524 }

525 VNInfo *DestVNI = LR->getVNInfoAt(NewStart);

526 assert(DestVNI && "PHI destination should be live at its definition.");

527 DestVNI->def = NewStart;

528 }

529 }

530

531

532 if (LV || LIS) {

533 for (unsigned i = 1; i != MPhi->getNumOperands(); i += 2) {

535 --VRegPHIUseCount[BBVRegPair(

538 }

539 }

540 }

541

542

543

545 for (int i = NumSrcs - 1; i >= 0; --i) {

551 "Machine PHI Operands must all be virtual registers!");

552

553

554

556

557

558

559

560 if (!MBBsInsertedInto.insert(&opBlock).second)

561 continue;

562

564 if (SrcRegDef && TII->isUnspillableTerminator(SrcRegDef)) {

567 "Expected operand 0 to be a reg def!");

568

569

571 "Expected a single use from UnspillableTerminator");

573

574

575 if (LV) {

580 }

581

582 continue;

583 }

584

585

586

589

590

592 if (!reusedIncoming && IncomingReg) {

593 if (SrcUndef) {

594

595

596

597 NewSrcInstr =

599 TII->get(TargetOpcode::IMPLICIT_DEF), IncomingReg);

600

601

604 ImpDefs.insert(DefMI);

605 } else {

606

607

608 NewSrcInstr = TII->createPHISourceCopy(opBlock, InsertPos, nullptr,

609 SrcReg, SrcSubReg, IncomingReg);

610 }

611 }

612

613

614

615

616 if (LV && !SrcUndef &&

617 !VRegPHIUseCount[BBVRegPair(opBlock.getNumber(), SrcReg)] &&

618 !LV->isLiveOut(SrcReg, opBlock)) {

619

620

621

622

623

624

625

626

627

628

629

630

631

632

633

634

638 if (Term->readsRegister(SrcReg, nullptr))

639 KillInst = Term;

640 }

641

642 if (KillInst == opBlock.end()) {

643

644

645 if (reusedIncoming || !IncomingReg) {

646

647 KillInst = InsertPos;

648 while (KillInst != opBlock.begin()) {

649 --KillInst;

650 if (KillInst->isDebugInstr())

651 continue;

652 if (KillInst->readsRegister(SrcReg, nullptr))

653 break;

654 }

655 } else {

656

657 KillInst = NewSrcInstr;

658 }

659 }

660 assert(KillInst->readsRegister(SrcReg, nullptr) &&

661 "Cannot find kill instruction");

662

663

664 LV->addVirtualRegisterKilled(SrcReg, *KillInst);

665

666

667 unsigned opBlockNum = opBlock.getNumber();

668 LV->getVarInfo(SrcReg).AliveBlocks.reset(opBlockNum);

669 }

670

671 if (LIS) {

672 if (NewSrcInstr) {

675 }

676

677 if (!SrcUndef &&

678 !VRegPHIUseCount[BBVRegPair(opBlock.getNumber(), SrcReg)]) {

680

685

686

687 if (VNI && VNI->def != startIdx) {

689 break;

690 }

691 }

692

697 if (Term->readsRegister(SrcReg, nullptr))

698 KillInst = Term;

699 }

700

701 if (KillInst == opBlock.end()) {

702

703

704 if (reusedIncoming || !IncomingReg) {

705

706 KillInst = InsertPos;

707 while (KillInst != opBlock.begin()) {

708 --KillInst;

709 if (KillInst->isDebugInstr())

710 continue;

711 if (KillInst->readsRegister(SrcReg, nullptr))

712 break;

713 }

714 } else {

715

716 KillInst = std::prev(InsertPos);

717 }

718 }

719 assert(KillInst->readsRegister(SrcReg, nullptr) &&

720 "Cannot find kill instruction");

721

725 for (auto &SR : SrcLI.subranges()) {

726 SR.removeSegment(LastUseIndex.getRegSlot(),

728 }

729 }

730 }

731 }

732 }

733

734

735 if (EliminateNow) {

736 if (LIS)

739 }

740}

741

742

743

744

745

746void PHIEliminationImpl::analyzePHINodes(const MachineFunction &MF) {

747 for (const auto &MBB : MF) {

748 for (const auto &BBI : MBB) {

749 if (!BBI.isPHI())

750 break;

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

752 if (!BBI.getOperand(i).isUndef()) {

753 ++VRegPHIUseCount[BBVRegPair(

754 BBI.getOperand(i + 1).getMBB()->getNumber(),

755 BBI.getOperand(i).getReg())];

756 }

757 }

758 }

759 }

760}

761

762bool PHIEliminationImpl::SplitPHIEdges(

766 return false;

767

769 bool IsLoopHeader = CurLoop && &MBB == CurLoop->getHeader();

770

771 bool Changed = false;

773 BBI != BBE && BBI->isPHI(); ++BBI) {

774 for (unsigned i = 1, e = BBI->getNumOperands(); i != e; i += 2) {

775 Register Reg = BBI->getOperand(i).getReg();

777

779 continue;

780

781

782

784 continue;

787 continue;

788

789

790

791

792

793

794

795 bool ShouldSplit = isLiveOutPastPHIs(Reg, PreMBB);

797 continue;

798 if (ShouldSplit) {

802 }

803

804

805

806

807

808

809

810

811

812 ShouldSplit = ShouldSplit && !isLiveIn(Reg, &MBB);

813

814

815 if (!ShouldSplit && CurLoop != PreLoop) {

817 dbgs() << "Split wouldn't help, maybe avoid loop copies?\n";

818 if (PreLoop)

819 dbgs() << "PreLoop: " << *PreLoop;

820 if (CurLoop)

821 dbgs() << "CurLoop: " << *CurLoop;

822 });

823

824

825

826

827 ShouldSplit = PreLoop && !PreLoop->contains(CurLoop);

828 }

830 continue;

833 LLVM_DEBUG(dbgs() << "Failed to split critical edge.\n");

834 continue;

835 }

836 Changed = true;

837 ++NumCriticalEdgesSplit;

838 }

839 }

840 return Changed;

841}

842

844 assert((LV || LIS) &&

845 "isLiveIn() requires either LiveVariables or LiveIntervals");

846 if (LIS)

848 else

849 return LV->isLiveIn(Reg, *MBB);

850}

851

852bool PHIEliminationImpl::isLiveOutPastPHIs(Register Reg,

854 assert((LV || LIS) &&

855 "isLiveOutPastPHIs() requires either LiveVariables or LiveIntervals");

856

857

858

859

860

861 if (LIS) {

865 return true;

866 return false;

867 } else {

868 return LV->isLiveOut(Reg, *MBB);

869 }

870}

unsigned const MachineRegisterInfo * MRI

for(const MachineOperand &MO :llvm::drop_begin(OldMI.operands(), Desc.getNumOperands()))

MachineInstrBuilder MachineInstrBuilder & DefMI

Unify divergent function exit nodes

This file defines the DenseMap class.

const HexagonInstrInfo * TII

static bool allPhiOperandsUndefined(const MachineInstr &MPhi, const MachineRegisterInfo &MRI)

Return true if all sources of the phi node are implicit_def's, or undef's.

Eliminate PHI nodes for register allocation

static cl::opt< bool > NoPhiElimLiveOutEarlyExit("no-phi-elim-live-out-early-exit", cl::init(false), cl::Hidden, cl::desc("Do not use an early exit if isLiveOutPastPHIs returns true."))

static bool isImplicitlyDefined(unsigned VirtReg, const MachineRegisterInfo &MRI)

Return true if all defs of VirtReg are implicit-defs.

static cl::opt< bool > DisableEdgeSplitting("disable-phi-elim-edge-splitting", cl::init(false), cl::Hidden, cl::desc("Disable critical edge splitting " "during PHI elimination"))

static cl::opt< bool > SplitAllCriticalEdges("phi-elim-split-all-critical-edges", cl::init(false), cl::Hidden, cl::desc("Split all critical edges during " "PHI elimination"))

#define INITIALIZE_PASS_DEPENDENCY(depName)

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

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

assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())

static bool isLiveOut(const MachineBasicBlock &MBB, unsigned Reg)

bool isDead(const MachineInstr &MI, const MachineRegisterInfo &MRI)

This file defines the SmallPtrSet class.

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

#define STATISTIC(VARNAME, DESC)

A container for analyses that lazily runs them and caches their results.

PassT::Result * getCachedResult(IRUnitT &IR) const

Get the cached result of an analysis pass for a given IR unit.

Represent the analysis usage information of a pass.

LiveInterval - This class represents the liveness of a register, or stack slot.

iterator_range< subrange_iterator > subranges()

SlotIndex getMBBStartIdx(const MachineBasicBlock *mbb) const

Return the first index in the given basic block.

SlotIndex InsertMachineInstrInMaps(MachineInstr &MI)

LiveInterval & getOrCreateEmptyInterval(Register Reg)

Return an existing interval for Reg.

SlotIndex getInstructionIndex(const MachineInstr &Instr) const

Returns the base index of the given instruction.

void RemoveMachineInstrFromMaps(MachineInstr &MI)

VNInfo::Allocator & getVNInfoAllocator()

SlotIndex getMBBEndIdx(const MachineBasicBlock *mbb) const

Return the last index in the given basic block.

LiveInterval & getInterval(Register Reg)

LiveInterval::Segment addSegmentToEndOfBlock(Register Reg, MachineInstr &startInst)

Given a register and an instruction, adds a live segment from that instruction to the end of its MBB.

bool isLiveInToMBB(const LiveRange &LR, const MachineBasicBlock *mbb) const

iterator addSegment(Segment S)

Add the specified Segment to this range, merging segments as appropriate.

bool liveAt(SlotIndex index) const

VNInfo * getNextValue(SlotIndex Def, VNInfo::Allocator &VNInfoAllocator)

getNextValue - Create a new value number and return it.

void removeSegment(SlotIndex Start, SlotIndex End, bool RemoveDeadValNo=false)

Remove the specified interval from this live range.

VNInfo * getVNInfoAt(SlotIndex Idx) const

getVNInfoAt - Return the VNInfo that is live at Idx, or NULL.

bool contains(const LoopT *L) const

Return true if the specified loop is contained within in this loop.

BlockT * getHeader() const

LoopT * getLoopFor(const BlockT *BB) const

Return the inner most loop that BB lives in.

unsigned pred_size() const

bool isEHPad() const

Returns true if the block is a landing pad.

MachineBasicBlock * SplitCriticalEdge(MachineBasicBlock *Succ, Pass &P, std::vector< SparseBitVector<> > *LiveInSets=nullptr, MachineDomTreeUpdater *MDTU=nullptr)

Split the critical edge from this block to the given successor block, and return the newly created bl...

int getNumber() const

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

iterator SkipPHIsAndLabels(iterator I)

Return the first instruction in MBB after I that is not a PHI or a label.

MachineInstr * remove(MachineInstr *I)

Remove the unbundled instruction from the instruction list without deleting it.

unsigned succ_size() const

const MachineFunction * getParent() const

Return the MachineFunction containing this basic block.

iterator_range< succ_iterator > successors()

iterator_range< pred_iterator > predecessors()

Analysis pass which computes a MachineDominatorTree.

DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to compute a normal dominat...

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.

virtual MachineFunctionProperties getSetProperties() const

virtual bool runOnMachineFunction(MachineFunction &MF)=0

runOnMachineFunction - This method must be overloaded to perform the desired machine code transformat...

Properties which a MachineFunction may have at a given point in time.

MachineFunctionProperties & set(Property P)

Location of a PHI instruction that is also a debug-info variable value, for the duration of register ...

const TargetSubtargetInfo & getSubtarget() const

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

void deleteMachineInstr(MachineInstr *MI)

DeleteMachineInstr - Delete the given MachineInstr.

MachineRegisterInfo & getRegInfo()

getRegInfo - Return information about the registers currently in use.

DenseMap< unsigned, DebugPHIRegallocPos > DebugPHIPositions

Map of debug instruction numbers to the position of their PHI instructions during register allocation...

Representation of each machine instruction.

bool isImplicitDef() const

const MachineBasicBlock * getParent() const

unsigned getNumOperands() const

Retuns the total number of operands.

unsigned peekDebugInstrNum() const

Examine the instruction number of this MachineInstr.

const DebugLoc & getDebugLoc() const

Returns the debug location id of this MachineInstr.

void eraseFromParent()

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

const MachineOperand & getOperand(unsigned i) const

Analysis pass that exposes the MachineLoopInfo for a machine function.

MachineOperand class - Representation of each machine instruction operand.

unsigned getSubReg() const

bool isReg() const

isReg - Tests if this is a MO_Register operand.

MachineBasicBlock * getMBB() const

void setReg(Register Reg)

Change the register this operand corresponds to.

getReg - Returns the register number.

MachineRegisterInfo - Keep track of information for virtual and physical registers,...

const TargetRegisterClass * getRegClass(Register Reg) const

Return the register class of the specified virtual register.

createVirtualRegister - Create and return a new virtual register in the function with the specified r...

PreservedAnalyses run(MachineFunction &MF, MachineFunctionAnalysisManager &MFAM)

static PassRegistry * getPassRegistry()

getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...

A set of analyses that are preserved following a run of a transformation pass.

static PreservedAnalyses all()

Construct a special preserved set that preserves all passes.

Wrapper class representing virtual and physical registers.

static Register index2VirtReg(unsigned Index)

Convert a 0-based index to a virtual register number.

constexpr bool isVirtual() const

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

SlotIndex - An opaque wrapper around machine indexes.

SlotIndex getRegSlot(bool EC=false) const

Returns the register use/def slot in the current instruction for a normal or early-clobber def.

std::pair< iterator, bool > insert(PtrType Ptr)

Inserts Ptr if and only if there is no element in the container equal to Ptr.

SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.

void push_back(const T &Elt)

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

SparseBitVectorIterator iterator

TargetInstrInfo - Interface to description of machine instruction set.

virtual const TargetInstrInfo * getInstrInfo() const

VNInfo - Value Number Information.

SlotIndex def

The index of the defining instruction.

unsigned ID

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

Reg

All possible values of the reg field in the ModR/M byte.

initializer< Ty > init(const Ty &Val)

PointerTypeMap run(const Module &M)

Compute the PointerTypeMap for the module M.

This is an optimization pass for GlobalISel generic memory operations.

MachineInstrBuilder BuildMI(MachineFunction &MF, const MIMetadata &MIMD, const MCInstrDesc &MCID)

Builder interface. Specify how to create the initial instruction itself.

PreservedAnalyses getMachineFunctionPassPreservedAnalyses()

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

void initializePHIEliminationPass(PassRegistry &)

raw_ostream & dbgs()

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

char & PHIEliminationID

PHIElimination - This pass eliminates machine instruction PHI nodes by inserting copy instructions.

MachineBasicBlock::iterator findPHICopyInsertPoint(MachineBasicBlock *MBB, MachineBasicBlock *SuccMBB, unsigned SrcReg)

findPHICopyInsertPoint - Find a safe place in MBB to insert a copy from SrcReg when following the CFG...

Printable printReg(Register Reg, const TargetRegisterInfo *TRI=nullptr, unsigned SubIdx=0, const MachineRegisterInfo *MRI=nullptr)

Prints virtual and physical registers with or without a TRI instance.

Printable printMBBReference(const MachineBasicBlock &MBB)

Prints a machine basic block reference.

This represents a simple continuous liveness interval for a value.

VarInfo - This represents the regions where a virtual register is live in the program.

SparseBitVector AliveBlocks

AliveBlocks - Set of blocks in which this value is alive completely through.