RegisterScavenging.cpp Source File (original) (raw)

39#include

40#include

41#include

42#include

44using namespace llvm;

46#define DEBUG_TYPE "reg-scavenging"

48 STATISTIC(NumScavengedRegs, "Number of frame index regs scavenged");

52}

59 LiveUnits.init(*TRI);

61 this->MBB = &MBB;

63 for (ScavengedInfo &SI : Scavenged) {

64 SI.Reg = 0;

65 SI.Restore = nullptr;

66 }

67}

70 init(MBB);

73}

76 init(MBB);

79}

86 for (ScavengedInfo &I : Scavenged) {

87 if (I.Restore == &MI) {

88 I.Reg = 0;

89 I.Restore = nullptr;

90 }

91 }

92}

95 if (isReserved(Reg))

96 return includeReserved;

98}

104 << "\n");

105 return Reg;

106 }

107 }

108 return 0;

109}

110

115 Mask.set(Reg);

116 return Mask;

117}

118

119

120

121

122

123

124

125

126static std::pair<MCPhysReg, MachineBasicBlock::iterator>

130 bool RestoreAfter) {

131 bool FoundTo = false;

136 unsigned InstrCountDown = InstrLimit;

139

140 assert(From->getParent() == To->getParent() &&

141 "Target instruction is in other than current basic block, use "

142 "enterBasicBlockEnd first");

143

146

147 Used.accumulate(MI);

148

149 if (I == To) {

150

152 if ( MRI .isReserved(Reg) && Used.available(Reg) &&

154 return std::make_pair(Reg, MBB.end());

155 }

156

157

158 FoundTo = true;

159 Pos = To;

160

161

162

163 if (RestoreAfter)

164 Used.accumulate(*std::next(From));

165 }

166 if (FoundTo) {

167

168

169

172 break;

173

174 if (Survivor == 0 || !Used.available(Survivor)) {

177 if ( MRI .isReserved(Reg) && Used.available(Reg)) {

178 AvilableReg = Reg;

179 break;

180 }

181 }

182 if (AvilableReg == 0)

183 break;

184 Survivor = AvilableReg;

185 }

186 if (--InstrCountDown == 0)

187 break;

188

189

190

191 bool FoundVReg = false;

193 if (MO.isReg() && MO.getReg().isVirtual()) {

194 FoundVReg = true;

195 break;

196 }

197 }

198 if (FoundVReg) {

200 Pos = I;

201 }

203 break;

204 }

205 assert(I != MBB.begin() && "Did not find target instruction while "

206 "iterating backwards");

207 }

208

209 return std::make_pair(Survivor, Pos);

210}

211

213 unsigned i = 0;

214 while (.getOperand(i).isFI()) {

215 ++i;

216 assert(i < MI.getNumOperands() && "Instr doesn't have FrameIndex operand!");

217 }

218 return i;

219}

220

221RegScavenger::ScavengedInfo &

225

226

231

232 unsigned SI = Scavenged.size(), Diff = std::numeric_limits::max();

234 for (unsigned I = 0; I < Scavenged.size(); ++I) {

235 if (Scavenged[I].Reg != 0)

236 continue;

237

238 int FI = Scavenged[I].FrameIndex;

239 if (FI < FIB || FI >= FIE)

240 continue;

243 if (NeedSize > S || NeedAlign > A)

244 continue;

245

246

247

248

249

250

251 unsigned D = (S - NeedSize) + (A.value() - NeedAlign.value());

252 if (D < Diff) {

254 Diff = D;

255 }

256 }

257

258 if (SI == Scavenged.size()) {

259

260

261 Scavenged.push_back(ScavengedInfo(FIE));

262 }

263

264

265 Scavenged[SI].Reg = Reg;

266

267

268

270

271 int FI = Scavenged[SI].FrameIndex;

272 if (FI < FIB || FI >= FIE) {

274 TRI->getName(Reg) + " from class " +

276 ": Cannot scavenge register without an emergency "

277 "spill slot!");

278 }

281

284

285

288

291 }

292 return Scavenged[SI];

293}

294

297 bool RestoreAfter, int SPAdj,

298 bool AllowSpill) {

301

302

306 *MRI, std::prev(MBBI), To, LiveUnits, AllocationOrder, RestoreAfter);

309

310 if (Reg != 0 && SpillBefore == MBB.end()) {

312 << '\n');

313 return Reg;

314 }

315

316 if (!AllowSpill)

317 return 0;

318

319 assert(Reg != 0 && "No register left to scavenge!");

320

322 RestoreAfter ? std::next(MBBI) : MBBI;

323 if (ReloadBefore != MBB.end())

324 LLVM_DEBUG(dbgs() << "Reload before: " << *ReloadBefore << '\n');

325 ScavengedInfo &Scavenged = spill(Reg, RC, SPAdj, SpillBefore, ReloadBefore);

326 Scavenged.Restore = &*std::prev(SpillBefore);

329 << " until " << *SpillBefore);

330 return Reg;

331}

332

333

334

335

336

337

339 Register VReg, bool ReserveAfter) {

341#ifndef NDEBUG

342

344

348 if (CommonMBB == nullptr)

349 CommonMBB = MBB;

350 assert(MBB == CommonMBB && "All defs+uses must be in the same basic block");

351 if (MO.isDef()) {

353 if (.readsRegister(VReg, &TRI)) {

354 assert((!RealDef || RealDef == &MI) &&

355 "Can have at most one definition which is not a redefinition");

356 RealDef = &MI;

357 }

358 }

359 }

360 assert(RealDef != nullptr && "Must have at least 1 Def");

361#endif

362

363

364

365

366

367

368

371 return !MO.getParent()->readsRegister(VReg, &TRI);

372 });

373 assert(FirstDef != MRI.def_end() &&

374 "Must have one definition that does not redefine vreg");

376

377

378

379 int SPAdj = 0;

382 ReserveAfter, SPAdj);

383 MRI.replaceRegWith(VReg, SReg);

384 ++NumScavengedRegs;

385 return SReg;

386}

387

388

389

390

396

397 unsigned InitialNumVirtRegs = MRI.getNumVirtRegs();

398 bool NextInstructionReadsVReg = false;

400

402 --I;

403

404

405 if (NextInstructionReadsVReg) {

409 if (!MO.isReg())

410 continue;

412

413

414

415 if (!Reg.isVirtual() ||

417 continue;

418 if (!MO.readsReg())

419 continue;

420

422 N->addRegisterKilled(SReg, &TRI, false);

424 }

425 }

426

427

428 NextInstructionReadsVReg = false;

431 if (!MO.isReg())

432 continue;

434

435 if (!Reg.isVirtual() ||

437 continue;

438

439

440

441 assert(!MO.isInternalRead() && "Cannot assign inside bundles");

442 assert((!MO.isUndef() || MO.isDef()) && "Cannot handle undef uses");

443 if (MO.readsReg()) {

444 NextInstructionReadsVReg = true;

445 }

446 if (MO.isDef()) {

448 I->addRegisterDead(SReg, &TRI, false);

449 }

450 }

451 }

452#ifndef NDEBUG

454 if (!MO.isReg() || !MO.getReg().isVirtual())

455 continue;

456 assert(!MO.isInternalRead() && "Cannot assign inside bundles");

457 assert((!MO.isUndef() || MO.isDef()) && "Cannot handle undef uses");

458 assert(!MO.readsReg() && "Vreg use in first instruction not allowed");

459 }

460#endif

461

462 return MRI.getNumVirtRegs() != InitialNumVirtRegs;

463}

464

466

467

468

470

471 if (MRI.getNumVirtRegs() == 0) {

473 return;

474 }

475

476

479 continue;

480

482 if (Again) {

483 LLVM_DEBUG(dbgs() << "Warning: Required two scavenging passes for block "

486

487

488 if (Again)

490 }

491 }

492

493 MRI.clearVirtRegs();

495}

496

497namespace {

498

499

500

502public:

503 static char ID;

504

506

507 bool runOnMachineFunction(MachineFunction &MF) override {

510

512

513

514

518

519

521 return true;

522 }

523};

524

525}

526

527char ScavengerTest::ID;

528

530 "Scavenge virtual registers inside basic blocks", false, false)

unsigned const MachineRegisterInfo * MRI

MachineInstrBuilder & UseMI

MachineInstrBuilder MachineInstrBuilder & DefMI

This file implements the BitVector class.

BlockVerifier::State From

static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")

static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")

static cl::opt< unsigned > InstrLimit("dfa-instr-limit", cl::Hidden, cl::init(0), cl::desc("If present, stops packetizing after N instructions"))

unsigned const TargetRegisterInfo * TRI

uint64_t IntrinsicInst * II

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

static Register scavengeVReg(MachineRegisterInfo &MRI, RegScavenger &RS, Register VReg, bool ReserveAfter)

Allocate a register for the virtual register VReg.

static unsigned getFrameIndexOperandNum(MachineInstr &MI)

static bool scavengeFrameVirtualRegsInBlock(MachineRegisterInfo &MRI, RegScavenger &RS, MachineBasicBlock &MBB)

Allocate (scavenge) vregs inside a single basic block.

static std::pair< MCPhysReg, MachineBasicBlock::iterator > findSurvivorBackwards(const MachineRegisterInfo &MRI, MachineBasicBlock::iterator From, MachineBasicBlock::iterator To, const LiveRegUnits &LiveOut, ArrayRef< MCPhysReg > AllocationOrder, bool RestoreAfter)

Given the bitvector Available of free register units at position From.

This file declares the machine register scavenger class.

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)

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

A set of register units used to track register liveness.

void addRegMasked(MCPhysReg Reg, LaneBitmask Mask)

Adds register units covered by physical register Reg that are part of the lanemask Mask.

bool available(MCPhysReg Reg) const

Returns true if no part of physical register Reg is live.

void init(const TargetRegisterInfo &TRI)

Initialize and clear the set.

void stepBackward(const MachineInstr &MI)

Updates liveness when stepping backwards over the instruction MI.

void addLiveOuts(const MachineBasicBlock &MBB)

Adds registers living out of block MBB.

void addLiveIns(const MachineBasicBlock &MBB)

Adds registers living into block MBB.

void removeReg(MCPhysReg Reg)

Removes all register units covered by physical register Reg.

const char * getName(MCRegister RegNo) const

Return the human-readable symbolic target-specific name for the specified physical register.

unsigned getNumRegs() const

Return the number of registers this target has (useful for sizing arrays holding per register informa...

const MachineFunction * getParent() const

Return the MachineFunction containing this basic block.

StringRef getName() const

Return the name of the corresponding LLVM basic block, or an empty string.

The MachineFrameInfo class represents an abstract stack frame until prolog/epilog code is inserted.

Align getObjectAlign(int ObjectIdx) const

Return the alignment of the specified stack object.

int64_t getObjectSize(int ObjectIdx) const

Return the size of the specified object.

int getObjectIndexEnd() const

Return one past the maximum frame object index.

int getObjectIndexBegin() const

Return the minimum frame object index.

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

MachineFunctionProperties & set(Property P)

const TargetSubtargetInfo & getSubtarget() const

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

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.

iterator_range< mop_iterator > operands()

MachineOperand class - Representation of each machine instruction operand.

MachineInstr * getParent()

getParent - Return the instruction that this operand belongs to.

reg_begin/reg_end - Provide iteration support to walk over all definitions and uses of a register wit...

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

void enterBasicBlockEnd(MachineBasicBlock &MBB)

Start tracking liveness from the end of basic block MBB.

bool isRegUsed(Register Reg, bool includeReserved=true) const

Return if a specific register is currently used.

Find an unused register of the specified register class.

void setRegUsed(Register Reg, LaneBitmask LaneMask=LaneBitmask::getAll())

Tell the scavenger a register is used.

void backward()

Update internal register state and move MBB iterator backwards.

void enterBasicBlock(MachineBasicBlock &MBB)

Start tracking liveness from the begin of basic block MBB.

Register scavengeRegisterBackwards(const TargetRegisterClass &RC, MachineBasicBlock::iterator To, bool RestoreAfter, int SPAdj, bool AllowSpill=true)

Make a register of the specific register class available from the current position backwards to the p...

BitVector getRegsAvailable(const TargetRegisterClass *RC)

Return all available registers in the register class in Mask.

Wrapper class representing virtual and physical registers.

static unsigned virtReg2Index(Register Reg)

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

void push_back(const T &Elt)

Information about stack frame layout on the target.

virtual void determineCalleeSaves(MachineFunction &MF, BitVector &SavedRegs, RegScavenger *RS=nullptr) const

This method determines which of the registers reported by TargetRegisterInfo::getCalleeSavedRegs() sh...

virtual void processFunctionBeforeFrameFinalized(MachineFunction &MF, RegScavenger *RS=nullptr) const

processFunctionBeforeFrameFinalized - This method is called immediately before the specified function...

virtual void storeRegToStackSlot(MachineBasicBlock &MBB, MachineBasicBlock::iterator MI, Register SrcReg, bool isKill, int FrameIndex, const TargetRegisterClass *RC, const TargetRegisterInfo *TRI, Register VReg, MachineInstr::MIFlag Flags=MachineInstr::NoFlags) const

Store the specified register of the given register class to the specified stack frame index.

virtual void loadRegFromStackSlot(MachineBasicBlock &MBB, MachineBasicBlock::iterator MI, Register DestReg, int FrameIndex, const TargetRegisterClass *RC, const TargetRegisterInfo *TRI, Register VReg, MachineInstr::MIFlag Flags=MachineInstr::NoFlags) const

Load the specified register of the given register class from the specified stack frame index.

ArrayRef< MCPhysReg > getRawAllocationOrder(const MachineFunction &MF) const

Returns the preferred order for allocating registers from this register class in MF.

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.

virtual bool eliminateFrameIndex(MachineBasicBlock::iterator MI, int SPAdj, unsigned FIOperandNum, RegScavenger *RS=nullptr) const =0

This method must be overriden to eliminate abstract frame indices from instructions which may use the...

virtual bool saveScavengerRegister(MachineBasicBlock &MBB, MachineBasicBlock::iterator I, MachineBasicBlock::iterator &UseMI, const TargetRegisterClass *RC, Register Reg) const

Spill the register so it can be used by the register scavenger.

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.

TargetSubtargetInfo - Generic base class for all target subtargets.

virtual const TargetRegisterInfo * getRegisterInfo() const

getRegisterInfo - If register information is available, return it.

virtual const TargetFrameLowering * getFrameLowering() const

virtual const TargetInstrInfo * getInstrInfo() const

Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...

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.

void scavengeFrameVirtualRegs(MachineFunction &MF, RegScavenger &RS)

Replaces all frame index virtual registers with physical registers.

raw_ostream & dbgs()

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

void report_fatal_error(Error Err, bool gen_crash_diag=true)

Report a serious error, calling any installed error handler.

auto find_if(R &&Range, UnaryPredicate P)

Provide wrappers to std::find_if which take ranges instead of having to pass begin/end explicitly.

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.

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

uint64_t value() const

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