B3 32-Bit Unsigned Division-by-Constant Optimization

15c111a

Source/JavaScriptCore/b3/B3ReduceStrength.cpp

+                    if (magic.add) {
+                        if constexpr (isARM64() || isX86()) {
+                            ASSERT(!magic.preShift);
+                            uint64_t fullMagic = static_cast<uint64_t>(magic.magicMultiplier) | (1ULL << 32);
+                            uint64_t shiftedMagic = fullMagic << (31 - magic.shift);
+                            Value* ext = m_insertionSet.insert<Value>(m_index, ZExt32, m_value->origin(), dividend);
+                            Value* mulHigh = m_insertionSet.insert<Value>(
+                                m_index, UMulHigh, m_value->origin(), ext,
+                                m_insertionSet.insert<Const64Value>(m_index, m_value->origin(), static_cast<int64_t>(shiftedMagic)));
+                            replaceWithNew<Value>(Trunc, m_value->origin(), mulHigh);
+                            break;
+                        }
+                    }

B3의 strength reduction pass에 32-bit 부호 없는 정수 나눗셈 상수 최적화가 추가되었습니다. Mitsunari & Hoshino (2026)의 33-bit magic multiplier 기법을 활용합니다. magic number에 33-bit 상수가 필요한 경우(magic.add == true)에는 기존 5단계 연산 시퀀스를 단일 UMulHigh64로 대체합니다. 수식으로는 x / d = Trunc(UMulHigh64(ZExt32(x), c << (31 - shift)))에 해당합니다.

Before (magic.add == true, 5 ops):          After (1 op):
  ZExt32(x)                                   ZExt32(x)
     │                                            │
  UMulHigh(x, magic)  ← 32-bit mul high       UMulHigh64(ZExt32(x), fullMagic << (31-shift))
     │                                            │
  sub (x - mulHigh)                            Trunc
     │
  Shr (sub, 1)
     │
  Add (shr + mulHigh)
     │
  Shr (result, shift)

Significance

벤치마크 결과 Wasm udiv-by-constant 워크로드에서 약 1.9배의 성능 향상이 측정되었습니다. 다만 strength-reduction transform에서 산술 오류가 발생하면 crash 없이 조용히 잘못된 나눗셈 결과가 반환됩니다.

31 - magic.shift 표현식을 살펴볼 필요가 있습니다. 유효한 32-bit 제수 중 magic.shift가 31을 초과할 수 있다면, 이 연산이 wrap-around되어 shiftedMagic이 쓰레기 값이 됩니다. 한편 ASSERT(!magic.preShift)는 debug 빌드에서만 동작합니다. 향후 어떤 제수가 magic.add && magic.preShift > 0 조건을 유발한다면, release 빌드에서는 preShift가 조용히 무시됩니다. 마지막으로 static_cast<int64_t>(shiftedMagic)은 상위 비트가 설정된 uint64_t 값을 부호 있는 값으로 IR constant에 전달합니다. UMulHigh의 semantics(signed vs. unsigned)는 별도로 검증이 필요합니다.