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
  35         -- | The slots that are still available to be allocated.
  36         { stackMapFreeSlots     :: [StackSlot]
  37
  38         -- | Assignment of vregs to stack slots.
  39         , stackMapAssignment    :: UniqFM StackSlot }
  40
  41
  42 -- | An empty stack map, with all slots available.
  43 emptyStackMap :: StackMap
  44 emptyStackMap = StackMap [0..maxSpillSlots] emptyUFM
  45
  46
  47 -- | If this vreg unique already has a stack assignment then return the slot number,
  48 --      otherwise allocate a new slot, and update the map.
  49 --
  50 getStackSlotFor :: StackMap -> Unique -> (StackMap, Int)
  51
  52 getStackSlotFor (StackMap [] _) _
  53
  54         -- This happens all the time when trying to compile darcs' SHA1.hs, see Track #1993
  55         --      SHA1.lhs has also been added to the Crypto library on Hackage,
  56         --      so we see this all the time.
  57         --
  58         -- It would be better to automatically invoke the graph allocator, or do something
  59         --      else besides panicing, but that's a job for a different day.  -- BL 2009/02
  60         --
  61         = panic $   "RegAllocLinear.getStackSlotFor: out of stack slots\n"
  62                 ++  "   If you are trying to compile SHA1.hs from the crypto library then this\n"
  63                 ++  "   is a known limitation in the linear allocator.\n"
  64                 ++  "\n"
  65                 ++  "   Try enabling the graph colouring allocator with -fregs-graph instead."
  66                 ++  "   You can still file a bug report if you like.\n"
  67
  68 getStackSlotFor fs@(StackMap (freeSlot:stack') reserved) reg =
  69     case lookupUFM reserved reg of
  70         Just slot       -> (fs, slot)
  71         Nothing         -> (StackMap stack' (addToUFM reserved reg freeSlot), freeSlot)
  72