Partial inlining via function splitting by kripken · Pull Request #4152 · WebAssembly/binaryen

kripken · 2021-09-14T16:07:57Z

(This is the last "big" optimization on my plate atm for wasm GC.)

This PR helps with functions like this:

function foo(x) {
  if (x) {
    ..
    lots of work here
    ..
  }
}

If "lots of work" is large enough, then we won't inline such a
function. However, we may end up calling into the function
only to get a false on that if and immediately exit. So it is useful
to partially inline this function, basically by creating a split
of it into a condition part that is inlineable

function foo$inlineable(x) {
  if (x) {
    foo$outlined();
  }
}

and an outlined part that is not inlineable:

function foo$outlined(x) {
  ..
  lots of work here
  ..
}

We can then inline the inlineable part. That means that a call
like

foo(param);

turns into

if (param) {
  foo$outlined();
}

In other words, we end up replacing a call and then a check with
a check and then a call. Any time that the condition is false, this
will be a speedup.

The cost here is increased size, as we duplicate the condition
into the callsites. For that reason, only do this when heavily
optimizing for size.

This is a 10% speedup on j2cl. This helps two types of functions
there: Java class inits, which often look like "have I been
initialized before? if not, do all this work", and also assertion
methods which look like "if the input is null, throw an
exception".

When we catches "Output must be deterministic" we can't see any details. This PR fix this and now we can see diff of b1.wasm and b2.wasm files. Example output: Output must be deterministic. Diff: --- expected +++ actual @@ -2072,9 +2072,7 @@ ) (drop (block $label$16 (result funcref) - (local.set $10 - (ref.null func) - ) + (nop) (drop (call $22 (f64.const 0.296)

tlively

I haven't read the tests yet, but here are my comments so far.

tlively · 2021-09-14T19:39:01Z

+  // (like limitations on which functions can be inlined into in each iteration,
+  // the number of iterations, etc.). Therefore this function will only find out
+  // if we *can* split, but not actually do any splitting.
+  bool canSplit(Function* func, const FunctionInfo& info) {


It looks like info is not used in this function.

Good catch!

tlively · 2021-09-14T20:51:12Z

+    // If the body is a block, and we have breaks to that block, then we cannot
+    // outline any code - we can't outline a break without the break's target.


Do we separately need to check for returns for the same reason?

Not necessarily - one of the patterns below allows returns. The other will check for them.

tlively · 2021-09-14T20:54:10Z

+    //
+    // TODO: support a return value
+    if (!iff->ifFalse && func->getResults() == Type::none &&
+        iff->ifTrue->is<Return>() && body->is<Block>()) {


Why do we need to check body->is<Block>() here?

Good point, we don't need to. In fact lower down we assert on that. I'll move the assert up here and remove the if.

tlively · 2021-09-14T20:56:08Z

+      split.inlineable = copyFunction(func, "inlineable-A");
+      auto* outlined = copyFunction(func, "outlined-A");


Why the -A in the names?

Also, it seems wasteful to create a full copy of the function for inlineable, which will end up being very small. Could we avoid copying entirely and have the two new functions refer to the original IR nodes directly?

-A is for "pattern A" as opposed to pattern B that appears below.

Yeah, there is a TODO in the copy function itself for avoiding the extra copying work. It's more work though, and potentially error-prone, so I'm not sure it's worth it. The overhead is wasteful but not that bad.

tlively · 2021-09-14T21:31:09Z

+  // Checks if an expression is very simple - something simple enough that we
+  // are willing to inline it in this optimization. This should basically take
+  // almost no cost at all to compute.
+  bool isSimple(Expression* curr) {


Should the comparison instructions be simple as well?

Do you mean the if conditions? This is called on them.

Or what do you mean here?

I mean things like i32.lt_u, i32.ge_s, etc.

Oh, yes, we may want those as well. For now I just added a tiny set of things, but it already handles the main things that j2cl needs. The rest is a TODO (on line 765).

Co-authored-by: Thomas Lively <7121787+tlively@users.noreply.github.com>

tlively · 2021-09-16T00:56:07Z

+ ;; CHECK-NEXT:  (local $24 i32)
+ ;; CHECK-NEXT:  (local $25 f64)


It would be good to replace this dump of real-world code with something more focused at some point. The diff here is not too useful for determining whether the code is working correctly.

Yeah, sorry about that - for a change like this, inlining more things, the diff on this existing file is quite large.

(Ideally we could somehow make this particular file ignore this change, but otherwise I guess ignoring it in review is second best.)

tlively · 2021-09-16T00:57:12Z

@@ -31060,3 +31021,87 @@
  )
 )
 )
+;; CHECK:      (func $byn-split-outlined-B$_fmt_u (param $0 i32) (param $1 i32) (param $2 i32)


Neat to see this work on real-world code, though!

tlively · 2021-09-17T00:50:55Z

+  ;; CHECK-NEXT:  )
+  ;; CHECK-NEXT: )
+  (func $call-reachable-if-body
+    ;; Note that the above contains


Would it be worth putting a loop in to make the test output less surprising?

Hmm, I think it's nice to show this actually. It is a useful result - if we regress this, we want to know.

tlively · 2021-09-17T00:52:33Z

+      (if
+        (i32.const 1)


It's not important that there's an if here, right?

Yes, we don't actually even scan this inner if - we just look for returns inside it.

Co-authored-by: Thomas Lively <7121787+tlively@users.noreply.github.com>

kripken and others added 30 commits August 24, 2021 14:20

start

39ee13c

more

6fcaf4f

maybe

6e14db0

almost

d7835d5

partial build

9d3dc24

partial build

91b8baa

start

c0accd6

better

f5e353e

bad

c8397c0

fix

e1dfb3f

start test

b2578f2

test

c2d58f8

test

c68da45

test

b644de4

test

25315a7

test

0f561a2

test

4c725b1

test

f74aa0e

test

3d5f58a

test

81fd400

more

cd552a6

test

ddb1ec4

test

971ea7e

test

535491d

format

64d246a

enable

b4810dc

fuzzing

7508074

typo

7df8866

fix

13f1ed9

kripken added 10 commits September 13, 2021 15:21

fix

dbafc48

fix

cb22401

global

1822e14

comment

208e5c6

comment

aec3965

comment

3471adf

comment

8d537cb

comment

6b7de9a

comment

8d7c795

simplify comment

f7616b9

kripken requested review from aheejin and tlively September 14, 2021 16:07

kripken added 2 commits September 14, 2021 09:18

format

7316387

fix

d425f97

tlively reviewed Sep 14, 2021

View reviewed changes

kripken and others added 7 commits September 15, 2021 12:56

Apply suggestions from code review

de3273f

Co-authored-by: Thomas Lively <7121787+tlively@users.noreply.github.com>

format

4ded325

Update src/passes/Inlining.cpp

8e414b4

Co-authored-by: Thomas Lively <7121787+tlively@users.noreply.github.com>

remove unused param

b39ffd8

Replace if with assert

2ffc6a9

comment

388e166

Merge remote-tracking branch 'origin/main' into partial

79818ea

tlively reviewed Sep 17, 2021

View reviewed changes

tlively approved these changes Sep 17, 2021

View reviewed changes

kripken and others added 2 commits September 16, 2021 19:28

Update test/lit/passes/inlining_splitting.wast

c955cf6

Co-authored-by: Thomas Lively <7121787+tlively@users.noreply.github.com>

update test output

9f34c61

kripken enabled auto-merge (squash) September 17, 2021 02:38

kripken merged commit eb83c42 into main Sep 17, 2021

kripken deleted the partial branch September 17, 2021 03:03

MaxGraey mentioned this pull request Sep 20, 2021

Could we eliminate redundant (double) branch checks for same predicate? #4168

Closed

		// If the body is a block, and we have breaks to that block, then we cannot
		// outline any code - we can't outline a break without the break's target.

		split.inlineable = copyFunction(func, "inlineable-A");
		auto* outlined = copyFunction(func, "outlined-A");

		;; CHECK-NEXT: (local $24 i32)
		;; CHECK-NEXT: (local $25 f64)

Conversation

kripken commented Sep 14, 2021

Uh oh!

tlively left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

3 participants