1 {-# OPTIONS -fno-warn-missing-signatures #-}
2 -- | Carries interesting info for debugging / profiling of the
3 -- graph coloring register allocator.
4 module RegAlloc.Graph.Stats (
18 #include "nativeGen/NCG.h"
20 import qualified GraphColor as Color
21 import RegAlloc.Liveness
22 import RegAlloc.Graph.Spill
23 import RegAlloc.Graph.SpillCost
24 import RegAlloc.Graph.TrivColorable
39 data RegAllocStats instr
43 { raLiveCmm :: [LiveCmmTop instr] -- ^ initial code, with liveness
44 , raGraph :: Color.Graph VirtualReg RegClass RealReg -- ^ the initial, uncolored graph
45 , raSpillCosts :: SpillCostInfo } -- ^ information to help choose which regs to spill
49 { raCode :: [LiveCmmTop instr] -- ^ the code we tried to allocate registers for
50 , raGraph :: Color.Graph VirtualReg RegClass RealReg -- ^ the partially colored graph
51 , raCoalesced :: UniqFM VirtualReg -- ^ the regs that were coaleced
52 , raSpillStats :: SpillStats -- ^ spiller stats
53 , raSpillCosts :: SpillCostInfo -- ^ number of instrs each reg lives for
54 , raSpilled :: [LiveCmmTop instr] } -- ^ code with spill instructions added
56 -- a successful coloring
57 | RegAllocStatsColored
58 { raCode :: [LiveCmmTop instr] -- ^ the code we tried to allocate registers for
59 , raGraph :: Color.Graph VirtualReg RegClass RealReg -- ^ the uncolored graph
60 , raGraphColored :: Color.Graph VirtualReg RegClass RealReg -- ^ the coalesced and colored graph
61 , raCoalesced :: UniqFM VirtualReg -- ^ the regs that were coaleced
62 , raCodeCoalesced :: [LiveCmmTop instr] -- ^ code with coalescings applied
63 , raPatched :: [LiveCmmTop instr] -- ^ code with vregs replaced by hregs
64 , raSpillClean :: [LiveCmmTop instr] -- ^ code with unneeded spill\/reloads cleaned out
65 , raFinal :: [NatCmmTop instr] -- ^ final code
66 , raSRMs :: (Int, Int, Int) } -- ^ spill\/reload\/reg-reg moves present in this code
68 instance Outputable instr => Outputable (RegAllocStats instr) where
70 ppr (s@RegAllocStatsStart{})
72 $$ text "# Native code with liveness information."
75 $$ text "# Initial register conflict graph."
79 targetVirtualRegSqueeze
84 ppr (s@RegAllocStatsSpill{})
87 $$ text "# Code with liveness information."
91 $$ (if (not $ isNullUFM $ raCoalesced s)
92 then text "# Registers coalesced."
93 $$ (vcat $ map ppr $ ufmToList $ raCoalesced s)
97 $$ text "# Spills inserted."
98 $$ ppr (raSpillStats s)
101 $$ text "# Code with spills inserted."
102 $$ (ppr (raSpilled s))
105 ppr (s@RegAllocStatsColored { raSRMs = (spills, reloads, moves) })
108 $$ text "# Code with liveness information."
112 $$ text "# Register conflict graph (colored)."
116 targetVirtualRegSqueeze
117 targetRealRegSqueeze)
121 $$ (if (not $ isNullUFM $ raCoalesced s)
122 then text "# Registers coalesced."
123 $$ (vcat $ map ppr $ ufmToList $ raCoalesced s)
127 $$ text "# Native code after coalescings applied."
128 $$ ppr (raCodeCoalesced s)
131 $$ text "# Native code after register allocation."
135 $$ text "# Clean out unneeded spill/reloads."
136 $$ ppr (raSpillClean s)
139 $$ text "# Final code, after rewriting spill/rewrite pseudo instrs."
143 $$ (text "# spills inserted: " <> int spills)
144 $$ (text "# reloads inserted: " <> int reloads)
145 $$ (text "# reg-reg moves remaining: " <> int moves)
148 -- | Do all the different analysis on this list of RegAllocStats
150 :: [RegAllocStats instr]
151 -> Color.Graph VirtualReg RegClass RealReg
155 = let outSpills = pprStatsSpills stats
156 outLife = pprStatsLifetimes stats
157 outConflict = pprStatsConflict stats
158 outScatter = pprStatsLifeConflict stats graph
160 in vcat [outSpills, outLife, outConflict, outScatter]
163 -- | Dump a table of how many spill loads \/ stores were inserted for each vreg.
165 :: [RegAllocStats instr] -> SDoc
169 finals = [ s | s@RegAllocStatsColored{} <- stats]
171 -- sum up how many stores\/loads\/reg-reg-moves were left in the code
172 total = foldl' addSRM (0, 0, 0)
175 in ( text "-- spills-added-total"
176 $$ text "-- (stores, loads, reg_reg_moves_remaining)"
181 -- | Dump a table of how long vregs tend to live for in the initial code.
183 :: [RegAllocStats instr] -> SDoc
185 pprStatsLifetimes stats
186 = let info = foldl' plusSpillCostInfo zeroSpillCostInfo
188 | s@RegAllocStatsStart{} <- stats ]
190 lifeBins = binLifetimeCount $ lifeMapFromSpillCostInfo info
192 in ( text "-- vreg-population-lifetimes"
193 $$ text "-- (instruction_count, number_of_vregs_that_lived_that_long)"
194 $$ (vcat $ map ppr $ eltsUFM lifeBins)
197 binLifetimeCount :: UniqFM (VirtualReg, Int) -> UniqFM (Int, Int)
199 = let lifes = map (\l -> (l, (l, 1)))
204 (\(l1, c1) (_, c2) -> (l1, c1 + c2))
209 -- | Dump a table of how many conflicts vregs tend to have in the initial code.
211 :: [RegAllocStats instr] -> SDoc
213 pprStatsConflict stats
214 = let confMap = foldl' (plusUFM_C (\(c1, n1) (_, n2) -> (c1, n1 + n2)))
216 $ map Color.slurpNodeConflictCount
217 [ raGraph s | s@RegAllocStatsStart{} <- stats ]
219 in ( text "-- vreg-conflicts"
220 $$ text "-- (conflict_count, number_of_vregs_that_had_that_many_conflicts)"
221 $$ (vcat $ map ppr $ eltsUFM confMap)
225 -- | For every vreg, dump it's how many conflicts it has and its lifetime
226 -- good for making a scatter plot.
228 :: [RegAllocStats instr]
229 -> Color.Graph VirtualReg RegClass RealReg -- ^ global register conflict graph
232 pprStatsLifeConflict stats graph
233 = let lifeMap = lifeMapFromSpillCostInfo
234 $ foldl' plusSpillCostInfo zeroSpillCostInfo
235 $ [ raSpillCosts s | s@RegAllocStatsStart{} <- stats ]
237 scatter = map (\r -> let lifetime = case lookupUFM lifeMap r of
240 Just node = Color.lookupNode graph r
241 in parens $ hcat $ punctuate (text ", ")
242 [ doubleQuotes $ ppr $ Color.nodeId node
243 , ppr $ sizeUniqSet (Color.nodeConflicts node)
247 $ Color.graphMap graph
249 in ( text "-- vreg-conflict-lifetime"
250 $$ text "-- (vreg, vreg_conflicts, vreg_lifetime)"
255 -- | Count spill/reload/reg-reg moves.
256 -- Lets us see how well the register allocator has done.
259 => LiveCmmTop instr -> (Int, Int, Int)
262 = execState (mapBlockTopM countSRM_block cmm) (0, 0, 0)
264 countSRM_block (BasicBlock i instrs)
265 = do instrs' <- mapM countSRM_instr instrs
266 return $ BasicBlock i instrs'
269 | LiveInstr SPILL{} _ <- li
270 = do modify $ \(s, r, m) -> (s + 1, r, m)
273 | LiveInstr RELOAD{} _ <- li
274 = do modify $ \(s, r, m) -> (s, r + 1, m)
277 | LiveInstr instr _ <- li
278 , Just _ <- takeRegRegMoveInstr instr
279 = do modify $ \(s, r, m) -> (s, r, m + 1)
286 addSRM (s1, r1, m1) (s2, r2, m2)
287 = (s1+s2, r1+r2, m1+m2)