compiler/nativeGen/RegArchBase.hs

   1
   2 -- | Utils for calculating general worst, bound, squeese and free, functions.
   3 --
   4 --      as per: "A Generalized Algorithm for Graph-Coloring Register Allocation"
   5 --              Michael Smith, Normal Ramsey, Glenn Holloway.
   6 --              PLDI 2004
   7 --
   8 --      These general versions are not used in GHC proper because they are too slow.
   9 --      Instead, hand written optimised versions are provided for each architecture
  10 --      in MachRegs*.hs
  11 --
  12 --      This code is here because we can test the architecture specific code against it.
  13 --
  14 --
  15 module RegArchBase (
  16         RegClass(..),
  17         Reg(..),
  18         RegSub(..),
  19
  20         worst,
  21         bound,
  22         squeese
  23 )
  24
  25 where
  26
  27
  28 -----
  29 import qualified Data.Set       as Set
  30 import Data.Set                 (Set)
  31
  32 -- import qualified Data.Map    as Map
  33 -- import Data.Map                      (Map)
  34
  35
  36 -- Some basic register classes.
  37 --      These aren't nessesarally in 1-to-1 correspondance with the allocatable
  38 --      RegClasses in MachRegs.hs
  39 --
  40 data RegClass
  41         -- general purpose regs
  42         = ClassG32      -- 32 bit GPRs
  43         | ClassG16      -- 16 bit GPRs
  44         | ClassG8       -- 8  bit GPRs
  45
  46         -- floating point regs
  47         | ClassF64      -- 64 bit FPRs
  48         deriving (Show, Ord, Eq)
  49
  50
  51 -- | A register of some class
  52 data Reg
  53         -- a register of some class
  54         = Reg RegClass Int
  55
  56         -- a sub-component of one of the other regs
  57         | RegSub RegSub Reg
  58         deriving (Show, Ord, Eq)
  59
  60
  61 -- | A subcomponent of another register
  62 data RegSub
  63         = SubL16        -- lowest 16 bits
  64         | SubL8         -- lowest  8 bits
  65         | SubL8H        -- second lowest 8 bits
  66         deriving (Show, Enum, Ord, Eq)
  67
  68
  69
  70 -- | Worst case displacement
  71 --
  72 --      a node N of classN has some number of neighbors,
  73 --      all of which are from classC.
  74 --
  75 --      (worst neighbors classN classC) is the maximum number of potential
  76 --      colors for N that can be lost by coloring its neighbors.
  77
  78 -- This should be hand coded/cached for each particular architecture,
  79 --      because the compute time is very long..
  80
  81 worst
  82         :: (RegClass    -> Set Reg)
  83         -> (Reg         -> Set Reg)
  84         -> Int -> RegClass -> RegClass -> Int
  85
  86 worst regsOfClass regAlias neighbors classN classC
  87  = let  regAliasS regs  = unionsS $ Set.map regAlias regs
  88
  89         -- all the regs in classes N, C
  90         regsN           = regsOfClass classN
  91         regsC           = regsOfClass classC
  92
  93         -- all the possible subsets of c which have size < m
  94         regsS           = Set.filter (\s -> Set.size s >= 1 && Set.size s <= neighbors)
  95                         $ powerset regsC
  96
  97         -- for each of the subsets of C, the regs which conflict with posiblities for N
  98         regsS_conflict
  99                 = Set.map (\s -> Set.intersection regsN (regAliasS s)) regsS
 100
 101   in    Set.findMax $ Set.map Set.size $ regsS_conflict
 102
 103
 104 -- | For a node N of classN and neighbors of classesC
 105 --      (bound classN classesC) is the maximum number of potential
 106 --      colors for N that can be lost by coloring its neighbors.
 107 --
 108
 109 bound
 110         :: (RegClass    -> Set Reg)
 111         -> (Reg         -> Set Reg)
 112         -> RegClass -> [RegClass] -> Int
 113
 114 bound regsOfClass regAlias classN classesC
 115  = let  regAliasS regs  = unionsS $ Set.map regAlias regs
 116
 117         regsC_aliases
 118                 = Set.unions
 119                 $ map (regAliasS . regsOfClass) classesC
 120
 121         overlap = Set.intersection (regsOfClass classN) regsC_aliases
 122
 123    in   Set.size overlap
 124
 125
 126 -- | The total squeese on a particular node with a list of neighbors.
 127 --
 128 --      A version of this should be constructed for each particular architecture,
 129 --      possibly including uses of bound, so that alised registers don't get counted
 130 --      twice, as per the paper.
 131 --
 132 squeese
 133         :: (RegClass    -> Set Reg)
 134         -> (Reg         -> Set Reg)
 135         -> RegClass -> [(Int, RegClass)] -> Int
 136
 137 squeese regsOfClass regAlias classN countCs
 138         = sum (map (\(i, classC) -> worst regsOfClass regAlias i classN classC) countCs)
 139
 140
 141 -- | powerset (for lists)
 142 powersetL :: Ord a => [a] -> [[a]]
 143 powersetL       = map concat . mapM (\x -> [[],[x]])
 144
 145 -- | powerset (for sets)
 146 powerset :: Ord a => Set a -> Set (Set a)
 147 powerset s      = Set.fromList $ map Set.fromList $ powersetL $ Set.toList s
 148
 149 -- | unions (for sets)
 150 unionsS :: Ord a => Set (Set a) -> Set a
 151 unionsS ss      = Set.unions $ Set.toList ss
 152
 153