VirtRegMap.cpp Source File (original) (raw)

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

45#include

46#include

47#include

49using namespace llvm;

51#define DEBUG_TYPE "regalloc"

53 STATISTIC(NumSpillSlots, "Number of spill slots allocated");

54 STATISTIC(NumIdCopies, "Number of identity moves eliminated after rewriting");

63 false, true)

66 MRI = &mf.getRegInfo();

67 TII = mf.getSubtarget().getInstrInfo();

68 TRI = mf.getSubtarget().getRegisterInfo();

69 MF = &mf;

71 Virt2PhysMap.clear();

72 Virt2StackSlotMap.clear();

73 Virt2SplitMap.clear();

74 Virt2ShapeMap.clear();

76 grow();

77}

81 Virt2PhysMap.resize(NumRegs);

82 Virt2StackSlotMap.resize(NumRegs);

83 Virt2SplitMap.resize(NumRegs);

84}

88 assert(!Virt2PhysMap[virtReg] &&

89 "attempt to assign physical register to already mapped "

90 "virtual register");

94 "Attempt to map virtReg to a reserved physReg");

95 Virt2PhysMap[virtReg] = physReg;

96}

101

103 Align CurrentAlign = ST.getFrameLowering()->getStackAlign();

104 if (Alignment > CurrentAlign && !ST.getRegisterInfo()->canRealignStack(*MF)) {

105 Alignment = CurrentAlign;

106 }

108 ++NumSpillSlots;

109 return SS;

110}

111

115 return false;

119}

120

123 if (Hint.second.isPhysical())

124 return true;

125 if (Hint.second.isVirtual())

126 return hasPhys(Hint.second);

127 return false;

128}

129

133 "attempt to assign stack slot to already spilled register");

135 return Virt2StackSlotMap[virtReg] = createSpillSlot(RC);

136}

137

141 "attempt to assign stack slot to already spilled register");

144 "illegal fixed frame index");

145 Virt2StackSlotMap[virtReg] = SS;

146}

147

149 OS << "********** REGISTER MAP **********\n";

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

152 if (Virt2PhysMap[Reg]) {

153 OS << '[' << printReg(Reg, TRI) << " -> "

154 << printReg(Virt2PhysMap[Reg], TRI) << "] "

156 }

157 }

158

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

162 OS << '[' << printReg(Reg, TRI) << " -> fi#" << Virt2StackSlotMap[Reg]

164 }

165 }

166 OS << '\n';

167}

168

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

172}

173#endif

174

176

182}

183

187 VRM.init(MF);

188 return VRM;

189}

190

191

192

193

194

195

196

197

198

199

200namespace {

201

213 bool ClearVirtRegs;

214

215 void rewrite();

216 void addMBBLiveIns();

217 bool readsUndefSubreg(const MachineOperand &MO) const;

222 LaneBitmask liveOutUndefPhiLanesForUndefSubregDef(

225

226public:

227 static char ID;

228 VirtRegRewriter(bool ClearVirtRegs_ = true) :

230 ClearVirtRegs(ClearVirtRegs_) {}

231

232 void getAnalysisUsage(AnalysisUsage &AU) const override;

233

235

237 if (ClearVirtRegs) {

239 MachineFunctionProperties::Property::NoVRegs);

240 }

241

243 }

244};

245

246}

247

248char VirtRegRewriter::ID = 0;

249

251

253 "Virtual Register Rewriter", false, false)

262

263void VirtRegRewriter::getAnalysisUsage(AnalysisUsage &AU) const {

264 AU.setPreservesCFG();

274

275 if (!ClearVirtRegs)

277

279}

280

281bool VirtRegRewriter::runOnMachineFunction(MachineFunction &fn) {

282 MF = &fn;

286 Indexes = &getAnalysis().getSI();

287 LIS = &getAnalysis().getLIS();

288 LRM = &getAnalysis().getLRM();

289 VRM = &getAnalysis().getVRM();

290 DebugVars = &getAnalysis().getLDV();

291 LLVM_DEBUG(dbgs() << "********** REWRITE VIRTUAL REGISTERS **********\n"

292 << "********** Function: " << MF->getName() << '\n');

294

295

297

298

299 addMBBLiveIns();

300

301

302 rewrite();

303

304 if (ClearVirtRegs) {

305

306

307

308

310

311

312

314 MRI->clearVirtRegs();

315 }

316

317 return true;

318}

319

320void VirtRegRewriter::addLiveInsForSubRanges(const LiveInterval &LI,

324

325 using SubRangeIteratorPair =

326 std::pair<const LiveInterval::SubRange *, LiveInterval::const_iterator>;

327

332 SubRanges.push_back(std::make_pair(&SR, SR.begin()));

333 if ( First .isValid() || SR.segments.front().start < First)

334 First = SR.segments.front().start;

335 if ( Last .isValid() || SR.segments.back().end > Last)

336 Last = SR.segments.back().end;

337 }

338

339

340

344

345

347 for (auto &RangeIterPair : SubRanges) {

350 while (SRI != SR->end() && SRI->end <= MBBBegin)

351 ++SRI;

352 if (SRI == SR->end())

353 continue;

354 if (SRI->start <= MBBBegin)

356 }

357 if (LaneMask.none())

358 continue;

361 }

362}

363

364

365

366void VirtRegRewriter::addMBBLiveIns() {

367 for (unsigned Idx = 0, IdxE = MRI->getNumVirtRegs(); Idx != IdxE; ++Idx) {

369 if (MRI->reg_nodbg_empty(VirtReg))

370 continue;

373 continue;

374

375

377 if (!PhysReg) {

378

379

380 assert(!ClearVirtRegs && "Unmapped virtual register");

381 continue;

382 }

383

385 addLiveInsForSubRanges(LI, PhysReg);

386 } else {

387

388

389

391 for (const auto &Seg : LI) {

393 for (; I != Indexes->MBBIndexEnd() && I->first < Seg.end; ++I) {

396 }

397 }

398 }

399 }

400

401

402

405}

406

407

408

409bool VirtRegRewriter::readsUndefSubreg(const MachineOperand &MO) const {

410

412 return true;

413

418

419

421 "Reads of completely dead register should be marked undef already");

422 unsigned SubRegIdx = MO.getSubReg();

424 LaneBitmask UseMask = TRI->getSubRegIndexLaneMask(SubRegIdx);

425

427 if ((SR.LaneMask & UseMask).any() && SR.liveAt(BaseIndex))

428 return false;

429 }

430 return true;

431}

432

433void VirtRegRewriter::handleIdentityCopy(MachineInstr &MI) {

434 if (.isIdentityCopy())

435 return;

437 ++NumIdCopies;

438

439 Register DstReg = MI.getOperand(0).getReg();

440

441

442

444 return;

445

446 RewriteRegs.insert(DstReg);

447

448

449

450

451

452

453

454 if (MI.getOperand(1).isUndef() || MI.getNumOperands() > 2) {

455 MI.setDesc(TII->get(TargetOpcode::KILL));

457 return;

458 }

459

460 if (Indexes)

462 MI.eraseFromBundle();

464}

465

466

467

468

469

470void VirtRegRewriter::expandCopyBundle(MachineInstr &MI) const {

471 if (.isCopy() && .isKill())

472 return;

473

474 if (MI.isBundledWithPred() && .isBundledWithSucc()) {

476

477

480 std::next(MI.getReverseIterator()), E = MBB.instr_rend();

481 I != E && I->isBundledWithSucc(); ++I) {

482 if (->isCopy() && ->isKill())

483 return;

484 MIs.push_back(&*I);

485 }

487

488 auto anyRegsAlias = [](const MachineInstr *Dst,

492 if (Src != Dst)

493 if (TRI->regsOverlap(Dst->getOperand(0).getReg(),

494 Src->getOperand(1).getReg()))

495 return true;

496 return false;

497 };

498

499

500

501

502 for (int E = MIs.size(), PrevE = E; E > 1; PrevE = E) {

503 for (int I = E; I--; )

504 if (!anyRegsAlias(MIs[I], ArrayRef(MIs).take_front(E), TRI)) {

505 if (I + 1 != E)

507 --E;

508 }

509 if (PrevE == E) {

510 MF->getFunction().getContext().emitError(

511 "register rewriting failed: cycle in copy bundle");

512 break;

513 }

514 }

515

518

519

520

521 if (BundledMI != BundleStart) {

523 MBB.insert(BundleStart, BundledMI);

524 } else if (BundledMI->isBundledWithSucc()) {

525 BundledMI->unbundleFromSucc();

526 BundleStart = &*std::next(BundledMI->getIterator());

527 }

528

529 if (Indexes && BundledMI != FirstMI)

531 }

532 }

533}

534

535

536

537

538bool VirtRegRewriter::subRegLiveThrough(const MachineInstr &MI,

543 for (MCRegUnit Unit : TRI->regunits(SuperPhysReg)) {

545

546

547

548

549

550

551

552

553

554

555 if (UnitRange.liveAt(AfterMIDefs) && UnitRange.liveAt(BeforeMIUses))

556 return true;

557 }

558 return false;

559}

560

561

562

563

564LaneBitmask VirtRegRewriter::liveOutUndefPhiLanesForUndefSubregDef(

569

571

576 LiveOutUndefLanes |= NeedImpDefLanes;

577 }

578 }

579 }

580

585 LiveOutUndefLanes &= ~InterferingLanes;

586

588 dbgs() << "Need live out undef defs for " << printReg(PhysReg)

589 << LiveOutUndefLanes << " from " << printMBBReference(MBB) << '\n';

590 });

591

592 return LiveOutUndefLanes;

593}

594

595void VirtRegRewriter::rewrite() {

596 bool NoSubRegLiveness = MRI ->subRegLivenessEnabled();

600

606

608 MRI->addPhysRegsUsedFromRegMask(MO.getRegMask());

609

611 continue;

614 if (!PhysReg)

615 continue;

616

618

619 RewriteRegs.insert(PhysReg);

620 assert(( MRI ->isReserved(PhysReg) ||

621 MF->getProperties().hasProperty(

623 "Reserved register assignment");

624

625

628 if (NoSubRegLiveness || MRI ->shouldTrackSubRegLiveness(VirtReg)) {

629

630

631

633 (MO.isDef() && subRegLiveThrough(MI, PhysReg)))

635

636 if (MO.isDef()) {

637

640 else

642 }

643 } else {

644 if (MO.isUse()) {

645 if (readsUndefSubreg(MO))

646

647

648

650 } else if (!MO.isDead()) {

654

656 liveOutUndefPhiLanesForUndefSubregDef(LI, *MBBI, SubReg,

657 PhysReg, MI);

658 if (LiveOutUndefLanes.any()) {

660

661

662

663 if ( TRI ->getCoveringSubRegIndexes(MRI->getRegClass(VirtReg),

664 LiveOutUndefLanes,

665 CoveringIndexes))

667 "cannot represent required subregister defs");

668

669

670

671

672

673

674 for (unsigned SubIdx : CoveringIndexes)

675 SuperDefs.push_back(TRI->getSubReg(PhysReg, SubIdx));

676 }

677 }

678 }

679 }

680

681

682

683

684

685 if (MO.isDef()) {

688 }

689

690

691 PhysReg = TRI->getSubReg(PhysReg, SubReg);

692 assert(PhysReg.isValid() && "Invalid SubReg for physical register");

694 }

695

696

699 }

700

701

702

703 while (!SuperKills.empty())

705

706 while (!SuperDeads.empty())

708

709 while (!SuperDefs.empty())

711

713

714 expandCopyBundle(MI);

715

716

717 handleIdentityCopy(MI);

718 }

719 }

720

721 if (LIS) {

722

723

724 for (Register PhysReg : RewriteRegs) {

725 for (MCRegUnit Unit : TRI->regunits(PhysReg)) {

727 }

728 }

729 }

730

731 RewriteRegs.clear();

732}

733

735 return new VirtRegRewriter(ClearVirtRegs);

736}

unsigned const MachineRegisterInfo * MRI

MachineBasicBlock MachineBasicBlock::iterator MBBI

#define LLVM_DUMP_METHOD

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

Returns the sub type a function will return at a given Idx Should correspond to the result type of an ExtractValue instruction executed with just that one unsigned Idx

const HexagonInstrInfo * TII

A common definition of LaneBitmask for use in TableGen and CodeGen.

unsigned const TargetRegisterInfo * TRI

ModuleAnalysisManager MAM

#define INITIALIZE_PASS_DEPENDENCY(depName)

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

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

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

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

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)

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

PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)

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

Represent the analysis usage information of a pass.

ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...

Implements a dense probed hash-table based set.

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

void emitDebugValues(VirtRegMap *VRM)

emitDebugValues - Emit new DBG_VALUE instructions reflecting the changes that happened during registe...

A live range for subregisters.

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

bool hasSubRanges() const

Returns true if subregister liveness information is available.

iterator_range< subrange_iterator > subranges()

void addKillFlags(const VirtRegMap *)

Add kill flags to any instruction that kills a virtual register.

SlotIndex getInstructionIndex(const MachineInstr &Instr) const

Returns the base index of the given instruction.

LiveRange & getRegUnit(unsigned Unit)

Return the live range for register unit Unit.

LiveInterval & getInterval(Register Reg)

MachineBasicBlock * intervalIsInOneMBB(const LiveInterval &LI) const

If LI is confined to a single basic block, return a pointer to that block.

void removeRegUnit(unsigned Unit)

Remove computed live range for register unit Unit.

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

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

This class represents the liveness of a register, stack slot, etc.

bool liveAt(SlotIndex index) const

LaneBitmask checkInterferenceLanes(SlotIndex Start, SlotIndex End, MCRegister PhysReg)

Check for interference in the segment [Start, End) that may prevent assignment to PhysReg,...

Wrapper class representing physical registers. Should be passed by value.

constexpr bool isValid() const

constexpr bool isPhysical() const

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

instr_iterator insert(instr_iterator I, MachineInstr *M)

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

void sortUniqueLiveIns()

Sorts and uniques the LiveIns vector.

void print(raw_ostream &OS, const SlotIndexes *=nullptr, bool IsStandalone=true) const

reverse_instr_iterator instr_rend()

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

Adds the specified register as a live in.

iterator_range< succ_iterator > successors()

Instructions::reverse_iterator reverse_instr_iterator

int CreateSpillStackObject(uint64_t Size, Align Alignment)

Create a new statically sized stack object that represents a spill slot, returning a nonnegative iden...

int getObjectIndexBegin() const

Return the minimum frame object index.

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.

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

MachineFunctionProperties & set(Property P)

bool hasProperty(Property P) const

const TargetSubtargetInfo & getSubtarget() const

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

StringRef getName() const

getName - Return the name of the corresponding LLVM function.

MachineFrameInfo & getFrameInfo()

getFrameInfo - Return the frame info object for the current function.

MachineRegisterInfo & getRegInfo()

getRegInfo - Return information about the registers currently in use.

const MachineFunctionProperties & getProperties() const

Get the function properties.

Representation of each machine instruction.

MachineInstr * removeFromBundle()

Unlink this instruction from its basic block and return it without deleting it.

MachineOperand class - Representation of each machine instruction operand.

void setSubReg(unsigned subReg)

unsigned getSubReg() const

void setIsInternalRead(bool Val=true)

bool readsReg() const

readsReg - Returns true if this operand reads the previous value of its register.

void setIsRenamable(bool Val=true)

bool isReg() const

isReg - Tests if this is a MO_Register operand.

bool isRegMask() const

isRegMask - Tests if this is a MO_RegisterMask operand.

void setReg(Register Reg)

Change the register this operand corresponds to.

MachineInstr * getParent()

getParent - Return the instruction that this operand belongs to.

void setIsUndef(bool Val=true)

getReg - Returns the register number.

const uint32_t * getRegMask() const

getRegMask - Returns a bit mask of registers preserved by this RegMask operand.

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

getSimpleHint - same as getRegAllocationHint except it will only return a target independent hint.

const TargetRegisterClass * getRegClass(Register Reg) const

Return the register class of the specified virtual register.

std::pair< unsigned, Register > getRegAllocationHint(Register VReg) const

getRegAllocationHint - Return the register allocation hint for the specified virtual register.

unsigned getNumVirtRegs() const

getNumVirtRegs - Return the number of virtual registers created.

A Module instance is used to store all the information related to an LLVM module.

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 isValid() const

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 getBoundaryIndex() const

Returns the boundary index for associated with this index.

SlotIndex getBaseIndex() const

Returns the base index for associated with this index.

SlotIndex getRegSlot(bool EC=false) const

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

SlotIndex insertMachineInstrInMaps(MachineInstr &MI, bool Late=false)

Insert the given machine instruction into the mapping.

MBBIndexIterator getMBBLowerBound(MBBIndexIterator Start, SlotIndex Idx) const

Get an iterator pointing to the first IdxMBBPair with SlotIndex greater than or equal to Idx.

void removeSingleMachineInstrFromMaps(MachineInstr &MI)

Removes a single machine instruction MI from the mapping.

MBBIndexIterator MBBIndexBegin() const

Returns an iterator for the begin of the idx2MBBMap.

MBBIndexIterator MBBIndexEnd() const

Return an iterator for the end of the idx2MBBMap.

SmallVectorImpl< IdxMBBPair >::const_iterator MBBIndexIterator

Iterator over the idx2MBBMap (sorted pairs of slot index of basic block begin and basic block)

void push_back(const T &Elt)

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

TargetInstrInfo - Interface to description of machine instruction set.

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

Align getSpillAlign(const TargetRegisterClass &RC) const

Return the minimum required alignment in bytes for a spill slot for a register of this class.

unsigned getSpillSize(const TargetRegisterClass &RC) const

Return the size in bytes of the stack slot allocated to hold a spilled copy of a register from class ...

const char * getRegClassName(const TargetRegisterClass *Class) const

Returns the name of the register class.

virtual const TargetRegisterInfo * getRegisterInfo() const

getRegisterInfo - If register information is available, return it.

virtual const TargetInstrInfo * getInstrInfo() const

VirtRegMap run(MachineFunction &MF, MachineFunctionAnalysisManager &MAM)

PreservedAnalyses run(MachineFunction &MF, MachineFunctionAnalysisManager &MFAM)

bool hasKnownPreference(Register VirtReg) const

returns true if VirtReg has a known preferred register.

void init(MachineFunction &MF)

int assignVirt2StackSlot(Register virtReg)

create a mapping for the specifed virtual register to the next available stack slot

void clearAllVirt()

clears all virtual to physical register mappings

bool hasPreferredPhys(Register VirtReg) const

returns true if VirtReg is assigned to its preferred physreg.

MachineRegisterInfo & getRegInfo() const

void assignVirt2Phys(Register virtReg, MCRegister physReg)

creates a mapping for the specified virtual register to the specified physical register

MCRegister getPhys(Register virtReg) const

returns the physical register mapped to the specified virtual register

void print(raw_ostream &OS, const Module *M=nullptr) const

bool hasPhys(Register virtReg) const

returns true if the specified virtual register is mapped to a physical register

static constexpr int NO_STACK_SLOT

std::pair< iterator, bool > insert(const ValueT &V)

This class implements an extremely fast bulk output stream that can only output to a stream.

#define llvm_unreachable(msg)

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

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.

This is an optimization pass for GlobalISel generic memory operations.

iterator_range< early_inc_iterator_impl< detail::IterOfRange< RangeT > > > make_early_inc_range(RangeT &&Range)

Make a range that does early increment to allow mutation of the underlying range without disrupting i...

auto reverse(ContainerTy &&C)

raw_ostream & dbgs()

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

@ First

Helpers to iterate all locations in the MemoryEffectsBase class.

char & VirtRegRewriterID

VirtRegRewriter pass.

FunctionPass * createVirtRegRewriter(bool ClearVirtRegs=true)

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.

void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)

Implement std::swap in terms of BitVector swap.

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

A special type used by analysis passes to provide an address that identifies that particular analysis...

constexpr bool none() const

constexpr bool any() const