RegAllocGreedy.h Source File (original) (raw)

61public:

68 struct RegInfo {

73 unsigned Cascade = 0;

75 RegInfo() = default;

76 };

79 unsigned NextCascade = 1;

81 public:

92 Info.grow(Reg.id());

93 Info[Reg].Stage = Stage;

94 }

100

101

103 Info.grow(Reg.id());

105 }

106

108

110 Info.grow(Reg.id());

111 Info[Reg].Cascade = Cascade;

112 }

113

116 if (!Cascade) {

117 Cascade = NextCascade++;

119 }

120 return Cascade;

121 }

122

125 if (!Cascade)

126 Cascade = NextCascade;

127 return Cascade;

128 }

129

130 template

132 for (; Begin != End; ++Begin) {

134 Info.grow(Reg.id());

136 Info[Reg].Stage = NewStage;

137 }

138 }

140 };

141

148

149

150

152 return RegClassPriorityTrumpsGlobalness;

153 }

155

156

157private:

158

159 using PQueue = std::priority_queue<std::pair<unsigned, unsigned>>;

161

162

163

164 using RecoloringStack =

166

167

169

170

172

173

182 LiveStacks *LSS = nullptr;

183

186

187

188 std::unique_ptr SpillerInstance;

189 PQueue Queue;

190 std::unique_ptr VRAI;

191 std::optional ExtraInfo;

192 std::unique_ptr EvictAdvisor;

193

194 std::unique_ptr PriorityAdvisor;

195

196

197

198

199 enum CutOffStage {

200

201 CO_None = 0,

202

203

204 CO_Depth = 1,

205

206

207 CO_Interf = 2

208 };

209

210 uint8_t CutOffInfo = CutOffStage::CO_None;

211

212#ifndef NDEBUG

213 static const char *const StageName[];

214#endif

215

216

217 std::unique_ptr SA;

218 std::unique_ptr SE;

219

220

221 InterferenceCache IntfCache;

222

223

224 SmallVector<SpillPlacement::BlockConstraint, 8> SplitConstraints;

225

226

227 struct GlobalSplitCandidate {

228

229 MCRegister PhysReg;

230

231

232 unsigned IntvIdx;

233

234

235 InterferenceCache::Cursor Intf;

236

237

238 BitVector LiveBundles;

239 SmallVector<unsigned, 8> ActiveBlocks;

240

241 void reset(InterferenceCache &Cache, MCRegister Reg) {

242 PhysReg = Reg;

243 IntvIdx = 0;

244 Intf.setPhysReg(Cache, Reg);

245 LiveBundles.clear();

246 ActiveBlocks.clear();

247 }

248

249

250 unsigned getBundles(SmallVectorImpl &B, unsigned C) {

251 unsigned Count = 0;

252 for (unsigned I : LiveBundles.set_bits())

253 if (B[I] == NoCand) {

254 B[I] = C;

256 }

258 }

259 };

260

261

262

263

264 SmallVector<GlobalSplitCandidate, 32> GlobalCand;

265

266 enum : unsigned { NoCand = ~0u };

267

268

269

270 SmallVector<unsigned, 32> BundleCand;

271

272

273 BlockFrequency CSRCost;

274

275

276 SmallSetVector<const LiveInterval *, 8> SetOfBrokenHints;

277

278

279

280 ArrayRef<uint8_t> RegCosts;

281

282

283

284 bool RegClassPriorityTrumpsGlobalness = false;

285

286 bool ReverseLocalAssignment = false;

287

288public:

289 RAGreedy(RequiredAnalyses &Analyses, const RegAllocFilterFunc F = nullptr);

290

292 void enqueueImpl(const LiveInterval *LI) override;

296 void aboutToRemoveInterval(const LiveInterval &) override;

297

298

300

301 void releaseMemory();

302

303private:

306 RecoloringStack &, unsigned = 0);

307

308 bool LRE_CanEraseVirtReg(Register) override;

309 void LRE_WillShrinkVirtReg(Register) override;

311 void enqueue(PQueue &CurQueue, const LiveInterval *LI);

312 const LiveInterval *dequeue(PQueue &CurQueue);

313

314 bool hasVirtRegAlloc();

318 bool growRegion(GlobalSplitCandidate &Cand);

319 BlockFrequency calcGlobalSplitCost(GlobalSplitCandidate &,

321 bool calcCompactRegion(GlobalSplitCandidate &);

326 bool mayRecolorAllInterferences(MCRegister PhysReg,

328 SmallLISet &RecoloringCandidates,

330

338

339 unsigned calculateRegionSplitCostAroundReg(MCRegister PhysReg,

342 unsigned &NumCands,

343 unsigned &BestCand);

344

345 unsigned calculateRegionSplitCost(const LiveInterval &VirtReg,

348 unsigned &NumCands, bool IgnoreCSR);

349

351 bool HasCompact,

353

357

358

361 uint8_t &CostPerUseLimit,

363 void initializeCSRCost();

375 unsigned);

378 void tryHintRecoloring(const LiveInterval &);

379 void tryHintsRecoloring();

380

381

382 struct HintInfo {

383

385

387

388

390

392 : Freq(Freq), Reg(Reg), PhysReg(PhysReg) {}

393 };

394 using HintsInfo = SmallVector<HintInfo, 4>;

395

396 BlockFrequency getBrokenHintFreq(const HintsInfo &, MCRegister);

397 void collectHintInfo(Register, HintsInfo &);

398

399

400 struct RAGreedyStats {

401 unsigned Reloads = 0;

402 unsigned FoldedReloads = 0;

403 unsigned ZeroCostFoldedReloads = 0;

404 unsigned Spills = 0;

405 unsigned FoldedSpills = 0;

407 float ReloadsCost = 0.0f;

408 float FoldedReloadsCost = 0.0f;

409 float SpillsCost = 0.0f;

410 float FoldedSpillsCost = 0.0f;

411 float CopiesCost = 0.0f;

412

413 bool isEmpty() {

414 return !(Reloads || FoldedReloads || Spills || FoldedSpills ||

415 ZeroCostFoldedReloads || Copies);

416 }

417

418 void add(const RAGreedyStats &other) {

419 Reloads += other.Reloads;

420 FoldedReloads += other.FoldedReloads;

421 ZeroCostFoldedReloads += other.ZeroCostFoldedReloads;

422 Spills += other.Spills;

423 FoldedSpills += other.FoldedSpills;

424 Copies += other.Copies;

425 ReloadsCost += other.ReloadsCost;

426 FoldedReloadsCost += other.FoldedReloadsCost;

427 SpillsCost += other.SpillsCost;

428 FoldedSpillsCost += other.FoldedSpillsCost;

429 CopiesCost += other.CopiesCost;

430 }

431

432 void report(MachineOptimizationRemarkMissed &R);

433 };

434

435

436 RAGreedyStats computeStats(MachineBasicBlock &MBB);

437

438

439 RAGreedyStats reportStats(MachineLoop *L);

440

441

442 void reportStats();

443};