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