# HG changeset patch
# User Christian Wimmer <christian.wimmer@oracle.com>
# Date 1422578013 28800
# Node ID 9a659d65bdddc1a4bfa071c9b4bb7cb45991a4ed
# Parent  a143c9cafe16b6677427bdc0c097d50aadb1d6db
Examples for Graal tutorial

diff -r a143c9cafe16 -r 9a659d65bddd graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/tutorial/GraalTutorial.java
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/tutorial/GraalTutorial.java	Thu Jan 29 16:33:33 2015 -0800
@@ -0,0 +1,157 @@
+/*
+ * Copyright (c) 2015, 2015, Oracle and/or its affiliates. All rights reserved.
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
+ *
+ * This code is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 only, as
+ * published by the Free Software Foundation.
+ *
+ * This code is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+ * version 2 for more details (a copy is included in the LICENSE file that
+ * accompanied this code).
+ *
+ * You should have received a copy of the GNU General Public License version
+ * 2 along with this work; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
+ *
+ * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
+ * or visit www.oracle.com if you need additional information or have any
+ * questions.
+ */
+package com.oracle.graal.compiler.test.tutorial;
+
+import org.junit.*;
+
+import com.oracle.graal.api.code.*;
+
+/**
+ * Examples for the Graal tutorial. Run them using the unittest harness of the mx script. To look at
+ * the examples in IGV (the graph visualization tool), use the options -G:Dump and -G:MethodFilter.
+ * For example, run the first test case using
+ *
+ * <pre>
+ * mx unittest -G:Dump= -G:MethodFilter=String.hashCode GraalTutorial#testStringHashCode
+ * </pre>
+ */
+public class GraalTutorial extends InvokeGraal {
+
+    /*
+     * A simple Graal compilation example: Compile the method String.hashCode()
+     */
+
+    @Test
+    public void testStringHashCode() throws InvalidInstalledCodeException {
+        InstalledCode installedCode = compileAndInstallMethod(findMethod(String.class, "hashCode"));
+
+        int result = (int) installedCode.executeVarargs("Hello World");
+        Assert.assertEquals(-862545276, result);
+    }
+
+    /*
+     * Tutorial example for speculative optimizations.
+     */
+
+    int f1;
+    int f2;
+
+    public void speculativeOptimization(boolean flag) {
+        f1 = 41;
+        if (flag) {
+            f2 = 42;
+            return;
+        }
+        f2 = 43;
+    }
+
+    @Test
+    public void testSpeculativeOptimization() throws InvalidInstalledCodeException {
+        /*
+         * Collect profiling information by running the method in the interpreter.
+         */
+        for (int i = 0; i < 10000; i++) {
+            speculativeOptimization(false);
+        }
+
+        /*
+         * Warmup to collect profiling information is done, now we compile the method. Since the
+         * value of "flag" was always false during the warmup, the compiled code speculates that the
+         * value remains false.
+         */
+
+        InstalledCode compiledMethod = compileAndInstallMethod(findMethod(GraalTutorial.class, "speculativeOptimization"));
+        f1 = 0;
+        f2 = 0;
+        compiledMethod.executeVarargs(this, true);
+        Assert.assertEquals(41, f1);
+        Assert.assertEquals(42, f2);
+
+        /*
+         * We executed the compiled method with a "flag" value that triggered deoptimization (since
+         * the warmup always used the different "flag" value). The interpreter updated the profiling
+         * information, so the second compilation does not perform the speculative optimization.
+         */
+
+        compiledMethod = compileAndInstallMethod(findMethod(GraalTutorial.class, "speculativeOptimization"));
+        f1 = 0;
+        f2 = 0;
+        compiledMethod.executeVarargs(this, false);
+        Assert.assertEquals(41, f1);
+        Assert.assertEquals(43, f2);
+    }
+
+    /*
+     * Tutorial example for snippets and lowering.
+     */
+
+    static class A {
+    }
+
+    static class B extends A {
+    }
+
+    public static int instanceOfUsage(Object obj) {
+        if (obj instanceof A) {
+            return 42;
+        } else {
+            return 0;
+        }
+    }
+
+    @Test
+    public void testInstanceOfUsage() throws InvalidInstalledCodeException {
+        A a = new A();
+
+        /* Allocate an (unsued) instance of B so that the class B gets loaded. */
+        @SuppressWarnings("unused")
+        B b = new B();
+
+        for (int i = 0; i < 10000; i++) {
+            instanceOfUsage(a);
+        }
+
+        /* Warmup to collect profiling information is done, now compile the method. */
+
+        InstalledCode compiledMethod = compileAndInstallMethod(findMethod(GraalTutorial.class, "instanceOfUsage"));
+
+        int result = (int) compiledMethod.executeVarargs(a);
+        Assert.assertEquals(42, result);
+    }
+
+    /*
+     * Tutorial example for intrinsic methods.
+     */
+
+    public static double intrinsicUsage(double val) {
+        return Math.sin(val);
+    }
+
+    @Test
+    public void testIntrinsicUsage() throws InvalidInstalledCodeException {
+        InstalledCode compiledMethod = compileAndInstallMethod(findMethod(GraalTutorial.class, "intrinsicUsage"));
+
+        double result = (double) compiledMethod.executeVarargs(42d);
+        Assert.assertEquals(Math.sin(42), result, 0);
+    }
+}
diff -r a143c9cafe16 -r 9a659d65bddd graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/tutorial/InvokeGraal.java
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/tutorial/InvokeGraal.java	Thu Jan 29 16:33:33 2015 -0800
@@ -0,0 +1,150 @@
+/*
+ * Copyright (c) 2015, 2015, Oracle and/or its affiliates. All rights reserved.
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
+ *
+ * This code is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 only, as
+ * published by the Free Software Foundation.
+ *
+ * This code is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+ * version 2 for more details (a copy is included in the LICENSE file that
+ * accompanied this code).
+ *
+ * You should have received a copy of the GNU General Public License version
+ * 2 along with this work; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
+ *
+ * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
+ * or visit www.oracle.com if you need additional information or have any
+ * questions.
+ */
+package com.oracle.graal.compiler.test.tutorial;
+
+import java.lang.reflect.*;
+import java.util.*;
+import java.util.concurrent.atomic.*;
+
+import com.oracle.graal.api.code.*;
+import com.oracle.graal.api.code.CallingConvention.Type;
+import com.oracle.graal.api.meta.*;
+import com.oracle.graal.api.runtime.*;
+import com.oracle.graal.compiler.*;
+import com.oracle.graal.compiler.target.*;
+import com.oracle.graal.debug.*;
+import com.oracle.graal.debug.Debug.Scope;
+import com.oracle.graal.lir.asm.*;
+import com.oracle.graal.nodes.*;
+import com.oracle.graal.phases.*;
+import com.oracle.graal.phases.tiers.*;
+import com.oracle.graal.phases.util.*;
+import com.oracle.graal.runtime.*;
+
+/**
+ * Sample code that shows how to invoke Graal from an application.
+ */
+public class InvokeGraal {
+
+    protected final Backend backend;
+    protected final Providers providers;
+    protected final MetaAccessProvider metaAccess;
+    protected final CodeCacheProvider codeCache;
+    protected final TargetDescription target;
+
+    public InvokeGraal() {
+        /* Ask the hosting Java VM for the entry point object to the Graal API. */
+        RuntimeProvider runtimeProvider = Graal.getRequiredCapability(RuntimeProvider.class);
+
+        /* The default backend (architecture, VM configuration) that the hosting VM is running on. */
+        backend = runtimeProvider.getHostBackend();
+        /* Access to all of the Graal API providers, as implemented by the hosting VM. */
+        providers = backend.getProviders();
+        /* Some frequently used providers and configuration objects. */
+        metaAccess = providers.getMetaAccess();
+        codeCache = providers.getCodeCache();
+        target = codeCache.getTarget();
+    }
+
+    private static AtomicInteger compilationId = new AtomicInteger();
+
+    /**
+     * The simplest way to compile a method, using the default behavior for everything.
+     */
+    protected InstalledCode compileAndInstallMethod(ResolvedJavaMethod method) {
+        /* Ensure every compilation gets a unique number, visible in IGV. */
+        try (Scope s = Debug.scope("compileAndInstallMethod", new DebugDumpScope(String.valueOf(compilationId.incrementAndGet()), true))) {
+
+            /*
+             * The graph that is compiled. We leave it empty (no nodes added yet). This means that
+             * it will be filled according to the graphBuilderSuite defined below.
+             */
+            StructuredGraph graph = new StructuredGraph(method);
+
+            /*
+             * The phases used to build the graph. Usually this is just the GraphBuilderPhase. If
+             * the graph already contains nodes, it is ignored.
+             */
+            PhaseSuite<HighTierContext> graphBuilderSuite = backend.getSuites().getDefaultGraphBuilderSuite();
+
+            /*
+             * The optimization phases that are applied to the graph. This is the main configuration
+             * point for Graal. Add or remove phases to customize your compilation.
+             */
+            Suites suites = backend.getSuites().createSuites();
+
+            /*
+             * The calling convention for the machine code. You should have a very good reason
+             * before you switch to a different calling convention than the one that the VM provides
+             * by default.
+             */
+            CallingConvention callingConvention = CodeUtil.getCallingConvention(codeCache, Type.JavaCallee, method, false);
+
+            /*
+             * We want Graal to perform all speculative optimisitic optimizations, using the
+             * profiling information that comes with the method (collected by the interpreter) for
+             * speculation.
+             */
+            OptimisticOptimizations optimisticOpts = OptimisticOptimizations.ALL;
+            ProfilingInfo profilingInfo = method.getProfilingInfo();
+
+            /* The default class and configuration for compilation results. */
+            CompilationResult compilationResult = new CompilationResult();
+            CompilationResultBuilderFactory factory = CompilationResultBuilderFactory.Default;
+
+            /* Advanced configuration objects that are not mandatory. */
+            Map<ResolvedJavaMethod, StructuredGraph> cache = null;
+            Object stub = null;
+            SpeculationLog speculationLog = null;
+
+            /* Invoke the whole Graal compilation pipeline. */
+            GraalCompiler.compileGraph(graph, stub, callingConvention, method, providers, backend, target, cache, graphBuilderSuite, optimisticOpts, profilingInfo, speculationLog, suites,
+                            compilationResult, factory);
+
+            /*
+             * Install the compilation result into the VM, i.e., copy the byte[] array that contains
+             * the machine code into an actual executable memory location.
+             */
+            InstalledCode installedCode = codeCache.addMethod(method, compilationResult, null, null);
+
+            return installedCode;
+        } catch (Throwable ex) {
+            throw Debug.handle(ex);
+        }
+    }
+
+    /**
+     * Look up a method using Java reflection and convert it to the Graal API method object.
+     */
+    protected ResolvedJavaMethod findMethod(Class<?> declaringClass, String name) {
+        Method reflectionMethod = null;
+        for (Method m : declaringClass.getDeclaredMethods()) {
+            if (m.getName().equals(name)) {
+                assert reflectionMethod == null : "More than one method with name " + name + " in class " + declaringClass.getName();
+                reflectionMethod = m;
+            }
+        }
+        assert reflectionMethod != null : "No method with name " + name + " in class " + declaringClass.getName();
+        return metaAccess.lookupJavaMethod(reflectionMethod);
+    }
+}
diff -r a143c9cafe16 -r 9a659d65bddd graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/tutorial/StaticAnalysis.java
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/tutorial/StaticAnalysis.java	Thu Jan 29 16:33:33 2015 -0800
@@ -0,0 +1,583 @@
+/*
+ * Copyright (c) 2015, 2015, Oracle and/or its affiliates. All rights reserved.
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
+ *
+ * This code is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 only, as
+ * published by the Free Software Foundation.
+ *
+ * This code is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+ * version 2 for more details (a copy is included in the LICENSE file that
+ * accompanied this code).
+ *
+ * You should have received a copy of the GNU General Public License version
+ * 2 along with this work; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
+ *
+ * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
+ * or visit www.oracle.com if you need additional information or have any
+ * questions.
+ */
+package com.oracle.graal.compiler.test.tutorial;
+
+import java.util.*;
+
+import com.oracle.graal.api.meta.*;
+import com.oracle.graal.compiler.common.*;
+import com.oracle.graal.debug.*;
+import com.oracle.graal.debug.Debug.Scope;
+import com.oracle.graal.graph.*;
+import com.oracle.graal.java.*;
+import com.oracle.graal.nodes.CallTargetNode.InvokeKind;
+import com.oracle.graal.nodes.*;
+import com.oracle.graal.nodes.java.*;
+import com.oracle.graal.nodes.util.*;
+import com.oracle.graal.phases.*;
+import com.oracle.graal.phases.graph.*;
+
+/**
+ * A simple context-insensitive static analysis based on the Graal API. It is intended for
+ * educational purposes, not for use in production. Only a limited set of Java functionality is
+ * supported to keep the code minimal.
+ * <p>
+ * The analysis builds a directed graph of {@link TypeFlow type flows}. If a type is added to type
+ * flow, it is propagated to all {@link TypeFlow#uses uses} of the type flow. Types are propagated
+ * using a {@link #worklist} of changed type flows until a fixpoint is reached, i.e., until no more
+ * types need to be added to any type state.
+ * <p>
+ * The type flows are constructed from a high-level Graal graph by the {@link TypeFlowBuilder}. All
+ * nodes that operate on {@link Kind#Object object} values are converted to the appropriate type
+ * flows. The analysis is context insensitive: every Java field has {@link Results#lookupField one
+ * list} of types assigned to the field; every Java method has {@link Results#lookupMethod one
+ * state} for each {@link MethodState#formalParameters parameter} as well as the
+ * {@link MethodState#formalReturn return value}.
+ */
+public class StaticAnalysis {
+    /** Access to type, method, and fields using the Graal API. */
+    private final MetaAccessProvider metaAccess;
+    /** The results of the static analysis. */
+    private final Results results;
+    /** Worklist for fixpoint iteration. */
+    private final Deque<WorklistEntry> worklist;
+
+    public StaticAnalysis(MetaAccessProvider metaAccess) {
+        this.metaAccess = metaAccess;
+        this.results = new Results();
+        this.worklist = new ArrayDeque<>();
+    }
+
+    /**
+     * Adds a root method to the static analysis. The method must be static and must not have any
+     * parameters, because the possible types of the parametes would not be known.
+     */
+    public void addMethod(ResolvedJavaMethod method) {
+        if (!method.isStatic() || method.getSignature().getParameterCount(false) > 0) {
+            error("Entry point method is not static or has parameters: " + method.format("%H.%n(%p)"));
+        }
+        addToWorklist(results.lookupMethod(method));
+    }
+
+    /**
+     * Performs the fixed-point analysis that finds all methods transitively reachable from the
+     * {@link #addMethod root methods}.
+     */
+    public void finish() {
+        while (!worklist.isEmpty()) {
+            worklist.removeFirst().process();
+        }
+    }
+
+    /**
+     * Returns the static analysis results computed by {@link StaticAnalysis#finish}.
+     */
+    public Results getResults() {
+        return results;
+    }
+
+    protected void addToWorklist(WorklistEntry task) {
+        worklist.addLast(task);
+    }
+
+    protected static RuntimeException error(String msg) {
+        throw GraalInternalError.shouldNotReachHere(msg);
+    }
+
+    /**
+     * Base class for all work items that can be {@link #addToWorklist added to the worklist}.
+     */
+    abstract class WorklistEntry {
+        protected abstract void process();
+    }
+
+    /**
+     * The results computed by the static analysis.
+     */
+    public class Results {
+        private final TypeFlow allInstantiatedTypes;
+        private final Map<ResolvedJavaField, TypeFlow> fields;
+        private final Map<ResolvedJavaMethod, MethodState> methods;
+
+        protected Results() {
+            allInstantiatedTypes = new TypeFlow();
+            fields = new HashMap<>();
+            methods = new HashMap<>();
+        }
+
+        /**
+         * All {@link TypeFlow#getTypes() types} that are found to be instantiated, i.e., all types
+         * allocated by the reachable instance and array allocation bytecodes.
+         */
+        public TypeFlow getAllInstantiatedTypes() {
+            return allInstantiatedTypes;
+        }
+
+        /**
+         * All {@link TypeFlow#getTypes() types} that the given field can have, i.e., all types
+         * assigned by the reachable field store bytecodes.
+         */
+        public TypeFlow lookupField(ResolvedJavaField field) {
+            TypeFlow result = fields.get(field);
+            if (result == null) {
+                result = new TypeFlow();
+                fields.put(field, result);
+            }
+            return result;
+        }
+
+        /**
+         * All {@link TypeFlow#getTypes() types} that {@link MethodState#formalParameters
+         * parameters} and {@link MethodState#formalReturn return value} of the given method can
+         * have.
+         */
+        public MethodState lookupMethod(ResolvedJavaMethod method) {
+            MethodState result = methods.get(method);
+            if (result == null) {
+                result = new MethodState(method);
+                methods.put(method, result);
+            }
+            return result;
+        }
+    }
+
+    /**
+     * The {@link TypeFlow#getTypes() types} of the parameters and return value of a method. Also
+     * serves as the worklist element to parse the bytecodes of the method.
+     */
+    public class MethodState extends WorklistEntry {
+        private final ResolvedJavaMethod method;
+        private final TypeFlow[] formalParameters;
+        private final TypeFlow formalReturn;
+        private boolean processed;
+
+        protected MethodState(ResolvedJavaMethod method) {
+            this.method = method;
+
+            formalParameters = new TypeFlow[method.getSignature().getParameterCount(!method.isStatic())];
+            for (int i = 0; i < formalParameters.length; i++) {
+                formalParameters[i] = new TypeFlow();
+            }
+            formalReturn = new TypeFlow();
+        }
+
+        /**
+         * All {@link TypeFlow#getTypes() types} that the parameters of this method can have.
+         */
+        public TypeFlow[] getFormalParameters() {
+            return formalParameters;
+        }
+
+        /**
+         * All {@link TypeFlow#getTypes() types} that the return value of this method can have.
+         */
+        public TypeFlow getFormalReturn() {
+            return formalReturn;
+        }
+
+        @Override
+        protected void process() {
+            if (!processed) {
+                /* We want to process a method only once. */
+                processed = true;
+
+                /*
+                 * Build the Graal graph for the method using the bytecode parser provided by Graal.
+                 */
+
+                StructuredGraph graph = new StructuredGraph(method);
+                /*
+                 * Support for graph dumping, IGV uses this information to show the method name of a
+                 * graph.
+                 */
+                try (Scope scope = Debug.scope("graph building", graph)) {
+                    /*
+                     * We want all types to be resolved by the graph builder, i.e., we want classes
+                     * referenced by the bytecodes to be loaded and initialized. Since we do not run
+                     * the code before static analysis, the classes would otherwise be not loaded
+                     * yet and the bytecode parser would only create a graph.
+                     */
+                    GraphBuilderConfiguration graphBuilderConfig = GraphBuilderConfiguration.getEagerDefault().withOmitAllExceptionEdges(true);
+                    /*
+                     * For simplicity, we ignore all exception handling during the static analysis.
+                     * This is a constraint of this example code, a real static analysis needs to
+                     * handle the Graal nodes for throwing and handling exceptions.
+                     */
+                    graphBuilderConfig = graphBuilderConfig.withOmitAllExceptionEdges(true);
+                    /*
+                     * We do not want Graal to perform any speculative optimistic optimizations,
+                     * i.e., we do not want to use profiling information. Since we do not run the
+                     * code before static analysis, the profiling information is empty and therefore
+                     * wrong.
+                     */
+                    OptimisticOptimizations optimisticOpts = OptimisticOptimizations.NONE;
+
+                    GraphBuilderPhase.Instance graphBuilder = new GraphBuilderPhase.Instance(metaAccess, graphBuilderConfig, optimisticOpts);
+                    graphBuilder.apply(graph);
+                } catch (Throwable ex) {
+                    Debug.handle(ex);
+                }
+
+                /*
+                 * Build the type flow graph from the Graal graph, i.e., process all nodes that are
+                 * deal with objects.
+                 */
+
+                TypeFlowBuilder typeFlowBuilder = new TypeFlowBuilder(graph);
+                typeFlowBuilder.apply();
+            }
+        }
+    }
+
+    /**
+     * The active element during static analysis: types are added until a fixed point is reached.
+     * When a new type is added, it is propagated to all usages by putting this element on the
+     * {@link StaticAnalysis#addToWorklist worklist}.
+     */
+    public class TypeFlow extends WorklistEntry {
+        private final Set<ResolvedJavaType> types;
+        private final Set<TypeFlow> uses;
+
+        protected TypeFlow() {
+            types = new HashSet<>();
+            uses = new HashSet<>();
+        }
+
+        /** Returns the types of this element. */
+        public Set<ResolvedJavaType> getTypes() {
+            return types;
+        }
+
+        /**
+         * Adds new types to this element. If that changes the state of this element, it is added to
+         * the {@link StaticAnalysis#addToWorklist worklist} in order to propagate the added types
+         * to all usages.
+         */
+        protected void addTypes(Set<ResolvedJavaType> newTypes) {
+            if (types.addAll(newTypes)) {
+                addToWorklist(this);
+            }
+        }
+
+        /**
+         * Adds a new use to this element. All types of this element are propagated to the new
+         * usage.
+         */
+        protected void addUse(TypeFlow use) {
+            if (uses.add(use)) {
+                use.addTypes(types);
+            }
+        }
+
+        /**
+         * Processing of the worklist element: propagate the types to all usages. That in turn can
+         * add the usages to the worklist (if the types of the usage are changed).
+         */
+        @Override
+        protected void process() {
+            for (TypeFlow use : uses) {
+                use.addTypes(types);
+            }
+        }
+    }
+
+    /**
+     * The active element for method invocations. For {@link InvokeKind#Virtual virtual} and
+     * {@link InvokeKind#Interface interface} calls, the {@link TypeFlow#getTypes() types} of this
+     * node are the receiver types. When a new receiver type is added, a new callee might be added.
+     * Adding a new callee means liking the type flow of the actual parameters with the formal
+     * parameters of the callee, and linking the return value of the callee with the return value
+     * state of the invocation.
+     *
+     * Statically bindable methods calls ({@link InvokeKind#Static static} and
+     * {@link InvokeKind#Special special} calls) have only one callee, but use the same code for
+     * simplicity.
+     */
+
+    class InvokeTypeFlow extends TypeFlow {
+        private final MethodCallTargetNode callTarget;
+        private final TypeFlow[] actualParameters;
+        private final TypeFlow actualReturn;
+        private final Set<ResolvedJavaMethod> callees;
+
+        protected InvokeTypeFlow(MethodCallTargetNode callTarget, TypeFlow[] actualParameterFlows, TypeFlow actualReturnFlow) {
+            this.callTarget = callTarget;
+            this.actualParameters = actualParameterFlows;
+            this.actualReturn = actualReturnFlow;
+            this.callees = new HashSet<>();
+        }
+
+        private void linkCallee(ResolvedJavaMethod callee) {
+            if (callees.add(callee)) {
+                /* We have added a new callee. */
+
+                /*
+                 * Connect the actual parameters of the invocation with the formal parameters of the
+                 * callee.
+                 */
+                MethodState calleeState = results.lookupMethod(callee);
+                for (int i = 0; i < actualParameters.length; i++) {
+                    if (actualParameters[i] != null) {
+                        actualParameters[i].addUse(calleeState.formalParameters[i]);
+                    }
+                }
+
+                /*
+                 * Connect the formal return value of the callee with the actual return value of the
+                 * invocation.
+                 */
+                if (actualReturn != null) {
+                    calleeState.formalReturn.addUse(actualReturn);
+                }
+                addToWorklist(calleeState);
+            }
+        }
+
+        @Override
+        protected void process() {
+            if (callTarget.invokeKind().isDirect()) {
+                /* Static and special calls: link the statically known callee method. */
+                linkCallee(callTarget.targetMethod());
+            } else {
+                /* Virtual and interface call: Iterate all receiver types. */
+                for (ResolvedJavaType type : getTypes()) {
+                    /*
+                     * Resolve the method call for one exact receiver type. The method linking
+                     * semantics of Java are complicated, but fortunatley we can use the linker of
+                     * the hosting Java VM. The Graal API exposes this functionality.
+                     */
+                    ResolvedJavaMethod method = type.resolveConcreteMethod(callTarget.targetMethod(), callTarget.invoke().getContextType());
+
+                    /*
+                     * Since the static analysis is conservative, the list of receiver types can
+                     * contain types that actually do not provide the method to be called. Ignore
+                     * these.
+                     */
+                    if (method != null && !method.isAbstract()) {
+                        linkCallee(method);
+                    }
+                }
+            }
+            super.process();
+        }
+    }
+
+    /**
+     * Converts the Graal nodes of a method to a type flow graph. The main part of the algorithm is
+     * a reverse-postorder iteration of the Graal nodes, which is provided by the base class
+     * {@link StatelessPostOrderNodeIterator}.
+     */
+    class TypeFlowBuilder extends StatelessPostOrderNodeIterator {
+        private final StructuredGraph graph;
+        private final MethodState methodState;
+        /**
+         * Mapping from Graal nodes to type flows. This uses an efficient Graal-provided
+         * {@link NodeMap collection class}.
+         */
+        private final NodeMap<TypeFlow> typeFlows;
+
+        protected TypeFlowBuilder(StructuredGraph graph) {
+            super(graph.start());
+
+            this.graph = graph;
+            this.methodState = results.lookupMethod(graph.method());
+            this.typeFlows = new NodeMap<>(graph);
+        }
+
+        /**
+         * Register the type flow node for a Graal node.
+         */
+        private void registerFlow(ValueNode node, TypeFlow flow) {
+            /*
+             * We ignore intermediate nodes used by Graal that, e.g., add more type information or
+             * encapsulate values flowing out of loops.
+             */
+            ValueNode unproxiedNode = GraphUtil.unproxify(node);
+
+            assert typeFlows.get(unproxiedNode) == null : "overwriting existing value";
+            typeFlows.set(unproxiedNode, flow);
+        }
+
+        /**
+         * Lookup the type flow node for a Graal node.
+         */
+        private TypeFlow lookupFlow(ValueNode node) {
+            ValueNode unproxiedNode = GraphUtil.unproxify(node);
+            TypeFlow result = typeFlows.get(unproxiedNode);
+            if (result == null) {
+                /*
+                 * This is only the prototype of a static analysis, the handling of many Graal nodes
+                 * (such as array accesses) is not implemented.
+                 */
+                throw error("Node is not supported yet by static analysis: " + node.getClass().getName());
+            }
+            return result;
+        }
+
+        private boolean isObject(ValueNode node) {
+            return node.getKind() == Kind.Object;
+        }
+
+        @Override
+        public void apply() {
+            /*
+             * Before the reverse-postorder iteration of fixed nodes, we handle some classes of
+             * floating nodes.
+             */
+            for (Node n : graph.getNodes()) {
+                if (n instanceof ParameterNode) {
+                    /*
+                     * Incoming method parameter already have a type flow created by the
+                     * MethodState.
+                     */
+                    ParameterNode node = (ParameterNode) n;
+                    if (isObject(node)) {
+                        registerFlow(node, methodState.formalParameters[(node.index())]);
+                    }
+                } else if (n instanceof ValuePhiNode) {
+                    /*
+                     * Phi functions for loops are cyclic. We create the type flow here (before
+                     * processing any loop nodes), but link the phi values only later (after
+                     * processing of all loop nodes.
+                     */
+                    ValuePhiNode node = (ValuePhiNode) n;
+                    if (isObject(node)) {
+                        registerFlow(node, new TypeFlow());
+                    }
+                } else if (n instanceof ConstantNode) {
+                    /* Constants have a known type. */
+                    ConstantNode node = (ConstantNode) n;
+                    JavaConstant constant = node.asJavaConstant();
+                    if (constant.isNull()) {
+                        registerFlow(node, new TypeFlow());
+                    }
+                }
+            }
+
+            super.apply();
+
+            for (Node n : graph.getNodes()) {
+                if (n instanceof ValuePhiNode) {
+                    /*
+                     * Post-processing of phi functions. Now the type flow for all input values has
+                     * been created, so we can link the type flows together.
+                     */
+                    ValuePhiNode node = (ValuePhiNode) n;
+                    if (isObject(node)) {
+                        TypeFlow phiFlow = lookupFlow(node);
+                        for (ValueNode value : node.values()) {
+                            lookupFlow(value).addUse(phiFlow);
+                        }
+                    }
+                }
+            }
+        }
+
+        private void allocation(ValueNode node, ResolvedJavaType type) {
+            /*
+             * The type flow of allocation nodes is one exact type. This is the source of the
+             * fixpoint iteration, the types are propagated downwards from these sources.
+             */
+            TypeFlow flow = new TypeFlow();
+            flow.addTypes(Collections.singleton(type));
+            registerFlow(node, flow);
+            flow.addUse(results.getAllInstantiatedTypes());
+        }
+
+        @Override
+        protected void node(FixedNode n) {
+            if (n instanceof NewInstanceNode) {
+                NewInstanceNode node = (NewInstanceNode) n;
+                allocation(node, node.instanceClass());
+            } else if (n instanceof NewArrayNode) {
+                NewArrayNode node = (NewArrayNode) n;
+                allocation(node, node.elementType().getArrayClass());
+
+            } else if (n instanceof LoadFieldNode) {
+                /*
+                 * The type flow of a field load is the type flow of the field itself. It
+                 * accumulates all types ever stored to the field.
+                 */
+                LoadFieldNode node = (LoadFieldNode) n;
+                if (isObject(node)) {
+                    registerFlow(node, results.lookupField(node.field()));
+                }
+            } else if (n instanceof StoreFieldNode) {
+                /*
+                 * Connect the type flow of the stored value with the type flow of the field.
+                 */
+                StoreFieldNode node = (StoreFieldNode) n;
+                if (isObject(node.value())) {
+                    TypeFlow fieldFlow = results.lookupField(node.field());
+                    lookupFlow(node.value()).addUse(fieldFlow);
+                }
+
+            } else if (n instanceof ReturnNode) {
+                /*
+                 * Connect the type flow of the returned value with the formal return type flow of
+                 * the MethodState.
+                 */
+                ReturnNode node = (ReturnNode) n;
+                if (node.result() != null && isObject(node.result())) {
+                    lookupFlow(node.result()).addUse(methodState.formalReturn);
+                }
+
+            } else if (n instanceof Invoke) {
+                /*
+                 * Create the InvokeTypeFlow, which performs all the linking of actual and formal
+                 * parameter values with all identified callees.
+                 */
+                Invoke invoke = (Invoke) n;
+                MethodCallTargetNode callTarget = (MethodCallTargetNode) invoke.callTarget();
+
+                TypeFlow[] actualParameters = new TypeFlow[callTarget.arguments().size()];
+                for (int i = 0; i < actualParameters.length; i++) {
+                    ValueNode actualParam = callTarget.arguments().get(i);
+                    if (isObject(actualParam)) {
+                        actualParameters[i] = lookupFlow(actualParam);
+                    }
+                }
+                TypeFlow actualReturn = null;
+                if (isObject(invoke.asNode())) {
+                    actualReturn = new TypeFlow();
+                    registerFlow(invoke.asNode(), actualReturn);
+                }
+
+                InvokeTypeFlow invokeFlow = new InvokeTypeFlow(callTarget, actualParameters, actualReturn);
+
+                if (callTarget.invokeKind().isIndirect()) {
+                    /*
+                     * For virtual and interface calls, new receiver types can lead to new callees.
+                     * Connect the type flow of the receiver with the invocation flow.
+                     */
+                    lookupFlow(callTarget.arguments().get(0)).addUse(invokeFlow);
+                }
+                /*
+                 * Ensure the invocation is on the worklist at least once, even if it is a static
+                 * call with not parameters that does not involve any type flows.
+                 */
+                addToWorklist(invokeFlow);
+            }
+        }
+    }
+}
diff -r a143c9cafe16 -r 9a659d65bddd graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/tutorial/StaticAnalysisTests.java
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/tutorial/StaticAnalysisTests.java	Thu Jan 29 16:33:33 2015 -0800
@@ -0,0 +1,205 @@
+/*
+ * Copyright (c) 2015, 2015, Oracle and/or its affiliates. All rights reserved.
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
+ *
+ * This code is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 only, as
+ * published by the Free Software Foundation.
+ *
+ * This code is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+ * version 2 for more details (a copy is included in the LICENSE file that
+ * accompanied this code).
+ *
+ * You should have received a copy of the GNU General Public License version
+ * 2 along with this work; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
+ *
+ * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
+ * or visit www.oracle.com if you need additional information or have any
+ * questions.
+ */
+package com.oracle.graal.compiler.test.tutorial;
+
+import java.lang.reflect.*;
+import java.util.*;
+
+import org.junit.*;
+
+import com.oracle.graal.api.meta.*;
+import com.oracle.graal.api.runtime.*;
+import com.oracle.graal.compiler.target.*;
+import com.oracle.graal.compiler.test.tutorial.StaticAnalysis.MethodState;
+import com.oracle.graal.compiler.test.tutorial.StaticAnalysis.TypeFlow;
+import com.oracle.graal.phases.util.*;
+import com.oracle.graal.runtime.*;
+
+public class StaticAnalysisTests {
+
+    static class A {
+        Object foo(Object arg) {
+            return arg;
+        }
+    }
+
+    static class B extends A {
+        @Override
+        Object foo(Object arg) {
+            if (arg instanceof Data) {
+                return ((Data) arg).f;
+            } else {
+                return super.foo(arg);
+            }
+        }
+    }
+
+    static class Data {
+        Object f;
+    }
+
+    private MetaAccessProvider metaAccess;
+
+    public StaticAnalysisTests() {
+        Backend backend = Graal.getRequiredCapability(RuntimeProvider.class).getHostBackend();
+        Providers providers = backend.getProviders();
+        this.metaAccess = providers.getMetaAccess();
+    }
+
+    static void test01Entry() {
+        A a = new A();
+        a.foo(null);
+    }
+
+    @Test
+    public void test01() {
+        StaticAnalysis sa = new StaticAnalysis(metaAccess);
+        sa.addMethod(findMethod(StaticAnalysisTests.class, "test01Entry"));
+        sa.finish();
+
+        assertEquals(sa.getResults().getAllInstantiatedTypes(), t(A.class));
+        assertEquals(f(sa, Data.class, "f"));
+        assertEquals(m(sa, A.class, "foo").getFormalParameters()[0], t(A.class));
+        assertEquals(m(sa, A.class, "foo").getFormalParameters()[1]);
+        assertEquals(m(sa, A.class, "foo").getFormalReturn());
+    }
+
+    static void test02Entry() {
+        A a = new A();
+        a.foo(new Data());
+
+        B b = new B();
+        b.foo(null);
+    }
+
+    @Test
+    public void test02() {
+        StaticAnalysis sa = new StaticAnalysis(metaAccess);
+        sa.addMethod(findMethod(StaticAnalysisTests.class, "test02Entry"));
+        sa.finish();
+
+        assertEquals(sa.getResults().getAllInstantiatedTypes(), t(A.class), t(B.class), t(Data.class));
+        assertEquals(f(sa, Data.class, "f"));
+        assertEquals(m(sa, A.class, "foo").getFormalParameters()[0], t(A.class), t(B.class));
+        assertEquals(m(sa, A.class, "foo").getFormalParameters()[1], t(Data.class));
+        assertEquals(m(sa, A.class, "foo").getFormalReturn(), t(Data.class));
+        assertEquals(m(sa, B.class, "foo").getFormalParameters()[0], t(B.class));
+        assertEquals(m(sa, B.class, "foo").getFormalParameters()[1]);
+        assertEquals(m(sa, B.class, "foo").getFormalReturn(), t(Data.class));
+    }
+
+    static void test03Entry() {
+        Data data = new Data();
+        data.f = new Integer(42);
+
+        A a = new A();
+        a.foo(new Data());
+
+        B b = new B();
+        b.foo(null);
+    }
+
+    @Test
+    public void test03() {
+        StaticAnalysis sa = new StaticAnalysis(metaAccess);
+        sa.addMethod(findMethod(StaticAnalysisTests.class, "test03Entry"));
+        sa.finish();
+
+        assertEquals(sa.getResults().getAllInstantiatedTypes(), t(A.class), t(B.class), t(Data.class), t(Integer.class));
+        assertEquals(f(sa, Data.class, "f"), t(Integer.class));
+        assertEquals(m(sa, A.class, "foo").getFormalParameters()[0], t(A.class), t(B.class));
+        assertEquals(m(sa, A.class, "foo").getFormalParameters()[1], t(Data.class));
+        assertEquals(m(sa, A.class, "foo").getFormalReturn(), t(Data.class));
+        assertEquals(m(sa, B.class, "foo").getFormalParameters()[0], t(B.class));
+        assertEquals(m(sa, B.class, "foo").getFormalParameters()[1]);
+        assertEquals(m(sa, B.class, "foo").getFormalReturn(), t(Data.class), t(Integer.class));
+    }
+
+    static void test04Entry() {
+        Data data = null;
+        for (int i = 0; i < 2; i++) {
+            if (i == 0) {
+                data = new Data();
+            } else if (i == 1) {
+                data.f = new Integer(42);
+            }
+        }
+
+        A a = new A();
+        a.foo(data);
+    }
+
+    @Test
+    public void test04() {
+        StaticAnalysis sa = new StaticAnalysis(metaAccess);
+        sa.addMethod(findMethod(StaticAnalysisTests.class, "test04Entry"));
+        sa.finish();
+
+        assertEquals(sa.getResults().getAllInstantiatedTypes(), t(A.class), t(Data.class), t(Integer.class));
+        assertEquals(f(sa, Data.class, "f"), t(Integer.class));
+        assertEquals(m(sa, A.class, "foo").getFormalParameters()[0], t(A.class));
+        assertEquals(m(sa, A.class, "foo").getFormalParameters()[1], t(Data.class));
+        assertEquals(m(sa, A.class, "foo").getFormalReturn(), t(Data.class));
+    }
+
+    private MethodState m(StaticAnalysis sa, Class<?> declaringClass, String name) {
+        return sa.getResults().lookupMethod(findMethod(declaringClass, name));
+    }
+
+    private TypeFlow f(StaticAnalysis sa, Class<?> declaringClass, String name) {
+        return sa.getResults().lookupField(findField(declaringClass, name));
+    }
+
+    private static void assertEquals(TypeFlow actual, Object... expected) {
+        Collection<?> actualTypes = actual.getTypes();
+        if (actualTypes.size() != expected.length || !actualTypes.containsAll(Arrays.asList(expected))) {
+            Assert.fail(actualTypes + " != " + Arrays.asList(expected));
+        }
+    }
+
+    private ResolvedJavaType t(Class<?> clazz) {
+        return metaAccess.lookupJavaType(clazz);
+    }
+
+    private ResolvedJavaMethod findMethod(Class<?> declaringClass, String name) {
+        Method reflectionMethod = null;
+        for (Method m : declaringClass.getDeclaredMethods()) {
+            if (m.getName().equals(name)) {
+                assert reflectionMethod == null : "More than one method with name " + name + " in class " + declaringClass.getName();
+                reflectionMethod = m;
+            }
+        }
+        assert reflectionMethod != null : "No method with name " + name + " in class " + declaringClass.getName();
+        return metaAccess.lookupJavaMethod(reflectionMethod);
+    }
+
+    private ResolvedJavaField findField(Class<?> declaringClass, String name) {
+        Field reflectionField;
+        try {
+            reflectionField = declaringClass.getDeclaredField(name);
+        } catch (NoSuchFieldException | SecurityException ex) {
+            throw new AssertionError(ex);
+        }
+        return metaAccess.lookupJavaField(reflectionField);
+    }
+}