Source code

001/*
002 * Copyright (c) 2013, 2014, Oracle and/or its affiliates. All rights reserved.
003 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
004 *
005 * This code is free software; you can redistribute it and/or modify it
006 * under the terms of the GNU General Public License version 2 only, as
007 * published by the Free Software Foundation.
008 *
009 * This code is distributed in the hope that it will be useful, but WITHOUT
010 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
011 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
012 * version 2 for more details (a copy is included in the LICENSE file that
013 * accompanied this code).
014 *
015 * You should have received a copy of the GNU General Public License version
016 * 2 along with this work; if not, write to the Free Software Foundation,
017 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
018 *
019 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
020 * or visit www.oracle.com if you need additional information or have any
021 * questions.
022 */
023package com.oracle.graal.phases.common.inlining.info;
024
025import com.oracle.graal.debug.*;
026import jdk.internal.jvmci.meta.ResolvedJavaType;
027import jdk.internal.jvmci.meta.Kind;
028import jdk.internal.jvmci.meta.DeoptimizationReason;
029import jdk.internal.jvmci.meta.DeoptimizationAction;
030import jdk.internal.jvmci.meta.ResolvedJavaMethod;
031import jdk.internal.jvmci.meta.JavaTypeProfile.ProfiledType;
032
033import java.util.*;
034
035import com.oracle.graal.compiler.common.type.*;
036import com.oracle.graal.graph.*;
037import com.oracle.graal.nodes.*;
038import com.oracle.graal.nodes.CallTargetNode.InvokeKind;
039import com.oracle.graal.nodes.extended.*;
040import com.oracle.graal.nodes.java.*;
041import com.oracle.graal.nodes.spi.*;
042import com.oracle.graal.nodes.util.*;
043import com.oracle.graal.phases.common.inlining.*;
044import com.oracle.graal.phases.common.inlining.info.elem.*;
045import com.oracle.graal.phases.util.*;
046
047/**
048 * Polymorphic inlining of m methods with n type checks (n &ge; m) in case that the profiling
049 * information suggests a reasonable amount of different receiver types and different methods. If an
050 * unknown type is encountered a deoptimization is triggered.
051 */
052public class MultiTypeGuardInlineInfo extends AbstractInlineInfo {
053
054    private final List<ResolvedJavaMethod> concretes;
055    private final double[] methodProbabilities;
056    private final double maximumMethodProbability;
057    private final ArrayList<Integer> typesToConcretes;
058    private final ArrayList<ProfiledType> ptypes;
059    private final double notRecordedTypeProbability;
060    private final Inlineable[] inlineableElements;
061
062    public MultiTypeGuardInlineInfo(Invoke invoke, ArrayList<ResolvedJavaMethod> concretes, ArrayList<ProfiledType> ptypes, ArrayList<Integer> typesToConcretes, double notRecordedTypeProbability) {
063        super(invoke);
064        assert concretes.size() > 0 : "must have at least one method";
065        assert ptypes.size() == typesToConcretes.size() : "array lengths must match";
066
067        this.concretes = concretes;
068        this.ptypes = ptypes;
069        this.typesToConcretes = typesToConcretes;
070        this.notRecordedTypeProbability = notRecordedTypeProbability;
071        this.inlineableElements = new Inlineable[concretes.size()];
072        this.methodProbabilities = computeMethodProbabilities();
073        this.maximumMethodProbability = maximumMethodProbability();
074        assert maximumMethodProbability > 0;
075        assert assertUniqueTypes(ptypes);
076    }
077
078    private static boolean assertUniqueTypes(ArrayList<ProfiledType> ptypes) {
079        Set<ResolvedJavaType> set = new HashSet<>();
080        for (ProfiledType ptype : ptypes) {
081            set.add(ptype.getType());
082        }
083        return set.size() == ptypes.size();
084    }
085
086    private double[] computeMethodProbabilities() {
087        double[] result = new double[concretes.size()];
088        for (int i = 0; i < typesToConcretes.size(); i++) {
089            int concrete = typesToConcretes.get(i);
090            double probability = ptypes.get(i).getProbability();
091            result[concrete] += probability;
092        }
093        return result;
094    }
095
096    private double maximumMethodProbability() {
097        double max = 0;
098        for (int i = 0; i < methodProbabilities.length; i++) {
099            max = Math.max(max, methodProbabilities[i]);
100        }
101        return max;
102    }
103
104    @Override
105    public int numberOfMethods() {
106        return concretes.size();
107    }
108
109    @Override
110    public ResolvedJavaMethod methodAt(int index) {
111        assert index >= 0 && index < concretes.size();
112        return concretes.get(index);
113    }
114
115    @Override
116    public Inlineable inlineableElementAt(int index) {
117        assert index >= 0 && index < concretes.size();
118        return inlineableElements[index];
119    }
120
121    @Override
122    public double probabilityAt(int index) {
123        return methodProbabilities[index];
124    }
125
126    @Override
127    public double relevanceAt(int index) {
128        return probabilityAt(index) / maximumMethodProbability;
129    }
130
131    @Override
132    public void setInlinableElement(int index, Inlineable inlineableElement) {
133        assert index >= 0 && index < concretes.size();
134        inlineableElements[index] = inlineableElement;
135    }
136
137    @Override
138    public Collection<Node> inline(Providers providers) {
139        if (hasSingleMethod()) {
140            return inlineSingleMethod(graph(), providers.getStampProvider());
141        } else {
142            return inlineMultipleMethods(graph(), providers);
143        }
144    }
145
146    public boolean shouldInline() {
147        for (ResolvedJavaMethod method : concretes) {
148            if (method.shouldBeInlined()) {
149                return true;
150            }
151        }
152        return false;
153    }
154
155    private boolean hasSingleMethod() {
156        return concretes.size() == 1 && !shouldFallbackToInvoke();
157    }
158
159    private boolean shouldFallbackToInvoke() {
160        return notRecordedTypeProbability > 0;
161    }
162
163    private Collection<Node> inlineMultipleMethods(StructuredGraph graph, Providers providers) {
164        int numberOfMethods = concretes.size();
165        FixedNode continuation = invoke.next();
166
167        // setup merge and phi nodes for results and exceptions
168        AbstractMergeNode returnMerge = graph.add(new MergeNode());
169        returnMerge.setStateAfter(invoke.stateAfter());
170
171        PhiNode returnValuePhi = null;
172        if (invoke.asNode().getKind() != Kind.Void) {
173            returnValuePhi = graph.addWithoutUnique(new ValuePhiNode(invoke.asNode().stamp().unrestricted(), returnMerge));
174        }
175
176        AbstractMergeNode exceptionMerge = null;
177        PhiNode exceptionObjectPhi = null;
178        if (invoke instanceof InvokeWithExceptionNode) {
179            InvokeWithExceptionNode invokeWithException = (InvokeWithExceptionNode) invoke;
180            ExceptionObjectNode exceptionEdge = (ExceptionObjectNode) invokeWithException.exceptionEdge();
181
182            exceptionMerge = graph.add(new MergeNode());
183
184            FixedNode exceptionSux = exceptionEdge.next();
185            graph.addBeforeFixed(exceptionSux, exceptionMerge);
186            exceptionObjectPhi = graph.addWithoutUnique(new ValuePhiNode(StampFactory.forKind(Kind.Object), exceptionMerge));
187            exceptionMerge.setStateAfter(exceptionEdge.stateAfter().duplicateModified(invoke.stateAfter().bci, true, Kind.Object, new Kind[]{Kind.Object}, new ValueNode[]{exceptionObjectPhi}));
188        }
189
190        // create one separate block for each invoked method
191        AbstractBeginNode[] successors = new AbstractBeginNode[numberOfMethods + 1];
192        for (int i = 0; i < numberOfMethods; i++) {
193            successors[i] = createInvocationBlock(graph, invoke, returnMerge, returnValuePhi, exceptionMerge, exceptionObjectPhi, true);
194        }
195
196        // create the successor for an unknown type
197        FixedNode unknownTypeSux;
198        if (shouldFallbackToInvoke()) {
199            unknownTypeSux = createInvocationBlock(graph, invoke, returnMerge, returnValuePhi, exceptionMerge, exceptionObjectPhi, false);
200        } else {
201            unknownTypeSux = graph.add(new DeoptimizeNode(DeoptimizationAction.InvalidateReprofile, DeoptimizationReason.TypeCheckedInliningViolated));
202        }
203        successors[successors.length - 1] = BeginNode.begin(unknownTypeSux);
204
205        // replace the invoke exception edge
206        if (invoke instanceof InvokeWithExceptionNode) {
207            InvokeWithExceptionNode invokeWithExceptionNode = (InvokeWithExceptionNode) invoke;
208            ExceptionObjectNode exceptionEdge = (ExceptionObjectNode) invokeWithExceptionNode.exceptionEdge();
209            exceptionEdge.replaceAtUsages(exceptionObjectPhi);
210            exceptionEdge.setNext(null);
211            GraphUtil.killCFG(invokeWithExceptionNode.exceptionEdge());
212        }
213
214        assert invoke.asNode().isAlive();
215
216        // replace the invoke with a switch on the type of the actual receiver
217        boolean methodDispatch = createDispatchOnTypeBeforeInvoke(graph, successors, false, providers.getStampProvider());
218
219        assert invoke.next() == continuation;
220        invoke.setNext(null);
221        returnMerge.setNext(continuation);
222        if (returnValuePhi != null) {
223            invoke.asNode().replaceAtUsages(returnValuePhi);
224        }
225        invoke.asNode().safeDelete();
226
227        ArrayList<GuardedValueNode> replacementNodes = new ArrayList<>();
228
229        // prepare the anchors for the invokes
230        for (int i = 0; i < numberOfMethods; i++) {
231            AbstractBeginNode node = successors[i];
232            Invoke invokeForInlining = (Invoke) node.next();
233
234            ResolvedJavaType commonType;
235            if (methodDispatch) {
236                commonType = concretes.get(i).getDeclaringClass();
237            } else {
238                commonType = getLeastCommonType(i);
239            }
240
241            ValueNode receiver = ((MethodCallTargetNode) invokeForInlining.callTarget()).receiver();
242            boolean exact = (getTypeCount(i) == 1 && !methodDispatch);
243            GuardedValueNode anchoredReceiver = InliningUtil.createAnchoredReceiver(graph, node, commonType, receiver, exact);
244            invokeForInlining.callTarget().replaceFirstInput(receiver, anchoredReceiver);
245
246            assert !anchoredReceiver.isDeleted() : anchoredReceiver;
247            replacementNodes.add(anchoredReceiver);
248        }
249        if (shouldFallbackToInvoke()) {
250            replacementNodes.add(null);
251        }
252
253        Collection<Node> canonicalizeNodes = new ArrayList<>();
254        // do the actual inlining for every invoke
255        for (int i = 0; i < numberOfMethods; i++) {
256            Invoke invokeForInlining = (Invoke) successors[i].next();
257            canonicalizeNodes.addAll(inline(invokeForInlining, methodAt(i), inlineableElementAt(i), false));
258        }
259        if (returnValuePhi != null) {
260            canonicalizeNodes.add(returnValuePhi);
261        }
262        return canonicalizeNodes;
263    }
264
265    private int getTypeCount(int concreteMethodIndex) {
266        int count = 0;
267        for (int i = 0; i < typesToConcretes.size(); i++) {
268            if (typesToConcretes.get(i) == concreteMethodIndex) {
269                count++;
270            }
271        }
272        return count;
273    }
274
275    private ResolvedJavaType getLeastCommonType(int concreteMethodIndex) {
276        ResolvedJavaType commonType = null;
277        for (int i = 0; i < typesToConcretes.size(); i++) {
278            if (typesToConcretes.get(i) == concreteMethodIndex) {
279                if (commonType == null) {
280                    commonType = ptypes.get(i).getType();
281                } else {
282                    commonType = commonType.findLeastCommonAncestor(ptypes.get(i).getType());
283                }
284            }
285        }
286        assert commonType != null;
287        return commonType;
288    }
289
290    private ResolvedJavaType getLeastCommonType() {
291        ResolvedJavaType result = getLeastCommonType(0);
292        for (int i = 1; i < concretes.size(); i++) {
293            result = result.findLeastCommonAncestor(getLeastCommonType(i));
294        }
295        return result;
296    }
297
298    private Collection<Node> inlineSingleMethod(StructuredGraph graph, StampProvider stampProvider) {
299        assert concretes.size() == 1 && inlineableElements.length == 1 && ptypes.size() > 1 && !shouldFallbackToInvoke() && notRecordedTypeProbability == 0;
300
301        AbstractBeginNode calleeEntryNode = graph.add(new BeginNode());
302
303        AbstractBeginNode unknownTypeSux = createUnknownTypeSuccessor(graph);
304        AbstractBeginNode[] successors = new AbstractBeginNode[]{calleeEntryNode, unknownTypeSux};
305        createDispatchOnTypeBeforeInvoke(graph, successors, false, stampProvider);
306
307        calleeEntryNode.setNext(invoke.asNode());
308
309        return inline(invoke, methodAt(0), inlineableElementAt(0), false);
310    }
311
312    private boolean createDispatchOnTypeBeforeInvoke(StructuredGraph graph, AbstractBeginNode[] successors, boolean invokeIsOnlySuccessor, StampProvider stampProvider) {
313        assert ptypes.size() >= 1;
314        ValueNode nonNullReceiver = InliningUtil.nonNullReceiver(invoke);
315        LoadHubNode hub = graph.unique(new LoadHubNode(stampProvider, nonNullReceiver));
316
317        Debug.log("Type switch with %d types", concretes.size());
318
319        ResolvedJavaType[] keys = new ResolvedJavaType[ptypes.size()];
320        double[] keyProbabilities = new double[ptypes.size() + 1];
321        int[] keySuccessors = new int[ptypes.size() + 1];
322        double totalProbability = notRecordedTypeProbability;
323        for (int i = 0; i < ptypes.size(); i++) {
324            keys[i] = ptypes.get(i).getType();
325            keyProbabilities[i] = ptypes.get(i).getProbability();
326            totalProbability += keyProbabilities[i];
327            keySuccessors[i] = invokeIsOnlySuccessor ? 0 : typesToConcretes.get(i);
328            assert keySuccessors[i] < successors.length - 1 : "last successor is the unknownTypeSux";
329        }
330        keyProbabilities[keyProbabilities.length - 1] = notRecordedTypeProbability;
331        keySuccessors[keySuccessors.length - 1] = successors.length - 1;
332
333        // Normalize the probabilities.
334        for (int i = 0; i < keyProbabilities.length; i++) {
335            keyProbabilities[i] /= totalProbability;
336        }
337
338        TypeSwitchNode typeSwitch = graph.add(new TypeSwitchNode(hub, successors, keys, keyProbabilities, keySuccessors));
339        FixedWithNextNode pred = (FixedWithNextNode) invoke.asNode().predecessor();
340        pred.setNext(typeSwitch);
341        return false;
342    }
343
344    private static AbstractBeginNode createInvocationBlock(StructuredGraph graph, Invoke invoke, AbstractMergeNode returnMerge, PhiNode returnValuePhi, AbstractMergeNode exceptionMerge,
345                    PhiNode exceptionObjectPhi, boolean useForInlining) {
346        Invoke duplicatedInvoke = duplicateInvokeForInlining(graph, invoke, exceptionMerge, exceptionObjectPhi, useForInlining);
347        AbstractBeginNode calleeEntryNode = graph.add(new BeginNode());
348        calleeEntryNode.setNext(duplicatedInvoke.asNode());
349
350        EndNode endNode = graph.add(new EndNode());
351        duplicatedInvoke.setNext(endNode);
352        returnMerge.addForwardEnd(endNode);
353
354        if (returnValuePhi != null) {
355            returnValuePhi.addInput(duplicatedInvoke.asNode());
356        }
357        return calleeEntryNode;
358    }
359
360    private static Invoke duplicateInvokeForInlining(StructuredGraph graph, Invoke invoke, AbstractMergeNode exceptionMerge, PhiNode exceptionObjectPhi, boolean useForInlining) {
361        Invoke result = (Invoke) invoke.asNode().copyWithInputs();
362        Node callTarget = result.callTarget().copyWithInputs();
363        result.asNode().replaceFirstInput(result.callTarget(), callTarget);
364        result.setUseForInlining(useForInlining);
365
366        Kind kind = invoke.asNode().getKind();
367        if (kind != Kind.Void) {
368            FrameState stateAfter = invoke.stateAfter();
369            stateAfter = stateAfter.duplicate(stateAfter.bci);
370            stateAfter.replaceFirstInput(invoke.asNode(), result.asNode());
371            result.setStateAfter(stateAfter);
372        }
373
374        if (invoke instanceof InvokeWithExceptionNode) {
375            assert exceptionMerge != null && exceptionObjectPhi != null;
376
377            InvokeWithExceptionNode invokeWithException = (InvokeWithExceptionNode) invoke;
378            ExceptionObjectNode exceptionEdge = (ExceptionObjectNode) invokeWithException.exceptionEdge();
379            FrameState stateAfterException = exceptionEdge.stateAfter();
380
381            ExceptionObjectNode newExceptionEdge = (ExceptionObjectNode) exceptionEdge.copyWithInputs();
382            // set new state (pop old exception object, push new one)
383            newExceptionEdge.setStateAfter(stateAfterException.duplicateModified(Kind.Object, Kind.Object, newExceptionEdge));
384
385            EndNode endNode = graph.add(new EndNode());
386            newExceptionEdge.setNext(endNode);
387            exceptionMerge.addForwardEnd(endNode);
388            exceptionObjectPhi.addInput(newExceptionEdge);
389
390            ((InvokeWithExceptionNode) result).setExceptionEdge(newExceptionEdge);
391        }
392        return result;
393    }
394
395    @Override
396    public void tryToDevirtualizeInvoke(Providers providers) {
397        if (hasSingleMethod()) {
398            devirtualizeWithTypeSwitch(graph(), InvokeKind.Special, concretes.get(0), providers.getStampProvider());
399        } else {
400            tryToDevirtualizeMultipleMethods(graph(), providers.getStampProvider());
401        }
402    }
403
404    private void tryToDevirtualizeMultipleMethods(StructuredGraph graph, StampProvider stampProvider) {
405        MethodCallTargetNode methodCallTarget = (MethodCallTargetNode) invoke.callTarget();
406        if (methodCallTarget.invokeKind() == InvokeKind.Interface) {
407            ResolvedJavaMethod targetMethod = methodCallTarget.targetMethod();
408            ResolvedJavaType leastCommonType = getLeastCommonType();
409            ResolvedJavaType contextType = invoke.getContextType();
410            // check if we have a common base type that implements the interface -> in that case
411            // we have a vtable entry for the interface method and can use a less expensive
412            // virtual call
413            if (!leastCommonType.isInterface() && targetMethod.getDeclaringClass().isAssignableFrom(leastCommonType)) {
414                ResolvedJavaMethod baseClassTargetMethod = leastCommonType.resolveConcreteMethod(targetMethod, contextType);
415                if (baseClassTargetMethod != null) {
416                    devirtualizeWithTypeSwitch(graph, InvokeKind.Virtual, leastCommonType.resolveConcreteMethod(targetMethod, contextType), stampProvider);
417                }
418            }
419        }
420    }
421
422    private void devirtualizeWithTypeSwitch(StructuredGraph graph, InvokeKind kind, ResolvedJavaMethod target, StampProvider stampProvider) {
423        AbstractBeginNode invocationEntry = graph.add(new BeginNode());
424        AbstractBeginNode unknownTypeSux = createUnknownTypeSuccessor(graph);
425        AbstractBeginNode[] successors = new AbstractBeginNode[]{invocationEntry, unknownTypeSux};
426        createDispatchOnTypeBeforeInvoke(graph, successors, true, stampProvider);
427
428        invocationEntry.setNext(invoke.asNode());
429        ValueNode receiver = ((MethodCallTargetNode) invoke.callTarget()).receiver();
430        GuardedValueNode anchoredReceiver = InliningUtil.createAnchoredReceiver(graph, invocationEntry, target.getDeclaringClass(), receiver, false);
431        invoke.callTarget().replaceFirstInput(receiver, anchoredReceiver);
432        InliningUtil.replaceInvokeCallTarget(invoke, graph, kind, target);
433    }
434
435    private static AbstractBeginNode createUnknownTypeSuccessor(StructuredGraph graph) {
436        return BeginNode.begin(graph.add(new DeoptimizeNode(DeoptimizationAction.InvalidateReprofile, DeoptimizationReason.TypeCheckedInliningViolated)));
437    }
438
439    @Override
440    public String toString() {
441        StringBuilder builder = new StringBuilder(shouldFallbackToInvoke() ? "megamorphic" : "polymorphic");
442        builder.append(", ");
443        builder.append(concretes.size());
444        builder.append(" methods [ ");
445        for (int i = 0; i < concretes.size(); i++) {
446            builder.append(concretes.get(i).format("  %H.%n(%p):%r"));
447        }
448        builder.append(" ], ");
449        builder.append(ptypes.size());
450        builder.append(" type checks [ ");
451        for (int i = 0; i < ptypes.size(); i++) {
452            builder.append("  ");
453            builder.append(ptypes.get(i).getType().getName());
454            builder.append(ptypes.get(i).getProbability());
455        }
456        builder.append(" ]");
457        return builder.toString();
458    }
459}