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