ResourcePriorityQueue.cpp Source File (original) (raw)

31using namespace llvm;

33#define DEBUG_TYPE "scheduler"

37 cl::desc("Disable use of DFA during scheduling"));

41 cl::desc("Track reg pressure and switch priority to in-depth"));

44 : Picker(this), InstrItins(IS->MF->getSubtarget().getInstrItineraryData()) {

47 TLI = IS->TLI;

49 ResourcesModel.reset(TII->CreateTargetScheduleState(STI));

52 assert(ResourcesModel && "Unimplemented CreateTargetScheduleState.");

54 unsigned NumRC = TRI->getNumRegClasses();

55 RegLimit.resize(NumRC);

56 RegPressure.resize(NumRC);

60 RegLimit[RC->getID()] = TRI->getRegPressureLimit(RC, *IS->MF);

62 ParallelLiveRanges = 0;

63 HorizontalVerticalBalance = 0;

64}

68unsigned

69ResourcePriorityQueue::numberRCValPredInSU(SUnit *SU, unsigned RCId) {

70 unsigned NumberDeps = 0;

72 if (Pred.isCtrl())

73 continue;

75 SUnit *PredSU = Pred.getSUnit();

78 if (!ScegN)

79 continue;

84 default: break;

88 case ISD::INLINEASM: break;

89 case ISD::INLINEASM_BR: break;

90 }

92 continue;

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

98 NumberDeps++;

99 break;

100 }

101 }

102 }

103 return NumberDeps;

104}

105

106unsigned ResourcePriorityQueue::numberRCValSuccInSU(SUnit *SU,

107 unsigned RCId) {

108 unsigned NumberDeps = 0;

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

111 continue;

112

113 SUnit *SuccSU = Succ.getSUnit();

114 const SDNode *ScegN = SuccSU->getNode();

115 if (!ScegN)

116 continue;

117

118

119

121 default: break;

125 case ISD::INLINEASM: break;

126 case ISD::INLINEASM_BR: break;

127 }

129 continue;

130

131 for (unsigned i = 0, e = ScegN->getNumOperands(); i != e; ++i) {

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

134 if (TLI->isTypeLegal(VT)

135 && (TLI->getRegClassFor(VT)->getID() == RCId)) {

136 NumberDeps++;

137 break;

138 }

139 }

140 }

141 return NumberDeps;

142}

143

145 unsigned NumberDeps = 0;

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

148 NumberDeps++;

149

150 return NumberDeps;

151}

152

154 unsigned NumberDeps = 0;

156 if (Pred.isCtrl())

157 NumberDeps++;

158

159 return NumberDeps;

160}

161

162

163

164

166 SUnits = &sunits;

167 NumNodesSolelyBlocking.resize(SUnits->size(), 0);

168

169 for (SUnit &SU : *SUnits) {

172 }

173}

174

175

176

178

179

180

181 if (LHS->isScheduleHigh && !RHS->isScheduleHigh)

182 return false;

183

184 if (!LHS->isScheduleHigh && RHS->isScheduleHigh)

185 return true;

186

187 unsigned LHSNum = LHS->NodeNum;

188 unsigned RHSNum = RHS->NodeNum;

189

190

191 unsigned LHSLatency = PQ->getLatency(LHSNum);

192 unsigned RHSLatency = PQ->getLatency(RHSNum);

193 if (LHSLatency < RHSLatency) return true;

194 if (LHSLatency > RHSLatency) return false;

195

196

197

198 unsigned LHSBlocked = PQ->getNumSolelyBlockNodes(LHSNum);

199 unsigned RHSBlocked = PQ->getNumSolelyBlockNodes(RHSNum);

200 if (LHSBlocked < RHSBlocked) return true;

201 if (LHSBlocked > RHSBlocked) return false;

202

203

204

205 return LHSNum < RHSNum;

206}

207

208

209

210

211SUnit *ResourcePriorityQueue::getSingleUnscheduledPred(SUnit *SU) {

212 SUnit *OnlyAvailablePred = nullptr;

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

214 SUnit &PredSU = *Pred.getSUnit();

216

217

218 if (OnlyAvailablePred && OnlyAvailablePred != &PredSU)

219 return nullptr;

220 OnlyAvailablePred = &PredSU;

221 }

222 }

223 return OnlyAvailablePred;

224}

225

227

228

229 unsigned NumNodesBlocking = 0;

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

231 if (getSingleUnscheduledPred(Succ.getSUnit()) == SU)

232 ++NumNodesBlocking;

233

234 NumNodesSolelyBlocking[SU->NodeNum] = NumNodesBlocking;

235 Queue.push_back(SU);

236}

237

238

239

241 if (!SU || !SU->getNode())

242 return false;

243

244

245

247 return true;

248

249

250

253 default:

254 if (!ResourcesModel->canReserveResources(&TII->get(

256 return false;

257 break;

258 case TargetOpcode::EXTRACT_SUBREG:

259 case TargetOpcode::INSERT_SUBREG:

260 case TargetOpcode::SUBREG_TO_REG:

261 case TargetOpcode::REG_SEQUENCE:

262 case TargetOpcode::IMPLICIT_DEF:

263 break;

264 }

265

266

267

268 for (const SUnit *S : Packet)

269 for (const SDep &Succ : S->Succs) {

270

271

273 continue;

274

276 return false;

277 }

278

279 return true;

280}

281

282

284

285

287 ResourcesModel->clearResources();

288 Packet.clear();

289 }

290

293 default:

294 ResourcesModel->reserveResources(&TII->get(

296 break;

297 case TargetOpcode::EXTRACT_SUBREG:

298 case TargetOpcode::INSERT_SUBREG:

299 case TargetOpcode::SUBREG_TO_REG:

300 case TargetOpcode::REG_SEQUENCE:

301 case TargetOpcode::IMPLICIT_DEF:

302 break;

303 }

304 Packet.push_back(SU);

305 }

306

307 else {

308 ResourcesModel->clearResources();

309 Packet.clear();

310 }

311

312

313

314 if (Packet.size() >= InstrItins->SchedModel.IssueWidth) {

315 ResourcesModel->clearResources();

316 Packet.clear();

317 }

318}

319

321 int RegBalance = 0;

322

324 return RegBalance;

325

326

329 if (TLI->isTypeLegal(VT)

330 && TLI->getRegClassFor(VT)

331 && TLI->getRegClassFor(VT)->getID() == RCId)

332 RegBalance += numberRCValSuccInSU(SU, RCId);

333 }

334

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

339 continue;

340

341 if (TLI->isTypeLegal(VT) && TLI->getRegClassFor(VT)

342 && TLI->getRegClassFor(VT)->getID() == RCId)

343 RegBalance -= numberRCValPredInSU(SU, RCId);

344 }

345 return RegBalance;

346}

347

348

349

350

351

352

353

355 int RegBalance = 0;

356

358 return RegBalance;

359

360 if (RawPressure) {

363 }

364 else {

366 if ((RegPressure[RC->getID()] +

368 (RegPressure[RC->getID()] +

371 }

372 }

373

374 return RegBalance;

375}

376

377

378

387

388

389

391

392 int ResCount = 1;

393

394

396 return ResCount;

397

398

401

402

403

404

406

408

409

412

413

414

416 }

417

418

419 else {

420

422

423 ResCount += (NumNodesSolelyBlocking[SU->NodeNum] * ScaleTwo);

424

425

428

430 }

431

432

433

434

436 if (N->isMachineOpcode()) {

437 const MCInstrDesc &TID = TII->get(N->getMachineOpcode());

440 }

441 else

442 switch (N->getOpcode()) {

443 default: break;

448 break;

449

450 case ISD::INLINEASM:

451 case ISD::INLINEASM_BR:

453 break;

454 }

455 }

456 return ResCount;

457}

458

459

460

462

463

464 if (!SU) {

465 ResourcesModel->clearResources();

466 Packet.clear();

467 return;

468 }

469

471

472

474

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

477

478 if (TLI->isTypeLegal(VT)) {

480 if (RC)

481 RegPressure[RC->getID()] += numberRCValSuccInSU(SU, RC->getID());

482 }

483 }

484

485 for (unsigned i = 0, e = ScegN->getNumOperands(); i != e; ++i) {

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

488

489 if (TLI->isTypeLegal(VT)) {

491 if (RC) {

492 if (RegPressure[RC->getID()] >

493 (numberRCValPredInSU(SU, RC->getID())))

494 RegPressure[RC->getID()] -= numberRCValPredInSU(SU, RC->getID());

495 else RegPressure[RC->getID()] = 0;

496 }

497 }

498 }

500 if (Pred.isCtrl() || (Pred.getSUnit()->NumRegDefsLeft == 0))

501 continue;

502 --Pred.getSUnit()->NumRegDefsLeft;

503 }

504 }

505

506

508

509

510

511

512 unsigned NumberNonControlDeps = 0;

513

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

515 adjustPriorityOfUnscheduledPreds(Succ.getSUnit());

517 NumberNonControlDeps++;

518 }

519

520 if (!NumberNonControlDeps) {

521 if (ParallelLiveRanges >= SU->NumPreds)

522 ParallelLiveRanges -= SU->NumPreds;

523 else

524 ParallelLiveRanges = 0;

525

526 }

527 else

529

530

533}

534

536 unsigned NodeNumDefs = 0;

538 if (N->isMachineOpcode()) {

539 const MCInstrDesc &TID = TII->get(N->getMachineOpcode());

540

541 if (N->getMachineOpcode() == TargetOpcode::IMPLICIT_DEF) {

542 NodeNumDefs = 0;

543 break;

544 }

545 NodeNumDefs = std::min(N->getNumValues(), TID.getNumDefs());

546 }

547 else

548 switch(N->getOpcode()) {

549 default: break;

551 NodeNumDefs++;

552 break;

553 case ISD::INLINEASM:

554 case ISD::INLINEASM_BR:

555 NodeNumDefs++;

556 break;

557 }

558

560}

561

562

563

564

565

566

567

568void ResourcePriorityQueue::adjustPriorityOfUnscheduledPreds(SUnit *SU) {

569 if (SU->isAvailable) return;

570

571 SUnit *OnlyAvailablePred = getSingleUnscheduledPred(SU);

572 if (!OnlyAvailablePred || !OnlyAvailablePred->isAvailable)

573 return;

574

575

576

577 remove(OnlyAvailablePred);

578

579

580

581 push(OnlyAvailablePred);

582}

583

584

585

586

589 return nullptr;

590

591 std::vector<SUnit *>::iterator Best = Queue.begin();

594 for (auto I = std::next(Queue.begin()), E = Queue.end(); I != E; ++I) {

595

598 Best = I;

599 }

600 }

601 }

602

603 else {

604 for (auto I = std::next(Queue.begin()), E = Queue.end(); I != E; ++I)

605 if (Picker(*Best, *I))

606 Best = I;

607 }

608

609 SUnit *V = *Best;

610 if (Best != std::prev(Queue.end()))

612

613 Queue.pop_back();

614

615 return V;

616}

617

618

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

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

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

624

625 Queue.pop_back();

626}

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

static const unsigned PriorityTwo

Definition ResourcePriorityQueue.cpp:380

static const unsigned FactorOne

Definition ResourcePriorityQueue.cpp:386

static const unsigned PriorityThree

Definition ResourcePriorityQueue.cpp:381

static cl::opt< int > RegPressureThreshold("dfa-sched-reg-pressure-threshold", cl::Hidden, cl::init(5), cl::desc("Track reg pressure and switch priority to in-depth"))

static const unsigned ScaleOne

Definition ResourcePriorityQueue.cpp:383

static unsigned numberCtrlPredInSU(SUnit *SU)

Definition ResourcePriorityQueue.cpp:153

static const unsigned PriorityOne

Definition ResourcePriorityQueue.cpp:379

static unsigned numberCtrlDepsInSU(SUnit *SU)

Definition ResourcePriorityQueue.cpp:144

static cl::opt< bool > DisableDFASched("disable-dfa-sched", cl::Hidden, cl::desc("Disable use of DFA during scheduling"))

static const unsigned PriorityFour

Definition ResourcePriorityQueue.cpp:382

static const unsigned ScaleTwo

Definition ResourcePriorityQueue.cpp:384

static const unsigned ScaleThree

Definition ResourcePriorityQueue.cpp:385

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

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

unsigned getNumDefs() const

Return the number of MachineOperands that are register definitions.

bool isCall() const

Return true if the instruction is a call.

const TargetSubtargetInfo & getSubtarget() const

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

void push(SUnit *U) override

Definition ResourcePriorityQueue.cpp:226

void scheduledNode(SUnit *SU) override

scheduledNode - Main resource tracking point.

Definition ResourcePriorityQueue.cpp:461

ResourcePriorityQueue(SelectionDAGISel *IS)

Definition ResourcePriorityQueue.cpp:43

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

Initialize nodes.

Definition ResourcePriorityQueue.cpp:165

bool empty() const override

SUnit * pop() override

Main access point - returns next instructions to be placed in scheduling sequence.

Definition ResourcePriorityQueue.cpp:587

int rawRegPressureDelta(SUnit *SU, unsigned RCId)

Definition ResourcePriorityQueue.cpp:320

int regPressureDelta(SUnit *SU, bool RawPressure=false)

Estimates change in reg pressure from this SU.

Definition ResourcePriorityQueue.cpp:354

void remove(SUnit *SU) override

Definition ResourcePriorityQueue.cpp:619

~ResourcePriorityQueue() override

void reserveResources(SUnit *SU)

Keep track of available resources.

Definition ResourcePriorityQueue.cpp:283

int SUSchedulingCost(SUnit *SU)

Single cost function reflecting benefit of scheduling SU in the current cycle.

Definition ResourcePriorityQueue.cpp:390

void initNumRegDefsLeft(SUnit *SU)

InitNumRegDefsLeft - Determine the # of regs defined by this node.

Definition ResourcePriorityQueue.cpp:535

bool isResourceAvailable(SUnit *SU)

Check if scheduling of this SU is possible in the current packet.

Definition ResourcePriorityQueue.cpp:240

Represents one node in the SelectionDAG.

bool isMachineOpcode() const

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

unsigned getOpcode() const

Return the SelectionDAG opcode value for this node.

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 getNumOperands() const

Return the number of values used by this operation.

unsigned getMachineOpcode() const

This may only be called if isMachineOpcode returns true.

const SDValue & getOperand(unsigned Num) const

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.

bool isCtrl() const

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

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

unsigned NodeQueueId

Queue id of node.

unsigned NodeNum

Entry # of node in the node vector.

unsigned getHeight() const

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

unsigned short NumRegDefsLeft

bool isScheduleHigh

True if preferable to schedule high.

bool isScheduled

True once scheduled.

bool isAvailable

True once available.

SmallVector< SDep, 4 > Succs

All sunit successors.

SDNode * getNode() const

Returns the representative SDNode for this SUnit.

SmallVector< SDep, 4 > Preds

All sunit predecessors.

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

const TargetLowering * TLI

virtual const TargetRegisterClass * getRegClassFor(MVT VT, bool isDivergent=false) const

Return the register class that should be used for the specified value type.

bool isTypeLegal(EVT VT) const

Return true if the target has native support for the specified value type.

unsigned getID() const

Return the register class ID number.

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.

@ CopyFromReg

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

@ 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)

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.

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

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

bool isa(const From &Val)

isa - Return true if the parameter to the template is an instance of one of the template type argu...

DWARFExpression::Operation Op

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

Implement std::swap in terms of BitVector swap.

bool operator()(const SUnit *LHS, const SUnit *RHS) const

This heuristic is used if DFA scheduling is not desired for some VLIW platform.

Definition ResourcePriorityQueue.cpp:177

ResourcePriorityQueue * PQ