Mercurial > hg > truffle

changeset 9993:053b837d0d7d

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Readded the pass that fixes DeoptimizeNode probabilities.
author Christian Haeubl <haeubl@ssw.jku.at>
date Tue, 11 Jun 2013 13:10:25 +0200
parents b2aea23ee2b1
children f90fc8987779
files graal/com.oracle.graal.hotspot/src/com/oracle/graal/hotspot/meta/HotSpotProfilingInfo.java graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/ControlSplitNode.java graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/IfNode.java graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/InvokeWithExceptionNode.java graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/extended/SwitchNode.java graal/com.oracle.graal.phases/src/com/oracle/graal/phases/graph/ComputeProbabilityClosure.java
diffstat 6 files changed, 108 insertions(+), 7 deletions(-) [+]
line wrap: on
line diff
--- a/graal/com.oracle.graal.hotspot/src/com/oracle/graal/hotspot/meta/HotSpotProfilingInfo.java	Mon Jun 10 15:17:10 2013 +0200
+++ b/graal/com.oracle.graal.hotspot/src/com/oracle/graal/hotspot/meta/HotSpotProfilingInfo.java	Tue Jun 11 13:10:25 2013 +0200
@@ -22,12 +22,9 @@
  */
 package com.oracle.graal.hotspot.meta;
 
-import static com.oracle.graal.hotspot.HotSpotGraalRuntime.*;
-
 import com.oracle.graal.api.meta.*;
 import com.oracle.graal.debug.*;
 import com.oracle.graal.hotspot.*;
-import com.oracle.graal.phases.*;
 
 public final class HotSpotProfilingInfo extends CompilerObject implements ProfilingInfo {
 
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/ControlSplitNode.java	Mon Jun 10 15:17:10 2013 +0200
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/ControlSplitNode.java	Tue Jun 11 13:10:25 2013 +0200
@@ -35,4 +35,6 @@
     }
 
     public abstract double probability(AbstractBeginNode successor);
+
+    public abstract void setProbability(AbstractBeginNode successor, double value);
 }
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/IfNode.java	Mon Jun 10 15:17:10 2013 +0200
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/IfNode.java	Tue Jun 11 13:10:25 2013 +0200
@@ -132,6 +132,12 @@
     }
 
     @Override
+    public void setProbability(AbstractBeginNode successor, double value) {
+        assert successor == trueSuccessor || successor == falseSuccessor;
+        setTrueSuccessorProbability(successor == trueSuccessor ? value : 1 - value);
+    }
+
+    @Override
     public void generate(LIRGeneratorTool gen) {
         gen.emitIf(this);
     }
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/InvokeWithExceptionNode.java	Mon Jun 10 15:17:10 2013 +0200
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/InvokeWithExceptionNode.java	Tue Jun 11 13:10:25 2013 +0200
@@ -36,6 +36,8 @@
 @NodeInfo(nameTemplate = "Invoke!#{p#targetMethod/s}")
 public class InvokeWithExceptionNode extends ControlSplitNode implements Node.IterableNodeType, Invoke, MemoryCheckpoint, LIRLowerable {
 
+    private static final double EXCEPTION_PROBA = 1e-5;
+
     @Successor private AbstractBeginNode next;
     @Successor private DispatchBeginNode exceptionEdge;
     @Input private CallTargetNode callTarget;
@@ -45,6 +47,7 @@
     private final int bci;
     private boolean polymorphic;
     private boolean useForInlining;
+    private double exceptionProbability;
 
     public InvokeWithExceptionNode(CallTargetNode callTarget, DispatchBeginNode exceptionEdge, int bci) {
         super(callTarget.returnStamp());
@@ -53,6 +56,7 @@
         this.callTarget = callTarget;
         this.polymorphic = false;
         this.useForInlining = true;
+        this.exceptionProbability = EXCEPTION_PROBA;
     }
 
     public DispatchBeginNode exceptionEdge() {
@@ -205,11 +209,15 @@
         }
     }
 
-    private static final double EXCEPTION_PROBA = 1e-5;
+    @Override
+    public double probability(AbstractBeginNode successor) {
+        return successor == next ? 1 - exceptionProbability : exceptionProbability;
+    }
 
     @Override
-    public double probability(AbstractBeginNode successor) {
-        return successor == next ? 1 - EXCEPTION_PROBA : EXCEPTION_PROBA;
+    public void setProbability(AbstractBeginNode successor, double value) {
+        assert successor == next || successor == exceptionEdge;
+        this.exceptionProbability = successor == next ? 1 - value : value;
     }
 
     @Override
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/extended/SwitchNode.java	Mon Jun 10 15:17:10 2013 +0200
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/extended/SwitchNode.java	Tue Jun 11 13:10:25 2013 +0200
@@ -76,7 +76,8 @@
         return sum;
     }
 
-    public void setProbability(Node successor, double value) {
+    @Override
+    public void setProbability(AbstractBeginNode successor, double value) {
         double changeInProbability = 0;
         int nonZeroProbabilityCases = 0;
         for (int i = 0; i < keySuccessors.length; i++) {
--- 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);