<commit_before>//===- llvm/Analysis/LoopInfo.h - Natural Loop Calculator -------*- C++ -*-===//
//
//                     The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// This file defines the LoopInfo class that is used to identify natural loops
// and determine the loop depth of various nodes of the CFG.  A natural loop
// has exactly one entry-point, which is called the header. Note that natural
// loops may actually be several loops that share the same header node.
//
// This analysis calculates the nesting structure of loops in a function.  For
// each natural loop identified, this analysis identifies natural loops
// contained entirely within the loop and the basic blocks the make up the loop.
//
// It can calculate on the fly various bits of information, for example:
//
//  * whether there is a preheader for the loop
//  * the number of back edges to the header
//  * whether or not a particular block branches out of the loop
//  * the successor blocks of the loop
//  * the loop depth
//  * etc...
//
//===----------------------------------------------------------------------===//

#ifndef LLVM_ANALYSIS_LOOPINFO_H
#define LLVM_ANALYSIS_LOOPINFO_H

#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/DenseSet.h"
#include "llvm/ADT/GraphTraits.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/Analysis/Dominators.h"
#include "llvm/Pass.h"
#include <algorithm>

namespace llvm {

template<typename T>
inline void RemoveFromVector(std::vector<T*> &V, T *N) {
  typename std::vector<T*>::iterator I = std::find(V.begin(), V.end(), N);
  assert(I != V.end() && "N is not in this list!");
  V.erase(I);
}

class DominatorTree;
class LoopInfo;
class Loop;
class MDNode;
class PHINode;
class raw_ostream;
template<class N, class M> class LoopInfoBase;
template<class N, class M> class LoopBase;

//===----------------------------------------------------------------------===//
/// LoopBase class - Instances of this class are used to represent loops that
/// are detected in the flow graph
///
template<class BlockT, class LoopT>
class LoopBase {
  LoopT *ParentLoop;
  // SubLoops - Loops contained entirely within this one.
  std::vector<LoopT *> SubLoops;

  // Blocks - The list of blocks in this loop.  First entry is the header node.
  std::vector<BlockT*> Blocks;

  SmallPtrSet<const BlockT*, 8> DenseBlockSet;

  LoopBase(const LoopBase<BlockT, LoopT> &) LLVM_DELETED_FUNCTION;
  const LoopBase<BlockT, LoopT>&
    operator=(const LoopBase<BlockT, LoopT> &) LLVM_DELETED_FUNCTION;
public:
  /// Loop ctor - This creates an empty loop.
  LoopBase() : ParentLoop(0) {}
  ~LoopBase() {
    for (size_t i = 0, e = SubLoops.size(); i != e; ++i)
      delete SubLoops[i];
  }

  /// getLoopDepth - Return the nesting level of this loop.  An outer-most
  /// loop has depth 1, for consistency with loop depth values used for basic
  /// blocks, where depth 0 is used for blocks not inside any loops.
  unsigned getLoopDepth() const {
    unsigned D = 1;
    for (const LoopT *CurLoop = ParentLoop; CurLoop;
         CurLoop = CurLoop->ParentLoop)
      ++D;
    return D;
  }
  BlockT *getHeader() const { return Blocks.front(); }
  LoopT *getParentLoop() const { return ParentLoop; }

  /// setParentLoop is a raw interface for bypassing addChildLoop.
  void setParentLoop(LoopT *L) { ParentLoop = L; }

  /// contains - Return true if the specified loop is contained within in
  /// this loop.
  ///
  bool contains(const LoopT *L) const {
    if (L == this) return true;
    if (L == 0)    return false;
    return contains(L->getParentLoop());
  }

  /// contains - Return true if the specified basic block is in this loop.
  ///
  bool contains(const BlockT *BB) const {
    return DenseBlockSet.count(BB);
  }

  /// contains - Return true if the specified instruction is in this loop.
  ///
  template<class InstT>
  bool contains(const InstT *Inst) const {
    return contains(Inst->getParent());
  }

  /// iterator/begin/end - Return the loops contained entirely within this loop.
  ///
  const std::vector<LoopT *> &getSubLoops() const { return SubLoops; }
  std::vector<LoopT *> &getSubLoopsVector() { return SubLoops; }
  typedef typename std::vector<LoopT *>::const_iterator iterator;
  typedef typename std::vector<LoopT *>::const_reverse_iterator
    reverse_iterator;
  iterator begin() const { return SubLoops.begin(); }
  iterator end() const { return SubLoops.end(); }
  reverse_iterator rbegin() const { return SubLoops.rbegin(); }
  reverse_iterator rend() const { return SubLoops.rend(); }
  bool empty() const { return SubLoops.empty(); }

  /// getBlocks - Get a list of the basic blocks which make up this loop.
  ///
  const std::vector<BlockT*> &getBlocks() const { return Blocks; }
  typedef typename std::vector<BlockT*>::const_iterator block_iterator;
  block_iterator block_begin() const { return Blocks.begin(); }
  block_iterator block_end() const { return Blocks.end(); }

  /// getNumBlocks - Get the number of blocks in this loop in constant time.
  unsigned getNumBlocks() const {
    return Blocks.size();
  }

  /// isLoopExiting - True if terminator in the block can branch to another
  /// block that is outside of the current loop.
  ///
  bool isLoopExiting(const BlockT *BB) const {
    typedef GraphTraits<const BlockT*> BlockTraits;
    for (typename BlockTraits::ChildIteratorType SI =
         BlockTraits::child_begin(BB),
         SE = BlockTraits::child_end(BB); SI != SE; ++SI) {
      if (!contains(*SI))
        return true;
    }
    return false;
  }

  /// getNumBackEdges - Calculate the number of back edges to the loop header
  ///
  unsigned getNumBackEdges() const {
    unsigned NumBackEdges = 0;
    BlockT *H = getHeader();

    typedef GraphTraits<Inverse<BlockT*> > InvBlockTraits;
    for (typename InvBlockTraits::ChildIteratorType I =
         InvBlockTraits::child_begin(H),
         E = InvBlockTraits::child_end(H); I != E; ++I)
      if (contains(*I))
        ++NumBackEdges;

    return NumBackEdges;
  }

  //===--------------------------------------------------------------------===//
  // APIs for simple analysis of the loop.
  //
  // Note that all of these methods can fail on general loops (ie, there may not
  // be a preheader, etc).  For best success, the loop simplification and
  // induction variable canonicalization pass should be used to normalize loops
  // for easy analysis.  These methods assume canonical loops.

  /// getExitingBlocks - Return all blocks inside the loop that have successors
  /// outside of the loop.  These are the blocks _inside of the current loop_
  /// which branch out.  The returned list is always unique.
  ///
  void getExitingBlocks(SmallVectorImpl<BlockT *> &ExitingBlocks) const;

  /// getExitingBlock - If getExitingBlocks would return exactly one block,
  /// return that block. Otherwise return null.
  BlockT *getExitingBlock() const;

  /// getExitBlocks - Return all of the successor blocks of this loop.  These
  /// are the blocks _outside of the current loop_ which are branched to.
  ///
  void getExitBlocks(SmallVectorImpl<BlockT*> &ExitBlocks) const;

  /// getExitBlock - If getExitBlocks would return exactly one block,
  /// return that block. Otherwise return null.
  BlockT *getExitBlock() const;

  /// Edge type.
  typedef std::pair<const BlockT*, const BlockT*> Edge;

  /// getExitEdges - Return all pairs of (_inside_block_,_outside_block_).
  void getExitEdges(SmallVectorImpl<Edge> &ExitEdges) const;

  /// getLoopPreheader - If there is a preheader for this loop, return it.  A
  /// loop has a preheader if there is only one edge to the header of the loop
  /// from outside of the loop.  If this is the case, the block branching to the
  /// header of the loop is the preheader node.
  ///
  /// This method returns null if there is no preheader for the loop.
  ///
  BlockT *getLoopPreheader() const;

  /// getLoopPredecessor - If the given loop's header has exactly one unique
  /// predecessor outside the loop, return it. Otherwise return null.
  /// This is less strict that the loop "preheader" concept, which requires
  /// the predecessor to have exactly one successor.
  ///
  BlockT *getLoopPredecessor() const;

  /// getLoopLatch - If there is a single latch block for this loop, return it.
  /// A latch block is a block that contains a branch back to the header.
  BlockT *getLoopLatch() const;

  //===--------------------------------------------------------------------===//
  // APIs for updating loop information after changing the CFG
  //

  /// addBasicBlockToLoop - This method is used by other analyses to update loop
  /// information.  NewBB is set to be a new member of the current loop.
  /// Because of this, it is added as a member of all parent loops, and is added
  /// to the specified LoopInfo object as being in the current basic block.  It
  /// is not valid to replace the loop header with this method.
  ///
  void addBasicBlockToLoop(BlockT *NewBB, LoopInfoBase<BlockT, LoopT> &LI);

  /// replaceChildLoopWith - This is used when splitting loops up.  It replaces
  /// the OldChild entry in our children list with NewChild, and updates the
  /// parent pointer of OldChild to be null and the NewChild to be this loop.
  /// This updates the loop depth of the new child.
  void replaceChildLoopWith(LoopT *OldChild, LoopT *NewChild);
<commit_msg>[block-freq] Add a method to loop info for returning all loop latches for a specific loop.<commit_after>//===- llvm/Analysis/LoopInfo.h - Natural Loop Calculator -------*- C++ -*-===//
//
//                     The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// This file defines the LoopInfo class that is used to identify natural loops
// and determine the loop depth of various nodes of the CFG.  A natural loop
// has exactly one entry-point, which is called the header. Note that natural
// loops may actually be several loops that share the same header node.
//
// This analysis calculates the nesting structure of loops in a function.  For
// each natural loop identified, this analysis identifies natural loops
// contained entirely within the loop and the basic blocks the make up the loop.
//
// It can calculate on the fly various bits of information, for example:
//
//  * whether there is a preheader for the loop
//  * the number of back edges to the header
//  * whether or not a particular block branches out of the loop
//  * the successor blocks of the loop
//  * the loop depth
//  * etc...
//
//===----------------------------------------------------------------------===//

#ifndef LLVM_ANALYSIS_LOOPINFO_H
#define LLVM_ANALYSIS_LOOPINFO_H

#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/DenseSet.h"
#include "llvm/ADT/GraphTraits.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/Analysis/Dominators.h"
#include "llvm/Pass.h"
#include <algorithm>

namespace llvm {

template<typename T>
inline void RemoveFromVector(std::vector<T*> &V, T *N) {
  typename std::vector<T*>::iterator I = std::find(V.begin(), V.end(), N);
  assert(I != V.end() && "N is not in this list!");
  V.erase(I);
}

class DominatorTree;
class LoopInfo;
class Loop;
class MDNode;
class PHINode;
class raw_ostream;
template<class N, class M> class LoopInfoBase;
template<class N, class M> class LoopBase;

//===----------------------------------------------------------------------===//
/// LoopBase class - Instances of this class are used to represent loops that
/// are detected in the flow graph
///
template<class BlockT, class LoopT>
class LoopBase {
  LoopT *ParentLoop;
  // SubLoops - Loops contained entirely within this one.
  std::vector<LoopT *> SubLoops;

  // Blocks - The list of blocks in this loop.  First entry is the header node.
  std::vector<BlockT*> Blocks;

  SmallPtrSet<const BlockT*, 8> DenseBlockSet;

  LoopBase(const LoopBase<BlockT, LoopT> &) LLVM_DELETED_FUNCTION;
  const LoopBase<BlockT, LoopT>&
    operator=(const LoopBase<BlockT, LoopT> &) LLVM_DELETED_FUNCTION;
public:
  /// Loop ctor - This creates an empty loop.
  LoopBase() : ParentLoop(0) {}
  ~LoopBase() {
    for (size_t i = 0, e = SubLoops.size(); i != e; ++i)
      delete SubLoops[i];
  }

  /// getLoopDepth - Return the nesting level of this loop.  An outer-most
  /// loop has depth 1, for consistency with loop depth values used for basic
  /// blocks, where depth 0 is used for blocks not inside any loops.
  unsigned getLoopDepth() const {
    unsigned D = 1;
    for (const LoopT *CurLoop = ParentLoop; CurLoop;
         CurLoop = CurLoop->ParentLoop)
      ++D;
    return D;
  }
  BlockT *getHeader() const { return Blocks.front(); }
  LoopT *getParentLoop() const { return ParentLoop; }

  /// setParentLoop is a raw interface for bypassing addChildLoop.
  void setParentLoop(LoopT *L) { ParentLoop = L; }

  /// contains - Return true if the specified loop is contained within in
  /// this loop.
  ///
  bool contains(const LoopT *L) const {
    if (L == this) return true;
    if (L == 0)    return false;
    return contains(L->getParentLoop());
  }

  /// contains - Return true if the specified basic block is in this loop.
  ///
  bool contains(const BlockT *BB) const {
    return DenseBlockSet.count(BB);
  }

  /// contains - Return true if the specified instruction is in this loop.
  ///
  template<class InstT>
  bool contains(const InstT *Inst) const {
    return contains(Inst->getParent());
  }

  /// iterator/begin/end - Return the loops contained entirely within this loop.
  ///
  const std::vector<LoopT *> &getSubLoops() const { return SubLoops; }
  std::vector<LoopT *> &getSubLoopsVector() { return SubLoops; }
  typedef typename std::vector<LoopT *>::const_iterator iterator;
  typedef typename std::vector<LoopT *>::const_reverse_iterator
    reverse_iterator;
  iterator begin() const { return SubLoops.begin(); }
  iterator end() const { return SubLoops.end(); }
  reverse_iterator rbegin() const { return SubLoops.rbegin(); }
  reverse_iterator rend() const { return SubLoops.rend(); }
  bool empty() const { return SubLoops.empty(); }

  /// getBlocks - Get a list of the basic blocks which make up this loop.
  ///
  const std::vector<BlockT*> &getBlocks() const { return Blocks; }
  typedef typename std::vector<BlockT*>::const_iterator block_iterator;
  block_iterator block_begin() const { return Blocks.begin(); }
  block_iterator block_end() const { return Blocks.end(); }

  /// getNumBlocks - Get the number of blocks in this loop in constant time.
  unsigned getNumBlocks() const {
    return Blocks.size();
  }

  /// isLoopExiting - True if terminator in the block can branch to another
  /// block that is outside of the current loop.
  ///
  bool isLoopExiting(const BlockT *BB) const {
    typedef GraphTraits<const BlockT*> BlockTraits;
    for (typename BlockTraits::ChildIteratorType SI =
         BlockTraits::child_begin(BB),
         SE = BlockTraits::child_end(BB); SI != SE; ++SI) {
      if (!contains(*SI))
        return true;
    }
    return false;
  }

  /// getNumBackEdges - Calculate the number of back edges to the loop header
  ///
  unsigned getNumBackEdges() const {
    unsigned NumBackEdges = 0;
    BlockT *H = getHeader();

    typedef GraphTraits<Inverse<BlockT*> > InvBlockTraits;
    for (typename InvBlockTraits::ChildIteratorType I =
         InvBlockTraits::child_begin(H),
         E = InvBlockTraits::child_end(H); I != E; ++I)
      if (contains(*I))
        ++NumBackEdges;

    return NumBackEdges;
  }

  //===--------------------------------------------------------------------===//
  // APIs for simple analysis of the loop.
  //
  // Note that all of these methods can fail on general loops (ie, there may not
  // be a preheader, etc).  For best success, the loop simplification and
  // induction variable canonicalization pass should be used to normalize loops
  // for easy analysis.  These methods assume canonical loops.

  /// getExitingBlocks - Return all blocks inside the loop that have successors
  /// outside of the loop.  These are the blocks _inside of the current loop_
  /// which branch out.  The returned list is always unique.
  ///
  void getExitingBlocks(SmallVectorImpl<BlockT *> &ExitingBlocks) const;

  /// getExitingBlock - If getExitingBlocks would return exactly one block,
  /// return that block. Otherwise return null.
  BlockT *getExitingBlock() const;

  /// getExitBlocks - Return all of the successor blocks of this loop.  These
  /// are the blocks _outside of the current loop_ which are branched to.
  ///
  void getExitBlocks(SmallVectorImpl<BlockT*> &ExitBlocks) const;

  /// getExitBlock - If getExitBlocks would return exactly one block,
  /// return that block. Otherwise return null.
  BlockT *getExitBlock() const;

  /// Edge type.
  typedef std::pair<const BlockT*, const BlockT*> Edge;

  /// getExitEdges - Return all pairs of (_inside_block_,_outside_block_).
  void getExitEdges(SmallVectorImpl<Edge> &ExitEdges) const;

  /// getLoopPreheader - If there is a preheader for this loop, return it.  A
  /// loop has a preheader if there is only one edge to the header of the loop
  /// from outside of the loop.  If this is the case, the block branching to the
  /// header of the loop is the preheader node.
  ///
  /// This method returns null if there is no preheader for the loop.
  ///
  BlockT *getLoopPreheader() const;

  /// getLoopPredecessor - If the given loop's header has exactly one unique
  /// predecessor outside the loop, return it. Otherwise return null.
  /// This is less strict that the loop "preheader" concept, which requires
  /// the predecessor to have exactly one successor.
  ///
  BlockT *getLoopPredecessor() const;

  /// getLoopLatch - If there is a single latch block for this loop, return it.
  /// A latch block is a block that contains a branch back to the header.
  BlockT *getLoopLatch() const;

  /// getLoopLatches - Return all loop latch blocks of this loop. A latch block
  /// is a block that contains a branch back to the header.
  void getLoopLatches(SmallVectorImpl<BlockT *> &LoopLatches) const {
    BlockT *H = getHeader();
    typedef GraphTraits<Inverse<BlockT*> > InvBlockTraits;
    for (typename InvBlockTraits::ChildIteratorType I =
         InvBlockTraits::child_begin(H),
         E = InvBlockTraits::child_end(H); I != E; ++I)
      if (contains(*I))
        LoopLatches.push_back(*I);
  }

  //===--------------------------------------------------------------------===//
  // APIs for updating loop information after changing the CFG
  //

  /// addBasicBlockToLoop - This method is used by other analyses to update loop
  /// information.  NewBB is set to be a new member of the current loop.
  /// Because of this, it is added as a member of all parent loops, and is added
  /// to the specified LoopInfo object as being in the current basic block.  It
  /// is not valid to replace the loop header with this method.
  ///
  void addBasicBlockToLoop(BlockT *NewBB, LoopInfoBase<BlockT, LoopT> &LI);

  /// replaceChildLoopWith - This is used when splitting loops up.  It replaces
  /// the OldChild entry in our children list with NewChild, and updates the
  /// parent pointer of OldChild to be null and the NewChild to be this loop.
  /// This updates the loop depth of the new child.
  void replaceChildLoopWith(LoopT *OldChild, LoopT *NewChild);

{'fraction_non_alphanumeric': 0.13886068237205523, 'fraction_numerical': 0.0008123476848090983, 'mean_word_length': 2.7704823889739663, 'pattern_counts': {'":': 0, '<': 62, '<?xml version=': 0, '>': 68, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '3081534', 'n_tokens_mistral': 5697, 'n_tokens_neox': 5501, 'n_words': 2215}