JITc语言编译器计算求余%上末地引起的一连串小故事

C1 RCE对%的解决

HotSpot VM的C1有一个RCE(Range Check Elimination,范畴查验清除)提升,说白了范畴查验清除,便是为了更好地恰当的抛出去数组越界出现异常,vm虚拟机必须在二维数组浏览的一些地区插进隐式的查验,可是这种查验会减少特性,例如在循环系统中每一次循环系统都得查验一次,因此HotSpot VM会想办法在很有可能的地区清除这种查验。我还在看C1 RCE的情况下发觉现阶段它对求余标记的适用比较欠缺,它只有解决形如下边的编码:

arr[x%arr.length] // 仅有除数是x.length的情况下,才可以运用RCE提升

假如余数是整数金额变量定义,它就不可以工作中了:

arr[x%3]
for(int i=0;i<10;i  ){
  arr[x]
}

事实上,依据JLS的界定,我们知道假如除数为整数金额变量定义(且等于零,由于0做为除数会抛出去运作时出现异常),是能够计算出結果的上末地的(也在于被除数的正负极),标准以下:

  • x % -y ==> [0, y - 1]
  • x % y ==> [0, y - 1]
  • -x % y ==> [-y 1, 0]
  • -x % -y ==> [-y 1, 0]

因此,我给JDK发过个patch,这个问题算作解决了。可是Nils提及,C2是不是有同样的提升呢?后边Tobias帮助确定了一下C2沒有,我再之后也进一步确定了,因此下一步是调查C2是不是能运用一样的提升。

调查为C2运用一样的提升

原本认为是较为trivial的事儿,为求余连接点的种类系统软件天赋加点编码,计算一下上末地就可以,事实上因为我那么做的,可是最终发觉那样沒有清除上末地。默认设置打开-XX: GenerateRangeChecks后,在二维数组浏览全过程中(Parse::array_addressing),C2依然转化成了范畴查验。

调节后发觉计算上末地压根沒有实行,由于C2建立完求余连接点后,会实行一个IGVN的全过程,即迭代更新的运用多种多样提升,在其中就包含理想,C2理想就是指运用许多 部分小提升的全过程,在这个事例中便是独特解决形如x%2^n,x%2^n-1x%1的状况,假如除数是整数金额变量定义,它还会继续应用一个来源于https://book.douban.com/subject/1784887/书里边的优化算法,即Division by Invariant Integers using Multiplication(by Granlund and Montgomery),搜过一下知乎问答有相近的文章内容,要想掌握关键点能够读一读https://zhuanlan.zhihu.com/p/151038723。知道缘故,因此我改了下编码,严禁了求余连接点的理想,想着这总就行了吧。

或是不好

是的,或是不好。虽然我已经严禁了对求余标记的理想提升,可是范畴查验或是转化成了。。。我又继续看编码,发觉除开理想的这一提升以外,C2在IR(正中间表明)结构的全过程中又 又 又 又 又对求余运算干了个提升!假如除数是整数变量定义,且是2^n,那麼C2会对它开展形变,IR如下图所示:

左侧的IR是 IR结构的情况下C2做的提升后的实际效果,右侧是理想提升后的实际效果。事实上他们做的事儿自身是较为反复的,并且历经检测发觉,理想提升的优化算法好些于IR结构全过程中的提升:

一个简易的micro benchmark:

public class ModPowerOf2 {
    @Benchmark
    public int testPositivePowerOf2() {
        int sum = 0;
        for (int i = 0; i < 1000; i  ) {
            sum  = i % 1;
            sum  = i % 2;
            sum  = i % 4;
            sum  = i % 8;
            sum  = i % 16;
            sum  = i % 32;
            sum  = i % 64;
            sum  = i % 128;
            sum  = i % 256;
            sum  = i % 512;
            sum  = i % 1024;
            sum  = i % 2048;
            sum  = i % 4096;
            sum  = i % 8192;
            sum  = i % 16384;
            sum  = i % 32768;
            sum  = i % 65536;
        }
        return sum;
    }

    @Benchmark
    public int testNegativePowerOf2() {
        int sum = 0;
        for (int i = 0; i < 1000; i  ) {
            sum  = i % -1;
            sum  = i % -2;
            sum  = i % -4;
            sum  = i % -8;
            sum  = i % -16;
            sum  = i % -32;
            sum  = i % -64;
            sum  = i % -128;
            sum  = i % -256;
            sum  = i % -512;
            sum  = i % -1024;
            sum  = i % -2048;
            sum  = i % -4096;
            sum  = i % -8192;
            sum  = i % -16384;
            sum  = i % -32768;
            sum  = i % -65536;
        }
        return sum;
    }
}

理想:

Benchmark Mode Cnt Score Error Units
ModPowerOf2.testNegativePowerOf2 avgt 25 8746.608 ± 139.777 ns/op
ModPowerOf2.testPositivePowerOf2 avgt 25 8735.545 ± 86.145 ns/op

IR结构提升:

Benchmark Mode Cnt Score Error Units
ModPowerOf2.testNegativePowerOf2 avgt 25 8693.797 ± 7.844 ns/op
ModPowerOf2.testPositivePowerOf2 avgt 25 6618.652 ± 1.739 ns/op

所以我提了个patch,提前准备清除IR结构做的提升来处理这个问题。

总结

我觉得为求余连接点计算上末地也是更有意义的,假如之后有别的提升会形变为求余运算,那麼他们能够运用这一计算,另外,为求余做统一健全的种类计算这件事情自身也是恰当的,因此我又提了个patch。能够见到,最后我只清除了C1 arr[x%4]的范畴查验,或是没能清除C2 arr[x%4]的范畴查验,是否之后可以说C1有的地区做的比C2好啦(狗头hh。

评论(0条)

刀客源码 游客评论