1 | //===- RegionInfoImpl.h - SESE region detection analysis --------*- C++ -*-===// |
2 | // |
3 | // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
4 | // See https://llvm.org/LICENSE.txt for license information. |
5 | // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
6 | // |
7 | //===----------------------------------------------------------------------===// |
8 | // Detects single entry single exit regions in the control flow graph. |
9 | //===----------------------------------------------------------------------===// |
10 | |
11 | #ifndef LLVM_ANALYSIS_REGIONINFOIMPL_H |
12 | #define LLVM_ANALYSIS_REGIONINFOIMPL_H |
13 | |
14 | #include "llvm/ADT/GraphTraits.h" |
15 | #include "llvm/ADT/PostOrderIterator.h" |
16 | #include "llvm/ADT/STLExtras.h" |
17 | #include "llvm/ADT/SmallVector.h" |
18 | #include "llvm/Analysis/LoopInfo.h" |
19 | #include "llvm/Analysis/PostDominators.h" |
20 | #include "llvm/Analysis/RegionInfo.h" |
21 | #include "llvm/Analysis/RegionIterator.h" |
22 | #include "llvm/Config/llvm-config.h" |
23 | #include "llvm/Support/Debug.h" |
24 | #include "llvm/Support/ErrorHandling.h" |
25 | #include <algorithm> |
26 | #include <cassert> |
27 | #include <iterator> |
28 | #include <memory> |
29 | #include <set> |
30 | #include <string> |
31 | #include <type_traits> |
32 | #include <vector> |
33 | |
34 | #define DEBUG_TYPE "region" |
35 | |
36 | namespace llvm { |
37 | class raw_ostream; |
38 | |
39 | //===----------------------------------------------------------------------===// |
40 | /// RegionBase Implementation |
41 | template <class Tr> |
42 | RegionBase<Tr>::RegionBase(BlockT *Entry, BlockT *Exit, |
43 | typename Tr::RegionInfoT *RInfo, DomTreeT *dt, |
44 | RegionT *Parent) |
45 | : RegionNodeBase<Tr>(Parent, Entry, 1), RI(RInfo), DT(dt), exit(Exit) {} |
46 | |
47 | template <class Tr> |
48 | RegionBase<Tr>::~RegionBase() { |
49 | // Only clean the cache for this Region. Caches of child Regions will be |
50 | // cleaned when the child Regions are deleted. |
51 | BBNodeMap.clear(); |
52 | } |
53 | |
54 | template <class Tr> |
55 | void RegionBase<Tr>::replaceEntry(BlockT *BB) { |
56 | this->entry.setPointer(BB); |
57 | } |
58 | |
59 | template <class Tr> |
60 | void RegionBase<Tr>::replaceExit(BlockT *BB) { |
61 | assert(exit && "No exit to replace!" ); |
62 | exit = BB; |
63 | } |
64 | |
65 | template <class Tr> |
66 | void RegionBase<Tr>::replaceEntryRecursive(BlockT *NewEntry) { |
67 | std::vector<RegionT *> RegionQueue; |
68 | BlockT *OldEntry = getEntry(); |
69 | |
70 | RegionQueue.push_back(static_cast<RegionT *>(this)); |
71 | while (!RegionQueue.empty()) { |
72 | RegionT *R = RegionQueue.back(); |
73 | RegionQueue.pop_back(); |
74 | |
75 | R->replaceEntry(NewEntry); |
76 | for (std::unique_ptr<RegionT> &Child : *R) { |
77 | if (Child->getEntry() == OldEntry) |
78 | RegionQueue.push_back(Child.get()); |
79 | } |
80 | } |
81 | } |
82 | |
83 | template <class Tr> |
84 | void RegionBase<Tr>::replaceExitRecursive(BlockT *NewExit) { |
85 | std::vector<RegionT *> RegionQueue; |
86 | BlockT *OldExit = getExit(); |
87 | |
88 | RegionQueue.push_back(static_cast<RegionT *>(this)); |
89 | while (!RegionQueue.empty()) { |
90 | RegionT *R = RegionQueue.back(); |
91 | RegionQueue.pop_back(); |
92 | |
93 | R->replaceExit(NewExit); |
94 | for (std::unique_ptr<RegionT> &Child : *R) { |
95 | if (Child->getExit() == OldExit) |
96 | RegionQueue.push_back(Child.get()); |
97 | } |
98 | } |
99 | } |
100 | |
101 | template <class Tr> |
102 | bool RegionBase<Tr>::contains(const BlockT *B) const { |
103 | BlockT *BB = const_cast<BlockT *>(B); |
104 | |
105 | if (!DT->getNode(BB)) |
106 | return false; |
107 | |
108 | BlockT *entry = getEntry(), *exit = getExit(); |
109 | |
110 | // Toplevel region. |
111 | if (!exit) |
112 | return true; |
113 | |
114 | return (DT->dominates(entry, BB) && |
115 | !(DT->dominates(exit, BB) && DT->dominates(entry, exit))); |
116 | } |
117 | |
118 | template <class Tr> |
119 | bool RegionBase<Tr>::contains(const LoopT *L) const { |
120 | // BBs that are not part of any loop are element of the Loop |
121 | // described by the NULL pointer. This loop is not part of any region, |
122 | // except if the region describes the whole function. |
123 | if (!L) |
124 | return getExit() == nullptr; |
125 | |
126 | if (!contains(L->getHeader())) |
127 | return false; |
128 | |
129 | SmallVector<BlockT *, 8> ExitingBlocks; |
130 | L->getExitingBlocks(ExitingBlocks); |
131 | |
132 | for (BlockT *BB : ExitingBlocks) { |
133 | if (!contains(BB)) |
134 | return false; |
135 | } |
136 | |
137 | return true; |
138 | } |
139 | |
140 | template <class Tr> |
141 | typename Tr::LoopT *RegionBase<Tr>::outermostLoopInRegion(LoopT *L) const { |
142 | if (!contains(L)) |
143 | return nullptr; |
144 | |
145 | while (L && contains(L->getParentLoop())) { |
146 | L = L->getParentLoop(); |
147 | } |
148 | |
149 | return L; |
150 | } |
151 | |
152 | template <class Tr> |
153 | typename Tr::LoopT *RegionBase<Tr>::outermostLoopInRegion(LoopInfoT *LI, |
154 | BlockT *BB) const { |
155 | assert(LI && BB && "LI and BB cannot be null!" ); |
156 | LoopT *L = LI->getLoopFor(BB); |
157 | return outermostLoopInRegion(L); |
158 | } |
159 | |
160 | template <class Tr> |
161 | typename RegionBase<Tr>::BlockT *RegionBase<Tr>::getEnteringBlock() const { |
162 | auto isEnteringBlock = [&](BlockT *Pred, bool AllowRepeats) -> BlockT * { |
163 | assert(!AllowRepeats && "Unexpected parameter value." ); |
164 | return DT->getNode(Pred) && !contains(Pred) ? Pred : nullptr; |
165 | }; |
166 | return find_singleton<BlockT>(llvm::inverse_children<BlockT *>(getEntry()), |
167 | isEnteringBlock); |
168 | } |
169 | |
170 | template <class Tr> |
171 | bool RegionBase<Tr>::getExitingBlocks( |
172 | SmallVectorImpl<BlockT *> &Exitings) const { |
173 | bool CoverAll = true; |
174 | |
175 | if (!exit) |
176 | return CoverAll; |
177 | |
178 | for (BlockT *Pred : llvm::inverse_children<BlockT *>(exit)) { |
179 | if (contains(Pred)) { |
180 | Exitings.push_back(Pred); |
181 | continue; |
182 | } |
183 | |
184 | CoverAll = false; |
185 | } |
186 | |
187 | return CoverAll; |
188 | } |
189 | |
190 | template <class Tr> |
191 | typename RegionBase<Tr>::BlockT *RegionBase<Tr>::getExitingBlock() const { |
192 | BlockT *exit = getExit(); |
193 | if (!exit) |
194 | return nullptr; |
195 | |
196 | auto isContained = [&](BlockT *Pred, bool AllowRepeats) -> BlockT * { |
197 | assert(!AllowRepeats && "Unexpected parameter value." ); |
198 | return contains(Pred) ? Pred : nullptr; |
199 | }; |
200 | return find_singleton<BlockT>(llvm::inverse_children<BlockT *>(exit), |
201 | isContained); |
202 | } |
203 | |
204 | template <class Tr> |
205 | bool RegionBase<Tr>::isSimple() const { |
206 | return !isTopLevelRegion() && getEnteringBlock() && getExitingBlock(); |
207 | } |
208 | |
209 | template <class Tr> |
210 | std::string RegionBase<Tr>::getNameStr() const { |
211 | std::string exitName; |
212 | std::string entryName; |
213 | |
214 | if (getEntry()->getName().empty()) { |
215 | raw_string_ostream OS(entryName); |
216 | |
217 | getEntry()->printAsOperand(OS, false); |
218 | } else |
219 | entryName = std::string(getEntry()->getName()); |
220 | |
221 | if (getExit()) { |
222 | if (getExit()->getName().empty()) { |
223 | raw_string_ostream OS(exitName); |
224 | |
225 | getExit()->printAsOperand(OS, false); |
226 | } else |
227 | exitName = std::string(getExit()->getName()); |
228 | } else |
229 | exitName = "<Function Return>" ; |
230 | |
231 | return entryName + " => " + exitName; |
232 | } |
233 | |
234 | template <class Tr> |
235 | void RegionBase<Tr>::verifyBBInRegion(BlockT *BB) const { |
236 | if (!contains(BB)) |
237 | report_fatal_error(reason: "Broken region found: enumerated BB not in region!" ); |
238 | |
239 | BlockT *entry = getEntry(), *exit = getExit(); |
240 | |
241 | for (BlockT *Succ : llvm::children<BlockT *>(BB)) { |
242 | if (!contains(Succ) && exit != Succ) |
243 | report_fatal_error(reason: "Broken region found: edges leaving the region must go " |
244 | "to the exit node!" ); |
245 | } |
246 | |
247 | if (entry != BB) { |
248 | for (BlockT *Pred : llvm::inverse_children<BlockT *>(BB)) { |
249 | // Allow predecessors that are unreachable, as these are ignored during |
250 | // region analysis. |
251 | if (!contains(Pred) && DT->isReachableFromEntry(Pred)) |
252 | report_fatal_error(reason: "Broken region found: edges entering the region must " |
253 | "go to the entry node!" ); |
254 | } |
255 | } |
256 | } |
257 | |
258 | template <class Tr> |
259 | void RegionBase<Tr>::verifyWalk(BlockT *BB, std::set<BlockT *> *visited) const { |
260 | BlockT *exit = getExit(); |
261 | |
262 | visited->insert(BB); |
263 | |
264 | verifyBBInRegion(BB); |
265 | |
266 | for (BlockT *Succ : llvm::children<BlockT *>(BB)) { |
267 | if (Succ != exit && visited->find(Succ) == visited->end()) |
268 | verifyWalk(BB: Succ, visited); |
269 | } |
270 | } |
271 | |
272 | template <class Tr> |
273 | void RegionBase<Tr>::verifyRegion() const { |
274 | // Only do verification when user wants to, otherwise this expensive check |
275 | // will be invoked by PMDataManager::verifyPreservedAnalysis when |
276 | // a regionpass (marked PreservedAll) finish. |
277 | if (!RegionInfoBase<Tr>::VerifyRegionInfo) |
278 | return; |
279 | |
280 | std::set<BlockT *> visited; |
281 | verifyWalk(BB: getEntry(), visited: &visited); |
282 | } |
283 | |
284 | template <class Tr> |
285 | void RegionBase<Tr>::verifyRegionNest() const { |
286 | for (const std::unique_ptr<RegionT> &R : *this) |
287 | R->verifyRegionNest(); |
288 | |
289 | verifyRegion(); |
290 | } |
291 | |
292 | template <class Tr> |
293 | typename RegionBase<Tr>::element_iterator RegionBase<Tr>::element_begin() { |
294 | return GraphTraits<RegionT *>::nodes_begin(static_cast<RegionT *>(this)); |
295 | } |
296 | |
297 | template <class Tr> |
298 | typename RegionBase<Tr>::element_iterator RegionBase<Tr>::element_end() { |
299 | return GraphTraits<RegionT *>::nodes_end(static_cast<RegionT *>(this)); |
300 | } |
301 | |
302 | template <class Tr> |
303 | typename RegionBase<Tr>::const_element_iterator |
304 | RegionBase<Tr>::element_begin() const { |
305 | return GraphTraits<const RegionT *>::nodes_begin( |
306 | static_cast<const RegionT *>(this)); |
307 | } |
308 | |
309 | template <class Tr> |
310 | typename RegionBase<Tr>::const_element_iterator |
311 | RegionBase<Tr>::element_end() const { |
312 | return GraphTraits<const RegionT *>::nodes_end( |
313 | static_cast<const RegionT *>(this)); |
314 | } |
315 | |
316 | template <class Tr> |
317 | typename Tr::RegionT *RegionBase<Tr>::getSubRegionNode(BlockT *BB) const { |
318 | using RegionT = typename Tr::RegionT; |
319 | |
320 | RegionT *R = RI->getRegionFor(BB); |
321 | |
322 | if (!R || R == this) |
323 | return nullptr; |
324 | |
325 | // If we pass the BB out of this region, that means our code is broken. |
326 | assert(contains(R) && "BB not in current region!" ); |
327 | |
328 | while (contains(R->getParent()) && R->getParent() != this) |
329 | R = R->getParent(); |
330 | |
331 | if (R->getEntry() != BB) |
332 | return nullptr; |
333 | |
334 | return R; |
335 | } |
336 | |
337 | template <class Tr> |
338 | typename Tr::RegionNodeT *RegionBase<Tr>::getBBNode(BlockT *BB) const { |
339 | assert(contains(BB) && "Can get BB node out of this region!" ); |
340 | |
341 | typename BBNodeMapT::const_iterator at = BBNodeMap.find(BB); |
342 | |
343 | if (at == BBNodeMap.end()) { |
344 | auto Deconst = const_cast<RegionBase<Tr> *>(this); |
345 | typename BBNodeMapT::value_type V = { |
346 | BB, |
347 | std::make_unique<RegionNodeT>(static_cast<RegionT *>(Deconst), BB)}; |
348 | at = BBNodeMap.insert(std::move(V)).first; |
349 | } |
350 | return at->second.get(); |
351 | } |
352 | |
353 | template <class Tr> |
354 | typename Tr::RegionNodeT *RegionBase<Tr>::getNode(BlockT *BB) const { |
355 | assert(contains(BB) && "Can get BB node out of this region!" ); |
356 | if (RegionT *Child = getSubRegionNode(BB)) |
357 | return Child->getNode(); |
358 | |
359 | return getBBNode(BB); |
360 | } |
361 | |
362 | template <class Tr> |
363 | void RegionBase<Tr>::transferChildrenTo(RegionT *To) { |
364 | for (std::unique_ptr<RegionT> &R : *this) { |
365 | R->parent = To; |
366 | To->children.push_back(std::move(R)); |
367 | } |
368 | children.clear(); |
369 | } |
370 | |
371 | template <class Tr> |
372 | void RegionBase<Tr>::addSubRegion(RegionT *SubRegion, bool moveChildren) { |
373 | assert(!SubRegion->parent && "SubRegion already has a parent!" ); |
374 | assert(llvm::none_of(*this, |
375 | [&](const std::unique_ptr<RegionT> &R) { |
376 | return R.get() == SubRegion; |
377 | }) && |
378 | "Subregion already exists!" ); |
379 | |
380 | SubRegion->parent = static_cast<RegionT *>(this); |
381 | children.push_back(std::unique_ptr<RegionT>(SubRegion)); |
382 | |
383 | if (!moveChildren) |
384 | return; |
385 | |
386 | assert(SubRegion->children.empty() && |
387 | "SubRegions that contain children are not supported" ); |
388 | |
389 | for (RegionNodeT *Element : elements()) { |
390 | if (!Element->isSubRegion()) { |
391 | BlockT *BB = Element->template getNodeAs<BlockT>(); |
392 | |
393 | if (SubRegion->contains(BB)) |
394 | RI->setRegionFor(BB, SubRegion); |
395 | } |
396 | } |
397 | |
398 | std::vector<std::unique_ptr<RegionT>> Keep; |
399 | for (std::unique_ptr<RegionT> &R : *this) { |
400 | if (SubRegion->contains(R.get()) && R.get() != SubRegion) { |
401 | R->parent = SubRegion; |
402 | SubRegion->children.push_back(std::move(R)); |
403 | } else |
404 | Keep.push_back(std::move(R)); |
405 | } |
406 | |
407 | children.clear(); |
408 | children.insert( |
409 | children.begin(), |
410 | std::move_iterator<typename RegionSet::iterator>(Keep.begin()), |
411 | std::move_iterator<typename RegionSet::iterator>(Keep.end())); |
412 | } |
413 | |
414 | template <class Tr> |
415 | typename Tr::RegionT *RegionBase<Tr>::removeSubRegion(RegionT *Child) { |
416 | assert(Child->parent == this && "Child is not a child of this region!" ); |
417 | Child->parent = nullptr; |
418 | typename RegionSet::iterator I = |
419 | llvm::find_if(children, [&](const std::unique_ptr<RegionT> &R) { |
420 | return R.get() == Child; |
421 | }); |
422 | assert(I != children.end() && "Region does not exit. Unable to remove." ); |
423 | children.erase(children.begin() + (I - begin())); |
424 | return Child; |
425 | } |
426 | |
427 | template <class Tr> |
428 | unsigned RegionBase<Tr>::getDepth() const { |
429 | unsigned Depth = 0; |
430 | |
431 | for (RegionT *R = getParent(); R != nullptr; R = R->getParent()) |
432 | ++Depth; |
433 | |
434 | return Depth; |
435 | } |
436 | |
437 | template <class Tr> |
438 | typename Tr::RegionT *RegionBase<Tr>::getExpandedRegion() const { |
439 | unsigned NumSuccessors = Tr::getNumSuccessors(exit); |
440 | |
441 | if (NumSuccessors == 0) |
442 | return nullptr; |
443 | |
444 | RegionT *R = RI->getRegionFor(exit); |
445 | |
446 | if (R->getEntry() != exit) { |
447 | for (BlockT *Pred : llvm::inverse_children<BlockT *>(getExit())) |
448 | if (!contains(Pred)) |
449 | return nullptr; |
450 | if (Tr::getNumSuccessors(exit) == 1) |
451 | return new RegionT(getEntry(), *BlockTraits::child_begin(exit), RI, DT); |
452 | return nullptr; |
453 | } |
454 | |
455 | while (R->getParent() && R->getParent()->getEntry() == exit) |
456 | R = R->getParent(); |
457 | |
458 | for (BlockT *Pred : llvm::inverse_children<BlockT *>(getExit())) { |
459 | if (!(contains(Pred) || R->contains(Pred))) |
460 | return nullptr; |
461 | } |
462 | |
463 | return new RegionT(getEntry(), R->getExit(), RI, DT); |
464 | } |
465 | |
466 | template <class Tr> |
467 | void RegionBase<Tr>::print(raw_ostream &OS, bool print_tree, unsigned level, |
468 | PrintStyle Style) const { |
469 | if (print_tree) |
470 | OS.indent(NumSpaces: level * 2) << '[' << level << "] " << getNameStr(); |
471 | else |
472 | OS.indent(NumSpaces: level * 2) << getNameStr(); |
473 | |
474 | OS << '\n'; |
475 | |
476 | if (Style != PrintNone) { |
477 | OS.indent(NumSpaces: level * 2) << "{\n" ; |
478 | OS.indent(NumSpaces: level * 2 + 2); |
479 | |
480 | if (Style == PrintBB) { |
481 | for (const auto *BB : blocks()) |
482 | OS << BB->getName() << ", " ; // TODO: remove the last "," |
483 | } else if (Style == PrintRN) { |
484 | for (const RegionNodeT *Element : elements()) { |
485 | OS << *Element << ", " ; // TODO: remove the last ", |
486 | } |
487 | } |
488 | |
489 | OS << '\n'; |
490 | } |
491 | |
492 | if (print_tree) { |
493 | for (const std::unique_ptr<RegionT> &R : *this) |
494 | R->print(OS, print_tree, level + 1, Style); |
495 | } |
496 | |
497 | if (Style != PrintNone) |
498 | OS.indent(NumSpaces: level * 2) << "} \n" ; |
499 | } |
500 | |
501 | #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) |
502 | template <class Tr> |
503 | void RegionBase<Tr>::dump() const { |
504 | print(OS&: dbgs(), print_tree: true, level: getDepth(), Style: RegionInfoBase<Tr>::printStyle); |
505 | } |
506 | #endif |
507 | |
508 | template <class Tr> |
509 | void RegionBase<Tr>::clearNodeCache() { |
510 | BBNodeMap.clear(); |
511 | for (std::unique_ptr<RegionT> &R : *this) |
512 | R->clearNodeCache(); |
513 | } |
514 | |
515 | //===----------------------------------------------------------------------===// |
516 | // RegionInfoBase implementation |
517 | // |
518 | |
519 | template <class Tr> |
520 | RegionInfoBase<Tr>::RegionInfoBase() = default; |
521 | |
522 | template <class Tr> |
523 | RegionInfoBase<Tr>::~RegionInfoBase() { |
524 | releaseMemory(); |
525 | } |
526 | |
527 | template <class Tr> |
528 | void RegionInfoBase<Tr>::verifyBBMap(const RegionT *R) const { |
529 | assert(R && "Re must be non-null" ); |
530 | for (const typename Tr::RegionNodeT *Element : R->elements()) { |
531 | if (Element->isSubRegion()) { |
532 | const RegionT *SR = Element->template getNodeAs<RegionT>(); |
533 | verifyBBMap(R: SR); |
534 | } else { |
535 | BlockT *BB = Element->template getNodeAs<BlockT>(); |
536 | if (getRegionFor(BB) != R) |
537 | report_fatal_error(reason: "BB map does not match region nesting" ); |
538 | } |
539 | } |
540 | } |
541 | |
542 | template <class Tr> |
543 | bool RegionInfoBase<Tr>::isCommonDomFrontier(BlockT *BB, BlockT *entry, |
544 | BlockT *exit) const { |
545 | for (BlockT *P : llvm::inverse_children<BlockT *>(BB)) { |
546 | if (DT->dominates(entry, P) && !DT->dominates(exit, P)) |
547 | return false; |
548 | } |
549 | |
550 | return true; |
551 | } |
552 | |
553 | template <class Tr> |
554 | bool RegionInfoBase<Tr>::isRegion(BlockT *entry, BlockT *exit) const { |
555 | assert(entry && exit && "entry and exit must not be null!" ); |
556 | |
557 | using DST = typename DomFrontierT::DomSetType; |
558 | |
559 | DST *entrySuccs = &DF->find(entry)->second; |
560 | |
561 | // Exit is the header of a loop that contains the entry. In this case, |
562 | // the dominance frontier must only contain the exit. |
563 | if (!DT->dominates(entry, exit)) { |
564 | for (BlockT *successor : *entrySuccs) { |
565 | if (successor != exit && successor != entry) |
566 | return false; |
567 | } |
568 | |
569 | return true; |
570 | } |
571 | |
572 | DST *exitSuccs = &DF->find(exit)->second; |
573 | |
574 | // Do not allow edges leaving the region. |
575 | for (BlockT *Succ : *entrySuccs) { |
576 | if (Succ == exit || Succ == entry) |
577 | continue; |
578 | if (!exitSuccs->contains(Succ)) |
579 | return false; |
580 | if (!isCommonDomFrontier(BB: Succ, entry, exit)) |
581 | return false; |
582 | } |
583 | |
584 | // Do not allow edges pointing into the region. |
585 | for (BlockT *Succ : *exitSuccs) { |
586 | if (DT->properlyDominates(entry, Succ) && Succ != exit) |
587 | return false; |
588 | } |
589 | |
590 | return true; |
591 | } |
592 | |
593 | template <class Tr> |
594 | void RegionInfoBase<Tr>::insertShortCut(BlockT *entry, BlockT *exit, |
595 | BBtoBBMap *ShortCut) const { |
596 | assert(entry && exit && "entry and exit must not be null!" ); |
597 | |
598 | typename BBtoBBMap::iterator e = ShortCut->find(exit); |
599 | |
600 | if (e == ShortCut->end()) |
601 | // No further region at exit available. |
602 | (*ShortCut)[entry] = exit; |
603 | else { |
604 | // We found a region e that starts at exit. Therefore (entry, e->second) |
605 | // is also a region, that is larger than (entry, exit). Insert the |
606 | // larger one. |
607 | BlockT *BB = e->second; |
608 | (*ShortCut)[entry] = BB; |
609 | } |
610 | } |
611 | |
612 | template <class Tr> |
613 | typename Tr::DomTreeNodeT * |
614 | RegionInfoBase<Tr>::getNextPostDom(DomTreeNodeT *N, BBtoBBMap *ShortCut) const { |
615 | typename BBtoBBMap::iterator e = ShortCut->find(N->getBlock()); |
616 | |
617 | if (e == ShortCut->end()) |
618 | return N->getIDom(); |
619 | |
620 | return PDT->getNode(e->second)->getIDom(); |
621 | } |
622 | |
623 | template <class Tr> |
624 | bool RegionInfoBase<Tr>::isTrivialRegion(BlockT *entry, BlockT *exit) const { |
625 | assert(entry && exit && "entry and exit must not be null!" ); |
626 | |
627 | unsigned num_successors = |
628 | BlockTraits::child_end(entry) - BlockTraits::child_begin(entry); |
629 | |
630 | if (num_successors <= 1 && exit == *(BlockTraits::child_begin(entry))) |
631 | return true; |
632 | |
633 | return false; |
634 | } |
635 | |
636 | template <class Tr> |
637 | typename Tr::RegionT *RegionInfoBase<Tr>::createRegion(BlockT *entry, |
638 | BlockT *exit) { |
639 | assert(entry && exit && "entry and exit must not be null!" ); |
640 | |
641 | if (isTrivialRegion(entry, exit)) |
642 | return nullptr; |
643 | |
644 | RegionT *region = |
645 | new RegionT(entry, exit, static_cast<RegionInfoT *>(this), DT); |
646 | BBtoRegion.insert({entry, region}); |
647 | |
648 | region->verifyRegion(); |
649 | |
650 | updateStatistics(R: region); |
651 | return region; |
652 | } |
653 | |
654 | template <class Tr> |
655 | void RegionInfoBase<Tr>::findRegionsWithEntry(BlockT *entry, |
656 | BBtoBBMap *ShortCut) { |
657 | assert(entry); |
658 | |
659 | DomTreeNodeT *N = PDT->getNode(entry); |
660 | if (!N) |
661 | return; |
662 | |
663 | RegionT *lastRegion = nullptr; |
664 | BlockT *lastExit = entry; |
665 | |
666 | // As only a BasicBlock that postdominates entry can finish a region, walk the |
667 | // post dominance tree upwards. |
668 | while ((N = getNextPostDom(N, ShortCut))) { |
669 | BlockT *exit = N->getBlock(); |
670 | |
671 | if (!exit) |
672 | break; |
673 | |
674 | if (isRegion(entry, exit)) { |
675 | RegionT *newRegion = createRegion(entry, exit); |
676 | |
677 | if (lastRegion) |
678 | newRegion->addSubRegion(lastRegion); |
679 | |
680 | lastRegion = newRegion; |
681 | lastExit = exit; |
682 | } |
683 | |
684 | // This can never be a region, so stop the search. |
685 | if (!DT->dominates(entry, exit)) |
686 | break; |
687 | } |
688 | |
689 | // Tried to create regions from entry to lastExit. Next time take a |
690 | // shortcut from entry to lastExit. |
691 | if (lastExit != entry) |
692 | insertShortCut(entry, exit: lastExit, ShortCut); |
693 | } |
694 | |
695 | template <class Tr> |
696 | void RegionInfoBase<Tr>::scanForRegions(FuncT &F, BBtoBBMap *ShortCut) { |
697 | using FuncPtrT = std::add_pointer_t<FuncT>; |
698 | |
699 | BlockT *entry = GraphTraits<FuncPtrT>::getEntryNode(&F); |
700 | DomTreeNodeT *N = DT->getNode(entry); |
701 | |
702 | // Iterate over the dominance tree in post order to start with the small |
703 | // regions from the bottom of the dominance tree. If the small regions are |
704 | // detected first, detection of bigger regions is faster, as we can jump |
705 | // over the small regions. |
706 | for (auto DomNode : post_order(N)) |
707 | findRegionsWithEntry(entry: DomNode->getBlock(), ShortCut); |
708 | } |
709 | |
710 | template <class Tr> |
711 | typename Tr::RegionT *RegionInfoBase<Tr>::getTopMostParent(RegionT *region) { |
712 | while (region->getParent()) |
713 | region = region->getParent(); |
714 | |
715 | return region; |
716 | } |
717 | |
718 | template <class Tr> |
719 | void RegionInfoBase<Tr>::buildRegionsTree(DomTreeNodeT *N, RegionT *region) { |
720 | BlockT *BB = N->getBlock(); |
721 | |
722 | // Passed region exit |
723 | while (BB == region->getExit()) |
724 | region = region->getParent(); |
725 | |
726 | typename BBtoRegionMap::iterator it = BBtoRegion.find(BB); |
727 | |
728 | // This basic block is a start block of a region. It is already in the |
729 | // BBtoRegion relation. Only the child basic blocks have to be updated. |
730 | if (it != BBtoRegion.end()) { |
731 | RegionT *newRegion = it->second; |
732 | region->addSubRegion(getTopMostParent(region: newRegion)); |
733 | region = newRegion; |
734 | } else { |
735 | BBtoRegion[BB] = region; |
736 | } |
737 | |
738 | for (DomTreeNodeBase<BlockT> *C : *N) { |
739 | buildRegionsTree(N: C, region); |
740 | } |
741 | } |
742 | |
743 | #ifdef EXPENSIVE_CHECKS |
744 | template <class Tr> |
745 | bool RegionInfoBase<Tr>::VerifyRegionInfo = true; |
746 | #else |
747 | template <class Tr> |
748 | bool RegionInfoBase<Tr>::VerifyRegionInfo = false; |
749 | #endif |
750 | |
751 | template <class Tr> |
752 | typename Tr::RegionT::PrintStyle RegionInfoBase<Tr>::printStyle = |
753 | RegionBase<Tr>::PrintNone; |
754 | |
755 | template <class Tr> |
756 | void RegionInfoBase<Tr>::print(raw_ostream &OS) const { |
757 | OS << "Region tree:\n" ; |
758 | TopLevelRegion->print(OS, true, 0, printStyle); |
759 | OS << "End region tree\n" ; |
760 | } |
761 | |
762 | #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) |
763 | template <class Tr> |
764 | void RegionInfoBase<Tr>::dump() const { print(OS&: dbgs()); } |
765 | #endif |
766 | |
767 | template <class Tr> void RegionInfoBase<Tr>::releaseMemory() { |
768 | BBtoRegion.clear(); |
769 | if (TopLevelRegion) { |
770 | delete TopLevelRegion; |
771 | TopLevelRegion = nullptr; |
772 | } |
773 | } |
774 | |
775 | template <class Tr> |
776 | void RegionInfoBase<Tr>::verifyAnalysis() const { |
777 | // Do only verify regions if explicitely activated using EXPENSIVE_CHECKS or |
778 | // -verify-region-info |
779 | if (!RegionInfoBase<Tr>::VerifyRegionInfo) |
780 | return; |
781 | |
782 | TopLevelRegion->verifyRegionNest(); |
783 | |
784 | verifyBBMap(R: TopLevelRegion); |
785 | } |
786 | |
787 | // Region pass manager support. |
788 | template <class Tr> |
789 | typename Tr::RegionT *RegionInfoBase<Tr>::getRegionFor(BlockT *BB) const { |
790 | return BBtoRegion.lookup(BB); |
791 | } |
792 | |
793 | template <class Tr> |
794 | void RegionInfoBase<Tr>::setRegionFor(BlockT *BB, RegionT *R) { |
795 | BBtoRegion[BB] = R; |
796 | } |
797 | |
798 | template <class Tr> |
799 | typename Tr::RegionT *RegionInfoBase<Tr>::operator[](BlockT *BB) const { |
800 | return getRegionFor(BB); |
801 | } |
802 | |
803 | template <class Tr> |
804 | typename RegionInfoBase<Tr>::BlockT * |
805 | RegionInfoBase<Tr>::getMaxRegionExit(BlockT *BB) const { |
806 | BlockT *Exit = nullptr; |
807 | |
808 | while (true) { |
809 | // Get largest region that starts at BB. |
810 | RegionT *R = getRegionFor(BB); |
811 | while (R && R->getParent() && R->getParent()->getEntry() == BB) |
812 | R = R->getParent(); |
813 | |
814 | // Get the single exit of BB. |
815 | if (R && R->getEntry() == BB) |
816 | Exit = R->getExit(); |
817 | else if (++BlockTraits::child_begin(BB) == BlockTraits::child_end(BB)) |
818 | Exit = *BlockTraits::child_begin(BB); |
819 | else // No single exit exists. |
820 | return Exit; |
821 | |
822 | // Get largest region that starts at Exit. |
823 | RegionT *ExitR = getRegionFor(BB: Exit); |
824 | while (ExitR && ExitR->getParent() && |
825 | ExitR->getParent()->getEntry() == Exit) |
826 | ExitR = ExitR->getParent(); |
827 | |
828 | for (BlockT *Pred : llvm::inverse_children<BlockT *>(Exit)) { |
829 | if (!R->contains(Pred) && !ExitR->contains(Pred)) |
830 | break; |
831 | } |
832 | |
833 | // This stops infinite cycles. |
834 | if (DT->dominates(Exit, BB)) |
835 | break; |
836 | |
837 | BB = Exit; |
838 | } |
839 | |
840 | return Exit; |
841 | } |
842 | |
843 | template <class Tr> |
844 | typename Tr::RegionT *RegionInfoBase<Tr>::getCommonRegion(RegionT *A, |
845 | RegionT *B) const { |
846 | assert(A && B && "One of the Regions is NULL" ); |
847 | |
848 | if (A->contains(B)) |
849 | return A; |
850 | |
851 | while (!B->contains(A)) |
852 | B = B->getParent(); |
853 | |
854 | return B; |
855 | } |
856 | |
857 | template <class Tr> |
858 | typename Tr::RegionT * |
859 | RegionInfoBase<Tr>::getCommonRegion(SmallVectorImpl<RegionT *> &Regions) const { |
860 | RegionT *ret = Regions.pop_back_val(); |
861 | |
862 | for (RegionT *R : Regions) |
863 | ret = getCommonRegion(ret, R); |
864 | |
865 | return ret; |
866 | } |
867 | |
868 | template <class Tr> |
869 | typename Tr::RegionT * |
870 | RegionInfoBase<Tr>::getCommonRegion(SmallVectorImpl<BlockT *> &BBs) const { |
871 | RegionT *ret = getRegionFor(BB: BBs.back()); |
872 | BBs.pop_back(); |
873 | |
874 | for (BlockT *BB : BBs) |
875 | ret = getCommonRegion(ret, getRegionFor(BB)); |
876 | |
877 | return ret; |
878 | } |
879 | |
880 | template <class Tr> |
881 | void RegionInfoBase<Tr>::calculate(FuncT &F) { |
882 | using FuncPtrT = std::add_pointer_t<FuncT>; |
883 | |
884 | // ShortCut a function where for every BB the exit of the largest region |
885 | // starting with BB is stored. These regions can be threated as single BBS. |
886 | // This improves performance on linear CFGs. |
887 | BBtoBBMap ShortCut; |
888 | |
889 | scanForRegions(F, ShortCut: &ShortCut); |
890 | BlockT *BB = GraphTraits<FuncPtrT>::getEntryNode(&F); |
891 | buildRegionsTree(N: DT->getNode(BB), region: TopLevelRegion); |
892 | } |
893 | |
894 | } // end namespace llvm |
895 | |
896 | #undef DEBUG_TYPE |
897 | |
898 | #endif // LLVM_ANALYSIS_REGIONINFOIMPL_H |
899 | |