Basic remainder operations are incredibly complicated

[chrisseaton]

def foo(a, b)
  a % b
end

loop do
  foo(rand(10), 1 + rand(10))
end

                                ;Comment 95:    12 stack:28|DWORD = MOVE r11|DWORD moveKind: DWORD
        0x128a606ff:    mov     dword ptr [rsp + 0x14], r11d
                                ;Comment 100:   14 TESTBRANCH (x: r11|DWORD, y: r11|DWORD) trueDestinationProbability: 0.0 condition: = trueDestination: B0 -> B1 falseDestination: B0 -> B2 size: DWORD
        0x128a60704:    test    r11d, r11d
        0x128a60707:    je      0x128a60888
                                ;Comment 109:   block B2 null
                                ;Comment 109:   24 [] = LABEL numbPhis: 0 align: false label: ?
                                ;Comment 109:   26 r8|DWORD[.] = MOV [r10|QWORD[.] + 44] size: DWORD
        0x128a6070d:    mov     r8d, dword ptr [r10 + 0x2c]
                                ;Comment 113:   28 r9|DWORD = MOV [r8|DWORD[.] * 8 + 12] size: DWORD
        0x128a60711:    mov     r9d, dword ptr [r8*8 + 0xc]
                                ;Comment 121:   30 rax|DWORD = MOVE r9|DWORD moveKind: DWORD
        0x128a60719:    mov     eax, r9d
                                ;Comment 124:   32 (highResult: rdx|DWORD, lowResult: rax|DWORD) = CDQ rax|DWORD size: DWORD
        0x128a6071c:    cdq
                                ;Comment 125:   34 (highResult: rdx|DWORD, lowResult: rax|DWORD) = IDIV (highX: rdx|DWORD, lowX: rax|DWORD, y: r11|DWORD) size: DWORD state [bci:0]
                                ;Comment 125 [rsi:0, r8:0, r10:0]at org.graalvm.compiler.truffle.runtime.OptimizedCallTarget.profiledPERoot(OptimizedCallTarget.java:615) [bci: 0, duringCall: false, rethrow: false]
                                ;            |0                                             |1             |2  |3 
                                ;   locals:  |Object[HotSpotOptimizedCallTarget@974543298]  |r10|QWORD[.]  |-  |- 
                                ;Comment 125:   {infopoint: IMPLICIT_EXCEPTION}
        0x128a6071d:    idiv    r11d
                                ;Comment 128:   36 rax|DWORD = ADD (x: rdx|DWORD, y: r11|DWORD) size: DWORD
        0x128a60720:    mov     eax, edx
        0x128a60722:    add     eax, r11d
                                ;Comment 133:   38 TESTBRANCH (x: rdx|DWORD, y: rdx|DWORD) trueDestinationProbability: 0.5 condition: < trueDestination: B2 -> B3 falseDestination: B2 -> B7 size: DWORD
        0x128a60725:    test    edx, edx
        0x128a60727:    jl      0x128a6080a
                                ;Comment 141:   block B7 null
                                ;Comment 141:   58 [] = LABEL numbPhis: 0 align: false label: ?
                                ;Comment 141:   60 CMPCONSTBRANCH rdx|DWORD trueDestinationProbability: 0.5 condition: < trueDestination: B7 -> B8 falseDestination: B7 -> B9 y: 1 size: DWORD inlinedY: null
        0x128a6072d:    cmp     edx, 1
        0x128a60730:    jl      0x128a60835
                                ;Comment 150:   block B9 null
                                ;Comment 150:   68 [] = LABEL numbPhis: 0 align: false label: ?
                                ;Comment 150:   70 TESTBRANCH (x: r11|DWORD, y: r11|DWORD) trueDestinationProbability: 0.5 condition: < trueDestination: B9 -> B10 falseDestination: B9 -> B11 size: DWORD
        0x128a60736:    test    r11d, r11d
        0x128a60739:    jl      0x128a6083c
                                ;Comment 159:   block B11 null
                                ;Comment 159:   78 [] = LABEL numbPhis: 0 align: false label: ?
                                ;Comment 159:   80 rcx|DWORD = MOVE rdx|DWORD moveKind: DWORD

Relates to oracle/graal#3866 but that's a small part of the problem.

[chrisseaton]

Maybe if we try a super-optimizer there's some sequence of instructions that does this more simply?

[rubyFeedback]

Off topic but ... how did you create that nifty image? That looks really nice.

[chrisseaton]

Thanks it's Seafoam. For example https://chrisseaton.com/truffleruby/basic-truffle-graphs/.

[eregon]

"incredibly complicated" as in it's two branches + the actual native modulo.
The native modulo is idiv, i.e., it's not cheaper than division and so I guess that would take most of the time.

Typically the RHS of a modulo would be constant and then it's just one guard:

We could add a specialization that guards both operands are positive, then that would be the only guards and no If, that's easy. Or just a guard that the RHS is positive, which I think is the case 99% of the time or so.

I wonder if amd64 or/and aarch64 have a modulo with Ruby semantics?

Or maybe Java has a method under Math which has those semantics and might be intrinsified?
Maybe Math.floorMod, see https://en.wikipedia.org/wiki/Modulo_operation#In_programming_languages

There is already a specialization if the the RHS is a power of two, together with constant RHS I think that's the most important to optimize.

[eregon]

FWIW here is the logic in CRuby: https://github.com/ruby/ruby/blob/ae5dffd66652752e3a7dfb3a6befa1df6cac7c74/internal/fixnum.h#L136-L138
The condition is a tiny bit simpler as it's a ternary on RHS > 0 (RHS = 0 already raises ArithmeticException before reaching the condition).