never executed always true always false
1 {-# LANGUAGE GADTs #-}
2 {-# LANGUAGE ScopedTypeVariables #-}
3
4 module GHC.CmmToAsm.Reg.Graph.SpillCost (
5 SpillCostRecord,
6 plusSpillCostRecord,
7 pprSpillCostRecord,
8
9 SpillCostInfo,
10 zeroSpillCostInfo,
11 plusSpillCostInfo,
12
13 slurpSpillCostInfo,
14 chooseSpill,
15
16 lifeMapFromSpillCostInfo
17 ) where
18 import GHC.Prelude
19
20 import GHC.CmmToAsm.Reg.Liveness
21 import GHC.CmmToAsm.Instr
22 import GHC.Platform.Reg.Class
23 import GHC.Platform.Reg
24
25 import GHC.Data.Graph.Base
26
27 import GHC.Cmm.Dataflow.Collections (mapLookup)
28 import GHC.Cmm.Dataflow.Label
29 import GHC.Cmm
30 import GHC.Types.Unique.FM
31 import GHC.Types.Unique.Set
32 import GHC.Data.Graph.Directed (flattenSCCs)
33 import GHC.Utils.Outputable
34 import GHC.Utils.Panic
35 import GHC.Platform
36 import GHC.Utils.Monad.State.Strict
37 import GHC.CmmToAsm.CFG
38
39 import Data.List (nub, minimumBy)
40 import Data.Maybe
41 import Control.Monad (join)
42
43
44 -- | Records the expected cost to spill some register.
45 type SpillCostRecord
46 = ( VirtualReg -- register name
47 , Int -- number of writes to this reg
48 , Int -- number of reads from this reg
49 , Int) -- number of instrs this reg was live on entry to
50
51
52 -- | Map of `SpillCostRecord`
53 type SpillCostInfo
54 = UniqFM VirtualReg SpillCostRecord
55
56 type SpillCostState = State SpillCostInfo ()
57
58 -- | An empty map of spill costs.
59 zeroSpillCostInfo :: SpillCostInfo
60 zeroSpillCostInfo = emptyUFM
61
62
63 -- | Add two spill cost infos.
64 plusSpillCostInfo :: SpillCostInfo -> SpillCostInfo -> SpillCostInfo
65 plusSpillCostInfo sc1 sc2
66 = plusUFM_C plusSpillCostRecord sc1 sc2
67
68
69 -- | Add two spill cost records.
70 plusSpillCostRecord :: SpillCostRecord -> SpillCostRecord -> SpillCostRecord
71 plusSpillCostRecord (r1, a1, b1, c1) (r2, a2, b2, c2)
72 | r1 == r2 = (r1, a1 + a2, b1 + b2, c1 + c2)
73 | otherwise = error "RegSpillCost.plusRegInt: regs don't match"
74
75
76 -- | Slurp out information used for determining spill costs.
77 --
78 -- For each vreg, the number of times it was written to, read from,
79 -- and the number of instructions it was live on entry to (lifetime)
80 --
81 slurpSpillCostInfo :: forall instr statics. Instruction instr
82 => Platform
83 -> Maybe CFG
84 -> LiveCmmDecl statics instr
85 -> SpillCostInfo
86
87 slurpSpillCostInfo platform cfg cmm
88 = execState (countCmm cmm) zeroSpillCostInfo
89 where
90 countCmm CmmData{} = return ()
91 countCmm (CmmProc info _ _ sccs)
92 = mapM_ (countBlock info freqMap)
93 $ flattenSCCs sccs
94 where
95 LiveInfo _ entries _ _ = info
96 freqMap = (fst . mkGlobalWeights (head entries)) <$> cfg
97
98 -- Lookup the regs that are live on entry to this block in
99 -- the info table from the CmmProc.
100 countBlock info freqMap (BasicBlock blockId instrs)
101 | LiveInfo _ _ blockLive _ <- info
102 , Just rsLiveEntry <- mapLookup blockId blockLive
103 , rsLiveEntry_virt <- takeVirtuals rsLiveEntry
104 = countLIs (ceiling $ blockFreq freqMap blockId) rsLiveEntry_virt instrs
105
106 | otherwise
107 = error "RegAlloc.SpillCost.slurpSpillCostInfo: bad block"
108
109
110 countLIs :: Int -> UniqSet VirtualReg -> [LiveInstr instr] -> SpillCostState
111 countLIs _ _ []
112 = return ()
113
114 -- Skip over comment and delta pseudo instrs.
115 countLIs scale rsLive (LiveInstr instr Nothing : lis)
116 | isMetaInstr instr
117 = countLIs scale rsLive lis
118
119 | otherwise
120 = pprPanic "RegSpillCost.slurpSpillCostInfo"
121 $ text "no liveness information on instruction " <> pprInstr platform instr
122
123 countLIs scale rsLiveEntry (LiveInstr instr (Just live) : lis)
124 = do
125 -- Increment the lifetime counts for regs live on entry to this instr.
126 mapM_ incLifetime $ nonDetEltsUniqSet rsLiveEntry
127 -- This is non-deterministic but we do not
128 -- currently support deterministic code-generation.
129 -- See Note [Unique Determinism and code generation]
130
131 -- Increment counts for what regs were read/written from.
132 let (RU read written) = regUsageOfInstr platform instr
133 mapM_ (incUses scale) $ catMaybes $ map takeVirtualReg $ nub read
134 mapM_ (incDefs scale) $ catMaybes $ map takeVirtualReg $ nub written
135
136 -- Compute liveness for entry to next instruction.
137 let liveDieRead_virt = takeVirtuals (liveDieRead live)
138 let liveDieWrite_virt = takeVirtuals (liveDieWrite live)
139 let liveBorn_virt = takeVirtuals (liveBorn live)
140
141 let rsLiveAcross
142 = rsLiveEntry `minusUniqSet` liveDieRead_virt
143
144 let rsLiveNext
145 = (rsLiveAcross `unionUniqSets` liveBorn_virt)
146 `minusUniqSet` liveDieWrite_virt
147
148 countLIs scale rsLiveNext lis
149
150 incDefs count reg = modify $ \s -> addToUFM_C plusSpillCostRecord s reg (reg, count, 0, 0)
151 incUses count reg = modify $ \s -> addToUFM_C plusSpillCostRecord s reg (reg, 0, count, 0)
152 incLifetime reg = modify $ \s -> addToUFM_C plusSpillCostRecord s reg (reg, 0, 0, 1)
153
154 blockFreq :: Maybe (LabelMap Double) -> Label -> Double
155 blockFreq freqs bid
156 | Just freq <- join (mapLookup bid <$> freqs)
157 = max 1.0 (10000 * freq)
158 | otherwise
159 = 1.0 -- Only if no cfg given
160
161 -- | Take all the virtual registers from this set.
162 takeVirtuals :: UniqSet Reg -> UniqSet VirtualReg
163 takeVirtuals set = mkUniqSet
164 [ vr | RegVirtual vr <- nonDetEltsUniqSet set ]
165 -- See Note [Unique Determinism and code generation]
166
167
168 -- | Choose a node to spill from this graph
169 chooseSpill
170 :: SpillCostInfo
171 -> Graph VirtualReg RegClass RealReg
172 -> VirtualReg
173
174 chooseSpill info graph
175 = let cost = spillCost_length info graph
176 node = minimumBy (\n1 n2 -> compare (cost $ nodeId n1) (cost $ nodeId n2))
177 $ nonDetEltsUFM $ graphMap graph
178 -- See Note [Unique Determinism and code generation]
179
180 in nodeId node
181
182
183 -------------------------------------------------------------------------------
184 -- | Chaitins spill cost function is:
185 --
186 -- cost = sum loadCost * freq (u) + sum storeCost * freq (d)
187 -- u <- uses (v) d <- defs (v)
188 --
189 -- There are no loops in our code at the moment, so we can set the freq's to 1.
190 --
191 -- If we don't have live range splitting then Chaitins function performs badly
192 -- if we have lots of nested live ranges and very few registers.
193 --
194 -- v1 v2 v3
195 -- def v1 .
196 -- use v1 .
197 -- def v2 . .
198 -- def v3 . . .
199 -- use v1 . . .
200 -- use v3 . . .
201 -- use v2 . .
202 -- use v1 .
203 --
204 -- defs uses degree cost
205 -- v1: 1 3 3 1.5
206 -- v2: 1 2 3 1.0
207 -- v3: 1 1 3 0.666
208 --
209 -- v3 has the lowest cost, but if we only have 2 hardregs and we insert
210 -- spill code for v3 then this isn't going to improve the colorability of
211 -- the graph.
212 --
213 -- When compiling SHA1, which as very long basic blocks and some vregs
214 -- with very long live ranges the allocator seems to try and spill from
215 -- the inside out and eventually run out of stack slots.
216 --
217 -- Without live range splitting, its's better to spill from the outside
218 -- in so set the cost of very long live ranges to zero
219 --
220
221 -- spillCost_chaitin
222 -- :: SpillCostInfo
223 -- -> Graph VirtualReg RegClass RealReg
224 -- -> VirtualReg
225 -- -> Float
226
227 -- spillCost_chaitin info graph reg
228 -- -- Spilling a live range that only lives for 1 instruction
229 -- -- isn't going to help us at all - and we definitely want to avoid
230 -- -- trying to re-spill previously inserted spill code.
231 -- | lifetime <= 1 = 1/0
232
233 -- -- It's unlikely that we'll find a reg for a live range this long
234 -- -- better to spill it straight up and not risk trying to keep it around
235 -- -- and have to go through the build/color cycle again.
236
237 -- -- To facility this we scale down the spill cost of long ranges.
238 -- -- This makes sure long ranges are still spilled first.
239 -- -- But this way spill cost remains relevant for long live
240 -- -- ranges.
241 -- | lifetime >= 128
242 -- = (spillCost / conflicts) / 10.0
243
244
245 -- -- Otherwise revert to chaitin's regular cost function.
246 -- | otherwise = (spillCost / conflicts)
247 -- where
248 -- !spillCost = fromIntegral (uses + defs) :: Float
249 -- conflicts = fromIntegral (nodeDegree classOfVirtualReg graph reg)
250 -- (_, defs, uses, lifetime)
251 -- = fromMaybe (reg, 0, 0, 0) $ lookupUFM info reg
252
253
254 -- Just spill the longest live range.
255 spillCost_length
256 :: SpillCostInfo
257 -> Graph VirtualReg RegClass RealReg
258 -> VirtualReg
259 -> Float
260
261 spillCost_length info _ reg
262 | lifetime <= 1 = 1/0
263 | otherwise = 1 / fromIntegral lifetime
264 where (_, _, _, lifetime)
265 = fromMaybe (reg, 0, 0, 0)
266 $ lookupUFM info reg
267
268
269 -- | Extract a map of register lifetimes from a `SpillCostInfo`.
270 lifeMapFromSpillCostInfo :: SpillCostInfo -> UniqFM VirtualReg (VirtualReg, Int)
271 lifeMapFromSpillCostInfo info
272 = listToUFM
273 $ map (\(r, _, _, life) -> (r, (r, life)))
274 $ nonDetEltsUFM info
275 -- See Note [Unique Determinism and code generation]
276
277
278 -- | Determine the degree (number of neighbors) of this node which
279 -- have the same class.
280 nodeDegree
281 :: (VirtualReg -> RegClass)
282 -> Graph VirtualReg RegClass RealReg
283 -> VirtualReg
284 -> Int
285
286 nodeDegree classOfVirtualReg graph reg
287 | Just node <- lookupUFM (graphMap graph) reg
288
289 , virtConflicts
290 <- length
291 $ filter (\r -> classOfVirtualReg r == classOfVirtualReg reg)
292 $ nonDetEltsUniqSet
293 -- See Note [Unique Determinism and code generation]
294 $ nodeConflicts node
295
296 = virtConflicts + sizeUniqSet (nodeExclusions node)
297
298 | otherwise
299 = 0
300
301
302 -- | Show a spill cost record, including the degree from the graph
303 -- and final calculated spill cost.
304 pprSpillCostRecord
305 :: (VirtualReg -> RegClass)
306 -> (Reg -> SDoc)
307 -> Graph VirtualReg RegClass RealReg
308 -> SpillCostRecord
309 -> SDoc
310
311 pprSpillCostRecord regClass pprReg graph (reg, uses, defs, life)
312 = hsep
313 [ pprReg (RegVirtual reg)
314 , ppr uses
315 , ppr defs
316 , ppr life
317 , ppr $ nodeDegree regClass graph reg
318 , text $ show $ (fromIntegral (uses + defs)
319 / fromIntegral (nodeDegree regClass graph reg) :: Float) ]
320