2 -- | Utils for calculating general worst, bound, squeese and free, functions.
4 -- as per: "A Generalized Algorithm for Graph-Coloring Register Allocation"
5 -- Michael Smith, Normal Ramsey, Glenn Holloway.
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
12 -- This code is here because we can test the architecture specific code against it.
29 import qualified Data.Set as Set
32 -- import qualified Data.Map as Map
33 -- import Data.Map (Map)
36 -- Some basic register classes.
37 -- These aren't nessesarally in 1-to-1 correspondance with the allocatable
38 -- RegClasses in MachRegs.hs
41 -- general purpose regs
42 = ClassG32 -- 32 bit GPRs
43 | ClassG16 -- 16 bit GPRs
44 | ClassG8 -- 8 bit GPRs
46 -- floating point regs
47 | ClassF64 -- 64 bit FPRs
48 deriving (Show, Ord, Eq)
51 -- | A register of some class
53 -- a register of some class
56 -- a sub-component of one of the other regs
58 deriving (Show, Ord, Eq)
61 -- | A subcomponent of another register
63 = SubL16 -- lowest 16 bits
64 | SubL8 -- lowest 8 bits
65 | SubL8H -- second lowest 8 bits
66 deriving (Show, Enum, Ord, Eq)
70 -- | Worst case displacement
72 -- a node N of classN has some number of neighbors,
73 -- all of which are from classC.
75 -- (worst neighbors classN classC) is the maximum number of potential
76 -- colors for N that can be lost by coloring its neighbors.
78 -- This should be hand coded/cached for each particular architecture,
79 -- because the compute time is very long..
82 :: (RegClass -> Set Reg)
84 -> Int -> RegClass -> RegClass -> Int
86 worst regsOfClass regAlias neighbors classN classC
87 = let regAliasS regs = unionsS $ Set.map regAlias regs
89 -- all the regs in classes N, C
90 regsN = regsOfClass classN
91 regsC = regsOfClass classC
93 -- all the possible subsets of c which have size < m
94 regsS = Set.filter (\s -> Set.size s >= 1 && Set.size s <= neighbors)
97 -- for each of the subsets of C, the regs which conflict with posiblities for N
99 = Set.map (\s -> Set.intersection regsN (regAliasS s)) regsS
101 in Set.findMax $ Set.map Set.size $ regsS_conflict
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.
110 :: (RegClass -> Set Reg)
112 -> RegClass -> [RegClass] -> Int
114 bound regsOfClass regAlias classN classesC
115 = let regAliasS regs = unionsS $ Set.map regAlias regs
119 $ map (regAliasS . regsOfClass) classesC
121 overlap = Set.intersection (regsOfClass classN) regsC_aliases
126 -- | The total squeese on a particular node with a list of neighbors.
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.
133 :: (RegClass -> Set Reg)
135 -> RegClass -> [(Int, RegClass)] -> Int
137 squeese regsOfClass regAlias classN countCs
138 = sum (map (\(i, classC) -> worst regsOfClass regAlias i classN classC) countCs)
141 -- | powerset (for lists)
142 powersetL :: Ord a => [a] -> [[a]]
143 powersetL = map concat . mapM (\x -> [[],[x]])
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
149 -- | unions (for sets)
150 unionsS :: Ord a => Set (Set a) -> Set a
151 unionsS ss = Set.unions $ Set.toList ss