# HG changeset patch
# User Doug Simon <doug.simon@oracle.com>
# Date 1351265577 -7200
# Node ID adb3879ffbe2e686b160fa094ec2cd9f984a5520
# Parent  cc32ce37eddc2e39ea5d4519df1c69b8a394aba3
improved IfNode simplification of removing intermediate materializations to handle (some) MergeNodes with a non-null frame state

diff -r cc32ce37eddc -r adb3879ffbe2 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	Thu Oct 25 20:08:32 2012 +0200
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/IfNode.java	Fri Oct 26 17:32:57 2012 +0200
@@ -233,32 +233,37 @@
             return false;
         }
 
-        if (merge.stateAfter() != null) {
-            // Not sure how (or if) the frame state of the merge can be correctly propagated to the successors
+        // Only consider merges with a single usage that is both a phi and an operand of the comparison
+        NodeUsagesList mergeUsages = merge.usages();
+        if (mergeUsages.count() != 1) {
             return false;
         }
-
-        NodeUsagesList usages = merge.usages();
-        if (usages.count() != 1) {
-            return false;
-        }
-
-        Node singleUsage = usages.first();
-
+        Node singleUsage = mergeUsages.first();
         if (!(singleUsage instanceof PhiNode) || (singleUsage != compare.x() && singleUsage != compare.y())) {
             return false;
         }
 
+        // Ensure phi is used by at most the comparison and the merge's frame state (if any)
+        PhiNode phi = (PhiNode) singleUsage;
+        for (Node usage : phi.usages()) {
+            if (usage != compare && usage != merge.stateAfter()) {
+                return false;
+            }
+        }
+
+
         Constant[] xs = constantValues(compare.x(), merge);
         Constant[] ys = constantValues(compare.y(), merge);
-
         if (xs == null || ys == null) {
             return false;
         }
 
+        // DebugScope.dump(this.graph(), "Before removeIntermediateMaterialization");
+
         List<EndNode> mergePredecessors = merge.cfgPredecessors().snapshot();
         List<EndNode> falseEnds = new ArrayList<>(mergePredecessors.size());
         List<EndNode> trueEnds = new ArrayList<>(mergePredecessors.size());
+        Map<EndNode, ValueNode> phiValues = new HashMap<>(mergePredecessors.size());
 
         BeginNode falseSuccessor = falseSuccessor();
         BeginNode trueSuccessor = trueSuccessor();
@@ -269,7 +274,7 @@
         Iterator<EndNode> ends = mergePredecessors.iterator();
         for (int i = 0; i < xs.length; i++) {
             EndNode end = ends.next();
-            merge.removeEnd(end);
+            phiValues.put(end, phi.valueAt(end));
             if (compare.condition().foldCondition(xs[i], ys[i], tool.runtime(), compare.unorderedIsTrue())) {
                 trueEnds.add(end);
             } else {
@@ -278,8 +283,8 @@
         }
         assert !ends.hasNext();
 
-        connectEnds(falseEnds, falseSuccessor, tool);
-        connectEnds(trueEnds, trueSuccessor, tool);
+        connectEnds(falseEnds, phiValues, falseSuccessor, merge, tool);
+        connectEnds(trueEnds, phiValues, trueSuccessor, merge, tool);
 
         GraphUtil.killCFG(merge);
         return true;
@@ -290,22 +295,37 @@
      * there is more than one end. If {@code ends} is empty, then {@code successor}
      * is {@linkplain GraphUtil#killCFG(FixedNode) killed} otherwise it is added to {@code tool}'s
      * {@linkplain SimplifierTool#addToWorkList(com.oracle.graal.graph.Node) work list}.
+     *
+     * @param oldMerge the merge being removed
+     * @param phiValues the values of the phi at the merge, keyed by the merge ends
      */
-    private void connectEnds(List<EndNode> ends, BeginNode successor, SimplifierTool tool) {
+    private void connectEnds(List<EndNode> ends, Map<EndNode, ValueNode> phiValues, BeginNode successor, MergeNode oldMerge, SimplifierTool tool) {
         if (ends.isEmpty()) {
             GraphUtil.killCFG(successor);
         } else {
             if (ends.size() == 1) {
-
                 EndNode end = ends.get(0);
                 ((FixedWithNextNode) end.predecessor()).setNext(successor);
+                oldMerge.removeEnd(end);
                 GraphUtil.killCFG(end);
             } else {
-                MergeNode falseMerge = graph().add(new MergeNode());
+                MergeNode newMerge = graph().add(new MergeNode());
+                PhiNode oldPhi = (PhiNode) oldMerge.usages().first();
+                PhiNode newPhi = graph().add(new PhiNode(oldPhi.stamp(), newMerge));
+
                 for (EndNode end : ends) {
-                    falseMerge.addForwardEnd(end);
+                    newPhi.addInput(phiValues.get(end));
+                    newMerge.addForwardEnd(end);
                 }
-                falseMerge.setNext(successor);
+
+                FrameState stateAfter = oldMerge.stateAfter();
+                if (stateAfter != null) {
+                    stateAfter = stateAfter.duplicate();
+                    stateAfter.replaceFirstInput(oldPhi, newPhi);
+                    newMerge.setStateAfter(stateAfter);
+                }
+
+                newMerge.setNext(successor);
             }
             tool.addToWorkList(successor);
         }
diff -r cc32ce37eddc -r adb3879ffbe2 graal/com.oracle.graal.snippets.test/src/com/oracle/graal/snippets/InstanceOfTest.java
--- a/graal/com.oracle.graal.snippets.test/src/com/oracle/graal/snippets/InstanceOfTest.java	Thu Oct 25 20:08:32 2012 +0200
+++ b/graal/com.oracle.graal.snippets.test/src/com/oracle/graal/snippets/InstanceOfTest.java	Fri Oct 26 17:32:57 2012 +0200
@@ -231,16 +231,11 @@
     }
 
     /**
-     * This test exists to show the kind of pattern that *should* be optimizable by {@code removeIntermediateMaterialization()}
-     * in {@link IfNode}. The optimization is currently blocked for the code pattern in this method because of a non-null
-     * frame state at the position indicated in the source. For this particular method, the frame state could be ignored
-     * as there are no deopt points after the merge. However, this is not the case for all methods where this pattern is
-     * present. The problem (yet to be solved) is figuring how how to evacuate the frame state of the merge to
-     * the code paths that result from the transformation.
+     * This test exists to show the kind of pattern that is be optimizable by
+     * {@code removeIntermediateMaterialization()} in {@link IfNode}.
      * <p>
      * The test exists in this source file as the transformation was originally motivated by the need to
-     * remove use of special JumpNodes in the {@code InstanceOfSnippets}. The transformation works for
-     * the snippet as all frame state are stripped from snippets.
+     * remove use of special JumpNodes in the {@code InstanceOfSnippets}.
      */
     @Test
     public void test_removeIntermediateMaterialization() {
@@ -263,7 +258,6 @@
                 }
             }
         }
-        // The merge here has a non-null frame state
         if (test) {
             return a;
         }