Typos in comments (notes too) [ci skip]
[ghc.git] / compiler / nativeGen / RegAlloc / Graph / ArchBase.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
13 -- it.
14 --
15 module RegAlloc.Graph.ArchBase (
16 RegClass(..),
17 Reg(..),
18 RegSub(..),
19
20 worst,
21 bound,
22 squeese
23 ) where
24 import UniqSet
25 import UniqFM
26 import Unique
27
28
29 -- Some basic register classes.
30 -- These aren't necessarily in 1-to-1 correspondence with the allocatable
31 -- RegClasses in MachRegs.hs
32 data RegClass
33 -- general purpose regs
34 = ClassG32 -- 32 bit GPRs
35 | ClassG16 -- 16 bit GPRs
36 | ClassG8 -- 8 bit GPRs
37
38 -- floating point regs
39 | ClassF64 -- 64 bit FPRs
40 deriving (Show, Eq, Enum)
41
42
43 -- | A register of some class
44 data Reg
45 -- a register of some class
46 = Reg RegClass Int
47
48 -- a sub-component of one of the other regs
49 | RegSub RegSub Reg
50 deriving (Show, Eq)
51
52
53 -- | so we can put regs in UniqSets
54 instance Uniquable Reg where
55 getUnique (Reg c i)
56 = mkRegSingleUnique
57 $ fromEnum c * 1000 + i
58
59 getUnique (RegSub s (Reg c i))
60 = mkRegSubUnique
61 $ fromEnum s * 10000 + fromEnum c * 1000 + i
62
63 getUnique (RegSub _ (RegSub _ _))
64 = error "RegArchBase.getUnique: can't have a sub-reg of a sub-reg."
65
66
67 -- | A subcomponent of another register
68 data RegSub
69 = SubL16 -- lowest 16 bits
70 | SubL8 -- lowest 8 bits
71 | SubL8H -- second lowest 8 bits
72 deriving (Show, Enum, Ord, Eq)
73
74
75 -- | Worst case displacement
76 --
77 -- a node N of classN has some number of neighbors,
78 -- all of which are from classC.
79 --
80 -- (worst neighbors classN classC) is the maximum number of potential
81 -- colors for N that can be lost by coloring its neighbors.
82 --
83 -- This should be hand coded/cached for each particular architecture,
84 -- because the compute time is very long..
85 worst :: (RegClass -> UniqSet Reg)
86 -> (Reg -> UniqSet Reg)
87 -> Int -> RegClass -> RegClass -> Int
88
89 worst regsOfClass regAlias neighbors classN classC
90 = let regAliasS regs = unionManyUniqSets
91 $ map regAlias
92 $ nonDetEltsUniqSet regs
93 -- This is non-deterministic but we do not
94 -- currently support deterministic code-generation.
95 -- See Note [Unique Determinism and code generation]
96
97 -- all the regs in classes N, C
98 regsN = regsOfClass classN
99 regsC = regsOfClass classC
100
101 -- all the possible subsets of c which have size < m
102 regsS = filter (\s -> sizeUniqSet s >= 1
103 && sizeUniqSet s <= neighbors)
104 $ powersetLS regsC
105
106 -- for each of the subsets of C, the regs which conflict
107 -- with posiblities for N
108 regsS_conflict
109 = map (\s -> intersectUniqSets regsN (regAliasS s)) regsS
110
111 in maximum $ map sizeUniqSet $ regsS_conflict
112
113
114 -- | For a node N of classN and neighbors of classesC
115 -- (bound classN classesC) is the maximum number of potential
116 -- colors for N that can be lost by coloring its neighbors.
117 bound :: (RegClass -> UniqSet Reg)
118 -> (Reg -> UniqSet Reg)
119 -> RegClass -> [RegClass] -> Int
120
121 bound regsOfClass regAlias classN classesC
122 = let regAliasS regs = unionManyUniqSets
123 $ map regAlias
124 $ nonDetEltsUFM regs
125 -- See Note [Unique Determinism and code generation]
126
127 regsC_aliases
128 = unionManyUniqSets
129 $ map (regAliasS . getUniqSet . regsOfClass) classesC
130
131 overlap = intersectUniqSets (regsOfClass classN) regsC_aliases
132
133 in sizeUniqSet overlap
134
135
136 -- | The total squeese on a particular node with a list of neighbors.
137 --
138 -- A version of this should be constructed for each particular architecture,
139 -- possibly including uses of bound, so that alised registers don't get
140 -- counted twice, as per the paper.
141 squeese :: (RegClass -> UniqSet Reg)
142 -> (Reg -> UniqSet Reg)
143 -> RegClass -> [(Int, RegClass)] -> Int
144
145 squeese regsOfClass regAlias classN countCs
146 = sum
147 $ map (\(i, classC) -> worst regsOfClass regAlias i classN classC)
148 $ countCs
149
150
151 -- | powerset (for lists)
152 powersetL :: [a] -> [[a]]
153 powersetL = map concat . mapM (\x -> [[],[x]])
154
155
156 -- | powersetLS (list of sets)
157 powersetLS :: Uniquable a => UniqSet a -> [UniqSet a]
158 powersetLS s = map mkUniqSet $ powersetL $ nonDetEltsUniqSet s
159 -- See Note [Unique Determinism and code generation]