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
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 { raCode :: [LiveCmmTop instr] -- ^ the code we tried to allocate registers for
49 , raGraph :: Color.Graph VirtualReg RegClass RealReg -- ^ the partially colored graph
50 , raCoalesced :: UniqFM VirtualReg -- ^ the regs that were coaleced
51 , raSpillStats :: SpillStats -- ^ spiller stats
52 , raSpillCosts :: SpillCostInfo -- ^ number of instrs each reg lives for
53 , raSpilled :: [LiveCmmTop instr] } -- ^ code with spill instructions added
55 -- a successful coloring
56 | RegAllocStatsColored
57 { raCode :: [LiveCmmTop instr] -- ^ the code we tried to allocate registers for
58 , raGraph :: Color.Graph VirtualReg RegClass RealReg -- ^ the uncolored graph
59 , raGraphColored :: Color.Graph VirtualReg RegClass RealReg -- ^ the coalesced and colored graph
60 , raCoalesced :: UniqFM VirtualReg -- ^ the regs that were coaleced
61 , raCodeCoalesced :: [LiveCmmTop instr] -- ^ code with coalescings applied
62 , raPatched :: [LiveCmmTop instr] -- ^ code with vregs replaced by hregs
63 , raSpillClean :: [LiveCmmTop instr] -- ^ code with unneeded spill\/reloads cleaned out
64 , raFinal :: [NatCmmTop instr] -- ^ final code
65 , raSRMs :: (Int, Int, Int) } -- ^ spill\/reload\/reg-reg moves present in this code
67 instance Outputable instr => Outputable (RegAllocStats instr) where
69 ppr (s@RegAllocStatsStart{})
71 $$ text "# Native code with liveness information."
74 $$ text "# Initial register conflict graph."
78 targetVirtualRegSqueeze
83 ppr (s@RegAllocStatsSpill{})
86 $$ text "# Code with liveness information."
90 $$ (if (not $ isNullUFM $ raCoalesced s)
91 then text "# Registers coalesced."
92 $$ (vcat $ map ppr $ ufmToList $ raCoalesced s)
96 $$ text "# Spills inserted."
97 $$ ppr (raSpillStats s)
100 $$ text "# Code with spills inserted."
101 $$ (ppr (raSpilled s))
104 ppr (s@RegAllocStatsColored { raSRMs = (spills, reloads, moves) })
107 $$ text "# Code with liveness information."
111 $$ text "# Register conflict graph (colored)."
115 targetVirtualRegSqueeze
116 targetRealRegSqueeze)
120 $$ (if (not $ isNullUFM $ raCoalesced s)
121 then text "# Registers coalesced."
122 $$ (vcat $ map ppr $ ufmToList $ raCoalesced s)
126 $$ text "# Native code after coalescings applied."
127 $$ ppr (raCodeCoalesced s)
130 $$ text "# Native code after register allocation."
134 $$ text "# Clean out unneeded spill/reloads."
135 $$ ppr (raSpillClean s)
138 $$ text "# Final code, after rewriting spill/rewrite pseudo instrs."
142 $$ (text "# spills inserted: " <> int spills)
143 $$ (text "# reloads inserted: " <> int reloads)
144 $$ (text "# reg-reg moves remaining: " <> int moves)
147 -- | Do all the different analysis on this list of RegAllocStats
149 :: [RegAllocStats instr]
150 -> Color.Graph VirtualReg RegClass RealReg
154 = let outSpills = pprStatsSpills stats
155 outLife = pprStatsLifetimes stats
156 outConflict = pprStatsConflict stats
157 outScatter = pprStatsLifeConflict stats graph
159 in vcat [outSpills, outLife, outConflict, outScatter]
162 -- | Dump a table of how many spill loads \/ stores were inserted for each vreg.
164 :: [RegAllocStats instr] -> SDoc
168 finals = [ s | s@RegAllocStatsColored{} <- stats]
170 -- sum up how many stores\/loads\/reg-reg-moves were left in the code
171 total = foldl' addSRM (0, 0, 0)
174 in ( text "-- spills-added-total"
175 $$ text "-- (stores, loads, reg_reg_moves_remaining)"
180 -- | Dump a table of how long vregs tend to live for in the initial code.
182 :: [RegAllocStats instr] -> SDoc
184 pprStatsLifetimes stats
185 = let info = foldl' plusSpillCostInfo zeroSpillCostInfo
187 | s@RegAllocStatsStart{} <- stats ]
189 lifeBins = binLifetimeCount $ lifeMapFromSpillCostInfo info
191 in ( text "-- vreg-population-lifetimes"
192 $$ text "-- (instruction_count, number_of_vregs_that_lived_that_long)"
193 $$ (vcat $ map ppr $ eltsUFM lifeBins)
196 binLifetimeCount :: UniqFM (VirtualReg, Int) -> UniqFM (Int, Int)
198 = let lifes = map (\l -> (l, (l, 1)))
203 (\(l1, c1) (_, c2) -> (l1, c1 + c2))
208 -- | Dump a table of how many conflicts vregs tend to have in the initial code.
210 :: [RegAllocStats instr] -> SDoc
212 pprStatsConflict stats
213 = let confMap = foldl' (plusUFM_C (\(c1, n1) (_, n2) -> (c1, n1 + n2)))
215 $ map Color.slurpNodeConflictCount
216 [ raGraph s | s@RegAllocStatsStart{} <- stats ]
218 in ( text "-- vreg-conflicts"
219 $$ text "-- (conflict_count, number_of_vregs_that_had_that_many_conflicts)"
220 $$ (vcat $ map ppr $ eltsUFM confMap)
224 -- | For every vreg, dump it's how many conflicts it has and its lifetime
225 -- good for making a scatter plot.
227 :: [RegAllocStats instr]
228 -> Color.Graph VirtualReg RegClass RealReg -- ^ global register conflict graph
231 pprStatsLifeConflict stats graph
232 = let lifeMap = lifeMapFromSpillCostInfo
233 $ foldl' plusSpillCostInfo zeroSpillCostInfo
234 $ [ raSpillCosts s | s@RegAllocStatsStart{} <- stats ]
236 scatter = map (\r -> let lifetime = case lookupUFM lifeMap r of
239 Just node = Color.lookupNode graph r
240 in parens $ hcat $ punctuate (text ", ")
241 [ doubleQuotes $ ppr $ Color.nodeId node
242 , ppr $ sizeUniqSet (Color.nodeConflicts node)
246 $ Color.graphMap graph
248 in ( text "-- vreg-conflict-lifetime"
249 $$ text "-- (vreg, vreg_conflicts, vreg_lifetime)"
254 -- | Count spill/reload/reg-reg moves.
255 -- Lets us see how well the register allocator has done.
258 => LiveCmmTop instr -> (Int, Int, Int)
261 = execState (mapBlockTopM countSRM_block cmm) (0, 0, 0)
263 countSRM_block (BasicBlock i instrs)
264 = do instrs' <- mapM countSRM_instr instrs
265 return $ BasicBlock i instrs'
268 | LiveInstr SPILL{} _ <- li
269 = do modify $ \(s, r, m) -> (s + 1, r, m)
272 | LiveInstr RELOAD{} _ <- li
273 = do modify $ \(s, r, m) -> (s, r + 1, m)
276 | LiveInstr instr _ <- li
277 , Just _ <- takeRegRegMoveInstr instr
278 = do modify $ \(s, r, m) -> (s, r, m + 1)
285 addSRM (s1, r1, m1) (s2, r2, m2)
286 = (s1+s2, r1+r2, m1+m2)