2 module RegAlloc.Graph.SpillCost (
14 lifeMapFromSpillCostInfo
20 import RegAlloc.Liveness
32 import Data.List (nub, minimumBy)
37 = ( Reg -- register name
38 , Int -- number of writes to this reg
39 , Int -- number of reads from this reg
40 , Int) -- number of instrs this reg was live on entry to
43 = UniqFM SpillCostRecord
46 zeroSpillCostInfo :: SpillCostInfo
47 zeroSpillCostInfo = emptyUFM
49 -- | Add two spillCostInfos
50 plusSpillCostInfo :: SpillCostInfo -> SpillCostInfo -> SpillCostInfo
51 plusSpillCostInfo sc1 sc2
52 = plusUFM_C plusSpillCostRecord sc1 sc2
54 plusSpillCostRecord :: SpillCostRecord -> SpillCostRecord -> SpillCostRecord
55 plusSpillCostRecord (r1, a1, b1, c1) (r2, a2, b2, c2)
56 | r1 == r2 = (r1, a1 + a2, b1 + b2, c1 + c2)
57 | otherwise = error "RegSpillCost.plusRegInt: regs don't match"
60 -- | Slurp out information used for determining spill costs
61 -- for each vreg, the number of times it was written to, read from,
62 -- and the number of instructions it was live on entry to (lifetime)
68 slurpSpillCostInfo cmm
69 = execState (countCmm cmm) zeroSpillCostInfo
71 countCmm CmmData{} = return ()
72 countCmm (CmmProc info _ _ (ListGraph blocks))
73 = mapM_ (countComp info) blocks
75 countComp info (BasicBlock _ blocks)
76 = mapM_ (countBlock info) blocks
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 _ _ blockLive <- info
82 , Just rsLiveEntry <- lookupBlockEnv blockLive blockId
83 = countLIs rsLiveEntry instrs
86 = error "RegAlloc.SpillCost.slurpSpillCostInfo: bad block"
91 -- skip over comment and delta pseudo instrs
92 countLIs rsLive (Instr instr Nothing : lis)
100 = pprPanic "RegSpillCost.slurpSpillCostInfo"
101 (text "no liveness information on instruction " <> ppr instr)
103 countLIs rsLiveEntry (Instr instr (Just live) : lis)
105 -- increment the lifetime counts for regs live on entry to this instr
106 mapM_ incLifetime $ uniqSetToList rsLiveEntry
108 -- increment counts for what regs were read/written from
109 let (RU read written) = regUsage instr
110 mapM_ incUses $ filter (not . isRealReg) $ nub read
111 mapM_ incDefs $ filter (not . isRealReg) $ nub written
113 -- compute liveness for entry to next instruction.
115 = rsLiveEntry `minusUniqSet` (liveDieRead live)
118 = (rsLiveAcross `unionUniqSets` (liveBorn live))
119 `minusUniqSet` (liveDieWrite live)
121 countLIs rsLiveNext lis
123 incDefs reg = modify $ \s -> addToUFM_C plusSpillCostRecord s reg (reg, 1, 0, 0)
124 incUses reg = modify $ \s -> addToUFM_C plusSpillCostRecord s reg (reg, 0, 1, 0)
125 incLifetime reg = modify $ \s -> addToUFM_C plusSpillCostRecord s reg (reg, 0, 0, 1)
128 -- | Choose a node to spill from this graph
132 -> Graph Reg RegClass Reg
135 chooseSpill info graph
136 = let cost = spillCost_length info graph
137 node = minimumBy (\n1 n2 -> compare (cost $ nodeId n1) (cost $ nodeId n2))
138 $ eltsUFM $ graphMap graph
144 -- | Chaitins spill cost function is:
146 -- cost = sum loadCost * freq (u) + sum storeCost * freq (d)
147 -- u <- uses (v) d <- defs (v)
149 -- There are no loops in our code at the momemnt, so we can set the freq's to 1
150 -- We divide this by the degree if t
153 -- If we don't have live range splitting then Chaitins function performs badly if we have
154 -- lots of nested live ranges and very few registers.
167 -- defs uses degree cost
172 -- v3 has the lowest cost, but if we only have 2 hardregs and we insert spill code for v3
173 -- then this isn't going to improve the colorability of the graph.
175 -- When compiling SHA1, which as very long basic blocks and some vregs with very long live ranges
176 -- the allocator seems to try and spill from the inside out and eventually run out of stack slots.
178 -- Without live range splitting, its's better to spill from the outside in so set the cost of very
179 -- long live ranges to zero
184 -> Graph Reg RegClass Reg
188 spillCost_chaitin info graph reg
189 -- Spilling a live range that only lives for 1 instruction isn't going to help
190 -- us at all - and we definately want to avoid trying to re-spill previously
191 -- inserted spill code.
192 | lifetime <= 1 = 1/0
194 -- It's unlikely that we'll find a reg for a live range this long
195 -- better to spill it straight up and not risk trying to keep it around
196 -- and have to go through the build/color cycle again.
197 | lifetime > allocatableRegsInClass (regClass reg) * 10
200 -- otherwise revert to chaitin's regular cost function.
201 | otherwise = fromIntegral (uses + defs) / fromIntegral (nodeDegree graph reg)
202 where (_, defs, uses, lifetime)
203 = fromMaybe (reg, 0, 0, 0) $ lookupUFM info reg
206 -- Just spill the longest live range.
209 -> Graph Reg RegClass Reg
213 spillCost_length info _ reg
214 | lifetime <= 1 = 1/0
215 | otherwise = 1 / fromIntegral lifetime
216 where (_, _, _, lifetime)
217 = fromMaybe (reg, 0, 0, 0) $ lookupUFM info reg
221 lifeMapFromSpillCostInfo :: SpillCostInfo -> UniqFM (Reg, Int)
222 lifeMapFromSpillCostInfo info
224 $ map (\(r, _, _, life) -> (r, (r, life)))
228 -- | Work out the degree (number of neighbors) of this node which have the same class.
229 nodeDegree :: Graph Reg RegClass Reg -> Reg -> Int
231 | Just node <- lookupUFM (graphMap graph) reg
232 , virtConflicts <- length $ filter (\r -> regClass r == regClass reg)
233 $ uniqSetToList $ nodeConflicts node
234 = virtConflicts + sizeUniqSet (nodeExclusions node)
240 -- | Show a spill cost record, including the degree from the graph and final calulated spill cos
241 pprSpillCostRecord :: Graph Reg RegClass Reg -> SpillCostRecord -> SDoc
242 pprSpillCostRecord graph (reg, uses, defs, life)
248 , ppr $ nodeDegree graph reg
249 , text $ show $ (fromIntegral (uses + defs) / fromIntegral (nodeDegree graph reg) :: Float) ]