import Dataflow (fixedpoint)
import CmmLive
+import CmmCPSData
+import CmmProcPoint
import MachOp
import ForeignCall
-- and heap memory (not sure if that's usefull at all though, but it may
-- be worth exploring the design space).
-data BrokenBlock
- = BrokenBlock {
- brokenBlockId :: BlockId, -- Like a CmmBasicBlock
- brokenBlockEntry :: BlockEntryInfo,
- -- How this block can be entered
-
- brokenBlockStmts :: [CmmStmt],
- -- Like a CmmBasicBlock
- -- (but without the last statement)
-
- brokenBlockTargets :: [BlockId],
- -- Blocks that this block could
- -- branch to one either by conditional
- -- branches or via the last statement
-
- brokenBlockExit :: FinalStmt
- -- How the block can be left
- }
-
continuationLabel (Continuation _ _ l _ _) = l
data Continuation =
Continuation
-- to a label. To jump to the first block in a Proc,
-- use the appropriate CLabel.
-data BlockEntryInfo
- = FunctionEntry -- Beginning of a function
- CLabel -- The function name
- CmmFormals -- Aguments to function
-
- | ContinuationEntry -- Return point of a call
- CmmFormals -- return values (argument to continuation)
- -- TODO:
- -- | ProcPointEntry -- no return values, but some live might end up as params or possibly in the frame
-
- | ControlEntry -- A label in the input
-
--- Final statement in a BlokenBlock
--- Constructors and arguments match those in Cmm,
--- but are restricted to branches, returns, jumps, calls and switches
-data FinalStmt
- = FinalBranch
- BlockId -- next block (must be a ControlEntry)
-
- | FinalReturn
- CmmActuals -- return values
-
- | FinalJump
- CmmExpr -- the function to call
- CmmActuals -- arguments to call
-
- | FinalCall
- 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)
-
- | FinalSwitch
- CmmExpr [Maybe BlockId] -- Table branch
-
- -- TODO: | ProcPointExit (needed?)
-
+-- Describes the layout of a stack frame for a continuation
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 -}
+ (Maybe CLabel) -- The label occupying the top slot
+ WordOff -- Total frame size in words
+ [(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
-blocksToBlockEnv :: [BrokenBlock] -> BlockEnv BrokenBlock
-blocksToBlockEnv blocks = listToUFM $ map (\b -> (brokenBlockId b, b)) blocks
-
-----------------------------------------------------------------------------
-calculateOwnership :: UniqSet BlockId -> [BrokenBlock] -> BlockEnv (UniqSet BlockId)
-calculateOwnership proc_points blocks =
- fixedpoint dependants update (map brokenBlockId blocks) emptyUFM
- where
- blocks_ufm :: BlockEnv BrokenBlock
- blocks_ufm = blocksToBlockEnv blocks
-
- dependants :: BlockId -> [BlockId]
- dependants ident =
- brokenBlockTargets $ lookupWithDefaultUFM
- blocks_ufm unknown_block ident
-
- update :: BlockId -> Maybe BlockId
- -> BlockEnv (UniqSet BlockId) -> Maybe (BlockEnv (UniqSet BlockId))
- update ident cause owners =
- case (cause, ident `elementOfUniqSet` proc_points) of
- (Nothing, True) -> Just $ addToUFM owners ident (unitUniqSet ident)
- (Nothing, False) -> Nothing
- (Just cause', True) -> Nothing
- (Just cause', False) ->
- if (sizeUniqSet old) == (sizeUniqSet new)
- then Nothing
- else Just $ addToUFM owners ident new
- where
- old = lookupWithDefaultUFM owners emptyUniqSet ident
- new = old `unionUniqSets` lookupWithDefaultUFM owners emptyUniqSet cause'
-
- unknown_block = panic "unknown BlockId in selectStackFormat"
-
-calculateProcPoints :: [BrokenBlock] -> UniqSet BlockId
-calculateProcPoints blocks = calculateProcPoints' init_proc_points blocks
- where
- init_proc_points = mkUniqSet $
- map brokenBlockId $
- filter always_proc_point blocks
- always_proc_point BrokenBlock {
- brokenBlockEntry = FunctionEntry _ _ } = True
- always_proc_point BrokenBlock {
- brokenBlockEntry = ContinuationEntry _ } = True
- always_proc_point _ = False
-
-calculateProcPoints' :: UniqSet BlockId -> [BrokenBlock] -> UniqSet BlockId
-calculateProcPoints' old_proc_points blocks =
- if sizeUniqSet old_proc_points == sizeUniqSet new_proc_points
- then old_proc_points
- else calculateProcPoints' new_proc_points blocks
- where
- owners = calculateOwnership old_proc_points blocks
- new_proc_points = unionManyUniqSets (old_proc_points:(map (calculateProcPoints'' owners) blocks))
-
-calculateProcPoints'' :: BlockEnv (UniqSet BlockId) -> BrokenBlock -> UniqSet BlockId
-calculateProcPoints'' owners block =
- unionManyUniqSets (map (f parent_id) child_ids)
- where
- parent_id = brokenBlockId block
- child_ids = brokenBlockTargets block
- f parent_id child_id =
- if needs_proc_point
- then unitUniqSet child_id
- else emptyUniqSet
- where
- parent_owners = lookupWithDefaultUFM owners emptyUniqSet parent_id
- child_owners = lookupWithDefaultUFM owners emptyUniqSet child_id
- needs_proc_point = not $ isEmptyUniqSet $ child_owners `minusUniqSet` parent_owners
- --needs_proc_point = sizeUniqSet (parent_owners `unionUniqSets` child_owners) /= sizeUniqSet parent_owners
-
-cmmCondBranchTargets (CmmCondBranch _ target) = [target]
-cmmCondBranchTargets _ = []
-
-finalBranchOrSwitchTargets (FinalBranch target) = [target]
-finalBranchOrSwitchTargets (FinalSwitch _ targets) = mapCatMaybes id targets
-finalBranchOrSwitchTargets _ = []
collectNonProcPointTargets ::
UniqSet BlockId -> BlockEnv BrokenBlock
else foldl (collectNonProcPointTargets proc_points blocks) new_targets targets
where
block' = lookupWithDefaultUFM blocks (panic "TODO") block
- targets = -- We can't use the brokenBlockTargets b/c we don't want to follow the final goto after a call -- brokenBlockTargets block'
- --finalBranchOrSwitchTargets (brokenBlockExit block') ++ concatMap cmmCondBranchTargets (brokenBlockStmts block')
+ targets =
+ -- Note the subtlety that since the extra branch after a call
+ -- will always be to a block that is a proc-point,
+ -- this subtraction will always remove that case
uniqSetToList $ (mkUniqSet $ brokenBlockTargets block') `minusUniqSet` proc_points
-- TODO: remove redundant uniqSetToList
new_targets = current_targets `unionUniqSets` (mkUniqSet targets)
--------------------------------------------------------------------------------
-- For now just select the continuation orders in the order they are in the set with no gaps
-selectStackFormat :: BlockEnv CmmLive -> [BrokenBlock] -> BlockEnv StackFormat
-selectStackFormat live blocks =
- fixedpoint dependants update (map brokenBlockId blocks) emptyUFM
- where
- blocks_ufm :: BlockEnv BrokenBlock
- blocks_ufm = listToUFM $ map (\b -> (brokenBlockId b, b)) blocks
-
- dependants :: BlockId -> [BlockId]
- dependants ident =
- brokenBlockTargets $ lookupWithDefaultUFM
- blocks_ufm unknown_block ident
-
- update :: BlockId -> Maybe BlockId
- -> BlockEnv StackFormat -> Maybe (BlockEnv StackFormat)
- update ident cause formats =
- if ident `elemUFM` formats
- then Nothing -- Blocks only need to be updated once
- else case (cause,
- brokenBlockEntry $ lookupWithDefaultUFM blocks_ufm
- unknown_block ident) of
- -- Propagate only to blocks entered by branches
- -- (not function entry blocks or continuation entry blocks)
- (Just cause_name, ControlEntry) ->
- Just $ addToUFM formats ident cause_format
- where cause_format = lookupWithDefaultUFM
- formats unknown_block
- cause_name
- -- Do initial calculates for function blocks
- (Nothing, FunctionEntry _ _) ->
- Just $
- addToUFM formats ident $
- StackFormat ident 0 []
- -- Do initial calculates for continuation blocks
- (Nothing, ContinuationEntry _) ->
- Just $
- addToUFM formats ident $
- live_to_format ident $
- lookupWithDefaultUFM live unknown_block ident
- _ -> Nothing
-
- unknown_block = panic "unknown BlockId in selectStackFormat"
-
- live_to_format :: BlockId -> CmmLive -> StackFormat
- 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)
-
selectStackFormat2 :: BlockEnv CmmLive -> [Continuation] -> [(CLabel, StackFormat)]
selectStackFormat2 live continuations =
map (\c -> (continuationLabel c, selectStackFormat' c)) continuations
where
selectStackFormat' (Continuation True info_table label formals blocks) =
- let ident = brokenBlockId $ head blocks -- TODO: CLabel isn't a uniquable, but we need a better way than this
- in StackFormat ident 0 []
+ --let ident = brokenBlockId $ head blocks -- TODO: CLabel isn't a uniquable, but we need a better way than this
+ --in
+ StackFormat (Just label) 0 []
selectStackFormat' (Continuation False info_table label formals blocks) =
+ -- TODO: assumes the first block is the entry block
let ident = brokenBlockId $ head blocks -- TODO: CLabel isn't a uniquable, but we need a better way than this
- in live_to_format ident $ lookupWithDefaultUFM live unknown_block ident
+ in live_to_format label formals $ lookupWithDefaultUFM live unknown_block ident
- live_to_format :: BlockId -> CmmLive -> StackFormat
- live_to_format label live =
+ live_to_format :: CLabel -> CmmFormals -> CmmLive -> StackFormat
+ live_to_format label formals live =
foldl extend_format
- (StackFormat label retAddrSizeW [])
- (uniqSetToList live)
+ (StackFormat (Just label) retAddrSizeW [])
+ (uniqSetToList (live `minusUniqSet` mkUniqSet (cmmFormalsToLiveLocals formals)))
extend_format :: StackFormat -> LocalReg -> StackFormat
- extend_format (StackFormat block size offsets) reg =
- StackFormat block (slot_size reg + size) ((CmmLocal reg, size) : offsets)
+ extend_format (StackFormat label size offsets) reg =
+ StackFormat label (slot_size reg + size) ((CmmLocal reg, size) : offsets)
unknown_block = panic "unknown BlockId in selectStackFormat"
constructContinuation formats (Continuation is_entry info label formals blocks) =
CmmProc info label formals (map (constructContinuation2' label formats) blocks)
-{-
- BasicBlock ident (prefix++stmts++postfix)
- where
-
- curr_format = lookupWithDefaultUFM formats unknown_block ident
- unknown_block = panic "unknown BlockId in constructContinuation"
- prefix = case entry of
- ControlEntry -> []
- FunctionEntry _ -> []
- ContinuationEntry formals ->
- unpack_continuation curr_format
- postfix = case exit of
- FinalBranch next -> [CmmBranch next]
- FinalSwitch expr targets -> [CmmSwitch expr targets]
- FinalReturn arguments ->
- exit_function curr_format
- (CmmLoad (CmmReg spReg) wordRep)
- arguments
- FinalJump target arguments ->
- exit_function curr_format target arguments
- -- TODO: do something about global saves
- FinalCall next (CmmForeignCall target CmmCallConv)
- results arguments saves ->
- pack_continuation curr_format cont_format ++
- [CmmJump target arguments]
- where
- cont_format = lookupWithDefaultUFM formats
- unknown_block next
- FinalCall next _ results arguments saves -> panic "unimplemented CmmCall"
--}
-
constructContinuation2' :: CLabel -> [(CLabel, StackFormat)] -> BrokenBlock
-> CmmBasicBlock
constructContinuation2' curr_ident formats (BrokenBlock ident entry stmts _ exit) =
lookup (mkReturnPtLabel $ getUnique next) formats
FinalCall next _ results arguments saves -> panic "unimplemented CmmCall"
-constructContinuation2 :: BlockEnv StackFormat -> BrokenBlock
- -> CmmBasicBlock
-constructContinuation2 formats (BrokenBlock ident entry stmts _ exit) =
- BasicBlock ident (prefix++stmts++postfix)
- where
- curr_format = lookupWithDefaultUFM formats unknown_block ident
- unknown_block = panic "unknown BlockId in constructContinuation"
- prefix = case entry of
- ControlEntry -> []
- FunctionEntry _ -> []
- ContinuationEntry formals ->
- unpack_continuation curr_format
- postfix = case exit of
- FinalBranch next -> [CmmBranch next]
- FinalSwitch expr targets -> [CmmSwitch expr targets]
- FinalReturn arguments ->
- exit_function curr_format
- (CmmLoad (CmmReg spReg) wordRep)
- arguments
- FinalJump target arguments ->
- exit_function curr_format target arguments
- -- TODO: do something about global saves
- FinalCall next (CmmForeignCall target CmmCallConv)
- results arguments saves ->
- pack_continuation curr_format cont_format ++
- [CmmJump target arguments]
- where
- cont_format = lookupWithDefaultUFM formats
- unknown_block next
- FinalCall next _ results arguments saves -> panic "unimplemented CmmCall"
-
--------------------------------------------------------------------------------
-- Functions that generate CmmStmt sequences
-- for packing/unpacking continuations
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))]
+ adjust_spReg =
+ if curr_frame_size == 0
+ then []
+ else [CmmAssign spReg
+ (CmmRegOff spReg (curr_frame_size*wORD_SIZE))]
jump = [CmmJump target arguments]
enter_function :: WordOff -> [CmmStmt]
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 {-TODO: use the correct function -} $ getUnique cont_id
+ needs_header =
+ case (curr_id, cont_id) of
+ (Just x, Just y) -> x /= y
+ _ -> isJust cont_id
+ set_stack_header =
+ if not needs_header
+ then []
+ else [CmmStore (CmmRegOff spReg (wORD_SIZE*(curr_frame_size - cont_frame_size))) continuation_function]
+ continuation_function = CmmLit $ CmmLabel $ fromJust cont_id
adjust_spReg =
if curr_frame_size == cont_frame_size
then []
-- Calculate live variables for each broken block
live :: BlockEntryLiveness
live = cmmLiveness $ map cmmBlockFromBrokenBlock broken_blocks
+ -- nothing can be live on entry to the first block so we could take the tail
proc_points :: UniqSet BlockId
proc_points = calculateProcPoints broken_blocks
--procs = groupBlocksIntoContinuations live broken_blocks
-- Select the stack format on entry to each block
- formats :: BlockEnv StackFormat
- formats = selectStackFormat live broken_blocks
-
formats2 :: [(CLabel, StackFormat)]
formats2 = selectStackFormat2 live continuations
-- Do the actual CPS transform
- cps_blocks :: [CmmBasicBlock]
- cps_blocks = map (constructContinuation2 formats) broken_blocks
-
cps_continuations :: [CmmTop]
cps_continuations = map (constructContinuation formats2) continuations