22ec6ee238c51b477c1882c67325c05449d976ee
[ghc.git] / compiler / cmm / Bitmap.hs
1 {-# LANGUAGE CPP, BangPatterns #-}
2
3 --
4 -- (c) The University of Glasgow 2003-2006
5 --
6
7 -- Functions for constructing bitmaps, which are used in various
8 -- places in generated code (stack frame liveness masks, function
9 -- argument liveness masks, SRT bitmaps).
10
11 module Bitmap (
12 Bitmap, mkBitmap,
13 intsToBitmap, intsToReverseBitmap,
14 mAX_SMALL_BITMAP_SIZE,
15 seqBitmap,
16 ) where
17
18 #include "HsVersions.h"
19 #include "../includes/MachDeps.h"
20
21 import SMRep
22 import DynFlags
23 import Util
24
25 import Data.Bits
26
27 {-|
28 A bitmap represented by a sequence of 'StgWord's on the /target/
29 architecture. These are used for bitmaps in info tables and other
30 generated code which need to be emitted as sequences of StgWords.
31 -}
32 type Bitmap = [StgWord]
33
34 -- | Make a bitmap from a sequence of bits
35 mkBitmap :: DynFlags -> [Bool] -> Bitmap
36 mkBitmap _ [] = []
37 mkBitmap dflags stuff = chunkToBitmap dflags chunk : mkBitmap dflags rest
38 where (chunk, rest) = splitAt (wORD_SIZE_IN_BITS dflags) stuff
39
40 chunkToBitmap :: DynFlags -> [Bool] -> StgWord
41 chunkToBitmap dflags chunk =
42 foldr (.|.) (toStgWord dflags 0) [ toStgWord dflags 1 `shiftL` n | (True,n) <- zip chunk [0..] ]
43
44 -- | Make a bitmap where the slots specified are the /ones/ in the bitmap.
45 -- eg. @[0,1,3], size 4 ==> 0xb@.
46 --
47 -- The list of @Int@s /must/ be already sorted.
48 intsToBitmap :: DynFlags
49 -> Int -- ^ size in bits
50 -> [Int] -- ^ sorted indices of ones
51 -> Bitmap
52 intsToBitmap dflags size = go 0
53 where
54 word_sz = wORD_SIZE_IN_BITS dflags
55 oneAt :: Int -> StgWord
56 oneAt i = toStgWord dflags 1 `shiftL` i
57
58 -- It is important that we maintain strictness here.
59 -- See Note [Strictness when building Bitmaps].
60 go :: Int -> [Int] -> Bitmap
61 go !pos slots
62 | size <= pos = []
63 | otherwise =
64 (foldr (.|.) (toStgWord dflags 0) (map (\i->oneAt (i - pos)) these)) :
65 go (pos + word_sz) rest
66 where
67 (these,rest) = span (< (pos + word_sz)) slots
68
69 -- | Make a bitmap where the slots specified are the /zeros/ in the bitmap.
70 -- eg. @[0,1,3], size 4 ==> 0x4@ (we leave any bits outside the size as zero,
71 -- just to make the bitmap easier to read).
72 --
73 -- The list of @Int@s /must/ be already sorted and duplicate-free.
74 intsToReverseBitmap :: DynFlags
75 -> Int -- ^ size in bits
76 -> [Int] -- ^ sorted indices of zeros free of duplicates
77 -> Bitmap
78 intsToReverseBitmap dflags size = go 0
79 where
80 word_sz = wORD_SIZE_IN_BITS dflags
81 oneAt :: Int -> StgWord
82 oneAt i = toStgWord dflags 1 `shiftL` i
83
84 -- It is important that we maintain strictness here.
85 -- See Note [Strictness when building Bitmaps].
86 go :: Int -> [Int] -> Bitmap
87 go !pos slots
88 | size <= pos = []
89 | otherwise =
90 (foldr xor (toStgWord dflags init) (map (\i->oneAt (i - pos)) these)) :
91 go (pos + word_sz) rest
92 where
93 (these,rest) = span (< (pos + word_sz)) slots
94 remain = size - pos
95 init
96 | remain >= word_sz = -1
97 | otherwise = (1 `shiftL` remain) - 1
98
99 {-
100
101 Note [Strictness when building Bitmaps]
102 ========================================
103
104 One of the places where @Bitmap@ is used is in in building Static Reference
105 Tables (SRTs) (in @CmmBuildInfoTables.procpointSRT@). In #7450 it was noticed
106 that some test cases (particularly those whose C-- have large numbers of CAFs)
107 produced large quantities of allocations from this function.
108
109 The source traced back to 'intsToBitmap', which was lazily subtracting the word
110 size from the elements of the tail of the @slots@ list and recursively invoking
111 itself with the result. This resulted in large numbers of subtraction thunks
112 being built up. Here we take care to avoid passing new thunks to the recursive
113 call. Instead we pass the unmodified tail along with an explicit position
114 accumulator, which get subtracted in the fold when we compute the Word.
115
116 -}
117
118 {- |
119 Magic number, must agree with @BITMAP_BITS_SHIFT@ in InfoTables.h.
120 Some kinds of bitmap pack a size\/bitmap into a single word if
121 possible, or fall back to an external pointer when the bitmap is too
122 large. This value represents the largest size of bitmap that can be
123 packed into a single word.
124 -}
125 mAX_SMALL_BITMAP_SIZE :: DynFlags -> Int
126 mAX_SMALL_BITMAP_SIZE dflags
127 | wORD_SIZE dflags == 4 = 27
128 | otherwise = 58
129
130 seqBitmap :: Bitmap -> a -> a
131 seqBitmap = seqList
132