From b4fd46494dc922a8e1134c9396cada1f10e74e55 Mon Sep 17 00:00:00 2001 From: "Michael D. Adams" Date: Fri, 18 May 2007 18:00:04 +0000 Subject: [PATCH] Second working draft of a CPS algorithm for C--. This is a safety check-in, before I begin a cleanup. --- compiler/cmm/Cmm.hs | 2 + compiler/cmm/CmmCPS.hs | 360 ++++++++++++++++++++++++++++++++++++++++------ compiler/cmm/Dataflow.hs | 9 +- 3 files changed, 327 insertions(+), 44 deletions(-) diff --git a/compiler/cmm/Cmm.hs b/compiler/cmm/Cmm.hs index 00d93b0..5ad8ee7 100644 --- a/compiler/cmm/Cmm.hs +++ b/compiler/cmm/Cmm.hs @@ -275,6 +275,8 @@ newtype BlockId = BlockId Unique instance Uniquable BlockId where getUnique (BlockId u) = u +type BlockEnv a = UniqFM {- BlockId -} a + ----------------------------------------------------------------------------- -- Static Data ----------------------------------------------------------------------------- diff --git a/compiler/cmm/CmmCPS.hs b/compiler/cmm/CmmCPS.hs index e708ebb..88d2585 100644 --- a/compiler/cmm/CmmCPS.hs +++ b/compiler/cmm/CmmCPS.hs @@ -6,11 +6,13 @@ import Cmm import CmmLint import PprCmm -import Dataflow (cmmLivenessComment, cmmLiveness, CmmLive) +import Dataflow -- (fixedpoint, cmmLivenessComment, cmmLiveness, CmmLive) import MachOp import ForeignCall import CLabel +import SMRep +import Constants import DynFlags import ErrUtils @@ -71,47 +73,158 @@ mapMCmmTop f (Cmm xs) = liftM Cmm $ liftM concat $ mapM f xs -- and heap memory (not sure if that's usefull at all though, but it may -- be worth exploring the design space). +data BrokenBlock + = BrokenBlock + BlockId -- Like a CmmBasicBlock + BlockEntryInfo -- How this block can be entered + [CmmStmt] -- Like a CmmBasicBlock (but without + -- the last statement) + BlockExitInfo -- How the block can be left + +data BlockEntryInfo + = FunctionEntry -- Beginning of function + + | ContinuationEntry -- Return point of a call + CmmFormals {- return values -} + -- TODO | ProcPointEntry {- no return values, but some live might end up as params -} + + | ControlEntry -- A label in the input + +data BlockExitInfo + = ControlExit [BlockId] -- blocks branched to conditionally + BlockId -- next block (must be a ControlEntry) + + | ReturnExit [BlockId] -- blocks branched to conditionally + CmmActuals -- return values + + | TailCallExit [BlockId] -- blocks branched to conditionally + CmmExpr -- the function to call + CmmActuals -- arguments to call + + | CallExit [BlockId] -- blocks branched to conditionally + BlockId -- next block after call (must be a ContinuationEntry) + CmmCallTarget -- the function to call + CmmFormals -- results from call (redundant with ContinuationEntry) + CmmActuals -- arguments to call + (Maybe [GlobalReg]) -- registers that must be saved (TODO) + -- TODO: | ProcPointExit (needed?) + data CPSBlockInfo = ControlBlock -- Consider whether a proc-point might want arguments on stack | ContinuationBlock [(CmmReg,MachHint)] {- params -} + | EntryBlock -type ContinuationFormat = [Maybe LocalReg] -- TODO: consider params as part of format +--type StackFormat = [Maybe LocalReg] -- TODO: consider params as part of format +data StackFormat + = StackFormat + BlockId {- block that is the start of the continuation. may or may not be the current block -} + WordOff {- total frame size -} + [(CmmReg, WordOff)] {- local reg offsets from stack top -} -- A block can be a continuation of a call -- A block can be a continuation of another block (w/ or w/o joins) -- A block can be an entry to a function -type CmmParam = [(CmmReg,MachHint)] - +-------------------------------------------------------------------------------- -- For now just select the continuation orders in the order they are in the set with no gaps -selectContinuationFormat :: UniqFM {-BlockId-} CmmParam -> UniqFM {-BlockId-} CmmLive -> UniqFM {-BlockId-} ContinuationFormat -selectContinuationFormat param live = mapUFM (map Just . uniqSetToList) live - +-- TODO: select a format that keeps blocks that can jump to each other the same +-- Assumed that jumps, calls +selectStackFormat :: UniqFM {-BlockId-} CmmFormals -> UniqFM {-BlockId-} CmmLive -> UniqFM {-BlockId-} [(CPSBlockInfo, CmmBasicBlock)] -> UniqFM {-BlockId-} StackFormat +selectStackFormat = undefined +{- +selectStackFormat param live blocks = fixedpoint +listToUFM $ map live_to_format $ ufmToList live + where + live_to_format (unique, live) = (unique, format) where + format = foldl extend_format + (StackFormat (BlockId unique) retAddrSizeW []) + (uniqSetToList live) + extend_format :: StackFormat -> LocalReg -> StackFormat + extend_format (StackFormat block size offsets) reg = + StackFormat block (slot_size reg + size) ((CmmLocal reg, size) : offsets) +-} + +selectStackFormat2 :: UniqFM {-BlockId-} CmmLive -> [BrokenBlock] -> UniqFM {-BlockId-} StackFormat +selectStackFormat2 live blocks = fixedpoint dependants update (map brokenBlockId blocks) emptyUFM where + blocks_ufm = listToUFM $ map (\b -> (brokenBlockId b, b)) blocks + dependants ident = + case lookupWithDefaultUFM blocks_ufm (panic "TODO") ident of + (BrokenBlock _ _ _ (ControlExit exits next)) -> next:exits + (BrokenBlock _ _ _ (ReturnExit exits _)) -> exits + (BrokenBlock _ _ _ (TailCallExit exits _ _)) -> exits + (BrokenBlock _ _ _ (CallExit exits _ _ _ _ _)) -> exits + update ident cause formats = + let BrokenBlock _ entry _ _ = lookupWithDefaultUFM blocks_ufm (panic "unknown BlockId in selectStackFormat:live") ident in + case cause of + -- Propagate only to blocks entered by branches (not function entry blocks or continuation entry blocks) + Just cause_name -> + let cause_format = lookupWithDefaultUFM formats (panic "update signaled for block not in format") cause_name + in case entry of + ControlEntry -> Just $ addToUFM formats ident cause_format + FunctionEntry -> Nothing + ContinuationEntry _ -> Nothing + -- Do initial calculates for function blocks + Nothing -> + case entry of + ControlEntry -> Nothing + FunctionEntry -> Just $ addToUFM formats ident $ StackFormat ident 0 [] + ContinuationEntry _ -> Just $ addToUFM formats ident $ live_to_format ident $ lookupWithDefaultUFM live (panic "TODO") ident + live_to_format label live = + foldl extend_format + (StackFormat label retAddrSizeW []) + (uniqSetToList live) + extend_format :: StackFormat -> LocalReg -> StackFormat + extend_format (StackFormat block size offsets) reg = + StackFormat block (slot_size reg + size) ((CmmLocal reg, size) : offsets) + +slot_size reg = ((machRepByteWidth (localRegRep reg) - 1) `div` wORD_SIZE) + 1 + +transformReturn :: UniqFM {-BlockId-} CPSBlockInfo -> UniqFM {-BlockId-} StackFormat -> CmmBasicBlock -> CmmBasicBlock transformReturn block_infos formats (BasicBlock ident stmts) = - case last $ init stmts of + -- NOTE: assumes that return/jump can *only* appear at end of block + case last stmts of CmmReturn arguments -> - BasicBlock ident $ (init $ init stmts) ++ - [CmmJump (CmmReg spReg) arguments] - -- TODO: tail calls - -- TODO: return direct at the end of a block + BasicBlock ident $ + (init stmts) ++ + exit_function curr_format (CmmLoad (CmmReg spReg) wordRep) arguments + CmmJump target arguments -> + BasicBlock ident $ + (init stmts) ++ + exit_function curr_format target arguments _ -> BasicBlock ident stmts + where + curr_format = lookupWithDefaultUFM formats (panic $ "format: unknown block " ++ (showSDoc $ ppr $ getUnique ident)) ident -destructContinuation :: UniqFM {-BlockId-} CPSBlockInfo -> UniqFM {-BlockId-} ContinuationFormat -> CmmBasicBlock -> CmmBasicBlock +destructContinuation :: UniqFM {-BlockId-} CPSBlockInfo -> UniqFM {-BlockId-} StackFormat -> CmmBasicBlock -> CmmBasicBlock destructContinuation block_infos formats (BasicBlock ident stmts) = case info of ControlBlock -> BasicBlock ident stmts - ContinuationBlock _ -> BasicBlock ident (unpack_continuation ++ stmts) + ContinuationBlock _ -> BasicBlock ident (unpack_continuation curr_format ++ stmts) where info = lookupWithDefaultUFM block_infos (panic $ "info: unknown block " ++ (showSDoc $ ppr $ getUnique ident)) ident - format = lookupWithDefaultUFM formats (panic $ "format: unknown block " ++ (showSDoc $ ppr $ getUnique ident)) ident - unpack_continuation = CmmAssign spReg (CmmRegOff spReg frame_size) : - [CmmAssign (CmmLocal reg) (CmmLoad (CmmRegOff spReg (i*stack_slot_size)) (localRegRep reg)) - | (i, Just reg) <- zip [1..] format] - frame_size = stack_header_size + stack_slot_size * (length format) - stack_header_size = stack_slot_size -- TODO: check if this could be different than stack_slot_size - stack_slot_size = 4 -- TODO: find actual variables to be used instead of this - -constructContinuation :: UniqFM {-BlockId-} CPSBlockInfo -> UniqFM {-BlockId-} ContinuationFormat -> CmmBasicBlock -> CmmBasicBlock + curr_format = lookupWithDefaultUFM formats (panic $ "format: unknown block " ++ (showSDoc $ ppr $ getUnique ident)) ident + +constructContinuation2 :: UniqFM {-BlockId-} StackFormat -> BrokenBlock -> CmmBasicBlock +constructContinuation2 formats (BrokenBlock ident entry stmts exit) = + BasicBlock ident (prefix++stmts++postfix) + where + curr_format = lookupWithDefaultUFM formats (panic $ "format: unknown block " ++ (showSDoc $ ppr $ getUnique ident)) ident + prefix = case entry of + ControlEntry -> [] + FunctionEntry -> [] + ContinuationEntry formals -> unpack_continuation curr_format + postfix = case exit of + ControlExit _ next -> [CmmBranch next] + ReturnExit _ arguments -> exit_function curr_format (CmmLoad (CmmReg spReg) wordRep) arguments + TailCallExit _ target arguments -> exit_function curr_format target arguments + -- TODO: do something about global saves + CallExit _ next (CmmForeignCall target CmmCallConv) results arguments saves -> + let cont_format = lookupWithDefaultUFM formats (panic $ "format: unknown block " ++ (showSDoc $ ppr $ getUnique next)) next + in pack_continuation curr_format cont_format ++ + [CmmJump target arguments] + CallExit _ next _ results arguments saves -> panic "unimplemented CmmCall" + +constructContinuation :: UniqFM {-BlockId-} CPSBlockInfo -> UniqFM {-BlockId-} StackFormat -> CmmBasicBlock -> CmmBasicBlock constructContinuation block_infos formats (BasicBlock ident stmts) = case last $ init stmts of -- TODO: global_saves @@ -119,47 +232,118 @@ constructContinuation block_infos formats (BasicBlock ident stmts) = CmmCall (CmmForeignCall target CmmCallConv) results arguments _ -> BasicBlock ident $ init (init stmts) ++ - pack_continuation ++ + pack_continuation curr_format cont_format ++ [CmmJump target arguments] CmmCall target results arguments _ -> panic "unimplemented CmmCall" - _ -> BasicBlock ident $ (init stmts) ++ build_block_branch + -- TODO: branches for proc-points + -- _ -> BasicBlock ident $ (init stmts) ++ build_block_branch + _ -> BasicBlock ident stmts where info = lookupWithDefaultUFM block_infos (panic $ "info: unknown block " ++ (showSDoc $ ppr $ getUnique next_block)) next_block - format = lookupWithDefaultUFM formats (panic $ "format: unknown block " ++ (showSDoc $ ppr $ getUnique next_block)) next_block + cont_format = lookupWithDefaultUFM formats (panic $ "format: unknown block " ++ (showSDoc $ ppr $ getUnique next_block)) next_block + curr_format = lookupWithDefaultUFM formats (panic $ "format: unknown block " ++ (showSDoc $ ppr $ getUnique next_block)) ident next_block = case last stmts of CmmBranch next -> next -- TODO: blocks with jump at end -- TODO: blocks with return at end - _ -> panic "basic block without a branch at the end (unimplemented)" + _ -> panic $ "basic block without a branch at the end (unimplemented) " ++ (showSDoc $ ppr $ stmts) next_block_as_proc_expr = CmmLit $ CmmLabel $ mkReturnPtLabel $ getUnique next_block - pack_continuation = CmmAssign spReg (CmmRegOff spReg (-frame_size)) : - CmmStore (CmmReg spReg) next_block_as_proc_expr : - [CmmStore (CmmRegOff spReg (i*stack_slot_size)) (CmmReg $ CmmLocal reg) - | (i, Just reg) <- zip [1..] format] - frame_size = stack_header_size + stack_slot_size * (length format) - stack_header_size = stack_slot_size -- TODO: check if this could be different than stack_slot_size (e.g. fixedHdrSize depends on PAR and GRAN) - stack_slot_size = 4 -- TODO: find actual variables to be used instead of this (e.g. cgRepSizeW) block_needs_call = True -- TODO: use a table (i.e. proc-point) build_block_branch = if block_needs_call then [CmmJump next_block_as_proc_expr [] {- TODO: pass live -}] {- NOTE: a block can never be both a continuation and a controll block -} else [CmmBranch next_block] +-------------------------------------------------------------------------------- +-- Functions that generate CmmStmt sequences +-- for packing/unpacking continuations +-- and entering/exiting functions + +exit_function :: StackFormat -> CmmExpr -> CmmActuals -> [CmmStmt] +exit_function (StackFormat curr_id curr_frame_size curr_offsets) target arguments + = adjust_spReg ++ jump where + adjust_spReg = [ + CmmAssign spReg + (CmmRegOff spReg (curr_frame_size*wORD_SIZE))] + jump = [CmmJump target arguments] + +enter_function :: WordOff -> [CmmStmt] +enter_function max_frame_size + = check_stack_limit where + check_stack_limit = [ + CmmCondBranch + (CmmMachOp (MO_U_Lt $ cmmRegRep spReg) + [CmmRegOff spReg max_frame_size, CmmReg spLimReg]) + gc_block] + gc_block = undefined -- TODO: get stack and heap checks to go to same + +-- TODO: fix branches to proc point (we have to insert a new block to marshel the continuation) +pack_continuation :: StackFormat -> StackFormat -> [CmmStmt] +pack_continuation (StackFormat curr_id curr_frame_size curr_offsets) + (StackFormat cont_id cont_frame_size cont_offsets) + = save_live_values ++ set_stack_header ++ adjust_spReg where + -- TODO: only save variables when actually needed + save_live_values = + [CmmStore + (CmmRegOff + spReg (wORD_SIZE*(curr_frame_size - cont_frame_size + offset))) + (CmmReg reg) + | (reg, offset) <- cont_offsets] + set_stack_header = -- TODO: only set when needed + [CmmStore (CmmRegOff spReg (wORD_SIZE*(curr_frame_size - cont_frame_size))) continuation_function] + continuation_function = CmmLit $ CmmLabel $ mkReturnPtLabel $ getUnique cont_id + adjust_spReg = + if curr_frame_size == cont_frame_size + then [] + else [CmmAssign spReg (CmmRegOff spReg ((curr_frame_size - cont_frame_size)*wORD_SIZE))] + +-- Lazy adjustment of stack headers assumes all blocks +-- that could branch to eachother (i.e. control blocks) +-- have the same stack format (this causes a problem +-- only for proc-point). +unpack_continuation :: StackFormat -> [CmmStmt] +unpack_continuation (StackFormat curr_id curr_frame_size curr_offsets) + = load_live_values where + -- TODO: only save variables when actually needed + load_live_values = + [CmmAssign + reg + (CmmLoad (CmmRegOff spReg (wORD_SIZE*offset)) (cmmRegRep reg)) + | (reg, offset) <- curr_offsets] + -- TODO: TBD when to adjust the stack cpsProc :: CmmTop -> CPS [CmmTop] cpsProc x@(CmmData _ _) = return [x] cpsProc x@(CmmProc info_table ident params blocks) = do + broken_blocks <- liftM concat $ mapM breakBlock blocks - let live = cmmLiveness (map snd broken_blocks) + broken_blocks2 <- liftM concat (zipWithM breakBlock2 blocks (FunctionEntry:repeat ControlEntry)) + -- broken_blocks :: [BrokenBlock] + + let live = cmmLiveness (map snd broken_blocks) + let live2 :: BlockEntryLiveness + live2 = cmmLiveness2 broken_blocks2 + let blocks_with_live = map (cmmLivenessComment live . snd) broken_blocks - let formats = selectContinuationFormat (undefined {-TODO-}) live + + let formats = selectStackFormat (panic "params to selectStackFormat" {-TODO-}) live (undefined) + let formats2 :: BlockEnv StackFormat -- Stack format on entry + formats2 = selectStackFormat2 live2 broken_blocks2 + let block_infos = listToUFM $ map (\(info, block) -> (blockId block, info)) broken_blocks - let blocks_with_live' = map (constructContinuation block_infos formats) blocks_with_live - let blocks_with_live'' = map (destructContinuation block_infos formats) blocks_with_live' - let blocks_with_live''' = map (transformReturn block_infos formats) blocks_with_live'' - - return $ [CmmProc info_table ident params blocks_with_live'''] + --let blocks_with_live' = map (constructContinuation block_infos formats) blocks_with_live + --let blocks_with_live'' = map (destructContinuation block_infos formats) blocks_with_live' + --let blocks_with_live''' = map (transformReturn block_infos formats) blocks_with_live'' + + return $ [CmmProc info_table ident params $ map (constructContinuation2 formats2) broken_blocks2] +{- + return $ [CmmProc info_table ident params $ + map (constructContinuation block_infos formats . + destructContinuation block_infos formats . + transformReturn block_infos formats) + blocks_with_live] +-} -------------------------------------------------------------------------------- -- Takes a basic block and returns a list of basic blocks that @@ -186,6 +370,100 @@ breakBlock' current_id block_info accum_stmts (stmt@(CmmCall _ results _ _):stmt breakBlock' current_id arguments accum_stmts (stmt:stmts) = breakBlock' current_id arguments (accum_stmts ++ [stmt]) stmts +breakBlock2 (BasicBlock ident stmts) entry = breakBlock2' ident entry [] [] stmts + +breakBlock2' current_id block_info exits accum_stmts [] = + panic "block doesn't end in jump, goto or return" +breakBlock2' current_id entry exits accum_stmts [CmmJump target arguments] = + return [BrokenBlock current_id entry accum_stmts (TailCallExit exits target arguments)] +breakBlock2' current_id entry exits accum_stmts [CmmReturn arguments] = + return [BrokenBlock current_id entry accum_stmts (ReturnExit exits arguments)] +breakBlock2' current_id entry exits accum_stmts [CmmBranch target] = + return [BrokenBlock current_id entry accum_stmts (ControlExit exits target)] +breakBlock2' _ _ _ _ (CmmJump _ _:_) = panic "jump in middle of block" +breakBlock2' _ _ _ _ (CmmReturn _:_) = panic "return in middle of block" +breakBlock2' _ _ _ _ (CmmBranch _:_) = panic "branch in middle of block" +breakBlock2' _ _ _ _ (CmmSwitch _ _:_) = panic "switch in block not implemented" +breakBlock2' current_id entry exits accum_stmts (CmmCall target results arguments saves:stmts) = do + new_id <- newLabelCPS + rest <- breakBlock2' new_id (ContinuationEntry results) [] [] stmts + return $ BrokenBlock current_id entry accum_stmts (CallExit exits new_id target results arguments saves) : rest +breakBlock2' current_id entry exits accum_stmts (s@(CmmCondBranch test target):stmts) = + breakBlock2' current_id entry (target:exits) (accum_stmts++[s]) stmts +breakBlock2' current_id entry exits accum_stmts (s:stmts) = + breakBlock2' current_id entry exits (accum_stmts++[s]) stmts + +brokenBlockTargets (BrokenBlock _ _ _ (TailCallExit exits _ _)) = exits +brokenBlockTargets (BrokenBlock _ _ _ (ReturnExit exits _)) = exits +brokenBlockTargets (BrokenBlock _ _ _ (ControlExit exits target)) = target:exits +brokenBlockTargets (BrokenBlock _ _ _ (CallExit exits next _ _ _ _)) = next:exits + +brokenBlockId (BrokenBlock ident _ _ _) = ident + +cmmBrokenBlockSources :: + [BrokenBlock] -> UniqFM {-BlockId-} (UniqSet BlockId) +cmmBrokenBlockSources blocks = foldr aux emptyUFM blocks where + aux block sourcesUFM = + foldr add_source_edges sourcesUFM targets where + add_source_edges t ufm = + addToUFM_Acc (flip addOneToUniqSet) unitUniqSet ufm t ident + targets = brokenBlockTargets block + ident = brokenBlockId block + +cmmBrokenBlockNames :: [BrokenBlock] -> UniqFM {-BlockId-} BrokenBlock +cmmBrokenBlockNames blocks = listToUFM $ map block_name blocks where + block_name b = (brokenBlockId b, b) + +cmmBrokenBlockDependants :: UniqFM {-BlockId-} (UniqSet BlockId) -> BlockId -> [BlockId] +cmmBrokenBlockDependants sources ident = + uniqSetToList $ lookupWithDefaultUFM sources emptyUniqSet ident + +cmmBrokenBlockLive :: UniqFM {-BlockId-} CmmLive -> BrokenBlock -> CmmLive +cmmBrokenBlockLive other_live (BrokenBlock _ _ stmts exit) = + foldr ((.) . (cmmStmtLive other_live)) id stmts live_at_end + where + live_at_end = + case exit of + ControlExit _ _ -> emptyUniqSet + ReturnExit _ actuals -> foldr ((.) . cmmExprLive) id (map fst actuals) emptyUniqSet + TailCallExit _ target actuals -> + cmmExprLive target $ foldr ((.) . cmmExprLive) id (map fst actuals) $ emptyUniqSet + CallExit _ _ target _ actuals live -> + target_liveness $ + foldr ((.) . cmmExprLive) id (map fst actuals) $ + emptyUniqSet + where + only_local_regs [] = [] + only_local_regs ((CmmGlobal _,_):args) = only_local_regs args + only_local_regs ((CmmLocal r,_):args) = r:only_local_regs args + target_liveness = + case target of + (CmmForeignCall target _) -> cmmExprLive target + (CmmPrim _) -> id + + +cmmBrokenBlockUpdate :: + UniqFM {-BlockId-} BrokenBlock + -> BlockId + -> Maybe BlockId + -> UniqFM {-BlockId-} CmmLive + -> Maybe (UniqFM {-BlockId-} CmmLive) +cmmBrokenBlockUpdate blocks node _ state = + let old_live = lookupWithDefaultUFM state (panic "unknown block id during liveness analysis") node + block = lookupWithDefaultUFM blocks (panic "unknown block id during liveness analysis") node + new_live = cmmBrokenBlockLive state block + in if (sizeUniqSet old_live) == (sizeUniqSet new_live) + then Nothing + else Just $ addToUFM state node new_live + + +cmmLiveness2 :: [BrokenBlock] -> UniqFM {-BlockId-} CmmLive +cmmLiveness2 blocks = + fixedpoint (cmmBrokenBlockDependants sources) (cmmBrokenBlockUpdate blocks') + (map brokenBlockId blocks) (listToUFM [(brokenBlockId b, emptyUniqSet) | b <- blocks]) where + sources = cmmBrokenBlockSources blocks + blocks' = cmmBrokenBlockNames blocks + -------------------------------------------------------------------------------- cmmCPS :: DynFlags -> [Cmm] -- C-- with Proceedures diff --git a/compiler/cmm/Dataflow.hs b/compiler/cmm/Dataflow.hs index 96565c3..093a8a6 100644 --- a/compiler/cmm/Dataflow.hs +++ b/compiler/cmm/Dataflow.hs @@ -1,4 +1,4 @@ -module Dataflow (cmmLivenessComment, cmmLiveness, CmmLive) where +module Dataflow {-(fixedpoint, cmmLivenessComment, cmmLiveness, CmmLive)-} where import Cmm import PprCmm () @@ -36,6 +36,9 @@ cmmBranchTargets (BasicBlock _ stmts) = -- The variables that were made live and killed respectively type CmmLive = UniqSet LocalReg + +type BlockEntryLiveness = BlockEnv CmmLive -- The variables live on entry to each block + addLive new_live live = live `unionUniqSets` new_live addKilled new_killed live = live `minusUniqSet` new_killed @@ -106,7 +109,7 @@ cmmBlockUpdate blocks node _ state = cmmBlockDependants :: UniqFM {-BlockId-} (UniqSet BlockId) -> BlockId -> [BlockId] cmmBlockDependants sources ident = - uniqSetToList $ lookupWithDefaultUFM sources emptyUFM ident + uniqSetToList $ lookupWithDefaultUFM sources emptyUniqSet ident cmmBlockSourcesAndTargets :: [CmmBasicBlock] @@ -124,7 +127,7 @@ cmmBlockNames :: [CmmBasicBlock] -> UniqFM {-BlockId-} CmmBasicBlock cmmBlockNames blocks = listToUFM $ map block_name blocks where block_name b = (blockId b, b) -cmmLiveness :: [CmmBasicBlock] -> UniqFM {-BlockId-} CmmLive +cmmLiveness :: [CmmBasicBlock] -> BlockEnv CmmLive cmmLiveness blocks = fixedpoint (cmmBlockDependants sources) (cmmBlockUpdate blocks') (map blockId blocks) (listToUFM [(blockId b, emptyUniqSet) | b <- blocks]) where -- 1.7.10.4