llvm/ADT/GenericCycleInfo.h

0001 //===- GenericCycleInfo.h - Info for Cycles in any IR ------*- C++ -*------===//
0002 //
0003 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
0004 // See https://llvm.org/LICENSE.txt for license information.
0005 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
0006 //
0007 //===----------------------------------------------------------------------===//
0008 ///
0009 /// \file
0010 /// \brief Find all cycles in a control-flow graph, including irreducible loops.
0011 ///
0012 /// See docs/CycleTerminology.rst for a formal definition of cycles.
0013 ///
0014 /// Briefly:
0015 /// - A cycle is a generalization of a loop which can represent
0016 ///   irreducible control flow.
0017 /// - Cycles identified in a program are implementation defined,
0018 ///   depending on the DFS traversal chosen.
0019 /// - Cycles are well-nested, and form a forest with a parent-child
0020 ///   relationship.
0021 /// - In any choice of DFS, every natural loop L is represented by a
0022 ///   unique cycle C which is a superset of L.
0023 /// - In the absence of irreducible control flow, the cycles are
0024 ///   exactly the natural loops in the program.
0025 ///
0026 //===----------------------------------------------------------------------===//
0027
0028 #ifndef LLVM_ADT_GENERICCYCLEINFO_H
0029 #define LLVM_ADT_GENERICCYCLEINFO_H
0030
0031 #include "llvm/ADT/DenseSet.h"
0032 #include "llvm/ADT/GenericSSAContext.h"
0033 #include "llvm/ADT/GraphTraits.h"
0034 #include "llvm/ADT/SetVector.h"
0035 #include "llvm/Support/Debug.h"
0036 #include "llvm/Support/raw_ostream.h"
0037
0038 namespace llvm {
0039
0040 template <typename ContextT> class GenericCycleInfo;
0041 template <typename ContextT> class GenericCycleInfoCompute;
0042
0043 /// A possibly irreducible generalization of a \ref Loop.
0044 template <typename ContextT> class GenericCycle {
0045 public:
0046   using BlockT = typename ContextT::BlockT;
0047   using FunctionT = typename ContextT::FunctionT;
0048   template <typename> friend class GenericCycleInfo;
0049   template <typename> friend class GenericCycleInfoCompute;
0050
0051 private:
0052   /// The parent cycle. Is null for the root "cycle". Top-level cycles point
0053   /// at the root.
0054   GenericCycle *ParentCycle = nullptr;
0055
0056   /// The entry block(s) of the cycle. The header is the only entry if
0057   /// this is a loop. Is empty for the root "cycle", to avoid
0058   /// unnecessary memory use.
0059   SmallVector<BlockT *, 1> Entries;
0060
0061   /// Child cycles, if any.
0062   std::vector<std::unique_ptr<GenericCycle>> Children;
0063
0064   /// Basic blocks that are contained in the cycle, including entry blocks,
0065   /// and including blocks that are part of a child cycle.
0066   using BlockSetVectorT = SetVector<BlockT *, SmallVector<BlockT *, 8>,
0067                                     DenseSet<const BlockT *>, 8>;
0068   BlockSetVectorT Blocks;
0069
0070   /// Depth of the cycle in the tree. The root "cycle" is at depth 0.
0071   ///
0072   /// \note Depths are not necessarily contiguous. However, child loops always
0073   ///       have strictly greater depth than their parents, and sibling loops
0074   ///       always have the same depth.
0075   unsigned Depth = 0;
0076
0077   /// Cache for the results of GetExitBlocks
0078   mutable SmallVector<BlockT *, 4> ExitBlocksCache;
0079
0080   void clear() {
0081     Entries.clear();
0082     Children.clear();
0083     Blocks.clear();
0084     Depth = 0;
0085     ParentCycle = nullptr;
0086     clearCache();
0087   }
0088
0089   void appendEntry(BlockT *Block) {
0090     Entries.push_back(Block);
0091     clearCache();
0092   }
0093
0094   void appendBlock(BlockT *Block) {
0095     Blocks.insert(Block);
0096     clearCache();
0097   }
0098
0099   GenericCycle(const GenericCycle &) = delete;
0100   GenericCycle &operator=(const GenericCycle &) = delete;
0101   GenericCycle(GenericCycle &&Rhs) = delete;
0102   GenericCycle &operator=(GenericCycle &&Rhs) = delete;
0103
0104 public:
0105   GenericCycle() = default;
0106
0107   /// \brief Whether the cycle is a natural loop.
0108   bool isReducible() const { return Entries.size() == 1; }
0109
0110   BlockT *getHeader() const { return Entries[0]; }
0111
0112   const SmallVectorImpl<BlockT *> & getEntries() const {
0113     return Entries;
0114   }
0115
0116   /// Clear the cache of the cycle.
0117   /// This should be run in all non-const function in GenericCycle
0118   /// and GenericCycleInfo.
0119   void clearCache() const { ExitBlocksCache.clear(); }
0120
0121   /// \brief Return whether \p Block is an entry block of the cycle.
0122   bool isEntry(const BlockT *Block) const {
0123     return is_contained(Entries, Block);
0124   }
0125
0126   /// \brief Replace all entries with \p Block as single entry.
0127   void setSingleEntry(BlockT *Block) {
0128     assert(contains(Block));
0129     Entries.clear();
0130     Entries.push_back(Block);
0131     clearCache();
0132   }
0133
0134   /// \brief Return whether \p Block is contained in the cycle.
0135   bool contains(const BlockT *Block) const { return Blocks.contains(Block); }
0136
0137   /// \brief Returns true iff this cycle contains \p C.
0138   ///
0139   /// Note: Non-strict containment check, i.e. returns true if C is the
0140   /// same cycle.
0141   bool contains(const GenericCycle *C) const;
0142
0143   const GenericCycle *getParentCycle() const { return ParentCycle; }
0144   GenericCycle *getParentCycle() { return ParentCycle; }
0145   unsigned getDepth() const { return Depth; }
0146
0147   /// Return all of the successor blocks of this cycle.
0148   ///
0149   /// These are the blocks _outside of the current cycle_ which are
0150   /// branched to.
0151   void getExitBlocks(SmallVectorImpl<BlockT *> &TmpStorage) const;
0152
0153   /// Return all blocks of this cycle that have successor outside of this cycle.
0154   /// These blocks have cycle exit branch.
0155   void getExitingBlocks(SmallVectorImpl<BlockT *> &TmpStorage) const;
0156
0157   /// Return the preheader block for this cycle. Pre-header is well-defined for
0158   /// reducible cycle in docs/LoopTerminology.rst as: the only one entering
0159   /// block and its only edge is to the entry block. Return null for irreducible
0160   /// cycles.
0161   BlockT *getCyclePreheader() const;
0162
0163   /// If the cycle has exactly one entry with exactly one predecessor, return
0164   /// it, otherwise return nullptr.
0165   BlockT *getCyclePredecessor() const;
0166
0167   void verifyCycle() const;
0168   void verifyCycleNest() const;
0169
0170   /// Iteration over child cycles.
0171   //@{
0172   using const_child_iterator_base =
0173       typename std::vector<std::unique_ptr<GenericCycle>>::const_iterator;
0174   struct const_child_iterator
0175       : iterator_adaptor_base<const_child_iterator, const_child_iterator_base> {
0176     using Base =
0177         iterator_adaptor_base<const_child_iterator, const_child_iterator_base>;
0178
0179     const_child_iterator() = default;
0180     explicit const_child_iterator(const_child_iterator_base I) : Base(I) {}
0181
0182     const const_child_iterator_base &wrapped() { return Base::wrapped(); }
0183     GenericCycle *operator*() const { return Base::I->get(); }
0184   };
0185
0186   const_child_iterator child_begin() const {
0187     return const_child_iterator{Children.begin()};
0188   }
0189   const_child_iterator child_end() const {
0190     return const_child_iterator{Children.end()};
0191   }
0192   size_t getNumChildren() const { return Children.size(); }
0193   iterator_range<const_child_iterator> children() const {
0194     return llvm::make_range(const_child_iterator{Children.begin()},
0195                             const_child_iterator{Children.end()});
0196   }
0197   //@}
0198
0199   /// Iteration over blocks in the cycle (including entry blocks).
0200   //@{
0201   using const_block_iterator = typename BlockSetVectorT::const_iterator;
0202
0203   const_block_iterator block_begin() const {
0204     return const_block_iterator{Blocks.begin()};
0205   }
0206   const_block_iterator block_end() const {
0207     return const_block_iterator{Blocks.end()};
0208   }
0209   size_t getNumBlocks() const { return Blocks.size(); }
0210   iterator_range<const_block_iterator> blocks() const {
0211     return llvm::make_range(block_begin(), block_end());
0212   }
0213   //@}
0214
0215   /// Iteration over entry blocks.
0216   //@{
0217   using const_entry_iterator =
0218       typename SmallVectorImpl<BlockT *>::const_iterator;
0219   const_entry_iterator entry_begin() const { return Entries.begin(); }
0220   const_entry_iterator entry_end() const { return Entries.end(); }
0221   size_t getNumEntries() const { return Entries.size(); }
0222   iterator_range<const_entry_iterator> entries() const {
0223     return llvm::make_range(entry_begin(), entry_end());
0224   }
0225   using const_reverse_entry_iterator =
0226       typename SmallVectorImpl<BlockT *>::const_reverse_iterator;
0227   const_reverse_entry_iterator entry_rbegin() const { return Entries.rbegin(); }
0228   const_reverse_entry_iterator entry_rend() const { return Entries.rend(); }
0229   //@}
0230
0231   Printable printEntries(const ContextT &Ctx) const {
0232     return Printable([this, &Ctx](raw_ostream &Out) {
0233       bool First = true;
0234       for (auto *Entry : Entries) {
0235         if (!First)
0236           Out << ' ';
0237         First = false;
0238         Out << Ctx.print(Entry);
0239       }
0240     });
0241   }
0242
0243   Printable print(const ContextT &Ctx) const {
0244     return Printable([this, &Ctx](raw_ostream &Out) {
0245       Out << "depth=" << Depth << ": entries(" << printEntries(Ctx) << ')';
0246
0247       for (auto *Block : Blocks) {
0248         if (isEntry(Block))
0249           continue;
0250
0251         Out << ' ' << Ctx.print(Block);
0252       }
0253     });
0254   }
0255 };
0256
0257 /// \brief Cycle information for a function.
0258 template <typename ContextT> class GenericCycleInfo {
0259 public:
0260   using BlockT = typename ContextT::BlockT;
0261   using CycleT = GenericCycle<ContextT>;
0262   using FunctionT = typename ContextT::FunctionT;
0263   template <typename> friend class GenericCycle;
0264   template <typename> friend class GenericCycleInfoCompute;
0265
0266 private:
0267   ContextT Context;
0268
0269   /// Map basic blocks to their inner-most containing cycle.
0270   DenseMap<BlockT *, CycleT *> BlockMap;
0271
0272   /// Map basic blocks to their top level containing cycle.
0273   DenseMap<BlockT *, CycleT *> BlockMapTopLevel;
0274
0275   /// Top-level cycles discovered by any DFS.
0276   ///
0277   /// Note: The implementation treats the nullptr as the parent of
0278   /// every top-level cycle. See \ref contains for an example.
0279   std::vector<std::unique_ptr<CycleT>> TopLevelCycles;
0280
0281   /// Move \p Child to \p NewParent by manipulating Children vectors.
0282   ///
0283   /// Note: This is an incomplete operation that does not update the depth of
0284   /// the subtree.
0285   void moveTopLevelCycleToNewParent(CycleT *NewParent, CycleT *Child);
0286
0287 public:
0288   GenericCycleInfo() = default;
0289   GenericCycleInfo(GenericCycleInfo &&) = default;
0290   GenericCycleInfo &operator=(GenericCycleInfo &&) = default;
0291
0292   void clear();
0293   void compute(FunctionT &F);
0294   void splitCriticalEdge(BlockT *Pred, BlockT *Succ, BlockT *New);
0295
0296   const FunctionT *getFunction() const { return Context.getFunction(); }
0297   const ContextT &getSSAContext() const { return Context; }
0298
0299   CycleT *getCycle(const BlockT *Block) const;
0300   CycleT *getSmallestCommonCycle(CycleT *A, CycleT *B) const;
0301   unsigned getCycleDepth(const BlockT *Block) const;
0302   CycleT *getTopLevelParentCycle(BlockT *Block);
0303
0304   /// Assumes that \p Cycle is the innermost cycle containing \p Block.
0305   /// \p Block will be appended to \p Cycle and all of its parent cycles.
0306   /// \p Block will be added to BlockMap with \p Cycle and
0307   /// BlockMapTopLevel with \p Cycle's top level parent cycle.
0308   void addBlockToCycle(BlockT *Block, CycleT *Cycle);
0309
0310   /// Methods for debug and self-test.
0311   //@{
0312   void verifyCycleNest(bool VerifyFull = false) const;
0313   void verify() const;
0314   void print(raw_ostream &Out) const;
0315   void dump() const { print(dbgs()); }
0316   Printable print(const CycleT *Cycle) { return Cycle->print(Context); }
0317   //@}
0318
0319   /// Iteration over top-level cycles.
0320   //@{
0321   using const_toplevel_iterator_base =
0322       typename std::vector<std::unique_ptr<CycleT>>::const_iterator;
0323   struct const_toplevel_iterator
0324       : iterator_adaptor_base<const_toplevel_iterator,
0325                               const_toplevel_iterator_base> {
0326     using Base = iterator_adaptor_base<const_toplevel_iterator,
0327                                        const_toplevel_iterator_base>;
0328
0329     const_toplevel_iterator() = default;
0330     explicit const_toplevel_iterator(const_toplevel_iterator_base I)
0331         : Base(I) {}
0332
0333     const const_toplevel_iterator_base &wrapped() { return Base::wrapped(); }
0334     CycleT *operator*() const { return Base::I->get(); }
0335   };
0336
0337   const_toplevel_iterator toplevel_begin() const {
0338     return const_toplevel_iterator{TopLevelCycles.begin()};
0339   }
0340   const_toplevel_iterator toplevel_end() const {
0341     return const_toplevel_iterator{TopLevelCycles.end()};
0342   }
0343
0344   iterator_range<const_toplevel_iterator> toplevel_cycles() const {
0345     return llvm::make_range(const_toplevel_iterator{TopLevelCycles.begin()},
0346                             const_toplevel_iterator{TopLevelCycles.end()});
0347   }
0348   //@}
0349 };
0350
0351 /// \brief GraphTraits for iterating over a sub-tree of the CycleT tree.
0352 template <typename CycleRefT, typename ChildIteratorT> struct CycleGraphTraits {
0353   using NodeRef = CycleRefT;
0354
0355   using nodes_iterator = ChildIteratorT;
0356   using ChildIteratorType = nodes_iterator;
0357
0358   static NodeRef getEntryNode(NodeRef Graph) { return Graph; }
0359
0360   static ChildIteratorType child_begin(NodeRef Ref) {
0361     return Ref->child_begin();
0362   }
0363   static ChildIteratorType child_end(NodeRef Ref) { return Ref->child_end(); }
0364
0365   // Not implemented:
0366   // static nodes_iterator nodes_begin(GraphType *G)
0367   // static nodes_iterator nodes_end  (GraphType *G)
0368   //    nodes_iterator/begin/end - Allow iteration over all nodes in the graph
0369
0370   // typedef EdgeRef           - Type of Edge token in the graph, which should
0371   //                             be cheap to copy.
0372   // typedef ChildEdgeIteratorType - Type used to iterate over children edges in
0373   //                             graph, dereference to a EdgeRef.
0374
0375   // static ChildEdgeIteratorType child_edge_begin(NodeRef)
0376   // static ChildEdgeIteratorType child_edge_end(NodeRef)
0377   //     Return iterators that point to the beginning and ending of the
0378   //     edge list for the given callgraph node.
0379   //
0380   // static NodeRef edge_dest(EdgeRef)
0381   //     Return the destination node of an edge.
0382   // static unsigned       size       (GraphType *G)
0383   //    Return total number of nodes in the graph
0384 };
0385
0386 template <typename BlockT>
0387 struct GraphTraits<const GenericCycle<BlockT> *>
0388     : CycleGraphTraits<const GenericCycle<BlockT> *,
0389                        typename GenericCycle<BlockT>::const_child_iterator> {};
0390 template <typename BlockT>
0391 struct GraphTraits<GenericCycle<BlockT> *>
0392     : CycleGraphTraits<GenericCycle<BlockT> *,
0393                        typename GenericCycle<BlockT>::const_child_iterator> {};
0394
0395 } // namespace llvm
0396
0397 #endif // LLVM_ADT_GENERICCYCLEINFO_H