Refactor Escape-analysis to use visitors

The current escape-analysis is entirely built around finding a single
'does-escape' boolean (and a few ancillary booleans). This change adds
a new VisitEscapes function that allows one to more easily track which
instructions cause escapes and rewrites the other escape-analysis
functions in terms of this VisitEscapes function.

Test: ./test.py --host
Bug: 67037140
Change-Id: Ie5ad7580544be21713d040c2943cae19ff5414d4

2 files changed, 155 insertions, 42 deletions

diff --git a/compiler/optimizing/escape.cc b/compiler/optimizing/escape.cc
index 2b578c1cc8..f3f5b15d99 100644
--- a/compiler/optimizing/escape.cc
+++ b/compiler/optimizing/escape.cc
@@ -20,43 +20,27 @@
 
 namespace art {
 
-void CalculateEscape(HInstruction* reference,
-                     bool (*no_escape)(HInstruction*, HInstruction*),
-                     /*out*/ bool* is_singleton,
-                     /*out*/ bool* is_singleton_and_not_returned,
-                     /*out*/ bool* is_singleton_and_not_deopt_visible) {
-  // For references not allocated in the method, don't assume anything.
-  if (!reference->IsNewInstance() && !reference->IsNewArray()) {
-    *is_singleton = false;
-    *is_singleton_and_not_returned = false;
-    *is_singleton_and_not_deopt_visible = false;
-    return;
-  }
-  // Assume the best until proven otherwise.
-  *is_singleton = true;
-  *is_singleton_and_not_returned = true;
-  *is_singleton_and_not_deopt_visible = true;
-
-  if (reference->IsNewInstance() && reference->AsNewInstance()->IsFinalizable()) {
-    // Finalizable reference is treated as being returned in the end.
-    *is_singleton_and_not_returned = false;
+void VisitEscapes(HInstruction* reference, EscapeVisitor& escape_visitor) {
+  // References not allocated in the method are intrinsically escaped.
+  // Finalizable references are always escaping since they end up in FinalizerQueues.
+  if ((!reference->IsNewInstance() && !reference->IsNewArray()) ||
+      (reference->IsNewInstance() && reference->AsNewInstance()->IsFinalizable())) {
+    if (!escape_visitor(reference)) {
+      return;
+    }
   }
 
   // Visit all uses to determine if this reference can escape into the heap,
   // a method call, an alias, etc.
   for (const HUseListNode<HInstruction*>& use : reference->GetUses()) {
     HInstruction* user = use.GetUser();
-    if (no_escape != nullptr && (*no_escape)(reference, user)) {
-      // Client supplied analysis says there is no escape.
-      continue;
-    } else if (user->IsBoundType() || user->IsNullCheck()) {
+    if (user->IsBoundType() || user->IsNullCheck()) {
       // BoundType shouldn't normally be necessary for an allocation. Just be conservative
       // for the uncommon cases. Similarly, null checks are eventually eliminated for explicit
       // allocations, but if we see one before it is simplified, assume an alias.
-      *is_singleton = false;
-      *is_singleton_and_not_returned = false;
-      *is_singleton_and_not_deopt_visible = false;
-      return;
+      if (!escape_visitor(user)) {
+        return;
+      }
     } else if (user->IsPhi() ||
                user->IsSelect() ||
                (user->IsInvoke() && user->GetSideEffects().DoesAnyWrite()) ||
@@ -67,21 +51,21 @@ void CalculateEscape(HInstruction* reference,
                (user->IsArraySet() && (reference == user->InputAt(2)))) {
       // The reference is merged to HPhi/HSelect, passed to a callee, or stored to heap.
       // Hence, the reference is no longer the only name that can refer to its value.
-      *is_singleton = false;
-      *is_singleton_and_not_returned = false;
-      *is_singleton_and_not_deopt_visible = false;
-      return;
+      if (!escape_visitor(user)) {
+        return;
+      }
     } else if ((user->IsUnresolvedInstanceFieldGet() && (reference == user->InputAt(0))) ||
                (user->IsUnresolvedInstanceFieldSet() && (reference == user->InputAt(0)))) {
       // The field is accessed in an unresolved way. We mark the object as a non-singleton.
       // Note that we could optimize this case and still perform some optimizations until
       // we hit the unresolved access, but the conservative assumption is the simplest.
-      *is_singleton = false;
-      *is_singleton_and_not_returned = false;
-      *is_singleton_and_not_deopt_visible = false;
-      return;
+      if (!escape_visitor(user)) {
+        return;
+      }
     } else if (user->IsReturn()) {
-      *is_singleton_and_not_returned = false;
+      if (!escape_visitor(user)) {
+        return;
+      }
     }
   }
 
@@ -90,13 +74,61 @@ void CalculateEscape(HInstruction* reference,
   for (const HUseListNode<HEnvironment*>& use : reference->GetEnvUses()) {
     HEnvironment* user = use.GetUser();
     if (user->GetHolder()->IsDeoptimize()) {
-      *is_singleton_and_not_deopt_visible = false;
-      break;
+      if (!escape_visitor(user->GetHolder())) {
+        return;
+      }
     }
   }
 }
 
-bool DoesNotEscape(HInstruction* reference, bool (*no_escape)(HInstruction*, HInstruction*)) {
+void CalculateEscape(HInstruction* reference,
+                     NoEscapeCheck& no_escape,
+                     /*out*/ bool* is_singleton,
+                     /*out*/ bool* is_singleton_and_not_returned,
+                     /*out*/ bool* is_singleton_and_not_deopt_visible) {
+  // For references not allocated in the method, don't assume anything.
+  if (!reference->IsNewInstance() && !reference->IsNewArray()) {
+    *is_singleton = false;
+    *is_singleton_and_not_returned = false;
+    *is_singleton_and_not_deopt_visible = false;
+    return;
+  }
+  // Assume the best until proven otherwise.
+  *is_singleton = true;
+  *is_singleton_and_not_returned = true;
+  *is_singleton_and_not_deopt_visible = true;
+
+  if (reference->IsNewInstance() && reference->AsNewInstance()->IsFinalizable()) {
+    // Finalizable reference is treated as being returned in the end.
+    *is_singleton_and_not_returned = false;
+  }
+
+  LambdaEscapeVisitor visitor([&](HInstruction* escape) -> bool {
+    if (escape == reference || no_escape(reference, escape)) {
+      // Ignore already known inherent escapes and escapes client supplied
+      // analysis knows is safe. Continue on.
+      return true;
+    } else if (escape->IsReturn()) {
+      // value is returned but might still be singleton. Continue on.
+      *is_singleton_and_not_returned = false;
+      return true;
+    } else if (escape->IsDeoptimize()) {
+      // value escapes through deopt but might still be singleton. Continue on.
+      *is_singleton_and_not_deopt_visible = false;
+      return true;
+    } else {
+      // Real escape. All knowledge about what happens to the value lost. We can
+      // stop here.
+      *is_singleton = false;
+      *is_singleton_and_not_returned = false;
+      *is_singleton_and_not_deopt_visible = false;
+      return false;
+    }
+  });
+  VisitEscapes(reference, visitor);
+}
+
+bool DoesNotEscape(HInstruction* reference, NoEscapeCheck& no_escape) {
   bool is_singleton = false;
   bool is_singleton_and_not_returned = false;
   bool is_singleton_and_not_deopt_visible = false;  // not relevant for escape
diff --git a/compiler/optimizing/escape.h b/compiler/optimizing/escape.h
index 75e37b0551..5402cb1763 100644
--- a/compiler/optimizing/escape.h
+++ b/compiler/optimizing/escape.h
@@ -26,6 +26,59 @@ class HInstruction;
  * allocation is visible outside ('escapes') its immediate method context.
  */
 
+// A visitor for seeing all instructions escape analysis considers escaping.
+// Called with each user of the reference passed to 'VisitEscapes'. Return true
+// to continue iteration and false to stop.
+class EscapeVisitor {
+ public:
+  virtual ~EscapeVisitor() {}
+  virtual bool Visit(HInstruction* escape) = 0;
+  bool operator()(HInstruction* user) {
+    return Visit(user);
+  }
+};
+
+// An explicit EscapeVisitor for lambdas
+template <typename F>
+class LambdaEscapeVisitor final : public EscapeVisitor {
+ public:
+  explicit LambdaEscapeVisitor(F f) : func_(f) {}
+  bool Visit(HInstruction* escape) override {
+    return func_(escape);
+  }
+
+ private:
+  F func_;
+};
+
+// This functor is used with the escape-checking functions. If the NoEscape
+// function returns true escape analysis will consider 'user' to not have
+// escaped 'reference'. This allows clients with additional information to
+// supplement the escape-analysis. If the NoEscape function returns false then
+// the normal escape-checking code will be used to determine whether or not
+// 'reference' escapes.
+class NoEscapeCheck {
+ public:
+  virtual ~NoEscapeCheck() {}
+  virtual bool NoEscape(HInstruction* reference, HInstruction* user) = 0;
+  bool operator()(HInstruction* ref, HInstruction* user) {
+    return NoEscape(ref, user);
+  }
+};
+
+// An explicit NoEscapeCheck for use with c++ lambdas.
+template <typename F>
+class LambdaNoEscapeCheck final : public NoEscapeCheck {
+ public:
+  explicit LambdaNoEscapeCheck(F f) : func_(f) {}
+  bool NoEscape(HInstruction* ref, HInstruction* user) override {
+    return func_(ref, user);
+  }
+
+ private:
+  F func_;
+};
+
 /*
  * Performs escape analysis on the given instruction, typically a reference to an
  * allocation. The method assigns true to parameter 'is_singleton' if the reference
@@ -52,16 +105,44 @@ class HInstruction;
  * analysis is applied to the user instead.
  */
 void CalculateEscape(HInstruction* reference,
-                     bool (*no_escape)(HInstruction*, HInstruction*),
+                     NoEscapeCheck& no_escape,
                      /*out*/ bool* is_singleton,
                      /*out*/ bool* is_singleton_and_not_returned,
                      /*out*/ bool* is_singleton_and_not_deopt_visible);
 
+inline void CalculateEscape(HInstruction* reference,
+                            bool (*no_escape_fn)(HInstruction*, HInstruction*),
+                            /*out*/ bool* is_singleton,
+                            /*out*/ bool* is_singleton_and_not_returned,
+                            /*out*/ bool* is_singleton_and_not_deopt_visible) {
+  LambdaNoEscapeCheck esc(no_escape_fn);
+  LambdaNoEscapeCheck noop_esc([](HInstruction*, HInstruction*) { return false; });
+  CalculateEscape(reference,
+                  no_escape_fn == nullptr ? static_cast<NoEscapeCheck&>(noop_esc) : esc,
+                  is_singleton,
+                  is_singleton_and_not_returned,
+                  is_singleton_and_not_deopt_visible);
+}
+
+/*
+ * Performs escape analysis and visits each escape of the reference. Does not try to calculate any
+ * overall information about the method. Escapes are calculated in the same way as CalculateEscape.
+ *
+ * The escape_visitor should return true to continue visiting, false otherwise.
+ */
+void VisitEscapes(HInstruction* reference, EscapeVisitor& escape_visitor);
+
 /*
  * Convenience method for testing the singleton and not returned properties at once.
  * Callers should be aware that this method invokes the full analysis at each call.
  */
-bool DoesNotEscape(HInstruction* reference, bool (*no_escape)(HInstruction*, HInstruction*));
+bool DoesNotEscape(HInstruction* reference, NoEscapeCheck& no_escape);
+
+inline bool DoesNotEscape(HInstruction* reference,
+                          bool (*no_escape_fn)(HInstruction*, HInstruction*)) {
+  LambdaNoEscapeCheck<typeof(no_escape_fn)> esc(no_escape_fn);
+  return DoesNotEscape(reference, esc);
+}
 
 }  // namespace art