[sanitizer] findPath for deadlock detector

git-svn-id: https://llvm.org/svn/llvm-project/compiler-rt/trunk@201306 91177308-0d34-0410-b5e6-96231b3b80d8

1 files changed, 20 insertions, 2 deletions

diff --git a/lib/sanitizer_common/sanitizer_bvgraph.h b/lib/sanitizer_common/sanitizer_bvgraph.h
index 5673a7a30..4ad43604b 100644
--- a/lib/sanitizer_common/sanitizer_bvgraph.h
+++ b/lib/sanitizer_common/sanitizer_bvgraph.h
@@ -47,8 +47,7 @@ class BVGraph {
   // to any of the nodes in 'targets'.
   bool isReachable(uptr from, const BV &targets) {
     BV to_visit, visited;
-    to_visit.clear();
-    to_visit.setUnion(v[from]);
+    to_visit.copyFrom(v[from]);
     visited.clear();
     visited.setBit(from);
     while (!to_visit.empty()) {
@@ -59,6 +58,25 @@ class BVGraph {
     return targets.intersectsWith(visited);
   }
 
+  // Finds a path from 'from' to one of the nodes in 'target',
+  // stores up to 'path_size' items of the path into 'path',
+  // returns the path length, or 0 if there is no path of size 'path_size'.
+  uptr findPath(uptr from, const BV &targets, uptr *path, uptr path_size) {
+    if (path_size == 0)
+      return 0;
+    path[0] = from;
+    if (targets.getBit(from))
+      return 1;
+    BV t;
+    t.copyFrom(v[from]);
+    while (!t.empty()) {
+      uptr idx = t.getAndClearFirstOne();
+      if (uptr res = findPath(idx, targets, path + 1, path_size - 1))
+        return res + 1;
+    }
+    return 0;
+  }
+
  private:
   void check(uptr idx) const { CHECK_LE(idx, size()); }
   BV v[kSize];