Dominators.cpp Source File (original) (raw)

18#include "llvm/Config/llvm-config.h"

31#include

33namespace llvm {

37}

38using namespace llvm;

43 cl::desc("Verify dominator info (time consuming)"));

45#ifdef EXPENSIVE_CHECKS

47#else

49#endif

52 unsigned NumEdgesToEnd = 0;

54 if (Succ == End)

55 ++NumEdgesToEnd;

56 if (NumEdgesToEnd >= 2)

57 return false;

58 }

59 assert(NumEdgesToEnd == 1);

60 return true;

61}

79template void llvm::DomTreeBuilder::CalculateDomTreeBuilder::BBDomTree(

81template void

82llvm::DomTreeBuilder::CalculateWithUpdatesDomTreeBuilder::BBDomTree(

85template void llvm::DomTreeBuilder::CalculateDomTreeBuilder::BBPostDomTree(

89template void llvm::DomTreeBuilder::InsertEdgeDomTreeBuilder::BBDomTree(

91template void llvm::DomTreeBuilder::InsertEdgeDomTreeBuilder::BBPostDomTree(

94template void llvm::DomTreeBuilder::DeleteEdgeDomTreeBuilder::BBDomTree(

96template void llvm::DomTreeBuilder::DeleteEdgeDomTreeBuilder::BBPostDomTree(

99template void llvm::DomTreeBuilder::ApplyUpdatesDomTreeBuilder::BBDomTree(

102template void llvm::DomTreeBuilder::ApplyUpdatesDomTreeBuilder::BBPostDomTree(

105

106template bool llvm::DomTreeBuilder::VerifyDomTreeBuilder::BBDomTree(

109template bool llvm::DomTreeBuilder::VerifyDomTreeBuilder::BBPostDomTree(

112

115

116

120}

121

123 Instruction *UserInst = cast(U.getUser());

124 if (auto *PN = dyn_cast(UserInst))

125

126

127 return dominates(BB, PN->getIncomingBlock(U));

128 else

130}

131

132

133

134

137 const Instruction *Def = dyn_cast(DefV);

138 if (!Def) {

139 assert((isa(DefV) || isa(DefV)) &&

140 "Should be called with an instruction, argument or constant");

141 return true;

142 }

143

145 const BasicBlock *DefBB = Def->getParent();

146

147

149 return true;

150

151

153 return false;

154

155

156 if (Def == User)

157 return false;

158

159

160

161

162

163 if (isa(Def) || isa(Def) || isa(User))

165

166 if (DefBB != UseBB)

168

169 return Def->comesBefore(User);

170}

171

172

173

176 const BasicBlock *DefBB = Def->getParent();

177

178

180 return true;

181

182

184 return false;

185

186 if (DefBB == UseBB)

187 return false;

188

189

190

191 if (const auto *II = dyn_cast(Def)) {

192 BasicBlock *NormalDest = II->getNormalDest();

195 }

196

198}

199

202

203

207 return false;

208

209

210

211 if (End->getSinglePredecessor())

212 return true;

213

214

215

216

217

218

219

220

221

222

223

224

225

226

227

228

229

230

231

232

233

234 int IsDuplicateEdge = 0;

236 if (BB == Start) {

237

238

239 if (IsDuplicateEdge++)

240 return false;

241 continue;

242 }

243

245 return false;

246 }

247 return true;

248}

249

251 Instruction *UserInst = cast(U.getUser());

252

253 PHINode *PN = dyn_cast(UserInst);

256 return true;

257

258

259

261 if (PN)

263 else

266}

267

269 const Instruction *Def = dyn_cast(DefV);

270 if (!Def) {

271 assert((isa(DefV) || isa(DefV)) &&

272 "Should be called with an instruction, argument or constant");

273 return true;

274 }

275

276 Instruction *UserInst = cast(U.getUser());

277 const BasicBlock *DefBB = Def->getParent();

278

279

280

281

283 if (PHINode *PN = dyn_cast(UserInst))

284 UseBB = PN->getIncomingBlock(U);

285 else

287

288

290 return true;

291

292

294 return false;

295

296

297

298

299

300

301 if (const InvokeInst *II = dyn_cast(Def)) {

302 BasicBlock *NormalDest = II->getNormalDest();

305 }

306

307

308

309 if (DefBB != UseBB)

311

312

313

314

315 if (isa(UserInst))

316 return true;

317

318 return Def->comesBefore(UserInst);

319}

320

322 Instruction *I = dyn_cast(U.getUser());

323

324

325

326 if () return true;

327

328

329 if (PHINode *PN = dyn_cast(I))

331

332

334}

335

336

340 return true;

342}

343

348 if (BB1 == BB2)

349 return I1->comesBefore(I2) ? I1 : I2;

351 return I1;

353 return I2;

355 if (BB1 == DomBB)

356 return I1;

357 if (BB2 == DomBB)

358 return I2;

360}

361

362

363

364

365

366

367

368

369

370

375 return DT;

376}

377

379

381

384 OS << "DominatorTree for function: " << F.getName() << "\n";

386

388}

389

394 (void)DT;

396}

397

398

399

400

401

402

403

404

405

406

408

411}

412

414 "Dominator Tree Construction", true, true)

415

418 return false;

419}

420

423 assert(DT.verify(DominatorTree::VerificationLevel::Full));

425 assert(DT.verify(DominatorTree::VerificationLevel::Basic));

426}

427

430}

BlockVerifier::State From

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

static constexpr bool ExpensiveChecksEnabled

static cl::opt< bool, true > VerifyDomInfoX("verify-dom-info", cl::location(VerifyDomInfo), cl::Hidden, cl::desc("Verify dominator info (time consuming)"))

static bool runOnFunction(Function &F, bool PostInlining)

Generic dominator tree construction - this file provides routines to construct immediate dominator in...

This file provides various utilities for inspecting and working with the control flow graph in LLVM I...

This header defines various interfaces for pass management in LLVM.

uint64_t IntrinsicInst * II

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

static constexpr bool ExpensiveChecksEnabled

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

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

API to communicate dependencies between analyses during invalidation.

A container for analyses that lazily runs them and caches their results.

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

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

This class represents an incoming formal argument to a Function.

const BasicBlock * getEnd() const

const BasicBlock * getStart() const

bool isSingleEdge() const

Check if this is the only edge between Start and End.

LLVM Basic Block Representation.

const Instruction * getTerminator() const LLVM_READONLY

Returns the terminator instruction if the block is well formed or null if the block is not well forme...

Represents analyses that only rely on functions' control flow.

This is an important base class in LLVM.

Base class for the actual dominator tree node.

Analysis pass which computes a DominatorTree.

DominatorTree run(Function &F, FunctionAnalysisManager &)

Run the analysis pass over a function and produce a dominator tree.

Core dominator tree base class.

void print(raw_ostream &O) const

print - Convert to human readable form

bool verify(VerificationLevel VL=VerificationLevel::Full) const

verify - checks if the tree is correct.

void recalculate(ParentType &Func)

recalculate - compute a dominator tree for the given function

bool properlyDominates(const DomTreeNodeBase< BasicBlock > *A, const DomTreeNodeBase< BasicBlock > *B) const

properlyDominates - Returns true iff A dominates B and A != B.

DominatorTreePrinterPass(raw_ostream &OS)

PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)

Legacy analysis pass which computes a DominatorTree.

DominatorTreeWrapperPass()

void print(raw_ostream &OS, const Module *M=nullptr) const override

print - Print out the internal state of the pass.

void verifyAnalysis() const override

verifyAnalysis() - This member can be implemented by a analysis pass to check state of analysis infor...

Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.

bool isReachableFromEntry(const Use &U) const

Provide an overload for a Use.

Instruction * findNearestCommonDominator(Instruction *I1, Instruction *I2) const

Find the nearest instruction I that dominates both I1 and I2, in the sense that a result produced bef...

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

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

bool invalidate(Function &F, const PreservedAnalyses &PA, FunctionAnalysisManager::Invalidator &)

Handle invalidation explicitly.

FunctionPass class - This class is used to implement most global optimizations.

A Module instance is used to store all the information related to an LLVM module.

BasicBlock * getIncomingBlock(unsigned i) const

Return incoming basic block number i.

static PassRegistry * getPassRegistry()

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

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

static PreservedAnalyses all()

Construct a special preserved set that preserves all passes.

PreservedAnalysisChecker getChecker() const

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

A Use represents the edge between a Value definition and its users.

LLVM Value Representation.

const ParentTy * getParent() const

This class implements an extremely fast bulk output stream that can only output to a stream.

LocationClass< Ty > location(Ty &L)

This is an optimization pass for GlobalISel generic memory operations.

auto successors(const MachineBasicBlock *BB)

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

void initializeDominatorTreeWrapperPassPass(PassRegistry &)

bool VerifyDomInfo

Enables verification of dominator trees.

auto predecessors(const MachineBasicBlock *BB)

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

PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)