1 | //===- RegionInfo.h - SESE region 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 | // |
9 | // Calculate a program structure tree built out of single entry single exit |
10 | // regions. |
11 | // The basic ideas are taken from "The Program Structure Tree - Richard Johnson, |
12 | // David Pearson, Keshav Pingali - 1994", however enriched with ideas from "The |
13 | // Refined Process Structure Tree - Jussi Vanhatalo, Hagen Voelyer, Jana |
14 | // Koehler - 2009". |
15 | // The algorithm to calculate these data structures however is completely |
16 | // different, as it takes advantage of existing information already available |
17 | // in (Post)dominace tree and dominance frontier passes. This leads to a simpler |
18 | // and in practice hopefully better performing algorithm. The runtime of the |
19 | // algorithms described in the papers above are both linear in graph size, |
20 | // O(V+E), whereas this algorithm is not, as the dominance frontier information |
21 | // itself is not, but in practice runtime seems to be in the order of magnitude |
22 | // of dominance tree calculation. |
23 | // |
24 | // WARNING: LLVM is generally very concerned about compile time such that |
25 | // the use of additional analysis passes in the default |
26 | // optimization sequence is avoided as much as possible. |
27 | // Specifically, if you do not need the RegionInfo, but dominance |
28 | // information could be sufficient please base your work only on |
29 | // the dominator tree. Most passes maintain it, such that using |
30 | // it has often near zero cost. In contrast RegionInfo is by |
31 | // default not available, is not maintained by existing |
32 | // transformations and there is no intention to do so. |
33 | // |
34 | //===----------------------------------------------------------------------===// |
35 | |
36 | #ifndef LLVM_ANALYSIS_REGIONINFO_H |
37 | #define LLVM_ANALYSIS_REGIONINFO_H |
38 | |
39 | #include "llvm/ADT/DenseMap.h" |
40 | #include "llvm/ADT/DepthFirstIterator.h" |
41 | #include "llvm/ADT/GraphTraits.h" |
42 | #include "llvm/ADT/PointerIntPair.h" |
43 | #include "llvm/ADT/iterator_range.h" |
44 | #include "llvm/Config/llvm-config.h" |
45 | #include "llvm/IR/Dominators.h" |
46 | #include "llvm/IR/PassManager.h" |
47 | #include "llvm/Pass.h" |
48 | #include <algorithm> |
49 | #include <cassert> |
50 | #include <map> |
51 | #include <memory> |
52 | #include <set> |
53 | #include <string> |
54 | #include <type_traits> |
55 | #include <vector> |
56 | |
57 | namespace llvm { |
58 | |
59 | class BasicBlock; |
60 | class DominanceFrontier; |
61 | class Loop; |
62 | class LoopInfo; |
63 | class PostDominatorTree; |
64 | class Region; |
65 | template <class RegionTr> class RegionBase; |
66 | class RegionInfo; |
67 | template <class RegionTr> class RegionInfoBase; |
68 | class RegionNode; |
69 | class raw_ostream; |
70 | |
71 | // Class to be specialized for different users of RegionInfo |
72 | // (i.e. BasicBlocks or MachineBasicBlocks). This is only to avoid needing to |
73 | // pass around an unreasonable number of template parameters. |
74 | template <class FuncT_> |
75 | struct RegionTraits { |
76 | // FuncT |
77 | // BlockT |
78 | // RegionT |
79 | // RegionNodeT |
80 | // RegionInfoT |
81 | using BrokenT = typename FuncT_::UnknownRegionTypeError; |
82 | }; |
83 | |
84 | template <> |
85 | struct RegionTraits<Function> { |
86 | using FuncT = Function; |
87 | using BlockT = BasicBlock; |
88 | using RegionT = Region; |
89 | using RegionNodeT = RegionNode; |
90 | using RegionInfoT = RegionInfo; |
91 | using DomTreeT = DominatorTree; |
92 | using DomTreeNodeT = DomTreeNode; |
93 | using DomFrontierT = DominanceFrontier; |
94 | using PostDomTreeT = PostDominatorTree; |
95 | using InstT = Instruction; |
96 | using LoopT = Loop; |
97 | using LoopInfoT = LoopInfo; |
98 | |
99 | static unsigned getNumSuccessors(BasicBlock *BB) { |
100 | return BB->getTerminator()->getNumSuccessors(); |
101 | } |
102 | }; |
103 | |
104 | /// Marker class to iterate over the elements of a Region in flat mode. |
105 | /// |
106 | /// The class is used to either iterate in Flat mode or by not using it to not |
107 | /// iterate in Flat mode. During a Flat mode iteration all Regions are entered |
108 | /// and the iteration returns every BasicBlock. If the Flat mode is not |
109 | /// selected for SubRegions just one RegionNode containing the subregion is |
110 | /// returned. |
111 | template <class GraphType> |
112 | class FlatIt {}; |
113 | |
114 | /// A RegionNode represents a subregion or a BasicBlock that is part of a |
115 | /// Region. |
116 | template <class Tr> |
117 | class RegionNodeBase { |
118 | friend class RegionBase<Tr>; |
119 | |
120 | public: |
121 | using BlockT = typename Tr::BlockT; |
122 | using RegionT = typename Tr::RegionT; |
123 | |
124 | private: |
125 | /// This is the entry basic block that starts this region node. If this is a |
126 | /// BasicBlock RegionNode, then entry is just the basic block, that this |
127 | /// RegionNode represents. Otherwise it is the entry of this (Sub)RegionNode. |
128 | /// |
129 | /// In the BBtoRegionNode map of the parent of this node, BB will always map |
130 | /// to this node no matter which kind of node this one is. |
131 | /// |
132 | /// The node can hold either a Region or a BasicBlock. |
133 | /// Use one bit to save, if this RegionNode is a subregion or BasicBlock |
134 | /// RegionNode. |
135 | PointerIntPair<BlockT *, 1, bool> entry; |
136 | |
137 | /// The parent Region of this RegionNode. |
138 | /// @see getParent() |
139 | RegionT *parent; |
140 | |
141 | protected: |
142 | /// Create a RegionNode. |
143 | /// |
144 | /// @param Parent The parent of this RegionNode. |
145 | /// @param Entry The entry BasicBlock of the RegionNode. If this |
146 | /// RegionNode represents a BasicBlock, this is the |
147 | /// BasicBlock itself. If it represents a subregion, this |
148 | /// is the entry BasicBlock of the subregion. |
149 | /// @param isSubRegion If this RegionNode represents a SubRegion. |
150 | inline RegionNodeBase(RegionT *Parent, BlockT *Entry, |
151 | bool isSubRegion = false) |
152 | : entry(Entry, isSubRegion), parent(Parent) {} |
153 | |
154 | public: |
155 | RegionNodeBase(const RegionNodeBase &) = delete; |
156 | RegionNodeBase &operator=(const RegionNodeBase &) = delete; |
157 | |
158 | /// Get the parent Region of this RegionNode. |
159 | /// |
160 | /// The parent Region is the Region this RegionNode belongs to. If for |
161 | /// example a BasicBlock is element of two Regions, there exist two |
162 | /// RegionNodes for this BasicBlock. Each with the getParent() function |
163 | /// pointing to the Region this RegionNode belongs to. |
164 | /// |
165 | /// @return Get the parent Region of this RegionNode. |
166 | inline RegionT *getParent() const { return parent; } |
167 | |
168 | /// Get the entry BasicBlock of this RegionNode. |
169 | /// |
170 | /// If this RegionNode represents a BasicBlock this is just the BasicBlock |
171 | /// itself, otherwise we return the entry BasicBlock of the Subregion |
172 | /// |
173 | /// @return The entry BasicBlock of this RegionNode. |
174 | inline BlockT *getEntry() const { return entry.getPointer(); } |
175 | |
176 | /// Get the content of this RegionNode. |
177 | /// |
178 | /// This can be either a BasicBlock or a subregion. Before calling getNodeAs() |
179 | /// check the type of the content with the isSubRegion() function call. |
180 | /// |
181 | /// @return The content of this RegionNode. |
182 | template <class T> inline T *getNodeAs() const; |
183 | |
184 | /// Is this RegionNode a subregion? |
185 | /// |
186 | /// @return True if it contains a subregion. False if it contains a |
187 | /// BasicBlock. |
188 | inline bool isSubRegion() const { return entry.getInt(); } |
189 | }; |
190 | |
191 | //===----------------------------------------------------------------------===// |
192 | /// A single entry single exit Region. |
193 | /// |
194 | /// A Region is a connected subgraph of a control flow graph that has exactly |
195 | /// two connections to the remaining graph. It can be used to analyze or |
196 | /// optimize parts of the control flow graph. |
197 | /// |
198 | /// A <em> simple Region </em> is connected to the remaining graph by just two |
199 | /// edges. One edge entering the Region and another one leaving the Region. |
200 | /// |
201 | /// An <em> extended Region </em> (or just Region) is a subgraph that can be |
202 | /// transform into a simple Region. The transformation is done by adding |
203 | /// BasicBlocks that merge several entry or exit edges so that after the merge |
204 | /// just one entry and one exit edge exists. |
205 | /// |
206 | /// The \e Entry of a Region is the first BasicBlock that is passed after |
207 | /// entering the Region. It is an element of the Region. The entry BasicBlock |
208 | /// dominates all BasicBlocks in the Region. |
209 | /// |
210 | /// The \e Exit of a Region is the first BasicBlock that is passed after |
211 | /// leaving the Region. It is not an element of the Region. The exit BasicBlock, |
212 | /// postdominates all BasicBlocks in the Region. |
213 | /// |
214 | /// A <em> canonical Region </em> cannot be constructed by combining smaller |
215 | /// Regions. |
216 | /// |
217 | /// Region A is the \e parent of Region B, if B is completely contained in A. |
218 | /// |
219 | /// Two canonical Regions either do not intersect at all or one is |
220 | /// the parent of the other. |
221 | /// |
222 | /// The <em> Program Structure Tree</em> is a graph (V, E) where V is the set of |
223 | /// Regions in the control flow graph and E is the \e parent relation of these |
224 | /// Regions. |
225 | /// |
226 | /// Example: |
227 | /// |
228 | /// \verbatim |
229 | /// A simple control flow graph, that contains two regions. |
230 | /// |
231 | /// 1 |
232 | /// / | |
233 | /// 2 | |
234 | /// / \ 3 |
235 | /// 4 5 | |
236 | /// | | | |
237 | /// 6 7 8 |
238 | /// \ | / |
239 | /// \ |/ Region A: 1 -> 9 {1,2,3,4,5,6,7,8} |
240 | /// 9 Region B: 2 -> 9 {2,4,5,6,7} |
241 | /// \endverbatim |
242 | /// |
243 | /// You can obtain more examples by either calling |
244 | /// |
245 | /// <tt> "opt -passes='print<regions>' anyprogram.ll" </tt> |
246 | /// or |
247 | /// <tt> "opt -view-regions-only anyprogram.ll" </tt> |
248 | /// |
249 | /// on any LLVM file you are interested in. |
250 | /// |
251 | /// The first call returns a textual representation of the program structure |
252 | /// tree, the second one creates a graphical representation using graphviz. |
253 | template <class Tr> |
254 | class RegionBase : public RegionNodeBase<Tr> { |
255 | friend class RegionInfoBase<Tr>; |
256 | |
257 | using FuncT = typename Tr::FuncT; |
258 | using BlockT = typename Tr::BlockT; |
259 | using RegionInfoT = typename Tr::RegionInfoT; |
260 | using RegionT = typename Tr::RegionT; |
261 | using RegionNodeT = typename Tr::RegionNodeT; |
262 | using DomTreeT = typename Tr::DomTreeT; |
263 | using LoopT = typename Tr::LoopT; |
264 | using LoopInfoT = typename Tr::LoopInfoT; |
265 | using InstT = typename Tr::InstT; |
266 | |
267 | using BlockTraits = GraphTraits<BlockT *>; |
268 | using InvBlockTraits = GraphTraits<Inverse<BlockT *>>; |
269 | using SuccIterTy = typename BlockTraits::ChildIteratorType; |
270 | using PredIterTy = typename InvBlockTraits::ChildIteratorType; |
271 | |
272 | // Information necessary to manage this Region. |
273 | RegionInfoT *RI; |
274 | DomTreeT *DT; |
275 | |
276 | // The exit BasicBlock of this region. |
277 | // (The entry BasicBlock is part of RegionNode) |
278 | BlockT *exit; |
279 | |
280 | using RegionSet = std::vector<std::unique_ptr<RegionT>>; |
281 | |
282 | // The subregions of this region. |
283 | RegionSet children; |
284 | |
285 | using BBNodeMapT = std::map<BlockT *, std::unique_ptr<RegionNodeT>>; |
286 | |
287 | // Save the BasicBlock RegionNodes that are element of this Region. |
288 | mutable BBNodeMapT BBNodeMap; |
289 | |
290 | /// Check if a BB is in this Region. This check also works |
291 | /// if the region is incorrectly built. (EXPENSIVE!) |
292 | void verifyBBInRegion(BlockT *BB) const; |
293 | |
294 | /// Walk over all the BBs of the region starting from BB and |
295 | /// verify that all reachable basic blocks are elements of the region. |
296 | /// (EXPENSIVE!) |
297 | void verifyWalk(BlockT *BB, std::set<BlockT *> *visitedBB) const; |
298 | |
299 | /// Verify if the region and its children are valid regions (EXPENSIVE!) |
300 | void verifyRegionNest() const; |
301 | |
302 | public: |
303 | /// Create a new region. |
304 | /// |
305 | /// @param Entry The entry basic block of the region. |
306 | /// @param Exit The exit basic block of the region. |
307 | /// @param RI The region info object that is managing this region. |
308 | /// @param DT The dominator tree of the current function. |
309 | /// @param Parent The surrounding region or NULL if this is a top level |
310 | /// region. |
311 | RegionBase(BlockT *Entry, BlockT *Exit, RegionInfoT *RI, DomTreeT *DT, |
312 | RegionT *Parent = nullptr); |
313 | |
314 | RegionBase(const RegionBase &) = delete; |
315 | RegionBase &operator=(const RegionBase &) = delete; |
316 | |
317 | /// Delete the Region and all its subregions. |
318 | ~RegionBase(); |
319 | |
320 | /// Get the entry BasicBlock of the Region. |
321 | /// @return The entry BasicBlock of the region. |
322 | BlockT *getEntry() const { |
323 | return RegionNodeBase<Tr>::getEntry(); |
324 | } |
325 | |
326 | /// Replace the entry basic block of the region with the new basic |
327 | /// block. |
328 | /// |
329 | /// @param BB The new entry basic block of the region. |
330 | void replaceEntry(BlockT *BB); |
331 | |
332 | /// Replace the exit basic block of the region with the new basic |
333 | /// block. |
334 | /// |
335 | /// @param BB The new exit basic block of the region. |
336 | void replaceExit(BlockT *BB); |
337 | |
338 | /// Recursively replace the entry basic block of the region. |
339 | /// |
340 | /// This function replaces the entry basic block with a new basic block. It |
341 | /// also updates all child regions that have the same entry basic block as |
342 | /// this region. |
343 | /// |
344 | /// @param NewEntry The new entry basic block. |
345 | void replaceEntryRecursive(BlockT *NewEntry); |
346 | |
347 | /// Recursively replace the exit basic block of the region. |
348 | /// |
349 | /// This function replaces the exit basic block with a new basic block. It |
350 | /// also updates all child regions that have the same exit basic block as |
351 | /// this region. |
352 | /// |
353 | /// @param NewExit The new exit basic block. |
354 | void replaceExitRecursive(BlockT *NewExit); |
355 | |
356 | /// Get the exit BasicBlock of the Region. |
357 | /// @return The exit BasicBlock of the Region, NULL if this is the TopLevel |
358 | /// Region. |
359 | BlockT *getExit() const { return exit; } |
360 | |
361 | /// Get the parent of the Region. |
362 | /// @return The parent of the Region or NULL if this is a top level |
363 | /// Region. |
364 | RegionT *getParent() const { |
365 | return RegionNodeBase<Tr>::getParent(); |
366 | } |
367 | |
368 | /// Get the RegionNode representing the current Region. |
369 | /// @return The RegionNode representing the current Region. |
370 | RegionNodeT *getNode() const { |
371 | return const_cast<RegionNodeT *>( |
372 | reinterpret_cast<const RegionNodeT *>(this)); |
373 | } |
374 | |
375 | /// Get the nesting level of this Region. |
376 | /// |
377 | /// An toplevel Region has depth 0. |
378 | /// |
379 | /// @return The depth of the region. |
380 | unsigned getDepth() const; |
381 | |
382 | /// Check if a Region is the TopLevel region. |
383 | /// |
384 | /// The toplevel region represents the whole function. |
385 | bool isTopLevelRegion() const { return exit == nullptr; } |
386 | |
387 | /// Return a new (non-canonical) region, that is obtained by joining |
388 | /// this region with its predecessors. |
389 | /// |
390 | /// @return A region also starting at getEntry(), but reaching to the next |
391 | /// basic block that forms with getEntry() a (non-canonical) region. |
392 | /// NULL if such a basic block does not exist. |
393 | RegionT *getExpandedRegion() const; |
394 | |
395 | /// Return the first block of this region's single entry edge, |
396 | /// if existing. |
397 | /// |
398 | /// @return The BasicBlock starting this region's single entry edge, |
399 | /// else NULL. |
400 | BlockT *getEnteringBlock() const; |
401 | |
402 | /// Return the first block of this region's single exit edge, |
403 | /// if existing. |
404 | /// |
405 | /// @return The BasicBlock starting this region's single exit edge, |
406 | /// else NULL. |
407 | BlockT *getExitingBlock() const; |
408 | |
409 | /// Collect all blocks of this region's single exit edge, if existing. |
410 | /// |
411 | /// @return True if this region contains all the predecessors of the exit. |
412 | bool getExitingBlocks(SmallVectorImpl<BlockT *> &Exitings) const; |
413 | |
414 | /// Is this a simple region? |
415 | /// |
416 | /// A region is simple if it has exactly one exit and one entry edge. |
417 | /// |
418 | /// @return True if the Region is simple. |
419 | bool isSimple() const; |
420 | |
421 | /// Returns the name of the Region. |
422 | /// @return The Name of the Region. |
423 | std::string getNameStr() const; |
424 | |
425 | /// Return the RegionInfo object, that belongs to this Region. |
426 | RegionInfoT *getRegionInfo() const { return RI; } |
427 | |
428 | /// PrintStyle - Print region in difference ways. |
429 | enum PrintStyle { PrintNone, PrintBB, PrintRN }; |
430 | |
431 | /// Print the region. |
432 | /// |
433 | /// @param OS The output stream the Region is printed to. |
434 | /// @param printTree Print also the tree of subregions. |
435 | /// @param level The indentation level used for printing. |
436 | void print(raw_ostream &OS, bool printTree = true, unsigned level = 0, |
437 | PrintStyle Style = PrintNone) const; |
438 | |
439 | #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) |
440 | /// Print the region to stderr. |
441 | void dump() const; |
442 | #endif |
443 | |
444 | /// Check if the region contains a BasicBlock. |
445 | /// |
446 | /// @param BB The BasicBlock that might be contained in this Region. |
447 | /// @return True if the block is contained in the region otherwise false. |
448 | bool contains(const BlockT *BB) const; |
449 | |
450 | /// Check if the region contains another region. |
451 | /// |
452 | /// @param SubRegion The region that might be contained in this Region. |
453 | /// @return True if SubRegion is contained in the region otherwise false. |
454 | bool contains(const RegionT *SubRegion) const { |
455 | // Toplevel Region. |
456 | if (!getExit()) |
457 | return true; |
458 | |
459 | return contains(SubRegion->getEntry()) && |
460 | (contains(SubRegion->getExit()) || |
461 | SubRegion->getExit() == getExit()); |
462 | } |
463 | |
464 | /// Check if the region contains an Instruction. |
465 | /// |
466 | /// @param Inst The Instruction that might be contained in this region. |
467 | /// @return True if the Instruction is contained in the region otherwise |
468 | /// false. |
469 | bool contains(const InstT *Inst) const { return contains(Inst->getParent()); } |
470 | |
471 | /// Check if the region contains a loop. |
472 | /// |
473 | /// @param L The loop that might be contained in this region. |
474 | /// @return True if the loop is contained in the region otherwise false. |
475 | /// In case a NULL pointer is passed to this function the result |
476 | /// is false, except for the region that describes the whole function. |
477 | /// In that case true is returned. |
478 | bool contains(const LoopT *L) const; |
479 | |
480 | /// Get the outermost loop in the region that contains a loop. |
481 | /// |
482 | /// Find for a Loop L the outermost loop OuterL that is a parent loop of L |
483 | /// and is itself contained in the region. |
484 | /// |
485 | /// @param L The loop the lookup is started. |
486 | /// @return The outermost loop in the region, NULL if such a loop does not |
487 | /// exist or if the region describes the whole function. |
488 | LoopT *outermostLoopInRegion(LoopT *L) const; |
489 | |
490 | /// Get the outermost loop in the region that contains a basic block. |
491 | /// |
492 | /// Find for a basic block BB the outermost loop L that contains BB and is |
493 | /// itself contained in the region. |
494 | /// |
495 | /// @param LI A pointer to a LoopInfo analysis. |
496 | /// @param BB The basic block surrounded by the loop. |
497 | /// @return The outermost loop in the region, NULL if such a loop does not |
498 | /// exist or if the region describes the whole function. |
499 | LoopT *outermostLoopInRegion(LoopInfoT *LI, BlockT *BB) const; |
500 | |
501 | /// Get the subregion that starts at a BasicBlock |
502 | /// |
503 | /// @param BB The BasicBlock the subregion should start. |
504 | /// @return The Subregion if available, otherwise NULL. |
505 | RegionT *getSubRegionNode(BlockT *BB) const; |
506 | |
507 | /// Get the RegionNode for a BasicBlock |
508 | /// |
509 | /// @param BB The BasicBlock at which the RegionNode should start. |
510 | /// @return If available, the RegionNode that represents the subregion |
511 | /// starting at BB. If no subregion starts at BB, the RegionNode |
512 | /// representing BB. |
513 | RegionNodeT *getNode(BlockT *BB) const; |
514 | |
515 | /// Get the BasicBlock RegionNode for a BasicBlock |
516 | /// |
517 | /// @param BB The BasicBlock for which the RegionNode is requested. |
518 | /// @return The RegionNode representing the BB. |
519 | RegionNodeT *getBBNode(BlockT *BB) const; |
520 | |
521 | /// Add a new subregion to this Region. |
522 | /// |
523 | /// @param SubRegion The new subregion that will be added. |
524 | /// @param moveChildren Move the children of this region, that are also |
525 | /// contained in SubRegion into SubRegion. |
526 | void addSubRegion(RegionT *SubRegion, bool moveChildren = false); |
527 | |
528 | /// Remove a subregion from this Region. |
529 | /// |
530 | /// The subregion is not deleted, as it will probably be inserted into another |
531 | /// region. |
532 | /// @param SubRegion The SubRegion that will be removed. |
533 | RegionT *removeSubRegion(RegionT *SubRegion); |
534 | |
535 | /// Move all direct child nodes of this Region to another Region. |
536 | /// |
537 | /// @param To The Region the child nodes will be transferred to. |
538 | void transferChildrenTo(RegionT *To); |
539 | |
540 | /// Verify if the region is a correct region. |
541 | /// |
542 | /// Check if this is a correctly build Region. This is an expensive check, as |
543 | /// the complete CFG of the Region will be walked. |
544 | void verifyRegion() const; |
545 | |
546 | /// Clear the cache for BB RegionNodes. |
547 | /// |
548 | /// After calling this function the BasicBlock RegionNodes will be stored at |
549 | /// different memory locations. RegionNodes obtained before this function is |
550 | /// called are therefore not comparable to RegionNodes abtained afterwords. |
551 | void clearNodeCache(); |
552 | |
553 | /// @name Subregion Iterators |
554 | /// |
555 | /// These iterators iterator over all subregions of this Region. |
556 | //@{ |
557 | using iterator = typename RegionSet::iterator; |
558 | using const_iterator = typename RegionSet::const_iterator; |
559 | |
560 | iterator begin() { return children.begin(); } |
561 | iterator end() { return children.end(); } |
562 | |
563 | const_iterator begin() const { return children.begin(); } |
564 | const_iterator end() const { return children.end(); } |
565 | //@} |
566 | |
567 | /// @name BasicBlock Iterators |
568 | /// |
569 | /// These iterators iterate over all BasicBlocks that are contained in this |
570 | /// Region. The iterator also iterates over BasicBlocks that are elements of |
571 | /// a subregion of this Region. It is therefore called a flat iterator. |
572 | //@{ |
573 | template <bool IsConst> |
574 | class block_iterator_wrapper |
575 | : public df_iterator< |
576 | std::conditional_t<IsConst, const BlockT, BlockT> *> { |
577 | using super = |
578 | df_iterator<std::conditional_t<IsConst, const BlockT, BlockT> *>; |
579 | |
580 | public: |
581 | using Self = block_iterator_wrapper<IsConst>; |
582 | using value_type = typename super::value_type; |
583 | |
584 | // Construct the begin iterator. |
585 | block_iterator_wrapper(value_type Entry, value_type Exit) |
586 | : super(df_begin(Entry)) { |
587 | // Mark the exit of the region as visited, so that the children of the |
588 | // exit and the exit itself, i.e. the block outside the region will never |
589 | // be visited. |
590 | super::Visited.insert(Exit); |
591 | } |
592 | |
593 | // Construct the end iterator. |
594 | block_iterator_wrapper() : super(df_end<value_type>((BlockT *)nullptr)) {} |
595 | |
596 | /*implicit*/ block_iterator_wrapper(super I) : super(I) {} |
597 | |
598 | // FIXME: Even a const_iterator returns a non-const BasicBlock pointer. |
599 | // This was introduced for backwards compatibility, but should |
600 | // be removed as soon as all users are fixed. |
601 | BlockT *operator*() const { |
602 | return const_cast<BlockT *>(super::operator*()); |
603 | } |
604 | }; |
605 | |
606 | using block_iterator = block_iterator_wrapper<false>; |
607 | using const_block_iterator = block_iterator_wrapper<true>; |
608 | |
609 | block_iterator block_begin() { return block_iterator(getEntry(), getExit()); } |
610 | |
611 | block_iterator block_end() { return block_iterator(); } |
612 | |
613 | const_block_iterator block_begin() const { |
614 | return const_block_iterator(getEntry(), getExit()); |
615 | } |
616 | const_block_iterator block_end() const { return const_block_iterator(); } |
617 | |
618 | using block_range = iterator_range<block_iterator>; |
619 | using const_block_range = iterator_range<const_block_iterator>; |
620 | |
621 | /// Returns a range view of the basic blocks in the region. |
622 | inline block_range blocks() { |
623 | return block_range(block_begin(), block_end()); |
624 | } |
625 | |
626 | /// Returns a range view of the basic blocks in the region. |
627 | /// |
628 | /// This is the 'const' version of the range view. |
629 | inline const_block_range blocks() const { |
630 | return const_block_range(block_begin(), block_end()); |
631 | } |
632 | //@} |
633 | |
634 | /// @name Element Iterators |
635 | /// |
636 | /// These iterators iterate over all BasicBlock and subregion RegionNodes that |
637 | /// are direct children of this Region. It does not iterate over any |
638 | /// RegionNodes that are also element of a subregion of this Region. |
639 | //@{ |
640 | using element_iterator = |
641 | df_iterator<RegionNodeT *, df_iterator_default_set<RegionNodeT *>, false, |
642 | GraphTraits<RegionNodeT *>>; |
643 | |
644 | using const_element_iterator = |
645 | df_iterator<const RegionNodeT *, |
646 | df_iterator_default_set<const RegionNodeT *>, false, |
647 | GraphTraits<const RegionNodeT *>>; |
648 | |
649 | element_iterator element_begin(); |
650 | element_iterator element_end(); |
651 | iterator_range<element_iterator> elements() { |
652 | return make_range(element_begin(), element_end()); |
653 | } |
654 | |
655 | const_element_iterator element_begin() const; |
656 | const_element_iterator element_end() const; |
657 | iterator_range<const_element_iterator> elements() const { |
658 | return make_range(element_begin(), element_end()); |
659 | } |
660 | //@} |
661 | }; |
662 | |
663 | /// Print a RegionNode. |
664 | template <class Tr> |
665 | inline raw_ostream &operator<<(raw_ostream &OS, const RegionNodeBase<Tr> &Node); |
666 | |
667 | //===----------------------------------------------------------------------===// |
668 | /// Analysis that detects all canonical Regions. |
669 | /// |
670 | /// The RegionInfo pass detects all canonical regions in a function. The Regions |
671 | /// are connected using the parent relation. This builds a Program Structure |
672 | /// Tree. |
673 | template <class Tr> |
674 | class RegionInfoBase { |
675 | friend class RegionInfo; |
676 | friend class MachineRegionInfo; |
677 | |
678 | using BlockT = typename Tr::BlockT; |
679 | using FuncT = typename Tr::FuncT; |
680 | using RegionT = typename Tr::RegionT; |
681 | using RegionInfoT = typename Tr::RegionInfoT; |
682 | using DomTreeT = typename Tr::DomTreeT; |
683 | using DomTreeNodeT = typename Tr::DomTreeNodeT; |
684 | using PostDomTreeT = typename Tr::PostDomTreeT; |
685 | using DomFrontierT = typename Tr::DomFrontierT; |
686 | using BlockTraits = GraphTraits<BlockT *>; |
687 | using InvBlockTraits = GraphTraits<Inverse<BlockT *>>; |
688 | using SuccIterTy = typename BlockTraits::ChildIteratorType; |
689 | using PredIterTy = typename InvBlockTraits::ChildIteratorType; |
690 | |
691 | using BBtoBBMap = DenseMap<BlockT *, BlockT *>; |
692 | using BBtoRegionMap = DenseMap<BlockT *, RegionT *>; |
693 | |
694 | RegionInfoBase(); |
695 | |
696 | RegionInfoBase(RegionInfoBase &&Arg) |
697 | : DT(std::move(Arg.DT)), PDT(std::move(Arg.PDT)), DF(std::move(Arg.DF)), |
698 | TopLevelRegion(std::move(Arg.TopLevelRegion)), |
699 | BBtoRegion(std::move(Arg.BBtoRegion)) { |
700 | Arg.wipe(); |
701 | } |
702 | |
703 | RegionInfoBase &operator=(RegionInfoBase &&RHS) { |
704 | DT = std::move(RHS.DT); |
705 | PDT = std::move(RHS.PDT); |
706 | DF = std::move(RHS.DF); |
707 | TopLevelRegion = std::move(RHS.TopLevelRegion); |
708 | BBtoRegion = std::move(RHS.BBtoRegion); |
709 | RHS.wipe(); |
710 | return *this; |
711 | } |
712 | |
713 | virtual ~RegionInfoBase(); |
714 | |
715 | DomTreeT *DT; |
716 | PostDomTreeT *PDT; |
717 | DomFrontierT *DF; |
718 | |
719 | /// The top level region. |
720 | RegionT *TopLevelRegion = nullptr; |
721 | |
722 | /// Map every BB to the smallest region, that contains BB. |
723 | BBtoRegionMap BBtoRegion; |
724 | |
725 | protected: |
726 | /// Update refences to a RegionInfoT held by the RegionT managed here |
727 | /// |
728 | /// This is a post-move helper. Regions hold references to the owning |
729 | /// RegionInfo object. After a move these need to be fixed. |
730 | template<typename TheRegionT> |
731 | void updateRegionTree(RegionInfoT &RI, TheRegionT *R) { |
732 | if (!R) |
733 | return; |
734 | R->RI = &RI; |
735 | for (auto &SubR : *R) |
736 | updateRegionTree(RI, SubR.get()); |
737 | } |
738 | |
739 | private: |
740 | /// Wipe this region tree's state without releasing any resources. |
741 | /// |
742 | /// This is essentially a post-move helper only. It leaves the object in an |
743 | /// assignable and destroyable state, but otherwise invalid. |
744 | void wipe() { |
745 | DT = nullptr; |
746 | PDT = nullptr; |
747 | DF = nullptr; |
748 | TopLevelRegion = nullptr; |
749 | BBtoRegion.clear(); |
750 | } |
751 | |
752 | // Check whether the entries of BBtoRegion for the BBs of region |
753 | // SR are correct. Triggers an assertion if not. Calls itself recursively for |
754 | // subregions. |
755 | void verifyBBMap(const RegionT *SR) const; |
756 | |
757 | // Returns true if BB is in the dominance frontier of |
758 | // entry, because it was inherited from exit. In the other case there is an |
759 | // edge going from entry to BB without passing exit. |
760 | bool isCommonDomFrontier(BlockT *BB, BlockT *entry, BlockT *exit) const; |
761 | |
762 | // Check if entry and exit surround a valid region, based on |
763 | // dominance tree and dominance frontier. |
764 | bool isRegion(BlockT *entry, BlockT *exit) const; |
765 | |
766 | // Saves a shortcut pointing from entry to exit. |
767 | // This function may extend this shortcut if possible. |
768 | void insertShortCut(BlockT *entry, BlockT *exit, BBtoBBMap *ShortCut) const; |
769 | |
770 | // Returns the next BB that postdominates N, while skipping |
771 | // all post dominators that cannot finish a canonical region. |
772 | DomTreeNodeT *getNextPostDom(DomTreeNodeT *N, BBtoBBMap *ShortCut) const; |
773 | |
774 | // A region is trivial, if it contains only one BB. |
775 | bool isTrivialRegion(BlockT *entry, BlockT *exit) const; |
776 | |
777 | // Creates a single entry single exit region. |
778 | RegionT *createRegion(BlockT *entry, BlockT *exit); |
779 | |
780 | // Detect all regions starting with bb 'entry'. |
781 | void findRegionsWithEntry(BlockT *entry, BBtoBBMap *ShortCut); |
782 | |
783 | // Detects regions in F. |
784 | void scanForRegions(FuncT &F, BBtoBBMap *ShortCut); |
785 | |
786 | // Get the top most parent with the same entry block. |
787 | RegionT *getTopMostParent(RegionT *region); |
788 | |
789 | // Build the region hierarchy after all region detected. |
790 | void buildRegionsTree(DomTreeNodeT *N, RegionT *region); |
791 | |
792 | // Update statistic about created regions. |
793 | virtual void updateStatistics(RegionT *R) = 0; |
794 | |
795 | // Detect all regions in function and build the region tree. |
796 | void calculate(FuncT &F); |
797 | |
798 | public: |
799 | RegionInfoBase(const RegionInfoBase &) = delete; |
800 | RegionInfoBase &operator=(const RegionInfoBase &) = delete; |
801 | |
802 | static bool VerifyRegionInfo; |
803 | static typename RegionT::PrintStyle printStyle; |
804 | |
805 | void print(raw_ostream &OS) const; |
806 | #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) |
807 | void dump() const; |
808 | #endif |
809 | |
810 | void releaseMemory(); |
811 | |
812 | /// Get the smallest region that contains a BasicBlock. |
813 | /// |
814 | /// @param BB The basic block. |
815 | /// @return The smallest region, that contains BB or NULL, if there is no |
816 | /// region containing BB. |
817 | RegionT *getRegionFor(BlockT *BB) const; |
818 | |
819 | /// Set the smallest region that surrounds a basic block. |
820 | /// |
821 | /// @param BB The basic block surrounded by a region. |
822 | /// @param R The smallest region that surrounds BB. |
823 | void setRegionFor(BlockT *BB, RegionT *R); |
824 | |
825 | /// A shortcut for getRegionFor(). |
826 | /// |
827 | /// @param BB The basic block. |
828 | /// @return The smallest region, that contains BB or NULL, if there is no |
829 | /// region containing BB. |
830 | RegionT *operator[](BlockT *BB) const; |
831 | |
832 | /// Return the exit of the maximal refined region, that starts at a |
833 | /// BasicBlock. |
834 | /// |
835 | /// @param BB The BasicBlock the refined region starts. |
836 | BlockT *getMaxRegionExit(BlockT *BB) const; |
837 | |
838 | /// Find the smallest region that contains two regions. |
839 | /// |
840 | /// @param A The first region. |
841 | /// @param B The second region. |
842 | /// @return The smallest region containing A and B. |
843 | RegionT *getCommonRegion(RegionT *A, RegionT *B) const; |
844 | |
845 | /// Find the smallest region that contains two basic blocks. |
846 | /// |
847 | /// @param A The first basic block. |
848 | /// @param B The second basic block. |
849 | /// @return The smallest region that contains A and B. |
850 | RegionT *getCommonRegion(BlockT *A, BlockT *B) const { |
851 | return getCommonRegion(getRegionFor(BB: A), getRegionFor(BB: B)); |
852 | } |
853 | |
854 | /// Find the smallest region that contains a set of regions. |
855 | /// |
856 | /// @param Regions A vector of regions. |
857 | /// @return The smallest region that contains all regions in Regions. |
858 | RegionT *getCommonRegion(SmallVectorImpl<RegionT *> &Regions) const; |
859 | |
860 | /// Find the smallest region that contains a set of basic blocks. |
861 | /// |
862 | /// @param BBs A vector of basic blocks. |
863 | /// @return The smallest region that contains all basic blocks in BBS. |
864 | RegionT *getCommonRegion(SmallVectorImpl<BlockT *> &BBs) const; |
865 | |
866 | RegionT *getTopLevelRegion() const { return TopLevelRegion; } |
867 | |
868 | /// Clear the Node Cache for all Regions. |
869 | /// |
870 | /// @see Region::clearNodeCache() |
871 | void clearNodeCache() { |
872 | if (TopLevelRegion) |
873 | TopLevelRegion->clearNodeCache(); |
874 | } |
875 | |
876 | void verifyAnalysis() const; |
877 | }; |
878 | |
879 | class RegionNode : public RegionNodeBase<RegionTraits<Function>> { |
880 | public: |
881 | inline RegionNode(Region *Parent, BasicBlock *Entry, bool isSubRegion = false) |
882 | : RegionNodeBase<RegionTraits<Function>>(Parent, Entry, isSubRegion) {} |
883 | |
884 | bool operator==(const Region &RN) const { |
885 | return this == reinterpret_cast<const RegionNode *>(&RN); |
886 | } |
887 | }; |
888 | |
889 | class Region : public RegionBase<RegionTraits<Function>> { |
890 | public: |
891 | Region(BasicBlock *Entry, BasicBlock *Exit, RegionInfo *RI, DominatorTree *DT, |
892 | Region *Parent = nullptr); |
893 | ~Region(); |
894 | |
895 | bool operator==(const RegionNode &RN) const { |
896 | return &RN == reinterpret_cast<const RegionNode *>(this); |
897 | } |
898 | }; |
899 | |
900 | class RegionInfo : public RegionInfoBase<RegionTraits<Function>> { |
901 | public: |
902 | using Base = RegionInfoBase<RegionTraits<Function>>; |
903 | |
904 | explicit RegionInfo(); |
905 | |
906 | RegionInfo(RegionInfo &&Arg) : Base(std::move(static_cast<Base &>(Arg))) { |
907 | updateRegionTree(RI&: *this, R: TopLevelRegion); |
908 | } |
909 | |
910 | RegionInfo &operator=(RegionInfo &&RHS) { |
911 | Base::operator=(RHS: std::move(static_cast<Base &>(RHS))); |
912 | updateRegionTree(RI&: *this, R: TopLevelRegion); |
913 | return *this; |
914 | } |
915 | |
916 | ~RegionInfo() override; |
917 | |
918 | /// Handle invalidation explicitly. |
919 | bool invalidate(Function &F, const PreservedAnalyses &PA, |
920 | FunctionAnalysisManager::Invalidator &); |
921 | |
922 | // updateStatistics - Update statistic about created regions. |
923 | void updateStatistics(Region *R) final; |
924 | |
925 | void recalculate(Function &F, DominatorTree *DT, PostDominatorTree *PDT, |
926 | DominanceFrontier *DF); |
927 | |
928 | #ifndef NDEBUG |
929 | /// Opens a viewer to show the GraphViz visualization of the regions. |
930 | /// |
931 | /// Useful during debugging as an alternative to dump(). |
932 | void view(); |
933 | |
934 | /// Opens a viewer to show the GraphViz visualization of this region |
935 | /// without instructions in the BasicBlocks. |
936 | /// |
937 | /// Useful during debugging as an alternative to dump(). |
938 | void viewOnly(); |
939 | #endif |
940 | }; |
941 | |
942 | class RegionInfoPass : public FunctionPass { |
943 | RegionInfo RI; |
944 | |
945 | public: |
946 | static char ID; |
947 | |
948 | explicit RegionInfoPass(); |
949 | ~RegionInfoPass() override; |
950 | |
951 | RegionInfo &getRegionInfo() { return RI; } |
952 | |
953 | const RegionInfo &getRegionInfo() const { return RI; } |
954 | |
955 | /// @name FunctionPass interface |
956 | //@{ |
957 | bool runOnFunction(Function &F) override; |
958 | void releaseMemory() override; |
959 | void verifyAnalysis() const override; |
960 | void getAnalysisUsage(AnalysisUsage &AU) const override; |
961 | void print(raw_ostream &OS, const Module *) const override; |
962 | void dump() const; |
963 | //@} |
964 | }; |
965 | |
966 | /// Analysis pass that exposes the \c RegionInfo for a function. |
967 | class RegionInfoAnalysis : public AnalysisInfoMixin<RegionInfoAnalysis> { |
968 | friend AnalysisInfoMixin<RegionInfoAnalysis>; |
969 | |
970 | static AnalysisKey Key; |
971 | |
972 | public: |
973 | using Result = RegionInfo; |
974 | |
975 | RegionInfo run(Function &F, FunctionAnalysisManager &AM); |
976 | }; |
977 | |
978 | /// Printer pass for the \c RegionInfo. |
979 | class RegionInfoPrinterPass : public PassInfoMixin<RegionInfoPrinterPass> { |
980 | raw_ostream &OS; |
981 | |
982 | public: |
983 | explicit RegionInfoPrinterPass(raw_ostream &OS); |
984 | |
985 | PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); |
986 | |
987 | static bool isRequired() { return true; } |
988 | }; |
989 | |
990 | /// Verifier pass for the \c RegionInfo. |
991 | struct RegionInfoVerifierPass : PassInfoMixin<RegionInfoVerifierPass> { |
992 | PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); |
993 | static bool isRequired() { return true; } |
994 | }; |
995 | |
996 | template <> |
997 | template <> |
998 | inline BasicBlock * |
999 | RegionNodeBase<RegionTraits<Function>>::getNodeAs<BasicBlock>() const { |
1000 | assert(!isSubRegion() && "This is not a BasicBlock RegionNode!" ); |
1001 | return getEntry(); |
1002 | } |
1003 | |
1004 | template <> |
1005 | template <> |
1006 | inline Region * |
1007 | RegionNodeBase<RegionTraits<Function>>::getNodeAs<Region>() const { |
1008 | assert(isSubRegion() && "This is not a subregion RegionNode!" ); |
1009 | auto Unconst = const_cast<RegionNodeBase<RegionTraits<Function>> *>(this); |
1010 | return reinterpret_cast<Region *>(Unconst); |
1011 | } |
1012 | |
1013 | template <class Tr> |
1014 | inline raw_ostream &operator<<(raw_ostream &OS, |
1015 | const RegionNodeBase<Tr> &Node) { |
1016 | using BlockT = typename Tr::BlockT; |
1017 | using RegionT = typename Tr::RegionT; |
1018 | |
1019 | if (Node.isSubRegion()) |
1020 | return OS << Node.template getNodeAs<RegionT>()->getNameStr(); |
1021 | else |
1022 | return OS << Node.template getNodeAs<BlockT>()->getName(); |
1023 | } |
1024 | |
1025 | extern template class RegionBase<RegionTraits<Function>>; |
1026 | extern template class RegionNodeBase<RegionTraits<Function>>; |
1027 | extern template class RegionInfoBase<RegionTraits<Function>>; |
1028 | |
1029 | } // end namespace llvm |
1030 | |
1031 | #endif // LLVM_ANALYSIS_REGIONINFO_H |
1032 | |