# HG changeset patch # User Thomas Wuerthinger # Date 1424201893 -3600 # Node ID 5b582897cc4b0c6144709c2873f3fb6dfd116f40 # Parent 3e5c4e59c5860839e2d4dd3aa3ea7e7a01d9020c# Parent ee96561afbd3fad064f50912e5bfe5215024d50c Merge. diff -r 3e5c4e59c586 -r 5b582897cc4b graal/com.oracle.graal.api.directives.test/src/com/oracle/graal/api/directives/test/ControlFlowAnchorDirectiveTest.java --- a/graal/com.oracle.graal.api.directives.test/src/com/oracle/graal/api/directives/test/ControlFlowAnchorDirectiveTest.java Tue Feb 17 20:37:45 2015 +0100 +++ b/graal/com.oracle.graal.api.directives.test/src/com/oracle/graal/api/directives/test/ControlFlowAnchorDirectiveTest.java Tue Feb 17 20:38:13 2015 +0100 @@ -106,7 +106,7 @@ @Test public void testDuplicate() { - test("verifyDuplicateSnippet", 42); + // test("verifyDuplicateSnippet", 42); test("preventDuplicateSnippet", 42); } diff -r 3e5c4e59c586 -r 5b582897cc4b graal/com.oracle.graal.api.meta/src/com/oracle/graal/api/meta/AbstractJavaProfile.java --- a/graal/com.oracle.graal.api.meta/src/com/oracle/graal/api/meta/AbstractJavaProfile.java Tue Feb 17 20:37:45 2015 +0100 +++ b/graal/com.oracle.graal.api.meta/src/com/oracle/graal/api/meta/AbstractJavaProfile.java Tue Feb 17 20:38:13 2015 +0100 @@ -46,6 +46,15 @@ assert !Double.isNaN(notRecordedProbability); this.notRecordedProbability = notRecordedProbability; assert isSorted(); + assert totalProbablility() >= 0 && totalProbablility() <= 1.0001 : totalProbablility() + " " + this; + } + + private double totalProbablility() { + double total = notRecordedProbability; + for (T item : pitems) { + total += item.probability; + } + return total; } /** diff -r 3e5c4e59c586 -r 5b582897cc4b graal/com.oracle.graal.api.meta/src/com/oracle/graal/api/meta/ProfilingInfo.java --- a/graal/com.oracle.graal.api.meta/src/com/oracle/graal/api/meta/ProfilingInfo.java Tue Feb 17 20:37:45 2015 +0100 +++ b/graal/com.oracle.graal.api.meta/src/com/oracle/graal/api/meta/ProfilingInfo.java Tue Feb 17 20:38:13 2015 +0100 @@ -41,6 +41,21 @@ public static TriState get(boolean value) { return value ? TRUE : FALSE; } + + /** + * This is optimistic about {@link #UNKNOWN} (it prefers known values over {@link #UNKNOWN}) + * and pesimistic about known (it perfers {@link #TRUE} over {@link #FALSE}). + */ + public static TriState merge(TriState a, TriState b) { + if (a == TRUE || b == TRUE) { + return TRUE; + } + if (a == FALSE || b == FALSE) { + return FALSE; + } + assert a == UNKNOWN && b == UNKNOWN; + return UNKNOWN; + } } /** diff -r 3e5c4e59c586 -r 5b582897cc4b graal/com.oracle.graal.compiler.common/src/com/oracle/graal/compiler/common/GraalOptions.java --- a/graal/com.oracle.graal.compiler.common/src/com/oracle/graal/compiler/common/GraalOptions.java Tue Feb 17 20:37:45 2015 +0100 +++ b/graal/com.oracle.graal.compiler.common/src/com/oracle/graal/compiler/common/GraalOptions.java Tue Feb 17 20:38:13 2015 +0100 @@ -307,7 +307,7 @@ public static final OptionValue OptFloatingReads = new OptionValue<>(true); @Option(help = "", type = OptionType.Debug) - public static final OptionValue OptTailDuplication = new OptionValue<>(true); + public static final OptionValue OptTailDuplication = new OptionValue<>(false); @Option(help = "", type = OptionType.Debug) public static final OptionValue OptEliminatePartiallyRedundantGuards = new OptionValue<>(true); diff -r 3e5c4e59c586 -r 5b582897cc4b graal/com.oracle.graal.hotspot/src/com/oracle/graal/hotspot/replacements/InstanceOfSnippets.java --- a/graal/com.oracle.graal.hotspot/src/com/oracle/graal/hotspot/replacements/InstanceOfSnippets.java Tue Feb 17 20:37:45 2015 +0100 +++ b/graal/com.oracle.graal.hotspot/src/com/oracle/graal/hotspot/replacements/InstanceOfSnippets.java Tue Feb 17 20:38:13 2015 +0100 @@ -61,17 +61,26 @@ */ public class InstanceOfSnippets implements Snippets { + private static final double COMPILED_VS_INTERPRETER_SPEEDUP = 50; + private static final double INSTANCEOF_DEOPT_SPEEDUP = 1.01; // generous 1% speedup + + private static final int DEOPT_THRESHOLD_FACTOR = (int) (COMPILED_VS_INTERPRETER_SPEEDUP / (INSTANCEOF_DEOPT_SPEEDUP - 1.0)); + /** * Gets the minimum required probability of a profiled instanceof hitting one the profiled types * for use of the {@linkplain #instanceofWithProfile deoptimizing} snippet. The value is - * computed to be an order of magnitude greater than the configured compilation threshold. For - * example, if a method is compiled after being interpreted 10000 times, the deoptimizing - * snippet will only be used for an instanceof if its profile indicates that less than 1 in - * 100000 executions are for an object whose type is not one of the top N profiled types (where - * {@code N == } {@link Options#TypeCheckMaxHints}). + * computed to be an order of greater than the configured compilation threshold by a + * {@linkplain #DEOPT_THRESHOLD_FACTOR factor}. + * + *

+ * This factor is such that the additional executions we get from using the deoptimizing snippet + * (({@linkplain #INSTANCEOF_DEOPT_SPEEDUP speedup} - 1) / probability threshold) is greater + * than the time lost during re-interpretation ({@linkplain #COMPILED_VS_INTERPRETER_SPEEDUP + * compiled code speedup} × compilation threshold). + *

*/ public static double hintHitProbabilityThresholdForDeoptimizingSnippet(long compilationThreshold) { - return 1.0D - (1.0D / (compilationThreshold * 10)); + return 1.0D - (1.0D / (compilationThreshold * DEOPT_THRESHOLD_FACTOR)); } /** diff -r 3e5c4e59c586 -r 5b582897cc4b graal/com.oracle.graal.loop/src/com/oracle/graal/loop/phases/LoopUnswitchingPhase.java --- a/graal/com.oracle.graal.loop/src/com/oracle/graal/loop/phases/LoopUnswitchingPhase.java Tue Feb 17 20:37:45 2015 +0100 +++ b/graal/com.oracle.graal.loop/src/com/oracle/graal/loop/phases/LoopUnswitchingPhase.java Tue Feb 17 20:38:13 2015 +0100 @@ -43,7 +43,7 @@ do { unswitched = false; final LoopsData dataUnswitch = new LoopsData(graph); - for (LoopEx loop : dataUnswitch.loops()) { + for (LoopEx loop : dataUnswitch.outerFirst()) { if (LoopPolicies.shouldTryUnswitch(loop)) { List controlSplits = LoopTransformations.findUnswitchable(loop); if (controlSplits != null) { diff -r 3e5c4e59c586 -r 5b582897cc4b graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/IfNode.java --- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/IfNode.java Tue Feb 17 20:37:45 2015 +0100 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/IfNode.java Tue Feb 17 20:38:13 2015 +0100 @@ -366,6 +366,16 @@ return false; } + private static final class MutableProfiledType { + final ResolvedJavaType type; + double probability; + + public MutableProfiledType(ResolvedJavaType type, double probability) { + this.type = type; + this.probability = probability; + } + } + private static boolean prepareForSwap(ConstantReflectionProvider constantReflection, LogicNode a, LogicNode b, double probabilityA, double probabilityB) { if (a instanceof InstanceOfNode) { InstanceOfNode instanceOfA = (InstanceOfNode) a; @@ -383,44 +393,8 @@ if (instanceOfA.getValue() == instanceOfB.getValue() && !instanceOfA.type().isInterface() && !instanceOfB.type().isInterface() && !instanceOfA.type().isAssignableFrom(instanceOfB.type()) && !instanceOfB.type().isAssignableFrom(instanceOfA.type())) { // Two instanceof on the same value with mutually exclusive types. - JavaTypeProfile profileA = instanceOfA.profile(); - JavaTypeProfile profileB = instanceOfB.profile(); - Debug.log("Can swap instanceof for types %s and %s", instanceOfA.type(), instanceOfB.type()); - JavaTypeProfile newProfile = null; - if (profileA != null && profileB != null) { - double remainder = 1.0; - ArrayList profiledTypes = new ArrayList<>(); - for (ProfiledType type : profileB.getTypes()) { - if (instanceOfB.type().isAssignableFrom(type.getType())) { - // Do not add to profile. - } else { - ProfiledType newType = new ProfiledType(type.getType(), Math.min(1.0, type.getProbability() * (1.0 - probabilityA) / (1.0 - probabilityB))); - profiledTypes.add(newType); - remainder -= newType.getProbability(); - } - } - - for (ProfiledType type : profileA.getTypes()) { - if (instanceOfA.type().isAssignableFrom(type.getType())) { - ProfiledType newType = new ProfiledType(type.getType(), Math.min(1.0, type.getProbability() / (1.0 - probabilityB))); - profiledTypes.add(newType); - remainder -= newType.getProbability(); - } - } - Collections.sort(profiledTypes); - - if (remainder < 0.0) { - // Can happen due to round-off errors. - remainder = 0.0; - } - newProfile = new JavaTypeProfile(profileB.getNullSeen(), remainder, profiledTypes.toArray(new ProfiledType[profiledTypes.size()])); - Debug.log("First profile: %s", profileA); - Debug.log("Original second profile: %s", profileB); - Debug.log("New second profile: %s", newProfile); - } - instanceOfB.setProfile(profileA); - instanceOfA.setProfile(newProfile); + swapInstanceOfProfiles(probabilityA, probabilityB, instanceOfA, instanceOfB); return true; } } @@ -477,6 +451,116 @@ return false; } + /** + * Arbitrary fraction of not recorded types that we'll guess are sub-types of B. + * + * This is is used because we can not check if the unrecorded types are sub-types of B or not. + */ + private static final double NOT_RECORDED_SUBTYPE_B = 0.5; + + /** + * If the not-recorded fraction of types for the new profile of instanceOfA is + * above this threshold, no profile is used for this instanceof after the swap. + * + * The idea is that the reconstructed profile would contain too much unknowns to be of any use. + */ + private static final double NOT_RECORDED_CUTOFF = 0.4; + + /** + * Tries to reconstruct profiles for the swapped instanceof checks. + * + * The tested types must be mutually exclusive. + */ + private static void swapInstanceOfProfiles(double probabilityA, double probabilityB, InstanceOfNode instanceOfA, InstanceOfNode instanceOfB) { + JavaTypeProfile profileA = instanceOfA.profile(); + JavaTypeProfile profileB = instanceOfB.profile(); + + JavaTypeProfile newProfileA = null; + JavaTypeProfile newProfileB = null; + if (profileA != null || profileB != null) { + List newProfiledTypesA = new ArrayList<>(); + List newProfiledTypesB = new ArrayList<>(); + double totalProbabilityA = 0.0; + double totalProbabilityB = 0.0; + double newNotRecordedA = 0.0; + double newNotRecordedB = 0.0; + TriState nullSeen = TriState.UNKNOWN; + if (profileA != null) { + for (ProfiledType profiledType : profileA.getTypes()) { + newProfiledTypesB.add(new MutableProfiledType(profiledType.getType(), profiledType.getProbability())); + totalProbabilityB += profiledType.getProbability(); + if (!instanceOfB.type().isAssignableFrom(profiledType.getType())) { + double typeProbabilityA = profiledType.getProbability() / (1 - probabilityB); + newProfiledTypesA.add(new MutableProfiledType(profiledType.getType(), typeProbabilityA)); + totalProbabilityA += typeProbabilityA; + } + } + newNotRecordedB += profileA.getNotRecordedProbability(); + newNotRecordedA += NOT_RECORDED_SUBTYPE_B * profileA.getNotRecordedProbability() / (1 - probabilityB); + nullSeen = profileA.getNullSeen(); + } + int searchA = newProfiledTypesA.size(); + int searchB = newProfiledTypesB.size(); + if (profileB != null) { + for (ProfiledType profiledType : profileB.getTypes()) { + double typeProbabilityB = profiledType.getProbability() * (1 - probabilityA); + appendOrMerge(profiledType.getType(), typeProbabilityB, searchB, newProfiledTypesB); + totalProbabilityB += typeProbabilityB; + if (!instanceOfB.type().isAssignableFrom(profiledType.getType())) { + double typeProbabilityA = typeProbabilityB / (1 - probabilityB); + appendOrMerge(profiledType.getType(), typeProbabilityA, searchA, newProfiledTypesA); + totalProbabilityA += typeProbabilityA; + } + } + newNotRecordedB += profileB.getNotRecordedProbability() * (1 - probabilityA); + newNotRecordedA += NOT_RECORDED_SUBTYPE_B * profileB.getNotRecordedProbability() * (1 - probabilityA) / (1 - probabilityB); + nullSeen = TriState.merge(nullSeen, profileB.getNullSeen()); + } + totalProbabilityA += newNotRecordedA; + totalProbabilityB += newNotRecordedB; + + if (newNotRecordedA / NOT_RECORDED_SUBTYPE_B > NOT_RECORDED_CUTOFF) { + // too much unknown + newProfileA = null; + } else { + newProfileA = makeProfile(totalProbabilityA, newNotRecordedA, newProfiledTypesA, nullSeen); + } + newProfileB = makeProfile(totalProbabilityB, newNotRecordedB, newProfiledTypesB, nullSeen); + } + + instanceOfB.setProfile(newProfileB); + instanceOfA.setProfile(newProfileA); + } + + private static JavaTypeProfile makeProfile(double totalProbability, double notRecorded, List profiledTypes, TriState nullSeen) { + // protect against NaNs and empty profiles + if (totalProbability > 0.0) { + // normalize + ProfiledType[] profiledTypesArray = new ProfiledType[profiledTypes.size()]; + int i = 0; + for (MutableProfiledType profiledType : profiledTypes) { + profiledTypesArray[i++] = new ProfiledType(profiledType.type, profiledType.probability / totalProbability); + } + + // sort + Arrays.sort(profiledTypesArray); + + return new JavaTypeProfile(nullSeen, notRecorded / totalProbability, profiledTypesArray); + } + return null; + } + + private static void appendOrMerge(ResolvedJavaType type, double probability, int searchUntil, List list) { + for (int i = 0; i < searchUntil; i++) { + MutableProfiledType profiledType = list.get(i); + if (profiledType.type.equals(type)) { + profiledType.probability += probability; + return; + } + } + list.add(new MutableProfiledType(type, probability)); + } + private static boolean valuesDistinct(ConstantReflectionProvider constantReflection, ValueNode a, ValueNode b) { if (a.isConstant() && b.isConstant()) { Boolean equal = constantReflection.constantEquals(a.asConstant(), b.asConstant()); diff -r 3e5c4e59c586 -r 5b582897cc4b hotspot/.cproject --- a/hotspot/.cproject Tue Feb 17 20:37:45 2015 +0100 +++ b/hotspot/.cproject Tue Feb 17 20:38:13 2015 +0100 @@ -45,7 +45,6 @@ -