<commit_before>//===- GenericDomTree.h - Generic dominator trees for graphs ----*- C++ -*-===//
//
//                     The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
/// \file
///
/// This file defines a set of templates that efficiently compute a dominator
/// tree over a generic graph. This is used typically in LLVM for fast
/// dominance queries on the CFG, but is fully generic w.r.t. the underlying
/// graph types.
///
//===----------------------------------------------------------------------===//

#ifndef LLVM_SUPPORT_GENERICDOMTREE_H
#define LLVM_SUPPORT_GENERICDOMTREE_H

#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/DepthFirstIterator.h"
#include "llvm/ADT/GraphTraits.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/Support/Compiler.h"
#include "llvm/Support/raw_ostream.h"
#include <algorithm>

namespace llvm {

/// \brief Base class that other, more interesting dominator analyses
/// inherit from.
template <class NodeT> class DominatorBase {
protected:
  std::vector<NodeT *> Roots;
  bool IsPostDominators;
  explicit DominatorBase(bool isPostDom)
      : Roots(), IsPostDominators(isPostDom) {}
  DominatorBase(DominatorBase &&Arg)
      : Roots(std::move(Arg.Roots)),
        IsPostDominators(std::move(Arg.IsPostDominators)) {
    Arg.Roots.clear();
  }
  DominatorBase &operator=(DominatorBase &&RHS) {
    Roots = std::move(RHS.Roots);
    IsPostDominators = std::move(RHS.IsPostDominators);
    RHS.Roots.clear();
    return *this;
  }

public:
  /// getRoots - Return the root blocks of the current CFG.  This may include
  /// multiple blocks if we are computing post dominators.  For forward
  /// dominators, this will always be a single block (the entry node).
  ///
  const std::vector<NodeT *> &getRoots() const { return Roots; }

  /// isPostDominator - Returns true if analysis based of postdoms
  ///
  bool isPostDominator() const { return IsPostDominators; }
};

template <class NodeT> class DominatorTreeBase;
struct PostDominatorTree;

/// \brief Base class for the actual dominator tree node.
template <class NodeT> class DomTreeNodeBase {
  NodeT *TheBB;
  DomTreeNodeBase<NodeT> *IDom;
  std::vector<DomTreeNodeBase<NodeT> *> Children;
  mutable int DFSNumIn, DFSNumOut;

  template <class N> friend class DominatorTreeBase;
  friend struct PostDominatorTree;

public:
  typedef typename std::vector<DomTreeNodeBase<NodeT> *>::iterator iterator;
  typedef typename std::vector<DomTreeNodeBase<NodeT> *>::const_iterator
      const_iterator;

  iterator begin() { return Children.begin(); }
  iterator end() { return Children.end(); }
  const_iterator begin() const { return Children.begin(); }
  const_iterator end() const { return Children.end(); }

  NodeT *getBlock() const { return TheBB; }
  DomTreeNodeBase<NodeT> *getIDom() const { return IDom; }
  const std::vector<DomTreeNodeBase<NodeT> *> &getChildren() const {
    return Children;
  }

  DomTreeNodeBase(NodeT *BB, DomTreeNodeBase<NodeT> *iDom)
      : TheBB(BB), IDom(iDom), DFSNumIn(-1), DFSNumOut(-1) {}

  std::unique_ptr<DomTreeNodeBase<NodeT>>
  addChild(std::unique_ptr<DomTreeNodeBase<NodeT>> C) {
    Children.push_back(C.get());
    return C;
  }

  size_t getNumChildren() const { return Children.size(); }

  void clearAllChildren() { Children.clear(); }

  bool compare(const DomTreeNodeBase<NodeT> *Other) const {
    if (getNumChildren() != Other->getNumChildren())
      return true;

    SmallPtrSet<const NodeT *, 4> OtherChildren;
    for (const_iterator I = Other->begin(), E = Other->end(); I != E; ++I) {
      const NodeT *Nd = (*I)->getBlock();
      OtherChildren.insert(Nd);
    }

    for (const_iterator I = begin(), E = end(); I != E; ++I) {
      const NodeT *N = (*I)->getBlock();
      if (OtherChildren.count(N) == 0)
        return true;
    }
    return false;
  }

  void setIDom(DomTreeNodeBase<NodeT> *NewIDom) {
    assert(IDom && "No immediate dominator?");
    if (IDom != NewIDom) {
      typename std::vector<DomTreeNodeBase<NodeT> *>::iterator I =
          std::find(IDom->Children.begin(), IDom->Children.end(), this);
      assert(I != IDom->Children.end() &&
             "Not in immediate dominator children set!");
      // I am no longer your child...
      IDom->Children.erase(I);

      // Switch to new dominator
      IDom = NewIDom;
      IDom->Children.push_back(this);
    }
  }

  /// getDFSNumIn/getDFSNumOut - These are an internal implementation detail, do
  /// not call them.
  unsigned getDFSNumIn() const { return DFSNumIn; }
  unsigned getDFSNumOut() const { return DFSNumOut; }

private:
  // Return true if this node is dominated by other. Use this only if DFS info
  // is valid.
  bool DominatedBy(const DomTreeNodeBase<NodeT> *other) const {
    return this->DFSNumIn >= other->DFSNumIn &&
           this->DFSNumOut <= other->DFSNumOut;
  }
};

template <class NodeT>
raw_ostream &operator<<(raw_ostream &o, const DomTreeNodeBase<NodeT> *Node) {
  if (Node->getBlock())
    Node->getBlock()->printAsOperand(o, false);
  else
    o << " <<exit node>>";<commit_msg>Update header documentation for API deliberately made public<commit_after>//===- GenericDomTree.h - Generic dominator trees for graphs ----*- C++ -*-===//
//
//                     The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
/// \file
///
/// This file defines a set of templates that efficiently compute a dominator
/// tree over a generic graph. This is used typically in LLVM for fast
/// dominance queries on the CFG, but is fully generic w.r.t. the underlying
/// graph types.
///
//===----------------------------------------------------------------------===//

#ifndef LLVM_SUPPORT_GENERICDOMTREE_H
#define LLVM_SUPPORT_GENERICDOMTREE_H

#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/DepthFirstIterator.h"
#include "llvm/ADT/GraphTraits.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/Support/Compiler.h"
#include "llvm/Support/raw_ostream.h"
#include <algorithm>

namespace llvm {

/// \brief Base class that other, more interesting dominator analyses
/// inherit from.
template <class NodeT> class DominatorBase {
protected:
  std::vector<NodeT *> Roots;
  bool IsPostDominators;
  explicit DominatorBase(bool isPostDom)
      : Roots(), IsPostDominators(isPostDom) {}
  DominatorBase(DominatorBase &&Arg)
      : Roots(std::move(Arg.Roots)),
        IsPostDominators(std::move(Arg.IsPostDominators)) {
    Arg.Roots.clear();
  }
  DominatorBase &operator=(DominatorBase &&RHS) {
    Roots = std::move(RHS.Roots);
    IsPostDominators = std::move(RHS.IsPostDominators);
    RHS.Roots.clear();
    return *this;
  }

public:
  /// getRoots - Return the root blocks of the current CFG.  This may include
  /// multiple blocks if we are computing post dominators.  For forward
  /// dominators, this will always be a single block (the entry node).
  ///
  const std::vector<NodeT *> &getRoots() const { return Roots; }

  /// isPostDominator - Returns true if analysis based of postdoms
  ///
  bool isPostDominator() const { return IsPostDominators; }
};

template <class NodeT> class DominatorTreeBase;
struct PostDominatorTree;

/// \brief Base class for the actual dominator tree node.
template <class NodeT> class DomTreeNodeBase {
  NodeT *TheBB;
  DomTreeNodeBase<NodeT> *IDom;
  std::vector<DomTreeNodeBase<NodeT> *> Children;
  mutable int DFSNumIn, DFSNumOut;

  template <class N> friend class DominatorTreeBase;
  friend struct PostDominatorTree;

public:
  typedef typename std::vector<DomTreeNodeBase<NodeT> *>::iterator iterator;
  typedef typename std::vector<DomTreeNodeBase<NodeT> *>::const_iterator
      const_iterator;

  iterator begin() { return Children.begin(); }
  iterator end() { return Children.end(); }
  const_iterator begin() const { return Children.begin(); }
  const_iterator end() const { return Children.end(); }

  NodeT *getBlock() const { return TheBB; }
  DomTreeNodeBase<NodeT> *getIDom() const { return IDom; }
  const std::vector<DomTreeNodeBase<NodeT> *> &getChildren() const {
    return Children;
  }

  DomTreeNodeBase(NodeT *BB, DomTreeNodeBase<NodeT> *iDom)
      : TheBB(BB), IDom(iDom), DFSNumIn(-1), DFSNumOut(-1) {}

  std::unique_ptr<DomTreeNodeBase<NodeT>>
  addChild(std::unique_ptr<DomTreeNodeBase<NodeT>> C) {
    Children.push_back(C.get());
    return C;
  }

  size_t getNumChildren() const { return Children.size(); }

  void clearAllChildren() { Children.clear(); }

  bool compare(const DomTreeNodeBase<NodeT> *Other) const {
    if (getNumChildren() != Other->getNumChildren())
      return true;

    SmallPtrSet<const NodeT *, 4> OtherChildren;
    for (const_iterator I = Other->begin(), E = Other->end(); I != E; ++I) {
      const NodeT *Nd = (*I)->getBlock();
      OtherChildren.insert(Nd);
    }

    for (const_iterator I = begin(), E = end(); I != E; ++I) {
      const NodeT *N = (*I)->getBlock();
      if (OtherChildren.count(N) == 0)
        return true;
    }
    return false;
  }

  void setIDom(DomTreeNodeBase<NodeT> *NewIDom) {
    assert(IDom && "No immediate dominator?");
    if (IDom != NewIDom) {
      typename std::vector<DomTreeNodeBase<NodeT> *>::iterator I =
          std::find(IDom->Children.begin(), IDom->Children.end(), this);
      assert(I != IDom->Children.end() &&
             "Not in immediate dominator children set!");
      // I am no longer your child...
      IDom->Children.erase(I);

      // Switch to new dominator
      IDom = NewIDom;
      IDom->Children.push_back(this);
    }
  }

  /// getDFSNumIn/getDFSNumOut - These return the DFS visitation order for nodes
  /// in the dominator tree. They are only guaranteed valid if
  /// updateDFSNumbers() has been called.
  unsigned getDFSNumIn() const { return DFSNumIn; }
  unsigned getDFSNumOut() const { return DFSNumOut; }

private:
  // Return true if this node is dominated by other. Use this only if DFS info
  // is valid.
  bool DominatedBy(const DomTreeNodeBase<NodeT> *other) const {
    return this->DFSNumIn >= other->DFSNumIn &&
           this->DFSNumOut <= other->DFSNumOut;
  }
};

template <class NodeT>
raw_ostream &operator<<(raw_ostream &o, const DomTreeNodeBase<NodeT> *Node) {
  if (Node->getBlock())
    Node->getBlock()->printAsOperand(o, false);
  else
    o << " <<exit node>>";
{'fraction_non_alphanumeric': 0.15989210306018045, 'fraction_numerical': 0.0007441168263417357, 'mean_word_length': 3.18854694195559, 'pattern_counts': {'":': 0, '<': 77, '<?xml version=': 0, '>': 103, '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': '6703407', 'n_tokens_mistral': 3401, 'n_tokens_neox': 3376, 'n_words': 910}