compiler/nativeGen/RegLiveness.hs

   1 -----------------------------------------------------------------------------
   2 --
   3 -- The register liveness determinator
   4 --
   5 -- (c) The University of Glasgow 2004
   6 --
   7 -----------------------------------------------------------------------------
   8
   9 {-# OPTIONS_GHC -w #-}
  10 -- The above warning supression flag is a temporary kludge.
  11 -- While working on this module you are encouraged to remove it and fix
  12 -- any warnings in the module. See
  13 --     http://hackage.haskell.org/trac/ghc/wiki/WorkingConventions#Warnings
  14 -- for details
  15
  16 module RegLiveness (
  17         RegSet,
  18         RegMap, emptyRegMap,
  19         BlockMap, emptyBlockMap,
  20         LiveCmmTop,
  21         LiveInstr (..),
  22         Liveness (..),
  23         LiveInfo (..),
  24         LiveBasicBlock,
  25
  26         mapBlockTop,    mapBlockTopM,
  27         mapGenBlockTop, mapGenBlockTopM,
  28         stripLive,
  29         spillNatBlock,
  30         slurpConflicts,
  31         lifetimeCount,
  32         eraseDeltasLive,
  33         patchEraseLive,
  34         patchRegsLiveInstr,
  35         regLiveness
  36
  37   ) where
  38
  39 #include "HsVersions.h"
  40
  41 import MachRegs
  42 import MachInstrs
  43 import PprMach
  44 import RegAllocInfo
  45 import Cmm
  46
  47 import Digraph
  48 import Outputable
  49 import Unique
  50 import UniqSet
  51 import UniqFM
  52 import UniqSupply
  53 import Bag
  54 import State
  55
  56 import Data.List
  57 import Data.Maybe
  58
  59 -----------------------------------------------------------------------------
  60 type RegSet = UniqSet Reg
  61
  62 type RegMap a = UniqFM a
  63 emptyRegMap = emptyUFM
  64
  65 type BlockMap a = UniqFM a
  66 emptyBlockMap = emptyUFM
  67
  68
  69 -- | A top level thing which carries liveness information.
  70 type LiveCmmTop
  71         = GenCmmTop
  72                 CmmStatic
  73                 LiveInfo
  74                 (GenBasicBlock LiveInstr)
  75                         -- the "instructions" here are actually more blocks,
  76                         --      single blocks are acyclic
  77                         --      multiple blocks are taken to be cyclic.
  78
  79 -- | An instruction with liveness information.
  80 data LiveInstr
  81         = Instr Instr (Maybe Liveness)
  82
  83 -- | Liveness information.
  84 --      The regs which die are ones which are no longer live in the *next* instruction
  85 --      in this sequence.
  86 --      (NB. if the instruction is a jump, these registers might still be live
  87 --      at the jump target(s) - you have to check the liveness at the destination
  88 --      block to find out).
  89
  90 data Liveness
  91         = Liveness
  92         { liveBorn      :: RegSet       -- ^ registers born in this instruction (written to for first time).
  93         , liveDieRead   :: RegSet       -- ^ registers that died because they were read for the last time.
  94         , liveDieWrite  :: RegSet }     -- ^ registers that died because they were clobbered by something.
  95
  96
  97 -- | Stash regs live on entry to each basic block in the info part of the cmm code.
  98 data LiveInfo
  99         = LiveInfo
 100                 [CmmStatic]             -- cmm static stuff
 101                 (Maybe BlockId)         -- id of the first block
 102                 (BlockMap RegSet)       -- argument locals live on entry to this block
 103
 104 -- | A basic block with liveness information.
 105 type LiveBasicBlock
 106         = GenBasicBlock LiveInstr
 107
 108
 109 instance Outputable LiveInstr where
 110         ppr (Instr instr Nothing)
 111          = ppr instr
 112
 113         ppr (Instr instr (Just live))
 114          =  ppr instr
 115                 $$ (nest 8
 116                         $ vcat
 117                         [ pprRegs (ptext SLIT("# born:    ")) (liveBorn live)
 118                         , pprRegs (ptext SLIT("# r_dying: ")) (liveDieRead live)
 119                         , pprRegs (ptext SLIT("# w_dying: ")) (liveDieWrite live) ]
 120                     $+$ space)
 121
 122          where  pprRegs :: SDoc -> RegSet -> SDoc
 123                 pprRegs name regs
 124                  | isEmptyUniqSet regs  = empty
 125                  | otherwise            = name <> (hcat $ punctuate space $ map (docToSDoc . pprUserReg) $ uniqSetToList regs)
 126
 127
 128 instance Outputable LiveInfo where
 129         ppr (LiveInfo static firstId liveOnEntry)
 130                 =  (vcat $ map ppr static)
 131                 $$ text "# firstId     = " <> ppr firstId
 132                 $$ text "# liveOnEntry = " <> ppr liveOnEntry
 133
 134
 135 -- | map a function across all the basic blocks in this code
 136 --
 137 mapBlockTop
 138         :: (LiveBasicBlock -> LiveBasicBlock)
 139         -> LiveCmmTop -> LiveCmmTop
 140
 141 mapBlockTop f cmm
 142         = evalState (mapBlockTopM (\x -> return $ f x) cmm) ()
 143
 144
 145 -- | map a function across all the basic blocks in this code (monadic version)
 146 --
 147 mapBlockTopM
 148         :: Monad m
 149         => (LiveBasicBlock -> m LiveBasicBlock)
 150         -> LiveCmmTop -> m LiveCmmTop
 151
 152 mapBlockTopM f cmm@(CmmData{})
 153         = return cmm
 154
 155 mapBlockTopM f (CmmProc header label params comps)
 156  = do   comps'  <- mapM (mapBlockCompM f) comps
 157         return  $ CmmProc header label params comps'
 158
 159 mapBlockCompM f (BasicBlock i blocks)
 160  = do   blocks' <- mapM f blocks
 161         return  $ BasicBlock i blocks'
 162
 163
 164 -- map a function across all the basic blocks in this code
 165 mapGenBlockTop
 166         :: (GenBasicBlock i -> GenBasicBlock i)
 167         -> (GenCmmTop d h i -> GenCmmTop d h i)
 168
 169 mapGenBlockTop f cmm
 170         = evalState (mapGenBlockTopM (\x -> return $ f x) cmm) ()
 171
 172
 173 -- | map a function across all the basic blocks in this code (monadic version)
 174 mapGenBlockTopM
 175         :: Monad m
 176         => (GenBasicBlock i -> m (GenBasicBlock i))
 177         -> (GenCmmTop d h i -> m (GenCmmTop d h i))
 178
 179 mapGenBlockTopM f cmm@(CmmData{})
 180         = return cmm
 181
 182 mapGenBlockTopM f (CmmProc header label params blocks)
 183  = do   blocks' <- mapM f blocks
 184         return  $ CmmProc header label params blocks'
 185
 186
 187 -- | Slurp out the list of register conflicts from this top level thing.
 188
 189 slurpConflicts :: LiveCmmTop -> Bag (UniqSet Reg)
 190 slurpConflicts live
 191         = slurpCmm emptyBag live
 192
 193  where  slurpCmm   rs  CmmData{}                = rs
 194         slurpCmm   rs (CmmProc info _ _ blocks)
 195                 = foldl' (slurpComp info) rs blocks
 196
 197         slurpComp  info rs (BasicBlock i blocks)
 198                 = foldl' (slurpBlock info) rs blocks
 199
 200         slurpBlock info rs (BasicBlock blockId instrs)
 201                 | LiveInfo _ _ blockLive        <- info
 202                 , Just rsLiveEntry              <- lookupUFM blockLive blockId
 203                 = consBag rsLiveEntry $ slurpLIs rsLiveEntry rs instrs
 204
 205         slurpLIs rsLive rs []                           = consBag rsLive rs
 206         slurpLIs rsLive rs (Instr _ Nothing     : lis)  = slurpLIs rsLive rs lis
 207
 208         slurpLIs rsLiveEntry rs (li@(Instr _ (Just live)) : lis)
 209          = let
 210                 -- regs that die because they are read for the last time at the start of an instruction
 211                 --      are not live across it.
 212                 rsLiveAcross    = rsLiveEntry `minusUniqSet` (liveDieRead live)
 213
 214                 -- regs live on entry to the next instruction.
 215                 --      be careful of orphans, make sure to delete dying regs _after_ unioning
 216                 --      in the ones that are born here.
 217                 rsLiveNext      = (rsLiveAcross `unionUniqSets` (liveBorn     live))
 218                                                 `minusUniqSet`  (liveDieWrite live)
 219
 220                 -- orphan vregs are the ones that die in the same instruction they are born in.
 221                 --      these are likely to be results that are never used, but we still
 222                 --      need to assign a hreg to them..
 223                 rsOrphans       = intersectUniqSets
 224                                         (liveBorn live)
 225                                         (unionUniqSets (liveDieWrite live) (liveDieRead live))
 226
 227                 --
 228                 rsConflicts     = unionUniqSets rsLiveNext rsOrphans
 229
 230           in    slurpLIs rsLiveNext (consBag rsConflicts rs) lis
 231
 232
 233 -- | Strip away liveness information, yielding NatCmmTop
 234
 235 stripLive :: LiveCmmTop -> NatCmmTop
 236 stripLive live
 237         = stripCmm live
 238
 239  where  stripCmm (CmmData sec ds)       = CmmData sec ds
 240         stripCmm (CmmProc (LiveInfo info _ _) label params comps)
 241                 = CmmProc info label params (concatMap stripComp comps)
 242
 243         stripComp  (BasicBlock i blocks)        = map stripBlock blocks
 244         stripBlock (BasicBlock i instrs)        = BasicBlock i (map stripLI instrs)
 245         stripLI    (Instr instr _)              = instr
 246
 247
 248 -- | Make real spill instructions out of SPILL, RELOAD pseudos
 249
 250 spillNatBlock :: NatBasicBlock -> NatBasicBlock
 251 spillNatBlock (BasicBlock i instrs)
 252  =      BasicBlock i instrs'
 253  where  (instrs', _)
 254                 = runState (spillNat [] instrs) 0
 255
 256         spillNat acc []
 257          =      return (reverse acc)
 258
 259         spillNat acc (instr@(DELTA i) : instrs)
 260          = do   put i
 261                 spillNat acc instrs
 262
 263         spillNat acc (SPILL reg slot : instrs)
 264          = do   delta   <- get
 265                 spillNat (mkSpillInstr reg delta slot : acc) instrs
 266
 267         spillNat acc (RELOAD slot reg : instrs)
 268          = do   delta   <- get
 269                 spillNat (mkLoadInstr reg delta slot : acc) instrs
 270
 271         spillNat acc (instr : instrs)
 272          =      spillNat (instr : acc) instrs
 273
 274
 275 -- | Slurp out a map of how many times each register was live upon entry to an instruction.
 276
 277 lifetimeCount
 278         :: LiveCmmTop
 279         -> UniqFM (Reg, Int)    -- ^ reg -> (reg, count)
 280
 281 lifetimeCount cmm
 282         = countCmm emptyUFM cmm
 283  where
 284         countCmm fm  CmmData{}          = fm
 285         countCmm fm (CmmProc info _ _ blocks)
 286                 = foldl' (countComp info) fm blocks
 287
 288         countComp info fm (BasicBlock i blocks)
 289                 = foldl' (countBlock info) fm blocks
 290
 291         countBlock info fm (BasicBlock blockId instrs)
 292                 | LiveInfo _ _ blockLive        <- info
 293                 , Just rsLiveEntry              <- lookupUFM blockLive blockId
 294                 = countLIs rsLiveEntry fm instrs
 295
 296         countLIs rsLive fm []                           = fm
 297         countLIs rsLive fm (Instr _ Nothing : lis)      = countLIs rsLive fm lis
 298
 299         countLIs rsLiveEntry fm (Instr _ (Just live) : lis)
 300          = let
 301                 rsLiveAcross    = rsLiveEntry `minusUniqSet` (liveDieRead live)
 302
 303                 rsLiveNext      = (rsLiveAcross `unionUniqSets` (liveBorn     live))
 304                                                  `minusUniqSet` (liveDieWrite live)
 305
 306                 add r fm        = addToUFM_C
 307                                         (\(r1, l1) (_, l2) -> (r1, l1 + l2))
 308                                         fm r (r, 1)
 309
 310                 fm'             = foldUniqSet add fm rsLiveEntry
 311            in   countLIs rsLiveNext fm' lis
 312
 313
 314 -- | Erase Delta instructions.
 315
 316 eraseDeltasLive :: LiveCmmTop -> LiveCmmTop
 317 eraseDeltasLive cmm
 318         = mapBlockTop eraseBlock cmm
 319  where
 320         isDelta (DELTA _)       = True
 321         isDelta _               = False
 322
 323         eraseBlock (BasicBlock id lis)
 324                 = BasicBlock id
 325                 $ filter (\(Instr i _) -> not $ isDelta i)
 326                 $ lis
 327
 328
 329 -- | Patch the registers in this code according to this register mapping.
 330 --      also erase reg -> reg moves when the reg is the same.
 331 --      also erase reg -> reg moves when the destination dies in this instr.
 332
 333 patchEraseLive
 334         :: (Reg -> Reg)
 335         -> LiveCmmTop -> LiveCmmTop
 336
 337 patchEraseLive patchF cmm
 338         = patchCmm cmm
 339  where
 340         patchCmm cmm@CmmData{}  = cmm
 341
 342         patchCmm cmm@(CmmProc info label params comps)
 343          | LiveInfo static id blockMap  <- info
 344          = let  patchRegSet set = mkUniqSet $ map patchF $ uniqSetToList set
 345                 blockMap'       = mapUFM patchRegSet blockMap
 346
 347                 info'           = LiveInfo static id blockMap'
 348            in   CmmProc info' label params $ map patchComp comps
 349
 350         patchComp (BasicBlock id blocks)
 351                 = BasicBlock id $ map patchBlock blocks
 352
 353         patchBlock (BasicBlock id lis)
 354                 = BasicBlock id $ patchInstrs lis
 355
 356         patchInstrs []          = []
 357         patchInstrs (li : lis)
 358
 359                 | Instr i (Just live)   <- li'
 360                 , Just (r1, r2) <- isRegRegMove i
 361                 , eatMe r1 r2 live
 362                 = patchInstrs lis
 363
 364                 | otherwise
 365                 = li' : patchInstrs lis
 366
 367                 where   li'     = patchRegsLiveInstr patchF li
 368
 369         eatMe   r1 r2 live
 370                 -- source and destination regs are the same
 371                 | r1 == r2      = True
 372
 373                 -- desination reg is never used
 374                 | elementOfUniqSet r2 (liveBorn live)
 375                 , elementOfUniqSet r2 (liveDieRead live) || elementOfUniqSet r2 (liveDieWrite live)
 376                 = True
 377
 378                 | otherwise     = False
 379
 380
 381 -- | Patch registers in this LiveInstr, including the liveness information.
 382 --
 383 patchRegsLiveInstr
 384         :: (Reg -> Reg)
 385         -> LiveInstr -> LiveInstr
 386
 387 patchRegsLiveInstr patchF li
 388  = case li of
 389         Instr instr Nothing
 390          -> Instr (patchRegs instr patchF) Nothing
 391
 392         Instr instr (Just live)
 393          -> Instr
 394                 (patchRegs instr patchF)
 395                 (Just live
 396                         { -- WARNING: have to go via lists here because patchF changes the uniq in the Reg
 397                           liveBorn      = mkUniqSet $ map patchF $ uniqSetToList $ liveBorn live
 398                         , liveDieRead   = mkUniqSet $ map patchF $ uniqSetToList $ liveDieRead live
 399                         , liveDieWrite  = mkUniqSet $ map patchF $ uniqSetToList $ liveDieWrite live })
 400
 401
 402 ---------------------------------------------------------------------------------
 403 -- Annotate code with register liveness information
 404 --
 405 regLiveness
 406         :: NatCmmTop
 407         -> UniqSM LiveCmmTop
 408
 409 regLiveness cmm@(CmmData sec d)
 410         = returnUs $ CmmData sec d
 411
 412 regLiveness cmm@(CmmProc info lbl params [])
 413         = returnUs $ CmmProc
 414                         (LiveInfo info Nothing emptyUFM)
 415                         lbl params []
 416
 417 regLiveness cmm@(CmmProc info lbl params blocks@(first:rest))
 418  = let  first_id                = blockId first
 419         sccs                    = sccBlocks blocks
 420         (ann_sccs, block_live)  = computeLiveness sccs
 421
 422         liveBlocks
 423          = map (\scc -> case scc of
 424                         AcyclicSCC  b@(BasicBlock l _)          -> BasicBlock l [b]
 425                         CyclicSCC  bs@(BasicBlock l _ : _)      -> BasicBlock l bs
 426                         CyclicSCC  []
 427                          -> panic "RegLiveness.regLiveness: no blocks in scc list")
 428                  $ ann_sccs
 429
 430    in   returnUs $ CmmProc
 431                         (LiveInfo info (Just first_id) block_live)
 432                         lbl params liveBlocks
 433
 434
 435 sccBlocks :: [NatBasicBlock] -> [SCC NatBasicBlock]
 436 sccBlocks blocks = stronglyConnComp graph
 437   where
 438         getOutEdges :: [Instr] -> [BlockId]
 439         getOutEdges instrs = foldl' (\a x -> jumpDests x a) [] instrs
 440
 441         graph = [ (block, getUnique id, map getUnique (getOutEdges instrs))
 442                 | block@(BasicBlock id instrs) <- blocks ]
 443
 444
 445 -- -----------------------------------------------------------------------------
 446 -- Computing liveness
 447
 448 computeLiveness
 449    :: [SCC NatBasicBlock]
 450    -> ([SCC LiveBasicBlock],            -- instructions annotated with list of registers
 451                                         -- which are "dead after this instruction".
 452        BlockMap RegSet)                 -- blocks annontated with set of live registers
 453                                         -- on entry to the block.
 454
 455   -- NOTE: on entry, the SCCs are in "reverse" order: later blocks may transfer
 456   -- control to earlier ones only.  The SCCs returned are in the *opposite*
 457   -- order, which is exactly what we want for the next pass.
 458
 459 computeLiveness sccs
 460         = livenessSCCs emptyBlockMap [] sccs
 461
 462
 463 livenessSCCs
 464        :: BlockMap RegSet
 465        -> [SCC LiveBasicBlock]          -- accum
 466        -> [SCC NatBasicBlock]
 467        -> ([SCC LiveBasicBlock], BlockMap RegSet)
 468
 469 livenessSCCs blockmap done [] = (done, blockmap)
 470
 471 livenessSCCs blockmap done (AcyclicSCC block : sccs)
 472  = let  (blockmap', block')     = livenessBlock blockmap block
 473    in   livenessSCCs blockmap' (AcyclicSCC block' : done) sccs
 474
 475 livenessSCCs blockmap done
 476         (CyclicSCC blocks : sccs) =
 477         livenessSCCs blockmap' (CyclicSCC blocks':done) sccs
 478  where      (blockmap', blocks')
 479                 = iterateUntilUnchanged linearLiveness equalBlockMaps
 480                                       blockmap blocks
 481
 482             iterateUntilUnchanged
 483                 :: (a -> b -> (a,c)) -> (a -> a -> Bool)
 484                 -> a -> b
 485                 -> (a,c)
 486
 487             iterateUntilUnchanged f eq a b
 488                 = head $
 489                   concatMap tail $
 490                   groupBy (\(a1, _) (a2, _) -> eq a1 a2) $
 491                   iterate (\(a, _) -> f a b) $
 492                   (a, error "RegisterAlloc.livenessSCCs")
 493
 494
 495             linearLiveness :: BlockMap RegSet -> [NatBasicBlock]
 496                            -> (BlockMap RegSet, [LiveBasicBlock])
 497             linearLiveness = mapAccumL livenessBlock
 498
 499                 -- probably the least efficient way to compare two
 500                 -- BlockMaps for equality.
 501             equalBlockMaps a b
 502                 = a' == b'
 503               where a' = map f $ ufmToList a
 504                     b' = map f $ ufmToList b
 505                     f (key,elt) = (key, uniqSetToList elt)
 506
 507
 508
 509 -- | Annotate a basic block with register liveness information.
 510 --
 511 livenessBlock
 512         :: BlockMap RegSet
 513         -> NatBasicBlock
 514         -> (BlockMap RegSet, LiveBasicBlock)
 515
 516 livenessBlock blockmap block@(BasicBlock block_id instrs)
 517  = let
 518         (regsLiveOnEntry, instrs1)
 519                 = livenessBack emptyUniqSet blockmap [] (reverse instrs)
 520         blockmap'       = addToUFM blockmap block_id regsLiveOnEntry
 521
 522         instrs2         = livenessForward regsLiveOnEntry instrs1
 523
 524         output          = BasicBlock block_id instrs2
 525
 526    in   ( blockmap', output)
 527
 528 -- | Calculate liveness going forwards,
 529 --      filling in when regs are born
 530
 531 livenessForward
 532         :: RegSet                       -- regs live on this instr
 533         -> [LiveInstr] -> [LiveInstr]
 534
 535 livenessForward rsLiveEntry []  = []
 536 livenessForward rsLiveEntry (li@(Instr instr mLive) : lis)
 537         | Nothing               <- mLive
 538         = li : livenessForward rsLiveEntry lis
 539
 540         | Just live             <- mLive
 541         , RU read written       <- regUsage instr
 542         = let
 543                 -- Regs that are written to but weren't live on entry to this instruction
 544                 --      are recorded as being born here.
 545                 rsBorn          = mkUniqSet
 546                                 $ filter (\r -> not $ elementOfUniqSet r rsLiveEntry) written
 547
 548                 rsLiveNext      = (rsLiveEntry `unionUniqSets` rsBorn)
 549                                         `minusUniqSet` (liveDieRead live)
 550                                         `minusUniqSet` (liveDieWrite live)
 551
 552         in Instr instr (Just live { liveBorn = rsBorn })
 553                 : livenessForward rsLiveNext lis
 554
 555
 556 -- | Calculate liveness going backwards,
 557 --      filling in when regs die, and what regs are live across each instruction
 558
 559 livenessBack
 560         :: RegSet                       -- regs live on this instr
 561         -> BlockMap RegSet              -- regs live on entry to other BBs
 562         -> [LiveInstr]                  -- instructions (accum)
 563         -> [Instr]                      -- instructions
 564         -> (RegSet, [LiveInstr])
 565
 566 livenessBack liveregs blockmap done []  = (liveregs, done)
 567
 568 livenessBack liveregs blockmap acc (instr : instrs)
 569  = let  (liveregs', instr')     = liveness1 liveregs blockmap instr
 570    in   livenessBack liveregs' blockmap (instr' : acc) instrs
 571
 572 -- don't bother tagging comments or deltas with liveness
 573 liveness1 liveregs blockmap (instr@COMMENT{})
 574         = (liveregs, Instr instr Nothing)
 575
 576 liveness1 liveregs blockmap (instr@DELTA{})
 577         = (liveregs, Instr instr Nothing)
 578
 579 liveness1 liveregs blockmap instr
 580
 581       | not_a_branch
 582       = (liveregs1, Instr instr
 583                         (Just $ Liveness
 584                         { liveBorn      = emptyUniqSet
 585                         , liveDieRead   = mkUniqSet r_dying
 586                         , liveDieWrite  = mkUniqSet w_dying }))
 587
 588       | otherwise
 589       = (liveregs_br, Instr instr
 590                         (Just $ Liveness
 591                         { liveBorn      = emptyUniqSet
 592                         , liveDieRead   = mkUniqSet r_dying_br
 593                         , liveDieWrite  = mkUniqSet w_dying }))
 594
 595       where
 596             RU read written = regUsage instr
 597
 598             -- registers that were written here are dead going backwards.
 599             -- registers that were read here are live going backwards.
 600             liveregs1   = (liveregs `delListFromUniqSet` written)
 601                                     `addListToUniqSet` read
 602
 603             -- registers that are not live beyond this point, are recorded
 604             --  as dying here.
 605             r_dying     = [ reg | reg <- read, reg `notElem` written,
 606                               not (elementOfUniqSet reg liveregs) ]
 607
 608             w_dying     = [ reg | reg <- written,
 609                              not (elementOfUniqSet reg liveregs) ]
 610
 611             -- union in the live regs from all the jump destinations of this
 612             -- instruction.
 613             targets      = jumpDests instr [] -- where we go from here
 614             not_a_branch = null targets
 615
 616             targetLiveRegs target
 617                   = case lookupUFM blockmap target of
 618                                 Just ra -> ra
 619                                 Nothing -> emptyBlockMap
 620
 621             live_from_branch = unionManyUniqSets (map targetLiveRegs targets)
 622
 623             liveregs_br = liveregs1 `unionUniqSets` live_from_branch
 624
 625             -- registers that are live only in the branch targets should
 626             -- be listed as dying here.
 627             live_branch_only = live_from_branch `minusUniqSet` liveregs
 628             r_dying_br  = uniqSetToList (mkUniqSet r_dying `unionUniqSets`
 629                                         live_branch_only)
 630
 631
 632
 633