SIOptimizeVGPRLiveRange.cpp Source File (original) (raw)

85using namespace llvm;

87#define DEBUG_TYPE "si-opt-vgpr-liverange"

89namespace {

91class SIOptimizeVGPRLiveRange {

92private:

100public:

105

107

111

112 void

117

118 void collectWaterfallCandidateRegisters(

123

126

129

130 void updateLiveRangeInElseRegion(

134

135 void

139

140 void optimizeWaterfallLiveRange(

144};

145

147public:

148 static char ID;

149

151

153

154 StringRef getPassName() const override {

155 return "SI Optimize VGPR LiveRange";

156 }

157

158 void getAnalysisUsage(AnalysisUsage &AU) const override {

167 }

168

171 }

172

175 }

176};

177

178}

179

180

181

185 if (BR.getOpcode() == AMDGPU::SI_ELSE)

186 return BR.getOperand(2).getMBB();

187 }

188 return nullptr;

189}

190

191void SIOptimizeVGPRLiveRange::collectElseRegionBlocks(

192 MachineBasicBlock *Flow, MachineBasicBlock *Endif,

193 SmallSetVector<MachineBasicBlock *, 16> &Blocks) const {

195

196 MachineBasicBlock *MBB = Endif;

197 unsigned Cur = 0;

198 while (MBB) {

200 if (Pred != Flow)

202 }

203

204 if (Cur < Blocks.size())

205 MBB = Blocks[Cur++];

206 else

207 MBB = nullptr;

208 }

209

211 dbgs() << "Found Else blocks: ";

212 for (auto *MBB : Blocks)

214 dbgs() << '\n';

215 });

216}

217

218

219void SIOptimizeVGPRLiveRange::findNonPHIUsesInBlock(

221 SmallVectorImpl<MachineInstr *> &Uses) const {

222 for (auto &UseMI : MRI->use_nodbg_instructions(Reg)) {

225 }

226}

227

228

229

230void SIOptimizeVGPRLiveRange::collectCandidateRegisters(

231 MachineBasicBlock *If, MachineBasicBlock *Flow, MachineBasicBlock *Endif,

232 SmallSetVector<MachineBasicBlock *, 16> &ElseBlocks,

233 SmallVectorImpl &CandidateRegs) const {

234

235 SmallSet<Register, 8> KillsInElse;

236

237 for (auto *Else : ElseBlocks) {

238 for (auto &MI : Else->instrs()) {

239 if (MI.isDebugInstr())

240 continue;

241

242 for (auto &MO : MI.operands()) {

243 if (!MO.isReg() || !MO.getReg() || MO.isDef())

244 continue;

245

246 Register MOReg = MO.getReg();

247

248 if (MOReg.isPhysical() || TRI ->isVectorRegister(*MRI, MOReg))

249 continue;

250

251 if (MO.readsReg()) {

252 LiveVariables::VarInfo &VI = LV->getVarInfo(MOReg);

253 const MachineBasicBlock *DefMBB = MRI->getVRegDef(MOReg)->getParent();

254

255

256

257 if ((VI.AliveBlocks.test(If->getNumber()) || DefMBB == If) &&

258 Loops->getLoopFor(DefMBB) == Loops->getLoopFor(If)) {

259

260

261 LiveVariables::VarInfo &VI = LV->getVarInfo(MOReg);

262 if (.isLiveIn(*Endif, MOReg, *MRI)) {

263 KillsInElse.insert(MOReg);

264 } else {

266 << " as Live in Endif\n");

267 }

268 }

269 }

270 }

271 }

272 }

273

274

275

276 for (auto &MI : Endif->phis()) {

277 for (unsigned Idx = 1; Idx < MI.getNumOperands(); Idx += 2) {

278 auto &MO = MI.getOperand(Idx);

279 auto *Pred = MI.getOperand(Idx + 1).getMBB();

280 if (Pred == Flow)

281 continue;

282 assert(ElseBlocks.contains(Pred) && "Should be from Else region\n");

283

284 if (!MO.isReg() || !MO.getReg() || MO.isUndef())

285 continue;

286

289 continue;

290

292

293 if (VI.isLiveIn(*Endif, Reg, *MRI)) {

295 << " as Live in Endif\n");

296 continue;

297 }

298

299

300

301 const MachineBasicBlock *DefMBB = MRI->getVRegDef(Reg)->getParent();

302 if ((VI.AliveBlocks.test(If->getNumber()) || DefMBB == If) &&

303 Loops->getLoopFor(DefMBB) == Loops->getLoopFor(If))

305 }

306 }

307

308 auto IsLiveThroughThen = [&](Register Reg) {

309 for (auto I = MRI->use_nodbg_begin(Reg), E = MRI->use_nodbg_end(); I != E;

310 ++I) {

311 if (->readsReg())

312 continue;

315 if (UseMBB == Flow || UseMBB == Endif) {

317 return true;

318

320

321

322 if ((UseMBB == Flow && IncomingMBB != If) ||

323 (UseMBB == Endif && IncomingMBB == Flow))

324 return true;

325 }

326 }

327 return false;

328 };

329

330 for (auto Reg : KillsInElse) {

331 if (!IsLiveThroughThen(Reg))

333 }

334}

335

336

337

338void SIOptimizeVGPRLiveRange::collectWaterfallCandidateRegisters(

339 MachineBasicBlock *LoopHeader, MachineBasicBlock *LoopEnd,

340 SmallSetVector<Register, 16> &CandidateRegs,

341 SmallSetVector<MachineBasicBlock *, 2> &Blocks,

342 SmallVectorImpl<MachineInstr *> &Instructions) const {

343

344

345 auto *MBB = LoopHeader;

346 for (;;) {

348 for (auto &MI : *MBB) {

349 if (MI.isDebugInstr())

350 continue;

352 }

353 if (MBB == LoopEnd)

354 break;

355

358 LLVM_DEBUG(dbgs() << "Unexpected edges in CFG, ignoring loop\n");

359 return;

360 }

361

363 }

364

365 for (auto *I : Instructions) {

366 auto &MI = *I;

367

368 for (auto &MO : MI.all_uses()) {

369 if (!MO.getReg())

370 continue;

371

372 Register MOReg = MO.getReg();

373

374 if (MOReg.isPhysical() || TRI ->isVectorRegister(*MRI, MOReg))

375 continue;

376

377 if (MO.readsReg()) {

378 MachineBasicBlock *DefMBB = MRI->getVRegDef(MOReg)->getParent();

379

380 if (!Blocks.contains(DefMBB) && !CandidateRegs.contains(MOReg)) {

381

382

383

384 LiveVariables::VarInfo &OldVarInfo = LV->getVarInfo(MOReg);

385 bool IsUsed = false;

386 for (auto *Succ : LoopEnd->successors()) {

387 if (!Blocks.contains(Succ) &&

388 OldVarInfo.isLiveIn(*Succ, MOReg, *MRI)) {

389 IsUsed = true;

390 break;

391 }

392 }

393 if (!IsUsed) {

396 CandidateRegs.insert(MOReg);

397 } else {

398 LLVM_DEBUG(dbgs() << "Reg is used after loop, ignoring: "

400 }

401 }

402 }

403 }

404 }

405}

406

407

408void SIOptimizeVGPRLiveRange::updateLiveRangeInThenRegion(

409 Register Reg, MachineBasicBlock *If, MachineBasicBlock *Flow) const {

410 SetVector<MachineBasicBlock *> Blocks;

412

413

414

415 while (!WorkList.empty()) {

416 auto *MBB = WorkList.pop_back_val();

418 if (Succ != Flow && Blocks.insert(Succ))

419 WorkList.push_back(Succ);

420 }

421 }

422

423 LiveVariables::VarInfo &OldVarInfo = LV->getVarInfo(Reg);

424 for (MachineBasicBlock *MBB : Blocks) {

425

427 << '\n');

429 }

430

431 SmallPtrSet<MachineBasicBlock *, 4> PHIIncoming;

432

433

434 for (auto I = MRI->use_nodbg_begin(Reg), E = MRI->use_nodbg_end(); I != E;

435 ++I) {

440 }

441 }

442

443 for (MachineBasicBlock *MBB : Blocks) {

445

446 findNonPHIUsesInBlock(Reg, MBB, Uses);

447

448 if (Uses.size() == 1) {

452 } else if (Uses.size() > 1) {

453

456 for (MachineInstr &MI : *MBB) {

459 }

460 }

461

462

466 }

467

468

469 for (auto *MI : OldVarInfo.Kills) {

470 if (Blocks.contains(MI->getParent()))

471 MI->addRegisterKilled(Reg, TRI);

472 }

473}

474

475void SIOptimizeVGPRLiveRange::updateLiveRangeInElseRegion(

477 MachineBasicBlock *Endif,

478 SmallSetVector<MachineBasicBlock *, 16> &ElseBlocks) const {

479 LiveVariables::VarInfo &NewVarInfo = LV->getVarInfo(NewReg);

480 LiveVariables::VarInfo &OldVarInfo = LV->getVarInfo(Reg);

481

482

483 for (auto *MBB : ElseBlocks) {

488 << '\n');

490 }

491 }

492

493

494 auto I = OldVarInfo.Kills.begin();

495 while (I != OldVarInfo.Kills.end()) {

496 if (ElseBlocks.contains((*I)->getParent())) {

497 NewVarInfo.Kills.push_back(*I);

498 I = OldVarInfo.Kills.erase(I);

499 } else {

500 ++I;

501 }

502 }

503}

504

505void SIOptimizeVGPRLiveRange::optimizeLiveRange(

506 Register Reg, MachineBasicBlock *If, MachineBasicBlock *Flow,

507 MachineBasicBlock *Endif,

508 SmallSetVector<MachineBasicBlock *, 16> &ElseBlocks) const {

509

510

512 const auto *RC = MRI->getRegClass(Reg);

513 Register NewReg = MRI->createVirtualRegister(RC);

514 Register UndefReg = MRI->createVirtualRegister(RC);

516 TII->get(TargetOpcode::PHI), NewReg);

517 for (auto *Pred : Flow->predecessors()) {

518 if (Pred == If)

519 PHI.addReg(Reg).addMBB(Pred);

520 else

522 }

523

524

525

527 auto *UseMI = O.getParent();

529

530 if (UseBlock == Endif) {

532 O.setReg(NewReg);

534 continue;

535 else {

536

537

538

539

541 }

542 continue;

543 }

544

545

546 if (ElseBlocks.contains(UseBlock))

547 O.setReg(NewReg);

548 }

549

550

551 LiveVariables::VarInfo &OldVarInfo = LV->getVarInfo(Reg);

553

554 updateLiveRangeInElseRegion(Reg, NewReg, Flow, Endif, ElseBlocks);

555 updateLiveRangeInThenRegion(Reg, If, Flow);

556}

557

558void SIOptimizeVGPRLiveRange::optimizeWaterfallLiveRange(

559 Register Reg, MachineBasicBlock *LoopHeader,

560 SmallSetVector<MachineBasicBlock *, 2> &Blocks,

561 SmallVectorImpl<MachineInstr *> &Instructions) const {

562

564 const auto *RC = MRI->getRegClass(Reg);

565 Register NewReg = MRI->createVirtualRegister(RC);

566 Register UndefReg = MRI->createVirtualRegister(RC);

567

568

569

571 auto *UseMI = O.getParent();

573

574 if (Blocks.contains(UseBlock))

575 O.setReg(NewReg);

576 }

577

578 MachineInstrBuilder PHI =

580 TII->get(TargetOpcode::PHI), NewReg);

581 for (auto *Pred : LoopHeader->predecessors()) {

584 else

585 PHI.addReg(Reg).addMBB(Pred);

586 }

587

588 LiveVariables::VarInfo &NewVarInfo = LV->getVarInfo(NewReg);

589 LiveVariables::VarInfo &OldVarInfo = LV->getVarInfo(Reg);

590

591

592 MachineInstr *Kill = nullptr;

593 for (auto *MI : reverse(Instructions)) {

594 if (MI->readsRegister(NewReg, TRI)) {

595 MI->addRegisterKilled(NewReg, TRI);

596 NewVarInfo.Kills.push_back(MI);

598 break;

599 }

600 }

601 assert(Kill && "Failed to find last usage of register in loop");

602

603 MachineBasicBlock *KillBlock = Kill->getParent();

604 bool PostKillBlock = false;

605 for (auto *Block : Blocks) {

606 auto BBNum = Block->getNumber();

607

608

609

610

612

613

614 PostKillBlock |= (Block == KillBlock);

615 if (PostKillBlock) {

617 } else if (Block != LoopHeader) {

619 }

620 }

621}

622

623char SIOptimizeVGPRLiveRangeLegacy::ID = 0;

624

626 "SI Optimize VGPR LiveRange", false, false)

632

634

636 return new SIOptimizeVGPRLiveRangeLegacy();

637}

638

639bool SIOptimizeVGPRLiveRangeLegacy::runOnMachineFunction(MachineFunction &MF) {

641 return false;

642

643 LiveVariables *LV = &getAnalysis().getLV();

645 &getAnalysis().getDomTree();

647 return SIOptimizeVGPRLiveRange(LV, MDT, Loops).run(MF);

648}

649

650PreservedAnalyses

657

658 bool Changed = SIOptimizeVGPRLiveRange(LV, MDT, Loops).run(MF);

661

667 return PA;

668}

669

672 TII = ST.getInstrInfo();

673 TRI = &TII->getRegisterInfo();

675

676 bool MadeChange = false;

677

678

679

681 for (auto &MI : MBB.terminators()) {

682

683 if (MI.getOpcode() == AMDGPU::SI_IF) {

685 auto *Endif = getElseTarget(IfTarget);

686 if (!Endif)

687 continue;

688

689

691 continue;

692

695

700

701

702 collectElseRegionBlocks(IfTarget, Endif, ElseBlocks);

703

704

705 collectCandidateRegisters(&MBB, IfTarget, Endif, ElseBlocks,

706 CandidateRegs);

707 MadeChange |= !CandidateRegs.empty();

708

709 for (auto Reg : CandidateRegs)

710 optimizeLiveRange(Reg, &MBB, IfTarget, Endif, ElseBlocks);

711 } else if (MI.getOpcode() == AMDGPU::SI_WATERFALL_LOOP) {

712 auto *LoopHeader = MI.getOperand(0).getMBB();

713 auto *LoopEnd = &MBB;

714

717

721

722 collectWaterfallCandidateRegisters(LoopHeader, LoopEnd, CandidateRegs,

723 Blocks, Instructions);

724 MadeChange |= !CandidateRegs.empty();

725

726 for (auto Reg : CandidateRegs)

727 optimizeWaterfallLiveRange(Reg, LoopHeader, Blocks, Instructions);

728 }

729 }

730 }

731

732 return MadeChange;

733}

unsigned const MachineRegisterInfo * MRI

MachineInstrBuilder & UseMI

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

const TargetInstrInfo & TII

Provides AMDGPU specific target descriptions.

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

AMD GCN specific subclass of TargetSubtarget.

Promote Memory to Register

#define INITIALIZE_PASS_DEPENDENCY(depName)

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

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

Remove Loads Into Fake Uses

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.

AnalysisUsage & addRequired()

AnalysisUsage & addPreserved()

Add the specified Pass class to the set of analyses preserved by this pass.

LLVM_ABI void setPreservesCFG()

This function should be called by the pass, iff they do not:

Represents analyses that only rely on functions' control flow.

Analysis pass which computes a DominatorTree.

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

LLVM_ABI void MarkVirtRegAliveInBlock(VarInfo &VRInfo, MachineBasicBlock *DefBlock, MachineBasicBlock *BB)

LLVM_ABI void HandleVirtRegUse(Register reg, MachineBasicBlock *MBB, MachineInstr &MI)

LLVM_ABI VarInfo & getVarInfo(Register Reg)

getVarInfo - Return the VarInfo structure for the specified VIRTUAL register.

const MCInstrDesc & get(unsigned Opcode) const

Return the machine instruction descriptor that corresponds to the specified instruction opcode.

An RAII based helper class to modify MachineFunctionProperties when running pass.

unsigned pred_size() const

int getNumber() const

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

succ_iterator succ_begin()

unsigned succ_size() const

LLVM_ABI iterator getFirstNonPHI()

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

iterator_range< iterator > terminators()

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

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.

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

const TargetSubtargetInfo & getSubtarget() const

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

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

bool isDebugInstr() const

const MachineOperand & getOperand(unsigned i) const

Analysis pass that exposes the MachineLoopInfo for a machine function.

MachineBasicBlock * getMBB() const

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

static PreservedAnalyses all()

Construct a special preserved set that preserves all passes.

Wrapper class representing virtual and physical registers.

constexpr bool isPhysical() const

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

PreservedAnalyses run(MachineFunction &MF, MachineFunctionAnalysisManager &MFAM)

Definition SIOptimizeVGPRLiveRange.cpp:651

size_type size() const

Determine the number of elements in the SetVector.

bool contains(const_arg_type key) const

Check if the SetVector contains the given key.

bool empty() const

Determine if the SetVector is empty or not.

bool insert(const value_type &X)

Insert a new element into the SetVector.

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

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

bool contains(ConstPtrType Ptr) const

A SetVector that performs no allocations if smaller than a certain size.

std::pair< const_iterator, bool > insert(const T &V)

insert - Insert an element into the set if it isn't already there.

This class consists of common code factored out of the SmallVector class to reduce code duplication b...

void push_back(const T &Elt)

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

bool test(unsigned Idx) const

StringRef - Represent a constant reference to a string, i.e.

unsigned ID

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

@ Kill

The last use of a register.

@ Undef

Value of the register doesn't matter.

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.

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

AnalysisManager< MachineFunction > MachineFunctionAnalysisManager

LLVM_ABI PreservedAnalyses getMachineFunctionPassPreservedAnalyses()

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

char & SIOptimizeVGPRLiveRangeLegacyID

Definition SIOptimizeVGPRLiveRange.cpp:633

auto reverse(ContainerTy &&C)

LLVM_ABI raw_ostream & dbgs()

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

class LLVM_GSL_OWNER SmallVector

Forward declaration of SmallVector so that calculateSmallVectorDefaultInlinedElements can reference s...

FunctionPass * createSIOptimizeVGPRLiveRangeLegacyPass()

Definition SIOptimizeVGPRLiveRange.cpp:635

bool is_contained(R &&Range, const E &Element)

Returns true if Element is found in Range.

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.

LLVM_ABI Printable printMBBReference(const MachineBasicBlock &MBB)

Prints a machine basic block reference.

std::vector< MachineInstr * > Kills

Kills - List of MachineInstruction's which are the last use of this virtual register (kill it) in the...

SparseBitVector AliveBlocks

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

LLVM_ABI bool isLiveIn(const MachineBasicBlock &MBB, Register Reg, MachineRegisterInfo &MRI)

isLiveIn - Is Reg live in to MBB?