7 files changed, 175 insertions, 96 deletions

diff --git a/include/llvm/Support/BlockFrequency.h b/include/llvm/Support/BlockFrequency.h
index 1b45cc52973f6..2e75cbdd29c16 100644
--- a/include/llvm/Support/BlockFrequency.h
+++ b/include/llvm/Support/BlockFrequency.h
@@ -71,6 +71,10 @@ public:
   bool operator>=(BlockFrequency RHS) const {
     return Frequency >= RHS.Frequency;
   }
+
+  bool operator==(BlockFrequency RHS) const {
+    return Frequency == RHS.Frequency;
+  }
 };
 
 }
diff --git a/include/llvm/Support/Compiler.h b/include/llvm/Support/Compiler.h
index be9e465400165..b19e37235df57 100644
--- a/include/llvm/Support/Compiler.h
+++ b/include/llvm/Support/Compiler.h
@@ -493,4 +493,14 @@ void AnnotateIgnoreWritesEnd(const char *file, int line);
 #define LLVM_THREAD_LOCAL
 #endif
 
+/// \macro LLVM_ENABLE_EXCEPTIONS
+/// \brief Whether LLVM is built with exception support.
+#if __has_feature(cxx_exceptions)
+#define LLVM_ENABLE_EXCEPTIONS 1
+#elif defined(__GNUC__) && defined(__EXCEPTIONS)
+#define LLVM_ENABLE_EXCEPTIONS 1
+#elif defined(_MSC_VER) && defined(_CPPUNWIND)
+#define LLVM_ENABLE_EXCEPTIONS 1
+#endif
+
 #endif
diff --git a/include/llvm/Support/DynamicLibrary.h b/include/llvm/Support/DynamicLibrary.h
index a8874a10d461a..469d5dfad0627 100644
--- a/include/llvm/Support/DynamicLibrary.h
+++ b/include/llvm/Support/DynamicLibrary.h
@@ -88,6 +88,22 @@ namespace sys {
       return !getPermanentLibrary(Filename, ErrMsg).isValid();
     }
 
+    enum SearchOrdering {
+      /// SO_Linker - Search as a call to dlsym(dlopen(NULL)) would when
+      /// DynamicLibrary::getPermanentLibrary(NULL) has been called or
+      /// search the list of explcitly loaded symbols if not.
+      SO_Linker,
+      /// SO_LoadedFirst - Search all loaded libraries, then as SO_Linker would.
+      SO_LoadedFirst,
+      /// SO_LoadedLast - Search as SO_Linker would, then loaded libraries.
+      /// Only useful to search if libraries with RTLD_LOCAL have been added.
+      SO_LoadedLast,
+      /// SO_LoadOrder - Or this in to search libraries in the ordered loaded.
+      /// The default bahaviour is to search loaded libraries in reverse.
+      SO_LoadOrder = 4
+    };
+    static SearchOrdering SearchOrder; // = SO_Linker
+
     /// This function will search through all previously loaded dynamic
     /// libraries for the symbol \p symbolName. If it is found, the address of
     /// that symbol is returned. If not, null is returned. Note that this will
diff --git a/include/llvm/Support/ErrorHandling.h b/include/llvm/Support/ErrorHandling.h
index 7c1edd8015712..b45f6348390e2 100644
--- a/include/llvm/Support/ErrorHandling.h
+++ b/include/llvm/Support/ErrorHandling.h
@@ -78,12 +78,48 @@ LLVM_ATTRIBUTE_NORETURN void report_fatal_error(StringRef reason,
 LLVM_ATTRIBUTE_NORETURN void report_fatal_error(const Twine &reason,
                                                 bool gen_crash_diag = true);
 
-  /// This function calls abort(), and prints the optional message to stderr.
-  /// Use the llvm_unreachable macro (that adds location info), instead of
-  /// calling this function directly.
-  LLVM_ATTRIBUTE_NORETURN void
-  llvm_unreachable_internal(const char *msg=nullptr, const char *file=nullptr,
-                            unsigned line=0);
+/// Installs a new bad alloc error handler that should be used whenever a
+/// bad alloc error, e.g. failing malloc/calloc, is encountered by LLVM.
+///
+/// The user can install a bad alloc handler, in order to define the behavior
+/// in case of failing allocations, e.g. throwing an exception. Note that this
+/// handler must not trigger any additional allocations itself.
+///
+/// If no error handler is installed the default is to print the error message
+/// to stderr, and call exit(1).  If an error handler is installed then it is
+/// the handler's responsibility to log the message, it will no longer be
+/// printed to stderr.  If the error handler returns, then exit(1) will be
+/// called.
+///
+///
+/// \param user_data - An argument which will be passed to the installed error
+/// handler.
+void install_bad_alloc_error_handler(fatal_error_handler_t handler,
+                                     void *user_data = nullptr);
+
+/// Restores default bad alloc error handling behavior.
+void remove_bad_alloc_error_handler();
+
+/// Reports a bad alloc error, calling any user defined bad alloc
+/// error handler. In contrast to the generic 'report_fatal_error'
+/// functions, this function is expected to return, e.g. the user
+/// defined error handler throws an exception.
+///
+/// Note: When throwing an exception in the bad alloc handler, make sure that
+/// the following unwind succeeds, e.g. do not trigger additional allocations
+/// in the unwind chain.
+///
+/// If no error handler is installed (default), then a bad_alloc exception
+/// is thrown if LLVM is compiled with exception support, otherwise an assertion
+/// is called.
+void report_bad_alloc_error(const char *Reason, bool GenCrashDiag = true);
+
+/// This function calls abort(), and prints the optional message to stderr.
+/// Use the llvm_unreachable macro (that adds location info), instead of
+/// calling this function directly.
+LLVM_ATTRIBUTE_NORETURN void
+llvm_unreachable_internal(const char *msg = nullptr, const char *file = nullptr,
+                          unsigned line = 0);
 }
 
 /// Marks that the current location is not supposed to be reachable.
diff --git a/include/llvm/Support/GenericDomTreeConstruction.h b/include/llvm/Support/GenericDomTreeConstruction.h
index 9edf03aa36210..a0fec668e05ca 100644
--- a/include/llvm/Support/GenericDomTreeConstruction.h
+++ b/include/llvm/Support/GenericDomTreeConstruction.h
@@ -32,6 +32,20 @@
 namespace llvm {
 namespace DomTreeBuilder {
 
+template <typename NodePtr, bool Inverse>
+struct ChildrenGetter {
+  static auto Get(NodePtr N) -> decltype(reverse(children<NodePtr>(N))) {
+    return reverse(children<NodePtr>(N));
+  }
+};
+
+template <typename NodePtr>
+struct ChildrenGetter<NodePtr, true> {
+  static auto Get(NodePtr N) -> decltype(inverse_children<NodePtr>(N)) {
+    return inverse_children<NodePtr>(N);
+  }
+};
+
 // Information record used by Semi-NCA during tree construction.
 template <typename NodeT>
 struct SemiNCAInfo {
@@ -45,6 +59,7 @@ struct SemiNCAInfo {
     unsigned Semi = 0;
     NodePtr Label = nullptr;
     NodePtr IDom = nullptr;
+    SmallVector<NodePtr, 2> ReverseChildren;
   };
 
   std::vector<NodePtr> NumToNode;
@@ -79,66 +94,49 @@ struct SemiNCAInfo {
         .get();
   }
 
-  // External storage for depth first iterator that reuses the info lookup map
-  // SemiNCAInfo already has. We don't have a set, but a map instead, so we are
-  // converting the one argument insert calls.
-  struct df_iterator_dom_storage {
-   public:
-    using BaseSet = decltype(NodeToInfo);
-    df_iterator_dom_storage(BaseSet &Storage) : Storage(Storage) {}
-
-    using iterator = typename BaseSet::iterator;
-    std::pair<iterator, bool> insert(NodePtr N) {
-      return Storage.insert({N, InfoRec()});
-    }
-    void completed(NodePtr) {}
-
-   private:
-    BaseSet &Storage;
-  };
-
-  df_iterator_dom_storage getStorage() { return {NodeToInfo}; }
+  static bool AlwaysDescend(NodePtr, NodePtr) { return true; }
 
-  unsigned runReverseDFS(NodePtr V, unsigned N) {
-    auto DFStorage = getStorage();
+  // Custom DFS implementation which can skip nodes based on a provided
+  // predicate. It also collects ReverseChildren so that we don't have to spend
+  // time getting predecessors in SemiNCA.
+  template <bool Inverse, typename DescendCondition>
+  unsigned runDFS(NodePtr V, unsigned LastNum, DescendCondition Condition,
+                  unsigned AttachToNum) {
+    assert(V);
+    SmallVector<NodePtr, 64> WorkList = {V};
+    if (NodeToInfo.count(V) != 0) NodeToInfo[V].Parent = AttachToNum;
 
-    bool IsChildOfArtificialExit = (N != 0);
-    for (auto I = idf_ext_begin(V, DFStorage), E = idf_ext_end(V, DFStorage);
-         I != E; ++I) {
-      NodePtr BB = *I;
+    while (!WorkList.empty()) {
+      const NodePtr BB = WorkList.pop_back_val();
       auto &BBInfo = NodeToInfo[BB];
-      BBInfo.DFSNum = BBInfo.Semi = ++N;
+
+      // Visited nodes always have positive DFS numbers.
+      if (BBInfo.DFSNum != 0) continue;
+      BBInfo.DFSNum = BBInfo.Semi = ++LastNum;
       BBInfo.Label = BB;
-      // Set the parent to the top of the visited stack.  The stack includes us,
-      // and is 1 based, so we subtract to account for both of these.
-      if (I.getPathLength() > 1)
-        BBInfo.Parent = NodeToInfo[I.getPath(I.getPathLength() - 2)].DFSNum;
-      NumToNode.push_back(BB);  // NumToNode[n] = V;
+      NumToNode.push_back(BB);
+
+      for (const NodePtr Succ : ChildrenGetter<NodePtr, Inverse>::Get(BB)) {
+        const auto SIT = NodeToInfo.find(Succ);
+        // Don't visit nodes more than once but remember to collect
+        // RerverseChildren.
+        if (SIT != NodeToInfo.end() && SIT->second.DFSNum != 0) {
+          if (Succ != BB) SIT->second.ReverseChildren.push_back(BB);
+          continue;
+        }
 
-      if (IsChildOfArtificialExit)
-        BBInfo.Parent = 1;
+        if (!Condition(BB, Succ)) continue;
 
-      IsChildOfArtificialExit = false;
+        // It's fine to add Succ to the map, because we know that it will be
+        // visited later.
+        auto &SuccInfo = NodeToInfo[Succ];
+        WorkList.push_back(Succ);
+        SuccInfo.Parent = LastNum;
+        SuccInfo.ReverseChildren.push_back(BB);
+      }
     }
-    return N;
-  }
-
-  unsigned runForwardDFS(NodePtr V, unsigned N) {
-    auto DFStorage = getStorage();
 
-    for (auto I = df_ext_begin(V, DFStorage), E = df_ext_end(V, DFStorage);
-         I != E; ++I) {
-      NodePtr BB = *I;
-      auto &BBInfo = NodeToInfo[BB];
-      BBInfo.DFSNum = BBInfo.Semi = ++N;
-      BBInfo.Label = BB;
-      // Set the parent to the top of the visited stack.  The stack includes us,
-      // and is 1 based, so we subtract to account for both of these.
-      if (I.getPathLength() > 1)
-        BBInfo.Parent = NodeToInfo[I.getPath(I.getPathLength() - 2)].DFSNum;
-      NumToNode.push_back(BB);  // NumToNode[n] = V;
-    }
-    return N;
+    return LastNum;
   }
 
   NodePtr eval(NodePtr VIn, unsigned LastLinked) {
@@ -181,31 +179,14 @@ struct SemiNCAInfo {
 
   template <typename NodeType>
   void runSemiNCA(DomTreeT &DT, unsigned NumBlocks) {
-    unsigned N = 0;
-    NumToNode.push_back(nullptr);
-
-    bool MultipleRoots = (DT.Roots.size() > 1);
-    if (MultipleRoots) {
-      auto &BBInfo = NodeToInfo[nullptr];
-      BBInfo.DFSNum = BBInfo.Semi = ++N;
-      BBInfo.Label = nullptr;
-
-      NumToNode.push_back(nullptr); // NumToNode[n] = V;
-    }
-
     // Step #1: Number blocks in depth-first order and initialize variables used
     // in later stages of the algorithm.
-    if (DT.isPostDominator()){
-      for (unsigned i = 0, e = static_cast<unsigned>(DT.Roots.size());
-           i != e; ++i)
-        N = runReverseDFS(DT.Roots[i], N);
-    } else {
-      N = runForwardDFS(DT.Roots[0], N);
-    }
+    const unsigned N = doFullDFSWalk(DT, AlwaysDescend);
 
     // It might be that some blocks did not get a DFS number (e.g., blocks of
     // infinite loops). In these cases an artificial exit node is required.
-    MultipleRoots |= (DT.isPostDominator() && N != NumBlocks);
+    const bool MultipleRoots =
+        DT.Roots.size() > 1 || (DT.isPostDominator() && N != NumBlocks);
 
     // Initialize IDoms to spanning tree parents.
     for (unsigned i = 1; i <= N; ++i) {
@@ -221,7 +202,7 @@ struct SemiNCAInfo {
 
       // Initialize the semi dominator to point to the parent node.
       WInfo.Semi = WInfo.Parent;
-      for (const auto &N : inverse_children<NodeType>(W))
+      for (const auto &N : WInfo.ReverseChildren)
         if (NodeToInfo.count(N)) {  // Only if this predecessor is reachable!
           unsigned SemiU = NodeToInfo[eval(N, i + 1)].Semi;
           if (SemiU < WInfo.Semi)
@@ -279,14 +260,27 @@ struct SemiNCAInfo {
     }
   }
 
-  void doFullDFSWalk(const DomTreeT &DT) {
-    NumToNode.push_back(nullptr);
+  template <typename DescendCondition>
+  unsigned doFullDFSWalk(const DomTreeT &DT, DescendCondition DC) {
     unsigned Num = 0;
-    for (auto *Root : DT.Roots)
-      if (!DT.isPostDominator())
-        Num = runForwardDFS(Root, Num);
-      else
-        Num = runReverseDFS(Root, Num);
+    NumToNode.push_back(nullptr);
+
+    if (DT.Roots.size() > 1) {
+      auto &BBInfo = NodeToInfo[nullptr];
+      BBInfo.DFSNum = BBInfo.Semi = ++Num;
+      BBInfo.Label = nullptr;
+
+      NumToNode.push_back(nullptr);  // NumToNode[n] = V;
+    }
+
+    if (DT.isPostDominator()) {
+      for (auto *Root : DT.Roots) Num = runDFS<true>(Root, Num, DC, 1);
+    } else {
+      assert(DT.Roots.size() == 1);
+      Num = runDFS<false>(DT.Roots[0], Num, DC, Num);
+    }
+
+    return Num;
   }
 
   static void PrintBlockOrNullptr(raw_ostream &O, NodePtr Obj) {
@@ -299,7 +293,7 @@ struct SemiNCAInfo {
   // Checks if the tree contains all reachable nodes in the input graph.
   bool verifyReachability(const DomTreeT &DT) {
     clear();
-    doFullDFSWalk(DT);
+    doFullDFSWalk(DT, AlwaysDescend);
 
     for (auto &NodeToTN : DT.DomTreeNodes) {
       const TreeNodePtr TN = NodeToTN.second.get();
@@ -356,7 +350,7 @@ struct SemiNCAInfo {
   //     NCD(From, To) == IDom(To) or To.
   bool verifyNCD(const DomTreeT &DT) {
     clear();
-    doFullDFSWalk(DT);
+    doFullDFSWalk(DT, AlwaysDescend);
 
     for (auto &BlockToInfo : NodeToInfo) {
       auto &Info = BlockToInfo.second;
@@ -440,8 +434,9 @@ struct SemiNCAInfo {
       if (!BB || TN->getChildren().empty()) continue;
 
       clear();
-      NodeToInfo.insert({BB, {}});
-      doFullDFSWalk(DT);
+      doFullDFSWalk(DT, [BB](NodePtr From, NodePtr To) {
+        return From != BB && To != BB;
+      });
 
       for (TreeNodePtr Child : TN->getChildren())
         if (NodeToInfo.count(Child->getBlock()) != 0) {
@@ -473,8 +468,10 @@ struct SemiNCAInfo {
       const auto &Siblings = TN->getChildren();
       for (const TreeNodePtr N : Siblings) {
         clear();
-        NodeToInfo.insert({N->getBlock(), {}});
-        doFullDFSWalk(DT);
+        NodePtr BBN = N->getBlock();
+        doFullDFSWalk(DT, [BBN](NodePtr From, NodePtr To) {
+          return From != BBN && To != BBN;
+        });
 
         for (const TreeNodePtr S : Siblings) {
           if (S == N) continue;
diff --git a/include/llvm/Support/ReverseIteration.h b/include/llvm/Support/ReverseIteration.h
new file mode 100644
index 0000000000000..cb97b60f06dd9
--- /dev/null
+++ b/include/llvm/Support/ReverseIteration.h
@@ -0,0 +1,17 @@
+#ifndef LLVM_SUPPORT_REVERSEITERATION_H
+#define LLVM_SUPPORT_REVERSEITERATION_H
+
+#include "llvm/Config/abi-breaking.h"
+
+namespace llvm {
+#if LLVM_ENABLE_ABI_BREAKING_CHECKS
+template <class T = void> struct ReverseIterate { static bool value; };
+#if LLVM_ENABLE_REVERSE_ITERATION
+template <class T> bool ReverseIterate<T>::value = true;
+#else
+template <class T> bool ReverseIterate<T>::value = false;
+#endif
+#endif
+}
+
+#endif
diff --git a/include/llvm/Support/UnicodeCharRanges.h b/include/llvm/Support/UnicodeCharRanges.h
index d4d4d8eb84a4b..4c655833b3967 100644
--- a/include/llvm/Support/UnicodeCharRanges.h
+++ b/include/llvm/Support/UnicodeCharRanges.h
@@ -18,11 +18,11 @@
 #include "llvm/Support/raw_ostream.h"
 #include <algorithm>
 
+#define DEBUG_TYPE "unicode"
+
 namespace llvm {
 namespace sys {
 
-#define DEBUG_TYPE "unicode"
-
 /// \brief Represents a closed range of Unicode code points [Lower, Upper].
 struct UnicodeCharRange {
   uint32_t Lower;
@@ -99,10 +99,9 @@ private:
   const CharRanges Ranges;
 };
 
-#undef DEBUG_TYPE // "unicode"
-
 } // namespace sys
 } // namespace llvm
 
+#undef DEBUG_TYPE // "unicode"
 
 #endif // LLVM_SUPPORT_UNICODECHARRANGES_H