diff --git a/compiler-rt/lib/sanitizer_common/CMakeLists.txt b/compiler-rt/lib/sanitizer_common/CMakeLists.txt
--- a/compiler-rt/lib/sanitizer_common/CMakeLists.txt
+++ b/compiler-rt/lib/sanitizer_common/CMakeLists.txt
@@ -3,6 +3,7 @@
 
 set(SANITIZER_SOURCES_NOTERMINATION
   sanitizer_allocator.cpp
+  sanitizer_common_region.cpp
   sanitizer_common.cpp
   sanitizer_deadlock_detector1.cpp
   sanitizer_deadlock_detector2.cpp
diff --git a/compiler-rt/lib/sanitizer_common/sanitizer_common_region.h b/compiler-rt/lib/sanitizer_common/sanitizer_common_region.h
new file mode 100644
--- /dev/null
+++ b/compiler-rt/lib/sanitizer_common/sanitizer_common_region.h
@@ -0,0 +1,39 @@
+//===-- sanitizer_common_region.h -------------------------------*- 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 file is shared between run-time libraries of sanitizers.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef SANITIZER_COMMON_REGION_H
+#define SANITIZER_COMMON_REGION_H
+
+#include "sanitizer_common.h"
+
+namespace __sanitizer {
+
+struct Region {
+  uptr begin;
+  uptr end;
+};
+
+inline bool operator==(const Region &lhs, const Region &rhs) {
+  return lhs.begin == rhs.begin && lhs.end == rhs.end;
+}
+
+inline bool operator!=(const Region &lhs, const Region &rhs) {
+  return !(lhs == rhs);
+}
+
+// Calculates intersection of two sets of regions in O(N log N) time.
+void Intersect(ArrayRef<Region> a, ArrayRef<Region> b,
+               InternalMmapVectorNoCtor<Region> &output);
+
+}  // namespace __sanitizer
+
+#endif  // SANITIZER_COMMON_REGION_H
diff --git a/compiler-rt/lib/sanitizer_common/sanitizer_common_region.cpp b/compiler-rt/lib/sanitizer_common/sanitizer_common_region.cpp
new file mode 100644
--- /dev/null
+++ b/compiler-rt/lib/sanitizer_common/sanitizer_common_region.cpp
@@ -0,0 +1,68 @@
+//===-- sanitizer_common_region.cpp ---------------------------------------===//
+//
+// 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 file is shared between AddressSanitizer and ThreadSanitizer
+// run-time libraries.
+//===----------------------------------------------------------------------===//
+
+#include "sanitizer_common_region.h"
+
+namespace __sanitizer {
+
+void Intersect(ArrayRef<Region> a, ArrayRef<Region> b,
+               InternalMmapVectorNoCtor<Region> &output) {
+  output.clear();
+  if (a.empty() || b.empty())
+    return;
+
+  struct RegionEvent {
+    uptr val;
+    s8 diff1;
+    s8 diff2;
+  };
+
+  InternalMmapVector<RegionEvent> events;
+  for (const Region &r : a) {
+    CHECK_LE(r.begin, r.end);
+    events.push_back({r.begin, 1, 0});
+    events.push_back({r.end, -1, 0});
+  }
+
+  for (const Region &r : b) {
+    CHECK_LE(r.begin, r.end);
+    events.push_back({r.begin, 0, 1});
+    events.push_back({r.end, 0, -1});
+  }
+
+  Sort(events.data(), events.size(),
+       [](const RegionEvent &lh, const RegionEvent &rh) {
+         return lh.val < rh.val;
+       });
+
+  uptr start = 0;
+  sptr state1 = 0;
+  sptr state2 = 0;
+  for (const auto &e : events) {
+    if (e.val != start) {
+      DCHECK_GE(state1, 0);
+      DCHECK_GE(state2, 0);
+      if (state1 && state2) {
+        if (!output.empty() && start == output.back().end)
+          output.back().end = e.val;
+        else
+          output.push_back({start, e.val});
+      }
+      start = e.val;
+    }
+
+    state1 += e.diff1;
+    state2 += e.diff2;
+  }
+}
+
+}  // namespace __sanitizer
diff --git a/compiler-rt/lib/sanitizer_common/tests/CMakeLists.txt b/compiler-rt/lib/sanitizer_common/tests/CMakeLists.txt
--- a/compiler-rt/lib/sanitizer_common/tests/CMakeLists.txt
+++ b/compiler-rt/lib/sanitizer_common/tests/CMakeLists.txt
@@ -16,6 +16,7 @@
   sanitizer_bitvector_test.cpp
   sanitizer_bvgraph_test.cpp
   sanitizer_chained_origin_depot_test.cpp
+  sanitizer_common_region_test.cpp
   sanitizer_common_test.cpp
   sanitizer_deadlock_detector_test.cpp
   sanitizer_dense_map_test.cpp
diff --git a/compiler-rt/lib/sanitizer_common/tests/sanitizer_common_region_test.cpp b/compiler-rt/lib/sanitizer_common/tests/sanitizer_common_region_test.cpp
new file mode 100644
--- /dev/null
+++ b/compiler-rt/lib/sanitizer_common/tests/sanitizer_common_region_test.cpp
@@ -0,0 +1,66 @@
+//===-- sanitizer_common_region_test.cpp ----------------------------------===//
+//
+// 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 file is a part of ThreadSanitizer/AddressSanitizer runtime.
+//
+//===----------------------------------------------------------------------===//
+#include "sanitizer_common/sanitizer_common_region.h"
+
+#include <algorithm>
+
+#include "gtest/gtest.h"
+#include "sanitizer_common/sanitizer_common.h"
+
+namespace __sanitizer {
+
+class SanitizerCommon
+    : public testing::TestWithParam<std::tuple<
+          std::vector<Region>, std::vector<Region>, std::vector<Region>>> {};
+
+TEST_P(SanitizerCommon, Intersect) {
+  {
+    InternalMmapVector<Region> output;
+    Intersect(std::get<0>(GetParam()), std::get<1>(GetParam()), output);
+    EXPECT_EQ(std::get<2>(GetParam()),
+              std::vector<Region>(output.begin(), output.end()));
+  }
+  {
+    InternalMmapVector<Region> output;
+    Intersect(std::get<1>(GetParam()), std::get<0>(GetParam()), output);
+    EXPECT_EQ(std::get<2>(GetParam()),
+              std::vector<Region>(output.begin(), output.end()));
+  }
+}
+
+void PrintTo(const Region& r, std::ostream* os) {
+  *os << "[" << r.begin << ", " << r.end << ")";
+}
+
+static const std::tuple<std::vector<Region>, std::vector<Region>,
+                        std::vector<Region>>
+    kTests[] = {
+        {{}, {}, {}},
+        {{{100, 1000}}, {{5000, 10000}}, {}},
+        {{{100, 1000}, {200, 2000}}, {{5000, 10000}, {6000, 11000}}, {}},
+        {{{100, 1000}}, {{100, 1000}}, {{100, 1000}}},
+        {{{100, 1000}}, {{50, 150}}, {{100, 150}}},
+        {{{100, 1000}}, {{150, 250}}, {{150, 250}}},
+        {{{100, 1000}, {100, 1000}}, {{100, 1000}}, {{100, 1000}}},
+        {{{100, 1000}}, {{500, 1500}}, {{500, 1000}}},
+        {{{100, 200}}, {{200, 300}, {1, 1000}}, {{100, 200}}},
+        {{{100, 200}, {200, 300}}, {{100, 300}}, {{100, 300}}},
+        {{{100, 200}, {200, 300}, {300, 400}}, {{150, 350}}, {{150, 350}}},
+        {{{100, 200}, {300, 400}, {500, 600}},
+         {{0, 1000}},
+         {{100, 200}, {300, 400}, {500, 600}}},
+};
+
+INSTANTIATE_TEST_SUITE_P(SanitizerCommonEmpty, SanitizerCommon,
+                         testing::ValuesIn(kTests));
+
+}  // namespace __sanitizer