import MachRegs
import MachCodeGen
import PprMach
-import RegisterAlloc
import RegAllocInfo
import NCGMonad
import PositionIndependentCode
+import RegLiveness
+import RegCoalesce
+import qualified RegAllocLinear as Linear
+import qualified RegAllocColor as Color
+import qualified RegAllocStats as Color
+import qualified GraphColor as Color
import Cmm
import CmmOpt ( cmmMiniInline, cmmMachOpFold )
-import PprCmm ( pprStmt, pprCmms )
+import PprCmm ( pprStmt, pprCmms, pprCmm )
import MachOp
import CLabel
import StaticFlags ( opt_Static, opt_PIC )
import Util
import Config ( cProjectVersion )
+import Module
import Digraph
import qualified Pretty
import Outputable
import FastString
+import UniqSet
-- DEBUGGING ONLY
--import OrdList
-#ifdef NCG_DEBUG
-import List ( intersperse )
-#endif
-
+import Data.List
import Data.Int
import Data.Word
import Data.Bits
+import Data.Maybe
import GHC.Exts
+import Control.Monad
{-
The native-code generator has machine-independent and
-- NB. We *lazilly* compile each block of code for space reasons.
-nativeCodeGen :: DynFlags -> [RawCmm] -> UniqSupply -> IO Pretty.Doc
-nativeCodeGen dflags cmms us
+--------------------
+nativeCodeGen :: DynFlags -> Module -> ModLocation -> [RawCmm] -> UniqSupply -> IO Pretty.Doc
+nativeCodeGen dflags mod modLocation cmms us
= let (res, _) = initUs us $
cgCmm (concat (map add_split cmms))
- cgCmm :: [RawCmmTop] -> UniqSM (RawCmm, Pretty.Doc, [CLabel])
+ cgCmm :: [RawCmmTop] -> UniqSM ( [CmmNativeGenDump], Pretty.Doc, [CLabel])
cgCmm tops =
lazyMapUs (cmmNativeGen dflags) tops `thenUs` \ results ->
- case unzip3 results of { (cmms,docs,imps) ->
- returnUs (Cmm cmms, my_vcat docs, concat imps)
+ case unzip3 results of { (dump,docs,imps) ->
+ returnUs (dump, my_vcat docs, concat imps)
}
in
- case res of { (ppr_cmms, insn_sdoc, imports) -> do
- dumpIfSet_dyn dflags Opt_D_dump_opt_cmm "Optimised Cmm" (pprCmms [ppr_cmms])
+ case res of { (dump, insn_sdoc, imports) -> do
+
+ cmmNativeGenDump dflags mod modLocation dump
+
return (insn_sdoc Pretty.$$ dyld_stubs imports
+
#if HAVE_SUBSECTIONS_VIA_SYMBOLS
-- On recent versions of Darwin, the linker supports
-- dead-stripping of code and data on a per-symbol basis.
#endif
--- Complete native code generation phase for a single top-level chunk
--- of Cmm.
-
-cmmNativeGen :: DynFlags -> RawCmmTop -> UniqSM (RawCmmTop, Pretty.Doc, [CLabel])
+-- Carries output of the code generator passes, for dumping.
+-- Make sure to only fill the one's we're interested in to avoid
+-- creating space leaks.
+
+data CmmNativeGenDump
+ = CmmNativeGenDump
+ { cdCmmOpt :: RawCmmTop
+ , cdNative :: [NatCmmTop]
+ , cdLiveness :: [LiveCmmTop]
+ , cdCoalesce :: Maybe [LiveCmmTop]
+ , cdRegAllocStats :: Maybe [Color.RegAllocStats]
+ , cdRegAllocStatsLinear :: [Linear.RegAllocStats]
+ , cdColoredGraph :: Maybe (Color.Graph Reg RegClass Reg)
+ , cdAlloced :: [NatCmmTop] }
+
+dchoose dflags opt a b
+ | dopt opt dflags = a
+ | otherwise = b
+
+dchooses dflags opts a b
+ | or $ map ( (flip dopt) dflags) opts = a
+ | otherwise = b
+
+-- | Complete native code generation phase for a single top-level chunk of Cmm.
+-- Unless they're being dumped, intermediate data structures are squashed after
+-- every stage to avoid creating space leaks.
+--
+-- TODO: passing data via CmmNativeDump/squashing structs has become a horrible mess.
+-- it might be better to forgo trying to keep all the outputs for each
+-- stage together and just thread IO() through cmmNativeGen so we can dump
+-- what we want to after each stage.
+--
+cmmNativeGen :: DynFlags -> RawCmmTop -> UniqSM (CmmNativeGenDump, Pretty.Doc, [CLabel])
cmmNativeGen dflags cmm
- = {-# SCC "fixAssigns" #-}
- fixAssignsTop cmm `thenUs` \ fixed_cmm ->
- {-# SCC "genericOpt" #-}
- cmmToCmm fixed_cmm `bind` \ (cmm, imports) ->
- (if dopt Opt_D_dump_opt_cmm dflags -- space leak avoidance
- then cmm
- else CmmData Text []) `bind` \ ppr_cmm ->
- {-# SCC "genMachCode" #-}
- genMachCode cmm `thenUs` \ (pre_regalloc, lastMinuteImports) ->
- {-# SCC "regAlloc" #-}
- mapUs regAlloc pre_regalloc `thenUs` \ with_regs ->
- {-# SCC "shortcutBranches" #-}
- shortcutBranches dflags with_regs `bind` \ shorted ->
- {-# SCC "sequenceBlocks" #-}
- map sequenceTop shorted `bind` \ sequenced ->
- {-# SCC "x86fp_kludge" #-}
- map x86fp_kludge sequenced `bind` \ final_mach_code ->
- {-# SCC "vcat" #-}
- Pretty.vcat (map pprNatCmmTop final_mach_code) `bind` \ final_sdoc ->
-
- returnUs (ppr_cmm, final_sdoc Pretty.$$ Pretty.text "", lastMinuteImports ++ imports)
- where
- x86fp_kludge :: NatCmmTop -> NatCmmTop
- x86fp_kludge top@(CmmData _ _) = top
+ = do
+ --
+ fixed_cmm
+ <- {-# SCC "fixAssigns" #-}
+ fixAssignsTop cmm
+
+ ---- cmm to cmm optimisations
+ (cmm, imports, ppr_cmm)
+ <- (\fixed_cmm
+ -> {-# SCC "genericOpt" #-}
+ do let (cmm, imports) = cmmToCmm dflags fixed_cmm
+
+ return ( cmm
+ , imports
+ , dchoose dflags Opt_D_dump_cmm cmm (CmmData Text []))
+ ) fixed_cmm
+
+
+ ---- generate native code from cmm
+ (native, lastMinuteImports, ppr_native)
+ <- (\cmm
+ -> {-# SCC "genMachCode" #-}
+ do (machCode, lastMinuteImports)
+ <- genMachCode dflags cmm
+
+ return ( machCode
+ , lastMinuteImports
+ , dchoose dflags Opt_D_dump_asm_native machCode [])
+ ) cmm
+
+
+ ---- tag instructions with register liveness information
+ (withLiveness, ppr_withLiveness)
+ <- (\native
+ -> {-# SCC "regLiveness" #-}
+ do
+ withLiveness <- mapUs regLiveness native
+
+ return ( withLiveness
+ , dchoose dflags Opt_D_dump_asm_liveness withLiveness []))
+ native
+
+ ---- allocate registers
+ ( alloced, ppr_alloced, ppr_coalesce
+ , ppr_regAllocStats, ppr_regAllocStatsLinear, ppr_coloredGraph)
+ <- (\withLiveness
+ -> {-# SCC "regAlloc" #-}
+ do
+ if dopt Opt_RegsGraph dflags
+ then do
+ -- the regs usable for allocation
+ let alloc_regs
+ = foldr (\r -> plusUFM_C unionUniqSets
+ $ unitUFM (regClass r) (unitUniqSet r))
+ emptyUFM
+ $ map RealReg allocatableRegs
+
+ -- aggressively coalesce moves between virtual regs
+ coalesced <- regCoalesce withLiveness
+
+ -- graph coloring register allocation
+ (alloced, regAllocStats)
+ <- Color.regAlloc
+ alloc_regs
+ (mkUniqSet [0..maxSpillSlots])
+ coalesced
+
+ return ( alloced
+ , dchoose dflags Opt_D_dump_asm_regalloc
+ alloced []
+ , dchoose dflags Opt_D_dump_asm_coalesce
+ (Just coalesced) Nothing
+ , dchooses dflags
+ [ Opt_D_dump_asm_regalloc_stages
+ , Opt_D_drop_asm_stats]
+ (Just regAllocStats) Nothing
+ , []
+ , dchoose dflags Opt_D_dump_asm_conflicts
+ Nothing Nothing)
+
+ else do
+ -- do linear register allocation
+ (alloced, stats)
+ <- liftM unzip
+ $ mapUs Linear.regAlloc withLiveness
+
+ return ( alloced
+ , dchoose dflags Opt_D_dump_asm_regalloc
+ alloced []
+ , Nothing
+ , Nothing
+ , dchoose dflags Opt_D_drop_asm_stats
+ (catMaybes stats) []
+ , Nothing ))
+ withLiveness
+
+
+ ---- shortcut branches
+ let shorted =
+ {-# SCC "shortcutBranches" #-}
+ shortcutBranches dflags alloced
+
+ ---- sequence blocks
+ let sequenced =
+ {-# SCC "sequenceBlocks" #-}
+ map sequenceTop shorted
+
+ ---- x86fp_kludge
+ let final_mach_code =
#if i386_TARGET_ARCH
- x86fp_kludge top@(CmmProc info lbl params code) =
- CmmProc info lbl params (map bb_i386_insert_ffrees code)
- where
- bb_i386_insert_ffrees (BasicBlock id instrs) =
- BasicBlock id (i386_insert_ffrees instrs)
+ {-# SCC "x86fp_kludge" #-}
+ map x86fp_kludge sequenced
#else
- x86fp_kludge top = top
+ sequenced
#endif
+
+ ---- vcat
+ let final_sdoc =
+ {-# SCC "vcat" #-}
+ Pretty.vcat (map pprNatCmmTop final_mach_code)
+
+ let dump =
+ CmmNativeGenDump
+ { cdCmmOpt = ppr_cmm
+ , cdNative = ppr_native
+ , cdLiveness = ppr_withLiveness
+ , cdCoalesce = ppr_coalesce
+ , cdRegAllocStats = ppr_regAllocStats
+ , cdRegAllocStatsLinear = ppr_regAllocStatsLinear
+ , cdColoredGraph = ppr_coloredGraph
+ , cdAlloced = ppr_alloced }
+
+ returnUs (dump, final_sdoc Pretty.$$ Pretty.text "", lastMinuteImports ++ imports)
+
+#if i386_TARGET_ARCH
+x86fp_kludge :: NatCmmTop -> NatCmmTop
+x86fp_kludge top@(CmmData _ _) = top
+x86fp_kludge top@(CmmProc info lbl params code) =
+ CmmProc info lbl params (map bb_i386_insert_ffrees code)
+ where
+ bb_i386_insert_ffrees (BasicBlock id instrs) =
+ BasicBlock id (i386_insert_ffrees instrs)
+#endif
+
+
+-- Dump output of native code generator passes
+-- stripe across the outputs for each block so all the information for a
+-- certain stage is concurrent in the dumps.
+--
+cmmNativeGenDump :: DynFlags -> Module -> ModLocation -> [CmmNativeGenDump] -> IO ()
+cmmNativeGenDump dflags mod modLocation dump
+ = do
+ dumpIfSet_dyn dflags
+ Opt_D_dump_opt_cmm "Optimised Cmm"
+ (pprCmm $ Cmm $ map cdCmmOpt dump)
+
+ dumpIfSet_dyn dflags
+ Opt_D_dump_asm_native "Native code"
+ (vcat $ map (docToSDoc . pprNatCmmTop) $ concatMap cdNative dump)
+
+ dumpIfSet_dyn dflags
+ Opt_D_dump_asm_liveness "Liveness annotations added"
+ (vcat $ map (ppr . cdLiveness) dump)
+
+ dumpIfSet_dyn dflags
+ Opt_D_dump_asm_coalesce "Reg-Reg moves coalesced"
+ (vcat $ map (fromMaybe empty . liftM ppr . cdCoalesce) dump)
+
+ dumpIfSet_dyn dflags
+ Opt_D_dump_asm_regalloc "Registers allocated"
+ (vcat $ map (docToSDoc . pprNatCmmTop) $ concatMap cdAlloced dump)
+
+ -- with the graph coloring allocator, show the result of each build/spill stage
+ -- for each block in turn.
+ when (dopt Opt_D_dump_asm_regalloc_stages dflags)
+ $ do mapM_ (\stats
+ -> printDump
+ $ vcat $ map (\(stage, stats) ->
+ text "-- Stage " <> int stage
+ $$ ppr stats)
+ (zip [0..] stats))
+ $ map (fromMaybe [] . cdRegAllocStats) dump
+
+ -- Build a global register conflict graph.
+ -- If you want to see the graph for just one basic block then use asm-regalloc-stages instead.
+ dumpIfSet_dyn dflags
+ Opt_D_dump_asm_conflicts "Register conflict graph"
+ $ Color.dotGraph Color.regDotColor trivColorable
+ $ foldl Color.union Color.initGraph
+ $ catMaybes $ map cdColoredGraph dump
+
+ -- Drop native code generator statistics.
+ -- This is potentially a large amount of information, and we want to be able
+ -- to collect it while running nofib. Drop a new file instead of emitting
+ -- it to stdout/stderr.
+ --
+ when (dopt Opt_D_drop_asm_stats dflags)
+ $ do -- make the drop file name based on the object file name
+ let dropFile = (init $ ml_obj_file modLocation) ++ "drop-asm-stats"
+
+ -- slurp out all the regalloc stats
+ let stats = concat $ catMaybes $ map cdRegAllocStats dump
+
+ -- build a global conflict graph
+ let graph = foldl Color.union Color.initGraph $ map Color.raGraph stats
+
+ -- pretty print the various sections and write out the file.
+ let outSpills = Color.pprStatsSpills stats
+ let outLife = Color.pprStatsLifetimes stats
+ let outConflict = Color.pprStatsConflict stats
+ let outScatter = Color.pprStatsLifeConflict stats graph
+
+ writeFile dropFile
+ (showSDoc $ vcat [outSpills, outLife, outConflict, outScatter])
+
+ return ()
-- -----------------------------------------------------------------------------
-- Sequencing the basic blocks
-- Switching between the two monads whilst carrying along the same
-- Unique supply breaks abstraction. Is that bad?
-genMachCode :: RawCmmTop -> UniqSM ([NatCmmTop], [CLabel])
+genMachCode :: DynFlags -> RawCmmTop -> UniqSM ([NatCmmTop], [CLabel])
-genMachCode cmm_top
+genMachCode dflags cmm_top
= do { initial_us <- getUs
- ; let initial_st = mkNatM_State initial_us 0
+ ; let initial_st = mkNatM_State initial_us 0 dflags
(new_tops, final_st) = initNat initial_st (cmmTopCodeGen cmm_top)
final_delta = natm_delta final_st
final_imports = natm_imports final_st
temp assignments, and certain assigns to mem...)
-}
-cmmToCmm :: RawCmmTop -> (RawCmmTop, [CLabel])
-cmmToCmm top@(CmmData _ _) = (top, [])
-cmmToCmm (CmmProc info lbl params blocks) = runCmmOpt $ do
+cmmToCmm :: DynFlags -> RawCmmTop -> (RawCmmTop, [CLabel])
+cmmToCmm _ top@(CmmData _ _) = (top, [])
+cmmToCmm dflags (CmmProc info lbl params blocks) = runCmmOpt dflags $ do
blocks' <- mapM cmmBlockConFold (cmmMiniInline blocks)
return $ CmmProc info lbl params blocks'
-newtype CmmOptM a = CmmOptM ([CLabel] -> (# a, [CLabel] #))
+newtype CmmOptM a = CmmOptM (([CLabel], DynFlags) -> (# a, [CLabel] #))
instance Monad CmmOptM where
- return x = CmmOptM $ \imports -> (# x,imports #)
+ return x = CmmOptM $ \(imports, _) -> (# x,imports #)
(CmmOptM f) >>= g =
- CmmOptM $ \imports ->
- case f imports of
+ CmmOptM $ \(imports, dflags) ->
+ case f (imports, dflags) of
(# x, imports' #) ->
case g x of
- CmmOptM g' -> g' imports'
+ CmmOptM g' -> g' (imports', dflags)
addImportCmmOpt :: CLabel -> CmmOptM ()
-addImportCmmOpt lbl = CmmOptM $ \imports -> (# (), lbl:imports #)
+addImportCmmOpt lbl = CmmOptM $ \(imports, dflags) -> (# (), lbl:imports #)
+
+getDynFlagsCmmOpt :: CmmOptM DynFlags
+getDynFlagsCmmOpt = CmmOptM $ \(imports, dflags) -> (# dflags, imports #)
-runCmmOpt :: CmmOptM a -> (a, [CLabel])
-runCmmOpt (CmmOptM f) = case f [] of
+runCmmOpt :: DynFlags -> CmmOptM a -> (a, [CLabel])
+runCmmOpt dflags (CmmOptM f) = case f ([], dflags) of
(# result, imports #) -> (result, imports)
cmmBlockConFold :: CmmBasicBlock -> CmmOptM CmmBasicBlock
-> do addr' <- cmmExprConFold JumpReference addr
return $ CmmJump addr' regs
- CmmCall target regs args srt
+ CmmCall target regs args srt returns
-> do target' <- case target of
- CmmForeignCall e conv -> do
+ CmmCallee e conv -> do
e' <- cmmExprConFold CallReference e
- return $ CmmForeignCall e' conv
+ return $ CmmCallee e' conv
other -> return other
args' <- mapM (\(arg, hint) -> do
arg' <- cmmExprConFold DataReference arg
return (arg', hint)) args
- return $ CmmCall target' regs args' srt
+ return $ CmmCall target' regs args' srt returns
CmmCondBranch test dest
-> do test' <- cmmExprConFold DataReference test
return $ cmmMachOpFold mop args'
CmmLit (CmmLabel lbl)
- -> cmmMakeDynamicReference addImportCmmOpt referenceKind lbl
+ -> do
+ dflags <- getDynFlagsCmmOpt
+ cmmMakeDynamicReference dflags addImportCmmOpt referenceKind lbl
CmmLit (CmmLabelOff lbl off)
- -> do dynRef <- cmmMakeDynamicReference addImportCmmOpt referenceKind lbl
+ -> do
+ dflags <- getDynFlagsCmmOpt
+ dynRef <- cmmMakeDynamicReference dflags addImportCmmOpt referenceKind lbl
return $ cmmMachOpFold (MO_Add wordRep) [
dynRef,
(CmmLit $ CmmInt (fromIntegral off) wordRep)