three ideas around inlining: further devirt; callee-specific-return-types; and how TypeSwitchNode deals with "umbrella" final-methods

[Lukas Stadler]

Hi Miguel,

you’re diving really deep :-)
see my comments inline…

- Lukas

On 26 Jan 2014, at 14:09, Garcia Gutierrez Miguel Alfredo <miguelalfredo.garcia at epfl.ch> wrote:

> 
> After exploring InliningPhase some ideas come to mind, it would be great if someone in the know could comment on them (those comments would be of help to those becoming familiar with Graal)
> 
> Summary:
> 
>  (1) some further devirtualization could be done in MethodCallTargetNode::canonical(), as shown below.
Yes, you’re right, although inline caching will probably hide most of the effect in HotSpot. Might be important for other backends, though.

>  (2) after further exploring, I realized that ConditionalEliminationPhase performs that additional devirtualization (ie it's not necessary for the receiver type to be exact, as long as the resolved target method is final; if the receiver's type had been pinned as final then it also would have been exact to start with). ConditionalEliminationPhase does a great job here, because it tracks types in a flow-sensitive manner.
We had a few cases where the flow-sensitive devirtualization in the ConditionalEliminationPhase is important, but it’s not hugely important in general.

>  (3) however there appears to be one place where the devirtualization in question is being missed, after making parameters more precise (as a result of inlining). The snippet shown below, in getInlineInfo()
> 
>      (3.a) does detect target methods for exact-type receivers,
>      (3.b) but forgets to check for non-exact-type receivers whether a final final method is resolved;
> 
> Anyway, at least for (3.a) an ExactInlineInfo for that callsite is returned, however without actually re-wiring the associated MethodCallTargetNode's targetMethod and invokeKind. It remains to-be-done, but an ExactInlineInfo's tryToDevirtualize() is a no-op (it assumes the InvokeSpecial is already there) thus leaving that job again for ConditionalEliminationPhase. Wouldn't it be simpler to just do it on the spot? The MethodCallTargetNode instance is a copy, mutating it shouldn't mess with anyone.
This functionality should really be factored out somehow - it’s implemented in a couple of places. And all versions looks quite different :-)
As stated above, I suspect that having the right InvokeKind will get more important as we turn towards non-x86/x64/HotSpot targets.

>  (4) unlike the items above, there's no code for this one, because it's just an idea: An ExactInlineInfo may end up not being inlined. Given that its getCachedGraph() was just accessed, would it be possible to find out "quickly", based on that graph, what the actual return type is? (which may well be more specific than the declared return type, as usual for a target method overriding the one the callsite states). With that information, a safe downcast can be inserted for the return value, that hopefully propagates in the caller's graph. This optimization could be added to ConditionalEliminationPhase, but the allure of having the getCachedGraph() already in the cache (ha-ha-ha) makes InliningPhase more appealing. The stamp of such "callee-specific return type" could well narrow things even more (including saying something about primitives being returned)
This one’s tricky.
First, it depends on the actual code within the callee, which can be changed at runtime. This could be solved by an assumption on the method’s contents.
But second, the graph only encodes the behavior encountered during profiling - so if a branch was never encountered in the profiling interpreter, it will be missing in the cached graph.
If the callee is executed in the interpreter, it could very well reach other branches that return types not encountered in the cached graph.
(also, we can’t create a graph that encodes all the code paths in a bytecode method - the GraphBuilder is just not designed for this purpose)
We could, however, use this information like profiling info: by first checking if it’s true.
That should, of course, only be done if the additional type information actually improves the resulting code.
We would need to experiment with that to see if it’s worth the trouble.

>  (5) Another "brainstorm-quality" idea: Detecting final-targets could prove useful in connection with TypeSwitchNode. Frameworks exist where final methods are sprinkled at some subclasses which themselves are extended by yet more classes. From a TypeSwitchNode perspective, lots of type-hub comparisons are made all mapping to the same final-target. In those cases, one or more instanceof could filter those "umbrella" cases, letting the TypeSwitchNode focus on a smaller set of concrete subtypes.
Hm… interesting. This could be implemented by a system similar to the SwitchStrategy, which tries different strategies for numeric switches and chooses the best one based on the profiled probabilities.


> Agree? Disagree? What do you think?
> 
> 
> Miguel
> 
> 
> 
> Exhibit for item (1) above: MethodCallTargetNode::canonical(), modified by yours truly
> ======================================================================================
> 
>    @Override
>    public Node canonical(CanonicalizerTool tool) {
>        if (invokeKind == InvokeKind.Interface || invokeKind == InvokeKind.Virtual) {
>            ValueNode receiver = receiver();
>            if (receiver != null) {
>                ResolvedJavaType receiverType = ObjectStamp.typeOrNull(receiver);
>                if (receiverType != null) {
>                    ResolvedJavaMethod method = null;
>                    boolean isExactType = ObjectStamp.isExactType(receiver);
>                    if (isExactType || receiverType.isInstanceClass()) {
>                        method = receiverType.resolveMethod(targetMethod);
>                        if (method != null && !isExactType && !method.canBeStaticallyBound()) {
>                            method = null;
>                        }
>                    }
>                    if (method != null) {
>                        invokeKind = InvokeKind.Special;
>                        targetMethod = method;
>                    }
>                }
>            }
>        }
>        return this;
>    }
> 
> Exhibit for item (2) above: ConditionalEliminationPhase devirt
> ==============================================================
> 
>            } else if (node instanceof Invoke) {
>                Invoke invoke = (Invoke) node;
>                if (invoke.callTarget() instanceof MethodCallTargetNode) {
>                    MethodCallTargetNode callTarget = (MethodCallTargetNode) invoke.callTarget();
>                    ValueNode receiver = callTarget.receiver();
>                    if (receiver != null && (callTarget.invokeKind() == InvokeKind.Interface || callTarget.invokeKind() == InvokeKind.Virtual)) {
>                        ResolvedJavaType type = state.getNodeType(receiver);
>                        if (type != ObjectStamp.typeOrNull(receiver)) {
>                            ResolvedJavaMethod method = type.resolveMethod(callTarget.targetMethod());
>                            if (method != null) {
>                                if ((method.getModifiers() & Modifier.FINAL) != 0 || (type.getModifiers() & Modifier.FINAL) != 0) {
>                                    callTarget.setInvokeKind(InvokeKind.Special);
>                                    callTarget.setTargetMethod(method);
>                                }
>                            }
>                        }
>                    }
>                }
> 
>            }
> 
> Exhibit for item (3) above: part of getInlineInfo()
> ===================================================
> 
>        if (receiverStamp.type() != null) {
>            // the invoke target might be more specific than the holder (happens after inlining:
>            // parameters lose their declared type...)
>            ResolvedJavaType receiverType = receiverStamp.type();
>            if (receiverType != null && holder.isAssignableFrom(receiverType)) {
>                holder = receiverType;
>                if (receiverStamp.isExactType()) {
>                    assert targetMethod.getDeclaringClass().isAssignableFrom(holder) : holder + " subtype of " + targetMethod.getDeclaringClass() + " for " + targetMethod;
>                    ResolvedJavaMethod resolvedMethod = holder.resolveMethod(targetMethod);
>                    if (resolvedMethod != null) {
>                        return getExactInlineInfo(data, invoke, replacements, optimisticOpts, resolvedMethod);
>                    }
>                }
>            }
>        }
> 
> 
> 
> 
> 
> --
> Miguel Garcia
> Swiss Federal Institute of Technology
> EPFL - IC - LAMP1 - INR 328 - Station 14
> CH-1015 Lausanne - Switzerland
> http://lamp.epfl.ch/~magarcia/