[MachineOutliner] Outline functions by order of benefit

Mostly NFC, only change is the order of outlined function names.

Loop over the outlined functions instead of walking the candidate list.

This is a bit easier to understand. It's far more natural to create a function,
then replace all of its occurrences with calls than the other way around.

The functions outlined after this do not change, but their names will be
decided by their benefit. E.g, OUTLINED_FUNCTION_0 will now always be the
most beneficial function, rather than the first one seen.

This makes it easier to enforce an ordering on the outlined functions. So,
this also adds a test to make sure that the ordering works as expected.

llvm-svn: 348414

1 files changed, 106 insertions, 0 deletions

diff --git a/llvm/test/CodeGen/AArch64/machine-outliner-ordering.mir b/llvm/test/CodeGen/AArch64/machine-outliner-ordering.mir
new file mode 100644
index 00000000000..7395df641f5
--- /dev/null
+++ b/llvm/test/CodeGen/AArch64/machine-outliner-ordering.mir
@@ -0,0 +1,106 @@
+# RUN: llc -mtriple=aarch64-unknown-unknown -run-pass=machine-outliner \
+# RUN: -verify-machineinstrs %s -o - | FileCheck %s
+
+# Ensure that outlined function names appear as expected. Currently, they are
+# output in order of benefit.
+
+--- |
+  define void @should_have_fn2() #0 { ret void }
+  define void @should_have_fn0() #0 { ret void }
+  define void @should_have_fn1() #0 { ret void }
+  attributes #0 = { noredzone optsize minsize }
+...
+---
+
+name: should_have_fn2
+tracksRegLiveness: true
+body:             |
+    bb.0:
+        ; CHECK-LABEL: name:        should_have_fn2
+        ; CHECK-NOT: OUTLINED_FUNCTION_1
+        ; CHECK-NOT: OUTLINED_FUNCTION_0
+        ; CHECK: OUTLINED_FUNCTION_2
+        $w0 = ORRWri $wzr, 1
+        $w0 = ORRWri $wzr, 1
+        $w0 = ORRWri $wzr, 1
+    bb.1:
+        ; CHECK-DAG: OUTLINED_FUNCTION_2
+        $w0 = ORRWri $wzr, 1
+        $w0 = ORRWri $wzr, 1
+        $w0 = ORRWri $wzr, 1
+    bb.2:
+        ; CHECK-DAG: OUTLINED_FUNCTION_2
+        $w0 = ORRWri $wzr, 1
+        $w0 = ORRWri $wzr, 1
+        $w0 = ORRWri $wzr, 1
+    bb.3:
+        ; CHECK-DAG: OUTLINED_FUNCTION_2
+        $w0 = ORRWri $wzr, 1
+        $w0 = ORRWri $wzr, 1
+        $w0 = ORRWri $wzr, 1
+    bb.4:
+        RET undef $lr
+
+...
+---
+
+name: should_have_fn0
+
+tracksRegLiveness: true
+body:             |
+    bb.0:
+        ; CHECK-LABEL: name: should_have_fn0
+        ; CHECK-NOT: OUTLINED_FUNCTION_1
+        ; CHECK-NOT: OUTLINED_FUNCTION_2
+        ; CHECK: OUTLINED_FUNCTION_0
+        $w1 = ORRWri $wzr, 1
+        $w1 = ORRWri $wzr, 1
+        $w1 = ORRWri $wzr, 1
+        $w1 = ORRWri $wzr, 1
+        $w1 = ORRWri $wzr, 1
+    bb.1:
+        ; CHECK-DAG: OUTLINED_FUNCTION_0
+        $w1 = ORRWri $wzr, 1
+        $w1 = ORRWri $wzr, 1
+        $w1 = ORRWri $wzr, 1
+        $w1 = ORRWri $wzr, 1
+        $w1 = ORRWri $wzr, 1
+    bb.3:
+        ; CHECK-DAG: OUTLINED_FUNCTION_0
+        $w1 = ORRWri $wzr, 1
+        $w1 = ORRWri $wzr, 1
+        $w1 = ORRWri $wzr, 1
+        $w1 = ORRWri $wzr, 1
+        $w1 = ORRWri $wzr, 1
+    bb.4:
+        RET undef $lr
+
+...
+---
+
+name: should_have_fn1
+tracksRegLiveness: true
+body:             |
+    bb.0:
+        ; CHECK-LABEL: name: should_have_fn1
+        ; CHECK-NOT: OUTLINED_FUNCTION_0
+        ; CHECK-NOT: OUTLINED_FUNCTION_2
+        ; CHECK: OUTLINED_FUNCTION_1
+        $w2 = ORRWri $wzr, 1
+        $w2 = ORRWri $wzr, 1
+        $w2 = ORRWri $wzr, 1
+        $w2 = ORRWri $wzr, 1
+    bb.1:
+        ; CHECK-DAG: OUTLINED_FUNCTION_1
+        $w2 = ORRWri $wzr, 1
+        $w2 = ORRWri $wzr, 1
+        $w2 = ORRWri $wzr, 1
+        $w2 = ORRWri $wzr, 1
+    bb.3:
+        ; CHECK-DAG: OUTLINED_FUNCTION_1
+        $w2 = ORRWri $wzr, 1
+        $w2 = ORRWri $wzr, 1
+        $w2 = ORRWri $wzr, 1
+        $w2 = ORRWri $wzr, 1
+    bb.4:
+        RET undef $lr