Limit recursive polymorphic inlining to prevent code bloat
If both NoRecursion and Wrapper implement the same method
MyMethod, NoRecursion with just `return false` and Wrapper
with `return BaseClass.MyMethod()` we would end up with
generated code similar to:
```
if (receiver == NoRecursion) {
return false;
} else if (receiver == Wrapper) {
// A polymorphic invoke which turns into:
if (unwrappedValue.receiver == NoRecursion) {
return false;
} else if (unwrappedValue.receiver == Wrapper) {
// A polymorphic invoke which turns into
// [...] you get the gist, we do this several times.
} else {
// HInvokeVirtual
}
} else {
// HInvokeVirtual
}
```
After the change we would have:
```
if (receiver == NoRecursion) {
return false;
} else {
// HInvokeVirtual
}
```
This pattern was worse when there were more than one recursive
polymorphic case, increasing exponentially in size. This was
common to see on Wrapper classes, but uncommon otherwise.
In the two wrappers plus one non-wrapper case in test/2238-,
we will now generate a .cfg which is about 6% the size versus
before this CL (12M -> 779K).
Test: art/test/testrunner/testrunner.py --host --64 --optimizing -b
Bug: 217464625
Change-Id: I3c6444193ea2f24af29d97549776a283ef177efd
diff --git a/compiler/optimizing/inliner.cc b/compiler/optimizing/inliner.cc
index ac71ce9..0157d65 100644
--- a/compiler/optimizing/inliner.cc
+++ b/compiler/optimizing/inliner.cc
@@ -64,6 +64,11 @@
// much inlining compared to code locality.
static constexpr size_t kMaximumNumberOfRecursiveCalls = 4;
+// Limit recursive polymorphic call inlining to prevent code bloat, since it can quickly get out of
+// hand in the presence of multiple Wrapper classes. We set this to 0 to disallow polymorphic
+// recursive calls at all.
+static constexpr size_t kMaximumNumberOfPolymorphicRecursiveCalls = 0;
+
// Controls the use of inline caches in AOT mode.
static constexpr bool kUseAOTInlineCaches = true;
@@ -952,8 +957,19 @@
dex::TypeIndex class_index = FindClassIndexIn(handle.Get(), caller_compilation_unit_);
HInstruction* return_replacement = nullptr;
- LOG_NOTE() << "Try inline polymorphic call to " << method->PrettyMethod();
- if (!class_index.IsValid() ||
+
+ const bool too_many_polymorphic_recursive_calls =
+ CountRecursiveCallsOf(method) > kMaximumNumberOfPolymorphicRecursiveCalls;
+ if (too_many_polymorphic_recursive_calls) {
+ LOG_FAIL(stats_, MethodCompilationStat::kNotInlinedPolymorphicRecursiveBudget)
+ << "Method " << method->PrettyMethod()
+ << " is not inlined because it has reached its polymorphic recursive call budget.";
+ } else if (class_index.IsValid()) {
+ LOG_NOTE() << "Try inline polymorphic call to " << method->PrettyMethod();
+ }
+
+ if (too_many_polymorphic_recursive_calls ||
+ !class_index.IsValid() ||
!TryBuildAndInline(invoke_instruction,
method,
ReferenceTypeInfo::Create(handle, /* is_exact= */ true),
diff --git a/compiler/optimizing/optimizing_compiler_stats.h b/compiler/optimizing/optimizing_compiler_stats.h
index a68a0be..d458e42 100644
--- a/compiler/optimizing/optimizing_compiler_stats.h
+++ b/compiler/optimizing/optimizing_compiler_stats.h
@@ -100,6 +100,7 @@
kNotInlinedCodeItem,
kNotInlinedWont,
kNotInlinedRecursiveBudget,
+ kNotInlinedPolymorphicRecursiveBudget,
kNotInlinedProxy,
kNotInlinedUnresolved,
kNotInlinedPolymorphic,
diff --git a/test/2238-checker-polymorphic-recursive-inlining/expected-stderr.txt b/test/2238-checker-polymorphic-recursive-inlining/expected-stderr.txt
new file mode 100644
index 0000000..e69de29
--- /dev/null
+++ b/test/2238-checker-polymorphic-recursive-inlining/expected-stderr.txt
diff --git a/test/2238-checker-polymorphic-recursive-inlining/expected-stdout.txt b/test/2238-checker-polymorphic-recursive-inlining/expected-stdout.txt
new file mode 100644
index 0000000..e69de29
--- /dev/null
+++ b/test/2238-checker-polymorphic-recursive-inlining/expected-stdout.txt
diff --git a/test/2238-checker-polymorphic-recursive-inlining/info.txt b/test/2238-checker-polymorphic-recursive-inlining/info.txt
new file mode 100644
index 0000000..7e03c06
--- /dev/null
+++ b/test/2238-checker-polymorphic-recursive-inlining/info.txt
@@ -0,0 +1 @@
+Test for recursive polymorphic inlining.
diff --git a/test/2238-checker-polymorphic-recursive-inlining/profile b/test/2238-checker-polymorphic-recursive-inlining/profile
new file mode 100644
index 0000000..497d084
--- /dev/null
+++ b/test/2238-checker-polymorphic-recursive-inlining/profile
@@ -0,0 +1,3 @@
+HSLBaseClassAnotherWrapper;->recursiveTwoWrappers()Z+LBaseClassAnotherWrapper;,LBaseClassWrapper;,LBaseClassNoRecursion;
+HSLBaseClassWrapper;->recursiveTwoWrappers()Z+LBaseClassAnotherWrapper;,LBaseClassWrapper;,LBaseClassNoRecursion;
+HSLBaseClassShallowWrapper;->recursiveShallow()Z+LBaseClassShallowWrapper;,LBaseClassShallowNoRecursion;
diff --git a/test/2238-checker-polymorphic-recursive-inlining/run b/test/2238-checker-polymorphic-recursive-inlining/run
new file mode 100644
index 0000000..a4e2692
--- /dev/null
+++ b/test/2238-checker-polymorphic-recursive-inlining/run
@@ -0,0 +1,18 @@
+#!/bin/bash
+#
+# Copyright (C) 2022 The Android Open Source Project
+#
+# Licensed under the Apache License, Version 2.0 (the "License");
+# you may not use this file except in compliance with the License.
+# You may obtain a copy of the License at
+#
+# http://www.apache.org/licenses/LICENSE-2.0
+#
+# Unless required by applicable law or agreed to in writing, software
+# distributed under the License is distributed on an "AS IS" BASIS,
+# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+# See the License for the specific language governing permissions and
+# limitations under the License.
+
+# Use a profile to put specific classes in the app image to trigger polymorphic inlining.
+exec ${RUN} $@ --profile -Xcompiler-option --compiler-filter=speed-profile
diff --git a/test/2238-checker-polymorphic-recursive-inlining/src/BaseClass.java b/test/2238-checker-polymorphic-recursive-inlining/src/BaseClass.java
new file mode 100644
index 0000000..38e6f07
--- /dev/null
+++ b/test/2238-checker-polymorphic-recursive-inlining/src/BaseClass.java
@@ -0,0 +1,19 @@
+/*
+ * Copyright (C) 2022 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+public abstract class BaseClass {
+ abstract boolean recursiveTwoWrappers();
+}
diff --git a/test/2238-checker-polymorphic-recursive-inlining/src/BaseClassShallow.java b/test/2238-checker-polymorphic-recursive-inlining/src/BaseClassShallow.java
new file mode 100644
index 0000000..27fc1f6
--- /dev/null
+++ b/test/2238-checker-polymorphic-recursive-inlining/src/BaseClassShallow.java
@@ -0,0 +1,19 @@
+/*
+ * Copyright (C) 2022 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+public abstract class BaseClassShallow {
+ abstract boolean recursiveShallow();
+}
diff --git a/test/2238-checker-polymorphic-recursive-inlining/src/Main.java b/test/2238-checker-polymorphic-recursive-inlining/src/Main.java
new file mode 100644
index 0000000..adf6e2a
--- /dev/null
+++ b/test/2238-checker-polymorphic-recursive-inlining/src/Main.java
@@ -0,0 +1,127 @@
+/*
+ * Copyright (C) 2022 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+// Check that we have only one call before the inliner.
+
+/// CHECK-START: boolean BaseClassWrapper.recursiveTwoWrappers() inliner (before)
+/// CHECK: InvokeVirtual method_name:BaseClass.recursiveTwoWrappers
+/// CHECK-NOT: InvokeVirtual method_name:BaseClass.recursiveTwoWrappers
+
+// After the inliner we will have:
+// if (receiver == BaseClassAnotherWrapper) {
+// // At this point we have no way to know that the Invoke was going
+// // to be a recursive one, but it cuts at the first iteration.
+// if (receiver == BaseClassNoRecursion) {
+// return false;
+// } else {
+// HInvokeVirtual
+// }
+// } else if (receiver == BaseClassNoRecursion) {
+// return false;
+// } else {
+// HInvokeVirtual
+// }
+
+// We should see LoadClasses for BaseClassNoRecursion, and BaseClassAnotherWrapper<BaseClassNoRecursion>, in some order.
+/// CHECK-START: boolean BaseClassWrapper.recursiveTwoWrappers() inliner (after)
+/// CHECK-DAG: LoadClass load_kind:BssEntry class_name:BaseClassAnotherWrapper
+/// CHECK-DAG: LoadClass load_kind:BssEntry class_name:BaseClassNoRecursion
+/// CHECK-DAG: LoadClass load_kind:BssEntry class_name:BaseClassNoRecursion
+
+// We should see the two HInvokeVirtual that appear in the above comment.
+/// CHECK-START: boolean BaseClassWrapper.recursiveTwoWrappers() inliner (after)
+/// CHECK: InvokeVirtual method_name:BaseClass.recursiveTwoWrappers
+/// CHECK: InvokeVirtual method_name:BaseClass.recursiveTwoWrappers
+/// CHECK-NOT: InvokeVirtual method_name:BaseClass.recursiveTwoWrappers
+class BaseClassWrapper extends BaseClass {
+ protected final BaseClass mBaseClass;
+
+ public BaseClassWrapper(BaseClass BaseClass) {
+ mBaseClass = BaseClass;
+ }
+
+ boolean recursiveTwoWrappers() {
+ return mBaseClass.recursiveTwoWrappers();
+ }
+}
+
+// Same thing here as above but swapping BaseClassWrapper and BaseClassAnotherWrapper.
+
+/// CHECK-START: boolean BaseClassAnotherWrapper.recursiveTwoWrappers() inliner (after)
+/// CHECK-DAG: LoadClass load_kind:BssEntry class_name:BaseClassWrapper
+/// CHECK-DAG: LoadClass load_kind:BssEntry class_name:BaseClassNoRecursion
+/// CHECK-DAG: LoadClass load_kind:BssEntry class_name:BaseClassNoRecursion
+
+/// CHECK-START: boolean BaseClassAnotherWrapper.recursiveTwoWrappers() inliner (after)
+/// CHECK: InvokeVirtual method_name:BaseClass.recursiveTwoWrappers
+/// CHECK: InvokeVirtual method_name:BaseClass.recursiveTwoWrappers
+/// CHECK-NOT: InvokeVirtual method_name:BaseClass.recursiveTwoWrappers
+class BaseClassAnotherWrapper extends BaseClass {
+ protected final BaseClass mBaseClass;
+
+ public BaseClassAnotherWrapper(BaseClass BaseClass) {
+ mBaseClass = BaseClass;
+ }
+
+ boolean recursiveTwoWrappers() {
+ return mBaseClass.recursiveTwoWrappers();
+ }
+}
+
+class BaseClassNoRecursion extends BaseClass {
+ boolean recursiveTwoWrappers() {
+ return false;
+ }
+}
+
+// Check that we have only one call before the inliner.
+
+/// CHECK-START: boolean BaseClassShallowWrapper.recursiveShallow() inliner (before)
+/// CHECK: InvokeVirtual method_name:BaseClassShallow.recursiveShallow
+/// CHECK-NOT: InvokeVirtual method_name:BaseClassShallow.recursiveShallow
+
+// After the inliner we will have
+// if (receiver == BaseClassShallowNoRecursion) {
+// return false;
+// } else {
+// HInvokeVirtual
+// }
+
+/// CHECK-START: boolean BaseClassShallowWrapper.recursiveShallow() inliner (after)
+/// CHECK: LoadClass load_kind:BssEntry class_name:BaseClassShallowNoRecursion
+/// CHECK: InvokeVirtual method_name:BaseClassShallow.recursiveShallow
+/// CHECK-NOT: InvokeVirtual method_name:BaseClassShallow.recursiveShallow
+class BaseClassShallowWrapper extends BaseClassShallow {
+ protected final BaseClassShallow mBaseClassShallow;
+
+ public BaseClassShallowWrapper(BaseClassShallow BaseClassShallow) {
+ mBaseClassShallow = BaseClassShallow;
+ }
+
+ boolean recursiveShallow() {
+ return mBaseClassShallow.recursiveShallow();
+ }
+}
+
+class BaseClassShallowNoRecursion extends BaseClassShallow {
+ boolean recursiveShallow() {
+ return false;
+ }
+}
+
+public class Main {
+ public static void main(String[] args) {}
+}
\ No newline at end of file