Remove from `base` obsolete CPP for `integer-gmp`
[ghc.git] / libraries / base / Data / Bits.hs
1 {-# LANGUAGE Trustworthy #-}
2 {-# LANGUAGE CPP, NoImplicitPrelude, BangPatterns, MagicHash #-}
3
4 -----------------------------------------------------------------------------
5 -- |
6 -- Module : Data.Bits
7 -- Copyright : (c) The University of Glasgow 2001
8 -- License : BSD-style (see the file libraries/base/LICENSE)
9 --
10 -- Maintainer : libraries@haskell.org
11 -- Stability : experimental
12 -- Portability : portable
13 --
14 -- This module defines bitwise operations for signed and unsigned
15 -- integers. Instances of the class 'Bits' for the 'Int' and
16 -- 'Integer' types are available from this module, and instances for
17 -- explicitly sized integral types are available from the
18 -- "Data.Int" and "Data.Word" modules.
19 --
20 -----------------------------------------------------------------------------
21
22 module Data.Bits (
23 Bits(
24 (.&.), (.|.), xor,
25 complement,
26 shift,
27 rotate,
28 zeroBits,
29 bit,
30 setBit,
31 clearBit,
32 complementBit,
33 testBit,
34 bitSizeMaybe,
35 bitSize,
36 isSigned,
37 shiftL, shiftR,
38 unsafeShiftL, unsafeShiftR,
39 rotateL, rotateR,
40 popCount
41 ),
42 FiniteBits(
43 finiteBitSize,
44 countLeadingZeros,
45 countTrailingZeros
46 ),
47
48 bitDefault,
49 testBitDefault,
50 popCountDefault,
51 toIntegralSized
52 ) where
53
54 -- Defines the @Bits@ class containing bit-based operations.
55 -- See library document for details on the semantics of the
56 -- individual operations.
57
58 #include "MachDeps.h"
59
60 import Data.Maybe
61 import GHC.Enum
62 import GHC.Num
63 import GHC.Base
64 import GHC.Real
65
66 infixl 8 `shift`, `rotate`, `shiftL`, `shiftR`, `rotateL`, `rotateR`
67 infixl 7 .&.
68 infixl 6 `xor`
69 infixl 5 .|.
70
71 {-# DEPRECATED bitSize "Use 'bitSizeMaybe' or 'finiteBitSize' instead" #-} -- deprecated in 7.8
72
73 -- | The 'Bits' class defines bitwise operations over integral types.
74 --
75 -- * Bits are numbered from 0 with bit 0 being the least
76 -- significant bit.
77 class Eq a => Bits a where
78 {-# MINIMAL (.&.), (.|.), xor, complement,
79 (shift | (shiftL, shiftR)),
80 (rotate | (rotateL, rotateR)),
81 bitSize, bitSizeMaybe, isSigned, testBit, bit, popCount #-}
82
83 -- | Bitwise \"and\"
84 (.&.) :: a -> a -> a
85
86 -- | Bitwise \"or\"
87 (.|.) :: a -> a -> a
88
89 -- | Bitwise \"xor\"
90 xor :: a -> a -> a
91
92 {-| Reverse all the bits in the argument -}
93 complement :: a -> a
94
95 {-| @'shift' x i@ shifts @x@ left by @i@ bits if @i@ is positive,
96 or right by @-i@ bits otherwise.
97 Right shifts perform sign extension on signed number types;
98 i.e. they fill the top bits with 1 if the @x@ is negative
99 and with 0 otherwise.
100
101 An instance can define either this unified 'shift' or 'shiftL' and
102 'shiftR', depending on which is more convenient for the type in
103 question. -}
104 shift :: a -> Int -> a
105
106 x `shift` i | i<0 = x `shiftR` (-i)
107 | i>0 = x `shiftL` i
108 | otherwise = x
109
110 {-| @'rotate' x i@ rotates @x@ left by @i@ bits if @i@ is positive,
111 or right by @-i@ bits otherwise.
112
113 For unbounded types like 'Integer', 'rotate' is equivalent to 'shift'.
114
115 An instance can define either this unified 'rotate' or 'rotateL' and
116 'rotateR', depending on which is more convenient for the type in
117 question. -}
118 rotate :: a -> Int -> a
119
120 x `rotate` i | i<0 = x `rotateR` (-i)
121 | i>0 = x `rotateL` i
122 | otherwise = x
123
124 {-
125 -- Rotation can be implemented in terms of two shifts, but care is
126 -- needed for negative values. This suggested implementation assumes
127 -- 2's-complement arithmetic. It is commented out because it would
128 -- require an extra context (Ord a) on the signature of 'rotate'.
129 x `rotate` i | i<0 && isSigned x && x<0
130 = let left = i+bitSize x in
131 ((x `shift` i) .&. complement ((-1) `shift` left))
132 .|. (x `shift` left)
133 | i<0 = (x `shift` i) .|. (x `shift` (i+bitSize x))
134 | i==0 = x
135 | i>0 = (x `shift` i) .|. (x `shift` (i-bitSize x))
136 -}
137
138 -- | 'zeroBits' is the value with all bits unset.
139 --
140 -- The following laws ought to hold (for all valid bit indices @/n/@):
141 --
142 -- * @'clearBit' 'zeroBits' /n/ == 'zeroBits'@
143 -- * @'setBit' 'zeroBits' /n/ == 'bit' /n/@
144 -- * @'testBit' 'zeroBits' /n/ == False@
145 -- * @'popCount' 'zeroBits' == 0@
146 --
147 -- This method uses @'clearBit' ('bit' 0) 0@ as its default
148 -- implementation (which ought to be equivalent to 'zeroBits' for
149 -- types which possess a 0th bit).
150 --
151 -- @since 4.7.0.0
152 zeroBits :: a
153 zeroBits = clearBit (bit 0) 0
154
155 -- | @bit /i/@ is a value with the @/i/@th bit set and all other bits clear.
156 --
157 -- Can be implemented using `bitDefault' if @a@ is also an
158 -- instance of 'Num'.
159 --
160 -- See also 'zeroBits'.
161 bit :: Int -> a
162
163 -- | @x \`setBit\` i@ is the same as @x .|. bit i@
164 setBit :: a -> Int -> a
165
166 -- | @x \`clearBit\` i@ is the same as @x .&. complement (bit i)@
167 clearBit :: a -> Int -> a
168
169 -- | @x \`complementBit\` i@ is the same as @x \`xor\` bit i@
170 complementBit :: a -> Int -> a
171
172 -- | Return 'True' if the @n@th bit of the argument is 1
173 --
174 -- Can be implemented using `testBitDefault' if @a@ is also an
175 -- instance of 'Num'.
176 testBit :: a -> Int -> Bool
177
178 {-| Return the number of bits in the type of the argument. The actual
179 value of the argument is ignored. Returns Nothing
180 for types that do not have a fixed bitsize, like 'Integer'.
181
182 @since 4.7.0.0
183 -}
184 bitSizeMaybe :: a -> Maybe Int
185
186 {-| Return the number of bits in the type of the argument. The actual
187 value of the argument is ignored. The function 'bitSize' is
188 undefined for types that do not have a fixed bitsize, like 'Integer'.
189
190 Default implementation based upon 'bitSizeMaybe' provided since
191 4.12.0.0.
192 -}
193 bitSize :: a -> Int
194 bitSize b = fromMaybe (error "bitSize is undefined") (bitSizeMaybe b)
195
196 {-| Return 'True' if the argument is a signed type. The actual
197 value of the argument is ignored -}
198 isSigned :: a -> Bool
199
200 {-# INLINE setBit #-}
201 {-# INLINE clearBit #-}
202 {-# INLINE complementBit #-}
203 x `setBit` i = x .|. bit i
204 x `clearBit` i = x .&. complement (bit i)
205 x `complementBit` i = x `xor` bit i
206
207 {-| Shift the argument left by the specified number of bits
208 (which must be non-negative).
209
210 An instance can define either this and 'shiftR' or the unified
211 'shift', depending on which is more convenient for the type in
212 question. -}
213 shiftL :: a -> Int -> a
214 {-# INLINE shiftL #-}
215 x `shiftL` i = x `shift` i
216
217 {-| Shift the argument left by the specified number of bits. The
218 result is undefined for negative shift amounts and shift amounts
219 greater or equal to the 'bitSize'.
220
221 Defaults to 'shiftL' unless defined explicitly by an instance.
222
223 @since 4.5.0.0 -}
224 unsafeShiftL :: a -> Int -> a
225 {-# INLINE unsafeShiftL #-}
226 x `unsafeShiftL` i = x `shiftL` i
227
228 {-| Shift the first argument right by the specified number of bits. The
229 result is undefined for negative shift amounts and shift amounts
230 greater or equal to the 'bitSize'.
231
232 Right shifts perform sign extension on signed number types;
233 i.e. they fill the top bits with 1 if the @x@ is negative
234 and with 0 otherwise.
235
236 An instance can define either this and 'shiftL' or the unified
237 'shift', depending on which is more convenient for the type in
238 question. -}
239 shiftR :: a -> Int -> a
240 {-# INLINE shiftR #-}
241 x `shiftR` i = x `shift` (-i)
242
243 {-| Shift the first argument right by the specified number of bits, which
244 must be non-negative and smaller than the number of bits in the type.
245
246 Right shifts perform sign extension on signed number types;
247 i.e. they fill the top bits with 1 if the @x@ is negative
248 and with 0 otherwise.
249
250 Defaults to 'shiftR' unless defined explicitly by an instance.
251
252 @since 4.5.0.0 -}
253 unsafeShiftR :: a -> Int -> a
254 {-# INLINE unsafeShiftR #-}
255 x `unsafeShiftR` i = x `shiftR` i
256
257 {-| Rotate the argument left by the specified number of bits
258 (which must be non-negative).
259
260 An instance can define either this and 'rotateR' or the unified
261 'rotate', depending on which is more convenient for the type in
262 question. -}
263 rotateL :: a -> Int -> a
264 {-# INLINE rotateL #-}
265 x `rotateL` i = x `rotate` i
266
267 {-| Rotate the argument right by the specified number of bits
268 (which must be non-negative).
269
270 An instance can define either this and 'rotateL' or the unified
271 'rotate', depending on which is more convenient for the type in
272 question. -}
273 rotateR :: a -> Int -> a
274 {-# INLINE rotateR #-}
275 x `rotateR` i = x `rotate` (-i)
276
277 {-| Return the number of set bits in the argument. This number is
278 known as the population count or the Hamming weight.
279
280 Can be implemented using `popCountDefault' if @a@ is also an
281 instance of 'Num'.
282
283 @since 4.5.0.0 -}
284 popCount :: a -> Int
285
286 -- |The 'FiniteBits' class denotes types with a finite, fixed number of bits.
287 --
288 -- @since 4.7.0.0
289 class Bits b => FiniteBits b where
290 -- | Return the number of bits in the type of the argument.
291 -- The actual value of the argument is ignored. Moreover, 'finiteBitSize'
292 -- is total, in contrast to the deprecated 'bitSize' function it replaces.
293 --
294 -- @
295 -- 'finiteBitSize' = 'bitSize'
296 -- 'bitSizeMaybe' = 'Just' . 'finiteBitSize'
297 -- @
298 --
299 -- @since 4.7.0.0
300 finiteBitSize :: b -> Int
301
302 -- | Count number of zero bits preceding the most significant set bit.
303 --
304 -- @
305 -- 'countLeadingZeros' ('zeroBits' :: a) = finiteBitSize ('zeroBits' :: a)
306 -- @
307 --
308 -- 'countLeadingZeros' can be used to compute log base 2 via
309 --
310 -- @
311 -- logBase2 x = 'finiteBitSize' x - 1 - 'countLeadingZeros' x
312 -- @
313 --
314 -- Note: The default implementation for this method is intentionally
315 -- naive. However, the instances provided for the primitive
316 -- integral types are implemented using CPU specific machine
317 -- instructions.
318 --
319 -- @since 4.8.0.0
320 countLeadingZeros :: b -> Int
321 countLeadingZeros x = (w-1) - go (w-1)
322 where
323 go i | i < 0 = i -- no bit set
324 | testBit x i = i
325 | otherwise = go (i-1)
326
327 w = finiteBitSize x
328
329 -- | Count number of zero bits following the least significant set bit.
330 --
331 -- @
332 -- 'countTrailingZeros' ('zeroBits' :: a) = finiteBitSize ('zeroBits' :: a)
333 -- 'countTrailingZeros' . 'negate' = 'countTrailingZeros'
334 -- @
335 --
336 -- The related
337 -- <http://en.wikipedia.org/wiki/Find_first_set find-first-set operation>
338 -- can be expressed in terms of 'countTrailingZeros' as follows
339 --
340 -- @
341 -- findFirstSet x = 1 + 'countTrailingZeros' x
342 -- @
343 --
344 -- Note: The default implementation for this method is intentionally
345 -- naive. However, the instances provided for the primitive
346 -- integral types are implemented using CPU specific machine
347 -- instructions.
348 --
349 -- @since 4.8.0.0
350 countTrailingZeros :: b -> Int
351 countTrailingZeros x = go 0
352 where
353 go i | i >= w = i
354 | testBit x i = i
355 | otherwise = go (i+1)
356
357 w = finiteBitSize x
358
359
360 -- The defaults below are written with lambdas so that e.g.
361 -- bit = bitDefault
362 -- is fully applied, so inlining will happen
363
364 -- | Default implementation for 'bit'.
365 --
366 -- Note that: @bitDefault i = 1 `shiftL` i@
367 --
368 -- @since 4.6.0.0
369 bitDefault :: (Bits a, Num a) => Int -> a
370 bitDefault = \i -> 1 `shiftL` i
371 {-# INLINE bitDefault #-}
372
373 -- | Default implementation for 'testBit'.
374 --
375 -- Note that: @testBitDefault x i = (x .&. bit i) /= 0@
376 --
377 -- @since 4.6.0.0
378 testBitDefault :: (Bits a, Num a) => a -> Int -> Bool
379 testBitDefault = \x i -> (x .&. bit i) /= 0
380 {-# INLINE testBitDefault #-}
381
382 -- | Default implementation for 'popCount'.
383 --
384 -- This implementation is intentionally naive. Instances are expected to provide
385 -- an optimized implementation for their size.
386 --
387 -- @since 4.6.0.0
388 popCountDefault :: (Bits a, Num a) => a -> Int
389 popCountDefault = go 0
390 where
391 go !c 0 = c
392 go c w = go (c+1) (w .&. (w - 1)) -- clear the least significant
393 {-# INLINABLE popCountDefault #-}
394
395
396 -- | Interpret 'Bool' as 1-bit bit-field
397 --
398 -- @since 4.7.0.0
399 instance Bits Bool where
400 (.&.) = (&&)
401
402 (.|.) = (||)
403
404 xor = (/=)
405
406 complement = not
407
408 shift x 0 = x
409 shift _ _ = False
410
411 rotate x _ = x
412
413 bit 0 = True
414 bit _ = False
415
416 testBit x 0 = x
417 testBit _ _ = False
418
419 bitSizeMaybe _ = Just 1
420
421 bitSize _ = 1
422
423 isSigned _ = False
424
425 popCount False = 0
426 popCount True = 1
427
428 -- | @since 4.7.0.0
429 instance FiniteBits Bool where
430 finiteBitSize _ = 1
431 countTrailingZeros x = if x then 0 else 1
432 countLeadingZeros x = if x then 0 else 1
433
434 -- | @since 2.01
435 instance Bits Int where
436 {-# INLINE shift #-}
437 {-# INLINE bit #-}
438 {-# INLINE testBit #-}
439
440 zeroBits = 0
441
442 bit = bitDefault
443
444 testBit = testBitDefault
445
446 (I# x#) .&. (I# y#) = I# (x# `andI#` y#)
447 (I# x#) .|. (I# y#) = I# (x# `orI#` y#)
448 (I# x#) `xor` (I# y#) = I# (x# `xorI#` y#)
449 complement (I# x#) = I# (notI# x#)
450 (I# x#) `shift` (I# i#)
451 | isTrue# (i# >=# 0#) = I# (x# `iShiftL#` i#)
452 | otherwise = I# (x# `iShiftRA#` negateInt# i#)
453 (I# x#) `shiftL` (I# i#) = I# (x# `iShiftL#` i#)
454 (I# x#) `unsafeShiftL` (I# i#) = I# (x# `uncheckedIShiftL#` i#)
455 (I# x#) `shiftR` (I# i#) = I# (x# `iShiftRA#` i#)
456 (I# x#) `unsafeShiftR` (I# i#) = I# (x# `uncheckedIShiftRA#` i#)
457
458 {-# INLINE rotate #-} -- See Note [Constant folding for rotate]
459 (I# x#) `rotate` (I# i#) =
460 I# ((x# `uncheckedIShiftL#` i'#) `orI#` (x# `uncheckedIShiftRL#` (wsib -# i'#)))
461 where
462 !i'# = i# `andI#` (wsib -# 1#)
463 !wsib = WORD_SIZE_IN_BITS# {- work around preprocessor problem (??) -}
464 bitSizeMaybe i = Just (finiteBitSize i)
465 bitSize i = finiteBitSize i
466
467 popCount (I# x#) = I# (word2Int# (popCnt# (int2Word# x#)))
468
469 isSigned _ = True
470
471 -- | @since 4.6.0.0
472 instance FiniteBits Int where
473 finiteBitSize _ = WORD_SIZE_IN_BITS
474 countLeadingZeros (I# x#) = I# (word2Int# (clz# (int2Word# x#)))
475 countTrailingZeros (I# x#) = I# (word2Int# (ctz# (int2Word# x#)))
476
477 -- | @since 2.01
478 instance Bits Word where
479 {-# INLINE shift #-}
480 {-# INLINE bit #-}
481 {-# INLINE testBit #-}
482
483 (W# x#) .&. (W# y#) = W# (x# `and#` y#)
484 (W# x#) .|. (W# y#) = W# (x# `or#` y#)
485 (W# x#) `xor` (W# y#) = W# (x# `xor#` y#)
486 complement (W# x#) = W# (x# `xor#` mb#)
487 where !(W# mb#) = maxBound
488 (W# x#) `shift` (I# i#)
489 | isTrue# (i# >=# 0#) = W# (x# `shiftL#` i#)
490 | otherwise = W# (x# `shiftRL#` negateInt# i#)
491 (W# x#) `shiftL` (I# i#) = W# (x# `shiftL#` i#)
492 (W# x#) `unsafeShiftL` (I# i#) = W# (x# `uncheckedShiftL#` i#)
493 (W# x#) `shiftR` (I# i#) = W# (x# `shiftRL#` i#)
494 (W# x#) `unsafeShiftR` (I# i#) = W# (x# `uncheckedShiftRL#` i#)
495 (W# x#) `rotate` (I# i#)
496 | isTrue# (i'# ==# 0#) = W# x#
497 | otherwise = W# ((x# `uncheckedShiftL#` i'#) `or#` (x# `uncheckedShiftRL#` (wsib -# i'#)))
498 where
499 !i'# = i# `andI#` (wsib -# 1#)
500 !wsib = WORD_SIZE_IN_BITS# {- work around preprocessor problem (??) -}
501 bitSizeMaybe i = Just (finiteBitSize i)
502 bitSize i = finiteBitSize i
503 isSigned _ = False
504 popCount (W# x#) = I# (word2Int# (popCnt# x#))
505 bit = bitDefault
506 testBit = testBitDefault
507
508 -- | @since 4.6.0.0
509 instance FiniteBits Word where
510 finiteBitSize _ = WORD_SIZE_IN_BITS
511 countLeadingZeros (W# x#) = I# (word2Int# (clz# x#))
512 countTrailingZeros (W# x#) = I# (word2Int# (ctz# x#))
513
514 -- | @since 2.01
515 instance Bits Integer where
516 (.&.) = andInteger
517 (.|.) = orInteger
518 xor = xorInteger
519 complement = complementInteger
520 shift x i@(I# i#) | i >= 0 = shiftLInteger x i#
521 | otherwise = shiftRInteger x (negateInt# i#)
522 testBit x (I# i) = testBitInteger x i
523 zeroBits = 0
524
525 bit (I# i#) = bitInteger i#
526 popCount x = I# (popCountInteger x)
527
528 rotate x i = shift x i -- since an Integer never wraps around
529
530 bitSizeMaybe _ = Nothing
531 bitSize _ = errorWithoutStackTrace "Data.Bits.bitSize(Integer)"
532 isSigned _ = True
533
534 -- | @since 4.8.0
535 instance Bits Natural where
536 (.&.) = andNatural
537 (.|.) = orNatural
538 xor = xorNatural
539 complement _ = errorWithoutStackTrace
540 "Bits.complement: Natural complement undefined"
541 shift x i
542 | i >= 0 = shiftLNatural x i
543 | otherwise = shiftRNatural x (negate i)
544 testBit x i = testBitNatural x i
545 zeroBits = wordToNaturalBase 0##
546 clearBit x i = x `xor` (bit i .&. x)
547
548 bit (I# i#) = bitNatural i#
549 popCount x = popCountNatural x
550
551 rotate x i = shift x i -- since an Natural never wraps around
552
553 bitSizeMaybe _ = Nothing
554 bitSize _ = errorWithoutStackTrace "Data.Bits.bitSize(Natural)"
555 isSigned _ = False
556
557 -----------------------------------------------------------------------------
558
559 -- | Attempt to convert an 'Integral' type @a@ to an 'Integral' type @b@ using
560 -- the size of the types as measured by 'Bits' methods.
561 --
562 -- A simpler version of this function is:
563 --
564 -- > toIntegral :: (Integral a, Integral b) => a -> Maybe b
565 -- > toIntegral x
566 -- > | toInteger x == y = Just (fromInteger y)
567 -- > | otherwise = Nothing
568 -- > where
569 -- > y = toInteger x
570 --
571 -- This version requires going through 'Integer', which can be inefficient.
572 -- However, @toIntegralSized@ is optimized to allow GHC to statically determine
573 -- the relative type sizes (as measured by 'bitSizeMaybe' and 'isSigned') and
574 -- avoid going through 'Integer' for many types. (The implementation uses
575 -- 'fromIntegral', which is itself optimized with rules for @base@ types but may
576 -- go through 'Integer' for some type pairs.)
577 --
578 -- @since 4.8.0.0
579
580 toIntegralSized :: (Integral a, Integral b, Bits a, Bits b) => a -> Maybe b
581 toIntegralSized x -- See Note [toIntegralSized optimization]
582 | maybe True (<= x) yMinBound
583 , maybe True (x <=) yMaxBound = Just y
584 | otherwise = Nothing
585 where
586 y = fromIntegral x
587
588 xWidth = bitSizeMaybe x
589 yWidth = bitSizeMaybe y
590
591 yMinBound
592 | isBitSubType x y = Nothing
593 | isSigned x, not (isSigned y) = Just 0
594 | isSigned x, isSigned y
595 , Just yW <- yWidth = Just (negate $ bit (yW-1)) -- Assumes sub-type
596 | otherwise = Nothing
597
598 yMaxBound
599 | isBitSubType x y = Nothing
600 | isSigned x, not (isSigned y)
601 , Just xW <- xWidth, Just yW <- yWidth
602 , xW <= yW+1 = Nothing -- Max bound beyond a's domain
603 | Just yW <- yWidth = if isSigned y
604 then Just (bit (yW-1)-1)
605 else Just (bit yW-1)
606 | otherwise = Nothing
607 {-# INLINABLE toIntegralSized #-}
608
609 -- | 'True' if the size of @a@ is @<=@ the size of @b@, where size is measured
610 -- by 'bitSizeMaybe' and 'isSigned'.
611 isBitSubType :: (Bits a, Bits b) => a -> b -> Bool
612 isBitSubType x y
613 -- Reflexive
614 | xWidth == yWidth, xSigned == ySigned = True
615
616 -- Every integer is a subset of 'Integer'
617 | ySigned, Nothing == yWidth = True
618 | not xSigned, not ySigned, Nothing == yWidth = True
619
620 -- Sub-type relations between fixed-with types
621 | xSigned == ySigned, Just xW <- xWidth, Just yW <- yWidth = xW <= yW
622 | not xSigned, ySigned, Just xW <- xWidth, Just yW <- yWidth = xW < yW
623
624 | otherwise = False
625 where
626 xWidth = bitSizeMaybe x
627 xSigned = isSigned x
628
629 yWidth = bitSizeMaybe y
630 ySigned = isSigned y
631 {-# INLINE isBitSubType #-}
632
633 {- Note [Constant folding for rotate]
634 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
635 The INLINE on the Int instance of rotate enables it to be constant
636 folded. For example:
637 sumU . mapU (`rotate` 3) . replicateU 10000000 $ (7 :: Int)
638 goes to:
639 Main.$wfold =
640 \ (ww_sO7 :: Int#) (ww1_sOb :: Int#) ->
641 case ww1_sOb of wild_XM {
642 __DEFAULT -> Main.$wfold (+# ww_sO7 56) (+# wild_XM 1);
643 10000000 -> ww_sO7
644 whereas before it was left as a call to $wrotate.
645
646 All other Bits instances seem to inline well enough on their
647 own to enable constant folding; for example 'shift':
648 sumU . mapU (`shift` 3) . replicateU 10000000 $ (7 :: Int)
649 goes to:
650 Main.$wfold =
651 \ (ww_sOb :: Int#) (ww1_sOf :: Int#) ->
652 case ww1_sOf of wild_XM {
653 __DEFAULT -> Main.$wfold (+# ww_sOb 56) (+# wild_XM 1);
654 10000000 -> ww_sOb
655 }
656 -}
657
658 -- Note [toIntegralSized optimization]
659 -- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
660 -- The code in 'toIntegralSized' relies on GHC optimizing away statically
661 -- decidable branches.
662 --
663 -- If both integral types are statically known, GHC will be able optimize the
664 -- code significantly (for @-O1@ and better).
665 --
666 -- For instance (as of GHC 7.8.1) the following definitions:
667 --
668 -- > w16_to_i32 = toIntegralSized :: Word16 -> Maybe Int32
669 -- >
670 -- > i16_to_w16 = toIntegralSized :: Int16 -> Maybe Word16
671 --
672 -- are translated into the following (simplified) /GHC Core/ language:
673 --
674 -- > w16_to_i32 = \x -> Just (case x of _ { W16# x# -> I32# (word2Int# x#) })
675 -- >
676 -- > i16_to_w16 = \x -> case eta of _
677 -- > { I16# b1 -> case tagToEnum# (<=# 0 b1) of _
678 -- > { False -> Nothing
679 -- > ; True -> Just (W16# (narrow16Word# (int2Word# b1)))
680 -- > }
681 -- > }