CFG.cpp Source File (original) (raw)

19using namespace llvm;

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

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

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

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

38 return;

47 do {

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

49 const BasicBlock *ParentBB = Top.first;

52 bool FoundNew = false;

54 BB = *I++;

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

56 FoundNew = true;

57 break;

58 }

60 if (InStack.count(BB))

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

62 }

64 if (FoundNew) {

68 } else {

71 }

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

73}

82#ifndef NDEBUG

83 unsigned e = Term->getNumSuccessors();

84#endif

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

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

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

88 return i;

89 }

90}

96 bool AllowIdenticalEdges) {

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

99}

100

102 bool AllowIdenticalEdges) {

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

105

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

108

110

111

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

114 ++I;

115 if (!AllowIdenticalEdges)

116 return I != E;

117

118

119

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

121 if (*I != FirstPred)

122 return true;

123 return false;

124}

125

126

127

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

131}

132

133template

135 const StopSetT &StopSet,

138

139

140 if (DT) {

141 for (auto *BB : StopSet) {

143 DT = nullptr;

144 break;

145 }

146 }

147 }

148

149

150

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

152 DT = nullptr;

153

154

155

156

158 if (LI && ExclusionSet) {

159 for (auto *BB : *ExclusionSet) {

161 LoopsWithHoles.insert(L);

162 }

163 }

164

166 if (LI) {

167 for (auto *StopSetBB : StopSet) {

170 }

171 }

172

175 do {

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

178 continue;

179 if (StopSet.contains(BB))

180 return true;

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

182 continue;

183 if (DT) {

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

186 }))

187 return true;

188 }

189

190 const Loop *Outer = nullptr;

191 if (LI) {

193

194

195

196

197 if (LoopsWithHoles.count(Outer))

198 Outer = nullptr;

199 if (StopLoops.contains(Outer))

200 return true;

201 }

202

203 if (!--Limit) {

204

205

206 return true;

207 }

208

209 if (Outer) {

210

211

212

213 Outer->getExitBlocks(Worklist);

214 } else {

216 }

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

218

219

220

221 return false;

222}

223

225public:

227

229

231

234

235private:

236 T Elem;

237};

238

243 return isReachableImpl<SingleEntrySet<const BasicBlock *>>(

245 LI);

246}

247

253 return isReachableImpl<SmallPtrSetImpl<const BasicBlock *>>(

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

255}

256

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

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

263

264 if (DT) {

266 return false;

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

269 return true;

271 return false;

272 }

273 }

274

277

279}

280

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

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

287

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

289

290

291

292

293

295

296

297

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

299 return true;

300

301

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

303 return true;

304

305

306

308 return false;

309

310

313 if (Worklist.empty()) {

314

315 return false;

316 }

317

319 ExclusionSet, DT, LI);

320 }

321

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

324}

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

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

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)

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

std::optional< std::vector< StOtherPiece > > Other

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

const_iterator end() const

const_iterator begin() const

bool contains(T Other) const

LLVM Basic Block Representation.

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.

bool isReachableFromEntry(const Use &U) const

Provide an overload for a Use.

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

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

unsigned getNumSuccessors() const LLVM_READONLY

Return the number of successors that this instruction has.

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)

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

auto pred_end(const MachineBasicBlock *BB)

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

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

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

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

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

Return true if the specified edge is a critical edge.

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.

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.

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