PostRASchedulerList.cpp Source File (original) (raw)

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

44using namespace llvm;

46#define DEBUG_TYPE "post-RA-sched"

48 STATISTIC(NumNoops, "Number of noops inserted");

49 STATISTIC(NumStalls, "Number of pipeline stalls");

50 STATISTIC(NumFixedAnti, "Number of fixed anti-dependencies");

57 cl::desc("Enable scheduling after register allocation"),

61 cl::desc("Break post-RA scheduling anti-dependencies: "

62 "\"critical\", \"all\", or \"none\""),

68 cl::desc("Debug control MBBs that are scheduled"),

72 cl::desc("Debug control MBBs that are scheduled"),

77namespace {

78class PostRAScheduler {

85public:

88 : TII(MF.getSubtarget().getInstrInfo()), MLI(MLI), AA(AA), TM(TM) {}

89 bool run(MachineFunction &MF);

90};

93public:

94 static char ID;

95 PostRASchedulerLegacy() : MachineFunctionPass(ID) {}

97 void getAnalysisUsage(AnalysisUsage &AU) const override {

101 AU.addRequired();

102 AU.addPreserved();

103 AU.addRequired();

104 AU.addPreserved();

106 }

107

108 MachineFunctionProperties getRequiredProperties() const override {

109 return MachineFunctionProperties().setNoVRegs();

110 }

111

112 bool runOnMachineFunction(MachineFunction &Fn) override;

113};

114char PostRASchedulerLegacy::ID = 0;

115

117

118

119 LatencyPriorityQueue AvailableQueue;

120

121

122

123

124

125 std::vector<SUnit *> PendingQueue;

126

127

128 ScheduleHazardRecognizer *HazardRec;

129

130

131 AntiDepBreaker *AntiDepBreak;

132

133

135

136

137 std::vector<SUnit *> Sequence;

138

139

140 std::vector<std::unique_ptr> Mutations;

141

142

143

144

145

146 unsigned EndIndex = 0;

147

148public:

149 SchedulePostRATDList(

150 MachineFunction &MF, MachineLoopInfo &MLI, AliasAnalysis *AA,

151 const RegisterClassInfo &,

153 SmallVectorImpl<const TargetRegisterClass *> &CriticalPathRCs);

154

155 ~SchedulePostRATDList() override;

156

157

158

159

160 void startBlock(MachineBasicBlock *BB) override;

161

162

163 void setEndIndex(unsigned EndIdx) { EndIndex = EndIdx; }

164

165

168 unsigned regioninstrs) override;

169

170

171 void exitRegion() override;

172

173

174

175 void schedule() override;

176

177 void EmitSchedule();

178

179

180

181

182 void Observe(MachineInstr &MI, unsigned Count);

183

184

185

186 void finishBlock() override;

187

188private:

189

190 void postProcessDAG();

191

192 void ReleaseSucc(SUnit *SU, SDep *SuccEdge);

193 void ReleaseSuccessors(SUnit *SU);

194 void ScheduleNodeTopDown(SUnit *SU, unsigned CurCycle);

195 void ListScheduleTopDown();

196

197 void dumpSchedule() const;

198 void emitNoop(unsigned CurCycle);

199};

200}

201

203

205 "Post RA top-down list latency scheduler", false, false)

206

207SchedulePostRATDList::SchedulePostRATDList(

213

215 MF.getSubtarget().getInstrItineraryData();

216 HazardRec =

217 MF.getSubtarget().getInstrInfo()->CreateTargetPostRAHazardRecognizer(

218 InstrItins, this);

219 MF.getSubtarget().getPostRAMutations(Mutations);

220

221 assert((AntiDepMode == TargetSubtargetInfo::ANTIDEP_NONE ||

222 MRI.tracksLiveness()) &&

223 "Live-ins must be accurate for anti-dependency breaking");

224 AntiDepBreak = ((AntiDepMode == TargetSubtargetInfo::ANTIDEP_ALL)

226 : ((AntiDepMode == TargetSubtargetInfo::ANTIDEP_CRITICAL)

228 : nullptr));

229}

230

231SchedulePostRATDList::~SchedulePostRATDList() {

232 delete HazardRec;

233 delete AntiDepBreak;

234}

235

236

237void SchedulePostRATDList::enterRegion(MachineBasicBlock *bb,

240 unsigned regioninstrs) {

242 Sequence.clear();

243}

244

245

246void SchedulePostRATDList::exitRegion() {

248 dbgs() << "*** Final schedule ***\n";

249 dumpSchedule();

250 dbgs() << '\n';

251 });

253}

254

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

256

257LLVM_DUMP_METHOD void SchedulePostRATDList::dumpSchedule() const {

258 for (const SUnit *SU : Sequence) {

259 if (SU)

260 dumpNode(*SU);

261 else

262 dbgs() << "**** NOOP ****\n";

263 }

264}

265#endif

266

269

272

273 return ST.enablePostRAScheduler() &&

274 OptLevel >= ST.getOptLevelToEnablePostRAScheduler();

275}

276

277bool PostRAScheduler::run(MachineFunction &MF) {

279

281 return false;

282

287 ? TargetSubtargetInfo::ANTIDEP_ALL

289 ? TargetSubtargetInfo::ANTIDEP_CRITICAL

290 : TargetSubtargetInfo::ANTIDEP_NONE);

291 }

293 Subtarget.getCriticalPathRCs(CriticalPathRCs);

295

297

298 SchedulePostRATDList Scheduler(MF, *MLI, AA, RegClassInfo, AntiDepMode,

299 CriticalPathRCs);

300

301

302 for (auto &MBB : MF) {

303#ifndef NDEBUG

304

306 static int bbcnt = 0;

308 continue;

309 dbgs() << "*** DEBUG scheduling " << MF.getName() << ":"

311 }

312#endif

313

314

316

317

318

322 MachineInstr &MI = *std::prev(I);

324

325

326

329 Scheduler.setEndIndex(CurrentCount);

333 Current = &MI;

334 CurrentCount = Count;

336 }

338 if (MI.isBundle())

339 Count -= MI.getBundleSize();

340 }

341 assert(Count == 0 && "Instruction count mismatch!");

342 assert((MBB.begin() == Current || CurrentCount != 0) &&

343 "Instruction count mismatch!");

345 Scheduler.setEndIndex(CurrentCount);

349

350

352

353

355 }

356

357 return true;

358}

359

360bool PostRASchedulerLegacy::runOnMachineFunction(MachineFunction &MF) {

362 return false;

363

364 MachineLoopInfo *MLI = &getAnalysis().getLI();

365 AliasAnalysis *AA = &getAnalysis().getAAResults();

366 const TargetMachine *TM =

367 &getAnalysis().getTM();

368 PostRAScheduler Impl(MF, MLI, AA, TM);

369 return Impl.run(MF);

370}

371

372PreservedAnalyses

376

379 .getManager();

381 PostRAScheduler Impl(MF, MLI, AA, TM);

382 bool Changed = Impl.run(MF);

385

390 return PA;

391}

392

393

394

395

397

399

400

401 HazardRec->Reset();

402 if (AntiDepBreak)

404}

405

406

407

408void SchedulePostRATDList::schedule() {

409

410 buildSchedGraph(AA);

411

412 if (AntiDepBreak) {

413 unsigned Broken =

415 EndIndex, DbgValues);

416

417 if (Broken != 0) {

418

419

420

421

422

423

425 buildSchedGraph(AA);

426

427 NumFixedAnti += Broken;

428 }

429 }

430

431 postProcessDAG();

432

433 LLVM_DEBUG(dbgs() << "********** List Scheduling **********\n");

435

436 AvailableQueue.initNodes(SUnits);

437 ListScheduleTopDown();

439}

440

441

442

443

444void SchedulePostRATDList::Observe(MachineInstr &MI, unsigned Count) {

445 if (AntiDepBreak)

447}

448

449

450

451void SchedulePostRATDList::finishBlock() {

452 if (AntiDepBreak)

454

455

457}

458

459

460void SchedulePostRATDList::postProcessDAG() {

461 for (auto &M : Mutations)

462 M->apply(this);

463}

464

465

466

467

468

469

470

471void SchedulePostRATDList::ReleaseSucc(SUnit *SU, SDep *SuccEdge) {

472 SUnit *SuccSU = SuccEdge->getSUnit();

473

474 if (SuccEdge->isWeak()) {

476 return;

477 }

478#ifndef NDEBUG

480 dbgs() << "*** Scheduling failed! ***\n";

481 dumpNode(*SuccSU);

482 dbgs() << " has been released too many times!\n";

484 }

485#endif

487

488

489

490

491

492

493

494

495

496

497

498

499

500

501 if (SuccSU->NumPredsLeft == 0 && SuccSU != &ExitSU)

502 PendingQueue.push_back(SuccSU);

503}

504

505

506void SchedulePostRATDList::ReleaseSuccessors(SUnit *SU) {

508 I != E; ++I) {

509 ReleaseSucc(SU, &*I);

510 }

511}

512

513

514

515

516void SchedulePostRATDList::ScheduleNodeTopDown(SUnit *SU, unsigned CurCycle) {

517 LLVM_DEBUG(dbgs() << "*** Scheduling [" << CurCycle << "]: ");

519

522 "Node scheduled above its depth!");

524

525 ReleaseSuccessors(SU);

528}

529

530

531void SchedulePostRATDList::emitNoop(unsigned CurCycle) {

532 LLVM_DEBUG(dbgs() << "*** Emitting noop in cycle " << CurCycle << '\n');

534 Sequence.push_back(nullptr);

535 ++NumNoops;

536}

537

538

539

540void SchedulePostRATDList::ListScheduleTopDown() {

541 unsigned CurCycle = 0;

542

543

544

545

546

547 HazardRec->Reset();

548

549

550 ReleaseSuccessors(&EntrySU);

551

552

553 for (SUnit &SUnit : SUnits) {

554

555 if (!SUnit.NumPredsLeft && !SUnit.isAvailable) {

556 AvailableQueue.push(&SUnit);

557 SUnit.isAvailable = true;

558 }

559 }

560

561

562

563 bool CycleHasInsts = false;

564

565

566

567 std::vector<SUnit*> NotReady;

568 Sequence.reserve(SUnits.size());

569 while (!AvailableQueue.empty() || !PendingQueue.empty()) {

570

571

572 unsigned MinDepth = ~0u;

573 for (unsigned i = 0, e = PendingQueue.size(); i != e; ++i) {

574 if (PendingQueue[i]->getDepth() <= CurCycle) {

575 AvailableQueue.push(PendingQueue[i]);

576 PendingQueue[i]->isAvailable = true;

577 PendingQueue[i] = PendingQueue.back();

578 PendingQueue.pop_back();

579 --i; --e;

580 } else if (PendingQueue[i]->getDepth() < MinDepth)

581 MinDepth = PendingQueue[i]->getDepth();

582 }

583

585 AvailableQueue.dump(this));

586

587 SUnit *FoundSUnit = nullptr, *NotPreferredSUnit = nullptr;

588 bool HasNoopHazards = false;

589 while (!AvailableQueue.empty()) {

590 SUnit *CurSUnit = AvailableQueue.pop();

591

593 HazardRec->getHazardType(CurSUnit, 0);

596 if (!NotPreferredSUnit) {

597

598

599

600

601 NotPreferredSUnit = CurSUnit;

602 continue;

603 }

604 } else {

605 FoundSUnit = CurSUnit;

606 break;

607 }

608 }

609

610

612

613 NotReady.push_back(CurSUnit);

614 }

615

616

617

618

619 if (NotPreferredSUnit) {

620 if (!FoundSUnit) {

622 dbgs() << "*** Will schedule a non-preferred instruction...\n");

623 FoundSUnit = NotPreferredSUnit;

624 } else {

625 AvailableQueue.push(NotPreferredSUnit);

626 }

627

628 NotPreferredSUnit = nullptr;

629 }

630

631

632 if (!NotReady.empty()) {

633 AvailableQueue.push_all(NotReady);

634 NotReady.clear();

635 }

636

637

638 if (FoundSUnit) {

639

640 unsigned NumPreNoops = HazardRec->PreEmitNoops(FoundSUnit);

641 for (unsigned i = 0; i != NumPreNoops; ++i)

642 emitNoop(CurCycle);

643

644

645 ScheduleNodeTopDown(FoundSUnit, CurCycle);

647 CycleHasInsts = true;

649 LLVM_DEBUG(dbgs() << "*** Max instructions per cycle " << CurCycle

650 << '\n');

652 ++CurCycle;

653 CycleHasInsts = false;

654 }

655 } else {

656 if (CycleHasInsts) {

657 LLVM_DEBUG(dbgs() << "*** Finished cycle " << CurCycle << '\n');

659 } else if (!HasNoopHazards) {

660

661

662 LLVM_DEBUG(dbgs() << "*** Stall in cycle " << CurCycle << '\n');

664 ++NumStalls;

665 } else {

666

667

668

669 emitNoop(CurCycle);

670 }

671

672 ++CurCycle;

673 CycleHasInsts = false;

674 }

675 }

676

677#ifndef NDEBUG

678 unsigned ScheduledNodes = VerifyScheduledDAG(false);

679 unsigned Noops = llvm::count(Sequence, nullptr);

681 "The number of nodes scheduled doesn't match the expected number!");

682#endif

683}

684

685

686void SchedulePostRATDList::EmitSchedule() {

687 RegionBegin = RegionEnd;

688

689

690 if (FirstDbgValue)

691 BB->splice(RegionEnd, BB, FirstDbgValue);

692

693

694 for (unsigned i = 0, e = Sequence.size(); i != e; i++) {

695 if (SUnit *SU = Sequence[i])

697 else

698

700

701

702

703 if (i == 0)

704 RegionBegin = std::prev(RegionEnd);

705 }

706

707

708 for (std::vector<std::pair<MachineInstr *, MachineInstr *> >::iterator

709 DI = DbgValues.end(), DE = DbgValues.begin(); DI != DE; --DI) {

710 std::pair<MachineInstr *, MachineInstr *> P = *std::prev(DI);

711 MachineInstr *DbgValue = P.first;

713 BB->splice(++OrigPrivMI, BB, DbgValue);

714 }

715 DbgValues.clear();

716 FirstDbgValue = nullptr;

717}

unsigned const MachineRegisterInfo * MRI

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

static cl::opt< int > DebugDiv("agg-antidep-debugdiv", cl::desc("Debug control for aggressive anti-dep breaker"), cl::init(0), cl::Hidden)

static cl::opt< int > DebugMod("agg-antidep-debugmod", cl::desc("Debug control for aggressive anti-dep breaker"), cl::init(0), cl::Hidden)

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

#define LLVM_DUMP_METHOD

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

const HexagonInstrInfo * TII

Machine Instruction Scheduler

FunctionAnalysisManager FAM

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

static cl::opt< int > DebugDiv("postra-sched-debugdiv", cl::desc("Debug control MBBs that are scheduled"), cl::init(0), cl::Hidden)

static cl::opt< bool > EnablePostRAScheduler("post-RA-scheduler", cl::desc("Enable scheduling after register allocation"), cl::init(false), cl::Hidden)

static cl::opt< std::string > EnableAntiDepBreaking("break-anti-dependencies", cl::desc("Break post-RA scheduling anti-dependencies: " "\"critical\", \"all\", or \"none\""), cl::init("none"), cl::Hidden)

static bool enablePostRAScheduler(const TargetSubtargetInfo &ST, CodeGenOptLevel OptLevel)

Definition PostRASchedulerList.cpp:267

static cl::opt< int > DebugMod("postra-sched-debugmod", cl::desc("Debug control MBBs that are scheduled"), cl::init(0), cl::Hidden)

This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...

#define STATISTIC(VARNAME, DESC)

Target-Independent Code Generator Pass Configuration Options pass.

A manager for alias analyses.

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

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

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:

virtual void FinishBlock()=0

Finish anti-dep breaking for a basic block.

virtual unsigned BreakAntiDependencies(const std::vector< SUnit > &SUnits, MachineBasicBlock::iterator Begin, MachineBasicBlock::iterator End, unsigned InsertPosIndex, DbgValueVector &DbgValues)=0

Identifiy anti-dependencies within a basic-block region and break them by renaming registers.

virtual void Observe(MachineInstr &MI, unsigned Count, unsigned InsertPosIndex)=0

Update liveness information to account for the current instruction, which will not be scheduled.

virtual ~AntiDepBreaker()

virtual void StartBlock(MachineBasicBlock *BB)=0

Initialize anti-dep breaking for a new basic block.

Represents analyses that only rely on functions' control flow.

void insertNoop(MachineBasicBlock &MBB, MachineBasicBlock::iterator MI) const override

Insert a noop into the instruction stream at the specified point.

bool isSchedulingBoundary(const MachineInstr &MI, const MachineBasicBlock *MBB, const MachineFunction &MF) const override

Test if the given instruction should be considered a scheduling boundary.

Itinerary data supplied by a subtarget to be used by a target.

void releaseState() override

void push(SUnit *U) override

LLVM_DUMP_METHOD void dump(ScheduleDAG *DAG) const override

void scheduledNode(SUnit *SU) override

As each node is scheduled, this method is invoked.

void initNodes(std::vector< SUnit > &sunits) override

bool empty() const override

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

void splice(iterator Where, MachineBasicBlock *Other, iterator From)

Take an instruction from MBB 'Other' at the position From, and insert it into this MBB right before '...

MachineInstrBundleIterator< MachineInstr > iterator

Analysis pass which computes a MachineDominatorTree.

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.

const TargetSubtargetInfo & getSubtarget() const

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

Function & getFunction()

Return the LLVM function that this machine code represents.

Analysis pass that exposes the MachineLoopInfo for a machine function.

PreservedAnalyses run(MachineFunction &MF, MachineFunctionAnalysisManager &MFAM)

Definition PostRASchedulerList.cpp:373

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.

PreservedAnalyses & preserveSet()

Mark an analysis set as preserved.

PreservedAnalyses & preserve()

Mark an analysis as preserved.

LLVM_ABI void runOnMachineFunction(const MachineFunction &MF, bool Rev=false)

runOnFunction - Prepare to answer questions about MF.

bool isWeak() const

Tests if this a weak dependence.

unsigned getDepth() const

Returns the depth of this node, which is the length of the maximum path up to any node which has no p...

bool isScheduled

True once scheduled.

SmallVector< SDep, 4 > Succs

All sunit successors.

SmallVectorImpl< SDep >::iterator succ_iterator

LLVM_ABI void setDepthToAtLeast(unsigned NewDepth)

If NewDepth is greater than this node's depth value, sets it to be the new depth value.

MachineInstr * getInstr() const

Returns the representative MachineInstr for this SUnit.

A ScheduleDAG for scheduling lists of MachineInstr.

virtual void finishBlock()

Cleans up after scheduling in the given block.

virtual void startBlock(MachineBasicBlock *BB)

Prepares to perform scheduling in the given block.

virtual void exitRegion()

Called when the scheduler has finished scheduling the current region.

virtual void enterRegion(MachineBasicBlock *bb, MachineBasicBlock::iterator begin, MachineBasicBlock::iterator end, unsigned regioninstrs)

Initialize the DAG and common scheduler state for a new scheduling region.

void clearDAG()

Clears the DAG state (between regions).

virtual void Reset()

Reset - This callback is invoked when a new block of instructions is about to be schedule.

virtual void EmitInstruction(SUnit *)

EmitInstruction - This callback is invoked when an instruction is emitted, to advance the hazard stat...

virtual bool atIssueLimit() const

atIssueLimit - Return true if no more instructions may be issued in this cycle.

virtual bool ShouldPreferAnother(SUnit *)

ShouldPreferAnother - This callback may be invoked if getHazardType returns NoHazard.

virtual void EmitNoop()

EmitNoop - This callback is invoked when a noop was added to the instruction stream.

virtual void AdvanceCycle()

AdvanceCycle - This callback is invoked whenever the next top-down instruction to be scheduled cannot...

virtual HazardType getHazardType(SUnit *, int Stalls=0)

getHazardType - Return the hazard type of emitting this node.

virtual unsigned PreEmitNoops(SUnit *)

PreEmitNoops - This callback is invoked prior to emitting an instruction.

void push_all(const std::vector< SUnit * > &Nodes)

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

TargetInstrInfo - Interface to description of machine instruction set.

Primary interface to the complete machine description for the target machine.

CodeGenOptLevel getOptLevel() const

Returns the optimization level: None, Less, Default, or Aggressive.

TargetSubtargetInfo - Generic base class for all target subtargets.

enum { ANTIDEP_NONE, ANTIDEP_CRITICAL, ANTIDEP_ALL } AntiDepBreakMode

virtual AntiDepBreakMode getAntiDepBreakMode() const

#define llvm_unreachable(msg)

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

Abstract Attribute helper functions.

initializer< Ty > init(const Ty &Val)

PointerTypeMap run(const Module &M)

Compute the PointerTypeMap for the module M.

Sequence

A sequence of states that a pointer may go through in which an objc_retain and objc_release are actua...

This is an optimization pass for GlobalISel generic memory operations.

void dump(const SparseBitVector< ElementSize > &LHS, raw_ostream &out)

AntiDepBreaker * createAggressiveAntiDepBreaker(MachineFunction &MFi, const RegisterClassInfo &RCI, TargetSubtargetInfo::RegClassVector &CriticalPathRCs)

LLVM_ABI char & PostRASchedulerID

PostRAScheduler - This pass performs post register allocation scheduling.

Definition PostRASchedulerList.cpp:202

AnalysisManager< MachineFunction > MachineFunctionAnalysisManager

LLVM_ABI PreservedAnalyses getMachineFunctionPassPreservedAnalyses()

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

LLVM_ABI raw_ostream & dbgs()

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

FunctionAddr VTableAddr Count

CodeGenOptLevel

Code generation optimization level.

class LLVM_GSL_OWNER SmallVector

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

auto count(R &&Range, const E &Element)

Wrapper function around std::count to count the number of times an element Element occurs in the give...

AntiDepBreaker * createCriticalAntiDepBreaker(MachineFunction &MFi, const RegisterClassInfo &RCI)

AAResults AliasAnalysis

Temporary typedef for legacy code that uses a generic AliasAnalysis pointer or reference.

LLVM_ABI Printable printMBBReference(const MachineBasicBlock &MBB)

Prints a machine basic block reference.