--- a/graal/com.oracle.graal.phases/src/com/oracle/graal/phases/graph/ComputeProbabilityClosure.java	Mon Jun 10 15:17:10 2013 +0200
+++ b/graal/com.oracle.graal.phases/src/com/oracle/graal/phases/graph/ComputeProbabilityClosure.java	Tue Jun 11 13:10:25 2013 +0200
@@ -24,6 +24,7 @@
 
 import java.util.*;
 
+import com.oracle.graal.debug.internal.*;
 import com.oracle.graal.graph.*;
 import com.oracle.graal.nodes.*;
 import com.oracle.graal.nodes.util.*;
@@ -63,12 +64,98 @@
     }
 
     public NodesToDoubles apply() {
+        adjustControlSplitProbabilities();
         new PropagateProbability(graph.start()).apply();
         computeLoopFactors();
         new PropagateLoopFrequency(graph.start()).apply();
+        assert verifyProbabilities();
         return nodeProbabilities;
     }
 
+    /**
+     * Assume that paths with a DeoptimizeNode at their end are taken infrequently.
+     */
+    private void adjustControlSplitProbabilities() {
+        HashSet<ControlSplitNode> result = new HashSet<>();
+        NodeBitMap visitedNodes = new NodeBitMap(graph);
+        for (DeoptimizeNode n : graph.getNodes(DeoptimizeNode.class)) {
+            if (n.action().doesInvalidateCompilation()) {
+                findParentControlSplitNodes(result, n, visitedNodes);
+            }
+        }
+
+        for (ControlSplitNode n : result) {
+            if (!allSuxVisited(n, visitedNodes)) {
+                modifyProbabilities(n, visitedNodes);
+            }
+        }
+    }
+
+    private static void findParentControlSplitNodes(HashSet<ControlSplitNode> result, DeoptimizeNode n, NodeBitMap visitedNodes) {
+        ArrayDeque<FixedNode> nodes = new ArrayDeque<>();
+        nodes.push(n);
+
+        Node currentNode;
+        do {
+            currentNode = nodes.pop();
+            visitedNodes.mark(currentNode);
+
+            for (Node pred : currentNode.cfgPredecessors()) {
+                FixedNode fixedPred = (FixedNode) pred;
+                if (visitedNodes.isMarked(fixedPred) && allPredsVisited(fixedPred, visitedNodes)) {
+                    DebugScope.dump(n.graph(), "ComputeProbabilityClosure");
+                    GraalInternalError.shouldNotReachHere(String.format("Endless loop because %s was already visited", fixedPred));
+                } else if (allSuxVisited(fixedPred, visitedNodes)) {
+                    nodes.push(fixedPred);
+                } else {
+                    assert fixedPred instanceof ControlSplitNode : "only control splits can have more than one sux";
+                    result.add((ControlSplitNode) fixedPred);
+                }
+            }
+        } while (!nodes.isEmpty());
+    }
+
+    private static void modifyProbabilities(ControlSplitNode controlSplit, NodeBitMap visitedNodes) {
+        assert !allSuxVisited(controlSplit, visitedNodes);
+        for (Node sux : controlSplit.successors()) {
+            if (visitedNodes.isMarked(sux)) {
+                controlSplit.setProbability((AbstractBeginNode) sux, 0);
+            }
+        }
+    }
+
+    private static boolean allSuxVisited(FixedNode node, NodeBitMap visitedNodes) {
+        return allVisited(node.successors(), visitedNodes);
+    }
+
+    private static boolean allPredsVisited(FixedNode node, NodeBitMap visitedNodes) {
+        return allVisited(node.cfgPredecessors(), visitedNodes);
+    }
+
+    private static boolean allVisited(Iterable<? extends Node> nodes, NodeBitMap visitedNodes) {
+        for (Node sux : nodes) {
+            if (!visitedNodes.contains(sux)) {
+                return false;
+            }
+        }
+        return true;
+    }
+
+    private boolean verifyProbabilities() {
+        if (doesNotAlwaysDeopt(graph)) {
+            for (DeoptimizeNode n : graph.getNodes(DeoptimizeNode.class)) {
+                if (n.action().doesInvalidateCompilation() && nodeProbabilities.get(n) > 0.01) {
+                    throw new AssertionError(String.format("%s with reason %s and probability %f in graph %s", n, n.reason(), nodeProbabilities.get(n), graph));
+                }
+            }
+        }
+        return true;
+    }
+
+    private static boolean doesNotAlwaysDeopt(StructuredGraph graph) {
+        return graph.getNodes(ReturnNode.class).iterator().hasNext();
+    }
+
     private void computeLoopFactors() {
         for (LoopInfo info : loopInfos) {
             double frequency = info.loopFrequency(nodeProbabilities);