StackSlotColoring.cpp Source File (original) (raw)

43#include

44#include

45#include

46#include

48using namespace llvm;

50#define DEBUG_TYPE "stack-slot-coloring"

55 cl::desc("Suppress slot sharing during stack coloring"));

59 STATISTIC(NumEliminated, "Number of stack slots eliminated due to coloring");

60 STATISTIC(NumDead, "Number of trivially dead stack accesses eliminated");

62namespace {

64class StackSlotColoring {

72 std::vector<LiveInterval *> SSIntervals;

100 class ColorAssignmentInfo {

101

102 LiveInterval *SingleLI = nullptr;

103

104 LiveIntervalUnion *LIU = nullptr;

105

106

107 uint8_t LIUPad[sizeof(LiveIntervalUnion)];

108

109 public:

110 ~ColorAssignmentInfo() {

111 if (LIU)

112 LIU->~LiveIntervalUnion();

113 }

114

115

116

117 bool overlaps(LiveInterval *LI) const {

118 if (LIU)

119 return LiveIntervalUnion::Query(*LI, *LIU).checkInterference();

120 return SingleLI ? SingleLI->overlaps(*LI) : false;

121 }

122

123

125 assert(!overlaps(LI));

126 if (LIU) {

127 LIU->unify(*LI, *LI);

128 } else if (SingleLI) {

129 LIU = new (LIUPad) LiveIntervalUnion(Alloc);

130 LIU->unify(*SingleLI, *SingleLI);

131 LIU->unify(*LI, *LI);

132 SingleLI = nullptr;

133 } else

134 SingleLI = LI;

135 }

136 };

137

139

140

142

143public:

144 StackSlotColoring(MachineFunction &MF, LiveStacks *LS,

145 MachineBlockFrequencyInfo *MBFI, SlotIndexes *Indexes)

146 : MFI(&MF.getFrameInfo()), TII(MF.getSubtarget().getInstrInfo()), LS(LS),

147 MBFI(MBFI), Indexes(Indexes) {}

148 bool run(MachineFunction &MF);

149

150private:

151 void InitializeSlots();

152 void ScanForSpillSlotRefs(MachineFunction &MF);

153 int ColorSlot(LiveInterval *li);

154 bool ColorSlots(MachineFunction &MF);

155 void RewriteInstruction(MachineInstr &MI, SmallVectorImpl &SlotMapping,

156 MachineFunction &MF);

157 bool RemoveDeadStores(MachineBasicBlock *MBB);

158};

159

161public:

162 static char ID;

163

164 StackSlotColoringLegacy() : MachineFunctionPass(ID) {

166 }

167

168 void getAnalysisUsage(AnalysisUsage &AU) const override {

170 AU.addRequired();

172 AU.addRequired();

173 AU.addRequired();

174 AU.addPreserved();

176

177

178

179

180

182 AU.addPreserved();

183

185 }

186

187 bool runOnMachineFunction(MachineFunction &MF) override;

188};

189

190}

191

192char StackSlotColoringLegacy::ID = 0;

193

195

197 "Stack Slot Coloring", false, false)

203

204namespace {

205

206

207

210 return LHS->weight() > RHS->weight();

211 }

212};

213

214}

215

216

217

218void StackSlotColoring::ScanForSpillSlotRefs(MachineFunction &MF) {

220

221

222 for (MachineBasicBlock &MBB : MF) {

223 for (MachineInstr &MI : MBB) {

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

225 if (!MO.isFI())

226 continue;

227 int FI = MO.getIndex();

228 if (FI < 0)

229 continue;

230 if (->hasInterval(FI))

231 continue;

232 LiveInterval &li = LS->getInterval(FI);

233 if (.isDebugInstr())

236 }

237 for (MachineMemOperand *MMO : MI.memoperands()) {

238 if (const FixedStackPseudoSourceValue *FSV =

240 MMO->getPseudoValue())) {

241 int FI = FSV->getFrameIndex();

242 if (FI >= 0)

244 }

245 }

246 }

247 }

248}

249

250

251

252void StackSlotColoring::InitializeSlots() {

254

255

257 UsedColors.resize(1);

258

259 OrigAlignments.resize(LastFI);

260 OrigSizes.resize(LastFI);

261 AllColors[0].resize(LastFI);

262 UsedColors[0].resize(LastFI);

263 Assignments.resize(LastFI);

264

265 using Pair = std::iterator_traitsLiveStacks::iterator::value_type;

266

268

269 Intervals.reserve(LS->getNumIntervals());

270 for (auto &I : *LS)

273 [](Pair *LHS, Pair *RHS) { return LHS->first < RHS->first; });

274

275

277 for (auto *I : Intervals) {

278 LiveInterval &li = I->second;

282 continue;

283

284 SSIntervals.push_back(&li);

287

289 if (StackID != 0) {

290 if (StackID >= AllColors.size()) {

291 AllColors.resize(StackID + 1);

292 UsedColors.resize(StackID + 1);

293 }

294 AllColors[StackID].resize(LastFI);

295 UsedColors[StackID].resize(LastFI);

296 }

297

298 AllColors[StackID].set(FI);

299 }

301

302

304

306

307

308 for (unsigned I = 0, E = AllColors.size(); I != E; ++I)

309 NextColors[I] = AllColors[I].find_first();

310}

311

312

313int StackSlotColoring::ColorSlot(LiveInterval *li) {

314 int Color = -1;

315 bool Share = false;

317 uint8_t StackID = MFI->getStackID(FI);

318

320

321

322 Color = UsedColors[StackID].find_first();

323 while (Color != -1) {

324 if (!Assignments[Color].overlaps(li)) {

325 Share = true;

326 ++NumEliminated;

327 break;

328 }

329 Color = UsedColors[StackID].find_next(Color);

330 }

331 }

332

334 LLVM_DEBUG(dbgs() << "cannot share FIs with different stack IDs\n");

335 Share = false;

336 }

337

338

339

340 if (!Share) {

341 assert(NextColors[StackID] != -1 && "No more spill slots?");

342 Color = NextColors[StackID];

343 UsedColors[StackID].set(Color);

344 NextColors[StackID] = AllColors[StackID].find_next(NextColors[StackID]);

345 }

346

348

349

350 Assignments[Color].add(li, LIUAlloc);

351 LLVM_DEBUG(dbgs() << "Assigning fi#" << FI << " to fi#" << Color << "\n");

352

353

354

355

356 Align Alignment = OrigAlignments[FI];

357 if (!Share || Alignment > MFI->getObjectAlign(Color))

359 int64_t Size = OrigSizes[FI];

362 return Color;

363}

364

365

366

367bool StackSlotColoring::ColorSlots(MachineFunction &MF) {

369 SmallVector<int, 16> SlotMapping(NumObjs, -1);

372 BitVector UsedColors(NumObjs);

373

374 LLVM_DEBUG(dbgs() << "Color spill slot intervals:\n");

376 for (LiveInterval *li : SSIntervals) {

378 int NewSS = ColorSlot(li);

379 assert(NewSS >= 0 && "Stack coloring failed?");

380 SlotMapping[SS] = NewSS;

381 RevMap[NewSS].push_back(SS);

382 SlotWeights[NewSS] += li->weight();

383 UsedColors.set(NewSS);

385 }

386

387 LLVM_DEBUG(dbgs() << "\nSpill slots after coloring:\n");

388 for (LiveInterval *li : SSIntervals) {

391 }

392

394

395#ifndef NDEBUG

396 for (LiveInterval *li : SSIntervals)

399#endif

400

402 return false;

403

404

405 for (unsigned SS = 0, SE = SSRefs.size(); SS != SE; ++SS) {

406 int NewFI = SlotMapping[SS];

407 if (NewFI == -1 || (NewFI == (int)SS))

408 continue;

409

411 SmallVectorImpl<MachineMemOperand *> &RefMMOs = SSRefs[SS];

412 for (MachineMemOperand *MMO : RefMMOs)

413 MMO->setValue(NewSV);

414 }

415

416

417 for (MachineBasicBlock &MBB : MF) {

418 for (MachineInstr &MI : MBB)

419 RewriteInstruction(MI, SlotMapping, MF);

420 RemoveDeadStores(&MBB);

421 }

422

423

424 for (int StackID = 0, E = AllColors.size(); StackID != E; ++StackID) {

425 int NextColor = NextColors[StackID];

426 while (NextColor != -1) {

427 LLVM_DEBUG(dbgs() << "Removing unused stack object fi#" << NextColor << "\n");

429 NextColor = AllColors[StackID].find_next(NextColor);

430 }

431 }

432

433 return true;

434}

435

436

437

438void StackSlotColoring::RewriteInstruction(MachineInstr &MI,

439 SmallVectorImpl &SlotMapping,

440 MachineFunction &MF) {

441

442 for (MachineOperand &MO : MI.operands()) {

443 if (!MO.isFI())

444 continue;

445 int OldFI = MO.getIndex();

446 if (OldFI < 0)

447 continue;

448 int NewFI = SlotMapping[OldFI];

449 if (NewFI == -1 || NewFI == OldFI)

450 continue;

451

453 MO.setIndex(NewFI);

454 }

455

456

457}

458

459

460

461

462

463

464bool StackSlotColoring::RemoveDeadStores(MachineBasicBlock* MBB) {

465

466

467 bool changed = false;

468

469 SmallVector<MachineInstr*, 4> toErase;

470

472 I != E; ++I) {

474 break;

475 int FirstSS, SecondSS;

476 if (TII->isStackSlotCopy(*I, FirstSS, SecondSS) && FirstSS == SecondSS &&

477 FirstSS != -1) {

478 ++NumDead;

479 changed = true;

481 continue;

482 }

483

486

492 continue;

493

494 while ((NextMI != E) && NextMI->isDebugInstr()) {

495 ++NextMI;

496 ++I;

497 }

498 if (NextMI == E) continue;

500 continue;

501 if (FirstSS != SecondSS || LoadReg != StoreReg || FirstSS == -1 ||

503 continue;

504

505 ++NumDead;

506 changed = true;

507

508 if (NextMI->findRegisterUseOperandIdx(LoadReg, nullptr, true) !=

509 -1) {

510 ++NumDead;

511 toErase.push_back(&*ProbableLoadMI);

512 }

513

515 ++I;

516 }

517

518 for (MachineInstr *MI : toErase) {

519 if (Indexes)

521 MI->eraseFromParent();

522 }

523

524 return changed;

525}

526

527bool StackSlotColoring::run(MachineFunction &MF) {

529 dbgs() << "********** Stack Slot Coloring **********\n"

530 << "********** Function: " << MF.getName() << '\n';

531 });

532

534

535 unsigned NumSlots = LS->getNumIntervals();

536 if (NumSlots == 0)

537

538 return false;

539

540

541

542

544 return false;

545

546

547 ScanForSpillSlotRefs(MF);

548 InitializeSlots();

549 Changed = ColorSlots(MF);

550

551 for (int &Next : NextColors)

553

554 SSIntervals.clear();

555 for (auto &RefMMOs : SSRefs)

556 RefMMOs.clear();

557 SSRefs.clear();

558 OrigAlignments.clear();

559 OrigSizes.clear();

560 AllColors.clear();

561 UsedColors.clear();

562 Assignments.clear();

563

565}

566

567bool StackSlotColoringLegacy::runOnMachineFunction(MachineFunction &MF) {

569 return false;

570

571 LiveStacks *LS = &getAnalysis().getLS();

572 MachineBlockFrequencyInfo *MBFI =

573 &getAnalysis().getMBFI();

574 SlotIndexes *Indexes = &getAnalysis().getSI();

575 StackSlotColoring Impl(MF, LS, MBFI, Indexes);

576 return Impl.run(MF);

577}

578

579PreservedAnalyses

586 StackSlotColoring Impl(MF, LS, MBFI, Indexes);

587 bool Changed = Impl.run(MF);

590

598 return PA;

599}

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

const TargetInstrInfo & TII

This file implements the BitVector class.

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

Promote Memory to Register

#define INITIALIZE_PASS_DEPENDENCY(depName)

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

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

This file defines the SmallVector class.

static cl::opt< bool > DisableSharing("no-stack-slot-sharing", cl::init(false), cl::Hidden, cl::desc("Suppress slot sharing during stack coloring"))

static cl::opt< int > DCELimit("ssc-dce-limit", cl::init(-1), cl::Hidden)

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

#define STATISTIC(VARNAME, DESC)

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

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

AnalysisUsage & addPreservedID(const void *ID)

AnalysisUsage & addRequired()

AnalysisUsage & addPreserved()

Add the specified Pass class to the set of analyses preserved by this pass.

LLVM_ABI void setPreservesCFG()

This function should be called by the pass, iff they do not:

Represents analyses that only rely on functions' control flow.

LiveSegments::Allocator Allocator

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

LLVM_ABI void dump() const

void incrementWeight(float Inc)

void setWeight(float Value)

static LLVM_ABI float getSpillWeight(bool isDef, bool isUse, const MachineBlockFrequencyInfo *MBFI, const MachineInstr &MI, ProfileSummaryInfo *PSI=nullptr)

Calculate the spill weight to assign to a single instruction.

MachineInstrBundleIterator< MachineInstr > iterator

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

Analysis pass which computes a MachineDominatorTree.

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

void setObjectSize(int ObjectIdx, int64_t Size)

Change the size of the specified stack object.

Align getObjectAlign(int ObjectIdx) const

Return the alignment of the specified stack object.

bool isSpillSlotObjectIndex(int ObjectIdx) const

Returns true if the specified index corresponds to a spill slot.

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.

bool isDeadObjectIndex(int ObjectIdx) const

Returns true if the specified index corresponds to a dead 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.

PseudoSourceValueManager & getPSVManager() const

StringRef getName() const

getName - Return the name of the corresponding LLVM function.

bool exposesReturnsTwice() const

exposesReturnsTwice - Returns true if the function calls setjmp or any other similar functions with a...

Function & getFunction()

Return the LLVM function that this machine code represents.

static LLVM_ABI PassRegistry * getPassRegistry()

getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...

static PreservedAnalyses all()

Construct a special preserved set that preserves all passes.

LLVM_ABI const PseudoSourceValue * getFixedStack(int FI)

Return a pseudo source value referencing a fixed stack frame entry, e.g., a spill slot.

int stackSlotIndex() const

Compute the frame index from a register value representing a stack slot.

LLVM_ABI void removeMachineInstrFromMaps(MachineInstr &MI, bool AllowBundled=false)

Removes machine instruction (bundle) MI from the mapping.

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 StackSlotColoring.cpp:580

TargetInstrInfo - Interface to description of machine instruction set.

virtual Register isLoadFromStackSlot(const MachineInstr &MI, int &FrameIndex) const

If the specified machine instruction is a direct load from a stack slot, return the virtual or physic...

virtual Register isStoreToStackSlot(const MachineInstr &MI, int &FrameIndex) const

If the specified machine instruction is a direct store to a stack slot, return the virtual or physica...

virtual bool isStackSlotCopy(const MachineInstr &MI, int &DestFrameIndex, int &SrcFrameIndex) const

Return true if the specified machine instruction is a copy of one stack slot to another and has no ot...

static constexpr TypeSize getZero()

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.

This is an optimization pass for GlobalISel generic memory operations.

void stable_sort(R &&Range)

LLVM_ABI char & MachineDominatorsID

MachineDominators - This pass is a machine dominators analysis pass.

AnalysisManager< MachineFunction > MachineFunctionAnalysisManager

LLVM_ABI void initializeStackSlotColoringLegacyPass(PassRegistry &)

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.

class LLVM_GSL_OWNER SmallVector

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

LLVM_ABI char & StackSlotColoringID

StackSlotColoring - This pass performs stack slot coloring.

Definition StackSlotColoring.cpp:194

FunctionAddr VTableAddr Next

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

Definition StackSlotColoring.cpp:209