module CmmBuildInfoTables
( CAFSet, CAFEnv, cafAnal, localCAFInfo, mkTopCAFInfo
, setInfoTableSRT, setInfoTableStackMap
, TopSRT, emptySRT, srtToData
, bundleCAFs
, lowerSafeForeignCalls
, cafTransfers, liveSlotTransfers
, mkLiveness )
where
#include "HsVersions.h"
import StgCmmForeign
import StgCmmUtils
import Constants
import Digraph
import qualified Prelude as P
import Prelude hiding (succ)
import Util (sortLe)
import BlockId
import Bitmap
import CLabel
import Cmm
import CmmUtils
import CmmStackLayout
import Module
import FastString
import ForeignCall
import IdInfo
import Data.List
import Maybes
import MkGraph as M
import Control.Monad
import Name
import OptimizationFuel
import Outputable
import Platform
import SMRep
import UniqSupply
import Compiler.Hoopl
import Data.Map (Map)
import qualified Data.Map as Map
import qualified FiniteMap as Map
type RegSlotInfo
= ( Int
, LocalReg
, Int)
live_ptrs :: ByteOff -> BlockEnv SubAreaSet -> AreaMap -> BlockId -> StackLayout
live_ptrs oldByte slotEnv areaMap bid =
res
where
res = mkLiveness (reverse $ slotsToList youngByte liveSlots [])
slotsToList :: Int -> [RegSlotInfo] -> [Maybe LocalReg] -> [Maybe LocalReg]
slotsToList n [] results | n == oldByte = results
slotsToList n (s : _) _ | n == oldByte =
pprPanic "slot left off live_ptrs" (ppr s <+> ppr oldByte <+>
ppr n <+> ppr liveSlots <+> ppr youngByte)
slotsToList n _ _ | n < oldByte =
panic "stack slots not allocated on word boundaries?"
slotsToList n l@((n', r, w) : rst) results =
if n == (n' + w) then
ASSERT (not (isPtr r) ||
(n `mod` wORD_SIZE == 0 && w == wORD_SIZE))
slotsToList next (dropWhile (non_ptr_younger_than next) rst)
(stack_rep : results)
else slotsToList next (dropWhile (non_ptr_younger_than next) l)
(Nothing : results)
where next = n wORD_SIZE
stack_rep = if isPtr r then Just r else Nothing
slotsToList n [] results = slotsToList (n wORD_SIZE) [] (Nothing : results)
non_ptr_younger_than next (n', r, w) =
n' + w > next &&
ASSERT (not (isPtr r))
True
isPtr = isGcPtrType . localRegType
liveSlots :: [RegSlotInfo]
liveSlots = sortBy (\ (off,_,_) (off',_,_) -> compare off' off)
(Map.foldRightWithKey (\_ -> flip $ foldl add_slot) [] slots)
add_slot :: [RegSlotInfo] -> SubArea -> [RegSlotInfo]
add_slot rst (a@(RegSlot r@(LocalReg _ ty)), off, w) =
if off == w && widthInBytes (typeWidth ty) == w then
(expectJust "add_slot" (Map.lookup a areaMap), r, w) : rst
else panic "live_ptrs: only part of a variable live at a proc point"
add_slot rst (CallArea Old, _, _) =
rst
add_slot rst ((CallArea _), _, _) =
rst
slots :: SubAreaSet
slots = expectJust "live_ptrs slots" $ mapLookup bid slotEnv
youngByte = expectJust "live_ptrs bid_pos" $ Map.lookup (CallArea (Young bid)) areaMap
setInfoTableStackMap :: SlotEnv -> AreaMap -> CmmDecl -> CmmDecl
setInfoTableStackMap slotEnv areaMap
t@(CmmProc (TopInfo {stack_info=StackInfo {updfr_space = Just updfr_off}}) _
(CmmGraph {g_entry = eid}))
= updInfo (const (live_ptrs updfr_off slotEnv areaMap eid)) id t
setInfoTableStackMap _ _ t = t
type CAFSet = Map CLabel ()
type CAFEnv = BlockEnv CAFSet
cafLattice :: DataflowLattice CAFSet
cafLattice = DataflowLattice "live cafs" Map.empty add
where add _ (OldFact old) (NewFact new) = case old `Map.union` new of
new' -> (changeIf $ Map.size new' > Map.size old, new')
cafTransfers :: Platform -> BwdTransfer CmmNode CAFSet
cafTransfers platform = mkBTransfer3 first middle last
where first _ live = live
middle m live = foldExpDeep addCaf m live
last l live = foldExpDeep addCaf l (joinOutFacts cafLattice l live)
addCaf e set = case e of
CmmLit (CmmLabel c) -> add c set
CmmLit (CmmLabelOff c _) -> add c set
CmmLit (CmmLabelDiffOff c1 c2 _) -> add c1 $ add c2 set
_ -> set
add l s = if hasCAF l then Map.insert (toClosureLbl platform l) () s
else s
cafAnal :: Platform -> CmmGraph -> FuelUniqSM CAFEnv
cafAnal platform g
= liftM snd $ dataflowPassBwd g [] $ analBwd cafLattice (cafTransfers platform)
data TopSRT = TopSRT { lbl :: CLabel
, next_elt :: Int
, rev_elts :: [CLabel]
, elt_map :: Map CLabel Int }
instance PlatformOutputable TopSRT where
pprPlatform platform (TopSRT lbl next elts eltmap) =
text "TopSRT:" <+> pprPlatform platform lbl
<+> ppr next
<+> pprPlatform platform elts
<+> pprPlatform platform eltmap
emptySRT :: MonadUnique m => m TopSRT
emptySRT =
do top_lbl <- getUniqueM >>= \ u -> return $ mkSRTLabel (mkFCallName u "srt") NoCafRefs
return TopSRT { lbl = top_lbl, next_elt = 0, rev_elts = [], elt_map = Map.empty }
cafMember :: TopSRT -> CLabel -> Bool
cafMember srt lbl = Map.member lbl (elt_map srt)
cafOffset :: TopSRT -> CLabel -> Maybe Int
cafOffset srt lbl = Map.lookup lbl (elt_map srt)
addCAF :: CLabel -> TopSRT -> TopSRT
addCAF caf srt =
srt { next_elt = last + 1
, rev_elts = caf : rev_elts srt
, elt_map = Map.insert caf last (elt_map srt) }
where last = next_elt srt
srtToData :: TopSRT -> CmmGroup
srtToData srt = [CmmData RelocatableReadOnlyData (Statics (lbl srt) tbl)]
where tbl = map (CmmStaticLit . CmmLabel) (reverse (rev_elts srt))
buildSRTs :: TopSRT -> Map CLabel CAFSet -> CAFSet ->
FuelUniqSM (TopSRT, Maybe CmmDecl, C_SRT)
buildSRTs topSRT topCAFMap cafs =
do let liftCAF lbl () z =
case Map.lookup lbl topCAFMap of Just cafs -> z `Map.union` cafs
Nothing -> Map.insert lbl () z
sub_srt topSRT localCafs =
let cafs = Map.keys (Map.foldRightWithKey liftCAF Map.empty localCafs)
mkSRT topSRT =
do localSRTs <- procpointSRT (lbl topSRT) (elt_map topSRT) cafs
return (topSRT, localSRTs)
in if length cafs > maxBmpSize then
mkSRT (foldl add_if_missing topSRT cafs)
else
mkSRT (add_if_too_far topSRT cafs)
add_if_missing srt caf =
if cafMember srt caf then srt else addCAF caf srt
add_if_too_far srt@(TopSRT {elt_map = m}) cafs =
add srt (sortBy farthestFst cafs)
where
farthestFst x y = case (Map.lookup x m, Map.lookup y m) of
(Nothing, Nothing) -> EQ
(Nothing, Just _) -> LT
(Just _, Nothing) -> GT
(Just d, Just d') -> compare d' d
add srt [] = srt
add srt@(TopSRT {next_elt = next}) (caf : rst) =
case cafOffset srt caf of
Just ix -> if next ix > maxBmpSize then
add (addCAF caf srt) rst
else srt
Nothing -> add (addCAF caf srt) rst
(topSRT, subSRTs) <- sub_srt topSRT cafs
let (sub_tbls, blockSRTs) = subSRTs
return (topSRT, sub_tbls, blockSRTs)
procpointSRT :: CLabel -> Map CLabel Int -> [CLabel] ->
FuelUniqSM (Maybe CmmDecl, C_SRT)
procpointSRT _ _ [] =
return (Nothing, NoC_SRT)
procpointSRT top_srt top_table entries =
do (top, srt) <- bitmap `seq` to_SRT top_srt offset len bitmap
return (top, srt)
where
ints = map (expectJust "constructSRT" . flip Map.lookup top_table) entries
sorted_ints = sortLe (<=) ints
offset = head sorted_ints
bitmap_entries = map (subtract offset) sorted_ints
len = P.last bitmap_entries + 1
bitmap = intsToBitmap len bitmap_entries
maxBmpSize :: Int
maxBmpSize = widthInBits wordWidth `div` 2
to_SRT :: CLabel -> Int -> Int -> Bitmap -> FuelUniqSM (Maybe CmmDecl, C_SRT)
to_SRT top_srt off len bmp
| len > maxBmpSize || bmp == [fromIntegral srt_escape]
= do id <- getUniqueM
let srt_desc_lbl = mkLargeSRTLabel id
tbl = CmmData RelocatableReadOnlyData $
Statics srt_desc_lbl $ map CmmStaticLit
( cmmLabelOffW top_srt off
: mkWordCLit (fromIntegral len)
: map mkWordCLit bmp)
return (Just tbl, C_SRT srt_desc_lbl 0 srt_escape)
| otherwise
= return (Nothing, C_SRT top_srt off (fromIntegral (head bmp)))
localCAFInfo :: Platform -> CAFEnv -> CmmDecl -> Maybe (CLabel, CAFSet)
localCAFInfo _ _ (CmmData _ _) = Nothing
localCAFInfo platform cafEnv (CmmProc top_info top_l (CmmGraph {g_entry=entry})) =
case info_tbl top_info of
CmmInfoTable { cit_rep = rep }
| not (isStaticRep rep)
-> Just (toClosureLbl platform top_l,
expectJust "maybeBindCAFs" $ mapLookup entry cafEnv)
_ -> Nothing
mkTopCAFInfo :: [(CLabel, CAFSet)] -> Map CLabel CAFSet
mkTopCAFInfo localCAFs = foldl addToTop Map.empty g
where addToTop env (AcyclicSCC (l, cafset)) =
Map.insert l (flatten env cafset) env
addToTop env (CyclicSCC nodes) =
let (lbls, cafsets) = unzip nodes
cafset = lbls `Map.deleteList` foldl Map.union Map.empty cafsets
in foldl (\env l -> Map.insert l (flatten env cafset) env) env lbls
flatten env cafset = Map.foldRightWithKey (lookup env) Map.empty cafset
lookup env caf () cafset' =
case Map.lookup caf env of Just cafs -> Map.foldRightWithKey add cafset' cafs
Nothing -> add caf () cafset'
add caf () cafset' = Map.insert caf () cafset'
g = stronglyConnCompFromEdgedVertices
(map (\n@(l, cafs) -> (n, l, Map.keys cafs)) localCAFs)
bundleCAFs :: CAFEnv -> CmmDecl -> (CAFSet, CmmDecl)
bundleCAFs cafEnv t@(CmmProc _ _ (CmmGraph {g_entry=entry})) =
(expectJust "bundleCAFs" (mapLookup entry cafEnv), t)
bundleCAFs _ t = (Map.empty, t)
setInfoTableSRT :: Map CLabel CAFSet -> TopSRT -> (CAFSet, CmmDecl) ->
FuelUniqSM (TopSRT, [CmmDecl])
setInfoTableSRT topCAFMap topSRT (cafs, t) =
setSRT cafs topCAFMap topSRT t
setSRT :: CAFSet -> Map CLabel CAFSet -> TopSRT ->
CmmDecl -> FuelUniqSM (TopSRT, [CmmDecl])
setSRT cafs topCAFMap topSRT t =
do (topSRT, cafTable, srt) <- buildSRTs topSRT topCAFMap cafs
let t' = updInfo id (const srt) t
case cafTable of
Just tbl -> return (topSRT, [t', tbl])
Nothing -> return (topSRT, [t'])
type StackLayout = Liveness
updInfo :: (StackLayout -> StackLayout) -> (C_SRT -> C_SRT) -> CmmDecl -> CmmDecl
updInfo toVars toSrt (CmmProc top_info top_l g) =
CmmProc (top_info {info_tbl=updInfoTbl toVars toSrt (info_tbl top_info)}) top_l g
updInfo _ _ t = t
updInfoTbl :: (StackLayout -> StackLayout) -> (C_SRT -> C_SRT) -> CmmInfoTable -> CmmInfoTable
updInfoTbl toVars toSrt info_tbl@(CmmInfoTable {})
= info_tbl { cit_srt = toSrt (cit_srt info_tbl)
, cit_rep = case cit_rep info_tbl of
StackRep ls -> StackRep (toVars ls)
other -> other }
updInfoTbl _ _ t@CmmNonInfoTable = t
lowerSafeForeignCalls :: AreaMap -> CmmDecl -> FuelUniqSM CmmDecl
lowerSafeForeignCalls _ t@(CmmData _ _) = return t
lowerSafeForeignCalls areaMap (CmmProc info l g@(CmmGraph {g_entry=entry})) = do
let block b mblocks = mblocks >>= lowerSafeCallBlock entry areaMap b
blocks <- foldGraphBlocks block (return mapEmpty) g
return $ CmmProc info l (ofBlockMap entry blocks)
lowerSafeCallBlock :: BlockId -> AreaMap -> CmmBlock -> BlockEnv CmmBlock
-> FuelUniqSM (BlockEnv CmmBlock)
lowerSafeCallBlock entry areaMap b blocks =
case blockToNodeList b of
(JustC (CmmEntry id), m, JustC l@(CmmForeignCall {})) -> lowerSafeForeignCall entry areaMap blocks id m l
_ -> return $ insertBlock b blocks
lowerSafeForeignCall :: BlockId -> AreaMap -> BlockEnv CmmBlock -> BlockId -> [CmmNode O O] -> CmmNode O C
-> FuelUniqSM (BlockEnv CmmBlock)
lowerSafeForeignCall entry areaMap blocks bid m
(CmmForeignCall {tgt=tgt, res=rs, args=as, succ=succ, updfr = updfr_off, intrbl = intrbl}) =
do let newTemp rep = getUniqueM >>= \u -> return (LocalReg u rep)
id <- newTemp bWord
new_base <- newTemp (cmmRegType (CmmGlobal BaseReg))
let (caller_save, caller_load) = callerSaveVolatileRegs
load_tso <- newTemp gcWord
load_stack <- newTemp gcWord
let (<**>) = (M.<*>)
let suspendThread = foreignLbl "suspendThread"
resumeThread = foreignLbl "resumeThread"
foreignLbl name = CmmLit (CmmLabel (mkCmmCodeLabel rtsPackageId (fsLit name)))
suspend = saveThreadState <**>
caller_save <**>
mkUnsafeCall (ForeignTarget suspendThread
(ForeignConvention CCallConv [AddrHint, NoHint] [AddrHint]))
[id] [CmmReg (CmmGlobal BaseReg), CmmLit (CmmInt (fromIntegral (fromEnum intrbl)) wordWidth)]
midCall = mkUnsafeCall tgt rs as
resume = mkUnsafeCall (ForeignTarget resumeThread
(ForeignConvention CCallConv [AddrHint] [AddrHint]))
[new_base] [CmmReg (CmmLocal id)] <**>
mkAssign (CmmGlobal BaseReg) (CmmReg (CmmLocal new_base)) <**>
caller_load <**>
loadThreadState load_tso load_stack
saveRetVals = foldl (<**>) emptyAGraph $ map (M.mkMiddle . spill) rs
spill r = CmmStore (regSlot r) (CmmReg $ CmmLocal r)
regSlot r@(LocalReg _ _) = CmmRegOff (CmmGlobal Sp) (sp_off offset)
where offset = w + expectJust "lowerForeign" (Map.lookup (RegSlot r) areaMap)
sp_off = wORD_SIZE + expectJust "lowerForeign" (Map.lookup (CallArea area) areaMap)
area = if succ == entry then Old else Young succ
w = widthInBytes $ typeWidth $ localRegType r
succLbl = CmmLit (CmmLabel (infoTblLbl succ))
jump = CmmCall { cml_target = succLbl, cml_cont = Nothing
, cml_args = widthInBytes wordWidth ,cml_ret_args = 0
, cml_ret_off = updfr_off}
graph' <- liftUniq $ labelAGraph bid $ catAGraphs (map M.mkMiddle m) <**>
suspend <**> midCall <**>
resume <**> saveRetVals <**> M.mkLast jump
return $ blocks `mapUnion` toBlockMap graph'
lowerSafeForeignCall _ _ _ _ _ _ = panic "lowerSafeForeignCall was passed something else"