compiler/nativeGen/RegAllocStats.hs

   1 -- Carries interesting info for debugging / profiling of the
   2 --      graph coloring register allocator.
   3 --
   4 {-# OPTIONS -fno-warn-missing-signatures #-}
   5
   6 module RegAllocStats (
   7         RegAllocStats (..),
   8         regDotColor,
   9
  10         pprStats,
  11         pprStatsSpills,
  12         pprStatsLifetimes,
  13         pprStatsConflict,
  14         pprStatsLifeConflict,
  15
  16         countSRMs, addSRM
  17 )
  18
  19 where
  20
  21 #include "nativeGen/NCG.h"
  22
  23 import qualified GraphColor as Color
  24 import RegLiveness
  25 import RegAllocInfo
  26 import RegSpill
  27 import RegSpillCost
  28 import MachRegs
  29 import MachInstrs
  30 import Cmm
  31
  32 import Outputable
  33 import UniqFM
  34 import UniqSet
  35 import State
  36
  37 import Data.List
  38
  39 data RegAllocStats
  40
  41         -- initial graph
  42         = RegAllocStatsStart
  43         { raLiveCmm     :: [LiveCmmTop]                   -- ^ initial code, with liveness
  44         , raGraph       :: Color.Graph Reg RegClass Reg   -- ^ the initial, uncolored graph
  45         , raSpillCosts  :: SpillCostInfo }                -- ^ information to help choose which regs to spill
  46
  47         -- a spill stage
  48         | RegAllocStatsSpill
  49         { raGraph       :: Color.Graph Reg RegClass Reg -- ^ the partially colored graph
  50         , raCoalesced   :: UniqFM Reg                   -- ^ the regs that were coaleced
  51         , raSpillStats  :: SpillStats                   -- ^ spiller stats
  52         , raSpillCosts  :: SpillCostInfo                -- ^ number of instrs each reg lives for
  53         , raSpilled     :: [LiveCmmTop] }               -- ^ code with spill instructions added
  54
  55         -- a successful coloring
  56         | RegAllocStatsColored
  57         { raGraph       :: Color.Graph Reg RegClass Reg -- ^ the colored graph
  58         , raCoalesced   :: UniqFM Reg                   -- ^ the regs that were coaleced
  59         , raPatched     :: [LiveCmmTop]                 -- ^ code with vregs replaced by hregs
  60         , raSpillClean  :: [LiveCmmTop]                 -- ^ code with unneeded spill/reloads cleaned out
  61         , raFinal       :: [NatCmmTop]                  -- ^ final code
  62         , raSRMs        :: (Int, Int, Int) }            -- ^ spill/reload/reg-reg moves present in this code
  63
  64 instance Outputable RegAllocStats where
  65
  66  ppr (s@RegAllocStatsStart{})
  67         =  text "#  Start"
  68         $$ text "#  Native code with liveness information."
  69         $$ ppr (raLiveCmm s)
  70         $$ text ""
  71         $$ text "#  Initial register conflict graph."
  72         $$ Color.dotGraph regDotColor trivColorable (raGraph s)
  73
  74
  75  ppr (s@RegAllocStatsSpill{})
  76         =  text "#  Spill"
  77
  78         $$ text "#  Register conflict graph."
  79         $$ Color.dotGraph regDotColor trivColorable (raGraph s)
  80         $$ text ""
  81
  82         $$ (if (not $ isNullUFM $ raCoalesced s)
  83                 then    text "#  Registers coalesced."
  84                         $$ (vcat $ map ppr $ ufmToList $ raCoalesced s)
  85                         $$ text ""
  86                 else empty)
  87
  88         $$ text "#  Spill costs.  reg uses defs lifetime degree cost"
  89         $$ vcat (map (pprSpillCostRecord (raGraph s)) $ eltsUFM $ raSpillCosts s)
  90         $$ text ""
  91
  92         $$ text "#  Spills inserted."
  93         $$ ppr (raSpillStats s)
  94         $$ text ""
  95
  96         $$ text "#  Code with spills inserted."
  97         $$ (ppr (raSpilled s))
  98
  99
 100  ppr (s@RegAllocStatsColored { raSRMs = (spills, reloads, moves) })
 101         =  text "#  Colored"
 102
 103         $$ text "#  Register conflict graph."
 104         $$ Color.dotGraph regDotColor trivColorable (raGraph s)
 105         $$ text ""
 106
 107         $$ (if (not $ isNullUFM $ raCoalesced s)
 108                 then    text "#  Registers coalesced."
 109                         $$ (vcat $ map ppr $ ufmToList $ raCoalesced s)
 110                         $$ text ""
 111                 else empty)
 112
 113         $$ text "#  Native code after register allocation."
 114         $$ ppr (raPatched s)
 115         $$ text ""
 116
 117         $$ text "#  Clean out unneeded spill/reloads."
 118         $$ ppr (raSpillClean s)
 119         $$ text ""
 120
 121         $$ text "#  Final code, after rewriting spill/rewrite pseudo instrs."
 122         $$ ppr (raFinal s)
 123         $$ text ""
 124         $$  text "#  Score:"
 125         $$ (text "#          spills  inserted: " <> int spills)
 126         $$ (text "#          reloads inserted: " <> int reloads)
 127         $$ (text "#   reg-reg moves remaining: " <> int moves)
 128         $$ text ""
 129
 130 -- | Do all the different analysis on this list of RegAllocStats
 131 pprStats :: [RegAllocStats] -> Color.Graph Reg RegClass Reg -> SDoc
 132 pprStats stats graph
 133  = let  outSpills       = pprStatsSpills    stats
 134         outLife         = pprStatsLifetimes stats
 135         outConflict     = pprStatsConflict  stats
 136         outScatter      = pprStatsLifeConflict stats graph
 137
 138   in    vcat [outSpills, outLife, outConflict, outScatter]
 139
 140
 141 -- | Dump a table of how many spill loads / stores were inserted for each vreg.
 142 pprStatsSpills
 143         :: [RegAllocStats] -> SDoc
 144
 145 pprStatsSpills stats
 146  = let
 147         finals  = [ s   | s@RegAllocStatsColored{} <- stats]
 148
 149         -- sum up how many stores/loads/reg-reg-moves were left in the code
 150         total   = foldl' addSRM (0, 0, 0)
 151                 $ map raSRMs finals
 152
 153     in  (  text "-- spills-added-total"
 154         $$ text "--    (stores, loads, reg_reg_moves_remaining)"
 155         $$ ppr total
 156         $$ text "")
 157
 158
 159 -- | Dump a table of how long vregs tend to live for in the initial code.
 160 pprStatsLifetimes
 161         :: [RegAllocStats] -> SDoc
 162
 163 pprStatsLifetimes stats
 164  = let  info            = foldl' plusSpillCostInfo zeroSpillCostInfo
 165                                 [ raSpillCosts s
 166                                         | s@RegAllocStatsStart{} <- stats ]
 167
 168         lifeBins        = binLifetimeCount $ lifeMapFromSpillCostInfo info
 169
 170    in   (  text "-- vreg-population-lifetimes"
 171         $$ text "--   (instruction_count, number_of_vregs_that_lived_that_long)"
 172         $$ (vcat $ map ppr $ eltsUFM lifeBins)
 173         $$ text "\n")
 174
 175 binLifetimeCount :: UniqFM (Reg, Int) -> UniqFM (Int, Int)
 176 binLifetimeCount fm
 177  = let  lifes   = map (\l -> (l, (l, 1)))
 178                 $ map snd
 179                 $ eltsUFM fm
 180
 181    in   addListToUFM_C
 182                 (\(l1, c1) (_, c2) -> (l1, c1 + c2))
 183                 emptyUFM
 184                 lifes
 185
 186
 187 -- | Dump a table of how many conflicts vregs tend to have in the initial code.
 188 pprStatsConflict
 189         :: [RegAllocStats] -> SDoc
 190
 191 pprStatsConflict stats
 192  = let  confMap = foldl' (plusUFM_C (\(c1, n1) (_, n2) -> (c1, n1 + n2)))
 193                         emptyUFM
 194                 $ map Color.slurpNodeConflictCount
 195                         [ raGraph s | s@RegAllocStatsStart{} <- stats ]
 196
 197    in   (  text "-- vreg-conflicts"
 198         $$ text "--   (conflict_count, number_of_vregs_that_had_that_many_conflicts)"
 199         $$ (vcat $ map ppr $ eltsUFM confMap)
 200         $$ text "\n")
 201
 202
 203 -- | For every vreg, dump it's how many conflicts it has and its lifetime
 204 --      good for making a scatter plot.
 205 pprStatsLifeConflict
 206         :: [RegAllocStats]
 207         -> Color.Graph Reg RegClass Reg         -- ^ global register conflict graph
 208         -> SDoc
 209
 210 pprStatsLifeConflict stats graph
 211  = let  lifeMap = lifeMapFromSpillCostInfo
 212                 $ foldl' plusSpillCostInfo zeroSpillCostInfo
 213                 $ [ raSpillCosts s | s@RegAllocStatsStart{} <- stats ]
 214
 215         scatter = map   (\r ->  let lifetime    = case lookupUFM lifeMap r of
 216                                                         Just (_, l)     -> l
 217                                                         Nothing         -> 0
 218                                     Just node   = Color.lookupNode graph r
 219                                 in parens $ hcat $ punctuate (text ", ")
 220                                         [ doubleQuotes $ ppr $ Color.nodeId node
 221                                         , ppr $ sizeUniqSet (Color.nodeConflicts node)
 222                                         , ppr $ lifetime ])
 223                 $ map Color.nodeId
 224                 $ eltsUFM
 225                 $ Color.graphMap graph
 226
 227    in   (  text "-- vreg-conflict-lifetime"
 228         $$ text "--   (vreg, vreg_conflicts, vreg_lifetime)"
 229         $$ (vcat scatter)
 230         $$ text "\n")
 231
 232
 233 -- | Count spill/reload/reg-reg moves.
 234 --      Lets us see how well the register allocator has done.
 235 --
 236 countSRMs :: LiveCmmTop -> (Int, Int, Int)
 237 countSRMs cmm
 238         = execState (mapBlockTopM countSRM_block cmm) (0, 0, 0)
 239
 240 countSRM_block (BasicBlock i instrs)
 241  = do   instrs' <- mapM countSRM_instr instrs
 242         return  $ BasicBlock i instrs'
 243
 244 countSRM_instr li@(Instr instr _)
 245         | SPILL _ _     <- instr
 246         = do    modify  $ \(s, r, m)    -> (s + 1, r, m)
 247                 return li
 248
 249         | RELOAD _ _    <- instr
 250         = do    modify  $ \(s, r, m)    -> (s, r + 1, m)
 251                 return li
 252
 253         | Just _                <- isRegRegMove instr
 254         = do    modify  $ \(s, r, m)    -> (s, r, m + 1)
 255                 return li
 256
 257         | otherwise
 258         =       return li
 259
 260 -- sigh..
 261 addSRM (s1, r1, m1) (s2, r2, m2)
 262         = (s1+s2, r1+r2, m1+m2)
 263
 264 -----
 265 -- Register colors for drawing conflict graphs
 266 --      Keep this out of MachRegs.hs because it's specific to the graph coloring allocator.
 267
 268
 269 -- reg colors for x86
 270 #if i386_TARGET_ARCH
 271 regDotColor :: Reg -> SDoc
 272 regDotColor reg
 273  = let  Just    str     = lookupUFM regColors reg
 274    in   text str
 275
 276 regColors
 277  = listToUFM
 278  $      [ (eax, "#00ff00")
 279         , (ebx, "#0000ff")
 280         , (ecx, "#00ffff")
 281         , (edx, "#0080ff")
 282
 283         , (fake0, "#ff00ff")
 284         , (fake1, "#ff00aa")
 285         , (fake2, "#aa00ff")
 286         , (fake3, "#aa00aa")
 287         , (fake4, "#ff0055")
 288         , (fake5, "#5500ff") ]
 289 #endif
 290
 291
 292 -- reg colors for x86_64
 293 #if x86_64_TARGET_ARCH
 294 regDotColor :: Reg -> SDoc
 295 regDotColor reg
 296  = let  Just    str     = lookupUFM regColors reg
 297    in   text str
 298
 299 regColors
 300  = listToUFM
 301  $      [ (rax, "#00ff00"), (eax, "#00ff00")
 302         , (rbx, "#0000ff"), (ebx, "#0000ff")
 303         , (rcx, "#00ffff"), (ecx, "#00ffff")
 304         , (rdx, "#0080ff"), (edx, "#00ffff")
 305         , (r8,  "#00ff80")
 306         , (r9,  "#008080")
 307         , (r10, "#0040ff")
 308         , (r11, "#00ff40")
 309         , (r12, "#008040")
 310         , (r13, "#004080")
 311         , (r14, "#004040")
 312         , (r15, "#002080") ]
 313
 314         ++ zip (map RealReg [16..31]) (repeat "red")
 315 #endif
 316
 317
 318 -- reg colors for ppc
 319 #if powerpc_TARGET_ARCH
 320 regDotColor :: Reg -> SDoc
 321 regDotColor reg
 322  = case regClass reg of
 323         RcInteger       -> text "blue"
 324         RcFloat         -> text "red"
 325 #endif
 326
 327
 328 {-
 329 toX11Color (r, g, b)
 330  = let  rs      = padL 2 '0' (showHex r "")
 331         gs      = padL 2 '0' (showHex r "")
 332         bs      = padL 2 '0' (showHex r "")
 333
 334         padL n c s
 335                 = replicate (n - length s) c ++ s
 336   in    "#" ++ rs ++ gs ++ bs
 337 -}