Mercurial > hg > truffle

changeset 19773:e66a6f8d63e3

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Truffle: implement recursive inlining and with a maximum depth of 4.
author Christian Humer <christian.humer@gmail.com>
date Wed, 11 Mar 2015 15:44:32 +0100
parents b3f566135b56
children 5e74068c9150
files graal/com.oracle.graal.truffle.test/sl/TestInliningRecursive1.sl graal/com.oracle.graal.truffle.test/sl/TestInliningRecursive2.sl graal/com.oracle.graal.truffle/src/com/oracle/graal/truffle/DefaultInliningPolicy.java graal/com.oracle.graal.truffle/src/com/oracle/graal/truffle/TruffleCompilerOptions.java graal/com.oracle.graal.truffle/src/com/oracle/graal/truffle/TruffleInlining.java graal/com.oracle.graal.truffle/src/com/oracle/graal/truffle/TruffleInliningProfile.java
diffstat 6 files changed, 19 insertions(+), 21 deletions(-) [+]
line wrap: on
line diff
--- a/graal/com.oracle.graal.truffle.test/sl/TestInliningRecursive1.sl	Wed Mar 11 15:44:32 2015 +0100
+++ b/graal/com.oracle.graal.truffle.test/sl/TestInliningRecursive1.sl	Wed Mar 11 15:44:32 2015 +0100
@@ -20,6 +20,4 @@
 
 function main() {
     callUntilOptimized(test);
-    assertTrue(isInlined(test, test, fib), "fib is not inlined");
-    assertFalse(isInlined(test, fib, fib), "fib -> fib is not inlined");
 }  
--- a/graal/com.oracle.graal.truffle.test/sl/TestInliningRecursive2.sl	Wed Mar 11 15:44:32 2015 +0100
+++ b/graal/com.oracle.graal.truffle.test/sl/TestInliningRecursive2.sl	Wed Mar 11 15:44:32 2015 +0100
@@ -29,9 +29,4 @@
 function main() {
     callUntilOptimized(test);
     assertTrue(isInlined(test, test, fib), "not inlined: test -> fib");
-    
-    assertTrue(isInlined(test, fib, call), "not inlined: fib -> call");
-    assertFalse(isInlined(test, call, fib), "inlined: call -> fib"); 
-    assertTrue(isInlined(test, call, void), "inlined: call -> void");
-    
 }  
--- a/graal/com.oracle.graal.truffle/src/com/oracle/graal/truffle/DefaultInliningPolicy.java	Wed Mar 11 15:44:32 2015 +0100
+++ b/graal/com.oracle.graal.truffle/src/com/oracle/graal/truffle/DefaultInliningPolicy.java	Wed Mar 11 15:44:32 2015 +0100
@@ -28,7 +28,7 @@
 
 public class DefaultInliningPolicy implements TruffleInliningPolicy {
 
-    private static final String REASON_RECURSION = "recursion";
+    private static final String REASON_RECURSION = "number of recursions > " + TruffleMaximumRecursiveInlining.getValue();
     private static final String REASON_MAXIMUM_NODE_COUNT = "deepNodeCount * callSites  > " + TruffleInliningMaxCallerSize.getValue();
     private static final String REASON_MAXIMUM_TOTAL_NODE_COUNT = "totalNodeCount > " + TruffleInliningMaxCallerSize.getValue();
 
@@ -39,7 +39,7 @@
 
     @Override
     public boolean isAllowed(TruffleInliningProfile profile, int currentNodeCount, CompilerOptions options) {
-        if (profile.isRecursiveCall()) {
+        if (profile.getRecursions() > TruffleMaximumRecursiveInlining.getValue()) {
             profile.setFailedReason(REASON_RECURSION);
             return false;
         }
--- a/graal/com.oracle.graal.truffle/src/com/oracle/graal/truffle/TruffleCompilerOptions.java	Wed Mar 11 15:44:32 2015 +0100
+++ b/graal/com.oracle.graal.truffle/src/com/oracle/graal/truffle/TruffleCompilerOptions.java	Wed Mar 11 15:44:32 2015 +0100
@@ -74,6 +74,9 @@
     @Option(help = "Stop inlining if caller's cumulative tree size would exceed this limit", type = OptionType.Expert)
     public static final OptionValue<Integer> TruffleInliningMaxCallerSize = new OptionValue<>(2250);
 
+    @Option(help = "Maximum level of recursive inlining", type = OptionType.Expert)
+    public static final OptionValue<Integer> TruffleMaximumRecursiveInlining = new OptionValue<>(4);
+
     @Option(help = "Defines the number of graal nodes that triggers a performance warning.", type = OptionType.Debug)
     public static final OptionValue<Integer> TrufflePerformanceWarningGraalNodeCount = new OptionValue<>(1000);
 
--- a/graal/com.oracle.graal.truffle/src/com/oracle/graal/truffle/TruffleInlining.java	Wed Mar 11 15:44:32 2015 +0100
+++ b/graal/com.oracle.graal.truffle/src/com/oracle/graal/truffle/TruffleInlining.java	Wed Mar 11 15:44:32 2015 +0100
@@ -68,15 +68,15 @@
         double frequency = calculateFrequency(parentTarget, callNode);
         int nodeCount = callNode.getCurrentCallTarget().countNonTrivialNodes();
 
-        boolean recursive = isRecursiveStack(callStack);
+        int recursions = countRecursions(callStack);
         int deepNodeCount = nodeCount;
-        if (!recursive && callStack.size() < 15) {
+        if (callStack.size() < 15 && recursions <= TruffleCompilerOptions.TruffleMaximumRecursiveInlining.getValue()) {
             /*
              * We make a preliminary optimistic inlining decision with best possible characteristics
              * to avoid the exploration of unnecessary paths in the inlining tree.
              */
             final CompilerOptions options = callNode.getRootNode().getCompilerOptions();
-            if (policy.isAllowed(new TruffleInliningProfile(callNode, nodeCount, nodeCount, frequency, recursive), callStackNodeCount, options)) {
+            if (policy.isAllowed(new TruffleInliningProfile(callNode, nodeCount, nodeCount, frequency, recursions), callStackNodeCount, options)) {
                 List<TruffleInliningDecision> exploredCallSites = exploreCallSites(callStack, callStackNodeCount + nodeCount, policy);
                 childCallSites = decideInlining(exploredCallSites, policy, nodeCount, options);
                 for (TruffleInliningDecision childCallSite : childCallSites) {
@@ -90,7 +90,7 @@
             }
         }
 
-        TruffleInliningProfile profile = new TruffleInliningProfile(callNode, nodeCount, deepNodeCount, frequency, recursive);
+        TruffleInliningProfile profile = new TruffleInliningProfile(callNode, nodeCount, deepNodeCount, frequency, recursions);
         profile.setScore(policy.calculateScore(profile));
         return new TruffleInliningDecision(currentTarget, profile, childCallSites);
     }
@@ -99,14 +99,16 @@
         return (double) Math.max(1, ocn.getCallCount()) / (double) Math.max(1, target.getCompilationProfile().getInterpreterCallCount());
     }
 
-    private static boolean isRecursiveStack(List<OptimizedCallTarget> stack) {
+    private static int countRecursions(List<OptimizedCallTarget> stack) {
+        int count = 0;
         OptimizedCallTarget top = stack.get(stack.size() - 1);
         for (int i = 0; i < stack.size() - 1; i++) {
             if (stack.get(i) == top) {
-                return true;
+                count++;
             }
         }
-        return false;
+
+        return count;
     }
 
     private static List<TruffleInliningDecision> decideInlining(List<TruffleInliningDecision> callSites, TruffleInliningPolicy policy, int nodeCount, CompilerOptions options) {
--- a/graal/com.oracle.graal.truffle/src/com/oracle/graal/truffle/TruffleInliningProfile.java	Wed Mar 11 15:44:32 2015 +0100
+++ b/graal/com.oracle.graal.truffle/src/com/oracle/graal/truffle/TruffleInliningProfile.java	Wed Mar 11 15:44:32 2015 +0100
@@ -30,22 +30,22 @@
     private final int nodeCount;
     private final int deepNodeCount;
     private final double frequency;
-    private final boolean recursiveCall;
+    private final int recursions;
 
     private String failedReason;
     private int queryIndex = -1;
     private double score;
 
-    public TruffleInliningProfile(OptimizedDirectCallNode callNode, int nodeCount, int deepNodeCount, double frequency, boolean recursiveCall) {
+    public TruffleInliningProfile(OptimizedDirectCallNode callNode, int nodeCount, int deepNodeCount, double frequency, int recursions) {
         this.callNode = callNode;
         this.nodeCount = nodeCount;
         this.deepNodeCount = deepNodeCount;
         this.frequency = frequency;
-        this.recursiveCall = recursiveCall;
+        this.recursions = recursions;
     }
 
-    public boolean isRecursiveCall() {
-        return recursiveCall;
+    public int getRecursions() {
+        return recursions;
     }
 
     public OptimizedDirectCallNode getCallNode() {