GenericIteratedDominanceFrontier.h Source File (original) (raw)

23#ifndef LLVM_SUPPORT_GENERICITERATEDDOMINANCEFRONTIER_H

24#define LLVM_SUPPORT_GENERICITERATEDDOMINANCEFRONTIER_H

30#include

32namespace llvm {

47}

59public:

61 std::conditional_t<IsPostDom, Inverse<NodeTy *>, NodeTy *>;

69 : DT(DT), ChildrenGetter(C) {}

77 DefBlocks = &Blocks;

78 }

86 LiveInBlocks = &Blocks;

87 useLiveIn = true;

88 }

93 LiveInBlocks = nullptr;

94 useLiveIn = false;

95 }

100

101

102

104

105private:

108 bool useLiveIn = false;

111};

112

113

114

115

116

118

119template <class NodeTy, bool IsPostDom>

122 using OrderedNodeTy =

124

126}

127

128}

129

130template <class NodeTy, bool IsPostDom>

133

134

135

136

137 using DomTreeNodePair =

138 std::pair<DomTreeNodeBase *, std::pair<unsigned, unsigned>>;

139 using IDFPriorityQueue =

140 std::priority_queue<DomTreeNodePair, SmallVector<DomTreeNodePair, 32>,

142

143 IDFPriorityQueue PQ;

144

145 DT.updateDFSNumbers();

146

150 if (useLiveIn) {

151 VisitedPQ.reserve(LiveInBlocks->size());

152 VisitedWorklist.reserve(LiveInBlocks->size());

153 }

154

155 for (NodeTy *BB : *DefBlocks)

157 PQ.push({Node, std::make_pair(Node->getLevel(), Node->getDFSNumIn())});

159 }

160

161 while (!PQ.empty()) {

162 DomTreeNodePair RootPair = PQ.top();

163 PQ.pop();

165 unsigned RootLevel = RootPair.second.first;

166

167

168

169

170

171

174

175 while (!Worklist.empty()) {

177 NodeTy *BB = Node->getBlock();

178

179

180 auto DoWork = [&](NodeTy *Succ) {

182

183 const unsigned SuccLevel = SuccNode->getLevel();

184 if (SuccLevel > RootLevel)

185 return;

186

187 if (!VisitedPQ.insert(SuccNode).second)

188 return;

189

190 NodeTy *SuccBB = SuccNode->getBlock();

191 if (useLiveIn && !LiveInBlocks->count(SuccBB))

192 return;

193

195 if (!DefBlocks->count(SuccBB))

196 PQ.push(std::make_pair(

197 SuccNode, std::make_pair(SuccLevel, SuccNode->getDFSNumIn())));

198 };

199

200 for (auto *Succ : ChildrenGetter.get(BB))

201 DoWork(Succ);

202

203 for (auto DomChild : *Node) {

204 if (VisitedWorklist.insert(DomChild).second)

206 }

207 }

208 }

209}

210

211}

212

213#endif

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

This file defines a set of templates that efficiently compute a dominator tree over a generic graph.

This file defines the SmallPtrSet class.

This file defines the SmallVector class.

Base class for the actual dominator tree node.

unsigned getDFSNumIn() const

getDFSNumIn/getDFSNumOut - These return the DFS visitation order for nodes in the dominator tree.

unsigned getLevel() const

Core dominator tree base class.

IDFCalculatorBase(DominatorTreeBase< NodeTy, IsPostDom > &DT)

Definition GenericIteratedDominanceFrontier.h:65

void resetLiveInBlocks()

Reset the live-in block set to be empty, and tell the IDF calculator to not use liveness anymore.

Definition GenericIteratedDominanceFrontier.h:92

void calculate(SmallVectorImpl< NodeTy * > &IDFBlocks)

Calculate iterated dominance frontiers.

Definition GenericIteratedDominanceFrontier.h:131

void setLiveInBlocks(const SmallPtrSetImpl< NodeTy * > &Blocks)

Give the IDF calculator the set of blocks in which the value is live on entry to the block.

Definition GenericIteratedDominanceFrontier.h:85

void setDefiningBlocks(const SmallPtrSetImpl< NodeTy * > &Blocks)

Give the IDF calculator the set of blocks in which the value is defined.

Definition GenericIteratedDominanceFrontier.h:76

IDFCalculatorBase(DominatorTreeBase< NodeTy, IsPostDom > &DT, const ChildrenGetterTy &C)

Definition GenericIteratedDominanceFrontier.h:67

std::conditional_t< IsPostDom, Inverse< NodeTy * >, NodeTy * > OrderedNodeTy

Definition GenericIteratedDominanceFrontier.h:60

IDFCalculatorDetail::ChildrenGetterTy< NodeTy, IsPostDom > ChildrenGetterTy

Definition GenericIteratedDominanceFrontier.h:62

void reserve(size_type NewNumEntries)

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

std::pair< iterator, bool > insert(PtrType Ptr)

Inserts Ptr if and only if there is no element in the container equal to Ptr.

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

reference emplace_back(ArgTypes &&... Args)

void push_back(const T &Elt)

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

A range adaptor for a pair of iterators.

This provides a very simple, boring adaptor for a begin and end iterator into a range type.

@ C

The default llvm calling convention, compatible with C.

This is an optimization pass for GlobalISel generic memory operations.

iterator_range< typename GraphTraits< GraphType >::ChildIteratorType > children(const typename GraphTraits< GraphType >::NodeRef &G)

typename GraphType::UnknownGraphTypeError NodeRef

Generic utility class used for getting the children of a basic block.

Definition GenericIteratedDominanceFrontier.h:39

iterator_range< ChildIteratorType > range

Definition GenericIteratedDominanceFrontier.h:42

typename GraphTraits< NodeTy * >::ChildIteratorType ChildIteratorType

Definition GenericIteratedDominanceFrontier.h:41

typename GraphTraits< NodeTy * >::NodeRef NodeRef

Definition GenericIteratedDominanceFrontier.h:40

range get(const NodeRef &N)

Definition GenericIteratedDominanceFrontier.h:121

Function object to check whether the second component of a container supported by std::get (like std:...