diff --git a/llvm/include/llvm/Analysis/CycleInfo.h b/llvm/include/llvm/Analysis/CycleInfo.h new file mode 100644 --- /dev/null +++ b/llvm/include/llvm/Analysis/CycleInfo.h @@ -0,0 +1,82 @@ +//===- CycleInfo.h - IR Cycle Info ------------------------------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// This file defines the CycleInfo class, which specializes the GenericCycleInfo +// for LLVM IR. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_IR_CYCLEINFO_H +#define LLVM_IR_CYCLEINFO_H + +#include "llvm/IR/CFG.h" +#include "llvm/IR/PassManager.h" +#include "llvm/Support/GenericCycleInfo.h" + +namespace llvm { + +using Cycle = GenericCycle; +using CycleInfo = GenericCycleInfo; + +template <> class ICycleInfoSsaContextMixin { +public: + auto predecessors(BasicBlock *block) const { + return llvm::predecessors(block); + } + auto successors(BasicBlock *block) const { return llvm::successors(block); } +}; + +/// Analysis pass which computes a \ref CycleInfo. +class CycleInfoAnalysis : public AnalysisInfoMixin { + friend AnalysisInfoMixin; + static AnalysisKey Key; + +public: + /// Provide the result typedef for this analysis pass. + using Result = CycleInfo; + + /// Run the analysis pass over a function and produce a dominator tree. + CycleInfo run(Function &F, FunctionAnalysisManager &); + + // TODO: verify analysis? +}; + +/// Printer pass for the \c DominatorTree. +class CycleInfoPrinterPass : public PassInfoMixin { + raw_ostream &OS; + +public: + explicit CycleInfoPrinterPass(raw_ostream &OS); + + PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); +}; + +/// Legacy analysis pass which computes a \ref CycleInfo. +class CycleInfoWrapperPass : public FunctionPass { + Function *m_function = nullptr; + CycleInfo m_cycleInfo; + +public: + static char ID; + + CycleInfoWrapperPass(); + + CycleInfo &getCycleInfo() { return m_cycleInfo; } + const CycleInfo &getCycleInfo() const { return m_cycleInfo; } + + bool runOnFunction(Function &F) override; + void getAnalysisUsage(AnalysisUsage &AU) const override; + void releaseMemory() override; + void print(raw_ostream &OS, const Module *M = nullptr) const override; + + // TODO: verify analysis? +}; + +} // end namespace llvm + +#endif // LLVM_ANALYSIS_CYCLEINFO_H diff --git a/llvm/include/llvm/InitializePasses.h b/llvm/include/llvm/InitializePasses.h --- a/llvm/include/llvm/InitializePasses.h +++ b/llvm/include/llvm/InitializePasses.h @@ -118,6 +118,7 @@ void initializeCorrelatedValuePropagationPass(PassRegistry&); void initializeCostModelAnalysisPass(PassRegistry&); void initializeCrossDSOCFIPass(PassRegistry&); +void initializeCycleInfoWrapperPassPass(PassRegistry&); void initializeDAEPass(PassRegistry&); void initializeDAHPass(PassRegistry&); void initializeDCELegacyPassPass(PassRegistry&); diff --git a/llvm/include/llvm/Support/GenericCycleInfo.h b/llvm/include/llvm/Support/GenericCycleInfo.h new file mode 100644 --- /dev/null +++ b/llvm/include/llvm/Support/GenericCycleInfo.h @@ -0,0 +1,587 @@ +//===- GenericCycleInfo.h - Control Flow Cycle Calculator -----------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +/// \file +/// \brief Find all cycles in a control-flow graph, including irreducible loops. +/// +/// Based on Havlak (1997), Nesting of Reducible and Irreducible Loops. +/// +/// The term "cycle" is chosen to avoid a clash with the existing notion of +/// (natural) "loop". +/// +/// Cycles are defined recursively: +/// 1. The root "cycle" consists of all basic blocks of a function. Its header +/// is the entry block of the function. +/// 2. The cycles nested inside a cycle C with header H are the maximal +/// non-trivial strongly connected components of the (induced) subgraph on +/// (C - H). (Non-trivial means that there must be an actual cycle, i.e. +/// a single basic blocks is only considered a cycle if it has a self-loop.) +/// +/// Note: the C++ representation of the root "cycle" does _not_ contain an +/// explicit list of blocks, to avoid unnecessary memory use. +/// +/// Every cycle has a \em header block, which is the target of a back edge in +/// the DFS tree chosen by the analysis. +/// +/// Every cycle has one or more \em entry blocks, i.e. blocks with incoming +/// arcs from outside the cycle. The header block is the first entry block; +/// there is no order among the non-header entry blocks. +/// +/// Warnings: +/// - Non-header entry blocks of a cycle can be contained in child cycles. +/// - Since the set of back edges depends on choices during a DFS (for +/// irreducible CFGs), there may be edges that "look like" back edges, but +/// whose destination block is not the header block of any cycle. +/// +/// Some interesting properties: +/// - If the CFG is reducible, the cycles are exactly the natural loops and +/// every cycle has exactly one entry block. +/// - Cycles are well-nested (by definition). +/// - The entry blocks of a cycle are siblings in the dominator tree. +/// - The header of every natural loop is the header of some cycle (natural +/// loop back edges are back edges in _every_ choice of DFS tree). This +/// cycle is a superset of the natural loop. +/// +/// Example (irreducible loop that contains natural loops; arcs are pointing +/// down unless indicated otherwise, brackets indicate self-loops): +/// +/// | | +/// />A] [B<\ +/// | \ / | +/// ^---C---^ +/// | +/// +/// The self-loops of A and B give rise to two single-block natural loops. +/// A possible hierarchy of cycles is: +/// - cycle of blocks A, B, C, with A as header and B as additional entry +/// block; containing: +/// -- cycle of blocks B and C, with C as header and B as additional entry +/// block; containing +/// --- singleton cycle of block B +/// This hierarchy arises when DFS visits the blocks in the order A, C, B (in +/// preorder). +/// +/// Example (irreducible loop as union of two natural loops): +/// +/// | | +/// A<->B +/// ^ ^ +/// | | +/// v v +/// C D +/// | | +/// +/// There are two natural loops: A, C and B, D. +/// A possible hierarchy of cycles is: +/// - cycle of blocks A, B, C, D, entry blocks A & B, with header A +/// -- cycle of blocks B, D, entry and header block B +/// +/// Example (irreducible loop with "back edge" not necessarily pointing to a +/// header): +/// +/// | | +/// [A<--B<\ +/// | | +/// C-----^ +/// | +/// +/// The self-loop of A gives rise to a natural loop. +/// One possible cycle analysis is the following hierarchy: +/// - cycle of blocks A, B, C, with A and B as entry blocks and B as header +/// -- singleton cycle of block A +/// Another possible cycle analysis is result is that there is a single cycle +/// of blocks A, B, C, with A and B as entry blocks and A as header. The +/// presumed back edge C->B does not target a cycle header. This analysis +/// result occurs when the DFS visits the blocks in the order A, C, B (in +/// preorder). +/// +/// Example (irreducible loop without any natural loops): +/// +/// | | +/// />A B<\ +/// | |\ /| | +/// | | x | | +/// | |/ \| | +/// ^-C D-^ +/// | | +/// +/// No natural loops, since A, B, C, D are siblings in the dominator tree. +/// A possible hierarchy of cycles is: +/// - cycle of blocks A, B, C, D, entry blocks A & B, with header A +/// -- cycle of blocks B, D, both as entry blocks, and D as header +/// +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_GENERICCYCLEINFO_H +#define LLVM_GENERICCYCLEINFO_H + +#include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/GraphTraits.h" +#include "llvm/ADT/SmallVector.h" +#include "llvm/Support/Debug.h" +#include "llvm/Support/Printable.h" +#include "llvm/Support/SsaContext.h" + +#include +#include + +namespace llvm { + +/// \brief Extended SsaContext interface for use by cycle info +class ICycleInfoSsaContext : public ISsaContext { +public: + virtual void appendPredecessors(BlockHandle block, + SmallVectorImpl &list) const = 0; + virtual void appendSuccessors(BlockHandle block, + SmallVectorImpl &list) const = 0; +}; + +/// \brief Implementation of \ref ICycleInfoSsaContext methods +/// +/// Every IR used with the generic cycle info must provide a specialization of +/// this template. +template class ICycleInfoSsaContextMixin { + // RangeType predecessors(BlockRef block) const; + // RangeType successors(BlockRef block) const; +}; + +template +class ICycleInfoSsaContextImplChain + : public BaseT, + public ICycleInfoSsaContextMixin { +public: + using SsaContext = typename BaseT::SsaContext; + using Wrapper = typename SsaContext::Wrapper; + using BlockRef = typename SsaContext::BlockRef; + +private: + using Mixin = ICycleInfoSsaContextMixin; + +public: + ICycleInfoSsaContextImplChain(BlockRef block) : BaseT(block) {} + + void appendPredecessors(BlockHandle block, + SmallVectorImpl &list) const final { + auto range = Mixin::predecessors(Wrapper::unwrapRef(block)); + list.insert(list.end(), Wrapper::wrapIterator(adl_begin(range)), + Wrapper::wrapIterator(adl_end(range))); + } + void appendSuccessors(BlockHandle block, + SmallVectorImpl &list) const final { + auto range = Mixin::successors(Wrapper::unwrapRef(block)); + list.insert(list.end(), Wrapper::wrapIterator(adl_begin(range)), + Wrapper::wrapIterator(adl_end(range))); + } +}; + +template +using ICycleInfoSsaContextImpl = + ICycleInfoSsaContextImplChain>; + +template +using ICycleInfoSsaContextFor = + ICycleInfoSsaContextImpl>; + +/// \brief Type-erased base class for a cycle of basic blocks. +class GenericCycleBase { + friend class GenericCycleInfoBase; + +protected: + /// The parent cycle. Is null for the root "cycle". Top-level cycles point + /// at the root. + GenericCycleBase *m_parent = nullptr; + + /// The entry block(s) of the cycle. The first entry is the header. + SmallVector m_entries; + + /// Child cycles, if any. + std::vector> m_children; + + /// Basic blocks that are contained in the cycle, including entry blocks, + /// and including blocks that are part of a child cycle. + std::vector m_blocks; + + /// Depth of the cycle in the tree. The root "cycle" is at depth 0. + /// + /// \note Depths are not necessarily contiguous. However, child loops always + /// have strictly greater depth than their parents, and sibling loops + /// always have the same depth. + unsigned m_depth = 0; + + GenericCycleBase(const GenericCycleBase &) = delete; + GenericCycleBase &operator=(const GenericCycleBase &) = delete; + GenericCycleBase(GenericCycleBase &&rhs) = delete; + GenericCycleBase &operator=(GenericCycleBase &&rhs) = delete; + +public: + GenericCycleBase() = default; + + bool isRoot() const { return !m_parent; } + + /// \brief Whether the cycle is a natural loop. + bool isNaturalLoop() const { return !isRoot() && m_entries.size() == 1; } + + BlockHandle getHeader() const { return m_entries[0]; } + + /// \brief Return whether \p block is an entry block of the cycle. + bool isEntry(BlockHandle block) const { + return is_contained(m_entries, block); + } + + /// \brief Return whether \p block is contained in the cycle. + bool containsBlock(BlockHandle block) const { + return is_contained(m_blocks, block); + } + + const GenericCycleBase *getParent() const { return m_parent; } + GenericCycleBase *getParent() { return m_parent; } + uint getDepth() const { return m_depth; } + + Printable printEntries(const ISsaContext &ctx) const; + Printable print(const ISsaContext &ctx) const; + + /// Iteration over child cycles. + //@{ + using const_child_iterator_base = + std::vector>::const_iterator; + struct const_child_iterator + : iterator_adaptor_base { + using Base = + iterator_adaptor_base; + + const_child_iterator() = default; + explicit const_child_iterator(const_child_iterator_base I) : Base(I) {} + + GenericCycleBase *operator*() const { return I->get(); } + }; + + const_child_iterator children_begin() const { + return const_child_iterator{m_children.begin()}; + } + const_child_iterator children_end() const { + return const_child_iterator{m_children.end()}; + } + size_t children_size() const { return m_children.size(); } + iterator_range children() const { + return llvm::make_range(const_child_iterator{m_children.begin()}, + const_child_iterator{m_children.end()}); + } + //@} + + /// Iteration over blocks in the cycle (including entry blocks). + //@{ + using const_blockref_iterator = std::vector::const_iterator; + + size_t blocks_size() const { return m_blocks.size(); } + iterator_range blocks() const { + return llvm::make_range(m_blocks.begin(), m_blocks.end()); + } + //@} + + /// Iteration over entry blocks. + //@{ + using const_entry_iterator = SmallVectorImpl::const_iterator; + + size_t entries_size() const { return m_entries.size(); } + iterator_range entries() const { + return llvm::make_range(m_entries.begin(), m_entries.end()); + } + //@} +}; + +/// \brief A cycle of basic blocks and child cycles. +template class GenericCycle : public GenericCycleBase { +public: + using SsaContext = SsaContextT; + using Wrapper = typename SsaContext::Wrapper; + using Self = GenericCycle; + using BlockRef = typename SsaContextT::BlockRef; + + bool isEntry(BlockRef block) const { + return GenericCycleBase::isEntry(Wrapper::wrapRef(block)); + } + BlockRef getHeader() const { + return Wrapper::unwrapRef(GenericCycleBase::getHeader()); + } + bool containsBlock(BlockRef block) const { + return GenericCycleBase::containsBlock(Wrapper::wrapRef(block)); + } + + const GenericCycle *getParent() const { + return static_cast(m_parent); + } + GenericCycle *getParent() { return static_cast(m_parent); } + + Printable printEntries() const { + return Printable([this](raw_ostream &out) { + ISsaContextImpl iface(getHeader()); + out << GenericCycleBase::printEntries(iface); + }); + } + Printable print() const { + return Printable([this](raw_ostream &out) { + ISsaContextImpl iface(getHeader()); + out << GenericCycleBase::print(iface); + }); + } + void dump() const { dbgs() << print(); } + + using const_child_iterator_base = GenericCycleBase::const_child_iterator_base; + struct const_child_iterator + : iterator_adaptor_base { + using Base = + iterator_adaptor_base; + + const_child_iterator() = default; + explicit const_child_iterator(const_child_iterator_base I) : Base(I) {} + + Self *operator*() const { return static_cast(this->I->get()); } + }; + + const_child_iterator children_begin() const { + return const_child_iterator{m_children.begin()}; + } + const_child_iterator children_end() const { + return const_child_iterator{m_children.end()}; + } + iterator_range children() const { + return llvm::make_range(children_begin(), children_end()); + } + + auto entries() const { return SsaContext::unwrapRange(m_entries); } + auto blocks() const { return SsaContext::unwrapRange(m_blocks); } +}; + +/// \brief Type-erased cycle information for a function. +class GenericCycleInfoBase { +protected: + /// Root "cycle". + /// + /// A cycle structure is used here primarily to simplify the \ref GraphTraits + /// implementation and related iteration. Only the cycle children and entrance + /// member is filled in, the blocks member remains empty. + /// + /// Top-level cycles link back to the root as their parent. + /// + /// A dynamic allocation is used here to allow GenericCycleInfo to be moved + /// without invalidating any cycle pointers. + std::unique_ptr m_root; + + /// Map basic blocks to their inner-most containing loop. + DenseMap m_blockMap; + +public: + GenericCycleInfoBase(); + ~GenericCycleInfoBase(); + GenericCycleInfoBase(GenericCycleInfoBase &&) = default; + GenericCycleInfoBase &operator=(GenericCycleInfoBase &&) = default; + + void reset(); + + void compute(const ICycleInfoSsaContext &iface, BlockHandle entryBlock); + + /// Methods for updating the cycle info. + //@{ + void splitBlock(BlockHandle oldBlock, BlockHandle newBlock); + void extendCycle(const ICycleInfoSsaContext &iface, + GenericCycleBase *cycleToExtend, BlockHandle toBlock, + SmallVectorImpl *transferredBlocks = nullptr); + void flattenCycles(GenericCycleBase *inner, GenericCycleBase *outer); + //@} + + /// \brief Return the root "cycle", which contains all the top-level cycles + /// as children. + GenericCycleBase *getRoot() { return m_root.get(); } + const GenericCycleBase *getRoot() const { return m_root.get(); } + + GenericCycleBase *getCycle(BlockHandle block); + const GenericCycleBase *getCycle(BlockHandle block) const { + return const_cast(this)->getCycle(block); + } + bool contains(const GenericCycleBase *a, const GenericCycleBase *b) const; + GenericCycleBase *findSmallestCommonCycle(const GenericCycleBase *a, + const GenericCycleBase *b); + const GenericCycleBase * + findSmallestCommonCycle(const GenericCycleBase *a, + const GenericCycleBase *b) const { + return const_cast(this)->findSmallestCommonCycle(a, + b); + }; + GenericCycleBase *findLargestDisjointAncestor(const GenericCycleBase *a, + const GenericCycleBase *b); + const GenericCycleBase * + findLargestDisjointAncestor(const GenericCycleBase *a, + const GenericCycleBase *b) const { + return const_cast(this) + ->findLargestDisjointAncestor(a, b); + } + + ArrayRef + findExitBlocks(const ICycleInfoSsaContext &iface, + const GenericCycleBase *cycle, + SmallVectorImpl &tmpStorage) const; + + /// Methods for debug and self-test. + //@{ + bool validateTree() const; + void print(const ISsaContext &ctx, raw_ostream &out) const; + void dump(const ISsaContext &ctx) const { print(ctx, dbgs()); } + //@} + +private: + // Helper classes used by the cycle info computation. + class ContractedDomSubTree; + class Compute; + + friend struct GraphTraits; + friend struct DenseMapInfo; +}; + +/// \brief Cycle information for a function. +template +class GenericCycleInfo : public GenericCycleInfoBase { +public: + using SsaContext = SsaContextT; + using Wrapper = typename SsaContext::Wrapper; + using BlockRef = typename SsaContext::BlockRef; + using Cycle = GenericCycle; + + void compute(BlockRef entryBlock) { + GenericCycleInfoBase::compute( + ICycleInfoSsaContextImpl(entryBlock), + Wrapper::wrapRef(entryBlock)); + } + + void splitBlock(BlockRef oldBlock, BlockRef newBlock) { + GenericCycleInfoBase::splitBlock(Wrapper::wrapRef(oldBlock), + Wrapper::wrapRef(newBlock)); + } + + void extendCycle(Cycle *cycleToExtend, BlockRef toBlock) { + GenericCycleInfoBase::extendCycle( + ICycleInfoSsaContextImpl(toBlock), cycleToExtend, + Wrapper::wrapRef(toBlock)); + } + + void flattenCycles(Cycle *inner, Cycle *outer) { + GenericCycleInfoBase::flattenCycles(inner, outer); + } + + Cycle *getRoot() { return static_cast(m_root.get()); } + const Cycle *getRoot() const { + return static_cast(m_root.get()); + } + + Cycle *getCycle(BlockRef block) { + return static_cast( + GenericCycleInfoBase::getCycle(Wrapper::wrapRef(block))); + } + const Cycle *getCycle(BlockRef block) const { + return static_cast( + GenericCycleInfoBase::getCycle(Wrapper::wrapRef(block))); + } + + bool contains(const Cycle *a, const Cycle *b) const { + return GenericCycleInfoBase::contains(a, b); + } + + Cycle *findSmallestCommonCycle(const Cycle *a, const Cycle *b) { + return static_cast( + GenericCycleInfoBase::findSmallestCommonCycle(a, b)); + } + const Cycle *findSmallestCommonCycle(const Cycle *a, const Cycle *b) const { + return static_cast( + GenericCycleInfoBase::findSmallestCommonCycle(a, b)); + } + + Cycle *findLargestDisjointAncestor(const Cycle *a, const Cycle *b) { + return static_cast( + GenericCycleInfoBase::findLargestDisjointAncestor(a, b)); + } + const Cycle *findLargestDisjointAncestor(const Cycle *a, + const Cycle *b) const { + return static_cast( + GenericCycleInfoBase::findLargestDisjointAncestor(a, b)); + } + + auto findExitBlocks(const Cycle *cycle, + SmallVectorImpl &tmpStorage) const { + return SsaContext::unwrapRange(GenericCycleInfoBase::findExitBlocks( + ICycleInfoSsaContextImpl(cycle->getHeader()), cycle, + tmpStorage)); + } + + void print(raw_ostream &out) const { + ISsaContextFor iface(getRoot()->getHeader()); + GenericCycleInfoBase::print(iface, out); + } + LLVM_DUMP_METHOD + void dump() const { print(dbgs()); } +}; + +/// \brief GraphTraits for iterating over a sub-tree of the Cycle tree. +template +struct GenericCycleGraphTraits { + using NodeRef = CycleRefT; + + using nodes_iterator = ChildIteratorT; + using ChildIteratorType = nodes_iterator; + + static NodeRef getEntryNode(NodeRef graph) { return graph; } + + static ChildIteratorType child_begin(NodeRef ref) { + return ref->children_begin(); + } + static ChildIteratorType child_end(NodeRef ref) { + return ref->children_end(); + } + + // Not implemented: + // static nodes_iterator nodes_begin(GraphType *G) + // static nodes_iterator nodes_end (GraphType *G) + // nodes_iterator/begin/end - Allow iteration over all nodes in the graph + + // typedef EdgeRef - Type of Edge token in the graph, which should + // be cheap to copy. + // typedef ChildEdgeIteratorType - Type used to iterate over children edges in + // graph, dereference to a EdgeRef. + + // static ChildEdgeIteratorType child_edge_begin(NodeRef) + // static ChildEdgeIteratorType child_edge_end(NodeRef) + // Return iterators that point to the beginning and ending of the + // edge list for the given callgraph node. + // + // static NodeRef edge_dest(EdgeRef) + // Return the destination node of an edge. + // static unsigned size (GraphType *G) + // Return total number of nodes in the graph +}; + +template <> +struct GraphTraits + : GenericCycleGraphTraits {}; +template <> +struct GraphTraits + : GenericCycleGraphTraits {}; +template +struct GraphTraits *> + : GenericCycleGraphTraits< + const GenericCycle *, + typename GenericCycle::const_child_iterator> {}; +template +struct GraphTraits *> + : GenericCycleGraphTraits< + GenericCycle *, + typename GenericCycle::const_child_iterator> {}; + +} // namespace llvm + +#endif // LLVM_GENERICCYCLEINFO_H diff --git a/llvm/lib/Analysis/Analysis.cpp b/llvm/lib/Analysis/Analysis.cpp --- a/llvm/lib/Analysis/Analysis.cpp +++ b/llvm/lib/Analysis/Analysis.cpp @@ -35,6 +35,7 @@ initializeCFGOnlyPrinterLegacyPassPass(Registry); initializeCFLAndersAAWrapperPassPass(Registry); initializeCFLSteensAAWrapperPassPass(Registry); + initializeCycleInfoWrapperPassPass(Registry); initializeDependenceAnalysisWrapperPassPass(Registry); initializeDelinearizationPass(Registry); initializeDemandedBitsWrapperPassPass(Registry); diff --git a/llvm/lib/Analysis/CMakeLists.txt b/llvm/lib/Analysis/CMakeLists.txt --- a/llvm/lib/Analysis/CMakeLists.txt +++ b/llvm/lib/Analysis/CMakeLists.txt @@ -38,6 +38,7 @@ CostModel.cpp CodeMetrics.cpp ConstantFolding.cpp + CycleInfo.cpp DDG.cpp ConstraintSystem.cpp Delinearization.cpp diff --git a/llvm/lib/Analysis/CycleInfo.cpp b/llvm/lib/Analysis/CycleInfo.cpp new file mode 100644 --- /dev/null +++ b/llvm/lib/Analysis/CycleInfo.cpp @@ -0,0 +1,78 @@ +//===- CycleInfo.cpp - IR Cycle Info ----------------------------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#include "llvm/Analysis/CycleInfo.h" +#include "llvm/IR/ModuleSlotTracker.h" + +#include "llvm/InitializePasses.h" + +using namespace llvm; + +//===----------------------------------------------------------------------===// +// CycleInfoAnalysis and related pass implementations +//===----------------------------------------------------------------------===// + +CycleInfo CycleInfoAnalysis::run(Function &F, FunctionAnalysisManager &) { + CycleInfo cycleInfo; + cycleInfo.compute(&F.getEntryBlock()); + return cycleInfo; +} + +AnalysisKey CycleInfoAnalysis::Key; + +CycleInfoPrinterPass::CycleInfoPrinterPass(raw_ostream &OS) : OS(OS) {} + +PreservedAnalyses CycleInfoPrinterPass::run(Function &F, + FunctionAnalysisManager &AM) { + OS << "CycleInfo for function: " << F.getName() << "\n"; + AM.getResult(F).print(OS); + + return PreservedAnalyses::all(); +} + +//===----------------------------------------------------------------------===// +// CycleInfoWrapperPass Implementation +//===----------------------------------------------------------------------===// +// +// The implementation details of the wrapper pass that holds a CycleInfo +// suitable for use with the legacy pass manager. +// +//===----------------------------------------------------------------------===// + +char CycleInfoWrapperPass::ID = 0; + +CycleInfoWrapperPass::CycleInfoWrapperPass() : FunctionPass(ID) { + initializeCycleInfoWrapperPassPass(*PassRegistry::getPassRegistry()); +} + +INITIALIZE_PASS_BEGIN(CycleInfoWrapperPass, "cycleinfo", "Cycle Info Analysis", + true, true) +INITIALIZE_PASS_END(CycleInfoWrapperPass, "cycleinfo", "Cycle Info Analysis", + true, true) + +void CycleInfoWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const { + AU.setPreservesAll(); +} + +bool CycleInfoWrapperPass::runOnFunction(Function &F) { + m_cycleInfo.reset(); + + m_function = &F; + m_cycleInfo.compute(&F.getEntryBlock()); + return false; +} + +void CycleInfoWrapperPass::print(raw_ostream &OS, const Module *) const { + OS << "CycleInfo for function: " << m_function->getName() << "\n"; + m_cycleInfo.print(OS); +} + +void CycleInfoWrapperPass::releaseMemory() { + m_cycleInfo.reset(); + m_function = nullptr; +} diff --git a/llvm/lib/Passes/PassBuilder.cpp b/llvm/lib/Passes/PassBuilder.cpp --- a/llvm/lib/Passes/PassBuilder.cpp +++ b/llvm/lib/Passes/PassBuilder.cpp @@ -28,6 +28,7 @@ #include "llvm/Analysis/CFLSteensAliasAnalysis.h" #include "llvm/Analysis/CGSCCPassManager.h" #include "llvm/Analysis/CallGraph.h" +#include "llvm/Analysis/CycleInfo.h" #include "llvm/Analysis/DDG.h" #include "llvm/Analysis/Delinearization.h" #include "llvm/Analysis/DemandedBits.h" diff --git a/llvm/lib/Passes/PassRegistry.def b/llvm/lib/Passes/PassRegistry.def --- a/llvm/lib/Passes/PassRegistry.def +++ b/llvm/lib/Passes/PassRegistry.def @@ -144,6 +144,7 @@ FUNCTION_ANALYSIS("assumptions", AssumptionAnalysis()) FUNCTION_ANALYSIS("block-freq", BlockFrequencyAnalysis()) FUNCTION_ANALYSIS("branch-prob", BranchProbabilityAnalysis()) +FUNCTION_ANALYSIS("cycleinfo", CycleInfoAnalysis()) FUNCTION_ANALYSIS("domtree", DominatorTreeAnalysis()) FUNCTION_ANALYSIS("postdomtree", PostDominatorTreeAnalysis()) FUNCTION_ANALYSIS("demanded-bits", DemandedBitsAnalysis()) @@ -261,6 +262,7 @@ FUNCTION_PASS("print", BlockFrequencyPrinterPass(dbgs())) FUNCTION_PASS("print", BranchProbabilityPrinterPass(dbgs())) FUNCTION_PASS("print", DependenceAnalysisPrinterPass(dbgs())) +FUNCTION_PASS("print", CycleInfoPrinterPass(dbgs())) FUNCTION_PASS("print", DominatorTreePrinterPass(dbgs())) FUNCTION_PASS("print", PostDominatorTreePrinterPass(dbgs())) FUNCTION_PASS("print", DelinearizationPrinterPass(dbgs())) diff --git a/llvm/lib/Support/CMakeLists.txt b/llvm/lib/Support/CMakeLists.txt --- a/llvm/lib/Support/CMakeLists.txt +++ b/llvm/lib/Support/CMakeLists.txt @@ -124,6 +124,7 @@ FoldingSet.cpp FormattedStream.cpp FormatVariadic.cpp + GenericCycleInfo.cpp GenericDomTree.cpp GlobPattern.cpp GraphWriter.cpp diff --git a/llvm/lib/Support/GenericCycleInfo.cpp b/llvm/lib/Support/GenericCycleInfo.cpp new file mode 100644 --- /dev/null +++ b/llvm/lib/Support/GenericCycleInfo.cpp @@ -0,0 +1,573 @@ +//===- GenericCycleInfo.cpp - Control Flow Cycle Calculator ---------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#include "llvm/Support/GenericCycleInfo.h" + +#include "llvm/ADT/DenseSet.h" +#include "llvm/ADT/DepthFirstIterator.h" +#include "llvm/ADT/PostOrderIterator.h" +#include "llvm/ADT/SCCIterator.h" +#include "llvm/Support/raw_ostream.h" + +using namespace llvm; + +/// \brief Helper class for computing the machine cycle information. +class GenericCycleInfoBase::Compute { + GenericCycleInfoBase &m_info; + const ICycleInfoSsaContext &m_iface; + + struct DfsInfo { + unsigned start = 0; // DFS start; positive if block is found + unsigned end = 0; // DFS end + + DfsInfo() {} + explicit DfsInfo(unsigned start) : start(start) {} + + /// Whether this node is an ancestor (or equal to) the node \p other + /// in the DFS tree. + bool isAncestorOf(const DfsInfo &other) const { + return start <= other.start && other.end <= end; + } + }; + + DenseMap m_blockDfsInfo; + SmallVector m_blockPreorder; + + friend struct GraphTraits; + + Compute(const Compute &) = delete; + Compute &operator=(const Compute &) = delete; + +public: + Compute(GenericCycleInfoBase &info, const ICycleInfoSsaContext &iface) + : m_info(info), m_iface(iface) {} + + void run(BlockHandle entryBlock); + + static void updateDepth(GenericCycleBase *subTree); + +private: + void dfs(BlockHandle entryBlock); +}; + +/// \brief Main function of the cycle info computations. +void GenericCycleInfoBase::Compute::run(BlockHandle entryBlock) { + assert(m_info.m_root->m_entries.empty()); + m_info.m_root->m_entries.push_back(entryBlock); + + dfs(entryBlock); + + SmallVector tmpPredecessors; + SmallVector worklist; + + for (BlockHandle headerCandidate : llvm::reverse(m_blockPreorder)) { + const DfsInfo blockDfsInfo = m_blockDfsInfo.lookup(headerCandidate); + + m_iface.appendPredecessors(headerCandidate, tmpPredecessors); + for (BlockHandle pred : tmpPredecessors) { + const DfsInfo predDfsInfo = m_blockDfsInfo.lookup(pred); + if (blockDfsInfo.isAncestorOf(predDfsInfo)) + worklist.push_back(pred); + } + tmpPredecessors.clear(); + if (worklist.empty()) + continue; + + // Found a cycle with the candidate as its header. + std::unique_ptr cycle = + std::make_unique(); + cycle->m_entries.push_back(headerCandidate); + cycle->m_blocks.push_back(headerCandidate); + m_info.m_blockMap.try_emplace(headerCandidate, cycle.get()); + + // Helper function to process (non-back-edge) predecessors of a discovered + // block and either add them to the worklist or recognize that the given + // block is an additional cycle entry. + auto processPredecessors = [&](BlockHandle block) { + bool isEntry = false; + m_iface.appendPredecessors(block, tmpPredecessors); + for (BlockHandle pred : tmpPredecessors) { + const DfsInfo predDfsInfo = m_blockDfsInfo.lookup(pred); + if (blockDfsInfo.isAncestorOf(predDfsInfo)) { + worklist.push_back(pred); + } else { + isEntry = true; + } + } + tmpPredecessors.clear(); + if (isEntry) { + assert(!is_contained(cycle->m_entries, block)); + cycle->m_entries.push_back(block); + } + }; + + do { + BlockHandle block = worklist.pop_back_val(); + if (block == headerCandidate) + continue; + + auto mapIt = m_info.m_blockMap.find(block); + if (mapIt != m_info.m_blockMap.end()) { + // The block has already been discovered by some cycle (possibly by + // ourself). Its outer-most discovered ancestor becomes our child if + // that hasn't happened yet. + GenericCycleBase *child = mapIt->second; + while (child->m_parent) + child = child->m_parent; + if (child != cycle.get()) { + auto rootIt = llvm::find_if( + m_info.m_root->m_children, + [=](const auto &ptr) -> bool { return child == ptr.get(); }); + assert(rootIt != m_info.m_root->m_children.end()); + cycle->m_children.push_back(std::move(*rootIt)); + *rootIt = std::move(m_info.m_root->m_children.back()); + m_info.m_root->m_children.pop_back(); + + child->m_parent = cycle.get(); + + cycle->m_blocks.insert(cycle->m_blocks.end(), child->m_blocks.begin(), + child->m_blocks.end()); + + for (BlockHandle childEntry : child->entries()) + processPredecessors(childEntry); + } + } else { + m_info.m_blockMap.try_emplace(block, cycle.get()); + assert(!is_contained(cycle->m_blocks, block)); + cycle->m_blocks.push_back(block); + processPredecessors(block); + } + } while (!worklist.empty()); + + m_info.m_root->m_children.push_back(std::move(cycle)); + } + + // Fix top-level cycle links and compute cycle depths. + for (GenericCycleBase *topLevelCycle : m_info.m_root->children()) { + topLevelCycle->m_parent = m_info.m_root.get(); + updateDepth(topLevelCycle); + } +} + +/// \brief Recompute depth values of \p subTree and all descendants. +void GenericCycleInfoBase::Compute::updateDepth(GenericCycleBase *subTree) { + for (GenericCycleBase *cycle : depth_first(subTree)) + cycle->m_depth = cycle->m_parent->m_depth + 1; +} + +/// \brief Compute a DFS of basic blocks starting at the function entry. +/// +/// Fills m_blockDfsInfo with start/end counters and m_blockPreorder. +void GenericCycleInfoBase::Compute::dfs(BlockHandle entryBlock) { + SmallVector dfsTreeStack; + SmallVector traverseStack; + unsigned counter = 0; + traverseStack.emplace_back(entryBlock); + + do { + BlockHandle block = traverseStack.back(); + if (!m_blockDfsInfo.count(block)) { + // We're visiting the block for the first time. Open its DfsInfo, add + // successors to the traversal stack, and remember the traversal stack + // depth at which the block was opened, so that we can correctly record + // its end time. + dfsTreeStack.emplace_back(traverseStack.size()); + m_iface.appendSuccessors(block, traverseStack); + + LLVM_ATTRIBUTE_UNUSED + bool added = m_blockDfsInfo.try_emplace(block, ++counter).second; + assert(added); + m_blockPreorder.push_back(block); + } else { + assert(!dfsTreeStack.empty()); + if (dfsTreeStack.back() == traverseStack.size()) { + m_blockDfsInfo.find(block)->second.end = ++counter; + dfsTreeStack.pop_back(); + } + traverseStack.pop_back(); + } + } while (!traverseStack.empty()); + assert(dfsTreeStack.empty()); +} + +/// \brief Return printable with space-separated cycle entry blocks. +Printable GenericCycleBase::printEntries(const ISsaContext &ctx) const { + return Printable([this, &ctx](raw_ostream &out) { + bool first = true; + for (BlockHandle entry : m_entries) { + if (!first) + out << ' '; + first = false; + out << ctx.printableName(entry); + } + }); +} + +/// \brief Return printable representation of the cycle. +Printable GenericCycleBase::print(const ISsaContext &ctx) const { + return Printable([this, &ctx](raw_ostream &out) { + out << "depth=" << m_depth << ": entries(" << printEntries(ctx) << ')'; + + for (BlockHandle block : m_blocks) { + if (isEntry(block)) + continue; + + out << ' ' << ctx.printableName(block); + } + }); +} + +GenericCycleInfoBase::GenericCycleInfoBase() + : m_root(std::make_unique()) {} +GenericCycleInfoBase::~GenericCycleInfoBase() {} + +/// \brief Reset the object to its initial state. +void GenericCycleInfoBase::reset() { + m_root->m_entries.clear(); // remove entry block + m_root->m_children.clear(); + m_blockMap.clear(); +} + +/// \brief Compute the cycle info for a function. +void GenericCycleInfoBase::compute(const ICycleInfoSsaContext &iface, + BlockHandle entryBlock) { + Compute compute(*this, iface); + compute.run(entryBlock); + + assert(validateTree()); +} + +/// \brief Update the cycle info after splitting a basic block. +/// +/// Notify the cycle info that \p oldBlock was split, with \p newBlock as its +/// new unique successor. All original successors of \p oldBlock are now +/// successors of \p newBlock. +void GenericCycleInfoBase::splitBlock(BlockHandle oldBlock, + BlockHandle newBlock) { + GenericCycleBase *cycle = getCycle(oldBlock); + if (cycle != getRoot()) { + cycle->m_blocks.push_back(newBlock); + m_blockMap[newBlock] = cycle; + } +} + +/// \brief Extend a cycle minimally such that it contains all predecessors of a +/// given block. +/// +/// The cycle structure is updated such that all predecessors of \p toBlock will +/// be contained (possibly indirectly) in \p cycleToExtend, without removing any +/// cycles: if \p toBlock is not contained in an ancestor of \p cycle, it and +/// its ancestors will be moved into \p cycleToExtend, as will cousin cycles +/// that are encountered while following control flow backwards from \p toBlock. +/// +/// If \p transferredBlocks is non-null, all blocks whose direct containing +/// cycle was changed are appended to the vector. +void GenericCycleInfoBase::extendCycle( + const ICycleInfoSsaContext &iface, GenericCycleBase *cycleToExtend, + BlockHandle toBlock, SmallVectorImpl *transferredBlocks) { + SmallVector workList; + iface.appendPredecessors(toBlock, workList); + + while (!workList.empty()) { + BlockHandle block = workList.pop_back_val(); + GenericCycleBase *cycle = getCycle(block); + if (contains(cycleToExtend, cycle)) + continue; + + GenericCycleBase *cycleToInclude = + findLargestDisjointAncestor(cycle, cycleToExtend); + if (cycleToInclude) { + GenericCycleBase *oldCommonAncestor = cycleToInclude->getParent(); + + // Move cycle into cycleToExtend. + auto childIt = llvm::find_if( + cycleToInclude->m_parent->m_children, + [=](const auto &ptr) -> bool { return cycleToInclude == ptr.get(); }); + assert(childIt != cycleToInclude->m_parent->m_children.end()); + cycleToExtend->m_children.push_back(std::move(*childIt)); + *childIt = std::move(cycleToInclude->m_parent->m_children.back()); + cycleToInclude->m_parent->m_children.pop_back(); + cycleToInclude->m_parent = cycleToExtend; + + assert(cycleToInclude->m_depth <= cycleToExtend->m_depth); + Compute::updateDepth(cycleToInclude); + + GenericCycleBase *newCommonAncestor = cycleToExtend; + do { + newCommonAncestor->m_blocks.insert(newCommonAncestor->m_blocks.end(), + cycleToInclude->m_blocks.begin(), + cycleToInclude->m_blocks.end()); + newCommonAncestor = newCommonAncestor->getParent(); + } while (newCommonAncestor != oldCommonAncestor); + + // Continue from the entries of the newly included cycle. + for (BlockHandle entry : cycleToInclude->m_entries) + iface.appendPredecessors(entry, workList); + } else { + // Block is contained in an ancestor of cycleToExtend, just add it + // to the cycle and proceed. + m_blockMap[block] = cycleToExtend; + if (transferredBlocks) + transferredBlocks->push_back(block); + + GenericCycleBase *ancestor = cycleToExtend; + do { + ancestor->m_blocks.push_back(block); + ancestor = ancestor->getParent(); + } while (ancestor != cycle); + + iface.appendPredecessors(block, workList); + } + } + + assert(validateTree()); +} + +/// \brief Flatten the cycle hierarchy such that \p inner is folded into +/// \p outer. +/// +/// \p outer must be a strict ancestor of \p inner. +/// +/// Example change to the cycle hierarchy: +/// +/// outer outer +/// / | / | \ +/// C1 * C1 C2 C3 +/// / \ => +/// C2 \ +/// inner +/// | +/// C3 +/// +void GenericCycleInfoBase::flattenCycles(GenericCycleBase *inner, + GenericCycleBase *outer) { + assert(outer != inner && contains(outer, inner)); + + // Re-assign blocks. + for (BlockHandle block : outer->m_blocks) { + auto it = m_blockMap.find(block); + GenericCycleBase *cycle = inner; + do { + if (cycle == it->second) { + it->second = outer; + break; + } + cycle = cycle->getParent(); + } while (cycle != outer); + } + + // Flatten the cycle hierarchy. + do { + // Remove the inner cycle from its direct parent. + GenericCycleBase *parent = inner->m_parent; + + auto it = llvm::find_if(parent->m_children, [=](const auto &child) { + return child.get() == inner; + }); + assert(it != parent->m_children.end()); + + std::unique_ptr innerPtr = std::move(*it); + parent->m_children.erase(it); + + // Move the inner cycle's direct children to the outer cycle. + for (auto &childPtr : inner->m_children) { + childPtr->m_parent = inner->m_parent; + outer->m_children.emplace_back(std::move(childPtr)); + } + + inner = inner->getParent(); + } while (inner != outer); + + assert(validateTree()); +} + +/// \brief Returns true iff \p a contains \p b. +/// +/// Note: Non-strict containment check, i.e. return true if a == b. +bool GenericCycleInfoBase::contains(const GenericCycleBase *a, + const GenericCycleBase *b) const { + if (a->m_depth > b->m_depth) + return false; + while (a->m_depth < b->m_depth) + b = b->m_parent; + return a == b; +} + +/// \brief Find the innermost cycle containing a given block. +/// +/// \returns the innermost cycle containing \p block or the root "cycle" if +/// is not contained in any cycle. +GenericCycleBase *GenericCycleInfoBase::getCycle(BlockHandle block) { + auto mapIt = m_blockMap.find(block); + if (mapIt != m_blockMap.end()) + return mapIt->second; + return m_root.get(); +} + +/// \brief Find the smallest cycle containing both \p a and \p b. +GenericCycleBase * +GenericCycleInfoBase::findSmallestCommonCycle(const GenericCycleBase *a, + const GenericCycleBase *b) { + if (a != b) { + for (;;) { + while (a->m_depth > b->m_depth) + a = a->m_parent; + while (a->m_depth < b->m_depth) + b = b->m_parent; + if (a == b) + break; + b = b->m_parent; + a = a->m_parent; + } + } + // const_cast is justified since cycles are owned by this object, which is + // non-const. + return const_cast(a); +} + +/// \brief Finds the largest ancestor of \p a that is disjoint from \b. +/// +/// The caller must ensure that \p b does not contain \p a. If \p a +/// contains \p b, null is returned. +GenericCycleBase * +GenericCycleInfoBase::findLargestDisjointAncestor(const GenericCycleBase *a, + const GenericCycleBase *b) { + while (a->m_depth < b->m_depth) + b = b->m_parent; + if (a == b) + return nullptr; + + for (;;) { + while (a->m_depth > b->m_depth) + a = a->m_parent; + while (a->m_depth < b->m_depth) + b = b->m_parent; + if (a->m_parent == b->m_parent) + break; + a = a->m_parent; + b = b->m_parent; + } + // const_cast is justified since cycles are owned by this object, which is + // non-const. + return const_cast(a); +} + +/// \brief Find (compute) the exit blocks of a given cycle +/// +/// Find the blocks outside the cycle with incoming edges from the cycle. +/// +/// The returned array reference remains valid as long as \p tmpStorage +/// remains unmodified. +ArrayRef GenericCycleInfoBase::findExitBlocks( + const ICycleInfoSsaContext &iface, const GenericCycleBase *cycle, + SmallVectorImpl &tmpStorage) const { + tmpStorage.clear(); + + size_t numExitBlocks = 0; + for (BlockHandle block : cycle->blocks()) { + iface.appendSuccessors(block, tmpStorage); + + for (size_t idx = numExitBlocks, end = tmpStorage.size(); idx < end; + ++idx) { + BlockHandle succ = tmpStorage[idx]; + if (!contains(cycle, getCycle(succ))) { + auto exitEndIt = tmpStorage.begin() + numExitBlocks; + if (std::find(tmpStorage.begin(), exitEndIt, succ) == exitEndIt) + tmpStorage[numExitBlocks++] = succ; + } + } + + tmpStorage.resize(numExitBlocks); + } + + return tmpStorage; +} + +/// \brief Validate the internal consistency of the cycle tree. +/// +/// Note that this does \em not check that cycles are really cycles in the CFG, +/// or that the right set of cycles in the CFG were found. +bool GenericCycleInfoBase::validateTree() const { + DenseSet blocks; + DenseSet entries; + + auto reportError = [](const char *file, int line, const char *cond) { + errs() << file << ':' << line + << ": GenericCycleInfoBase::validateTree: " << cond << '\n'; + }; +#define check(cond) \ + do { \ + if (!(cond)) { \ + reportError(__FILE__, __LINE__, #cond); \ + return false; \ + } \ + } while (false) + + for (const GenericCycleBase *cycle : depth_first(getRoot())) { + if (!cycle->m_parent) { + check(cycle == getRoot()); + check(cycle->m_entries.size() == 1); + check(cycle->m_blocks.empty()); // root cycle is "empty" by convention + check(cycle->m_depth == 0); + } else { + check(cycle != getRoot()); + check(is_contained(cycle->m_parent->children(), cycle)); + + for (BlockHandle block : cycle->m_blocks) { + auto mapIt = m_blockMap.find(block); + check(mapIt != m_blockMap.end()); + check(contains(cycle, mapIt->second)); + check(blocks.insert(block).second); // duplicates in block list? + } + blocks.clear(); + + check(!cycle->m_entries.empty()); + for (BlockHandle entry : cycle->m_entries) { + check(entries.insert(entry).second); // duplicate entry? + check(is_contained(cycle->m_blocks, entry)); + } + entries.clear(); + } + + uint childDepth = 0; + for (const GenericCycleBase *child : cycle->children()) { + check(child->m_depth > cycle->m_depth); + if (!childDepth) { + childDepth = child->m_depth; + } else { + check(childDepth == child->m_depth); + } + } + } + + for (const auto &entry : m_blockMap) { + BlockHandle block = entry.first; + for (const GenericCycleBase *cycle = entry.second; cycle != getRoot(); + cycle = cycle->m_parent) { + check(is_contained(cycle->m_blocks, block)); + } + } + +#undef check + + return true; +} + +/// \brief Print the cycle info. +void GenericCycleInfoBase::print(const ISsaContext &ctx, + raw_ostream &out) const { + for (const GenericCycleBase *cycle : depth_first(getRoot())) { + if (!cycle->m_depth) + continue; + + for (uint i = 0; i < cycle->m_depth; ++i) + out << " "; + + out << cycle->print(ctx) << '\n'; + } +} diff --git a/llvm/test/Analysis/CycleInfo/basic.ll b/llvm/test/Analysis/CycleInfo/basic.ll new file mode 100644 --- /dev/null +++ b/llvm/test/Analysis/CycleInfo/basic.ll @@ -0,0 +1,302 @@ +; RUN: opt < %s -cycleinfo -analyze | FileCheck %s -check-prefix=CHECK +; RUN: opt < %s -disable-output -passes='print' 2>&1 | FileCheck %s -check-prefix=CHECK + +define void @empty() { +; CHECK-LABEL: CycleInfo for function: empty +; CHECK-NOT: depth + + ret void +} + +define void @simple() { +; CHECK-LABEL: CycleInfo for function: simple +; CHECK: depth=1: entries(loop) +entry: + br label %loop + +loop: + br i1 undef, label %loop, label %exit + +exit: + ret void +} + +define void @two_latches() { +; CHECK-LABEL: CycleInfo for function: two_latches +; CHECK: depth=1: entries(loop) loop_next +entry: + br label %loop + +loop: + br i1 undef, label %loop, label %loop_next + +loop_next: + br i1 undef, label %exit, label %loop + +exit: + ret void +} + +define void @nested_simple() { +; CHECK-LABEL: CycleInfo for function: nested_simple +; CHECK: depth=1: entries(outer_header) outer_latch inner +; CHECK: depth=2: entries(inner) +entry: + br label %outer_header + +outer_header: + br label %inner + +inner: + br i1 undef, label %inner, label %outer_latch + +outer_latch: + br i1 undef, label %outer_header, label %exit + +exit: + ret void +} + +define void @nested_outer_latch_in_inner_loop() { +; CHECK-LABEL: CycleInfo for function: nested_outer_latch_in_inner_loop +; CHECK: depth=1: entries(outer_header) inner_header inner_latch +; CHECK: depth=2: entries(inner_header) inner_latch +entry: + br label %outer_header + +outer_header: + br label %inner_header + +inner_header: + br i1 undef, label %inner_latch, label %outer_header + +inner_latch: + br i1 undef, label %exit, label %inner_header + +exit: + ret void +} + +define void @sibling_loops() { +; CHECK-LABEL: CycleInfo for function: sibling_loops +; CHECK-DAG: depth=1: entries(left) +; CHECK-DAG: depth=1: entries(right) +entry: + br i1 undef, label %left, label %right + +left: + br i1 undef, label %left, label %exit + +right: + br i1 undef, label %right, label %exit + +exit: + ret void +} + +define void @serial_loops() { +; CHECK-LABEL: CycleInfo for function: serial_loops +; CHECK-DAG: depth=1: entries(second) +; CHECK-DAG: depth=1: entries(first) +entry: + br label %first + +first: + br i1 undef, label %first, label %second + +second: + br i1 undef, label %second, label %exit + +exit: + ret void +} + +define void @nested_sibling_loops() { +; CHECK-LABEL: CycleInfo for function: nested_sibling_loops +; CHECK: depth=1: entries(outer_header) left right +; CHECK-DAG: depth=2: entries(right) +; CHECK-DAG: depth=2: entries(left) +entry: + br label %outer_header + +outer_header: + br i1 undef, label %left, label %right + +left: + switch i32 undef, label %exit [ i32 0, label %left + i32 1, label %outer_header ] + +right: + switch i32 undef, label %outer_header [ i32 0, label %exit + i32 1, label %right ] + +exit: + ret void +} + +define void @deeper_nest() { +; CHECK-LABEL: CycleInfo for function: deeper_nest +; CHECK: depth=1: entries(outer_header) outer_latch middle_header inner_header inner_latch +; CHECK: depth=2: entries(middle_header) inner_header inner_latch +; CHECK: depth=3: entries(inner_header) inner_latch +entry: + br label %outer_header + +outer_header: + br label %middle_header + +middle_header: + br label %inner_header + +inner_header: + br i1 undef, label %middle_header, label %inner_latch + +inner_latch: + br i1 undef, label %inner_header, label %outer_latch + +outer_latch: + br i1 undef, label %outer_header, label %exit + +exit: + ret void +} + +define void @irreducible_basic() { +; CHECK-LABEL: CycleInfo for function: irreducible_basic +; CHECK: depth=1: entries(right left) +entry: + br i1 undef, label %left, label %right + +left: + br i1 undef, label %right, label %exit + +right: + br i1 undef, label %left, label %exit + +exit: + ret void +} + +define void @irreducible_mess() { +; CHECK-LABEL: CycleInfo for function: irreducible_mess +; CHECK: depth=1: entries(B A) D C +; CHECK: depth=2: entries(D C A) +; CHECK: depth=3: entries(C A) +entry: + br i1 undef, label %A, label %B + +A: + br i1 undef, label %C, label %D + +B: + br i1 undef, label %C, label %D + +C: + switch i32 undef, label %A [ i32 0, label %D + i32 1, label %exit ] + +D: + switch i32 undef, label %B [ i32 0, label %C + i32 1, label %exit ] + +exit: + ret void +} + +define void @irreducible_into_simple_cycle() { +; CHECK-LABEL: CycleInfo for function: irreducible_into_simple_cycle +; CHECK: depth=1: entries(F C A) E D B +entry: + switch i32 undef, label %A [ i32 0, label %C + i32 1, label %F ] + +A: + br label %B + +B: + br label %C + +C: + br label %D + +D: + br i1 undef, label %E, label %exit + +E: + br label %F + +F: + br i1 undef, label %A, label %exit + +exit: + ret void +} + +define void @irreducible_mountain_bug() { +; CHECK-LABEL: CycleInfo for function: irreducible_mountain_bug +; CHECK: depth=1: entries(while.cond) +; CHECK: depth=2: entries(cond.end61 cond.true49) while.body63 while.cond47 +; CHECK: depth=3: entries(while.body63 cond.true49) while.cond47 +entry: + br i1 undef, label %if.end, label %if.then + +if.end: + br i1 undef, label %if.then7, label %if.else + +if.then7: + br label %if.end16 + +if.else: + br label %if.end16 + +if.end16: + br i1 undef, label %while.cond.preheader, label %if.then39 + +while.cond.preheader: + br label %while.cond + +while.cond: + br i1 undef, label %cond.true49, label %lor.rhs + +cond.true49: + br i1 undef, label %if.then69, label %while.body63 + +while.body63: + br i1 undef, label %exit, label %while.cond47 + +while.cond47: + br i1 undef, label %cond.true49, label %cond.end61 + +cond.end61: + br i1 undef, label %while.body63, label %while.cond + +if.then69: + br i1 undef, label %exit, label %while.cond + +lor.rhs: + br i1 undef, label %cond.end61, label %while.end76 + +while.end76: + br label %exit + +if.then39: + br i1 undef, label %exit, label %if.end.i145 + +if.end.i145: + br i1 undef, label %exit, label %if.end8.i149 + +if.end8.i149: + br label %exit + +if.then: + br i1 undef, label %exit, label %if.end.i + +if.end.i: + br i1 undef, label %exit, label %if.end8.i + +if.end8.i: + br label %exit + +exit: + ret void +}