Skip to content

Commit a2ee9df

Browse files
sjrdsjrd
authored
Merge pull request #5181 from sjrd/ir-clz
Introduce IR UnaryOps for `numberOfLeadingZeros` (`clz`).
2 parents 6b83864 + f414dae commit a2ee9df

File tree

15 files changed

+123
-81
lines changed

15 files changed

+123
-81
lines changed

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

Lines changed: 4 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -7426,11 +7426,13 @@ private object GenJSCode {
74267426
val byClass: Map[ClassName, Map[MethodName, JavalibOpBody]] = Map(
74277427
jswkn.BoxedIntegerClass.withSuffix("$") -> Map(
74287428
m("divideUnsigned", List(I, I), I) -> ArgBinaryOp(binop.Int_unsigned_/),
7429-
m("remainderUnsigned", List(I, I), I) -> ArgBinaryOp(binop.Int_unsigned_%)
7429+
m("remainderUnsigned", List(I, I), I) -> ArgBinaryOp(binop.Int_unsigned_%),
7430+
m("numberOfLeadingZeros", List(I), I) -> ArgUnaryOp(unop.Int_clz)
74307431
),
74317432
jswkn.BoxedLongClass.withSuffix("$") -> Map(
74327433
m("divideUnsigned", List(J, J), J) -> ArgBinaryOp(binop.Long_unsigned_/),
7433-
m("remainderUnsigned", List(J, J), J) -> ArgBinaryOp(binop.Long_unsigned_%)
7434+
m("remainderUnsigned", List(J, J), J) -> ArgBinaryOp(binop.Long_unsigned_%),
7435+
m("numberOfLeadingZeros", List(J), I) -> ArgUnaryOp(unop.Long_clz)
74347436
),
74357437
jswkn.BoxedFloatClass.withSuffix("$") -> Map(
74367438
m("floatToIntBits", List(F), I) -> ArgUnaryOp(unop.Float_toBits),

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

Lines changed: 6 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -517,6 +517,10 @@ object Trees {
517517
// final val Double_toRawBits = 36 // Reserved
518518
final val Double_fromBits = 37
519519

520+
// Other nodes introduced in 1.20
521+
final val Int_clz = 38
522+
final val Long_clz = 39
523+
520524
def isClassOp(op: Code): Boolean =
521525
op >= Class_name && op <= Class_superClass
522526

@@ -538,7 +542,8 @@ object Trees {
538542
case IntToShort =>
539543
ShortType
540544
case CharToInt | ByteToInt | ShortToInt | LongToInt | DoubleToInt |
541-
String_length | Array_length | IdentityHashCode | Float_toBits =>
545+
String_length | Array_length | IdentityHashCode | Float_toBits |
546+
Int_clz | Long_clz =>
542547
IntType
543548
case IntToLong | DoubleToLong | Double_toBits =>
544549
LongType

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

Lines changed: 2 additions & 24 deletions
Original file line numberDiff line numberDiff line change
@@ -274,30 +274,8 @@ object Integer {
274274
@inline def signum(i: scala.Int): scala.Int =
275275
if (i == 0) 0 else if (i < 0) -1 else 1
276276

277-
// Intrinsic, fallback on actual code for non-literal in JS
278-
@inline def numberOfLeadingZeros(i: scala.Int): scala.Int = {
279-
if (LinkingInfo.esVersion >= ESVersion.ES2015) js.Math.clz32(i)
280-
else clz32Dynamic(i)
281-
}
282-
283-
private def clz32Dynamic(i: scala.Int) = {
284-
if (js.typeOf(js.Dynamic.global.Math.clz32) == "function") {
285-
js.Math.clz32(i)
286-
} else {
287-
// See Hacker's Delight, Section 5-3
288-
var x = i
289-
if (x == 0) {
290-
32
291-
} else {
292-
var r = 1
293-
if ((x & 0xffff0000) == 0) { x <<= 16; r += 16 }
294-
if ((x & 0xff000000) == 0) { x <<= 8; r += 8 }
295-
if ((x & 0xf0000000) == 0) { x <<= 4; r += 4 }
296-
if ((x & 0xc0000000) == 0) { x <<= 2; r += 2 }
297-
r + (x >> 31)
298-
}
299-
}
300-
}
277+
@inline def numberOfLeadingZeros(i: scala.Int): scala.Int =
278+
throw new Error("stub") // body replaced by the compiler back-end
301279

302280
// Wasm intrinsic
303281
@inline def numberOfTrailingZeros(i: scala.Int): scala.Int =

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

Lines changed: 2 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -419,13 +419,9 @@ object Long {
419419
else 1
420420
}
421421

422-
// Wasm intrinsic
423422
@inline
424-
def numberOfLeadingZeros(l: scala.Long): Int = {
425-
val hi = (l >>> 32).toInt
426-
if (hi != 0) Integer.numberOfLeadingZeros(hi)
427-
else Integer.numberOfLeadingZeros(l.toInt) + 32
428-
}
423+
def numberOfLeadingZeros(l: scala.Long): Int =
424+
throw new Error("stub") // body replaced by the compiler back-end
429425

430426
// Wasm intrinsic
431427
@inline

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

Lines changed: 7 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -661,6 +661,13 @@ object RuntimeLong {
661661
(if (hi < 0) -absRes else absRes).toFloat
662662
}
663663

664+
@inline
665+
def clz(a: RuntimeLong): Int = {
666+
val hi = a.hi
667+
if (hi != 0) Integer.numberOfLeadingZeros(hi)
668+
else 32 + Integer.numberOfLeadingZeros(a.lo)
669+
}
670+
664671
@inline
665672
def fromInt(value: Int): RuntimeLong =
666673
new RuntimeLong(value, value >> 31)

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

Lines changed: 40 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -192,6 +192,25 @@ private[emitter] object CoreJSLib {
192192
Return((al * bl) + (((ah * bl + al * bh) << 16) >>> 0) | 0)
193193
))
194194

195+
case Clz32Builtin =>
196+
// See Hacker's Delight, Section 5-3
197+
val x = varRef("x")
198+
val r = varRef("r")
199+
genArrowFunction(paramList(x), {
200+
If(x === 0, {
201+
Return(32)
202+
}, {
203+
Block(
204+
let(r, 1),
205+
If((x & 0xffff0000) === 0, Block(x := x << 16, r := r + 16), Skip()),
206+
If((x & 0xff000000) === 0, Block(x := x << 8, r := r + 8), Skip()),
207+
If((x & 0xf0000000) === 0, Block(x := x << 4, r := r + 4), Skip()),
208+
If((x & 0xc0000000) === 0, Block(x := x << 2, r := r + 2), Skip()),
209+
Return(r + (x >> 31))
210+
)
211+
})
212+
})
213+
195214
case FroundBuiltin =>
196215
val v = varRef("v")
197216
val Float32ArrayRef = globalRef("Float32Array")
@@ -954,6 +973,27 @@ private[emitter] object CoreJSLib {
954973
}
955974
) :::
956975
condDefs(allowBigIntsForLongs)(
976+
defineFunction1(VarField.longClz) { x =>
977+
// (Math.clz32 o Number)(bigIntArg), i.e., Math.clz32(Number(bigIntArg))
978+
def clz32_o_Number(bigIntArg: Tree): Tree = {
979+
genCallPolyfillableBuiltin(PolyfillableBuiltin.Clz32Builtin,
980+
Apply(NumberRef, List(bigIntArg)))
981+
}
982+
983+
val hi = varRef("hi")
984+
985+
Block(
986+
const(hi, x >> bigInt(32)),
987+
Return {
988+
If(hi !== bigInt(0L), {
989+
clz32_o_Number(hi)
990+
}, {
991+
int(32) + clz32_o_Number(x)
992+
})
993+
}
994+
)
995+
} :::
996+
957997
defineFunction1(VarField.doubleToLong)(x => Return {
958998
If(x < double(-9223372036854775808.0), { // -2^63
959999
bigInt(-9223372036854775808L)

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

Lines changed: 9 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -2531,6 +2531,15 @@ private[emitter] class FunctionEmitter(sjsGen: SJSGen) {
25312531
genCallHelper(VarField.doubleToBits, newLhs)
25322532
case Double_fromBits =>
25332533
genCallHelper(VarField.doubleFromBits, newLhs)
2534+
2535+
// clz
2536+
case Int_clz =>
2537+
genCallPolyfillableBuiltin(PolyfillableBuiltin.Clz32Builtin, newLhs)
2538+
case Long_clz =>
2539+
if (useBigIntForLongs)
2540+
genCallHelper(VarField.longClz, newLhs)
2541+
else
2542+
genLongApplyStatic(LongImpl.clz, newLhs)
25342543
}
25352544

25362545
case BinaryOp(op, lhs, rhs) =>

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

Lines changed: 3 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -89,6 +89,7 @@ private[linker] object LongImpl {
8989
final val toFloat = MethodName("toFloat", OneRTLongRef, FloatRef)
9090
final val toDouble = MethodName("toDouble", OneRTLongRef, DoubleRef)
9191
final val bitsToDouble = MethodName("bitsToDouble", List(RTLongRef, ObjectRef), DoubleRef)
92+
final val clz = MethodName("clz", OneRTLongRef, IntRef)
9293

9394
final val fromInt = MethodName("fromInt", List(IntRef), RTLongRef)
9495
final val fromDouble = MethodName("fromDouble", List(DoubleRef), RTLongRef)
@@ -100,7 +101,8 @@ private[linker] object LongImpl {
100101
divide, remainder, divideUnsigned, remainderUnsigned,
101102
or, and, xor, shl, shr, sar,
102103
equals_, notEquals, lt, le, gt, ge,
103-
toInt, toFloat, toDouble, bitsToDouble, fromInt, fromDouble, fromDoubleBits
104+
toInt, toFloat, toDouble, bitsToDouble, clz,
105+
fromInt, fromDouble, fromDoubleBits
104106
)
105107

106108
// Methods used for intrinsics

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

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -21,6 +21,7 @@ private[emitter] object PolyfillableBuiltin {
2121
lazy val All: List[PolyfillableBuiltin] = List(
2222
ObjectIsBuiltin,
2323
ImulBuiltin,
24+
Clz32Builtin,
2425
FroundBuiltin,
2526
PrivateSymbolBuiltin,
2627
GetOwnPropertyDescriptorsBuiltin
@@ -36,6 +37,7 @@ private[emitter] object PolyfillableBuiltin {
3637

3738
case object ObjectIsBuiltin extends NamespacedBuiltin("Object", "is", VarField.is, ESVersion.ES2015)
3839
case object ImulBuiltin extends NamespacedBuiltin("Math", "imul", VarField.imul, ESVersion.ES2015)
40+
case object Clz32Builtin extends NamespacedBuiltin("Math", "clz32", VarField.clz32, ESVersion.ES2015)
3941
case object FroundBuiltin extends NamespacedBuiltin("Math", "fround", VarField.fround, ESVersion.ES2015)
4042
case object PrivateSymbolBuiltin
4143
extends GlobalVarBuiltin("Symbol", VarField.privateJSFieldSymbol, ESVersion.ES2015)

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

Lines changed: 3 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -263,6 +263,8 @@ private[emitter] object VarField {
263263

264264
final val checkLongDivisor = mk("$checkLongDivisor")
265265

266+
final val longClz = mk("$longClz")
267+
266268
final val longToFloat = mk("$longToFloat")
267269

268270
final val doubleToLong = mk("$doubleToLong")
@@ -277,6 +279,7 @@ private[emitter] object VarField {
277279
// Polyfills
278280

279281
final val imul = mk("$imul")
282+
final val clz32 = mk("$clz32")
280283
final val fround = mk("$fround")
281284
final val privateJSFieldSymbol = mk("$privateJSFieldSymbol")
282285
final val getOwnPropertyDescriptors = mk("$getOwnPropertyDescriptors")

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

Lines changed: 6 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1685,6 +1685,12 @@ private class FunctionEmitter private (
16851685
fb += wa.LocalGet(bitsLocal)
16861686
case Double_fromBits =>
16871687
fb += wa.F64ReinterpretI64
1688+
1689+
case Int_clz =>
1690+
fb += wa.I32Clz
1691+
case Long_clz =>
1692+
fb += wa.I64Clz
1693+
fb += wa.I32WrapI64
16881694
}
16891695

16901696
tree.tpe

‎linker/shared/src/main/scala/org/scalajs/linker/backend/wasmemitter/WasmTransients.scala

Lines changed: 12 additions & 16 deletions
Original file line numberDiff line numberDiff line change
@@ -47,11 +47,9 @@ object WasmTransients {
4747
Transient(WasmUnaryOp(op, transformer.transform(lhs)))
4848

4949
def wasmInstr: wa.SimpleInstr = (op: @switch) match {
50-
case I32Clz => wa.I32Clz
5150
case I32Ctz => wa.I32Ctz
5251
case I32Popcnt => wa.I32Popcnt
5352

54-
case I64Clz => wa.I64Clz
5553
case I64Ctz => wa.I64Ctz
5654
case I64Popcnt => wa.I64Popcnt
5755

@@ -75,27 +73,25 @@ object WasmTransients {
7573
/** Codes are raw Ints to be able to write switch matches on them. */
7674
type Code = Int
7775

78-
final val I32Clz = 1
79-
final val I32Ctz = 2
80-
final val I32Popcnt = 3
76+
final val I32Ctz = 1
77+
final val I32Popcnt = 2
8178

82-
final val I64Clz = 4
83-
final val I64Ctz = 5
84-
final val I64Popcnt = 6
79+
final val I64Ctz = 3
80+
final val I64Popcnt = 4
8581

86-
final val F32Abs = 7
82+
final val F32Abs = 5
8783

88-
final val F64Abs = 8
89-
final val F64Ceil = 9
90-
final val F64Floor = 10
91-
final val F64Nearest = 11
92-
final val F64Sqrt = 12
84+
final val F64Abs = 6
85+
final val F64Ceil = 7
86+
final val F64Floor = 8
87+
final val F64Nearest = 9
88+
final val F64Sqrt = 10
9389

9490
def resultTypeOf(op: Code): Type = (op: @switch) match {
95-
case I32Clz | I32Ctz | I32Popcnt =>
91+
case I32Ctz | I32Popcnt =>
9692
IntType
9793

98-
case I64Clz | I64Ctz | I64Popcnt =>
94+
case I64Ctz | I64Popcnt =>
9995
LongType
10096

10197
case F32Abs =>

‎linker/shared/src/main/scala/org/scalajs/linker/checker/IRChecker.scala

Lines changed: 4 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -538,9 +538,11 @@ private final class IRChecker(linkTimeProperties: LinkTimeProperties,
538538
ByteType
539539
case ShortToInt =>
540540
ShortType
541-
case IntToLong | IntToDouble | IntToChar | IntToByte | IntToShort | Float_fromBits =>
541+
case IntToLong | IntToDouble | IntToChar | IntToByte | IntToShort |
542+
Float_fromBits | Int_clz =>
542543
IntType
543-
case LongToInt | LongToDouble | LongToFloat | Double_fromBits =>
544+
case LongToInt | LongToDouble | LongToFloat | Double_fromBits |
545+
Long_clz =>
544546
LongType
545547
case FloatToDouble | Float_toBits =>
546548
FloatType

0 commit comments

Comments
 (0)