Index: include/llvm/Support/Regex.h
===================================================================
--- include/llvm/Support/Regex.h
+++ include/llvm/Support/Regex.h
@@ -90,6 +90,11 @@
     /// expression that matches Str and only Str.
     static bool isLiteralERE(StringRef Str);
 
+    /// \brief If this function returns true, Str is a simple wildcard with
+    /// regular chars and optional star and dot wildcards like foo*b.r. This is a
+    /// common case for sanitizers blacklists.
+    static bool isSimpleWildcard(StringRef Str);
+
     /// \brief Turn String into a regex by escaping its special characters.
     static std::string escape(StringRef String);
 
Index: lib/Support/Regex.cpp
===================================================================
--- lib/Support/Regex.cpp
+++ lib/Support/Regex.cpp
@@ -185,6 +185,7 @@
 
 // These are the special characters matched in functions like "p_ere_exp".
 static const char RegexMetachars[] = "()^$|*+?.[]\\{}";
+static const char RegexAdvancedMetachars[] = "()^$|+?[]\\{}";
 
 bool Regex::isLiteralERE(StringRef Str) {
   // Check for regex metacharacters.  This list was derived from our regex
@@ -193,6 +194,11 @@
   return Str.find_first_of(RegexMetachars) == StringRef::npos;
 }
 
+bool Regex::isSimpleWildcard(StringRef Str) {
+  // Check for regex metacharacters other than '*' and '.'.
+  return Str.find_first_of(RegexAdvancedMetachars) == StringRef::npos;
+}
+
 std::string Regex::escape(StringRef String) {
   std::string RegexStr;
   for (unsigned i = 0, e = String.size(); i != e; ++i) {
Index: lib/Support/SpecialCaseList.cpp
===================================================================
--- lib/Support/SpecialCaseList.cpp
+++ lib/Support/SpecialCaseList.cpp
@@ -20,12 +20,102 @@
 #include "llvm/ADT/StringSet.h"
 #include "llvm/Support/MemoryBuffer.h"
 #include "llvm/Support/Regex.h"
+#include <map>
 #include <string>
 #include <system_error>
 #include <utility>
 
 namespace llvm {
 
+struct TrigramIndex {
+  bool Defeated;
+  std::vector<std::string> Rules;
+  std::vector<int> Counts;
+  std::map<std::string, std::vector<int>> Index;
+
+  void insert(std::string Rule) {
+    Rules.push_back(Rule);
+    //fprintf(stderr, "TrigramIndex::insert(%s)\n", Rule.c_str());
+  }
+
+  void build() {
+    //fprintf(stderr, "TrigramIndex::build\n");
+    std::map<std::string, int> Tris;
+    // Count trigrams in rules.
+    for (size_t I = 0; I < Rules.size(); I++) {
+      const auto& Rule = Rules[I];
+      int Cnt = 0;
+      for (size_t J = 0; J < Rule.size() - 2; J++) {
+        std::string Tri = Rule.substr(J, 3);
+        if (Tri.find_first_of(".*") != std::string::npos)
+          continue;
+        Cnt++;
+        Tris[Tri]++;
+      }
+      if (!Cnt) {
+        // This rule does not have trigrams at all.
+        // The heuristic check is defeated, as we can't rely on the
+        // trigrams check to find if the query is definitely not matched.
+        Defeated = true;
+        fprintf(stderr, "TrigramIndex is defeated (loc1)\n");
+        return;
+      }
+    }
+
+    Index.clear();
+    Counts.clear();
+    Counts.resize(Rules.size());
+    for (size_t I = 0; I < Rules.size(); I++) {
+      const auto& Rule = Rules[I];
+      int Cnt = 0;
+      StringSet<> Was;
+      for (size_t J = 0; J < Rule.size() - 2; J++) {
+        std::string Tri = Rule.substr(J, 3);
+        if (Tri.find_first_of(".*") != std::string::npos || Was.count(Tri))
+          continue;
+        if (Tris[Tri] > 0 && Tris[Tri] < 4) {
+          Cnt++;
+          Index[Tri].push_back(I);
+        }
+        Was.insert(Tri);
+      }
+      if (!Cnt) {
+        // This rule does not have remarkable trigrams to rely on.
+        // We have to always call the full regexp chain.
+        fprintf(stderr, "TrigramIndex is defeated (loc2)\n");
+        Defeated = true;
+        return;
+      }
+      Counts[I] = Cnt;
+    }
+  }
+
+  bool isDefinitelyOut(StringRef Query) const {
+    //fprintf(stderr, "TrigramIndex:isDefinitelyOut(%s)\n", Query.str().c_str());
+    if (Defeated) {
+      //fprintf(stderr, "TrigramIndex is defeated\n");
+      return false;
+    }
+    std::vector<int> CurCounts(Rules.size());
+    for (int I = 0; I < static_cast<int>(Query.size()) - 2; I++) {
+      std::string Tri = Query.substr(I, 3);
+      if (Tri.find_first_of(".*") != std::string::npos || !Index.count(Tri))
+        continue;
+      for (int J : Index.find(Tri)->second) {
+        CurCounts[J]++;
+        // If we have reached a desired limit, we have to look at the query
+        // more closely by running a full regex.
+        if (CurCounts[J] >= Counts[J]) {
+          // fprintf(stderr, "TrigramIndex:isDefinitelyOut(%s) is FALSE\n", Query.str().c_str());
+          return false;
+        }
+      }
+    }
+    // fprintf(stderr, "TrigramIndex:isDefinitelyOut(%s) is TRUE\n", Query.str().c_str());
+    return true;
+  }
+};
+
 /// Represents a set of regular expressions.  Regular expressions which are
 /// "literal" (i.e. no regex metacharacters) are stored in Strings, while all
 /// others are represented as a single pipe-separated regex in RegEx.  The
@@ -33,10 +123,16 @@
 /// literal strings than Regex.
 struct SpecialCaseList::Entry {
   StringSet<> Strings;
+  TrigramIndex Trigrams;
   std::unique_ptr<Regex> RegEx;
+  bool DisableTrigrams;
 
   bool match(StringRef Query) const {
-    return Strings.count(Query) || (RegEx && RegEx->match(Query));
+    if (Strings.count(Query))
+      return true;
+    if (!DisableTrigrams && Trigrams.isDefinitelyOut(Query))
+      return false;
+    return RegEx && RegEx->match(Query);
   }
 };
 
@@ -104,9 +200,15 @@
     StringRef Category = SplitRegexp.second;
 
     // See if we can store Regexp in Strings.
+    auto& Entry = Entries[Prefix][Category];
     if (Regex::isLiteralERE(Regexp)) {
-      Entries[Prefix][Category].Strings.insert(Regexp);
+      Entry.Strings.insert(Regexp);
       continue;
+    } else if (!Entry.DisableTrigrams && Regex::isSimpleWildcard(Regexp)) {
+      Entry.Trigrams.insert(Regexp);
+    } else {
+      fprintf(stderr, "Disable Trigrams for Prefix=%s, Category=%s, Regexp=%s\n", Prefix.str().c_str(), Category.str().c_str(), Regexp.c_str());
+      Entry.DisableTrigrams = true;
     }
 
     // Replace * with .*
@@ -142,6 +244,7 @@
                                                 IE = I->second.end();
          II != IE; ++II) {
       Entries[I->getKey()][II->getKey()].RegEx.reset(new Regex(II->getValue()));
+      Entries[I->getKey()][II->getKey()].Trigrams.build();
     }
   }
   Regexps.clear();