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  =      ( Reg   -- 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                 = countLIs rsLiveEntry instrs
  87
  88                 | otherwise
  89                 = error "RegAlloc.SpillCost.slurpSpillCostInfo: bad block"
  90
  91         countLIs _      []
  92                 = return ()
  93
  94         -- skip over comment and delta pseudo instrs
  95         countLIs rsLive (SPILL{} : lis)
  96                 = countLIs rsLive lis
  97
  98         countLIs rsLive (RELOAD{} : lis)
  99                 = countLIs rsLive lis
 100
 101         countLIs rsLive (Instr instr Nothing : lis)
 102                 | isMetaInstr instr
 103                 = countLIs rsLive lis
 104
 105                 | otherwise
 106                 = pprPanic "RegSpillCost.slurpSpillCostInfo"
 107                         (text "no liveness information on instruction " <> ppr instr)
 108
 109         countLIs rsLiveEntry (Instr instr (Just live) : lis)
 110          = do
 111                 -- increment the lifetime counts for regs live on entry to this instr
 112                 mapM_ incLifetime $ uniqSetToList rsLiveEntry
 113
 114                 -- increment counts for what regs were read/written from
 115                 let (RU read written)   = regUsageOfInstr instr
 116                 mapM_ incUses   $ filter (not . isRealReg) $ nub read
 117                 mapM_ incDefs   $ filter (not . isRealReg) $ nub written
 118
 119                 -- compute liveness for entry to next instruction.
 120                 let rsLiveAcross
 121                         = rsLiveEntry `minusUniqSet` (liveDieRead live)
 122
 123                 let rsLiveNext
 124                         = (rsLiveAcross `unionUniqSets` (liveBorn     live))
 125                                         `minusUniqSet` (liveDieWrite live)
 126
 127                 countLIs rsLiveNext lis
 128
 129         incDefs     reg = modify $ \s -> addToUFM_C plusSpillCostRecord s reg (reg, 1, 0, 0)
 130         incUses     reg = modify $ \s -> addToUFM_C plusSpillCostRecord s reg (reg, 0, 1, 0)
 131         incLifetime reg = modify $ \s -> addToUFM_C plusSpillCostRecord s reg (reg, 0, 0, 1)
 132
 133
 134 -- | Choose a node to spill from this graph
 135
 136 chooseSpill
 137         :: SpillCostInfo
 138         -> Graph Reg RegClass Reg
 139         -> Reg
 140
 141 chooseSpill info graph
 142  = let  cost    = spillCost_length info graph
 143         node    = minimumBy (\n1 n2 -> compare (cost $ nodeId n1) (cost $ nodeId n2))
 144                 $ eltsUFM $ graphMap graph
 145
 146    in   nodeId node
 147
 148
 149
 150 -- | Chaitins spill cost function is:
 151 --
 152 --          cost =     sum         loadCost * freq (u)  +    sum        storeCost * freq (d)
 153 --                  u <- uses (v)                         d <- defs (v)
 154 --
 155 --      There are no loops in our code at the momemnt, so we can set the freq's to 1
 156 --      We divide this by the degree if t
 157 --
 158 --
 159 --  If we don't have live range splitting then Chaitins function performs badly if we have
 160 --      lots of nested live ranges and very few registers.
 161 --
 162 --               v1 v2 v3
 163 --      def v1   .
 164 --      use v1   .
 165 --      def v2   .  .
 166 --      def v3   .  .  .
 167 --      use v1   .  .  .
 168 --      use v3   .  .  .
 169 --      use v2   .  .
 170 --      use v1   .
 171 --
 172 --
 173 --           defs uses degree   cost
 174 --      v1:  1     3     3      1.5
 175 --      v2:  1     2     3      1.0
 176 --      v3:  1     1     3      0.666
 177 --
 178 --      v3 has the lowest cost, but if we only have 2 hardregs and we insert spill code for v3
 179 --      then this isn't going to improve the colorability of the graph.
 180 --
 181 --  When compiling SHA1, which as very long basic blocks and some vregs with very long live ranges
 182 --      the allocator seems to try and spill from the inside out and eventually run out of stack slots.
 183 --
 184 --  Without live range splitting, its's better to spill from the outside in so set the cost of very
 185 --      long live ranges to zero
 186 --
 187 {-
 188 spillCost_chaitin
 189         :: SpillCostInfo
 190         -> Graph Reg RegClass Reg
 191         -> Reg
 192         -> Float
 193
 194 spillCost_chaitin info graph reg
 195         -- Spilling a live range that only lives for 1 instruction isn't going to help
 196         --      us at all - and we definately want to avoid trying to re-spill previously
 197         --      inserted spill code.
 198         | lifetime <= 1         = 1/0
 199
 200         -- It's unlikely that we'll find a reg for a live range this long
 201         --      better to spill it straight up and not risk trying to keep it around
 202         --      and have to go through the build/color cycle again.
 203         | lifetime > allocatableRegsInClass (regClass reg) * 10
 204         = 0
 205
 206         -- otherwise revert to chaitin's regular cost function.
 207         | otherwise     = fromIntegral (uses + defs) / fromIntegral (nodeDegree graph reg)
 208         where (_, defs, uses, lifetime)
 209                 = fromMaybe (reg, 0, 0, 0) $ lookupUFM info reg
 210 -}
 211
 212 -- Just spill the longest live range.
 213 spillCost_length
 214         :: SpillCostInfo
 215         -> Graph Reg RegClass Reg
 216         -> Reg
 217         -> Float
 218
 219 spillCost_length info _ reg
 220         | lifetime <= 1         = 1/0
 221         | otherwise             = 1 / fromIntegral lifetime
 222         where (_, _, _, lifetime)
 223                 = fromMaybe (reg, 0, 0, 0) $ lookupUFM info reg
 224
 225
 226
 227 lifeMapFromSpillCostInfo :: SpillCostInfo -> UniqFM (Reg, Int)
 228 lifeMapFromSpillCostInfo info
 229         = listToUFM
 230         $ map (\(r, _, _, life) -> (r, (r, life)))
 231         $ eltsUFM info
 232
 233
 234 -- | Work out the degree (number of neighbors) of this node which have the same class.
 235 nodeDegree
 236         :: (Reg -> RegClass)
 237         -> Graph Reg RegClass Reg -> Reg -> Int
 238
 239 nodeDegree regClass graph reg
 240         | Just node     <- lookupUFM (graphMap graph) reg
 241         , virtConflicts <- length       $ filter (\r -> regClass r == regClass reg)
 242                                         $ uniqSetToList $ nodeConflicts node
 243         = virtConflicts + sizeUniqSet (nodeExclusions node)
 244
 245         | otherwise
 246         = 0
 247
 248
 249 -- | Show a spill cost record, including the degree from the graph and final calulated spill cos
 250 pprSpillCostRecord
 251         :: (Reg -> RegClass)
 252         -> (Reg -> SDoc)
 253         -> Graph Reg RegClass Reg -> SpillCostRecord -> SDoc
 254
 255 pprSpillCostRecord regClass pprReg graph (reg, uses, defs, life)
 256         =  hsep
 257         [ pprReg reg
 258         , ppr uses
 259         , ppr defs
 260         , ppr life
 261         , ppr $ nodeDegree regClass graph reg
 262         , text $ show $ (fromIntegral (uses + defs)
 263                         / fromIntegral (nodeDegree regClass graph reg) :: Float) ]