Import prebuilt clang toolchain for linux.
diff --git a/linux-x64/clang/include/llvm/Analysis/DominanceFrontierImpl.h b/linux-x64/clang/include/llvm/Analysis/DominanceFrontierImpl.h
new file mode 100644
index 0000000..dffb2e0
--- /dev/null
+++ b/linux-x64/clang/include/llvm/Analysis/DominanceFrontierImpl.h
@@ -0,0 +1,231 @@
+//===- llvm/Analysis/DominanceFrontier.h - Dominator Frontiers --*- C++ -*-===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// 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/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