JoinToTargets.hs 14.5 KB
Newer Older
1 2 3

-- | Handles joining of a jump instruction to its targets.

4 5 6
--      The first time we encounter a jump to a particular basic block, we
--      record the assignment of temporaries.  The next time we encounter a
--      jump to the same block, we compare our current assignment to the
Gabor Greif's avatar
Typos  
Gabor Greif committed
7
--      stored one.  They might be different if spilling has occurred in one
8
--      branch; so some fixup code will be required to match up the assignments.
9
--
10
module RegAlloc.Linear.JoinToTargets (joinToTargets) where
11 12 13 14

import RegAlloc.Linear.State
import RegAlloc.Linear.Base
import RegAlloc.Linear.FreeRegs
15
import RegAlloc.Liveness
16 17
import Instruction
import Reg
18 19 20

import BlockId
import Digraph
21
import DynFlags
22 23 24 25 26 27 28
import Outputable
import Unique
import UniqFM
import UniqSet


-- | For a jump instruction at the end of a block, generate fixup code so its
29
--      vregs are in the correct regs for its destination.
30 31
--
joinToTargets
32
        :: (FR freeRegs, Instruction instr)
33
        => BlockMap RegSet              -- ^ maps the unique of the blockid to the set of vregs
34
                                        --      that are known to be live on the entry to each block.
35

36 37
        -> BlockId                      -- ^ id of the current block
        -> instr                        -- ^ branch instr on the end of the source block.
38

39 40 41 42 43
        -> RegM freeRegs ([NatBasicBlock instr] -- fresh blocks of fixup code.
                         , instr)               -- the original branch
                                                -- instruction, but maybe
                                                -- patched to jump
                                                -- to a fixup block first.
44

45
joinToTargets block_live id instr
46

47 48 49
        -- we only need to worry about jump instructions.
        | not $ isJumpishInstr instr
        = return ([], instr)
50

51
        | otherwise
52
        = joinToTargets' block_live [] id instr (jumpDestsOfInstr instr)
53 54 55

-----
joinToTargets'
56
        :: (FR freeRegs, Instruction instr)
57
        => BlockMap RegSet              -- ^ maps the unique of the blockid to the set of vregs
58
                                        --      that are known to be live on the entry to each block.
59

60
        -> [NatBasicBlock instr]        -- ^ acc blocks of fixup code.
61

62 63
        -> BlockId                      -- ^ id of the current block
        -> instr                        -- ^ branch instr on the end of the source block.
64

65
        -> [BlockId]                    -- ^ branch destinations still to consider.
66

67
        -> RegM freeRegs ([NatBasicBlock instr], instr)
68 69

-- no more targets to consider. all done.
70
joinToTargets' _          new_blocks _ instr []
71
        = return (new_blocks, instr)
72 73

-- handle a branch target.
74
joinToTargets' block_live new_blocks block_id instr (dest:dests)
75 76 77 78 79 80 81 82 83 84 85 86 87 88 89
 = do
        -- get the map of where the vregs are stored on entry to each basic block.
        block_assig     <- getBlockAssigR

        -- get the assignment on entry to the branch instruction.
        assig           <- getAssigR

        -- adjust the current assignment to remove any vregs that are not live
        -- on entry to the destination block.
        let Just live_set       = mapLookup dest block_live
        let still_live uniq _   = uniq `elemUniqSet_Directly` live_set
        let adjusted_assig      = filterUFM_Directly still_live assig

        -- and free up those registers which are now free.
        let to_free =
niteria's avatar
niteria committed
90 91 92 93
                [ r     | (reg, loc) <- nonDetUFMToList assig
                        -- This is non-deterministic but we do not
                        -- currently support deterministic code-generation.
                        -- See Note [Unique Determinism and code generation]
94 95 96 97 98 99
                        , not (elemUniqSet_Directly reg live_set)
                        , r          <- regsOfLoc loc ]

        case mapLookup dest block_assig of
         Nothing
          -> joinToTargets_first
100
                        block_live new_blocks block_id instr dest dests
101 102 103 104
                        block_assig adjusted_assig to_free

         Just (_, dest_assig)
          -> joinToTargets_again
105
                        block_live new_blocks block_id instr dest dests
106
                        adjusted_assig dest_assig
107 108 109


-- this is the first time we jumped to this block.
110
joinToTargets_first :: (FR freeRegs, Instruction instr)
111
                    => BlockMap RegSet
112 113 114 115 116 117 118 119 120
                    -> [NatBasicBlock instr]
                    -> BlockId
                    -> instr
                    -> BlockId
                    -> [BlockId]
                    -> BlockAssignment freeRegs
                    -> RegMap Loc
                    -> [RealReg]
                    -> RegM freeRegs ([NatBasicBlock instr], instr)
121
joinToTargets_first block_live new_blocks block_id instr dest dests
122 123 124
        block_assig src_assig
        to_free

125 126 127 128
 = do   dflags <- getDynFlags
        let platform = targetPlatform dflags

        -- free up the regs that are not live on entry to this block.
129 130
        freeregs        <- getFreeRegsR
        let freeregs' = foldr (frReleaseReg platform) freeregs to_free
131

132 133
        -- remember the current assignment on entry to this block.
        setBlockAssigR (mapInsert dest (freeregs', src_assig) block_assig)
134

135
        joinToTargets' block_live new_blocks block_id instr dests
136 137 138


-- we've jumped to this block before
139
joinToTargets_again :: (Instruction instr, FR freeRegs)
140
                    => BlockMap RegSet
141 142 143 144 145 146 147 148
                    -> [NatBasicBlock instr]
                    -> BlockId
                    -> instr
                    -> BlockId
                    -> [BlockId]
                    -> UniqFM Loc
                    -> UniqFM Loc
                    -> RegM freeRegs ([NatBasicBlock instr], instr)
149
joinToTargets_again
150
    block_live new_blocks block_id instr dest dests
151
    src_assig dest_assig
152

153
        -- the assignments already match, no problem.
niteria's avatar
niteria committed
154 155 156 157
        | nonDetUFMToList dest_assig == nonDetUFMToList src_assig
        -- This is non-deterministic but we do not
        -- currently support deterministic code-generation.
        -- See Note [Unique Determinism and code generation]
158
        = joinToTargets' block_live new_blocks block_id instr dests
159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177

        -- assignments don't match, need fixup code
        | otherwise
        = do

                -- make a graph of what things need to be moved where.
                let graph = makeRegMovementGraph src_assig dest_assig

                -- look for cycles in the graph. This can happen if regs need to be swapped.
                -- Note that we depend on the fact that this function does a
                --      bottom up traversal of the tree-like portions of the graph.
                --
                --  eg, if we have
                --      R1 -> R2 -> R3
                --
                --  ie move value in R1 to R2 and value in R2 to R3.
                --
                -- We need to do the R2 -> R3 move before R1 -> R2.
                --
niteria's avatar
niteria committed
178
                let sccs  = stronglyConnCompFromEdgedVerticesOrdR graph
179 180 181 182 183 184 185 186 187 188 189 190

{-              -- debugging
                pprTrace
                        ("joinToTargets: making fixup code")
                        (vcat   [ text "        in block: "     <> ppr block_id
                                , text " jmp instruction: "     <> ppr instr
                                , text "  src assignment: "     <> ppr src_assig
                                , text " dest assignment: "     <> ppr dest_assig
                                , text "  movement graph: "     <> ppr graph
                                , text "   sccs of graph: "     <> ppr sccs
                                , text ""])
                        (return ())
191
-}
192
                delta           <- getDeltaR
193
                fixUpInstrs_    <- mapM (handleComponent delta instr) sccs
194 195 196 197 198 199 200 201 202 203 204 205 206 207
                let fixUpInstrs = concat fixUpInstrs_

                -- make a new basic block containing the fixup code.
                --      A the end of the current block we will jump to the fixup one,
                --      then that will jump to our original destination.
                fixup_block_id <- getUniqueR
                let block = BasicBlock (mkBlockId fixup_block_id)
                                $ fixUpInstrs ++ mkJumpInstr dest

{-              pprTrace
                        ("joinToTargets: fixup code is:")
                        (vcat   [ ppr block
                                , text ""])
                        (return ())
208
-}
209 210
                -- if we didn't need any fixups, then don't include the block
                case fixUpInstrs of
211
                 []     -> joinToTargets' block_live new_blocks block_id instr dests
212

213 214 215 216 217 218 219
                 -- patch the original branch instruction so it goes to our
                 --     fixup block instead.
                 _      -> let  instr'  =  patchJumpInstr instr
                                                (\bid -> if bid == dest
                                                                then mkBlockId fixup_block_id
                                                                else bid) -- no change!

220
                           in   joinToTargets' block_live (block : new_blocks) block_id instr' dests
221 222 223 224


-- | Construct a graph of register\/spill movements.
--
225
--      Cyclic components seem to occur only very rarely.
226
--
227 228
--      We cut some corners by not handling memory-to-memory moves.
--      This shouldn't happen because every temporary gets its own stack slot.
229 230 231
--
makeRegMovementGraph :: RegMap Loc -> RegMap Loc -> [(Unique, Loc, [Loc])]
makeRegMovementGraph adjusted_assig dest_assig
niteria's avatar
niteria committed
232 233 234 235
 = [ node       | (vreg, src) <- nonDetUFMToList adjusted_assig
                    -- This is non-deterministic but we do not
                    -- currently support deterministic code-generation.
                    -- See Note [Unique Determinism and code generation]
236 237 238
                    -- source reg might not be needed at the dest:
                , Just loc <- [lookupUFM_Directly dest_assig vreg]
                , node <- expandNode vreg src loc ]
239 240 241


-- | Expand out the destination, so InBoth destinations turn into
242
--      a combination of InReg and InMem.
243

244 245 246 247
--      The InBoth handling is a little tricky here.  If the destination is
--      InBoth, then we must ensure that the value ends up in both locations.
--      An InBoth  destination must conflict with an InReg or InMem source, so
--      we expand an InBoth destination as necessary.
248
--
249 250
--      An InBoth source is slightly different: we only care about the register
--      that the source value is in, so that we can move it to the destinations.
251
--
252 253 254 255 256
expandNode
        :: a
        -> Loc                  -- ^ source of move
        -> Loc                  -- ^ destination of move
        -> [(a, Loc, [Loc])]
257 258

expandNode vreg loc@(InReg src) (InBoth dst mem)
259 260
        | src == dst = [(vreg, loc, [InMem mem])]
        | otherwise  = [(vreg, loc, [InReg dst, InMem mem])]
261 262

expandNode vreg loc@(InMem src) (InBoth dst mem)
263 264
        | src == mem = [(vreg, loc, [InReg dst])]
        | otherwise  = [(vreg, loc, [InReg dst, InMem mem])]
265 266

expandNode _        (InBoth _ src) (InMem dst)
267
        | src == dst = [] -- guaranteed to be true
268 269

expandNode _        (InBoth src _) (InReg dst)
270
        | src == dst = []
271 272

expandNode vreg     (InBoth src _) dst
273
        = expandNode vreg (InReg src) dst
274 275

expandNode vreg src dst
276 277
        | src == dst = []
        | otherwise  = [(vreg, src, [dst])]
278 279 280


-- | Generate fixup code for a particular component in the move graph
281 282 283
--      This component tells us what values need to be moved to what
--      destinations. We have eliminated any possibility of single-node
--      cycles in expandNode above.
284
--
285 286
handleComponent
        :: Instruction instr
287
        => Int -> instr -> SCC (Unique, Loc, [Loc])
288
        -> RegM freeRegs [instr]
289 290

-- If the graph is acyclic then we won't get the swapping problem below.
291 292
--      In this case we can just do the moves directly, and avoid having to
--      go via a spill slot.
293
--
294 295
handleComponent delta _  (AcyclicSCC (vreg, src, dsts))
        = mapM (makeMove delta vreg src) dsts
296 297 298


-- Handle some cyclic moves.
299 300 301 302 303 304 305 306
--      This can happen if we have two regs that need to be swapped.
--      eg:
--           vreg   source loc   dest loc
--          (vreg1, InReg r1,    [InReg r2])
--          (vreg2, InReg r2,    [InReg r1])
--
--      To avoid needing temp register, we just spill all the source regs, then
--      reaload them into their destination regs.
307
--
308 309 310 311
--      Note that we can not have cycles that involve memory locations as
--      sources as single destination because memory locations (stack slots)
--      are allocated exclusively for a virtual register and therefore can not
--      require a fixup.
312
--
313
handleComponent delta instr
314
        (CyclicSCC ((vreg, InReg sreg, (InReg dreg: _)) : rest))
315
        -- dest list may have more than one element, if the reg is also InMem.
316
 = do
317 318 319 320 321 322
        -- spill the source into its slot
        (instrSpill, slot)
                        <- spillR (RegReal sreg) vreg

        -- reload into destination reg
        instrLoad       <- loadR (RegReal dreg) slot
323

324
        remainingFixUps <- mapM (handleComponent delta instr)
niteria's avatar
niteria committed
325
                                (stronglyConnCompFromEdgedVerticesOrdR rest)
326

327 328 329
        -- make sure to do all the reloads after all the spills,
        --      so we don't end up clobbering the source values.
        return ([instrSpill] ++ concat remainingFixUps ++ [instrLoad])
330

331
handleComponent _ _ (CyclicSCC _)
332 333 334 335 336
 = panic "Register Allocator: handleComponent cyclic"


-- | Move a vreg between these two locations.
--
337 338
makeMove
    :: Instruction instr
339
    => Int      -- ^ current C stack delta.
340 341 342 343 344
    -> Unique   -- ^ unique of the vreg that we're moving.
    -> Loc      -- ^ source location.
    -> Loc      -- ^ destination location.
    -> RegM freeRegs instr  -- ^ move instruction.

345 346 347 348 349 350 351 352 353 354
makeMove delta vreg src dst
 = do dflags <- getDynFlags
      let platform = targetPlatform dflags

      case (src, dst) of
          (InReg s, InReg d) ->
              do recordSpill (SpillJoinRR vreg)
                 return $ mkRegRegMoveInstr platform (RegReal s) (RegReal d)
          (InMem s, InReg d) ->
              do recordSpill (SpillJoinRM vreg)
355
                 return $ mkLoadInstr dflags (RegReal d) delta s
356 357
          (InReg s, InMem d) ->
              do recordSpill (SpillJoinRM vreg)
358
                 return $ mkSpillInstr dflags (RegReal s) delta d
359 360 361 362 363 364 365
          _ ->
              -- we don't handle memory to memory moves.
              -- they shouldn't happen because we don't share
              -- stack slots between vregs.
              panic ("makeMove " ++ show vreg ++ " (" ++ show src ++ ") ("
                  ++ show dst ++ ")"
                  ++ " we don't handle mem->mem moves.")
366