# HG changeset patch
# User Doug Simon <doug.simon@oracle.com>
# Date 1335962385 -7200
# Node ID 439ca5ecc7dcf8ba6a68f7fcad6eeb7e01cf62a0
# Parent  ecc2b68344debb853a86163222ef3531f177c5dd
types profiles are now sorted in descending order of each profiled type's probability

diff -r ecc2b68344de -r 439ca5ecc7dc graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/util/InliningUtil.java
--- a/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/util/InliningUtil.java	Wed May 02 12:59:59 2012 +0200
+++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/util/InliningUtil.java	Wed May 02 14:39:45 2012 +0200
@@ -29,6 +29,7 @@
 import com.oracle.max.cri.ci.*;
 import com.oracle.max.cri.ri.*;
 import com.oracle.max.cri.ri.RiType.Representation;
+import com.oracle.max.cri.ri.RiTypeProfile.ProfiledType;
 import com.oracle.graal.compiler.*;
 import com.oracle.graal.compiler.phases.*;
 import com.oracle.graal.cri.*;
@@ -223,21 +224,19 @@
      */
     private static class MultiTypeGuardInlineInfo extends InlineInfo {
         public final List<RiResolvedMethod> concretes;
-        public final RiResolvedType[] types;
+        public final ProfiledType[] ptypes;
         public final int[] typesToConcretes;
-        public final double[] typeProbabilities;
         public final double notRecordedTypeProbability;
 
-        public MultiTypeGuardInlineInfo(Invoke invoke, double weight, int level, List<RiResolvedMethod> concretes, RiResolvedType[] types,
-                        int[] typesToConcretes, double[] typeProbabilities, double notRecordedTypeProbability) {
+        public MultiTypeGuardInlineInfo(Invoke invoke, double weight, int level, List<RiResolvedMethod> concretes, ProfiledType[] ptypes,
+                        int[] typesToConcretes, double notRecordedTypeProbability) {
             super(invoke, weight, level);
-            assert concretes.size() > 0 && concretes.size() <= types.length : "must have at least one method but no more than types methods";
-            assert types.length == typesToConcretes.length && types.length == typeProbabilities.length : "array length must match";
+            assert concretes.size() > 0 && concretes.size() <= ptypes.length : "must have at least one method but no more than types methods";
+            assert ptypes.length == typesToConcretes.length : "array lengths must match";
 
             this.concretes = concretes;
-            this.types = types;
+            this.ptypes = ptypes;
             this.typesToConcretes = typesToConcretes;
-            this.typeProbabilities = typeProbabilities;
             this.notRecordedTypeProbability = notRecordedTypeProbability;
         }
 
@@ -305,7 +304,7 @@
                 for (int j = 0; j < typesToConcretes.length; j++) {
                     if (typesToConcretes[j] == i) {
                         predecessors++;
-                        probability += typeProbabilities[j];
+                        probability += ptypes[j].probability;
                     }
                 }
 
@@ -364,9 +363,9 @@
             for (int i = 0; i < typesToConcretes.length; i++) {
                 if (typesToConcretes[i] == concreteMethodIndex) {
                     if (commonType == null) {
-                        commonType = types[i];
+                        commonType = ptypes[i].type;
                     } else {
-                        commonType = commonType.leastCommonAncestor(types[i]);
+                        commonType = commonType.leastCommonAncestor(ptypes[i].type);
                     }
                 }
             }
@@ -375,7 +374,7 @@
         }
 
         private void inlineSingleMethod(StructuredGraph graph, GraalRuntime runtime, InliningCallback callback) {
-            assert concretes.size() == 1 && types.length > 1 && !shouldFallbackToInvoke() && notRecordedTypeProbability == 0;
+            assert concretes.size() == 1 && ptypes.length > 1 && !shouldFallbackToInvoke() && notRecordedTypeProbability == 0;
 
             MergeNode calleeEntryNode = graph.add(new MergeNode());
             calleeEntryNode.setProbability(invoke.probability());
@@ -397,15 +396,15 @@
         }
 
         private FixedNode createDispatchOnType(StructuredGraph graph, ReadHubNode objectClassNode, BeginNode[] calleeEntryNodes, FixedNode unknownTypeSux) {
-            assert types.length > 1;
+            assert ptypes.length > 1;
 
-            int lastIndex = types.length - 1;
-            double[] branchProbabilities = convertTypeToBranchProbabilities(typeProbabilities, notRecordedTypeProbability);
-            double nodeProbability = typeProbabilities[lastIndex];
-            IfNode nextNode = createTypeCheck(graph, objectClassNode, types[lastIndex], calleeEntryNodes[typesToConcretes[lastIndex]], unknownTypeSux, branchProbabilities[lastIndex], invoke.probability() * nodeProbability);
+            int lastIndex = ptypes.length - 1;
+            double[] branchProbabilities = convertTypeToBranchProbabilities(ptypes, notRecordedTypeProbability);
+            double nodeProbability = ptypes[lastIndex].probability;
+            IfNode nextNode = createTypeCheck(graph, objectClassNode, ptypes[lastIndex].type, calleeEntryNodes[typesToConcretes[lastIndex]], unknownTypeSux, branchProbabilities[lastIndex], invoke.probability() * nodeProbability);
             for (int i = lastIndex - 1; i >= 0; i--) {
-                nodeProbability += typeProbabilities[i];
-                nextNode = createTypeCheck(graph, objectClassNode, types[i], calleeEntryNodes[typesToConcretes[i]], nextNode, branchProbabilities[i], invoke.probability() * nodeProbability);
+                nodeProbability += ptypes[i].probability;
+                nextNode = createTypeCheck(graph, objectClassNode, ptypes[i].type, calleeEntryNodes[typesToConcretes[i]], nextNode, branchProbabilities[i], invoke.probability() * nodeProbability);
             }
 
             return nextNode;
@@ -425,12 +424,12 @@
             return result;
         }
 
-        private static double[] convertTypeToBranchProbabilities(double[] typeProbabilities, double notRecordedTypeProbability) {
-            double[] result = new double[typeProbabilities.length];
+        private static double[] convertTypeToBranchProbabilities(ProfiledType[] ptypes, double notRecordedTypeProbability) {
+            double[] result = new double[ptypes.length];
             double total = notRecordedTypeProbability;
-            for (int i = typeProbabilities.length - 1; i >= 0; i--) {
-                total += typeProbabilities[i];
-                result[i] = typeProbabilities[i] / total;
+            for (int i = ptypes.length - 1; i >= 0; i--) {
+                total += ptypes[i].probability;
+                result[i] = ptypes[i].probability / total;
             }
             assert total > 0.99 && total < 1.01;
             return result;
@@ -497,7 +496,7 @@
         @Override
         public String toString() {
             StringBuilder builder = new StringBuilder(shouldFallbackToInvoke() ? "megamorphic" : "polymorphic");
-            builder.append(String.format(", %d methods with %d type checks:", concretes.size(), types.length));
+            builder.append(String.format(", %d methods with %d type checks:", concretes.size(), ptypes.length));
             for (int i = 0; i < concretes.size(); i++) {
                 builder.append(CiUtil.format("  %H.%n(%p):%r", concretes.get(i)));
             }
@@ -612,15 +611,13 @@
         RiProfilingInfo profilingInfo = parent.profilingInfo();
         RiTypeProfile typeProfile = profilingInfo.getTypeProfile(invoke.bci());
         if (typeProfile != null) {
-            RiResolvedType[] types = typeProfile.getTypes();
-            double[] probabilities = typeProfile.getProbabilities();
+            ProfiledType[] ptypes = typeProfile.getTypes();
 
-            if (types != null && probabilities != null && types.length > 0) {
-                assert types.length == probabilities.length : "length must match";
+            if (ptypes != null && ptypes.length > 0) {
                 double notRecordedTypeProbability = typeProfile.getNotRecordedProbability();
-                if (types.length == 1 && notRecordedTypeProbability == 0) {
+                if (ptypes.length == 1 && notRecordedTypeProbability == 0) {
                     if (optimisticOpts.inlineMonomorphicCalls()) {
-                        RiResolvedType type = types[0];
+                        RiResolvedType type = ptypes[0].type;
                         RiResolvedMethod concrete = type.resolveMethodImpl(targetMethod);
                         if (checkTargetConditions(invoke, concrete, optimisticOpts)) {
                             double weight = callback == null ? 0 : callback.inliningWeight(parent, concrete, invoke);
@@ -646,9 +643,9 @@
 
                         // determine concrete methods and map type to specific method
                         ArrayList<RiResolvedMethod> concreteMethods = new ArrayList<>();
-                        int[] typesToConcretes = new int[types.length];
-                        for (int i = 0; i < types.length; i++) {
-                            RiResolvedMethod concrete = types[i].resolveMethodImpl(targetMethod);
+                        int[] typesToConcretes = new int[ptypes.length];
+                        for (int i = 0; i < ptypes.length; i++) {
+                            RiResolvedMethod concrete = ptypes[i].type.resolveMethodImpl(targetMethod);
 
                             int index = concreteMethods.indexOf(concrete);
                             if (index < 0) {
@@ -669,7 +666,7 @@
                         }
 
                         if (canInline) {
-                            return new MultiTypeGuardInlineInfo(invoke, totalWeight, level, concreteMethods, types, typesToConcretes, probabilities, notRecordedTypeProbability);
+                            return new MultiTypeGuardInlineInfo(invoke, totalWeight, level, concreteMethods, ptypes, typesToConcretes, notRecordedTypeProbability);
                         } else {
                             Debug.log("not inlining %s because it is a polymorphic method call and at least one invoked method cannot be inlined", methodName(targetMethod, invoke));
                             return null;
diff -r ecc2b68344de -r 439ca5ecc7dc graal/com.oracle.graal.hotspot/src/com/oracle/graal/hotspot/ri/HotSpotMethodData.java
--- a/graal/com.oracle.graal.hotspot/src/com/oracle/graal/hotspot/ri/HotSpotMethodData.java	Wed May 02 12:59:59 2012 +0200
+++ b/graal/com.oracle.graal.hotspot/src/com/oracle/graal/hotspot/ri/HotSpotMethodData.java	Wed May 02 14:39:45 2012 +0200
@@ -30,6 +30,7 @@
 import com.oracle.graal.hotspot.*;
 import com.oracle.graal.hotspot.Compiler;
 import com.oracle.max.cri.ri.*;
+import com.oracle.max.cri.ri.RiTypeProfile.*;
 
 
 public final class HotSpotMethodData extends CompilerObject {
@@ -332,8 +333,8 @@
         public RiTypeProfile getTypeProfile(HotSpotMethodData data, int position) {
             int typeProfileWidth = config.typeProfileWidth;
 
-            RiResolvedType[] sparseTypes = new RiResolvedType[typeProfileWidth];
-            double[] counts = new double[typeProfileWidth];
+            RiResolvedType[] types = new RiResolvedType[typeProfileWidth];
+            long[] counts = new long[typeProfileWidth];
             long totalCount = 0;
             int entries = 0;
 
@@ -346,7 +347,9 @@
                         graalMirror = CompilerImpl.getInstance().getCompilerToVM().getType(javaClass);
                         assert graalMirror != null : "must not return null";
                     }
-                    sparseTypes[entries] = (RiResolvedType) graalMirror;
+
+
+                    types[entries] = (RiResolvedType) graalMirror;
 
                     long count = data.readUnsignedInt(position, getCountOffset(i));
                     totalCount += count;
@@ -357,7 +360,7 @@
             }
 
             totalCount += getTypesNotRecordedExecutionCount(data, position);
-            return createRiTypeProfile(sparseTypes, counts, totalCount, entries);
+            return createRiTypeProfile(types, counts, totalCount, entries);
         }
 
         protected long getTypesNotRecordedExecutionCount(HotSpotMethodData data, int position) {
@@ -366,29 +369,24 @@
             return getCounterValue(data, position);
         }
 
-        private static RiTypeProfile createRiTypeProfile(RiResolvedType[] sparseTypes, double[] counts, long totalCount, int entries) {
-            RiResolvedType[] types;
-            double[] probabilities;
-
+        private static RiTypeProfile createRiTypeProfile(RiResolvedType[] types, long[] counts, long totalCount, int entries) {
             if (entries <= 0 || totalCount < GraalOptions.MatureExecutionsTypeProfile) {
                 return null;
-            } else if (entries < sparseTypes.length) {
-                types = Arrays.copyOf(sparseTypes, entries);
-                probabilities = new double[entries];
-            } else {
-                types = sparseTypes;
-                probabilities = counts;
             }
 
+            ProfiledType[] ptypes = new ProfiledType[entries];
             double totalProbability = 0.0;
             for (int i = 0; i < entries; i++) {
-                double p = counts[i] / totalCount;
-                probabilities[i] = p;
+                double p = counts[i];
+                p = p / totalCount;
                 totalProbability += p;
+                ptypes[i] = new ProfiledType(types[i], p);
             }
 
+            Arrays.sort(ptypes);
+
             double notRecordedTypeProbability = entries < config.typeProfileWidth ? 0.0 : Math.min(1.0, Math.max(0.0, 1.0 - totalProbability));
-            return new RiTypeProfile(types, notRecordedTypeProbability, probabilities);
+            return new RiTypeProfile(ptypes, notRecordedTypeProbability);
         }
 
         private static int getReceiverOffset(int row) {
diff -r ecc2b68344de -r 439ca5ecc7dc graal/com.oracle.graal.hotspot/src/com/oracle/graal/hotspot/ri/HotSpotMethodResolvedImpl.java
--- a/graal/com.oracle.graal.hotspot/src/com/oracle/graal/hotspot/ri/HotSpotMethodResolvedImpl.java	Wed May 02 12:59:59 2012 +0200
+++ b/graal/com.oracle.graal.hotspot/src/com/oracle/graal/hotspot/ri/HotSpotMethodResolvedImpl.java	Wed May 02 14:39:45 2012 +0200
@@ -29,6 +29,7 @@
 
 import com.oracle.max.cri.ci.*;
 import com.oracle.max.cri.ri.*;
+import com.oracle.max.cri.ri.RiTypeProfile.ProfiledType;
 import com.oracle.max.criutils.*;
 import com.oracle.graal.compiler.*;
 import com.oracle.graal.hotspot.*;
@@ -265,14 +266,14 @@
             }
 
             if (profilingInfo.getBranchTakenProbability(i) != -1) {
-                TTY.println("  branchProbability@%d: %f", i, profilingInfo.getBranchTakenProbability(i));
+                TTY.println("  branchProbability@%d: %.3f", i, profilingInfo.getBranchTakenProbability(i));
             }
 
             double[] switchProbabilities = profilingInfo.getSwitchProbabilities(i);
             if (switchProbabilities != null) {
                 TTY.print("  switchProbabilities@%d:", i);
                 for (int j = 0; j < switchProbabilities.length; j++) {
-                    TTY.print(" %f", switchProbabilities[j]);
+                    TTY.print(" %.3f", switchProbabilities[j]);
                 }
                 TTY.println();
             }
@@ -283,15 +284,14 @@
 
             RiTypeProfile typeProfile = profilingInfo.getTypeProfile(i);
             if (typeProfile != null) {
-                RiResolvedType[] types = typeProfile.getTypes();
-                double[] probabilities = typeProfile.getProbabilities();
-                if (types != null && probabilities != null) {
-                    assert types.length == probabilities.length : "length must match";
-                    TTY.print("  types@%d:", i);
-                    for (int j = 0; j < types.length; j++) {
-                        TTY.print(" %s (%f)", types[j], probabilities[j]);
+                ProfiledType[] ptypes = typeProfile.getTypes();
+                if (ptypes != null) {
+                    TTY.println("  types@%d:", i);
+                    for (int j = 0; j < ptypes.length; j++) {
+                        ProfiledType ptype = ptypes[j];
+                        TTY.println("    %.3f %s", ptype.probability, ptype.type);
                     }
-                    TTY.println(" not recorded (%f)", typeProfile.getNotRecordedProbability());
+                    TTY.println("    %.3f <not recorded>", typeProfile.getNotRecordedProbability());
                 }
             }
         }
diff -r ecc2b68344de -r 439ca5ecc7dc graal/com.oracle.graal.java/src/com/oracle/graal/java/GraphBuilderPhase.java
--- a/graal/com.oracle.graal.java/src/com/oracle/graal/java/GraphBuilderPhase.java	Wed May 02 12:59:59 2012 +0200
+++ b/graal/com.oracle.graal.java/src/com/oracle/graal/java/GraphBuilderPhase.java	Wed May 02 14:39:45 2012 +0200
@@ -46,6 +46,7 @@
 import com.oracle.max.cri.ci.*;
 import com.oracle.max.cri.ri.*;
 import com.oracle.max.cri.ri.RiType.Representation;
+import com.oracle.max.cri.ri.RiTypeProfile.ProfiledType;
 import com.oracle.max.criutils.*;
 
 /**
@@ -601,12 +602,14 @@
                 RiTypeProfile typeProfile = profilingInfo.getTypeProfile(bci());
                 if (typeProfile != null) {
                     double notRecordedTypes = typeProfile.getNotRecordedProbability();
-                    RiResolvedType[] types = typeProfile.getTypes();
+                    ProfiledType[] ptypes = typeProfile.getTypes();
 
-                    if (notRecordedTypes == 0 && types != null && types.length > 0 && types.length <= maxHints) {
-                        RiResolvedType[] hints = new RiResolvedType[types.length];
+                    if (notRecordedTypes == 0 && ptypes != null && ptypes.length > 0 && ptypes.length <= maxHints) {
+                    //if (notRecordedTypes < 0.1d && ptypes != null && ptypes.length > 0) {
+                        RiResolvedType[] hints = new RiResolvedType[ptypes.length];
                         int hintCount = 0;
-                        for (RiResolvedType hint : types) {
+                        for (ProfiledType ptype : ptypes) {
+                            RiResolvedType hint = ptype.type;
                             if (hint.isSubtypeOf(type)) {
                                 hints[hintCount++] = hint;
                             }
diff -r ecc2b68344de -r 439ca5ecc7dc graal/com.oracle.max.cri/src/com/oracle/max/cri/ri/RiTypeProfile.java
--- a/graal/com.oracle.max.cri/src/com/oracle/max/cri/ri/RiTypeProfile.java	Wed May 02 12:59:59 2012 +0200
+++ b/graal/com.oracle.max.cri/src/com/oracle/max/cri/ri/RiTypeProfile.java	Wed May 02 14:39:45 2012 +0200
@@ -33,22 +33,49 @@
 
     private static final long serialVersionUID = -6877016333706838441L;
 
-    private final RiResolvedType[] types;
-    private final double notRecordedProbability;
-    private final double[] probabilities;
+    /**
+     * A profiled type that has a probability. Profiled types are naturally sorted in
+     * descending order of their probabilities.
+     */
+    public static class ProfiledType implements Comparable<ProfiledType> {
+        public final RiResolvedType type;
+        public final double probability;
 
-    public RiTypeProfile(RiResolvedType[] types, double notRecordedProbability, double[] probabilites) {
-        this.types = types;
-        this.notRecordedProbability = notRecordedProbability;
-        this.probabilities = probabilites;
+        public ProfiledType(RiResolvedType type, double probability) {
+            this.type = type;
+            this.probability = probability;
+        }
+
+        @Override
+        public int compareTo(ProfiledType o) {
+            if (probability > o.probability) {
+                return -1;
+            } else if (probability < o.probability) {
+                return 1;
+            }
+            return 0;
+        }
     }
 
+    private final double notRecordedProbability;
+    private final ProfiledType[] ptypes;
+
     /**
-     * The estimated probabilities of the different receivers. This array needs to have the same length as the array returned by
-     * {@link RiTypeProfile#types}.
+     * Determines if an array of profiled types are sorted in descending order of their probabilities.
      */
-    public double[] getProbabilities() {
-        return probabilities;
+    public static boolean isSorted(ProfiledType[] ptypes) {
+        for (int i = 1; i < ptypes.length; i++) {
+            if (ptypes[i - 1].probability < ptypes[i].probability) {
+                return false;
+            }
+        }
+        return true;
+    }
+
+    public RiTypeProfile(ProfiledType[] ptypes, double notRecordedProbability) {
+        this.ptypes = ptypes;
+        this.notRecordedProbability = notRecordedProbability;
+        assert isSorted(ptypes);
     }
 
     /**
@@ -60,10 +87,9 @@
     }
 
     /**
-     * A list of receivers for which the runtime has recorded probability information. This array needs to have the same
-     * length as {@link RiTypeProfile#probabilities}.
+     * A list of types for which the runtime has recorded probability information.
      */
-    public RiResolvedType[] getTypes() {
-        return types;
+    public ProfiledType[] getTypes() {
+        return ptypes;
     }
 }