Dominators.h Source File (original) (raw)

13#ifndef LLVM_CLANG_ANALYSIS_ANALYSES_DOMINATORS_H

14#define LLVM_CLANG_ANALYSIS_ANALYSES_DOMINATORS_H

18#include "llvm/ADT/DepthFirstIterator.h"

19#include "llvm/ADT/GraphTraits.h"

20#include "llvm/ADT/iterator.h"

21#include "llvm/Support/GenericIteratedDominanceFrontier.h"

22#include "llvm/Support/GenericDomTree.h"

23#include "llvm/Support/GenericDomTreeConstruction.h"

24#include "llvm/Support/raw_ostream.h"

32class Module;

34}

38using DomTreeNode = llvm::DomTreeNodeBase;

41template

43 virtual void anchor();

45public:

62 return DT.getRoot();

63 }

67 return DT.getRootNode();

68 }

77 if (!R || !OtherR || R->getBlock() != OtherR->getBlock())

78 return true;

80 if (DT.compare(Other.getBase()))

81 return true;

83 return false;

84 }

88 assert(cfg);

89 this->cfg = cfg;

90 DT.recalculate(*cfg);

91 }

95 llvm::errs() << "Immediate " << (IsPostDom ? "post " : "")

96 << "dominance tree (Node#,IDom#):\n";

98 E = cfg->end(); I != E; ++I) {

100 assert(*I &&

101 "LLVM's Dominator tree builder uses nullpointers to signify the "

102 "virtual root!");

103

104 DomTreeNode *IDom = DT.getNode(*I)->getIDom();

105 if (IDom && IDom->getBlock())

106 llvm::errs() << "(" << (*I)->getBlockID()

107 << ","

108 << IDom->getBlock()->getBlockID()

109 << ")\n";

110 else {

111 bool IsEntryBlock = *I == &(*I)->getParent()->getEntry();

112 bool IsExitBlock = *I == &(*I)->getParent()->getExit();

113

114 bool IsDomTreeRoot = !IDom && !IsPostDom && IsEntryBlock;

115 bool IsPostDomTreeRoot =

116 IDom && !IDom->getBlock() && IsPostDom && IsExitBlock;

117

118 assert((IsDomTreeRoot || IsPostDomTreeRoot) &&

119 "If the immediate dominator node is nullptr, the CFG block "

120 "should be the exit point (since it's the root of the dominator "

121 "tree), or if the CFG block it refers to is a nullpointer, it "

122 "must be the entry block (since it's the root of the post "

123 "dominator tree)");

124

125 (void)IsDomTreeRoot;

126 (void)IsPostDomTreeRoot;

127

128 llvm::errs() << "(" << (*I)->getBlockID()

129 << "," << (*I)->getBlockID() << ")\n";

130 }

131 }

132 }

133

134

135

137 return DT.dominates(A, B);

138 }

139

140

141

142

144 return DT.properlyDominates(A, B);

145 }

146

147

148

150 return DT.findNearestCommonDominator(A, B);

151 }

152

155 return DT.findNearestCommonDominator(A, B);

156 }

157

158

159

161 DT.changeImmediateDominator(N, NewIDom);

162 }

163

164

166 return DT.isReachableFromEntry(A);

167 }

168

169

171

172

173 virtual void print(raw_ostream &OS, const llvm::Module* M= nullptr) const {

174 DT.print(OS);

175 }

176

177private:

178 CFG *cfg;

180};

181

184

185template<> void CFGDominatorTreeImpl::anchor();

186template<> void CFGDominatorTreeImpl::anchor();

187

188}

189

190namespace llvm {

192

193

194template

195struct ChildrenGetterTy<clang::CFGBlock, IsPostDom> {

196 using NodeRef = typename GraphTraits<clang::CFGBlock *>::NodeRef;

198

200 using OrderedNodeTy =

201 typename IDFCalculatorBase<clang::CFGBlock, IsPostDom>::OrderedNodeTy;

202

203 auto Children = children(N);

205 llvm::erase(Ret, nullptr);

206 return Ret;

207 }

208};

209

210}

211}

212

214

216 using IDFCalculator = llvm::IDFCalculatorBase<CFGBlock, true>;

219

221 IDFCalculator IDFCalc;

222

223 llvm::DenseMap<CFGBlock *, CFGBlockVector> ControlDepenencyMap;

224

225public:

227 : PostDomTree(cfg), IDFCalc(PostDomTree.getBase()) {}

228

230

231

233 auto It = ControlDepenencyMap.find(A);

234 if (It == ControlDepenencyMap.end()) {

235 CFGBlockSet DefiningBlock = {A};

236 IDFCalc.setDefiningBlocks(DefiningBlock);

237

238 CFGBlockVector ControlDependencies;

239 IDFCalc.calculate(ControlDependencies);

240

241 It = ControlDepenencyMap.insert({A, ControlDependencies}).first;

242 }

243

244 assert(It != ControlDepenencyMap.end());

245 return It->second;

246 }

247

248

252

253

254 LLVM_DUMP_METHOD void dump() {

255 CFG *cfg = PostDomTree.getCFG();

256 llvm::errs() << "Control dependencies (Node#,Dependency#):\n";

258

259 assert(BB &&

260 "LLVM's Dominator tree builder uses nullpointers to signify the "

261 "virtual root!");

262

264 llvm::errs() << "(" << BB->getBlockID()

265 << ","

266 << isControlDependency->getBlockID()

267 << ")\n";

268 }

269 }

270};

271

272}

273

274namespace llvm {

275

276

277

278

279

280template <> struct GraphTraits<clang::DomTreeNode *> {

283

287

289 llvm::pointer_iterator<df_iterator<::clang::DomTreeNode *>>;

290

294

298};

299

300template <> struct GraphTraits<clang::CFGDomTree *>

301 : public GraphTraits<clang::DomTreeNode *> {

305

309

313};

314

315}

316

317#endif

This file defines AnalysisDeclContext, a class that manages the analysis context data for context sen...

SmallVector< AnnotatedLine *, 1 > Children

If this token starts a block, this contains all the unwrapped lines in it.

Represents a single basic block in a source-level CFG.

Dominator tree builder for Clang's CFG based on llvm::DominatorTreeBase.

Definition Dominators.h:42

virtual void releaseMemory()

Releases the memory held by the dominator tree.

Definition Dominators.h:170

CFGDominatorTreeImpl(CFG *cfg)

Definition Dominators.h:50

virtual void print(raw_ostream &OS, const llvm::Module *M=nullptr) const

Converts the dominator tree to human readable form.

Definition Dominators.h:173

CFGBlock * findNearestCommonDominator(CFGBlock *A, CFGBlock *B)

Definition Dominators.h:149

bool compare(CFGDominatorTreeImpl &Other) const

Compares two dominator trees.

Definition Dominators.h:73

CFGBlock * getRoot() const

Definition Dominators.h:61

CFG * getCFG()

Definition Dominators.h:58

void dump()

Dumps immediate dominators for each block.

Definition Dominators.h:94

void buildDominatorTree(CFG *cfg)

Builds the dominator tree for a given CFG.

Definition Dominators.h:87

~CFGDominatorTreeImpl() override=default

llvm::DominatorTreeBase< CFGBlock, IsPostDom > DominatorTreeBase

Definition Dominators.h:46

const CFGBlock * findNearestCommonDominator(const CFGBlock *A, const CFGBlock *B)

Definition Dominators.h:153

bool properlyDominates(const CFGBlock *A, const CFGBlock *B) const

Tests whether A properly dominates B.

Definition Dominators.h:143

DomTreeNode * getRootNode()

Definition Dominators.h:66

void changeImmediateDominator(CFGBlock *N, CFGBlock *NewIDom)

Update the dominator tree information when a node's immediate dominator changes.

Definition Dominators.h:160

DominatorTreeBase & getBase()

Definition Dominators.h:56

CFGDominatorTreeImpl()=default

bool dominates(const CFGBlock *A, const CFGBlock *B) const

Tests whether A dominates B.

Definition Dominators.h:136

bool isReachableFromEntry(const CFGBlock *A)

Tests whether A is reachable from the entry block.

Definition Dominators.h:165

Represents a source-level, intra-procedural CFG that represents the control-flow of a Stmt.

CFGBlockListTy::const_iterator const_iterator

ControlDependencyCalculator(CFG *cfg)

Definition Dominators.h:226

LLVM_DUMP_METHOD void dump()

Definition Dominators.h:254

const CFGBlockVector & getControlDependencies(CFGBlock *A)

Definition Dominators.h:232

const CFGPostDomTree & getCFGPostDomTree() const

Definition Dominators.h:229

bool isControlDependent(CFGBlock *A, CFGBlock *B)

Whether A is control dependent on B.

Definition Dominators.h:249

ManagedAnalysis()=default

The JSON file list parser is used to communicate input to InstallAPI.

CFGDominatorTreeImpl< true > CFGPostDomTree

Definition Dominators.h:183

CFGDominatorTreeImpl< false > CFGDomTree

Definition Dominators.h:182

llvm::DomTreeNodeBase< CFGBlock > DomTreeNode

Definition Dominators.h:38

@ Other

Other implicit parameter.

Definition Dominators.h:191

Diagnostic wrappers for TextAPI types for error reporting.

Definition Dominators.h:30

static nodes_iterator nodes_end(clang::CFGDomTree *N)

Definition Dominators.h:310

static nodes_iterator nodes_begin(clang::CFGDomTree *N)

Definition Dominators.h:306

static NodeRef getEntryNode(clang::CFGDomTree *DT)

Definition Dominators.h:302

static NodeRef getEntryNode(NodeRef N)

Definition Dominators.h:284

::clang::DomTreeNode::const_iterator ChildIteratorType

Definition Dominators.h:282

::clang::DomTreeNode * NodeRef

Definition Dominators.h:281

static ChildIteratorType child_end(NodeRef N)

Definition Dominators.h:286

static nodes_iterator nodes_begin(::clang::DomTreeNode *N)

Definition Dominators.h:291

static ChildIteratorType child_begin(NodeRef N)

Definition Dominators.h:285

llvm::pointer_iterator< df_iterator<::clang::DomTreeNode * > > nodes_iterator

Definition Dominators.h:288

static nodes_iterator nodes_end(::clang::DomTreeNode *N)

Definition Dominators.h:295

ChildrenTy get(const NodeRef &N)

Definition Dominators.h:199

typename GraphTraits< clang::CFGBlock * >::NodeRef NodeRef

Definition Dominators.h:196

SmallVector< NodeRef, 8 > ChildrenTy

Definition Dominators.h:197