compiler/nativeGen/RegAllocStats.hs

   1
   2 -- Carries interesting info for debugging / profiling of the
   3 --      graph coloring register allocator.
   4
   5 module RegAllocStats (
   6         RegAllocStats (..),
   7         regDotColor,
   8
   9         pprStats,
  10         pprStatsSpills,
  11         pprStatsLifetimes,
  12         pprStatsConflict,
  13         pprStatsLifeConflict
  14 )
  15
  16 where
  17
  18 #include "nativeGen/NCG.h"
  19
  20 import qualified GraphColor as Color
  21 import RegLiveness
  22 import RegSpill
  23 import MachRegs
  24 import MachInstrs
  25
  26 import Outputable
  27 import UniqFM
  28 import UniqSet
  29
  30 import Data.List
  31
  32 data RegAllocStats
  33
  34         -- initial graph
  35         = RegAllocStatsStart
  36         { raLiveCmm     :: [LiveCmmTop]                   -- ^ initial code, with liveness
  37         , raGraph       :: Color.Graph Reg RegClass Reg  -- ^ the initial, uncolored graph
  38         , raLifetimes   :: UniqFM (Reg, Int) }            -- ^ number of instrs each reg lives for
  39
  40         -- a spill stage
  41         | RegAllocStatsSpill
  42         { raGraph       :: Color.Graph Reg RegClass Reg -- ^ the partially colored graph
  43         , raSpillStats  :: SpillStats                   -- ^ spiller stats
  44         , raLifetimes   :: UniqFM (Reg, Int)            -- ^ number of instrs each reg lives for
  45         , raSpilled     :: [LiveCmmTop] }               -- ^ code with spill instructions added
  46
  47         -- a successful coloring
  48         | RegAllocStatsColored
  49         { raGraph       :: Color.Graph Reg RegClass Reg -- ^ the colored graph
  50         , raPatched     :: [LiveCmmTop]                 -- ^ code with vregs replaced by hregs
  51         , raSpillClean  :: [LiveCmmTop]                 -- ^ code with unneeded spill/reloads cleaned out
  52         , raFinal       :: [NatCmmTop] }                -- ^ final code
  53
  54 instance Outputable RegAllocStats where
  55
  56  ppr (s@RegAllocStatsStart{})
  57         =  text "#  Start"
  58         $$ text "#  Native code with liveness information."
  59         $$ ppr (raLiveCmm s)
  60         $$ text ""
  61         $$ text "#  Initial register conflict graph."
  62         $$ Color.dotGraph regDotColor trivColorable (raGraph s)
  63
  64  ppr (s@RegAllocStatsSpill{})
  65         =  text "#  Spill"
  66         $$ text "#  Register conflict graph."
  67         $$ Color.dotGraph regDotColor trivColorable (raGraph s)
  68         $$ text ""
  69         $$ text "#  Spills inserted."
  70         $$ ppr (raSpillStats s)
  71         $$ text ""
  72         $$ text "#  Code with spills inserted."
  73         $$ (ppr (raSpilled s))
  74
  75  ppr (s@RegAllocStatsColored{})
  76         =  text "#  Colored"
  77         $$ text "#  Register conflict graph."
  78         $$ Color.dotGraph regDotColor trivColorable (raGraph s)
  79         $$ text ""
  80         $$ text "#  Native code after register allocation."
  81         $$ ppr (raPatched s)
  82         $$ text ""
  83         $$ text "#  Clean out unneeded spill/reloads."
  84         $$ ppr (raSpillClean s)
  85         $$ text ""
  86         $$ text "#  Final code, after rewriting spill/rewrite pseudo instrs."
  87         $$ ppr (raFinal s)
  88         $$ text ""
  89
  90
  91 -- | Do all the different analysis on this list of RegAllocStats
  92 pprStats :: [RegAllocStats] -> Color.Graph Reg RegClass Reg -> SDoc
  93 pprStats stats graph
  94  = let  outSpills       = pprStatsSpills    stats
  95         outLife         = pprStatsLifetimes stats
  96         outConflict     = pprStatsConflict  stats
  97         outScatter      = pprStatsLifeConflict stats graph
  98
  99   in    vcat [outSpills, outLife, outConflict, outScatter]
 100
 101
 102 -- | Dump a table of how many spill loads / stores were inserted for each vreg.
 103 pprStatsSpills
 104         :: [RegAllocStats] -> SDoc
 105
 106 pprStatsSpills stats
 107  = let  -- slurp out the stats from all the spiller stages
 108         spillStats      = [ s   | s@RegAllocStatsSpill{} <- stats]
 109
 110         -- build a map of how many spill load/stores were inserted for each vreg
 111         spillSL         = foldl' (plusUFM_C accSpillSL) emptyUFM
 112                         $ map (spillStoreLoad . raSpillStats) spillStats
 113
 114         -- print the count of load/spills as a tuple so we can read back from the file easilly
 115         pprSpillSL (r, loads, stores)
 116          = (parens $ (hcat $ punctuate (text ", ") [doubleQuotes (ppr r), int loads, int stores]))
 117
 118         -- sum up the total number of spill instructions inserted
 119         spillList       = eltsUFM spillSL
 120         spillTotal      = foldl' (\(s1, l1) (s2, l2) -> (s1 + s2, l1 + l2))
 121                                 (0, 0)
 122                         $ map (\(n, s, l) -> (s, l))
 123                         $ spillList
 124
 125     in  (  text "-- spills-added-total"
 126         $$ text "--    (stores, loads)"
 127         $$ (ppr spillTotal)
 128         $$ text ""
 129         $$ text "-- spills-added"
 130         $$ text "--    (reg_name, stores, loads)"
 131         $$ (vcat $ map pprSpillSL $ spillList)
 132         $$ text "")
 133
 134
 135 -- | Dump a table of how long vregs tend to live for in the initial code.
 136 pprStatsLifetimes
 137         :: [RegAllocStats] -> SDoc
 138
 139 pprStatsLifetimes stats
 140  = let  lifeMap         = foldl' plusUFM emptyUFM
 141                                 [ raLifetimes s | s@RegAllocStatsStart{} <- stats ]
 142         lifeBins        = binLifetimeCount lifeMap
 143
 144    in   (  text "-- vreg-population-lifetimes"
 145         $$ text "--   (instruction_count, number_of_vregs_that_lived_that_long)"
 146         $$ (vcat $ map ppr $ eltsUFM lifeBins)
 147         $$ text "\n")
 148
 149 binLifetimeCount :: UniqFM (Reg, Int) -> UniqFM (Int, Int)
 150 binLifetimeCount fm
 151  = let  lifes   = map (\l -> (l, (l, 1)))
 152                 $ map snd
 153                 $ eltsUFM fm
 154
 155    in   addListToUFM_C
 156                 (\(l1, c1) (l2, c2) -> (l1, c1 + c2))
 157                 emptyUFM
 158                 lifes
 159
 160
 161 -- | Dump a table of how many conflicts vregs tend to have in the initial code.
 162 pprStatsConflict
 163         :: [RegAllocStats] -> SDoc
 164
 165 pprStatsConflict stats
 166  = let  confMap = foldl' (plusUFM_C (\(c1, n1) (c2, n2) -> (c1, n1 + n2)))
 167                         emptyUFM
 168                 $ map Color.slurpNodeConflictCount
 169                         [ raGraph s | s@RegAllocStatsStart{} <- stats ]
 170
 171    in   (  text "-- vreg-conflicts"
 172         $$ text "--   (conflict_count, number_of_vregs_that_had_that_many_conflicts)"
 173         $$ (vcat $ map ppr $ eltsUFM confMap)
 174         $$ text "\n")
 175
 176
 177 -- | For every vreg, dump it's how many conflicts it has and its lifetime
 178 --      good for making a scatter plot.
 179 pprStatsLifeConflict
 180         :: [RegAllocStats]
 181         -> Color.Graph Reg RegClass Reg         -- ^ global register conflict graph
 182         -> SDoc
 183
 184 pprStatsLifeConflict stats graph
 185  = let  lifeMap = foldl' plusUFM emptyUFM
 186                         [ raLifetimes s | s@RegAllocStatsStart{} <- stats ]
 187
 188         scatter = map   (\r ->  let lifetime    = case lookupUFM lifeMap r of
 189                                                         Just (_, l)     -> l
 190                                                         Nothing         -> 0
 191                                     Just node   = Color.lookupNode graph r
 192                                 in parens $ hcat $ punctuate (text ", ")
 193                                         [ doubleQuotes $ ppr $ Color.nodeId node
 194                                         , ppr $ sizeUniqSet (Color.nodeConflicts node)
 195                                         , ppr $ lifetime ])
 196                 $ map Color.nodeId
 197                 $ eltsUFM
 198                 $ Color.graphMap graph
 199
 200    in   (  text "-- vreg-conflict-lifetime"
 201         $$ text "--   (vreg, vreg_conflicts, vreg_lifetime)"
 202         $$ (vcat scatter)
 203         $$ text "\n")
 204
 205
 206 -----
 207 -- Register colors for drawing conflict graphs
 208 --      Keep this out of MachRegs.hs because it's specific to the graph coloring allocator.
 209
 210
 211 -- reg colors for x86
 212 #if i386_TARGET_ARCH
 213 regDotColor :: Reg -> SDoc
 214 regDotColor reg
 215  = let  Just    str     = lookupUFM regColors reg
 216    in   text str
 217
 218 regColors
 219  = listToUFM
 220  $      [ (eax, "#00ff00")
 221         , (ebx, "#0000ff")
 222         , (ecx, "#00ffff")
 223         , (edx, "#0080ff")
 224
 225         , (fake0, "#ff00ff")
 226         , (fake1, "#ff00aa")
 227         , (fake2, "#aa00ff")
 228         , (fake3, "#aa00aa")
 229         , (fake4, "#ff0055")
 230         , (fake5, "#5500ff") ]
 231 #endif
 232
 233
 234 -- reg colors for x86_64
 235 #if x86_64_TARGET_ARCH
 236 regDotColor :: Reg -> SDoc
 237 regDotColor reg
 238  = let  Just    str     = lookupUFM regColors reg
 239    in   text str
 240
 241 regColors
 242  = listToUFM
 243  $      [ (rax, "#00ff00"), (eax, "#00ff00")
 244         , (rbx, "#0000ff"), (ebx, "#0000ff")
 245         , (rcx, "#00ffff"), (ecx, "#00ffff")
 246         , (rdx, "#0080ff"), (edx, "#00ffff")
 247         , (r8,  "#00ff80")
 248         , (r9,  "#008080")
 249         , (r10, "#0040ff")
 250         , (r11, "#00ff40")
 251         , (r12, "#008040")
 252         , (r13, "#004080")
 253         , (r14, "#004040")
 254         , (r15, "#002080") ]
 255
 256         ++ zip (map RealReg [16..31]) (repeat "red")
 257 #endif
 258
 259
 260 -- reg colors for ppc
 261 #if powerpc_TARGET_ARCH
 262 regDotColor :: Reg -> SDoc
 263 regDotColor reg
 264  = case regClass reg of
 265         RcInteger       -> text "blue"
 266         RcFloat         -> text "red"
 267 #endif
 268
 269
 270 {-
 271 toX11Color (r, g, b)
 272  = let  rs      = padL 2 '0' (showHex r "")
 273         gs      = padL 2 '0' (showHex r "")
 274         bs      = padL 2 '0' (showHex r "")
 275
 276         padL n c s
 277                 = replicate (n - length s) c ++ s
 278   in    "#" ++ rs ++ gs ++ bs
 279 -}