compiler/nativeGen/RegAlloc/Linear/StackMap.hs

   1
   2 -- | The assignment of virtual registers to stack slots
   3
   4 --      We have lots of stack slots. Memory-to-memory moves are a pain on most
   5 --      architectures. Therefore, we avoid having to generate memory-to-memory moves
   6 --      by simply giving every virtual register its own stack slot.
   7
   8 --      The StackMap stack map keeps track of virtual register - stack slot
   9 --      associations and of which stack slots are still free. Once it has been
  10 --      associated, a stack slot is never "freed" or removed from the StackMap again,
  11 --      it remains associated until we are done with the current CmmProc.
  12 --
  13 module RegAlloc.Linear.StackMap (
  14         StackSlot,
  15         StackMap(..),
  16         emptyStackMap,
  17         getStackSlotFor
  18 )
  19
  20 where
  21
  22 import RegAllocInfo     (maxSpillSlots)
  23
  24 import Outputable
  25 import UniqFM
  26 import Unique
  27
  28
  29 -- | Identifier for a stack slot.
  30 type StackSlot = Int
  31
  32 data StackMap
  33         = StackMap
  34         { -- | The slots that are still available to be allocated.
  35           stackMapFreeSlots     :: [StackSlot]
  36
  37           -- | Assignment of vregs to stack slots.
  38         , stackMapAssignment    :: UniqFM StackSlot }
  39
  40
  41 -- | An empty stack map, with all slots available.
  42 emptyStackMap :: StackMap
  43 emptyStackMap = StackMap [0..maxSpillSlots] emptyUFM
  44
  45
  46 -- | If this vreg unique already has a stack assignment then return the slot number,
  47 --      otherwise allocate a new slot, and update the map.
  48 --
  49 getStackSlotFor :: StackMap -> Unique -> (StackMap, Int)
  50
  51 getStackSlotFor (StackMap [] _) _
  52
  53         -- This happens all the time when trying to compile darcs' SHA1.hs, see Track #1993
  54         --      SHA1.lhs has also been added to the Crypto library on Hackage,
  55         --      so we see this all the time.
  56         --
  57         -- It would be better to automatically invoke the graph allocator, or do something
  58         --      else besides panicing, but that's a job for a different day.  -- BL 2009/02
  59         --
  60         = panic $   "RegAllocLinear.getStackSlotFor: out of stack slots\n"
  61                 ++  "   If you are trying to compile SHA1.hs from the crypto library then this\n"
  62                 ++  "   is a known limitation in the linear allocator.\n"
  63                 ++  "\n"
  64                 ++  "   Try enabling the graph colouring allocator with -fregs-graph instead."
  65                 ++  "   You can still file a bug report if you like.\n"
  66
  67 getStackSlotFor fs@(StackMap (freeSlot:stack') reserved) reg =
  68     case lookupUFM reserved reg of
  69         Just slot       -> (fs, slot)
  70         Nothing         -> (StackMap stack' (addToUFM reserved reg freeSlot), freeSlot)
  71