93217d51923d11b02ff86be7b378e6abb7d6534e
[ghc.git] / compiler / cmm / Bitmap.hs
1 --
2 -- (c) The University of Glasgow 2003-2006
3 --
4
5 -- Functions for constructing bitmaps, which are used in various
6 -- places in generated code (stack frame liveness masks, function
7 -- argument liveness masks, SRT bitmaps).
8
9 {-# OPTIONS -fno-warn-tabs #-}
10 -- The above warning supression flag is a temporary kludge.
11 -- While working on this module you are encouraged to remove it and
12 -- detab the module (please do the detabbing in a separate patch). See
13 -- http://hackage.haskell.org/trac/ghc/wiki/Commentary/CodingStyle#TabsvsSpaces
14 -- for details
15
16 module Bitmap (
17 Bitmap, mkBitmap,
18 intsToBitmap, intsToReverseBitmap,
19 mAX_SMALL_BITMAP_SIZE,
20 seqBitmap,
21 ) where
22
23 #include "HsVersions.h"
24 #include "../includes/MachDeps.h"
25
26 import SMRep
27 import DynFlags
28 import Util
29
30 import Data.Bits
31
32 {-|
33 A bitmap represented by a sequence of 'StgWord's on the /target/
34 architecture. These are used for bitmaps in info tables and other
35 generated code which need to be emitted as sequences of StgWords.
36 -}
37 type Bitmap = [StgWord]
38
39 -- | Make a bitmap from a sequence of bits
40 mkBitmap :: DynFlags -> [Bool] -> Bitmap
41 mkBitmap _ [] = []
42 mkBitmap dflags stuff = chunkToBitmap chunk : mkBitmap dflags rest
43 where (chunk, rest) = splitAt (wORD_SIZE_IN_BITS dflags) stuff
44
45 chunkToBitmap :: [Bool] -> StgWord
46 chunkToBitmap chunk =
47 foldr (.|.) 0 [ 1 `shiftL` n | (True,n) <- zip chunk [0..] ]
48
49 -- | Make a bitmap where the slots specified are the /ones/ in the bitmap.
50 -- eg. @[0,1,3], size 4 ==> 0xb@.
51 --
52 -- The list of @Int@s /must/ be already sorted.
53 intsToBitmap :: DynFlags -> Int -> [Int] -> Bitmap
54 intsToBitmap dflags size slots{- must be sorted -}
55 | size <= 0 = []
56 | otherwise =
57 (foldr (.|.) 0 (map (1 `shiftL`) these)) :
58 intsToBitmap dflags (size - wORD_SIZE_IN_BITS dflags)
59 (map (\x -> x - wORD_SIZE_IN_BITS dflags) rest)
60 where (these,rest) = span (< wORD_SIZE_IN_BITS dflags) slots
61
62 -- | Make a bitmap where the slots specified are the /zeros/ in the bitmap.
63 -- eg. @[0,1,3], size 4 ==> 0x4@ (we leave any bits outside the size as zero,
64 -- just to make the bitmap easier to read).
65 --
66 -- The list of @Int@s /must/ be already sorted and duplicate-free.
67 intsToReverseBitmap :: DynFlags -> Int -> [Int] -> Bitmap
68 intsToReverseBitmap dflags size slots{- must be sorted -}
69 | size <= 0 = []
70 | otherwise =
71 (foldr xor init (map (1 `shiftL`) these)) :
72 intsToReverseBitmap dflags (size - wORD_SIZE_IN_BITS dflags)
73 (map (\x -> x - wORD_SIZE_IN_BITS dflags) rest)
74 where (these,rest) = span (< wORD_SIZE_IN_BITS dflags) slots
75 init
76 | size >= wORD_SIZE_IN_BITS dflags = complement 0
77 | otherwise = (1 `shiftL` size) - 1
78
79 {- |
80 Magic number, must agree with @BITMAP_BITS_SHIFT@ in InfoTables.h.
81 Some kinds of bitmap pack a size\/bitmap into a single word if
82 possible, or fall back to an external pointer when the bitmap is too
83 large. This value represents the largest size of bitmap that can be
84 packed into a single word.
85 -}
86 mAX_SMALL_BITMAP_SIZE :: DynFlags -> Int
87 mAX_SMALL_BITMAP_SIZE dflags
88 | wORD_SIZE dflags == 4 = 27
89 | otherwise = 58
90
91 seqBitmap :: Bitmap -> a -> a
92 seqBitmap = seqList
93