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