-- | Utils for calculating general worst, bound, squeese and free, functions.
--
-- as per: "A Generalized Algorithm for Graph-Coloring Register Allocation"
-- Michael Smith, Normal Ramsey, Glenn Holloway.
-- PLDI 2004
--
-- These general versions are not used in GHC proper because they are too slow.
-- Instead, hand written optimised versions are provided for each architecture
-- in MachRegs*.hs
--
-- This code is here because we can test the architecture specific code against
-- it.
--
module RegAlloc.Graph.ArchBase (
RegClass(..),
Reg(..),
RegSub(..),
worst,
bound,
squeese
) where
import GhcPrelude
import UniqSet
import UniqFM
import Unique
-- Some basic register classes.
-- These aren't necessarily in 1-to-1 correspondence with the allocatable
-- RegClasses in MachRegs.hs
data RegClass
-- general purpose regs
= ClassG32 -- 32 bit GPRs
| ClassG16 -- 16 bit GPRs
| ClassG8 -- 8 bit GPRs
-- floating point regs
| ClassF64 -- 64 bit FPRs
deriving (Show, Eq, Enum)
-- | A register of some class
data Reg
-- a register of some class
= Reg RegClass Int
-- a sub-component of one of the other regs
| RegSub RegSub Reg
deriving (Show, Eq)
-- | so we can put regs in UniqSets
instance Uniquable Reg where
getUnique (Reg c i)
= mkRegSingleUnique
$ fromEnum c * 1000 + i
getUnique (RegSub s (Reg c i))
= mkRegSubUnique
$ fromEnum s * 10000 + fromEnum c * 1000 + i
getUnique (RegSub _ (RegSub _ _))
= error "RegArchBase.getUnique: can't have a sub-reg of a sub-reg."
-- | A subcomponent of another register
data RegSub
= SubL16 -- lowest 16 bits
| SubL8 -- lowest 8 bits
| SubL8H -- second lowest 8 bits
deriving (Show, Enum, Ord, Eq)
-- | Worst case displacement
--
-- a node N of classN has some number of neighbors,
-- all of which are from classC.
--
-- (worst neighbors classN classC) is the maximum number of potential
-- colors for N that can be lost by coloring its neighbors.
--
-- This should be hand coded/cached for each particular architecture,
-- because the compute time is very long..
worst :: (RegClass -> UniqSet Reg)
-> (Reg -> UniqSet Reg)
-> Int -> RegClass -> RegClass -> Int
worst regsOfClass regAlias neighbors classN classC
= let regAliasS regs = unionManyUniqSets
$ map regAlias
$ nonDetEltsUniqSet regs
-- This is non-deterministic but we do not
-- currently support deterministic code-generation.
-- See Note [Unique Determinism and code generation]
-- all the regs in classes N, C
regsN = regsOfClass classN
regsC = regsOfClass classC
-- all the possible subsets of c which have size < m
regsS = filter (\s -> sizeUniqSet s >= 1
&& sizeUniqSet s <= neighbors)
$ powersetLS regsC
-- for each of the subsets of C, the regs which conflict
-- with posiblities for N
regsS_conflict
= map (\s -> intersectUniqSets regsN (regAliasS s)) regsS
in maximum $ map sizeUniqSet $ regsS_conflict
-- | For a node N of classN and neighbors of classesC
-- (bound classN classesC) is the maximum number of potential
-- colors for N that can be lost by coloring its neighbors.
bound :: (RegClass -> UniqSet Reg)
-> (Reg -> UniqSet Reg)
-> RegClass -> [RegClass] -> Int
bound regsOfClass regAlias classN classesC
= let regAliasS regs = unionManyUniqSets
$ map regAlias
$ nonDetEltsUFM regs
-- See Note [Unique Determinism and code generation]
regsC_aliases
= unionManyUniqSets
$ map (regAliasS . getUniqSet . regsOfClass) classesC
overlap = intersectUniqSets (regsOfClass classN) regsC_aliases
in sizeUniqSet overlap
-- | The total squeese on a particular node with a list of neighbors.
--
-- A version of this should be constructed for each particular architecture,
-- possibly including uses of bound, so that alised registers don't get
-- counted twice, as per the paper.
squeese :: (RegClass -> UniqSet Reg)
-> (Reg -> UniqSet Reg)
-> RegClass -> [(Int, RegClass)] -> Int
squeese regsOfClass regAlias classN countCs
= sum
$ map (\(i, classC) -> worst regsOfClass regAlias i classN classC)
$ countCs
-- | powerset (for lists)
powersetL :: [a] -> [[a]]
powersetL = map concat . mapM (\x -> [[],[x]])
-- | powersetLS (list of sets)
powersetLS :: Uniquable a => UniqSet a -> [UniqSet a]
powersetLS s = map mkUniqSet $ powersetL $ nonDetEltsUniqSet s
-- See Note [Unique Determinism and code generation]