intermediate changes

ref:cde9a383711a11544ce7e107a78147fb96cc4029

1 files changed, 242 insertions, 0 deletions

diff --git a/contrib/libs/llvm12/include/llvm/Analysis/DominanceFrontierImpl.h b/contrib/libs/llvm12/include/llvm/Analysis/DominanceFrontierImpl.h
new file mode 100644
index 0000000000..58f4087ede
--- /dev/null
+++ b/contrib/libs/llvm12/include/llvm/Analysis/DominanceFrontierImpl.h
@@ -0,0 +1,242 @@
+#pragma once
+
+#ifdef __GNUC__
+#pragma GCC diagnostic push
+#pragma GCC diagnostic ignored "-Wunused-parameter"
+#endif
+
+//===- 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 is the generic implementation of the DominanceFrontier class, which
+// calculate and holds the dominance frontier for a function for.
+//
+// This should be considered deprecated, don't add any more uses of this data
+// structure.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_ANALYSIS_DOMINANCEFRONTIERIMPL_H
+#define LLVM_ANALYSIS_DOMINANCEFRONTIERIMPL_H
+
+#include "llvm/ADT/GraphTraits.h"
+#include "llvm/ADT/SmallPtrSet.h"
+#include "llvm/Analysis/DominanceFrontier.h"
+#include "llvm/Config/llvm-config.h"
+#include "llvm/Support/Debug.h"
+#include "llvm/Support/GenericDomTree.h"
+#include "llvm/Support/raw_ostream.h"
+#include <cassert>
+#include <set>
+#include <utility>
+#include <vector>
+
+namespace llvm {
+
+template <class BlockT>
+class DFCalculateWorkObject {
+public:
+  using DomTreeNodeT = DomTreeNodeBase<BlockT>;
+
+  DFCalculateWorkObject(BlockT *B, BlockT *P, const DomTreeNodeT *N,
+                        const DomTreeNodeT *PN)
+      : currentBB(B), parentBB(P), Node(N), parentNode(PN) {}
+
+  BlockT *currentBB;
+  BlockT *parentBB;
+  const DomTreeNodeT *Node;
+  const DomTreeNodeT *parentNode;
+};
+
+template <class BlockT, bool IsPostDom>
+void DominanceFrontierBase<BlockT, IsPostDom>::removeBlock(BlockT *BB) {
+  assert(find(BB) != end() && "Block is not in DominanceFrontier!");
+  for (iterator I = begin(), E = end(); I != E; ++I)
+    I->second.erase(BB);
+  Frontiers.erase(BB);
+}
+
+template <class BlockT, bool IsPostDom>
+void DominanceFrontierBase<BlockT, IsPostDom>::addToFrontier(iterator I,
+                                                             BlockT *Node) {
+  assert(I != end() && "BB is not in DominanceFrontier!");
+  assert(I->second.count(Node) && "Node is not in DominanceFrontier of BB");
+  I->second.erase(Node);
+}
+
+template <class BlockT, bool IsPostDom>
+void DominanceFrontierBase<BlockT, IsPostDom>::removeFromFrontier(
+    iterator I, BlockT *Node) {
+  assert(I != end() && "BB is not in DominanceFrontier!");
+  assert(I->second.count(Node) && "Node is not in DominanceFrontier of BB");
+  I->second.erase(Node);
+}
+
+template <class BlockT, bool IsPostDom>
+bool DominanceFrontierBase<BlockT, IsPostDom>::compareDomSet(
+    DomSetType &DS1, const DomSetType &DS2) const {
+  std::set<BlockT *> tmpSet;
+  for (BlockT *BB : DS2)
+    tmpSet.insert(BB);
+
+  for (typename DomSetType::const_iterator I = DS1.begin(), E = DS1.end();
+       I != E;) {
+    BlockT *Node = *I++;
+
+    if (tmpSet.erase(Node) == 0)
+      // Node is in DS1 but tnot in DS2.
+      return true;
+  }
+
+  if (!tmpSet.empty()) {
+    // There are nodes that are in DS2 but not in DS1.
+    return true;
+  }
+
+  // DS1 and DS2 matches.
+  return false;
+}
+
+template <class BlockT, bool IsPostDom>
+bool DominanceFrontierBase<BlockT, IsPostDom>::compare(
+    DominanceFrontierBase<BlockT, IsPostDom> &Other) const {
+  DomSetMapType tmpFrontiers;
+  for (typename DomSetMapType::const_iterator I = Other.begin(),
+                                              E = Other.end();
+       I != E; ++I)
+    tmpFrontiers.insert(std::make_pair(I->first, I->second));
+
+  for (typename DomSetMapType::iterator I = tmpFrontiers.begin(),
+                                        E = tmpFrontiers.end();
+       I != E;) {
+    BlockT *Node = I->first;
+    const_iterator DFI = find(Node);
+    if (DFI == end())
+      return true;
+
+    if (compareDomSet(I->second, DFI->second))
+      return true;
+
+    ++I;
+    tmpFrontiers.erase(Node);
+  }
+
+  if (!tmpFrontiers.empty())
+    return true;
+
+  return false;
+}
+
+template <class BlockT, bool IsPostDom>
+void DominanceFrontierBase<BlockT, IsPostDom>::print(raw_ostream &OS) const {
+  for (const_iterator I = begin(), E = end(); I != E; ++I) {
+    OS << "  DomFrontier for BB ";
+    if (I->first)
+      I->first->printAsOperand(OS, false);
+    else
+      OS << " <<exit node>>";
+    OS << " is:\t";
+
+    const std::set<BlockT *> &BBs = I->second;
+
+    for (const BlockT *BB : BBs) {
+      OS << ' ';
+      if (BB)
+        BB->printAsOperand(OS, false);
+      else
+        OS << "<<exit node>>";
+    }
+    OS << '\n';
+  }
+}
+
+#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
+template <class BlockT, bool IsPostDom>
+void DominanceFrontierBase<BlockT, IsPostDom>::dump() const {
+  print(dbgs());
+}
+#endif
+
+template <class BlockT>
+const typename ForwardDominanceFrontierBase<BlockT>::DomSetType &
+ForwardDominanceFrontierBase<BlockT>::calculate(const DomTreeT &DT,
+                                                const DomTreeNodeT *Node) {
+  BlockT *BB = Node->getBlock();
+  DomSetType *Result = nullptr;
+
+  std::vector<DFCalculateWorkObject<BlockT>> workList;
+  SmallPtrSet<BlockT *, 32> visited;
+
+  workList.push_back(DFCalculateWorkObject<BlockT>(BB, nullptr, Node, nullptr));
+  do {
+    DFCalculateWorkObject<BlockT> *currentW = &workList.back();
+    assert(currentW && "Missing work object.");
+
+    BlockT *currentBB = currentW->currentBB;
+    BlockT *parentBB = currentW->parentBB;
+    const DomTreeNodeT *currentNode = currentW->Node;
+    const DomTreeNodeT *parentNode = currentW->parentNode;
+    assert(currentBB && "Invalid work object. Missing current Basic Block");
+    assert(currentNode && "Invalid work object. Missing current Node");
+    DomSetType &S = this->Frontiers[currentBB];
+
+    // Visit each block only once.
+    if (visited.insert(currentBB).second) {
+      // Loop over CFG successors to calculate DFlocal[currentNode]
+      for (const auto Succ : children<BlockT *>(currentBB)) {
+        // Does Node immediately dominate this successor?
+        if (DT[Succ]->getIDom() != currentNode)
+          S.insert(Succ);
+      }
+    }
+
+    // At this point, S is DFlocal.  Now we union in DFup's of our children...
+    // Loop through and visit the nodes that Node immediately dominates (Node's
+    // children in the IDomTree)
+    bool visitChild = false;
+    for (typename DomTreeNodeT::const_iterator NI = currentNode->begin(),
+                                               NE = currentNode->end();
+         NI != NE; ++NI) {
+      DomTreeNodeT *IDominee = *NI;
+      BlockT *childBB = IDominee->getBlock();
+      if (visited.count(childBB) == 0) {
+        workList.push_back(DFCalculateWorkObject<BlockT>(
+            childBB, currentBB, IDominee, currentNode));
+        visitChild = true;
+      }
+    }
+
+    // If all children are visited or there is any child then pop this block
+    // from the workList.
+    if (!visitChild) {
+      if (!parentBB) {
+        Result = &S;
+        break;
+      }
+
+      typename DomSetType::const_iterator CDFI = S.begin(), CDFE = S.end();
+      DomSetType &parentSet = this->Frontiers[parentBB];
+      for (; CDFI != CDFE; ++CDFI) {
+        if (!DT.properlyDominates(parentNode, DT[*CDFI]))
+          parentSet.insert(*CDFI);
+      }
+      workList.pop_back();
+    }
+
+  } while (!workList.empty());
+
+  return *Result;
+}
+
+} // end namespace llvm
+
+#endif // LLVM_ANALYSIS_DOMINANCEFRONTIERIMPL_H
+
+#ifdef __GNUC__
+#pragma GCC diagnostic pop
+#endif