# HG changeset patch
# User Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
# Date 1367069897 -7200
# Node ID f1170c277b7b2b403039464bbbc591e5893020b4
# Parent  50a81e6eddbc7d9be5f0cf2a7f6ebcbcadf1b286
Implement instanceof after instanceof swapping.

diff -r 50a81e6eddbc -r f1170c277b7b graal/com.oracle.graal.api.meta/src/com/oracle/graal/api/meta/JavaTypeProfile.java
--- a/graal/com.oracle.graal.api.meta/src/com/oracle/graal/api/meta/JavaTypeProfile.java	Sat Apr 27 14:01:59 2013 +0200
+++ b/graal/com.oracle.graal.api.meta/src/com/oracle/graal/api/meta/JavaTypeProfile.java	Sat Apr 27 15:38:17 2013 +0200
@@ -78,6 +78,11 @@
             }
             return 0;
         }
+
+        @Override
+        public String toString() {
+            return "{" + type.getName() + ", " + probability + "}";
+        }
     }
 
     private final TriState nullSeen;
@@ -129,4 +134,38 @@
     public ProfiledType[] getTypes() {
         return ptypes;
     }
+
+    /**
+     * Searches for an entry of a given resolved Java type.
+     * 
+     * @param type the type for which an entry should be searched
+     * @return the entry or null if no entry for this type can be found
+     */
+    public ProfiledType findEntry(ResolvedJavaType type) {
+        if (ptypes != null) {
+            for (ProfiledType pt : ptypes) {
+                if (pt.getType() == type) {
+                    return pt;
+                }
+            }
+        }
+        return null;
+    }
+
+    @Override
+    public String toString() {
+        StringBuilder builder = new StringBuilder();
+        builder.append("JavaTypeProfile[");
+        builder.append(this.nullSeen);
+        builder.append(", ");
+        if (ptypes != null) {
+            for (ProfiledType pt : ptypes) {
+                builder.append(pt.toString());
+                builder.append(", ");
+            }
+        }
+        builder.append(this.notRecordedProbability);
+        builder.append("]");
+        return builder.toString();
+    }
 }
diff -r 50a81e6eddbc -r f1170c277b7b 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	Sat Apr 27 14:01:59 2013 +0200
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/IfNode.java	Sat Apr 27 15:38:17 2013 +0200
@@ -22,14 +22,16 @@
  */
 package com.oracle.graal.nodes;
 
-import java.io.*;
 import java.util.*;
 
 import com.oracle.graal.api.meta.*;
+import com.oracle.graal.api.meta.JavaTypeProfile.ProfiledType;
+import com.oracle.graal.debug.*;
 import com.oracle.graal.graph.*;
 import com.oracle.graal.graph.iterators.*;
 import com.oracle.graal.nodes.PhiNode.PhiType;
 import com.oracle.graal.nodes.calc.*;
+import com.oracle.graal.nodes.java.*;
 import com.oracle.graal.nodes.spi.*;
 import com.oracle.graal.nodes.type.*;
 import com.oracle.graal.nodes.util.*;
@@ -162,6 +164,81 @@
         if (removeIntermediateMaterialization(tool)) {
             return;
         }
+
+        if (falseSuccessor().guards().isEmpty() && falseSuccessor().next() instanceof IfNode) {
+            BeginNode intermediateBegin = falseSuccessor();
+            IfNode nextIf = (IfNode) intermediateBegin.next();
+            double probabilityB = (1.0 - this.trueSuccessorProbability) * nextIf.trueSuccessorProbability;
+            if (this.trueSuccessorProbability < probabilityB) {
+                // Reordering of those two if statements is beneficial from the point of view of
+                // their probabilities.
+                if (prepareForSwap(condition(), nextIf.condition(), this.trueSuccessorProbability, probabilityB)) {
+                    assert intermediateBegin.next() == nextIf;
+                    BeginNode bothFalseBegin = nextIf.falseSuccessor();
+                    nextIf.setFalseSuccessor(null);
+                    intermediateBegin.setNext(null);
+                    this.setFalseSuccessor(null);
+
+                    this.replaceAtPredecessor(nextIf);
+                    nextIf.setFalseSuccessor(intermediateBegin);
+                    intermediateBegin.setNext(this);
+                    this.setFalseSuccessor(bothFalseBegin);
+                }
+            }
+        }
+    }
+
+    private static boolean prepareForSwap(LogicNode a, LogicNode b, double probabilityA, double probabilityB) {
+        if (a instanceof InstanceOfNode) {
+            InstanceOfNode instanceOfA = (InstanceOfNode) a;
+            if (b instanceof InstanceOfNode) {
+                InstanceOfNode instanceOfB = (InstanceOfNode) b;
+                if (instanceOfA.object() == instanceOfB.object() && !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, %.3f) and (%s, %.3f)", instanceOfA.type(), probabilityA, instanceOfB.type(), probabilityB);
+                    JavaTypeProfile newProfile = null;
+                    if (profileA != null && profileB != null) {
+                        double remainder = 1.0;
+                        ArrayList<ProfiledType> 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(), 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(), 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);
+                    return true;
+                }
+            }
+        }
+
+        return false;
     }
 
     /**
diff -r 50a81e6eddbc -r f1170c277b7b graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/java/InstanceOfNode.java
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/java/InstanceOfNode.java	Sat Apr 27 14:01:59 2013 +0200
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/java/InstanceOfNode.java	Sat Apr 27 15:38:17 2013 +0200
@@ -36,7 +36,7 @@
 
     @Input private ValueNode object;
     private final ResolvedJavaType type;
-    private final JavaTypeProfile profile;
+    private JavaTypeProfile profile;
 
     /**
      * Constructs a new InstanceOfNode.
@@ -109,6 +109,10 @@
         return profile;
     }
 
+    public void setProfile(JavaTypeProfile profile) {
+        this.profile = profile;
+    }
+
     @Override
     public boolean verify() {
         for (Node usage : usages()) {