ScheduleDAG.cpp Source File (original) (raw)

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

29#include

30#include

31#include

32#include

33#include

34#include

36using namespace llvm;

38#define DEBUG_TYPE "pre-RA-sched"

40 STATISTIC(NumNewPredsAdded, "Number of times a single predecessor was added");

42 "Number of times the topological order has been recomputed");

44#ifndef NDEBUG

47 cl::desc("Stress test instruction scheduling"));

48#endif

50void SchedulingPriorityQueue::anchor() {}

53 : TM(mf.getTarget()), TII(mf.getSubtarget().getInstrInfo()),

54 TRI(mf.getSubtarget().getRegisterInfo()), MF(mf),

55 MRI(mf.getRegInfo()) {

56#ifndef NDEBUG

58#endif

59}

70 if ( Node || Node ->isMachineOpcode()) return nullptr;

71 return &TII->get(Node->getMachineOpcode());

72}

76 case Data: dbgs() << "Data"; break;

77 case Anti: dbgs() << "Anti"; break;

79 case Order: dbgs() << "Ord "; break;

80 }

87 break;

91 break;

94 switch(Contents.OrdKind) {

95 case Barrier: dbgs() << " Barrier"; break;

99 case Weak: dbgs() << " Weak"; break;

100 case Cluster: dbgs() << " Cluster"; break;

101 }

102 break;

103 }

104}

105

107

109

110

111 if ( Required && PredDep.getSUnit() == D.getSUnit())

112 return false;

113 if (PredDep.overlaps(D)) {

114

115

116 if (PredDep.getLatency() < D.getLatency()) {

117 SUnit *PredSU = PredDep.getSUnit();

118

119 SDep ForwardD = PredDep;

121 for (SDep &SuccDep : PredSU->Succs) {

122 if (SuccDep == ForwardD) {

124 break;

125 }

126 }

127 PredDep.setLatency(D.getLatency());

128

131 }

132 return false;

133 }

134 }

135

137 P.setSUnit(this);

139

141 assert(NumPreds < std::numeric_limits::max() &&

142 "NumPreds will overflow!");

143 assert(N->NumSuccs < std::numeric_limits::max() &&

144 "NumSuccs will overflow!");

146 ++N->NumSuccs;

147 }

148 if (->isScheduled) {

149 if (D.isWeak()) {

151 }

152 else {

154 "NumPredsLeft will overflow!");

156 }

157 }

159 if (D.isWeak()) {

160 ++N->WeakSuccsLeft;

161 }

162 else {

163 assert(N->NumSuccsLeft < std::numeric_limits::max() &&

164 "NumSuccsLeft will overflow!");

165 ++N->NumSuccsLeft;

166 }

167 }

169 N->Succs.push_back(P);

172 return true;

173}

174

176

178 if (I == Preds.end())

179 return;

180

182 P.setSUnit(this);

185 assert(Succ != N->Succs.end() && "Mismatching preds / succs lists!");

186

189 assert(N->NumSuccs > 0 && "NumSuccs will underflow!");

191 --N->NumSuccs;

192 }

193 if (->isScheduled) {

194 if (D.isWeak()) {

197 } else {

200 }

201 }

203 if (D.isWeak()) {

204 assert(N->WeakSuccsLeft > 0 && "WeakSuccsLeft will underflow!");

205 --N->WeakSuccsLeft;

206 } else {

207 assert(N->NumSuccsLeft > 0 && "NumSuccsLeft will underflow!");

208 --N->NumSuccsLeft;

209 }

210 }

211 N->Succs.erase(Succ);

215}

216

218 if (!isDepthCurrent) return;

221 do {

223 SU->isDepthCurrent = false;

224 for (SDep &SuccDep : SU->Succs) {

226 if (SuccSU->isDepthCurrent)

228 }

229 } while (!WorkList.empty());

230}

231

233 if (!isHeightCurrent) return;

236 do {

238 SU->isHeightCurrent = false;

239 for (SDep &PredDep : SU->Preds) {

241 if (PredSU->isHeightCurrent)

243 }

244 } while (!WorkList.empty());

245}

246

249 return;

251 Depth = NewDepth;

252 isDepthCurrent = true;

253}

254

257 return;

259 Height = NewHeight;

260 isHeightCurrent = true;

261}

262

263

264void SUnit::ComputeDepth() {

267 do {

269

270 bool Done = true;

271 unsigned MaxPredDepth = 0;

272 for (const SDep &PredDep : Cur->Preds) {

274 if (PredSU->isDepthCurrent)

275 MaxPredDepth = std::max(MaxPredDepth,

276 PredSU->Depth + PredDep.getLatency());

277 else {

278 Done = false;

280 }

281 }

282

285 if (MaxPredDepth != Cur->Depth) {

287 Cur->Depth = MaxPredDepth;

288 }

289 Cur->isDepthCurrent = true;

290 }

291 } while (!WorkList.empty());

292}

293

294

295void SUnit::ComputeHeight() {

298 do {

300

301 bool Done = true;

302 unsigned MaxSuccHeight = 0;

303 for (const SDep &SuccDep : Cur->Succs) {

305 if (SuccSU->isHeightCurrent)

306 MaxSuccHeight = std::max(MaxSuccHeight,

307 SuccSU->Height + SuccDep.getLatency());

308 else {

309 Done = false;

311 }

312 }

313

316 if (MaxSuccHeight != Cur->Height) {

318 Cur->Height = MaxSuccHeight;

319 }

320 Cur->isHeightCurrent = true;

321 }

322 } while (!WorkList.empty());

323}

324

327 return;

328

330 unsigned MaxDepth = BestI->getSUnit()->getDepth();

332 ++I) {

333 if (I->getKind() == SDep::Data && I->getSUnit()->getDepth() > MaxDepth) {

334 MaxDepth = I->getSUnit()->getDepth();

335 BestI = I;

336 }

337 }

338 if (BestI != Preds.begin())

340}

341

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

355

358 dbgs() << "EntrySU";

359 else if (&SU == &ExitSU)

360 dbgs() << "ExitSU";

361 else

363}

364

370

371 if (SU.Preds.size() > 0) {

372 dbgs() << " Predecessors:\n";

373 for (const SDep &Dep : SU.Preds) {

374 dbgs() << " ";

376 dbgs() << ": ";

378 dbgs() << '\n';

379 }

380 }

381 if (SU.Succs.size() > 0) {

382 dbgs() << " Successors:\n";

383 for (const SDep &Dep : SU.Succs) {

384 dbgs() << " ";

386 dbgs() << ": ";

388 dbgs() << '\n';

389 }

390 }

391}

392#endif

393

394#ifndef NDEBUG

396 bool AnyNotSched = false;

397 unsigned DeadNodes = 0;

401 ++DeadNodes;

402 continue;

403 }

404 if (!AnyNotSched)

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

407 dbgs() << "has not been scheduled!\n";

408 AnyNotSched = true;

409 }

412 unsigned(std::numeric_limits::max())) {

413 if (!AnyNotSched)

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

416 dbgs() << "has an unexpected "

417 << (isBottomUp ? "Height" : "Depth") << " value!\n";

418 AnyNotSched = true;

419 }

420 if (isBottomUp) {

422 if (!AnyNotSched)

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

425 dbgs() << "has successors left!\n";

426 AnyNotSched = true;

427 }

428 } else {

430 if (!AnyNotSched)

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

433 dbgs() << "has predecessors left!\n";

434 AnyNotSched = true;

435 }

436 }

437 }

438 assert(!AnyNotSched);

439 return SUnits.size() - DeadNodes;

440}

441#endif

442

444

445

446

447

448

449

450

451

452

453

454

455

456

457

458

459

460

461

462

463

464

465

466

467

468

469

470

471

472 Dirty = false;

473 Updates.clear();

474

475 unsigned DAGSize = SUnits.size();

476 std::vector<SUnit*> WorkList;

477 WorkList.reserve(DAGSize);

478

479 Index2Node.resize(DAGSize);

480 Node2Index.resize(DAGSize);

481

482

483 if (ExitSU)

484 WorkList.push_back(ExitSU);

485 for (SUnit &SU : SUnits) {

486 int NodeNum = SU.NodeNum;

487 unsigned Degree = SU.Succs.size();

488

489 Node2Index[NodeNum] = Degree;

490

491

492 if (Degree == 0) {

493 assert(SU.Succs.empty() && "SUnit should have no successors");

494

495 WorkList.push_back(&SU);

496 }

497 }

498

499 int Id = DAGSize;

500 while (!WorkList.empty()) {

501 SUnit *SU = WorkList.back();

502 WorkList.pop_back();

503 if (SU->NodeNum < DAGSize)

504 Allocate(SU->NodeNum, --Id);

505 for (const SDep &PredDep : SU->Preds) {

507 if (SU->NodeNum < DAGSize && !--Node2Index[SU->NodeNum])

508

509

510 WorkList.push_back(SU);

511 }

512 }

513

514 Visited.resize(DAGSize);

515 NumTopoInits++;

516

517#ifndef NDEBUG

518

519 for (SUnit &SU : SUnits) {

520 for (const SDep &PD : SU.Preds) {

521 assert(Node2Index[SU.NodeNum] > Node2Index[PD.getSUnit()->NodeNum] &&

522 "Wrong topological sorting");

523 }

524 }

525#endif

526}

527

528void ScheduleDAGTopologicalSort::FixOrder() {

529

530 if (Dirty) {

532 return;

533 }

534

535

536 for (auto &U : Updates)

537 AddPred(U.first, U.second);

538 Updates.clear();

539}

540

542

543

544

545 Dirty = Dirty || Updates.size() > 10;

546

547 if (Dirty)

548 return;

549

550 Updates.emplace_back(Y, X);

551}

552

554 int UpperBound, LowerBound;

555 LowerBound = Node2Index[Y->NodeNum];

556 UpperBound = Node2Index[X->NodeNum];

557 bool HasLoop = false;

558

559 if (LowerBound < UpperBound) {

560

561 Visited.reset();

562 DFS(Y, UpperBound, HasLoop);

563 assert(!HasLoop && "Inserted edge creates a loop!");

564

565 Shift(Visited, LowerBound, UpperBound);

566 }

567

568 NumNewPredsAdded++;

569}

570

574

575void ScheduleDAGTopologicalSort::DFS(const SUnit *SU, int UpperBound,

576 bool &HasLoop) {

577 std::vector<const SUnit*> WorkList;

578 WorkList.reserve(SUnits.size());

579

580 WorkList.push_back(SU);

581 do {

582 SU = WorkList.back();

583 WorkList.pop_back();

587

588 if (s >= Node2Index.size())

589 continue;

590 if (Node2Index[s] == UpperBound) {

591 HasLoop = true;

592 return;

593 }

594

595 if (!Visited.test(s) && Node2Index[s] < UpperBound) {

596 WorkList.push_back(SuccDep.getSUnit());

597 }

598 }

599 } while (!WorkList.empty());

600}

601

603 const SUnit &TargetSU,

605 std::vector<const SUnit*> WorkList;

606 int LowerBound = Node2Index[StartSU.NodeNum];

607 int UpperBound = Node2Index[TargetSU.NodeNum];

608 bool Found = false;

610 std::vector Nodes;

611

612 if (LowerBound > UpperBound) {

614 return Nodes;

615 }

616

617 WorkList.reserve(SUnits.size());

618 Visited.reset();

619

620

621

622 WorkList.push_back(&StartSU);

623 do {

624 const SUnit *SU = WorkList.back();

625 WorkList.pop_back();

627 const SUnit *Succ = SD.getSUnit();

628 unsigned s = Succ->NodeNum;

629

631 continue;

632 if (Node2Index[s] == UpperBound) {

633 Found = true;

634 continue;

635 }

636

637 if (!Visited.test(s) && Node2Index[s] < UpperBound) {

638 Visited.set(s);

639 WorkList.push_back(Succ);

640 }

641 }

642 } while (!WorkList.empty());

643

644 if (!Found) {

646 return Nodes;

647 }

648

649 WorkList.clear();

650 VisitedBack.resize(SUnits.size());

651 Found = false;

652

653

654

655

656 WorkList.push_back(&TargetSU);

657 do {

658 const SUnit *SU = WorkList.back();

659 WorkList.pop_back();

661 const SUnit *Pred = SD.getSUnit();

662 unsigned s = Pred->NodeNum;

663

664 if (Pred->isBoundaryNode())

665 continue;

666 if (Node2Index[s] == LowerBound) {

667 Found = true;

668 continue;

669 }

670 if (!VisitedBack.test(s) && Visited.test(s)) {

671 VisitedBack.set(s);

672 WorkList.push_back(Pred);

673 Nodes.push_back(s);

674 }

675 }

676 } while (!WorkList.empty());

677

678 assert(Found && "Error in SUnit Graph!");

680 return Nodes;

681}

682

683void ScheduleDAGTopologicalSort::Shift(BitVector& Visited, int LowerBound,

684 int UpperBound) {

685 std::vector L;

686 int shift = 0;

687 int i;

688

689 for (i = LowerBound; i <= UpperBound; ++i) {

690

691 int w = Index2Node[i];

692 if (Visited.test(w)) {

693

694 Visited.reset(w);

695 L.push_back(w);

696 shift = shift + 1;

697 } else {

698 Allocate(w, i - shift);

699 }

700 }

701

702 for (unsigned LI : L) {

703 Allocate(LI, i - shift);

704 i = i + 1;

705 }

706}

707

709 FixOrder();

710

712 return true;

713 for (const SDep &PredDep : TargetSU->Preds)

716 return true;

717 return false;

718}

719

721 assert(SU->NodeNum == Index2Node.size() && "Node cannot be added at the end");

722 assert(SU->NumPreds == 0 && "Can only add SU's with no predecessors");

723 Node2Index.push_back(Index2Node.size());

724 Index2Node.push_back(SU->NodeNum);

725 Visited.resize(Node2Index.size());

726}

727

729 const SUnit *TargetSU) {

730 assert(TargetSU != nullptr && "Invalid target SUnit");

731 assert(SU != nullptr && "Invalid SUnit");

732 FixOrder();

733

734

735 int UpperBound, LowerBound;

736 LowerBound = Node2Index[TargetSU->NodeNum];

737 UpperBound = Node2Index[SU->NodeNum];

738 bool HasLoop = false;

739

740 if (LowerBound < UpperBound) {

741 Visited.reset();

742

743 DFS(TargetSU, UpperBound, HasLoop);

744 }

745 return HasLoop;

746}

747

748void ScheduleDAGTopologicalSort::Allocate(int n, int index) {

749 Node2Index[n] = index;

750 Index2Node[index] = n;

751}

752

755 : SUnits(sunits), ExitSU(exitsu) {}

756

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

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

#define LLVM_DUMP_METHOD

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

const HexagonInstrInfo * TII

static cl::opt< bool > StressSchedOpt("stress-sched", cl::Hidden, cl::init(false), cl::desc("Stress test instruction scheduling"))

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)

static TableGen::Emitter::Opt Y("gen-skeleton-entry", EmitSkeleton, "Generate example skeleton entry")

static TableGen::Emitter::OptClass< SkeletonEmitter > X("gen-skeleton-class", "Generate example skeleton class")

bool test(unsigned Idx) const

void resize(unsigned N, bool t=false)

resize - Grow or shrink the bitvector.

Describe properties that are true of each instruction in the target description file.

Represents one node in the SelectionDAG.

Kind getKind() const

Returns an enum value representing the kind of the dependence.

@ Output

A register output-dependence (aka WAW).

@ Order

Any other ordering dependency.

@ Anti

A register anti-dependence (aka WAR).

@ Data

Regular data dependence (aka true-dependence).

void setLatency(unsigned Lat)

Sets the latency for this edge.

@ Cluster

Weak DAG edge linking a chain of clustered instrs.

@ Barrier

An unknown scheduling barrier.

@ Artificial

Arbitrary strong DAG edge (no real dependence).

@ MayAliasMem

Nonvolatile load/Store instructions that may alias.

@ Weak

Arbitrary weak DAG edge.

@ MustAliasMem

Nonvolatile load/Store instructions that must alias.

unsigned getLatency() const

Returns the latency value for this edge, which roughly means the minimum number of cycles that must e...

bool isAssignedRegDep() const

Tests if this is a Data dependence that is associated with a register.

Returns the register associated with this edge.

LLVM_ABI void dump(const TargetRegisterInfo *TRI=nullptr) const

Definition ScheduleDAG.cpp:74

Scheduling unit. This is a node in the scheduling DAG.

LLVM_ABI void setHeightToAtLeast(unsigned NewHeight)

If NewHeight is greater than this node's height value, set it to be the new height value.

Definition ScheduleDAG.cpp:255

unsigned NodeNum

Entry # of node in the node vector.

LLVM_ABI void biasCriticalPath()

Orders this node's predecessor edges such that the critical path edge occurs first.

Definition ScheduleDAG.cpp:325

unsigned getHeight() const

Returns the height of this node, which is the length of the maximum path down to any node which has n...

LLVM_ABI void setHeightDirty()

Sets a flag in this node to indicate that its stored Height value will require recomputation the next...

Definition ScheduleDAG.cpp:232

LLVM_ABI void removePred(const SDep &D)

Removes the specified edge as a pred of the current node if it exists.

Definition ScheduleDAG.cpp:175

unsigned short Latency

Node latency.

SmallVectorImpl< SDep >::iterator pred_iterator

bool isBoundaryNode() const

Boundary nodes are placeholders for the boundary of the scheduling region.

unsigned short NumRegDefsLeft

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.

unsigned ParentClusterIdx

The parent cluster id.

LLVM_ABI void dumpAttributes() const

Definition ScheduleDAG.cpp:343

SmallVector< SDep, 4 > Succs

All sunit successors.

SUnit(SDNode *node, unsigned nodenum)

Constructs an SUnit for pre-regalloc scheduling to represent an SDNode and any nodes flagged to it.

LLVM_ABI void setDepthDirty()

Sets a flag in this node to indicate that its stored Depth value will require recomputation the next ...

Definition ScheduleDAG.cpp:217

SmallVector< SDep, 4 > Preds

All sunit predecessors.

LLVM_ABI void setDepthToAtLeast(unsigned NewDepth)

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

Definition ScheduleDAG.cpp:247

LLVM_ABI bool addPred(const SDep &D, bool Required=true)

Adds the specified edge as a pred of the current node if not already.

Definition ScheduleDAG.cpp:106

LLVM_ABI void RemovePred(SUnit *M, SUnit *N)

Updates the topological ordering to accommodate an edge to be removed from the specified node N from ...

Definition ScheduleDAG.cpp:571

LLVM_ABI bool WillCreateCycle(SUnit *TargetSU, SUnit *SU)

Returns true if addPred(TargetSU, SU) creates a cycle.

Definition ScheduleDAG.cpp:708

LLVM_ABI void AddSUnitWithoutPredecessors(const SUnit *SU)

Add a SUnit without predecessors to the end of the topological order.

Definition ScheduleDAG.cpp:720

LLVM_ABI ScheduleDAGTopologicalSort(std::vector< SUnit > &SUnits, SUnit *ExitSU)

Definition ScheduleDAG.cpp:754

LLVM_ABI std::vector< int > GetSubGraph(const SUnit &StartSU, const SUnit &TargetSU, bool &Success)

Returns an array of SUs that are both in the successor subtree of StartSU and in the predecessor subt...

Definition ScheduleDAG.cpp:602

LLVM_ABI void InitDAGTopologicalSorting()

Creates the initial topological ordering from the DAG to be scheduled.

Definition ScheduleDAG.cpp:443

LLVM_ABI void AddPred(SUnit *Y, SUnit *X)

Updates the topological ordering to accommodate an edge to be added from SUnit X to SUnit Y.

Definition ScheduleDAG.cpp:553

LLVM_ABI bool IsReachable(const SUnit *SU, const SUnit *TargetSU)

Checks if SU is reachable from TargetSU.

Definition ScheduleDAG.cpp:728

LLVM_ABI void AddPredQueued(SUnit *Y, SUnit *X)

Queues an update to the topological ordering to accommodate an edge to be added from SUnit X to SUnit...

Definition ScheduleDAG.cpp:541

MachineRegisterInfo & MRI

Virtual/real register map.

void clearDAG()

Clears the DAG state (between regions).

Definition ScheduleDAG.cpp:63

const TargetInstrInfo * TII

Target instruction information.

std::vector< SUnit > SUnits

The scheduling units.

const TargetRegisterInfo * TRI

Target processor register info.

SUnit EntrySU

Special node for the region entry.

MachineFunction & MF

Machine function.

ScheduleDAG(const ScheduleDAG &)=delete

void dumpNodeAll(const SUnit &SU) const

Definition ScheduleDAG.cpp:365

const TargetMachine & TM

Target processor.

unsigned VerifyScheduledDAG(bool isBottomUp)

Verifies that all SUnits were scheduled and that their state is consistent.

Definition ScheduleDAG.cpp:395

virtual void dumpNode(const SUnit &SU) const =0

void dumpNodeName(const SUnit &SU) const

Definition ScheduleDAG.cpp:356

SUnit ExitSU

Special node for the region exit.

virtual ~ScheduleHazardRecognizer()

typename SuperClass::iterator iterator

void push_back(const T &Elt)

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

TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...

initializer< Ty > init(const Ty &Val)

This is an optimization pass for GlobalISel generic memory operations.

auto find(R &&Range, const T &Val)

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

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

@ Success

The lock was released successfully.

constexpr unsigned InvalidClusterId

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.

void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)

Implement std::swap in terms of BitVector swap.