ScheduleDAGRRList.cpp Source File (original) (raw)

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

50#include

51#include

52#include

53#include

54#include

55#include

56#include

57#include

58#include

60using namespace llvm;

62#define DEBUG_TYPE "pre-RA-sched"

64 STATISTIC(NumBacktracks, "Number of times scheduler backtracked");

65 STATISTIC(NumUnfolds, "Number of nodes unfolded");

66 STATISTIC(NumDups, "Number of duplicated nodes");

67 STATISTIC(NumPRCopies, "Number of physical register copies");

71 "Bottom-up register reduction list scheduling",

76 "Similar to list-burr but schedules in source "

77 "order when possible",

82 "Bottom-up register pressure aware list scheduling "

83 "which tries to balance latency and register pressure",

88 "Bottom-up register pressure aware list scheduling "

89 "which tries to balance ILP and register pressure",

94 cl::desc("Disable cycle-level precision during preRA scheduling"));

100 cl::desc("Disable regpressure priority in sched=list-ilp"));

103 cl::desc("Disable live use priority in sched=list-ilp"));

106 cl::desc("Disable virtual register cycle interference checks"));

109 cl::desc("Disable physreg def-use affinity"));

112 cl::desc("Disable no-stall priority in sched=list-ilp"));

115 cl::desc("Disable critical path priority in sched=list-ilp"));

118 cl::desc("Disable scheduled-height priority in sched=list-ilp"));

121 cl::desc("Disable scheduler's two-address hack"));

122

125 cl::desc("Number of instructions to allow ahead of the critical path "

126 "in sched=list-ilp"));

127

130 cl::desc("Average inst/cycle when no target itinerary exists."));

131

132namespace {

133

134

135

136

137

139private:

140

141 bool NeedLatency;

142

143

145

146

147

148

149

150 std::vector<SUnit *> PendingQueue;

151

152

154

155

156 unsigned CurCycle = 0;

157

158

159 unsigned MinAvailableCycle = ~0u;

160

161

162

163 unsigned IssueCount = 0u;

164

165

166

167

168 unsigned NumLiveRegs = 0u;

169 std::unique_ptr<SUnit*[]> LiveRegDefs;

170 std::unique_ptr<SUnit*[]> LiveRegGens;

171

172

173

175

177

178 LRegsMapT LRegsMap;

179

180

181

183

184

185

187

188public:

193 AvailableQueue(availqueue), Topo(SUnits, nullptr) {

197 else

198 HazardRec = STI.getInstrInfo()->CreateTargetHazardRecognizer(&STI, this);

199 }

200

201 ~ScheduleDAGRRList() override {

202 delete HazardRec;

203 delete AvailableQueue;

204 }

205

206 void Schedule() override;

207

208 ScheduleHazardRecognizer *getHazardRec() { return HazardRec; }

209

210

211 bool IsReachable(const SUnit *SU, const SUnit *TargetSU) {

212 return Topo.IsReachable(SU, TargetSU);

213 }

214

215

216

217 bool WillCreateCycle(SUnit *SU, SUnit *TargetSU) {

218 return Topo.WillCreateCycle(SU, TargetSU);

219 }

220

221

222

223

224 void AddPredQueued(SUnit *SU, const SDep &D) {

225 Topo.AddPredQueued(SU, D.getSUnit());

227 }

228

229

230

231

232 void AddPred(SUnit *SU, const SDep &D) {

233 Topo.AddPred(SU, D.getSUnit());

235 }

236

237

238

239

240 void RemovePred(SUnit *SU, const SDep &D) {

241 Topo.RemovePred(SU, D.getSUnit());

243 }

244

245private:

246 bool isReady(SUnit *SU) {

248 AvailableQueue->isReady(SU);

249 }

250

251 void ReleasePred(SUnit *SU, const SDep *PredEdge);

252 void ReleasePredecessors(SUnit *SU);

253 void ReleasePending();

254 void AdvanceToCycle(unsigned NextCycle);

255 void AdvancePastStalls(SUnit *SU);

256 void EmitNode(SUnit *SU);

257 void ScheduleNodeBottomUp(SUnit*);

258 void CapturePred(SDep *PredEdge);

259 void UnscheduleNodeBottomUp(SUnit*);

260 void RestoreHazardCheckerBottomUp();

261 void BacktrackBottomUp(SUnit*, SUnit*);

262 SUnit *TryUnfoldSU(SUnit *);

263 SUnit *CopyAndMoveSuccessors(SUnit*);

264 void InsertCopiesAndMoveSuccs(SUnit*, unsigned,

265 const TargetRegisterClass*,

266 const TargetRegisterClass*,

267 SmallVectorImpl<SUnit*>&);

268 bool DelayForLiveRegsBottomUp(SUnit*, SmallVectorImpl&);

269

270 void releaseInterferences(unsigned Reg = 0);

271

272 SUnit *PickNodeToScheduleBottomUp();

273 void ListScheduleBottomUp();

274

275

276 SUnit *CreateNewSUnit(SDNode *N) {

277 unsigned NumSUnits = SUnits.size();

278 SUnit *NewNode = newSUnit(N);

279

280 if (NewNode->NodeNum >= NumSUnits)

281 Topo.AddSUnitWithoutPredecessors(NewNode);

282 return NewNode;

283 }

284

285

286 SUnit *CreateClone(SUnit *N) {

287 unsigned NumSUnits = SUnits.size();

288 SUnit *NewNode = Clone(N);

289

290 if (NewNode->NodeNum >= NumSUnits)

291 Topo.AddSUnitWithoutPredecessors(NewNode);

292 return NewNode;

293 }

294

295

296

297 bool forceUnitLatencies() const override {

298 return !NeedLatency;

299 }

300};

301

302}

303

305

306

307

308

309

314 unsigned &RegClass, unsigned &Cost,

317

318

319

320 if (VT == MVT::Untyped) {

322

323

327 RegClass = RC->getID();

328 Cost = 1;

329 return;

330 }

331

332 unsigned Opcode = Node->getMachineOpcode();

333 if (Opcode == TargetOpcode::REG_SEQUENCE) {

334 unsigned DstRCIdx = Node->getConstantOperandVal(0);

336 RegClass = RC->getID();

338 return;

339 }

340

341 unsigned Idx = RegDefPos.GetIdx();

344 assert(RC && "Not a valid register class");

345 RegClass = RC->getID();

346

347

348 Cost = 1;

349 } else {

352 }

353}

354

355

356void ScheduleDAGRRList::Schedule() {

358 << " '" << BB->getName() << "' **********\n");

359

360 CurCycle = 0;

361 IssueCount = 0;

362 MinAvailableCycle =

364 NumLiveRegs = 0;

365

366

367 LiveRegDefs.reset(new SUnit*[TRI->getNumRegs() + 1]());

368 LiveRegGens.reset(new SUnit*[TRI->getNumRegs() + 1]());

369 CallSeqEndForStart.clear();

370 assert(Interferences.empty() && LRegsMap.empty() && "stale Interferences");

371

372

373 BuildSchedGraph();

374

377

378 AvailableQueue->initNodes(SUnits);

379

380 HazardRec->Reset();

381

382

383 ListScheduleBottomUp();

384

386

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

389 dumpSchedule();

390 dbgs() << '\n';

391 });

392}

393

394

395

396

397

398

399

400void ScheduleDAGRRList::ReleasePred(SUnit *SU, const SDep *PredEdge) {

401 SUnit *PredSU = PredEdge->getSUnit();

402

403#ifndef NDEBUG

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

406 dumpNode(*PredSU);

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

409 }

410#endif

412

413 if (!forceUnitLatencies()) {

414

415

417 }

418

419

420

421 if (PredSU->NumSuccsLeft == 0 && PredSU != &EntrySU) {

423

424 unsigned Height = PredSU->getHeight();

425 if (Height < MinAvailableCycle)

426 MinAvailableCycle = Height;

427

428 if (isReady(PredSU)) {

429 AvailableQueue->push(PredSU);

430 }

431

432

435 PendingQueue.push_back(PredSU);

436 }

437 }

438}

439

440

441

443 unsigned NestLevel,

446 while (true) {

447 if (N == Inner)

448 return true;

449

450

451

453 for (const SDValue &Op : N->op_values())

455 return true;

456 return false;

457 }

458

459 if (N->isMachineOpcode()) {

460 if (N->getMachineOpcode() == TII->getCallFrameDestroyOpcode()) {

461 ++NestLevel;

462 } else if (N->getMachineOpcode() == TII->getCallFrameSetupOpcode()) {

463 if (NestLevel == 0)

464 return false;

465 --NestLevel;

466 }

467 }

468

469 for (const SDValue &Op : N->op_values())

470 if (Op.getValueType() == MVT::Other) {

471 N = Op.getNode();

472 goto found_chain_operand;

473 }

474 return false;

475 found_chain_operand:;

477 return false;

478 }

479}

480

481

482

483

484

485

486

487

488

489

490static SDNode *

493 while (true) {

494

495

496

498 SDNode *Best = nullptr;

499 unsigned BestMaxNest = MaxNest;

500 for (const SDValue &Op : N->op_values()) {

501 unsigned MyNestLevel = NestLevel;

502 unsigned MyMaxNest = MaxNest;

504 MyNestLevel, MyMaxNest, TII))

505 if (!Best || (MyMaxNest > BestMaxNest)) {

506 Best = New;

507 BestMaxNest = MyMaxNest;

508 }

509 }

511 MaxNest = BestMaxNest;

512 return Best;

513 }

514

515 if (N->isMachineOpcode()) {

516 if (N->getMachineOpcode() == TII->getCallFrameDestroyOpcode()) {

517 ++NestLevel;

518 MaxNest = std::max(MaxNest, NestLevel);

519 } else if (N->getMachineOpcode() == TII->getCallFrameSetupOpcode()) {

520 assert(NestLevel != 0);

521 --NestLevel;

522 if (NestLevel == 0)

523 return N;

524 }

525 }

526

527 for (const SDValue &Op : N->op_values())

528 if (Op.getValueType() == MVT::Other) {

529 N = Op.getNode();

530 goto found_chain_operand;

531 }

532 return nullptr;

533 found_chain_operand:;

535 return nullptr;

536 }

537}

538

539

540

541

542

543

544

545

546

547

548

549

550

551

552

553

554

555

556void ScheduleDAGRRList::ReleasePredecessors(SUnit *SU) {

557

558 for (SDep &Pred : SU->Preds) {

559 ReleasePred(SU, &Pred);

561

562

563

564

565 SUnit *RegDef = LiveRegDefs[Pred.getReg()]; (void)RegDef;

566 assert((!RegDef || RegDef == SU || RegDef == Pred.getSUnit()) &&

567 "interference on register dependence");

569 if (!LiveRegGens[Pred.getReg()]) {

570 ++NumLiveRegs;

571 LiveRegGens[Pred.getReg()] = SU;

572 }

573 }

574 }

575

576

577

578

579 unsigned CallResource = TRI->getNumRegs();

580 if (!LiveRegDefs[CallResource])

581 for (SDNode *Node = SU->getNode(); Node; Node = Node->getGluedNode())

582 if (Node->isMachineOpcode() &&

584 unsigned NestLevel = 0;

585 unsigned MaxNest = 0;

587 assert(N && "Must find call sequence start");

588

589 SUnit *Def = &SUnits[N->getNodeId()];

590 CallSeqEndForStart[Def] = SU;

591

592 ++NumLiveRegs;

593 LiveRegDefs[CallResource] = Def;

594 LiveRegGens[CallResource] = SU;

595 break;

596 }

597}

598

599

600

601void ScheduleDAGRRList::ReleasePending() {

603 assert(PendingQueue.empty() && "pending instrs not allowed in this mode");

604 return;

605 }

606

607

608 if (AvailableQueue->empty())

609 MinAvailableCycle = std::numeric_limits::max();

610

611

612

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

614 unsigned ReadyCycle = PendingQueue[i]->getHeight();

615 if (ReadyCycle < MinAvailableCycle)

616 MinAvailableCycle = ReadyCycle;

617

618 if (PendingQueue[i]->isAvailable) {

619 if (!isReady(PendingQueue[i]))

620 continue;

621 AvailableQueue->push(PendingQueue[i]);

622 }

623 PendingQueue[i]->isPending = false;

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

625 PendingQueue.pop_back();

626 --i; --e;

627 }

628}

629

630

631void ScheduleDAGRRList::AdvanceToCycle(unsigned NextCycle) {

632 if (NextCycle <= CurCycle)

633 return;

634

635 IssueCount = 0;

638

639 CurCycle = NextCycle;

640 }

641 else {

642 for (; CurCycle != NextCycle; ++CurCycle) {

644 }

645 }

646

647

648 ReleasePending();

649}

650

651

652

653void ScheduleDAGRRList::AdvancePastStalls(SUnit *SU) {

655 return;

656

657

658

659

660

661

662

663

664 unsigned ReadyCycle = SU->getHeight();

665

666

667

668

669

670 AdvanceToCycle(ReadyCycle);

671

672

673

674

676 return;

677

678

679

680 int Stalls = 0;

681 while (true) {

684

686 break;

687

688 ++Stalls;

689 }

690 AdvanceToCycle(CurCycle + Stalls);

691}

692

693

694

695void ScheduleDAGRRList::EmitNode(SUnit *SU) {

697 return;

698

699

701 return;

702

704 default:

706 "This target-independent node should not be scheduled.");

707 break;

710 case ISD::LIFETIME_START:

711 case ISD::LIFETIME_END:

714 case ISD::EH_LABEL:

715

716

717 return;

718 case ISD::INLINEASM:

719 case ISD::INLINEASM_BR:

720

721 HazardRec->Reset();

722 return;

723 }

725

726

727 HazardRec->Reset();

728 }

729

731}

732

734

735

736

737

738void ScheduleDAGRRList::ScheduleNodeBottomUp(SUnit *SU) {

739 LLVM_DEBUG(dbgs() << "\n*** Scheduling [" << CurCycle << "]: ");

741

742#ifndef NDEBUG

743 if (CurCycle < SU->getHeight())

745 << "] pipeline stall!\n");

746#endif

747

748

749

750

751

753

754

755 EmitNode(SU);

756

758

760

761

762

763

765 AdvanceToCycle(CurCycle + 1);

766

767

768

769 ReleasePredecessors(SU);

770

771

772 for (SDep &Succ : SU->Succs) {

773

775 assert(NumLiveRegs > 0 && "NumLiveRegs is already zero!");

776 --NumLiveRegs;

777 LiveRegDefs[Succ.getReg()] = nullptr;

778 LiveRegGens[Succ.getReg()] = nullptr;

779 releaseInterferences(Succ.getReg());

780 }

781 }

782

783

784 unsigned CallResource = TRI->getNumRegs();

785 if (LiveRegDefs[CallResource] == SU)

786 for (const SDNode *SUNode = SU->getNode(); SUNode;

788 if (SUNode->isMachineOpcode() &&

790 assert(NumLiveRegs > 0 && "NumLiveRegs is already zero!");

791 --NumLiveRegs;

792 LiveRegDefs[CallResource] = nullptr;

793 LiveRegGens[CallResource] = nullptr;

794 releaseInterferences(CallResource);

795 }

796 }

797

799

801

802

803

804

805

806

807

808

809

812 ++IssueCount;

815 AdvanceToCycle(CurCycle + 1);

816 }

817}

818

819

820

821

822void ScheduleDAGRRList::CapturePred(SDep *PredEdge) {

823 SUnit *PredSU = PredEdge->getSUnit();

827 AvailableQueue->remove(PredSU);

828 }

829

830 assert(PredSU->NumSuccsLeft < std::numeric_limits::max() &&

831 "NumSuccsLeft will overflow!");

833}

834

835

836

837void ScheduleDAGRRList::UnscheduleNodeBottomUp(SUnit *SU) {

840

841 for (SDep &Pred : SU->Preds) {

842 CapturePred(&Pred);

844 assert(NumLiveRegs > 0 && "NumLiveRegs is already zero!");

846 "Physical register dependency violated?");

847 --NumLiveRegs;

848 LiveRegDefs[Pred.getReg()] = nullptr;

849 LiveRegGens[Pred.getReg()] = nullptr;

850 releaseInterferences(Pred.getReg());

851 }

852 }

853

854

855

856 unsigned CallResource = TRI->getNumRegs();

857 for (const SDNode *SUNode = SU->getNode(); SUNode;

859 if (SUNode->isMachineOpcode() &&

861 SUnit *SeqEnd = CallSeqEndForStart[SU];

862 assert(SeqEnd && "Call sequence start/end must be known");

863 assert(!LiveRegDefs[CallResource]);

864 assert(!LiveRegGens[CallResource]);

865 ++NumLiveRegs;

866 LiveRegDefs[CallResource] = SU;

867 LiveRegGens[CallResource] = SeqEnd;

868 }

869 }

870

871

872

873 if (LiveRegGens[CallResource] == SU)

874 for (const SDNode *SUNode = SU->getNode(); SUNode;

876 if (SUNode->isMachineOpcode() &&

878 assert(NumLiveRegs > 0 && "NumLiveRegs is already zero!");

879 assert(LiveRegDefs[CallResource]);

880 assert(LiveRegGens[CallResource]);

881 --NumLiveRegs;

882 LiveRegDefs[CallResource] = nullptr;

883 LiveRegGens[CallResource] = nullptr;

884 releaseInterferences(CallResource);

885 }

886 }

887

888 for (auto &Succ : SU->Succs) {

891 if (!LiveRegDefs[Reg])

892 ++NumLiveRegs;

893

894

895 LiveRegDefs[Reg] = SU;

896

897

898

899 if (!LiveRegGens[Reg]) {

900

902 for (auto &Succ2 : SU->Succs) {

903 if (Succ2.isAssignedRegDep() && Succ2.getReg() == Reg &&

904 Succ2.getSUnit()->getHeight() < LiveRegGens[Reg]->getHeight())

905 LiveRegGens[Reg] = Succ2.getSUnit();

906 }

907 }

908 }

909 }

910 if (SU->getHeight() < MinAvailableCycle)

911 MinAvailableCycle = SU->getHeight();

912

917

919 PendingQueue.push_back(SU);

920 }

921 else {

922 AvailableQueue->push(SU);

923 }

925}

926

927

928

929void ScheduleDAGRRList::RestoreHazardCheckerBottomUp() {

930 HazardRec->Reset();

931

932 unsigned LookAhead = std::min((unsigned)Sequence.size(),

934 if (LookAhead == 0)

935 return;

936

937 std::vector<SUnit *>::const_iterator I = (Sequence.end() - LookAhead);

938 unsigned HazardCycle = (*I)->getHeight();

940 SUnit *SU = *I;

941 for (; SU->getHeight() > HazardCycle; ++HazardCycle) {

943 }

944 EmitNode(SU);

945 }

946}

947

948

949

950void ScheduleDAGRRList::BacktrackBottomUp(SUnit *SU, SUnit *BtSU) {

951 SUnit *OldSU = Sequence.back();

952 while (true) {

954

956 UnscheduleNodeBottomUp(OldSU);

958 if (OldSU == BtSU)

959 break;

961 }

962

963 assert(!SU->isSucc(OldSU) && "Something is wrong!");

964

965 RestoreHazardCheckerBottomUp();

966

967 ReleasePending();

968

969 ++NumBacktracks;

970}

971

973 for (const SDNode *SUNode = SU->getNode(); SUNode;

975 if (SUNode->isOperandOf(N))

976 return true;

977 }

978 return false;

979}

980

981

982SUnit *ScheduleDAGRRList::TryUnfoldSU(SUnit *SU) {

984

987 return nullptr;

988

989 assert(NewNodes.size() == 2 && "Expected a load folding node!");

990

991 N = NewNodes[1];

992 SDNode *LoadNode = NewNodes[0];

993 unsigned NumVals = N->getNumValues();

995

996

997

998

999 bool isNewLoad = true;

1000 SUnit *LoadSU;

1001 if (LoadNode->getNodeId() != -1) {

1002 LoadSU = &SUnits[LoadNode->getNodeId()];

1003

1004

1006 return SU;

1007 isNewLoad = false;

1008 } else {

1009 LoadSU = CreateNewSUnit(LoadNode);

1011

1012 InitNumRegDefsLeft(LoadSU);

1013 computeLatency(LoadSU);

1014 }

1015

1016 bool isNewN = true;

1017 SUnit *NewSU;

1018

1019 if (N->getNodeId() != -1) {

1020 NewSU = &SUnits[N->getNodeId()];

1021

1022

1024 return SU;

1025 }

1026 isNewN = false;

1027 } else {

1028 NewSU = CreateNewSUnit(N);

1029 N->setNodeId(NewSU->NodeNum);

1030

1031 const MCInstrDesc &MCID = TII->get(N->getMachineOpcode());

1032 for (unsigned i = 0; i != MCID.getNumOperands(); ++i) {

1035 break;

1036 }

1037 }

1040

1041 InitNumRegDefsLeft(NewSU);

1042 computeLatency(NewSU);

1043 }

1044

1046

1047

1048 for (unsigned i = 0; i != NumVals; ++i)

1050 DAG->ReplaceAllUsesOfValueWith(SDValue(SU->getNode(), OldNumVals - 1),

1052

1053

1059 for (SDep &Pred : SU->Preds) {

1064 else

1066 }

1067 for (SDep &Succ : SU->Succs) {

1070 else

1072 }

1073

1074

1075 for (const SDep &Pred : ChainPreds) {

1076 RemovePred(SU, Pred);

1077 if (isNewLoad)

1078 AddPredQueued(LoadSU, Pred);

1079 }

1080 for (const SDep &Pred : LoadPreds) {

1081 RemovePred(SU, Pred);

1082 if (isNewLoad)

1083 AddPredQueued(LoadSU, Pred);

1084 }

1085 for (const SDep &Pred : NodePreds) {

1086 RemovePred(SU, Pred);

1087 AddPredQueued(NewSU, Pred);

1088 }

1089 for (SDep &D : NodeSuccs) {

1090 SUnit *SuccDep = D.getSUnit();

1091 D.setSUnit(SU);

1092 RemovePred(SuccDep, D);

1093 D.setSUnit(NewSU);

1094 AddPredQueued(SuccDep, D);

1095

1099 }

1100 for (SDep &D : ChainSuccs) {

1101 SUnit *SuccDep = D.getSUnit();

1102 D.setSUnit(SU);

1103 RemovePred(SuccDep, D);

1104 if (isNewLoad) {

1105 D.setSUnit(LoadSU);

1106 AddPredQueued(SuccDep, D);

1107 }

1108 }

1109

1110

1111

1113 D.setLatency(LoadSU->Latency);

1114 AddPredQueued(NewSU, D);

1115

1116 if (isNewLoad)

1117 AvailableQueue->addNode(LoadSU);

1118 if (isNewN)

1119 AvailableQueue->addNode(NewSU);

1120

1121 ++NumUnfolds;

1122

1125

1126 return NewSU;

1127}

1128

1129

1130

1131SUnit *ScheduleDAGRRList::CopyAndMoveSuccessors(SUnit *SU) {

1133 if ()

1134 return nullptr;

1135

1136 LLVM_DEBUG(dbgs() << "Considering duplicating the SU\n");

1138

1139 if (N->getGluedNode() &&

1143 << "Giving up because it has incoming glue and the target does not "

1144 "want to copy it\n");

1145 return nullptr;

1146 }

1147

1148 SUnit *NewSU;

1149 bool TryUnfold = false;

1150 for (unsigned i = 0, e = N->getNumValues(); i != e; ++i) {

1151 MVT VT = N->getSimpleValueType(i);

1152 if (VT == MVT::Glue) {

1153 LLVM_DEBUG(dbgs() << "Giving up because it has outgoing glue\n");

1154 return nullptr;

1155 } else if (VT == MVT::Other)

1156 TryUnfold = true;

1157 }

1158 for (const SDValue &Op : N->op_values()) {

1159 MVT VT = Op.getNode()->getSimpleValueType(Op.getResNo());

1162 dbgs() << "Giving up because it one of the operands is glue and "

1163 "the target does not want to copy it\n");

1164 return nullptr;

1165 }

1166 }

1167

1168

1169 if (TryUnfold) {

1170 SUnit *UnfoldSU = TryUnfoldSU(SU);

1171 if (!UnfoldSU)

1172 return nullptr;

1173 SU = UnfoldSU;

1175

1177 return SU;

1178 }

1179

1181 NewSU = CreateClone(SU);

1182

1183

1184 for (SDep &Pred : SU->Preds)

1186 AddPredQueued(NewSU, Pred);

1187

1188

1189

1191

1192

1193

1195 for (SDep &Succ : SU->Succs) {

1197 continue;

1198 SUnit *SuccSU = Succ.getSUnit();

1200 SDep D = Succ;

1202 AddPredQueued(SuccSU, D);

1203 D.setSUnit(SU);

1205 }

1206 }

1207 for (const auto &[DelSU, DelD] : DelDeps)

1208 RemovePred(DelSU, DelD);

1209

1211 AvailableQueue->addNode(NewSU);

1212

1213 ++NumDups;

1214 return NewSU;

1215}

1216

1217

1218

1219void ScheduleDAGRRList::InsertCopiesAndMoveSuccs(SUnit *SU, unsigned Reg,

1220 const TargetRegisterClass *DestRC,

1221 const TargetRegisterClass *SrcRC,

1222 SmallVectorImpl<SUnit*> &Copies) {

1223 SUnit *CopyFromSU = CreateNewSUnit(nullptr);

1226

1227 SUnit *CopyToSU = CreateNewSUnit(nullptr);

1230

1231

1232

1234 for (SDep &Succ : SU->Succs) {

1236 continue;

1237 SUnit *SuccSU = Succ.getSUnit();

1239 SDep D = Succ;

1241 AddPredQueued(SuccSU, D);

1243 }

1244 else {

1245

1246

1247

1249 }

1250 }

1251 for (const auto &[DelSU, DelD] : DelDeps)

1252 RemovePred(DelSU, DelD);

1253

1255 FromDep.setLatency(SU->Latency);

1256 AddPredQueued(CopyFromSU, FromDep);

1257 SDep ToDep(CopyFromSU, SDep::Data, 0);

1258 ToDep.setLatency(CopyFromSU->Latency);

1259 AddPredQueued(CopyToSU, ToDep);

1260

1262 AvailableQueue->addNode(CopyFromSU);

1263 AvailableQueue->addNode(CopyToSU);

1264 Copies.push_back(CopyFromSU);

1265 Copies.push_back(CopyToSU);

1266

1267 ++NumPRCopies;

1268}

1269

1270

1271

1272

1275 unsigned NumRes;

1277

1278 NumRes = 1;

1279 } else {

1281 assert( MCID .implicit_defs().empty() &&

1282 "Physical reg def must be in implicit def list!");

1283 NumRes = MCID.getNumDefs();

1285 if (Reg == ImpDef)

1286 break;

1287 ++NumRes;

1288 }

1289 }

1290 return N->getSimpleValueType(NumRes);

1291}

1292

1293

1294

1301

1302

1303 if (!LiveRegDefs[*AliasI]) continue;

1304

1305

1306 if (LiveRegDefs[*AliasI] == SU) continue;

1307

1308

1310 continue;

1311

1312

1313 if (RegAdded.insert(*AliasI).second) {

1315 }

1316 }

1317}

1318

1319

1320

1325

1326 for (unsigned i = 1, e = LiveRegDefs.size()-1; i != e; ++i) {

1327 if (!LiveRegDefs[i]) continue;

1328 if (LiveRegDefs[i] == SU) continue;

1330 if (RegAdded.insert(i).second)

1332 }

1333}

1334

1335

1337 for (const SDValue &Op : N->op_values())

1339 return RegOp->getRegMask();

1340 return nullptr;

1341}

1342

1343

1344

1345

1346

1347bool ScheduleDAGRRList::

1348DelayForLiveRegsBottomUp(SUnit *SU, SmallVectorImpl &LRegs) {

1349 if (NumLiveRegs == 0)

1350 return false;

1351

1352 SmallSet<unsigned, 4> RegAdded;

1353

1354

1355

1356

1357 for (SDep &Pred : SU->Preds) {

1360 RegAdded, LRegs, TRI);

1361 }

1362

1363 for (SDNode *Node = SU->getNode(); Node; Node = Node->getGluedNode()) {

1364 if (Node->getOpcode() == ISD::INLINEASM ||

1365 Node->getOpcode() == ISD::INLINEASM_BR) {

1366

1367 unsigned NumOps = Node->getNumOperands();

1368 if (Node->getOperand(NumOps-1).getValueType() == MVT::Glue)

1369 --NumOps;

1370

1372 unsigned Flags = Node->getConstantOperandVal(i);

1373 const InlineAsm::Flag F(Flags);

1374 unsigned NumVals = F.getNumOperandRegisters();

1375

1376 ++i;

1377 if (F.isRegDefKind() || F.isRegDefEarlyClobberKind() ||

1378 F.isClobberKind()) {

1379

1380 for (; NumVals; --NumVals, ++i) {

1384 }

1385 } else

1386 i += NumVals;

1387 }

1388 continue;

1389 }

1390

1394 SDNode *SrcNode = Node->getOperand(2).getNode();

1396 SrcNode);

1397 }

1398 }

1399

1400 if ( Node ->isMachineOpcode())

1401 continue;

1402

1403

1404

1406

1407 unsigned CallResource = TRI->getNumRegs();

1408 if (LiveRegDefs[CallResource]) {

1409 SDNode *Gen = LiveRegGens[CallResource]->getNode();

1411 Gen = Glued;

1413 RegAdded.insert(CallResource).second)

1415 }

1416 }

1419 ArrayRef(LiveRegDefs.get(), TRI->getNumRegs()),

1420 RegAdded, LRegs);

1421

1422 const MCInstrDesc &MCID = TII->get(Node->getMachineOpcode());

1424

1425

1426

1427

1428 for (unsigned i = 0; i < MCID.getNumDefs(); ++i)

1429 if (MCID.operands()[i].isOptionalDef()) {

1433 }

1434 }

1437 }

1438

1439 return !LRegs.empty();

1440}

1441

1442void ScheduleDAGRRList::releaseInterferences(unsigned Reg) {

1443

1444 for (unsigned i = Interferences.size(); i > 0; --i) {

1445 SUnit *SU = Interferences[i-1];

1446 LRegsMapT::iterator LRegsPos = LRegsMap.find(SU);

1447 if (Reg) {

1448 SmallVectorImpl &LRegs = LRegsPos->second;

1450 continue;

1451 }

1453

1454

1455

1458 AvailableQueue->push(SU);

1459 }

1460 if (i < Interferences.size())

1461 Interferences[i-1] = Interferences.back();

1463 LRegsMap.erase(LRegsPos);

1464 }

1465}

1466

1467

1468

1469

1470

1471SUnit *ScheduleDAGRRList::PickNodeToScheduleBottomUp() {

1472 SUnit *CurSU = AvailableQueue->empty() ? nullptr : AvailableQueue->pop();

1473 auto FindAvailableNode = [&]() {

1474 while (CurSU) {

1475 SmallVector<unsigned, 4> LRegs;

1476 if (!DelayForLiveRegsBottomUp(CurSU, LRegs))

1477 break;

1479 if (LRegs[0] == TRI->getNumRegs()) dbgs() << "CallResource";

1481 dbgs() << " SU #" << CurSU->NodeNum << '\n');

1482 auto [LRegsIter, LRegsInserted] = LRegsMap.try_emplace(CurSU, LRegs);

1483 if (LRegsInserted) {

1484 CurSU->isPending = true;

1486 }

1487 else {

1488 assert(CurSU->isPending && "Interferences are pending");

1489

1490 LRegsIter->second = LRegs;

1491 }

1492 CurSU = AvailableQueue->pop();

1493 }

1494 };

1495 FindAvailableNode();

1496 if (CurSU)

1497 return CurSU;

1498

1499

1500

1501

1502

1503

1504

1505

1506

1507 for (SUnit *TrySU : Interferences) {

1508 SmallVectorImpl &LRegs = LRegsMap[TrySU];

1509

1510

1511

1512 SUnit *BtSU = nullptr;

1513 unsigned LiveCycle = std::numeric_limits::max();

1514 for (unsigned Reg : LRegs) {

1515 if (LiveRegGens[Reg]->getHeight() < LiveCycle) {

1516 BtSU = LiveRegGens[Reg];

1518 }

1519 }

1520 if (!WillCreateCycle(TrySU, BtSU)) {

1521

1522 BacktrackBottomUp(TrySU, BtSU);

1523

1524

1525

1529 AvailableQueue->remove(BtSU);

1530 }

1532 << ") to SU(" << TrySU->NodeNum << ")\n");

1534

1535

1536

1537 if (!TrySU->isAvailable || !TrySU->NodeQueueId) {

1538 LLVM_DEBUG(dbgs() << "TrySU not available; choosing node from queue\n");

1539 CurSU = AvailableQueue->pop();

1540 } else {

1542

1543 AvailableQueue->remove(TrySU);

1544 CurSU = TrySU;

1545 }

1546 FindAvailableNode();

1547

1548 break;

1549 }

1550 }

1551

1552 if (!CurSU) {

1553

1554

1555

1556

1557

1558 SUnit *TrySU = Interferences[0];

1559 SmallVectorImpl &LRegs = LRegsMap[TrySU];

1560 assert(LRegs.size() == 1 && "Can't handle this yet!");

1561 unsigned Reg = LRegs[0];

1562 SUnit *LRDef = LiveRegDefs[Reg];

1564 const TargetRegisterClass *RC =

1565 TRI->getMinimalPhysRegClass(Reg, VT);

1566 const TargetRegisterClass *DestRC = TRI->getCrossCopyRegClass(RC);

1567

1568

1569

1570

1571

1572

1573

1574

1575 SUnit *NewDef = nullptr;

1576 if (DestRC != RC) {

1577 NewDef = CopyAndMoveSuccessors(LRDef);

1578 if (!DestRC && !NewDef)

1579 report_fatal_error("Can't handle live physical register dependency!");

1580 }

1581 if (!NewDef) {

1582

1584 InsertCopiesAndMoveSuccs(LRDef, Reg, DestRC, RC, Copies);

1586 << " to SU #" << Copies.front()->NodeNum << "\n");

1588 NewDef = Copies.back();

1589 }

1590

1592 << " to SU #" << TrySU->NodeNum << "\n");

1593 LiveRegDefs[Reg] = NewDef;

1596 CurSU = NewDef;

1597 }

1598 assert(CurSU && "Unable to resolve live physical register dependencies!");

1599 return CurSU;

1600}

1601

1602

1603

1604void ScheduleDAGRRList::ListScheduleBottomUp() {

1605

1606 ReleasePredecessors(&ExitSU);

1607

1608

1609 if (!SUnits.empty()) {

1610 SUnit *RootSU = &SUnits[DAG->getRoot().getNode()->getNodeId()];

1611 assert(RootSU->Succs.empty() && "Graph root shouldn't have successors!");

1613 AvailableQueue->push(RootSU);

1614 }

1615

1616

1617

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

1619 while (!AvailableQueue->empty() || !Interferences.empty()) {

1621 AvailableQueue->dump(this));

1622

1623

1624

1625 SUnit *SU = PickNodeToScheduleBottomUp();

1626

1627 AdvancePastStalls(SU);

1628

1629 ScheduleNodeBottomUp(SU);

1630

1631 while (AvailableQueue->empty() && !PendingQueue.empty()) {

1632

1633 assert(MinAvailableCycle < std::numeric_limits::max() &&

1634 "MinAvailableCycle uninitialized");

1635 AdvanceToCycle(std::max(CurCycle + 1, MinAvailableCycle));

1636 }

1637 }

1638

1639

1641

1642#ifndef NDEBUG

1643 VerifyScheduledSequence(true);

1644#endif

1645}

1646

1647namespace {

1648

1649class RegReductionPQBase;

1650

1651struct queue_sort {

1652 bool isReady(SUnit* SU, unsigned CurCycle) const { return true; }

1653};

1654

1655#ifndef NDEBUG

1656template

1657struct reverse_sort : public queue_sort {

1658 SF &SortFunc;

1659

1660 reverse_sort(SF &sf) : SortFunc(sf) {}

1661

1662 bool operator()(SUnit* left, SUnit* right) const {

1663

1664

1665 return SortFunc(right, left);

1666 }

1667};

1668#endif

1669

1670

1671

1672struct bu_ls_rr_sort : public queue_sort {

1673 enum {

1674 IsBottomUp = true,

1675 HasReadyFilter = false

1676 };

1677

1678 RegReductionPQBase *SPQ;

1679

1680 bu_ls_rr_sort(RegReductionPQBase *spq) : SPQ(spq) {}

1681

1682 bool operator()(SUnit* left, SUnit* right) const;

1683};

1684

1685

1686struct src_ls_rr_sort : public queue_sort {

1687 enum {

1688 IsBottomUp = true,

1689 HasReadyFilter = false

1690 };

1691

1692 RegReductionPQBase *SPQ;

1693

1694 src_ls_rr_sort(RegReductionPQBase *spq) : SPQ(spq) {}

1695

1696 bool operator()(SUnit* left, SUnit* right) const;

1697};

1698

1699

1700struct hybrid_ls_rr_sort : public queue_sort {

1701 enum {

1702 IsBottomUp = true,

1703 HasReadyFilter = false

1704 };

1705

1706 RegReductionPQBase *SPQ;

1707

1708 hybrid_ls_rr_sort(RegReductionPQBase *spq) : SPQ(spq) {}

1709

1710 bool isReady(SUnit *SU, unsigned CurCycle) const;

1711

1712 bool operator()(SUnit* left, SUnit* right) const;

1713};

1714

1715

1716

1717struct ilp_ls_rr_sort : public queue_sort {

1718 enum {

1719 IsBottomUp = true,

1720 HasReadyFilter = false

1721 };

1722

1723 RegReductionPQBase *SPQ;

1724

1725 ilp_ls_rr_sort(RegReductionPQBase *spq) : SPQ(spq) {}

1726

1727 bool isReady(SUnit *SU, unsigned CurCycle) const;

1728

1729 bool operator()(SUnit* left, SUnit* right) const;

1730};

1731

1732class RegReductionPQBase : public SchedulingPriorityQueue {

1733protected:

1734 std::vector<SUnit *> Queue;

1735 unsigned CurQueueId = 0;

1736 bool TracksRegPressure;

1737 bool SrcOrder;

1738

1739

1740 std::vector *SUnits = nullptr;

1741

1742 MachineFunction &MF;

1743 const TargetInstrInfo *TII = nullptr;

1744 const TargetRegisterInfo *TRI = nullptr;

1745 const TargetLowering *TLI = nullptr;

1746 ScheduleDAGRRList *scheduleDAG = nullptr;

1747

1748

1749 std::vector SethiUllmanNumbers;

1750

1751

1752 std::vector RegPressure;

1753

1754

1755

1756 std::vector RegLimit;

1757

1758public:

1759 RegReductionPQBase(MachineFunction &mf,

1760 bool hasReadyFilter,

1761 bool tracksrp,

1762 bool srcorder,

1763 const TargetInstrInfo *tii,

1764 const TargetRegisterInfo *tri,

1765 const TargetLowering *tli)

1766 : SchedulingPriorityQueue(hasReadyFilter), TracksRegPressure(tracksrp),

1767 SrcOrder(srcorder), MF(mf), TII(tii), TRI(tri), TLI(tli) {

1768 if (TracksRegPressure) {

1769 unsigned NumRC = TRI->getNumRegClasses();

1770 RegLimit.resize(NumRC);

1774 for (const TargetRegisterClass *RC : TRI->regclasses())

1776 }

1777 }

1778

1779 void setScheduleDAG(ScheduleDAGRRList *scheduleDag) {

1780 scheduleDAG = scheduleDag;

1781 }

1782

1783 ScheduleHazardRecognizer* getHazardRec() {

1784 return scheduleDAG->getHazardRec();

1785 }

1786

1787 void initNodes(std::vector &sunits) override;

1788

1789 void addNode(const SUnit *SU) override;

1790

1791 void updateNode(const SUnit *SU) override;

1792

1793 void releaseState() override {

1794 SUnits = nullptr;

1795 SethiUllmanNumbers.clear();

1797 }

1798

1799 unsigned getNodePriority(const SUnit *SU) const;

1800

1801 unsigned getNodeOrdering(const SUnit *SU) const {

1802 if (!SU->getNode()) return 0;

1803

1805 }

1806

1807 bool empty() const override { return Queue.empty(); }

1808

1809 void push(SUnit *U) override {

1810 assert(->NodeQueueId && "Node in the queue already");

1811 U->NodeQueueId = ++CurQueueId;

1812 Queue.push_back(U);

1813 }

1814

1815 void remove(SUnit *SU) override {

1816 assert( Queue .empty() && "Queue is empty!");

1818 std::vector<SUnit *>::iterator I = llvm::find(Queue, SU);

1819 if (I != std::prev(Queue.end()))

1821 Queue.pop_back();

1823 }

1824

1825 bool tracksRegPressure() const override { return TracksRegPressure; }

1826

1827 void dumpRegPressure() const;

1828

1829 bool HighRegPressure(const SUnit *SU) const;

1830

1831 bool MayReduceRegPressure(SUnit *SU) const;

1832

1833 int RegPressureDiff(SUnit *SU, unsigned &LiveUses) const;

1834

1835 void scheduledNode(SUnit *SU) override;

1836

1837 void unscheduledNode(SUnit *SU) override;

1838

1839protected:

1840 bool canClobber(const SUnit *SU, const SUnit *Op);

1841 void AddPseudoTwoAddrDeps();

1842 void PrescheduleNodesWithMultipleUses();

1843 void CalculateSethiUllmanNumbers();

1844};

1845

1846template

1847static SUnit *popFromQueueImpl(std::vector<SUnit *> &Q, SF &Picker) {

1848 unsigned BestIdx = 0;

1849

1850

1851 for (unsigned I = 1, E = std::min(Q.size(), (decltype(Q.size()))1000); I != E;

1852 I++)

1853 if (Picker(Q[BestIdx], Q[I]))

1854 BestIdx = I;

1855 SUnit *V = Q[BestIdx];

1856 if (BestIdx + 1 != Q.size())

1857 std::swap(Q[BestIdx], Q.back());

1858 Q.pop_back();

1859 return V;

1860}

1861

1862template

1863SUnit *popFromQueue(std::vector<SUnit *> &Q, SF &Picker, ScheduleDAG *DAG) {

1864#ifndef NDEBUG

1866 reverse_sort RPicker(Picker);

1867 return popFromQueueImpl(Q, RPicker);

1868 }

1869#endif

1870 (void)DAG;

1871 return popFromQueueImpl(Q, Picker);

1872}

1873

1874

1875

1876

1877

1878

1879

1880

1881template

1882class RegReductionPriorityQueue : public RegReductionPQBase {

1883 SF Picker;

1884

1885public:

1886 RegReductionPriorityQueue(MachineFunction &mf,

1887 bool tracksrp,

1888 bool srcorder,

1889 const TargetInstrInfo *tii,

1890 const TargetRegisterInfo *tri,

1891 const TargetLowering *tli)

1892 : RegReductionPQBase(mf, SF::HasReadyFilter, tracksrp, srcorder,

1893 tii, tri, tli),

1894 Picker(this) {}

1895

1896 bool isBottomUp() const override { return SF::IsBottomUp; }

1897

1898 bool isReady(SUnit *U) const override {

1899 return Picker.HasReadyFilter && Picker.isReady(U, getCurCycle());

1900 }

1901

1902 SUnit *pop() override {

1903 if (Queue.empty()) return nullptr;

1904

1905 SUnit *V = popFromQueue(Queue, Picker, scheduleDAG);

1906 V->NodeQueueId = 0;

1907 return V;

1908 }

1909

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

1912

1913 std::vector<SUnit *> DumpQueue = Queue;

1914 SF DumpPicker = Picker;

1915 while (!DumpQueue.empty()) {

1916 SUnit *SU = popFromQueue(DumpQueue, DumpPicker, scheduleDAG);

1919 }

1920 }

1921#endif

1922};

1923

1924using BURegReductionPriorityQueue = RegReductionPriorityQueue<bu_ls_rr_sort>;

1925using SrcRegReductionPriorityQueue = RegReductionPriorityQueue<src_ls_rr_sort>;

1926using HybridBURRPriorityQueue = RegReductionPriorityQueue<hybrid_ls_rr_sort>;

1927using ILPBURRPriorityQueue = RegReductionPriorityQueue<ilp_ls_rr_sort>;

1928

1929}

1930

1931

1932

1933

1934

1935

1936

1937

1938

1939

1940

1944 if (LSchedLow != RSchedLow)

1945 return LSchedLow < RSchedLow ? 1 : -1;

1946 return 0;

1947}

1948

1949

1950

1951static unsigned

1953 if (SUNumbers[SU->NodeNum] != 0)

1954 return SUNumbers[SU->NodeNum];

1955

1956

1957 struct WorkState {

1958 WorkState(const SUnit *SU) : SU(SU) {}

1959 const SUnit *SU;

1960 unsigned PredsProcessed = 0;

1961 };

1962

1965 while (!WorkList.empty()) {

1966 auto &Temp = WorkList.back();

1967 auto *TempSU = Temp.SU;

1968 bool AllPredsKnown = true;

1969

1970 for (unsigned P = Temp.PredsProcessed; P < TempSU->Preds.size(); ++P) {

1971 auto &Pred = TempSU->Preds[P];

1972 if (Pred.isCtrl()) continue;

1973 SUnit *PredSU = Pred.getSUnit();

1974 if (SUNumbers[PredSU->NodeNum] == 0) {

1975#ifndef NDEBUG

1976

1977 for (auto It : WorkList)

1978 assert(It.SU != PredSU && "Trying to push an element twice?");

1979#endif

1980

1981 Temp.PredsProcessed = P + 1;

1982 WorkList.push_back(PredSU);

1983 AllPredsKnown = false;

1984 break;

1985 }

1986 }

1987

1988 if (!AllPredsKnown)

1989 continue;

1990

1991

1992 unsigned SethiUllmanNumber = 0;

1993 unsigned Extra = 0;

1994 for (const SDep &Pred : TempSU->Preds) {

1995 if (Pred.isCtrl()) continue;

1996 SUnit *PredSU = Pred.getSUnit();

1997 unsigned PredSethiUllman = SUNumbers[PredSU->NodeNum];

1998 assert(PredSethiUllman > 0 && "We should have evaluated this pred!");

1999 if (PredSethiUllman > SethiUllmanNumber) {

2000 SethiUllmanNumber = PredSethiUllman;

2001 Extra = 0;

2002 } else if (PredSethiUllman == SethiUllmanNumber)

2003 ++Extra;

2004 }

2005

2006 SethiUllmanNumber += Extra;

2007 if (SethiUllmanNumber == 0)

2008 SethiUllmanNumber = 1;

2009 SUNumbers[TempSU->NodeNum] = SethiUllmanNumber;

2011 }

2012

2013 assert(SUNumbers[SU->NodeNum] > 0 && "SethiUllman should never be zero!");

2014 return SUNumbers[SU->NodeNum];

2015}

2016

2017

2018

2019void RegReductionPQBase::CalculateSethiUllmanNumbers() {

2020 SethiUllmanNumbers.assign(SUnits->size(), 0);

2021

2022 for (const SUnit &SU : *SUnits)

2024}

2025

2026void RegReductionPQBase::addNode(const SUnit *SU) {

2027 unsigned SUSize = SethiUllmanNumbers.size();

2028 if (SUnits->size() > SUSize)

2029 SethiUllmanNumbers.resize(SUSize*2, 0);

2031}

2032

2033void RegReductionPQBase::updateNode(const SUnit *SU) {

2034 SethiUllmanNumbers[SU->NodeNum] = 0;

2036}

2037

2038

2039

2040unsigned RegReductionPQBase::getNodePriority(const SUnit *SU) const {

2041 assert(SU->NodeNum < SethiUllmanNumbers.size());

2044

2045

2046 return 0;

2047 if (Opc == TargetOpcode::EXTRACT_SUBREG ||

2048 Opc == TargetOpcode::SUBREG_TO_REG ||

2049 Opc == TargetOpcode::INSERT_SUBREG)

2050

2051

2052 return 0;

2054

2055

2056

2057

2058

2059 return 0xffff;

2061

2062

2063 return 0;

2064#if 1

2065 return SethiUllmanNumbers[SU->NodeNum];

2066#else

2067 unsigned Priority = SethiUllmanNumbers[SU->NodeNum];

2069

2071 return (NP > 0) ? NP : 0;

2072 }

2073 return Priority;

2074#endif

2075}

2076

2077

2078

2079

2080

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

2082LLVM_DUMP_METHOD void RegReductionPQBase::dumpRegPressure() const {

2083 for (const TargetRegisterClass *RC : TRI->regclasses()) {

2084 unsigned Id = RC->getID();

2086 if (!RP) continue;

2087 LLVM_DEBUG(dbgs() << TRI->getRegClassName(RC) << ": " << RP << " / "

2088 << RegLimit[Id] << '\n');

2089 }

2090}

2091#endif

2092

2093bool RegReductionPQBase::HighRegPressure(const SUnit *SU) const {

2094 if (!TLI)

2095 return false;

2096

2097 for (const SDep &Pred : SU->Preds) {

2099 continue;

2100 SUnit *PredSU = Pred.getSUnit();

2101

2102

2104 continue;

2105 }

2106 for (ScheduleDAGSDNodes::RegDefIter RegDefPos(PredSU, scheduleDAG);

2107 RegDefPos.IsValid(); RegDefPos.Advance()) {

2108 unsigned RCId, Cost;

2110

2111 if ((RegPressure[RCId] + Cost) >= RegLimit[RCId])

2112 return true;

2113 }

2114 }

2115 return false;

2116}

2117

2118bool RegReductionPQBase::MayReduceRegPressure(SUnit *SU) const {

2119 const SDNode *N = SU->getNode();

2120

2121 if (->isMachineOpcode() || !SU->NumSuccs)

2122 return false;

2123

2124 unsigned NumDefs = TII->get(N->getMachineOpcode()).getNumDefs();

2125 for (unsigned i = 0; i != NumDefs; ++i) {

2126 MVT VT = N->getSimpleValueType(i);

2127 if (->hasAnyUseOfValue(i))

2128 continue;

2130 if (RegPressure[RCId] >= RegLimit[RCId])

2131 return true;

2132 }

2133 return false;

2134}

2135

2136

2137

2138

2139

2140

2141

2142

2143int RegReductionPQBase::RegPressureDiff(SUnit *SU, unsigned &LiveUses) const {

2144 LiveUses = 0;

2145 int PDiff = 0;

2146 for (const SDep &Pred : SU->Preds) {

2148 continue;

2149 SUnit *PredSU = Pred.getSUnit();

2150

2151

2154 ++LiveUses;

2155 continue;

2156 }

2157 for (ScheduleDAGSDNodes::RegDefIter RegDefPos(PredSU, scheduleDAG);

2158 RegDefPos.IsValid(); RegDefPos.Advance()) {

2159 MVT VT = RegDefPos.GetValue();

2161 if (RegPressure[RCId] >= RegLimit[RCId])

2162 ++PDiff;

2163 }

2164 }

2165 const SDNode *N = SU->getNode();

2166

2167 if ( || ->isMachineOpcode() || !SU->NumSuccs)

2168 return PDiff;

2169

2170 unsigned NumDefs = TII->get(N->getMachineOpcode()).getNumDefs();

2171 for (unsigned i = 0; i != NumDefs; ++i) {

2172 MVT VT = N->getSimpleValueType(i);

2173 if (->hasAnyUseOfValue(i))

2174 continue;

2176 if (RegPressure[RCId] >= RegLimit[RCId])

2177 --PDiff;

2178 }

2179 return PDiff;

2180}

2181

2182void RegReductionPQBase::scheduledNode(SUnit *SU) {

2183 if (!TracksRegPressure)

2184 return;

2185

2187 return;

2188

2189 for (const SDep &Pred : SU->Preds) {

2191 continue;

2192 SUnit *PredSU = Pred.getSUnit();

2193

2194

2196 continue;

2197 }

2198

2199

2200

2201

2202

2203

2204

2205

2206

2207

2208

2209

2210

2211

2212

2215 for (ScheduleDAGSDNodes::RegDefIter RegDefPos(PredSU, scheduleDAG);

2216 RegDefPos.IsValid(); RegDefPos.Advance(), --SkipRegDefs) {

2217 if (SkipRegDefs)

2218 continue;

2219

2220 unsigned RCId, Cost;

2223 break;

2224 }

2225 }

2226

2227

2228

2229

2231 for (ScheduleDAGSDNodes::RegDefIter RegDefPos(SU, scheduleDAG);

2232 RegDefPos.IsValid(); RegDefPos.Advance(), --SkipRegDefs) {

2233 if (SkipRegDefs > 0)

2234 continue;

2235 unsigned RCId, Cost;

2237 if (RegPressure[RCId] < Cost) {

2238

2239

2241 << ") has too many regdefs\n");

2243 }

2244 else {

2246 }

2247 }

2249}

2250

2251void RegReductionPQBase::unscheduledNode(SUnit *SU) {

2252 if (!TracksRegPressure)

2253 return;

2254

2255 const SDNode *N = SU->getNode();

2256 if () return;

2257

2258 if (->isMachineOpcode()) {

2260 return;

2261 } else {

2262 unsigned Opc = N->getMachineOpcode();

2263 if (Opc == TargetOpcode::EXTRACT_SUBREG ||

2264 Opc == TargetOpcode::INSERT_SUBREG ||

2265 Opc == TargetOpcode::SUBREG_TO_REG ||

2266 Opc == TargetOpcode::REG_SEQUENCE ||

2267 Opc == TargetOpcode::IMPLICIT_DEF)

2268 return;

2269 }

2270

2271 for (const SDep &Pred : SU->Preds) {

2273 continue;

2274 SUnit *PredSU = Pred.getSUnit();

2275

2276

2278 continue;

2279 const SDNode *PN = PredSU->getNode();

2285 }

2286 continue;

2287 }

2289 if (POpc == TargetOpcode::IMPLICIT_DEF)

2290 continue;

2291 if (POpc == TargetOpcode::EXTRACT_SUBREG ||

2292 POpc == TargetOpcode::INSERT_SUBREG ||

2293 POpc == TargetOpcode::SUBREG_TO_REG) {

2297 continue;

2298 }

2299 if (POpc == TargetOpcode::REG_SEQUENCE) {

2301 const TargetRegisterClass *RC = TRI->getRegClass(DstRCIdx);

2302 unsigned RCId = RC->getID();

2303

2304

2306 continue;

2307 }

2309 for (unsigned i = 0; i != NumDefs; ++i) {

2312 continue;

2315

2317 else

2319 }

2320 }

2321

2322

2323

2324 if (SU->NumSuccs && N->isMachineOpcode()) {

2325 unsigned NumDefs = TII->get(N->getMachineOpcode()).getNumDefs();

2326 for (unsigned i = NumDefs, e = N->getNumValues(); i != e; ++i) {

2327 MVT VT = N->getSimpleValueType(i);

2328 if (VT == MVT::Glue || VT == MVT::Other)

2329 continue;

2330 if (->hasAnyUseOfValue(i))

2331 continue;

2334 }

2335 }

2336

2338}

2339

2340

2341

2342

2343

2344

2345

2347 unsigned MaxHeight = 0;

2348 for (const SDep &Succ : SU->Succs) {

2349 if (Succ.isCtrl()) continue;

2351

2352

2356 if (Height > MaxHeight)

2357 MaxHeight = Height;

2358 }

2359 return MaxHeight;

2360}

2361

2362

2363

2365 unsigned Scratches = 0;

2366 for (const SDep &Pred : SU->Preds) {

2367 if (Pred.isCtrl()) continue;

2368 Scratches++;

2369 }

2370 return Scratches;

2371}

2372

2373

2374

2376 bool RetVal = false;

2377 for (const SDep &Pred : SU->Preds) {

2378 if (Pred.isCtrl()) continue;

2379 const SUnit *PredSU = Pred.getSUnit();

2380 if (PredSU->getNode() &&

2384 if (Reg.isVirtual()) {

2385 RetVal = true;

2386 continue;

2387 }

2388 }

2389 return false;

2390 }

2391 return RetVal;

2392}

2393

2394

2395

2396

2398 bool RetVal = false;

2399 for (const SDep &Succ : SU->Succs) {

2400 if (Succ.isCtrl()) continue;

2405 if (Reg.isVirtual()) {

2406 RetVal = true;

2407 continue;

2408 }

2409 }

2410 return false;

2411 }

2412 return RetVal;

2413}

2414

2415

2416

2417

2418

2419

2420

2421

2422

2423

2424

2427 return;

2428

2430 return;

2431

2433

2435

2436 for (const SDep &Pred : SU->Preds) {

2437 if (Pred.isCtrl()) continue;

2438 Pred.getSUnit()->isVRegCycle = true;

2439 }

2440}

2441

2442

2443

2446 return;

2447

2448 for (const SDep &Pred : SU->Preds) {

2449 if (Pred.isCtrl()) continue;

2450 SUnit *PredSU = Pred.getSUnit();

2453 "VRegCycle def must be CopyFromReg");

2454 Pred.getSUnit()->isVRegCycle = false;

2455 }

2456 }

2457}

2458

2459

2460

2462

2464 return false;

2465

2466 for (const SDep &Pred : SU->Preds) {

2467 if (Pred.isCtrl()) continue;

2468 if (Pred.getSUnit()->isVRegCycle &&

2469 Pred.getSUnit()->getNode()->getOpcode() == ISD::CopyFromReg) {

2471 return true;

2472 }

2473 }

2474 return false;

2475}

2476

2477

2478

2479

2481 if ((int)SPQ->getCurCycle() < Height) return true;

2482 if (SPQ->getHazardRec()->getHazardType(SU, 0)

2484 return true;

2485 return false;

2486}

2487

2488

2489

2491 RegReductionPQBase *SPQ) {

2492

2493

2496 int LHeight = (int)left->getHeight() + LPenalty;

2497 int RHeight = (int)right->getHeight() + RPenalty;

2498

2503

2504

2505

2506

2507 if (LStall) {

2508 if (!RStall)

2509 return 1;

2510 if (LHeight != RHeight)

2511 return LHeight > RHeight ? 1 : -1;

2512 } else if (RStall)

2513 return -1;

2514

2515

2516

2519

2520

2521

2522

2523 if (!SPQ->getHazardRec()->isEnabled()) {

2524 if (LHeight != RHeight)

2525 return LHeight > RHeight ? 1 : -1;

2526 }

2527 int LDepth = left->getDepth() - LPenalty;

2528 int RDepth = right->getDepth() - RPenalty;

2529 if (LDepth != RDepth) {

2531 << ") depth " << LDepth << " vs SU (" << right->NodeNum

2532 << ") depth " << RDepth << "\n");

2533 return LDepth < RDepth ? 1 : -1;

2534 }

2537 }

2538 return 0;

2539}

2540

2542

2543

2544

2545

2549 if (LHasPhysReg != RHasPhysReg) {

2550 #ifndef NDEBUG

2551 static const char *const PhysRegMsg[] = { " has no physreg",

2552 " defines a physreg" };

2553 #endif

2555 << PhysRegMsg[LHasPhysReg] << " SU(" << right->NodeNum

2556 << ") " << PhysRegMsg[RHasPhysReg] << "\n");

2557 return LHasPhysReg < RHasPhysReg;

2558 }

2559 }

2560

2561

2562 unsigned LPriority = SPQ->getNodePriority(left);

2563 unsigned RPriority = SPQ->getNodePriority(right);

2564

2565

2566

2569 RPriority = (RPriority > RNumVals) ? (RPriority - RNumVals) : 0;

2570 }

2573 LPriority = (LPriority > LNumVals) ? (LPriority - LNumVals) : 0;

2574 }

2575

2576 if (LPriority != RPriority)

2577 return LPriority > RPriority;

2578

2579

2580

2582 unsigned LOrder = SPQ->getNodeOrdering(left);

2583 unsigned ROrder = SPQ->getNodeOrdering(right);

2584

2585

2586

2587 if ((LOrder || ROrder) && LOrder != ROrder)

2588 return LOrder != 0 && (LOrder < ROrder || ROrder == 0);

2589 }

2590

2591

2592

2593

2594

2595

2596

2597

2598

2599

2600

2601

2602

2603

2604

2605

2606

2607

2610 if (LDist != RDist)

2611 return LDist < RDist;

2612

2613

2616 if (LScratch != RScratch)

2617 return LScratch > RScratch;

2618

2619

2620

2621 if ((left->isCall && RPriority > 0) || (right->isCall && LPriority > 0))

2623

2624

2627 int result = BUCompareLatency(left, right, false , SPQ);

2628 if (result != 0)

2629 return result > 0;

2630 }

2631 else {

2634

2637 }

2638

2640 "NodeQueueId cannot be zero");

2642}

2643

2644

2645bool bu_ls_rr_sort::operator()(SUnit *left, SUnit *right) const {

2647 return res > 0;

2648

2649 return BURRSort(left, right, SPQ);

2650}

2651

2652

2653bool src_ls_rr_sort::operator()(SUnit *left, SUnit *right) const {

2655 return res > 0;

2656

2657 unsigned LOrder = SPQ->getNodeOrdering(left);

2658 unsigned ROrder = SPQ->getNodeOrdering(right);

2659

2660

2661

2662 if ((LOrder || ROrder) && LOrder != ROrder)

2663 return LOrder != 0 && (LOrder < ROrder || ROrder == 0);

2664

2665 return BURRSort(left, right, SPQ);

2666}

2667

2668

2669

2670

2671

2672bool hybrid_ls_rr_sort::isReady(SUnit *SU, unsigned CurCycle) const {

2673 static const unsigned ReadyDelay = 3;

2674

2675 if (SPQ->MayReduceRegPressure(SU)) return true;

2676

2677 if (SU->getHeight() > (CurCycle + ReadyDelay)) return false;

2678

2679 if (SPQ->getHazardRec()->getHazardType(SU, -ReadyDelay)

2681 return false;

2682

2683 return true;

2684}

2685

2686

2687bool hybrid_ls_rr_sort::operator()(SUnit *left, SUnit *right) const {

2689 return res > 0;

2690

2692

2693 return BURRSort(left, right, SPQ);

2694

2695 bool LHigh = SPQ->HighRegPressure(left);

2696 bool RHigh = SPQ->HighRegPressure(right);

2697

2698

2699 if (LHigh && !RHigh) {

2701 << right->NodeNum << ")\n");

2702 return true;

2703 }

2704 else if (!LHigh && RHigh) {

2706 << left->NodeNum << ")\n");

2707 return false;

2708 }

2709 if (!LHigh && !RHigh) {

2710 int result = BUCompareLatency(left, right, true , SPQ);

2711 if (result != 0)

2712 return result > 0;

2713 }

2714 return BURRSort(left, right, SPQ);

2715}

2716

2717

2718

2719bool ilp_ls_rr_sort::isReady(SUnit *SU, unsigned CurCycle) const {

2720 if (SU->getHeight() > CurCycle) return false;

2721

2722 if (SPQ->getHazardRec()->getHazardType(SU, 0)

2724 return false;

2725

2726 return true;

2727}

2728

2732

2733

2734 return true;

2735

2736 if (Opc == TargetOpcode::EXTRACT_SUBREG ||

2737 Opc == TargetOpcode::SUBREG_TO_REG ||

2738 Opc == TargetOpcode::INSERT_SUBREG)

2739

2740

2741 return true;

2742

2744

2745

2746 return true;

2747

2748 return false;

2749}

2750

2751

2752

2753bool ilp_ls_rr_sort::operator()(SUnit *left, SUnit *right) const {

2755 return res > 0;

2756

2758

2759 return BURRSort(left, right, SPQ);

2760

2761 unsigned LLiveUses = 0, RLiveUses = 0;

2762 int LPDiff = 0, RPDiff = 0;

2764 LPDiff = SPQ->RegPressureDiff(left, LLiveUses);

2765 RPDiff = SPQ->RegPressureDiff(right, RLiveUses);

2766 }

2769 << "): " << LPDiff << " != SU(" << right->NodeNum

2770 << "): " << RPDiff << "\n");

2771 return LPDiff > RPDiff;

2772 }

2773

2777 if (LReduce && !RReduce) return false;

2778 if (RReduce && !LReduce) return true;

2779 }

2780

2783 << " != SU(" << right->NodeNum << "): " << RLiveUses

2784 << "\n");

2785 return LLiveUses < RLiveUses;

2786 }

2787

2791 if (LStall != RStall)

2793 }

2794

2796 int spread = (int)left->getDepth() - (int)right->getDepth();

2800 << "): " << right->getDepth() << "\n");

2802 }

2803 }

2804

2809 }

2810

2811 return BURRSort(left, right, SPQ);

2812}

2813

2814void RegReductionPQBase::initNodes(std::vector &sunits) {

2815 SUnits = &sunits;

2816

2818 AddPseudoTwoAddrDeps();

2819

2820 if (!TracksRegPressure && !SrcOrder)

2821 PrescheduleNodesWithMultipleUses();

2822

2823 CalculateSethiUllmanNumbers();

2824

2825

2826 if (scheduleDAG->BB->isSuccessor(scheduleDAG->BB))

2827 for (SUnit &SU : sunits)

2829}

2830

2831

2832

2833

2834

2835bool RegReductionPQBase::canClobber(const SUnit *SU, const SUnit *Op) {

2838 const MCInstrDesc &MCID = TII->get(Opc);

2839 unsigned NumRes = MCID.getNumDefs();

2841 for (unsigned i = 0; i != NumOps; ++i) {

2845 Op->OrigNode == &(*SUnits)[DU->getNodeId()])

2846 return true;

2847 }

2848 }

2849 }

2850 return false;

2851}

2852

2853

2854

2855

2857 ScheduleDAGRRList *scheduleDAG,

2863 if (ImpDefs.empty() && !RegMask)

2864 return false;

2865

2866 for (const SDep &Succ : SU->Succs) {

2868 for (const SDep &SuccPred : SuccSU->Preds) {

2870 continue;

2871

2872 if (RegMask &&

2874 scheduleDAG->IsReachable(DepSU, SuccPred.getSUnit()))

2875 return true;

2876

2877 for (MCPhysReg ImpDef : ImpDefs) {

2878

2879

2880

2881 if (TRI->regsOverlap(ImpDef, SuccPred.getReg()) &&

2882 scheduleDAG->IsReachable(DepSU, SuccPred.getSUnit()))

2883 return true;

2884 }

2885 }

2886 }

2887 return false;

2888}

2889

2890

2891

2896 unsigned NumDefs = TII->get(N->getMachineOpcode()).getNumDefs();

2898 assert(!ImpDefs.empty() && "Caller should check hasPhysRegDefs");

2899 for (const SDNode *SUNode = SU->getNode(); SUNode;

2901 if (!SUNode->isMachineOpcode())

2902 continue;

2904 TII->get(SUNode->getMachineOpcode()).implicit_defs();

2906 if (SUImpDefs.empty() && !SURegMask)

2907 continue;

2908 for (unsigned i = NumDefs, e = N->getNumValues(); i != e; ++i) {

2909 MVT VT = N->getSimpleValueType(i);

2910 if (VT == MVT::Glue || VT == MVT::Other)

2911 continue;

2912 if (->hasAnyUseOfValue(i))

2913 continue;

2916 return true;

2917 for (MCPhysReg SUReg : SUImpDefs) {

2918 if (TRI->regsOverlap(Reg, SUReg))

2919 return true;

2920 }

2921 }

2922 }

2923 return false;

2924}

2925

2926

2927

2928

2929

2930

2931

2932

2933

2934

2935

2936

2937

2938

2939

2940

2941

2942

2943

2944

2945

2946

2947

2948

2949

2950

2951

2952

2953

2954

2955

2956void RegReductionPQBase::PrescheduleNodesWithMultipleUses() {

2957

2958 for (SUnit &SU : *SUnits) {

2959

2960

2961

2963 continue;

2964

2966 continue;

2967

2968

2969 if (SDNode *N = SU.getNode())

2972 continue;

2973

2974 SDNode *PredFrameSetup = nullptr;

2975 for (const SDep &Pred : SU.Preds)

2977

2979

2980

2981

2982

2983

2984

2985

2986

2989 PredFrameSetup = PredND;

2990 break;

2991 }

2992 }

2993

2994 if (PredFrameSetup != nullptr)

2995 continue;

2996

2997

2998 SUnit *PredSU = nullptr;

2999 for (const SDep &Pred : SU.Preds)

3000 if (!Pred.isCtrl()) {

3002 break;

3003 }

3005

3006

3007

3009 continue;

3010

3012 continue;

3013

3014

3015 if (SDNode *N = SU.getNode())

3018 continue;

3019

3020

3021 for (const SDep &PredSucc : PredSU->Succs) {

3022 SUnit *PredSuccSU = PredSucc.getSUnit();

3023 if (PredSuccSU == &SU) continue;

3024

3025

3026 if (PredSuccSU->NumSuccs == 0)

3027 goto outer_loop_continue;

3028

3031 goto outer_loop_continue;

3032

3033 if (scheduleDAG->IsReachable(&SU, PredSuccSU))

3034 goto outer_loop_continue;

3035 }

3036

3037

3038

3040 dbgs() << " Prescheduling SU #" << SU.NodeNum << " next to PredSU #"

3042 << " to guide scheduling in the presence of multiple uses\n");

3043 for (unsigned i = 0; i != PredSU->Succs.size(); ++i) {

3046 SUnit *SuccSU = Edge.getSUnit();

3047 if (SuccSU != &SU) {

3048 Edge.setSUnit(PredSU);

3049 scheduleDAG->RemovePred(SuccSU, Edge);

3050 scheduleDAG->AddPredQueued(&SU, Edge);

3051 Edge.setSUnit(&SU);

3052 scheduleDAG->AddPredQueued(SuccSU, Edge);

3053 --i;

3054 }

3055 }

3056 outer_loop_continue:;

3057 }

3058}

3059

3060

3061

3062

3063

3064

3065

3066

3067void RegReductionPQBase::AddPseudoTwoAddrDeps() {

3068 for (SUnit &SU : *SUnits) {

3070 continue;

3071

3074 continue;

3075

3077 unsigned Opc = Node->getMachineOpcode();

3078 const MCInstrDesc &MCID = TII->get(Opc);

3079 unsigned NumRes = MCID.getNumDefs();

3081 for (unsigned j = 0; j != NumOps; ++j) {

3083 continue;

3086 continue;

3087 const SUnit *DUSU = &(*SUnits)[DU->getNodeId()];

3088 if (!DUSU)

3089 continue;

3090 for (const SDep &Succ : DUSU->Succs) {

3092 continue;

3093 SUnit *SuccSU = Succ.getSUnit();

3094 if (SuccSU == &SU)

3095 continue;

3096

3097

3100 continue;

3101

3102

3103

3104

3105 while (SuccSU->Succs.size() == 1 &&

3108 TargetOpcode::COPY_TO_REGCLASS)

3109 SuccSU = SuccSU->Succs.front().getSUnit();

3110

3112 continue;

3113

3114

3117 continue;

3118 }

3119

3120

3122 if (SuccOpc == TargetOpcode::EXTRACT_SUBREG ||

3123 SuccOpc == TargetOpcode::INSERT_SUBREG ||

3124 SuccOpc == TargetOpcode::SUBREG_TO_REG)

3125 continue;

3127 (!canClobber(SuccSU, DUSU) ||

3130 !scheduleDAG->IsReachable(SuccSU, &SU)) {

3132 << " Adding a pseudo-two-addr edge from SU #"

3133 << SU.NodeNum << " to SU #" << SuccSU->NodeNum << "\n");

3134 scheduleDAG->AddPredQueued(&SU, SDep(SuccSU, SDep::Artificial));

3135 }

3136 }

3137 }

3138 }

3139}

3140

3141

3142

3143

3144

3150

3151 BURegReductionPriorityQueue *PQ =

3152 new BURegReductionPriorityQueue(*IS->MF, false, false, TII, TRI, nullptr);

3153 ScheduleDAGRRList *SD = new ScheduleDAGRRList(*IS->MF, false, PQ, OptLevel);

3154 PQ->setScheduleDAG(SD);

3155 return SD;

3156}

3157

3164

3165 SrcRegReductionPriorityQueue *PQ =

3166 new SrcRegReductionPriorityQueue(*IS->MF, false, true, TII, TRI, nullptr);

3167 ScheduleDAGRRList *SD = new ScheduleDAGRRList(*IS->MF, false, PQ, OptLevel);

3168 PQ->setScheduleDAG(SD);

3169 return SD;

3170}

3171

3179

3180 HybridBURRPriorityQueue *PQ =

3181 new HybridBURRPriorityQueue(*IS->MF, true, false, TII, TRI, TLI);

3182

3183 ScheduleDAGRRList *SD = new ScheduleDAGRRList(*IS->MF, true, PQ, OptLevel);

3184 PQ->setScheduleDAG(SD);

3185 return SD;

3186}

3187

3194

3195 ILPBURRPriorityQueue *PQ =

3196 new ILPBURRPriorityQueue(*IS->MF, true, false, TII, TRI, TLI);

3197 ScheduleDAGRRList *SD = new ScheduleDAGRRList(*IS->MF, true, PQ, OptLevel);

3198 PQ->setScheduleDAG(SD);

3199 return SD;

3200}

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

const TargetInstrInfo & TII

static msgpack::DocNode getNode(msgpack::DocNode DN, msgpack::Type Type, MCValue Val)

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

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.

This file defines the DenseMap class.

const size_t AbstractManglingParser< Derived, Alloc >::NumOps

Promote Memory to Register

static bool isLiveOut(const MachineBasicBlock &MBB, unsigned Reg)

std::pair< BasicBlock *, BasicBlock * > Edge

static MVT getPhysicalRegisterVT(SDNode *N, unsigned Reg, const TargetInstrInfo *TII)

getPhysicalRegisterVT - Returns the ValueType of the physical register definition of the specified no...

static bool CheckForLiveRegDef(SUnit *SU, MCRegister Reg, std::vector< SUnit * > &LiveRegDefs, SmallSet< unsigned, 4 > &RegAdded, SmallVectorImpl< unsigned > &LRegs, const TargetRegisterInfo *TRI, const SDNode *Node=nullptr)

CheckForLiveRegDef - Return true and update live register vector if the specified register def of the...

static bool canEnableCoalescing(SUnit *SU)

Definition ScheduleDAGRRList.cpp:2729

static RegisterScheduler sourceListDAGScheduler("source", "Similar to list-burr but schedules in source " "order when possible", createSourceListDAGScheduler)

static cl::opt< bool > DisableSchedCycles("disable-sched-cycles", cl::Hidden, cl::init(false), cl::desc("Disable cycle-level precision during preRA scheduling"))

static cl::opt< bool > DisableSchedStalls("disable-sched-stalls", cl::Hidden, cl::init(true), cl::desc("Disable no-stall priority in sched=list-ilp"))

static bool hasOnlyLiveInOpers(const SUnit *SU)

hasOnlyLiveInOpers - Return true if SU has only value predecessors that are CopyFromReg from a virtua...

Definition ScheduleDAGRRList.cpp:2375

static bool IsChainDependent(SDNode *Outer, SDNode *Inner, unsigned NestLevel, const TargetInstrInfo *TII)

IsChainDependent - Test if Outer is reachable from Inner through chain dependencies.

Definition ScheduleDAGRRList.cpp:442

static bool hasOnlyLiveOutUses(const SUnit *SU)

hasOnlyLiveOutUses - Return true if SU has only value successors that are CopyToReg to a virtual regi...

Definition ScheduleDAGRRList.cpp:2397

static cl::opt< bool > DisableSchedCriticalPath("disable-sched-critical-path", cl::Hidden, cl::init(false), cl::desc("Disable critical path priority in sched=list-ilp"))

static cl::opt< bool > Disable2AddrHack("disable-2addr-hack", cl::Hidden, cl::init(true), cl::desc("Disable scheduler's two-address hack"))

static RegisterScheduler ILPListDAGScheduler("list-ilp", "Bottom-up register pressure aware list scheduling " "which tries to balance ILP and register pressure", createILPListDAGScheduler)

static void resetVRegCycle(SUnit *SU)

Definition ScheduleDAGRRList.cpp:2444

static RegisterScheduler hybridListDAGScheduler("list-hybrid", "Bottom-up register pressure aware list scheduling " "which tries to balance latency and register pressure", createHybridListDAGScheduler)

static bool canClobberReachingPhysRegUse(const SUnit *DepSU, const SUnit *SU, ScheduleDAGRRList *scheduleDAG, const TargetInstrInfo *TII, const TargetRegisterInfo *TRI)

canClobberReachingPhysRegUse - True if SU would clobber one of it's successor's explicit physregs who...

Definition ScheduleDAGRRList.cpp:2856

static cl::opt< bool > DisableSchedPhysRegJoin("disable-sched-physreg-join", cl::Hidden, cl::init(false), cl::desc("Disable physreg def-use affinity"))

static bool canClobberPhysRegDefs(const SUnit *SuccSU, const SUnit *SU, const TargetInstrInfo *TII, const TargetRegisterInfo *TRI)

canClobberPhysRegDefs - True if SU would clobber one of SuccSU's physical register defs.

Definition ScheduleDAGRRList.cpp:2892

static cl::opt< unsigned > AvgIPC("sched-avg-ipc", cl::Hidden, cl::init(1), cl::desc("Average inst/cycle when no target itinerary exists."))

static void GetCostForDef(const ScheduleDAGSDNodes::RegDefIter &RegDefPos, const TargetLowering *TLI, const TargetInstrInfo *TII, const TargetRegisterInfo *TRI, unsigned &RegClass, unsigned &Cost, const MachineFunction &MF)

GetCostForDef - Looks up the register class and cost for a given definition.

Definition ScheduleDAGRRList.cpp:310

static bool BURRSort(SUnit *left, SUnit *right, RegReductionPQBase *SPQ)

Definition ScheduleDAGRRList.cpp:2541

static cl::opt< bool > DisableSchedRegPressure("disable-sched-reg-pressure", cl::Hidden, cl::init(false), cl::desc("Disable regpressure priority in sched=list-ilp"))

static bool BUHasStall(SUnit *SU, int Height, RegReductionPQBase *SPQ)

Definition ScheduleDAGRRList.cpp:2480

static void initVRegCycle(SUnit *SU)

Definition ScheduleDAGRRList.cpp:2425

static constexpr unsigned RegSequenceCost

Definition ScheduleDAGRRList.cpp:304

static cl::opt< int > MaxReorderWindow("max-sched-reorder", cl::Hidden, cl::init(6), cl::desc("Number of instructions to allow ahead of the critical path " "in sched=list-ilp"))

static SDNode * FindCallSeqStart(SDNode *N, unsigned &NestLevel, unsigned &MaxNest, const TargetInstrInfo *TII)

FindCallSeqStart - Starting from the (lowered) CALLSEQ_END node, locate the corresponding (lowered) C...

Definition ScheduleDAGRRList.cpp:491

static bool isOperandOf(const SUnit *SU, SDNode *N)

Definition ScheduleDAGRRList.cpp:972

static cl::opt< bool > DisableSchedVRegCycle("disable-sched-vrcycle", cl::Hidden, cl::init(false), cl::desc("Disable virtual register cycle interference checks"))

static int checkSpecialNodes(const SUnit *left, const SUnit *right)

Definition ScheduleDAGRRList.cpp:1941

static cl::opt< bool > DisableSchedLiveUses("disable-sched-live-uses", cl::Hidden, cl::init(true), cl::desc("Disable live use priority in sched=list-ilp"))

static const uint32_t * getNodeRegMask(const SDNode *N)

getNodeRegMask - Returns the register mask attached to an SDNode, if any.

Definition ScheduleDAGRRList.cpp:1336

static unsigned closestSucc(const SUnit *SU)

closestSucc - Returns the scheduled cycle of the successor which is closest to the current cycle.

Definition ScheduleDAGRRList.cpp:2346

static bool hasVRegCycleUse(const SUnit *SU)

Definition ScheduleDAGRRList.cpp:2461

static cl::opt< bool > DisableSchedHeight("disable-sched-height", cl::Hidden, cl::init(false), cl::desc("Disable scheduled-height priority in sched=list-ilp"))

static RegisterScheduler burrListDAGScheduler("list-burr", "Bottom-up register reduction list scheduling", createBURRListDAGScheduler)

static unsigned calcMaxScratches(const SUnit *SU)

calcMaxScratches - Returns an cost estimate of the worse case requirement for scratch registers,...

Definition ScheduleDAGRRList.cpp:2364

static unsigned CalcNodeSethiUllmanNumber(const SUnit *SU, std::vector< unsigned > &SUNumbers)

CalcNodeSethiUllmanNumber - Compute Sethi Ullman number.

Definition ScheduleDAGRRList.cpp:1952

static int BUCompareLatency(SUnit *left, SUnit *right, bool checkPref, RegReductionPQBase *SPQ)

Definition ScheduleDAGRRList.cpp:2490

static void CheckForLiveRegDefMasked(SUnit *SU, const uint32_t *RegMask, ArrayRef< SUnit * > LiveRegDefs, SmallSet< unsigned, 4 > &RegAdded, SmallVectorImpl< unsigned > &LRegs)

CheckForLiveRegDefMasked - Check for any live physregs that are clobbered by RegMask,...

Definition ScheduleDAGRRList.cpp:1321

This file defines the SmallSet 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)

This file describes how to lower LLVM code to machine code.

ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...

size_t size() const

size - Get the array size.

bool empty() const

empty - Check if the array is empty.

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

unsigned getNumOperands() const

Return the number of declared MachineOperands for this MachineInstruction.

ArrayRef< MCOperandInfo > operands() const

bool hasOptionalDef() const

Set if this instruction has an optional definition, e.g.

unsigned getNumDefs() const

Return the number of MachineOperands that are register definitions.

int getOperandConstraint(unsigned OpNum, MCOI::OperandConstraint Constraint) const

Returns the value of the specified operand constraint if it is present.

ArrayRef< MCPhysReg > implicit_defs() const

Return a list of registers that are potentially written by any instance of this machine instruction.

bool isCommutable() const

Return true if this may be a 2- or 3-address instruction (of the form "X = op Y, Z,...

const MCInstrDesc & get(unsigned Opcode) const

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

MCRegAliasIterator enumerates all registers aliasing Reg.

Wrapper class representing physical registers. Should be passed by value.

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.

static bool clobbersPhysReg(const uint32_t *RegMask, MCRegister PhysReg)

clobbersPhysReg - Returns true if this RegMask clobbers PhysReg.

const TargetRegisterClass * getRegClass(Register Reg) const

Return the register class of the specified virtual register.

Wrapper class representing virtual and physical registers.

constexpr bool isPhysical() const

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

Represents one node in the SelectionDAG.

bool isMachineOpcode() const

Test if this node has a post-isel opcode, directly corresponding to a MachineInstr opcode.

int getNodeId() const

Return the unique node id.

unsigned getOpcode() const

Return the SelectionDAG opcode value for this node.

unsigned getIROrder() const

Return the node ordering.

void setNodeId(int Id)

Set unique node id.

MVT getSimpleValueType(unsigned ResNo) const

Return the type of a specified result as a simple type.

unsigned getNumValues() const

Return the number of values defined/returned by this operator.

unsigned getMachineOpcode() const

This may only be called if isMachineOpcode returns true.

const SDValue & getOperand(unsigned Num) const

uint64_t getConstantOperandVal(unsigned Num) const

Helper method returns the integer value of a ConstantSDNode operand.

LLVM_ABI bool hasAnyUseOfValue(unsigned Value) const

Return true if there are any use of the indicated value.

SDNode * getGluedNode() const

If this node has a glue operand, return the node to which the glue operand points.

Unlike LLVM values, Selection DAG nodes may return multiple values as the result of a computation.

SDNode * getNode() const

get the SDNode which holds the desired result

@ Data

Regular data dependence (aka true-dependence).

@ Artificial

Arbitrary strong DAG edge (no real dependence).

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.

bool isArtificial() const

Tests if this is an Order dependence that is marked as "artificial", meaning it isn't necessary for c...

bool isCtrl() const

Shorthand for getKind() != SDep::Data.

Returns the register associated with this edge.

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

bool isCall

Is a function call.

LLVM_ABI void setHeightToAtLeast(unsigned NewHeight)

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

unsigned NodeQueueId

Queue id of node.

unsigned NodeNum

Entry # of node in the node vector.

bool hasPhysRegClobbers

Has any physreg defs, used or not.

bool isCallOp

Is a function call operand.

const TargetRegisterClass * CopyDstRC

Is a special copy node if != nullptr.

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

bool isSucc(const SUnit *N) const

Tests if node N is a successor of this node.

LLVM_ABI void removePred(const SDep &D)

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

unsigned short Latency

Node latency.

unsigned short NumRegDefsLeft

bool isPending

True once pending.

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.

bool isAvailable

True once available.

bool isScheduleLow

True if preferable to schedule low.

bool hasPhysRegDefs

Has physreg defs that are being used.

SmallVector< SDep, 4 > Succs

All sunit successors.

Sched::Preference SchedulingPref

Scheduling preference.

const TargetRegisterClass * CopySrcRC

SDNode * getNode() const

Returns the representative SDNode for this SUnit.

bool isTwoAddress

Is a two-address instruction.

bool isCommutable

Is a commutable instruction.

bool isVRegCycle

May use and def the same vreg.

SmallVector< SDep, 4 > Preds

All sunit predecessors.

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

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

RegDefIter - In place iteration over the values defined by an SUnit.

const SDNode * GetNode() const

ScheduleDAGSDNodes - A ScheduleDAG for scheduling SDNode-based DAGs.

This class can compute a topological ordering for SUnits and provides methods for dynamically updatin...

void MarkDirty()

Mark the ordering as temporarily broken, after a new node has been added.

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

HazardRecognizer - This determines whether or not an instruction can be issued this cycle,...

unsigned getMaxLookAhead() const

virtual void RecedeCycle()

RecedeCycle - This callback is invoked whenever the next bottom-up instruction to be scheduled cannot...

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 HazardType getHazardType(SUnit *, int Stalls=0)

getHazardType - Return the hazard type of emitting this node.

This interface is used to plug different priorities computation algorithms into the list scheduler.

void setCurCycle(unsigned Cycle)

virtual void remove(SUnit *SU)=0

virtual void releaseState()=0

virtual void scheduledNode(SUnit *)

As each node is scheduled, this method is invoked.

virtual bool tracksRegPressure() const

virtual void dump(ScheduleDAG *) const

bool hasReadyFilter() const

virtual void initNodes(std::vector< SUnit > &SUnits)=0

virtual bool empty() const =0

virtual void unscheduledNode(SUnit *)

virtual void addNode(const SUnit *SU)=0

virtual void updateNode(const SUnit *SU)=0

virtual void push(SUnit *U)=0

SelectionDAGISel - This is the common base class used for SelectionDAG-based pattern-matching instruc...

const TargetLowering * TLI

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

reference emplace_back(ArgTypes &&... Args)

void push_back(const T &Elt)

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

TargetInstrInfo - Interface to description of machine instruction set.

virtual bool canCopyGluedNodeDuringSchedule(SDNode *N) const

Return true if the given SDNode can be copied during scheduling even if it has glue.

unsigned getCallFrameSetupOpcode() const

These methods return the opcode of the frame setup/destroy instructions if they exist (-1 otherwise).

virtual bool unfoldMemoryOperand(MachineFunction &MF, MachineInstr &MI, Register Reg, bool UnfoldLoad, bool UnfoldStore, SmallVectorImpl< MachineInstr * > &NewMIs) const

unfoldMemoryOperand - Separate a single instruction which folded a load or a store or a load and a st...

unsigned getCallFrameDestroyOpcode() const

virtual uint8_t getRepRegClassCostFor(MVT VT) const

Return the cost of the 'representative' register class for the specified value type.

virtual const TargetRegisterClass * getRepRegClassFor(MVT VT) const

Return the 'representative' register class for the specified value type.

This class defines information used to lower LLVM code to legal SelectionDAG operators that the targe...

unsigned getID() const

Return the register class ID number.

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

virtual unsigned getRegPressureLimit(const TargetRegisterClass *RC, MachineFunction &MF) const

Return the register pressure "high water mark" for the specific register class.

TargetSubtargetInfo - Generic base class for all target subtargets.

virtual const TargetInstrInfo * getInstrInfo() const

virtual const TargetRegisterInfo * getRegisterInfo() const =0

Return the target's register information.

#define llvm_unreachable(msg)

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

@ MERGE_VALUES

MERGE_VALUES - This node takes multiple discrete operands and returns them all as its individual resu...

@ CopyFromReg

CopyFromReg - This node indicates that the input value is a virtual or physical register that is defi...

@ EntryToken

EntryToken - This is the marker used to indicate the start of a region.

@ CopyToReg

CopyToReg - This node has three operands: a chain, a register number to set to this value,...

@ TokenFactor

TokenFactor - This node takes multiple tokens as input and produces a single token result.

initializer< Ty > init(const Ty &Val)

Sequence

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

NodeAddr< DefNode * > Def

NodeAddr< NodeBase * > Node

LLVM_ABI std::error_code remove(const Twine &path, bool IgnoreNonExisting=true)

Remove path.

This is an optimization pass for GlobalISel generic memory operations.

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

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

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

void fill(R &&Range, T &&Value)

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

LLVM_ABI ScheduleDAGSDNodes * createBURRListDAGScheduler(SelectionDAGISel *IS, CodeGenOptLevel OptLevel)

createBURRListDAGScheduler - This creates a bottom up register usage reduction list scheduler.

Definition ScheduleDAGRRList.cpp:3145

decltype(auto) dyn_cast(const From &Val)

dyn_cast - Return the argument parameter cast to the specified type.

LLVM_ABI ScheduleDAGSDNodes * createHybridListDAGScheduler(SelectionDAGISel *IS, CodeGenOptLevel)

createHybridListDAGScheduler - This creates a bottom up register pressure aware list scheduler that m...

Definition ScheduleDAGRRList.cpp:3173

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)

CodeGenOptLevel

Code generation optimization level.

class LLVM_GSL_OWNER SmallVector

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

LLVM_ABI ScheduleDAGSDNodes * createSourceListDAGScheduler(SelectionDAGISel *IS, CodeGenOptLevel OptLevel)

createSourceListDAGScheduler - This creates a bottom up list scheduler that schedules nodes in source...

Definition ScheduleDAGRRList.cpp:3159

uint16_t MCPhysReg

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

DWARFExpression::Operation Op

ArrayRef(const T &OneElt) -> ArrayRef< T >

LLVM_ABI ScheduleDAGSDNodes * createILPListDAGScheduler(SelectionDAGISel *IS, CodeGenOptLevel)

createILPListDAGScheduler - This creates a bottom up register pressure aware list scheduler that trie...

Definition ScheduleDAGRRList.cpp:3188

decltype(auto) cast(const From &Val)

cast - Return the argument parameter cast to the specified type.

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.

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

Implement std::swap in terms of BitVector swap.