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