CriticalAntiDepBreaker.cpp Source File (original) (raw)

34#include

35#include

37using namespace llvm;

39#define DEBUG_TYPE "post-RA-sched"

43 : MF(MFi), MRI(MF.getRegInfo()), TII(MF.getSubtarget().getInstrInfo()),

44 TRI(MF.getSubtarget().getRegisterInfo()), RegClassInfo(RCI),

45 Classes(TRI->getNumRegs(), nullptr), KillIndices(TRI->getNumRegs(), 0),

46 DefIndices(TRI->getNumRegs(), 0), KeepRegs(TRI->getNumRegs(), false) {}

51 const unsigned BBSize = BB->size();

52 for (unsigned i = 1, e = TRI->getNumRegs(); i != e; ++i) {

54 Classes[i] = nullptr;

57 KillIndices[i] = ~0u;

58 DefIndices[i] = BBSize;

59 }

62 KeepRegs.reset();

68 for (const auto &LI : Succ->liveins()) {

72 KillIndices[Reg.id()] = BBSize;

73 DefIndices[Reg.id()] = ~0u;

74 }

75 }

82 for (const MCPhysReg *I = MF.getRegInfo().getCalleeSavedRegs(); *I;

83 ++I) {

84 unsigned Reg = *I;

85 if (!IsReturnBlock && !Pristine.test(Reg))

86 continue;

90 KillIndices[Reg.id()] = BBSize;

91 DefIndices[Reg.id()] = ~0u;

92 }

93 }

94}

100

102 unsigned InsertPosIndex) {

103

104

105

106

107

108

109

110 if (MI.isDebugInstr() || MI.isKill())

111 return;

112 assert(Count < InsertPosIndex && "Instruction index out of expected range!");

113

114 for (unsigned Reg = 1; Reg != TRI->getNumRegs(); ++Reg) {

115 if (KillIndices[Reg] != ~0u) {

116

117

118

120 KillIndices[Reg] = Count;

121 } else if (DefIndices[Reg] < InsertPosIndex && DefIndices[Reg] >= Count) {

122

123

124

125

127

128

129

130 DefIndices[Reg] = InsertPosIndex;

131 }

132 }

133

134 PrescanInstruction(MI);

135 ScanInstruction(MI, Count);

136}

137

138

139

142 unsigned NextDepth = 0;

143

145 const SUnit *PredSU = P.getSUnit();

146 unsigned PredLatency = P.getLatency();

147 unsigned PredTotalLatency = PredSU->getDepth() + PredLatency;

148

149

150 if (NextDepth < PredTotalLatency ||

151 (NextDepth == PredTotalLatency && P.getKind() == SDep::Anti)) {

152 NextDepth = PredTotalLatency;

154 }

155 }

157}

158

159void CriticalAntiDepBreaker::PrescanInstruction(MachineInstr &MI) {

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176 bool Special =

177 MI.isCall() || MI.hasExtraSrcRegAllocReq() || TII->isPredicated(MI);

178

179

180

181 for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) {

182 MachineOperand &MO = MI.getOperand(i);

183 if (!MO.isReg()) continue;

185 if ( Reg )

186 continue;

187 const TargetRegisterClass *NewRC = nullptr;

188

189 if (i < MI.getDesc().getNumOperands())

190 NewRC = TII->getRegClass(MI.getDesc(), i);

191

192

193

194 if (!Classes[Reg.id()] && NewRC)

195 Classes[Reg.id()] = NewRC;

196 else if (!NewRC || Classes[Reg.id()] != NewRC)

197 Classes[Reg.id()] = reinterpret_cast<TargetRegisterClass *>(-1);

198

199

200 for (MCRegAliasIterator AI(Reg, TRI, false); AI.isValid(); ++AI) {

201

202

203

204 unsigned AliasReg = (*AI).id();

205 if (Classes[AliasReg]) {

206 Classes[AliasReg] = reinterpret_cast<TargetRegisterClass *>(-1);

207 Classes[Reg.id()] = reinterpret_cast<TargetRegisterClass *>(-1);

208 }

209 }

210

211

212 if (Classes[Reg.id()] != reinterpret_cast<TargetRegisterClass *>(-1))

213 RegRefs.emplace(Reg, &MO);

214

215 if (MO.isUse() && Special) {

216 if (!KeepRegs.test(Reg.id())) {

218 KeepRegs.set(SubReg);

219 }

220 }

221 }

222

223 for (unsigned I = 0, E = MI.getNumOperands(); I != E; ++I) {

224 const MachineOperand &MO = MI.getOperand(I);

225 if (!MO.isReg()) continue;

228 continue;

229

230

231

232

233

234

235

236

237

238

239 if (MI.isRegTiedToUseOperand(I) &&

240 Classes[Reg.id()] == reinterpret_cast<TargetRegisterClass *>(-1)) {

242 KeepRegs.set(SubReg);

243 }

244 for (MCPhysReg SuperReg : TRI->superregs(Reg)) {

245 KeepRegs.set(SuperReg);

246 }

247 }

248 }

249}

250

251void CriticalAntiDepBreaker::ScanInstruction(MachineInstr &MI, unsigned Count) {

252

253

254

255 assert(.isKill() && "Attempting to scan a kill instruction");

256

257 if (!TII->isPredicated(MI)) {

258

259

260 for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) {

261 MachineOperand &MO = MI.getOperand(i);

262

264 auto ClobbersPhysRegAndSubRegs = [&](unsigned PhysReg) {

265 return all_of(TRI->subregs_inclusive(PhysReg),

266 [&](MCPhysReg SR) { return MO.clobbersPhysReg(SR); });

267 };

268

269 for (unsigned i = 1, e = TRI->getNumRegs(); i != e; ++i) {

270 if (ClobbersPhysRegAndSubRegs(i)) {

271 DefIndices[i] = Count;

272 KillIndices[i] = ~0u;

273 KeepRegs.reset(i);

274 Classes[i] = nullptr;

275 RegRefs.erase(i);

276 }

277 }

278 }

279

280 if (!MO.isReg()) continue;

282 if ( Reg )

283 continue;

284 if (!MO.isDef()) continue;

285

286

287 if (MI.isRegTiedToUseOperand(i))

288 continue;

289

290

291

292 bool Keep = KeepRegs.test(Reg.id());

293

294

295

296 for (MCPhysReg SubregReg : TRI->subregs_inclusive(Reg)) {

297 DefIndices[SubregReg] = Count;

298 KillIndices[SubregReg] = ~0u;

299 Classes[SubregReg] = nullptr;

300 RegRefs.erase(SubregReg);

302 KeepRegs.reset(SubregReg);

303 }

304

306 Classes[SR] = reinterpret_cast<TargetRegisterClass *>(-1);

307 }

308 }

309 for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) {

310 MachineOperand &MO = MI.getOperand(i);

311 if (!MO.isReg()) continue;

313 if ( Reg )

314 continue;

315 if (!MO.isUse()) continue;

316

317 const TargetRegisterClass *NewRC = nullptr;

318 if (i < MI.getDesc().getNumOperands())

319 NewRC = TII->getRegClass(MI.getDesc(), i);

320

321

322

323 if (!Classes[Reg.id()] && NewRC)

324 Classes[Reg.id()] = NewRC;

325 else if (!NewRC || Classes[Reg.id()] != NewRC)

326 Classes[Reg.id()] = reinterpret_cast<TargetRegisterClass *>(-1);

327

328 RegRefs.emplace(Reg, &MO);

329

330

331

332 for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI) {

333 MCRegister AliasReg = *AI;

334 if (KillIndices[AliasReg.id()] == ~0u) {

335 KillIndices[AliasReg.id()] = Count;

336 DefIndices[AliasReg.id()] = ~0u;

337 }

338 }

339 }

340}

341

342

343

344

345

346

347

348

349

350

351

352

353bool CriticalAntiDepBreaker::isNewRegClobberedByRefs(RegRefIter RegRefBegin,

354 RegRefIter RegRefEnd,

356 for (RegRefIter I = RegRefBegin; I != RegRefEnd; ++I ) {

357 MachineOperand *RefOper = I->second;

358

359

360

361

363 return true;

364

365

367 for (const MachineOperand &CheckOper : MI->operands()) {

368 if (CheckOper.isRegMask() && CheckOper.clobbersPhysReg(NewReg))

369 return true;

370

371 if (!CheckOper.isReg() || !CheckOper.isDef() ||

372 CheckOper.getReg() != NewReg)

373 continue;

374

375

376

377 if (RefOper->isDef())

378 return true;

379

380

381

382 if (CheckOper.isEarlyClobber())

383 return true;

384

385

386

387 if (MI->isInlineAsm())

388 return true;

389 }

390 }

391 return false;

392}

393

394MCRegister CriticalAntiDepBreaker::findSuitableFreeRegister(

395 RegRefIter RegRefBegin, RegRefIter RegRefEnd, MCRegister AntiDepReg,

399 for (MCRegister NewReg : Order) {

400

401 if (NewReg == AntiDepReg) continue;

402

403

404

405 if (NewReg == LastNewReg) continue;

406

407

408

409 if (isNewRegClobberedByRefs(RegRefBegin, RegRefEnd, NewReg)) continue;

410

411

412 assert(((KillIndices[AntiDepReg.id()] == ~0u) !=

413 (DefIndices[AntiDepReg.id()] == ~0u)) &&

414 "Kill and Def maps aren't consistent for AntiDepReg!");

415 assert(((KillIndices[NewReg.id()] == ~0u) !=

416 (DefIndices[NewReg.id()] == ~0u)) &&

417 "Kill and Def maps aren't consistent for NewReg!");

418 if (KillIndices[NewReg.id()] != ~0u ||

419 Classes[NewReg.id()] == reinterpret_cast<TargetRegisterClass *>(-1) ||

420 KillIndices[AntiDepReg.id()] > DefIndices[NewReg.id()])

421 continue;

422

423 bool Forbidden = false;

425 if (TRI->regsOverlap(NewReg, R)) {

426 Forbidden = true;

427 break;

428 }

429 if (Forbidden) continue;

430 return NewReg;

431 }

432

433

434 return MCRegister();

435}

436

441 unsigned InsertPosIndex,

443

444

445 if (SUnits.empty()) return 0;

446

447

448

449

450

452

453

454 const SUnit *Max = nullptr;

455 for (const SUnit &SU : SUnits) {

456 MISUnitMap[SU.getInstr()] = &SU;

457 if (!Max || SU.getDepth() + SU.Latency > Max->getDepth() + Max->Latency)

458 Max = &SU;

459 }

460 assert(Max && "Failed to find bottom of the critical path");

461

462#ifndef NDEBUG

463 {

464 LLVM_DEBUG(dbgs() << "Critical path has total latency "

465 << (Max->getDepth() + Max->Latency) << "\n");

467 for (unsigned Reg = 1; Reg < TRI->getNumRegs(); ++Reg) {

468 if (KillIndices[Reg] == ~0u)

470 }

472 }

473#endif

474

475

476

477 const SUnit *CriticalPathSU = Max;

479

480

481

482

483

484

485

486

487

488

489

490

491

492

493

494

495

496

497

498

499

500

501

502

503

504

505

506

507

508

509

510

511

512

513

514

515

516

517

518

519

520

521 std::vector LastNewReg(TRI->getNumRegs(), MCRegister());

522

523

524

525

526 unsigned Broken = 0;

527 unsigned Count = InsertPosIndex - 1;

530

531

532

533

534

535

536

537 if (MI.isDebugInstr() || MI.isKill())

538 continue;

539

540

541

542

543

544

545

546

547

548

549

550

551

552

554 if (&MI == CriticalPathMI) {

556 const SUnit *NextSU = Edge->getSUnit();

557

558

560 AntiDepReg = Edge->getReg().asMCReg();

561 assert(AntiDepReg && "Anti-dependence on reg0?");

562 if (!MRI.isAllocatable(AntiDepReg))

563

565 else if (KeepRegs.test(AntiDepReg.id()))

566

567

569 else {

570

571

572

573

574

575

576

577

578 for (const SDep &P : CriticalPathSU->Preds)

579 if (P.getSUnit() == NextSU

580 ? (P.getKind() != SDep::Anti || P.getReg() != AntiDepReg)

582 P.getReg() == AntiDepReg)) {

584 break;

585 }

586 }

587 }

588 CriticalPathSU = NextSU;

589 CriticalPathMI = CriticalPathSU->getInstr();

590 } else {

591

592 CriticalPathSU = nullptr;

593 CriticalPathMI = nullptr;

594 }

595 }

596

597 PrescanInstruction(MI);

598

600

601

602

603

604 if (MI.isCall() || MI.hasExtraDefRegAllocReq() || TII->isPredicated(MI))

605

606

608 else if (AntiDepReg) {

609

610

611

612

614 if (!MO.isReg()) continue;

616 if (!Reg)

617 continue;

618 if (MO.isUse() && TRI->regsOverlap(AntiDepReg, Reg)) {

620 break;

621 }

622 if (MO.isDef() && Reg != AntiDepReg)

624 }

625 }

626

627

628

630 AntiDepReg ? Classes[AntiDepReg.id()] : nullptr;

631 assert((!AntiDepReg || RC != nullptr) &&

632 "Register should be live if it's causing an anti-dependence!");

635

636

637

638

639

640 if (AntiDepReg) {

641 std::pair<std::multimap<MCRegister, MachineOperand *>::iterator,

642 std::multimap<MCRegister, MachineOperand *>::iterator>

643 Range = RegRefs.equal_range(AntiDepReg);

644 if (MCRegister NewReg = findSuitableFreeRegister(

645 Range.first, Range.second, AntiDepReg,

646 LastNewReg[AntiDepReg.id()], RC, ForbidRegs)) {

647 LLVM_DEBUG(dbgs() << "Breaking anti-dependence edge on "

648 << printReg(AntiDepReg, TRI) << " with "

649 << RegRefs.count(AntiDepReg) << " references"

650 << " using " << printReg(NewReg, TRI) << "!\n");

651

652

653

654 for (std::multimap<MCRegister, MachineOperand *>::iterator

656 QE = Range.second;

657 Q != QE; ++Q) {

658 Q->second->setReg(NewReg);

659

660

661

662 const SUnit *SU = MISUnitMap[Q->second->getParent()];

663 if (!SU) continue;

665 AntiDepReg, NewReg);

666 }

667

668

669

670

671 Classes[NewReg.id()] = Classes[AntiDepReg.id()];

672 DefIndices[NewReg.id()] = DefIndices[AntiDepReg.id()];

673 KillIndices[NewReg.id()] = KillIndices[AntiDepReg.id()];

674 assert(((KillIndices[NewReg.id()] == ~0u) !=

675 (DefIndices[NewReg.id()] == ~0u)) &&

676 "Kill and Def maps aren't consistent for NewReg!");

677

678 Classes[AntiDepReg.id()] = nullptr;

679 DefIndices[AntiDepReg.id()] = KillIndices[AntiDepReg.id()];

680 KillIndices[AntiDepReg.id()] = ~0u;

681 assert(((KillIndices[AntiDepReg.id()] == ~0u) !=

682 (DefIndices[AntiDepReg.id()] == ~0u)) &&

683 "Kill and Def maps aren't consistent for AntiDepReg!");

684

685 RegRefs.erase(AntiDepReg);

686 LastNewReg[AntiDepReg.id()] = NewReg;

687 ++Broken;

688 }

689 }

690

691 ScanInstruction(MI, Count);

692 }

693

694 return Broken;

695}

696

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

static const SUnit * CriticalPathStep(const SUnit *SU)

CriticalPathStep - Return the next SUnit after SU on the bottom-up critical path.

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

This file defines the DenseMap class.

Promote Memory to Register

ConstantRange Range(APInt(BitWidth, Low), APInt(BitWidth, High))

This file defines the SmallVector class.

This class works in conjunction with the post-RA scheduler to rename registers to break register anti...

void UpdateDbgValues(const DbgValueVector &DbgValues, MachineInstr *ParentMI, MCRegister OldReg, MCRegister NewReg)

Update all DBG_VALUE instructions that may be affected by the dependency breaker's update of ParentMI...

std::vector< std::pair< MachineInstr *, MachineInstr * > > DbgValueVector

bool test(unsigned Idx) const

void clear()

clear - Removes all bits from the bitvector.

~CriticalAntiDepBreaker() override

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

Identifiy anti-dependencies along the critical path of the ScheduleDAG and break them by renaming reg...

Definition CriticalAntiDepBreaker.cpp:438

void FinishBlock() override

Finish anti-dep breaking for a basic block.

Definition CriticalAntiDepBreaker.cpp:96

void Observe(MachineInstr &MI, unsigned Count, unsigned InsertPosIndex) override

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

Definition CriticalAntiDepBreaker.cpp:101

void StartBlock(MachineBasicBlock *BB) override

Initialize anti-dep breaking for a new basic block.

Definition CriticalAntiDepBreaker.cpp:50

CriticalAntiDepBreaker(MachineFunction &MFi, const RegisterClassInfo &RCI)

Definition CriticalAntiDepBreaker.cpp:41

MCRegAliasIterator enumerates all registers aliasing Reg.

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

constexpr unsigned id() const

bool isReturnBlock() const

Convenience function that returns true if the block ends in a return instruction.

iterator_range< succ_iterator > successors()

MachineInstrBundleIterator< MachineInstr > iterator

The MachineFrameInfo class represents an abstract stack frame until prolog/epilog code is inserted.

LLVM_ABI BitVector getPristineRegs(const MachineFunction &MF) const

Return a set of physical registers that are pristine.

Representation of each machine instruction.

MachineOperand class - Representation of each machine instruction operand.

bool isReg() const

isReg - Tests if this is a MO_Register operand.

bool isRegMask() const

isRegMask - Tests if this is a MO_RegisterMask operand.

MachineInstr * getParent()

getParent - Return the instruction that this operand belongs to.

bool isEarlyClobber() const

getReg - Returns the register number.

Wrapper class representing virtual and physical registers.

constexpr bool isValid() const

constexpr unsigned id() const

@ Anti

A register anti-dependence (aka WAR).

@ Data

Regular data dependence (aka true-dependence).

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

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

SmallVector< SDep, 4 > Preds

All sunit predecessors.

MachineInstr * getInstr() const

Returns the representative MachineInstr for this SUnit.

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

void push_back(const T &Elt)

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

This is an optimization pass for GlobalISel generic memory operations.

bool all_of(R &&range, UnaryPredicate P)

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

LLVM_ABI raw_ostream & dbgs()

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

FunctionAddr VTableAddr Count

uint16_t MCPhysReg

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

FunctionAddr VTableAddr Next

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

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

Definition CriticalAntiDepBreaker.cpp:698

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.

@ Keep

No function return thunk.