compiler/nativeGen/RegSpillCost.hs

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