compiler/codeGen/Bitmap.hs

   1 {-# OPTIONS -w #-}
   2 -- The above warning supression flag is a temporary kludge.
   3 -- While working on this module you are encouraged to remove it and fix
   4 -- any warnings in the module. See
   5 --     http://hackage.haskell.org/trac/ghc/wiki/Commentary/CodingStyle#Warnings
   6 -- for details
   7
   8 --
   9 -- (c) The University of Glasgow 2003-2006
  10 --
  11
  12 -- Functions for constructing bitmaps, which are used in various
  13 -- places in generated code (stack frame liveness masks, function
  14 -- argument liveness masks, SRT bitmaps).
  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 Constants
  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 :: [Bool] -> Bitmap
  41 mkBitmap [] = []
  42 mkBitmap stuff = chunkToBitmap chunk : mkBitmap rest
  43   where (chunk, rest) = splitAt wORD_SIZE_IN_BITS 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 :: Int -> [Int] -> Bitmap
  54 intsToBitmap size slots{- must be sorted -}
  55   | size <= 0 = []
  56   | otherwise =
  57     (foldr (.|.) 0 (map (1 `shiftL`) these)) :
  58         intsToBitmap (size - wORD_SIZE_IN_BITS)
  59              (map (\x -> x - wORD_SIZE_IN_BITS) rest)
  60    where (these,rest) = span (<wORD_SIZE_IN_BITS) 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.
  67 intsToReverseBitmap :: Int -> [Int] -> Bitmap
  68 intsToReverseBitmap size slots{- must be sorted -}
  69   | size <= 0 = []
  70   | otherwise =
  71     (foldr xor init (map (1 `shiftL`) these)) :
  72         intsToReverseBitmap (size - wORD_SIZE_IN_BITS)
  73              (map (\x -> x - wORD_SIZE_IN_BITS) rest)
  74    where (these,rest) = span (<wORD_SIZE_IN_BITS) slots
  75          init
  76            | size >= wORD_SIZE_IN_BITS = 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 :: Int
  87 mAX_SMALL_BITMAP_SIZE  | wORD_SIZE == 4 = 27
  88                        | otherwise      = 58
  89
  90 seqBitmap :: Bitmap -> a -> a
  91 seqBitmap = seqList
  92