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
diff --git a/compiler/optimizing/escape.cc b/compiler/optimizing/escape.cc
index 2b578c1..f3f5b15 100644
--- a/compiler/optimizing/escape.cc
+++ b/compiler/optimizing/escape.cc
@@ -20,8 +20,69 @@
namespace art {
+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 (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.
+ if (!escape_visitor(user)) {
+ return;
+ }
+ } else if (user->IsPhi() ||
+ user->IsSelect() ||
+ (user->IsInvoke() && user->GetSideEffects().DoesAnyWrite()) ||
+ (user->IsInstanceFieldSet() && (reference == user->InputAt(1))) ||
+ (user->IsUnresolvedInstanceFieldSet() && (reference == user->InputAt(1))) ||
+ (user->IsStaticFieldSet() && (reference == user->InputAt(1))) ||
+ (user->IsUnresolvedStaticFieldSet() && (reference == user->InputAt(0))) ||
+ (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.
+ 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.
+ if (!escape_visitor(user)) {
+ return;
+ }
+ } else if (user->IsReturn()) {
+ if (!escape_visitor(user)) {
+ return;
+ }
+ }
+ }
+
+ // Look at the environment uses if it's for HDeoptimize. Other environment uses are fine,
+ // as long as client optimizations that rely on this information are disabled for debuggable.
+ for (const HUseListNode<HEnvironment*>& use : reference->GetEnvUses()) {
+ HEnvironment* user = use.GetUser();
+ if (user->GetHolder()->IsDeoptimize()) {
+ if (!escape_visitor(user->GetHolder())) {
+ return;
+ }
+ }
+ }
+}
+
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) {
@@ -42,61 +103,32 @@
*is_singleton_and_not_returned = false;
}
- // 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()) {
- // 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.
+ 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;
- } else if (user->IsPhi() ||
- user->IsSelect() ||
- (user->IsInvoke() && user->GetSideEffects().DoesAnyWrite()) ||
- (user->IsInstanceFieldSet() && (reference == user->InputAt(1))) ||
- (user->IsUnresolvedInstanceFieldSet() && (reference == user->InputAt(1))) ||
- (user->IsStaticFieldSet() && (reference == user->InputAt(1))) ||
- (user->IsUnresolvedStaticFieldSet() && (reference == user->InputAt(0))) ||
- (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;
- } 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;
- } else if (user->IsReturn()) {
- *is_singleton_and_not_returned = false;
+ return false;
}
- }
-
- // Look at the environment uses if it's for HDeoptimize. Other environment uses are fine,
- // as long as client optimizations that rely on this information are disabled for debuggable.
- for (const HUseListNode<HEnvironment*>& use : reference->GetEnvUses()) {
- HEnvironment* user = use.GetUser();
- if (user->GetHolder()->IsDeoptimize()) {
- *is_singleton_and_not_deopt_visible = false;
- break;
- }
- }
+ });
+ VisitEscapes(reference, visitor);
}
-bool DoesNotEscape(HInstruction* reference, bool (*no_escape)(HInstruction*, HInstruction*)) {
+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 75e37b0..5402cb1 100644
--- a/compiler/optimizing/escape.h
+++ b/compiler/optimizing/escape.h
@@ -26,6 +26,59 @@
* 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 @@
* 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