2 -- Carries interesting info for debugging / profiling of the
3 -- graph coloring register allocator.
20 #include "nativeGen/NCG.h"
22 import qualified GraphColor as Color
41 { raLiveCmm :: [LiveCmmTop] -- ^ initial code, with liveness
42 , raGraph :: Color.Graph Reg RegClass Reg -- ^ the initial, uncolored graph
43 , raLifetimes :: UniqFM (Reg, Int) } -- ^ number of instrs each reg lives for
47 { raGraph :: Color.Graph Reg RegClass Reg -- ^ the partially colored graph
48 , raSpillStats :: SpillStats -- ^ spiller stats
49 , raLifetimes :: UniqFM (Reg, Int) -- ^ number of instrs each reg lives for
50 , raSpilled :: [LiveCmmTop] } -- ^ code with spill instructions added
52 -- a successful coloring
53 | RegAllocStatsColored
54 { raGraph :: Color.Graph Reg RegClass Reg -- ^ the colored graph
55 , raPatched :: [LiveCmmTop] -- ^ code with vregs replaced by hregs
56 , raSpillClean :: [LiveCmmTop] -- ^ code with unneeded spill/reloads cleaned out
57 , raFinal :: [NatCmmTop] -- ^ final code
58 , raSRMs :: (Int, Int, Int) } -- ^ spill/reload/reg-reg moves present in this code
60 instance Outputable RegAllocStats where
62 ppr (s@RegAllocStatsStart{})
64 $$ text "# Native code with liveness information."
67 $$ text "# Initial register conflict graph."
68 $$ Color.dotGraph regDotColor trivColorable (raGraph s)
70 ppr (s@RegAllocStatsSpill{})
72 $$ text "# Register conflict graph."
73 $$ Color.dotGraph regDotColor trivColorable (raGraph s)
75 $$ text "# Spills inserted."
76 $$ ppr (raSpillStats s)
78 $$ text "# Code with spills inserted."
79 $$ (ppr (raSpilled s))
81 ppr (s@RegAllocStatsColored { raSRMs = (spills, reloads, moves) })
83 $$ text "# Register conflict graph."
84 $$ Color.dotGraph regDotColor trivColorable (raGraph s)
86 $$ text "# Native code after register allocation."
89 $$ text "# Clean out unneeded spill/reloads."
90 $$ ppr (raSpillClean s)
92 $$ text "# Final code, after rewriting spill/rewrite pseudo instrs."
96 $$ (text "# spills inserted: " <> int spills)
97 $$ (text "# reloads inserted: " <> int reloads)
98 $$ (text "# reg-reg moves remaining: " <> int moves)
101 -- | Do all the different analysis on this list of RegAllocStats
102 pprStats :: [RegAllocStats] -> Color.Graph Reg RegClass Reg -> SDoc
104 = let outSpills = pprStatsSpills stats
105 outLife = pprStatsLifetimes stats
106 outConflict = pprStatsConflict stats
107 outScatter = pprStatsLifeConflict stats graph
109 in vcat [outSpills, outLife, outConflict, outScatter]
112 -- | Dump a table of how many spill loads / stores were inserted for each vreg.
114 :: [RegAllocStats] -> SDoc
118 finals = [ s | s@RegAllocStatsColored{} <- stats]
120 -- sum up how many stores/loads/reg-reg-moves were left in the code
121 total = foldl' addSRM (0, 0, 0)
124 in ( text "-- spills-added-total"
125 $$ text "-- (stores, loads, reg_reg_moves_remaining)"
130 -- | Dump a table of how long vregs tend to live for in the initial code.
132 :: [RegAllocStats] -> SDoc
134 pprStatsLifetimes stats
135 = let lifeMap = foldl' plusUFM emptyUFM
136 [ raLifetimes s | s@RegAllocStatsStart{} <- stats ]
137 lifeBins = binLifetimeCount lifeMap
139 in ( text "-- vreg-population-lifetimes"
140 $$ text "-- (instruction_count, number_of_vregs_that_lived_that_long)"
141 $$ (vcat $ map ppr $ eltsUFM lifeBins)
144 binLifetimeCount :: UniqFM (Reg, Int) -> UniqFM (Int, Int)
146 = let lifes = map (\l -> (l, (l, 1)))
151 (\(l1, c1) (l2, c2) -> (l1, c1 + c2))
156 -- | Dump a table of how many conflicts vregs tend to have in the initial code.
158 :: [RegAllocStats] -> SDoc
160 pprStatsConflict stats
161 = let confMap = foldl' (plusUFM_C (\(c1, n1) (c2, n2) -> (c1, n1 + n2)))
163 $ map Color.slurpNodeConflictCount
164 [ raGraph s | s@RegAllocStatsStart{} <- stats ]
166 in ( text "-- vreg-conflicts"
167 $$ text "-- (conflict_count, number_of_vregs_that_had_that_many_conflicts)"
168 $$ (vcat $ map ppr $ eltsUFM confMap)
172 -- | For every vreg, dump it's how many conflicts it has and its lifetime
173 -- good for making a scatter plot.
176 -> Color.Graph Reg RegClass Reg -- ^ global register conflict graph
179 pprStatsLifeConflict stats graph
180 = let lifeMap = foldl' plusUFM emptyUFM
181 [ raLifetimes s | s@RegAllocStatsStart{} <- stats ]
183 scatter = map (\r -> let lifetime = case lookupUFM lifeMap r of
186 Just node = Color.lookupNode graph r
187 in parens $ hcat $ punctuate (text ", ")
188 [ doubleQuotes $ ppr $ Color.nodeId node
189 , ppr $ sizeUniqSet (Color.nodeConflicts node)
193 $ Color.graphMap graph
195 in ( text "-- vreg-conflict-lifetime"
196 $$ text "-- (vreg, vreg_conflicts, vreg_lifetime)"
201 -- | Count spill/reload/reg-reg moves.
202 -- Lets us see how well the register allocator has done.
204 countSRMs :: LiveCmmTop -> (Int, Int, Int)
206 = execState (mapBlockTopM countSRM_block cmm) (0, 0, 0)
208 countSRM_block (BasicBlock i instrs)
209 = do instrs' <- mapM countSRM_instr instrs
210 return $ BasicBlock i instrs'
212 countSRM_instr li@(Instr instr live)
213 | SPILL reg slot <- instr
214 = do modify $ \(s, r, m) -> (s + 1, r, m)
217 | RELOAD slot reg <- instr
218 = do modify $ \(s, r, m) -> (s, r + 1, m)
221 | Just _ <- isRegRegMove instr
222 = do modify $ \(s, r, m) -> (s, r, m + 1)
229 addSRM (s1, r1, m1) (s2, r2, m2)
230 = (s1+s2, r1+r2, m1+m2)
233 -- Register colors for drawing conflict graphs
234 -- Keep this out of MachRegs.hs because it's specific to the graph coloring allocator.
237 -- reg colors for x86
239 regDotColor :: Reg -> SDoc
241 = let Just str = lookupUFM regColors reg
256 , (fake5, "#5500ff") ]
260 -- reg colors for x86_64
261 #if x86_64_TARGET_ARCH
262 regDotColor :: Reg -> SDoc
264 = let Just str = lookupUFM regColors reg
269 $ [ (rax, "#00ff00"), (eax, "#00ff00")
270 , (rbx, "#0000ff"), (ebx, "#0000ff")
271 , (rcx, "#00ffff"), (ecx, "#00ffff")
272 , (rdx, "#0080ff"), (edx, "#00ffff")
282 ++ zip (map RealReg [16..31]) (repeat "red")
286 -- reg colors for ppc
287 #if powerpc_TARGET_ARCH
288 regDotColor :: Reg -> SDoc
290 = case regClass reg of
291 RcInteger -> text "blue"
292 RcFloat -> text "red"
298 = let rs = padL 2 '0' (showHex r "")
299 gs = padL 2 '0' (showHex r "")
300 bs = padL 2 '0' (showHex r "")
303 = replicate (n - length s) c ++ s
304 in "#" ++ rs ++ gs ++ bs