Improve inlining limits for recursion (#4067)

Previously we would keep doing iterations of inlining until we hit
the number of functions in the module (at which point, we would
definitely know we are recursing). This prevents infinite recursion,
but it can take a very very long time to notice that in a huge
module with one tiny recursive function and 100,000 other ones.

To do better than that, track how many times we've inlined into
a function. After a fixed number of such inlinings, stop.

Aside from avoding very slow compile times, such infinite
recursion likely is not that beneficial to do a great many times,
so anyhow it is best to stop after a few iterations.

1 files changed, 203 insertions, 1 deletions

diff --git a/test/lit/passes/inlining_optimize-level=3.wast b/test/lit/passes/inlining_optimize-level=3.wast
index ad5f2b44e..c9e60fc47 100644
--- a/test/lit/passes/inlining_optimize-level=3.wast
+++ b/test/lit/passes/inlining_optimize-level=3.wast
@@ -4,6 +4,8 @@
 ;; RUN: foreach %s %t wasm-opt --inlining --optimize-level=3 -S -o - | filecheck %s
 
 (module
+  ;; CHECK:      (type $i32_=>_i32 (func (param i32) (result i32)))
+
   ;; CHECK:      (type $none_=>_i32 (func (result i32)))
 
   ;; CHECK:      (type $none_=>_none (func))
@@ -19,6 +21,14 @@
   (table 1 1 funcref)
   (elem (i32.const 0) $no-loops-but-one-use-but-tabled)
 
+  ;; CHECK:      (export "A" (func $recursive-inlining-1))
+
+  ;; CHECK:      (export "B" (func $recursive-inlining-2))
+
+  ;; CHECK:      (export "BA" (func $b-recursive-inlining-1))
+
+  ;; CHECK:      (export "BB" (func $b-recursive-inlining-2))
+
   ;; CHECK:      (func $yes (result i32)
   ;; CHECK-NEXT:  (i32.const 1)
   ;; CHECK-NEXT: )
@@ -220,5 +230,197 @@
     (drop (call $no-loops-but-one-use-but-exported))
     (drop (call $no-loops-but-one-use-but-tabled))
   )
-)
 
+  ;; Two functions that call each other. (Exported, so that they are not removed
+  ;; after inlining.) We should only perform a limited amount of inlining here -
+  ;; a little might help, but like loop unrolling it loses its benefit quickly.
+  ;; Specifically here we will see the infinite recursion after one inlining,
+  ;; and stop (since we do not inline a method into itself).
+
+  ;; CHECK:      (func $recursive-inlining-1 (param $x i32) (result i32)
+  ;; CHECK-NEXT:  (local $1 i32)
+  ;; CHECK-NEXT:  (block $__inlined_func$recursive-inlining-2 (result i32)
+  ;; CHECK-NEXT:   (local.set $1
+  ;; CHECK-NEXT:    (local.get $x)
+  ;; CHECK-NEXT:   )
+  ;; CHECK-NEXT:   (block (result i32)
+  ;; CHECK-NEXT:    (call $recursive-inlining-1
+  ;; CHECK-NEXT:     (local.get $1)
+  ;; CHECK-NEXT:    )
+  ;; CHECK-NEXT:   )
+  ;; CHECK-NEXT:  )
+  ;; CHECK-NEXT: )
+  (func $recursive-inlining-1 (export "A") (param $x i32) (result i32)
+    (call $recursive-inlining-2
+      (local.get $x)
+    )
+  )
+
+  ;; CHECK:      (func $recursive-inlining-2 (param $x i32) (result i32)
+  ;; CHECK-NEXT:  (call $recursive-inlining-1
+  ;; CHECK-NEXT:   (local.get $x)
+  ;; CHECK-NEXT:  )
+  ;; CHECK-NEXT: )
+  (func $recursive-inlining-2 (export "B") (param $x i32) (result i32)
+    (call $recursive-inlining-1
+      (local.get $x)
+    )
+  )
+
+  ;; As above, but both call the second. The first will inline the second
+  ;; several times before hitting the limit (of around 5).
+
+  ;; CHECK:      (func $b-recursive-inlining-1 (param $x i32) (result i32)
+  ;; CHECK-NEXT:  (local $1 i32)
+  ;; CHECK-NEXT:  (local $2 i32)
+  ;; CHECK-NEXT:  (local $3 i32)
+  ;; CHECK-NEXT:  (local $4 i32)
+  ;; CHECK-NEXT:  (local $5 i32)
+  ;; CHECK-NEXT:  (block $__inlined_func$b-recursive-inlining-2 (result i32)
+  ;; CHECK-NEXT:   (local.set $1
+  ;; CHECK-NEXT:    (local.get $x)
+  ;; CHECK-NEXT:   )
+  ;; CHECK-NEXT:   (block (result i32)
+  ;; CHECK-NEXT:    (block $__inlined_func$b-recursive-inlining-20 (result i32)
+  ;; CHECK-NEXT:     (local.set $2
+  ;; CHECK-NEXT:      (local.get $1)
+  ;; CHECK-NEXT:     )
+  ;; CHECK-NEXT:     (block (result i32)
+  ;; CHECK-NEXT:      (block $__inlined_func$b-recursive-inlining-21 (result i32)
+  ;; CHECK-NEXT:       (local.set $3
+  ;; CHECK-NEXT:        (local.get $2)
+  ;; CHECK-NEXT:       )
+  ;; CHECK-NEXT:       (block (result i32)
+  ;; CHECK-NEXT:        (block $__inlined_func$b-recursive-inlining-22 (result i32)
+  ;; CHECK-NEXT:         (local.set $4
+  ;; CHECK-NEXT:          (local.get $3)
+  ;; CHECK-NEXT:         )
+  ;; CHECK-NEXT:         (block (result i32)
+  ;; CHECK-NEXT:          (block $__inlined_func$b-recursive-inlining-23 (result i32)
+  ;; CHECK-NEXT:           (local.set $5
+  ;; CHECK-NEXT:            (local.get $4)
+  ;; CHECK-NEXT:           )
+  ;; CHECK-NEXT:           (call $b-recursive-inlining-2
+  ;; CHECK-NEXT:            (local.get $5)
+  ;; CHECK-NEXT:           )
+  ;; CHECK-NEXT:          )
+  ;; CHECK-NEXT:         )
+  ;; CHECK-NEXT:        )
+  ;; CHECK-NEXT:       )
+  ;; CHECK-NEXT:      )
+  ;; CHECK-NEXT:     )
+  ;; CHECK-NEXT:    )
+  ;; CHECK-NEXT:   )
+  ;; CHECK-NEXT:  )
+  ;; CHECK-NEXT: )
+  (func $b-recursive-inlining-1 (export "BA") (param $x i32) (result i32)
+    (call $b-recursive-inlining-2
+      (local.get $x)
+    )
+  )
+
+  ;; CHECK:      (func $b-recursive-inlining-2 (param $x i32) (result i32)
+  ;; CHECK-NEXT:  (call $b-recursive-inlining-2
+  ;; CHECK-NEXT:   (local.get $x)
+  ;; CHECK-NEXT:  )
+  ;; CHECK-NEXT: )
+  (func $b-recursive-inlining-2 (export "BB") (param $x i32) (result i32)
+    (call $b-recursive-inlining-2
+      (local.get $x)
+    )
+  )
+
+  ;; Verify that we can do a large number (larger than the limit of ~5 we just
+  ;; saw for recursion) of calls into a single function, if we can do it all in
+  ;; a single iteration (which is the usual case, and the case here).
+
+  ;; CHECK:      (func $call-many-getters
+  ;; CHECK-NEXT:  (block
+  ;; CHECK-NEXT:   (block $__inlined_func$getter
+  ;; CHECK-NEXT:    (drop
+  ;; CHECK-NEXT:     (i32.const 1)
+  ;; CHECK-NEXT:    )
+  ;; CHECK-NEXT:   )
+  ;; CHECK-NEXT:  )
+  ;; CHECK-NEXT:  (block
+  ;; CHECK-NEXT:   (block $__inlined_func$getter0
+  ;; CHECK-NEXT:    (drop
+  ;; CHECK-NEXT:     (i32.const 1)
+  ;; CHECK-NEXT:    )
+  ;; CHECK-NEXT:   )
+  ;; CHECK-NEXT:  )
+  ;; CHECK-NEXT:  (block
+  ;; CHECK-NEXT:   (block $__inlined_func$getter1
+  ;; CHECK-NEXT:    (drop
+  ;; CHECK-NEXT:     (i32.const 1)
+  ;; CHECK-NEXT:    )
+  ;; CHECK-NEXT:   )
+  ;; CHECK-NEXT:  )
+  ;; CHECK-NEXT:  (block
+  ;; CHECK-NEXT:   (block $__inlined_func$getter2
+  ;; CHECK-NEXT:    (drop
+  ;; CHECK-NEXT:     (i32.const 1)
+  ;; CHECK-NEXT:    )
+  ;; CHECK-NEXT:   )
+  ;; CHECK-NEXT:  )
+  ;; CHECK-NEXT:  (block
+  ;; CHECK-NEXT:   (block $__inlined_func$getter3
+  ;; CHECK-NEXT:    (drop
+  ;; CHECK-NEXT:     (i32.const 1)
+  ;; CHECK-NEXT:    )
+  ;; CHECK-NEXT:   )
+  ;; CHECK-NEXT:  )
+  ;; CHECK-NEXT:  (block
+  ;; CHECK-NEXT:   (block $__inlined_func$getter4
+  ;; CHECK-NEXT:    (drop
+  ;; CHECK-NEXT:     (i32.const 1)
+  ;; CHECK-NEXT:    )
+  ;; CHECK-NEXT:   )
+  ;; CHECK-NEXT:  )
+  ;; CHECK-NEXT:  (block
+  ;; CHECK-NEXT:   (block $__inlined_func$getter5
+  ;; CHECK-NEXT:    (drop
+  ;; CHECK-NEXT:     (i32.const 1)
+  ;; CHECK-NEXT:    )
+  ;; CHECK-NEXT:   )
+  ;; CHECK-NEXT:  )
+  ;; CHECK-NEXT:  (block
+  ;; CHECK-NEXT:   (block $__inlined_func$getter6
+  ;; CHECK-NEXT:    (drop
+  ;; CHECK-NEXT:     (i32.const 1)
+  ;; CHECK-NEXT:    )
+  ;; CHECK-NEXT:   )
+  ;; CHECK-NEXT:  )
+  ;; CHECK-NEXT:  (block
+  ;; CHECK-NEXT:   (block $__inlined_func$getter7
+  ;; CHECK-NEXT:    (drop
+  ;; CHECK-NEXT:     (i32.const 1)
+  ;; CHECK-NEXT:    )
+  ;; CHECK-NEXT:   )
+  ;; CHECK-NEXT:  )
+  ;; CHECK-NEXT:  (block
+  ;; CHECK-NEXT:   (block $__inlined_func$getter8
+  ;; CHECK-NEXT:    (drop
+  ;; CHECK-NEXT:     (i32.const 1)
+  ;; CHECK-NEXT:    )
+  ;; CHECK-NEXT:   )
+  ;; CHECK-NEXT:  )
+  ;; CHECK-NEXT: )
+  (func $call-many-getters
+    (call $getter)
+    (call $getter)
+    (call $getter)
+    (call $getter)
+    (call $getter)
+    (call $getter)
+    (call $getter)
+    (call $getter)
+    (call $getter)
+    (call $getter)
+  )
+
+  (func $getter
+    (drop (i32.const 1))
+  )
+)
+.