SpillPlacement.cpp Source File (original) (raw)

38#include

39#include

40#include

41#include

43using namespace llvm;

45#define DEBUG_TYPE "spill-code-placement"

52 "Spill Code Placement Analysis", true, true)

55 "Spill Code Placement Analysis", true, true)

58 AU.setPreservesAll();

62}

106

107

108

116

117

119

121

122

123 for (std::pair<BlockFrequency, unsigned> &L : Links)

124 if (L.second == b) {

125 L.first += w;

126 return;

127 }

128

129 Links.push_back(std::make_pair(w, b));

130 }

131

132

134 switch (direction) {

135 default:

136 break;

139 break;

142 break;

145 break;

146 }

147 }

148

149

150

152

155 for (std::pair<BlockFrequency, unsigned> &L : Links) {

156 if (nodes[L.second].Value == -1)

157 SumN += L.first;

158 else if (nodes[L.second].Value == 1)

159 SumP += L.first;

160 }

161

162

163

164

165

166

167

168

169

171 if (SumN >= SumP + Threshold)

173 else if (SumP >= SumN + Threshold)

175 else

178 }

179

181 const Node nodes[]) const {

182 for (const auto &Elt : Links) {

183 unsigned n = Elt.second;

184

185

187 List.insert(n);

188 }

189 }

190};

191

192bool SpillPlacementWrapperLegacy::runOnMachineFunction(MachineFunction &MF) {

195

196 Impl.run(MF, Bundles, MBFI);

197 return false;

198}

199

201

208 Impl.run(MF, Bundles, MBFI);

209 return Impl;

210}

211

214 MachineFunctionAnalysisManager::Invalidator &Inv) {

217 return true;

218

221}

222

226

227void SpillPlacement::releaseMemory() {

229 TodoList.clear();

230}

231

234 MF = &mf;

235 this->bundles = Bundles;

236 this->MBFI = MBFI;

237

240 TodoList.clear();

242

243

246 for (auto &I : mf) {

247 unsigned Num = I.getNumber();

249 }

250}

251

252

253void SpillPlacement::activate(unsigned n) {

254 TodoList.insert(n);

255 if (ActiveNodes->test(n))

256 return;

257 ActiveNodes->set(n);

258 nodes[n].clear(Threshold);

259

260

261

262

263

264

265

266

267

268

269 if (bundles->getBlocks(n).size() > 100) {

270 nodes[n].BiasP = BlockFrequency(0);

271 BlockFrequency BiasN = MBFI->getEntryFreq();

272 BiasN >>= 4;

273 nodes[n].BiasN = BiasN;

274 }

275}

276

277

278

279

280

281

282void SpillPlacement::setThreshold(BlockFrequency Entry) {

283

284

285 uint64_t Freq = Entry.getFrequency();

286 uint64_t Scaled = (Freq >> 13) + bool(Freq & (1 << 12));

287 Threshold = BlockFrequency(std::max(UINT64_C(1), Scaled));

288}

289

290

291

295

296

298 unsigned ib = bundles->getBundle(LB.Number, false);

299 activate(ib);

300 nodes[ib].addBias(Freq, LB.Entry);

301 }

302

303

305 unsigned ob = bundles->getBundle(LB.Number, true);

306 activate(ob);

307 nodes[ob].addBias(Freq, LB.Exit);

308 }

309 }

310}

311

312

314 for (unsigned B : Blocks) {

316 if (Strong)

317 Freq += Freq;

318 unsigned ib = bundles->getBundle(B, false);

319 unsigned ob = bundles->getBundle(B, true);

320 activate(ib);

321 activate(ob);

322 nodes[ib].addBias(Freq, PrefSpill);

323 nodes[ob].addBias(Freq, PrefSpill);

324 }

325}

326

328 for (unsigned Number : Links) {

329 unsigned ib = bundles->getBundle(Number, false);

330 unsigned ob = bundles->getBundle(Number, true);

331

332

333 if (ib == ob)

334 continue;

335 activate(ib);

336 activate(ob);

338 nodes[ib].addLink(ob, Freq);

339 nodes[ob].addLink(ib, Freq);

340 }

341}

342

344 RecentPositive.clear();

345 for (unsigned n : ActiveNodes->set_bits()) {

346 update(n);

347

348

349 if (nodes[n].mustSpill())

350 continue;

351 if (nodes[n].preferReg())

352 RecentPositive.push_back(n);

353 }

354 return !RecentPositive.empty();

355}

356

357bool SpillPlacement::update(unsigned n) {

358 if ( nodes [n].update(nodes.get(), Threshold))

359 return false;

360 nodes[n].getDissentingNeighbors(TodoList, nodes.get());

361 return true;

362}

363

364

365

367

368

369 RecentPositive.clear();

370

371

372

373

374

375 unsigned Limit = bundles->getNumBundles() * 10;

376 while(Limit-- > 0 && !TodoList.empty()) {

377 unsigned n = TodoList.pop_back_val();

378 if (!update(n))

379 continue;

380 if (nodes[n].preferReg())

381 RecentPositive.push_back(n);

382 }

383}

384

386 RecentPositive.clear();

387 TodoList.clear();

388

389 ActiveNodes = &RegBundles;

390 ActiveNodes->clear();

391 ActiveNodes->resize(bundles->getNumBundles());

392}

393

394bool

396 assert(ActiveNodes && "Call prepare() first");

397

398

399 bool Perfect = true;

400 for (unsigned n : ActiveNodes->set_bits())

401 if (!nodes[n].preferReg()) {

402 ActiveNodes->reset(n);

403 Perfect = false;

404 }

405 ActiveNodes = nullptr;

406 return Perfect;

407}

408

411 switch(C) {

412 case DontCare: return "DontCare";

413 case PrefReg: return "PrefReg";

414 case PrefSpill: return "PrefSpill";

415 case PrefBoth: return "PrefBoth";

416 case MustSpill: return "MustSpill";

417 };

419 };

420

424 << (ChangesValue ? "changes" : "no change") << "}";

425}

426

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

Unify divergent function exit nodes

This file implements the BitVector class.

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

#define INITIALIZE_PASS_DEPENDENCY(depName)

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

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

This templated class represents "all analyses that operate over " (e....

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.

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

void clear()

clear - Removes all bits from the bitvector.

static BlockFrequency max()

Returns the maximum possible frequency, the saturation value.

unsigned getNumBundles() const

getNumBundles - Return the total number of bundles in the CFG.

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

LLVM_ABI BlockFrequency getBlockFreq(const MachineBasicBlock *MBB) const

getblockFreq - Return block frequency.

LLVM_ABI BlockFrequency getEntryFreq() const

Divide a block's BlockFrequency::getFrequency() value by this value to obtain the entry block - relat...

void getAnalysisUsage(AnalysisUsage &AU) const override

getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.

unsigned getNumBlockIDs() const

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

AnalysisType & getAnalysis() const

getAnalysis() - This function is used by subclasses to get to the analysis information ...

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

PreservedAnalysisChecker getChecker() const

Build a checker for this PreservedAnalyses and the specified analysis type.

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

SparseSet - Fast set implementation for objects that can be identified by small unsigned keys.

void clear()

clear - Clears the set.

void setUniverse(unsigned U)

setUniverse - Set the universe size which determines the largest key the set can hold.

SpillPlacement run(MachineFunction &, MachineFunctionAnalysisManager &)

Definition SpillPlacement.cpp:203

void addConstraints(ArrayRef< BlockConstraint > LiveBlocks)

addConstraints - Add constraints and biases.

Definition SpillPlacement.cpp:292

bool finish()

finish - Compute the optimal spill code placement given the constraints.

Definition SpillPlacement.cpp:395

void addPrefSpill(ArrayRef< unsigned > Blocks, bool Strong)

addPrefSpill - Add PrefSpill constraints to all blocks listed.

Definition SpillPlacement.cpp:313

void prepare(BitVector &RegBundles)

prepare - Reset state and prepare for a new spill placement computation.

Definition SpillPlacement.cpp:385

bool scanActiveBundles()

scanActiveBundles - Perform an initial scan of all bundles activated by addConstraints and addLinks,...

Definition SpillPlacement.cpp:343

bool invalidate(MachineFunction &MF, const PreservedAnalyses &PA, MachineFunctionAnalysisManager::Invalidator &Inv)

Definition SpillPlacement.cpp:212

friend class SpillPlacementAnalysis

void addLinks(ArrayRef< unsigned > Links)

addLinks - Add transparent blocks with the given numbers.

Definition SpillPlacement.cpp:327

void iterate()

iterate - Update the network iteratively until convergence, or new bundles are found.

Definition SpillPlacement.cpp:366

BorderConstraint

BorderConstraint - A basic block has separate constraints for entry and exit.

@ MustSpill

A register is impossible, variable must be spilled.

@ DontCare

Block doesn't care / variable not live.

@ PrefBoth

Block entry prefers both register and stack.

@ PrefReg

Block entry/exit prefers a register.

@ PrefSpill

Block entry/exit prefers a stack slot.

SpillPlacement(SpillPlacement &&)

StringRef - Represent a constant reference to a string, i.e.

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.

This is an optimization pass for GlobalISel generic memory operations.

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

iterator_range< typename GraphTraits< GraphType >::nodes_iterator > nodes(const GraphType &G)

AnalysisManager< MachineFunction > MachineFunctionAnalysisManager

LLVM_ABI char & SpillPlacementID

SpillPlacement analysis.

Definition SpillPlacement.cpp:49

LLVM_ABI raw_ostream & dbgs()

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

std::string toString(const APInt &I, unsigned Radix, bool Signed, bool formatAsCLiteral=false, bool UpperCase=true, bool InsertSeparators=false)

Node - Each edge bundle corresponds to a Hopfield node.

Definition SpillPlacement.cpp:72

void addBias(BlockFrequency freq, BorderConstraint direction)

addBias - Bias this node.

Definition SpillPlacement.cpp:133

bool preferReg() const

preferReg - Return true when this node prefers to be in a register.

Definition SpillPlacement.cpp:94

bool update(const Node nodes[], BlockFrequency Threshold)

update - Recompute Value from Bias and Links.

Definition SpillPlacement.cpp:151

BlockFrequency SumLinkWeights

SumLinkWeights - Cached sum of the weights of all links + ThresHold.

Definition SpillPlacement.cpp:91

BlockFrequency BiasN

BiasN - Sum of blocks that prefer a spill.

Definition SpillPlacement.cpp:74

void addLink(unsigned b, BlockFrequency w)

addLink - Add a link to bundle b with weight w.

Definition SpillPlacement.cpp:118

LinkVector Links

Links - (Weight, BundleNo) for all transparent blocks connecting to other bundles.

Definition SpillPlacement.cpp:88

int Value

Value - Output value of this node computed from the Bias and links.

Definition SpillPlacement.cpp:82

BlockFrequency BiasP

BiasP - Sum of blocks that prefer a register.

Definition SpillPlacement.cpp:77

SmallVector< std::pair< BlockFrequency, unsigned >, 4 > LinkVector

Definition SpillPlacement.cpp:84

void clear(BlockFrequency Threshold)

clear - Reset per-query data, but preserve frequencies that only depend on the CFG.

Definition SpillPlacement.cpp:109

bool mustSpill() const

mustSpill - Return True if this node is so biased that it must spill.

Definition SpillPlacement.cpp:100

void getDissentingNeighbors(SparseSet< unsigned > &List, const Node nodes[]) const

Definition SpillPlacement.cpp:180

A special type used by analysis passes to provide an address that identifies that particular analysis...

BlockConstraint - Entry and exit constraints for a basic block.

BorderConstraint Exit

Constraint on block exit.

void dump() const

Definition SpillPlacement.cpp:427

void print(raw_ostream &OS) const

Definition SpillPlacement.cpp:409

bool ChangesValue

True when this block changes the value of the live range.

BorderConstraint Entry

Constraint on block entry.

unsigned Number

Basic block number (from MBB::getNumber()).