# HG changeset patch
# User Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
# Date 1367089772 -7200
# Node ID 8649dbda7d2549e5e7533fd9e350297203bd9966
# Parent  f11381a657256bf6cde094a210233d1180200b51
New experiment with megamorphic inlining.

diff -r f11381a65725 -r 8649dbda7d25 graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/InliningUtil.java
--- a/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/InliningUtil.java	Sat Apr 27 20:17:10 2013 +0200
+++ b/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/InliningUtil.java	Sat Apr 27 21:09:32 2013 +0200
@@ -546,6 +546,7 @@
             if (shouldFallbackToInvoke()) {
                 replacementNodes.add(null);
             }
+
             if (GraalOptions.OptTailDuplication) {
                 /*
                  * We might want to perform tail duplication at the merge after a type switch, if
@@ -619,7 +620,7 @@
         }
 
         private void createDispatchOnTypeBeforeInvoke(StructuredGraph graph, BeginNode[] successors, boolean invokeIsOnlySuccessor) {
-            assert ptypes.size() > 1;
+            assert ptypes.size() >= 1;
 
             Kind hubKind = ((MethodCallTargetNode) invoke.callTarget()).targetMethod().getDeclaringClass().getEncoding(Representation.ObjectHub).getKind();
             LoadHubNode hub = graph.add(new LoadHubNode(((MethodCallTargetNode) invoke.callTarget()).receiver(), hubKind));
@@ -906,26 +907,93 @@
                                 notRecordedTypeProbability * 100);
             }
 
+            ArrayList<ProfiledType> usedTypes = ptypes;
+            if (notRecordedTypeProbability > 0) {
+                // Clean out uncommon types.
+                ArrayList<ProfiledType> newTypes = new ArrayList<>();
+                for (ProfiledType type : ptypes) {
+                    if (type.getProbability() < GraalOptions.MegamorphicInliningMinTypeProbability) {
+                        notRecordedTypeProbability += type.getProbability();
+                    } else {
+                        newTypes.add(type);
+                    }
+                }
+
+                if (newTypes.size() == 0) {
+                    // No type left that is worth checking for.
+                    return logNotInlinedMethodAndReturnNull(invoke, targetMethod, "no types remaining after filtering less frequent types (%d types previously)", ptypes.size());
+                }
+
+                usedTypes = newTypes;
+            }
+
             // determine concrete methods and map type to specific method
             ArrayList<ResolvedJavaMethod> concreteMethods = new ArrayList<>();
-            int[] typesToConcretes = new int[ptypes.size()];
-            for (int i = 0; i < ptypes.size(); i++) {
-                ResolvedJavaMethod concrete = ptypes.get(i).getType().resolveMethod(targetMethod);
+            ArrayList<Double> concreteMethodsProbabilities = new ArrayList<>();
+            int[] typesToConcretes = new int[usedTypes.size()];
+            for (int i = 0; i < usedTypes.size(); i++) {
+                ResolvedJavaMethod concrete = usedTypes.get(i).getType().resolveMethod(targetMethod);
 
                 int index = concreteMethods.indexOf(concrete);
                 if (index < 0) {
                     index = concreteMethods.size();
                     concreteMethods.add(concrete);
+                    concreteMethodsProbabilities.add(usedTypes.get(i).getProbability());
+                } else {
+                    concreteMethodsProbabilities.set(index, concreteMethodsProbabilities.get(index) + usedTypes.get(i).getProbability());
                 }
                 typesToConcretes[i] = index;
             }
 
+            if (notRecordedTypeProbability > 0) {
+                // Clean out uncommon methods.
+                ArrayList<ResolvedJavaMethod> newConcreteMethods = new ArrayList<>();
+                for (int i = 0; i < concreteMethods.size(); ++i) {
+                    if (concreteMethodsProbabilities.get(i) >= GraalOptions.MegamorphicInliningMinMethodProbability) {
+                        newConcreteMethods.add(concreteMethods.get(i));
+                    } else {
+                        concreteMethods.set(i, null);
+                    }
+                }
+
+                if (concreteMethods.size() != newConcreteMethods.size()) {
+
+                    if (newConcreteMethods.size() == 0) {
+                        // No method left that is worth inlining.
+                        return logNotInlinedMethodAndReturnNull(invoke, targetMethod, "no methods remaining after filtering less frequent methods (%d methods previously)", concreteMethods.size());
+                    }
+
+                    // Clean all types that referred to cleaned methods.
+                    ArrayList<ProfiledType> newTypes = new ArrayList<>();
+                    ArrayList<Integer> newTypesToConcretes = new ArrayList<>();
+                    for (int i = 0; i < typesToConcretes.length; ++i) {
+                        ResolvedJavaMethod resolvedJavaMethod = concreteMethods.get(typesToConcretes[i]);
+                        if (resolvedJavaMethod != null) {
+                            newTypes.add(usedTypes.get(i));
+                            newTypesToConcretes.add(newConcreteMethods.indexOf(resolvedJavaMethod));
+                        } else {
+                            notRecordedTypeProbability += usedTypes.get(i).getProbability();
+                        }
+                    }
+
+                    int[] newTypesToConcretesArray = new int[newTypesToConcretes.size()];
+                    for (int i = 0; i < newTypesToConcretesArray.length; ++i) {
+                        newTypesToConcretesArray[i] = newTypesToConcretes.get(i);
+                        concreteMethods.get(typesToConcretes[i]);
+                    }
+
+                    usedTypes = newTypes;
+                    typesToConcretes = newTypesToConcretesArray;
+                    concreteMethods = newConcreteMethods;
+                }
+            }
+
             for (ResolvedJavaMethod concrete : concreteMethods) {
                 if (!checkTargetConditions(replacements, invoke, concrete, optimisticOpts)) {
                     return logNotInlinedMethodAndReturnNull(invoke, targetMethod, "it is a polymorphic method call and at least one invoked method cannot be inlined");
                 }
             }
-            return new MultiTypeGuardInlineInfo(invoke, concreteMethods, ptypes, typesToConcretes, notRecordedTypeProbability);
+            return new MultiTypeGuardInlineInfo(invoke, concreteMethods, usedTypes, typesToConcretes, notRecordedTypeProbability);
         }
     }
 
diff -r f11381a65725 -r 8649dbda7d25 graal/com.oracle.graal.phases/src/com/oracle/graal/phases/GraalOptions.java
--- a/graal/com.oracle.graal.phases/src/com/oracle/graal/phases/GraalOptions.java	Sat Apr 27 20:17:10 2013 +0200
+++ b/graal/com.oracle.graal.phases/src/com/oracle/graal/phases/GraalOptions.java	Sat Apr 27 21:09:32 2013 +0200
@@ -44,7 +44,9 @@
     public static boolean Intrinsify                         = true;
            static boolean InlineMonomorphicCalls             = true;
            static boolean InlinePolymorphicCalls             = true;
-           static boolean InlineMegamorphicCalls             = ____;
+           static boolean InlineMegamorphicCalls             = true;
+    public static double  MegamorphicInliningMinTypeProbability = 0.1;
+    public static double  MegamorphicInliningMinMethodProbability = 0.25;
     public static int     MaximumDesiredSize                 = 5000;
     public static int     MaximumRecursiveInlining           = 1;
     public static float   BoostInliningForEscapeAnalysis     = 2f;