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.
15 module RegAlloc.Graph.ArchBase (
30 -- Some basic register classes.
31 -- These aren't nessesarally in 1-to-1 correspondance with the allocatable
32 -- RegClasses in MachRegs.hs
34 -- general purpose regs
35 = ClassG32 -- 32 bit GPRs
36 | ClassG16 -- 16 bit GPRs
37 | ClassG8 -- 8 bit GPRs
39 -- floating point regs
40 | ClassF64 -- 64 bit FPRs
41 deriving (Show, Eq, Enum)
44 -- | A register of some class
46 -- a register of some class
49 -- a sub-component of one of the other regs
54 -- | so we can put regs in UniqSets
55 instance Uniquable Reg where
58 $ fromEnum c * 1000 + i
60 getUnique (RegSub s (Reg c i))
62 $ fromEnum s * 10000 + fromEnum c * 1000 + i
64 getUnique (RegSub _ (RegSub _ _))
65 = error "RegArchBase.getUnique: can't have a sub-reg of a sub-reg."
67 -- | A subcomponent of another register
69 = SubL16 -- lowest 16 bits
70 | SubL8 -- lowest 8 bits
71 | SubL8H -- second lowest 8 bits
72 deriving (Show, Enum, Ord, Eq)
75 -- | Worst case displacement
77 -- a node N of classN has some number of neighbors,
78 -- all of which are from classC.
80 -- (worst neighbors classN classC) is the maximum number of potential
81 -- colors for N that can be lost by coloring its neighbors.
83 -- This should be hand coded/cached for each particular architecture,
84 -- because the compute time is very long..
86 :: (RegClass -> UniqSet Reg)
87 -> (Reg -> UniqSet Reg)
88 -> Int -> RegClass -> RegClass -> Int
90 worst regsOfClass regAlias neighbors classN classC
91 = let regAliasS regs = unionManyUniqSets
95 -- all the regs in classes N, C
96 regsN = regsOfClass classN
97 regsC = regsOfClass classC
99 -- all the possible subsets of c which have size < m
100 regsS = filter (\s -> sizeUniqSet s >= 1 && sizeUniqSet s <= neighbors)
103 -- for each of the subsets of C, the regs which conflict with posiblities for N
105 = map (\s -> intersectUniqSets regsN (regAliasS s)) regsS
107 in maximum $ map sizeUniqSet $ regsS_conflict
110 -- | For a node N of classN and neighbors of classesC
111 -- (bound classN classesC) is the maximum number of potential
112 -- colors for N that can be lost by coloring its neighbors.
114 :: (RegClass -> UniqSet Reg)
115 -> (Reg -> UniqSet Reg)
116 -> RegClass -> [RegClass] -> Int
118 bound regsOfClass regAlias classN classesC
119 = let regAliasS regs = unionManyUniqSets
125 $ map (regAliasS . regsOfClass) classesC
127 overlap = intersectUniqSets (regsOfClass classN) regsC_aliases
129 in sizeUniqSet overlap
132 -- | The total squeese on a particular node with a list of neighbors.
134 -- A version of this should be constructed for each particular architecture,
135 -- possibly including uses of bound, so that alised registers don't get counted
136 -- twice, as per the paper.
138 :: (RegClass -> UniqSet Reg)
139 -> (Reg -> UniqSet Reg)
140 -> RegClass -> [(Int, RegClass)] -> Int
142 squeese regsOfClass regAlias classN countCs
143 = sum (map (\(i, classC) -> worst regsOfClass regAlias i classN classC) countCs)
146 -- | powerset (for lists)
147 powersetL :: [a] -> [[a]]
148 powersetL = map concat . mapM (\x -> [[],[x]])
150 -- | powersetLS (list of sets)
151 powersetLS :: Uniquable a => UniqSet a -> [UniqSet a]
152 powersetLS s = map mkUniqSet $ powersetL $ uniqSetToList s
155 -- | unions (for sets)
156 unionsS :: Ord a => Set (Set a) -> Set a
157 unionsS ss = Set.unions $ Set.toList ss