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) {

30 if (Strategy == UpdateStrategy::Eager) {

31 if (DT)

33 if (PDT)

34 PDT->recalculate(F);

35 return;

36 }

42 IsRecalculatingDomTree = IsRecalculatingPostDomTree = true;

46 derived().forceFlushDeletedBB();

47 if (DT)

49 if (PDT)

50 PDT->recalculate(F);

53 IsRecalculatingDomTree = IsRecalculatingPostDomTree = false;

54 PendDTUpdateIndex = PendPDTUpdateIndex = PendUpdates.size();

55 dropOutOfDateUpdates();

56}

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

61 if (!DT && !PDT)

62 return;

64 if (Strategy == UpdateStrategy::Lazy) {

65 PendUpdates.reserve(PendUpdates.size() + Updates.size());

66 for (const auto &U : Updates)

67 if (!isSelfDominance(U))

68 PendUpdates.push_back(U);

70 return;

71 }

73 if (DT)

75 if (PDT)

76 PDT->applyUpdates(Updates);

77}

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

82 if (!DT && !PDT)

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

111 if (!isSelfDominance(U) && Seen.insert(Edge).second) {

112

113

114

115 if (isUpdateValid(U)) {

116 if (isLazy())

117 PendUpdates.push_back(U);

118 else

119 DeduplicatedUpdates.push_back(U);

120 }

121 }

122 }

123

124 if (Strategy == UpdateStrategy::Lazy)

125 return;

126

127 if (DT)

129 if (PDT)

130 PDT->applyUpdates(DeduplicatedUpdates);

131}

132

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

136 if (!DT && !PDT)

137 return;

138

140 if (Strategy == UpdateStrategy::Lazy) {

141 PendUpdates.push_back(E);

142 return;

143 }

144

145 if (DT)

146 splitDTCriticalEdges(E);

147 if (PDT)

148 splitPDTCriticalEdges(E);

149}

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

152DomTreeT &

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

155 applyDomTreeUpdates();

156 dropOutOfDateUpdates();

157 return *DT;

158}

159

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

161PostDomTreeT &

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

164 applyPostDomTreeUpdates();

165 dropOutOfDateUpdates();

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: ";

176 if (DT || PDT) {

177 if (DT)

178 OS << "DomTree ";

179 if (PDT)

180 OS << "PostDomTree ";

181 OS << "\n";

182 } else

183 OS << "None\n";

184

185 OS << "UpdateStrategy: ";

186 if (Strategy == UpdateStrategy::Eager) {

187 OS << "Eager\n";

188 return;

189 } else

190 OS << "Lazy\n";

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";

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

211 if (!It->IsCriticalEdgeSplit) {

212 auto U = It->Update;

213 OS << " " << 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) {

232 const auto I = PendUpdates.begin() + PendDTUpdateIndex;

233 assert(PendUpdates.begin() <= I && I <= PendUpdates.end() &&

234 "Iterator out of range.");

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

236 printUpdates(PendUpdates.begin(), I);

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

238 printUpdates(I, PendUpdates.end());

239 }

240

241 if (PDT) {

242 const auto I = PendUpdates.begin() + PendPDTUpdateIndex;

243 assert(PendUpdates.begin() <= I && I <= PendUpdates.end() &&

244 "Iterator out of range.");

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

246 printUpdates(PendUpdates.begin(), I);

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

248 printUpdates(I, PendUpdates.end());

249 }

250

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

253 for (const auto *BB : DeletedBBs) {

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

256 if (BB->hasName())

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

258 else

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

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

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)

290 DomTree->applyUpdates(NormalUpdates);

291 PendUpdateIndex += NormalUpdates.size();

292 } else {

293 SmallVector CriticalEdges;

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>

333 if (DT && !IsRecalculatingDomTree)

336

337 if (PDT && !IsRecalculatingPostDomTree)

338 if (PDT->getNode(DelBB))

339 PDT->eraseNode(DelBB);

340}

341

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

344 PostDomTreeT>::tryFlushDeletedBB() {

345 if (!hasPendingUpdates())

346 derived().forceFlushDeletedBB();

347}

348

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

351 PostDomTreeT>::dropOutOfDateUpdates() {

352 if (Strategy == UpdateStrategy::Eager)

353 return;

354

355 tryFlushDeletedBB();

356

357

358 if (!DT)

359 PendDTUpdateIndex = PendUpdates.size();

360 if (!PDT)

361 PendPDTUpdateIndex = PendUpdates.size();

362

363 const size_t dropIndex = std::min(PendDTUpdateIndex, PendPDTUpdateIndex);

364 const auto B = PendUpdates.begin();

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

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

367 PendUpdates.erase(B, E);

368

369 PendDTUpdateIndex -= dropIndex;

370 PendPDTUpdateIndex -= dropIndex;

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 }

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])

441 }

442}

443

444

445

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

447void GenericDomTreeUpdater<DerivedT, DomTreeT, PostDomTreeT>::

448 splitPDTCriticalEdges(ArrayRef Edges) {

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 }

460 PDT->applyUpdates(Updates);

461}

462

463}

464

465#endif

BlockVerifier::State From

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

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.

Returns the sub type a function will return at a given Idx Should correspond to the result type of an ExtractValue instruction executed with just that one unsigned Idx

assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())

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.

void changeImmediateDominator(DomTreeNodeBase< NodeT > *N, DomTreeNodeBase< NodeT > *NewIDom)

changeImmediateDominator - This method is used to update the dominator tree information when a node's...

DomTreeNodeBase< NodeT > * addNewBlock(NodeT *BB, NodeT *DomBB)

Add a new node to the dominator tree information.

void applyUpdates(ArrayRef< UpdateType > Updates)

Inform the dominator tree about a sequence of CFG edge insertions and deletions and perform a batch u...

void recalculate(ParentType &Func)

recalculate - compute a dominator tree for the given function

void eraseNode(NodeT *BB)

eraseNode - Removes a node from the dominator tree.

DomTreeNodeBase< NodeT > * getNode(const NodeT *BB) const

getNode - return the (Post)DominatorTree node for the specified basic block.

bool dominates(const BasicBlock *BB, const Use &U) const

Return true if the (end of the) basic block BB dominates the use U.

DomTreeT & getDomTree()

Flush DomTree updates and return DomTree.

PostDomTreeT & getPostDomTree()

Flush PostDomTree updates and return PostDomTree.

void applyUpdatesPermissive(ArrayRef< UpdateT > Updates)

Submit updates to all available trees.

void applyUpdates(ArrayRef< UpdateT > Updates)

Submit updates to all available trees.

void eraseDelBBNode(BasicBlockT *DelBB)

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

typename DomTreeT::UpdateType UpdateT

typename DomTreeT::NodeType BasicBlockT

void recalculate(FuncT &F)

Notify DTU that the entry block was replaced.

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

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

bool isUpdateValid(UpdateT Update) const

Returns true if the update appears in the LLVM IR.

LLVM_DUMP_METHOD void dump() const

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

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

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

bool contains(const T &V) const

Check if the SmallSet contains the given element.

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.

const_iterator begin(StringRef path LLVM_LIFETIME_BOUND, Style style=Style::native)

Get begin iterator over path.

const_iterator end(StringRef path LLVM_LIFETIME_BOUND)

Get end iterator over path.

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)

raw_ostream & dbgs()

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

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.