8000 Introduce IR BinaryOps for unsigned division and remainder. · scala-js/scala-js@862ae3e · GitHub
[go: up one dir, main page]
Skip to content

Commit 862ae3e

Browse files
sjrdsjrd
committed
Introduce IR BinaryOps for unsigned division and remainder.
This allows to better mutualize their implementation with the signed divisions. Moreover, our 3 implementation strategies (JS with `RuntimeLong`, JS with `bigint` and Wasm) have different efficient implementations of those operations. Using IR BinaryOps for them allows each backend to use the most appropriate implementation, while letting the optimizer generically manipulate their mathematical properties.
1 parent 46962c5 commit 862ae3e

File tree

18 files changed

+226
-252
l 8000 ines changed

18 files changed

+226
-252
lines changed

‎compiler/src/main/scala/org/scalajs/nscplugin/GenJSCode.scala

Lines changed: 9 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -7411,14 +7411,22 @@ private object GenJSCode {
74117411
private lazy val JavalibMethodsWithOpBody: Map[(ClassName, MethodName), JavalibOpBody] = {
74127412
import JavalibOpBody._
74137413
import js.{UnaryOp => unop, BinaryOp => binop}
7414-
import jstpe.{BooleanRef => Z, CharRef => C, IntRef => I}
7414+
import jstpe.{BooleanRef => Z, CharRef => C, IntRef => I, LongRef => J}
74157415
import MethodName.{apply => m}
74167416

74177417
val O = jswkn.ObjectRef
74187418
val CC = jstpe.ClassRef(jswkn.ClassClass)
74197419
val T = jstpe.ClassRef(jswkn.BoxedStringClass)
74207420

74217421
val byClass: Map[ClassName, Map[MethodName, JavalibOpBody]] = Map(
7422+
jswkn.BoxedIntegerClass.withSuffix("$") -> Map(
7423+
m("divideUnsigned", List(I, I), I) -> ArgBinaryOp(binop.Int_unsigned_/),
7424+
m("remainderUnsigned", List(I, I), I) -> ArgBinaryOp(binop.Int_unsigned_%),
7425+
),
7426+
jswkn.BoxedLongClass.withSuffix("$") -> Map(
7427+
m("divideUnsigned", List(J, J), J) -> ArgBinaryOp(binop.Long_unsigned_/),
7428+
m("remainderUnsigned", List(J, J), J) -> ArgBinaryOp(binop.Long_unsigned_%),
7429+
),
74227430
jswkn.BoxedStringClass -> Map(
74237431
m("length", Nil, I) -> ThisUnaryOp(unop.String_length),
74247432
m("charAt", List(I), C) -> ThisBinaryOp(binop.String_charAt)

‎ir/shared/src/main/scala/org/scalajs/ir/Printers.scala

Lines changed: 5 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -571,6 +571,11 @@ object Printers {
571571
case Double_<= => "<=[double]"
572572
case Double_> => ">[double]"
573573
case Double_>= => ">=[double]"
574+
575+
case Int_unsigned_/ => "unsigned_/[int]"
576+
case Int_unsigned_% => "unsigned_%[int]"
577+
case Long_unsigned_/ => "unsigned_/[long]"
578+
case Long_unsigned_% => "unsigned_%[long]"
574579
})
575580
print(' ')
576581
print(rhs)

‎ir/shared/src/main/scala/org/scalajs/ir/Trees.scala

Lines changed: 10 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -671,6 +671,12 @@ object Trees {
671671
final val Class_cast = 61
672672
final val Class_newArray = 62
673673

674+
// New in 1.20
675+
final val Int_unsigned_/ = 63
676+
final val Int_unsigned_% = 64
677+
final val Long_unsigned_/ = 65
678+
final val Long_unsigned_% = 66
679+
674680
def isClassOp(op: Code): Boolean =
675681
op >= Class_isInstance && op <= Class_newArray
676682

@@ -685,10 +691,12 @@ object Trees {
685691
case String_+ =>
686692
StringType
687693
case Int_+ | Int_- | Int_* | Int_/ | Int_% |
688-
Int_| | Int_& | Int_^ | Int_<< | Int_>>> | Int_>> =>
694+
Int_| | Int_& | Int_^ | Int_<< | Int_>>> | Int_>> |
695+
Int_unsigned_/ | Int_unsigned_% =>
689696
IntType
690697
case Long_+ | Long_- | Long_* | Long_/ | Long_% |
691-
Long_| | Long_& | Long_^ | Long_<< | Long_>>> | Long_>> =>
698+
Long_| | Long_& | Long_^ | Long_<< | Long_>>> | Long_>> |
699+
Long_unsigned_/ | Long_unsigned_% =>
692700
LongType
693701
case Float_+ | Float_- | Float_* | Float_/ | Float_% =>
694702
FloatType

‎ir/shared/src/test/scala/org/scalajs/ir/PrintersTest.scala

Lines changed: 9 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -666,6 +666,15 @@ class PrintersTest {
666666
BinaryOp(Class_isAssignableFrom, classVarRef, ref("y", ClassType(ClassClass, nullable = false))))
667667
assertPrintEquals("cast(x, y)", BinaryOp(Class_cast, classVarRef, ref("y", AnyType)))
668668
assertPrintEquals("newArray(x, y)", BinaryOp(Class_newArray, classVarRef, ref("y", IntType)))
669+
670+
assertPrintEquals("(x unsigned_/[int] y)",
671+
BinaryOp(Int_unsigned_/, ref("x", IntType), ref("y", IntType)))
672+
assertPrintEquals("(x unsigned_%[int] y)",
673+
BinaryOp(Int_unsigned_%, ref("x", IntType), ref("y", IntType)))
674+
assertPrintEquals("(x unsigned_/[long] y)",
675+
BinaryOp(Long_unsigned_/, ref("x", LongType), ref("y", LongType)))
676+
assertPrintEquals("(x unsigned_%[long] y)",
677+
BinaryOp(Long_unsigned_%, ref("x", LongType), ref("y", LongType)))
669678
}
670679

671680
@Test def printNewArray(): Unit = {

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

Lines changed: 2 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -221,15 +221,11 @@ object Integer {
221221
(((t2 + (t2 >> 4)) & 0xF0F0F0F) * 0x1010101) >> 24
222222
}
223223

224-
// Wasm intrinsic
225224
@inline def divideUnsigned(dividend: Int, divisor: Int): Int =
226-
if (divisor == 0) 0 / 0
227-
else asInt(asUint(dividend) / asUint(divisor))
225+
throw new Error("stub") // body replaced by the compiler back-end
228226

229-
// Wasm intrinsic
230227
@inline def remainderUnsigned(dividend: Int, divisor: Int): Int =
231-
if (divisor == 0) 0 % 0
232-
else asInt(asUint(dividend) % asUint(divisor))
228+
throw new Error("stub") // body replaced by the compiler back-end
233229

234230
@inline def highestOneBit(i: Int): Int = {
235231
/* The natural way of implementing this is:

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

Lines changed: 4 additions & 40 deletions
Original file line numberDiff line numberDiff line change
@@ -348,47 +348,11 @@ object Long {
348348
@inline def compareUnsigned(x: scala.Long, y: scala.Long): scala.Int =
349349
compare(x ^ SignBit, y ^ SignBit)
350350

351-
// Intrinsic, except for JS when using bigint's for longs
352-
def divideUnsigned(dividend: scala.Long, divisor: scala.Long): scala.Long =
353-
divModUnsigned(dividend, divisor, isDivide = true)
354-
355-
// Intrinsic, except for JS when using bigint's for longs
356-
def remainderUnsigned(dividend: scala.Long, divisor: scala.Long): scala.Long =
357-
divModUnsigned(dividend, divisor, isDivide = false)
358-
359-
private def divModUnsigned(a: scala.Long, b: scala.Long,
360-
isDivide: scala.Boolean): scala.Long = {
361-
/* This is a much simplified (and slow) version of
362-
* RuntimeLong.unsignedDivModHelper.
363-
*/
364-
365-
if (b == 0L)
366-
throw new ArithmeticException("/ by zero")
367-
368-
var shift = numberOfLeadingZeros(b) - numberOfLeadingZeros(a)
369-
var bShift = b << shift
370-
371-
var rem = a
372-
var quot = 0L
373-
374-
/* Invariants:
375-
* bShift == b << shift == b * 2^shift
376-
* quot >= 0
377-
* 0 <= rem < 2 * bShift
378-
* quot * b + rem == a
379-
*/
380-
while (shift >= 0 && rem != 0) {
381-
if ((rem ^ SignBit) >= (bShift ^ SignBit)) {
382-
rem -= bShift
383-
quot |= (1L << shift)
384-
}
385-
shift -= 1
386-
bShift >>>= 1
387-
}
351+
@inline def divideUnsigned(dividend: scala.Long, divisor: scala.Long): scala.Long =
352+
throw new Error("stub") // body replaced by the compiler back-end
388353

389-
if (isDivide) quot
390-
else rem
391-
}
354+
@inline def remainderUnsigned(dividend: scala.Long, divisor: scala.Long): scala.Long =
355+
throw new Error("stub") // body replaced by the compiler back-end
392356

393357
@inline
394358
def highestOneBit(i: scala.Long): scala.Long = {

‎linker/shared/src/main/scala/org/scalajs/linker/analyzer/Infos.scala

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -789,12 +789,12 @@ object Infos {
789789
import BinaryOp._
790790

791791
op match {
792-
case Int_/ | Int_% =>
792+
case Int_/ | Int_% | Int_unsigned_/ | Int_unsigned_% =>
793793
rhs match {
794794
case IntLiteral(r) if r != 0 =>
795795
case _ => builder.addUsedIntLongDivModByMaybeZero()
796796
}
797-
case Long_/ | Long_% =>
797+
case Long_/ | Long_% | Long_unsigned_/ | Long_unsigned_% =>
798798
rhs match {
799799
case LongLiteral(r) if r != 0L =>
800800
case _ => builder.addUsedIntLongDivModByMaybeZero()

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

Lines changed: 6 additions & 18 deletions
Original file line numberDiff line numberDiff line change
@@ -875,17 +875,11 @@ private[emitter] object CoreJSLib {
875875
Apply(genIdentBracketSelect(BigIntRef, "asIntN"), 64 :: tree :: Nil)
876876

877877
condDefs(shouldDefineIntLongDivModFunctions)(
878-
defineFunction2(VarField.intDiv) { (x, y) =>
878+
defineFunction1(VarField.checkIntDivisor) { y =>
879879
If(y === 0, throwDivByZero, {
880-
Return((x / y) | 0)
880+
Return(y)
881881
})
882-
} :::
883-
defineFunction2(VarField.intMod) { (x, y) =>
884-
If(y === 0, throwDivByZero, {
885-
Return((x % y) | 0)
886-
})
887-
} :::
888-
Nil
882+
}
889883
) :::
890884
defineFunction1(VarField.doubleToInt) { x =>
891885
Return(If(x > 2147483647, 2147483647, If(x < -2147483648, -2147483648, x | 0)))
@@ -909,17 +903,11 @@ private[emitter] object CoreJSLib {
909903
}
910904
) :::
911905
condDefs(allowBigIntsForLongs && shouldDefineIntLongDivModFunctions)(
912-
defineFunction2(VarField.longDiv) { (x, y) =>
906+
defineFunction1(VarField.checkLongDivisor) { y =>
913907
If(y === bigInt(0), throwDivByZero, {
914-
Return(wrapBigInt64(x / y))
908+
Return(y)
915909
})
916-
} :::
917-
defineFunction2(VarField.longMod) { (x, y) =>
918-
If(y === bigInt(0), throwDivByZero, {
919-
Return(wrapBigInt64(x % y))
920-
})
921-
} :::
922-
Nil
910+
}
923911
) :::
924912
condDefs(allowBigIntsForLongs)(
925913
defineFunction1(VarField.doubleToLong)(x => Return {

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

Lines changed: 34 additions & 32 deletions
Original file line numberDiff line numberDiff line change
@@ -1286,12 +1286,14 @@ private[emitter] class FunctionEmitter(sjsGen: SJSGen) {
12861286
allowSideEffects && test(lhs)
12871287

12881288
// Division and modulo, preserve pureness unless they can divide by 0
1289-
case BinaryOp(BinaryOp.Int_/ | BinaryOp.Int_%, lhs, rhs) if !allowSideEffects =>
1289+
case BinaryOp(BinaryOp.Int_/ | BinaryOp.Int_% | BinaryOp.Int_unsigned_/ | BinaryOp.Int_unsigned_%, lhs, rhs)
1290+
if !allowSideEffects =>
12901291
rhs match {
12911292
case IntLiteral(r) if r != 0 => test(lhs)
12921293
case _ => false
12931294
}
1294-
case BinaryOp(BinaryOp.Long_/ | BinaryOp.Long_%, lhs, rhs) if !allowSideEffects =>
1295+
case BinaryOp(BinaryOp.Long_/ | BinaryOp.Long_% | BinaryOp.Long_unsigned_/ | BinaryOp.Long_unsigned_%, lhs, rhs)
1296+
if !allowSideEffects =>
12951297
rhs match {
12961298
case LongLiteral(r) if r != 0L => test(lhs)
12971299
case _ => false
@@ -2205,6 +2207,9 @@ private[emitter] class FunctionEmitter(sjsGen: SJSGen) {
22052207
def or0(tree: js.Tree): js.Tree =
22062208
js.BinaryOp(JSBinaryOp.|, tree, js.IntLiteral(0))
22072209

2210+
def shr0(tree: js.Tree): js.Tree =
2211+
js.BinaryOp(JSBinaryOp.>>>, tree, js.IntLiteral(0))
2212+
22082213
def bigIntShiftRhs(tree: js.Tree): js.Tree = {
22092214
tree match {
22102215
case js.IntLiteral(v) =>
@@ -2620,20 +2625,17 @@ private[emitter] class FunctionEmitter(sjsGen: SJSGen) {
26202625
}
26212626
case Int_* =>
26222627
genCallPolyfillableBuiltin(ImulBuiltin, newLhs, newRhs)
2623-
case Int_/ =>
2624-
rhs match {
2625-
case IntLiteral(r) if r != 0 =>
2626-
or0(js.BinaryOp(JSBinaryOp./, newLhs, newRhs))
2627-
case _ =>
2628-
genCallHelper(VarField.intDiv, newLhs, newRhs)
2629-
}
2630-
case Int_% =>
2631-
rhs match {
2632-
case IntLiteral(r) if r != 0 =>
2633-
or0(js.BinaryOp(JSBinaryOp.%, newLhs, newRhs))
2634-
case _ =>
2635-
genCallHelper(VarField.intMod, newLhs, newRhs)
2628+
case Int_/ | Int_% | Int_unsigned_/ | Int_unsigned_% =>
2629+
val newRhs1 = rhs match {
2630+
case IntLiteral(r) if r != 0 => newRhs
2631+
case _ => genCallHelper(VarField.checkIntDivisor, newRhs)
26362632
}
2633+
or0((op: @switch) match {
2634+
case Int_/ => js.BinaryOp(JSBinaryOp./, newLhs, newRhs1)
2635+
case Int_% => js.BinaryOp(JSBinaryOp.%, newLhs, newRhs1)
2636+
case Int_unsigned_/ => js.BinaryOp(JSBinaryOp./, shr0(newLhs), shr0(newRhs1))
2637+
case Int_unsigned_% => js.BinaryOp(JSBinaryOp.%, shr0(newLhs), shr0(newRhs1))
2638+
})
26372639

26382640
case Int_| => js.BinaryOp(JSBinaryOp.|, newLhs, newRhs)
26392641
case Int_& => js.BinaryOp(JSBinaryOp.&, newLhs, newRhs)
@@ -2674,27 +2676,27 @@ private[emitter] class FunctionEmitter(sjsGen: SJSGen) {
26742676
wrapBigInt64(js.BinaryOp(JSBinaryOp.*, newLhs, newRhs))
26752677
else
26762678
genApply(newLhs, LongImpl.*, newRhs)
2677-
case Long_/ =>
2679+
case Long_/ | Long_% | Long_unsigned_/ | Long_unsigned_% =>
26782680
if (useBigIntForLongs) {
2679-
rhs match {
2680-
case LongLiteral(r) if r != 0L =>
2681-
wrapBigInt64(js.BinaryOp(JSBinaryOp./, newLhs, newRhs))
2682-
case _ =>
2683-
genCallHelper(VarField.longDiv, newLhs, newRhs)
2681+
val newRhs1 = rhs match {
2682+
case LongLiteral(r) if r != 0L => newRhs
2683+
case _ => genCallHelper(VarField.checkLongDivisor, newRhs)
26842684
}
2685+
wrapBigInt64((op: @switch) match {
2686+
case Long_/ => js.BinaryOp(JSBinaryOp./, newLhs, newRhs1)
2687+
case Long_% => js.BinaryOp(JSBinaryOp.%, newLhs, newRhs1)
2688+
case Long_unsigned_/ => js.BinaryOp(JSBinaryOp./, wrapBigIntU64(newLhs), wrapBigIntU64(newRhs1))
2689+
case Long_unsigned_% => js.BinaryOp(JSBinaryOp.%, wrapBigIntU64(newLhs), wrapBigIntU64(newRhs1))
2690+
})
26852691
} else {
2686-
genApply(newLhs, LongImpl./, newRhs)
2687-
}
2688-
case Long_% =>
2689-
if (useBigIntForLongs) {
2690-
rhs match {
2691-
case LongLiteral(r) if r != 0L =>
2692-
wrapBigInt64(js.BinaryOp(JSBinaryOp.%, newLhs, newRhs))
2693-
case _ =>
2694-
genCallHelper(VarField.longMod, newLhs, newRhs)
2692+
// The zero divisor check is performed by the implementation methods
2693+
val implMethodName = (op: @switch) match {
2694+
case Long_/ => LongImpl./
2695+
case Long_% => LongImpl.%
2696+
case Long_unsigned_/ => LongImpl.divideUnsigned
2697+
case Long_unsigned_% => LongImpl.remainderUnsigned
26952698
}
2696-
} else {
2697-
genApply(newLhs, LongImpl.%, newRhs)
2699+
genApply(newLhs, implMethodName, newRhs)
26982700
}
26992701

27002702
case Long_| =>

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

Lines changed: 7 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -47,6 +47,9 @@ private[linker] object LongImpl {
4747
final val / = binaryOp("$div")
4848
final val % = binaryOp("$percent")
4949

50+
final val divideUnsigned = binaryOp("divideUnsigned")
51+
final val remainderUnsigned = binaryOp("remainderUnsigned")
52+
5053
final val | = binaryOp("$bar")
5154
final val & = binaryOp("$amp")
5255
final val ^ = binaryOp("$up")
@@ -80,8 +83,8 @@ private[linker] object LongImpl {
8083
final val compareToO = MethodName("compareTo", List(ClassRef(ObjectClass)), IntRef)
8184

8285
private val OperatorMethods = Set(
83-
UNARY_-, UNARY_~, this.+, this.-, *, /, %, |, &, ^, <<, >>>, >>,
84-
===, !==, <, <=, >, >=, toInt, toFloat, toDouble)
86+
UNARY_-, UNARY_~, this.+, this.-, *, /, divideUnsigned, remainderUnsigned,
87+
%, |, &, ^, <<, >>>, >>, ===, !==, <, <=, >, >=, toInt, toFloat, toDouble)
8588

8689
private val BoxedLongMethods = Set(
8790
byteValue, shortValue, intValue, longValue, floatValue, doubleValue,
@@ -91,12 +94,10 @@ private[linker] object LongImpl {
9194

9295
// Methods used for intrinsics
9396

94-
final val compareToRTLong = MethodName("compareTo", List(RTLongRef), IntRef)
95-
final val divideUnsigned = binaryOp("divideUnsigned")
96-
final val remainderUnsigned = binaryOp("remainderUnsigned")
97+
final val compareToRTLong = MethodName("compareTo", List(RTLongRef), IntRef)
9798

9899
val AllIntrinsicMethods = Set(
99-
compareToRTLong, divideUnsigned, remainderUnsigned)
100+
compareToRTLong)
100101

101102
// Constructors
102103

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

Lines changed: 2 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -256,16 +256,12 @@ private[emitter] object VarField {
256256

257257
// Arithmetic Call Helpers
258258

259-
final val intDiv = mk("$intDiv")
259+
final val checkIntDivisor = mk("$checkIntDivisor")
260260

261-
final val intMod = mk("$intMod")
261+
final val checkLongDivisor = mk("$checkLongDivisor")
262262

263263
final val longToFloat = mk("$longToFloat")
264264

265-
final val longDiv = mk("$longDiv")
266-
267-
final val longMod = mk("$longMod")
268-
269265
final val doubleToLong = mk("$doubleToLong")
270266

271267
final val doubleToInt = mk("$doubleToInt")

0 commit comments

Comments
 (0)
0