StackColoring.cpp Source File (original) (raw)

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

58#include

59#include

60#include

61#include

62#include

64using namespace llvm;

66#define DEBUG_TYPE "stack-coloring"

71 cl::desc("Disable stack coloring"));

81 cl::desc("Do not optimize lifetime zones that "

82 "are broken"));

91 cl::desc("Treat stack lifetimes as starting on first use, not on START marker."));

94 STATISTIC(NumMarkerSeen, "Number of lifetime markers found.");

95 STATISTIC(StackSpaceSaved, "Number of bytes saved due to merging slots.");

96 STATISTIC(StackSlotMerged, "Number of stack slot merged.");

97 STATISTIC(EscapedAllocas, "Number of allocas that escaped the lifetime region");

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220

221

222

223

224

225

226

227

228

229

230

231

232

233

234

235

236

237

238

239

240

241

242

243

244

245

246

247

248

249

250

251

252

253

254

255

256

257

258

259

260

261

262

263

264

265

266

267

268

269

270

271

272

273

274

275

276

277

278

279

280

281

282

283

284

285

286

287

288

289

290

291

292

293

294

295

296

297

298

299

300

301

302

303

304

305

306

307

308

309

310

311

312

313

314

315

316

317

318

319

320

321

322

323

324

325

326

327

328

329

330

331

332

333

334

335

336

337

338

339

340

341

342

343

344

345

346

347

348

349

350

351

352

353

354

355

356

357

358

359

360

361

362

363

364

365

366

367

368

369

370

371

372

373

374

375

376namespace {

377

378

379

380class StackColoring {

383

384

385

386

387 struct BlockLifetimeInfo {

388

390

391

393

394

396

397

399 };

400

401

402 using LivenessMap = DenseMap<const MachineBasicBlock *, BlockLifetimeInfo>;

403 LivenessMap BlockLiveness;

404

405

406 DenseMap<const MachineBasicBlock *, int> BasicBlocks;

407

408

410

411

412

414

415

417

418

420

421

422 SlotIndexes *Indexes = nullptr;

423

424

425

426 SmallVector<MachineInstr*, 8> Markers;

427

428

429

430 BitVector InterestingSlots;

431

432

433

434 BitVector ConservativeSlots;

435

436

437 unsigned NumIterations;

438

439public:

440 StackColoring(SlotIndexes *Indexes) : Indexes(Indexes) {}

441 bool run(MachineFunction &Func);

442

443private:

444

445 using BlockBitVecMap = DenseMap<const MachineBasicBlock *, BitVector>;

446

447

448 void dump() const;

449 void dumpIntervals() const;

450 void dumpBB(MachineBasicBlock *MBB) const;

451 void dumpBV(const char *tag, const BitVector &BV) const;

452

453

454

455 bool removeAllMarkers();

456

457

458

459

460 unsigned collectMarkers(unsigned NumSlot);

461

462

463

464

465

466 void calculateLocalLiveness();

467

468

469

470 bool applyFirstUse(int Slot) {

472 return false;

473 if (ConservativeSlots.test(Slot))

474 return false;

475 return true;

476 }

477

478

479

480

481

482

483 bool isLifetimeStartOrEnd(const MachineInstr &MI,

484 SmallVector<int, 4> &slots,

485 bool &isStart);

486

487

488 void calculateLiveIntervals(unsigned NumSlots);

489

490

491

492 void remapInstructions(DenseMap<int, int> &SlotRemap);

493

494

495

496

497

498

499

500 void removeInvalidSlotRanges();

501

502

503

504 void expungeSlotMap(DenseMap<int, int> &SlotRemap, unsigned NumSlots);

505};

506

508public:

509 static char ID;

510

511 StackColoringLegacy() : MachineFunctionPass(ID) {}

512

513 void getAnalysisUsage(AnalysisUsage &AU) const override;

514 bool runOnMachineFunction(MachineFunction &Func) override;

515};

516

517}

518

519char StackColoringLegacy::ID = 0;

520

522

524 "Merge disjoint stack slots", false, false)

528

529void StackColoringLegacy::getAnalysisUsage(AnalysisUsage &AU) const {

532}

533

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

537 dbgs() << tag << " : { ";

538 for (unsigned I = 0, E = BV.size(); I != E; ++I)

540 dbgs() << "}\n";

541}

542

543LLVM_DUMP_METHOD void StackColoring::dumpBB(MachineBasicBlock *MBB) const {

544 LivenessMap::const_iterator BI = BlockLiveness.find(MBB);

545 assert(BI != BlockLiveness.end() && "Block not found");

546 const BlockLifetimeInfo &BlockInfo = BI->second;

547

548 dumpBV("BEGIN", BlockInfo.Begin);

549 dumpBV("END", BlockInfo.End);

550 dumpBV("LIVE_IN", BlockInfo.LiveIn);

551 dumpBV("LIVE_OUT", BlockInfo.LiveOut);

552}

553

558 dumpBB(MBB);

559 }

560}

561

563 for (unsigned I = 0, E = Intervals.size(); I != E; ++I) {

564 dbgs() << "Interval[" << I << "]:\n";

565 Intervals[I]->dump();

566 }

567}

568#endif

569

571{

572 assert((MI.getOpcode() == TargetOpcode::LIFETIME_START ||

573 MI.getOpcode() == TargetOpcode::LIFETIME_END) &&

574 "Expected LIFETIME_START or LIFETIME_END op");

577 if (Slot >= 0)

578 return Slot;

579 return -1;

580}

581

582

583

584

585

586bool StackColoring::isLifetimeStartOrEnd(const MachineInstr &MI,

587 SmallVector<int, 4> &slots,

588 bool &isStart) {

589 if (MI.getOpcode() == TargetOpcode::LIFETIME_START ||

590 MI.getOpcode() == TargetOpcode::LIFETIME_END) {

592 if (Slot < 0)

593 return false;

594 if (!InterestingSlots.test(Slot))

595 return false;

596 slots.push_back(Slot);

597 if (MI.getOpcode() == TargetOpcode::LIFETIME_END) {

598 isStart = false;

599 return true;

600 }

601 if (!applyFirstUse(Slot)) {

602 isStart = true;

603 return true;

604 }

606 if (.isDebugInstr()) {

607 bool found = false;

608 for (const MachineOperand &MO : MI.operands()) {

609 if (!MO.isFI())

610 continue;

611 int Slot = MO.getIndex();

612 if (Slot<0)

613 continue;

614 if (InterestingSlots.test(Slot) && applyFirstUse(Slot)) {

615 slots.push_back(Slot);

616 found = true;

617 }

618 }

619 if (found) {

620 isStart = true;

621 return true;

622 }

623 }

624 }

625 return false;

626}

627

628unsigned StackColoring::collectMarkers(unsigned NumSlot) {

629 unsigned MarkersFound = 0;

630 BlockBitVecMap SeenStartMap;

631 InterestingSlots.clear();

632 InterestingSlots.resize(NumSlot);

633 ConservativeSlots.clear();

634 ConservativeSlots.resize(NumSlot);

635

636

637 SmallVector<int, 8> NumStartLifetimes(NumSlot, 0);

638 SmallVector<int, 8> NumEndLifetimes(NumSlot, 0);

639

640

641

643

644

645

646 BitVector BetweenStartEnd;

647 BetweenStartEnd.resize(NumSlot);

648 for (const MachineBasicBlock *Pred : MBB->predecessors()) {

649 BlockBitVecMap::const_iterator I = SeenStartMap.find(Pred);

650 if (I != SeenStartMap.end()) {

651 BetweenStartEnd |= I->second;

652 }

653 }

654

655

656 for (MachineInstr &MI : *MBB) {

657 if (MI.isDebugInstr())

658 continue;

659 if (MI.getOpcode() == TargetOpcode::LIFETIME_START ||

660 MI.getOpcode() == TargetOpcode::LIFETIME_END) {

662 if (Slot < 0)

663 continue;

664 InterestingSlots.set(Slot);

665 if (MI.getOpcode() == TargetOpcode::LIFETIME_START) {

666 BetweenStartEnd.set(Slot);

667 NumStartLifetimes[Slot] += 1;

668 } else {

669 BetweenStartEnd.reset(Slot);

670 NumEndLifetimes[Slot] += 1;

671 }

673 if (Allocation) {

675 LLVM_DEBUG(dbgs() << (MI.getOpcode() == TargetOpcode::LIFETIME_START

676 ? "start"

677 : "end"));

680 << " with allocation: " << Allocation->getName() << "\n");

681 }

683 MarkersFound += 1;

684 } else {

685 for (const MachineOperand &MO : MI.operands()) {

686 if (!MO.isFI())

687 continue;

688 int Slot = MO.getIndex();

689 if (Slot < 0)

690 continue;

691 if (! BetweenStartEnd.test(Slot)) {

692 ConservativeSlots.set(Slot);

693 }

694 }

695 }

696 }

697 BitVector &SeenStart = SeenStartMap[MBB];

698 SeenStart |= BetweenStartEnd;

699 }

700 if (!MarkersFound) {

701 return 0;

702 }

703

704

705

706 for (unsigned slot = 0; slot < NumSlot; ++slot) {

707 if (NumStartLifetimes[slot] > 1 || NumEndLifetimes[slot] > 1)

708 ConservativeSlots.set(slot);

709 }

710

711

712

713

714

716 for (WinEHTryBlockMapEntry &TBME : EHInfo->TryBlockMap)

718 if (H.CatchObj.FrameIndex != std::numeric_limits::max() &&

719 H.CatchObj.FrameIndex >= 0)

720 ConservativeSlots.set(H.CatchObj.FrameIndex);

721

722 LLVM_DEBUG(dumpBV("Conservative slots", ConservativeSlots));

723

724

725

726

727

729

730 BasicBlocks[MBB] = BasicBlockNumbering.size();

732

733

734 BlockLifetimeInfo &BlockInfo = BlockLiveness[MBB];

735

736 BlockInfo.Begin.resize(NumSlot);

737 BlockInfo.End.resize(NumSlot);

738

739 SmallVector<int, 4> slots;

740 for (MachineInstr &MI : *MBB) {

741 bool isStart = false;

743 if (isLifetimeStartOrEnd(MI, slots, isStart)) {

744 if (!isStart) {

745 assert(slots.size() == 1 && "unexpected: MI ends multiple slots");

747 if (BlockInfo.Begin.test(Slot)) {

748 BlockInfo.Begin.reset(Slot);

749 }

750 BlockInfo.End.set(Slot);

751 } else {

752 for (auto Slot : slots) {

753 LLVM_DEBUG(dbgs() << "Found a use of slot #" << Slot);

758 if (Allocation) {

760 << " with allocation: " << Allocation->getName());

761 }

763 if (BlockInfo.End.test(Slot)) {

764 BlockInfo.End.reset(Slot);

765 }

766 BlockInfo.Begin.set(Slot);

767 }

768 }

769 }

770 }

771 }

772

773

774 NumMarkerSeen += MarkersFound;

775 return MarkersFound;

776}

777

778void StackColoring::calculateLocalLiveness() {

779 unsigned NumIters = 0;

780 bool changed = true;

781

782

783 BitVector LocalLiveIn;

784 BitVector LocalLiveOut;

785 while (changed) {

786 changed = false;

787 ++NumIters;

788

789 for (const MachineBasicBlock *BB : BasicBlockNumbering) {

790

791 LivenessMap::iterator BI = BlockLiveness.find(BB);

792 assert(BI != BlockLiveness.end() && "Block not found");

793 BlockLifetimeInfo &BlockInfo = BI->second;

794

795

796 LocalLiveIn.clear();

797 for (MachineBasicBlock *Pred : BB->predecessors()) {

798 LivenessMap::const_iterator I = BlockLiveness.find(Pred);

799

800

801

802 if (I != BlockLiveness.end())

803 LocalLiveIn |= I->second.LiveOut;

804 }

805

806

807

808

809

810

811

812

813 LocalLiveOut = LocalLiveIn;

814 LocalLiveOut.reset(BlockInfo.End);

815 LocalLiveOut |= BlockInfo.Begin;

816

817

818 if (LocalLiveIn.test(BlockInfo.LiveIn)) {

819 changed = true;

820 BlockInfo.LiveIn |= LocalLiveIn;

821 }

822

823

824 if (LocalLiveOut.test(BlockInfo.LiveOut)) {

825 changed = true;

826 BlockInfo.LiveOut |= LocalLiveOut;

827 }

828 }

829 }

830

831 NumIterations = NumIters;

832}

833

834void StackColoring::calculateLiveIntervals(unsigned NumSlots) {

837

838

839

840 for (const MachineBasicBlock &MBB : *MF) {

842 Starts.resize(NumSlots);

843 DefinitelyInUse.clear();

844 DefinitelyInUse.resize(NumSlots);

845

846

847 BlockLifetimeInfo &MBBLiveness = BlockLiveness[&MBB];

848 for (int pos = MBBLiveness.LiveIn.find_first(); pos != -1;

849 pos = MBBLiveness.LiveIn.find_next(pos)) {

851 }

852

853

854 for (const MachineInstr &MI : MBB) {

855 SmallVector<int, 4> slots;

856 bool IsStart = false;

857 if (!isLifetimeStartOrEnd(MI, slots, IsStart))

858 continue;

860 for (auto Slot : slots) {

861 if (IsStart) {

862

863

864

865 if (!DefinitelyInUse[Slot]) {

867 DefinitelyInUse[Slot] = true;

868 }

869 if (!Starts[Slot].isValid())

870 Starts[Slot] = ThisIndex;

871 } else {

872 if (Starts[Slot].isValid()) {

873 VNInfo *VNI = Intervals[Slot]->getValNumInfo(0);

874 Intervals[Slot]->addSegment(

875 LiveInterval::Segment(Starts[Slot], ThisIndex, VNI));

876 Starts[Slot] = SlotIndex();

877 DefinitelyInUse[Slot] = false;

878 }

879 }

880 }

881 }

882

883

884 for (unsigned i = 0; i < NumSlots; ++i) {

885 if (!Starts[i].isValid())

886 continue;

887

889 VNInfo *VNI = Intervals[i]->getValNumInfo(0);

890 Intervals[i]->addSegment(LiveInterval::Segment(Starts[i], EndIdx, VNI));

891 }

892 }

893}

894

895bool StackColoring::removeAllMarkers() {

896 unsigned Count = 0;

897 for (MachineInstr *MI : Markers) {

898 MI->eraseFromParent();

900 }

902

905}

906

907void StackColoring::remapInstructions(DenseMap<int, int> &SlotRemap) {

908 unsigned FixedInstr = 0;

909 unsigned FixedMemOp = 0;

910 unsigned FixedDbg = 0;

911

912

913 for (auto &VI : MF->getVariableDbgInfo()) {

914 if (.Var || .inStackSlot())

915 continue;

916 int Slot = VI.getStackSlot();

917 if (auto It = SlotRemap.find(Slot); It != SlotRemap.end()) {

920 VI.updateStackSlot(It->second);

921 FixedDbg++;

922 }

923 }

924

925

926 DenseMap<const AllocaInst*, const AllocaInst*> Allocas;

927

928

929 SmallPtrSet<const AllocaInst*, 32> MergedAllocas;

930

931 for (const std::pair<int, int> &SI : SlotRemap) {

934 assert(To && From && "Invalid allocation object");

935 Allocas[From] = To;

936

937

938

940 const_cast<AllocaInst *>(To)->moveBefore(

941 const_cast<AllocaInst *>(From)->getIterator());

942

943

944

945

946

947

948

949 Instruction *Inst = const_cast<AllocaInst *>(To);

951 BitCastInst *Cast = new BitCastInst(Inst, From->getType());

953 Inst = Cast;

954 }

955

956

957 MergedAllocas.insert(From);

958 MergedAllocas.insert(To);

959

960

961

962

971

972

973

974 AllocaInst *FromAI = const_cast<AllocaInst *>(From);

977 for (auto &Use : FromAI->uses()) {

979 if (BCI->isUsedByMetadata())

981 }

982

983

984

985

987 }

988

989

990 std::vector<std::vector<MachineMemOperand *>> SSRefs(

992 for (MachineBasicBlock &BB : *MF)

993 for (MachineInstr &I : BB) {

994

995 if (I.getOpcode() == TargetOpcode::LIFETIME_START ||

996 I.getOpcode() == TargetOpcode::LIFETIME_END)

997 continue;

998

999

1000 for (MachineMemOperand *MMO : I.memoperands()) {

1001

1002

1004 if (!AI)

1005 continue;

1006

1007 auto It = Allocas.find(AI);

1008 if (It == Allocas.end())

1009 continue;

1010

1011 MMO->setValue(It->second);

1012 FixedMemOp++;

1013 }

1014

1015

1016 for (MachineOperand &MO : I.operands()) {

1017 if (!MO.isFI())

1018 continue;

1019 int FromSlot = MO.getIndex();

1020

1021

1022 if (FromSlot<0)

1023 continue;

1024

1025

1026 if (!SlotRemap.count(FromSlot))

1027 continue;

1028

1029

1030

1031

1032

1033

1034

1035

1036#ifndef NDEBUG

1037 bool TouchesMemory = I.mayLoadOrStore();

1038

1039

1042 const LiveInterval *Interval = &*Intervals[FromSlot];

1044 "Found instruction usage outside of live range.");

1045 }

1046#endif

1047

1048

1049 int ToSlot = SlotRemap[FromSlot];

1050 MO.setIndex(ToSlot);

1051 FixedInstr++;

1052 }

1053

1054

1056 bool ReplaceMemOps = false;

1057 for (MachineMemOperand *MMO : I.memoperands()) {

1058

1059

1061 MMO->getPseudoValue())) {

1062 int FI = FSV->getFrameIndex();

1063 auto To = SlotRemap.find(FI);

1064 if (To != SlotRemap.end())

1065 SSRefs[FI].push_back(MMO);

1066 }

1067

1068

1069

1070 bool MayHaveConflictingAAMD = false;

1071 if (MMO->getAAInfo()) {

1072 if (const Value *MMOV = MMO->getValue()) {

1075

1076 if (Objs.empty())

1077 MayHaveConflictingAAMD = true;

1078 else

1079 for (Value *V : Objs) {

1080

1081

1082

1084 if (AI && MergedAllocas.count(AI)) {

1085 MayHaveConflictingAAMD = true;

1086 break;

1087 }

1088 }

1089 }

1090 }

1091 if (MayHaveConflictingAAMD) {

1092 NewMMOs.push_back(MF->getMachineMemOperand(MMO, AAMDNodes()));

1093 ReplaceMemOps = true;

1094 } else {

1096 }

1097 }

1098

1099

1100

1101 if (ReplaceMemOps)

1102 I.setMemRefs(*MF, NewMMOs);

1103 }

1104

1105

1107 if (.value().empty()) {

1108 const PseudoSourceValue *NewSV =

1109 MF->getPSVManager().getFixedStack(SlotRemap.find(E.index())->second);

1110 for (MachineMemOperand *Ref : E.value())

1111 Ref->setValue(NewSV);

1112 }

1113

1114

1115 if (WinEHFuncInfo *EHInfo = MF->getWinEHFuncInfo())

1116 for (WinEHTryBlockMapEntry &TBME : EHInfo->TryBlockMap)

1118 if (H.CatchObj.FrameIndex != std::numeric_limits::max())

1119 if (auto It = SlotRemap.find(H.CatchObj.FrameIndex);

1120 It != SlotRemap.end())

1121 H.CatchObj.FrameIndex = It->second;

1122

1123 LLVM_DEBUG(dbgs() << "Fixed " << FixedMemOp << " machine memory operands.\n");

1124 LLVM_DEBUG(dbgs() << "Fixed " << FixedDbg << " debug locations.\n");

1125 LLVM_DEBUG(dbgs() << "Fixed " << FixedInstr << " machine instructions.\n");

1126 (void) FixedMemOp;

1127 (void) FixedDbg;

1128 (void) FixedInstr;

1129}

1130

1131void StackColoring::removeInvalidSlotRanges() {

1132 for (MachineBasicBlock &BB : *MF)

1133 for (MachineInstr &I : BB) {

1134 if (I.getOpcode() == TargetOpcode::LIFETIME_START ||

1135 I.getOpcode() == TargetOpcode::LIFETIME_END || I.isDebugInstr())

1136 continue;

1137

1138

1139

1140

1141

1142

1143

1144 if (.mayLoad() && .mayStore())

1145 continue;

1146

1147

1148 for (const MachineOperand &MO : I.operands()) {

1149 if (!MO.isFI())

1150 continue;

1151

1152 int Slot = MO.getIndex();

1153

1154 if (Slot<0)

1155 continue;

1156

1157 if (Intervals[Slot]->empty())

1158 continue;

1159

1160

1161

1166 LLVM_DEBUG(dbgs() << "Invalidating range #" << Slot << "\n");

1167 EscapedAllocas++;

1168 }

1169 }

1170 }

1171}

1172

1173void StackColoring::expungeSlotMap(DenseMap<int, int> &SlotRemap,

1174 unsigned NumSlots) {

1175

1176 for (unsigned i=0; i < NumSlots; ++i) {

1177

1178 if (auto It = SlotRemap.find(i); It != SlotRemap.end()) {

1179 int Target = It->second;

1180

1181 while (true) {

1182 auto It = SlotRemap.find(Target);

1183 if (It == SlotRemap.end())

1184 break;

1185 Target = It->second;

1186 SlotRemap[i] = Target;

1187 }

1188 }

1189 }

1190}

1191

1192bool StackColoringLegacy::runOnMachineFunction(MachineFunction &MF) {

1194 return false;

1195

1196 StackColoring SC(&getAnalysis().getSI());

1197 return SC.run(MF);

1198}

1199

1203 if (SC.run(MF))

1206}

1207

1209 LLVM_DEBUG(dbgs() << "********** Stack Coloring **********\n"

1210 << "********** Function: " << Func.getName() << '\n');

1211 MF = &Func;

1213 BlockLiveness.clear();

1214 BasicBlocks.clear();

1215 BasicBlockNumbering.clear();

1217 Intervals.clear();

1218 LiveStarts.clear();

1219 VNInfoAllocator.Reset();

1220

1222

1223

1224 if (!NumSlots)

1225 return false;

1226

1228 SortedSlots.reserve(NumSlots);

1229 Intervals.reserve(NumSlots);

1230 LiveStarts.resize(NumSlots);

1231

1232 unsigned NumMarkers = collectMarkers(NumSlots);

1233

1234 unsigned TotalSize = 0;

1235 LLVM_DEBUG(dbgs() << "Found " << NumMarkers << " markers and " << NumSlots

1236 << " slots\n");

1238

1241 << " bytes.\n");

1243 }

1244

1245 LLVM_DEBUG(dbgs() << "Total Stack size: " << TotalSize << " bytes\n\n");

1246

1247

1248

1249 if (NumMarkers < 2 || TotalSize < 16 || DisableColoring) {

1250 LLVM_DEBUG(dbgs() << "Will not try to merge slots.\n");

1251 return removeAllMarkers();

1252 }

1253

1254 for (unsigned i=0; i < NumSlots; ++i) {

1255 std::unique_ptr LI(new LiveInterval(i, 0));

1256 LI->getNextValue(Indexes->getZeroIndex(), VNInfoAllocator);

1257 Intervals.push_back(std::move(LI));

1259 }

1260

1261

1262 calculateLocalLiveness();

1263 LLVM_DEBUG(dbgs() << "Dataflow iterations: " << NumIterations << "\n");

1265

1266

1267 calculateLiveIntervals(NumSlots);

1269

1270

1271

1273 removeInvalidSlotRanges();

1274

1275

1276 DenseMap<int, int> SlotRemap;

1277 unsigned RemovedSlots = 0;

1278 unsigned ReducedSize = 0;

1279

1280

1281 for (unsigned I = 0; I < NumSlots; ++I) {

1282 if (Intervals[SortedSlots[I]]->empty())

1283 SortedSlots[I] = -1;

1284 }

1285

1286

1287

1288

1289

1290

1291

1292

1293

1295

1296 if (LHS == -1)

1297 return false;

1298 if (RHS == -1)

1299 return true;

1300

1302 });

1303

1304 for (auto &s : LiveStarts)

1306

1310 for (unsigned I = 0; I < NumSlots; ++I) {

1311 if (SortedSlots[I] == -1)

1312 continue;

1313

1314 for (unsigned J=I+1; J < NumSlots; ++J) {

1315 if (SortedSlots[J] == -1)

1316 continue;

1317

1318 int FirstSlot = SortedSlots[I];

1319 int SecondSlot = SortedSlots[J];

1320

1321

1323 continue;

1324

1325 LiveInterval *First = &*Intervals[FirstSlot];

1326 LiveInterval *Second = &*Intervals[SecondSlot];

1327 auto &FirstS = LiveStarts[FirstSlot];

1328 auto &SecondS = LiveStarts[SecondSlot];

1329 assert( First ->empty() && !Second->empty() && "Found an empty range");

1330

1331

1332

1333 if ( First ->isLiveAtIndexes(SecondS) &&

1336 First->MergeSegmentsInAsValue(*Second, First->getValNumInfo(0));

1337

1338 int OldSize = FirstS.size();

1339 FirstS.append(SecondS.begin(), SecondS.end());

1340 auto Mid = FirstS.begin() + OldSize;

1341 std::inplace_merge(FirstS.begin(), Mid, FirstS.end());

1342

1343 SlotRemap[SecondSlot] = FirstSlot;

1344 SortedSlots[J] = -1;

1345 LLVM_DEBUG(dbgs() << "Merging #" << FirstSlot << " and slots #"

1346 << SecondSlot << " together.\n");

1349

1352 "Merging a small object into a larger one");

1353

1354 RemovedSlots+=1;

1358 }

1359 }

1360 }

1361 }

1362

1363

1364 StackSpaceSaved += ReducedSize;

1365 StackSlotMerged += RemovedSlots;

1366 LLVM_DEBUG(dbgs() << "Merge " << RemovedSlots << " slots. Saved "

1367 << ReducedSize << " bytes\n");

1368

1369

1370

1371 if (!SlotRemap.empty()) {

1372 expungeSlotMap(SlotRemap, NumSlots);

1373 remapInstructions(SlotRemap);

1374 }

1375

1376 return removeAllMarkers();

1377}

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

This file implements the BitVector class.

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

#define LLVM_DUMP_METHOD

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

This file contains the declarations for the subclasses of Constant, which represent the different fla...

This file defines the DenseMap class.

This file builds on the ADT/GraphTraits.h file to build generic depth first graph iterator.

This defines the Use class.

std::pair< uint64_t, uint64_t > Interval

#define INITIALIZE_PASS_DEPENDENCY(depName)

#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)

#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)

static bool isValid(const char C)

Returns true if C is a valid mangled character: <0-9a-zA-Z_>.

This file defines the SmallPtrSet class.

This file defines the SmallVector class.

static int getStartOrEndSlot(const MachineInstr &MI)

Definition StackColoring.cpp:570

static cl::opt< bool > DisableColoring("no-stack-coloring", cl::init(false), cl::Hidden, cl::desc("Disable stack coloring"))

static cl::opt< bool > ProtectFromEscapedAllocas("protect-from-escaped-allocas", cl::init(false), cl::Hidden, cl::desc("Do not optimize lifetime zones that " "are broken"))

The user may write code that uses allocas outside of the declared lifetime zone.

static cl::opt< bool > LifetimeStartOnFirstUse("stackcoloring-lifetime-start-on-first-use", cl::init(true), cl::Hidden, cl::desc("Treat stack lifetimes as starting on first use, not on START marker."))

Enable enhanced dataflow scheme for lifetime analysis (treat first use of stack slot as start of slot...

Merge disjoint stack slots

Definition StackColoring.cpp:527

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

#define STATISTIC(VARNAME, DESC)

PointerType * getType() const

Overload to return most specific pointer type.

PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)

Get the result of an analysis pass for a given IR unit.

Represent the analysis usage information of a pass.

bool test(unsigned Idx) const

void resize(unsigned N, bool t=false)

resize - Grow or shrink the bitvector.

void clear()

clear - Removes all bits from the bitvector.

size_type size() const

size - Returns the number of bits in this bitvector.

iterator find(const_arg_type_t< KeyT > Val)

LLVM_ABI bool comesBefore(const Instruction *Other) const

Given an instruction Other in the same basic block as this instruction, return true if this instructi...

LLVM_ABI void insertAfter(Instruction *InsertPos)

Insert an unlinked instruction into a basic block immediately after the specified instruction.

LLVM_ABI bool isLiveAtIndexes(ArrayRef< SlotIndex > Slots) const

int getNumber() const

MachineBasicBlocks are uniquely numbered at the function level, unless they're not in a MachineFuncti...

iterator_range< pred_iterator > predecessors()

LLVM_ABI StringRef getName() const

Return the name of the corresponding LLVM basic block, or an empty string.

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

SSPLayoutKind getObjectSSPLayout(int ObjectIdx) const

const AllocaInst * getObjectAllocation(int ObjectIdx) const

Return the underlying Alloca of the specified stack object if it exists.

SSPLayoutKind

Stack Smashing Protection (SSP) rules require that vulnerable stack allocations are located close the...

@ SSPLK_LargeArray

Array or nested array >= SSP-buffer-size.

@ SSPLK_AddrOf

The address of this allocation is exposed and triggered protection.

@ SSPLK_None

Did not trigger a stack protector.

void setObjectSSPLayout(int ObjectIdx, SSPLayoutKind Kind)

Align getObjectAlign(int ObjectIdx) const

Return the alignment of the specified stack object.

int64_t getObjectSize(int ObjectIdx) const

Return the size of the specified object.

void RemoveStackObject(int ObjectIdx)

Remove or mark dead a statically sized stack object.

int getObjectIndexEnd() const

Return one past the maximum frame object index.

uint8_t getStackID(int ObjectIdx) const

void setObjectAlignment(int ObjectIdx, Align Alignment)

setObjectAlignment - Change the alignment of the specified stack object.

MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...

void getAnalysisUsage(AnalysisUsage &AU) const override

getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.

const WinEHFuncInfo * getWinEHFuncInfo() const

getWinEHFuncInfo - Return information about how the current function uses Windows exception handling.

MachineFrameInfo & getFrameInfo()

getFrameInfo - Return the frame info object for the current function.

Function & getFunction()

Return the LLVM function that this machine code represents.

Representation of each machine instruction.

MachineOperand class - Representation of each machine instruction operand.

static LLVM_ABI PoisonValue * get(Type *T)

Static factory methods - Return an 'poison' object of the specified type.

A set of analyses that are preserved following a run of a transformation pass.

static PreservedAnalyses all()

Construct a special preserved set that preserves all passes.

LLVM_ABI void print(raw_ostream &os) const

Print this index to the given raw_ostream.

SlotIndex getMBBEndIdx(unsigned Num) const

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

SlotIndex getInstructionIndex(const MachineInstr &MI, bool IgnoreBundle=false) const

Returns the base index for the given instruction.

SlotIndex getMBBStartIdx(unsigned Num) const

Returns the first index in the given basic block number.

SlotIndex getZeroIndex()

Returns the zero index for this analysis.

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.

void reserve(size_type N)

void push_back(const T &Elt)

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

PreservedAnalyses run(MachineFunction &MF, MachineFunctionAnalysisManager &MFAM)

Definition StackColoring.cpp:1200

BumpPtrAllocator Allocator

LLVM_ABI void replaceAllUsesWith(Value *V)

Change all uses of this to point to a new Value.

bool isUsedByMetadata() const

Return true if there is metadata referencing this value.

iterator_range< use_iterator > uses()

LLVM_ABI StringRef getName() const

Return a constant reference to the value's name.

self_iterator getIterator()

constexpr char Align[]

Key for Kernel::Arg::Metadata::mAlign.

initializer< Ty > init(const Ty &Val)

PointerTypeMap run(const Module &M)

Compute the PointerTypeMap for the module M.

NodeAddr< UseNode * > Use

friend class Instruction

Iterator for Instructions in a `BasicBlock.

constexpr size_t MaxAlignment

This is an optimization pass for GlobalISel generic memory operations.

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

FunctionAddr VTableAddr Value

void stable_sort(R &&Range)

auto enumerate(FirstRange &&First, RestRanges &&...Rest)

Given two or more input ranges, returns a new range whose values are tuples (A, B,...

decltype(auto) dyn_cast(const From &Val)

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

LLVM_ABI bool getUnderlyingObjectsForCodeGen(const Value *V, SmallVectorImpl< Value * > &Objects)

This is a wrapper around getUnderlyingObjects and adds support for basic ptrtoint+arithmetic+inttoptr...

AnalysisManager< MachineFunction > MachineFunctionAnalysisManager

LLVM_ABI PreservedAnalyses getMachineFunctionPassPreservedAnalyses()

Returns the minimum set of Analyses that all machine function passes must preserve.

auto dyn_cast_or_null(const Y &Val)

void sort(IteratorTy Start, IteratorTy End)

LLVM_ABI raw_ostream & dbgs()

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

FunctionAddr VTableAddr Count

class LLVM_GSL_OWNER SmallVector

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

@ Ref

The access may reference the value stored in memory.

@ First

Helpers to iterate all locations in the MemoryEffectsBase class.

LLVM_ABI char & StackColoringLegacyID

StackSlotColoring - This pass performs stack coloring and merging.

Definition StackColoring.cpp:521

decltype(auto) cast(const From &Val)

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

iterator_range< df_iterator< T > > depth_first(const T &G)

LLVM_ABI Printable printMBBReference(const MachineBasicBlock &MBB)

Prints a machine basic block reference.

SmallVector< WinEHHandlerType, 1 > HandlerArray