CFG.cpp Source File (original) (raw)

20using namespace llvm;

26 "dom-tree-reachability-max-bbs-to-explore", cl::Hidden,

27 cl::desc("Max number of BBs to explore for reachability analysis"),

36 SmallVectorImpl<std::pair<const BasicBlock*,const BasicBlock*> > &Result) {

37 const BasicBlock *BB = &F.getEntryBlock();

39 return;

48 do {

49 std::pair<const BasicBlock *, const_succ_iterator> &Top = VisitStack.back();

50 const BasicBlock *ParentBB = Top.first;

53 bool FoundNew = false;

55 BB = *I++;

56 if (Visited.insert(BB).second) {

57 FoundNew = true;

58 break;

59 }

61 if (InStack.count(BB))

62 Result.push_back(std::make_pair(ParentBB, BB));

63 }

65 if (FoundNew) {

69 } else {

72 }

73 } while (!VisitStack.empty());

74}

83#ifndef NDEBUG

84 unsigned e = Term->getNumSuccessors();

85#endif

86 for (unsigned i = 0; ; ++i) {

87 assert(i != e && "Didn't find edge?");

88 if (Term->getSuccessor(i) == Succ)

89 return i;

90 }

91}

97 bool AllowIdenticalEdges) {

98 assert(SuccNum < TI->getNumSuccessors() && "Illegal edge specification!");

100}

101

103 bool AllowIdenticalEdges) {

104 assert(TI->isTerminator() && "Must be a terminator to have successors!");

106

108 "No edge between TI's block and Dest.");

109

111

112

113 assert(I != E && "No preds, but we have an edge to the block?");

115 ++I;

116 if (!AllowIdenticalEdges)

117 return I != E;

118

119

120

121 for (; I != E; ++I)

122 if (*I != FirstPred)

123 return true;

124 return false;

125}

126

127

128

131 return L ? L->getOutermostLoop() : nullptr;

132}

133

134template

136 const StopSetT &StopSet,

139

140

141 if (DT) {

142 for (auto *BB : StopSet) {

144 DT = nullptr;

145 break;

146 }

147 }

148 }

149

150

151

152 if (ExclusionSet && !ExclusionSet->empty())

153 DT = nullptr;

154

155

156

157

159 if (LI && ExclusionSet) {

160 for (auto *BB : *ExclusionSet) {

162 LoopsWithHoles.insert(L);

163 }

164 }

165

167 if (LI) {

168 for (auto *StopSetBB : StopSet) {

171 }

172 }

173

176 do {

178 if (!Visited.insert(BB).second)

179 continue;

180 if (StopSet.contains(BB))

181 return true;

182 if (ExclusionSet && ExclusionSet->count(BB))

183 continue;

184 if (DT) {

186 return DT->dominates(BB, StopBB);

187 }))

188 return true;

189 }

190

191 const Loop *Outer = nullptr;

192 if (LI) {

194

195

196

197

198 if (LoopsWithHoles.count(Outer))

199 Outer = nullptr;

200 if (StopLoops.contains(Outer))

201 return true;

202 }

203

204 if (!--Limit) {

205

206

207 return true;

208 }

209

210 if (Outer) {

211

212

213

214 Outer->getExitBlocks(Worklist);

215 } else {

217 }

218 } while (!Worklist.empty());

219

220

221

222 return false;

223}

224

226public:

228

230

232

235

236private:

237 T Elem;

238};

239

248

255 Worklist, StopSet, ExclusionSet, DT, LI);

256}

257

262 assert(A->getParent() == B->getParent() &&

263 "This analysis is function-local!");

264

265 if (DT) {

267 return false;

268 if (!ExclusionSet || ExclusionSet->empty()) {

270 return true;

272 return false;

273 }

274 }

275

278

280}

281

286 assert(A->getParent()->getParent() == B->getParent()->getParent() &&

287 "This analysis is function-local!");

288

289 if (A->getParent() == B->getParent()) {

290

291

292

293

294

296

297

298

299 if (LI && LI->getLoopFor(BB) != nullptr)

300 return true;

301

302

303 if (A == B || A->comesBefore(B))

304 return true;

305

306

307

309 return false;

310

311

314 if (Worklist.empty()) {

315

316 return false;

317 }

318

320 ExclusionSet, DT, LI);

321 }

322

324 A->getParent(), B->getParent(), ExclusionSet, DT, LI);

325}

326

329 return CB->hasFnAttr(Attribute::NoReturn);

330 return false;

331}

332

333

334

340

341

345

346 Visited.insert(&F.front());

348

349 do {

352 return true;

354 if (Visited.insert(Succ).second)

356 } while (!Worklist.empty());

357

358 return false;

359}

360

364 if (!Src.getParent()->isPresplitCoroutine())

365 return false;

368 return Intr->getIntrinsicID() == Intrinsic::coro_suspend &&

369 SW->getDefaultDest() == &Dest;

370 return false;

371}

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

static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")

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

static cl::opt< unsigned > DefaultMaxBBsToExplore("dom-tree-reachability-max-bbs-to-explore", cl::Hidden, cl::desc("Max number of BBs to explore for reachability analysis"), cl::init(32))

static bool isReachableImpl(SmallVectorImpl< BasicBlock * > &Worklist, const StopSetT &StopSet, const SmallPtrSetImpl< BasicBlock * > *ExclusionSet, const DominatorTree *DT, const LoopInfo *LI)

Definition CFG.cpp:135

static const Loop * getOutermostLoop(const LoopInfo *LI, const BasicBlock *BB)

Definition CFG.cpp:129

static bool instructionDoesNotReturn(const Instruction &I)

Definition CFG.cpp:327

static bool basicBlockCanReturn(const BasicBlock &BB)

Definition CFG.cpp:335

const_iterator end() const

Definition CFG.cpp:234

const_iterator begin() const

Definition CFG.cpp:233

const T * const_iterator

Definition CFG.cpp:227

bool contains(T Other) const

Definition CFG.cpp:231

SingleEntrySet(T Elem)

Definition CFG.cpp:229

LLVM Basic Block Representation.

const Function * getParent() const

Return the enclosing method, or null if none.

LLVM_ABI bool isEntryBlock() const

Return true if this is the entry block of the containing function.

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

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.

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.

LLVM_ABI unsigned getNumSuccessors() const LLVM_READONLY

Return the number of successors that this instruction has.

LLVM_ABI BasicBlock * getSuccessor(unsigned Idx) const LLVM_READONLY

Return the specified successor. This instruction must be a terminator.

bool isTerminator() const

LoopT * getLoopFor(const BlockT *BB) const

Return the inner most loop that BB lives in.

Represents a single loop in the control flow graph.

A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...

bool erase(PtrType Ptr)

Remove pointer from the set.

size_type count(ConstPtrType Ptr) const

count - Return 1 if the specified pointer is in the set, 0 otherwise.

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.

This class consists of common code factored out of the SmallVector class to reduce code duplication b...

void append(ItTy in_start, ItTy in_end)

Add the specified range to the end of the SmallVector.

void push_back(const T &Elt)

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

const ParentTy * getParent() const

initializer< Ty > init(const Ty &Val)

This is an optimization pass for GlobalISel generic memory operations.

bool succ_empty(const Instruction *I)

LLVM_ABI unsigned GetSuccessorNumber(const BasicBlock *BB, const BasicBlock *Succ)

Search for the specified successor of basic block BB and return its position in the terminator instru...

Definition CFG.cpp:80

auto pred_end(const MachineBasicBlock *BB)

LLVM_ABI bool isPotentiallyReachableFromMany(SmallVectorImpl< BasicBlock * > &Worklist, const BasicBlock *StopBB, const SmallPtrSetImpl< BasicBlock * > *ExclusionSet, const DominatorTree *DT=nullptr, const LoopInfo *LI=nullptr)

Determine whether there is at least one path from a block in 'Worklist' to 'StopBB' without passing t...

Definition CFG.cpp:240

decltype(auto) dyn_cast(const From &Val)

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

auto successors(const MachineBasicBlock *BB)

PredIterator< const BasicBlock, Value::const_user_iterator > const_pred_iterator

bool any_of(R &&range, UnaryPredicate P)

Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.

bool none_of(R &&Range, UnaryPredicate P)

Provide wrappers to std::none_of which take ranges instead of having to pass begin/end explicitly.

LLVM_ABI bool isManyPotentiallyReachableFromMany(SmallVectorImpl< BasicBlock * > &Worklist, const SmallPtrSetImpl< const BasicBlock * > &StopSet, const SmallPtrSetImpl< BasicBlock * > *ExclusionSet, const DominatorTree *DT=nullptr, const LoopInfo *LI=nullptr)

Determine whether there is a potentially a path from at least one block in 'Worklist' to at least one...

Definition CFG.cpp:249

bool isa(const From &Val)

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

RNSuccIterator< NodeRef, BlockT, RegionT > succ_begin(NodeRef Node)

RNSuccIterator< NodeRef, BlockT, RegionT > succ_end(NodeRef Node)

LLVM_ABI bool isCriticalEdge(const Instruction *TI, unsigned SuccNum, bool AllowIdenticalEdges=false)

Return true if the specified edge is a critical edge.

Definition CFG.cpp:96

auto pred_begin(const MachineBasicBlock *BB)

LLVM_ABI bool isPresplitCoroSuspendExitEdge(const BasicBlock &Src, const BasicBlock &Dest)

Definition CFG.cpp:361

auto predecessors(const MachineBasicBlock *BB)

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

Returns true if Element is found in Range.

SuccIterator< const Instruction, const BasicBlock > const_succ_iterator

LLVM_ABI void FindFunctionBackedges(const Function &F, SmallVectorImpl< std::pair< const BasicBlock *, const BasicBlock * > > &Result)

Analyze the specified function to find all of the loop backedges in the function and return them.

Definition CFG.cpp:35

LLVM_ABI bool canReturn(const Function &F)

Return true if there is at least a path through which F can return, false if there is no such path.

Definition CFG.cpp:342

LLVM_ABI bool isPotentiallyReachable(const Instruction *From, const Instruction *To, const SmallPtrSetImpl< BasicBlock * > *ExclusionSet=nullptr, const DominatorTree *DT=nullptr, const LoopInfo *LI=nullptr)

Determine whether instruction 'To' is reachable from 'From', without passing through any blocks in Ex...

Definition CFG.cpp:282