Dominators.cpp Source File (original) (raw)

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

32#include

34namespace llvm {

38}

39using namespace llvm;

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

46#ifdef EXPENSIVE_CHECKS

48#else

50#endif

53 unsigned NumEdgesToEnd = 0;

55 if (Succ == End)

56 ++NumEdgesToEnd;

57 if (NumEdgesToEnd >= 2)

58 return false;

59 }

60 assert(NumEdgesToEnd == 1);

61 return true;

62}

100

107

116

125

127 FunctionAnalysisManager::Invalidator &) {

128

129

133}

134

138

139

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

141 else

143}

144

145

146

147

151 if (!Def) {

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

154 return true;

155 }

156

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

159

160

162 return true;

163

164

166 return false;

167

168

169 if (Def == User)

170 return false;

171

172

173

174

175

178

179 if (DefBB != UseBB)

181

182 return Def->comesBefore(User);

183}

184

185

186

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

190

191

193 return true;

194

195

197 return false;

198

199 if (DefBB == UseBB)

200 return false;

201

202

203

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

208 }

209

211}

212

215

216

220 return false;

221

222

223

225 return true;

226

227

228

229

230

231

232

233

234

235

236

237

238

239

240

241

242

243

244

245

246

247 int IsDuplicateEdge = 0;

249 if (BB == Start) {

250

251

252 if (IsDuplicateEdge++)

253 return false;

254 continue;

255 }

256

258 return false;

259 }

260 return true;

261}

262

265

269 return true;

270

271

272

274 if (PN)

276 else

279}

280

283 if (!Def) {

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

286 return true;

287 }

288

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

291

292

293

294

297 UseBB = PN->getIncomingBlock(U);

298 else

300

301

303 return true;

304

305

307 return false;

308

309

310

311

312

313

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

318 }

319

320

321

322 if (DefBB != UseBB)

324

325

326

327

329 return true;

330

331 return Def->comesBefore(UserInst);

332}

333

336

337

338

339 if () return true;

340

341

344

345

347}

348

349

356

361 if (BB1 == BB2)

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

364 return I1;

366 return I2;

368 if (BB1 == DomBB)

369 return I1;

370 if (BB2 == DomBB)

371 return I2;

373}

374

375

376

377

378

379

380

381

382

383

390

392

394

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

399

401}

402

410

411

412

413

414

415

416

417

418

419

421

425

427 "Dominator Tree Construction", true, true)

428

430 DT.recalculate(F);

431 return false;

432}

433

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

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

439}

440

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

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

#define LLVM_EXPORT_TEMPLATE

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

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.

This class represents an incoming formal argument to a Function.

const BasicBlock * getEnd() const

const BasicBlock * getStart() const

LLVM_ABI bool isSingleEdge() const

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

Definition Dominators.cpp:52

LLVM Basic Block Representation.

LLVM_ABI const BasicBlock * getSinglePredecessor() const

Return the predecessor of this block if it has a single predecessor block.

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.

LLVM_ABI DominatorTree run(Function &F, FunctionAnalysisManager &)

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

Definition Dominators.cpp:384

Core dominator tree base class.

void recalculate(ParentType &Func)

recalculate - compute a dominator tree for the given function

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

LLVM_ABI DominatorTreePrinterPass(raw_ostream &OS)

Definition Dominators.cpp:393

LLVM_ABI PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)

Definition Dominators.cpp:395

Legacy analysis pass which computes a DominatorTree.

DominatorTreeWrapperPass()

Definition Dominators.cpp:422

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

print - Print out the internal state of the pass.

Definition Dominators.cpp:441

void verifyAnalysis() const override

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

Definition Dominators.cpp:434

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

LLVM_ABI bool isReachableFromEntry(const Use &U) const

Provide an overload for a Use.

Definition Dominators.cpp:334

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

Definition Dominators.cpp:357

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

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

Definition Dominators.cpp:135

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

Handle invalidation explicitly.

Definition Dominators.cpp:126

LLVM_ABI bool dominates(const Instruction *Def, const BasicBlock *BB) const

Returns true if Def would dominate a use in any instruction in BB.

Definition Dominators.cpp:187

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

bool Verify(const DomTreeT &DT, typename DomTreeT::VerificationLevel VL)

GraphDiff< BasicBlock *, false > BBDomTreeGraphDiff

void CalculateWithUpdates(DomTreeT &DT, ArrayRef< typename DomTreeT::UpdateType > Updates)

GraphDiff< BasicBlock *, true > BBPostDomTreeGraphDiff

void DeleteEdge(DomTreeT &DT, typename DomTreeT::NodePtr From, typename DomTreeT::NodePtr To)

void Calculate(DomTreeT &DT)

PostDomTreeBase< BasicBlock > BBPostDomTree

void ApplyUpdates(DomTreeT &DT, GraphDiff< typename DomTreeT::NodePtr, DomTreeT::IsPostDominator > &PreViewCFG, GraphDiff< typename DomTreeT::NodePtr, DomTreeT::IsPostDominator > *PostViewCFG)

void InsertEdge(DomTreeT &DT, typename DomTreeT::NodePtr From, typename DomTreeT::NodePtr To)

DomTreeBase< BasicBlock > BBDomTree

LocationClass< Ty > location(Ty &L)

This is an optimization pass for GlobalISel generic memory operations.

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

decltype(auto) dyn_cast(const From &Val)

dyn_cast - Return the argument parameter cast to the specified type.

auto successors(const MachineBasicBlock *BB)

LLVM_ABI void initializeDominatorTreeWrapperPassPass(PassRegistry &)

bool isa(const From &Val)

isa - Return true if the parameter to the template is an instance of one of the template type argu...

LLVM_ABI bool VerifyDomInfo

Enables verification of dominator trees.

Definition Dominators.cpp:41

decltype(auto) cast(const From &Val)

cast - Return the argument parameter cast to the specified type.

auto predecessors(const MachineBasicBlock *BB)

AnalysisManager< Function > FunctionAnalysisManager

Convenience typedef for the Function analysis manager.

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

LLVM_ABI PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)

Definition Dominators.cpp:403