compiler/nativeGen/RegAlloc/Linear/Base.hs

   1
   2 -- | Put common type definitions here to break recursive module dependencies.
   3
   4 module RegAlloc.Linear.Base (
   5         BlockAssignment,
   6
   7         Loc(..),
   8         regsOfLoc,
   9
  10         -- for stats
  11         SpillReason(..),
  12         RegAllocStats(..),
  13
  14         -- the allocator monad
  15         RA_State(..),
  16         RegM(..)
  17 )
  18
  19 where
  20
  21 import RegAlloc.Linear.StackMap
  22 import RegAlloc.Liveness
  23 import Reg
  24
  25 import Outputable
  26 import Unique
  27 import UniqFM
  28 import UniqSupply
  29
  30
  31 -- | Used to store the register assignment on entry to a basic block.
  32 --      We use this to handle join points, where multiple branch instructions
  33 --      target a particular label. We have to insert fixup code to make
  34 --      the register assignments from the different sources match up.
  35 --
  36 type BlockAssignment freeRegs
  37         = BlockMap (freeRegs, RegMap Loc)
  38
  39
  40 -- | Where a vreg is currently stored
  41 --      A temporary can be marked as living in both a register and memory
  42 --      (InBoth), for example if it was recently loaded from a spill location.
  43 --      This makes it cheap to spill (no save instruction required), but we
  44 --      have to be careful to turn this into InReg if the value in the
  45 --      register is changed.
  46
  47 --      This is also useful when a temporary is about to be clobbered.  We
  48 --      save it in a spill location, but mark it as InBoth because the current
  49 --      instruction might still want to read it.
  50 --
  51 data Loc
  52         -- | vreg is in a register
  53         = InReg   !RealReg
  54
  55         -- | vreg is held in a stack slot
  56         | InMem   {-# UNPACK #-}  !StackSlot
  57
  58
  59         -- | vreg is held in both a register and a stack slot
  60         | InBoth   !RealReg
  61                    {-# UNPACK #-} !StackSlot
  62         deriving (Eq, Show, Ord)
  63
  64 instance Outputable Loc where
  65         ppr l = text (show l)
  66
  67
  68 -- | Get the reg numbers stored in this Loc.
  69 regsOfLoc :: Loc -> [RealReg]
  70 regsOfLoc (InReg r)    = [r]
  71 regsOfLoc (InBoth r _) = [r]
  72 regsOfLoc (InMem _)    = []
  73
  74
  75 -- | Reasons why instructions might be inserted by the spiller.
  76 --      Used when generating stats for -ddrop-asm-stats.
  77 --
  78 data SpillReason
  79         -- | vreg was spilled to a slot so we could use its
  80         --      current hreg for another vreg
  81         = SpillAlloc    !Unique
  82
  83         -- | vreg was moved because its hreg was clobbered
  84         | SpillClobber  !Unique
  85
  86         -- | vreg was loaded from a spill slot
  87         | SpillLoad     !Unique
  88
  89         -- | reg-reg move inserted during join to targets
  90         | SpillJoinRR   !Unique
  91
  92         -- | reg-mem move inserted during join to targets
  93         | SpillJoinRM   !Unique
  94
  95
  96 -- | Used to carry interesting stats out of the register allocator.
  97 data RegAllocStats
  98         = RegAllocStats
  99         { ra_spillInstrs        :: UniqFM [Int] }
 100
 101
 102 -- | The register alloctor state
 103 data RA_State freeRegs
 104         = RA_State
 105
 106         {
 107         -- | the current mapping from basic blocks to
 108         --      the register assignments at the beginning of that block.
 109           ra_blockassig :: BlockAssignment freeRegs
 110
 111         -- | free machine registers
 112         , ra_freeregs   :: !freeRegs
 113
 114         -- | assignment of temps to locations
 115         , ra_assig      :: RegMap Loc
 116
 117         -- | current stack delta
 118         , ra_delta      :: Int
 119
 120         -- | free stack slots for spilling
 121         , ra_stack      :: StackMap
 122
 123         -- | unique supply for generating names for join point fixup blocks.
 124         , ra_us         :: UniqSupply
 125
 126         -- | Record why things were spilled, for -ddrop-asm-stats.
 127         --      Just keep a list here instead of a map of regs -> reasons.
 128         --      We don't want to slow down the allocator if we're not going to emit the stats.
 129         , ra_spills     :: [SpillReason] }
 130
 131
 132 -- | The register allocator monad type.
 133 newtype RegM freeRegs a
 134         = RegM { unReg :: RA_State freeRegs -> (# RA_State freeRegs, a #) }
 135
 136