compiler/nativeGen/AsmCodeGen.lhs

   1 -- -----------------------------------------------------------------------------
   2 --
   3 -- (c) The University of Glasgow 1993-2004
   4 --
   5 -- This is the top-level module in the native code generator.
   6 --
   7 -- -----------------------------------------------------------------------------
   8
   9 \begin{code}
  10 module AsmCodeGen ( nativeCodeGen ) where
  11
  12 #include "HsVersions.h"
  13 #include "nativeGen/NCG.h"
  14
  15 import MachInstrs
  16 import MachRegs
  17 import MachCodeGen
  18 import PprMach
  19 import RegAllocInfo
  20 import NCGMonad
  21 import PositionIndependentCode
  22 import RegLiveness
  23 import RegCoalesce
  24 import qualified RegAllocLinear as Linear
  25 import qualified RegAllocColor  as Color
  26 import qualified RegAllocStats  as Color
  27 import qualified GraphColor     as Color
  28
  29 import Cmm
  30 import CmmOpt           ( cmmMiniInline, cmmMachOpFold )
  31 import PprCmm           ( pprStmt, pprCmms, pprCmm )
  32 import MachOp
  33 import CLabel
  34
  35 import UniqFM
  36 import Unique           ( Unique, getUnique )
  37 import UniqSupply
  38 import FastTypes
  39 import List             ( groupBy, sortBy )
  40 import ErrUtils         ( dumpIfSet_dyn )
  41 import DynFlags
  42 import StaticFlags      ( opt_Static, opt_PIC )
  43 import Util
  44 import Config           ( cProjectVersion )
  45 import Module
  46
  47 import Digraph
  48 import qualified Pretty
  49 import Outputable
  50 import FastString
  51 import UniqSet
  52
  53 -- DEBUGGING ONLY
  54 --import OrdList
  55
  56 import Data.List
  57 import Data.Int
  58 import Data.Word
  59 import Data.Bits
  60 import Data.Maybe
  61 import GHC.Exts
  62 import Control.Monad
  63
  64 {-
  65 The native-code generator has machine-independent and
  66 machine-dependent modules.
  67
  68 This module ("AsmCodeGen") is the top-level machine-independent
  69 module.  Before entering machine-dependent land, we do some
  70 machine-independent optimisations (defined below) on the
  71 'CmmStmts's.
  72
  73 We convert to the machine-specific 'Instr' datatype with
  74 'cmmCodeGen', assuming an infinite supply of registers.  We then use
  75 a machine-independent register allocator ('regAlloc') to rejoin
  76 reality.  Obviously, 'regAlloc' has machine-specific helper
  77 functions (see about "RegAllocInfo" below).
  78
  79 Finally, we order the basic blocks of the function so as to minimise
  80 the number of jumps between blocks, by utilising fallthrough wherever
  81 possible.
  82
  83 The machine-dependent bits break down as follows:
  84
  85   * ["MachRegs"]  Everything about the target platform's machine
  86     registers (and immediate operands, and addresses, which tend to
  87     intermingle/interact with registers).
  88
  89   * ["MachInstrs"]  Includes the 'Instr' datatype (possibly should
  90     have a module of its own), plus a miscellany of other things
  91     (e.g., 'targetDoubleSize', 'smStablePtrTable', ...)
  92
  93   * ["MachCodeGen"]  is where 'Cmm' stuff turns into
  94     machine instructions.
  95
  96   * ["PprMach"] 'pprInstr' turns an 'Instr' into text (well, really
  97     a 'Doc').
  98
  99   * ["RegAllocInfo"] In the register allocator, we manipulate
 100     'MRegsState's, which are 'BitSet's, one bit per machine register.
 101     When we want to say something about a specific machine register
 102     (e.g., ``it gets clobbered by this instruction''), we set/unset
 103     its bit.  Obviously, we do this 'BitSet' thing for efficiency
 104     reasons.
 105
 106     The 'RegAllocInfo' module collects together the machine-specific
 107     info needed to do register allocation.
 108
 109    * ["RegisterAlloc"] The (machine-independent) register allocator.
 110 -}
 111
 112 -- -----------------------------------------------------------------------------
 113 -- Top-level of the native codegen
 114
 115 -- NB. We *lazilly* compile each block of code for space reasons.
 116
 117 --------------------
 118 nativeCodeGen :: DynFlags -> Module -> ModLocation -> [RawCmm] -> UniqSupply -> IO Pretty.Doc
 119 nativeCodeGen dflags mod modLocation cmms us
 120   = let (res, _) = initUs us $
 121            cgCmm (concat (map add_split cmms))
 122
 123         cgCmm :: [RawCmmTop] -> UniqSM ( [CmmNativeGenDump], Pretty.Doc, [CLabel])
 124         cgCmm tops =
 125            lazyMapUs (cmmNativeGen dflags) tops  `thenUs` \ results ->
 126            case unzip3 results of { (dump,docs,imps) ->
 127            returnUs (dump, my_vcat docs, concat imps)
 128            }
 129     in
 130     case res of { (dump, insn_sdoc, imports) -> do
 131
 132     cmmNativeGenDump dflags mod modLocation dump
 133
 134     return (insn_sdoc Pretty.$$ dyld_stubs imports
 135
 136 #if HAVE_SUBSECTIONS_VIA_SYMBOLS
 137                 -- On recent versions of Darwin, the linker supports
 138                 -- dead-stripping of code and data on a per-symbol basis.
 139                 -- There's a hack to make this work in PprMach.pprNatCmmTop.
 140             Pretty.$$ Pretty.text ".subsections_via_symbols"
 141 #endif
 142 #if HAVE_GNU_NONEXEC_STACK
 143                 -- On recent GNU ELF systems one can mark an object file
 144                 -- as not requiring an executable stack. If all objects
 145                 -- linked into a program have this note then the program
 146                 -- will not use an executable stack, which is good for
 147                 -- security. GHC generated code does not need an executable
 148                 -- stack so add the note in:
 149             Pretty.$$ Pretty.text ".section .note.GNU-stack,\"\",@progbits"
 150 #endif
 151 #if !defined(darwin_TARGET_OS)
 152                 -- And just because every other compiler does, lets stick in
 153                 -- an identifier directive: .ident "GHC x.y.z"
 154             Pretty.$$ let compilerIdent = Pretty.text "GHC" Pretty.<+>
 155                                           Pretty.text cProjectVersion
 156                        in Pretty.text ".ident" Pretty.<+>
 157                           Pretty.doubleQuotes compilerIdent
 158 #endif
 159             )
 160    }
 161
 162   where
 163
 164     add_split (Cmm tops)
 165         | dopt Opt_SplitObjs dflags = split_marker : tops
 166         | otherwise                 = tops
 167
 168     split_marker = CmmProc [] mkSplitMarkerLabel [] []
 169
 170          -- Generate "symbol stubs" for all external symbols that might
 171          -- come from a dynamic library.
 172 {-    dyld_stubs imps = Pretty.vcat $ map pprDyldSymbolStub $
 173                                     map head $ group $ sort imps-}
 174
 175         -- (Hack) sometimes two Labels pretty-print the same, but have
 176         -- different uniques; so we compare their text versions...
 177     dyld_stubs imps
 178         | needImportedSymbols
 179           = Pretty.vcat $
 180             (pprGotDeclaration :) $
 181             map (pprImportedSymbol . fst . head) $
 182             groupBy (\(_,a) (_,b) -> a == b) $
 183             sortBy (\(_,a) (_,b) -> compare a b) $
 184             map doPpr $
 185             imps
 186         | otherwise
 187           = Pretty.empty
 188
 189         where doPpr lbl = (lbl, Pretty.render $ pprCLabel lbl astyle)
 190               astyle = mkCodeStyle AsmStyle
 191
 192 #ifndef NCG_DEBUG
 193     my_vcat sds = Pretty.vcat sds
 194 #else
 195     my_vcat sds = Pretty.vcat (
 196                       intersperse (
 197                          Pretty.char ' '
 198                             Pretty.$$ Pretty.ptext SLIT("# ___ncg_debug_marker")
 199                             Pretty.$$ Pretty.char ' '
 200                       )
 201                       sds
 202                    )
 203 #endif
 204
 205
 206 -- Carries output of the code generator passes, for dumping.
 207 --      Make sure to only fill the one's we're interested in to avoid
 208 --      creating space leaks.
 209
 210 data CmmNativeGenDump
 211         = CmmNativeGenDump
 212         { cdCmmOpt              :: RawCmmTop
 213         , cdNative              :: [NatCmmTop]
 214         , cdLiveness            :: [LiveCmmTop]
 215         , cdCoalesce            :: Maybe [LiveCmmTop]
 216         , cdRegAllocStats       :: Maybe [Color.RegAllocStats]
 217         , cdRegAllocStatsLinear :: [Linear.RegAllocStats]
 218         , cdColoredGraph        :: Maybe (Color.Graph Reg RegClass Reg)
 219         , cdAlloced             :: [NatCmmTop] }
 220
 221 dchoose dflags opt a b
 222         | dopt opt dflags       = a
 223         | otherwise             = b
 224
 225 dchooses dflags opts a b
 226         | or $ map ( (flip dopt) dflags) opts   = a
 227         | otherwise             = b
 228
 229 -- | Complete native code generation phase for a single top-level chunk of Cmm.
 230 --      Unless they're being dumped, intermediate data structures are squashed after
 231 --      every stage to avoid creating space leaks.
 232 --
 233 -- TODO: passing data via CmmNativeDump/squashing structs has become a horrible mess.
 234 --       it might be better to forgo trying to keep all the outputs for each
 235 --       stage together and just thread IO() through cmmNativeGen so we can dump
 236 --       what we want to after each stage.
 237 --
 238 cmmNativeGen :: DynFlags -> RawCmmTop -> UniqSM (CmmNativeGenDump, Pretty.Doc, [CLabel])
 239 cmmNativeGen dflags cmm
 240  = do
 241         --
 242         fixed_cmm
 243          <-     {-# SCC "fixAssigns"  #-}
 244                 fixAssignsTop cmm
 245
 246         ---- cmm to cmm optimisations
 247         (cmm, imports, ppr_cmm)
 248          <- (\fixed_cmm
 249          -> {-# SCC "genericOpt"  #-}
 250            do   let (cmm, imports)      = cmmToCmm dflags fixed_cmm
 251
 252                 return  ( cmm
 253                         , imports
 254                         , dchoose dflags Opt_D_dump_cmm cmm (CmmData Text []))
 255              ) fixed_cmm
 256
 257
 258         ---- generate native code from cmm
 259         (native, lastMinuteImports, ppr_native)
 260          <- (\cmm
 261          -> {-# SCC "genMachCode" #-}
 262            do   (machCode, lastMinuteImports)
 263                         <- genMachCode dflags cmm
 264
 265                 return  ( machCode
 266                         , lastMinuteImports
 267                         , dchoose dflags Opt_D_dump_asm_native machCode [])
 268             ) cmm
 269
 270
 271         ---- tag instructions with register liveness information
 272         (withLiveness, ppr_withLiveness)
 273          <- (\native
 274          -> {-# SCC "regLiveness" #-}
 275            do
 276                 withLiveness    <- mapUs regLiveness native
 277
 278                 return  ( withLiveness
 279                         , dchoose dflags Opt_D_dump_asm_liveness withLiveness []))
 280                 native
 281
 282         ---- allocate registers
 283         (  alloced, ppr_alloced, ppr_coalesce
 284          , ppr_regAllocStats, ppr_regAllocStatsLinear, ppr_coloredGraph)
 285          <- (\withLiveness
 286          -> {-# SCC "regAlloc" #-}
 287            do
 288                 if dopt Opt_RegsGraph dflags
 289                  then do
 290                         -- the regs usable for allocation
 291                         let alloc_regs
 292                                 = foldr (\r -> plusUFM_C unionUniqSets
 293                                                         $ unitUFM (regClass r) (unitUniqSet r))
 294                                         emptyUFM
 295                                 $ map RealReg allocatableRegs
 296
 297                         -- aggressively coalesce moves between virtual regs
 298                         coalesced       <- regCoalesce withLiveness
 299
 300                         -- graph coloring register allocation
 301                         (alloced, regAllocStats)
 302                                 <- Color.regAlloc
 303                                         alloc_regs
 304                                         (mkUniqSet [0..maxSpillSlots])
 305                                         coalesced
 306
 307                         return  ( alloced
 308                                 , dchoose  dflags Opt_D_dump_asm_regalloc
 309                                         alloced []
 310                                 , dchoose  dflags Opt_D_dump_asm_coalesce
 311                                         (Just coalesced)     Nothing
 312                                 , dchooses dflags
 313                                         [ Opt_D_dump_asm_regalloc_stages
 314                                         , Opt_D_drop_asm_stats]
 315                                         (Just regAllocStats) Nothing
 316                                 , []
 317                                 , dchoose  dflags Opt_D_dump_asm_conflicts
 318                                         Nothing Nothing)
 319
 320                  else do
 321                         -- do linear register allocation
 322                         (alloced, stats)
 323                                 <- liftM unzip
 324                                 $ mapUs Linear.regAlloc withLiveness
 325
 326                         return  ( alloced
 327                                 , dchoose dflags Opt_D_dump_asm_regalloc
 328                                         alloced []
 329                                 , Nothing
 330                                 , Nothing
 331                                 , dchoose dflags Opt_D_drop_asm_stats
 332                                         (catMaybes stats) []
 333                                 , Nothing ))
 334                 withLiveness
 335
 336
 337         ---- shortcut branches
 338         let shorted     =
 339                 {-# SCC "shortcutBranches" #-}
 340                 shortcutBranches dflags alloced
 341
 342         ---- sequence blocks
 343         let sequenced   =
 344                 {-# SCC "sequenceBlocks" #-}
 345                 map sequenceTop shorted
 346
 347         ---- x86fp_kludge
 348         let final_mach_code =
 349 #if i386_TARGET_ARCH
 350                 {-# SCC "x86fp_kludge" #-}
 351                 map x86fp_kludge sequenced
 352 #else
 353                 sequenced
 354 #endif
 355
 356         ---- vcat
 357         let final_sdoc  =
 358                 {-# SCC "vcat" #-}
 359                 Pretty.vcat (map pprNatCmmTop final_mach_code)
 360
 361         let dump        =
 362                 CmmNativeGenDump
 363                 { cdCmmOpt              = ppr_cmm
 364                 , cdNative              = ppr_native
 365                 , cdLiveness            = ppr_withLiveness
 366                 , cdCoalesce            = ppr_coalesce
 367                 , cdRegAllocStats       = ppr_regAllocStats
 368                 , cdRegAllocStatsLinear = ppr_regAllocStatsLinear
 369                 , cdColoredGraph        = ppr_coloredGraph
 370                 , cdAlloced             = ppr_alloced }
 371
 372         returnUs (dump, final_sdoc Pretty.$$ Pretty.text "", lastMinuteImports ++ imports)
 373
 374 #if i386_TARGET_ARCH
 375 x86fp_kludge :: NatCmmTop -> NatCmmTop
 376 x86fp_kludge top@(CmmData _ _) = top
 377 x86fp_kludge top@(CmmProc info lbl params code) =
 378         CmmProc info lbl params (map bb_i386_insert_ffrees code)
 379         where
 380                 bb_i386_insert_ffrees (BasicBlock id instrs) =
 381                         BasicBlock id (i386_insert_ffrees instrs)
 382 #endif
 383
 384
 385 -- Dump output of native code generator passes
 386 --      stripe across the outputs for each block so all the information for a
 387 --      certain stage is concurrent in the dumps.
 388 --
 389 cmmNativeGenDump :: DynFlags -> Module -> ModLocation -> [CmmNativeGenDump] -> IO ()
 390 cmmNativeGenDump dflags mod modLocation dump
 391  = do
 392         dumpIfSet_dyn dflags
 393                 Opt_D_dump_opt_cmm "Optimised Cmm"
 394                 (pprCmm $ Cmm $ map cdCmmOpt dump)
 395
 396         dumpIfSet_dyn dflags
 397                 Opt_D_dump_asm_native   "Native code"
 398                 (vcat $ map (docToSDoc . pprNatCmmTop)  $ concatMap cdNative dump)
 399
 400         dumpIfSet_dyn dflags
 401                 Opt_D_dump_asm_liveness "Liveness annotations added"
 402                 (vcat $ map (ppr . cdLiveness) dump)
 403
 404         dumpIfSet_dyn dflags
 405                 Opt_D_dump_asm_coalesce "Reg-Reg moves coalesced"
 406                 (vcat $ map (fromMaybe empty . liftM ppr . cdCoalesce) dump)
 407
 408         dumpIfSet_dyn dflags
 409                 Opt_D_dump_asm_regalloc "Registers allocated"
 410                 (vcat $ map (docToSDoc . pprNatCmmTop) $ concatMap cdAlloced dump)
 411
 412         -- with the graph coloring allocator, show the result of each build/spill stage
 413         --        for each block in turn.
 414         when (dopt Opt_D_dump_asm_regalloc_stages dflags)
 415          $ do   mapM_ (\stats
 416                          -> printDump
 417                          $  vcat $ map (\(stage, stats) ->
 418                                          text "-- Stage " <> int stage
 419                                          $$ ppr stats)
 420                                         (zip [0..] stats))
 421                  $ map (fromMaybe [] . cdRegAllocStats) dump
 422
 423         -- Build a global register conflict graph.
 424         --      If you want to see the graph for just one basic block then use asm-regalloc-stages instead.
 425         dumpIfSet_dyn dflags
 426                 Opt_D_dump_asm_conflicts "Register conflict graph"
 427                 $ Color.dotGraph Color.regDotColor trivColorable
 428                 $ foldl Color.union Color.initGraph
 429                 $ catMaybes $ map cdColoredGraph dump
 430
 431         -- Drop native code generator statistics.
 432         --      This is potentially a large amount of information, and we want to be able
 433         --      to collect it while running nofib. Drop a new file instead of emitting
 434         --      it to stdout/stderr.
 435         --
 436         when (dopt Opt_D_drop_asm_stats dflags)
 437          $ do   -- make the drop file name based on the object file name
 438                 let dropFile    = (init $ ml_obj_file modLocation) ++ "drop-asm-stats"
 439
 440                 -- slurp out all the regalloc stats
 441                 let stats       = concat $ catMaybes $ map cdRegAllocStats dump
 442
 443                 -- build a global conflict graph
 444                 let graph       = foldl Color.union Color.initGraph $ map Color.raGraph stats
 445
 446                 -- pretty print the various sections and write out the file.
 447                 let outSpills   = Color.pprStatsSpills    stats
 448                 let outLife     = Color.pprStatsLifetimes stats
 449                 let outConflict = Color.pprStatsConflict  stats
 450                 let outScatter  = Color.pprStatsLifeConflict stats graph
 451
 452                 writeFile dropFile
 453                         (showSDoc $ vcat [outSpills, outLife, outConflict, outScatter])
 454
 455         return ()
 456
 457 -- -----------------------------------------------------------------------------
 458 -- Sequencing the basic blocks
 459
 460 -- Cmm BasicBlocks are self-contained entities: they always end in a
 461 -- jump, either non-local or to another basic block in the same proc.
 462 -- In this phase, we attempt to place the basic blocks in a sequence
 463 -- such that as many of the local jumps as possible turn into
 464 -- fallthroughs.
 465
 466 sequenceTop :: NatCmmTop -> NatCmmTop
 467 sequenceTop top@(CmmData _ _) = top
 468 sequenceTop (CmmProc info lbl params blocks) =
 469   CmmProc info lbl params (makeFarBranches $ sequenceBlocks blocks)
 470
 471 -- The algorithm is very simple (and stupid): we make a graph out of
 472 -- the blocks where there is an edge from one block to another iff the
 473 -- first block ends by jumping to the second.  Then we topologically
 474 -- sort this graph.  Then traverse the list: for each block, we first
 475 -- output the block, then if it has an out edge, we move the
 476 -- destination of the out edge to the front of the list, and continue.
 477
 478 sequenceBlocks :: [NatBasicBlock] -> [NatBasicBlock]
 479 sequenceBlocks [] = []
 480 sequenceBlocks (entry:blocks) =
 481   seqBlocks (mkNode entry : reverse (flattenSCCs (sccBlocks blocks)))
 482   -- the first block is the entry point ==> it must remain at the start.
 483
 484 sccBlocks :: [NatBasicBlock] -> [SCC (NatBasicBlock,Unique,[Unique])]
 485 sccBlocks blocks = stronglyConnCompR (map mkNode blocks)
 486
 487 getOutEdges :: [Instr] -> [Unique]
 488 getOutEdges instrs = case jumpDests (last instrs) [] of
 489                         [one] -> [getUnique one]
 490                         _many -> []
 491                 -- we're only interested in the last instruction of
 492                 -- the block, and only if it has a single destination.
 493
 494 mkNode block@(BasicBlock id instrs) = (block, getUnique id, getOutEdges instrs)
 495
 496 seqBlocks [] = []
 497 seqBlocks ((block,_,[]) : rest)
 498   = block : seqBlocks rest
 499 seqBlocks ((block@(BasicBlock id instrs),_,[next]) : rest)
 500   | can_fallthrough = BasicBlock id (init instrs) : seqBlocks rest'
 501   | otherwise       = block : seqBlocks rest'
 502   where
 503         (can_fallthrough, rest') = reorder next [] rest
 504           -- TODO: we should do a better job for cycles; try to maximise the
 505           -- fallthroughs within a loop.
 506 seqBlocks _ = panic "AsmCodegen:seqBlocks"
 507
 508 reorder id accum [] = (False, reverse accum)
 509 reorder id accum (b@(block,id',out) : rest)
 510   | id == id'  = (True, (block,id,out) : reverse accum ++ rest)
 511   | otherwise  = reorder id (b:accum) rest
 512
 513
 514 -- -----------------------------------------------------------------------------
 515 -- Making far branches
 516
 517 -- Conditional branches on PowerPC are limited to +-32KB; if our Procs get too
 518 -- big, we have to work around this limitation.
 519
 520 makeFarBranches :: [NatBasicBlock] -> [NatBasicBlock]
 521
 522 #if powerpc_TARGET_ARCH
 523 makeFarBranches blocks
 524     | last blockAddresses < nearLimit = blocks
 525     | otherwise = zipWith handleBlock blockAddresses blocks
 526     where
 527         blockAddresses = scanl (+) 0 $ map blockLen blocks
 528         blockLen (BasicBlock _ instrs) = length instrs
 529
 530         handleBlock addr (BasicBlock id instrs)
 531                 = BasicBlock id (zipWith makeFar [addr..] instrs)
 532
 533         makeFar addr (BCC ALWAYS tgt) = BCC ALWAYS tgt
 534         makeFar addr (BCC cond tgt)
 535             | abs (addr - targetAddr) >= nearLimit
 536             = BCCFAR cond tgt
 537             | otherwise
 538             = BCC cond tgt
 539             where Just targetAddr = lookupUFM blockAddressMap tgt
 540         makeFar addr other            = other
 541
 542         nearLimit = 7000 -- 8192 instructions are allowed; let's keep some
 543                          -- distance, as we have a few pseudo-insns that are
 544                          -- pretty-printed as multiple instructions,
 545                          -- and it's just not worth the effort to calculate
 546                          -- things exactly
 547
 548         blockAddressMap = listToUFM $ zip (map blockId blocks) blockAddresses
 549 #else
 550 makeFarBranches = id
 551 #endif
 552
 553 -- -----------------------------------------------------------------------------
 554 -- Shortcut branches
 555
 556 shortcutBranches :: DynFlags -> [NatCmmTop] -> [NatCmmTop]
 557 shortcutBranches dflags tops
 558   | optLevel dflags < 1 = tops    -- only with -O or higher
 559   | otherwise           = map (apply_mapping mapping) tops'
 560   where
 561     (tops', mappings) = mapAndUnzip build_mapping tops
 562     mapping = foldr plusUFM emptyUFM mappings
 563
 564 build_mapping top@(CmmData _ _) = (top, emptyUFM)
 565 build_mapping (CmmProc info lbl params [])
 566   = (CmmProc info lbl params [], emptyUFM)
 567 build_mapping (CmmProc info lbl params (head:blocks))
 568   = (CmmProc info lbl params (head:others), mapping)
 569         -- drop the shorted blocks, but don't ever drop the first one,
 570         -- because it is pointed to by a global label.
 571   where
 572     -- find all the blocks that just consist of a jump that can be
 573     -- shorted.
 574     (shortcut_blocks, others) = partitionWith split blocks
 575     split (BasicBlock id [insn]) | Just dest <- canShortcut insn
 576                                  = Left (id,dest)
 577     split other = Right other
 578
 579     -- build a mapping from BlockId to JumpDest for shorting branches
 580     mapping = foldl add emptyUFM shortcut_blocks
 581     add ufm (id,dest) = addToUFM ufm id dest
 582
 583 apply_mapping ufm (CmmData sec statics)
 584   = CmmData sec (map (shortcutStatic (lookupUFM ufm)) statics)
 585   -- we need to get the jump tables, so apply the mapping to the entries
 586   -- of a CmmData too.
 587 apply_mapping ufm (CmmProc info lbl params blocks)
 588   = CmmProc info lbl params (map short_bb blocks)
 589   where
 590     short_bb (BasicBlock id insns) = BasicBlock id $! map short_insn insns
 591     short_insn i = shortcutJump (lookupUFM ufm) i
 592                  -- shortcutJump should apply the mapping repeatedly,
 593                  -- just in case we can short multiple branches.
 594
 595 -- -----------------------------------------------------------------------------
 596 -- Instruction selection
 597
 598 -- Native code instruction selection for a chunk of stix code.  For
 599 -- this part of the computation, we switch from the UniqSM monad to
 600 -- the NatM monad.  The latter carries not only a Unique, but also an
 601 -- Int denoting the current C stack pointer offset in the generated
 602 -- code; this is needed for creating correct spill offsets on
 603 -- architectures which don't offer, or for which it would be
 604 -- prohibitively expensive to employ, a frame pointer register.  Viz,
 605 -- x86.
 606
 607 -- The offset is measured in bytes, and indicates the difference
 608 -- between the current (simulated) C stack-ptr and the value it was at
 609 -- the beginning of the block.  For stacks which grow down, this value
 610 -- should be either zero or negative.
 611
 612 -- Switching between the two monads whilst carrying along the same
 613 -- Unique supply breaks abstraction.  Is that bad?
 614
 615 genMachCode :: DynFlags -> RawCmmTop -> UniqSM ([NatCmmTop], [CLabel])
 616
 617 genMachCode dflags cmm_top
 618   = do  { initial_us <- getUs
 619         ; let initial_st           = mkNatM_State initial_us 0 dflags
 620               (new_tops, final_st) = initNat initial_st (cmmTopCodeGen cmm_top)
 621               final_delta          = natm_delta final_st
 622               final_imports        = natm_imports final_st
 623         ; if   final_delta == 0
 624           then return (new_tops, final_imports)
 625           else pprPanic "genMachCode: nonzero final delta" (int final_delta)
 626     }
 627
 628 -- -----------------------------------------------------------------------------
 629 -- Fixup assignments to global registers so that they assign to
 630 -- locations within the RegTable, if appropriate.
 631
 632 -- Note that we currently don't fixup reads here: they're done by
 633 -- the generic optimiser below, to avoid having two separate passes
 634 -- over the Cmm.
 635
 636 fixAssignsTop :: RawCmmTop -> UniqSM RawCmmTop
 637 fixAssignsTop top@(CmmData _ _) = returnUs top
 638 fixAssignsTop (CmmProc info lbl params blocks) =
 639   mapUs fixAssignsBlock blocks `thenUs` \ blocks' ->
 640   returnUs (CmmProc info lbl params blocks')
 641
 642 fixAssignsBlock :: CmmBasicBlock -> UniqSM CmmBasicBlock
 643 fixAssignsBlock (BasicBlock id stmts) =
 644   fixAssigns stmts `thenUs` \ stmts' ->
 645   returnUs (BasicBlock id stmts')
 646
 647 fixAssigns :: [CmmStmt] -> UniqSM [CmmStmt]
 648 fixAssigns stmts =
 649   mapUs fixAssign stmts `thenUs` \ stmtss ->
 650   returnUs (concat stmtss)
 651
 652 fixAssign :: CmmStmt -> UniqSM [CmmStmt]
 653 fixAssign (CmmAssign (CmmGlobal reg) src)
 654   | Left  realreg <- reg_or_addr
 655   = returnUs [CmmAssign (CmmGlobal reg) src]
 656   | Right baseRegAddr <- reg_or_addr
 657   = returnUs [CmmStore baseRegAddr src]
 658            -- Replace register leaves with appropriate StixTrees for
 659            -- the given target. GlobalRegs which map to a reg on this
 660            -- arch are left unchanged.  Assigning to BaseReg is always
 661            -- illegal, so we check for that.
 662   where
 663         reg_or_addr = get_GlobalReg_reg_or_addr reg
 664
 665 fixAssign other_stmt = returnUs [other_stmt]
 666
 667 -- -----------------------------------------------------------------------------
 668 -- Generic Cmm optimiser
 669
 670 {-
 671 Here we do:
 672
 673   (a) Constant folding
 674   (b) Simple inlining: a temporary which is assigned to and then
 675       used, once, can be shorted.
 676   (c) Replacement of references to GlobalRegs which do not have
 677       machine registers by the appropriate memory load (eg.
 678       Hp ==>  *(BaseReg + 34) ).
 679   (d) Position independent code and dynamic linking
 680         (i)  introduce the appropriate indirections
 681              and position independent refs
 682         (ii) compile a list of imported symbols
 683
 684 Ideas for other things we could do (ToDo):
 685
 686   - shortcut jumps-to-jumps
 687   - eliminate dead code blocks
 688   - simple CSE: if an expr is assigned to a temp, then replace later occs of
 689     that expr with the temp, until the expr is no longer valid (can push through
 690     temp assignments, and certain assigns to mem...)
 691 -}
 692
 693 cmmToCmm :: DynFlags -> RawCmmTop -> (RawCmmTop, [CLabel])
 694 cmmToCmm _ top@(CmmData _ _) = (top, [])
 695 cmmToCmm dflags (CmmProc info lbl params blocks) = runCmmOpt dflags $ do
 696   blocks' <- mapM cmmBlockConFold (cmmMiniInline blocks)
 697   return $ CmmProc info lbl params blocks'
 698
 699 newtype CmmOptM a = CmmOptM (([CLabel], DynFlags) -> (# a, [CLabel] #))
 700
 701 instance Monad CmmOptM where
 702   return x = CmmOptM $ \(imports, _) -> (# x,imports #)
 703   (CmmOptM f) >>= g =
 704     CmmOptM $ \(imports, dflags) ->
 705                 case f (imports, dflags) of
 706                   (# x, imports' #) ->
 707                     case g x of
 708                       CmmOptM g' -> g' (imports', dflags)
 709
 710 addImportCmmOpt :: CLabel -> CmmOptM ()
 711 addImportCmmOpt lbl = CmmOptM $ \(imports, dflags) -> (# (), lbl:imports #)
 712
 713 getDynFlagsCmmOpt :: CmmOptM DynFlags
 714 getDynFlagsCmmOpt = CmmOptM $ \(imports, dflags) -> (# dflags, imports #)
 715
 716 runCmmOpt :: DynFlags -> CmmOptM a -> (a, [CLabel])
 717 runCmmOpt dflags (CmmOptM f) = case f ([], dflags) of
 718                         (# result, imports #) -> (result, imports)
 719
 720 cmmBlockConFold :: CmmBasicBlock -> CmmOptM CmmBasicBlock
 721 cmmBlockConFold (BasicBlock id stmts) = do
 722   stmts' <- mapM cmmStmtConFold stmts
 723   return $ BasicBlock id stmts'
 724
 725 cmmStmtConFold stmt
 726    = case stmt of
 727         CmmAssign reg src
 728            -> do src' <- cmmExprConFold DataReference src
 729                  return $ case src' of
 730                    CmmReg reg' | reg == reg' -> CmmNop
 731                    new_src -> CmmAssign reg new_src
 732
 733         CmmStore addr src
 734            -> do addr' <- cmmExprConFold DataReference addr
 735                  src'  <- cmmExprConFold DataReference src
 736                  return $ CmmStore addr' src'
 737
 738         CmmJump addr regs
 739            -> do addr' <- cmmExprConFold JumpReference addr
 740                  return $ CmmJump addr' regs
 741
 742         CmmCall target regs args srt returns
 743            -> do target' <- case target of
 744                               CmmCallee e conv -> do
 745                                 e' <- cmmExprConFold CallReference e
 746                                 return $ CmmCallee e' conv
 747                               other -> return other
 748                  args' <- mapM (\(arg, hint) -> do
 749                                   arg' <- cmmExprConFold DataReference arg
 750                                   return (arg', hint)) args
 751                  return $ CmmCall target' regs args' srt returns
 752
 753         CmmCondBranch test dest
 754            -> do test' <- cmmExprConFold DataReference test
 755                  return $ case test' of
 756                    CmmLit (CmmInt 0 _) ->
 757                      CmmComment (mkFastString ("deleted: " ++
 758                                         showSDoc (pprStmt stmt)))
 759
 760                    CmmLit (CmmInt n _) -> CmmBranch dest
 761                    other -> CmmCondBranch test' dest
 762
 763         CmmSwitch expr ids
 764            -> do expr' <- cmmExprConFold DataReference expr
 765                  return $ CmmSwitch expr' ids
 766
 767         other
 768            -> return other
 769
 770
 771 cmmExprConFold referenceKind expr
 772    = case expr of
 773         CmmLoad addr rep
 774            -> do addr' <- cmmExprConFold DataReference addr
 775                  return $ CmmLoad addr' rep
 776
 777         CmmMachOp mop args
 778            -- For MachOps, we first optimize the children, and then we try
 779            -- our hand at some constant-folding.
 780            -> do args' <- mapM (cmmExprConFold DataReference) args
 781                  return $ cmmMachOpFold mop args'
 782
 783         CmmLit (CmmLabel lbl)
 784            -> do
 785                 dflags <- getDynFlagsCmmOpt
 786                 cmmMakeDynamicReference dflags addImportCmmOpt referenceKind lbl
 787         CmmLit (CmmLabelOff lbl off)
 788            -> do
 789                  dflags <- getDynFlagsCmmOpt
 790                  dynRef <- cmmMakeDynamicReference dflags addImportCmmOpt referenceKind lbl
 791                  return $ cmmMachOpFold (MO_Add wordRep) [
 792                      dynRef,
 793                      (CmmLit $ CmmInt (fromIntegral off) wordRep)
 794                    ]
 795
 796 #if powerpc_TARGET_ARCH
 797            -- On powerpc (non-PIC), it's easier to jump directly to a label than
 798            -- to use the register table, so we replace these registers
 799            -- with the corresponding labels:
 800         CmmReg (CmmGlobal GCEnter1)
 801           | not opt_PIC
 802           -> cmmExprConFold referenceKind $
 803              CmmLit (CmmLabel (mkRtsCodeLabel SLIT( "__stg_gc_enter_1")))
 804         CmmReg (CmmGlobal GCFun)
 805           | not opt_PIC
 806           -> cmmExprConFold referenceKind $
 807              CmmLit (CmmLabel (mkRtsCodeLabel SLIT( "__stg_gc_fun")))
 808 #endif
 809
 810         CmmReg (CmmGlobal mid)
 811            -- Replace register leaves with appropriate StixTrees for
 812            -- the given target.  MagicIds which map to a reg on this
 813            -- arch are left unchanged.  For the rest, BaseReg is taken
 814            -- to mean the address of the reg table in MainCapability,
 815            -- and for all others we generate an indirection to its
 816            -- location in the register table.
 817            -> case get_GlobalReg_reg_or_addr mid of
 818                  Left  realreg -> return expr
 819                  Right baseRegAddr
 820                     -> case mid of
 821                           BaseReg -> cmmExprConFold DataReference baseRegAddr
 822                           other   -> cmmExprConFold DataReference
 823                                         (CmmLoad baseRegAddr (globalRegRep mid))
 824            -- eliminate zero offsets
 825         CmmRegOff reg 0
 826            -> cmmExprConFold referenceKind (CmmReg reg)
 827
 828         CmmRegOff (CmmGlobal mid) offset
 829            -- RegOf leaves are just a shorthand form. If the reg maps
 830            -- to a real reg, we keep the shorthand, otherwise, we just
 831            -- expand it and defer to the above code.
 832            -> case get_GlobalReg_reg_or_addr mid of
 833                 Left  realreg -> return expr
 834                 Right baseRegAddr
 835                    -> cmmExprConFold DataReference (CmmMachOp (MO_Add wordRep) [
 836                                         CmmReg (CmmGlobal mid),
 837                                         CmmLit (CmmInt (fromIntegral offset)
 838                                                        wordRep)])
 839         other
 840            -> return other
 841
 842 -- -----------------------------------------------------------------------------
 843 -- Utils
 844
 845 bind f x = x $! f
 846
 847 \end{code}
 848