Marge Bot pushed to branch master at Glasgow Haskell Compiler / GHC Commits: 71808e29 by Sylvain Henry at 2026-10-22T04:50:24-04:00 Add GHC.Internal.Unboxed.Do: do-notation for unboxed values (#27944) QualifiedDo operators can be representation-polymorphic: a do-block is expanded into ordinary applications before typechecking, and the only check on a bound variable is the deferred fixed-runtime-rep check. A representation-polymorphic (>>=) cannot be defined directly, though, because its body would bind a variable of unknown representation. The new module provides such operators for State#-passing code as methods of a class indexed by RuntimeRep, with one instance per representation. With optimisation the dictionaries disappear and a block compiles to the usual nested case expressions: Ubx.do { x <- readWordArray# mba 0# -- x :: Word# ; writeWordArray# mba 1# x -- unit actions are statements ; Ubx.pure x } Also add users guide documentation and tests. Co-Authored-By: Claude Fable 5.1 <noreply@anthropic.com> - - - - - 33247780 by Sylvain Henry at 2026-10-22T04:50:24-04:00 Bignum: use Ubx.do for State#-passing code (#27944) Rewrite the State#-passing code of the GHC.Internal.Bignum modules (Primitives, WordArray, BigNat, Natural, Integer, Backend.Native, Backend.GMP) with the qualified do-notation of GHC.Internal.Unboxed.Do. Nested case chains such as case newWordArray# sz s of { (# s, mwa #) -> case act mwa s of { s -> unsafeFreezeByteArray# mwa s }} become Ubx.do mwa <- newWordArray# sz act mwa unsafeFreezeByteArray# mwa The optimised Core is unchanged (compared per top-level binding). BigNat now enables MonoLocalBinds: local loops written with Ubx.do must stay monomorphic in the state type, otherwise GHC does not turn them into join points. Co-Authored-By: Claude Fable 5.1 <noreply@anthropic.com> - - - - - 21 changed files: - + changelog.d/unboxed-do - docs/users_guide/exts/qualified_do.rst - libraries/ghc-internal/CHANGELOG.md - libraries/ghc-internal/ghc-internal.cabal.in - libraries/ghc-internal/src/GHC/Internal/Bignum/Backend/GMP.hs - libraries/ghc-internal/src/GHC/Internal/Bignum/Backend/Native.hs - libraries/ghc-internal/src/GHC/Internal/Bignum/BigNat.hs - libraries/ghc-internal/src/GHC/Internal/Bignum/Integer.hs - libraries/ghc-internal/src/GHC/Internal/Bignum/Natural.hs - libraries/ghc-internal/src/GHC/Internal/Bignum/Primitives.hs - libraries/ghc-internal/src/GHC/Internal/Bignum/WordArray.hs - + libraries/ghc-internal/src/GHC/Internal/Unboxed/Do.hs - testsuite/tests/qualifieddo/should_compile/all.T - + testsuite/tests/qualifieddo/should_compile/qdocompile003.hs - + testsuite/tests/qualifieddo/should_compile/qdocompile003.stderr - testsuite/tests/qualifieddo/should_fail/all.T - + testsuite/tests/qualifieddo/should_fail/qdofail006.hs - + testsuite/tests/qualifieddo/should_fail/qdofail006.stderr - testsuite/tests/qualifieddo/should_run/all.T - + testsuite/tests/qualifieddo/should_run/qdorun008.hs - + testsuite/tests/qualifieddo/should_run/qdorun008.stdout Changes: ===================================== changelog.d/unboxed-do ===================================== @@ -0,0 +1,11 @@ +section: ghc-internal +issues: #27944 +mrs: !16808 +synopsis: + Add ``GHC.Internal.Unboxed.Do`` for do-notation over unboxed values +description: + The new module ``GHC.Internal.Unboxed.Do`` provides ``QualifiedDo`` + operations for ``State#``-passing code. Bound variables can have any + representation (``Word#``, ``MutableByteArray# s``, ``(# Word#, Word# #)``, + ...) and unit actions of type ``State# s -> State# s`` can be used as + statements. The ``GHC.Internal.Bignum`` modules now use it. ===================================== docs/users_guide/exts/qualified_do.rst ===================================== @@ -118,6 +118,17 @@ If no qualifier is specified with ``-XQualifiedDo`` enabled, it defaults to the Note that the operations to be qualified must be in scope for QualifiedDo to work. I.e. ``import MAC (label)`` in the example above would result in an error, since ``MAC.>>=`` and ``MAC.>>`` would not be in scope. +.. _qualified-do-rep-poly: + +Representation-polymorphic operations +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ + +The operations can be representation-polymorphic, so that the variables bound +by ``pat <- u`` can have unboxed types such as ``Word#``. The representation of +each bound variable must be fixed by the type of ``u`` +(see :ref:`representation-polymorphism-restrictions`). This does not work with +:extension:`ApplicativeDo`. + Examples ~~~~~~~~ ===================================== libraries/ghc-internal/CHANGELOG.md ===================================== @@ -4,6 +4,7 @@ * Introduce `dataToCodeQ` and `liftDataTyped`, typed variants of `dataToExpQ` and `liftData` respectively. * Add new `gc_sync_elapsed_ns` counter to GHC.Internal.Stats +* Add `GHC.Internal.Unboxed.Do`: `QualifiedDo` operations for `State#`-passing code that binds unboxed values. ## 9.1001.0 -- 2024-05-01 ===================================== libraries/ghc-internal/ghc-internal.cabal.in ===================================== @@ -94,6 +94,7 @@ Library OverloadedStrings ParallelListComp PolyKinds + QualifiedDo RankNTypes RecordWildCards RoleAnnotations @@ -328,6 +329,7 @@ Library GHC.Internal.Text.Show GHC.Internal.Type.Reflection GHC.Internal.Type.Reflection.Unsafe + GHC.Internal.Unboxed.Do GHC.Internal.Unsafe.Coerce GHC.Internal.CString ===================================== libraries/ghc-internal/src/GHC/Internal/Bignum/Backend/GMP.hs ===================================== @@ -9,6 +9,7 @@ {-# LANGUAGE NegativeLiterals #-} {-# LANGUAGE BlockArguments #-} {-# LANGUAGE LambdaCase #-} +{-# LANGUAGE QualifiedDo #-} {-# OPTIONS_GHC -Wno-name-shadowing #-} @@ -26,6 +27,7 @@ import GHC.Internal.Bignum.Primitives import GHC.Internal.Prim import GHC.Internal.Types import GHC.Internal.Magic (runRW#) +import qualified GHC.Internal.Unboxed.Do as Ubx import {-# SOURCE #-} GHC.Internal.Bignum.Integer import {-# SOURCE #-} GHC.Internal.Bignum.BigNat import {-# SOURCE #-} GHC.Internal.Bignum.Natural @@ -75,15 +77,17 @@ bignat_add -> State# RealWorld -> State# RealWorld {-# INLINE bignat_add #-} -bignat_add mwa wa wb s +bignat_add mwa wa wb -- weird GMP requirement: the biggest comes first | isTrue# (wordArraySize# wb ># wordArraySize# wa) - = case ioWord# (c_mpn_add mwa wb (wordArraySize# wb) wa (wordArraySize# wa)) s of - (# s', c #) -> mwaWriteMostSignificant mwa c s' + = Ubx.do + c <- ioWord# (c_mpn_add mwa wb (wordArraySize# wb) wa (wordArraySize# wa)) + mwaWriteMostSignificant mwa c | True - = case ioWord# (c_mpn_add mwa wa (wordArraySize# wa) wb (wordArraySize# wb)) s of - (# s', c #) -> mwaWriteMostSignificant mwa c s' + = Ubx.do + c <- ioWord# (c_mpn_add mwa wa (wordArraySize# wa) wb (wordArraySize# wb)) + mwaWriteMostSignificant mwa c bignat_add_word :: MutableWordArray# RealWorld @@ -92,9 +96,9 @@ bignat_add_word -> State# RealWorld -> State# RealWorld {-# INLINE bignat_add_word #-} -bignat_add_word mwa wa b s = do - case ioWord# (c_mpn_add_1 mwa wa (wordArraySize# wa) b) s of - (# s', c #) -> mwaWriteMostSignificant mwa c s' +bignat_add_word mwa wa b = Ubx.do + c <- ioWord# (c_mpn_add_1 mwa wa (wordArraySize# wa) b) + mwaWriteMostSignificant mwa c bignat_sub :: MutableWordArray# RealWorld @@ -103,10 +107,11 @@ bignat_sub -> State# RealWorld -> (# State# RealWorld, Bool# #) {-# INLINE bignat_sub #-} -bignat_sub mwa wa wb s = - case ioWord# (c_mpn_sub mwa wa (wordArraySize# wa) wb (wordArraySize# wb)) s of - (# s', 1## #) -> (# s', 0# #) -- underflow - (# s', _ #) -> (# s', 1# #) -- no underflow +bignat_sub mwa wa wb = Ubx.do + c <- ioWord# (c_mpn_sub mwa wa (wordArraySize# wa) wb (wordArraySize# wb)) + case c of + 1## -> Ubx.pure 0# -- underflow + _ -> Ubx.pure 1# -- no underflow bignat_sub_word :: MutableWordArray# RealWorld @@ -115,10 +120,11 @@ bignat_sub_word -> State# RealWorld -> (# State# RealWorld, Bool# #) {-# INLINE bignat_sub_word #-} -bignat_sub_word mwa wa b s = - case ioWord# (c_mpn_sub_1 mwa wa (wordArraySize# wa) b) s of - (# s', 1## #) -> (# s', 0# #) -- underflow - (# s', _ #) -> (# s', 1# #) -- no underflow +bignat_sub_word mwa wa b = Ubx.do + c <- ioWord# (c_mpn_sub_1 mwa wa (wordArraySize# wa) b) + case c of + 1## -> Ubx.pure 0# -- underflow + _ -> Ubx.pure 1# -- no underflow bignat_mul :: MutableWordArray# RealWorld @@ -127,11 +133,12 @@ bignat_mul -> State# RealWorld -> State# RealWorld {-# INLINE bignat_mul #-} -bignat_mul mwa wa wb s = do - case ioWord# (c_mpn_mul mwa wa (wordArraySize# wa) wb (wordArraySize# wb)) s of - (# s', _msl #) -> s' -- we don't care about the most-significant - -- limb. The caller shrink the mwa if - -- necessary anyway. +bignat_mul mwa wa wb = Ubx.do + _msl <- ioWord# (c_mpn_mul mwa wa (wordArraySize# wa) wb (wordArraySize# wb)) + -- _msl is the most-significant limb of the result. It tells if the result + -- has a leading zero limb. We ignore it: the caller removes leading zero + -- limbs anyway (see withNewWordArrayTrimmed#). + Ubx.nop bignat_mul_word :: MutableWordArray# RealWorld -- ^ Result @@ -140,9 +147,9 @@ bignat_mul_word -> State# RealWorld -> State# RealWorld {-# INLINE bignat_mul_word #-} -bignat_mul_word mwa wa b s = - case ioWord# (c_mpn_mul_1 mwa wa (wordArraySize# wa) b) s of - (# s', c #) -> mwaWriteMostSignificant mwa c s' +bignat_mul_word mwa wa b = Ubx.do + c <- ioWord# (c_mpn_mul_1 mwa wa (wordArraySize# wa) b) + mwaWriteMostSignificant mwa c bignat_popcount :: WordArray# -> Word# {-# INLINE bignat_popcount #-} @@ -156,11 +163,12 @@ bignat_shiftl -> State# RealWorld -> State# RealWorld {-# INLINE bignat_shiftl #-} -bignat_shiftl mwa wa n s = - case ioWord# (c_mpn_lshift mwa wa (wordArraySize# wa) n) s of - (# s', _msl #) -> s' -- we don't care about the most-significant - -- limb. The caller shrink the mwa if - -- necessary anyway. +bignat_shiftl mwa wa n = Ubx.do + _msl <- ioWord# (c_mpn_lshift mwa wa (wordArraySize# wa) n) + -- _msl is the most-significant limb of the result. It tells if the result + -- has a leading zero limb. We ignore it: the caller removes leading zero + -- limbs anyway (see withNewWordArrayTrimmed#). + Ubx.nop bignat_shiftr :: MutableWordArray# RealWorld @@ -169,11 +177,12 @@ bignat_shiftr -> State# RealWorld -> State# RealWorld {-# INLINE bignat_shiftr #-} -bignat_shiftr mwa wa n s = - case ioWord# (c_mpn_rshift mwa wa (wordArraySize# wa) n) s of - (# s', _msl #) -> s' -- we don't care about the most-significant - -- limb. The caller shrink the mwa if - -- necessary anyway. +bignat_shiftr mwa wa n = Ubx.do + _msl <- ioWord# (c_mpn_rshift mwa wa (wordArraySize# wa) n) + -- _msl is the most-significant limb of the result. It tells if the result + -- has a leading zero limb. We ignore it: the caller removes leading zero + -- limbs anyway (see withNewWordArrayTrimmed#). + Ubx.nop bignat_or :: MutableWordArray# RealWorld @@ -182,15 +191,16 @@ bignat_or -> State# RealWorld -> State# RealWorld {-# INLINE bignat_or #-} -bignat_or mwa wa wb s1 - | isTrue# (szA >=# szB) = go wa szA wb szB s1 - | True = go wb szB wa szA s1 +bignat_or mwa wa wb + | isTrue# (szA >=# szB) = go wa szA wb szB + | True = go wb szB wa szA where !szA = wordArraySize# wa !szB = wordArraySize# wb -- nx >= ny - go wx nx wy ny s = case ioVoid (c_mpn_ior_n mwa wx wy ny) s of - s' -> mwaArrayCopy# mwa ny wx ny (nx -# ny) s' + go wx nx wy ny = Ubx.do + ioVoid (c_mpn_ior_n mwa wx wy ny) + mwaArrayCopy# mwa ny wx ny (nx -# ny) bignat_xor :: MutableWordArray# RealWorld @@ -199,15 +209,16 @@ bignat_xor -> State# RealWorld -> State# RealWorld {-# INLINE bignat_xor #-} -bignat_xor mwa wa wb s1 - | isTrue# (szA >=# szB) = go wa szA wb szB s1 - | True = go wb szB wa szA s1 +bignat_xor mwa wa wb + | isTrue# (szA >=# szB) = go wa szA wb szB + | True = go wb szB wa szA where !szA = wordArraySize# wa !szB = wordArraySize# wb -- nx >= ny - go wx nx wy ny s = case ioVoid (c_mpn_xor_n mwa wx wy ny) s of - s' -> mwaArrayCopy# mwa ny wx ny (nx -# ny) s' + go wx nx wy ny = Ubx.do + ioVoid (c_mpn_xor_n mwa wx wy ny) + mwaArrayCopy# mwa ny wx ny (nx -# ny) bignat_and :: MutableWordArray# RealWorld -- ^ Result @@ -229,9 +240,9 @@ bignat_and_not -> State# RealWorld -> State# RealWorld {-# INLINE bignat_and_not #-} -bignat_and_not mwa wa wb s = - case ioVoid (c_mpn_andn_n mwa wa wb n) s of - s' -> mwaArrayCopy# mwa szB wa szB (szA -# szB) s' +bignat_and_not mwa wa wb = Ubx.do + ioVoid (c_mpn_andn_n mwa wa wb n) + mwaArrayCopy# mwa szB wa szB (szA -# szB) where !szA = wordArraySize# wa !szB = wordArraySize# wb @@ -291,9 +302,7 @@ bignat_quot_word -> Word# -> State# RealWorld -> State# RealWorld -bignat_quot_word mwq wa b s = - case bignat_quotrem_word mwq wa b s of - (# s', _ #) -> s' +bignat_quot_word mwq wa b = Ubx.void (bignat_quotrem_word mwq wa b) bignat_rem_word :: WordArray# @@ -309,10 +318,10 @@ bignat_gcd -> WordArray# -> State# RealWorld -> State# RealWorld -bignat_gcd mwr wa wb s = +bignat_gcd mwr wa wb = Ubx.do -- wa > wb - case ioInt# (c_mpn_gcd# mwr wa (wordArraySize# wa) wb (wordArraySize# wb)) s of - (# s', sz #) -> mwaSetSize# mwr (narrowGmpSize# sz) s' + sz <- ioInt# (c_mpn_gcd# mwr wa (wordArraySize# wa) wb (wordArraySize# wb)) + mwaSetSize# mwr (narrowGmpSize# sz) bignat_gcd_word :: WordArray# @@ -379,7 +388,7 @@ integer_powmod b e m = naturalFromBigNat# (withNewWordArray# szm io) 0# -> szb _ -> negateInt# szb - io r s = sbignat_powmod r ssb bb be bm s + io r = sbignat_powmod r ssb bb be bm sbignat_powmod @@ -390,9 +399,9 @@ sbignat_powmod -> WordArray# -> State# RealWorld -> State# RealWorld -sbignat_powmod r b_signed_size b e m s = - case ioInt# (integer_gmp_powm# r b b_signed_size e (wordArraySize# e) m (wordArraySize# m)) s of - (# s', n #) -> mwaSetSize# r (narrowGmpSize# n) s' +sbignat_powmod r b_signed_size b e m = Ubx.do + n <- ioInt# (integer_gmp_powm# r b b_signed_size e (wordArraySize# e) m (wordArraySize# m)) + mwaSetSize# r (narrowGmpSize# n) integer_gcde :: Integer @@ -422,40 +431,39 @@ integer_gcde a b = case runRW# io of (# _, a #) -> a !x_init_sz = szb !y_init_sz = sza - io s = + io = Ubx.do -- allocate output arrays - case newWordArray# g_init_sz s of { (# s, mbg #) -> - case newWordArray# x_init_sz s of { (# s, mbx #) -> - case newWordArray# y_init_sz s of { (# s, mby #) -> + mbg <- newWordArray# g_init_sz + mbx <- newWordArray# x_init_sz + mby <- newWordArray# y_init_sz -- allocate space to return sizes (3x4 = 12) - case newPinnedByteArray# 12# s of { (# s, mszs #) -> - case unsafeFreezeByteArray# mszs s of { (# s, szs #) -> - let !ssx_ptr = byteArrayContents# szs in - let !ssy_ptr = ssx_ptr `plusAddr#` 4# in - let !sg_ptr = ssy_ptr `plusAddr#` 4# in + mszs <- newPinnedByteArray# 12# + szs <- unsafeFreezeByteArray# mszs + let !ssx_ptr = byteArrayContents# szs + !ssy_ptr = ssx_ptr `plusAddr#` 4# + !sg_ptr = ssy_ptr `plusAddr#` 4# -- call GMP - case ioVoid (integer_gmp_gcdext# mbx ssx_ptr mby ssy_ptr mbg sg_ptr ba ssa bb ssb) s of { s -> + ioVoid (integer_gmp_gcdext# mbx ssx_ptr mby ssy_ptr mbg sg_ptr ba ssa bb ssb) -- read sizes - case readInt32OffAddr# ssx_ptr 0# s of { (# s, ssx #) -> - case readInt32OffAddr# ssy_ptr 0# s of { (# s, ssy #) -> - case readInt32OffAddr# sg_ptr 0# s of { (# s, sg #) -> - case touch# szs s of { s -> + ssx <- readInt32OffAddr# ssx_ptr 0# + ssy <- readInt32OffAddr# ssy_ptr 0# + sg <- readInt32OffAddr# sg_ptr 0# + touch# szs -- shrink x, y and g to their actual sizes and freeze them - let !sx = absI# (int32ToInt# ssx) in - let !sy = absI# (int32ToInt# ssy) in - case mwaSetSize# mbx sx s of { s -> - case mwaSetSize# mby sy s of { s -> - case mwaSetSize# mbg (int32ToInt# sg) s of { s -> + let !sx = absI# (int32ToInt# ssx) + !sy = absI# (int32ToInt# ssy) + mwaSetSize# mbx sx + mwaSetSize# mby sy + mwaSetSize# mbg (int32ToInt# sg) -- return x, y and g as Integer - case unsafeFreezeByteArray# mbx s of { (# s, bx #) -> - case unsafeFreezeByteArray# mby s of { (# s, by #) -> - case unsafeFreezeByteArray# mbg s of { (# s, bg #) -> + bx <- unsafeFreezeByteArray# mbx + by <- unsafeFreezeByteArray# mby + bg <- unsafeFreezeByteArray# mbg - (# s, (# integerFromBigNat# bg - , integerFromBigNatSign# (int32ToInt# ssx <# 0#) bx - , integerFromBigNatSign# (int32ToInt# ssy <# 0#) by #) #) - }}}}}}}}}}}}}}}} + Ubx.pure (# integerFromBigNat# bg + , integerFromBigNatSign# (int32ToInt# ssx <# 0#) bx + , integerFromBigNatSign# (int32ToInt# ssy <# 0#) by #) @@ -477,8 +485,9 @@ integer_recip_mod x m = sbignat_recip_mod :: Int# -> BigNat# -> BigNat# -> BigNat# sbignat_recip_mod sign_x x m = withNewWordArray# szm io where - io r s = case ioInt# (integer_gmp_invert# r x ssx m szm) s of - (# s, rn #) -> mwaSetSize# r (narrowGmpSize# rn) s + io r = Ubx.do + rn <- ioInt# (integer_gmp_invert# r x ssx m szm) + mwaSetSize# r (narrowGmpSize# rn) !szx = bigNatSize# x !szm = bigNatSize# m !ssx = case sign_x of -- signed size of x ===================================== libraries/ghc-internal/src/GHC/Internal/Bignum/Backend/Native.hs ===================================== @@ -7,6 +7,7 @@ {-# LANGUAGE NegativeLiterals #-} {-# LANGUAGE MultiWayIf #-} {-# LANGUAGE BinaryLiterals #-} +{-# LANGUAGE QualifiedDo #-} {-# OPTIONS_GHC -Wno-name-shadowing #-} module GHC.Internal.Bignum.Backend.Native where @@ -27,6 +28,7 @@ import GHC.Internal.Bignum.WordArray import GHC.Internal.Bignum.Primitives import GHC.Internal.Prim import GHC.Internal.Types +import qualified GHC.Internal.Unboxed.Do as Ubx -- See W1 of Note [Tracking dependencies on primitives] in GHC.Internal.Base -- (This module uses the empty tuple () and string literals.) @@ -96,39 +98,41 @@ bignat_add mwa wa wb = addABc 0# 0## -- 4) We only have a potential carry -- => write the carry or shrink the array - addABc i carry s - | isTrue# (i <# szMin) = + addABc i carry + | isTrue# (i <# szMin) = Ubx.do let !(# carry', r #) = plusWord3# (indexWordArray# wa i) (indexWordArray# wb i) carry - in case mwaWrite# mwa i r s of - s' -> addABc (i +# 1#) carry' s' + mwaWrite# mwa i r + addABc (i +# 1#) carry' | isTrue# ((i ==# szA) & (i ==# szB)) - = mwaWriteOrShrink mwa carry i s + = mwaWriteOrShrink mwa carry i | isTrue# (i ==# szA) - = addAoBc wb i carry s + = addAoBc wb i carry | True - = addAoBc wa i carry s + = addAoBc wa i carry - addAoBc wab i carry s + addAoBc wab i carry | isTrue# (i ==# wordArraySize# wab) - = mwaWriteOrShrink mwa carry i s + = mwaWriteOrShrink mwa carry i | 0## <- carry - = -- copy the remaining words and remove the word allocated for the - -- potential carry - case mwaArrayCopy# mwa i wab i (wordArraySize# wab -# i) s of - s' -> mwaShrink# mwa 1# s' + = Ubx.do + -- copy the remaining words and remove the word allocated for the + -- potential carry + mwaArrayCopy# mwa i wab i (wordArraySize# wab -# i) + mwaShrink# mwa 1# | True - = let !(# carry', r #) = plusWord2# (indexWordArray# wab i) carry - in case mwaWrite# mwa i r s of - s' -> addAoBc wab (i +# 1#) carry' s' + = Ubx.do + let !(# carry', r #) = plusWord2# (indexWordArray# wab i) carry + mwaWrite# mwa i r + addAoBc wab (i +# 1#) carry' -- | Add a non-zero BigNat and a non-zero Word# -- @@ -163,22 +167,25 @@ bignat_sub_word bignat_sub_word mwa wa b = go b 0# where !sz = wordArraySize# wa - go carry i s + go carry i | isTrue# (i >=# sz) - = (# s, carry `eqWord#` 0## #) + = Ubx.pure (carry `eqWord#` 0##) | 0## <- carry - = case mwaArrayCopy# mwa i wa i (sz -# i) s of - s' -> (# s', 1# #) -- no underflow + = Ubx.do + mwaArrayCopy# mwa i wa i (sz -# i) + Ubx.pure 1# -- no underflow | True = case subWordC# (indexWordArray# wa i) carry of (# 0##, 0# #) - | isTrue# (i ==# sz) -> case mwaShrink# mwa 1# s of - s' -> (# s', 1# #) -- no underflow + | isTrue# (i ==# sz) -> Ubx.do + mwaShrink# mwa 1# + Ubx.pure 1# -- no underflow - (# l , c #) -> case mwaWrite# mwa i l s of - s1 -> go (int2Word# c) (i +# 1#) s1 + (# l , c #) -> Ubx.do + mwaWrite# mwa i l + go (int2Word# c) (i +# 1#) -- | Multiply a non-zero BigNat and a non-zero Word# -- @@ -196,14 +203,14 @@ bignat_mul_word bignat_mul_word mwa wa b = go 0# 0## where !szA = wordArraySize# wa - go i carry s - | isTrue# (i ==# szA) = mwaWriteOrShrink mwa carry i s - | True = + go i carry + | isTrue# (i ==# szA) = mwaWriteOrShrink mwa carry i + | True = Ubx.do let ai = indexWordArray# wa i !(# carry', r #) = plusWord12# carry (timesWord2# ai b) - in case mwaWrite# mwa i r s of - s' -> go (i +# 1#) carry' s' + mwaWrite# mwa i r + go (i +# 1#) carry' -- | Multiply two non-zero BigNat @@ -219,10 +226,10 @@ bignat_mul -> WordArray# -> State# RealWorld -> State# RealWorld -bignat_mul mwa wa wb s1 = +bignat_mul mwa wa wb = Ubx.do -- initialize the resulting WordArray - case mwaFill# mwa 0## 0## (int2Word# sz) s1 of - s' -> mulEachB ctzB s' -- loop on b Words + mwaFill# mwa 0## 0## (int2Word# sz) + mulEachB ctzB -- loop on b Words where !szA = wordArraySize# wa !szB = wordArraySize# wb @@ -232,27 +239,29 @@ bignat_mul mwa wa wb s1 = !ctzB = word2Int# (bigNatCtzWord# wb) -- multiply a single bj Word# to the whole wa WordArray - mul mwa wa bj j i carry s + mul mwa wa bj j i carry | isTrue# (i ==# wordArraySize# wa) -- write the carry - = mwaAddInplaceWord# mwa (i +# j) carry s + = mwaAddInplaceWord# mwa (i +# j) carry - | True = let - ai = indexWordArray# wa i - !(# c',r' #) = timesWord2# ai bj - !(# c'',r #) = plusWord2# r' carry - carry' = plusWord# c' c'' - in case mwaAddInplaceWord# mwa (i +# j) r s of - s' -> mul mwa wa bj j (i +# 1#) carry' s' + | True = Ubx.do + let + ai = indexWordArray# wa i + !(# c',r' #) = timesWord2# ai bj + !(# c'',r #) = plusWord2# r' carry + carry' = plusWord# c' c'' + mwaAddInplaceWord# mwa (i +# j) r + mul mwa wa bj j (i +# 1#) carry' -- for each bj in wb, call `mul bj wa` - mulEachB i s - | isTrue# (i ==# szB) = s + mulEachB i + | isTrue# (i ==# szB) = Ubx.nop | True = case indexWordArray# wb i of -- detect bj == 0## and skip the loop - 0## -> mulEachB (i +# 1#) s - bi -> case mul mwa wa bi i ctzA 0## s of - s' -> mulEachB (i +# 1#) s' + 0## -> mulEachB (i +# 1#) + bi -> Ubx.do + mul mwa wa bi i ctzA 0## + mulEachB (i +# 1#) -- | Sub two non-zero BigNat -- @@ -269,12 +278,12 @@ bignat_sub -> WordArray# -> State# RealWorld -> (# State# RealWorld, Bool# #) -bignat_sub mwa wa wb s = +bignat_sub mwa wa wb = Ubx.do -- initialize the resulting WordArray -- Note: we could avoid the copy by subtracting the first non-zero -- less-significant word of b... - case mwaArrayCopy# mwa 0# wa 0# (wordArraySize# wa) s of - s' -> mwaSubInplaceArray mwa 0# wb s' + mwaArrayCopy# mwa 0# wa 0# (wordArraySize# wa) + mwaSubInplaceArray mwa 0# wb -- | PopCount of a non-zero BigNat bignat_popcount :: WordArray# -> Word# @@ -298,30 +307,29 @@ bignat_shiftl -> Word# -> State# s -> State# s -bignat_shiftl mwa wa n s1 = +bignat_shiftl mwa wa n = Ubx.do -- set the lower words to 0 - case mwaFill# mwa 0## 0## (int2Word# nw) s1 of - s2 -> if - | 0# <- nb -> mwaArrayCopy# mwa nw wa 0# szA s2 - | True -> mwaBitShift 0# 0## s2 + mwaFill# mwa 0## 0## (int2Word# nw) + if | 0# <- nb -> mwaArrayCopy# mwa nw wa 0# szA + | True -> mwaBitShift 0# 0## where !szA = wordArraySize# wa !(# nw, nb #) = count_words_bits_int n !sh = WORD_SIZE_IN_BITS# -# nb -- Bit granularity (c is the carry from the previous shift) - mwaBitShift i c s + mwaBitShift i c -- write the carry | isTrue# (i ==# szA) - = mwaWriteOrShrink mwa c (i +# nw) s + = mwaWriteOrShrink mwa c (i +# nw) - | True = + | True = Ubx.do let !ai = indexWordArray# wa i !v = c `or#` (ai `uncheckedShiftL#` nb) !c' = ai `uncheckedShiftRL#` sh - in case mwaWrite# mwa (i +# nw) v s of - s' -> mwaBitShift (i +# 1#) c' s' + mwaWrite# mwa (i +# nw) v + mwaBitShift (i +# 1#) c' -- | Right-shift a non-zero BigNat by a non-zero amount of bits @@ -337,9 +345,9 @@ bignat_shiftr -> Word# -> State# s -> State# s -bignat_shiftr mwa wa n s1 - | isTrue# (nb ==# 0#) = mwaArrayCopy# mwa 0# wa nw sz s1 - | True = mwaBitShift (sz -# 1#) 0## s1 +bignat_shiftr mwa wa n + | isTrue# (nb ==# 0#) = mwaArrayCopy# mwa 0# wa nw sz + | True = mwaBitShift (sz -# 1#) 0## where !szA = wordArraySize# wa !(# nw, nb #) = count_words_bits_int n @@ -347,15 +355,15 @@ bignat_shiftr mwa wa n s1 !sh = WORD_SIZE_IN_BITS# -# nb -- Bit granularity (c is the carry from the previous shift) - mwaBitShift i c s - | isTrue# (i <# 0#) = s - | True = + mwaBitShift i c + | isTrue# (i <# 0#) = Ubx.nop + | True = Ubx.do let !ai = indexWordArray# wa (i +# nw) !v = c `or#` (ai `uncheckedShiftRL#` nb) !c' = ai `uncheckedShiftL#` sh - in case mwaWrite# mwa i v s of - s' -> mwaBitShift (i -# 1#) c' s' + mwaWrite# mwa i v + mwaBitShift (i -# 1#) c' -- | Right-shift a non-zero BigNat by a non-zero amount of bits by first -- converting it into its two's complement representation and then again after @@ -372,15 +380,15 @@ bignat_shiftr_neg -> Word# -> State# s -> State# s -bignat_shiftr_neg mwa wa n s1 +bignat_shiftr_neg mwa wa n = Ubx.do -- initialize higher limb of mwa - = case mwaSize# mwa s1 of - (# s2, sz_mwa #) -> case mwaWrite# mwa (sz_mwa -# 1#) 0## s2 of - s3 -> case bignat_shiftr mwa wa n s3 of - s4 -> if nz_shifted_out - -- round if non-zero bits were shifted out - then mwaAddInplaceWord# mwa 0# 1## s4 - else s4 + sz_mwa <- mwaSize# mwa + mwaWrite# mwa (sz_mwa -# 1#) 0## + bignat_shiftr mwa wa n + if nz_shifted_out + -- round if non-zero bits were shifted out + then mwaAddInplaceWord# mwa 0# 1## + else Ubx.nop where !(# nw, nb #) = count_words_bits_int n @@ -412,16 +420,16 @@ bignat_or -> WordArray# -> State# RealWorld -> State# RealWorld -bignat_or mwa wa wb s1 - | isTrue# (szA >=# szB) = go wa szA wb szB s1 - | True = go wb szB wa szA s1 +bignat_or mwa wa wb + | isTrue# (szA >=# szB) = go wa szA wb szB + | True = go wb szB wa szA where !szA = wordArraySize# wa !szB = wordArraySize# wb -- nx >= ny - go wx nx wy ny s = - case mwaInitArrayBinOp mwa wx wy or# s of - s' -> mwaArrayCopy# mwa ny wx ny (nx -# ny) s' + go wx nx wy ny = Ubx.do + mwaInitArrayBinOp mwa wx wy or# + mwaArrayCopy# mwa ny wx ny (nx -# ny) -- | XOR two non-zero BigNat -- @@ -436,16 +444,16 @@ bignat_xor -> WordArray# -> State# RealWorld -> State# RealWorld -bignat_xor mwa wa wb s1 - | isTrue# (szA >=# szB) = go wa szA wb szB s1 - | True = go wb szB wa szA s1 +bignat_xor mwa wa wb + | isTrue# (szA >=# szB) = go wa szA wb szB + | True = go wb szB wa szA where !szA = wordArraySize# wa !szB = wordArraySize# wb -- nx >= ny - go wx nx wy ny s = - case mwaInitArrayBinOp mwa wx wy xor# s of - s' -> mwaArrayCopy# mwa ny wx ny (nx -# ny) s' + go wx nx wy ny = Ubx.do + mwaInitArrayBinOp mwa wx wy xor# + mwaArrayCopy# mwa ny wx ny (nx -# ny) -- | AND two non-zero BigNat -- @@ -475,9 +483,9 @@ bignat_and_not -> WordArray# -> State# RealWorld -> State# RealWorld -bignat_and_not mwa wa wb s = - case mwaInitArrayBinOp mwa wa wb (\x y -> x `and#` not# y) s of - s' -> mwaArrayCopy# mwa szB wa szB (szA -# szB) s' +bignat_and_not mwa wa wb = Ubx.do + mwaInitArrayBinOp mwa wa wb (\x y -> x `and#` not# y) + mwaArrayCopy# mwa szB wa szB (szA -# szB) where !szA = wordArraySize# wa !szB = wordArraySize# wb @@ -497,7 +505,7 @@ bignat_quotrem -> WordArray# -> State# s -> State# s -bignat_quotrem mwq mwr uwa uwb s0 = +bignat_quotrem mwq mwr uwa uwb = Ubx.do -- Normalization consists in left-shifting bits in B and A so that the -- most-significant bit of the most-significant word of B is 1. It makes -- quotient prediction much more efficient as we only use the two most @@ -513,30 +521,27 @@ bignat_quotrem mwq mwr uwa uwb s0 = -- -- We allocate it here with an additionnal Word compared to A because -- normalizing can left shift at most (N-1) bits (on N-bit arch). - in case newWordArray# (wordArraySize# uwa +# 1#) s0 of { (# s1, mnwa #) -> + mnwa <- newWordArray# (wordArraySize# uwa +# 1#) -- normalized A in mnwa - let normalizeA s = case mwaWrite# mnwa (wordArraySize# uwa) 0## s of -- init potential carry - s -> case bignat_shiftl mnwa uwa clzb s of -- left shift - s -> mwaTrimZeroes# mnwa s -- remove null carry if any - in case normalizeA s1 of { s2 -> + mwaWrite# mnwa (wordArraySize# uwa) 0## -- init potential carry + bignat_shiftl mnwa uwa clzb -- left shift + mwaTrimZeroes# mnwa -- remove null carry if any -- normalize B. We don't do it in a MutableWordArray because it will remain -- constant during the whole computation. - let !nwb = bigNatShiftL# uwb clzb in + let !nwb = bigNatShiftL# uwb clzb -- perform quotrem on normalized inputs - case bignat_quotrem_normalized mwq mnwa nwb s2 of { s3 -> + bignat_quotrem_normalized mwq mnwa nwb -- denormalize the remainder now stored in mnwa. We just have to right shift -- of "clzb" bits. We copy the result into "mwr" array. - let denormalizeR s = case mwaTrimZeroes# mnwa s of - s -> case unsafeFreezeByteArray# mnwa s of - (# s, wr #) -> case mwaSetSize# mwr (wordArraySize# wr) s of - s -> case bignat_shiftr mwr wr clzb s of - s -> mwaTrimZeroes# mwr s - in denormalizeR s3 - }}} + mwaTrimZeroes# mnwa + wr <- unsafeFreezeByteArray# mnwa + mwaSetSize# mwr (wordArraySize# wr) + bignat_shiftr mwr wr clzb + mwaTrimZeroes# mwr @@ -553,10 +558,10 @@ bignat_quot -> WordArray# -> State# RealWorld -> State# RealWorld -bignat_quot mwq wa wb s = +bignat_quot mwq wa wb = Ubx.do -- allocate a temporary array for the remainder and call quotrem - case newWordArray# (wordArraySize# wb) s of - (# s, mwr #) -> bignat_quotrem mwq mwr wa wb s + mwr <- newWordArray# (wordArraySize# wb) + bignat_quotrem mwq mwr wa wb -- | Remainder of two non-zero BigNat -- @@ -571,12 +576,12 @@ bignat_rem -> WordArray# -> State# RealWorld -> State# RealWorld -bignat_rem mwr wa wb s = +bignat_rem mwr wa wb = Ubx.do -- allocate a temporary array for the quotient and call quotrem -- (we could avoid allocating it as it is not used to compute the result but -- it would require non trivial modification of bignat_quotrem) - case newWordArray# szQ s of - (# s, mwq #) -> bignat_quotrem mwq mwr wa wb s + mwq <- newWordArray# szQ + bignat_quotrem mwq mwr wa wb where szA = wordArraySize# wa szB = wordArraySize# wb @@ -593,14 +598,14 @@ bignat_quotrem_normalized -> WordArray# -> State# s -> State# s -bignat_quotrem_normalized mwq mwa b s0 = +bignat_quotrem_normalized mwq mwa b = Ubx.do -- n is the size of B let !n = wordArraySize# b -- m+n is the size of A (m >= 0) - in case mwaSize# mwa s0 of { (# s1, szA #) -> - let !m = szA -# n in + szA <- mwaSize# mwa + let !m = szA -# n -- Definitions: -- MSW(x) is the most-significant word of x @@ -624,18 +629,22 @@ bignat_quotrem_normalized mwq mwa b s0 = -- A := A - (B << m words) -- else Qm = 0 -- A unchanged - let computeQm s = case mwaTrimCompare m mwa b s of - (# s, LT #) -> (# s, 0## #) - (# s, _ #) -> (# s, 1## #) - - updateQj j qj qjb s = case mwaWrite# mwq j qj s of -- write Qj - s | 0## <- qj -> s - | True -> case mwaSubInplaceArray mwa j qjb s of -- subtract (qjB << j words) - (# s, _ #) -> s + let computeQm = Ubx.do + c <- mwaTrimCompare m mwa b + case c of + LT -> Ubx.pure 0## + _ -> Ubx.pure 1## + + updateQj j qj qjb = Ubx.do + mwaWrite# mwq j qj -- write Qj + case qj of + 0## -> Ubx.nop + _ -> Ubx.void (mwaSubInplaceArray mwa j qjb) -- subtract (qjB << j words) -- update the highest word of Q - updateQm s = case computeQm s of - (# s, qm #) -> updateQj m qm b s + updateQm = Ubx.do + qm <- computeQm + updateQj m qm b -- the size of Q is szA+szB+1 BEFORE normalization. Normalization may add -- an additional higher word to A. @@ -649,11 +658,13 @@ bignat_quotrem_normalized mwq mwa b s0 = -- accordingly -- -- We detect if A has an additional limb by comparing the size of Q with m - updateQmMaybe s = case mwaSize# mwq s of - (# s, szQ #) | isTrue# (m <# szQ) -> updateQm s - | True -> s + updateQmMaybe = Ubx.do + szQ <- mwaSize# mwq + if isTrue# (m <# szQ) + then updateQm + else Ubx.nop - in case updateQmMaybe s1 of { s2 -> + updateQmMaybe -- main loop: for j from (m-1) downto 0 @@ -669,33 +680,37 @@ bignat_quotrem_normalized mwq mwa b s0 = let bmsw = wordArrayLast# b -- most significant word of B - estimateQj j s = - case mwaRead# mwa (n +# j) s of - (# s, a1 #) -> case mwaRead# mwa (n +# j -# 1#) s of - (# s, a0 #) -> case quotRemWord3# (# a1, a0 #) bmsw of - (# (# 0##, qj #), _ #) -> (# s, qj #) - (# (# _, _ #), _ #) -> (# s, WORD_MAXBOUND## #) + estimateQj j = Ubx.do + a1 <- mwaRead# mwa (n +# j) + a0 <- mwaRead# mwa (n +# j -# 1#) + case quotRemWord3# (# a1, a0 #) bmsw of + (# (# 0##, qj #), _ #) -> Ubx.pure qj + (# (# _, _ #), _ #) -> Ubx.pure WORD_MAXBOUND## -- we perform the qj*B multiplication once and then we subtract B from -- qj*B as much as needed until (qj'*B << j words) <= A - findRealQj j qj s = findRealQj' j qj (bigNatMulWord# b qj) s + findRealQj j qj = findRealQj' j qj (bigNatMulWord# b qj) - findRealQj' j qj qjB s = case mwaTrimCompare j mwa qjB s of - (# s, LT #) -> findRealQj' j (qj `minusWord#` 1##) (bigNatSubUnsafe qjB b) s + findRealQj' j qj qjB = Ubx.do + c <- mwaTrimCompare j mwa qjB + case c of + LT -> findRealQj' j (qj `minusWord#` 1##) (bigNatSubUnsafe qjB b) -- TODO: we could do the sub inplace to -- reduce allocations - (# s, _ #) -> (# s, qj, qjB #) + _ -> Ubx.pure (# qj, qjB #) - loop j s = case estimateQj j s of - (# s, qj #) -> case findRealQj j qj s of - (# s, qj, qjB #) -> case updateQj j qj qjB s of - s | 0# <- j -> s - | True -> loop (j -# 1#) s + loop j = Ubx.do + qj <- estimateQj j + (# qj', qjB #) <- findRealQj j qj + updateQj j qj' qjB + case j of + 0# -> Ubx.nop + _ -> loop (j -# 1#) - in if | 0# <- m -> s2 - | True -> loop (m -# 1#) s2 - }} + case m of + 0# -> Ubx.nop + _ -> loop (m -# 1#) -- | QuotRem of a non-zero BigNat and a non-zero Word -- @@ -712,17 +727,17 @@ bignat_quotrem_word -> Word# -> State# s -> (# State# s, Word# #) -bignat_quotrem_word mwq wa b s = go (sz -# 1#) 0## s +bignat_quotrem_word mwq wa b = go (sz -# 1#) 0## where sz = wordArraySize# wa - go i r s - | isTrue# (i <# 0#) = (# s, r #) - | True = + go i r + | isTrue# (i <# 0#) = Ubx.pure r + | True = Ubx.do let ai = indexWordArray# wa i !(# q,r' #) = quotRemWord2# r ai b - in case mwaWrite# mwq i q s of - s' -> go (i -# 1#) r' s' + mwaWrite# mwq i q + go (i -# 1#) r' -- | Quot of a non-zero BigNat and a non-zero Word -- @@ -737,17 +752,17 @@ bignat_quot_word -> Word# -> State# s -> State# s -bignat_quot_word mwq wa b s = go (sz -# 1#) 0## s +bignat_quot_word mwq wa b = go (sz -# 1#) 0## where sz = wordArraySize# wa - go i r s - | isTrue# (i <# 0#) = s - | True = + go i r + | isTrue# (i <# 0#) = Ubx.nop + | True = Ubx.do let ai = indexWordArray# wa i !(# q,r' #) = quotRemWord2# r ai b - in case mwaWrite# mwq i q s of - s' -> go (i -# 1#) r' s' + mwaWrite# mwq i q + go (i -# 1#) r' -- | Remainder of a non-zero BigNat and a non-zero Word -- @@ -784,15 +799,15 @@ bignat_gcd -> State# s bignat_gcd mwr = go where - go wmax wmin s + go wmax wmin | isTrue# (wordArraySize# wmin ==# 0#) - = mwaInitCopyShrink# mwr wmax s + = mwaInitCopyShrink# mwr wmax | True = let wmax' = wmin !wmin' = bigNatRem wmax wmin - in go wmax' wmin' s + in go wmax' wmin' -- | Greatest common divisor (GCD) of a non-zero/non-one BigNat and a -- non-zero/non-one Word# ===================================== libraries/ghc-internal/src/GHC/Internal/Bignum/BigNat.hs ===================================== @@ -9,6 +9,11 @@ {-# LANGUAGE PolyKinds #-} {-# LANGUAGE KindSignatures #-} {-# LANGUAGE BinaryLiterals #-} +{-# LANGUAGE QualifiedDo #-} +{-# LANGUAGE MonoLocalBinds #-} + -- Local State#-passing loops (e.g. in bigNatFromAddrLE#) must stay + -- monomorphic in the state type, otherwise GHC does not turn them into + -- join points (see #14620). {-# OPTIONS_GHC -fdefines-known-key-names #-} -- Defines lots of functions that have BuiltinRules @@ -28,6 +33,7 @@ import GHC.Internal.Magic import GHC.Internal.Bignum.Primitives import GHC.Internal.Bignum.WordArray import GHC.Internal.Bignum.Backend +import qualified GHC.Internal.Unboxed.Do as Ubx -- | A BigNat -- @@ -198,10 +204,10 @@ bigNatFromWordListUnsafe xs = length i [] = i length i (_:ys) = length (i +# 1#) ys !lxs = length 0# xs - writeWordList _mwa _i [] s = s - writeWordList mwa i (W# w:ws) s = - case mwaWrite# mwa i w s of - s1 -> writeWordList mwa (i -# 1#) ws s1 + writeWordList _mwa _i [] = Ubx.nop + writeWordList mwa i (W# w:ws) = Ubx.do + mwaWrite# mwa i w + writeWordList mwa (i -# 1#) ws in withNewWordArray# lxs \mwa -> writeWordList mwa (lxs -# 1#) xs @@ -503,17 +509,18 @@ bigNatSubWordUnsafe# x y where !sz = wordArraySize# x - go mwa carry i s + go mwa carry i | isTrue# (i >=# sz) - = s + = Ubx.nop | 0## <- carry - = mwaArrayCopy# mwa i x i (sz -# i) s + = mwaArrayCopy# mwa i x i (sz -# i) | True - = case subWordC# (indexWordArray# x i) carry of - (# l, c #) -> case mwaWrite# mwa i l s of - s1 -> go mwa (int2Word# c) (i +# 1#) s1 + = Ubx.do + let !(# l, c #) = subWordC# (indexWordArray# x i) carry + mwaWrite# mwa i l + go mwa (int2Word# c) (i +# 1#) -- | Subtract a Word# from a BigNat -- @@ -537,13 +544,14 @@ bigNatSubUnsafe a b | bigNatIsZero b = a | True = let szA = wordArraySize# a - in withNewWordArrayTrimmed# szA \mwa s-> - case inline bignat_sub mwa a b s of - (# s', 1# #) -> s' - (# s', _ #) -> case raiseUnderflow of - !_ -> s' - -- see Note [ghc-bignum exceptions] in - -- GHC.Internal.Bignum.Primitives + in withNewWordArrayTrimmed# szA \mwa -> Ubx.do + ok <- inline bignat_sub mwa a b + case ok of + 1# -> Ubx.nop + _ -> case raiseUnderflow of + !_ -> Ubx.nop + -- see Note [ghc-bignum exceptions] in + -- GHC.Internal.Bignum.Primitives -- | Subtract two BigNat bigNatSub :: BigNat# -> BigNat# -> (# (# #) | BigNat# #) @@ -620,13 +628,12 @@ bigNatQuotRemWord# a b | True = let sz = wordArraySize# a - io s = - case newWordArray# sz s of { (# s1, mwq #) -> - case inline bignat_quotrem_word mwq a b s1 of { (# s2, r #) -> - case mwaTrimZeroes# mwq s2 of { s3 -> - case unsafeFreezeByteArray# mwq s3 of { (# s4, wq #) -> - (# s4, (# wq, r #) #) - }}}} + io = Ubx.do + mwq <- newWordArray# sz + r <- inline bignat_quotrem_word mwq a b + mwaTrimZeroes# mwq + wq <- unsafeFreezeByteArray# mwq + Ubx.pure (# wq, r #) in case runRW# io of (# _, (# wq,r #) #) -> (# wq, r #) @@ -815,9 +822,9 @@ bigNatOrWord# a b | 0## <- b = a | True = let sz = wordArraySize# a - in withNewWordArray# sz \mwa s -> - case mwaArrayCopy# mwa 1# a 1# (sz -# 1#) s of - s' -> mwaWrite# mwa 0# (indexWordArray# a 0# `or#` b) s' + in withNewWordArray# sz \mwa -> Ubx.do + mwaArrayCopy# mwa 1# a 1# (sz -# 1#) + mwaWrite# mwa 0# (indexWordArray# a 0# `or#` b) -- | Bitwise AND bigNatAnd :: BigNat# -> BigNat# -> BigNat# @@ -852,11 +859,10 @@ bigNatAndNotWord# :: BigNat# -> Word# -> BigNat# bigNatAndNotWord# a b | bigNatIsZero a = a | szA <- bigNatSize# a - = withNewWordArray# szA \mwa s -> + = withNewWordArray# szA \mwa -> Ubx.do -- duplicate higher limbs - case mwaArrayCopy# mwa 1# a 1# (szA -# 1#) s of - s' -> writeWordArray# mwa 0# - (indexWordArray# a 0# `and#` not# b) s' + mwaArrayCopy# mwa 1# a 1# (szA -# 1#) + writeWordArray# mwa 0# (indexWordArray# a 0# `and#` not# b) -- | Bitwise AND with Int# bigNatAndInt# :: BigNat# -> Int# -> BigNat# @@ -864,11 +870,10 @@ bigNatAndInt# a b | bigNatIsZero a = a | isTrue# (b >=# 0#) = bigNatAndWord# a (int2Word# b) | szA <- bigNatSize# a - = withNewWordArray# szA \mwa s -> + = withNewWordArray# szA \mwa -> Ubx.do -- duplicate higher limbs (because of sign-extension of b) - case mwaArrayCopy# mwa 1# a 1# (szA -# 1#) s of - s' -> writeWordArray# mwa 0# - (indexWordArray# a 0# `and#` int2Word# b) s' + mwaArrayCopy# mwa 1# a 1# (szA -# 1#) + writeWordArray# mwa 0# (indexWordArray# a 0# `and#` int2Word# b) -- | Bitwise XOR @@ -891,9 +896,9 @@ bigNatXorWord# a b | True = let sz = wordArraySize# a - in withNewWordArray# sz \mwa s -> - case mwaArrayCopy# mwa 1# a 1# (sz -# 1#) s of - s' -> mwaWrite# mwa 0# (indexWordArray# a 0# `xor#` b) s' + in withNewWordArray# sz \mwa -> Ubx.do + mwaArrayCopy# mwa 1# a 1# (sz -# 1#) + mwaWrite# mwa 0# (indexWordArray# a 0# `xor#` b) -- | PopCount for BigNat bigNatPopCount :: BigNat# -> Word @@ -1005,11 +1010,11 @@ bigNatBit# i !nb = word2Int# (i `and#` WORD_SIZE_BITS_MASK##) !sz = nw +# 1# !v = 1## `uncheckedShiftL#` nb - in withNewWordArray# sz \mwa s -> + in withNewWordArray# sz \mwa -> Ubx.do -- clear the array - case mwaFill# mwa 0## 0## (int2Word# sz) s of - -- set the bit in the most-significant word - s2 -> mwaWrite# mwa (sz -# 1#) v s2 + mwaFill# mwa 0## 0## (int2Word# sz) + -- set the bit in the most-significant word + mwaWrite# mwa (sz -# 1#) v -- | Return a BigNat whose bit `i` is the only one set. -- @@ -1042,9 +1047,9 @@ bigNatClearBit# a n mwaArrayCopy# mwa 0# a 0# nsz s | True -> - withNewWordArray# sz \mwa s -> - case mwaArrayCopy# mwa 0# a 0# sz s of - s' -> writeWordArray# mwa nw nv s' + withNewWordArray# sz \mwa -> Ubx.do + mwaArrayCopy# mwa 0# a 0# sz + writeWordArray# mwa nw nv -- | BigNat set bit bigNatSetBit# :: BigNat# -> Word# -> BigNat# @@ -1061,15 +1066,15 @@ bigNatSetBit# a n in if -- result BigNat will have more limbs | isTrue# (d ># 0#) - -> withNewWordArray# (nw +# 1#) \mwa s -> - case mwaArrayCopy# mwa 0# a 0# sz s of - s' -> case mwaFill# mwa 0## (int2Word# sz) (int2Word# (d -# 1#)) s' of - s'' -> writeWordArray# mwa nw (bitW# nb) s'' + -> withNewWordArray# (nw +# 1#) \mwa -> Ubx.do + mwaArrayCopy# mwa 0# a 0# sz + mwaFill# mwa 0## (int2Word# sz) (int2Word# (d -# 1#)) + writeWordArray# mwa nw (bitW# nb) | nv <- bigNatIndex# a nw `or#` bitW# nb - -> withNewWordArray# sz \mwa s -> - case mwaArrayCopy# mwa 0# a 0# sz s of - s' -> writeWordArray# mwa nw nv s' + -> withNewWordArray# sz \mwa -> Ubx.do + mwaArrayCopy# mwa 0# a 0# sz + writeWordArray# mwa nw nv -- | Reverse the given bit bigNatComplementBit# :: BigNat# -> Word# -> BigNat# @@ -1082,15 +1087,15 @@ bigNatComplementBit# a n = in if -- result BigNat will have more limbs | isTrue# (d ># 0#) - -> withNewWordArray# (nw +# 1#) \mwa s -> - case mwaArrayCopy# mwa 0# a 0# sz s of - s' -> case mwaFill# mwa 0## (int2Word# sz) (int2Word# (d -# 1#)) s' of - s'' -> writeWordArray# mwa nw (bitW# nb) s'' + -> withNewWordArray# (nw +# 1#) \mwa -> Ubx.do + mwaArrayCopy# mwa 0# a 0# sz + mwaFill# mwa 0## (int2Word# sz) (int2Word# (d -# 1#)) + writeWordArray# mwa nw (bitW# nb) | nv <- bigNatIndex# a nw `xor#` bitW# nb - -> withNewWordArrayTrimmed# sz \mwa s -> - case mwaArrayCopy# mwa 0# a 0# sz s of - s' -> writeWordArray# mwa nw nv s' + -> withNewWordArrayTrimmed# sz \mwa -> Ubx.do + mwaArrayCopy# mwa 0# a 0# sz + writeWordArray# mwa nw nv ------------------------------------------------- -- Log operations @@ -1259,11 +1264,12 @@ bigNatCtzWord a = W# (bigNatCtzWord# a) -- zero bytes written. bigNatToAddrLE# :: BigNat# -> Addr# -> State# s -> (# State# s, Word# #) {-# NOINLINE bigNatToAddrLE# #-} -bigNatToAddrLE# a addr s0 - | isTrue# (sz ==# 0#) = (# s0, 0## #) - | True = case writeMSB s0 of - (# s1, k #) -> case go 0# s1 of - s2 -> (# s2, k `plusWord#` (int2Word# li `uncheckedShiftL#` WORD_SIZE_BYTES_SHIFT#) #) +bigNatToAddrLE# a addr + | isTrue# (sz ==# 0#) = Ubx.pure 0## + | True = Ubx.do + k <- writeMSB + go 0# + Ubx.pure (k `plusWord#` (int2Word# li `uncheckedShiftL#` WORD_SIZE_BYTES_SHIFT#)) where !sz = wordArraySize# a !li = sz -# 1# @@ -1271,15 +1277,16 @@ bigNatToAddrLE# a addr s0 writeMSB = wordToAddrLE# (indexWordArray# a li) (addr `plusAddr#` (li `uncheckedIShiftL#` WORD_SIZE_BYTES_SHIFT#)) - go i s + go i | isTrue# (i <# li) , off <- i `uncheckedIShiftL#` WORD_SIZE_BYTES_SHIFT# , w <- indexWordArray# a i - = case wordWriteAddrLE# w (addr `plusAddr#` off) s of - s -> go (i +# 1#) s + = Ubx.do + wordWriteAddrLE# w (addr `plusAddr#` off) + go (i +# 1#) | True - = s + = Ubx.nop -- | Write a BigNat in base-256 big-endian representation and return the -- number of bytes written. @@ -1289,23 +1296,24 @@ bigNatToAddrLE# a addr s0 -- zero bytes written. bigNatToAddrBE# :: BigNat# -> Addr# -> State# s -> (# State# s, Word# #) {-# NOINLINE bigNatToAddrBE# #-} -bigNatToAddrBE# a addr s0 - | isTrue# (sz ==# 0#) = (# s0, 0## #) +bigNatToAddrBE# a addr + | isTrue# (sz ==# 0#) = Ubx.pure 0## | msw <- indexWordArray# a (sz -# 1#) - = case wordToAddrBE# msw addr s0 of - (# s1, k #) -> case go (sz -# 1#) (addr `plusAddr#` word2Int# k) s1 of - s2 -> (# s2, k `plusWord#` (int2Word# (sz -# 1#) `uncheckedShiftL#` WORD_SIZE_BYTES_SHIFT#) #) + = Ubx.do + k <- wordToAddrBE# msw addr + go (sz -# 1#) (addr `plusAddr#` word2Int# k) + Ubx.pure (k `plusWord#` (int2Word# (sz -# 1#) `uncheckedShiftL#` WORD_SIZE_BYTES_SHIFT#)) where sz = wordArraySize# a - go i adr s + go i adr | 0# <- i - = s + = Ubx.nop | w <- indexWordArray# a (i -# 1#) - = case wordWriteAddrBE# w adr s of - s' -> go (i -# 1#) - (adr `plusAddr#` WORD_SIZE_IN_BYTES# ) s' + = Ubx.do + wordWriteAddrBE# w adr + go (i -# 1#) (adr `plusAddr#` WORD_SIZE_IN_BYTES# ) -- | Write a BigNat in base-256 representation and return the @@ -1333,8 +1341,9 @@ bigNatToAddr# a addr _ s = bigNatToAddrBE# a addr s -- written in advance. In case of @/i/ == 0@, the function will write and report -- zero bytes written. bigNatToAddr :: BigNat# -> Addr# -> Bool# -> IO Word -bigNatToAddr a addr e = IO \s -> case bigNatToAddr# a addr e s of - (# s', w #) -> (# s', W# w #) +bigNatToAddr a addr e = IO Ubx.do + w <- bigNatToAddr# a addr e + Ubx.pure (W# w) @@ -1349,34 +1358,37 @@ bigNatToAddr a addr e = IO \s -> case bigNatToAddr# a addr e s of -- Higher limbs equal to 0 are automatically trimmed. bigNatFromAddrLE# :: Word# -> Addr# -> State# s -> (# State# s, BigNat# #) {-# NOINLINE bigNatFromAddrLE# #-} -bigNatFromAddrLE# 0## _ s = (# s, bigNatZero# (# #) #) -bigNatFromAddrLE# sz addr s = +bigNatFromAddrLE# 0## _ = Ubx.pure (bigNatZero# (# #)) +bigNatFromAddrLE# sz addr = let !nw = sz `uncheckedShiftRL#` WORD_SIZE_BYTES_SHIFT# !nb = sz `and#` WORD_SIZE_BYTES_MASK## - readMSB mwa s + readMSB mwa | 0## <- nb - = s + = Ubx.nop | off <- word2Int# (nw `uncheckedShiftL#` WORD_SIZE_BYTES_SHIFT#) - = case wordFromAddrLE# nb (addr `plusAddr#` off) s of - (# s, w #) -> mwaWrite# mwa (word2Int# nw) w s + = Ubx.do + w <- wordFromAddrLE# nb (addr `plusAddr#` off) + mwaWrite# mwa (word2Int# nw) w - go mwa i s + go mwa i | isTrue# (i ==# word2Int# nw) - = s + = Ubx.nop | off <- i `uncheckedIShiftL#` WORD_SIZE_BYTES_SHIFT# - = case wordFromAddrLE# WORD_SIZE_IN_BYTES## (addr `plusAddr#` off) s of - (# s, w #) -> case mwaWrite# mwa i w s of - s -> go mwa (i +# 1#) s - - in case newWordArray# (word2Int# nw +# (word2Int# nb /=# 0#)) s of - (# s, mwa #) -> case readMSB mwa s of - s -> case go mwa 0# s of - s -> case mwaTrimZeroes# mwa s of - s -> unsafeFreezeByteArray# mwa s + = Ubx.do + w <- wordFromAddrLE# WORD_SIZE_IN_BYTES## (addr `plusAddr#` off) + mwaWrite# mwa i w + go mwa (i +# 1#) + + in Ubx.do + mwa <- newWordArray# (word2Int# nw +# (word2Int# nb /=# 0#)) + readMSB mwa + go mwa 0# + mwaTrimZeroes# mwa + unsafeFreezeByteArray# mwa -- | Read a BigNat in base-256 big-endian representation from an Addr#. -- @@ -1385,35 +1397,38 @@ bigNatFromAddrLE# sz addr s = -- Null higher limbs are automatically trimmed. bigNatFromAddrBE# :: Word# -> Addr# -> State# s -> (# State# s, BigNat# #) {-# NOINLINE bigNatFromAddrBE# #-} -bigNatFromAddrBE# 0## _ s = (# s, bigNatZero# (# #) #) -bigNatFromAddrBE# sz addr s = +bigNatFromAddrBE# 0## _ = Ubx.pure (bigNatZero# (# #)) +bigNatFromAddrBE# sz addr = let !nw = word2Int# (sz `uncheckedShiftRL#` WORD_SIZE_BYTES_SHIFT#) !nb = sz `and#` WORD_SIZE_BYTES_MASK## - goMSB mwa s + goMSB mwa | 0## <- nb - = s + = Ubx.nop | True - = case wordFromAddrBE# nb addr s of - (# s, w #) -> mwaWrite# mwa nw w s + = Ubx.do + w <- wordFromAddrBE# nb addr + mwaWrite# mwa nw w - go mwa i s + go mwa i | isTrue# (i ==# nw) - = s + = Ubx.nop | k <- nw -# 1# -# i , off <- (k `uncheckedIShiftL#` WORD_SIZE_BYTES_SHIFT#) +# word2Int# nb - = case wordFromAddrBE# WORD_SIZE_IN_BYTES## (addr `plusAddr#` off) s of - (# s, w #) -> case mwaWrite# mwa i w s of - s -> go mwa (i +# 1#) s - - in case newWordArray# (nw +# (word2Int# nb /=# 0#)) s of - (# s, mwa #) -> case goMSB mwa s of - s -> case go mwa 0# s of - s -> case mwaTrimZeroes# mwa s of - s -> unsafeFreezeByteArray# mwa s + = Ubx.do + w <- wordFromAddrBE# WORD_SIZE_IN_BYTES## (addr `plusAddr#` off) + mwaWrite# mwa i w + go mwa (i +# 1#) + + in Ubx.do + mwa <- newWordArray# (nw +# (word2Int# nb /=# 0#)) + goMSB mwa + go mwa 0# + mwaTrimZeroes# mwa + unsafeFreezeByteArray# mwa -- | Read a BigNat in base-256 representation from an Addr#. -- @@ -1440,11 +1455,12 @@ bigNatFromAddr# sz addr _ s = bigNatFromAddrBE# sz addr s -- zero bytes written. bigNatToMutableByteArrayLE# :: BigNat# -> MutableByteArray# s -> Word# -> State# s -> (# State# s, Word# #) {-# NOINLINE bigNatToMutableByteArrayLE# #-} -bigNatToMutableByteArrayLE# a mba moff s0 - | isTrue# (sz ==# 0#) = (# s0, 0## #) - | True = case writeMSB s0 of - (# s1, k #) -> case go 0# s1 of - s2 -> (# s2, k `plusWord#` (int2Word# li `uncheckedShiftL#` WORD_SIZE_BYTES_SHIFT#) #) +bigNatToMutableByteArrayLE# a mba moff + | isTrue# (sz ==# 0#) = Ubx.pure 0## + | True = Ubx.do + k <- writeMSB + go 0# + Ubx.pure (k `plusWord#` (int2Word# li `uncheckedShiftL#` WORD_SIZE_BYTES_SHIFT#)) where !sz = wordArraySize# a !li = sz -# 1# @@ -1452,15 +1468,16 @@ bigNatToMutableByteArrayLE# a mba moff s0 writeMSB = wordToMutableByteArrayLE# (indexWordArray# a li) mba (moff `plusWord#` int2Word# (li `uncheckedIShiftL#` WORD_SIZE_BYTES_SHIFT#)) - go i s + go i | isTrue# (i <# li) , off <- int2Word# i `uncheckedShiftL#` WORD_SIZE_BYTES_SHIFT# , w <- indexWordArray# a i - = case wordWriteMutableByteArrayLE# w mba (moff `plusWord#` off) s of - s -> go (i +# 1#) s + = Ubx.do + wordWriteMutableByteArrayLE# w mba (moff `plusWord#` off) + go (i +# 1#) | True - = s + = Ubx.nop -- | Write a BigNat in base-256 big-endian representation and return the -- number of bytes written. @@ -1470,23 +1487,24 @@ bigNatToMutableByteArrayLE# a mba moff s0 -- zero bytes written. bigNatToMutableByteArrayBE# :: BigNat# -> MutableByteArray# s -> Word# -> State# s -> (# State# s, Word# #) {-# NOINLINE bigNatToMutableByteArrayBE# #-} -bigNatToMutableByteArrayBE# a mba moff s0 - | isTrue# (sz ==# 0#) = (# s0, 0## #) +bigNatToMutableByteArrayBE# a mba moff + | isTrue# (sz ==# 0#) = Ubx.pure 0## | msw <- indexWordArray# a (sz -# 1#) - = case wordToMutableByteArrayBE# msw mba moff s0 of - (# s1, k #) -> case go (sz -# 1#) k s1 of - s2 -> (# s2, k `plusWord#` (int2Word# (sz -# 1#) `uncheckedShiftL#` WORD_SIZE_BYTES_SHIFT#) #) + = Ubx.do + k <- wordToMutableByteArrayBE# msw mba moff + go (sz -# 1#) k + Ubx.pure (k `plusWord#` (int2Word# (sz -# 1#) `uncheckedShiftL#` WORD_SIZE_BYTES_SHIFT#)) where sz = wordArraySize# a - go i c s + go i c | 0# <- i - = s + = Ubx.nop | w <- indexWordArray# a (i -# 1#) - = case wordWriteMutableByteArrayBE# w mba (moff `plusWord#` c) s of - s' -> go (i -# 1#) - (c `plusWord#` WORD_SIZE_IN_BYTES## ) s' + = Ubx.do + wordWriteMutableByteArrayBE# w mba (moff `plusWord#` c) + go (i -# 1#) (c `plusWord#` WORD_SIZE_IN_BYTES## ) -- | Write a BigNat in base-256 representation and return the @@ -1514,34 +1532,36 @@ bigNatToMutableByteArray# a mba off _ s = bigNatToMutableByteArrayBE# a mba off -- Null higher limbs are automatically trimmed. bigNatFromByteArrayLE# :: Word# -> ByteArray# -> Word# -> State# s -> (# State# s, BigNat# #) {-# NOINLINE bigNatFromByteArrayLE# #-} -bigNatFromByteArrayLE# 0## _ _ s = (# s, bigNatZero# (# #) #) -bigNatFromByteArrayLE# sz ba moff s = +bigNatFromByteArrayLE# 0## _ _ = Ubx.pure (bigNatZero# (# #)) +bigNatFromByteArrayLE# sz ba moff = let !nw = sz `uncheckedShiftRL#` WORD_SIZE_BYTES_SHIFT# !nb = sz `and#` WORD_SIZE_BYTES_MASK## - readMSB mwa s + readMSB mwa | 0## <- nb - = s + = Ubx.nop | off <- nw `uncheckedShiftL#` WORD_SIZE_BYTES_SHIFT# = case wordFromByteArrayLE# nb ba (moff `plusWord#` off) of - w -> mwaWrite# mwa (word2Int# nw) w s + w -> mwaWrite# mwa (word2Int# nw) w - go mwa i s + go mwa i | isTrue# (i `eqWord#` nw) - = s + = Ubx.nop | off <- i `uncheckedShiftL#` WORD_SIZE_BYTES_SHIFT# = case wordFromByteArrayLE# WORD_SIZE_IN_BYTES## ba (moff `plusWord#` off) of - w -> case mwaWrite# mwa (word2Int# i) w s of - s -> go mwa (i `plusWord#` 1##) s + w -> Ubx.do + mwaWrite# mwa (word2Int# i) w + go mwa (i `plusWord#` 1##) - in case newWordArray# (word2Int# nw +# (word2Int# nb /=# 0#)) s of - (# s, mwa #) -> case readMSB mwa s of - s -> case go mwa 0## s of - s -> case mwaTrimZeroes# mwa s of - s -> unsafeFreezeByteArray# mwa s + in Ubx.do + mwa <- newWordArray# (word2Int# nw +# (word2Int# nb /=# 0#)) + readMSB mwa + go mwa 0## + mwaTrimZeroes# mwa + unsafeFreezeByteArray# mwa -- | Read a BigNat in base-256 big-endian representation from a ByteArray#. -- @@ -1550,35 +1570,37 @@ bigNatFromByteArrayLE# sz ba moff s = -- Null higher limbs are automatically trimmed. bigNatFromByteArrayBE# :: Word# -> ByteArray# -> Word# -> State# s -> (# State# s, BigNat# #) {-# NOINLINE bigNatFromByteArrayBE# #-} -bigNatFromByteArrayBE# 0## _ _ s = (# s, bigNatZero# (# #) #) -bigNatFromByteArrayBE# sz ba moff s = +bigNatFromByteArrayBE# 0## _ _ = Ubx.pure (bigNatZero# (# #)) +bigNatFromByteArrayBE# sz ba moff = let !nw = sz `uncheckedShiftRL#` WORD_SIZE_BYTES_SHIFT# !nb = sz `and#` WORD_SIZE_BYTES_MASK## - goMSB mwa s + goMSB mwa | 0## <- nb - = s + = Ubx.nop | True = case wordFromByteArrayBE# nb ba moff of - w -> mwaWrite# mwa (word2Int# nw) w s + w -> mwaWrite# mwa (word2Int# nw) w - go mwa i s + go mwa i | isTrue# (i `eqWord#` nw) - = s + = Ubx.nop | k <- nw `minusWord#` 1## `minusWord#` i , off <- (k `uncheckedShiftL#` WORD_SIZE_BYTES_SHIFT#) `plusWord#` nb = case wordFromByteArrayBE# WORD_SIZE_IN_BYTES## ba (moff `plusWord#` off) of - w -> case mwaWrite# mwa (word2Int# i) w s of - s -> go mwa (i `plusWord#` 1##) s - - in case newWordArray# (word2Int# nw +# (word2Int# nb /=# 0#)) s of - (# s, mwa #) -> case goMSB mwa s of - s -> case go mwa 0## s of - s -> case mwaTrimZeroes# mwa s of - s -> unsafeFreezeByteArray# mwa s + w -> Ubx.do + mwaWrite# mwa (word2Int# i) w + go mwa (i `plusWord#` 1##) + + in Ubx.do + mwa <- newWordArray# (word2Int# nw +# (word2Int# nb /=# 0#)) + goMSB mwa + go mwa 0## + mwaTrimZeroes# mwa + unsafeFreezeByteArray# mwa -- | Read a BigNat in base-256 representation from a ByteArray#. -- ===================================== libraries/ghc-internal/src/GHC/Internal/Bignum/Integer.hs ===================================== @@ -7,6 +7,7 @@ {-# LANGUAGE BinaryLiterals #-} {-# LANGUAGE BlockArguments #-} {-# LANGUAGE LambdaCase #-} +{-# LANGUAGE QualifiedDo #-} {-# OPTIONS_GHC -fdefines-known-key-names #-} -- Defines lots of functions that have BuiltinRules @@ -166,6 +167,7 @@ import GHC.Internal.Bignum.Primitives import GHC.Internal.Bignum.BigNat import GHC.Internal.Bignum.Natural import qualified GHC.Internal.Bignum.Backend as Backend +import qualified GHC.Internal.Unboxed.Do as Ubx -- | Arbitrary precision integers. In contrast with fixed-size integral types -- such as 'Int', the 'Integer' type represents the entire infinite range of @@ -1334,8 +1336,9 @@ integerToAddr# (IN n) = bigNatToAddr# n -- byte first (big-endian) if @1#@ or least significant byte first -- (little-endian) if @0#@. integerToAddr :: Integer -> Addr# -> Bool# -> IO Word -integerToAddr a addr e = IO \s -> case integerToAddr# a addr e s of - (# s', w #) -> (# s', W# w #) +integerToAddr a addr e = IO Ubx.do + w <- integerToAddr# a addr e + Ubx.pure (W# w) -- | Read an 'Integer' (without sign) in base-256 representation from an Addr#. -- @@ -1347,9 +1350,9 @@ integerToAddr a addr e = IO \s -> case integerToAddr# a addr e s of -- -- Null higher limbs are automatically trimed. integerFromAddr# :: Word# -> Addr# -> Bool# -> State# s -> (# State# s, Integer #) -integerFromAddr# sz addr e s = - case bigNatFromAddr# sz addr e s of - (# s', n #) -> (# s', integerFromBigNat# n #) +integerFromAddr# sz addr e = Ubx.do + n <- bigNatFromAddr# sz addr e + Ubx.pure (integerFromBigNat# n) -- | Read an 'Integer' (without sign) in base-256 representation from an Addr#. -- @@ -1383,8 +1386,9 @@ integerToMutableByteArray# (IN a) = bigNatToMutableByteArray# a -- byte first (big-endian) if @1#@ or least significant byte first -- (little-endian) if @0#@. integerToMutableByteArray :: Integer -> MutableByteArray# RealWorld -> Word# -> Bool# -> IO Word -integerToMutableByteArray i mba w e = IO \s -> case integerToMutableByteArray# i mba w e s of - (# s', r #) -> (# s', W# r #) +integerToMutableByteArray i mba w e = IO Ubx.do + r <- integerToMutableByteArray# i mba w e + Ubx.pure (W# r) -- | Read an 'Integer' (without sign) in base-256 representation from a ByteArray#. -- @@ -1396,8 +1400,9 @@ integerToMutableByteArray i mba w e = IO \s -> case integerToMutableByteArray# i -- -- Null higher limbs are automatically trimed. integerFromByteArray# :: Word# -> ByteArray# -> Word# -> Bool# -> State# s -> (# State# s, Integer #) -integerFromByteArray# sz ba off e s = case bigNatFromByteArray# sz ba off e s of - (# s', a #) -> (# s', integerFromBigNat# a #) +integerFromByteArray# sz ba off e = Ubx.do + a <- bigNatFromByteArray# sz ba off e + Ubx.pure (integerFromBigNat# a) -- | Read an 'Integer' (without sign) in base-256 representation from a ByteArray#. -- ===================================== libraries/ghc-internal/src/GHC/Internal/Bignum/Natural.hs ===================================== @@ -4,6 +4,7 @@ {-# LANGUAGE UnboxedTuples #-} {-# LANGUAGE BangPatterns #-} {-# LANGUAGE BlockArguments #-} +{-# LANGUAGE QualifiedDo #-} {-# OPTIONS_GHC -fdefines-known-key-names #-} -- Defines lots of functions that have BuiltinRules @@ -121,6 +122,7 @@ import GHC.Internal.Classes import GHC.Internal.Bignum.BigNat import GHC.Internal.Bignum.Primitives +import qualified GHC.Internal.Unboxed.Do as Ubx -- | Natural number -- @@ -656,8 +658,9 @@ naturalToAddr# (NB n) = bigNatToAddr# n -- byte first (big-endian) if @1#@ or least significant byte first -- (little-endian) if @0#@. naturalToAddr :: Natural -> Addr# -> Bool# -> IO Word -naturalToAddr a addr e = IO \s -> case naturalToAddr# a addr e s of - (# s', w #) -> (# s', W# w #) +naturalToAddr a addr e = IO Ubx.do + w <- naturalToAddr# a addr e + Ubx.pure (W# w) -- | Read a Natural in base-256 representation from an Addr#. @@ -670,9 +673,9 @@ naturalToAddr a addr e = IO \s -> case naturalToAddr# a addr e s of -- -- Null higher limbs are automatically trimed. naturalFromAddr# :: Word# -> Addr# -> Bool# -> State# s -> (# State# s, Natural #) -naturalFromAddr# sz addr e s = - case bigNatFromAddr# sz addr e s of - (# s', n #) -> (# s', naturalFromBigNat# n #) +naturalFromAddr# sz addr e = Ubx.do + n <- bigNatFromAddr# sz addr e + Ubx.pure (naturalFromBigNat# n) -- | Read a Natural in base-256 representation from an Addr#. -- @@ -707,8 +710,9 @@ naturalToMutableByteArray# (NB a) = bigNatToMutableByteArray# a -- -- Null higher limbs are automatically trimed. naturalFromByteArray# :: Word# -> ByteArray# -> Word# -> Bool# -> State# s -> (# State# s, Natural #) -naturalFromByteArray# sz ba off e s = case bigNatFromByteArray# sz ba off e s of - (# s', a #) -> (# s', naturalFromBigNat# a #) +naturalFromByteArray# sz ba off e = Ubx.do + a <- bigNatFromByteArray# sz ba off e + Ubx.pure (naturalFromBigNat# a) ===================================== libraries/ghc-internal/src/GHC/Internal/Bignum/Primitives.hs ===================================== @@ -11,6 +11,7 @@ {-# LANGUAGE ScopedTypeVariables #-} {-# LANGUAGE BlockArguments #-} {-# LANGUAGE BinaryLiterals #-} +{-# LANGUAGE QualifiedDo #-} {-# OPTIONS_GHC -fexpose-all-unfoldings #-} module GHC.Internal.Bignum.Primitives @@ -93,6 +94,7 @@ import GHC.Internal.Prim.Exception import GHC.Internal.Prim import GHC.Internal.Types +import qualified GHC.Internal.Unboxed.Do as Ubx ---------------------------------- -- Bool# @@ -322,13 +324,14 @@ wordReverseBits32# x0 = wordReverseBits# x0 wordToAddrLE# :: Word# -> Addr# -> State# s -> (# State# s, Word# #) wordToAddrLE# x addr = go x 0# where - go w c s + go w c | 0## <- w - = (# s, int2Word# c #) + = Ubx.pure (int2Word# c) | True - = case writeWord8OffAddr# addr c (wordToWord8# w) s of - s' -> go (w `uncheckedShiftRL#` 8#) (c +# 1#) s' + = Ubx.do + writeWord8OffAddr# addr c (wordToWord8# w) + go (w `uncheckedShiftRL#` 8#) (c +# 1#) -- | Write a Word to @/addr/@ in base-256 big-endian representation and -- return the number of bytes written. @@ -337,14 +340,15 @@ wordToAddrBE# w addr = go 0# (WORD_SIZE_IN_BITS# -# clz) where !clz = word2Int# (clz# w `and#` (not# 0b0111##)) -- keep complete bytes - go c sh s + go c sh | 0# <- sh - = (# s, int2Word# c #) + = Ubx.pure (int2Word# c) | True , w' <- wordToWord8# (w `uncheckedShiftRL#` (sh -# 8#)) - = case writeWord8OffAddr# addr c w' s of - s' -> go (c +# 1#) (sh -# 8#) s' + = Ubx.do + writeWord8OffAddr# addr c w' + go (c +# 1#) (sh -# 8#) -- | Write a Word to @/addr/@ in base-256 representation and -- return the number of bytes written. @@ -361,53 +365,55 @@ wordToAddr# a addr _ s = wordToAddrBE# a addr s -- -- @'n' is the number of bytes to read. wordFromAddrLE# :: Word# -> Addr# -> State# s -> (# State# s, Word# #) -wordFromAddrLE# n addr s +wordFromAddrLE# n addr -- Optimize when we read a full word | WORD_SIZE_IN_BYTES## <- n - = case readWordOffAddr# addr 0# s of + = Ubx.do + w <- readWordOffAddr# addr 0# #if defined(WORDS_BIGENDIAN) - (# s', w #) -> (# s', wordReverseBytes# w #) + Ubx.pure (wordReverseBytes# w) #else - (# s', w #) -> (# s', w #) + Ubx.pure w #endif -wordFromAddrLE# n addr s0 = go 0## 0# s0 +wordFromAddrLE# n addr = go 0## 0# where - go w c s + go w c | isTrue# (c ==# word2Int# n) - = (# s, w #) + = Ubx.pure w | True - = case readWord8OffAddr# addr c s of - (# s', b #) -> go (w `or#` (word8ToWord# b `uncheckedShiftL#` (c `uncheckedIShiftL#` 3#))) - (c +# 1#) - s' + = Ubx.do + b <- readWord8OffAddr# addr c + go (w `or#` (word8ToWord# b `uncheckedShiftL#` (c `uncheckedIShiftL#` 3#))) + (c +# 1#) -- | Read a Word from @/addr/@ in base-256 big-endian representation. -- -- @'n' is the number of bytes to read. wordFromAddrBE# :: Word# -> Addr# -> State# s -> (# State# s, Word# #) -wordFromAddrBE# n addr s +wordFromAddrBE# n addr -- Optimize when we read a full word | WORD_SIZE_IN_BYTES## <- n - = case readWordOffAddr# addr 0# s of + = Ubx.do + w <- readWordOffAddr# addr 0# #if defined(WORDS_BIGENDIAN) - (# s', w #) -> (# s', w #) + Ubx.pure w #else - (# s', w #) -> (# s', wordReverseBytes# w #) + Ubx.pure (wordReverseBytes# w) #endif -wordFromAddrBE# n addr s0 = go 0## 0# s0 +wordFromAddrBE# n addr = go 0## 0# where - go w c s + go w c | isTrue# (c ==# word2Int# n) - = (# s, w #) + = Ubx.pure w | True - = case readWord8OffAddr# addr c s of - (# s', b #) -> go ((w `uncheckedShiftL#` 8#) `or#` word8ToWord# b) - (c +# 1#) - s' + = Ubx.do + b <- readWord8OffAddr# addr c + go ((w `uncheckedShiftL#` 8#) `or#` word8ToWord# b) + (c +# 1#) -- | Read a Word from @/addr/@ in base-256 representation. -- @@ -447,13 +453,14 @@ wordWriteAddrBE# w addr = writeWordOffAddr# addr 0# wordToMutableByteArrayLE# :: Word# -> MutableByteArray# s -> Word# -> State# s -> (# State# s, Word# #) wordToMutableByteArrayLE# x mba off = go x 0# where - go w c s + go w c | 0## <- w - = (# s, int2Word# c #) + = Ubx.pure (int2Word# c) | True - = case writeWord8Array# mba (word2Int# off +# c) (wordToWord8# w) s of - s' -> go (w `uncheckedShiftRL#` 8#) (c +# 1#) s' + = Ubx.do + writeWord8Array# mba (word2Int# off +# c) (wordToWord8# w) + go (w `uncheckedShiftRL#` 8#) (c +# 1#) -- | Write a Word to @/MutableByteArray/@ in base-256 big-endian representation and -- return the number of bytes written. @@ -464,14 +471,15 @@ wordToMutableByteArrayBE# w mba off = go 0# (WORD_SIZE_IN_BITS# -# clz) where !clz = word2Int# (clz# w `and#` (not# 0b0111##)) -- keep complete bytes - go c sh s + go c sh | 0# <- sh - = (# s, int2Word# c #) + = Ubx.pure (int2Word# c) | True , w' <- wordToWord8# (w `uncheckedShiftRL#` (sh -# 8#)) - = case writeWord8Array# mba (word2Int# off +# c) w' s of - s' -> go (c +# 1#) (sh -# 8#) s' + = Ubx.do + writeWord8Array# mba (word2Int# off +# c) w' + go (c +# 1#) (sh -# 8#) -- | Write a Word to @/MutableByteArray/@ in base-256 representation and -- return the number of bytes written. @@ -568,21 +576,24 @@ wordFromByteArray# a ba off _ = wordFromByteArrayBE# a ba off ---------------------------------- ioVoid :: IO a -> State# RealWorld -> State# RealWorld -ioVoid (IO io) s = case io s of - (# s', _ #) -> s' +ioVoid (IO io) = Ubx.void io ioWord# :: IO Word -> State# RealWorld -> (# State# RealWorld, Word# #) -ioWord# (IO io) s = case io s of - (# s', W# w #) -> (# s', w #) +ioWord# (IO io) = Ubx.do + W# w <- io + Ubx.pure w ioInt# :: IO Int -> State# RealWorld -> (# State# RealWorld, Int# #) -ioInt# (IO io) s = case io s of - (# s', I# i #) -> (# s', i #) +ioInt# (IO io) = Ubx.do + I# i <- io + Ubx.pure i ioBool :: IO Bool -> State# RealWorld -> (# State# RealWorld, Bool# #) -ioBool (IO io) s = case io s of - (# s', False #) -> (# s', 0# #) - (# s', True #) -> (# s', 1# #) +ioBool (IO io) = Ubx.do + b <- io + case b of + False -> Ubx.pure 0# + True -> Ubx.pure 1# ---------------------------------- ===================================== libraries/ghc-internal/src/GHC/Internal/Bignum/WordArray.hs ===================================== @@ -8,7 +8,7 @@ {-# LANGUAGE LambdaCase #-} {-# LANGUAGE PolyKinds #-} {-# LANGUAGE KindSignatures #-} -{-# OPTIONS_GHC -Wno-name-shadowing #-} +{-# LANGUAGE QualifiedDo #-} module GHC.Internal.Bignum.WordArray where @@ -16,6 +16,7 @@ import GHC.Internal.Prim import GHC.Internal.Magic import GHC.Internal.Types import GHC.Internal.Bignum.Primitives +import qualified GHC.Internal.Unboxed.Do as Ubx #include "MachDeps.h" #include "WordSize.h" @@ -44,11 +45,10 @@ withNewWordArray# -> WordArray# withNewWordArray# sz act = case runRW# io of (# _, a #) -> a where - io s = - case newWordArray# sz s of { (# s, mwa #) -> - case act mwa s of { s -> - unsafeFreezeByteArray# mwa s - }} + io = Ubx.do + mwa <- newWordArray# sz + act mwa + unsafeFreezeByteArray# mwa -- | Create two new WordArray# of the given sizes (*in Word#*) and apply the -- action to them before returning them frozen @@ -62,14 +62,13 @@ withNewWordArray2# -> (# WordArray#, WordArray# #) withNewWordArray2# sz1 sz2 act = case runRW# io of (# _, a #) -> a where - io s = - case newWordArray# sz1 s of { (# s, mwa1 #) -> - case newWordArray# sz2 s of { (# s, mwa2 #) -> - case act mwa1 mwa2 s of { s -> - case unsafeFreezeByteArray# mwa1 s of { (# s, wa1 #) -> - case unsafeFreezeByteArray# mwa2 s of { (# s, wa2 #) -> - (# s, (# wa1, wa2 #) #) - }}}}} + io = Ubx.do + mwa1 <- newWordArray# sz1 + mwa2 <- newWordArray# sz2 + act mwa1 mwa2 + wa1 <- unsafeFreezeByteArray# mwa1 + wa2 <- unsafeFreezeByteArray# mwa2 + Ubx.pure (# wa1, wa2 #) -- | Create a new WordArray# newWordArray# :: Int# -> State# s -> (# State# s, MutableWordArray# s #) @@ -81,9 +80,9 @@ withNewWordArrayTrimmed# :: Int# -- ^ Size in Word -> (MutableWordArray# RealWorld -> State# RealWorld -> State# RealWorld) -> WordArray# -withNewWordArrayTrimmed# sz act = withNewWordArray# sz \mwa s -> - case act mwa s of - s' -> mwaTrimZeroes# mwa s' +withNewWordArrayTrimmed# sz act = withNewWordArray# sz \mwa -> Ubx.do + act mwa + mwaTrimZeroes# mwa -- | Create two new WordArray# of the given sizes (*in Word#*), apply the action -- to them, trim their most significant zeroes, then return them frozen @@ -95,10 +94,10 @@ withNewWordArray2Trimmed# -> State# RealWorld -> State# RealWorld) -> (# WordArray#, WordArray# #) -withNewWordArray2Trimmed# sz1 sz2 act = withNewWordArray2# sz1 sz2 \mwa1 mwa2 s -> - case act mwa1 mwa2 s of - s' -> case mwaTrimZeroes# mwa1 s' of - s'' -> mwaTrimZeroes# mwa2 s'' +withNewWordArray2Trimmed# sz1 sz2 act = withNewWordArray2# sz1 sz2 \mwa1 mwa2 -> Ubx.do + act mwa1 mwa2 + mwaTrimZeroes# mwa1 + mwaTrimZeroes# mwa2 -- | Create a new WordArray# of the given size (*in Word#*), apply the action to -- it. If the action returns true#, trim its most significant zeroes, then @@ -109,13 +108,15 @@ withNewWordArrayTrimmedMaybe# -> (# (# #) | WordArray# #) withNewWordArrayTrimmedMaybe# sz act = case runRW# io of (# _, a #) -> a where - io s = - case newWordArray# sz s of - (# s, mwa #) -> case act mwa s of - (# s, 0# #) -> (# s, (# (# #) | #) #) - (# s, _ #) -> case mwaTrimZeroes# mwa s of - s -> case unsafeFreezeByteArray# mwa s of - (# s, ba #) -> (# s, (# | ba #) #) + io = Ubx.do + mwa <- newWordArray# sz + b <- act mwa + case b of + 0# -> Ubx.pure (# (# #) | #) + _ -> Ubx.do + mwaTrimZeroes# mwa + ba <- unsafeFreezeByteArray# mwa + Ubx.pure (# | ba #) -- | Create a WordArray# from two Word# -- @@ -124,9 +125,9 @@ withNewWordArrayTrimmedMaybe# sz act = case runRW# io of (# _, a #) -> a -- l is the least significant word wordArrayFromWord2# :: Word# -> Word# -> WordArray# wordArrayFromWord2# h l = - withNewWordArray# 2# \mwa s -> - case mwaWrite# mwa 0# l s of - s -> mwaWrite# mwa 1# h s + withNewWordArray# 2# \mwa -> Ubx.do + mwaWrite# mwa 0# l + mwaWrite# mwa 1# h -- | Create a WordArray# from one Word# wordArrayFromWord# :: Word# -> WordArray# @@ -143,8 +144,9 @@ wordArraySize# ba = bytesToWords# (sizeofByteArray# ba) -- | Get size in Words mwaSize# :: MutableWordArray# s-> State# s -> (# State# s, Int# #) -mwaSize# mba s = case getSizeofMutableByteArray# mba s of - (# s2, sz #) -> (# s2, bytesToWords# sz #) +mwaSize# mba = Ubx.do + sz <- getSizeofMutableByteArray# mba + Ubx.pure (bytesToWords# sz) -- | Get the last Word (must be non empty!) wordArrayLast# :: WordArray# -> Word# @@ -163,10 +165,10 @@ mwaArrayCopy# dst dstIdx src srcIdx n s -- | Shrink last words of a WordArray mwaShrink# :: MutableByteArray# s -> Int# -> State# s -> State# s -mwaShrink# _mwa 0# s = s -mwaShrink# mwa i s = - case mwaSize# mwa s of - (# s, n #) -> shrinkMutableByteArray# mwa (wordsToBytes# (n -# i)) s +mwaShrink# _mwa 0# = Ubx.nop +mwaShrink# mwa i = Ubx.do + n <- mwaSize# mwa + shrinkMutableByteArray# mwa (wordsToBytes# (n -# i)) -- | Set size mwaSetSize# :: MutableByteArray# s -> Int# -> State# s -> State# s @@ -175,31 +177,35 @@ mwaSetSize# mwa n s = shrinkMutableByteArray# mwa (wordsToBytes# n) s -- | Copy the WordArray into the MWA and shrink the size of MWA to the one of -- the WordArray mwaInitCopyShrink# :: MutableByteArray# s -> WordArray# -> State# s -> State# s -mwaInitCopyShrink# mwa wa s = - case mwaArrayCopy# mwa 0# wa 0# (wordArraySize# wa) s of - s -> mwaSetSize# mwa (wordArraySize# wa) s +mwaInitCopyShrink# mwa wa = Ubx.do + mwaArrayCopy# mwa 0# wa 0# (wordArraySize# wa) + mwaSetSize# mwa (wordArraySize# wa) -- | Trim ending zeroes mwaTrimZeroes# :: MutableByteArray# s -> State# s -> State# s -mwaTrimZeroes# mwa s1 = - case mwaClz mwa s1 of - (# s2, 0# #) -> s2 - (# s2, c #) -> mwaShrink# mwa c s2 +mwaTrimZeroes# mwa = Ubx.do + c <- mwaClz mwa + case c of + 0# -> Ubx.nop + _ -> mwaShrink# mwa c -- | Count leading zero Words mwaClz :: MutableWordArray# s -> State# s -> (# State# s, Int# #) -mwaClz mwa s1 = case mwaSize# mwa s1 of - (# s2,sz #) -> mwaClzAt mwa (sz -# 1#) s2 +mwaClz mwa = Ubx.do + sz <- mwaSize# mwa + mwaClzAt mwa (sz -# 1#) -- | Count leading zero Words starting at given position mwaClzAt :: MutableWordArray# s -> Int# -> State# s -> (# State# s, Int# #) mwaClzAt mwa = go 0# where - go c i s - | isTrue# (i <# 0#) = (# s, c #) - | True = case readWordArray# mwa i s of - (# s', 0## #) -> go (c +# 1#) (i -# 1#) s' - (# s', _ #) -> (# s', c #) + go c i + | isTrue# (i <# 0#) = Ubx.pure c + | True = Ubx.do + w <- readWordArray# mwa i + case w of + 0## -> go (c +# 1#) (i -# 1#) + _ -> Ubx.pure c -- | Count leading zero Words starting at given position waClzAt :: WordArray# -> Int# -> Int# @@ -258,15 +264,16 @@ mwaInitArrayPlusWord :: MutableWordArray# s -> WordArray# -> Word# -> State# s - mwaInitArrayPlusWord mwa wa = go 0# where sz = wordArraySize# wa - go i carry s - | isTrue# (i ># sz) = s - | isTrue# (i ==# sz) = mwaWriteOrShrink mwa carry i s - | 0## <- carry = -- copy higher remaining words and shrink the mwa - case mwaArrayCopy# mwa i wa i (sz -# i) s of - s2 -> mwaShrink# mwa 1# s2 - | True = let !(# l,c #) = addWordC# (indexWordArray# wa i) carry - in case mwaWrite# mwa i l s of - s2 -> go (i +# 1#) (int2Word# c) s2 + go i carry + | isTrue# (i ># sz) = Ubx.nop + | isTrue# (i ==# sz) = mwaWriteOrShrink mwa carry i + | 0## <- carry = Ubx.do -- copy higher remaining words and shrink the mwa + mwaArrayCopy# mwa i wa i (sz -# i) + mwaShrink# mwa 1# + | True = Ubx.do + let !(# l, c #) = addWordC# (indexWordArray# wa i) carry + mwaWrite# mwa i l + go (i +# 1#) (int2Word# c) -- | Write the most-significant Word: -- * if it is 0: shrink the array of 1 Word @@ -277,23 +284,24 @@ mwaWriteOrShrink mwa w i s = mwaWrite# mwa i w s -- | Compute the index of the most-significant Word and write it. mwaWriteMostSignificant :: MutableWordArray# s -> Word# -> State# s -> State# s -mwaWriteMostSignificant mwa w s = - case mwaSize# mwa s of - (# s', sz #) -> mwaWriteOrShrink mwa w (sz -# 1#) s' +mwaWriteMostSignificant mwa w = Ubx.do + sz <- mwaSize# mwa + mwaWriteOrShrink mwa w (sz -# 1#) -- | MutableWordArray <- zipWith op wa1 wa2 -- -- Required output: Size(MutableWordArray) = min Size(wa1) Size(wa2) mwaInitArrayBinOp :: MutableWordArray# s -> WordArray# -> WordArray# -> (Word# -> Word# -> Word#) -> State# s -> State#s -mwaInitArrayBinOp mwa wa wb op s = go 0# s +mwaInitArrayBinOp mwa wa wb op = go 0# where !sz = minI# (wordArraySize# wa) (wordArraySize# wb) - go i s' - | isTrue# (i ==# sz) = s' + go i + | isTrue# (i ==# sz) = Ubx.nop | True = case indexWordArray# wa i `op` indexWordArray# wb i of - v -> case mwaWrite# mwa i v s' of - s'' -> go (i +# 1#) s'' + v -> Ubx.do + mwaWrite# mwa i v + go (i +# 1#) -- | Write an element of the MutableWordArray mwaWrite# :: MutableWordArray# s -> Int# -> Word# -> State# s -> State# s @@ -301,17 +309,19 @@ mwaWrite# = writeWordArray# -- | Fill some part of a MutableWordArray with the given Word# mwaFill# :: MutableWordArray# s -> Word# -> Word# -> Word# -> State# s -> State# s -mwaFill# _ _ _ 0## s = s -mwaFill# mwa v off n s = case mwaWrite# mwa (word2Int# off) v s of - s' -> mwaFill# mwa v (off `plusWord#` 1##) (n `minusWord#` 1##) s' +mwaFill# _ _ _ 0## = Ubx.nop +mwaFill# mwa v off n = Ubx.do + mwaWrite# mwa (word2Int# off) v + mwaFill# mwa v (off `plusWord#` 1##) (n `minusWord#` 1##) -- | Add Word# inplace (a the specified offset) in the mwa with carry propagation. mwaAddInplaceWord# :: MutableWordArray# d -> Int# -> Word# -> State# d -> State# d -mwaAddInplaceWord# _ _ 0## s = s -mwaAddInplaceWord# mwa i y s = case readWordArray# mwa i s of - (# s1, x #) -> let !(# h,l #) = plusWord2# x y - in case mwaWrite# mwa i l s1 of - s2 -> mwaAddInplaceWord# mwa (i +# 1#) h s2 +mwaAddInplaceWord# _ _ 0## = Ubx.nop +mwaAddInplaceWord# mwa i y = Ubx.do + x <- readWordArray# mwa i + let !(# h, l #) = plusWord2# x y + mwaWrite# mwa i l + mwaAddInplaceWord# mwa (i +# 1#) h -- | Sub Word# inplace (at the specified offset) in the mwa with carry -- propagation. @@ -323,43 +333,44 @@ mwaSubInplaceWord# -> Word# -> State# d -> (# State# d, Bool# #) -mwaSubInplaceWord# mwa ii iw s1 = case mwaSize# mwa s1 of - (# is, sz #) -> - let - go _ 0## s = (# s, 1# #) -- no underflow - go i y s - | isTrue# (i >=# sz) = (# s, 0# #) -- underflow - | True = case readWordArray# mwa i s of - (# s1, x #) -> let !(# l,h #) = subWordC# x y - in case mwaWrite# mwa i l s1 of - s2 -> go (i +# 1#) (int2Word# h) s2 - in go ii iw is +mwaSubInplaceWord# mwa ii iw = Ubx.do + sz <- mwaSize# mwa + let + go _ 0## = Ubx.pure 1# -- no underflow + go i y + | isTrue# (i >=# sz) = Ubx.pure 0# -- underflow + | True = Ubx.do + x <- readWordArray# mwa i + let !(# l, h #) = subWordC# x y + mwaWrite# mwa i l + go (i +# 1#) (int2Word# h) + go ii iw -- | Trim `a` of `k` less significant limbs and then compare the result with `b` -- -- "mwa" doesn't need to be trimmed mwaTrimCompare :: Int# -> MutableWordArray# s -> WordArray# -> State# s -> (# State# s, Ordering #) -mwaTrimCompare k mwa wb s1 - | (# s, szA #) <- mwaSize# mwa s1 - , szB <- wordArraySize# wb - = - let - go i s - | isTrue# (i <# 0#) = (# s, EQ #) - | True = case readWordArray# mwa (i +# k) s of - (# s2, ai #) -> - let bi = if isTrue# (i >=# szB) - then 0## - else indexWordArray# wb i - in if | isTrue# (ai `gtWord#` bi) -> (# s2, GT #) - | isTrue# (bi `gtWord#` ai) -> (# s2, LT #) - | True -> go (i -# 1#) s2 +mwaTrimCompare k mwa wb = Ubx.do + szA <- mwaSize# mwa + let + szB = wordArraySize# wb + + go i + | isTrue# (i <# 0#) = Ubx.pure EQ + | True = Ubx.do + ai <- readWordArray# mwa (i +# k) + let bi = if isTrue# (i >=# szB) + then 0## + else indexWordArray# wb i + if | isTrue# (ai `gtWord#` bi) -> Ubx.pure GT + | isTrue# (bi `gtWord#` ai) -> Ubx.pure LT + | True -> go (i -# 1#) szTrimA = szA -# k - in if | isTrue# (szTrimA <# szB) -> (# s, LT #) - | True -> go (szA -# k -# 1#) s + if | isTrue# (szTrimA <# szB) -> Ubx.pure LT + | True -> go (szA -# k -# 1#) -- | Sub array inplace (at the specified offset) in the mwa with carry propagation. @@ -370,12 +381,13 @@ mwaTrimCompare k mwa wb s1 mwaSubInplaceArray :: MutableWordArray# d -> Int# -> WordArray# -> State# d -> (# State# d, Bool# #) mwaSubInplaceArray mwa off wb = go (wordArraySize# wb -# 1#) where - go i s - | isTrue# (i <# 0#) = (# s, 1# #) -- no underflow - | True - = case mwaSubInplaceWord# mwa (off +# i) (indexWordArray# wb i) s of - (# s2, 1# #) -> go (i -# 1#) s2 - (# s2, _ #) -> (# s2, 0# #) -- underflow + go i + | isTrue# (i <# 0#) = Ubx.pure 1# -- no underflow + | True = Ubx.do + b <- mwaSubInplaceWord# mwa (off +# i) (indexWordArray# wb i) + case b of + 1# -> go (i -# 1#) + _ -> Ubx.pure 0# -- underflow -- | Add array inplace (a the specified offset) in the mwa with carry propagation. -- @@ -384,13 +396,13 @@ mwaAddInplaceArray :: MutableWordArray# d -> Int# -> WordArray# -> State# d -> S mwaAddInplaceArray mwa off wb = go 0# 0## where !maxi = wordArraySize# wb - go i c s - | isTrue# (i ==# maxi) = mwaAddInplaceWord# mwa (i +# off) c s - | True - = case readWordArray# mwa (i +# off) s of - (# s, v #) -> case plusWord3# v (indexWordArray# wb i) c of - (# c', v' #) -> case writeWordArray# mwa (i +# off) v' s of - s -> go (i +# 1#) c' s + go i c + | isTrue# (i ==# maxi) = mwaAddInplaceWord# mwa (i +# off) c + | True = Ubx.do + v <- readWordArray# mwa (i +# off) + let !(# c', v' #) = plusWord3# v (indexWordArray# wb i) c + writeWordArray# mwa (i +# off) v' + go (i +# 1#) c' -- | Sub array inplace (at the specified offset) in the mwa with carry propagation. -- @@ -398,35 +410,36 @@ mwaAddInplaceArray mwa off wb = go 0# 0## -- -- Return False# on underflow. mwaSubInplaceMutableArray :: MutableWordArray# d -> Int# -> MutableWordArray# d -> State# d -> (# State# d, Bool# #) -mwaSubInplaceMutableArray mwa off mwb s0 = - case mwaSize# mwb s0 of - (# s1, szB #) -> go (szB -# 1#) s1 +mwaSubInplaceMutableArray mwa off mwb = Ubx.do + szB <- mwaSize# mwb + go (szB -# 1#) where - go i s - | isTrue# (i <# 0#) = (# s, 1# #) -- no underflow - | True - = case readWordArray# mwb i s of - (# s1, bi #) -> case mwaSubInplaceWord# mwa (off +# i) bi s1 of - (# s2, 1# #) -> go (i -# 1#) s2 - (# s2, _ #) -> (# s2, 0# #) -- underflow + go i + | isTrue# (i <# 0#) = Ubx.pure 1# -- no underflow + | True = Ubx.do + bi <- readWordArray# mwb i + b <- mwaSubInplaceWord# mwa (off +# i) bi + case b of + 1# -> go (i -# 1#) + _ -> Ubx.pure 0# -- underflow -- | Sub an array inplace and then trim zeroes -- -- Don't check overflow. The caller must ensure that a>=b mwaSubInplaceArrayTrim :: MutableWordArray# d -> Int# -> WordArray# -> State# d -> State# d -mwaSubInplaceArrayTrim mwa off wb s = - case mwaSubInplaceArray mwa off wb s of - (# s', _ #) -> mwaTrimZeroes# mwa s' +mwaSubInplaceArrayTrim mwa off wb = Ubx.do + _ <- mwaSubInplaceArray mwa off wb + mwaTrimZeroes# mwa -- | Read an indexed Word in the MutableWordArray. If the index is out-of-bound, -- return zero. mwaReadOrZero :: MutableWordArray# s -> Int# -> State# s -> (# State# s, Word# #) -mwaReadOrZero mwa i s = case mwaSize# mwa s of - (# s2, sz #) - | isTrue# (i >=# sz) -> (# s2, 0## #) - | isTrue# (i <# 0#) -> (# s2, 0## #) - | True -> readWordArray# mwa i s2 +mwaReadOrZero mwa i = Ubx.do + sz <- mwaSize# mwa + if | isTrue# (i >=# sz) -> Ubx.pure 0## + | isTrue# (i <# 0#) -> Ubx.pure 0## + | True -> readWordArray# mwa i mwaRead# :: MutableWordArray# s -> Int# -> State# s -> (# State# s, Word# #) mwaRead# = readWordArray# ===================================== libraries/ghc-internal/src/GHC/Internal/Unboxed/Do.hs ===================================== @@ -0,0 +1,152 @@ +{-# LANGUAGE CPP #-} +{-# LANGUAGE NoImplicitPrelude #-} +{-# LANGUAGE MagicHash #-} +{-# LANGUAGE UnboxedTuples #-} +{-# LANGUAGE DataKinds #-} +{-# LANGUAGE PolyKinds #-} +{-# LANGUAGE KindSignatures #-} +{-# LANGUAGE RankNTypes #-} +{-# LANGUAGE FlexibleInstances #-} +{-# LANGUAGE MultiParamTypeClasses #-} +{-# LANGUAGE TypeFamilies #-} +{-# LANGUAGE TypeOperators #-} +{-# LANGUAGE StandaloneKindSignatures #-} + +-- | +-- Module : GHC.Internal.Unboxed.Do +-- Copyright : (c) The University of Glasgow 2026 +-- License : see libraries/ghc-internal/LICENSE +-- +-- Maintainer : ghc-devs@haskell.org +-- Stability : internal +-- Portability : non-portable (GHC Extensions) +-- +-- Do-notation for @State#@-passing code that binds unboxed values. +-- +-- Import this module qualified and use it with @QualifiedDo@: +-- +-- > {-# LANGUAGE QualifiedDo, MagicHash, UnboxedTuples #-} +-- > import qualified GHC.Internal.Unboxed.Do as Ubx +-- > +-- > sumTwo :: MutableByteArray# s -> State# s -> (# State# s, Word# #) +-- > sumTwo mba = Ubx.do +-- > a <- readWordArray# mba 0# -- a :: Word# +-- > b <- readWordArray# mba 1# +-- > writeWordArray# mba 2# (plusWord# a b) -- a unit action is a statement too +-- > Ubx.pure (plusWord# a b) +-- +-- A block has type @State# s -> o@ for any @o@: it can end with a unit +-- action (@State# s -> State# s@) or with an action that returns a value +-- (@State# s -> (# State# s, a #)@). Bound variables can have any +-- representation for which there is a 'Bind#' instance. +-- +-- See #27944. + +module GHC.Internal.Unboxed.Do + ( ST# + , Bind# (..) + , Then# (..) + , nop + , void + ) +where + +import GHC.Internal.Prim +import GHC.Internal.Types + +-- | A @State#@-passing action that returns a value of any representation. +type ST# :: forall (r :: RuntimeRep). Type -> TYPE r -> Type +type ST# s a = State# s -> (# State# s, a #) + +-- | Operations of 'ST#' actions whose result has representation @r@. +-- One instance per representation, so that the bound variable has a fixed one. +-- +-- The continuation result @o@ is arbitrary, so that a block can end with a +-- unit action (@o = State# s@) or with an 'ST#' action. +class Bind# (r :: RuntimeRep) where + (>>=) :: forall s (a :: TYPE r) {r'} (o :: TYPE r'). + ST# s a -> (a -> State# s -> o) -> State# s -> o + + -- | Sequence two actions, discard the result of the first one + then# :: forall s (a :: TYPE r) {r'} (o :: TYPE r'). + ST# s a -> (State# s -> o) -> State# s -> o + + pure :: forall s (a :: TYPE r). a -> ST# s a + +-- | Sequencing. The discarded action @m@ is a unit action +-- (@State# s -> State# s@) or an 'ST#' action. +class Then# (m :: Type) (n :: Type) where + (>>) :: m -> n -> n + +infixl 1 >>=, >> + +-- The `s ~ s'` contexts give instance improvement: the state type of the +-- continuation is inferred from the discarded action. +instance forall s s' r' (o :: TYPE r'). s ~ s' + => Then# (State# s -> State# s) (State# s' -> o) where + {-# INLINE (>>) #-} + m >> k = \s -> case m s of s2 -> k s2 + +instance forall s s' r (a :: TYPE r) r' (o :: TYPE r'). (s ~ s', Bind# r) + => Then# (State# s -> (# State# s, a #)) (State# s' -> o) where + {-# INLINE (>>) #-} + m >> k = m `then#` k + +-- | Unit action that does nothing. +nop :: State# s -> State# s +nop s = s +{-# INLINE nop #-} + +-- | Run an action and discard its result. +void :: forall s r (a :: TYPE r). Bind# r => ST# s a -> State# s -> State# s +void m = m `then#` nop +{-# INLINE void #-} + +#define BIND_INSTANCE(rep) \ +instance Bind# (rep) where { \ + {-# INLINE (>>=) #-} ; \ + m >>= k = \s -> case m s of { (# s2, a #) -> k a s2 } ; \ + {-# INLINE then# #-} ; \ + m `then#` k = \s -> case m s of { (# s2, _ #) -> k s2 } ; \ + {-# INLINE pure #-} ; \ + pure a = \s -> (# s, a #) } + +-- Traditional CPP: no commas in macro arguments, hence the type synonyms. +type TupleRep_WW = TupleRep '[WordRep, WordRep] -- (# Word#, Word# #) +type TupleRep_WI = TupleRep '[WordRep, IntRep] -- (# Word#, Int# #) +type TupleRep_IW = TupleRep '[IntRep, WordRep] -- (# Int#, Word# #) +type TupleRep_II = TupleRep '[IntRep, IntRep] -- (# Int#, Int# #) +type TupleRep_UU = TupleRep '[UnliftedRep, UnliftedRep] -- (# ByteArray#, ByteArray# #) +type TupleRep_UW = TupleRep '[UnliftedRep, WordRep] -- (# ByteArray#, Word# #) +type TupleRep_WU = TupleRep '[WordRep, UnliftedRep] -- (# Word#, ByteArray# #) +type TupleRep_LL = TupleRep '[LiftedRep, LiftedRep] -- (# a, b #) +type TupleRep_LLL = TupleRep '[LiftedRep, LiftedRep, LiftedRep] -- (# a, b, c #) +type SumRep_0U = SumRep '[ZeroBitRep, UnliftedRep] -- (# (# #) | ByteArray# #) + +-- Only the representations used in ghc-internal. Extend as needed (#27944). +BIND_INSTANCE(IntRep) +BIND_INSTANCE(Int8Rep) +BIND_INSTANCE(Int16Rep) +BIND_INSTANCE(Int32Rep) +BIND_INSTANCE(Int64Rep) +BIND_INSTANCE(WordRep) +BIND_INSTANCE(Word8Rep) +BIND_INSTANCE(Word16Rep) +BIND_INSTANCE(Word32Rep) +BIND_INSTANCE(Word64Rep) +BIND_INSTANCE(AddrRep) +BIND_INSTANCE(FloatRep) +BIND_INSTANCE(DoubleRep) +BIND_INSTANCE(LiftedRep) +BIND_INSTANCE(UnliftedRep) +BIND_INSTANCE(ZeroBitRep) +BIND_INSTANCE(TupleRep_WW) +BIND_INSTANCE(TupleRep_WI) +BIND_INSTANCE(TupleRep_IW) +BIND_INSTANCE(TupleRep_II) +BIND_INSTANCE(TupleRep_UU) +BIND_INSTANCE(TupleRep_UW) +BIND_INSTANCE(TupleRep_WU) +BIND_INSTANCE(TupleRep_LL) +BIND_INSTANCE(TupleRep_LLL) +BIND_INSTANCE(SumRep_0U) ===================================== testsuite/tests/qualifieddo/should_compile/all.T ===================================== @@ -2,3 +2,4 @@ setTestOpts(only_ways(['normal'])); test('qdocompile001', normal, compile, ['-v0 -ddump-rn -dsuppress-uniques']) test('qdocompile002', normal, compile, ['-v0']) +test('qdocompile003', normal, compile, ['-O -ddump-simpl -dsuppress-all -dsuppress-uniques -dno-typeable-binds']) ===================================== testsuite/tests/qualifieddo/should_compile/qdocompile003.hs ===================================== @@ -0,0 +1,16 @@ +{-# LANGUAGE QualifiedDo #-} +{-# LANGUAGE MagicHash #-} +{-# LANGUAGE UnboxedTuples #-} + +-- With -O, the block must compile to nested case expressions. +module QDoCompile003 where + +import GHC.Exts +import qualified GHC.Internal.Unboxed.Do as Ubx + +sumTwo :: MutableByteArray# s -> State# s -> (# State# s, Word# #) +sumTwo mba = Ubx.do + a <- readWordArray# mba 0# + b <- readWordArray# mba 1# + writeWordArray# mba 2# (plusWord# a b) + Ubx.pure (plusWord# a b) ===================================== testsuite/tests/qualifieddo/should_compile/qdocompile003.stderr ===================================== @@ -0,0 +1,18 @@ + +==================== Tidy Core ==================== +Result size of Tidy Core + = {terms: 30, types: 44, coercions: 0, joins: 0/0} + +sumTwo + = \ @s mba s1 -> + case readWordArray# mba 0# s1 of { (# ipv, ipv1 #) -> + case readWordArray# mba 1# ipv of { (# ipv2, ipv3 #) -> + case writeWordArray# mba 2# (plusWord# ipv1 ipv3) ipv2 of s2 + { __DEFAULT -> + (# s2, plusWord# ipv1 ipv3 #) + } + } + } + + + ===================================== testsuite/tests/qualifieddo/should_fail/all.T ===================================== @@ -5,3 +5,4 @@ test('qdofail002', normal, compile_fail, ['-v0']) test('qdofail003', normal, compile_fail, ['-v0']) test('qdofail004', normal, compile_fail, ['-v0']) test('qdofail005', normal, compile_fail, ['-v0']) +test('qdofail006', normal, compile_fail, ['-v0']) ===================================== testsuite/tests/qualifieddo/should_fail/qdofail006.hs ===================================== @@ -0,0 +1,18 @@ +{-# LANGUAGE QualifiedDo #-} +{-# LANGUAGE MagicHash #-} +{-# LANGUAGE UnboxedTuples #-} +{-# LANGUAGE PolyKinds #-} +{-# LANGUAGE DataKinds #-} +{-# LANGUAGE RankNTypes #-} + +-- A bound variable must have a fixed runtime representation. +module QDoFail006 where + +import GHC.Exts +import qualified GHC.Internal.Unboxed.Do as Ubx +import GHC.Internal.Unboxed.Do (ST#) + +bad :: forall s r (a :: TYPE r). ST# s a -> ST# s a +bad m = Ubx.do + x <- m + Ubx.pure x ===================================== testsuite/tests/qualifieddo/should_fail/qdofail006.stderr ===================================== @@ -0,0 +1,14 @@ +qdofail006.hs:17:3: error: [GHC-55287] + • The binder of the lambda expression + does not have a fixed runtime representation. + Its type is: + a :: TYPE r + • In a stmt of a qualified 'do' block: x <- m + In the expression: + Ubx.do x <- m + Ubx.pure x + In an equation for ‘bad’: + bad m + = Ubx.do x <- m + Ubx.pure x + ===================================== testsuite/tests/qualifieddo/should_run/all.T ===================================== @@ -9,3 +9,4 @@ test('qdorun004', normal, compile_and_run, ['']) test('qdorun005', [qextra_files], multimod_compile_and_run, ['qdorun005', '']) test('qdorun006', [req_th,qextra_files], multimod_compile_and_run, ['qdorun006', '']) test('qdorun007', [qextra_files], multimod_compile_and_run, ['qdorun007', '']) +test('qdorun008', normal, compile_and_run, ['']) ===================================== testsuite/tests/qualifieddo/should_run/qdorun008.hs ===================================== @@ -0,0 +1,43 @@ +{-# LANGUAGE QualifiedDo #-} +{-# LANGUAGE MagicHash #-} +{-# LANGUAGE UnboxedTuples #-} +{-# LANGUAGE BangPatterns #-} +{-# LANGUAGE MultiWayIf #-} + +module Main where + +import GHC.Exts +import qualified GHC.Internal.Unboxed.Do as Ubx +import GHC.Internal.Unboxed.Do (ST#) + +fill :: MutableByteArray# s -> Word# -> State# s -> State# s -- unit result +fill mba x = Ubx.do + writeWordArray# mba 0# x -- unit action as a statement + n <- getSizeofMutableByteArray# mba -- binds an Int# + writeWordArray# mba 1# (int2Word# n) + +sumAll :: Int# -> ST# s Word# +sumAll n = Ubx.do + mba <- newByteArray# n -- binds an unlifted pointer + fill mba 40## + a <- readWordArray# mba 0# -- binds a Word# + b <- readWordArray# mba 1# + (# c, ov #) <- Ubx.pure (addWordC# a b) -- binds an unboxed tuple + let !(# hi, lo #) = timesWord2# a 2## + Ubx.pure (plusWord# (plusWord# c (int2Word# ov)) (plusWord# hi lo)) + +ordering :: MutableByteArray# s -> ST# s Ordering -- lifted result +ordering mba = Ubx.do + a <- readWordArray# mba 0# + b <- readWordArray# mba 1# + if | isTrue# (ltWord# a b) -> Ubx.pure LT + | isTrue# (gtWord# a b) -> Ubx.pure GT + | True -> Ubx.pure EQ + +main :: IO () +main = do + print (W# (case runRW# (sumAll 16#) of (# _, w #) -> w)) + print (case runRW# (\s -> case newByteArray# 16# s of + (# s1, mba #) -> case fill mba 5## s1 of + s2 -> ordering mba s2) of + (# _, o #) -> o) ===================================== testsuite/tests/qualifieddo/should_run/qdorun008.stdout ===================================== @@ -0,0 +1,2 @@ +136 +LT View it on GitLab: https://gitlab.haskell.org/ghc/ghc/-/compare/6bbca56943ef68ba32520bcf8712a8f... -- View it on GitLab: https://gitlab.haskell.org/ghc/ghc/-/compare/6bbca56943ef68ba32520bcf8712a8f... You're receiving this email because of your account on gitlab.haskell.org. Manage all notifications: https://gitlab.haskell.org/-/profile/notifications | Help: https://gitlab.haskell.org/help