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 RegAllocLinear
  23 import RegAllocStats
  24 import RegLiveness
  25 import RegCoalesce
  26 import qualified RegAllocColor  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 [RegAllocStats]
 217         , cdColoredGraph        :: Maybe (Color.Graph Reg RegClass Reg)
 218         , cdAlloced             :: [NatCmmTop] }
 219
 220 dchoose dflags opt a b
 221         | dopt opt dflags       = a
 222         | otherwise             = b
 223
 224 dchooses dflags opts a b
 225         | or $ map ( (flip dopt) dflags) opts   = a
 226         | otherwise             = b
 227
 228 -- | Complete native code generation phase for a single top-level chunk of Cmm.
 229 --      Unless they're being dumped, intermediate data structures are squashed after
 230 --      every stage to avoid creating space leaks.
 231 --
 232 cmmNativeGen :: DynFlags -> RawCmmTop -> UniqSM (CmmNativeGenDump, Pretty.Doc, [CLabel])
 233 cmmNativeGen dflags cmm
 234  = do
 235         --
 236         fixed_cmm
 237          <-     {-# SCC "fixAssigns"  #-}
 238                 fixAssignsTop cmm
 239
 240         ---- cmm to cmm optimisations
 241         (cmm, imports, ppr_cmm)
 242          <- (\fixed_cmm
 243          -> {-# SCC "genericOpt"  #-}
 244            do   let (cmm, imports)      = cmmToCmm dflags fixed_cmm
 245
 246                 return  ( cmm
 247                         , imports
 248                         , dchoose dflags Opt_D_dump_cmm cmm (CmmData Text []))
 249              ) fixed_cmm
 250
 251
 252         ---- generate native code from cmm
 253         (native, lastMinuteImports, ppr_native)
 254          <- (\cmm
 255          -> {-# SCC "genMachCode" #-}
 256            do   (machCode, lastMinuteImports)
 257                         <- genMachCode dflags cmm
 258
 259                 return  ( machCode
 260                         , lastMinuteImports
 261                         , dchoose dflags Opt_D_dump_asm_native machCode [])
 262             ) cmm
 263
 264
 265         ---- tag instructions with register liveness information
 266         (withLiveness, ppr_withLiveness)
 267          <- (\native
 268          -> {-# SCC "regLiveness" #-}
 269            do
 270                 withLiveness    <- mapUs regLiveness native
 271
 272                 return  ( withLiveness
 273                         , dchoose dflags Opt_D_dump_asm_liveness withLiveness []))
 274                 native
 275
 276         ---- allocate registers
 277         (alloced, ppr_alloced, ppr_coalesce, ppr_regAllocStats, ppr_coloredGraph)
 278          <- (\withLiveness
 279          -> {-# SCC "regAlloc" #-}
 280            do
 281                 if dopt Opt_RegsGraph dflags
 282                  then do
 283                         -- the regs usable for allocation
 284                         let alloc_regs
 285                                 = foldr (\r -> plusUFM_C unionUniqSets
 286                                                         $ unitUFM (regClass r) (unitUniqSet r))
 287                                         emptyUFM
 288                                 $ map RealReg allocatableRegs
 289
 290                         -- aggressively coalesce moves between virtual regs
 291                         coalesced       <- regCoalesce withLiveness
 292
 293                         -- graph coloring register allocation
 294                         (alloced, regAllocStats)
 295                                 <- Color.regAlloc
 296                                         alloc_regs
 297                                         (mkUniqSet [0..maxSpillSlots])
 298                                         coalesced
 299
 300                         return  ( alloced
 301                                 , dchoose  dflags Opt_D_dump_asm_regalloc       alloced []
 302                                 , dchoose  dflags Opt_D_dump_asm_coalesce       (Just coalesced)     Nothing
 303                                 , dchooses dflags
 304                                         [ Opt_D_dump_asm_regalloc_stages
 305                                         , Opt_D_drop_asm_stats]
 306                                         (Just regAllocStats) Nothing
 307                                 , dchoose  dflags Opt_D_dump_asm_conflicts      Nothing Nothing)
 308
 309                  else do
 310                         -- do linear register allocation
 311                         alloced <- mapUs regAlloc withLiveness
 312                         return  ( alloced
 313                                 , dchoose dflags Opt_D_dump_asm_regalloc        alloced []
 314                                 , Nothing
 315                                 , Nothing
 316                                 , Nothing ))
 317                 withLiveness
 318
 319
 320         ---- shortcut branches
 321         let shorted     =
 322                 {-# SCC "shortcutBranches" #-}
 323                 shortcutBranches dflags alloced
 324
 325         ---- sequence blocks
 326         let sequenced   =
 327                 {-# SCC "sequenceBlocks" #-}
 328                 map sequenceTop shorted
 329
 330         ---- x86fp_kludge
 331         let final_mach_code =
 332 #if i386_TARGET_ARCH
 333                 {-# SCC "x86fp_kludge" #-}
 334                 map x86fp_kludge sequenced
 335 #else
 336                 sequenced
 337 #endif
 338
 339         ---- vcat
 340         let final_sdoc  =
 341                 {-# SCC "vcat" #-}
 342                 Pretty.vcat (map pprNatCmmTop final_mach_code)
 343
 344         let dump        =
 345                 CmmNativeGenDump
 346                 { cdCmmOpt              = ppr_cmm
 347                 , cdNative              = ppr_native
 348                 , cdLiveness            = ppr_withLiveness
 349                 , cdCoalesce            = ppr_coalesce
 350                 , cdRegAllocStats       = ppr_regAllocStats
 351                 , cdColoredGraph        = ppr_coloredGraph
 352                 , cdAlloced             = ppr_alloced }
 353
 354         returnUs (dump, final_sdoc Pretty.$$ Pretty.text "", lastMinuteImports ++ imports)
 355
 356 #if i386_TARGET_ARCH
 357 x86fp_kludge :: NatCmmTop -> NatCmmTop
 358 x86fp_kludge top@(CmmData _ _) = top
 359 x86fp_kludge top@(CmmProc info lbl params code) =
 360         CmmProc info lbl params (map bb_i386_insert_ffrees code)
 361         where
 362                 bb_i386_insert_ffrees (BasicBlock id instrs) =
 363                         BasicBlock id (i386_insert_ffrees instrs)
 364 #endif
 365
 366
 367 -- Dump output of native code generator passes
 368 --      stripe across the outputs for each block so all the information for a
 369 --      certain stage is concurrent in the dumps.
 370 --
 371 cmmNativeGenDump :: DynFlags -> Module -> ModLocation -> [CmmNativeGenDump] -> IO ()
 372 cmmNativeGenDump dflags mod modLocation dump
 373  = do
 374
 375         dumpIfSet_dyn dflags
 376                 Opt_D_dump_opt_cmm "Optimised Cmm"
 377                 (pprCmm $ Cmm $ map cdCmmOpt dump)
 378
 379         dumpIfSet_dyn dflags
 380                 Opt_D_dump_asm_native   "(asm-native) Native code"
 381                 (vcat $ map (docToSDoc . pprNatCmmTop)  $ concatMap cdNative dump)
 382
 383         dumpIfSet_dyn dflags
 384                 Opt_D_dump_asm_liveness "(asm-liveness) Liveness info added"
 385                 (vcat $ map (ppr . cdLiveness) dump)
 386
 387         dumpIfSet_dyn dflags
 388                 Opt_D_dump_asm_coalesce "(asm-coalesce) Register moves coalesced."
 389                 (vcat $ map (ppr . (\(Just c) -> c) . cdCoalesce) dump)
 390
 391         dumpIfSet_dyn dflags
 392                 Opt_D_dump_asm_regalloc "(asm-regalloc) Registers allocated"
 393                 (vcat $ map (docToSDoc . pprNatCmmTop) $ concatMap cdAlloced dump)
 394
 395         -- with the graph coloring allocator, show the result of each build/spill stage
 396         --        for each block in turn.
 397         mapM_ (\codeGraphs
 398          -> dumpIfSet_dyn dflags
 399                 Opt_D_dump_asm_regalloc_stages "(asm-regalloc-stages)"
 400                 (vcat $ map (\(stage, stats) ->
 401                                  text "-- Stage " <> int stage
 402                                  $$ ppr stats)
 403                                 (zip [0..] codeGraphs)))
 404          $ map ((\(Just c) -> c) . cdRegAllocStats) dump
 405
 406
 407         -- Build a global register conflict graph.
 408         --      If you want to see the graph for just one basic block then use asm-regalloc-stages instead.
 409         dumpIfSet_dyn dflags
 410                 Opt_D_dump_asm_conflicts "(asm-conflicts) Register conflict graph"
 411                 $ Color.dotGraph Color.regDotColor trivColorable
 412                 $ foldl Color.union Color.initGraph
 413                 $ catMaybes $ map cdColoredGraph dump
 414
 415
 416         -- Drop native code gen statistics.
 417         --      This is potentially a large amount of information, so we make a new file instead
 418         --      of dumping it to stdout.
 419         when (dopt Opt_D_drop_asm_stats dflags)
 420          $ do   -- make the drop file name based on the object file name
 421                 let dropFile    = (init $ ml_obj_file modLocation) ++ "drop-asm-stats"
 422
 423                 -- slurp out all the regalloc stats
 424                 let stats       = concat $ catMaybes $ map cdRegAllocStats dump
 425
 426                 -- build a global conflict graph
 427                 let graph       = foldl Color.union Color.initGraph $ map raGraph stats
 428
 429                 -- pretty print the various sections and write out the file.
 430                 let outSpills   = pprStatsSpills    stats
 431                 let outLife     = pprStatsLifetimes stats
 432                 let outConflict = pprStatsConflict  stats
 433                 let outScatter  = pprStatsLifeConflict stats graph
 434
 435                 writeFile dropFile
 436                         (showSDoc $ vcat [outSpills, outLife, outConflict, outScatter])
 437
 438                 return ()
 439
 440         return ()
 441
 442 -- -----------------------------------------------------------------------------
 443 -- Sequencing the basic blocks
 444
 445 -- Cmm BasicBlocks are self-contained entities: they always end in a
 446 -- jump, either non-local or to another basic block in the same proc.
 447 -- In this phase, we attempt to place the basic blocks in a sequence
 448 -- such that as many of the local jumps as possible turn into
 449 -- fallthroughs.
 450
 451 sequenceTop :: NatCmmTop -> NatCmmTop
 452 sequenceTop top@(CmmData _ _) = top
 453 sequenceTop (CmmProc info lbl params blocks) =
 454   CmmProc info lbl params (makeFarBranches $ sequenceBlocks blocks)
 455
 456 -- The algorithm is very simple (and stupid): we make a graph out of
 457 -- the blocks where there is an edge from one block to another iff the
 458 -- first block ends by jumping to the second.  Then we topologically
 459 -- sort this graph.  Then traverse the list: for each block, we first
 460 -- output the block, then if it has an out edge, we move the
 461 -- destination of the out edge to the front of the list, and continue.
 462
 463 sequenceBlocks :: [NatBasicBlock] -> [NatBasicBlock]
 464 sequenceBlocks [] = []
 465 sequenceBlocks (entry:blocks) =
 466   seqBlocks (mkNode entry : reverse (flattenSCCs (sccBlocks blocks)))
 467   -- the first block is the entry point ==> it must remain at the start.
 468
 469 sccBlocks :: [NatBasicBlock] -> [SCC (NatBasicBlock,Unique,[Unique])]
 470 sccBlocks blocks = stronglyConnCompR (map mkNode blocks)
 471
 472 getOutEdges :: [Instr] -> [Unique]
 473 getOutEdges instrs = case jumpDests (last instrs) [] of
 474                         [one] -> [getUnique one]
 475                         _many -> []
 476                 -- we're only interested in the last instruction of
 477                 -- the block, and only if it has a single destination.
 478
 479 mkNode block@(BasicBlock id instrs) = (block, getUnique id, getOutEdges instrs)
 480
 481 seqBlocks [] = []
 482 seqBlocks ((block,_,[]) : rest)
 483   = block : seqBlocks rest
 484 seqBlocks ((block@(BasicBlock id instrs),_,[next]) : rest)
 485   | can_fallthrough = BasicBlock id (init instrs) : seqBlocks rest'
 486   | otherwise       = block : seqBlocks rest'
 487   where
 488         (can_fallthrough, rest') = reorder next [] rest
 489           -- TODO: we should do a better job for cycles; try to maximise the
 490           -- fallthroughs within a loop.
 491 seqBlocks _ = panic "AsmCodegen:seqBlocks"
 492
 493 reorder id accum [] = (False, reverse accum)
 494 reorder id accum (b@(block,id',out) : rest)
 495   | id == id'  = (True, (block,id,out) : reverse accum ++ rest)
 496   | otherwise  = reorder id (b:accum) rest
 497
 498
 499 -- -----------------------------------------------------------------------------
 500 -- Making far branches
 501
 502 -- Conditional branches on PowerPC are limited to +-32KB; if our Procs get too
 503 -- big, we have to work around this limitation.
 504
 505 makeFarBranches :: [NatBasicBlock] -> [NatBasicBlock]
 506
 507 #if powerpc_TARGET_ARCH
 508 makeFarBranches blocks
 509     | last blockAddresses < nearLimit = blocks
 510     | otherwise = zipWith handleBlock blockAddresses blocks
 511     where
 512         blockAddresses = scanl (+) 0 $ map blockLen blocks
 513         blockLen (BasicBlock _ instrs) = length instrs
 514
 515         handleBlock addr (BasicBlock id instrs)
 516                 = BasicBlock id (zipWith makeFar [addr..] instrs)
 517
 518         makeFar addr (BCC ALWAYS tgt) = BCC ALWAYS tgt
 519         makeFar addr (BCC cond tgt)
 520             | abs (addr - targetAddr) >= nearLimit
 521             = BCCFAR cond tgt
 522             | otherwise
 523             = BCC cond tgt
 524             where Just targetAddr = lookupUFM blockAddressMap tgt
 525         makeFar addr other            = other
 526
 527         nearLimit = 7000 -- 8192 instructions are allowed; let's keep some
 528                          -- distance, as we have a few pseudo-insns that are
 529                          -- pretty-printed as multiple instructions,
 530                          -- and it's just not worth the effort to calculate
 531                          -- things exactly
 532
 533         blockAddressMap = listToUFM $ zip (map blockId blocks) blockAddresses
 534 #else
 535 makeFarBranches = id
 536 #endif
 537
 538 -- -----------------------------------------------------------------------------
 539 -- Shortcut branches
 540
 541 shortcutBranches :: DynFlags -> [NatCmmTop] -> [NatCmmTop]
 542 shortcutBranches dflags tops
 543   | optLevel dflags < 1 = tops    -- only with -O or higher
 544   | otherwise           = map (apply_mapping mapping) tops'
 545   where
 546     (tops', mappings) = mapAndUnzip build_mapping tops
 547     mapping = foldr plusUFM emptyUFM mappings
 548
 549 build_mapping top@(CmmData _ _) = (top, emptyUFM)
 550 build_mapping (CmmProc info lbl params [])
 551   = (CmmProc info lbl params [], emptyUFM)
 552 build_mapping (CmmProc info lbl params (head:blocks))
 553   = (CmmProc info lbl params (head:others), mapping)
 554         -- drop the shorted blocks, but don't ever drop the first one,
 555         -- because it is pointed to by a global label.
 556   where
 557     -- find all the blocks that just consist of a jump that can be
 558     -- shorted.
 559     (shortcut_blocks, others) = partitionWith split blocks
 560     split (BasicBlock id [insn]) | Just dest <- canShortcut insn
 561                                  = Left (id,dest)
 562     split other = Right other
 563
 564     -- build a mapping from BlockId to JumpDest for shorting branches
 565     mapping = foldl add emptyUFM shortcut_blocks
 566     add ufm (id,dest) = addToUFM ufm id dest
 567
 568 apply_mapping ufm (CmmData sec statics)
 569   = CmmData sec (map (shortcutStatic (lookupUFM ufm)) statics)
 570   -- we need to get the jump tables, so apply the mapping to the entries
 571   -- of a CmmData too.
 572 apply_mapping ufm (CmmProc info lbl params blocks)
 573   = CmmProc info lbl params (map short_bb blocks)
 574   where
 575     short_bb (BasicBlock id insns) = BasicBlock id $! map short_insn insns
 576     short_insn i = shortcutJump (lookupUFM ufm) i
 577                  -- shortcutJump should apply the mapping repeatedly,
 578                  -- just in case we can short multiple branches.
 579
 580 -- -----------------------------------------------------------------------------
 581 -- Instruction selection
 582
 583 -- Native code instruction selection for a chunk of stix code.  For
 584 -- this part of the computation, we switch from the UniqSM monad to
 585 -- the NatM monad.  The latter carries not only a Unique, but also an
 586 -- Int denoting the current C stack pointer offset in the generated
 587 -- code; this is needed for creating correct spill offsets on
 588 -- architectures which don't offer, or for which it would be
 589 -- prohibitively expensive to employ, a frame pointer register.  Viz,
 590 -- x86.
 591
 592 -- The offset is measured in bytes, and indicates the difference
 593 -- between the current (simulated) C stack-ptr and the value it was at
 594 -- the beginning of the block.  For stacks which grow down, this value
 595 -- should be either zero or negative.
 596
 597 -- Switching between the two monads whilst carrying along the same
 598 -- Unique supply breaks abstraction.  Is that bad?
 599
 600 genMachCode :: DynFlags -> RawCmmTop -> UniqSM ([NatCmmTop], [CLabel])
 601
 602 genMachCode dflags cmm_top
 603   = do  { initial_us <- getUs
 604         ; let initial_st           = mkNatM_State initial_us 0 dflags
 605               (new_tops, final_st) = initNat initial_st (cmmTopCodeGen cmm_top)
 606               final_delta          = natm_delta final_st
 607               final_imports        = natm_imports final_st
 608         ; if   final_delta == 0
 609           then return (new_tops, final_imports)
 610           else pprPanic "genMachCode: nonzero final delta" (int final_delta)
 611     }
 612
 613 -- -----------------------------------------------------------------------------
 614 -- Fixup assignments to global registers so that they assign to
 615 -- locations within the RegTable, if appropriate.
 616
 617 -- Note that we currently don't fixup reads here: they're done by
 618 -- the generic optimiser below, to avoid having two separate passes
 619 -- over the Cmm.
 620
 621 fixAssignsTop :: RawCmmTop -> UniqSM RawCmmTop
 622 fixAssignsTop top@(CmmData _ _) = returnUs top
 623 fixAssignsTop (CmmProc info lbl params blocks) =
 624   mapUs fixAssignsBlock blocks `thenUs` \ blocks' ->
 625   returnUs (CmmProc info lbl params blocks')
 626
 627 fixAssignsBlock :: CmmBasicBlock -> UniqSM CmmBasicBlock
 628 fixAssignsBlock (BasicBlock id stmts) =
 629   fixAssigns stmts `thenUs` \ stmts' ->
 630   returnUs (BasicBlock id stmts')
 631
 632 fixAssigns :: [CmmStmt] -> UniqSM [CmmStmt]
 633 fixAssigns stmts =
 634   mapUs fixAssign stmts `thenUs` \ stmtss ->
 635   returnUs (concat stmtss)
 636
 637 fixAssign :: CmmStmt -> UniqSM [CmmStmt]
 638 fixAssign (CmmAssign (CmmGlobal reg) src)
 639   | Left  realreg <- reg_or_addr
 640   = returnUs [CmmAssign (CmmGlobal reg) src]
 641   | Right baseRegAddr <- reg_or_addr
 642   = returnUs [CmmStore baseRegAddr src]
 643            -- Replace register leaves with appropriate StixTrees for
 644            -- the given target. GlobalRegs which map to a reg on this
 645            -- arch are left unchanged.  Assigning to BaseReg is always
 646            -- illegal, so we check for that.
 647   where
 648         reg_or_addr = get_GlobalReg_reg_or_addr reg
 649
 650 fixAssign other_stmt = returnUs [other_stmt]
 651
 652 -- -----------------------------------------------------------------------------
 653 -- Generic Cmm optimiser
 654
 655 {-
 656 Here we do:
 657
 658   (a) Constant folding
 659   (b) Simple inlining: a temporary which is assigned to and then
 660       used, once, can be shorted.
 661   (c) Replacement of references to GlobalRegs which do not have
 662       machine registers by the appropriate memory load (eg.
 663       Hp ==>  *(BaseReg + 34) ).
 664   (d) Position independent code and dynamic linking
 665         (i)  introduce the appropriate indirections
 666              and position independent refs
 667         (ii) compile a list of imported symbols
 668
 669 Ideas for other things we could do (ToDo):
 670
 671   - shortcut jumps-to-jumps
 672   - eliminate dead code blocks
 673   - simple CSE: if an expr is assigned to a temp, then replace later occs of
 674     that expr with the temp, until the expr is no longer valid (can push through
 675     temp assignments, and certain assigns to mem...)
 676 -}
 677
 678 cmmToCmm :: DynFlags -> RawCmmTop -> (RawCmmTop, [CLabel])
 679 cmmToCmm _ top@(CmmData _ _) = (top, [])
 680 cmmToCmm dflags (CmmProc info lbl params blocks) = runCmmOpt dflags $ do
 681   blocks' <- mapM cmmBlockConFold (cmmMiniInline blocks)
 682   return $ CmmProc info lbl params blocks'
 683
 684 newtype CmmOptM a = CmmOptM (([CLabel], DynFlags) -> (# a, [CLabel] #))
 685
 686 instance Monad CmmOptM where
 687   return x = CmmOptM $ \(imports, _) -> (# x,imports #)
 688   (CmmOptM f) >>= g =
 689     CmmOptM $ \(imports, dflags) ->
 690                 case f (imports, dflags) of
 691                   (# x, imports' #) ->
 692                     case g x of
 693                       CmmOptM g' -> g' (imports', dflags)
 694
 695 addImportCmmOpt :: CLabel -> CmmOptM ()
 696 addImportCmmOpt lbl = CmmOptM $ \(imports, dflags) -> (# (), lbl:imports #)
 697
 698 getDynFlagsCmmOpt :: CmmOptM DynFlags
 699 getDynFlagsCmmOpt = CmmOptM $ \(imports, dflags) -> (# dflags, imports #)
 700
 701 runCmmOpt :: DynFlags -> CmmOptM a -> (a, [CLabel])
 702 runCmmOpt dflags (CmmOptM f) = case f ([], dflags) of
 703                         (# result, imports #) -> (result, imports)
 704
 705 cmmBlockConFold :: CmmBasicBlock -> CmmOptM CmmBasicBlock
 706 cmmBlockConFold (BasicBlock id stmts) = do
 707   stmts' <- mapM cmmStmtConFold stmts
 708   return $ BasicBlock id stmts'
 709
 710 cmmStmtConFold stmt
 711    = case stmt of
 712         CmmAssign reg src
 713            -> do src' <- cmmExprConFold DataReference src
 714                  return $ case src' of
 715                    CmmReg reg' | reg == reg' -> CmmNop
 716                    new_src -> CmmAssign reg new_src
 717
 718         CmmStore addr src
 719            -> do addr' <- cmmExprConFold DataReference addr
 720                  src'  <- cmmExprConFold DataReference src
 721                  return $ CmmStore addr' src'
 722
 723         CmmJump addr regs
 724            -> do addr' <- cmmExprConFold JumpReference addr
 725                  return $ CmmJump addr' regs
 726
 727         CmmCall target regs args srt returns
 728            -> do target' <- case target of
 729                               CmmCallee e conv -> do
 730                                 e' <- cmmExprConFold CallReference e
 731                                 return $ CmmCallee e' conv
 732                               other -> return other
 733                  args' <- mapM (\(arg, hint) -> do
 734                                   arg' <- cmmExprConFold DataReference arg
 735                                   return (arg', hint)) args
 736                  return $ CmmCall target' regs args' srt returns
 737
 738         CmmCondBranch test dest
 739            -> do test' <- cmmExprConFold DataReference test
 740                  return $ case test' of
 741                    CmmLit (CmmInt 0 _) ->
 742                      CmmComment (mkFastString ("deleted: " ++
 743                                         showSDoc (pprStmt stmt)))
 744
 745                    CmmLit (CmmInt n _) -> CmmBranch dest
 746                    other -> CmmCondBranch test' dest
 747
 748         CmmSwitch expr ids
 749            -> do expr' <- cmmExprConFold DataReference expr
 750                  return $ CmmSwitch expr' ids
 751
 752         other
 753            -> return other
 754
 755
 756 cmmExprConFold referenceKind expr
 757    = case expr of
 758         CmmLoad addr rep
 759            -> do addr' <- cmmExprConFold DataReference addr
 760                  return $ CmmLoad addr' rep
 761
 762         CmmMachOp mop args
 763            -- For MachOps, we first optimize the children, and then we try
 764            -- our hand at some constant-folding.
 765            -> do args' <- mapM (cmmExprConFold DataReference) args
 766                  return $ cmmMachOpFold mop args'
 767
 768         CmmLit (CmmLabel lbl)
 769            -> do
 770                 dflags <- getDynFlagsCmmOpt
 771                 cmmMakeDynamicReference dflags addImportCmmOpt referenceKind lbl
 772         CmmLit (CmmLabelOff lbl off)
 773            -> do
 774                  dflags <- getDynFlagsCmmOpt
 775                  dynRef <- cmmMakeDynamicReference dflags addImportCmmOpt referenceKind lbl
 776                  return $ cmmMachOpFold (MO_Add wordRep) [
 777                      dynRef,
 778                      (CmmLit $ CmmInt (fromIntegral off) wordRep)
 779                    ]
 780
 781 #if powerpc_TARGET_ARCH
 782            -- On powerpc (non-PIC), it's easier to jump directly to a label than
 783            -- to use the register table, so we replace these registers
 784            -- with the corresponding labels:
 785         CmmReg (CmmGlobal GCEnter1)
 786           | not opt_PIC
 787           -> cmmExprConFold referenceKind $
 788              CmmLit (CmmLabel (mkRtsCodeLabel SLIT( "__stg_gc_enter_1")))
 789         CmmReg (CmmGlobal GCFun)
 790           | not opt_PIC
 791           -> cmmExprConFold referenceKind $
 792              CmmLit (CmmLabel (mkRtsCodeLabel SLIT( "__stg_gc_fun")))
 793 #endif
 794
 795         CmmReg (CmmGlobal mid)
 796            -- Replace register leaves with appropriate StixTrees for
 797            -- the given target.  MagicIds which map to a reg on this
 798            -- arch are left unchanged.  For the rest, BaseReg is taken
 799            -- to mean the address of the reg table in MainCapability,
 800            -- and for all others we generate an indirection to its
 801            -- location in the register table.
 802            -> case get_GlobalReg_reg_or_addr mid of
 803                  Left  realreg -> return expr
 804                  Right baseRegAddr
 805                     -> case mid of
 806                           BaseReg -> cmmExprConFold DataReference baseRegAddr
 807                           other   -> cmmExprConFold DataReference
 808                                         (CmmLoad baseRegAddr (globalRegRep mid))
 809            -- eliminate zero offsets
 810         CmmRegOff reg 0
 811            -> cmmExprConFold referenceKind (CmmReg reg)
 812
 813         CmmRegOff (CmmGlobal mid) offset
 814            -- RegOf leaves are just a shorthand form. If the reg maps
 815            -- to a real reg, we keep the shorthand, otherwise, we just
 816            -- expand it and defer to the above code.
 817            -> case get_GlobalReg_reg_or_addr mid of
 818                 Left  realreg -> return expr
 819                 Right baseRegAddr
 820                    -> cmmExprConFold DataReference (CmmMachOp (MO_Add wordRep) [
 821                                         CmmReg (CmmGlobal mid),
 822                                         CmmLit (CmmInt (fromIntegral offset)
 823                                                        wordRep)])
 824         other
 825            -> return other
 826
 827 -- -----------------------------------------------------------------------------
 828 -- Utils
 829
 830 bind f x = x $! f
 831
 832 \end{code}
 833