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   ) where
  21
  22 #include "HsVersions.h"
  23 #include "../includes/MachDeps.h"
  24
  25 import SMRep
  26 import Constants
  27
  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 :: [Bool] -> Bitmap
  39 mkBitmap [] = []
  40 mkBitmap stuff = chunkToBitmap chunk : mkBitmap rest
  41   where (chunk, rest) = splitAt wORD_SIZE_IN_BITS stuff
  42
  43 chunkToBitmap :: [Bool] -> StgWord
  44 chunkToBitmap chunk =
  45   foldr (.|.) 0 [ 1 `shiftL` n | (True,n) <- zip chunk [0..] ]
  46
  47 -- | Make a bitmap where the slots specified are the /ones/ in the bitmap.
  48 -- eg. @[0,1,3], size 4 ==> 0xb@.
  49 --
  50 -- The list of @Int@s /must/ be already sorted.
  51 intsToBitmap :: Int -> [Int] -> Bitmap
  52 intsToBitmap size slots{- must be sorted -}
  53   | size <= 0 = []
  54   | otherwise =
  55     (foldr (.|.) 0 (map (1 `shiftL`) these)) :
  56         intsToBitmap (size - wORD_SIZE_IN_BITS)
  57              (map (\x -> x - wORD_SIZE_IN_BITS) rest)
  58    where (these,rest) = span (<wORD_SIZE_IN_BITS) slots
  59
  60 -- | Make a bitmap where the slots specified are the /zeros/ in the bitmap.
  61 -- eg. @[0,1,3], size 4 ==> 0x4@  (we leave any bits outside the size as zero,
  62 -- just to make the bitmap easier to read).
  63 --
  64 -- The list of @Int@s /must/ be already sorted.
  65 intsToReverseBitmap :: Int -> [Int] -> Bitmap
  66 intsToReverseBitmap size slots{- must be sorted -}
  67   | size <= 0 = []
  68   | otherwise =
  69     (foldr xor init (map (1 `shiftL`) these)) :
  70         intsToReverseBitmap (size - wORD_SIZE_IN_BITS)
  71              (map (\x -> x - wORD_SIZE_IN_BITS) rest)
  72    where (these,rest) = span (<wORD_SIZE_IN_BITS) slots
  73          init
  74            | size >= wORD_SIZE_IN_BITS = complement 0
  75            | otherwise                 = (1 `shiftL` size) - 1
  76
  77 {- |
  78 Magic number, must agree with @BITMAP_BITS_SHIFT@ in InfoTables.h.
  79 Some kinds of bitmap pack a size\/bitmap into a single word if
  80 possible, or fall back to an external pointer when the bitmap is too
  81 large.  This value represents the largest size of bitmap that can be
  82 packed into a single word.
  83 -}
  84 mAX_SMALL_BITMAP_SIZE :: Int
  85 mAX_SMALL_BITMAP_SIZE  | wORD_SIZE == 4 = 27
  86                        | otherwise      = 58
  87