compiler/nativeGen/RegAlloc/Graph/Stats.hs

   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 (
   5         RegAllocStats (..),
   6
   7         pprStats,
   8         pprStatsSpills,
   9         pprStatsLifetimes,
  10         pprStatsConflict,
  11         pprStatsLifeConflict,
  12
  13         countSRMs, addSRM
  14 )
  15
  16 where
  17
  18 #include "nativeGen/NCG.h"
  19
  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
  25 import Instruction
  26 import RegClass
  27 import Reg
  28 import TargetReg
  29
  30 import Cmm
  31 import Outputable
  32 import UniqFM
  33 import UniqSet
  34 import State
  35
  36 import Data.List
  37
  38 data RegAllocStats instr
  39
  40         -- initial graph
  41         = RegAllocStatsStart
  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
  45
  46         -- a spill stage
  47         | RegAllocStatsSpill
  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
  54
  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
  66
  67 instance Outputable instr => Outputable (RegAllocStats instr) where
  68
  69  ppr (s@RegAllocStatsStart{})
  70         =  text "#  Start"
  71         $$ text "#  Native code with liveness information."
  72         $$ ppr (raLiveCmm s)
  73         $$ text ""
  74         $$ text "#  Initial register conflict graph."
  75         $$ Color.dotGraph
  76                 targetRegDotColor
  77                 (trivColorable
  78                         targetVirtualRegSqueeze
  79                         targetRealRegSqueeze)
  80                 (raGraph s)
  81
  82
  83  ppr (s@RegAllocStatsSpill{})
  84         =  text "#  Spill"
  85
  86         $$ text "#  Code with liveness information."
  87         $$ (ppr (raCode s))
  88         $$ text ""
  89
  90         $$ (if (not $ isNullUFM $ raCoalesced s)
  91                 then    text "#  Registers coalesced."
  92                         $$ (vcat $ map ppr $ ufmToList $ raCoalesced s)
  93                         $$ text ""
  94                 else empty)
  95
  96         $$ text "#  Spills inserted."
  97         $$ ppr (raSpillStats s)
  98         $$ text ""
  99
 100         $$ text "#  Code with spills inserted."
 101         $$ (ppr (raSpilled s))
 102
 103
 104  ppr (s@RegAllocStatsColored { raSRMs = (spills, reloads, moves) })
 105         =  text "#  Colored"
 106
 107         $$ text "#  Code with liveness information."
 108         $$ (ppr (raCode s))
 109         $$ text ""
 110
 111         $$ text "#  Register conflict graph (colored)."
 112         $$ Color.dotGraph
 113                 targetRegDotColor
 114                 (trivColorable
 115                         targetVirtualRegSqueeze
 116                         targetRealRegSqueeze)
 117                 (raGraphColored s)
 118         $$ text ""
 119
 120         $$ (if (not $ isNullUFM $ raCoalesced s)
 121                 then    text "#  Registers coalesced."
 122                         $$ (vcat $ map ppr $ ufmToList $ raCoalesced s)
 123                         $$ text ""
 124                 else empty)
 125
 126         $$ text "#  Native code after coalescings applied."
 127         $$ ppr (raCodeCoalesced s)
 128         $$ text ""
 129
 130         $$ text "#  Native code after register allocation."
 131         $$ ppr (raPatched s)
 132         $$ text ""
 133
 134         $$ text "#  Clean out unneeded spill/reloads."
 135         $$ ppr (raSpillClean s)
 136         $$ text ""
 137
 138         $$ text "#  Final code, after rewriting spill/rewrite pseudo instrs."
 139         $$ ppr (raFinal s)
 140         $$ text ""
 141         $$  text "#  Score:"
 142         $$ (text "#          spills  inserted: " <> int spills)
 143         $$ (text "#          reloads inserted: " <> int reloads)
 144         $$ (text "#   reg-reg moves remaining: " <> int moves)
 145         $$ text ""
 146
 147 -- | Do all the different analysis on this list of RegAllocStats
 148 pprStats
 149         :: [RegAllocStats instr]
 150         -> Color.Graph VirtualReg RegClass RealReg
 151         -> SDoc
 152
 153 pprStats stats graph
 154  = let  outSpills       = pprStatsSpills    stats
 155         outLife         = pprStatsLifetimes stats
 156         outConflict     = pprStatsConflict  stats
 157         outScatter      = pprStatsLifeConflict stats graph
 158
 159   in    vcat [outSpills, outLife, outConflict, outScatter]
 160
 161
 162 -- | Dump a table of how many spill loads \/ stores were inserted for each vreg.
 163 pprStatsSpills
 164         :: [RegAllocStats instr] -> SDoc
 165
 166 pprStatsSpills stats
 167  = let
 168         finals  = [ s   | s@RegAllocStatsColored{} <- stats]
 169
 170         -- sum up how many stores\/loads\/reg-reg-moves were left in the code
 171         total   = foldl' addSRM (0, 0, 0)
 172                 $ map raSRMs finals
 173
 174     in  (  text "-- spills-added-total"
 175         $$ text "--    (stores, loads, reg_reg_moves_remaining)"
 176         $$ ppr total
 177         $$ text "")
 178
 179
 180 -- | Dump a table of how long vregs tend to live for in the initial code.
 181 pprStatsLifetimes
 182         :: [RegAllocStats instr] -> SDoc
 183
 184 pprStatsLifetimes stats
 185  = let  info            = foldl' plusSpillCostInfo zeroSpillCostInfo
 186                                 [ raSpillCosts s
 187                                         | s@RegAllocStatsStart{} <- stats ]
 188
 189         lifeBins        = binLifetimeCount $ lifeMapFromSpillCostInfo info
 190
 191    in   (  text "-- vreg-population-lifetimes"
 192         $$ text "--   (instruction_count, number_of_vregs_that_lived_that_long)"
 193         $$ (vcat $ map ppr $ eltsUFM lifeBins)
 194         $$ text "\n")
 195
 196 binLifetimeCount :: UniqFM (VirtualReg, Int) -> UniqFM (Int, Int)
 197 binLifetimeCount fm
 198  = let  lifes   = map (\l -> (l, (l, 1)))
 199                 $ map snd
 200                 $ eltsUFM fm
 201
 202    in   addListToUFM_C
 203                 (\(l1, c1) (_, c2) -> (l1, c1 + c2))
 204                 emptyUFM
 205                 lifes
 206
 207
 208 -- | Dump a table of how many conflicts vregs tend to have in the initial code.
 209 pprStatsConflict
 210         :: [RegAllocStats instr] -> SDoc
 211
 212 pprStatsConflict stats
 213  = let  confMap = foldl' (plusUFM_C (\(c1, n1) (_, n2) -> (c1, n1 + n2)))
 214                         emptyUFM
 215                 $ map Color.slurpNodeConflictCount
 216                         [ raGraph s | s@RegAllocStatsStart{} <- stats ]
 217
 218    in   (  text "-- vreg-conflicts"
 219         $$ text "--   (conflict_count, number_of_vregs_that_had_that_many_conflicts)"
 220         $$ (vcat $ map ppr $ eltsUFM confMap)
 221         $$ text "\n")
 222
 223
 224 -- | For every vreg, dump it's how many conflicts it has and its lifetime
 225 --      good for making a scatter plot.
 226 pprStatsLifeConflict
 227         :: [RegAllocStats instr]
 228         -> Color.Graph VirtualReg RegClass RealReg      -- ^ global register conflict graph
 229         -> SDoc
 230
 231 pprStatsLifeConflict stats graph
 232  = let  lifeMap = lifeMapFromSpillCostInfo
 233                 $ foldl' plusSpillCostInfo zeroSpillCostInfo
 234                 $ [ raSpillCosts s | s@RegAllocStatsStart{} <- stats ]
 235
 236         scatter = map   (\r ->  let lifetime    = case lookupUFM lifeMap r of
 237                                                         Just (_, l)     -> l
 238                                                         Nothing         -> 0
 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)
 243                                         , ppr $ lifetime ])
 244                 $ map Color.nodeId
 245                 $ eltsUFM
 246                 $ Color.graphMap graph
 247
 248    in   (  text "-- vreg-conflict-lifetime"
 249         $$ text "--   (vreg, vreg_conflicts, vreg_lifetime)"
 250         $$ (vcat scatter)
 251         $$ text "\n")
 252
 253
 254 -- | Count spill/reload/reg-reg moves.
 255 --      Lets us see how well the register allocator has done.
 256 countSRMs
 257         :: Instruction instr
 258         => LiveCmmTop instr -> (Int, Int, Int)
 259
 260 countSRMs cmm
 261         = execState (mapBlockTopM countSRM_block cmm) (0, 0, 0)
 262
 263 countSRM_block (BasicBlock i instrs)
 264  = do   instrs' <- mapM countSRM_instr instrs
 265         return  $ BasicBlock i instrs'
 266
 267 countSRM_instr li
 268         | LiveInstr SPILL{} _    <- li
 269         = do    modify  $ \(s, r, m)    -> (s + 1, r, m)
 270                 return li
 271
 272         | LiveInstr RELOAD{} _  <- li
 273         = do    modify  $ \(s, r, m)    -> (s, r + 1, m)
 274                 return li
 275
 276         | LiveInstr instr _     <- li
 277         , Just _        <- takeRegRegMoveInstr instr
 278         = do    modify  $ \(s, r, m)    -> (s, r, m + 1)
 279                 return li
 280
 281         | otherwise
 282         =       return li
 283
 284 -- sigh..
 285 addSRM (s1, r1, m1) (s2, r2, m2)
 286         = (s1+s2, r1+r2, m1+m2)
 287