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");

51 LiveUnits.addRegMasked(Reg, LaneMask);

52}

61 this->MBB = &MBB;

63 for (ScavengedInfo &SI : Scavenged) {

64 SI.Reg = 0;

65 SI.Restore = nullptr;

66 }

67}

70 init(MBB);

71 LiveUnits.addLiveIns(MBB);

72 MBBI = MBB.begin();

73}

76 init(MBB);

77 LiveUnits.addLiveOuts(MBB);

78 MBBI = MBB.end();

79}

83 LiveUnits.stepBackward(MI);

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;

97 return !LiveUnits.available(Reg);

98}

104 << "\n");

105 return Reg;

106 }

107 }

108 return 0;

109}

110

112 BitVector Mask(TRI->getNumRegs());

115 Mask.set(Reg.id());

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 }

202 if (I == MBB.begin())

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

227 const MachineFunction &MF = *Before->getMF();

228 const MachineFrameInfo &MFI = MF.getFrameInfo();

229 unsigned NeedSize = TRI->getSpillSize(RC);

230 Align NeedAlign = TRI->getSpillAlign(RC);

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

269 if (!TRI->saveScavengerRegister(*MBB, Before, UseMI, &RC, Reg)) {

270

271 int FI = Scavenged[SI].FrameIndex;

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

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

275 TRI->getRegClassName(&RC) +

276 ": Cannot scavenge register without an emergency "

277 "spill slot!");

278 }

279 TII->storeRegToStackSlot(*MBB, Before, Reg, true, FI, &RC, Register());

281

283 TRI->eliminateFrameIndex(II, SPAdj, FIOperandNum, this);

284

285

286 TII->loadRegFromStackSlot(*MBB, UseMI, Reg, FI, &RC, Register());

288

290 TRI->eliminateFrameIndex(II, SPAdj, FIOperandNum, this);

291 }

292 return Scavenged[SI];

293}

294

297 bool RestoreAfter, int SPAdj,

298 bool AllowSpill) {

301

302

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

308

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

311 << '\n');

312 return Reg;

313 }

314

315 if (!AllowSpill)

316 return 0;

317

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

319

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

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

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

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

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

326 LiveUnits.removeReg(Reg);

328 << " until " << *SpillBefore);

329 return Reg;

330}

331

332

333

334

335

336

338 Register VReg, bool ReserveAfter) {

340#ifndef NDEBUG

341

343

347 if (CommonMBB == nullptr)

348 CommonMBB = MBB;

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

350 if (MO.isDef()) {

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

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

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

355 RealDef = &MI;

356 }

357 }

358 }

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

360#endif

361

362

363

364

365

366

367

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

371 });

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

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

375

376

377

378 int SPAdj = 0;

380 Register SReg = RS.scavengeRegisterBackwards(RC, DefMI.getIterator(),

381 ReserveAfter, SPAdj);

382 MRI.replaceRegWith(VReg, SReg);

383 ++NumScavengedRegs;

384 return SReg;

385}

386

387

388

389

394 RS.enterBasicBlockEnd(MBB);

395

396 unsigned InitialNumVirtRegs = MRI.getNumVirtRegs();

397 bool NextInstructionReadsVReg = false;

399

400 RS.backward(I);

401 --I;

402

403

404 if (NextInstructionReadsVReg) {

408 if (!MO.isReg())

409 continue;

411

412

413

414 if ( Reg .isVirtual() || Reg.virtRegIndex() >= InitialNumVirtRegs)

415 continue;

416 if (!MO.readsReg())

417 continue;

418

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

421 RS.setRegUsed(SReg);

422 }

423 }

424

425

426 NextInstructionReadsVReg = false;

429 if (!MO.isReg())

430 continue;

432

433 if ( Reg .isVirtual() || Reg.virtRegIndex() >= InitialNumVirtRegs)

434 continue;

435

436

437

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

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

440 if (MO.readsReg()) {

441 NextInstructionReadsVReg = true;

442 }

443 if (MO.isDef()) {

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

446 }

447 }

448 }

449#ifndef NDEBUG

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

452 continue;

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

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

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

456 }

457#endif

458

459 return MRI.getNumVirtRegs() != InitialNumVirtRegs;

460}

461

463

464

465

467

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

470 return;

471 }

472

473

475 if (MBB.empty())

476 continue;

477

479 if (Again) {

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

481 << MBB.getName() << '\n');

483

484

485 if (Again)

487 }

488 }

489

490 MRI.clearVirtRegs();

492}

493

494namespace {

495

496

497

499public:

500 static char ID;

501

503

504 bool runOnMachineFunction(MachineFunction &MF) override {

505 const TargetSubtargetInfo &STI = MF.getSubtarget();

507

508 RegScavenger RS;

509

510

511

512 BitVector SavedRegs;

515

516

518 return true;

519 }

520};

521

522}

523

524char ScavengerTest::ID;

525

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

unsigned const MachineRegisterInfo * MRI

MachineInstrBuilder & UseMI

MachineInstrBuilder MachineInstrBuilder & DefMI

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

const TargetInstrInfo & TII

This file implements the BitVector class.

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"))

Promote Memory to Register

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.

Definition RegisterScavenging.cpp:337

static unsigned getFrameIndexOperandNum(MachineInstr &MI)

Definition RegisterScavenging.cpp:212

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

Allocate (scavenge) vregs inside a single basic block.

Definition RegisterScavenging.cpp:390

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.

Definition RegisterScavenging.cpp:127

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)

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.

bool available(MCRegister Reg) const

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

void init(const TargetRegisterInfo &TRI)

Initialize and clear the set.

MachineInstrBundleIterator< MachineInstr > iterator

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

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.

MachineOperand class - Representation of each machine instruction operand.

MachineInstr * getParent()

getParent - Return the instruction that this operand belongs to.

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

defusechain_iterator< false, true, false, true, false > def_iterator

def_iterator/def_begin/def_end - Walk all defs of the specified register.

void enterBasicBlockEnd(MachineBasicBlock &MBB)

Start tracking liveness from the end of basic block MBB.

Definition RegisterScavenging.cpp:75

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

Return if a specific register is currently used.

Definition RegisterScavenging.cpp:94

Find an unused register of the specified register class.

Definition RegisterScavenging.cpp:100

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

Tell the scavenger a register is used.

Definition RegisterScavenging.cpp:50

void backward()

Update internal register state and move MBB iterator backwards.

Definition RegisterScavenging.cpp:81

void enterBasicBlock(MachineBasicBlock &MBB)

Start tracking liveness from the begin of basic block MBB.

Definition RegisterScavenging.cpp:69

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

Definition RegisterScavenging.cpp:295

BitVector getRegsAvailable(const TargetRegisterClass *RC)

Return all available registers in the register class in Mask.

Definition RegisterScavenging.cpp:111

Wrapper class representing virtual and physical registers.

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

ArrayRef< MCPhysReg > getRawAllocationOrder(const MachineFunction &MF, bool Rev=false) 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...

virtual const TargetFrameLowering * getFrameLowering() const

virtual const TargetInstrInfo * getInstrInfo() const

virtual const TargetRegisterInfo * getRegisterInfo() const =0

Return the target's register information.

constexpr char Align[]

Key for Kernel::Arg::Metadata::mAlign.

unsigned ID

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

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.

Definition RegisterScavenging.cpp:462

LLVM_ABI raw_ostream & dbgs()

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

LLVM_ABI void report_fatal_error(Error Err, bool gen_crash_diag=true)

uint16_t MCPhysReg

An unsigned integer type large enough to represent all physical registers, but not necessarily virtua...

auto find_if(R &&Range, UnaryPredicate P)

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

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

constexpr uint64_t value() const

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