JIT编译器推导求余%上下界引发的一连串故事

C1 RCE对%的处理

HotSpot VM的C1有个RCE（Range Check Elimination，范围检查消除）优化，所谓范围检查消除，就是为了正确的抛出数组越界异常，虚拟机需要在数组访问的一些地方插入隐式的检查，但是这些检查会降低性能，比如在循环中每次循环都得检查一次，所以HotSpot VM会想办法在可能的地方消除这些检查。我在看C1 RCE的时候发现目前它对求余符号的支持较为薄弱，它只能处理形如下面的代码：

arr[x%arr.length] // 只有除数是x.length的时候，才能应用RCE优化

如果余数是整数常量，它就不能工作了：

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

实际上，根据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-1和x%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如图所示：

JIT编译器推导求余%上下界引发的一连串故事-LMLPHP

左边的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。

kelthuzadx