ghc/compiler/nativeGen/AsmCodeGen.lhs

   1 %
   2 % (c) The AQUA Project, Glasgow University, 1993-1998
   3 %
   4
   5 \begin{code}
   6 module AsmCodeGen ( nativeCodeGen ) where
   7
   8 #include "HsVersions.h"
   9 #include "nativeGen/NCG.h"
  10
  11 import IO               ( Handle )
  12 import List             ( intersperse )
  13
  14 import MachMisc
  15 import MachRegs
  16 import MachCode
  17 import PprMach
  18
  19 import AbsCStixGen      ( genCodeAbstractC )
  20 import AbsCSyn          ( AbstractC, MagicId )
  21 import AsmRegAlloc      ( runRegAllocate )
  22 import OrdList          ( OrdList )
  23 import PrimOp           ( commutableOp, PrimOp(..) )
  24 import RegAllocInfo     ( mkMRegsState, MRegsState, findReservedRegs )
  25 import Stix             ( StixTree(..), StixReg(..),
  26                           pprStixTrees, CodeSegment(..) )
  27 import PrimRep          ( isFloatingRep, PrimRep(..) )
  28 import UniqSupply       ( returnUs, thenUs, mapUs, initUs,
  29                           initUs_, UniqSM, UniqSupply )
  30 import UniqFM           ( UniqFM, emptyUFM, addToUFM, lookupUFM )
  31 import MachMisc         ( IF_ARCH_i386(i386_insert_ffrees,) )
  32
  33 import Outputable
  34
  35 \end{code}
  36
  37 The 96/03 native-code generator has machine-independent and
  38 machine-dependent modules (those \tr{#include}'ing \tr{NCG.h}).
  39
  40 This module (@AsmCodeGen@) is the top-level machine-independent
  41 module.  It uses @AbsCStixGen.genCodeAbstractC@ to produce @StixTree@s
  42 (defined in module @Stix@), using support code from @StixInfo@ (info
  43 tables), @StixPrim@ (primitive operations), @StixMacro@ (Abstract C
  44 macros), and @StixInteger@ (GMP arbitrary-precision operations).
  45
  46 Before entering machine-dependent land, we do some machine-independent
  47 @genericOpt@imisations (defined below) on the @StixTree@s.
  48
  49 We convert to the machine-specific @Instr@ datatype with
  50 @stmt2Instrs@, assuming an ``infinite'' supply of registers.  We then
  51 use a machine-independent register allocator (@runRegAllocate@) to
  52 rejoin reality.  Obviously, @runRegAllocate@ has machine-specific
  53 helper functions (see about @RegAllocInfo@ below).
  54
  55 The machine-dependent bits break down as follows:
  56 \begin{description}
  57 \item[@MachRegs@:]  Everything about the target platform's machine
  58     registers (and immediate operands, and addresses, which tend to
  59     intermingle/interact with registers).
  60
  61 \item[@MachMisc@:]  Includes the @Instr@ datatype (possibly should
  62     have a module of its own), plus a miscellany of other things
  63     (e.g., @targetDoubleSize@, @smStablePtrTable@, ...)
  64
  65 \item[@MachCode@:]  @stmt2Instrs@ is where @Stix@ stuff turns into
  66     machine instructions.
  67
  68 \item[@PprMach@:] @pprInstr@ turns an @Instr@ into text (well, really
  69     an @Doc@).
  70
  71 \item[@RegAllocInfo@:] In the register allocator, we manipulate
  72     @MRegsState@s, which are @BitSet@s, one bit per machine register.
  73     When we want to say something about a specific machine register
  74     (e.g., ``it gets clobbered by this instruction''), we set/unset
  75     its bit.  Obviously, we do this @BitSet@ thing for efficiency
  76     reasons.
  77
  78     The @RegAllocInfo@ module collects together the machine-specific
  79     info needed to do register allocation.
  80 \end{description}
  81
  82 So, here we go:
  83
  84 \begin{code}
  85 nativeCodeGen :: AbstractC -> UniqSupply -> (SDoc, SDoc)
  86 nativeCodeGen absC us
  87    = let (stixRaw, us1) = initUs us (genCodeAbstractC absC)
  88          stixOpt        = map (map genericOpt) stixRaw
  89          insns          = initUs_ us1 (codeGen stixOpt)
  90          debug_stix     = vcat (map pprStixTrees stixOpt)
  91      in
  92          (debug_stix, insns)
  93 \end{code}
  94
  95 @codeGen@ is the top-level code-generation function:
  96 \begin{code}
  97 codeGen :: [[StixTree]] -> UniqSM SDoc
  98
  99 codeGen stixFinal
 100   = mapUs genMachCode stixFinal `thenUs` \ dynamic_codes ->
 101     let
 102         fp_kludge :: [Instr] -> [Instr]
 103         fp_kludge = IF_ARCH_i386(i386_insert_ffrees,id)
 104
 105         static_instrss :: [[Instr]]
 106         static_instrss = map fp_kludge (scheduleMachCode dynamic_codes)
 107         docs           = map (vcat . map pprInstr) static_instrss
 108     in
 109     returnUs (vcat (intersperse (char ' '
 110                                  $$ text "# ___stg_split_marker"
 111                                  $$ char ' ')
 112                     docs))
 113 \end{code}
 114
 115 Top level code generator for a chunk of stix code:
 116 \begin{code}
 117 genMachCode :: [StixTree] -> UniqSM InstrList
 118
 119 genMachCode stmts
 120   = mapUs stmt2Instrs stmts             `thenUs` \ blocks ->
 121     returnUs (foldr (.) id blocks asmVoid)
 122 \end{code}
 123
 124 The next bit does the code scheduling.  The scheduler must also deal
 125 with register allocation of temporaries.  Much parallelism can be
 126 exposed via the OrdList, but more might occur, so further analysis
 127 might be needed.
 128
 129 \begin{code}
 130 scheduleMachCode :: [InstrList] -> [[Instr]]
 131
 132 scheduleMachCode
 133   = map (runRegAllocate freeRegsState findReservedRegs)
 134   where
 135     freeRegsState = mkMRegsState (extractMappedRegNos freeRegs)
 136 \end{code}
 137
 138 %************************************************************************
 139 %*                                                                      *
 140 \subsection[NCOpt]{The Generic Optimiser}
 141 %*                                                                      *
 142 %************************************************************************
 143
 144 This is called between translating Abstract C to its Tree and actually
 145 using the Native Code Generator to generate the annotations.  It's a
 146 chance to do some strength reductions.
 147
 148 ** Remember these all have to be machine independent ***
 149
 150 Note that constant-folding should have already happened, but we might
 151 have introduced some new opportunities for constant-folding wrt
 152 address manipulations.
 153
 154 \begin{code}
 155 genericOpt :: StixTree -> StixTree
 156 \end{code}
 157
 158 For most nodes, just optimize the children.
 159
 160 \begin{code}
 161 genericOpt (StInd pk addr) = StInd pk (genericOpt addr)
 162
 163 genericOpt (StAssign pk dst src)
 164   = StAssign pk (genericOpt dst) (genericOpt src)
 165
 166 genericOpt (StJump addr) = StJump (genericOpt addr)
 167
 168 genericOpt (StCondJump addr test)
 169   = StCondJump addr (genericOpt test)
 170
 171 genericOpt (StCall fn cconv pk args)
 172   = StCall fn cconv pk (map genericOpt args)
 173 \end{code}
 174
 175 Fold indices together when the types match:
 176 \begin{code}
 177 genericOpt (StIndex pk (StIndex pk' base off) off')
 178   | pk == pk'
 179   = StIndex pk (genericOpt base)
 180                (genericOpt (StPrim IntAddOp [off, off']))
 181
 182 genericOpt (StIndex pk base off)
 183   = StIndex pk (genericOpt base) (genericOpt off)
 184 \end{code}
 185
 186 For PrimOps, we first optimize the children, and then we try our hand
 187 at some constant-folding.
 188
 189 \begin{code}
 190 genericOpt (StPrim op args) = primOpt op (map genericOpt args)
 191 \end{code}
 192
 193 Replace register leaves with appropriate StixTrees for the given
 194 target.
 195
 196 \begin{code}
 197 genericOpt leaf@(StReg (StixMagicId id))
 198   = case (stgReg id) of
 199         Always tree -> genericOpt tree
 200         Save _      -> leaf
 201
 202 genericOpt other = other
 203 \end{code}
 204
 205 Now, try to constant-fold the PrimOps.  The arguments have already
 206 been optimized and folded.
 207
 208 \begin{code}
 209 primOpt
 210     :: PrimOp           -- The operation from an StPrim
 211     -> [StixTree]       -- The optimized arguments
 212     -> StixTree
 213
 214 primOpt op arg@[StInt x]
 215   = case op of
 216         IntNegOp -> StInt (-x)
 217         _ -> StPrim op arg
 218
 219 primOpt op args@[StInt x, StInt y]
 220   = case op of
 221         CharGtOp -> StInt (if x > y  then 1 else 0)
 222         CharGeOp -> StInt (if x >= y then 1 else 0)
 223         CharEqOp -> StInt (if x == y then 1 else 0)
 224         CharNeOp -> StInt (if x /= y then 1 else 0)
 225         CharLtOp -> StInt (if x < y  then 1 else 0)
 226         CharLeOp -> StInt (if x <= y then 1 else 0)
 227         IntAddOp -> StInt (x + y)
 228         IntSubOp -> StInt (x - y)
 229         IntMulOp -> StInt (x * y)
 230         IntQuotOp -> StInt (x `quot` y)
 231         IntRemOp -> StInt (x `rem` y)
 232         IntGtOp -> StInt (if x > y  then 1 else 0)
 233         IntGeOp -> StInt (if x >= y then 1 else 0)
 234         IntEqOp -> StInt (if x == y then 1 else 0)
 235         IntNeOp -> StInt (if x /= y then 1 else 0)
 236         IntLtOp -> StInt (if x < y  then 1 else 0)
 237         IntLeOp -> StInt (if x <= y then 1 else 0)
 238         -- ToDo: WordQuotOp, WordRemOp.
 239         _ -> StPrim op args
 240 \end{code}
 241
 242 When possible, shift the constants to the right-hand side, so that we
 243 can match for strength reductions.  Note that the code generator will
 244 also assume that constants have been shifted to the right when
 245 possible.
 246
 247 \begin{code}
 248 primOpt op [x@(StInt _), y] | commutableOp op = primOpt op [y, x]
 249 \end{code}
 250
 251 We can often do something with constants of 0 and 1 ...
 252
 253 \begin{code}
 254 primOpt op args@[x, y@(StInt 0)]
 255   = case op of
 256         IntAddOp -> x
 257         IntSubOp -> x
 258         IntMulOp -> y
 259         AndOp    -> y
 260         OrOp     -> x
 261         XorOp    -> x
 262         SllOp    -> x
 263         SrlOp    -> x
 264         ISllOp   -> x
 265         ISraOp   -> x
 266         ISrlOp   -> x
 267         _        -> StPrim op args
 268
 269 primOpt op args@[x, y@(StInt 1)]
 270   = case op of
 271         IntMulOp  -> x
 272         IntQuotOp -> x
 273         IntRemOp  -> StInt 0
 274         _         -> StPrim op args
 275 \end{code}
 276
 277 Now look for multiplication/division by powers of 2 (integers).
 278
 279 \begin{code}
 280 primOpt op args@[x, y@(StInt n)]
 281   = case op of
 282         IntMulOp -> case exactLog2 n of
 283             Nothing -> StPrim op args
 284             Just p  -> StPrim ISllOp [x, StInt p]
 285         IntQuotOp -> case exactLog2 n of
 286             Nothing -> StPrim op args
 287             Just p  -> StPrim ISrlOp [x, StInt p]
 288         _ -> StPrim op args
 289 \end{code}
 290
 291 Anything else is just too hard.
 292
 293 \begin{code}
 294 primOpt op args = StPrim op args
 295 \end{code}