我知道 Java 尚未添加尾调用消除优化，并打算将其作为Project Loom的后期添加。相反，我的问题是：JIT 是否会完全优化递归方法调用并将它们转换为迭代形式？名义上这似乎是可能的，但相对困难，所以我猜他们是否会在某些文档中进行强烈描述，但我正在努力追踪有关该主题的任何内容。
作为后续，如果 JIT 确实消除了超出 Loom 中描述的某种形式的递归调用，那么它是如何出现在堆栈跟踪上的？
问问题
122 次
1 回答
2
您的问题“它是如何出现在堆栈跟踪上的？” 是 JVM 中尾调用优化的未解决问题之一。对 Java 代码的可管理性有一个期望，特别是当代码在递归算法中花费很长时间（或者甚至挂在无休止的递归中）并且开发人员想要找出发生了什么时。
所以简而言之，JVM（当前版本的 HotSpot）没有尾调用优化。但它能够内联有限数量的递归调用，就像它可以内联其他调用一样。
当我们使用
public class Recursion {
public static void main(String[] args) {
runs: for(int run = 0; run < 10; run++) {
for(int i = 1; i < 1_000_000_000; i++) try {
int counted = recursiveCounter(i, 0);
if(i != counted) throw new AssertionError();
} catch(StackOverflowError e) {
System.out.println("limit reached at " + i);
continue runs;
}
}
}
private static int recursiveCounter(int limit, int count) {
return limit == 0? count: recursiveCounter(limit - 1, count + 1);
}
}
我们得到的值类似于为什么我可以达到的最大递归深度是不确定的？运行-XX:CompileCommand=print,Recursion.recursiveCounter
-XX:+UnlockDiagnosticVMOptions -XX:+PrintInlining打印
@ 18 Recursion::recursiveCounter (18 bytes) inline
@ 14 Recursion::recursiveCounter (18 bytes) inline
@ 14 Recursion::recursiveCounter (18 bytes) recursive inlining too deep
和
0x0000026398871220: mov dword ptr [rsp+0ffffffffffff9000h],eax
0x0000026398871227: push rbp
0x0000026398871228: sub rsp,10h ;*synchronization entry
; - Recursion::recursiveCounter@-1 (line 16)
0x000002639887122c: test edx,edx
0x000002639887122e: je 26398871254h ;*ifne {reexecute=0 rethrow=0 return_oop=0}
; - Recursion::recursiveCounter@1 (line 16)
0x0000026398871230: cmp edx,1h
0x0000026398871233: je 26398871259h ;*ifne {reexecute=0 rethrow=0 return_oop=0}
; - Recursion::recursiveCounter@1 (line 16)
; - Recursion::recursiveCounter@14 (line 16)
0x0000026398871235: add r8d,2h ;*iadd {reexecute=0 rethrow=0 return_oop=0}
; - Recursion::recursiveCounter@13 (line 16)
; - Recursion::recursiveCounter@14 (line 16)
0x0000026398871239: add edx,0fffffffeh ;*isub {reexecute=0 rethrow=0 return_oop=0}
; - Recursion::recursiveCounter@10 (line 16)
; - Recursion::recursiveCounter@14 (line 16)
0x000002639887123c: nop
0x000002639887123f: call 26398871220h ; ImmutableOopMap {}
;*invokestatic recursiveCounter {reexecute=0 rethrow=0 return_oop=0}
; - Recursion::recursiveCounter@14 (line 16)
; - Recursion::recursiveCounter@14 (line 16)
; {static_call}
0x0000026398871244: add rsp,10h
0x0000026398871248: pop rbp
0x0000026398871249: mov r10,qword ptr [r15+110h]
0x0000026398871250: test dword ptr [r10],eax ; {poll_return}
0x0000026398871253: ret
0x0000026398871254: mov eax,r8d
0x0000026398871257: jmp 26398871244h
0x0000026398871259: mov eax,r8d
0x000002639887125c: inc eax ;*iadd {reexecute=0 rethrow=0 return_oop=0}
; - Recursion::recursiveCounter@13 (line 16)
0x000002639887125e: jmp 26398871244h ;*invokestatic recursiveCounter {reexecute=0 rethrow=0 return_oop=0}
; - Recursion::recursiveCounter@14 (line 16)
; - Recursion::recursiveCounter@14 (line 16)
0x0000026398871260: mov rdx,rax
0x0000026398871263: add rsp,10h
0x0000026398871267: pop rbp
0x0000026398871268: jmp 26390ea4d00h ;*ireturn {reexecute=0 rethrow=0 return_oop=0}
; - Recursion::recursiveCounter@17 (line 16)
; - Recursion::recursiveCounter@14 (line 16)
; {runtime_call _rethrow_Java}
有趣的部分是符合我们条件的test edx,edx指令。limit == 0如果这个条件不满足，cmp edx,1h接下来会有一个测试，有效地测试下一个递归调用将测试什么，如果这个条件也不满足，代码将执行add r8d,2hand add edx,0fffffffeh，增加count2 并减少limit2。
所以我们清楚地看到了内联一级递归和融合操作的效果。内联诊断告诉我们已经超过了限制，因此值得研究指定时会发生什么，例如-XX:MaxRecursiveInlineLevel=4：
@ 18 Recursion::recursiveCounter (18 bytes) inline
@ 14 Recursion::recursiveCounter (18 bytes) inline
@ 14 Recursion::recursiveCounter (18 bytes) inline
@ 14 Recursion::recursiveCounter (18 bytes) inline
@ 14 Recursion::recursiveCounter (18 bytes) inline
@ 14 Recursion::recursiveCounter (18 bytes) recursive inlining too deep
0x0000025345d31620: mov dword ptr [rsp+0ffffffffffff9000h],eax
0x0000025345d31627: push rbp
0x0000025345d31628: sub rsp,10h ;*synchronization entry
; - Recursion::recursiveCounter@-1 (line 16)
0x0000025345d3162c: test edx,edx
0x0000025345d3162e: je 25345d31660h ;*ifne {reexecute=0 rethrow=0 return_oop=0}
; - Recursion::recursiveCounter@1 (line 16)
0x0000025345d31630: cmp edx,1h
0x0000025345d31633: je 25345d31665h ;*ifne {reexecute=0 rethrow=0 return_oop=0}
; - Recursion::recursiveCounter@1 (line 16)
; - Recursion::recursiveCounter@14 (line 16)
0x0000025345d31635: cmp edx,2h
0x0000025345d31638: je 25345d3166ch ;*ifne {reexecute=0 rethrow=0 return_oop=0}
; - Recursion::recursiveCounter@1 (line 16)
; - Recursion::recursiveCounter@14 (line 16)
; - Recursion::recursiveCounter@14 (line 16)
0x0000025345d3163a: cmp edx,3h
0x0000025345d3163d: je 25345d31674h ;*ifne {reexecute=0 rethrow=0 return_oop=0}
; - Recursion::recursiveCounter@1 (line 16)
; - Recursion::recursiveCounter@14 (line 16)
; - Recursion::recursiveCounter@14 (line 16)
; - Recursion::recursiveCounter@14 (line 16)
0x0000025345d3163f: cmp edx,4h
0x0000025345d31642: je 25345d3167ch ;*ifne {reexecute=0 rethrow=0 return_oop=0}
; - Recursion::recursiveCounter@1 (line 16)
; - Recursion::recursiveCounter@14 (line 16)
; - Recursion::recursiveCounter@14 (line 16)
; - Recursion::recursiveCounter@14 (line 16)
; - Recursion::recursiveCounter@14 (line 16)
0x0000025345d31644: add r8d,5h ;*iadd {reexecute=0 rethrow=0 return_oop=0}
; - Recursion::recursiveCounter@13 (line 16)
; - Recursion::recursiveCounter@14 (line 16)
; - Recursion::recursiveCounter@14 (line 16)
; - Recursion::recursiveCounter@14 (line 16)
; - Recursion::recursiveCounter@14 (line 16)
0x0000025345d31648: add edx,0fffffffbh
0x0000025345d3164b: call 25345d31620h ; ImmutableOopMap {}
;*invokestatic recursiveCounter {reexecute=0 rethrow=0 return_oop=0}
; - Recursion::recursiveCounter@14 (line 16)
; - Recursion::recursiveCounter@14 (line 16)
; - Recursion::recursiveCounter@14 (line 16)
; - Recursion::recursiveCounter@14 (line 16)
; - Recursion::recursiveCounter@14 (line 16)
; {static_call}
0x0000025345d31650: add rsp,10h
0x0000025345d31654: pop rbp
0x0000025345d31655: mov r10,qword ptr [r15+110h]
0x0000025345d3165c: test dword ptr [r10],eax ; {poll_return}
0x0000025345d3165f: ret
0x0000025345d31660: mov eax,r8d
0x0000025345d31663: jmp 25345d31650h
0x0000025345d31665: mov eax,r8d
0x0000025345d31668: inc eax ;*iadd {reexecute=0 rethrow=0 return_oop=0}
; - Recursion::recursiveCounter@13 (line 16)
0x0000025345d3166a: jmp 25345d31650h
0x0000025345d3166c: mov eax,r8d
0x0000025345d3166f: add eax,2h ;*iadd {reexecute=0 rethrow=0 return_oop=0}
; - Recursion::recursiveCounter@13 (line 16)
; - Recursion::recursiveCounter@14 (line 16)
0x0000025345d31672: jmp 25345d31650h
0x0000025345d31674: mov eax,r8d
0x0000025345d31677: add eax,3h ;*iadd {reexecute=0 rethrow=0 return_oop=0}
; - Recursion::recursiveCounter@13 (line 16)
; - Recursion::recursiveCounter@14 (line 16)
; - Recursion::recursiveCounter@14 (line 16)
0x0000025345d3167a: jmp 25345d31650h
0x0000025345d3167c: mov eax,r8d
0x0000025345d3167f: add eax,4h ;*iadd {reexecute=0 rethrow=0 return_oop=0}
; - Recursion::recursiveCounter@13 (line 16)
; - Recursion::recursiveCounter@14 (line 16)
; - Recursion::recursiveCounter@14 (line 16)
; - Recursion::recursiveCounter@14 (line 16)
0x0000025345d31682: jmp 25345d31650h ;*invokestatic recursiveCounter {reexecute=0 rethrow=0 return_oop=0}
; - Recursion::recursiveCounter@14 (line 16)
; - Recursion::recursiveCounter@14 (line 16)
; - Recursion::recursiveCounter@14 (line 16)
; - Recursion::recursiveCounter@14 (line 16)
; - Recursion::recursiveCounter@14 (line 16)
0x0000025345d31684: mov rdx,rax
0x0000025345d31687: add rsp,10h
0x0000025345d3168b: pop rbp
0x0000025345d3168c: jmp 2533e364d00h ;*ireturn {reexecute=0 rethrow=0 return_oop=0}
; - Recursion::recursiveCounter@17 (line 16)
; - Recursion::recursiveCounter@14 (line 16)
; {runtime_call _rethrow_Java}
我们现在可以看到，编译后的代码已经学会了一次最多加五个。该应用程序还将打印更大的嵌套调用限制。指令后面的注释表明，关于嵌套调用的元信息仍然存在，即使没有与调用级别相关联的单独指令。这意味着仍然可以构建代表整个原始调用链的堆栈跟踪。
当然，这和实际的尾调用优化是不一样的。无论我们设置多高的限制，它仍然内联有限数量的调用，并且已经认识到将限制设置得太高会产生不合理的代码大小。
因此，对于“Java JIT 是否曾经优化掉递归方法调用”这个字面问题的答案？是“是的，确实如此”。但不是整个递归而是有限数量的调用，换句话说，不是尾调用优化的形式。
于 2021-12-21T15:34:23.987 回答