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
38 data RegAllocStats instr
42 { raLiveCmm :: [LiveCmmTop instr] -- ^ initial code, with liveness
43 , raGraph :: Color.Graph VirtualReg RegClass RealReg -- ^ the initial, uncolored graph
44 , raSpillCosts :: SpillCostInfo } -- ^ information to help choose which regs to spill
48 { raGraph :: Color.Graph VirtualReg RegClass RealReg -- ^ the partially colored graph
49 , raCoalesced :: UniqFM VirtualReg -- ^ the regs that were coaleced
50 , raSpillStats :: SpillStats -- ^ spiller stats
51 , raSpillCosts :: SpillCostInfo -- ^ number of instrs each reg lives for
52 , raSpilled :: [LiveCmmTop instr] } -- ^ code with spill instructions added
54 -- a successful coloring
55 | RegAllocStatsColored
56 { raGraph :: Color.Graph VirtualReg RegClass RealReg -- ^ the uncolored graph
57 , raGraphColored :: Color.Graph VirtualReg RegClass RealReg -- ^ the coalesced and colored graph
58 , raCoalesced :: UniqFM VirtualReg -- ^ the regs that were coaleced
59 , raCodeCoalesced :: [LiveCmmTop instr] -- ^ code with coalescings applied
60 , raPatched :: [LiveCmmTop instr] -- ^ code with vregs replaced by hregs
61 , raSpillClean :: [LiveCmmTop instr] -- ^ code with unneeded spill\/reloads cleaned out
62 , raFinal :: [NatCmmTop instr] -- ^ final code
63 , raSRMs :: (Int, Int, Int) } -- ^ spill\/reload\/reg-reg moves present in this code
65 instance Outputable instr => Outputable (RegAllocStats instr) where
67 ppr (s@RegAllocStatsStart{})
69 $$ text "# Native code with liveness information."
72 -- $$ text "# Initial register conflict graph."
73 -- $$ Color.dotGraph regDotColor trivColorable (raGraph s)
76 ppr (s@RegAllocStatsSpill{})
79 -- $$ text "# Register conflict graph."
80 -- $$ Color.dotGraph regDotColor trivColorable (raGraph s)
83 $$ (if (not $ isNullUFM $ raCoalesced s)
84 then text "# Registers coalesced."
85 $$ (vcat $ map ppr $ ufmToList $ raCoalesced s)
89 -- $$ text "# Spill costs. reg uses defs lifetime degree cost"
90 -- $$ vcat (map (pprSpillCostRecord (raGraph s)) $ eltsUFM $ raSpillCosts s)
93 $$ text "# Spills inserted."
94 $$ ppr (raSpillStats s)
97 $$ text "# Code with spills inserted."
98 $$ (ppr (raSpilled s))
101 ppr (s@RegAllocStatsColored { raSRMs = (spills, reloads, moves) })
104 -- $$ text "# Register conflict graph (initial)."
105 -- $$ Color.dotGraph regDotColor trivColorable (raGraph s)
108 -- $$ text "# Register conflict graph (colored)."
109 -- $$ Color.dotGraph regDotColor trivColorable (raGraphColored s)
112 $$ (if (not $ isNullUFM $ raCoalesced s)
113 then text "# Registers coalesced."
114 $$ (vcat $ map ppr $ ufmToList $ raCoalesced s)
118 $$ text "# Native code after coalescings applied."
119 $$ ppr (raCodeCoalesced s)
122 $$ text "# Native code after register allocation."
126 $$ text "# Clean out unneeded spill/reloads."
127 $$ ppr (raSpillClean s)
130 $$ text "# Final code, after rewriting spill/rewrite pseudo instrs."
134 $$ (text "# spills inserted: " <> int spills)
135 $$ (text "# reloads inserted: " <> int reloads)
136 $$ (text "# reg-reg moves remaining: " <> int moves)
139 -- | Do all the different analysis on this list of RegAllocStats
141 :: [RegAllocStats instr]
142 -> Color.Graph VirtualReg RegClass RealReg
146 = let outSpills = pprStatsSpills stats
147 outLife = pprStatsLifetimes stats
148 outConflict = pprStatsConflict stats
149 outScatter = pprStatsLifeConflict stats graph
151 in vcat [outSpills, outLife, outConflict, outScatter]
154 -- | Dump a table of how many spill loads \/ stores were inserted for each vreg.
156 :: [RegAllocStats instr] -> SDoc
160 finals = [ s | s@RegAllocStatsColored{} <- stats]
162 -- sum up how many stores\/loads\/reg-reg-moves were left in the code
163 total = foldl' addSRM (0, 0, 0)
166 in ( text "-- spills-added-total"
167 $$ text "-- (stores, loads, reg_reg_moves_remaining)"
172 -- | Dump a table of how long vregs tend to live for in the initial code.
174 :: [RegAllocStats instr] -> SDoc
176 pprStatsLifetimes stats
177 = let info = foldl' plusSpillCostInfo zeroSpillCostInfo
179 | s@RegAllocStatsStart{} <- stats ]
181 lifeBins = binLifetimeCount $ lifeMapFromSpillCostInfo info
183 in ( text "-- vreg-population-lifetimes"
184 $$ text "-- (instruction_count, number_of_vregs_that_lived_that_long)"
185 $$ (vcat $ map ppr $ eltsUFM lifeBins)
188 binLifetimeCount :: UniqFM (VirtualReg, Int) -> UniqFM (Int, Int)
190 = let lifes = map (\l -> (l, (l, 1)))
195 (\(l1, c1) (_, c2) -> (l1, c1 + c2))
200 -- | Dump a table of how many conflicts vregs tend to have in the initial code.
202 :: [RegAllocStats instr] -> SDoc
204 pprStatsConflict stats
205 = let confMap = foldl' (plusUFM_C (\(c1, n1) (_, n2) -> (c1, n1 + n2)))
207 $ map Color.slurpNodeConflictCount
208 [ raGraph s | s@RegAllocStatsStart{} <- stats ]
210 in ( text "-- vreg-conflicts"
211 $$ text "-- (conflict_count, number_of_vregs_that_had_that_many_conflicts)"
212 $$ (vcat $ map ppr $ eltsUFM confMap)
216 -- | For every vreg, dump it's how many conflicts it has and its lifetime
217 -- good for making a scatter plot.
219 :: [RegAllocStats instr]
220 -> Color.Graph VirtualReg RegClass RealReg -- ^ global register conflict graph
223 pprStatsLifeConflict stats graph
224 = let lifeMap = lifeMapFromSpillCostInfo
225 $ foldl' plusSpillCostInfo zeroSpillCostInfo
226 $ [ raSpillCosts s | s@RegAllocStatsStart{} <- stats ]
228 scatter = map (\r -> let lifetime = case lookupUFM lifeMap r of
231 Just node = Color.lookupNode graph r
232 in parens $ hcat $ punctuate (text ", ")
233 [ doubleQuotes $ ppr $ Color.nodeId node
234 , ppr $ sizeUniqSet (Color.nodeConflicts node)
238 $ Color.graphMap graph
240 in ( text "-- vreg-conflict-lifetime"
241 $$ text "-- (vreg, vreg_conflicts, vreg_lifetime)"
246 -- | Count spill/reload/reg-reg moves.
247 -- Lets us see how well the register allocator has done.
251 => LiveCmmTop instr -> (Int, Int, Int)
254 = execState (mapBlockTopM countSRM_block cmm) (0, 0, 0)
256 countSRM_block (BasicBlock i instrs)
257 = do instrs' <- mapM countSRM_instr instrs
258 return $ BasicBlock i instrs'
262 = do modify $ \(s, r, m) -> (s + 1, r, m)
266 = do modify $ \(s, r, m) -> (s, r + 1, m)
269 | Instr instr _ <- li
270 , Just _ <- takeRegRegMoveInstr instr
271 = do modify $ \(s, r, m) -> (s, r, m + 1)
278 addSRM (s1, r1, m1) (s2, r2, m2)
279 = (s1+s2, r1+r2, m1+m2)
288 = let rs = padL 2 '0' (showHex r "")
289 gs = padL 2 '0' (showHex r "")
290 bs = padL 2 '0' (showHex r "")
293 = replicate (n - length s) c ++ s
294 in "#" ++ rs ++ gs ++ bs