Subversion Repositories QNX 8.QNX8 LLVM/Clang compiler suite

//===- llvm/Analysis/DominanceFrontier.h - Dominator Frontiers --*- 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 DominanceFrontier class, which calculate and holds the

// dominance frontier for a function.

//

// This should be considered deprecated, don't add any more uses of this data

// structure.

//

//===----------------------------------------------------------------------===//

#ifndef LLVM_ANALYSIS_DOMINANCEFRONTIER_H

#define LLVM_ANALYSIS_DOMINANCEFRONTIER_H

#include "llvm/ADT/GraphTraits.h"

#include "llvm/Config/llvm-config.h"

#include "llvm/IR/PassManager.h"

#include "llvm/Pass.h"

#include "llvm/Support/GenericDomTree.h"

#include <cassert>

#include <map>

#include <set>

#include <utility>

namespace llvm {

class Function;

class raw_ostream;

//===----------------------------------------------------------------------===//

/// DominanceFrontierBase - Common base class for computing forward and inverse

/// dominance frontiers for a function.

///

template <class BlockT, bool IsPostDom>

class DominanceFrontierBase {

public:

  using DomSetType = std::set<BlockT *>;                // Dom set for a bb

  using DomSetMapType = std::map<BlockT *, DomSetType>; // Dom set map

protected:

  using BlockTraits = GraphTraits<BlockT *>;

  DomSetMapType Frontiers;

  // Postdominators can have multiple roots.

  SmallVector<BlockT *, IsPostDom ? 4 : 1> Roots;

  static constexpr bool IsPostDominators = IsPostDom;

public:

  DominanceFrontierBase() = default;

  /// 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 SmallVectorImpl<BlockT *> &getRoots() const { return Roots; }

  BlockT *getRoot() const {

    assert(Roots.size() == 1 && "Should always have entry node!");

    return Roots[0];

  }

  /// isPostDominator - Returns true if analysis based of postdoms

  bool isPostDominator() const {

    return IsPostDominators;

  }

  void releaseMemory() {

    Frontiers.clear();

  }

  // Accessor interface:

  using iterator = typename DomSetMapType::iterator;

  using const_iterator = typename DomSetMapType::const_iterator;

  iterator begin() { return Frontiers.begin(); }

  const_iterator begin() const { return Frontiers.begin(); }

  iterator end() { return Frontiers.end(); }

  const_iterator end() const { return Frontiers.end(); }

  iterator find(BlockT *B) { return Frontiers.find(B); }

  const_iterator find(BlockT *B) const { return Frontiers.find(B); }

  iterator addBasicBlock(BlockT *BB, const DomSetType &frontier) {

    assert(find(BB) == end() && "Block already in DominanceFrontier!");

    return Frontiers.insert(std::make_pair(BB, frontier)).first;

  }

  /// removeBlock - Remove basic block BB's frontier.

  void removeBlock(BlockT *BB);

  void addToFrontier(iterator I, BlockT *Node);

  void removeFromFrontier(iterator I, BlockT *Node);

  /// compareDomSet - Return false if two domsets match. Otherwise

  /// return true;

  bool compareDomSet(DomSetType &DS1, const DomSetType &DS2) const;

  /// compare - Return true if the other dominance frontier base matches

  /// this dominance frontier base. Otherwise return false.

  bool compare(DominanceFrontierBase &Other) const;

  /// print - Convert to human readable form

  ///

  void print(raw_ostream &OS) const;

  /// dump - Dump the dominance frontier to dbgs().

#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)

  void dump() const;

#endif

};

//===-------------------------------------

/// DominanceFrontier Class - Concrete subclass of DominanceFrontierBase that is

/// used to compute a forward dominator frontiers.

///

template <class BlockT>

class ForwardDominanceFrontierBase

    : public DominanceFrontierBase<BlockT, false> {

private:

  using BlockTraits = GraphTraits<BlockT *>;

public:

  using DomTreeT = DomTreeBase<BlockT>;

  using DomTreeNodeT = DomTreeNodeBase<BlockT>;

  using DomSetType = typename DominanceFrontierBase<BlockT, false>::DomSetType;

  void analyze(DomTreeT &DT) {

    assert(DT.root_size() == 1 &&

           "Only one entry block for forward domfronts!");

    this->Roots = {DT.getRoot()};

    calculate(DT, DT[this->Roots[0]]);

  }

  const DomSetType &calculate(const DomTreeT &DT, const DomTreeNodeT *Node);

};

class DominanceFrontier : public ForwardDominanceFrontierBase<BasicBlock> {

public:

  using DomTreeT = DomTreeBase<BasicBlock>;

  using DomTreeNodeT = DomTreeNodeBase<BasicBlock>;

  using DomSetType = DominanceFrontierBase<BasicBlock, false>::DomSetType;

  using iterator = DominanceFrontierBase<BasicBlock, false>::iterator;

  using const_iterator =

      DominanceFrontierBase<BasicBlock, false>::const_iterator;

  /// Handle invalidation explicitly.

  bool invalidate(Function &F, const PreservedAnalyses &PA,

                  FunctionAnalysisManager::Invalidator &);

};

class DominanceFrontierWrapperPass : public FunctionPass {

  DominanceFrontier DF;

public:

  static char ID; // Pass ID, replacement for typeid

  DominanceFrontierWrapperPass();

  DominanceFrontier &getDominanceFrontier() { return DF; }

  const DominanceFrontier &getDominanceFrontier() const { return DF;  }

  void releaseMemory() override;

  bool runOnFunction(Function &) override;

  void getAnalysisUsage(AnalysisUsage &AU) const override;

  void print(raw_ostream &OS, const Module * = nullptr) const override;

  void dump() const;

};

extern template class DominanceFrontierBase<BasicBlock, false>;

extern template class DominanceFrontierBase<BasicBlock, true>;

extern template class ForwardDominanceFrontierBase<BasicBlock>;

/// Analysis pass which computes a \c DominanceFrontier.

class DominanceFrontierAnalysis

    : public AnalysisInfoMixin<DominanceFrontierAnalysis> {

  friend AnalysisInfoMixin<DominanceFrontierAnalysis>;

  static AnalysisKey Key;

public:

  /// Provide the result type for this analysis pass.

  using Result = DominanceFrontier;

  /// Run the analysis pass over a function and produce a dominator tree.

  DominanceFrontier run(Function &F, FunctionAnalysisManager &AM);

};

/// Printer pass for the \c DominanceFrontier.

class DominanceFrontierPrinterPass

    : public PassInfoMixin<DominanceFrontierPrinterPass> {

  raw_ostream &OS;

public:

  explicit DominanceFrontierPrinterPass(raw_ostream &OS);

  PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);

};

} // end namespace llvm

#endif // LLVM_ANALYSIS_DOMINANCEFRONTIER_H