Graal: Optimize divisions by constant using multiplication with shifts

[plokhotnyuk]

Currently, only constants which are pow of 2 are optimized to shifts: https://github.com/oracle/graal/blob/079591ab18a5694a8ba5cf630ed4f76d3442fe21/compiler/src/org.graalvm.compiler.nodes/src/org/graalvm/compiler/nodes/calc/SignedDivNode.java#L120

Could it be improved to use imul and shr/sub/add operations for _any_ constant divisor, like it is done by C++ compilers in the following example for 64-bit division by 10? https://godbolt.org/g/DUcz25

[plokhotnyuk]

Moreover, comparing to OpenJDK 8/11 it looks more like regression and affects lot of routines which converts numbers or date-time stamps to textual representation, starting from standard toString and ending by advanced itoa, dtoa routines which encourage fast division by constants:

https://github.com/FasterXML/jackson-core/blob/fa64390b1bd5f1435daa9d2b17a58594cfb22817/src/main/java/com/fasterxml/jackson/core/io/NumberOutput.java#L157

https://github.com/ngs-doo/dsl-json/blob/master/library/src/main/java/com/dslplatform/json/NumberConverter.java#L1036

https://github.com/ulfjack/ryu/blob/master/src/main/java/info/adams/ryu/RyuDouble.java#L261

[dougxc]

Hi @plokhotnyuk , thanks for pointing this out. We will consider adding this optimization to Graal.

[plokhotnyuk]

Division by Invariant Integers Using Multiplication (1994)
by Torbjörn Granlund , Peter L. Montgomery

[mur47x111]

Should be resolved by https://github.com/oracle/graal/pull/896

[plokhotnyuk]

Thank you all for fixing it!

I am waiting a new release of GraalVM with impatience!