Context-sensitivity of the inline cost

[Quuxplusone]

Bugzilla Link	PR28383
Status	NEW
Importance	P normal
Reported by	Artur Pilipenko (apilipenko@azulsystems.com)
Reported on	2016-07-01 04:31:06 -0700
Last modified on	2016-07-01 18:59:34 -0700
Version	trunk
Hardware	PC All
CC	ehsanamiri@gmail.com, hfinkel@anl.gov, llvm-bugs@lists.llvm.org, silvasean@google.com, spatel+llvm@rotateright.com
Fixed by commit(s)
Attachments
Blocks
Blocked by
See also

In order to estimate the cost of inlining for a given call site InlineCost
analyzes the body of the callee AND the caller context. For example, if one of
the arguments is known to be non-null in the caller InlineCost takes this fact
into account and discounts the cost of a null-check on this argument in the
callee.

The current pass manager doesn't account for this context-sensitivity.
CallGraphSCC pass manager traverses SCCs of the call graph in the bottom-up
order running inliner and a set of simplification passes on each SCC. This way
inliner always looks at optimized inlining candidates which increases chances
of inlining. Because of context-sensitivity of the inline cost optimizations of
the current SCC might enable more inlining in this SCC. Although, the pass
manager doesn't expect that and doesn't try to inline in this SCC again after
simplifications unless simplifications resulted in devirtualization.

The pass manager should expect that new inlineable call sites can appear as a
result of simplifications other than devirtualization and should iterate on the
current SCC as long as the inliner makes progress.

For example, initial function:
foo(%a) {
  checkNonNull(%a)
  foo_impl(%a)
}

checkNonNull has been inlined and instcombine has propagated context-sensitive
non-null fact to the call-site:

foo(%a) {
  if (%a == null)
    uncommon trap
  foo_impl(nonnull %a)
}
Knowledge about %a being not-null might enable inlining of foo_impl. But the
inliner never tries to inline call sites in foo after that.

[Quuxplusone]

This can be done by making RefreshCallGraph set "DevirtualizedCall" for other
reasons. The "DevirtualizedCall" should really just be named "revisit this SCC"
because that is all it does.

I gave some examples of this in my comments on http://reviews.llvm.org/D21464
(and the corresponding email thread)
In particular look at the post where I reference http://reviews.llvm.org/P6012