1 {-# OPTIONS -fno-warn-missing-signatures #-}
2 -- Carries interesting info for debugging / profiling of the
3 -- graph coloring register allocator.
6 module RegAlloc.Graph.Stats (
20 #include "nativeGen/NCG.h"
22 import qualified GraphColor as Color
23 import RegAlloc.Liveness
24 import RegAlloc.Graph.Spill
25 import RegAlloc.Graph.SpillCost
26 import RegAlloc.Graph.TrivColorable
40 data RegAllocStats instr
44 { raLiveCmm :: [LiveCmmTop instr] -- ^ initial code, with liveness
45 , raGraph :: Color.Graph VirtualReg RegClass RealReg -- ^ the initial, uncolored graph
46 , raSpillCosts :: SpillCostInfo } -- ^ information to help choose which regs to spill
50 { raCode :: [LiveCmmTop instr] -- ^ the code we tried to allocate registers for
51 , raGraph :: Color.Graph VirtualReg RegClass RealReg -- ^ the partially colored graph
52 , raCoalesced :: UniqFM VirtualReg -- ^ the regs that were coaleced
53 , raSpillStats :: SpillStats -- ^ spiller stats
54 , raSpillCosts :: SpillCostInfo -- ^ number of instrs each reg lives for
55 , raSpilled :: [LiveCmmTop instr] } -- ^ code with spill instructions added
57 -- a successful coloring
58 | RegAllocStatsColored
59 { raCode :: [LiveCmmTop instr] -- ^ the code we tried to allocate registers for
60 , raGraph :: Color.Graph VirtualReg RegClass RealReg -- ^ the uncolored graph
61 , raGraphColored :: Color.Graph VirtualReg RegClass RealReg -- ^ the coalesced and colored graph
62 , raCoalesced :: UniqFM VirtualReg -- ^ the regs that were coaleced
63 , raCodeCoalesced :: [LiveCmmTop instr] -- ^ code with coalescings applied
64 , raPatched :: [LiveCmmTop instr] -- ^ code with vregs replaced by hregs
65 , raSpillClean :: [LiveCmmTop instr] -- ^ code with unneeded spill\/reloads cleaned out
66 , raFinal :: [NatCmmTop instr] -- ^ final code
67 , raSRMs :: (Int, Int, Int) } -- ^ spill\/reload\/reg-reg moves present in this code
69 instance Outputable instr => Outputable (RegAllocStats instr) where
71 ppr (s@RegAllocStatsStart{})
73 $$ text "# Native code with liveness information."
76 $$ text "# Initial register conflict graph."
80 targetVirtualRegSqueeze
85 ppr (s@RegAllocStatsSpill{})
88 $$ text "# Code with liveness information."
92 -- $$ text "# Register conflict graph."
93 -- $$ Color.dotGraph regDotColor trivColorable (raGraph s)
96 $$ (if (not $ isNullUFM $ raCoalesced s)
97 then text "# Registers coalesced."
98 $$ (vcat $ map ppr $ ufmToList $ raCoalesced s)
102 -- $$ text "# Spill costs. reg uses defs lifetime degree cost"
103 -- $$ vcat (map (pprSpillCostRecord (raGraph s)) $ eltsUFM $ raSpillCosts s)
106 $$ text "# Spills inserted."
107 $$ ppr (raSpillStats s)
110 $$ text "# Code with spills inserted."
111 $$ (ppr (raSpilled s))
114 ppr (s@RegAllocStatsColored { raSRMs = (spills, reloads, moves) })
117 -- $$ text "# Register conflict graph (initial)."
118 -- $$ Color.dotGraph regDotColor trivColorable (raGraph s)
121 $$ text "# Code with liveness information."
125 $$ text "# Register conflict graph (colored)."
129 targetVirtualRegSqueeze
130 targetRealRegSqueeze)
134 $$ (if (not $ isNullUFM $ raCoalesced s)
135 then text "# Registers coalesced."
136 $$ (vcat $ map ppr $ ufmToList $ raCoalesced s)
140 $$ text "# Native code after coalescings applied."
141 $$ ppr (raCodeCoalesced s)
144 $$ text "# Native code after register allocation."
148 $$ text "# Clean out unneeded spill/reloads."
149 $$ ppr (raSpillClean s)
152 $$ text "# Final code, after rewriting spill/rewrite pseudo instrs."
156 $$ (text "# spills inserted: " <> int spills)
157 $$ (text "# reloads inserted: " <> int reloads)
158 $$ (text "# reg-reg moves remaining: " <> int moves)
161 -- | Do all the different analysis on this list of RegAllocStats
163 :: [RegAllocStats instr]
164 -> Color.Graph VirtualReg RegClass RealReg
168 = let outSpills = pprStatsSpills stats
169 outLife = pprStatsLifetimes stats
170 outConflict = pprStatsConflict stats
171 outScatter = pprStatsLifeConflict stats graph
173 in vcat [outSpills, outLife, outConflict, outScatter]
176 -- | Dump a table of how many spill loads \/ stores were inserted for each vreg.
178 :: [RegAllocStats instr] -> SDoc
182 finals = [ s | s@RegAllocStatsColored{} <- stats]
184 -- sum up how many stores\/loads\/reg-reg-moves were left in the code
185 total = foldl' addSRM (0, 0, 0)
188 in ( text "-- spills-added-total"
189 $$ text "-- (stores, loads, reg_reg_moves_remaining)"
194 -- | Dump a table of how long vregs tend to live for in the initial code.
196 :: [RegAllocStats instr] -> SDoc
198 pprStatsLifetimes stats
199 = let info = foldl' plusSpillCostInfo zeroSpillCostInfo
201 | s@RegAllocStatsStart{} <- stats ]
203 lifeBins = binLifetimeCount $ lifeMapFromSpillCostInfo info
205 in ( text "-- vreg-population-lifetimes"
206 $$ text "-- (instruction_count, number_of_vregs_that_lived_that_long)"
207 $$ (vcat $ map ppr $ eltsUFM lifeBins)
210 binLifetimeCount :: UniqFM (VirtualReg, Int) -> UniqFM (Int, Int)
212 = let lifes = map (\l -> (l, (l, 1)))
217 (\(l1, c1) (_, c2) -> (l1, c1 + c2))
222 -- | Dump a table of how many conflicts vregs tend to have in the initial code.
224 :: [RegAllocStats instr] -> SDoc
226 pprStatsConflict stats
227 = let confMap = foldl' (plusUFM_C (\(c1, n1) (_, n2) -> (c1, n1 + n2)))
229 $ map Color.slurpNodeConflictCount
230 [ raGraph s | s@RegAllocStatsStart{} <- stats ]
232 in ( text "-- vreg-conflicts"
233 $$ text "-- (conflict_count, number_of_vregs_that_had_that_many_conflicts)"
234 $$ (vcat $ map ppr $ eltsUFM confMap)
238 -- | For every vreg, dump it's how many conflicts it has and its lifetime
239 -- good for making a scatter plot.
241 :: [RegAllocStats instr]
242 -> Color.Graph VirtualReg RegClass RealReg -- ^ global register conflict graph
245 pprStatsLifeConflict stats graph
246 = let lifeMap = lifeMapFromSpillCostInfo
247 $ foldl' plusSpillCostInfo zeroSpillCostInfo
248 $ [ raSpillCosts s | s@RegAllocStatsStart{} <- stats ]
250 scatter = map (\r -> let lifetime = case lookupUFM lifeMap r of
253 Just node = Color.lookupNode graph r
254 in parens $ hcat $ punctuate (text ", ")
255 [ doubleQuotes $ ppr $ Color.nodeId node
256 , ppr $ sizeUniqSet (Color.nodeConflicts node)
260 $ Color.graphMap graph
262 in ( text "-- vreg-conflict-lifetime"
263 $$ text "-- (vreg, vreg_conflicts, vreg_lifetime)"
268 -- | Count spill/reload/reg-reg moves.
269 -- Lets us see how well the register allocator has done.
273 => LiveCmmTop instr -> (Int, Int, Int)
276 = execState (mapBlockTopM countSRM_block cmm) (0, 0, 0)
278 countSRM_block (BasicBlock i instrs)
279 = do instrs' <- mapM countSRM_instr instrs
280 return $ BasicBlock i instrs'
283 | LiveInstr SPILL{} _ <- li
284 = do modify $ \(s, r, m) -> (s + 1, r, m)
287 | LiveInstr RELOAD{} _ <- li
288 = do modify $ \(s, r, m) -> (s, r + 1, m)
291 | LiveInstr instr _ <- li
292 , Just _ <- takeRegRegMoveInstr instr
293 = do modify $ \(s, r, m) -> (s, r, m + 1)
300 addSRM (s1, r1, m1) (s2, r2, m2)
301 = (s1+s2, r1+r2, m1+m2)
310 = let rs = padL 2 '0' (showHex r "")
311 gs = padL 2 '0' (showHex r "")
312 bs = padL 2 '0' (showHex r "")
315 = replicate (n - length s) c ++ s
316 in "#" ++ rs ++ gs ++ bs