File Manager

003 File Manager

Current Path: /usr/src/contrib/llvm-project/llvm/include/llvm/Analysis

usr / src / contrib / llvm-project / llvm / include / llvm / Analysis /

📁 ..
📄 AliasAnalysis.h(51.98 KB)
📄 AliasAnalysisEvaluator.h(2.7 KB)
📄 AliasSetTracker.h(15.42 KB)
📄 AssumeBundleQueries.h(6.66 KB)
📄 AssumptionCache.h(8.39 KB)
📄 BasicAliasAnalysis.h(10.2 KB)
📄 BlockFrequencyInfo.h(5.59 KB)
📄 BlockFrequencyInfoImpl.h(56.46 KB)
📄 BranchProbabilityInfo.h(10.1 KB)
📄 CFG.h(7.76 KB)
📄 CFGPrinter.h(9.31 KB)
📄 CFLAliasAnalysisUtils.h(1.66 KB)
📄 CFLAndersAliasAnalysis.h(3.97 KB)
📄 CFLSteensAliasAnalysis.h(4.58 KB)
📄 CGSCCPassManager.h(41.2 KB)
📄 CallGraph.h(18.88 KB)
📄 CallGraphSCCPass.h(5.01 KB)
📄 CallPrinter.h(799 B)
📄 CaptureTracking.h(4.78 KB)
📄 CmpInstAnalysis.h(2.57 KB)
📄 CodeMetrics.h(3.15 KB)
📄 ConstantFolding.h(8.01 KB)
📄 DDG.h(19.15 KB)
📄 DOTGraphTraitsPass.h(5.5 KB)
📄 DemandedBits.h(4.07 KB)
📄 DependenceAnalysis.h(41.83 KB)
📄 DependenceGraphBuilder.h(7.74 KB)
📄 DivergenceAnalysis.h(7.38 KB)
📄 DomPrinter.h(1.04 KB)
📄 DomTreeUpdater.h(13.2 KB)
📄 DominanceFrontier.h(6.63 KB)
📄 DominanceFrontierImpl.h(7.12 KB)
📄 EHPersonalities.h(3.22 KB)
📄 GlobalsModRef.h(5.96 KB)
📄 GuardUtils.h(2.11 KB)
📄 HeatUtils.h(1.16 KB)
📄 IVDescriptors.h(14.56 KB)
📄 IVUsers.h(6.07 KB)
📄 IndirectCallPromotionAnalysis.h(2.61 KB)
📄 IndirectCallVisitor.h(1.16 KB)
📄 InlineAdvisor.h(8.71 KB)
📄 InlineCost.h(11.33 KB)
📄 InlineFeaturesAnalysis.h(1.5 KB)
📄 InlineModelFeatureMaps.h(3.41 KB)
📄 InlineSizeEstimatorAnalysis.h(1.07 KB)
📄 InstructionPrecedenceTracking.h(5.9 KB)
📄 InstructionSimplify.h(13.36 KB)
📄 Interval.h(4.84 KB)
📄 IntervalIterator.h(10.64 KB)
📄 IntervalPartition.h(4.05 KB)
📄 IteratedDominanceFrontier.h(2.62 KB)
📄 LazyBlockFrequencyInfo.h(4.34 KB)
📄 LazyBranchProbabilityInfo.h(4.21 KB)
📄 LazyCallGraph.h(50.13 KB)
📄 LazyValueInfo.h(5.4 KB)
📄 LegacyDivergenceAnalysis.h(2.53 KB)
📄 Lint.h(1.35 KB)
📄 Loads.h(7.86 KB)
📄 LoopAccessAnalysis.h(29.75 KB)
📄 LoopAnalysisManager.h(5.83 KB)
📄 LoopCacheAnalysis.h(11.91 KB)
📄 LoopInfo.h(48.27 KB)
📄 LoopInfoImpl.h(27.14 KB)
📄 LoopIterator.h(8.83 KB)
📄 LoopNestAnalysis.h(5.61 KB)
📄 LoopPass.h(4.29 KB)
📄 LoopUnrollAnalyzer.h(3.42 KB)
📄 MLInlineAdvisor.h(3.48 KB)
📄 MLModelRunner.h(1.16 KB)
📄 MemoryBuiltins.h(13.42 KB)
📄 MemoryDependenceAnalysis.h(20.82 KB)
📄 MemoryLocation.h(10.99 KB)
📄 MemorySSA.h(45.92 KB)
📄 MemorySSAUpdater.h(14.55 KB)
📄 ModuleSummaryAnalysis.h(3.44 KB)
📄 MustExecute.h(20.2 KB)
📄 ObjCARCAliasAnalysis.h(3.35 KB)
📄 ObjCARCAnalysisUtils.h(10.22 KB)
📄 ObjCARCInstKind.h(4.87 KB)
📄 OptimizationRemarkEmitter.h(5.93 KB)
📄 PHITransAddr.h(4.77 KB)
📄 Passes.h(3.88 KB)
📄 PhiValues.h(5.25 KB)
📄 PostDominators.h(3.41 KB)
📄 ProfileSummaryInfo.h(9.3 KB)
📄 PtrUseVisitor.h(9.96 KB)
📄 RegionInfo.h(35.23 KB)
📄 RegionInfoImpl.h(25.16 KB)
📄 RegionIterator.h(14.07 KB)
📄 RegionPass.h(4.05 KB)
📄 RegionPrinter.h(2.25 KB)
📄 ScalarEvolution.h(89.21 KB)
📄 ScalarEvolutionAliasAnalysis.h(2.09 KB)
📄 ScalarEvolutionDivision.h(2.48 KB)
📄 ScalarEvolutionExpressions.h(28.61 KB)
📄 ScalarEvolutionNormalization.h(2.47 KB)
📄 ScopedNoAliasAA.h(2.83 KB)
📄 SparsePropagation.h(19.43 KB)
📄 StackLifetime.h(6.16 KB)
📄 StackSafetyAnalysis.h(4.91 KB)
📄 SyncDependenceAnalysis.h(2.85 KB)
📄 SyntheticCountsUtils.h(1.85 KB)
📄 TargetFolder.h(11.04 KB)
📄 TargetLibraryInfo.def(55.35 KB)
📄 TargetLibraryInfo.h(16.86 KB)
📄 TargetTransformInfo.h(96.51 KB)
📄 TargetTransformInfoImpl.h(37.63 KB)
📄 Trace.h(4.1 KB)
📄 TypeBasedAliasAnalysis.h(3.05 KB)
📄 TypeMetadataUtils.h(1.94 KB)
📁 Utils
📄 ValueLattice.h(15.14 KB)
📄 ValueLatticeUtils.h(1.66 KB)
📄 ValueTracking.h(35.82 KB)
📄 VecFuncs.def(10.94 KB)
📄 VectorUtils.h(37.26 KB)

Editing: LoopIterator.h

//===--------- LoopIterator.h - Iterate over loop blocks --------*- 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 iterators to visit the basic blocks within a loop.
//
// These iterators currently visit blocks within subloops as well.
// Unfortunately we have no efficient way of summarizing loop exits which would
// allow skipping subloops during traversal.
//
// If you want to visit all blocks in a loop and don't need an ordered traveral,
// use Loop::block_begin() instead.
//
// This is intentionally designed to work with ill-formed loops in which the
// backedge has been deleted. The only prerequisite is that all blocks
// contained within the loop according to the most recent LoopInfo analysis are
// reachable from the loop header.
//===----------------------------------------------------------------------===//

#ifndef LLVM_ANALYSIS_LOOPITERATOR_H
#define LLVM_ANALYSIS_LOOPITERATOR_H

#include "llvm/ADT/PostOrderIterator.h"
#include "llvm/Analysis/LoopInfo.h"

namespace llvm {

class LoopBlocksTraversal;

// A traits type that is intended to be used in graph algorithms. The graph
// traits starts at the loop header, and traverses the BasicBlocks that are in
// the loop body, but not the loop header. Since the loop header is skipped,
// the back edges are excluded.
//
// TODO: Explore the possibility to implement LoopBlocksTraversal in terms of
//       LoopBodyTraits, so that insertEdge doesn't have to be specialized.
struct LoopBodyTraits {
  using NodeRef = std::pair<const Loop *, BasicBlock *>;

// This wraps a const Loop * into the iterator, so we know which edges to
  // filter out.
  class WrappedSuccIterator
      : public iterator_adaptor_base<
            WrappedSuccIterator, succ_iterator,
            typename std::iterator_traits<succ_iterator>::iterator_category,
            NodeRef, std::ptrdiff_t, NodeRef *, NodeRef> {
    using BaseT = iterator_adaptor_base<
        WrappedSuccIterator, succ_iterator,
        typename std::iterator_traits<succ_iterator>::iterator_category,
        NodeRef, std::ptrdiff_t, NodeRef *, NodeRef>;

const Loop *L;

public:
    WrappedSuccIterator(succ_iterator Begin, const Loop *L)
        : BaseT(Begin), L(L) {}

NodeRef operator*() const { return {L, *I}; }
  };

struct LoopBodyFilter {
    bool operator()(NodeRef N) const {
      const Loop *L = N.first;
      return N.second != L->getHeader() && L->contains(N.second);
    }
  };

using ChildIteratorType =
      filter_iterator<WrappedSuccIterator, LoopBodyFilter>;

static NodeRef getEntryNode(const Loop &G) { return {&G, G.getHeader()}; }

static ChildIteratorType child_begin(NodeRef Node) {
    return make_filter_range(make_range<WrappedSuccIterator>(
                                 {succ_begin(Node.second), Node.first},
                                 {succ_end(Node.second), Node.first}),
                             LoopBodyFilter{})
        .begin();
  }

static ChildIteratorType child_end(NodeRef Node) {
    return make_filter_range(make_range<WrappedSuccIterator>(
                                 {succ_begin(Node.second), Node.first},
                                 {succ_end(Node.second), Node.first}),
                             LoopBodyFilter{})
        .end();
  }
};

/// Store the result of a depth first search within basic blocks contained by a
/// single loop.
///
/// TODO: This could be generalized for any CFG region, or the entire CFG.
class LoopBlocksDFS {
public:
  /// Postorder list iterators.
  typedef std::vector<BasicBlock*>::const_iterator POIterator;
  typedef std::vector<BasicBlock*>::const_reverse_iterator RPOIterator;

friend class LoopBlocksTraversal;

private:
  Loop *L;

/// Map each block to its postorder number. A block is only mapped after it is
  /// preorder visited by DFS. It's postorder number is initially zero and set
  /// to nonzero after it is finished by postorder traversal.
  DenseMap<BasicBlock*, unsigned> PostNumbers;
  std::vector<BasicBlock*> PostBlocks;

public:
  LoopBlocksDFS(Loop *Container) :
    L(Container), PostNumbers(NextPowerOf2(Container->getNumBlocks())) {
    PostBlocks.reserve(Container->getNumBlocks());
  }

Loop *getLoop() const { return L; }

/// Traverse the loop blocks and store the DFS result.
  void perform(LoopInfo *LI);

/// Return true if postorder numbers are assigned to all loop blocks.
  bool isComplete() const { return PostBlocks.size() == L->getNumBlocks(); }

/// Iterate over the cached postorder blocks.
  POIterator beginPostorder() const {
    assert(isComplete() && "bad loop DFS");
    return PostBlocks.begin();
  }
  POIterator endPostorder() const { return PostBlocks.end(); }

/// Reverse iterate over the cached postorder blocks.
  RPOIterator beginRPO() const {
    assert(isComplete() && "bad loop DFS");
    return PostBlocks.rbegin();
  }
  RPOIterator endRPO() const { return PostBlocks.rend(); }

/// Return true if this block has been preorder visited.
  bool hasPreorder(BasicBlock *BB) const { return PostNumbers.count(BB); }

/// Return true if this block has a postorder number.
  bool hasPostorder(BasicBlock *BB) const {
    DenseMap<BasicBlock*, unsigned>::const_iterator I = PostNumbers.find(BB);
    return I != PostNumbers.end() && I->second;
  }

/// Get a block's postorder number.
  unsigned getPostorder(BasicBlock *BB) const {
    DenseMap<BasicBlock*, unsigned>::const_iterator I = PostNumbers.find(BB);
    assert(I != PostNumbers.end() && "block not visited by DFS");
    assert(I->second && "block not finished by DFS");
    return I->second;
  }

/// Get a block's reverse postorder number.
  unsigned getRPO(BasicBlock *BB) const {
    return 1 + PostBlocks.size() - getPostorder(BB);
  }

void clear() {
    PostNumbers.clear();
    PostBlocks.clear();
  }
};

/// Wrapper class to LoopBlocksDFS that provides a standard begin()/end()
/// interface for the DFS reverse post-order traversal of blocks in a loop body.
class LoopBlocksRPO {
private:
  LoopBlocksDFS DFS;

public:
  LoopBlocksRPO(Loop *Container) : DFS(Container) {}

/// Traverse the loop blocks and store the DFS result.
  void perform(LoopInfo *LI) {
    DFS.perform(LI);
  }

/// Reverse iterate over the cached postorder blocks.
  LoopBlocksDFS::RPOIterator begin() const { return DFS.beginRPO(); }
  LoopBlocksDFS::RPOIterator end() const { return DFS.endRPO(); }
};

/// Specialize po_iterator_storage to record postorder numbers.
template<> class po_iterator_storage<LoopBlocksTraversal, true> {
  LoopBlocksTraversal &LBT;
public:
  po_iterator_storage(LoopBlocksTraversal &lbs) : LBT(lbs) {}
  // These functions are defined below.
  bool insertEdge(Optional<BasicBlock *> From, BasicBlock *To);
  void finishPostorder(BasicBlock *BB);
};

/// Traverse the blocks in a loop using a depth-first search.
class LoopBlocksTraversal {
public:
  /// Graph traversal iterator.
  typedef po_iterator<BasicBlock*, LoopBlocksTraversal, true> POTIterator;

private:
  LoopBlocksDFS &DFS;
  LoopInfo *LI;

public:
  LoopBlocksTraversal(LoopBlocksDFS &Storage, LoopInfo *LInfo) :
    DFS(Storage), LI(LInfo) {}

/// Postorder traversal over the graph. This only needs to be done once.
  /// po_iterator "automatically" calls back to visitPreorder and
  /// finishPostorder to record the DFS result.
  POTIterator begin() {
    assert(DFS.PostBlocks.empty() && "Need clear DFS result before traversing");
    assert(DFS.L->getNumBlocks() && "po_iterator cannot handle an empty graph");
    return po_ext_begin(DFS.L->getHeader(), *this);
  }
  POTIterator end() {
    // po_ext_end interface requires a basic block, but ignores its value.
    return po_ext_end(DFS.L->getHeader(), *this);
  }

/// Called by po_iterator upon reaching a block via a CFG edge. If this block
  /// is contained in the loop and has not been visited, then mark it preorder
  /// visited and return true.
  ///
  /// TODO: If anyone is interested, we could record preorder numbers here.
  bool visitPreorder(BasicBlock *BB) {
    if (!DFS.L->contains(LI->getLoopFor(BB)))
      return false;

return DFS.PostNumbers.insert(std::make_pair(BB, 0)).second;
  }

/// Called by po_iterator each time it advances, indicating a block's
  /// postorder.
  void finishPostorder(BasicBlock *BB) {
    assert(DFS.PostNumbers.count(BB) && "Loop DFS skipped preorder");
    DFS.PostBlocks.push_back(BB);
    DFS.PostNumbers[BB] = DFS.PostBlocks.size();
  }
};

inline bool po_iterator_storage<LoopBlocksTraversal, true>::insertEdge(
    Optional<BasicBlock *> From, BasicBlock *To) {
  return LBT.visitPreorder(To);
}

inline void po_iterator_storage<LoopBlocksTraversal, true>::
finishPostorder(BasicBlock *BB) {
  LBT.finishPostorder(BB);
}

} // End namespace llvm

#endif

003 File Manager

Editing: LoopIterator.h

Upload File

Create Folder