... | @@ -20,8 +20,38 @@ The other implementation currently available is `integer-simple`, which uses a s |
... | @@ -20,8 +20,38 @@ The other implementation currently available is `integer-simple`, which uses a s |
|
All Integer implementations should export the same set of types and functions from `GHC.Integer` (within whatever `integer` package you are using). These exports are used by the `base` package. However, all of these types and functions must actually be defined in `GHC.Integer.Type`, so that GHC knows where to find them.
|
|
All Integer implementations should export the same set of types and functions from `GHC.Integer` (within whatever `integer` package you are using). These exports are used by the `base` package. However, all of these types and functions must actually be defined in `GHC.Integer.Type`, so that GHC knows where to find them.
|
|
Specifically, the interface is this:
|
|
Specifically, the interface is this:
|
|
|
|
|
|
|
|
|
|
```
|
|
```
|
|
dataIntegermkInteger::Bool-- True <=> non-negative->[Int]-- Absolute value in 31 bit chunks, least significant first-- ideally these would be Words rather than Ints, but-- we don't have Word available at the moment. (why?)->IntegersmallInteger::Int#->IntegerintegerToInt::Integer->Int#wordToInteger::Word#->IntegerintegerToWord::Integer->Word#-- And similarly for Int64#, Word64# on 64-bitfloatFromInteger::Integer->Float#decodeFloatInteger::Float#->(#Integer,Int##)encodeFloatInteger::Integer->Int#->Float#-- And similarly DoubleplusInteger::Integer->Integer->Integer-- And similarly: minusInteger, timesInteger, negateInteger,-- eqInteger, neqInteger, absInteger, signumInteger,-- leInteger, gtInteger, ltInteger, geInteger, compareInteger,-- divModInteger, quotRemInteger, quotInteger, remInteger,-- andInteger, orInteger, xorInteger, complementInteger,-- shiftLInteger, shiftRInteger,-- hashInteger,
|
|
data Integer
|
|
|
|
|
|
|
|
mkInteger :: Bool -- True <=> non-negative
|
|
|
|
-> [Int] -- Absolute value in 31 bit chunks, least significant first
|
|
|
|
-- ideally these would be Words rather than Ints, but
|
|
|
|
-- we don't have Word available at the moment. (why?)
|
|
|
|
-> Integer
|
|
|
|
|
|
|
|
smallInteger :: Int# -> Integer
|
|
|
|
integerToInt :: Integer -> Int#
|
|
|
|
|
|
|
|
wordToInteger :: Word# -> Integer
|
|
|
|
integerToWord :: Integer -> Word#
|
|
|
|
|
|
|
|
-- And similarly for Int64#, Word64# on 64-bit
|
|
|
|
|
|
|
|
floatFromInteger :: Integer -> Float#
|
|
|
|
decodeFloatInteger :: Float# -> (# Integer, Int# #)
|
|
|
|
encodeFloatInteger :: Integer -> Int# -> Float#
|
|
|
|
|
|
|
|
-- And similarly Double
|
|
|
|
|
|
|
|
plusInteger :: Integer -> Integer -> Integer
|
|
|
|
-- And similarly: minusInteger, timesInteger, negateInteger,
|
|
|
|
-- eqInteger, neqInteger, absInteger, signumInteger,
|
|
|
|
-- leInteger, gtInteger, ltInteger, geInteger, compareInteger,
|
|
|
|
-- divModInteger, quotRemInteger, quotInteger, remInteger,
|
|
|
|
-- andInteger, orInteger, xorInteger, complementInteger,
|
|
|
|
-- shiftLInteger, shiftRInteger,
|
|
|
|
-- hashInteger,
|
|
```
|
|
```
|
|
|
|
|
|
## How Integer is handled inside GHC
|
|
## How Integer is handled inside GHC
|
... | @@ -42,7 +72,8 @@ dataIntegermkInteger::Bool-- True <=> non-negative->[Int]-- Absolute value in 31 |
... | @@ -42,7 +72,8 @@ dataIntegermkInteger::Bool-- True <=> non-negative->[Int]-- Absolute value in 31 |
|
instance Integral Integer where
|
|
instance Integral Integer where
|
|
toInteger n = n
|
|
toInteger n = n
|
|
|
|
|
|
{-# INLINE quot #-}_`quot`0= divZeroError
|
|
{-# INLINE quot #-}
|
|
|
|
_ `quot` 0 = divZeroError
|
|
n `quot` d = n `quotInteger` d
|
|
n `quot` d = n `quotInteger` d
|
|
```
|
|
```
|
|
|
|
|
... | @@ -64,16 +95,25 @@ dataIntegermkInteger::Bool-- True <=> non-negative->[Int]-- Absolute value in 31 |
... | @@ -64,16 +95,25 @@ dataIntegermkInteger::Bool-- True <=> non-negative->[Int]-- Absolute value in 31 |
|
|
|
|
|
- **Representing integers**. We stick to the `LitInteger` representation (which hides the concrete representation) as late as possible in the compiler. In particular, it's important that the `LitInteger` representation is used in unfoldings in interface files, so that constant folding can happen on expressions that get inlined.
|
|
- **Representing integers**. We stick to the `LitInteger` representation (which hides the concrete representation) as late as possible in the compiler. In particular, it's important that the `LitInteger` representation is used in unfoldings in interface files, so that constant folding can happen on expressions that get inlined.
|
|
|
|
|
|
|
|
>
|
|
>
|
|
>
|
|
> We finally convert `LitInteger` to a proper core representation of Integer in [compiler/coreSyn/CorePrep.lhs](/trac/ghc/browser/ghc/compiler/coreSyn/CorePrep.lhs), which looks up the Id for `mkInteger` and uses it to build an expression like `mkInteger True [123, 456]` (where the `Bool` represents the sign, and the list of `Int`s are 31 bit chunks of the absolute value from lowest to highest).
|
|
> We finally convert `LitInteger` to a proper core representation of Integer in [compiler/coreSyn/CorePrep.lhs](/trac/ghc/browser/ghc/compiler/coreSyn/CorePrep.lhs), which looks up the Id for `mkInteger` and uses it to build an expression like `mkInteger True [123, 456]` (where the `Bool` represents the sign, and the list of `Int`s are 31 bit chunks of the absolute value from lowest to highest).
|
|
|
|
>
|
|
|
|
>
|
|
|
|
|
|
|
|
>
|
|
>
|
|
>
|
|
> However, there is a special case for `Integer`s that are within the range of `Int` when the `integer-gmp` implementation is being used; in that case, we use the `S#` constructor (via `integerGmpSDataCon` in [compiler/prelude/TysWiredIn.lhs](/trac/ghc/browser/ghc/compiler/prelude/TysWiredIn.lhs)) to break the abstraction and directly create the datastructure.
|
|
> However, there is a special case for `Integer`s that are within the range of `Int` when the `integer-gmp` implementation is being used; in that case, we use the `S#` constructor (via `integerGmpSDataCon` in [compiler/prelude/TysWiredIn.lhs](/trac/ghc/browser/ghc/compiler/prelude/TysWiredIn.lhs)) to break the abstraction and directly create the datastructure.
|
|
|
|
>
|
|
|
|
>
|
|
|
|
|
|
- **Don't inline integer functions**. Most of the functions in the Integer implementation in the `integer` package are marked `NOINLINE`. For example in `integer-gmp` we have
|
|
- **Don't inline integer functions**. Most of the functions in the Integer implementation in the `integer` package are marked `NOINLINE`. For example in `integer-gmp` we have
|
|
|
|
|
|
```
|
|
```
|
|
plusInteger::Integer->Integer->IntegerplusInteger(S# i1)(S# i2)=...plusInteger(S# i1)(J# j1 j2)=...-- ...two more cases...
|
|
plusInteger :: Integer -> Integer -> Integer
|
|
|
|
plusInteger (S# i1) (S# i2) = ...
|
|
|
|
plusInteger (S# i1) (J# j1 j2) = ...
|
|
|
|
-- ...two more cases...
|
|
```
|
|
```
|
|
|
|
|
|
Not only is this a big function to inline, but inlining it typically does no good because the representation of literals is abstact, so no pattern-matching cancellation happens. And even if you have `(a+b+c)`, the conditionals mean that no cancellation happens, or you get an exponential code explosion! |
|
Not only is this a big function to inline, but inlining it typically does no good because the representation of literals is abstact, so no pattern-matching cancellation happens. And even if you have `(a+b+c)`, the conditionals mean that no cancellation happens, or you get an exponential code explosion! |