LiveInterval.cpp Source File (original) (raw)

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

40#include

41#include

42#include

43#include

44#include

46using namespace llvm;

48namespace {

64template <typename ImplT, typename IteratorT, typename CollectionT>

65class CalcLiveRangeUtilBase {

66protected:

69protected:

70 CalcLiveRangeUtilBase(LiveRange *LR) : LR(LR) {}

72public:

73 using Segment = LiveRange::Segment;

88 VNInfo *ForVNI) {

89 assert( Def .isDead() && "Cannot define a value at the dead slot");

90 assert((!ForVNI || ForVNI->def == Def) &&

91 "If ForVNI is specified, it must match Def");

92 iterator I = impl().find(Def);

93 if (I == segments().end()) {

94 VNInfo *VNI = ForVNI ? ForVNI : LR->getNextValue(Def, *VNInfoAllocator);

95 impl().insertAtEnd(Segment(Def, Def.getDeadSlot(), VNI));

96 return VNI;

97 }

99 Segment *S = segmentAt(I);

101 assert((!ForVNI || ForVNI == S->valno) && "Value number mismatch");

102 assert(S->valno->def == S->start && "Inconsistent existing value def");

103

104

105

106

107

108

109 Def = std::min(Def, S->start);

110 if (Def != S->start)

111 S->start = S->valno->def = Def;

112 return S->valno;

113 }

115 VNInfo *VNI = ForVNI ? ForVNI : LR->getNextValue(Def, *VNInfoAllocator);

116 segments().insert(I, Segment(Def, Def.getDeadSlot(), VNI));

117 return VNI;

118 }

119

120 VNInfo *extendInBlock(SlotIndex StartIdx, SlotIndex Use) {

121 if (segments().empty())

122 return nullptr;

123 iterator I =

124 impl().findInsertPos(Segment(Use.getPrevSlot(), Use, nullptr));

125 if (I == segments().begin())

126 return nullptr;

127 --I;

128 if (I->end <= StartIdx)

129 return nullptr;

130 if (I->end < Use)

131 extendSegmentEndTo(I, Use);

132 return I->valno;

133 }

134

136 SlotIndex StartIdx, SlotIndex Use) {

137 if (segments().empty())

138 return std::make_pair(nullptr, false);

139 SlotIndex BeforeUse = Use.getPrevSlot();

140 iterator I = impl().findInsertPos(Segment(BeforeUse, Use, nullptr));

141 if (I == segments().begin())

142 return std::make_pair(nullptr, LR->isUndefIn(Undefs, StartIdx, BeforeUse));

143 --I;

144 if (I->end <= StartIdx)

145 return std::make_pair(nullptr, LR->isUndefIn(Undefs, StartIdx, BeforeUse));

146 if (I->end < Use) {

147 if (LR->isUndefIn(Undefs, I->end, BeforeUse))

148 return std::make_pair(nullptr, true);

149 extendSegmentEndTo(I, Use);

150 }

151 return std::make_pair(I->valno, false);

152 }

153

154

155

156

157

158 void extendSegmentEndTo(iterator I, SlotIndex NewEnd) {

159 assert(I != segments().end() && "Not a valid segment!");

160 Segment *S = segmentAt(I);

161 VNInfo *ValNo = I->valno;

162

163

164 iterator MergeTo = std::next(I);

165 for (; MergeTo != segments().end() && NewEnd >= MergeTo->end; ++MergeTo)

166 assert(MergeTo->valno == ValNo && "Cannot merge with differing values!");

167

168

169 S->end = std::max(NewEnd, std::prev(MergeTo)->end);

170

171

172

173 if (MergeTo != segments().end() && MergeTo->start <= I->end &&

174 MergeTo->valno == ValNo) {

175 S->end = MergeTo->end;

176 ++MergeTo;

177 }

178

179

180 segments().erase(std::next(I), MergeTo);

181 }

182

183

184

185

186 iterator extendSegmentStartTo(iterator I, SlotIndex NewStart) {

187 assert(I != segments().end() && "Not a valid segment!");

188 Segment *S = segmentAt(I);

189 VNInfo *ValNo = I->valno;

190

191

192 iterator MergeTo = I;

193 do {

194 if (MergeTo == segments().begin()) {

195 S->start = NewStart;

196 segments().erase(MergeTo, I);

197 return I;

198 }

199 assert(MergeTo->valno == ValNo && "Cannot merge with differing values!");

200 --MergeTo;

201 } while (NewStart <= MergeTo->start);

202

203

204

205 if (MergeTo->end >= NewStart && MergeTo->valno == ValNo) {

206 segmentAt(MergeTo)->end = S->end;

207 } else {

208

209 ++MergeTo;

210 Segment *MergeToSeg = segmentAt(MergeTo);

211 MergeToSeg->start = NewStart;

212 MergeToSeg->end = S->end;

213 }

214

215 segments().erase(std::next(MergeTo), std::next(I));

216 return MergeTo;

217 }

218

219 iterator addSegment(Segment S) {

220 SlotIndex Start = S.start, End = S.end;

221 iterator I = impl().findInsertPos(S);

222

223

224

225 if (I != segments().begin()) {

226 iterator B = std::prev(I);

227 if (S.valno == B->valno) {

228 if (B->start <= Start && B->end >= Start) {

229 extendSegmentEndTo(B, End);

230 return B;

231 }

232 } else {

233

234

235 assert(B->end <= Start &&

236 "Cannot overlap two segments with differing ValID's"

237 " (did you def the same reg twice in a MachineInstr?)");

238 }

239 }

240

241

242

243 if (I != segments().end()) {

244 if (S.valno == I->valno) {

245 if (I->start <= End) {

246 I = extendSegmentStartTo(I, Start);

247

248

249

250 if (End > I->end)

251 extendSegmentEndTo(I, End);

252 return I;

253 }

254 } else {

255

256

257 assert(I->start >= End &&

258 "Cannot overlap two segments with differing ValID's");

259 }

260 }

261

262

263

264

265 return segments().insert(I, S);

266 }

267

268private:

269 ImplT &impl() { return *static_cast<ImplT *>(this); }

270

271 CollectionT &segments() { return impl().segmentsColl(); }

272

273 Segment *segmentAt(iterator I) { return const_cast<Segment *>(&(*I)); }

274};

275

276

277

278

279

280

281class CalcLiveRangeUtilVector;

282using CalcLiveRangeUtilVectorBase =

285

286class CalcLiveRangeUtilVector : public CalcLiveRangeUtilVectorBase {

287public:

288 CalcLiveRangeUtilVector(LiveRange *LR) : CalcLiveRangeUtilVectorBase(LR) {}

289

290private:

291 friend CalcLiveRangeUtilVectorBase;

292

293 LiveRange::Segments &segmentsColl() { return LR->segments; }

294

295 void insertAtEnd(const Segment &S) { LR->segments.push_back(S); }

296

298

300};

301

302

303

304

305

306

307class CalcLiveRangeUtilSet;

308using CalcLiveRangeUtilSetBase =

309 CalcLiveRangeUtilBase<CalcLiveRangeUtilSet, LiveRange::SegmentSet::iterator,

311

312class CalcLiveRangeUtilSet : public CalcLiveRangeUtilSetBase {

313public:

314 CalcLiveRangeUtilSet(LiveRange *LR) : CalcLiveRangeUtilSetBase(LR) {}

315

316private:

317 friend CalcLiveRangeUtilSetBase;

318

319 LiveRange::SegmentSet &segmentsColl() { return *LR->segmentSet; }

320

321 void insertAtEnd(const Segment &S) {

323 }

324

329 return I;

331 if (Pos < (*PrevI).end)

332 return PrevI;

333 return I;

334 }

335

338 if (I != LR->segmentSet->end() && !(S.start < *I))

339 ++I;

340 return I;

341 }

342};

343

344}

345

346

347

348

349

352 [&](const Segment &X) { return X.end <= Pos; });

353}

354

356

358 return CalcLiveRangeUtilSet(this).createDeadDef(Def, &VNIAlloc, nullptr);

359

360 return CalcLiveRangeUtilVector(this).createDeadDef(Def, &VNIAlloc, nullptr);

361}

362

364

366 return CalcLiveRangeUtilSet(this).createDeadDef(VNI->def, nullptr, VNI);

367

368 return CalcLiveRangeUtilVector(this).createDeadDef(VNI->def, nullptr, VNI);

369}

370

371

372

373

374

375

376

377

378

379

380

381

382

383

384

385

386

387

388

396

397 assert((StartPos->start <= i->start || StartPos == other.begin()) &&

398 StartPos != other.end() && "Bogus start position hint!");

399

400 if (i->start < j->start) {

401 i = std::upper_bound(i, ie, j->start);

402 if (i != begin()) --i;

403 } else if (j->start < i->start) {

404 ++StartPos;

405 if (StartPos != other.end() && StartPos->start <= i->start) {

407 j = std::upper_bound(j, je, i->start);

408 if (j != other.begin()) --j;

409 }

410 } else {

411 return true;

412 }

413

414 if (j == je) return false;

415

416 while (i != ie) {

417 if (i->start > j->start) {

420 }

421

422 if (i->end > j->start)

423 return true;

424 ++i;

425 }

426

427 return false;

428}

429

433 if (Other.empty())

434 return false;

435

436

439 if (I == IE)

440 return false;

443 if (J == JE)

444 return false;

445

446 while (true) {

447

448 assert(J->end > I->start);

449

450 if (J->start < I->end) {

451

452 SlotIndex Def = std::max(I->start, J->start);

453

454 if (Def.isBlock() ||

456 return true;

457 }

458

459 if (J->end > I->end) {

462 }

463

464 do

465 if (++J == JE)

466 return false;

467 while (J->end <= I->start);

468 }

469}

470

471

472

474 assert(Start < End && "Invalid range");

476 return I != begin() && (--I)->end > Start;

477}

478

481 return Other.empty();

482

486 if (I == end() || I->start > O.start)

487 return false;

488

489

490 while (I->end < O.end) {

492

493 ++I;

494 if (I == end() || Last->end != I->start)

495 return false;

496 }

497 }

498 return true;

499}

500

501

502

503

504void LiveRange::markValNoForDeletion(VNInfo *ValNo) {

506 do {

509 } else {

511 }

512}

513

514

515

520 VNInfo *VNI = S.valno;

521 if (!Seen.insert(VNI).second)

522 continue;

523 assert(!VNI->isUnused() && "Unused valno used by live segment");

525 valnos.push_back(VNI);

526 }

527}

528

529void LiveRange::addSegmentToSet(Segment S) {

530 CalcLiveRangeUtilSet(this).addSegment(S);

531}

532

534

536 addSegmentToSet(S);

537 return end();

538 }

539

540 return CalcLiveRangeUtilVector(this).addSegment(S);

541}

542

548

551

553 return CalcLiveRangeUtilSet(this).extendInBlock(Undefs, StartIdx, Kill);

554

555 return CalcLiveRangeUtilVector(this).extendInBlock(Undefs, StartIdx, Kill);

556}

557

559

561 return CalcLiveRangeUtilSet(this).extendInBlock(StartIdx, Kill);

562

563 return CalcLiveRangeUtilVector(this).extendInBlock(StartIdx, Kill);

564}

565

567 bool RemoveDeadValNo) {

568

570

571

572 if (I == end())

573 return;

574

575 assert(I->containsInterval(Start, End)

576 && "Segment is not entirely in range!");

577

578

579 VNInfo *ValNo = I->valno;

580 if (I->start == Start) {

581 if (I->end == End) {

582 segments.erase(I);

583

584 if (RemoveDeadValNo)

586 } else

587 I->start = End;

588 return;

589 }

590

591

592

593 if (I->end == End) {

594 I->end = Start;

595 return;

596 }

597

598

600 I->end = Start;

601

602

604}

605

607 VNInfo *ValNo = I->valno;

609 if (RemoveDeadValNo)

611 return I;

612}

613

616 markValNoForDeletion(ValNo);

617}

618

619

620

622 if (empty()) return;

624 [ValNo](const Segment &S) { return S.valno == ValNo; });

625

626 markValNoForDeletion(ValNo);

627}

628

630 const int *LHSValNoAssignments,

631 const int *RHSValNoAssignments,

635

636

637

638 bool MustMapCurValNos = false;

640 unsigned NumNewVals = NewVNInfo.size();

641 for (unsigned i = 0; i != NumVals; ++i) {

642 unsigned LHSValID = LHSValNoAssignments[i];

643 if (i != LHSValID ||

644 (NewVNInfo[LHSValID] && NewVNInfo[LHSValID] != getValNumInfo(i))) {

645 MustMapCurValNos = true;

646 break;

647 }

648 }

649

650

651 if (MustMapCurValNos && empty ()) {

652

653

655 OutIt->valno = NewVNInfo[LHSValNoAssignments[OutIt->valno->id]];

656 for (iterator I = std::next(OutIt), E = end(); I != E; ++I) {

657 VNInfo* nextValNo = NewVNInfo[LHSValNoAssignments[I->valno->id]];

658 assert(nextValNo && "Huh?");

659

660

661

662

663 if (OutIt->valno == nextValNo && OutIt->end == I->start) {

664 OutIt->end = I->end;

665 } else {

666

667 ++OutIt;

668 OutIt->valno = nextValNo;

669 if (OutIt != I) {

670 OutIt->start = I->start;

671 OutIt->end = I->end;

672 }

673 }

674 }

675

676 ++OutIt;

678 }

679

680

681

682

683

685 S.valno = NewVNInfo[RHSValNoAssignments[S.valno->id]];

686

687

688

689 unsigned NumValNos = 0;

690 for (unsigned i = 0; i < NumNewVals; ++i) {

691 VNInfo *VNI = NewVNInfo[i];

692 if (VNI) {

693 if (NumValNos >= NumVals)

694 valnos.push_back(VNI);

695 else

696 valnos[NumValNos] = VNI;

697 VNI->id = NumValNos++;

698 }

699 }

700 if (NumNewVals < NumVals)

701 valnos.resize(NumNewVals);

702

703

706 Updater.add(S);

707}

708

709

710

711

712

716 for (const Segment &S : RHS.segments)

718}

719

720

721

722

723

724

726 const VNInfo *RHSValNo,

729 for (const Segment &S : RHS.segments)

730 if (S.valno == RHSValNo)

732}

733

734

735

736

737

739 assert(V1 != V2 && "Identical value#'s are always equivalent!");

740

741

742

743

744

745

746

747 if (V1->id < V2->id) {

750 }

751

752

755 if (S->valno != V1) continue;

756

757

758

759 if (S != begin()) {

761 if (Prev->valno == V2 && Prev->end == S->start) {

762 Prev->end = S->end;

763

764

766 I = Prev+1;

767 S = Prev;

768 }

769 }

770

771

772

773 S->valno = V2;

774

775

776

777

778 if (I != end()) {

779 if (I->start == S->end && I->valno == V2) {

780 S->end = I->end;

782 I = S+1;

783 }

784 }

785 }

786

787

788 markValNoForDeletion(V1);

789

790 return V2;

791}

792

794 assert(segmentSet != nullptr && "segment set must have been created");

797 "segment set can be used only initially before switching to the array");

801}

802

806

807

808 if (SlotI == SlotE)

809 return false;

810

811

814

815

816 if (SegmentI == SegmentE)

817 return false;

818

819

820 for ( ; SlotI != SlotE; ++SlotI) {

821

822

823 SegmentI = advanceTo(SegmentI, *SlotI);

824 if (SegmentI == SegmentE)

825 return false;

826

827

828 if (SegmentI->contains(*SlotI))

829 return true;

830

831 }

832

833

834 return false;

835}

836

837void LiveInterval::freeSubRange(SubRange *S) {

838 S->~SubRange();

839

840}

841

843 SubRange **NextPtr = &SubRanges;

845 while (I != nullptr) {

846 if (->empty()) {

847 NextPtr = &I->Next;

848 I = *NextPtr;

849 continue;

850 }

851

852 do {

854 freeSubRange(I);

856 } while (I != nullptr && I->empty());

857 *NextPtr = I;

858 }

859}

860

864 freeSubRange(I);

865 }

866 SubRanges = nullptr;

867}

868

869

870

871

876 unsigned ComposeSubRegIdx) {

877

878

879 if ( Reg || Reg .isVirtual())

880 return;

881

885 continue;

886

887

889 continue;

891 assert(MI && "Cannot find the definition of a value");

892 bool hasDef = false;

894 if (!MOI->isReg() || !MOI->isDef())

895 continue;

896 if (MOI->getReg() != Reg)

897 continue;

898 LaneBitmask OrigMask = TRI.getSubRegIndexLaneMask(MOI->getSubReg());

900 ComposeSubRegIdx

901 ? TRI.composeSubRegIndexLaneMask(ComposeSubRegIdx, OrigMask)

902 : OrigMask;

903 if ((ExpectedDefMask & LaneMask).none())

904 continue;

905 hasDef = true;

906 break;

907 }

908

909 if (!hasDef)

911 }

912 for (VNInfo *VNI : ToBeRemoved)

914

915

916

917}

918

923 unsigned ComposeSubRegIdx) {

927 LaneBitmask Matching = SRMask & LaneMask;

928 if (Matching.none())

929 continue;

930

932 if (SRMask == Matching) {

933

934 MatchingRange = &SR;

935 } else {

936

937

938 SR.LaneMask = SRMask & ~Matching;

939

941

942

944 ComposeSubRegIdx);

946 ComposeSubRegIdx);

947 }

948 Apply(*MatchingRange);

949 ToApply &= ~Matching;

950 }

951

952 if (ToApply.any()) {

954 Apply(*NewRange);

955 }

956}

957

959 unsigned Sum = 0;

961 Sum += S.start.distance(S.end);

962 return Sum;

963}

964

971 assert((VRegMask & LaneMask).any());

974 if (!MO.isUndef())

975 continue;

976 unsigned SubReg = MO.getSubReg();

977 assert(SubReg != 0 && "Undef should only be set on subreg defs");

979 LaneBitmask UndefMask = VRegMask & ~DefMask;

980 if ((UndefMask & LaneMask).any()) {

982 bool EarlyClobber = MO.isEarlyClobber();

985 }

986 }

987}

988

990 return OS << '[' << S.start << ',' << S.end << ':' << S.valno->id << ')';

991}

992

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

995 dbgs() << *this << '\n';

996}

997#endif

998

1000 OS << id << '@';

1002 OS << 'x';

1003 } else {

1004 OS << def;

1006 OS << "-phi";

1007 }

1008}

1009

1012 OS << "EMPTY";

1013 else {

1015 OS << S;

1017 }

1018 }

1019

1020

1022 OS << ' ';

1023 unsigned vnum = 0;

1025 ++i, ++vnum) {

1026 const VNInfo *vni = *i;

1027 if (vnum)

1028 OS << ' ';

1029 OS << *vni;

1030 assert(vnum == vni->id && "Bad VNInfo");

1031 }

1032 }

1033}

1034

1037 << static_cast<const LiveRange &>(*this);

1038}

1039

1043

1045 OS << SR;

1046 OS << " weight:" << Weight;

1047}

1048

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

1051

1053

1055 dbgs() << *this << '\n';

1056}

1057

1059 dbgs() << *this << '\n';

1060}

1061#endif

1062

1063#ifndef NDEBUG

1066 if (->start.isValid())

1067 return false;

1068 if (->end.isValid())

1069 return false;

1070 if (I->start >= I->end)

1071 return false;

1072 if (I->valno == nullptr)

1073 return false;

1074 if (I->valno->id >= valnos.size())

1075 return false;

1076 if (I->valno != valnos[I->valno->id])

1077 return false;

1078 if (std::next(I) != E) {

1079 if (I->end > std::next(I)->start)

1080 return false;

1081 if (I->end == std::next(I)->start) {

1082 if (I->valno == std::next(I)->valno)

1083 return false;

1084 }

1085 }

1086 }

1087

1088 return true;

1089}

1090

1093 return false;

1094

1095

1100

1101 if ((Mask & SR.LaneMask).any())

1102 return false;

1103

1104 Mask |= SR.LaneMask;

1105

1106

1107 if ((Mask & ~MaxMask).any())

1108 return false;

1109

1110

1111 if (SR.empty())

1112 return false;

1113

1114 if (!SR.verify())

1115 return false;

1116

1117

1119 return false;

1120 }

1121

1122 return true;

1123}

1124#endif

1125

1126

1127

1128

1129

1130

1131

1132

1133

1134

1135

1136

1137

1138

1139

1140

1141

1142

1143

1144

1145

1146

1147

1148

1149

1150

1151

1152

1153

1154

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

1158 if (LR)

1159 OS << "Clean updater: " << *LR << '\n';

1160 else

1161 OS << "Null updater.\n";

1162 return;

1163 }

1164 assert(LR && "Can't have null LR in dirty updater.");

1165 OS << " updater with gap = " << (ReadI - WriteI)

1166 << ", last start = " << LastStart

1167 << ":\n Area 1:";

1168 for (const auto &S : make_range(LR->begin(), WriteI))

1169 OS << ' ' << S;

1170 OS << "\n Spills:";

1172 OS << ' ' << Spill;

1173 OS << "\n Area 2:";

1174 for (const auto &S : make_range(ReadI, LR->end()))

1175 OS << ' ' << S;

1176 OS << '\n';

1177}

1178

1182#endif

1183

1184

1187 assert(A.start <= B.start && "Unordered live segments.");

1188 if (A.end == B.start)

1189 return A.valno == B.valno;

1190 if (A.end < B.start)

1191 return false;

1192 assert(A.valno == B.valno && "Cannot overlap different values");

1193 return true;

1194}

1195

1197 assert(LR && "Cannot add to a null destination");

1198

1199

1200

1201 if (LR->segmentSet != nullptr) {

1202 LR->addSegmentToSet(Seg);

1203 return;

1204 }

1205

1206

1207 if (!LastStart.isValid() || LastStart > Seg.start) {

1210

1211 assert(Spills.empty() && "Leftover spilled segments");

1212 WriteI = ReadI = LR->begin();

1213 }

1214

1215

1216 LastStart = Seg.start;

1217

1218

1220 if (ReadI != E && ReadI->end <= Seg.start) {

1221

1222 if (ReadI != WriteI)

1223 mergeSpills();

1224

1225 if (ReadI == WriteI)

1226 ReadI = WriteI = LR->find(Seg.start);

1227 else

1228 while (ReadI != E && ReadI->end <= Seg.start)

1229 *WriteI++ = *ReadI++;

1230 }

1231

1232 assert(ReadI == E || ReadI->end > Seg.start);

1233

1234

1235 if (ReadI != E && ReadI->start <= Seg.start) {

1236 assert(ReadI->valno == Seg.valno && "Cannot overlap different values");

1237

1238 if (ReadI->end >= Seg.end)

1239 return;

1240

1241 Seg.start = ReadI->start;

1242 ++ReadI;

1243 }

1244

1245

1246 while (ReadI != E && coalescable(Seg, *ReadI)) {

1247 Seg.end = std::max(Seg.end, ReadI->end);

1248 ++ReadI;

1249 }

1250

1251

1252 if (!Spills.empty() && coalescable(Spills.back(), Seg)) {

1253 Seg.start = Spills.back().start;

1254 Seg.end = std::max(Spills.back().end, Seg.end);

1255 Spills.pop_back();

1256 }

1257

1258

1259 if (WriteI != LR->begin() && coalescable(WriteI[-1], Seg)) {

1260 WriteI[-1].end = std::max(WriteI[-1].end, Seg.end);

1261 return;

1262 }

1263

1264

1265 if (WriteI != ReadI) {

1266 *WriteI++ = Seg;

1267 return;

1268 }

1269

1270

1271 if (WriteI == E) {

1272 LR->segments.push_back(Seg);

1273 WriteI = ReadI = LR->end();

1274 } else

1275 Spills.push_back(Seg);

1276}

1277

1278

1279

1280void LiveRangeUpdater::mergeSpills() {

1281

1282 size_t GapSize = ReadI - WriteI;

1283 size_t NumMoved = std::min(Spills.size(), GapSize);

1288

1289

1290 WriteI = Dst;

1291

1292

1293 while (Src != Dst) {

1294 if (Src != B && Src[-1].start > SpillSrc[-1].start)

1295 *--Dst = *--Src;

1296 else

1297 *--Dst = *--SpillSrc;

1298 }

1299 assert(NumMoved == size_t(Spills.end() - SpillSrc));

1300 Spills.erase(SpillSrc, Spills.end());

1301}

1302

1305 return;

1306

1308

1309 assert(LR && "Cannot add to a null destination");

1310

1311

1312 if (Spills.empty()) {

1313 LR->segments.erase(WriteI, ReadI);

1314 assert(LR->verify());

1315 return;

1316 }

1317

1318

1319 size_t GapSize = ReadI - WriteI;

1320 if (GapSize < Spills.size()) {

1321

1322 size_t WritePos = WriteI - LR->begin();

1323 LR->segments.insert(ReadI, Spills.size() - GapSize, LiveRange::Segment());

1324

1325 WriteI = LR->begin() + WritePos;

1326 } else {

1327

1328 LR->segments.erase(WriteI + Spills.size(), ReadI);

1329 }

1330 ReadI = WriteI + Spills.size();

1331 mergeSpills();

1332 assert(LR->verify());

1333}

1334

1336

1337 EqClass.clear();

1339

1340 const VNInfo *used = nullptr, *unused = nullptr;

1341

1342

1344

1346 if (unused)

1347 EqClass.join(unused->id, VNI->id);

1348 unused = VNI;

1349 continue;

1350 }

1351 used = VNI;

1354 assert(MBB && "Phi-def has no defining MBB");

1355

1358 EqClass.join(VNI->id, PVNI->id);

1359 } else {

1360

1361

1362

1363

1365 EqClass.join(VNI->id, UVNI->id);

1366 }

1367 }

1368

1369

1370 if (used && unused)

1371 EqClass.join(used->id, unused->id);

1372

1373 EqClass.compress();

1374 return EqClass.getNumClasses();

1375}

1376

1379

1384 if (MI->isDebugValue()) {

1385

1386

1387 SlotIndex Idx = LIS.getSlotIndexes()->getIndexBefore(*MI);

1389 } else {

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

1393 }

1394

1395

1396 if (!VNI)

1397 continue;

1398 if (unsigned EqClass = getEqClass(VNI))

1399 MO.setReg(LIV[EqClass - 1]->reg());

1400 }

1401

1402

1404 unsigned NumComponents = EqClass.getNumClasses();

1409

1410

1411 unsigned NumValNos = SR.valnos.size();

1412 VNIMapping.clear();

1413 VNIMapping.reserve(NumValNos);

1414 SubRanges.clear();

1415 SubRanges.resize(NumComponents-1, nullptr);

1416 for (unsigned I = 0; I < NumValNos; ++I) {

1417 const VNInfo &VNI = *SR.valnos[I];

1418 unsigned ComponentNum;

1420 ComponentNum = 0;

1421 } else {

1423 assert(MainRangeVNI != nullptr

1424 && "SubRange def must have corresponding main range def");

1425 ComponentNum = getEqClass(MainRangeVNI);

1426 if (ComponentNum > 0 && SubRanges[ComponentNum-1] == nullptr) {

1427 SubRanges[ComponentNum-1]

1428 = LIV[ComponentNum-1]->createSubRange(Allocator, SR.LaneMask);

1429 }

1430 }

1431 VNIMapping.push_back(ComponentNum);

1432 }

1434 }

1436 }

1437

1438

1440}

unsigned const MachineRegisterInfo * MRI

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

static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")

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

static BasicBlock::iterator findInsertPos(Value *Addr, Instruction *MemoryInst, Value *SunkAddr)

#define LLVM_DUMP_METHOD

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

A common definition of LaneBitmask for use in TableGen and CodeGen.

static void createDeadDef(SlotIndexes &Indexes, VNInfo::Allocator &Alloc, LiveRange &LR, const MachineOperand &MO)

static bool coalescable(const LiveRange::Segment &A, const LiveRange::Segment &B)

Definition LiveInterval.cpp:1185

static void stripValuesNotDefiningMask(Register Reg, LiveInterval::SubRange &SR, LaneBitmask LaneMask, const SlotIndexes &Indexes, const TargetRegisterInfo &TRI, unsigned ComposeSubRegIdx)

For each VNI in SR, check whether or not that value defines part of the mask describe by LaneMask and...

Definition LiveInterval.cpp:872

This file contains helper functions to modify live ranges.

place backedge safepoints impl

SI Optimize VGPR LiveRange

This file defines the SmallPtrSet class.

This file defines the SmallVector class.

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

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

A helper class for register coalescers.

LLVM_ABI void Distribute(LiveInterval &LI, LiveInterval *LIV[], MachineRegisterInfo &MRI)

Distribute values in LI into a separate LiveIntervals for each connected component.

Definition LiveInterval.cpp:1377

LLVM_ABI unsigned Classify(const LiveRange &LR)

Classify the values in LR into connected components.

Definition LiveInterval.cpp:1335

unsigned getEqClass(const VNInfo *VNI) const

getEqClass - Classify creates equivalence classes numbered 0..N.

ConstMIBundleOperands - Iterate over all operands in a const bundle of machine instructions.

A live range for subregisters.

LLVM_ABI void print(raw_ostream &OS) const

Definition LiveInterval.cpp:1035

LLVM_ABI void dump() const

Definition LiveInterval.cpp:1054

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

Definition LiveInterval.cpp:842

bool hasSubRanges() const

Returns true if subregister liveness information is available.

LLVM_ABI void dump() const

Definition LiveInterval.cpp:1058

LLVM_ABI unsigned getSize() const

getSize - Returns the sum of sizes of all the LiveRange's.

Definition LiveInterval.cpp:958

SubRange * createSubRangeFrom(BumpPtrAllocator &Allocator, LaneBitmask LaneMask, const LiveRange &CopyFrom)

Like createSubRange() but the new range is filled with a copy of the liveness information in CopyFrom...

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.

Definition LiveInterval.cpp:919

LLVM_ABI void print(raw_ostream &OS) const

Definition LiveInterval.cpp:1040

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

Definition LiveInterval.cpp:965

SubRange * createSubRange(BumpPtrAllocator &Allocator, LaneBitmask LaneMask)

Creates a new empty subregister live range.

LLVM_ABI void clearSubRanges()

Removes all subregister liveness information.

Definition LiveInterval.cpp:861

Result of a LiveRange query.

VNInfo * valueIn() const

Return the value that is live-in to the instruction.

VNInfo * valueOut() const

Return the value leaving the instruction, if any.

VNInfo * valueDefined() const

Return the value defined by this instruction, if any.

LLVM_ABI void print(raw_ostream &) const

Definition LiveInterval.cpp:1156

LLVM_ABI void flush()

Flush the updater state to LR so it is valid and contains all added segments.

Definition LiveInterval.cpp:1303

LLVM_ABI void dump() const

Definition LiveInterval.cpp:1179

bool isDirty() const

Return true if the LR is currently in an invalid state, and flush() needs to be called.

LLVM_ABI void add(LiveRange::Segment)

Add a segment to LR and coalesce when possible, just like LR.addSegment().

Definition LiveInterval.cpp:1196

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

LiveRange(bool UseSegmentSet=false)

Constructs a new LiveRange object.

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.

Definition LiveInterval.cpp:533

Segments::iterator iterator

LLVM_ABI void join(LiveRange &Other, const int *ValNoAssignments, const int *RHSValNoAssignments, SmallVectorImpl< VNInfo * > &NewVNInfo)

join - Join two live ranges (this, and other) together.

Definition LiveInterval.cpp:629

LLVM_ABI void MergeValueInAsValue(const LiveRange &RHS, const VNInfo *RHSValNo, VNInfo *LHSValNo)

MergeValueInAsValue - Merge all of the segments of a specific val# in RHS into this live range as the...

Definition LiveInterval.cpp:725

Segments::const_iterator const_iterator

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

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

Definition LiveInterval.cpp:355

std::set< Segment > SegmentSet

LLVM_ABI bool isLiveAtIndexes(ArrayRef< SlotIndex > Slots) const

Definition LiveInterval.cpp:803

LLVM_ABI bool covers(const LiveRange &Other) const

Returns true if all segments of the Other live range are completely covered by this live range.

Definition LiveInterval.cpp:479

iterator advanceTo(iterator I, SlotIndex Pos)

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

std::unique_ptr< SegmentSet > segmentSet

LLVM_ABI void removeValNo(VNInfo *ValNo)

removeValNo - Remove all the segments defined by the specified value#.

Definition LiveInterval.cpp:621

LLVM_ABI void RenumberValues()

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

Definition LiveInterval.cpp:516

bool overlaps(const LiveRange &other) const

overlaps - Return true if the intersection of the two live ranges is not empty.

LLVM_ABI bool overlapsFrom(const LiveRange &Other, const_iterator StartPos) const

overlapsFrom - Return true if the intersection of the two live ranges is not empty.

Definition LiveInterval.cpp:389

LiveQueryResult Query(SlotIndex Idx) const

Query Liveness at Idx.

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.

Definition LiveInterval.cpp:549

bool verify() const

Walk the range and assert if any invariants fail to hold.

Definition LiveInterval.cpp:1064

LLVM_ABI void append(const LiveRange::Segment S)

Append a segment to the list of segments.

Definition LiveInterval.cpp:543

friend class LiveRangeUpdater

LLVM_ABI VNInfo * MergeValueNumberInto(VNInfo *V1, VNInfo *V2)

MergeValueNumberInto - This method is called when two value numbers are found to be equivalent.

Definition LiveInterval.cpp:738

unsigned getNumValNums() const

LLVM_ABI void MergeSegmentsInAsValue(const LiveRange &RHS, VNInfo *LHSValNo)

Merge all of the live segments of a specific val# in RHS into this live range as the specified value ...

Definition LiveInterval.cpp:713

SmallVector< Segment, 2 > Segments

VNInfoList::const_iterator const_vni_iterator

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

Remove the specified interval from this live range.

Definition LiveInterval.cpp:566

LLVM_ABI void removeValNoIfDead(VNInfo *ValNo)

Mark ValNo for deletion if no segments in this range use it.

Definition LiveInterval.cpp:614

LLVM_ABI void dump() const

Definition LiveInterval.cpp:1052

LLVM_ABI void print(raw_ostream &OS) const

Definition LiveInterval.cpp:1010

LLVM_ABI void flushSegmentSet()

Flush segment set into the regular segment vector.

Definition LiveInterval.cpp:793

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

Definition LiveInterval.cpp:350

bool isValid() const

isValid - Returns true until all the operands have been visited.

Representation of each machine instruction.

MachineOperand class - Representation of each machine instruction operand.

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.

static bool isEarlierInstr(SlotIndex A, SlotIndex B)

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

SlotIndex getNextSlot() const

Returns the next 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 getInstructionIndex(const MachineInstr &MI, bool IgnoreBundle=false) const

Returns the base index for the given instruction.

MachineInstr * getInstructionFromIndex(SlotIndex index) const

Returns the instruction for the given index, or null if the given index has no instruction associated...

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

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

SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.

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

void reserve(size_type N)

void push_back(const T &Elt)

pointer data()

Return a pointer to the vector's buffer, even if empty().

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

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

VNInfo - Value Number Information.

void copyFrom(VNInfo &src)

Copy from the parameter into this VNInfo.

LLVM_ABI void dump() const

Definition LiveInterval.cpp:1050

LLVM_ABI void print(raw_ostream &OS) const

Definition LiveInterval.cpp:999

void markUnused()

Mark this value as unused.

BumpPtrAllocator Allocator

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

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

This provides a very simple, boring adaptor for a begin and end iterator into a range type.

NodeAddr< DefNode * > Def

NodeAddr< UseNode * > Use

LLVM_ABI iterator begin() const

This is an optimization pass for GlobalISel generic memory operations.

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

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

auto partition_point(R &&Range, Predicate P)

Binary search for the first iterator in a range where a predicate is false.

iterator_range< T > make_range(T x, T y)

Convenience function for iterating over sub-ranges.

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

Printable PrintLaneMask(LaneBitmask LaneMask)

Create Printable object to print LaneBitmasks on a raw_ostream.

auto upper_bound(R &&Range, T &&Value)

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

static void DistributeRange(LiveRangeT &LR, LiveRangeT *SplitLRs[], EqClassesT VNIClasses)

Helper function that distributes live range value numbers and the corresponding segments of a primary...

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 raw_fd_ostream & errs()

This returns a reference to a raw_ostream for standard error.

auto lower_bound(R &&Range, T &&Value)

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

FunctionAddr VTableAddr Next

raw_ostream & operator<<(raw_ostream &OS, const APFixedPoint &FX)

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

void erase_if(Container &C, UnaryPredicate P)

Provide a container algorithm similar to C++ Library Fundamentals v2's erase_if which is equivalent t...

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.

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

Implement std::swap in terms of BitVector swap.

ListT< IteratorSpecifierT< T, I, E > > IteratorT

static constexpr LaneBitmask getAll()

constexpr bool none() const

constexpr bool any() const

This represents a simple continuous liveness interval for a value.

LLVM_ABI void dump() const

Definition LiveInterval.cpp:994