Dominance.cpp Source File (original) (raw)

17 #include "llvm/ADT/DenseMap.h"

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

20 using namespace mlir;

23 template class llvm::DominatorTreeBase<Block, false>;

24 template class llvm::DominatorTreeBase<Block, true>;

25 template class llvm::DomTreeNodeBase;

31 template

33 for (auto entry : dominanceInfos)

34 delete entry.second.getPointer();

35 }

37 template

39 for (auto entry : dominanceInfos)

40 delete entry.second.getPointer();

41 dominanceInfos.clear();

44 template

46 auto it = dominanceInfos.find(region);

47 if (it != dominanceInfos.end()) {

48 delete it->second.getPointer();

49 dominanceInfos.erase(it);

51 }

56 template

58 bool needsDomTree) const

59 -> llvm::PointerIntPair<DomTree *, 1, bool> {

61 auto itAndInserted = dominanceInfos.insert({region, {nullptr, true}});

62 auto &entry = itAndInserted.first->second;

67 if (!itAndInserted.second) {

70 if (needsDomTree && !entry.getPointer() && !region->hasOneBlock()) {

71 auto *domTree = new DomTree();

72 domTree->recalculate(*region);

73 entry.setPointer(domTree);

74 }

75 return entry;

76 }

81 auto *domTree = new DomTree();

82 domTree->recalculate(*region);

83 entry.setPointer(domTree);

85 return entry;

86 }

90 if (!parentOp->isRegistered()) {

91 entry.setInt(false);

92 } else if (auto regionKindItf = dyn_cast(parentOp)) {

95 entry.setInt(regionKindItf.hasSSADominance(region->getRegionNumber()));

96 }

97 }

99 return entry;

100 }

101

102

103

106 return ancestorOp->getBlock();

107 return nullptr;

108 }

109

110

111

112

113

114

115 template

117 do {

118

119 if (func(block))

120 return block;

122 return nullptr;

123 }

124

125

126

128

129

132 if (aRegion == bRegion)

133 return true;

134

135

136

137

138 size_t aRegionDepth = 0;

140 ++aRegionDepth;

141 return block->getParent() == bRegion;

142 })) {

143 a = aResult;

144 return true;

145 }

146

147

148

149

150 size_t bRegionDepth = 0;

152 ++bRegionDepth;

153 return block->getParent() == aRegion;

154 })) {

155 b = bResult;

156 return true;

157 }

158

159

160

161 while (true) {

162 if (aRegionDepth > bRegionDepth) {

164 --aRegionDepth;

165 } else if (aRegionDepth < bRegionDepth) {

167 --bRegionDepth;

168 } else {

169 break;

170 }

171 }

172

173

174

175 while (a) {

176

177

179 return true;

180

183 }

184

185

186

187 return false;

188 }

189

190 template

193 Block *b) const {

194

195 if (!a || !b)

196 return nullptr;

197

198

199 if (a == b)

200 return a;

201

202

204 return nullptr;

205

206

207

208 if (a == b)

209 return a;

210

211

212

213 return getDomTree(a->getParent()).findNearestCommonDominator(a, b);

214 }

215

216

217

218

219

220

221

222

223 static std::pair<Block *, Block::iterator>

225

227 return std::make_pair(b, it);

228

229

231 if (!parentOp)

233 Operation *op = r->findAncestorOpInRegion(*parentOp);

234 if (!op)

236 return std::make_pair(op->getBlock(), op->getIterator());

237 }

238

239

240

241

244 if (a == b)

245 return false;

246 if (a == block->end())

247 return false;

248 if (b == block->end())

249 return true;

250 return a->isBeforeInBlock(&*b);

251 }

252

253 template

256 bool enclosingOk) const {

257 assert(aBlock && bBlock && "expected non-null blocks");

258

259

260

261 if (aBlock == bBlock && aIt == bIt)

262 return !hasSSADominance(aBlock);

263

264

265

267 if (aRegion != bBlock->getParent()) {

268

269

270 if (!aRegion) {

271 bBlock = nullptr;

273 } else {

274 std::tie(bBlock, bIt) =

276 }

277 if (!bBlock)

278 return false;

279 assert(bBlock->getParent() == aRegion && "expected block in regionA");

280

281

282 if (aBlock == bBlock && aIt == bIt && enclosingOk)

283 return true;

284 }

285

286

287 if (aBlock == bBlock) {

288

289

290

291 if (!hasSSADominance(aBlock))

292 return true;

293 if constexpr (IsPostDom) {

295 } else {

297 }

298 }

299

300

301 return getDomTree(aRegion).properlyDominates(aBlock, bBlock);

302 }

303

304

305

306 template

308

310 if (&region->front() == a)

311 return true;

312

313

314 return getDomTree(region).isReachableFromEntry(a);

315 }

316

319

320

321

322

323

325 bool enclosingOpOk) const {

326 return super::properlyDominatesImpl(a->getBlock(), a->getIterator(),

327 b->getBlock(), b->getIterator(),

328 enclosingOpOk);

329 }

330

332 return super::properlyDominatesImpl(a, a->begin(), b, b->begin(),

333 true);

334 }

335

336

337

338

340

341

342 if (auto blockArg = dyn_cast(a))

343 return dominates(blockArg.getOwner(), b->getBlock());

344

345

346

347 return properlyDominates(a.getDefiningOp(), b, false);

348 }

349

350

351

352

353

355 bool enclosingOpOk) const {

356 return super::properlyDominatesImpl(a->getBlock(), a->getIterator(),

357 b->getBlock(), b->getIterator(),

358 enclosingOpOk);

359 }

360

362 return super::properlyDominatesImpl(a, a->end(), b, b->end(),

363 true);

364 }

static Block * traverseAncestors(Block *block, const FuncT &func)

Walks up the list of containers of the given block and calls the user-defined traversal function for ...

static bool isBeforeInBlock(Block *block, Block::iterator a, Block::iterator b)

Given two iterators into the same block, return "true" if a is before `b.

static std::pair< Block *, Block::iterator > findAncestorIteratorInRegion(Region *r, Block *b, Block::iterator it)

Returns the given block iterator if it lies within the region region.

static bool tryGetBlocksInSameRegion(Block *&a, Block *&b)

Tries to update the given block references to live in the same region by exploring the relationship o...

static Block * getAncestorBlock(Block *block)

Return the ancestor block enclosing the specified block.

Block represents an ordered list of Operations.

OpListType::iterator iterator

Region * getParent() const

Provide a 'getParent' method for ilist_node_with_parent methods.

Operation * getParentOp()

Returns the closest surrounding operation that contains this block.

bool properlyDominates(Operation *a, Operation *b, bool enclosingOpOk=true) const

Return true if operation A properly dominates operation B, i.e.

Operation is the basic unit of execution within MLIR.

Block * getBlock()

Returns the operation block that contains this operation.

bool properlyPostDominates(Operation *a, Operation *b, bool enclosingOpOk=true) const

Return true if operation A properly postdominates operation B.

This class contains a list of basic blocks and a link to the parent operation it is attached to.

unsigned getRegionNumber()

Return the number of this region in the parent operation.

Operation * getParentOp()

Return the parent operation this region is attached to.

bool hasOneBlock()

Return true if this region has exactly one block.

This class represents an instance of an SSA value in the MLIR system, representing a computable value...

Operation * getDefiningOp() const

If this value is the result of an operation, return the operation that defines it.

llvm::PointerIntPair< DomTree *, 1, bool > getDominanceInfo(Region *region, bool needsDomTree) const

Return the dom tree and "hasSSADominance" bit for the given region.

bool isReachableFromEntry(Block *a) const

Return true if the specified block is reachable from the entry block of its region.

bool properlyDominatesImpl(Block *aBlock, Block::iterator aIt, Block *bBlock, Block::iterator bIt, bool enclosingOk=true) const

Return "true" if block iterator A properly (post)dominates block iterator B.

Block * findNearestCommonDominator(Block *a, Block *b) const

Finds the nearest common dominator block for the two given blocks a and b.

void invalidate()

Invalidate dominance info.

Include the generated interface declarations.