SIOptimizeVGPRLiveRange.cpp Source File (original) (raw)

84using namespace llvm;

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

88namespace {

90class SIOptimizeVGPRLiveRange {

91private:

99public:

104

106

110

111 void

116

117 void collectWaterfallCandidateRegisters(

122

125

128

129 void updateLiveRangeInElseRegion(

133

134 void

138

139 void optimizeWaterfallLiveRange(

143};

144

146public:

147 static char ID;

148

150

152

154 return "SI Optimize VGPR LiveRange";

155 }

156

166 }

167

170 MachineFunctionProperties::Property::IsSSA);

171 }

172

175 MachineFunctionProperties::Property::NoPHIs);

176 }

177};

178

179}

180

181

182

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

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

188 }

189 return nullptr;

190}

191

192void SIOptimizeVGPRLiveRange::collectElseRegionBlocks(

196

198 unsigned Cur = 0;

199 while (MBB) {

201 if (Pred != Flow)

203 }

204

205 if (Cur < Blocks.size())

207 else

208 MBB = nullptr;

209 }

210

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

215 dbgs() << '\n';

216 });

217}

218

219

220void SIOptimizeVGPRLiveRange::findNonPHIUsesInBlock(

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

226 }

227}

228

229

230

231void SIOptimizeVGPRLiveRange::collectCandidateRegisters(

235

237

238 for (auto *Else : ElseBlocks) {

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

240 if (MI.isDebugInstr())

241 continue;

242

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

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

245 continue;

246

247 Register MOReg = MO.getReg();

248

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

250 continue;

251

252 if (MO.readsReg()) {

255

256

257

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

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

260

261

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

264 KillsInElse.insert(MOReg);

265 } else {

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

268 }

269 }

270 }

271 }

272 }

273 }

274

275

276

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

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

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

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

281 if (Pred == Flow)

282 continue;

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

284

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

286 continue;

287

289 if (Reg.isPhysical() || TRI ->isVectorRegister(*MRI, Reg))

290 continue;

291

293

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

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

297 continue;

298 }

299

300

301

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

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

305 KillsInElse.insert(Reg);

306 }

307 }

308

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

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

311 ++I) {

312 if (->readsReg())

313 continue;

314 auto *UseMI = I->getParent();

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

318 return true;

319

320 auto *IncomingMBB = UseMI->getOperand(I.getOperandNo() + 1).getMBB();

321

322

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

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

325 return true;

326 }

327 }

328 return false;

329 };

330

331 for (auto Reg : KillsInElse) {

332 if (!IsLiveThroughThen(Reg))

334 }

335}

336

337

338

339void SIOptimizeVGPRLiveRange::collectWaterfallCandidateRegisters(

344

345

346 auto *MBB = LoopHeader;

347 for (;;) {

349 for (auto &MI : *MBB) {

350 if (MI.isDebugInstr())

351 continue;

353 }

354 if (MBB == LoopEnd)

355 break;

356

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

360 return;

361 }

362

364 }

365

366 for (auto *I : Instructions) {

367 auto &MI = *I;

368

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

370 if (!MO.getReg())

371 continue;

372

373 Register MOReg = MO.getReg();

374

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

376 continue;

377

378 if (MO.readsReg()) {

380

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

382

383

384

386 bool IsUsed = false;

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

388 if ( Blocks .contains(Succ) &&

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

390 IsUsed = true;

391 break;

392 }

393 }

394 if (!IsUsed) {

397 CandidateRegs.insert(MOReg);

398 } else {

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

401 }

402 }

403 }

404 }

405 }

406}

407

408

409void SIOptimizeVGPRLiveRange::updateLiveRangeInThenRegion(

413

414

415

416 while (!WorkList.empty()) {

417 auto *MBB = WorkList.pop_back_val();

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

421 }

422 }

423

426

428 << '\n');

430 }

431

433

434

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

436 ++I) {

437 auto *UseMI = I->getParent();

441 }

442 }

443

446

447 findNonPHIUsesInBlock(Reg, MBB, Uses);

448

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

452 LV->HandleVirtRegUse(Reg, MBB, *(*Uses.begin()));

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

454

459 LV->HandleVirtRegUse(Reg, MBB, MI);

460 }

461 }

462

463

465 LV->MarkVirtRegAliveInBlock(OldVarInfo, MRI->getVRegDef(Reg)->getParent(),

467 }

468

469

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

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

472 MI->addRegisterKilled(Reg, TRI);

473 }

474}

475

476void SIOptimizeVGPRLiveRange::updateLiveRangeInElseRegion(

482

483

484 for (auto *MBB : ElseBlocks) {

489 << '\n');

491 }

492 }

493

494

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

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

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

498 NewVarInfo.Kills.push_back(*I);

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

500 } else {

501 ++I;

502 }

503 }

504}

505

506void SIOptimizeVGPRLiveRange::optimizeLiveRange(

510

511

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

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

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

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

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

519 if (Pred == If)

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

521 else

523 }

524

525

526

528 auto *UseMI = O.getParent();

530

531 if (UseBlock == Endif) {

533 O.setReg(NewReg);

535 continue;

536 else {

537

538

539

540

542 }

543 continue;

544 }

545

546

547 if (ElseBlocks.contains(UseBlock))

548 O.setReg(NewReg);

549 }

550

551

554

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

556 updateLiveRangeInThenRegion(Reg, If, Flow);

557}

558

559void SIOptimizeVGPRLiveRange::optimizeWaterfallLiveRange(

563

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

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

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

568

569

570

572 auto *UseMI = O.getParent();

574

575 if (Blocks.contains(UseBlock))

576 O.setReg(NewReg);

577 }

578

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

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

583 if (Blocks.contains(Pred))

585 else

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

587 }

588

591

592

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

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

596 MI->addRegisterKilled(NewReg, TRI);

597 NewVarInfo.Kills.push_back(MI);

599 break;

600 }

601 }

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

603

605 bool PostKillBlock = false;

607 auto BBNum = Block->getNumber();

608

609

610

611

613

614

615 PostKillBlock |= (Block == KillBlock);

616 if (PostKillBlock) {

618 } else if (Block != LoopHeader) {

620 }

621 }

622}

623

624char SIOptimizeVGPRLiveRangeLegacy::ID = 0;

625

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

633

635

637 return new SIOptimizeVGPRLiveRangeLegacy();

638}

639

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

642 return false;

643

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

646 &getAnalysis().getDomTree();

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

649}

650

658

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

660 if (!Changed)

662

668 return PA;

669}

670

673 TII = ST.getInstrInfo();

674 TRI = &TII->getRegisterInfo();

676

677 bool MadeChange = false;

678

679

680

683

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

686 auto *Endif = getElseTarget(IfTarget);

687 if (!Endif)

688 continue;

689

690

692 continue;

693

696

701

702

703 collectElseRegionBlocks(IfTarget, Endif, ElseBlocks);

704

705

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

707 CandidateRegs);

708 MadeChange |= !CandidateRegs.empty();

709

710 for (auto Reg : CandidateRegs)

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

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

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

714 auto *LoopEnd = &MBB;

715

718

722

723 collectWaterfallCandidateRegisters(LoopHeader, LoopEnd, CandidateRegs,

724 Blocks, Instructions);

725 MadeChange |= !CandidateRegs.empty();

726

727 for (auto Reg : CandidateRegs)

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

729 }

730 }

731 }

732

733 return MadeChange;

734}

unsigned const MachineRegisterInfo * MRI

MachineInstrBuilder & UseMI

Provides AMDGPU specific target descriptions.

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

DenseMap< Block *, BlockRelaxAux > Blocks

AMD GCN specific subclass of TargetSubtarget.

const HexagonInstrInfo * TII

unsigned const TargetRegisterInfo * TRI

#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

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

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.

AnalysisUsage & addRequired()

AnalysisUsage & addPreserved()

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

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.

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

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

void push_back(MachineInstr *MI)

succ_iterator succ_begin()

unsigned succ_size() const

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

virtual MachineFunctionProperties getClearedProperties() const

void getAnalysisUsage(AnalysisUsage &AU) const override

getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.

virtual bool runOnMachineFunction(MachineFunction &MF)=0

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

virtual MachineFunctionProperties getRequiredProperties() const

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

MachineFunctionProperties & set(Property P)

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.

Representation of each machine instruction.

const MachineBasicBlock * getParent() const

bool isDebugInstr() const

const MachineOperand & getOperand(unsigned i) const

Analysis pass that exposes the MachineLoopInfo for a machine function.

Result run(MachineFunction &MF, MachineFunctionAnalysisManager &MFAM)

MachineBasicBlock * getMBB() const

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

virtual StringRef getPassName() const

getPassName - Return a nice clean name for a pass.

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.

constexpr bool isPhysical() const

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

PreservedAnalyses run(MachineFunction &MF, MachineFunctionAnalysisManager &MFAM)

A vector that has set insertion semantics.

bool empty() const

Determine if the SetVector is empty or not.

bool insert(const value_type &X)

Insert a new element into the SetVector.

bool contains(const key_type &key) const

Check if the SetVector contains the given key.

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

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

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

SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...

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.

@ BR

Control flow instructions. These all have token chains.

@ Kill

The last use of a register.

@ Undef

Value of the register doesn't matter.

Reg

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

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

PreservedAnalyses getMachineFunctionPassPreservedAnalyses()

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

char & SIOptimizeVGPRLiveRangeLegacyID

auto reverse(ContainerTy &&C)

raw_ostream & dbgs()

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

FunctionPass * createSIOptimizeVGPRLiveRangeLegacyPass()

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

Returns true if Element is found in Range.

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.

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

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.

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

isLiveIn - Is Reg live in to MBB? This means that Reg is live through MBB, or it is killed in MBB.