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