1 -- -----------------------------------------------------------------------------
3 -- (c) The University of Glasgow 1993-2004
5 -- This is the top-level module in the native code generator.
7 -- -----------------------------------------------------------------------------
10 module AsmCodeGen ( nativeCodeGen ) where
12 #include "HsVersions.h"
13 #include "nativeGen/NCG.h"
20 import RegAllocInfo ( jumpDests )
22 import PositionIndependentCode
25 import CmmOpt ( cmmMiniInline, cmmMachOpFold )
26 import PprCmm ( pprStmt, pprCmms )
28 import CLabel ( CLabel, mkSplitMarkerLabel, mkAsmTempLabel )
29 #if powerpc_TARGET_ARCH
30 import CLabel ( mkRtsCodeLabel )
34 import Unique ( Unique, getUnique )
37 import List ( groupBy, sortBy )
38 import CLabel ( pprCLabel )
39 import ErrUtils ( dumpIfSet_dyn )
40 import DynFlags ( DynFlags, DynFlag(..), dopt )
41 import StaticFlags ( opt_Static, opt_PIC )
42 import Config ( cProjectVersion )
45 import qualified Pretty
53 import List ( intersperse )
62 The native-code generator has machine-independent and
63 machine-dependent modules.
65 This module ("AsmCodeGen") is the top-level machine-independent
66 module. Before entering machine-dependent land, we do some
67 machine-independent optimisations (defined below) on the
70 We convert to the machine-specific 'Instr' datatype with
71 'cmmCodeGen', assuming an infinite supply of registers. We then use
72 a machine-independent register allocator ('regAlloc') to rejoin
73 reality. Obviously, 'regAlloc' has machine-specific helper
74 functions (see about "RegAllocInfo" below).
76 Finally, we order the basic blocks of the function so as to minimise
77 the number of jumps between blocks, by utilising fallthrough wherever
80 The machine-dependent bits break down as follows:
82 * ["MachRegs"] Everything about the target platform's machine
83 registers (and immediate operands, and addresses, which tend to
84 intermingle/interact with registers).
86 * ["MachInstrs"] Includes the 'Instr' datatype (possibly should
87 have a module of its own), plus a miscellany of other things
88 (e.g., 'targetDoubleSize', 'smStablePtrTable', ...)
90 * ["MachCodeGen"] is where 'Cmm' stuff turns into
93 * ["PprMach"] 'pprInstr' turns an 'Instr' into text (well, really
96 * ["RegAllocInfo"] In the register allocator, we manipulate
97 'MRegsState's, which are 'BitSet's, one bit per machine register.
98 When we want to say something about a specific machine register
99 (e.g., ``it gets clobbered by this instruction''), we set/unset
100 its bit. Obviously, we do this 'BitSet' thing for efficiency
103 The 'RegAllocInfo' module collects together the machine-specific
104 info needed to do register allocation.
106 * ["RegisterAlloc"] The (machine-independent) register allocator.
109 -- -----------------------------------------------------------------------------
110 -- Top-level of the native codegen
112 -- NB. We *lazilly* compile each block of code for space reasons.
114 nativeCodeGen :: DynFlags -> [Cmm] -> UniqSupply -> IO Pretty.Doc
115 nativeCodeGen dflags cmms us
116 = let (res, _) = initUs us $
117 cgCmm (concat (map add_split cmms))
119 cgCmm :: [CmmTop] -> UniqSM (Cmm, Pretty.Doc, [CLabel])
121 lazyMapUs (cmmNativeGen dflags) tops `thenUs` \ results ->
122 case unzip3 results of { (cmms,docs,imps) ->
123 returnUs (Cmm cmms, my_vcat docs, concat imps)
126 case res of { (ppr_cmms, insn_sdoc, imports) -> do
127 dumpIfSet_dyn dflags Opt_D_dump_opt_cmm "Optimised Cmm" (pprCmms [ppr_cmms])
128 return (insn_sdoc Pretty.$$ dyld_stubs imports
129 #if HAVE_SUBSECTIONS_VIA_SYMBOLS
130 -- On recent versions of Darwin, the linker supports
131 -- dead-stripping of code and data on a per-symbol basis.
132 -- There's a hack to make this work in PprMach.pprNatCmmTop.
133 Pretty.$$ Pretty.text ".subsections_via_symbols"
135 #if HAVE_GNU_NONEXEC_STACK
136 -- On recent GNU ELF systems one can mark an object file
137 -- as not requiring an executable stack. If all objects
138 -- linked into a program have this note then the program
139 -- will not use an executable stack, which is good for
140 -- security. GHC generated code does not need an executable
141 -- stack so add the note in:
142 Pretty.$$ Pretty.text ".section .note.GNU-stack,\"\",@progbits"
144 #if !defined(darwin_TARGET_OS)
145 -- And just because every other compiler does, lets stick in
146 -- an identifier directive: .ident "GHC x.y.z"
147 Pretty.$$ let compilerIdent = Pretty.text "GHC" Pretty.<+>
148 Pretty.text cProjectVersion
149 in Pretty.text ".ident" Pretty.<+>
150 Pretty.doubleQuotes compilerIdent
158 | dopt Opt_SplitObjs dflags = split_marker : tops
161 split_marker = CmmProc [] mkSplitMarkerLabel [] []
163 -- Generate "symbol stubs" for all external symbols that might
164 -- come from a dynamic library.
165 {- dyld_stubs imps = Pretty.vcat $ map pprDyldSymbolStub $
166 map head $ group $ sort imps-}
168 -- (Hack) sometimes two Labels pretty-print the same, but have
169 -- different uniques; so we compare their text versions...
171 | needImportedSymbols
173 (pprGotDeclaration :) $
174 map (pprImportedSymbol . fst . head) $
175 groupBy (\(_,a) (_,b) -> a == b) $
176 sortBy (\(_,a) (_,b) -> compare a b) $
182 where doPpr lbl = (lbl, Pretty.render $ pprCLabel lbl astyle)
183 astyle = mkCodeStyle AsmStyle
186 my_vcat sds = Pretty.vcat sds
188 my_vcat sds = Pretty.vcat (
191 Pretty.$$ Pretty.ptext SLIT("# ___ncg_debug_marker")
192 Pretty.$$ Pretty.char ' '
199 -- Complete native code generation phase for a single top-level chunk
202 cmmNativeGen :: DynFlags -> CmmTop -> UniqSM (CmmTop, Pretty.Doc, [CLabel])
203 cmmNativeGen dflags cmm
204 = {-# SCC "fixAssigns" #-}
205 fixAssignsTop cmm `thenUs` \ fixed_cmm ->
206 {-# SCC "genericOpt" #-}
207 cmmToCmm fixed_cmm `bind` \ (cmm, imports) ->
208 (if dopt Opt_D_dump_opt_cmm dflags -- space leak avoidance
210 else CmmData Text []) `bind` \ ppr_cmm ->
211 {-# SCC "genMachCode" #-}
212 genMachCode cmm `thenUs` \ (pre_regalloc, lastMinuteImports) ->
213 {-# SCC "regAlloc" #-}
214 mapUs regAlloc pre_regalloc `thenUs` \ with_regs ->
215 {-# SCC "sequenceBlocks" #-}
216 map sequenceTop with_regs `bind` \ sequenced ->
217 {-# SCC "x86fp_kludge" #-}
218 map x86fp_kludge sequenced `bind` \ final_mach_code ->
220 Pretty.vcat (map pprNatCmmTop final_mach_code) `bind` \ final_sdoc ->
222 returnUs (ppr_cmm, final_sdoc Pretty.$$ Pretty.text "", lastMinuteImports ++ imports)
224 x86fp_kludge :: NatCmmTop -> NatCmmTop
225 x86fp_kludge top@(CmmData _ _) = top
227 x86fp_kludge top@(CmmProc info lbl params code) =
228 CmmProc info lbl params (map bb_i386_insert_ffrees code)
230 bb_i386_insert_ffrees (BasicBlock id instrs) =
231 BasicBlock id (i386_insert_ffrees instrs)
233 x86fp_kludge top = top
236 -- -----------------------------------------------------------------------------
237 -- Sequencing the basic blocks
239 -- Cmm BasicBlocks are self-contained entities: they always end in a
240 -- jump, either non-local or to another basic block in the same proc.
241 -- In this phase, we attempt to place the basic blocks in a sequence
242 -- such that as many of the local jumps as possible turn into
245 sequenceTop :: NatCmmTop -> NatCmmTop
246 sequenceTop top@(CmmData _ _) = top
247 sequenceTop (CmmProc info lbl params blocks) =
248 CmmProc info lbl params (makeFarBranches $ sequenceBlocks blocks)
250 -- The algorithm is very simple (and stupid): we make a graph out of
251 -- the blocks where there is an edge from one block to another iff the
252 -- first block ends by jumping to the second. Then we topologically
253 -- sort this graph. Then traverse the list: for each block, we first
254 -- output the block, then if it has an out edge, we move the
255 -- destination of the out edge to the front of the list, and continue.
257 sequenceBlocks :: [NatBasicBlock] -> [NatBasicBlock]
258 sequenceBlocks [] = []
259 sequenceBlocks (entry:blocks) =
260 seqBlocks (mkNode entry : reverse (flattenSCCs (sccBlocks blocks)))
261 -- the first block is the entry point ==> it must remain at the start.
263 sccBlocks :: [NatBasicBlock] -> [SCC (NatBasicBlock,Unique,[Unique])]
264 sccBlocks blocks = stronglyConnCompR (map mkNode blocks)
266 getOutEdges :: [Instr] -> [Unique]
267 getOutEdges instrs = case jumpDests (last instrs) [] of
268 [one] -> [getUnique one]
270 -- we're only interested in the last instruction of
271 -- the block, and only if it has a single destination.
273 mkNode block@(BasicBlock id instrs) = (block, getUnique id, getOutEdges instrs)
276 seqBlocks ((block,_,[]) : rest)
277 = block : seqBlocks rest
278 seqBlocks ((block@(BasicBlock id instrs),_,[next]) : rest)
279 | can_fallthrough = BasicBlock id (init instrs) : seqBlocks rest'
280 | otherwise = block : seqBlocks rest'
282 (can_fallthrough, rest') = reorder next [] rest
283 -- TODO: we should do a better job for cycles; try to maximise the
284 -- fallthroughs within a loop.
285 seqBlocks _ = panic "AsmCodegen:seqBlocks"
287 reorder id accum [] = (False, reverse accum)
288 reorder id accum (b@(block,id',out) : rest)
289 | id == id' = (True, (block,id,out) : reverse accum ++ rest)
290 | otherwise = reorder id (b:accum) rest
293 -- -----------------------------------------------------------------------------
294 -- Making far branches
296 -- Conditional branches on PowerPC are limited to +-32KB; if our Procs get too
297 -- big, we have to work around this limitation.
299 makeFarBranches :: [NatBasicBlock] -> [NatBasicBlock]
301 #if powerpc_TARGET_ARCH
302 makeFarBranches blocks
303 | last blockAddresses < nearLimit = blocks
304 | otherwise = zipWith handleBlock blockAddresses blocks
306 blockAddresses = scanl (+) 0 $ map blockLen blocks
307 blockLen (BasicBlock _ instrs) = length instrs
309 handleBlock addr (BasicBlock id instrs)
310 = BasicBlock id (zipWith makeFar [addr..] instrs)
312 makeFar addr (BCC ALWAYS tgt) = BCC ALWAYS tgt
313 makeFar addr (BCC cond tgt)
314 | abs (addr - targetAddr) >= nearLimit
318 where Just targetAddr = lookupUFM blockAddressMap tgt
319 makeFar addr other = other
321 nearLimit = 7000 -- 8192 instructions are allowed; let's keep some
322 -- distance, as we have a few pseudo-insns that are
323 -- pretty-printed as multiple instructions,
324 -- and it's just not worth the effort to calculate
327 blockAddressMap = listToUFM $ zip (map blockId blocks) blockAddresses
332 -- -----------------------------------------------------------------------------
333 -- Instruction selection
335 -- Native code instruction selection for a chunk of stix code. For
336 -- this part of the computation, we switch from the UniqSM monad to
337 -- the NatM monad. The latter carries not only a Unique, but also an
338 -- Int denoting the current C stack pointer offset in the generated
339 -- code; this is needed for creating correct spill offsets on
340 -- architectures which don't offer, or for which it would be
341 -- prohibitively expensive to employ, a frame pointer register. Viz,
344 -- The offset is measured in bytes, and indicates the difference
345 -- between the current (simulated) C stack-ptr and the value it was at
346 -- the beginning of the block. For stacks which grow down, this value
347 -- should be either zero or negative.
349 -- Switching between the two monads whilst carrying along the same
350 -- Unique supply breaks abstraction. Is that bad?
352 genMachCode :: CmmTop -> UniqSM ([NatCmmTop], [CLabel])
355 = do { initial_us <- getUs
356 ; let initial_st = mkNatM_State initial_us 0
357 (new_tops, final_st) = initNat initial_st (cmmTopCodeGen cmm_top)
358 final_us = natm_us final_st
359 final_delta = natm_delta final_st
360 final_imports = natm_imports final_st
361 ; if final_delta == 0
362 then return (new_tops, final_imports)
363 else pprPanic "genMachCode: nonzero final delta" (int final_delta)
366 -- -----------------------------------------------------------------------------
367 -- Fixup assignments to global registers so that they assign to
368 -- locations within the RegTable, if appropriate.
370 -- Note that we currently don't fixup reads here: they're done by
371 -- the generic optimiser below, to avoid having two separate passes
374 fixAssignsTop :: CmmTop -> UniqSM CmmTop
375 fixAssignsTop top@(CmmData _ _) = returnUs top
376 fixAssignsTop (CmmProc info lbl params blocks) =
377 mapUs fixAssignsBlock blocks `thenUs` \ blocks' ->
378 returnUs (CmmProc info lbl params blocks')
380 fixAssignsBlock :: CmmBasicBlock -> UniqSM CmmBasicBlock
381 fixAssignsBlock (BasicBlock id stmts) =
382 fixAssigns stmts `thenUs` \ stmts' ->
383 returnUs (BasicBlock id stmts')
385 fixAssigns :: [CmmStmt] -> UniqSM [CmmStmt]
387 mapUs fixAssign stmts `thenUs` \ stmtss ->
388 returnUs (concat stmtss)
390 fixAssign :: CmmStmt -> UniqSM [CmmStmt]
391 fixAssign (CmmAssign (CmmGlobal BaseReg) src)
392 = panic "cmmStmtConFold: assignment to BaseReg";
394 fixAssign (CmmAssign (CmmGlobal reg) src)
395 | Left realreg <- reg_or_addr
396 = returnUs [CmmAssign (CmmGlobal reg) src]
397 | Right baseRegAddr <- reg_or_addr
398 = returnUs [CmmStore baseRegAddr src]
399 -- Replace register leaves with appropriate StixTrees for
400 -- the given target. GlobalRegs which map to a reg on this
401 -- arch are left unchanged. Assigning to BaseReg is always
402 -- illegal, so we check for that.
404 reg_or_addr = get_GlobalReg_reg_or_addr reg
406 fixAssign (CmmCall target results args vols)
407 = mapAndUnzipUs fixResult results `thenUs` \ (results',stores) ->
408 returnUs (caller_save ++
409 CmmCall target results' args vols :
413 -- we also save/restore any caller-saves STG registers here
414 (caller_save, caller_restore) = callerSaveVolatileRegs vols
416 fixResult g@(CmmGlobal reg,hint) =
417 case get_GlobalReg_reg_or_addr reg of
418 Left realreg -> returnUs (g, [])
420 getUniqueUs `thenUs` \ uq ->
421 let local = CmmLocal (LocalReg uq (globalRegRep reg)) in
422 returnUs ((local,hint),
423 [CmmStore baseRegAddr (CmmReg local)])
427 fixAssign other_stmt = returnUs [other_stmt]
429 -- -----------------------------------------------------------------------------
430 -- Generic Cmm optimiser
436 (b) Simple inlining: a temporary which is assigned to and then
437 used, once, can be shorted.
438 (c) Replacement of references to GlobalRegs which do not have
439 machine registers by the appropriate memory load (eg.
440 Hp ==> *(BaseReg + 34) ).
441 (d) Position independent code and dynamic linking
442 (i) introduce the appropriate indirections
443 and position independent refs
444 (ii) compile a list of imported symbols
446 Ideas for other things we could do (ToDo):
448 - shortcut jumps-to-jumps
449 - eliminate dead code blocks
450 - simple CSE: if an expr is assigned to a temp, then replace later occs of
451 that expr with the temp, until the expr is no longer valid (can push through
452 temp assignments, and certain assigns to mem...)
455 cmmToCmm :: CmmTop -> (CmmTop, [CLabel])
456 cmmToCmm top@(CmmData _ _) = (top, [])
457 cmmToCmm (CmmProc info lbl params blocks) = runCmmOpt $ do
458 blocks' <- mapM cmmBlockConFold (cmmMiniInline blocks)
459 return $ CmmProc info lbl params blocks'
461 newtype CmmOptM a = CmmOptM ([CLabel] -> (# a, [CLabel] #))
463 instance Monad CmmOptM where
464 return x = CmmOptM $ \imports -> (# x,imports #)
466 CmmOptM $ \imports ->
470 CmmOptM g' -> g' imports'
472 addImportCmmOpt :: CLabel -> CmmOptM ()
473 addImportCmmOpt lbl = CmmOptM $ \imports -> (# (), lbl:imports #)
475 runCmmOpt :: CmmOptM a -> (a, [CLabel])
476 runCmmOpt (CmmOptM f) = case f [] of
477 (# result, imports #) -> (result, imports)
479 cmmBlockConFold :: CmmBasicBlock -> CmmOptM CmmBasicBlock
480 cmmBlockConFold (BasicBlock id stmts) = do
481 stmts' <- mapM cmmStmtConFold stmts
482 return $ BasicBlock id stmts'
487 -> do src' <- cmmExprConFold DataReference src
488 return $ case src' of
489 CmmReg reg' | reg == reg' -> CmmNop
490 new_src -> CmmAssign reg new_src
493 -> do addr' <- cmmExprConFold DataReference addr
494 src' <- cmmExprConFold DataReference src
495 return $ CmmStore addr' src'
498 -> do addr' <- cmmExprConFold JumpReference addr
499 return $ CmmJump addr' regs
501 CmmCall target regs args vols
502 -> do target' <- case target of
503 CmmForeignCall e conv -> do
504 e' <- cmmExprConFold CallReference e
505 return $ CmmForeignCall e' conv
506 other -> return other
507 args' <- mapM (\(arg, hint) -> do
508 arg' <- cmmExprConFold DataReference arg
509 return (arg', hint)) args
510 return $ CmmCall target' regs args' vols
512 CmmCondBranch test dest
513 -> do test' <- cmmExprConFold DataReference test
514 return $ case test' of
515 CmmLit (CmmInt 0 _) ->
516 CmmComment (mkFastString ("deleted: " ++
517 showSDoc (pprStmt stmt)))
519 CmmLit (CmmInt n _) -> CmmBranch dest
520 other -> CmmCondBranch test' dest
523 -> do expr' <- cmmExprConFold DataReference expr
524 return $ CmmSwitch expr' ids
530 cmmExprConFold referenceKind expr
533 -> do addr' <- cmmExprConFold DataReference addr
534 return $ CmmLoad addr' rep
537 -- For MachOps, we first optimize the children, and then we try
538 -- our hand at some constant-folding.
539 -> do args' <- mapM (cmmExprConFold DataReference) args
540 return $ cmmMachOpFold mop args'
542 CmmLit (CmmLabel lbl)
543 -> cmmMakeDynamicReference addImportCmmOpt referenceKind lbl
544 CmmLit (CmmLabelOff lbl off)
545 -> do dynRef <- cmmMakeDynamicReference addImportCmmOpt referenceKind lbl
546 return $ cmmMachOpFold (MO_Add wordRep) [
548 (CmmLit $ CmmInt (fromIntegral off) wordRep)
551 #if powerpc_TARGET_ARCH
552 -- On powerpc (non-PIC), it's easier to jump directly to a label than
553 -- to use the register table, so we replace these registers
554 -- with the corresponding labels:
555 CmmReg (CmmGlobal GCEnter1)
557 -> cmmExprConFold referenceKind $
558 CmmLit (CmmLabel (mkRtsCodeLabel SLIT( "__stg_gc_enter_1")))
559 CmmReg (CmmGlobal GCFun)
561 -> cmmExprConFold referenceKind $
562 CmmLit (CmmLabel (mkRtsCodeLabel SLIT( "__stg_gc_fun")))
565 CmmReg (CmmGlobal mid)
566 -- Replace register leaves with appropriate StixTrees for
567 -- the given target. MagicIds which map to a reg on this
568 -- arch are left unchanged. For the rest, BaseReg is taken
569 -- to mean the address of the reg table in MainCapability,
570 -- and for all others we generate an indirection to its
571 -- location in the register table.
572 -> case get_GlobalReg_reg_or_addr mid of
573 Left realreg -> return expr
576 BaseReg -> cmmExprConFold DataReference baseRegAddr
577 other -> cmmExprConFold DataReference
578 (CmmLoad baseRegAddr (globalRegRep mid))
579 -- eliminate zero offsets
581 -> cmmExprConFold referenceKind (CmmReg reg)
583 CmmRegOff (CmmGlobal mid) offset
584 -- RegOf leaves are just a shorthand form. If the reg maps
585 -- to a real reg, we keep the shorthand, otherwise, we just
586 -- expand it and defer to the above code.
587 -> case get_GlobalReg_reg_or_addr mid of
588 Left realreg -> return expr
590 -> cmmExprConFold DataReference (CmmMachOp (MO_Add wordRep) [
591 CmmReg (CmmGlobal mid),
592 CmmLit (CmmInt (fromIntegral offset)
597 -- -----------------------------------------------------------------------------