8000 Merge pull request #5175 from sjrd/long-mul-hi · scala-wasm/scala-wasm@f73a8ae · GitHub
[go: up one dir, main page]
Skip to content

Commit f73a8ae

Browse files
gzm0gzm0
authored
Merge pull request scala-js#5175 from sjrd/long-mul-hi
Implement jl.Math.{multiplyFull, multiplyHigh, unsignedMultiplyHigh}.
2 parents 4c11983 + 4c128da commit f73a8ae

File tree

12 files changed

+501
-5
lines changed

12 files changed

+501
-5
lines changed

‎javalib/src/main/scala/java/lang/Math.scala

Lines changed: 37 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -462,6 +462,43 @@ object Math {
462462
if (a >= Integer.MIN_VALUE && a <= Integer.MAX_VALUE) a.toInt
463463
else throw new ArithmeticException("Integer overflow")
464464

465+
// RuntimeLong intrinsic
466+
@inline
467+
def multiplyFull(x: scala.Int, y: scala.Int): scala.Long =
468+
x.toLong * y.toLong
469+
470+
@inline
471+
def multiplyHigh(x: scala.Long, y: scala.Long): scala.Long = {
472+
/* Hacker's Delight, Section 8-2, Figure 8-2,
473+
* where we have "inlined" all the variables used only once to help our
474+
* optimizer perform simplifications.
475+
*/
476+
477+
val x0 = x & 0xffffffffL
478+
val x1 = x >> 32
479+
val y0 = y & 0xffffffffL
480+
val y1 = y >> 32
481+
482+
val t = x1 * y0 + ((x0 * y0) >>> 32)
483+
x1 * y1 + (t >> 32) + (((t & 0xffffffffL) + x0 * y1) >> 32)
484+
}
485+
486+
@inline
487+
def unsignedMultiplyHigh(x: scala.Long, y: scala.Long): scala.Long = {
488+
/* Hacker's Delight, Section 8-2:
489+
* > For an unsigned version, simply change all the int declarations to unsigned.
490+
* In Scala, that means changing all the >> into >>>.
491+
*/
492+
493+
val x0 = x & 0xffffffffL
494+
val x1 = x >>> 32
495+
val y0 = y & 0xffffffffL
496+
val y1 = y >>> 32
497+
498+
val t = x1 * y0 + ((x0 * y0) >>> 32)
499+
x1 * y1 + (t >>> 32) + (((t & 0xffffffffL) + x0 * y1) >>> 32)
500+
}
501+
465502
def floorDiv(a: scala.Int, b: scala.Int): scala.Int = {
466503
val quot = a / b
467504
if ((a < 0) == (b < 0) || quot * b == a) quot

‎linker-private-library/src/main/scala/org/scalajs/linker/runtime/RuntimeLong.scala

Lines changed: 41 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -767,6 +767,47 @@ object RuntimeLong {
767767
}
768768
}
769769

770+
/** Intrinsic for Math.multiplyFull.
771+
*
772+
* Compared to the regular expansion of `x.toLong * y.toLong`, this
773+
* intrinsic avoids 2 int multiplications.
774+
*/
775+
@inline
776+
def multiplyFull(a: Int, b: Int): RuntimeLong = {
777+
/* We use Hacker's Delight, Section 8-2, Figure 8-2, to compute the hi
778+
* word of the result. We reuse intermediate products to compute the lo
779+
* word, like we do in `RuntimeLong.*`.
780+
*
781+
* We swap the role of a1b0 and a0b1 compared to Hacker's Delight, to
782+
* optimize for the case where a1b0 collapses to 0, like we do in
783+
* `RuntimeLong.*`. The optimizer normalizes constants in multiplyFull to
784+
* be on the left-hand-side (when it cannot do constant-folding to begin
785+
* with). Therefore, `b` is never constant in practice.
786+
*/
787+
788+
val a0 = a & 0xffff
789+
val a1 = a >> 16
790+
val b0 = b & 0xffff
791+
val b1 = b >> 16
792+ F438
793+
val a0b0 = a0 * b0
794+
val a1b0 = a1 * b0 // collapses to 0 when a is constant and 0 <= a <= 0xffff
795+
val a0b1 = a0 * b1
796+
797+
/* lo = a * b, but we compute the above 3 subproducts for hi anyway,
798+
* so we reuse them to compute lo too, trading a * for 2 +'s and 1 <<.
799+
*/
800+
val lo = a0b0 + ((a1b0 + a0b1) << 16)
801+
802+
val t = a0b1 + (a0b0 >>> 16)
803+
val hi = {
804+
a1 * b1 + (t >> 16) +
805+
(((t & 0xffff) + a1b0) >> 16) // collapses to 0 when a1b0 = 0
806+
}
807+
808+
new RuntimeLong(lo, hi)
809+
}
810+
770811
@inline
771812
def divide(a: RuntimeLong, b: RuntimeLong): RuntimeLong = {
772813
val lo = divideImpl(a.lo, a.hi, b.lo, b.hi)

‎linker/shared/src/main/scala/org/scalajs/linker/backend/emitter/LongImpl.scala

Lines changed: 7 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -116,6 +116,13 @@ private[linker] object LongImpl {
116116
val AllModuleMethods = Set(
117117
fromInt, fromDouble, fromDoubleBits)
118118

119+
// Methods on the companion used for intrinsics
120+
121+
final val multiplyFull = MethodName("multiplyFull", List(IntRef, IntRef), RTLongRef)
122+
123+
val AllIntrinsicModuleMethods = Set(
124+
multiplyFull)
125+
119126
// Extract the parts to give to the initFromParts constructor
120127

121128
def extractParts(value: Long): (Int, Int) =

‎linker/shared/src/main/scala/org/scalajs/linker/frontend/optimizer/IncOptimizer.scala

Lines changed: 4 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -75,7 +75,10 @@ final class IncOptimizer private[optimizer] (config: CommonPhaseConfig, collOps:
7575
multiple(
7676
cond(!targetIsWebAssembly && !esFeatures.allowBigIntsForLongs) {
7777
// Required by the intrinsics manipulating Longs
78-
callMethods(LongImpl.RuntimeLongClass, LongImpl.AllIntrinsicMethods.toList)
78+
multiple(
79+
callMethods(LongImpl.RuntimeLongClass, LongImpl.AllIntrinsicMethods.toList),
80+
callMethods(LongImpl.RuntimeLongModuleClass, LongImpl.AllIntrinsicModuleMethods.toList)
81+
)
7982
},
8083
cond(targetIsWebAssembly) {
8184
// Required by the intrinsic CharacterCodePointToString

‎linker/shared/src/main/scala/org/scalajs/linker/frontend/optimizer/OptimizerCore.scala

Lines changed: 39 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -2993,6 +2993,32 @@ private[optimizer] abstract class OptimizerCore(
29932993
case MathMaxDouble =>
29942994
contTree(wasmBinaryOp(WasmBinaryOp.F64Max, targs.head, targs.tail.head))
29952995

2996+
case MathMultiplyFull =>
2997+
def expand(targs: List[PreTransform]): TailRec[Tree] = {
2998+
import LongImpl.{RuntimeLongModuleClass => modCls}
2999+
val receiver =
3000+
makeCast(LoadModule(modCls), ClassType(modCls, nullable = false)).toPreTransform
3001+
3002+
pretransformApply(ApplyFlags.empty,
3003+
receiver,
3004+
MethodIdent(LongImpl.multiplyFull),
3005+
targs,
3006+
ClassType(LongImpl.RuntimeLongClass, nullable = true),
3007+
isStat, usePreTransform)(
3008+
cont)
3009+
}
3010+
3011+
targs match {
3012+
case List(PreTransLit(IntLiteral(x)), PreTransLit(IntLiteral(y))) =>
3013+
// cannot actually call multiplyHigh to constant-fold because it is JDK9+
3014+
contTree(LongLiteral(x.toLong * y.toLong))
3015+
case List(tlhs, trhs @ PreTransLit(_)) =>
3016+
// normalize a single constant on the left; the implementation is optimized for that case
3017+
expand(trhs :: tlhs :: Nil)
3018+
case _ =>
3019+
expand(targs)
3020+
}
3021+
29963022
// scala.collection.mutable.ArrayBuilder
29973023

29983024
case GenericArrayBuilderResult =>
@@ -4374,6 +4400,14 @@ private[optimizer] abstract class OptimizerCore(
43744400
PreTransLit(IntLiteral(_))) if (y & 31) != 0 =>
43754401
foldBinaryOp(Int_>>>, lhs, rhs)
43764402

4403+
case (PreTransBinaryOp(op @ (Int_| | Int_& | Int_^),
4404+
PreTransLit(IntLiteral(x)), y),
4405+
z @ PreTransLit(IntLiteral(zValue))) =>
4406+
foldBinaryOp(
4407+
op,
4408+
PreTransLit(IntLiteral(x >> zValue)),
4409+
foldBinaryOp(Int_>>, y, z))
4410+
43774411
case (_, PreTransLit(IntLiteral(y))) =>
43784412
val dist = y & 31
43794413
if (dist == 0)
@@ -6518,8 +6552,9 @@ private[optimizer] object OptimizerCore {
65186552
final val MathMinDouble = MathMinFloat + 1
65196553
final val MathMaxFloat = MathMinDouble + 1
65206554
final val MathMaxDouble = MathMaxFloat + 1
6555+
final val MathMultiplyFull = MathMaxDouble + 1
65216556

6522-
final val ArrayBuilderZeroOf = MathMaxDouble + 1
6557+
final val ArrayBuilderZeroOf = MathMultiplyFull + 1
65236558
final val GenericArrayBuilderResult = ArrayBuilderZeroOf + 1
65246559

65256560
final val ClassGetName = GenericArrayBuilderResult + 1
@@ -6611,6 +6646,9 @@ private[optimizer] object OptimizerCore {
66116646
ClassName("java.lang.Long$") -> List(
66126647
m("toString", List(J), ClassRef(BoxedStringClass)) -> LongToString,
66136648
m("compare", List(J, J), I) -> LongCompare
6649+
),
6650+
ClassName("java.lang.Math$") -> List(
6651+
m("multiplyFull", List(I, I), J) -> MathMultiplyFull
66146652
)
66156653
)
66166654

‎project/Build.scala

Lines changed: 0 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -2138,7 +2138,6 @@ object Build {
21382138
List(sharedTestDir / "scala", sharedTestDir / "require-scala2") :::
21392139
collectionsEraDependentDirectory(scalaV, sharedTestDir) ::
21402140
includeIf(sharedTestDir / "require-jdk11", javaV >= 11) :::
2141-
includeIf(sharedTestDir / "require-jdk15", javaV >= 15) :::
21422141
includeIf(sharedTestDir / "require-jdk17", javaV >= 17) :::
21432142
includeIf(sharedTestDir / "require-jdk21", javaV >= 21) :::
21442143
includeIf(testDir / "require-scala2", isJSTest)

0 commit comments

Comments
 (0)
0