--- | A mapping from block labels to the blocks that target it
-type BlockSources = BlockEnv (UniqSet BlockId)
-
--- | A mapping from block labels to the statements in the block
-type BlockStmts = BlockEnv [CmmStmt]
-
------------------------------------------------------------------------------
--- | Calculated liveness info for a list of 'CmmBasicBlock'
------------------------------------------------------------------------------
-cmmLiveness :: [CmmBasicBlock] -> BlockEntryLiveness
-cmmLiveness blocks =
- fixedpoint (cmmBlockDependants sources)
- (cmmBlockUpdate blocks')
- (map blockId blocks)
- (listToUFM [(blockId b, emptyUniqSet) | b <- blocks])
- where
- sources :: BlockSources
- sources = cmmBlockSources blocks
-
- blocks' :: BlockStmts
- blocks' = listToUFM $ map block_name blocks
-
- block_name :: CmmBasicBlock -> (BlockId, [CmmStmt])
- block_name b = (blockId b, blockStmts b)
-
-{-
--- For debugging, annotate each block with a comment indicating
--- the calculated live variables
-cmmLivenessComment ::
- BlockEnv (UniqSet LocalReg) -> CmmBasicBlock -> CmmBasicBlock
-cmmLivenessComment live (BasicBlock ident stmts) =
- BasicBlock ident stmts' where
- stmts' = (CmmComment $ mkFastString $ showSDoc $ ppr $ live'):stmts
- live' = map CmmLocal $ uniqSetToList $ lookupWithDefaultUFM live emptyUniqSet ident
--}
-
-
------------------------------------------------------------------------------
--- | Calculates a table of where one can lookup the blocks that might
--- need updating after a given block is updated in the liveness analysis
------------------------------------------------------------------------------
-cmmBlockSources :: [CmmBasicBlock] -> BlockSources
-cmmBlockSources blocks = foldr aux emptyUFM blocks
- where
- aux :: CmmBasicBlock
- -> BlockSources
- -> BlockSources
- aux block sourcesUFM =
- foldUniqSet (add_source_edges $ blockId block)
- sourcesUFM
- (branch_targets $ blockStmts block)
-
- add_source_edges :: BlockId -> BlockId
- -> BlockSources
- -> BlockSources
- add_source_edges source target ufm =
- addToUFM_Acc (flip addOneToUniqSet) unitUniqSet ufm target source
-
- branch_targets :: [CmmStmt] -> UniqSet BlockId
- branch_targets stmts =
- mkUniqSet $ concatMap target stmts where
- target (CmmBranch ident) = [ident]
- target (CmmCondBranch _ ident) = [ident]
- target (CmmSwitch _ blocks) = mapMaybe id blocks
- target _ = []
-
------------------------------------------------------------------------------
--- | Given the table calculated by 'cmmBlockSources', list all blocks
--- that depend on the result of a particular block.
---
--- Used by the call to 'fixedpoint'.
------------------------------------------------------------------------------
-cmmBlockDependants :: BlockSources -> BlockId -> [BlockId]
-cmmBlockDependants sources ident =
- uniqSetToList $ lookupWithDefaultUFM sources emptyUniqSet ident
-
------------------------------------------------------------------------------
--- | Given the table of type 'BlockStmts' and a block that was updated,
--- calculate an updated BlockEntryLiveness
------------------------------------------------------------------------------
-cmmBlockUpdate ::
- BlockStmts
- -> BlockId
- -> Maybe BlockId
- -> BlockEntryLiveness
- -> Maybe BlockEntryLiveness
-cmmBlockUpdate blocks node _ state =
- if (sizeUniqSet old_live) == (sizeUniqSet new_live)
- then Nothing
- else Just $ addToUFM state node new_live
- where
- new_live, old_live :: CmmLive
- new_live = cmmStmtListLive state block_stmts
- old_live = lookupWithDefaultUFM state missing_live node
-
- block_stmts :: [CmmStmt]
- block_stmts = lookupWithDefaultUFM blocks missing_block node
-
- missing_live = panic "unknown block id during liveness analysis"
- missing_block = panic "unknown block id during liveness analysis"
-
------------------------------------------------------------------------------
--- Section:
------------------------------------------------------------------------------