Source code

001/*
002 * Copyright (c) 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.replacements;
024
025import static com.oracle.graal.graphbuilderconf.IntrinsicContext.CompilationContext.*;
026
027import java.lang.reflect.*;
028import java.util.*;
029
030import jdk.internal.jvmci.code.*;
031import jdk.internal.jvmci.meta.*;
032
033import com.oracle.graal.graph.*;
034import com.oracle.graal.graphbuilderconf.*;
035import com.oracle.graal.graphbuilderconf.GraphBuilderConfiguration.Plugins;
036import com.oracle.graal.java.*;
037import com.oracle.graal.nodes.*;
038import com.oracle.graal.nodes.CallTargetNode.InvokeKind;
039import com.oracle.graal.nodes.StructuredGraph.AllowAssumptions;
040import com.oracle.graal.nodes.calc.*;
041import com.oracle.graal.nodes.java.*;
042import com.oracle.graal.nodes.type.*;
043import com.oracle.graal.phases.*;
044import com.oracle.graal.phases.common.*;
045import com.oracle.graal.phases.common.DeadCodeEliminationPhase.Optionality;
046import com.oracle.graal.phases.common.inlining.*;
047import com.oracle.graal.phases.util.*;
048import com.oracle.graal.word.*;
049
050/**
051 * A utility for manually creating a graph. This will be expanded as necessary to support all
052 * subsystems that employ manual graph creation (as opposed to {@linkplain GraphBuilderPhase
053 * bytecode parsing} based graph creation).
054 */
055public class GraphKit {
056
057    protected final Providers providers;
058    protected final StructuredGraph graph;
059    protected final WordTypes wordTypes;
060    protected final GraphBuilderConfiguration.Plugins graphBuilderPlugins;
061    protected FixedWithNextNode lastFixedNode;
062
063    private final List<Structure> structures;
064
065    abstract static class Structure {
066    }
067
068    public GraphKit(StructuredGraph graph, Providers providers, WordTypes wordTypes, GraphBuilderConfiguration.Plugins graphBuilderPlugins) {
069        this.providers = providers;
070        this.graph = graph;
071        this.wordTypes = wordTypes;
072        this.graphBuilderPlugins = graphBuilderPlugins;
073        this.lastFixedNode = graph.start();
074
075        structures = new ArrayList<>();
076        /* Add a dummy element, so that the access of the last element never leads to an exception. */
077        structures.add(new Structure() {
078        });
079    }
080
081    public StructuredGraph getGraph() {
082        return graph;
083    }
084
085    /**
086     * Ensures a floating node is added to or already present in the graph via {@link Graph#unique}.
087     *
088     * @return a node similar to {@code node} if one exists, otherwise {@code node}
089     */
090    public <T extends FloatingNode> T unique(T node) {
091        return graph.unique(changeToWord(node));
092    }
093
094    public <T extends ValueNode> T changeToWord(T node) {
095        if (wordTypes != null && wordTypes.isWord(node)) {
096            node.setStamp(wordTypes.getWordStamp(StampTool.typeOrNull(node)));
097        }
098        return node;
099    }
100
101    /**
102     * Appends a fixed node to the graph.
103     */
104    public <T extends FixedNode> T append(T node) {
105        T result = graph.add(changeToWord(node));
106        assert lastFixedNode != null;
107        assert result.predecessor() == null;
108        graph.addAfterFixed(lastFixedNode, result);
109        if (result instanceof FixedWithNextNode) {
110            lastFixedNode = (FixedWithNextNode) result;
111        } else {
112            lastFixedNode = null;
113        }
114        return result;
115    }
116
117    public InvokeNode createInvoke(Class<?> declaringClass, String name, ValueNode... args) {
118        return createInvoke(declaringClass, name, InvokeKind.Static, null, BytecodeFrame.UNKNOWN_BCI, args);
119    }
120
121    /**
122     * Creates and appends an {@link InvokeNode} for a call to a given method with a given set of
123     * arguments. The method is looked up via reflection based on the declaring class and name.
124     *
125     * @param declaringClass the class declaring the invoked method
126     * @param name the name of the invoked method
127     * @param args the arguments to the invocation
128     */
129    public InvokeNode createInvoke(Class<?> declaringClass, String name, InvokeKind invokeKind, FrameStateBuilder frameStateBuilder, int bci, ValueNode... args) {
130        boolean isStatic = invokeKind == InvokeKind.Static;
131        ResolvedJavaMethod method = findMethod(declaringClass, name, isStatic);
132        return createInvoke(method, invokeKind, frameStateBuilder, bci, args);
133    }
134
135    public ResolvedJavaMethod findMethod(Class<?> declaringClass, String name, boolean isStatic) {
136        ResolvedJavaMethod method = null;
137        for (Method m : declaringClass.getDeclaredMethods()) {
138            if (Modifier.isStatic(m.getModifiers()) == isStatic && m.getName().equals(name)) {
139                assert method == null : "found more than one method in " + declaringClass + " named " + name;
140                method = providers.getMetaAccess().lookupJavaMethod(m);
141            }
142        }
143        assert method != null : "did not find method in " + declaringClass + " named " + name;
144        return method;
145    }
146
147    /**
148     * Creates and appends an {@link InvokeNode} for a call to a given method with a given set of
149     * arguments.
150     */
151    public InvokeNode createInvoke(ResolvedJavaMethod method, InvokeKind invokeKind, FrameStateBuilder frameStateBuilder, int bci, ValueNode... args) {
152        assert method.isStatic() == (invokeKind == InvokeKind.Static);
153        Signature signature = method.getSignature();
154        JavaType returnType = signature.getReturnType(null);
155        assert checkArgs(method, args);
156        MethodCallTargetNode callTarget = graph.add(createMethodCallTarget(invokeKind, method, args, returnType, bci));
157        InvokeNode invoke = append(new InvokeNode(callTarget, bci));
158
159        if (frameStateBuilder != null) {
160            if (invoke.getKind() != Kind.Void) {
161                frameStateBuilder.push(returnType.getKind(), invoke);
162            }
163            invoke.setStateAfter(frameStateBuilder.create(bci, invoke));
164            if (invoke.getKind() != Kind.Void) {
165                frameStateBuilder.pop(returnType.getKind());
166            }
167        }
168        return invoke;
169    }
170
171    protected MethodCallTargetNode createMethodCallTarget(InvokeKind invokeKind, ResolvedJavaMethod targetMethod, ValueNode[] args, JavaType returnType, @SuppressWarnings("unused") int bci) {
172        return new MethodCallTargetNode(invokeKind, targetMethod, args, returnType, null);
173    }
174
175    /**
176     * Determines if a given set of arguments is compatible with the signature of a given method.
177     *
178     * @return true if {@code args} are compatible with the signature if {@code method}
179     * @throws AssertionError if {@code args} are not compatible with the signature if
180     *             {@code method}
181     */
182    public boolean checkArgs(ResolvedJavaMethod method, ValueNode... args) {
183        Signature signature = method.getSignature();
184        boolean isStatic = method.isStatic();
185        if (signature.getParameterCount(!isStatic) != args.length) {
186            throw new AssertionError(graph + ": wrong number of arguments to " + method);
187        }
188        int argIndex = 0;
189        if (!isStatic) {
190            ResolvedJavaType expectedType = method.getDeclaringClass();
191            Kind expected = wordTypes == null ? expectedType.getKind() : wordTypes.asKind(expectedType);
192            Kind actual = args[argIndex++].stamp().getStackKind();
193            assert expected == actual : graph + ": wrong kind of value for receiver argument of call to " + method + " [" + actual + " != " + expected + "]";
194        }
195        for (int i = 0; i != signature.getParameterCount(false); i++) {
196            JavaType expectedType = signature.getParameterType(i, method.getDeclaringClass());
197            Kind expected = wordTypes == null ? expectedType.getKind().getStackKind() : wordTypes.asKind(expectedType).getStackKind();
198            Kind actual = args[argIndex++].stamp().getStackKind();
199            if (expected != actual) {
200                throw new AssertionError(graph + ": wrong kind of value for argument " + i + " of call to " + method + " [" + actual + " != " + expected + "]");
201            }
202        }
203        return true;
204    }
205
206    /**
207     * Recursively {@linkplain #inline inlines} all invocations currently in the graph.
208     */
209    public void inlineInvokes() {
210        while (!graph.getNodes().filter(InvokeNode.class).isEmpty()) {
211            for (InvokeNode invoke : graph.getNodes().filter(InvokeNode.class).snapshot()) {
212                inline(invoke);
213            }
214        }
215
216        // Clean up all code that is now dead after inlining.
217        new DeadCodeEliminationPhase().apply(graph);
218    }
219
220    /**
221     * Inlines a given invocation to a method. The graph of the inlined method is processed in the
222     * same manner as for snippets and method substitutions.
223     */
224    public void inline(InvokeNode invoke) {
225        ResolvedJavaMethod method = ((MethodCallTargetNode) invoke.callTarget()).targetMethod();
226
227        MetaAccessProvider metaAccess = providers.getMetaAccess();
228        Plugins plugins = new Plugins(graphBuilderPlugins);
229        GraphBuilderConfiguration config = GraphBuilderConfiguration.getSnippetDefault(plugins);
230
231        StructuredGraph calleeGraph = new StructuredGraph(method, AllowAssumptions.NO);
232        IntrinsicContext initialReplacementContext = new IntrinsicContext(method, method, INLINE_AFTER_PARSING);
233        new GraphBuilderPhase.Instance(metaAccess, providers.getStampProvider(), providers.getConstantReflection(), config, OptimisticOptimizations.NONE, initialReplacementContext).apply(calleeGraph);
234
235        // Remove all frame states from inlinee
236        for (Node node : calleeGraph.getNodes()) {
237            if (node instanceof StateSplit) {
238                ((StateSplit) node).setStateAfter(null);
239            }
240        }
241        new DeadCodeEliminationPhase(Optionality.Required).apply(calleeGraph);
242
243        InliningUtil.inline(invoke, calleeGraph, false, null);
244    }
245
246    protected void pushStructure(Structure structure) {
247        structures.add(structure);
248    }
249
250    protected <T extends Structure> T getTopStructure(Class<T> expectedClass) {
251        return expectedClass.cast(structures.get(structures.size() - 1));
252    }
253
254    protected void popStructure() {
255        structures.remove(structures.size() - 1);
256    }
257
258    protected enum IfState {
259        CONDITION,
260        THEN_PART,
261        ELSE_PART,
262        FINISHED
263    }
264
265    static class IfStructure extends Structure {
266        protected IfState state;
267        protected FixedNode thenPart;
268        protected FixedNode elsePart;
269    }
270
271    /**
272     * Starts an if-block. This call can be followed by a call to {@link #thenPart} to start
273     * emitting the code executed when the condition hold; and a call to {@link #elsePart} to start
274     * emititng the code when the condition does not hold. It must be followed by a call to
275     * {@link #endIf} to close the if-block.
276     *
277     * @param condition The condition for the if-block
278     * @param trueProbability The estimated probability the the condition is true
279     */
280    public void startIf(LogicNode condition, double trueProbability) {
281        AbstractBeginNode thenSuccessor = graph.add(new BeginNode());
282        AbstractBeginNode elseSuccessor = graph.add(new BeginNode());
283        append(new IfNode(condition, thenSuccessor, elseSuccessor, trueProbability));
284        lastFixedNode = null;
285
286        IfStructure s = new IfStructure();
287        s.state = IfState.CONDITION;
288        s.thenPart = thenSuccessor;
289        s.elsePart = elseSuccessor;
290        pushStructure(s);
291    }
292
293    private IfStructure saveLastNode() {
294        IfStructure s = getTopStructure(IfStructure.class);
295        switch (s.state) {
296            case CONDITION:
297                assert lastFixedNode == null;
298                break;
299            case THEN_PART:
300                s.thenPart = lastFixedNode;
301                break;
302            case ELSE_PART:
303                s.elsePart = lastFixedNode;
304                break;
305            case FINISHED:
306                assert false;
307                break;
308        }
309        lastFixedNode = null;
310        return s;
311    }
312
313    public void thenPart() {
314        IfStructure s = saveLastNode();
315        lastFixedNode = (FixedWithNextNode) s.thenPart;
316        s.state = IfState.THEN_PART;
317    }
318
319    public void elsePart() {
320        IfStructure s = saveLastNode();
321        lastFixedNode = (FixedWithNextNode) s.elsePart;
322        s.state = IfState.ELSE_PART;
323    }
324
325    public void endIf() {
326        IfStructure s = saveLastNode();
327
328        FixedWithNextNode thenPart = s.thenPart instanceof FixedWithNextNode ? (FixedWithNextNode) s.thenPart : null;
329        FixedWithNextNode elsePart = s.elsePart instanceof FixedWithNextNode ? (FixedWithNextNode) s.elsePart : null;
330
331        if (thenPart != null && elsePart != null) {
332            /* Both parts are alive, we need a real merge. */
333            EndNode thenEnd = graph.add(new EndNode());
334            graph.addAfterFixed(thenPart, thenEnd);
335            EndNode elseEnd = graph.add(new EndNode());
336            graph.addAfterFixed(elsePart, elseEnd);
337
338            AbstractMergeNode merge = graph.add(new MergeNode());
339            merge.addForwardEnd(thenEnd);
340            merge.addForwardEnd(elseEnd);
341
342            lastFixedNode = merge;
343
344        } else if (thenPart != null) {
345            /* elsePart ended with a control sink, so we can continue with thenPart. */
346            lastFixedNode = thenPart;
347
348        } else if (elsePart != null) {
349            /* thenPart ended with a control sink, so we can continue with elsePart. */
350            lastFixedNode = elsePart;
351
352        } else {
353            /* Both parts ended with a control sink, so no nodes can be added after the if. */
354            assert lastFixedNode == null;
355        }
356        s.state = IfState.FINISHED;
357        popStructure();
358    }
359}