GenericDomTreeUpdaterImpl.h Source File (original) (raw)

16#ifndef LLVM_ANALYSIS_GENERICDOMTREEUPDATERIMPL_H

17#define LLVM_ANALYSIS_GENERICDOMTREEUPDATERIMPL_H

24namespace llvm {

26template <typename DerivedT, typename DomTreeT, typename PostDomTreeT>

27template

29 FuncT &F) {

31 if (DT)

32 DT->recalculate(F);

34 PDT->recalculate(F);

35 return;

36 }

46 derived().forceFlushDeletedBB();

47 if (DT)

48 DT->recalculate(F);

50 PDT->recalculate(F);

56}

58template <typename DerivedT, typename DomTreeT, typename PostDomTreeT>

62 return;

66 for (const auto &U : Updates)

70 return;

71 }

73 if (DT)

74 DT->applyUpdates(Updates);

76 PDT->applyUpdates(Updates);

77}

79template <typename DerivedT, typename DomTreeT, typename PostDomTreeT>

83 return;

87 for (const auto &U : Updates) {

88 auto Edge = std::make_pair(U.getFrom(), U.getTo());

100

101

102

103

104

105

106

107

108

109

110

112

113

114

118 else

119 DeduplicatedUpdates.push_back(U);

120 }

121 }

122 }

123

125 return;

126

127 if (DT)

128 DT->applyUpdates(DeduplicatedUpdates);

130 PDT->applyUpdates(DeduplicatedUpdates);

131}

132

133template <typename DerivedT, typename DomTreeT, typename PostDomTreeT>

137 return;

138

142 return;

143 }

144

145 if (DT)

146 splitDTCriticalEdges(E);

148 splitPDTCriticalEdges(E);

149}

150

151template <typename DerivedT, typename DomTreeT, typename PostDomTreeT>

152DomTreeT &

154 assert(DT && "Invalid acquisition of a null DomTree");

157 return *DT;

158}

159

160template <typename DerivedT, typename DomTreeT, typename PostDomTreeT>

161PostDomTreeT &

163 assert(PDT && "Invalid acquisition of a null PostDomTree");

166 return *PDT;

167}

168

169template <typename DerivedT, typename DomTreeT, typename PostDomTreeT>

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

174

175 OS << "Available Trees: ";

177 if (DT)

178 OS << "DomTree ";

180 OS << "PostDomTree ";

181 OS << "\n";

182 } else

183 OS << "None\n";

184

185 OS << "UpdateStrategy: ";

187 OS << "Eager\n";

188 return;

189 } else

190 OS << "Lazy\n";

191 int Index = 0;

192

194 if (BB) {

195 auto S = BB->getName();

196 if (!BB->hasName())

197 S = "(no name)";

198 OS << S << "(" << BB << ")" << Ending;

199 } else {

200 OS << "(badref)" << Ending;

201 }

202 };

203

204 auto printUpdates =

207 if (begin == end)

208 OS << " None\n";

209 Index = 0;

210 for (auto It = begin, ItEnd = end; It != ItEnd; ++It) {

211 if (!It->IsCriticalEdgeSplit) {

212 auto U = It->Update;

213 OS << " " << Index << " : ";

214 ++Index;

215 if (U.getKind() == DomTreeT::Insert)

216 OS << "Insert, ";

217 else

218 OS << "Delete, ";

219 printBlockInfo(U.getFrom(), ", ");

220 printBlockInfo(U.getTo(), "\n");

221 } else {

222 const auto &Edge = It->EdgeSplit;

223 OS << " " << Index++ << " : Split critical edge, ";

224 printBlockInfo(Edge.FromBB, ", ");

225 printBlockInfo(Edge.ToBB, ", ");

226 printBlockInfo(Edge.NewBB, "\n");

227 }

228 }

229 };

230

231 if (DT) {

234 "Iterator out of range.");

235 OS << "Applied but not cleared DomTreeUpdates:\n";

237 OS << "Pending DomTreeUpdates:\n";

239 }

240

241 if (PDT) {

244 "Iterator out of range.");

245 OS << "Applied but not cleared PostDomTreeUpdates:\n";

247 OS << "Pending PostDomTreeUpdates:\n";

249 }

250

251 OS << "Pending DeletedBBs:\n";

252 Index = 0;

254 OS << " " << Index << " : ";

255 ++Index;

256 if (BB->hasName())

257 OS << BB->getName() << "(";

258 else

259 OS << "(no name)(";

260 OS << BB << ")\n";

261 }

262#endif

263}

264

265template <typename DerivedT, typename DomTreeT, typename PostDomTreeT>

266template

268 PostDomTreeT>::applyUpdatesImpl() {

269 auto *DomTree = [&]() {

270 if constexpr (IsForward)

271 return DT;

272 else

273 return PDT;

274 }();

275

276 if (Strategy != UpdateStrategy::Lazy || !DomTree)

277 return;

278 size_t &PendUpdateIndex = IsForward ? PendDTUpdateIndex : PendPDTUpdateIndex;

279

280

281 while (IsForward ? hasPendingDomTreeUpdates()

282 : hasPendingPostDomTreeUpdates()) {

283 auto I = PendUpdates.begin() + PendUpdateIndex;

284 const auto E = PendUpdates.end();

285 assert(I < E && "Iterator range invalid; there should be DomTree updates.");

286 if (->IsCriticalEdgeSplit) {

288 for (; I != E && ->IsCriticalEdgeSplit; ++I)

289 NormalUpdates.push_back(I->Update);

290 DomTree->applyUpdates(NormalUpdates);

291 PendUpdateIndex += NormalUpdates.size();

292 } else {

294 for (; I != E && I->IsCriticalEdgeSplit; ++I)

295 CriticalEdges.push_back(I->EdgeSplit);

296 IsForward ? splitDTCriticalEdges(CriticalEdges)

297 : splitPDTCriticalEdges(CriticalEdges);

298 PendUpdateIndex += CriticalEdges.size();

299 }

300 }

301}

302

303template <typename DerivedT, typename DomTreeT, typename PostDomTreeT>

306 const auto *From = Update.getFrom();

307 const auto *To = Update.getTo();

308 const auto Kind = Update.getKind();

309

310

311

312

313

315

316

317

318

319

320 if (Kind == DomTreeT::Insert && !HasEdge)

321 return false;

322

323

324 if (Kind == DomTreeT::Delete && HasEdge)

325 return false;

326

327 return true;

328}

329

330template <typename DerivedT, typename DomTreeT, typename PostDomTreeT>

334 if (DT->getNode(DelBB))

335 DT->eraseNode(DelBB);

336

338 if (PDT->getNode(DelBB))

339 PDT->eraseNode(DelBB);

340}

341

342template <typename DerivedT, typename DomTreeT, typename PostDomTreeT>

346 derived().forceFlushDeletedBB();

347}

348

349template <typename DerivedT, typename DomTreeT, typename PostDomTreeT>

353 return;

354

356

357

358 if ()

360 if ( PDT )

362

365 const auto E = PendUpdates.begin() + dropIndex;

366 assert(B <= E && "Iterator out of range.");

368

371}

372

373template <typename DerivedT, typename DomTreeT, typename PostDomTreeT>

376

377 if (!DT || Edges.empty())

378 return;

379

380

381

382

383

384

385

387 for (auto &Edge : Edges)

388 NewBBs.insert(Edge.NewBB);

389

390

391

392

394

395

396

397 for (const auto &[Idx, Edge] : enumerate(Edges)) {

398

399 BasicBlockT *Succ = Edge.ToBB;

400 auto *SuccDTNode = DT->getNode(Succ);

401

402 for (BasicBlockT *PredBB : predecessors(Succ)) {

403 if (PredBB == Edge.NewBB)

404 continue;

405

406

407

408

409

410

411

412

413

414

415

416

417

418 if (NewBBs.contains(PredBB)) {

419 assert(pred_size(PredBB) == 1 && "A basic block resulting from a "

420 "critical edge split has more "

421 "than one predecessor!");

423 }

424 if (!DT->dominates(SuccDTNode, DT->getNode(PredBB))) {

425 IsNewIDom[Idx] = false;

426 break;

427 }

428 }

429 }

430

431

432 for (const auto &[Idx, Edge] : enumerate(Edges)) {

433

434 auto *NewDTNode = DT->addNewBlock(Edge.NewBB, Edge.FromBB);

435

436

437

438

439 if (IsNewIDom[Idx])

440 DT->changeImmediateDominator(DT->getNode(Edge.ToBB), NewDTNode);

441 }

442}

443

444

445

446template <typename DerivedT, typename DomTreeT, typename PostDomTreeT>

449

450 if (!PDT || Edges.empty())

451 return;

452

453 std::vector Updates;

454 for (const auto &Edge : Edges) {

455 Updates.push_back({PostDomTreeT::Insert, Edge.FromBB, Edge.NewBB});

456 Updates.push_back({PostDomTreeT::Insert, Edge.NewBB, Edge.ToBB});

458 Updates.push_back({PostDomTreeT::Delete, Edge.FromBB, Edge.ToBB});

459 }

461}

462

463}

464

465#endif

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

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

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

#define LLVM_DUMP_METHOD

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

std::pair< BasicBlock *, BasicBlock * > Edge

This file implements the SmallBitVector class.

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

const_pointer const_iterator

size_t size() const

size - Get the array size.

bool empty() const

empty - Check if the array is empty.

SmallPtrSet< BasicBlockT *, 8 > DeletedBBs

DomTreeT & getDomTree()

Flush DomTree updates and return DomTree.

Definition GenericDomTreeUpdaterImpl.h:153

PostDomTreeT & getPostDomTree()

Flush PostDomTree updates and return PostDomTree.

Definition GenericDomTreeUpdaterImpl.h:162

void applyPostDomTreeUpdates()

Helper function to apply all pending PostDomTree updates.

void applyUpdatesPermissive(ArrayRef< UpdateT > Updates)

Submit updates to all available trees.

Definition GenericDomTreeUpdaterImpl.h:81

void applyUpdates(ArrayRef< UpdateT > Updates)

Submit updates to all available trees.

Definition GenericDomTreeUpdaterImpl.h:59

bool IsRecalculatingPostDomTree

void eraseDelBBNode(BasicBlockT *DelBB)

Erase Basic Block node before it is unlinked from Function in the DomTree and PostDomTree.

Definition GenericDomTreeUpdaterImpl.h:331

bool hasPendingUpdates() const

Returns true if either of DT or PDT is valid and the tree has at least one update pending.

bool isSelfDominance(UpdateT Update) const

Returns true if the update is self dominance.

const UpdateStrategy Strategy

typename DomTreeT::UpdateType UpdateT

typename DomTreeT::NodeType BasicBlockT

void recalculate(FuncT &F)

Notify DTU that the entry block was replaced.

Definition GenericDomTreeUpdaterImpl.h:28

void tryFlushDeletedBB()

Helper function to flush deleted BasicBlocks if all available trees are up-to-date.

Definition GenericDomTreeUpdaterImpl.h:344

void dropOutOfDateUpdates()

Drop all updates applied by all available trees and delete BasicBlocks if all available trees are up-...

Definition GenericDomTreeUpdaterImpl.h:351

bool IsRecalculatingDomTree

size_t PendPDTUpdateIndex

void splitCriticalEdge(BasicBlockT *FromBB, BasicBlockT *ToBB, BasicBlockT *NewBB)

Apply updates that the critical edge (FromBB, ToBB) has been split with NewBB.

Definition GenericDomTreeUpdaterImpl.h:134

void applyDomTreeUpdates()

Helper function to apply all pending DomTree updates.

bool isUpdateValid(UpdateT Update) const

Returns true if the update appears in the LLVM IR.

Definition GenericDomTreeUpdaterImpl.h:304

SmallVector< DomTreeUpdate, 16 > PendUpdates

LLVM_DUMP_METHOD void dump() const

Debug method to help view the internal state of this class.

Definition GenericDomTreeUpdaterImpl.h:171

bool isLazy() const

Returns true if the current strategy is Lazy.

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

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

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

bool contains(ConstPtrType Ptr) const

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

SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...

std::pair< const_iterator, bool > insert(const T &V)

insert - Insert an element into the set if it isn't already there.

void push_back(const T &Elt)

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

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.

This is an optimization pass for GlobalISel generic memory operations.

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

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

auto successors(const MachineBasicBlock *BB)

auto pred_size(const MachineBasicBlock *BB)

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

auto pred_begin(const MachineBasicBlock *BB)

auto predecessors(const MachineBasicBlock *BB)

bool is_contained(R &&Range, const E &Element)

Returns true if Element is found in Range.

Helper structure used to hold all the basic blocks involved in the split of a critical edge.