Base.hs

{-# LANGUAGE RecordWildCards #-}

-- | Put common type definitions here to break recursive module dependencies.

module GHC.CmmToAsm.Reg.Linear.Base (
        BlockAssignment,
        lookupBlockAssignment,
        lookupFirstUsed,
        emptyBlockAssignment,
        updateBlockAssignment,

        Loc(..),
        regsOfLoc,
        RealRegUsage(..),

        -- for stats
        SpillReason(..),
        RegAllocStats(..),

        -- the allocator monad
        RA_State(..),
)

where

import GHC.Prelude

import GHC.CmmToAsm.Reg.Linear.StackMap
import GHC.CmmToAsm.Reg.Liveness
import GHC.CmmToAsm.Config
import GHC.Platform.Reg

import GHC.Utils.Outputable
import GHC.Types.Unique
import GHC.Types.Unique.FM
import GHC.Types.Unique.DSM
import GHC.Cmm.BlockId
import GHC.Cmm.Dataflow.Label
import GHC.CmmToAsm.Reg.Utils
import GHC.CmmToAsm.Format

import Data.Function ( on )

data ReadingOrWriting = Reading | Writing deriving (Eq,Ord)

-- | Used to store the register assignment on entry to a basic block.
--      We use this to handle join points, where multiple branch instructions
--      target a particular label. We have to insert fixup code to make
--      the register assignments from the different sources match up.
--
data BlockAssignment freeRegs
        = BlockAssignment { blockMap :: !(BlockMap (freeRegs, RegMap Loc))
                          , firstUsed :: !(UniqFM VirtualReg RealReg) }

-- | Find the register mapping for a specific BlockId.
lookupBlockAssignment :: BlockId -> BlockAssignment freeRegs -> Maybe (freeRegs, RegMap Loc)
lookupBlockAssignment bid ba = mapLookup bid (blockMap ba)

-- | Lookup which register a virtual register was first assigned to.
lookupFirstUsed :: VirtualReg -> BlockAssignment freeRegs -> Maybe RealReg
lookupFirstUsed vr ba = lookupUFM (firstUsed ba) vr

-- | An initial empty 'BlockAssignment'
emptyBlockAssignment :: BlockAssignment freeRegs
emptyBlockAssignment = BlockAssignment mapEmpty mempty

-- | Add new register mappings for a specific block.
updateBlockAssignment :: BlockId
  -> (freeRegs, RegMap Loc)
  -> BlockAssignment freeRegs
  -> BlockAssignment freeRegs
updateBlockAssignment dest (freeRegs, regMap) (BlockAssignment {..}) =
  BlockAssignment (mapInsert dest (freeRegs, regMap) blockMap)
                  (mergeUFM combWithExisting id (mapMaybeUFM fromLoc) (firstUsed) (toVRegMap regMap))
  where
    -- The blocks are processed in dependency order, so if there's already an
    -- entry in the map then keep that assignment rather than writing the new
    -- assignment.
    combWithExisting :: RealReg -> Loc -> Maybe RealReg
    combWithExisting old_reg _ = Just $ old_reg

    fromLoc :: Loc -> Maybe RealReg
    fromLoc (InReg rr) = Just $ realReg rr
    fromLoc (InBoth rr _) = Just $ realReg rr
    fromLoc _ = Nothing


-- | Where a vreg is currently stored
--      A temporary can be marked as living in both a register and memory
--      (InBoth), for example if it was recently loaded from a spill location.
--      This makes it cheap to spill (no save instruction required), but we
--      have to be careful to turn this into InReg if the value in the
--      register is changed.

--      This is also useful when a temporary is about to be clobbered.  We
--      save it in a spill location, but mark it as InBoth because the current
--      instruction might still want to read it.
--
data Loc
        -- | vreg is in a register
        = InReg   {-# UNPACK #-} !RealRegUsage

        -- | vreg is held in stack slots
        | InMem   {-# UNPACK #-}  !StackSlot


        -- | vreg is held in both a register and stack slots
        | InBoth   {-# UNPACK #-} !RealRegUsage
                   {-# UNPACK #-} !StackSlot
        deriving (Eq, Ord, Show)

instance Outputable Loc where
        ppr l = text (show l)

-- | A 'RealReg', together with the specific 'Format' it is used at.
data RealRegUsage
  = RealRegUsage
    { realReg :: !RealReg
    , realRegFormat :: !Format
    } deriving Show

instance Outputable RealRegUsage where
  ppr (RealRegUsage r fmt) = ppr r <> dcolon <+> ppr fmt

-- NB: these instances only compare the underlying 'RealReg', as that is what
-- is important for register allocation.
--
-- (It would nonetheless be a good idea to remove these instances.)
instance Eq RealRegUsage where
  (==) = (==) `on` realReg
instance Ord RealRegUsage where
  compare = compare `on` realReg

-- | Get the reg numbers stored in this Loc.
regsOfLoc :: Loc -> [RealRegUsage]
regsOfLoc (InReg r)    = [r]
regsOfLoc (InBoth r _) = [r]
regsOfLoc (InMem _)    = []


-- | Reasons why instructions might be inserted by the spiller.
--      Used when generating stats for -ddrop-asm-stats.
--
data SpillReason
        -- | vreg was spilled to a slot so we could use its
        --      current hreg for another vreg
        = SpillAlloc    !Unique

        -- | vreg was moved because its hreg was clobbered
        | SpillClobber  !Unique

        -- | vreg was loaded from a spill slot
        | SpillLoad     !Unique

        -- | reg-reg move inserted during join to targets
        | SpillJoinRR   !Unique

        -- | reg-mem move inserted during join to targets
        | SpillJoinRM   !Unique


-- | Used to carry interesting stats out of the register allocator.
data RegAllocStats
        = RegAllocStats
        { ra_spillInstrs        :: UniqFM Unique [Int] -- Keys are the uniques of regs
                                                       -- and taken from SpillReason
                                                       -- See Note [UniqFM and the register allocator]
        , ra_fixupList     :: [(BlockId,BlockId,BlockId)]
        -- ^ (from,fixup,to) : We inserted fixup code between from and to
        }


-- | The register allocator state
data RA_State freeRegs
        = RA_State

        {
        -- | the current mapping from basic blocks to
        --      the register assignments at the beginning of that block.
          ra_blockassig :: BlockAssignment freeRegs

        -- | free machine registers
        , ra_freeregs   :: !freeRegs

        -- | assignment of temps to locations
        , ra_assig      :: RegMap Loc

        -- | current stack delta
        , ra_delta      :: Int

        -- | free stack slots for spilling
        , ra_stack      :: StackMap

        -- | unique supply for generating names for join point fixup blocks.
        , ra_us         :: DUniqSupply

        -- | Record why things were spilled, for -ddrop-asm-stats.
        --      Just keep a list here instead of a map of regs -> reasons.
        --      We don't want to slow down the allocator if we're not going to emit the stats.
        , ra_spills     :: [SpillReason]

        -- | Native code generator configuration
        , ra_config     :: !NCGConfig

        -- | (from,fixup,to) : We inserted fixup code between from and to
        , ra_fixups     :: [(BlockId,BlockId,BlockId)]

        }