<commit_before>//===- LazyCallGraph.h - Analysis of a Module's call graph ------*- C++ -*-===//
//
//                     The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
/// \file
///
/// Implements a lazy call graph analysis and related passes for the new pass
/// manager.
///
/// NB: This is *not* a traditional call graph! It is a graph which models both
/// the current calls and potential calls. As a consequence there are many
/// edges in this call graph that do not correspond to a 'call' or 'invoke'
/// instruction.
///
/// The primary use cases of this graph analysis is to facilitate iterating
/// across the functions of a module in ways that ensure all callees are
/// visited prior to a caller (given any SCC constraints), or vice versa. As
/// such is it particularly well suited to organizing CGSCC optimizations such
/// as inlining, outlining, argument promotion, etc. That is its primary use
/// case and motivates the design. It may not be appropriate for other
/// purposes. The use graph of functions or some other conservative analysis of
/// call instructions may be interesting for optimizations and subsequent
/// analyses which don't work in the context of an overly specified
/// potential-call-edge graph.
///
/// To understand the specific rules and nature of this call graph analysis,
/// see the documentation of the \c LazyCallGraph below.
///
//===----------------------------------------------------------------------===//

#ifndef LLVM_ANALYSIS_LAZY_CALL_GRAPH
#define LLVM_ANALYSIS_LAZY_CALL_GRAPH

#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/PointerUnion.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/IR/BasicBlock.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/Module.h"
#include "llvm/Support/Allocator.h"
#include <iterator>

namespace llvm {
class ModuleAnalysisManager;
class PreservedAnalyses;
class raw_ostream;

/// \brief A lazily constructed view of the call graph of a module.
///
/// With the edges of this graph, the motivating constraint that we are
/// attempting to maintain is that function-local optimization, CGSCC-local
/// optimizations, and optimizations transforming a pair of functions connected
/// by an edge in the graph, do not invalidate a bottom-up traversal of the SCC
/// DAG. That is, no optimizations will delete, remove, or add an edge such
/// that functions already visited in a bottom-up order of the SCC DAG are no
/// longer valid to have visited, or such that functions not yet visited in
/// a bottom-up order of the SCC DAG are not required to have already been
/// visited.
///
/// Within this constraint, the desire is to minimize the merge points of the
/// SCC DAG. The greater the fanout of the SCC DAG and the fewer merge points
/// in the SCC DAG, the more independence there is in optimizing within it.
/// There is a strong desire to enable parallelization of optimizations over
/// the call graph, and both limited fanout and merge points will (artificially
/// in some cases) limit the scaling of such an effort.
///
/// To this end, graph represents both direct and any potential resolution to
/// an indirect call edge. Another way to think about it is that it represents
/// both the direct call edges and any direct call edges that might be formed
/// through static optimizations. Specifically, it considers taking the address
/// of a function to be an edge in the call graph because this might be
/// forwarded to become a direct call by some subsequent function-local
/// optimization. The result is that the graph closely follows the use-def
/// edges for functions. Walking "up" the graph can be done by looking at all
/// of the uses of a function.
///
/// The roots of the call graph are the external functions and functions
/// escaped into global variables. Those functions can be called from outside
/// of the module or via unknowable means in the IR -- we may not be able to
/// form even a potential call edge from a function body which may dynamically
/// load the function and call it.
///
/// This analysis still requires updates to remain valid after optimizations
/// which could potentially change the set of potential callees. The
/// constraints it operates under only make the traversal order remain valid.
///
/// The entire analysis must be re-computed if full interprocedural
/// optimizations run at any point. For example, globalopt completely
/// invalidates the information in this analysis.
///
/// FIXME: This class is named LazyCallGraph in a lame attempt to distinguish
/// it from the existing CallGraph. At some point, it is expected that this
/// will be the only call graph and it will be renamed accordingly.
class LazyCallGraph {
public:
  class Node;
  typedef SmallVector<PointerUnion<Function *, Node *>, 4> NodeVectorT;
  typedef SmallVectorImpl<PointerUnion<Function *, Node *>> NodeVectorImplT;

  /// \brief A lazy iterator used for both the entry nodes and child nodes.
  ///
  /// When this iterator is dereferenced, if not yet available, a function will
  /// be scanned for "calls" or uses of functions and its child information
  /// will be constructed. All of these results are accumulated and cached in
  /// the graph.
  class iterator : public std::iterator<std::bidirectional_iterator_tag, Node *,
                                        ptrdiff_t, Node *, Node *> {
    friend class LazyCallGraph;
    friend class LazyCallGraph::Node;
    typedef std::iterator<std::bidirectional_iterator_tag, Node *, ptrdiff_t,
                          Node *, Node *> BaseT;

    /// \brief Nonce type to select the constructor for the end iterator.
    struct IsAtEndT {};

    LazyCallGraph *G;
    NodeVectorImplT::iterator NI;

    // Build the begin iterator for a node.
    explicit iterator(LazyCallGraph &G, NodeVectorImplT &Nodes)
        : G(&G), NI(Nodes.begin()) {}

    // Build the end iterator for a node. This is selected purely by overload.
    iterator(LazyCallGraph &G, NodeVectorImplT &Nodes, IsAtEndT /*Nonce*/)
        : G(&G), NI(Nodes.end()) {}

  public:
    bool operator==(const iterator &Arg) { return NI == Arg.NI; }
    bool operator!=(const iterator &Arg) { return !operator==(Arg); }

    reference operator*() const {
      if (NI->is<Node *>())
        return NI->get<Node *>();

      Function *F = NI->get<Function *>();
      Node *ChildN = G->get(*F);
      *NI = ChildN;
      return ChildN;
    }
    pointer operator->() const { return operator*(); }

    iterator &operator++() {
      ++NI;
      return *this;
    }
    iterator operator++(int) {
      iterator prev = *this;
      ++*this;
      return prev;
    }

    iterator &operator--() {
      --NI;
      return *this;
    }
    iterator operator--(int) {
      iterator next = *this;
      --*this;
      return next;
    }
  };

  /// \brief A node in the call graph.
  ///
  /// This represents a single node. It's primary roles are to cache the list of
  /// callees, de-duplicate and provide fast testing of whether a function is
  /// a callee, and facilitate iteration of child nodes in the graph.
  class Node {
    friend class LazyCallGraph;

    LazyCallGraph *G;
    Function &F;
    mutable NodeVectorT Callees;
    SmallPtrSet<Function *, 4> CalleeSet;

    /// \brief Basic constructor implements the scanning of F into Callees and
    /// CalleeSet.
    Node(LazyCallGraph &G, Function &F);

    /// \brief Constructor used when copying a node from one graph to another.
    Node(LazyCallGraph &G, const Node &OtherN);

    /// \brief Constructor used when moving a node from one graph to another.
    Node(LazyCallGraph &G, Node &&OtherN);

  public:
    typedef LazyCallGraph::iterator iterator;<commit_msg>[LCG] Remove a dead declaration. This stopped being used when I switched to a more normal move operation on the graph itself. The definition already got removed, but I missed the declaration.<commit_after>//===- LazyCallGraph.h - Analysis of a Module's call graph ------*- C++ -*-===//
//
//                     The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
/// \file
///
/// Implements a lazy call graph analysis and related passes for the new pass
/// manager.
///
/// NB: This is *not* a traditional call graph! It is a graph which models both
/// the current calls and potential calls. As a consequence there are many
/// edges in this call graph that do not correspond to a 'call' or 'invoke'
/// instruction.
///
/// The primary use cases of this graph analysis is to facilitate iterating
/// across the functions of a module in ways that ensure all callees are
/// visited prior to a caller (given any SCC constraints), or vice versa. As
/// such is it particularly well suited to organizing CGSCC optimizations such
/// as inlining, outlining, argument promotion, etc. That is its primary use
/// case and motivates the design. It may not be appropriate for other
/// purposes. The use graph of functions or some other conservative analysis of
/// call instructions may be interesting for optimizations and subsequent
/// analyses which don't work in the context of an overly specified
/// potential-call-edge graph.
///
/// To understand the specific rules and nature of this call graph analysis,
/// see the documentation of the \c LazyCallGraph below.
///
//===----------------------------------------------------------------------===//

#ifndef LLVM_ANALYSIS_LAZY_CALL_GRAPH
#define LLVM_ANALYSIS_LAZY_CALL_GRAPH

#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/PointerUnion.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/IR/BasicBlock.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/Module.h"
#include "llvm/Support/Allocator.h"
#include <iterator>

namespace llvm {
class ModuleAnalysisManager;
class PreservedAnalyses;
class raw_ostream;

/// \brief A lazily constructed view of the call graph of a module.
///
/// With the edges of this graph, the motivating constraint that we are
/// attempting to maintain is that function-local optimization, CGSCC-local
/// optimizations, and optimizations transforming a pair of functions connected
/// by an edge in the graph, do not invalidate a bottom-up traversal of the SCC
/// DAG. That is, no optimizations will delete, remove, or add an edge such
/// that functions already visited in a bottom-up order of the SCC DAG are no
/// longer valid to have visited, or such that functions not yet visited in
/// a bottom-up order of the SCC DAG are not required to have already been
/// visited.
///
/// Within this constraint, the desire is to minimize the merge points of the
/// SCC DAG. The greater the fanout of the SCC DAG and the fewer merge points
/// in the SCC DAG, the more independence there is in optimizing within it.
/// There is a strong desire to enable parallelization of optimizations over
/// the call graph, and both limited fanout and merge points will (artificially
/// in some cases) limit the scaling of such an effort.
///
/// To this end, graph represents both direct and any potential resolution to
/// an indirect call edge. Another way to think about it is that it represents
/// both the direct call edges and any direct call edges that might be formed
/// through static optimizations. Specifically, it considers taking the address
/// of a function to be an edge in the call graph because this might be
/// forwarded to become a direct call by some subsequent function-local
/// optimization. The result is that the graph closely follows the use-def
/// edges for functions. Walking "up" the graph can be done by looking at all
/// of the uses of a function.
///
/// The roots of the call graph are the external functions and functions
/// escaped into global variables. Those functions can be called from outside
/// of the module or via unknowable means in the IR -- we may not be able to
/// form even a potential call edge from a function body which may dynamically
/// load the function and call it.
///
/// This analysis still requires updates to remain valid after optimizations
/// which could potentially change the set of potential callees. The
/// constraints it operates under only make the traversal order remain valid.
///
/// The entire analysis must be re-computed if full interprocedural
/// optimizations run at any point. For example, globalopt completely
/// invalidates the information in this analysis.
///
/// FIXME: This class is named LazyCallGraph in a lame attempt to distinguish
/// it from the existing CallGraph. At some point, it is expected that this
/// will be the only call graph and it will be renamed accordingly.
class LazyCallGraph {
public:
  class Node;
  typedef SmallVector<PointerUnion<Function *, Node *>, 4> NodeVectorT;
  typedef SmallVectorImpl<PointerUnion<Function *, Node *>> NodeVectorImplT;

  /// \brief A lazy iterator used for both the entry nodes and child nodes.
  ///
  /// When this iterator is dereferenced, if not yet available, a function will
  /// be scanned for "calls" or uses of functions and its child information
  /// will be constructed. All of these results are accumulated and cached in
  /// the graph.
  class iterator : public std::iterator<std::bidirectional_iterator_tag, Node *,
                                        ptrdiff_t, Node *, Node *> {
    friend class LazyCallGraph;
    friend class LazyCallGraph::Node;
    typedef std::iterator<std::bidirectional_iterator_tag, Node *, ptrdiff_t,
                          Node *, Node *> BaseT;

    /// \brief Nonce type to select the constructor for the end iterator.
    struct IsAtEndT {};

    LazyCallGraph *G;
    NodeVectorImplT::iterator NI;

    // Build the begin iterator for a node.
    explicit iterator(LazyCallGraph &G, NodeVectorImplT &Nodes)
        : G(&G), NI(Nodes.begin()) {}

    // Build the end iterator for a node. This is selected purely by overload.
    iterator(LazyCallGraph &G, NodeVectorImplT &Nodes, IsAtEndT /*Nonce*/)
        : G(&G), NI(Nodes.end()) {}

  public:
    bool operator==(const iterator &Arg) { return NI == Arg.NI; }
    bool operator!=(const iterator &Arg) { return !operator==(Arg); }

    reference operator*() const {
      if (NI->is<Node *>())
        return NI->get<Node *>();

      Function *F = NI->get<Function *>();
      Node *ChildN = G->get(*F);
      *NI = ChildN;
      return ChildN;
    }
    pointer operator->() const { return operator*(); }

    iterator &operator++() {
      ++NI;
      return *this;
    }
    iterator operator++(int) {
      iterator prev = *this;
      ++*this;
      return prev;
    }

    iterator &operator--() {
      --NI;
      return *this;
    }
    iterator operator--(int) {
      iterator next = *this;
      --*this;
      return next;
    }
  };

  /// \brief A node in the call graph.
  ///
  /// This represents a single node. It's primary roles are to cache the list of
  /// callees, de-duplicate and provide fast testing of whether a function is
  /// a callee, and facilitate iteration of child nodes in the graph.
  class Node {
    friend class LazyCallGraph;

    LazyCallGraph *G;
    Function &F;
    mutable NodeVectorT Callees;
    SmallPtrSet<Function *, 4> CalleeSet;

    /// \brief Basic constructor implements the scanning of F into Callees and
    /// CalleeSet.
    Node(LazyCallGraph &G, Function &F);

    /// \brief Constructor used when copying a node from one graph to another.
    Node(LazyCallGraph &G, const Node &OtherN);

  public:
    typedef LazyCallGraph::iterator iterator;
{'fraction_non_alphanumeric': 0.11306311958840506, 'fraction_numerical': 0.00025097251850922326, 'mean_word_length': 2.7986177311725453, 'pattern_counts': {'":': 0, '<': 25, '<?xml version=': 0, '>': 35, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '7133996', 'n_tokens_mistral': 4199, 'n_tokens_neox': 4083, 'n_words': 2004}