Mercurial > hg > graal-compiler

changeset 14079:ca92db718c74

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Truffle: refined split/inlining heuristics.
author Christian Humer <christian.humer@gmail.com>
date Wed, 05 Mar 2014 23:33:25 +0100
parents f157fabf6b38
children cd4595e8a685
files graal/com.oracle.graal.truffle/src/com/oracle/graal/truffle/OptimizedCallNode.java graal/com.oracle.graal.truffle/src/com/oracle/graal/truffle/OptimizedCallNodeProfile.java graal/com.oracle.graal.truffle/src/com/oracle/graal/truffle/OptimizedCallTarget.java graal/com.oracle.graal.truffle/src/com/oracle/graal/truffle/TruffleCompilerOptions.java graal/com.oracle.truffle.api/src/com/oracle/truffle/api/nodes/CallNode.java
diffstat 5 files changed, 88 insertions(+), 40 deletions(-) [+]
line wrap: on
line diff
--- a/graal/com.oracle.graal.truffle/src/com/oracle/graal/truffle/OptimizedCallNode.java	Wed Mar 05 23:33:25 2014 +0100
+++ b/graal/com.oracle.graal.truffle/src/com/oracle/graal/truffle/OptimizedCallNode.java	Wed Mar 05 23:33:25 2014 +0100
@@ -61,7 +61,6 @@
 
     @SuppressWarnings("unused")
     public void nodeReplaced(Node oldNode, Node newNode, String reason) {
-
     }
 
     @Override
@@ -88,38 +87,28 @@
 
     private static final class DefaultOptimizedCallNode extends OptimizedCallNode {
 
-        private boolean splitTried;
+        private boolean trySplit = true;
 
         DefaultOptimizedCallNode(OptimizedCallTarget target) {
             super(target);
+            registerCallTarget(this);
         }
 
         @Override
         public Object call(PackedFrame caller, Arguments arguments) {
             if (CompilerDirectives.inInterpreter()) {
                 callCount++;
-                if (!splitTried) {
+                if (trySplit && callCount > 1) {
+                    trySplit = false;
                     return trySplit(caller, arguments);
                 }
             }
             return callTarget.call(caller, arguments);
         }
 
-        @Override
-        public void nodeReplaced(Node oldNode, Node newNode, String reason) {
-
-        }
-
         private Object trySplit(PackedFrame caller, Arguments arguments) {
-            int effectiveCallCount = callCount;
-            // we try splitting for the first two invocations
-            if (effectiveCallCount <= 3) {
-                if (isSplittable() && shouldSplit()) {
-                    return splitImpl(true).call(caller, arguments);
-                }
-                if (effectiveCallCount == 3) {
-                    splitTried = true;
-                }
+            if (shouldSplit()) {
+                return splitImpl(true).call(caller, arguments);
             }
             return callTarget.call(caller, arguments);
         }
@@ -128,20 +117,35 @@
             if (!TruffleCompilerOptions.TruffleSplittingEnabled.getValue()) {
                 return false;
             }
-
+            if (!isSplittable()) {
+                return false;
+            }
             int nodeCount = NodeUtil.countNodes(getCallTarget().getRootNode(), null, false);
-
-            // max one child call and callCount > 2 and kind of small number of nodes
-            if (callCount > 2 && isMaxSingleCall()) {
-                if (nodeCount <= 100) {
-                    return true;
-                }
-            }
-
             if (nodeCount > TruffleCompilerOptions.TruffleSplittingMaxCalleeSize.getValue()) {
                 return false;
             }
-            return countPolymorphic() > 1 || countGeneric() > 0;
+
+// // is the only call target -> do not split
+// if (getCallTarget().getRootNode().getCachedCallNodes().size() == 1 &&
+// getCallTarget().getRootNode().getCachedCallNodes().contains(this)) {
+// return false;
+// }
+
+            // max one child call and callCount > 2 and kind of small number of nodes
+            if (isMaxSingleCall()) {
+                return true;
+            }
+            return countPolymorphic() >= 1 || countGeneric() > 0;
+        }
+
+        @Override
+        public void nodeReplaced(Node oldNode, Node newNode, String reason) {
+            trySplit = true;
+        }
+
+        @Override
+        protected void notifyCallNodeAdded() {
+            trySplit = true;
         }
 
         private boolean isMaxSingleCall() {
@@ -159,11 +163,11 @@
         }
 
         private int countPolymorphic() {
-            return NodeUtil.countNodes(getCallTarget().getRootNode(), null, Kind.POLYMORPHIC, true);
+            return NodeUtil.countNodes(getCallTarget().getRootNode(), null, Kind.POLYMORPHIC, false);
         }
 
         private int countGeneric() {
-            return NodeUtil.countNodes(getCallTarget().getRootNode(), null, Kind.GENERIC, true);
+            return NodeUtil.countNodes(getCallTarget().getRootNode(), null, Kind.GENERIC, false);
         }
 
         @Override
--- a/graal/com.oracle.graal.truffle/src/com/oracle/graal/truffle/OptimizedCallNodeProfile.java	Wed Mar 05 23:33:25 2014 +0100
+++ b/graal/com.oracle.graal.truffle/src/com/oracle/graal/truffle/OptimizedCallNodeProfile.java	Wed Mar 05 23:33:25 2014 +0100
@@ -52,12 +52,12 @@
         this.targetShallowNodeCount = NodeUtil.countNodes(inlineRoot, null, false);
         this.targetDeepNodeCount = NodeUtil.countNodes(inlineRoot, null, true);
         this.compilationRoots = findCompilationRoots(callNode);
-        this.averageFrequency = calculateFrequency(compilationRoots);
+        this.averageFrequency = calculateFrequency();
         this.score = calculateScore();
     }
 
-    private double calculateFrequency(@SuppressWarnings("unused") List<OptimizedCallTarget> compilationRoots2) {
-        return calculateSimpleFrequency();
+    private double calculateFrequency() {
+        return calculateAdvancedFrequency();
     }
 
     public OptimizedCallNode getCallNode() {
@@ -143,6 +143,50 @@
 
     }
 
+    double calculateAdvancedFrequency() {
+        // get the call hierarchy from call target to the call node
+        final ArrayDeque<OptimizedCallNode> callStack = new ArrayDeque<>();
+        callTarget.getRootNode().accept(new NodeVisitor() {
+            private boolean found = false;
+
+            public boolean visit(Node node) {
+                if (node == callNode) {
+                    // found our call
+                    callStack.push((OptimizedCallNode) node);
+                    found = true;
+                    return false;
+                }
+
+                if (node instanceof OptimizedCallNode) {
+                    OptimizedCallNode c = ((OptimizedCallNode) node);
+                    if (c.isInlined()) {
+                        if (!found) {
+                            callStack.push(c);
+                        }
+                        c.getCurrentRootNode().accept(this);
+                        if (!found) {
+                            callStack.pop();
+                        }
+                    }
+                }
+                return !found;
+            }
+        });
+
+        int parentCallCount = callTarget.getCompilationProfile().getCallCount();
+        double frequency = 1.0d;
+        for (OptimizedCallNode c : callStack) {
+            int childCallCount = c.getCallCount();
+            frequency *= childCallCount / (double) parentCallCount;
+            if (c.isInlined() || c.isSplit()) {
+                parentCallCount = childCallCount;
+            } else {
+                parentCallCount = c.getCurrentCallTarget().getCompilationProfile().getCallCount();
+            }
+        }
+        return frequency;
+    }
+
     double calculateSimpleFrequency() {
         return callNode.getCallCount() / (double) callTarget.getCompilationProfile().getCallCount();
     }
--- a/graal/com.oracle.graal.truffle/src/com/oracle/graal/truffle/OptimizedCallTarget.java	Wed Mar 05 23:33:25 2014 +0100
+++ b/graal/com.oracle.graal.truffle/src/com/oracle/graal/truffle/OptimizedCallTarget.java	Wed Mar 05 23:33:25 2014 +0100
@@ -213,7 +213,7 @@
             public boolean visit(Node node) {
                 if (node instanceof OptimizedCallNode) {
                     OptimizedCallNode call = ((OptimizedCallNode) node);
-                    if (call.isInlinable() && !call.isInlined() && !visitedCallSites.contains(call)) {
+                    if (!call.isInlined() && !visitedCallSites.contains(call)) {
                         queue.add(call.createInliningProfile(target));
                         visitedCallSites.add(call);
                     }
--- a/graal/com.oracle.graal.truffle/src/com/oracle/graal/truffle/TruffleCompilerOptions.java	Wed Mar 05 23:33:25 2014 +0100
+++ b/graal/com.oracle.graal.truffle/src/com/oracle/graal/truffle/TruffleCompilerOptions.java	Wed Mar 05 23:33:25 2014 +0100
@@ -66,7 +66,7 @@
     @Option(help = "Enable call target splitting")
     public static final OptionValue<Boolean> TruffleSplittingEnabled = new OptionValue<>(true);
     @Option(help = "Disable call target splitting if tree size exceeds this limit")
-    public static final OptionValue<Integer> TruffleSplittingMaxCalleeSize = new OptionValue<>(50);
+    public static final OptionValue<Integer> TruffleSplittingMaxCalleeSize = new OptionValue<>(100);
     @Option(help = "Number of most recently used methods in truffle cache")
     public static final OptionValue<Integer> TruffleMaxCompilationCacheSize = new OptionValue<>(512);
     @Option(help = "Enable asynchronous truffle compilation in background thread")
--- a/graal/com.oracle.truffle.api/src/com/oracle/truffle/api/nodes/CallNode.java	Wed Mar 05 23:33:25 2014 +0100
+++ b/graal/com.oracle.truffle.api/src/com/oracle/truffle/api/nodes/CallNode.java	Wed Mar 05 23:33:25 2014 +0100
@@ -111,13 +111,13 @@
             oldRoot.removeCachedCallNode(oldCall);
         }
 
-        /*
-         * New call nodes are registered in the new target root node.
-         */
-        CallNode newCall = (CallNode) newNode;
-        RootNode newRoot = newCall.getCurrentRootNode();
+        registerCallTarget((CallNode) newNode);
+    }
+
+    protected final void registerCallTarget(CallNode newNode) {
+        RootNode newRoot = newNode.getCurrentRootNode();
         if (newRoot != null) {
-            newRoot.addCachedCallNode(newCall);
+            newRoot.addCachedCallNode(newNode);
         }
     }