Revert "Batch merge"
[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). Some instances may throw an
209 'Control.Exception.Overflow' exception if given a negative input.
210
211 An instance can define either this and 'shiftR' or the unified
212 'shift', depending on which is more convenient for the type in
213 question. -}
214 shiftL :: a -> Int -> a
215 {-# INLINE shiftL #-}
216 x `shiftL` i = x `shift` i
217
218 {-| Shift the argument left by the specified number of bits. The
219 result is undefined for negative shift amounts and shift amounts
220 greater or equal to the 'bitSize'.
221
222 Defaults to 'shiftL' unless defined explicitly by an instance.
223
224 @since 4.5.0.0 -}
225 unsafeShiftL :: a -> Int -> a
226 {-# INLINE unsafeShiftL #-}
227 x `unsafeShiftL` i = x `shiftL` i
228
229 {-| Shift the first argument right by the specified number of bits. The
230 result is undefined for negative shift amounts and shift amounts
231 greater or equal to the 'bitSize'. Some instances may throw an
232 'Control.Exception.Overflow' exception if given a negative input.
233
234 Right shifts perform sign extension on signed number types;
235 i.e. they fill the top bits with 1 if the @x@ is negative
236 and with 0 otherwise.
237
238 An instance can define either this and 'shiftL' or the unified
239 'shift', depending on which is more convenient for the type in
240 question. -}
241 shiftR :: a -> Int -> a
242 {-# INLINE shiftR #-}
243 x `shiftR` i = x `shift` (-i)
244
245 {-| Shift the first argument right by the specified number of bits, which
246 must be non-negative and smaller than the number of bits in the type.
247
248 Right shifts perform sign extension on signed number types;
249 i.e. they fill the top bits with 1 if the @x@ is negative
250 and with 0 otherwise.
251
252 Defaults to 'shiftR' unless defined explicitly by an instance.
253
254 @since 4.5.0.0 -}
255 unsafeShiftR :: a -> Int -> a
256 {-# INLINE unsafeShiftR #-}
257 x `unsafeShiftR` i = x `shiftR` i
258
259 {-| Rotate the argument left by the specified number of bits
260 (which must be non-negative).
261
262 An instance can define either this and 'rotateR' or the unified
263 'rotate', depending on which is more convenient for the type in
264 question. -}
265 rotateL :: a -> Int -> a
266 {-# INLINE rotateL #-}
267 x `rotateL` i = x `rotate` i
268
269 {-| Rotate the argument right by the specified number of bits
270 (which must be non-negative).
271
272 An instance can define either this and 'rotateL' or the unified
273 'rotate', depending on which is more convenient for the type in
274 question. -}
275 rotateR :: a -> Int -> a
276 {-# INLINE rotateR #-}
277 x `rotateR` i = x `rotate` (-i)
278
279 {-| Return the number of set bits in the argument. This number is
280 known as the population count or the Hamming weight.
281
282 Can be implemented using `popCountDefault' if @a@ is also an
283 instance of 'Num'.
284
285 @since 4.5.0.0 -}
286 popCount :: a -> Int
287
288 -- |The 'FiniteBits' class denotes types with a finite, fixed number of bits.
289 --
290 -- @since 4.7.0.0
291 class Bits b => FiniteBits b where
292 -- | Return the number of bits in the type of the argument.
293 -- The actual value of the argument is ignored. Moreover, 'finiteBitSize'
294 -- is total, in contrast to the deprecated 'bitSize' function it replaces.
295 --
296 -- @
297 -- 'finiteBitSize' = 'bitSize'
298 -- 'bitSizeMaybe' = 'Just' . 'finiteBitSize'
299 -- @
300 --
301 -- @since 4.7.0.0
302 finiteBitSize :: b -> Int
303
304 -- | Count number of zero bits preceding the most significant set bit.
305 --
306 -- @
307 -- 'countLeadingZeros' ('zeroBits' :: a) = finiteBitSize ('zeroBits' :: a)
308 -- @
309 --
310 -- 'countLeadingZeros' can be used to compute log base 2 via
311 --
312 -- @
313 -- logBase2 x = 'finiteBitSize' x - 1 - 'countLeadingZeros' x
314 -- @
315 --
316 -- Note: The default implementation for this method is intentionally
317 -- naive. However, the instances provided for the primitive
318 -- integral types are implemented using CPU specific machine
319 -- instructions.
320 --
321 -- @since 4.8.0.0
322 countLeadingZeros :: b -> Int
323 countLeadingZeros x = (w-1) - go (w-1)
324 where
325 go i | i < 0 = i -- no bit set
326 | testBit x i = i
327 | otherwise = go (i-1)
328
329 w = finiteBitSize x
330
331 -- | Count number of zero bits following the least significant set bit.
332 --
333 -- @
334 -- 'countTrailingZeros' ('zeroBits' :: a) = finiteBitSize ('zeroBits' :: a)
335 -- 'countTrailingZeros' . 'negate' = 'countTrailingZeros'
336 -- @
337 --
338 -- The related
339 -- <http://en.wikipedia.org/wiki/Find_first_set find-first-set operation>
340 -- can be expressed in terms of 'countTrailingZeros' as follows
341 --
342 -- @
343 -- findFirstSet x = 1 + 'countTrailingZeros' x
344 -- @
345 --
346 -- Note: The default implementation for this method is intentionally
347 -- naive. However, the instances provided for the primitive
348 -- integral types are implemented using CPU specific machine
349 -- instructions.
350 --
351 -- @since 4.8.0.0
352 countTrailingZeros :: b -> Int
353 countTrailingZeros x = go 0
354 where
355 go i | i >= w = i
356 | testBit x i = i
357 | otherwise = go (i+1)
358
359 w = finiteBitSize x
360
361
362 -- The defaults below are written with lambdas so that e.g.
363 -- bit = bitDefault
364 -- is fully applied, so inlining will happen
365
366 -- | Default implementation for 'bit'.
367 --
368 -- Note that: @bitDefault i = 1 `shiftL` i@
369 --
370 -- @since 4.6.0.0
371 bitDefault :: (Bits a, Num a) => Int -> a
372 bitDefault = \i -> 1 `shiftL` i
373 {-# INLINE bitDefault #-}
374
375 -- | Default implementation for 'testBit'.
376 --
377 -- Note that: @testBitDefault x i = (x .&. bit i) /= 0@
378 --
379 -- @since 4.6.0.0
380 testBitDefault :: (Bits a, Num a) => a -> Int -> Bool
381 testBitDefault = \x i -> (x .&. bit i) /= 0
382 {-# INLINE testBitDefault #-}
383
384 -- | Default implementation for 'popCount'.
385 --
386 -- This implementation is intentionally naive. Instances are expected to provide
387 -- an optimized implementation for their size.
388 --
389 -- @since 4.6.0.0
390 popCountDefault :: (Bits a, Num a) => a -> Int
391 popCountDefault = go 0
392 where
393 go !c 0 = c
394 go c w = go (c+1) (w .&. (w - 1)) -- clear the least significant
395 {-# INLINABLE popCountDefault #-}
396
397
398 -- | Interpret 'Bool' as 1-bit bit-field
399 --
400 -- @since 4.7.0.0
401 instance Bits Bool where
402 (.&.) = (&&)
403
404 (.|.) = (||)
405
406 xor = (/=)
407
408 complement = not
409
410 shift x 0 = x
411 shift _ _ = False
412
413 rotate x _ = x
414
415 bit 0 = True
416 bit _ = False
417
418 testBit x 0 = x
419 testBit _ _ = False
420
421 bitSizeMaybe _ = Just 1
422
423 bitSize _ = 1
424
425 isSigned _ = False
426
427 popCount False = 0
428 popCount True = 1
429
430 -- | @since 4.7.0.0
431 instance FiniteBits Bool where
432 finiteBitSize _ = 1
433 countTrailingZeros x = if x then 0 else 1
434 countLeadingZeros x = if x then 0 else 1
435
436 -- | @since 2.01
437 instance Bits Int where
438 {-# INLINE shift #-}
439 {-# INLINE bit #-}
440 {-# INLINE testBit #-}
441
442 zeroBits = 0
443
444 bit = bitDefault
445
446 testBit = testBitDefault
447
448 (I# x#) .&. (I# y#) = I# (x# `andI#` y#)
449 (I# x#) .|. (I# y#) = I# (x# `orI#` y#)
450 (I# x#) `xor` (I# y#) = I# (x# `xorI#` y#)
451 complement (I# x#) = I# (notI# x#)
452 (I# x#) `shift` (I# i#)
453 | isTrue# (i# >=# 0#) = I# (x# `iShiftL#` i#)
454 | otherwise = I# (x# `iShiftRA#` negateInt# i#)
455 (I# x#) `shiftL` (I# i#)
456 | isTrue# (i# >=# 0#) = I# (x# `iShiftL#` i#)
457 | otherwise = overflowError
458 (I# x#) `unsafeShiftL` (I# i#) = I# (x# `uncheckedIShiftL#` i#)
459 (I# x#) `shiftR` (I# i#)
460 | isTrue# (i# >=# 0#) = I# (x# `iShiftRA#` i#)
461 | otherwise = overflowError
462 (I# x#) `unsafeShiftR` (I# i#) = I# (x# `uncheckedIShiftRA#` i#)
463
464 {-# INLINE rotate #-} -- See Note [Constant folding for rotate]
465 (I# x#) `rotate` (I# i#) =
466 I# ((x# `uncheckedIShiftL#` i'#) `orI#` (x# `uncheckedIShiftRL#` (wsib -# i'#)))
467 where
468 !i'# = i# `andI#` (wsib -# 1#)
469 !wsib = WORD_SIZE_IN_BITS# {- work around preprocessor problem (??) -}
470 bitSizeMaybe i = Just (finiteBitSize i)
471 bitSize i = finiteBitSize i
472
473 popCount (I# x#) = I# (word2Int# (popCnt# (int2Word# x#)))
474
475 isSigned _ = True
476
477 -- | @since 4.6.0.0
478 instance FiniteBits Int where
479 finiteBitSize _ = WORD_SIZE_IN_BITS
480 countLeadingZeros (I# x#) = I# (word2Int# (clz# (int2Word# x#)))
481 countTrailingZeros (I# x#) = I# (word2Int# (ctz# (int2Word# x#)))
482
483 -- | @since 2.01
484 instance Bits Word where
485 {-# INLINE shift #-}
486 {-# INLINE bit #-}
487 {-# INLINE testBit #-}
488
489 (W# x#) .&. (W# y#) = W# (x# `and#` y#)
490 (W# x#) .|. (W# y#) = W# (x# `or#` y#)
491 (W# x#) `xor` (W# y#) = W# (x# `xor#` y#)
492 complement (W# x#) = W# (x# `xor#` mb#)
493 where !(W# mb#) = maxBound
494 (W# x#) `shift` (I# i#)
495 | isTrue# (i# >=# 0#) = W# (x# `shiftL#` i#)
496 | otherwise = W# (x# `shiftRL#` negateInt# i#)
497 (W# x#) `shiftL` (I# i#)
498 | isTrue# (i# >=# 0#) = W# (x# `shiftL#` i#)
499 | otherwise = overflowError
500 (W# x#) `unsafeShiftL` (I# i#) = W# (x# `uncheckedShiftL#` i#)
501 (W# x#) `shiftR` (I# i#)
502 | isTrue# (i# >=# 0#) = W# (x# `shiftRL#` i#)
503 | otherwise = overflowError
504 (W# x#) `unsafeShiftR` (I# i#) = W# (x# `uncheckedShiftRL#` i#)
505 (W# x#) `rotate` (I# i#)
506 | isTrue# (i'# ==# 0#) = W# x#
507 | otherwise = W# ((x# `uncheckedShiftL#` i'#) `or#` (x# `uncheckedShiftRL#` (wsib -# i'#)))
508 where
509 !i'# = i# `andI#` (wsib -# 1#)
510 !wsib = WORD_SIZE_IN_BITS# {- work around preprocessor problem (??) -}
511 bitSizeMaybe i = Just (finiteBitSize i)
512 bitSize i = finiteBitSize i
513 isSigned _ = False
514 popCount (W# x#) = I# (word2Int# (popCnt# x#))
515 bit = bitDefault
516 testBit = testBitDefault
517
518 -- | @since 4.6.0.0
519 instance FiniteBits Word where
520 finiteBitSize _ = WORD_SIZE_IN_BITS
521 countLeadingZeros (W# x#) = I# (word2Int# (clz# x#))
522 countTrailingZeros (W# x#) = I# (word2Int# (ctz# x#))
523
524 -- | @since 2.01
525 instance Bits Integer where
526 (.&.) = andInteger
527 (.|.) = orInteger
528 xor = xorInteger
529 complement = complementInteger
530 shift x i@(I# i#) | i >= 0 = shiftLInteger x i#
531 | otherwise = shiftRInteger x (negateInt# i#)
532 testBit x (I# i) = testBitInteger x i
533 zeroBits = 0
534
535 bit (I# i#) = bitInteger i#
536 popCount x = I# (popCountInteger x)
537
538 rotate x i = shift x i -- since an Integer never wraps around
539
540 bitSizeMaybe _ = Nothing
541 bitSize _ = errorWithoutStackTrace "Data.Bits.bitSize(Integer)"
542 isSigned _ = True
543
544 -- | @since 4.8.0
545 instance Bits Natural where
546 (.&.) = andNatural
547 (.|.) = orNatural
548 xor = xorNatural
549 complement _ = errorWithoutStackTrace
550 "Bits.complement: Natural complement undefined"
551 shift x i
552 | i >= 0 = shiftLNatural x i
553 | otherwise = shiftRNatural x (negate i)
554 testBit x i = testBitNatural x i
555 zeroBits = wordToNaturalBase 0##
556 clearBit x i = x `xor` (bit i .&. x)
557
558 bit (I# i#) = bitNatural i#
559 popCount x = popCountNatural x
560
561 rotate x i = shift x i -- since an Natural never wraps around
562
563 bitSizeMaybe _ = Nothing
564 bitSize _ = errorWithoutStackTrace "Data.Bits.bitSize(Natural)"
565 isSigned _ = False
566
567 -----------------------------------------------------------------------------
568
569 -- | Attempt to convert an 'Integral' type @a@ to an 'Integral' type @b@ using
570 -- the size of the types as measured by 'Bits' methods.
571 --
572 -- A simpler version of this function is:
573 --
574 -- > toIntegral :: (Integral a, Integral b) => a -> Maybe b
575 -- > toIntegral x
576 -- > | toInteger x == y = Just (fromInteger y)
577 -- > | otherwise = Nothing
578 -- > where
579 -- > y = toInteger x
580 --
581 -- This version requires going through 'Integer', which can be inefficient.
582 -- However, @toIntegralSized@ is optimized to allow GHC to statically determine
583 -- the relative type sizes (as measured by 'bitSizeMaybe' and 'isSigned') and
584 -- avoid going through 'Integer' for many types. (The implementation uses
585 -- 'fromIntegral', which is itself optimized with rules for @base@ types but may
586 -- go through 'Integer' for some type pairs.)
587 --
588 -- @since 4.8.0.0
589
590 toIntegralSized :: (Integral a, Integral b, Bits a, Bits b) => a -> Maybe b
591 toIntegralSized x -- See Note [toIntegralSized optimization]
592 | maybe True (<= x) yMinBound
593 , maybe True (x <=) yMaxBound = Just y
594 | otherwise = Nothing
595 where
596 y = fromIntegral x
597
598 xWidth = bitSizeMaybe x
599 yWidth = bitSizeMaybe y
600
601 yMinBound
602 | isBitSubType x y = Nothing
603 | isSigned x, not (isSigned y) = Just 0
604 | isSigned x, isSigned y
605 , Just yW <- yWidth = Just (negate $ bit (yW-1)) -- Assumes sub-type
606 | otherwise = Nothing
607
608 yMaxBound
609 | isBitSubType x y = Nothing
610 | isSigned x, not (isSigned y)
611 , Just xW <- xWidth, Just yW <- yWidth
612 , xW <= yW+1 = Nothing -- Max bound beyond a's domain
613 | Just yW <- yWidth = if isSigned y
614 then Just (bit (yW-1)-1)
615 else Just (bit yW-1)
616 | otherwise = Nothing
617 {-# INLINABLE toIntegralSized #-}
618
619 -- | 'True' if the size of @a@ is @<=@ the size of @b@, where size is measured
620 -- by 'bitSizeMaybe' and 'isSigned'.
621 isBitSubType :: (Bits a, Bits b) => a -> b -> Bool
622 isBitSubType x y
623 -- Reflexive
624 | xWidth == yWidth, xSigned == ySigned = True
625
626 -- Every integer is a subset of 'Integer'
627 | ySigned, Nothing == yWidth = True
628 | not xSigned, not ySigned, Nothing == yWidth = True
629
630 -- Sub-type relations between fixed-with types
631 | xSigned == ySigned, Just xW <- xWidth, Just yW <- yWidth = xW <= yW
632 | not xSigned, ySigned, Just xW <- xWidth, Just yW <- yWidth = xW < yW
633
634 | otherwise = False
635 where
636 xWidth = bitSizeMaybe x
637 xSigned = isSigned x
638
639 yWidth = bitSizeMaybe y
640 ySigned = isSigned y
641 {-# INLINE isBitSubType #-}
642
643 {- Note [Constant folding for rotate]
644 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
645 The INLINE on the Int instance of rotate enables it to be constant
646 folded. For example:
647 sumU . mapU (`rotate` 3) . replicateU 10000000 $ (7 :: Int)
648 goes to:
649 Main.$wfold =
650 \ (ww_sO7 :: Int#) (ww1_sOb :: Int#) ->
651 case ww1_sOb of wild_XM {
652 __DEFAULT -> Main.$wfold (+# ww_sO7 56) (+# wild_XM 1);
653 10000000 -> ww_sO7
654 whereas before it was left as a call to $wrotate.
655
656 All other Bits instances seem to inline well enough on their
657 own to enable constant folding; for example 'shift':
658 sumU . mapU (`shift` 3) . replicateU 10000000 $ (7 :: Int)
659 goes to:
660 Main.$wfold =
661 \ (ww_sOb :: Int#) (ww1_sOf :: Int#) ->
662 case ww1_sOf of wild_XM {
663 __DEFAULT -> Main.$wfold (+# ww_sOb 56) (+# wild_XM 1);
664 10000000 -> ww_sOb
665 }
666 -}
667
668 -- Note [toIntegralSized optimization]
669 -- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
670 -- The code in 'toIntegralSized' relies on GHC optimizing away statically
671 -- decidable branches.
672 --
673 -- If both integral types are statically known, GHC will be able optimize the
674 -- code significantly (for @-O1@ and better).
675 --
676 -- For instance (as of GHC 7.8.1) the following definitions:
677 --
678 -- > w16_to_i32 = toIntegralSized :: Word16 -> Maybe Int32
679 -- >
680 -- > i16_to_w16 = toIntegralSized :: Int16 -> Maybe Word16
681 --
682 -- are translated into the following (simplified) /GHC Core/ language:
683 --
684 -- > w16_to_i32 = \x -> Just (case x of _ { W16# x# -> I32# (word2Int# x#) })
685 -- >
686 -- > i16_to_w16 = \x -> case eta of _
687 -- > { I16# b1 -> case tagToEnum# (<=# 0 b1) of _
688 -- > { False -> Nothing
689 -- > ; True -> Just (W16# (narrow16Word# (int2Word# b1)))
690 -- > }
691 -- > }