SplitKit.cpp Source File (original) (raw)

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

37#include

38#include

39#include

40#include

41#include

43using namespace llvm;

45#define DEBUG_TYPE "regalloc"

49 cl::desc("Enable loop iv regalloc heuristic"),

52 STATISTIC(NumFinished, "Number of splits finished");

53 STATISTIC(NumSimple, "Number of splits that were simple");

54 STATISTIC(NumCopies, "Number of copies inserted for splitting");

55 STATISTIC(NumRemats, "Number of rematerialized defs for splitting");

62 unsigned BBNum)

63 : LIS(lis), LastInsertPoint(BBNum) {}

66InsertPointAnalysis::computeLastInsertPoint(const LiveInterval &CurLI,

68 unsigned Num = MBB.getNumber();

69 std::pair<SlotIndex, SlotIndex> &LIP = LastInsertPoint[Num];

73 bool EHPadSuccessor = false;

75 if (SMBB->isEHPad()) {

76 ExceptionalSuccessors.push_back(SMBB);

77 EHPadSuccessor = true;

78 } else if (SMBB->isInlineAsmBrIndirectTarget())

79 ExceptionalSuccessors.push_back(SMBB);

80 }

84 if (!LIP.first.isValid()) {

86 if (FirstTerm == MBB.end())

87 LIP.first = MBBEnd;

88 else

89 LIP.first = LIS.getInstructionIndex(*FirstTerm);

97 if (ExceptionalSuccessors.empty())

98 return LIP.first;

100 if ((EHPadSuccessor && MI.isCall()) ||

101 MI.getOpcode() == TargetOpcode::INLINEASM_BR) {

102 LIP.second = LIS.getInstructionIndex(MI);

103 break;

104 }

105 }

106 }

107

108

109

110 if (!LIP.second)

111 return LIP.first;

112

113 if (none_of(ExceptionalSuccessors, [&](const MachineBasicBlock *EHPad) {

114 return LIS.isLiveInToMBB(CurLI, EHPad);

115 }))

116 return LIP.first;

117

118

120 if (!VNI)

121 return LIP.first;

122

123

124

126 if (auto *I = LIS.getInstructionFromIndex(LIP.second))

127 if (I->getOpcode() == TargetOpcode::STATEPOINT)

128 return LIP.second;

129

130

131

132

134 return LIP.first;

135

136

137

138 return LIP.second;

139}

140

145 if (LIP == LIS.getMBBEndIdx(&MBB))

146 return MBB.end();

147 return LIS.getInstructionFromIndex(LIP);

148}

149

150

151

152

153

156 : MF(vrm.getMachineFunction()), VRM(vrm), LIS(lis), Loops(mli),

157 TII(*MF.getSubtarget().getInstrInfo()), IPA(lis, MF.getNumBlockIDs()) {}

158

160 UseSlots.clear();

161 UseBlocks.clear();

162 ThroughBlocks.clear();

163 CurLI = nullptr;

164}

165

166

167void SplitAnalysis::analyzeUses() {

168 assert(UseSlots.empty() && "Call clear first");

169

170

171

174 UseSlots.push_back(VNI->def);

175

176

179 if (!MO.isUndef())

181

183

184

185

187 UseSlots.end());

188

189

190 calcLiveBlockInfo();

191

192 LLVM_DEBUG(dbgs() << "Analyze counted " << UseSlots.size() << " instrs in "

193 << UseBlocks.size() << " blocks, through "

194 << NumThroughBlocks << " blocks.\n");

195}

196

197

198

199void SplitAnalysis::calcLiveBlockInfo() {

201 NumThroughBlocks = NumGapBlocks = 0;

202 if (CurLI->empty())

203 return;

204

207

209 UseI = UseSlots.begin();

210 UseE = UseSlots.end();

211

212

215 while (true) {

216 BlockInfo BI;

217 BI.MBB = &*MFI;

220

221

222

223

224 if (UseI == UseE || *UseI >= Stop) {

225 ++NumThroughBlocks;

226 ThroughBlocks.set(BI.MBB->getNumber());

227

228

229 assert(LVI->end >= Stop && "range ends mid block with no uses");

230 } else {

231

232 BI.FirstInstr = *UseI;

233 assert(BI.FirstInstr >= Start);

234 do ++UseI;

235 while (UseI != UseE && *UseI < Stop);

236 BI.LastInstr = UseI[-1];

237 assert(BI.LastInstr < Stop);

238

239

240 BI.LiveIn = LVI->start <= Start;

241

242

243 if (!BI.LiveIn) {

244 assert(LVI->start == LVI->valno->def && "Dangling Segment start");

245 assert(LVI->start == BI.FirstInstr && "First instr should be a def");

246 BI.FirstDef = BI.FirstInstr;

247 }

248

249

250 BI.LiveOut = true;

251 while (LVI->end < Stop) {

252 SlotIndex LastStop = LVI->end;

253 if (++LVI == LVE || LVI->start >= Stop) {

254 BI.LiveOut = false;

255 BI.LastInstr = LastStop;

256 break;

257 }

258

259 if (LastStop < LVI->start) {

260

261

262 ++NumGapBlocks;

263

264

265 BI.LiveOut = false;

266 UseBlocks.push_back(BI);

267 UseBlocks.back().LastInstr = LastStop;

268

269

270 BI.LiveIn = false;

271 BI.LiveOut = true;

272 BI.FirstInstr = BI.FirstDef = LVI->start;

273 }

274

275

276 assert(LVI->start == LVI->valno->def && "Dangling Segment start");

277 if (!BI.FirstDef)

278 BI.FirstDef = LVI->start;

279 }

280

281 UseBlocks.push_back(BI);

282

283

284 if (LVI == LVE)

285 break;

286 }

287

288

289 if (LVI->end == Stop && ++LVI == LVE)

290 break;

291

292

293 if (LVI->start < Stop)

294 ++MFI;

295 else

296 MFI = LIS.getMBBFromIndex(LVI->start)->getIterator();

297 }

298

301 MachineLoop *L = Loops.getLoopFor(BI.MBB);

302 return BI.LiveIn && BI.LiveOut && BI.FirstDef && L &&

303 L->isLoopLatch(BI.MBB);

304 });

305

307}

308

310 if (cli->empty())

311 return 0;

315 unsigned Count = 0;

316

317

319 LIS.getMBBFromIndex(LVI->start)->getIterator();

321 while (true) {

324 if (LVI == LVE)

326 do {

327 ++MFI;

328 Stop = LIS.getMBBEndIdx(&*MFI);

329 } while (Stop <= LVI->start);

330 }

331}

332

334 Register OrigReg = VRM.getOriginal(CurLI->reg());

336 assert(!Orig.empty() && "Splitting empty interval?");

338

339

340 if (I != Orig.end() && I->start <= Idx)

341 return I->start == Idx;

342

343

344 return I != Orig.begin() && (--I)->end == Idx;

345}

346

349 CurLI = li;

350 analyzeUses();

351}

352

353

354

355

356

357

361 : SA(SA), LIS(LIS), VRM(VRM), MRI(VRM.getMachineFunction().getRegInfo()),

362 MDT(MDT), TII(*VRM.getMachineFunction().getSubtarget().getInstrInfo()),

363 TRI(*VRM.getMachineFunction().getSubtarget().getRegisterInfo()),

364 MBFI(MBFI), VRAI(VRAI), RegAssign(Allocator) {}

365

367 Edit = &LRE;

368 SpillMode = SM;

369 OpenIdx = 0;

370 RegAssign.clear();

371 Values.clear();

372

373

374 LICalc[0].reset(&VRM.getMachineFunction(), LIS.getSlotIndexes(), &MDT,

375 &LIS.getVNInfoAllocator());

376 if (SpillMode)

377 LICalc[1].reset(&VRM.getMachineFunction(), LIS.getSlotIndexes(), &MDT,

378 &LIS.getVNInfoAllocator());

379}

380

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

383 if (RegAssign.empty()) {

384 dbgs() << " empty\n";

385 return;

386 }

387

388 for (RegAssignMap::const_iterator I = RegAssign.begin(); I.valid(); ++I)

389 dbgs() << " [" << I.start() << ';' << I.stop() << "):" << I.value();

390 dbgs() << '\n';

391}

392#endif

393

394

395

396

397

399 for (auto &S : LI.subranges())

400 if (S.LaneMask == LM)

401 return S;

403}

404

409

414

415

416

417

418

422 if ((S.LaneMask & LM) == LM)

423 return S;

425}

426

427void SplitEditor::addDeadDef(LiveInterval &LI, VNInfo *VNI, bool Original) {

430 return;

431 }

432

433 SlotIndex Def = VNI->def;

434 if (Original) {

435

436

437

438 for (LiveInterval::SubRange &S : LI.subranges()) {

440 VNInfo *PV = PS.getVNInfoAt(Def);

441 if (PV != nullptr && PV->def == Def)

442 S.createDeadDef(Def, LIS.getVNInfoAllocator());

443 }

444 } else {

445

446

447

448 const MachineInstr *DefMI = LIS.getInstructionFromIndex(Def);

450 LaneBitmask LM;

451 for (const MachineOperand &DefOp : DefMI->defs()) {

453 if (R != LI.reg())

454 continue;

455 if (unsigned SR = DefOp.getSubReg())

456 LM |= TRI.getSubRegIndexLaneMask(SR);

457 else {

458 LM = MRI.getMaxLaneMaskForVReg(R);

459 break;

460 }

461 }

462 for (LiveInterval::SubRange &S : LI.subranges())

463 if ((S.LaneMask & LM).any())

464 S.createDeadDef(Def, LIS.getVNInfoAllocator());

465 }

466}

467

468VNInfo *SplitEditor::defValue(unsigned RegIdx,

469 const VNInfo *ParentVNI,

471 bool Original) {

472 assert(ParentVNI && "Mapping NULL value");

474 assert(Edit->getParent().getVNInfoAt(Idx) == ParentVNI && "Bad Parent VNI");

475 LiveInterval *LI = &LIS.getInterval(Edit->get(RegIdx));

476

477

478 VNInfo *VNI = LI->getNextValue(Idx, LIS.getVNInfoAllocator());

479

481 ValueForcePair FP(Force ? nullptr : VNI, Force);

482

483 std::pair<ValueMap::iterator, bool> InsP =

484 Values.insert(std::make_pair(std::make_pair(RegIdx, ParentVNI->id), FP));

485

486

487

488 if (!Force && InsP.second)

489 return VNI;

490

491

492 if (VNInfo *OldVNI = InsP.first->second.getPointer()) {

493 addDeadDef(*LI, OldVNI, Original);

494

495

496

497 InsP.first->second = ValueForcePair(nullptr, Force);

498 }

499

500

501 addDeadDef(*LI, VNI, Original);

502 return VNI;

503}

504

505void SplitEditor::forceRecompute(unsigned RegIdx, const VNInfo &ParentVNI) {

506 ValueForcePair &VFP = Values[std::make_pair(RegIdx, ParentVNI.id)];

507 VNInfo *VNI = VFP.getPointer();

508

509

510

511 if (!VNI) {

512 VFP.setInt(true);

513 return;

514 }

515

516

517

518 addDeadDef(LIS.getInterval(Edit->get(RegIdx)), VNI, false);

519

520

521 VFP = ValueForcePair(nullptr, true);

522}

523

524SlotIndex SplitEditor::buildSingleSubRegCopy(

528 bool FirstCopy = Def .isValid();

532 .addReg(FromReg, 0, SubIdx);

533

534 SlotIndexes &Indexes = *LIS.getSlotIndexes();

535 if (FirstCopy) {

537 } else {

539 }

540 return Def;

541}

542

546 const MCInstrDesc &Desc =

547 TII.get(TII.getLiveRangeSplitOpcode(FromReg, *MBB.getParent()));

548 SlotIndexes &Indexes = *LIS.getSlotIndexes();

549 if (LaneMask.all() || LaneMask == MRI.getMaxLaneMaskForVReg(FromReg)) {

550

551 MachineInstr *CopyMI =

554 }

555

556

557

558

559 LiveInterval &DestLI = LIS.getInterval(Edit->get(RegIdx));

560

561

562

563 const TargetRegisterClass *RC = MRI.getRegClass(FromReg);

564 assert(RC == MRI.getRegClass(ToReg) && "Should have same reg class");

565

566 SmallVector<unsigned, 8> SubIndexes;

567

568

569 if (!TRI.getCoveringSubRegIndexes(RC, LaneMask, SubIndexes))

571

572 SlotIndex Def;

573 for (unsigned BestIdx : SubIndexes) {

574 Def = buildSingleSubRegCopy(FromReg, ToReg, MBB, InsertBefore, BestIdx,

575 DestLI, Late, Def, Desc);

576 }

577

580 Allocator, LaneMask,

581 [Def, &Allocator](LiveInterval::SubRange &SR) {

583 },

584 Indexes, TRI);

585

586 return Def;

587}

588

589bool SplitEditor::rematWillIncreaseRestriction(const MachineInstr *DefMI,

592 const MachineInstr *UseMI = LIS.getInstructionFromIndex(UseIdx);

594 return false;

595

596

597 const unsigned DefOperandIdx = 0;

598

599

600

601 const TargetRegisterClass *DefConstrainRC =

603 if (!DefConstrainRC)

604 return false;

605

606 const TargetRegisterClass *RC = MRI.getRegClass(Edit->getReg());

607

608

609

610 const TargetRegisterClass *SuperRC =

611 TRI.getLargestLegalSuperClass(RC, *MBB.getParent());

612

614 const TargetRegisterClass *UseConstrainRC =

616 true);

617 return UseConstrainRC->hasSubClass(DefConstrainRC);

618}

619

620VNInfo *SplitEditor::defFromParent(unsigned RegIdx, const VNInfo *ParentVNI,

623 LiveInterval *LI = &LIS.getInterval(Edit->get(RegIdx));

624

625

626

627 bool Late = RegIdx != 0;

628

629

630 Register Original = VRM.getOriginal(Edit->get(RegIdx));

631 LiveInterval &OrigLI = LIS.getInterval(Original);

632 VNInfo *OrigVNI = OrigLI.getVNInfoAt(UseIdx);

633

635 if (OrigVNI) {

636 LiveRangeEdit::Remat RM(ParentVNI);

637 RM.OrigMI = LIS.getInstructionFromIndex(OrigVNI->def);

638 if (RM.OrigMI && TII.isAsCheapAsAMove(*RM.OrigMI) &&

639 Edit->canRematerializeAt(RM, UseIdx)) {

640 if (!rematWillIncreaseRestriction(RM.OrigMI, MBB, UseIdx)) {

641 SlotIndex Def = Edit->rematerializeAt(MBB, I, Reg, RM, TRI, Late);

642 ++NumRemats;

643

644 return defValue(RegIdx, ParentVNI, Def, false);

645 }

647 dbgs() << "skipping rematerialize of " << printReg(Reg) << " at "

648 << UseIdx

649 << " since it will increase register class restrictions\n");

650 }

651 }

652

653 LaneBitmask LaneMask;

656 for (LiveInterval::SubRange &S : OrigLI.subranges()) {

657 if (S.liveAt(UseIdx))

658 LaneMask |= S.LaneMask;

659 }

660 } else {

662 }

663

664 SlotIndex Def;

665 if (LaneMask.none()) {

666 const MCInstrDesc &Desc = TII.get(TargetOpcode::IMPLICIT_DEF);

668 SlotIndexes &Indexes = *LIS.getSlotIndexes();

670 } else {

671 ++NumCopies;

672 Def = buildCopy(Edit->getReg(), Reg, LaneMask, MBB, I, Late, RegIdx);

673 }

674

675

676 return defValue(RegIdx, ParentVNI, Def, false);

677}

678

679

681

682 if (Edit->empty())

683 Edit->createEmptyInterval();

684

685

686 OpenIdx = Edit->size();

687 Edit->createEmptyInterval();

688 return OpenIdx;

689}

690

692 assert(Idx != 0 && "Cannot select the complement interval");

693 assert(Idx < Edit->size() && "Can only select previously opened interval");

694 LLVM_DEBUG(dbgs() << " selectIntv " << OpenIdx << " -> " << Idx << '\n');

695 OpenIdx = Idx;

696}

697

699 assert(OpenIdx && "openIntv not called before enterIntvBefore");

702 VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Idx);

703 if (!ParentVNI) {

705 return Idx;

706 }

709 assert(MI && "enterIntvBefore called with invalid index");

710

711 VNInfo *VNI = defFromParent(OpenIdx, ParentVNI, Idx, *MI->getParent(), MI);

712 return VNI->def;

713}

714

716 assert(OpenIdx && "openIntv not called before enterIntvAfter");

719 VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Idx);

720 if (!ParentVNI) {

722 return Idx;

723 }

726 assert(MI && "enterIntvAfter called with invalid index");

727

728 VNInfo *VNI = defFromParent(OpenIdx, ParentVNI, Idx, *MI->getParent(),

730 return VNI->def;

731}

732

734 assert(OpenIdx && "openIntv not called before enterIntvAtEnd");

739 VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Last);

740 if (!ParentVNI) {

742 return End;

743 }

745 if (LSP < Last) {

746

747

748

749

750

751

753 ParentVNI = Edit->getParent().getVNInfoAt(Last);

754 if (!ParentVNI) {

755

757 return End;

758 }

759 }

760

762 VNInfo *VNI = defFromParent(OpenIdx, ParentVNI, Last, MBB,

763 SA.getLastSplitPointIter(&MBB));

764 RegAssign.insert(VNI->def, End, OpenIdx);

766 return VNI->def;

767}

768

769

771 useIntv(LIS.getMBBStartIdx(&MBB), LIS.getMBBEndIdx(&MBB));

772}

773

775 assert(OpenIdx && "openIntv not called before useIntv");

776 LLVM_DEBUG(dbgs() << " useIntv [" << Start << ';' << End << "):");

777 RegAssign.insert(Start, End, OpenIdx);

779}

780

782 assert(OpenIdx && "openIntv not called before leaveIntvAfter");

784

785

787 VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Boundary);

788 if (!ParentVNI) {

791 }

793 MachineInstr *MI = LIS.getInstructionFromIndex(Boundary);

794 assert(MI && "No instruction at index");

795

796

797

798

799

801 MI->readsVirtualRegister(Edit->getReg())) {

802 forceRecompute(0, *ParentVNI);

803 defFromParent(0, ParentVNI, Idx, *MI->getParent(), MI);

804 return Idx;

805 }

806

807 VNInfo *VNI = defFromParent(0, ParentVNI, Boundary, *MI->getParent(),

809 return VNI->def;

810}

811

813 assert(OpenIdx && "openIntv not called before leaveIntvBefore");

815

816

818 VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Idx);

819 if (!ParentVNI) {

822 }

824

826 assert(MI && "No instruction at index");

827 VNInfo *VNI = defFromParent(0, ParentVNI, Idx, *MI->getParent(), MI);

828 return VNI->def;

829}

830

832 assert(OpenIdx && "openIntv not called before leaveIntvAtTop");

835 << Start);

836

837 VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Start);

838 if (!ParentVNI) {

840 return Start;

841 }

842

843 unsigned RegIdx = 0;

844 Register Reg = LIS.getInterval(Edit->get(RegIdx)).reg();

845 VNInfo *VNI = defFromParent(RegIdx, ParentVNI, Start, MBB,

846 MBB.SkipPHIsLabelsAndDebug(MBB.begin(), Reg));

847 RegAssign.insert(Start, VNI->def, OpenIdx);

849 return VNI->def;

850}

851

854 return MO.isReg() && MO.isTied() && MO.getReg() == Reg;

855 });

856}

857

859 assert(OpenIdx && "openIntv not called before overlapIntv");

860 const VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Start);

861 assert(ParentVNI == Edit->getParent().getVNInfoBefore(End) &&

862 "Parent changes value in extended range");

863 assert(LIS.getMBBFromIndex(Start) == LIS.getMBBFromIndex(End) &&

864 "Range cannot span basic blocks");

865

866

867 if (ParentVNI)

868 forceRecompute(0, *ParentVNI);

869

870

871

872

873 if (auto *MI = LIS.getInstructionFromIndex(End))

875 LLVM_DEBUG(dbgs() << "skip overlap due to tied def at end\n");

876 return;

877 }

878

879 LLVM_DEBUG(dbgs() << " overlapIntv [" << Start << ';' << End << "):");

880 RegAssign.insert(Start, End, OpenIdx);

882}

883

884

885

886

887

892 AssignI.setMap(RegAssign);

893

897 assert(MI && "No instruction for back-copy");

898

901 bool AtBegin;

902 do AtBegin = MBBI == MBB->begin();

903 while (!AtBegin && (--MBBI)->isDebugOrPseudoInstr());

904

908 MI->eraseFromParent();

909

910

911

912 AssignI.find(Def.getPrevSlot());

913 if (!AssignI.valid() || AssignI.start() >= Def)

914 continue;

915

916 if (AssignI.stop() != Def)

917 continue;

918 unsigned RegIdx = AssignI.value();

919

920

921

922

924 AtBegin ? SlotIndex() : LIS.getInstructionIndex(*MBBI).getRegSlot();

925 if (AtBegin || MBBI ->readsVirtualRegister(Edit->getReg()) ||

926 Kill <= AssignI.start()) {

927 LLVM_DEBUG(dbgs() << " cannot find simple kill of RegIdx " << RegIdx

928 << '\n');

929 forceRecompute(RegIdx, *Edit->getParent().getVNInfoAt(Def));

930 } else {

931 LLVM_DEBUG(dbgs() << " move kill to " << Kill << '\t' << *MBBI);

932 AssignI.setStop(Kill);

933 }

934 }

935}

936

940 if (MBB == DefMBB)

941 return MBB;

942 assert(MDT.dominates(DefMBB, MBB) && "MBB must be dominated by the def.");

943

944 const MachineLoopInfo &Loops = SA.Loops;

945 const MachineLoop *DefLoop = Loops.getLoopFor(DefMBB);

947

948

949 MachineBasicBlock *BestMBB = MBB;

950 unsigned BestDepth = std::numeric_limits::max();

951

952 while (true) {

953 const MachineLoop *Loop = Loops.getLoopFor(MBB);

954

955

956

957 if (!Loop) {

960 << " at depth 0\n");

961 return MBB;

962 }

963

964

965 if (Loop == DefLoop) {

968 << " in the same loop\n");

969 return MBB;

970 }

971

972

974 if (Depth < BestDepth) {

975 BestMBB = MBB;

976 BestDepth = Depth;

979 << " at depth " << Depth << '\n');

980 }

981

982

983

985

986

987 if (!IDom || !MDT.dominates(DefDomNode, IDom))

988 return BestMBB;

989

991 }

992}

993

994void SplitEditor::computeRedundantBackCopies(

996 LiveInterval *LI = &LIS.getInterval(Edit->get(0));

997 const LiveInterval *Parent = &Edit->getParent();

999 SmallPtrSet<VNInfo *, 8> DominatedVNIs;

1000

1001

1002 for (VNInfo *VNI : LI->valnos) {

1004 continue;

1005 VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(VNI->def);

1006 EqualVNs[ParentVNI->id].insert(VNI);

1007 }

1008

1009

1010

1011 for (unsigned i = 0, e = Parent->getNumValNums(); i != e; ++i) {

1012 const VNInfo *ParentVNI = Parent->getValNumInfo(i);

1013 if (!NotToHoistSet.count(ParentVNI->id))

1014 continue;

1015 SmallPtrSetIterator<VNInfo *> It1 = EqualVNs[ParentVNI->id].begin();

1016 SmallPtrSetIterator<VNInfo *> It2 = It1;

1017 for (; It1 != EqualVNs[ParentVNI->id].end(); ++It1) {

1018 It2 = It1;

1019 for (++It2; It2 != EqualVNs[ParentVNI->id].end(); ++It2) {

1020 if (DominatedVNIs.count(*It1) || DominatedVNIs.count(*It2))

1021 continue;

1022

1023 MachineBasicBlock *MBB1 = LIS.getMBBFromIndex((*It1)->def);

1024 MachineBasicBlock *MBB2 = LIS.getMBBFromIndex((*It2)->def);

1025 if (MBB1 == MBB2) {

1026 DominatedVNIs.insert((*It1)->def < (*It2)->def ? (*It2) : (*It1));

1027 } else if (MDT.dominates(MBB1, MBB2)) {

1028 DominatedVNIs.insert(*It2);

1029 } else if (MDT.dominates(MBB2, MBB1)) {

1030 DominatedVNIs.insert(*It1);

1031 }

1032 }

1033 }

1034 if (!DominatedVNIs.empty()) {

1035 forceRecompute(0, *ParentVNI);

1037 DominatedVNIs.clear();

1038 }

1039 }

1040}

1041

1042

1043

1044

1045

1046

1047void SplitEditor::hoistCopies() {

1048

1049 LiveInterval *LI = &LIS.getInterval(Edit->get(0));

1050 const LiveInterval *Parent = &Edit->getParent();

1051

1052

1053

1054 using DomPair = std::pair<MachineBasicBlock *, SlotIndex>;

1056

1058

1059

1060 DenseSet NotToHoistSet;

1061

1062

1063

1064 for (VNInfo *VNI : LI->valnos) {

1066 continue;

1067 VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(VNI->def);

1068 assert(ParentVNI && "Parent not live at complement def");

1069

1070

1071

1072 if (Edit->didRematerialize(ParentVNI))

1073 continue;

1074

1075 MachineBasicBlock *ValMBB = LIS.getMBBFromIndex(VNI->def);

1076

1077 DomPair &Dom = NearestDom[ParentVNI->id];

1078

1079

1080

1081

1082 if (VNI->def == ParentVNI->def) {

1083 LLVM_DEBUG(dbgs() << "Direct complement def at " << VNI->def << '\n');

1084 Dom = DomPair(ValMBB, VNI->def);

1085 continue;

1086 }

1087

1088

1089 if (Values.lookup(std::make_pair(0, ParentVNI->id)).getPointer()) {

1090 LLVM_DEBUG(dbgs() << "Single complement def at " << VNI->def << '\n');

1091 continue;

1092 }

1093

1094 if (!Dom.first) {

1095

1096 Dom = DomPair(ValMBB, VNI->def);

1097 } else if (Dom.first == ValMBB) {

1098

1099 if (!Dom.second.isValid() || VNI->def < Dom.second)

1100 Dom.second = VNI->def;

1101 } else {

1102

1103 MachineBasicBlock *Near =

1104 MDT.findNearestCommonDominator(Dom.first, ValMBB);

1105 if (Near == ValMBB)

1106

1107 Dom = DomPair(ValMBB, VNI->def);

1108 else if (Near != Dom.first)

1109

1110 Dom = DomPair(Near, SlotIndex());

1111 Costs[ParentVNI->id] += MBFI.getBlockFreq(ValMBB);

1112 }

1113

1114 LLVM_DEBUG(dbgs() << "Multi-mapped complement " << VNI->id << '@'

1115 << VNI->def << " for parent " << ParentVNI->id << '@'

1116 << ParentVNI->def << " hoist to "

1118 << '\n');

1119 }

1120

1121

1122 for (unsigned i = 0, e = Parent->getNumValNums(); i != e; ++i) {

1123 DomPair &Dom = NearestDom[i];

1124 if (!Dom.first || Dom.second.isValid())

1125 continue;

1126

1127 const VNInfo *ParentVNI = Parent->getValNumInfo(i);

1128 MachineBasicBlock *DefMBB = LIS.getMBBFromIndex(ParentVNI->def);

1129

1130 Dom.first = findShallowDominator(Dom.first, DefMBB);

1131 if (SpillMode == SM_Speed &&

1132 MBFI.getBlockFreq(Dom.first) > Costs[ParentVNI->id]) {

1133 NotToHoistSet.insert(ParentVNI->id);

1134 continue;

1135 }

1136 SlotIndex LSP = SA.getLastSplitPoint(Dom.first);

1137 if (LSP <= ParentVNI->def) {

1138 NotToHoistSet.insert(ParentVNI->id);

1139 continue;

1140 }

1141 Dom.second = defFromParent(0, ParentVNI, LSP, *Dom.first,

1142 SA.getLastSplitPointIter(Dom.first))->def;

1143 }

1144

1145

1146

1148 for (VNInfo *VNI : LI->valnos) {

1150 continue;

1151 VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(VNI->def);

1152 const DomPair &Dom = NearestDom[ParentVNI->id];

1153 if (!Dom.first || Dom.second == VNI->def ||

1154 NotToHoistSet.count(ParentVNI->id))

1155 continue;

1157 forceRecompute(0, *ParentVNI);

1158 }

1159

1160

1161

1162 if (SpillMode == SM_Speed && !NotToHoistSet.empty())

1163 computeRedundantBackCopies(NotToHoistSet, BackCopies);

1164

1165 removeBackCopies(BackCopies);

1166}

1167

1168

1169

1170bool SplitEditor::transferValues() {

1172 RegAssignMap::const_iterator AssignI = RegAssign.begin();

1173 for (const LiveRange::Segment &S : Edit->getParent()) {

1175 VNInfo *ParentVNI = S.valno;

1176

1177 SlotIndex Start = S.start;

1178 AssignI.advanceTo(Start);

1179 do {

1180 unsigned RegIdx;

1181 SlotIndex End = S.end;

1182 if (!AssignI.valid()) {

1183 RegIdx = 0;

1184 } else if (AssignI.start() <= Start) {

1185 RegIdx = AssignI.value();

1186 if (AssignI.stop() < End) {

1187 End = AssignI.stop();

1188 ++AssignI;

1189 }

1190 } else {

1191 RegIdx = 0;

1192 End = std::min(End, AssignI.start());

1193 }

1194

1195

1196 LLVM_DEBUG(dbgs() << " [" << Start << ';' << End << ")=" << RegIdx << '('

1197 << printReg(Edit->get(RegIdx)) << ')');

1198 LiveInterval &LI = LIS.getInterval(Edit->get(RegIdx));

1199

1200

1201 ValueForcePair VFP = Values.lookup(std::make_pair(RegIdx, ParentVNI->id));

1202 if (VNInfo *VNI = VFP.getPointer()) {

1204 LI.addSegment(LiveInterval::Segment(Start, End, VNI));

1206 continue;

1207 }

1208

1209

1210 if (VFP.getInt()) {

1214 continue;

1215 }

1216

1217 LiveIntervalCalc &LIC = getLICalc(RegIdx);

1218

1219

1220

1221

1223 SlotIndex BlockStart, BlockEnd;

1224 std::tie(BlockStart, BlockEnd) = LIS.getSlotIndexes()->getMBBRange(&*MBB);

1225

1226

1227 if (Start != BlockStart) {

1228 VNInfo *VNI = LI.extendInBlock(BlockStart, std::min(BlockEnd, End));

1229 assert(VNI && "Missing def for complex mapped value");

1231

1232 if (BlockEnd <= End)

1234

1235

1237 BlockStart = BlockEnd;

1238 }

1239

1240

1241 assert(Start <= BlockStart && "Expected live-in block");

1242 while (BlockStart < End) {

1244 BlockEnd = LIS.getMBBEndIdx(&*MBB);

1245 if (BlockStart == ParentVNI->def) {

1246

1247 assert(ParentVNI->isPHIDef() && "Non-phi defined at block start?");

1248 VNInfo *VNI = LI.extendInBlock(BlockStart, std::min(BlockEnd, End));

1249 assert(VNI && "Missing def for complex mapped parent PHI");

1250 if (End >= BlockEnd)

1252 } else {

1253

1254

1255 if (End < BlockEnd)

1257 else {

1258

1261 }

1262 }

1263 BlockStart = BlockEnd;

1265 }

1267 } while (Start != S.end);

1269 }

1270

1271 LICalc[0].calculateValues();

1272 if (SpillMode)

1273 LICalc[1].calculateValues();

1274

1276}

1277

1280 if (Seg == nullptr)

1281 return true;

1282 if (Seg->end != Def.getDeadSlot())

1283 return false;

1284

1286 return true;

1287}

1288

1292 for (MachineBasicBlock *P : B.predecessors()) {

1293 SlotIndex End = LIS.getMBBEndIdx(P);

1295

1296

1297 const LiveInterval &PLI = Edit->getParent();

1298

1299

1302 if (PSR.liveAt(LastUse))

1303 LIC.extend(LR, End, 0, Undefs);

1304 }

1305}

1306

1307void SplitEditor::extendPHIKillRanges() {

1308

1309

1310

1311

1312

1313

1314 const LiveInterval &ParentLI = Edit->getParent();

1315 for (const VNInfo *V : ParentLI.valnos) {

1316 if (V->isUnused() || ->isPHIDef())

1317 continue;

1318

1319 unsigned RegIdx = RegAssign.lookup(V->def);

1320 LiveInterval &LI = LIS.getInterval(Edit->get(RegIdx));

1321 LiveIntervalCalc &LIC = getLICalc(RegIdx);

1322 MachineBasicBlock &B = *LIS.getMBBFromIndex(V->def);

1325 }

1326

1328 LiveIntervalCalc SubLIC;

1329

1330 for (const LiveInterval::SubRange &PS : ParentLI.subranges()) {

1331 for (const VNInfo *V : PS.valnos) {

1332 if (V->isUnused() || ->isPHIDef())

1333 continue;

1334 unsigned RegIdx = RegAssign.lookup(V->def);

1335 LiveInterval &LI = LIS.getInterval(Edit->get(RegIdx));

1338 continue;

1339

1340 MachineBasicBlock &B = *LIS.getMBBFromIndex(V->def);

1341 SubLIC.reset(&VRM.getMachineFunction(), LIS.getSlotIndexes(), &MDT,

1342 &LIS.getVNInfoAllocator());

1345 extendPHIRange(B, SubLIC, S, PS.LaneMask, Undefs);

1346 }

1347 }

1348}

1349

1350

1351void SplitEditor::rewriteAssigned(bool ExtendRanges) {

1352 struct ExtPoint {

1353 ExtPoint(const MachineOperand &O, unsigned R, SlotIndex N)

1354 : MO(O), RegIdx(R), Next(N) {}

1355

1356 MachineOperand MO;

1357 unsigned RegIdx;

1358 SlotIndex Next;

1359 };

1360

1362

1363 for (MachineOperand &MO :

1365 MachineInstr *MI = MO.getParent();

1366

1367 if (MI->isDebugValue()) {

1368 LLVM_DEBUG(dbgs() << "Zapping " << *MI);

1369 MO.setReg(0);

1370 continue;

1371 }

1372

1373

1374

1375

1376 SlotIndex Idx = LIS.getInstructionIndex(*MI);

1377 if (MO.isDef() || MO.isUndef())

1378 Idx = Idx.getRegSlot(MO.isEarlyClobber());

1379

1380

1381 unsigned RegIdx = RegAssign.lookup(Idx);

1382 LiveInterval &LI = LIS.getInterval(Edit->get(RegIdx));

1383 MO.setReg(LI.reg());

1385 << '\t' << Idx << ':' << RegIdx << '\t' << *MI);

1386

1387

1388 if (!ExtendRanges || MO.isUndef())

1389 continue;

1390

1391

1392 if (MO.isDef()) {

1393 if (!MO.getSubReg() && !MO.isEarlyClobber())

1394 continue;

1395

1396

1397 if (!Edit->getParent().liveAt(Idx.getPrevSlot()))

1398 continue;

1399 } else {

1400 assert(MO.isUse());

1401 bool IsEarlyClobber = false;

1402 if (MO.isTied()) {

1403

1404

1405

1406

1407

1408

1409

1410

1411

1412

1413

1414

1415 unsigned OpIdx = MO.getOperandNo();

1416 unsigned DefOpIdx = MI->findTiedOperandIdx(OpIdx);

1417 const MachineOperand &DefOp = MI->getOperand(DefOpIdx);

1418 IsEarlyClobber = DefOp.isEarlyClobber();

1419 }

1420

1421 Idx = Idx.getRegSlot(IsEarlyClobber);

1422 }

1423

1426

1427

1428

1429

1430 if (MO.isUse())

1431 ExtPoints.push_back(ExtPoint(MO, RegIdx, Next));

1432 } else {

1433 LiveIntervalCalc &LIC = getLICalc(RegIdx);

1434 LIC.extend(LI, Next, 0, ArrayRef());

1435 }

1436 }

1437

1438 for (ExtPoint &EP : ExtPoints) {

1439 LiveInterval &LI = LIS.getInterval(Edit->get(EP.RegIdx));

1441

1444 unsigned Sub = EP.MO.getSubReg();

1446 : MRI.getMaxLaneMaskForVReg(Reg);

1448 if ((S.LaneMask & LM).none())

1449 continue;

1450

1451

1452

1453

1454

1456 continue;

1457 SubLIC.reset(&VRM.getMachineFunction(), LIS.getSlotIndexes(), &MDT,

1458 &LIS.getVNInfoAllocator());

1461 SubLIC.extend(S, EP.Next, 0, Undefs);

1462 }

1463 }

1464

1468 continue;

1471 LIS.constructMainRangeFromSubranges(LI);

1472 }

1473}

1474

1475void SplitEditor::deleteRematVictims() {

1476 SmallVector<MachineInstr*, 8> Dead;

1477 for (const Register &R : *Edit) {

1478 LiveInterval *LI = &LIS.getInterval(R);

1479 for (const LiveRange::Segment &S : LI->segments) {

1480

1482 continue;

1484 continue;

1485 MachineInstr *MI = LIS.getInstructionFromIndex(S.valno->def);

1486 assert(MI && "Missing instruction for dead def");

1487 MI->addRegisterDead(LI->reg(), &TRI);

1488

1489 if (->allDefsAreDead())

1490 continue;

1491

1494 }

1495 }

1496

1497 if (Dead.empty())

1498 return;

1499

1500 Edit->eliminateDeadDefs(Dead, {});

1501}

1502

1503void SplitEditor::forceRecomputeVNI(const VNInfo &ParentVNI) {

1504

1505 if (!ParentVNI.isPHIDef()) {

1506 for (unsigned I = 0, E = Edit->size(); I != E; ++I)

1507 forceRecompute(I, ParentVNI);

1508 return;

1509 }

1510

1511

1512

1513 SmallPtrSet<const VNInfo *, 8> Visited = {&ParentVNI};

1515

1516 const LiveInterval &ParentLI = Edit->getParent();

1517 const SlotIndexes &Indexes = *LIS.getSlotIndexes();

1518 do {

1519 const VNInfo &VNI = *WorkList.pop_back_val();

1520 for (unsigned I = 0, E = Edit->size(); I != E; ++I)

1521 forceRecompute(I, VNI);

1523 continue;

1524

1526 for (const MachineBasicBlock *Pred : MBB.predecessors()) {

1527 SlotIndex PredEnd = Indexes.getMBBEndIdx(Pred);

1529 assert(PredVNI && "Value available in PhiVNI predecessor");

1530 if (Visited.insert(PredVNI).second)

1532 }

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

1534}

1535

1537 ++NumFinished;

1538

1539

1540

1541

1542

1543 for (const VNInfo *ParentVNI : Edit->getParent().valnos) {

1545 continue;

1546 unsigned RegIdx = RegAssign.lookup(ParentVNI->def);

1547 defValue(RegIdx, ParentVNI, ParentVNI->def, true);

1548

1549

1550

1551 if (Edit->didRematerialize(ParentVNI))

1552 forceRecomputeVNI(*ParentVNI);

1553 }

1554

1555

1556 switch (SpillMode) {

1558

1559 break;

1562

1563 hoistCopies();

1564 }

1565

1566

1567 bool Skipped = transferValues();

1568

1569

1570 rewriteAssigned(Skipped);

1571

1572 if (Skipped)

1573 extendPHIKillRanges();

1574 else

1575 ++NumSimple;

1576

1577

1578 if (Skipped)

1579 deleteRematVictims();

1580

1581

1582 for (Register Reg : *Edit) {

1586 }

1587

1588

1589 if (LRMap) {

1591 LRMap->assign(Seq.begin(), Seq.end());

1592 }

1593

1594

1596 for (unsigned i = 0, e = Edit->size(); i != e; ++i) {

1597

1598 Register VReg = Edit->get(i);

1601 LIS.splitSeparateComponents(LI, SplitLIs);

1602 Register Original = VRM.getOriginal(VReg);

1604 VRM.setIsSplitFromReg(SplitLI->reg(), Original);

1605

1606

1607 if (LRMap)

1608 LRMap->resize(Edit->size(), i);

1609 }

1610

1611

1612 Edit->calculateRegClassAndHint(VRM.getMachineFunction(), VRAI);

1613

1614 assert(!LRMap || LRMap->size() == Edit->size());

1615}

1616

1617

1618

1619

1620

1622 bool SingleInstrs) const {

1623

1625 return true;

1626

1627 if (!SingleInstrs)

1628 return false;

1629

1631 return true;

1632

1634 bool copyLike = TII.isCopyInstr(*MI) || MI->isSubregToReg();

1635 if (copyLike)

1636 return false;

1637

1639}

1640

1643 SlotIndex LastSplitPoint = SA.getLastSplitPoint(BI.MBB);

1645 LastSplitPoint));

1648 } else {

1649

1651 useIntv(SegStart, SegStop);

1653 }

1654}

1655

1656

1657

1658

1659

1660

1661

1662

1663

1664

1665

1666

1668 unsigned IntvIn, SlotIndex LeaveBefore,

1669 unsigned IntvOut, SlotIndex EnterAfter){

1671 std::tie(Start, Stop) = LIS.getSlotIndexes()->getMBBRange(MBBNum);

1672

1673 LLVM_DEBUG(dbgs() << "%bb." << MBBNum << " [" << Start << ';' << Stop

1674 << ") intf " << LeaveBefore << '-' << EnterAfter

1675 << ", live-through " << IntvIn << " -> " << IntvOut);

1676

1677 assert((IntvIn || IntvOut) && "Use splitSingleBlock for isolated blocks");

1678

1679 assert((!LeaveBefore || LeaveBefore < Stop) && "Interference after block");

1680 assert((!IntvIn || !LeaveBefore || LeaveBefore > Start) && "Impossible intf");

1681 assert((!EnterAfter || EnterAfter >= Start) && "Interference before block");

1682

1684

1685 if (!IntvOut) {

1687

1688

1689

1690

1691

1694 assert((!LeaveBefore || Idx <= LeaveBefore) && "Interference");

1695 (void)Idx;

1696 return;

1697 }

1698

1699 if (!IntvIn) {

1701

1702

1703

1704

1705

1708 assert((!EnterAfter || Idx >= EnterAfter) && "Interference");

1709 (void)Idx;

1710 return;

1711 }

1712

1713 if (IntvIn == IntvOut && !LeaveBefore && !EnterAfter) {

1715

1716

1717

1718

1721 return;

1722 }

1723

1724

1725 SlotIndex LSP = SA.getLastSplitPoint(MBBNum);

1726 assert((!IntvOut || !EnterAfter || EnterAfter < LSP) && "Impossible intf");

1727

1728 if (IntvIn != IntvOut && (!LeaveBefore || !EnterAfter ||

1730 LLVM_DEBUG(dbgs() << ", switch avoiding interference.\n");

1731

1732

1733

1734

1735

1738 if (LeaveBefore && LeaveBefore < LSP) {

1741 } else {

1743 }

1746 assert((!LeaveBefore || Idx <= LeaveBefore) && "Interference");

1747 assert((!EnterAfter || Idx >= EnterAfter) && "Interference");

1748 return;

1749 }

1750

1751 LLVM_DEBUG(dbgs() << ", create local intv for interference.\n");

1752

1753

1754

1755

1756

1757 assert(LeaveBefore <= EnterAfter && "Missed case");

1758

1762 assert((!EnterAfter || Idx >= EnterAfter) && "Interference");

1763

1767 assert((!LeaveBefore || Idx <= LeaveBefore) && "Interference");

1768}

1769

1771 unsigned IntvIn, SlotIndex LeaveBefore) {

1773 std::tie(Start, Stop) = LIS.getSlotIndexes()->getMBBRange(BI.MBB);

1774

1776 << Stop << "), uses " << BI.FirstInstr << '-'

1777 << BI.LastInstr << ", reg-in " << IntvIn

1778 << ", leave before " << LeaveBefore

1779 << (BI.LiveOut ? ", stack-out" : ", killed in block"));

1780

1781 assert(IntvIn && "Must have register in");

1783 assert((!LeaveBefore || LeaveBefore > Start) && "Bad interference");

1784

1785 if (!BI.LiveOut && (!LeaveBefore || LeaveBefore >= BI.LastInstr)) {

1787

1788

1789

1790

1791

1794 return;

1795 }

1796

1797 SlotIndex LSP = SA.getLastSplitPoint(BI.MBB);

1798

1800

1801

1802

1803

1804

1805

1806

1807

1808

1809

1811 LLVM_DEBUG(dbgs() << ", spill after last use before interference.\n");

1815 assert((!LeaveBefore || Idx <= LeaveBefore) && "Interference");

1816 } else {

1817 LLVM_DEBUG(dbgs() << ", spill before last split point.\n");

1822 assert((!LeaveBefore || Idx <= LeaveBefore) && "Interference");

1823 }

1824 return;

1825 }

1826

1827

1828

1829

1830 unsigned LocalIntv = openIntv();

1831 (void)LocalIntv;

1832 LLVM_DEBUG(dbgs() << ", creating local interval " << LocalIntv << ".\n");

1833

1835

1836

1837

1838

1839

1845 assert((!LeaveBefore || From <= LeaveBefore) && "Interference");

1846 return;

1847 }

1848

1849

1850

1851

1852

1853

1860 assert((!LeaveBefore || From <= LeaveBefore) && "Interference");

1861}

1862

1864 unsigned IntvOut, SlotIndex EnterAfter) {

1866 std::tie(Start, Stop) = LIS.getSlotIndexes()->getMBBRange(BI.MBB);

1867

1869 << Stop << "), uses " << BI.FirstInstr << '-'

1870 << BI.LastInstr << ", reg-out " << IntvOut

1871 << ", enter after " << EnterAfter

1872 << (BI.LiveIn ? ", stack-in" : ", defined in block"));

1873

1874 SlotIndex LSP = SA.getLastSplitPoint(BI.MBB);

1875

1876 assert(IntvOut && "Must have register out");

1878 assert((!EnterAfter || EnterAfter < LSP) && "Bad interference");

1879

1880 if (!BI.LiveIn && (!EnterAfter || EnterAfter <= BI.FirstInstr)) {

1882

1883

1884

1885

1886

1889 return;

1890 }

1891

1893 LLVM_DEBUG(dbgs() << ", reload after interference.\n");

1894

1895

1896

1897

1898

1902 assert((!EnterAfter || Idx >= EnterAfter) && "Interference");

1903 return;

1904 }

1905

1906

1907

1908

1909 LLVM_DEBUG(dbgs() << ", interference overlaps uses.\n");

1910

1911

1912

1913

1914

1918 assert((!EnterAfter || Idx >= EnterAfter) && "Interference");

1919

1923}

1924

1928 << "1st def " << FirstDef << ", "

1929 << (LiveIn ? "live in" : "dead in") << ", "

1930 << (LiveOut ? "live out" : "dead out") << "}";

1931}

1932

1935 dbgs() << "\n";

1936}

unsigned const MachineRegisterInfo * MRI

MachineInstrBuilder & UseMI

MachineInstrBuilder MachineInstrBuilder & DefMI

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

MachineBasicBlock MachineBasicBlock::iterator MBBI

This file defines the BumpPtrAllocator interface.

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

static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")

#define LLVM_DUMP_METHOD

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

Promote Memory to Register

SI Optimize VGPR LiveRange

LiveInterval::SubRange & getSubRangeForMaskExact(LaneBitmask LM, LiveInterval &LI)

Definition SplitKit.cpp:405

static bool removeDeadSegment(SlotIndex Def, LiveRange &LR)

Definition SplitKit.cpp:1278

auto & getSubrangeImpl(LaneBitmask LM, T &LI)

Find a subrange corresponding to the exact lane mask LM in the live interval LI.

Definition SplitKit.cpp:398

const LiveInterval::SubRange & getSubRangeForMask(LaneBitmask LM, const LiveInterval &LI)

Find a subrange corresponding to the lane mask LM, or a superset of it, in the live interval LI.

Definition SplitKit.cpp:419

static bool hasTiedUseOf(MachineInstr &MI, Register Reg)

Definition SplitKit.cpp:852

static cl::opt< bool > EnableLoopIVHeuristic("enable-split-loopiv-heuristic", cl::desc("Enable loop iv regalloc heuristic"), cl::init(true))

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

#define STATISTIC(VARNAME, DESC)

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

void resize(unsigned N, bool t=false)

resize - Grow or shrink the bitvector.

ConnectedVNInfoEqClasses - Helper class that can divide VNInfos in a LiveInterval into equivalence cl...

Implements a dense probed hash-table based set.

DomTreeNodeBase * getIDom() const

MachineBasicBlock::iterator getLastInsertPointIter(const LiveInterval &CurLI, MachineBasicBlock &MBB)

Returns the last insert point as an iterator for \pCurLI in \pMBB.

Definition SplitKit.cpp:142

SlotIndex getLastInsertPoint(const LiveInterval &CurLI, const MachineBasicBlock &MBB)

Return the base index of the last valid insert point for \pCurLI in \pMBB.

InsertPointAnalysis(const LiveIntervals &lis, unsigned BBNum)

Definition SplitKit.cpp:61

A live range for subregisters.

LiveInterval - This class represents the liveness of a register, or stack slot.

LLVM_ABI void removeEmptySubRanges()

Removes all subranges without any segments (subranges without segments are not considered valid and s...

bool hasSubRanges() const

Returns true if subregister liveness information is available.

iterator_range< subrange_iterator > subranges()

LLVM_ABI void refineSubRanges(BumpPtrAllocator &Allocator, LaneBitmask LaneMask, std::function< void(LiveInterval::SubRange &)> Apply, const SlotIndexes &Indexes, const TargetRegisterInfo &TRI, unsigned ComposeSubRegIdx=0)

Refines the subranges to support LaneMask.

LLVM_ABI void computeSubRangeUndefs(SmallVectorImpl< SlotIndex > &Undefs, LaneBitmask LaneMask, const MachineRegisterInfo &MRI, const SlotIndexes &Indexes) const

For a given lane mask LaneMask, compute indexes at which the lane is marked undefined by subregister ...

MachineInstr * getInstructionFromIndex(SlotIndex index) const

Returns the instruction associated with the given index.

SlotIndexes * getSlotIndexes() const

SlotIndex getInstructionIndex(const MachineInstr &Instr) const

Returns the base index of the given instruction.

void RemoveMachineInstrFromMaps(MachineInstr &MI)

SlotIndex getMBBEndIdx(const MachineBasicBlock *mbb) const

Return the last index in the given basic block.

LiveInterval & getInterval(Register Reg)

LLVM_ABI void removeVRegDefAt(LiveInterval &LI, SlotIndex Pos)

Remove value number and related live segments of LI and its subranges that start at position Pos.

MachineBasicBlock * getMBBFromIndex(SlotIndex index) const

void addLiveInBlock(LiveRange &LR, MachineDomTreeNode *DomNode, SlotIndex Kill=SlotIndex())

addLiveInBlock - Add a block with an unknown live-in value.

LLVM_ABI void reset(const MachineFunction *mf, SlotIndexes *SI, MachineDominatorTree *MDT, VNInfo::Allocator *VNIA)

reset - Prepare caches for a new set of non-overlapping live ranges.

LLVM_ABI void extend(LiveRange &LR, SlotIndex Use, Register PhysReg, ArrayRef< SlotIndex > Undefs)

Extend the live range of LR to reach Use.

void setLiveOutValue(MachineBasicBlock *MBB, VNInfo *VNI)

setLiveOutValue - Indicate that VNI is live out from MBB.

This class represents the liveness of a register, stack slot, etc.

VNInfo * getValNumInfo(unsigned ValNo)

getValNumInfo - Returns pointer to the specified val#.

LLVM_ABI iterator addSegment(Segment S)

Add the specified Segment to this range, merging segments as appropriate.

Segments::iterator iterator

const Segment * getSegmentContaining(SlotIndex Idx) const

Return the segment that contains the specified index, or null if there is none.

Segments::const_iterator const_iterator

bool liveAt(SlotIndex index) const

LLVM_ABI VNInfo * createDeadDef(SlotIndex Def, VNInfo::Allocator &VNIAlloc)

createDeadDef - Make sure the range has a value defined at Def.

iterator advanceTo(iterator I, SlotIndex Pos)

advanceTo - Advance the specified iterator to point to the Segment containing the specified position,...

LLVM_ABI void RenumberValues()

RenumberValues - Renumber all values in order of appearance and remove unused values.

VNInfo * getVNInfoBefore(SlotIndex Idx) const

getVNInfoBefore - Return the VNInfo that is live up to but not necessarily including Idx,...

LLVM_ABI std::pair< VNInfo *, bool > extendInBlock(ArrayRef< SlotIndex > Undefs, SlotIndex StartIdx, SlotIndex Kill)

Attempt to extend a value defined after StartIdx to include Use.

unsigned getNumValNums() const

VNInfo * getNextValue(SlotIndex Def, VNInfo::Allocator &VNInfoAllocator)

getNextValue - Create a new value number and return it.

LLVM_ABI void removeSegment(SlotIndex Start, SlotIndex End, bool RemoveDeadValNo=false)

Remove the specified interval from this live range.

VNInfo * getVNInfoAt(SlotIndex Idx) const

getVNInfoAt - Return the VNInfo that is live at Idx, or NULL.

LLVM_ABI iterator find(SlotIndex Pos)

find - Return an iterator pointing to the first segment that ends after Pos, or end().

BlockT * getHeader() const

unsigned getLoopDepth() const

Return the nesting level of this loop.

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

MachineInstrBundleIterator< const MachineInstr > const_iterator

LLVM_ABI iterator getFirstTerminator()

Returns an iterator to the first terminator instruction of this basic block.

const MachineFunction * getParent() const

Return the MachineFunction containing this basic block.

iterator_range< pred_iterator > predecessors()

MachineInstrBundleIterator< MachineInstr > iterator

MachineBlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate machine basic b...

DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to compute a normal dominat...

MachineRegisterInfo & getRegInfo()

getRegInfo - Return information about the registers currently in use.

unsigned getNumBlockIDs() const

getNumBlockIDs - Return the number of MBB ID's allocated.

BasicBlockListType::iterator iterator

BasicBlockListType::const_iterator const_iterator

const MachineInstrBuilder & addReg(Register RegNo, unsigned flags=0, unsigned SubReg=0) const

Add a new virtual register operand.

Representation of each machine instruction.

mop_range defs()

Returns all explicit operands that are register definitions.

LLVM_ABI void bundleWithPred()

Bundle this instruction with its predecessor.

LLVM_ABI const TargetRegisterClass * getRegClassConstraintEffectForVReg(Register Reg, const TargetRegisterClass *CurRC, const TargetInstrInfo *TII, const TargetRegisterInfo *TRI, bool ExploreBundle=false) const

Applies the constraints (def/use) implied by this MI on Reg to the given CurRC.

const MachineOperand & getOperand(unsigned i) const

LLVM_ABI const TargetRegisterClass * getRegClassConstraint(unsigned OpIdx, const TargetInstrInfo *TII, const TargetRegisterInfo *TRI) const

Compute the static register class constraint for operand OpIdx.

MachineOperand class - Representation of each machine instruction operand.

getReg - Returns the register number.

MachineRegisterInfo - Keep track of information for virtual and physical registers,...

Wrapper class representing virtual and physical registers.

SlotIndex - An opaque wrapper around machine indexes.

static bool isSameInstr(SlotIndex A, SlotIndex B)

isSameInstr - Return true if A and B refer to the same instruction.

SlotIndex getDeadSlot() const

Returns the dead def kill slot for the current instruction.

static bool isEarlierInstr(SlotIndex A, SlotIndex B)

isEarlierInstr - Return true if A refers to an instruction earlier than B.

bool isValid() const

Returns true if this is a valid index.

SlotIndex getBoundaryIndex() const

Returns the boundary index for associated with this index.

SlotIndex getBaseIndex() const

Returns the base index for associated with this index.

SlotIndex getNextSlot() const

Returns the next slot in the index list.

SlotIndex getPrevSlot() const

Returns the previous slot in the index list.

SlotIndex getRegSlot(bool EC=false) const

Returns the register use/def slot in the current instruction for a normal or early-clobber def.

SlotIndex insertMachineInstrInMaps(MachineInstr &MI, bool Late=false)

Insert the given machine instruction into the mapping.

MachineBasicBlock * getMBBFromIndex(SlotIndex index) const

Returns the basic block which the given index falls in.

const std::pair< SlotIndex, SlotIndex > & getMBBRange(unsigned Num) const

Return the (start,end) range of the given basic block number.

SlotIndex getMBBEndIdx(unsigned Num) const

Returns the index past the last valid index in the given basic block.

size_type count(ConstPtrType Ptr) const

count - Return 1 if the specified pointer is in the set, 0 otherwise.

std::pair< iterator, bool > insert(PtrType Ptr)

Inserts Ptr if and only if there is no element in the container equal to Ptr.

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

void assign(size_type NumElts, ValueParamT Elt)

typename SuperClass::const_iterator const_iterator

void push_back(const T &Elt)

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

SplitAnalysis - Analyze a LiveInterval, looking for live range splitting opportunities.

SplitAnalysis(const VirtRegMap &vrm, const LiveIntervals &lis, const MachineLoopInfo &mli)

Definition SplitKit.cpp:154

const MachineFunction & MF

bool isOriginalEndpoint(SlotIndex Idx) const

isOriginalEndpoint - Return true if the original live range was killed or (re-)defined at Idx.

Definition SplitKit.cpp:333

unsigned countLiveBlocks(const LiveInterval *li) const

countLiveBlocks - Return the number of blocks where li is live.

Definition SplitKit.cpp:309

const LiveIntervals & LIS

void analyze(const LiveInterval *li)

analyze - set CurLI to the specified interval, and analyze how it may be split.

Definition SplitKit.cpp:347

void clear()

clear - clear all data structures so SplitAnalysis is ready to analyze a new interval.

Definition SplitKit.cpp:159

const MachineLoopInfo & Loops

const TargetInstrInfo & TII

unsigned getNumLiveBlocks() const

getNumLiveBlocks - Return the number of blocks where CurLI is live.

bool shouldSplitSingleBlock(const BlockInfo &BI, bool SingleInstrs) const

shouldSplitSingleBlock - Returns true if it would help to create a local live range for the instructi...

Definition SplitKit.cpp:1621

void overlapIntv(SlotIndex Start, SlotIndex End)

overlapIntv - Indicate that all instructions in range should use the open interval if End does not ha...

Definition SplitKit.cpp:858

unsigned openIntv()

Create a new virtual register and live interval.

Definition SplitKit.cpp:680

SplitEditor(SplitAnalysis &SA, LiveIntervals &LIS, VirtRegMap &VRM, MachineDominatorTree &MDT, MachineBlockFrequencyInfo &MBFI, VirtRegAuxInfo &VRAI)

Create a new SplitEditor for editing the LiveInterval analyzed by SA.

Definition SplitKit.cpp:358

void splitRegOutBlock(const SplitAnalysis::BlockInfo &BI, unsigned IntvOut, SlotIndex EnterAfter)

splitRegOutBlock - Split CurLI in the given block such that it enters the block on the stack (or isn'...

Definition SplitKit.cpp:1863

SlotIndex enterIntvAfter(SlotIndex Idx)

enterIntvAfter - Enter the open interval after the instruction at Idx.

Definition SplitKit.cpp:715

SlotIndex enterIntvBefore(SlotIndex Idx)

enterIntvBefore - Enter the open interval before the instruction at Idx.

Definition SplitKit.cpp:698

void useIntv(const MachineBasicBlock &MBB)

useIntv - indicate that all instructions in MBB should use OpenLI.

Definition SplitKit.cpp:770

SlotIndex leaveIntvAfter(SlotIndex Idx)

leaveIntvAfter - Leave the open interval after the instruction at Idx.

Definition SplitKit.cpp:781

void reset(LiveRangeEdit &, ComplementSpillMode=SM_Partition)

reset - Prepare for a new split.

Definition SplitKit.cpp:366

SlotIndex enterIntvAtEnd(MachineBasicBlock &MBB)

enterIntvAtEnd - Enter the open interval at the end of MBB.

Definition SplitKit.cpp:733

SlotIndex leaveIntvAtTop(MachineBasicBlock &MBB)

leaveIntvAtTop - Leave the interval at the top of MBB.

Definition SplitKit.cpp:831

SlotIndex leaveIntvBefore(SlotIndex Idx)

leaveIntvBefore - Leave the open interval before the instruction at Idx.

Definition SplitKit.cpp:812

void finish(SmallVectorImpl< unsigned > *LRMap=nullptr)

finish - after all the new live ranges have been created, compute the remaining live range,...

Definition SplitKit.cpp:1536

void splitRegInBlock(const SplitAnalysis::BlockInfo &BI, unsigned IntvIn, SlotIndex LeaveBefore)

splitRegInBlock - Split CurLI in the given block such that it enters the block in IntvIn and leaves i...

Definition SplitKit.cpp:1770

void splitLiveThroughBlock(unsigned MBBNum, unsigned IntvIn, SlotIndex LeaveBefore, unsigned IntvOut, SlotIndex EnterAfter)

splitLiveThroughBlock - Split CurLI in the given block such that it enters the block in IntvIn and le...

Definition SplitKit.cpp:1667

ComplementSpillMode

ComplementSpillMode - Select how the complement live range should be created.

@ SM_Partition

SM_Partition(Default) - Try to create the complement interval so it doesn't overlap any other interva...

@ SM_Speed

SM_Speed - Overlap intervals to minimize the expected execution frequency of the inserted copies.

@ SM_Size

SM_Size - Overlap intervals to minimize the number of inserted COPY instructions.

void selectIntv(unsigned Idx)

selectIntv - Select a previously opened interval index.

Definition SplitKit.cpp:691

void splitSingleBlock(const SplitAnalysis::BlockInfo &BI)

splitSingleBlock - Split CurLI into a separate live interval around the uses in a single block.

Definition SplitKit.cpp:1641

void dump() const

dump - print the current interval mapping to dbgs().

Definition SplitKit.cpp:382

bool hasSubClass(const TargetRegisterClass *RC) const

Return true if the specified TargetRegisterClass is a proper sub-class of this TargetRegisterClass.

VNInfo - Value Number Information.

bool isUnused() const

Returns true if this value is unused.

unsigned id

The ID number of this value.

SlotIndex def

The index of the defining instruction.

bool isPHIDef() const

Returns true if this value is defined by a PHI instruction (or was, PHI instructions may have been el...

Calculate auxiliary information for a virtual register such as its spill weight and allocation hint.

std::pair< iterator, bool > insert(const ValueT &V)

size_type count(const_arg_type_t< ValueT > V) const

Return 1 if the specified key is in the set, 0 otherwise.

self_iterator getIterator()

This class implements an extremely fast bulk output stream that can only output to a stream.

#define llvm_unreachable(msg)

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

@ C

The default llvm calling convention, compatible with C.

@ Define

@ Skipped

Validation was skipped, as it was not needed.

initializer< Ty > init(const Ty &Val)

NodeAddr< DefNode * > Def

This is an optimization pass for GlobalISel generic memory operations.

Printable print(const GCNRegPressure &RP, const GCNSubtarget *ST=nullptr, unsigned DynamicVGPRBlockSize=0)

auto size(R &&Range, std::enable_if_t< std::is_base_of< std::random_access_iterator_tag, typename std::iterator_traits< decltype(Range.begin())>::iterator_category >::value, void > *=nullptr)

Get the size of a range.

MachineInstrBuilder BuildMI(MachineFunction &MF, const MIMetadata &MIMD, const MCInstrDesc &MCID)

Builder interface. Specify how to create the initial instruction itself.

void append_range(Container &C, Range &&R)

Wrapper function to append range R to container C.

iterator_range< early_inc_iterator_impl< detail::IterOfRange< RangeT > > > make_early_inc_range(RangeT &&Range)

Make a range that does early increment to allow mutation of the underlying range without disrupting i...

auto unique(Range &&R, Predicate P)

bool any_of(R &&range, UnaryPredicate P)

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

auto reverse(ContainerTy &&C)

LLVM_ABI raw_ostream & dbgs()

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

bool none_of(R &&Range, UnaryPredicate P)

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

LLVM_ABI void report_fatal_error(Error Err, bool gen_crash_diag=true)

unsigned getInternalReadRegState(bool B)

FunctionAddr VTableAddr Count

class LLVM_GSL_OWNER SmallVector

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

DomTreeNodeBase< MachineBasicBlock > MachineDomTreeNode

unsigned getUndefRegState(bool B)

@ Sub

Subtraction of integers.

FunctionAddr VTableAddr Next

auto seq(T Begin, T End)

Iterate over an integral type from Begin up to - but not including - End.

void array_pod_sort(IteratorTy Start, IteratorTy End)

array_pod_sort - This sorts an array with the specified start and end extent.

BumpPtrAllocatorImpl<> BumpPtrAllocator

The standard BumpPtrAllocator which just uses the default template parameters.

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.

static constexpr LaneBitmask getAll()

constexpr bool none() const

constexpr bool all() const

static constexpr LaneBitmask getNone()

This represents a simple continuous liveness interval for a value.

Additional information about basic blocks where the current variable is live.

SlotIndex FirstDef

First non-phi valno->def, or SlotIndex().

bool LiveOut

Current reg is live out.

bool LiveIn

Current reg is live in.

bool isOneInstr() const

isOneInstr - Returns true when this BlockInfo describes a single instruction.

void print(raw_ostream &OS) const

Definition SplitKit.cpp:1925

SlotIndex LastInstr

Last instr accessing current reg.

void dump() const

Definition SplitKit.cpp:1933

SlotIndex FirstInstr

First instr accessing current reg.