compiler/nativeGen/RegAlloc/Graph/SpillCost.hs

   1
   2 module RegAlloc.Graph.SpillCost (
   3         SpillCostRecord,
   4         plusSpillCostRecord,
   5         pprSpillCostRecord,
   6
   7         SpillCostInfo,
   8         zeroSpillCostInfo,
   9         plusSpillCostInfo,
  10
  11         slurpSpillCostInfo,
  12         chooseSpill,
  13
  14         lifeMapFromSpillCostInfo
  15 )
  16
  17 where
  18
  19 import RegAlloc.Liveness
  20 import Instruction
  21 import RegClass
  22 import Reg
  23
  24 import GraphBase
  25
  26
  27 import BlockId
  28 import Cmm
  29 import UniqFM
  30 import UniqSet
  31 import Outputable
  32 import State
  33
  34 import Data.List        (nub, minimumBy)
  35 import Data.Maybe
  36 import Control.Monad
  37
  38 type SpillCostRecord
  39  =      ( VirtualReg    -- register name
  40         , Int           -- number of writes to this reg
  41         , Int           -- number of reads from this reg
  42         , Int)          -- number of instrs this reg was live on entry to
  43
  44 type SpillCostInfo
  45         = UniqFM SpillCostRecord
  46
  47
  48 zeroSpillCostInfo :: SpillCostInfo
  49 zeroSpillCostInfo       = emptyUFM
  50
  51 -- | Add two spillCostInfos
  52 plusSpillCostInfo :: SpillCostInfo -> SpillCostInfo -> SpillCostInfo
  53 plusSpillCostInfo sc1 sc2
  54         = plusUFM_C plusSpillCostRecord sc1 sc2
  55
  56 plusSpillCostRecord :: SpillCostRecord -> SpillCostRecord -> SpillCostRecord
  57 plusSpillCostRecord (r1, a1, b1, c1) (r2, a2, b2, c2)
  58         | r1 == r2      = (r1, a1 + a2, b1 + b2, c1 + c2)
  59         | otherwise     = error "RegSpillCost.plusRegInt: regs don't match"
  60
  61
  62 -- | Slurp out information used for determining spill costs
  63 --      for each vreg, the number of times it was written to, read from,
  64 --      and the number of instructions it was live on entry to (lifetime)
  65 --
  66 slurpSpillCostInfo
  67         :: (Outputable instr, Instruction instr)
  68         => LiveCmmTop instr
  69         -> SpillCostInfo
  70
  71 slurpSpillCostInfo cmm
  72         = execState (countCmm cmm) zeroSpillCostInfo
  73  where
  74         countCmm CmmData{}              = return ()
  75         countCmm (CmmProc info _ _ (ListGraph blocks))
  76                 = mapM_ (countComp info) blocks
  77
  78         countComp info (BasicBlock _ blocks)
  79                 = mapM_ (countBlock info) blocks
  80
  81         -- lookup the regs that are live on entry to this block in
  82         --      the info table from the CmmProc
  83         countBlock info (BasicBlock blockId instrs)
  84                 | LiveInfo _ _ blockLive        <- info
  85                 , Just rsLiveEntry              <- lookupBlockEnv blockLive blockId
  86
  87                 , rsLiveEntry_virt      <- mapUniqSet (\(RegVirtual vr) -> vr)
  88                                         $  filterUniqSet isVirtualReg rsLiveEntry
  89
  90                 = countLIs rsLiveEntry_virt instrs
  91
  92                 | otherwise
  93                 = error "RegAlloc.SpillCost.slurpSpillCostInfo: bad block"
  94
  95         countLIs _      []
  96                 = return ()
  97
  98         -- skip over comment and delta pseudo instrs
  99         countLIs rsLive (SPILL{} : lis)
 100                 = countLIs rsLive lis
 101
 102         countLIs rsLive (RELOAD{} : lis)
 103                 = countLIs rsLive lis
 104
 105         countLIs rsLive (Instr instr Nothing : lis)
 106                 | isMetaInstr instr
 107                 = countLIs rsLive lis
 108
 109                 | otherwise
 110                 = pprPanic "RegSpillCost.slurpSpillCostInfo"
 111                         (text "no liveness information on instruction " <> ppr instr)
 112
 113         countLIs rsLiveEntry (Instr instr (Just live) : lis)
 114          = do
 115                 -- increment the lifetime counts for regs live on entry to this instr
 116                 mapM_ incLifetime $ uniqSetToList rsLiveEntry
 117
 118                 -- increment counts for what regs were read/written from
 119                 let (RU read written)   = regUsageOfInstr instr
 120                 mapM_ incUses   $ catMaybes $ map takeVirtualReg $ nub read
 121                 mapM_ incDefs   $ catMaybes $ map takeVirtualReg $ nub written
 122
 123                 -- compute liveness for entry to next instruction.
 124                 let takeVirtuals set
 125                         = mapUniqSet (\(RegVirtual vr) -> vr)
 126                         $ filterUniqSet isVirtualReg set
 127
 128                 let liveDieRead_virt    = takeVirtuals (liveDieRead  live)
 129                 let liveDieWrite_virt   = takeVirtuals (liveDieWrite live)
 130                 let liveBorn_virt       = takeVirtuals (liveBorn     live)
 131
 132                 let rsLiveAcross
 133                         = rsLiveEntry `minusUniqSet` liveDieRead_virt
 134
 135                 let rsLiveNext
 136                         = (rsLiveAcross `unionUniqSets` liveBorn_virt)
 137                                         `minusUniqSet`  liveDieWrite_virt
 138
 139                 countLIs rsLiveNext lis
 140
 141         incDefs     reg = modify $ \s -> addToUFM_C plusSpillCostRecord s reg (reg, 1, 0, 0)
 142         incUses     reg = modify $ \s -> addToUFM_C plusSpillCostRecord s reg (reg, 0, 1, 0)
 143         incLifetime reg = modify $ \s -> addToUFM_C plusSpillCostRecord s reg (reg, 0, 0, 1)
 144
 145
 146 -- | Choose a node to spill from this graph
 147
 148 chooseSpill
 149         :: SpillCostInfo
 150         -> Graph VirtualReg RegClass RealReg
 151         -> VirtualReg
 152
 153 chooseSpill info graph
 154  = let  cost    = spillCost_length info graph
 155         node    = minimumBy (\n1 n2 -> compare (cost $ nodeId n1) (cost $ nodeId n2))
 156                 $ eltsUFM $ graphMap graph
 157
 158    in   nodeId node
 159
 160
 161
 162 -- | Chaitins spill cost function is:
 163 --
 164 --          cost =     sum         loadCost * freq (u)  +    sum        storeCost * freq (d)
 165 --                  u <- uses (v)                         d <- defs (v)
 166 --
 167 --      There are no loops in our code at the momemnt, so we can set the freq's to 1
 168 --      We divide this by the degree if t
 169 --
 170 --
 171 --  If we don't have live range splitting then Chaitins function performs badly if we have
 172 --      lots of nested live ranges and very few registers.
 173 --
 174 --               v1 v2 v3
 175 --      def v1   .
 176 --      use v1   .
 177 --      def v2   .  .
 178 --      def v3   .  .  .
 179 --      use v1   .  .  .
 180 --      use v3   .  .  .
 181 --      use v2   .  .
 182 --      use v1   .
 183 --
 184 --
 185 --           defs uses degree   cost
 186 --      v1:  1     3     3      1.5
 187 --      v2:  1     2     3      1.0
 188 --      v3:  1     1     3      0.666
 189 --
 190 --      v3 has the lowest cost, but if we only have 2 hardregs and we insert spill code for v3
 191 --      then this isn't going to improve the colorability of the graph.
 192 --
 193 --  When compiling SHA1, which as very long basic blocks and some vregs with very long live ranges
 194 --      the allocator seems to try and spill from the inside out and eventually run out of stack slots.
 195 --
 196 --  Without live range splitting, its's better to spill from the outside in so set the cost of very
 197 --      long live ranges to zero
 198 --
 199 {-
 200 spillCost_chaitin
 201         :: SpillCostInfo
 202         -> Graph Reg RegClass Reg
 203         -> Reg
 204         -> Float
 205
 206 spillCost_chaitin info graph reg
 207         -- Spilling a live range that only lives for 1 instruction isn't going to help
 208         --      us at all - and we definately want to avoid trying to re-spill previously
 209         --      inserted spill code.
 210         | lifetime <= 1         = 1/0
 211
 212         -- It's unlikely that we'll find a reg for a live range this long
 213         --      better to spill it straight up and not risk trying to keep it around
 214         --      and have to go through the build/color cycle again.
 215         | lifetime > allocatableRegsInClass (regClass reg) * 10
 216         = 0
 217
 218         -- otherwise revert to chaitin's regular cost function.
 219         | otherwise     = fromIntegral (uses + defs) / fromIntegral (nodeDegree graph reg)
 220         where (_, defs, uses, lifetime)
 221                 = fromMaybe (reg, 0, 0, 0) $ lookupUFM info reg
 222 -}
 223
 224 -- Just spill the longest live range.
 225 spillCost_length
 226         :: SpillCostInfo
 227         -> Graph VirtualReg RegClass RealReg
 228         -> VirtualReg
 229         -> Float
 230
 231 spillCost_length info _ reg
 232         | lifetime <= 1         = 1/0
 233         | otherwise             = 1 / fromIntegral lifetime
 234         where (_, _, _, lifetime)
 235                 = fromMaybe (reg, 0, 0, 0)
 236                 $ lookupUFM info reg
 237
 238
 239
 240 lifeMapFromSpillCostInfo :: SpillCostInfo -> UniqFM (VirtualReg, Int)
 241 lifeMapFromSpillCostInfo info
 242         = listToUFM
 243         $ map (\(r, _, _, life) -> (r, (r, life)))
 244         $ eltsUFM info
 245
 246
 247 -- | Work out the degree (number of neighbors) of this node which have the same class.
 248 nodeDegree
 249         :: (VirtualReg -> RegClass)
 250         -> Graph VirtualReg RegClass RealReg
 251         -> VirtualReg
 252         -> Int
 253
 254 nodeDegree classOfVirtualReg graph reg
 255         | Just node     <- lookupUFM (graphMap graph) reg
 256
 257         , virtConflicts <- length
 258                         $ filter (\r -> classOfVirtualReg r == classOfVirtualReg reg)
 259                         $ uniqSetToList
 260                         $ nodeConflicts node
 261
 262         = virtConflicts + sizeUniqSet (nodeExclusions node)
 263
 264         | otherwise
 265         = 0
 266
 267
 268 -- | Show a spill cost record, including the degree from the graph and final calulated spill cos
 269 pprSpillCostRecord
 270         :: (VirtualReg -> RegClass)
 271         -> (Reg -> SDoc)
 272         -> Graph VirtualReg RegClass RealReg
 273         -> SpillCostRecord
 274         -> SDoc
 275
 276 pprSpillCostRecord regClass pprReg graph (reg, uses, defs, life)
 277         =  hsep
 278         [ pprReg (RegVirtual reg)
 279         , ppr uses
 280         , ppr defs
 281         , ppr life
 282         , ppr $ nodeDegree regClass graph reg
 283         , text $ show $ (fromIntegral (uses + defs)
 284                         / fromIntegral (nodeDegree regClass graph reg) :: Float) ]
 285
 286