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,92 @@
 #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;
+  bool IsBuilt;
+  std::vector<std::string> Rules;
+  std::vector<int> Counts;
+  std::map<std::string, std::vector<int>> Index;
+
+  void insert(std::string Regex) {
+    if (Defeated) return;
+    if (!Regex::isSimpleWildcard(Regex)) {
+      Defeated = true;
+      fprintf(stderr, "TrigramIndex is defeated (loc3)\n");
+      return;
+    }
+    Rules.push_back(Regex);
+  }
+
+  void build() {
+    assert(!IsBuilt && "build() should only be called once");
+    IsBuilt = true;
+    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)
+          continue;
+        // We don't want the index to grow too much for the popular trigrams,
+        // as they are weak signals. It's ok to still require them for the
+        // rules we have already processed. It's just a small additional
+        // computational cost.
+        if (Index[Tri].size() >= 4)
+          continue;
+        Cnt++;
+        if (!Was.count(Tri)) {
+          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 {
+    assert(IsBuilt && "TrigramIndex::build() was not called!");
+    //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 +113,15 @@
 /// literal strings than Regex.
 struct SpecialCaseList::Entry {
   StringSet<> Strings;
+  TrigramIndex Trigrams;
   std::unique_ptr<Regex> RegEx;
 
   bool match(StringRef Query) const {
-    return Strings.count(Query) || (RegEx && RegEx->match(Query));
+    if (Strings.count(Query))
+      return true;
+    if (Trigrams.isDefinitelyOut(Query))
+      return false;
+    return RegEx && RegEx->match(Query);
   }
 };
 
@@ -104,10 +189,12 @@
     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
+      Entry.Trigrams.insert(Regexp);
 
     // Replace * with .*
     for (size_t pos = 0; (pos = Regexp.find("*", pos)) != std::string::npos;
@@ -145,6 +232,11 @@
     }
   }
   Regexps.clear();
+
+  // Build trigram indices
+  for (auto& I : Entries)
+    for (auto& II : I.getValue())
+      II.getValue().Trigrams.build();
   IsCompiled = true;
 }
 
Index: unittests/Support/SpecialCaseListTest.cpp
===================================================================
--- unittests/Support/SpecialCaseListTest.cpp
+++ unittests/Support/SpecialCaseListTest.cpp
@@ -134,4 +134,38 @@
     sys::fs::remove(Path);
 }
 
+TEST_F(SpecialCaseListTest, NoTrigramsInRules) {
+  std::unique_ptr<SpecialCaseList> SCL = makeSpecialCaseList("fun:b.r\n"
+                                                             "fun:za*az\n");
+  EXPECT_TRUE(SCL->inSection("fun", "bar"));
+  EXPECT_FALSE(SCL->inSection("fun", "baz"));
+  EXPECT_TRUE(SCL->inSection("fun", "zakaz"));
+  EXPECT_FALSE(SCL->inSection("fun", "zaraza"));
+}
+
+TEST_F(SpecialCaseListTest, NoTrigramsInARule) {
+  std::unique_ptr<SpecialCaseList> SCL = makeSpecialCaseList("fun:*bar*\n"
+                                                             "fun:za*az\n");
+  EXPECT_TRUE(SCL->inSection("fun", "abara"));
+  EXPECT_FALSE(SCL->inSection("fun", "bor"));
+  EXPECT_TRUE(SCL->inSection("fun", "zakaz"));
+  EXPECT_FALSE(SCL->inSection("fun", "zaraza"));
+}
+
+TEST_F(SpecialCaseListTest, RepetitiveRule) {
+  std::unique_ptr<SpecialCaseList> SCL = makeSpecialCaseList("fun:*bar*bar*bar*bar*\n"
+                                                             "fun:bar*\n");
+  EXPECT_TRUE(SCL->inSection("fun", "bara"));
+  EXPECT_FALSE(SCL->inSection("fun", "abara"));
+  EXPECT_TRUE(SCL->inSection("fun", "barbarbarbar"));
+  EXPECT_TRUE(SCL->inSection("fun", "abarbarbarbar"));
+  EXPECT_FALSE(SCL->inSection("fun", "abarbarbar"));
+}
+
+TEST_F(SpecialCaseListTest, SpecialSymbolRule) {
+  std::unique_ptr<SpecialCaseList> SCL = makeSpecialCaseList("src:*c\\+\\+abi*\n");
+  EXPECT_TRUE(SCL->inSection("src", "c++abi"));
+  EXPECT_FALSE(SCL->inSection("src", "c\\+\\+abi"));
+}
+
 }