compiler/cmm/Cmm.hs

   1 -----------------------------------------------------------------------------
   2 --
   3 -- Cmm data types
   4 --
   5 -- (c) The University of Glasgow 2004-2006
   6 --
   7 -----------------------------------------------------------------------------
   8
   9 module Cmm (
  10         GenCmm(..), Cmm, RawCmm,
  11         GenCmmTop(..), CmmTop, RawCmmTop,
  12         ListGraph(..),
  13         cmmMapGraph, cmmTopMapGraph,
  14         cmmMapGraphM, cmmTopMapGraphM,
  15         CmmInfo(..), UpdateFrame(..),
  16         CmmInfoTable(..), HasStaticClosure, ClosureTypeInfo(..), ConstrDescription,
  17         ProfilingInfo(..), ClosureTypeTag,
  18         GenBasicBlock(..), CmmBasicBlock, blockId, blockStmts, mapBlockStmts,
  19         CmmReturnInfo(..),
  20         CmmStmt(..), CmmActual, CmmActuals, CmmFormal, CmmFormals,
  21         HintedCmmFormal, HintedCmmFormals, HintedCmmActual, HintedCmmActuals,
  22         CmmSafety(..),
  23         CmmCallTarget(..), CallishMachOp(..), pprCallishMachOp,
  24         ForeignHint(..), CmmHinted(..),
  25         CmmStatic(..), Section(..),
  26         module CmmExpr,
  27   ) where
  28
  29 #include "HsVersions.h"
  30
  31 import BlockId
  32 import CmmExpr
  33 import CLabel
  34 import ForeignCall
  35 import SMRep
  36
  37 import ClosureInfo
  38 import Outputable
  39 import FastString
  40
  41 import Data.Word
  42
  43
  44 -- A [[BlockId]] is a local label.
  45 -- Local labels must be unique within an entire compilation unit, not
  46 -- just a single top-level item, because local labels map one-to-one
  47 -- with assembly-language labels.
  48
  49 -----------------------------------------------------------------------------
  50 --  Cmm, CmmTop, CmmBasicBlock
  51 -----------------------------------------------------------------------------
  52
  53 -- A file is a list of top-level chunks.  These may be arbitrarily
  54 -- re-orderd during code generation.
  55
  56 -- GenCmm is abstracted over
  57 --   d, the type of static data elements in CmmData
  58 --   h, the static info preceding the code of a CmmProc
  59 --   g, the control-flow graph of a CmmProc
  60 --
  61 -- We expect there to be two main instances of this type:
  62 --   (a) C--, i.e. populated with various C-- constructs
  63 --       (Cmm and RawCmm below)
  64 --   (b) Native code, populated with data/instructions
  65 --
  66 -- A second family of instances based on ZipCfg is work in progress.
  67 --
  68 newtype GenCmm d h g = Cmm [GenCmmTop d h g]
  69
  70 -- | A top-level chunk, abstracted over the type of the contents of
  71 -- the basic blocks (Cmm or instructions are the likely instantiations).
  72 data GenCmmTop d h g
  73   = CmmProc     -- A procedure
  74      h                 -- Extra header such as the info table
  75      CLabel            -- Used to generate both info & entry labels
  76      CmmFormals              -- Argument locals live on entry (C-- procedure params)
  77                        -- XXX Odd that there are no kinds, but there you are ---NR
  78      g                 -- Control-flow graph for the procedure's code
  79
  80   | CmmData     -- Static data
  81         Section
  82         [d]
  83
  84 -- | A control-flow graph represented as a list of extended basic blocks.
  85 newtype ListGraph i = ListGraph [GenBasicBlock i]
  86    -- ^ Code, may be empty.  The first block is the entry point.  The
  87    -- order is otherwise initially unimportant, but at some point the
  88    -- code gen will fix the order.
  89
  90    -- BlockIds must be unique across an entire compilation unit, since
  91    -- they are translated to assembly-language labels, which scope
  92    -- across a whole compilation unit.
  93
  94 -- | Cmm with the info table as a data type
  95 type Cmm    = GenCmm    CmmStatic CmmInfo (ListGraph CmmStmt)
  96 type CmmTop = GenCmmTop CmmStatic CmmInfo (ListGraph CmmStmt)
  97
  98 -- | Cmm with the info tables converted to a list of 'CmmStatic'
  99 type RawCmm    = GenCmm    CmmStatic [CmmStatic] (ListGraph CmmStmt)
 100 type RawCmmTop = GenCmmTop CmmStatic [CmmStatic] (ListGraph CmmStmt)
 101
 102
 103 -- A basic block containing a single label, at the beginning.
 104 -- The list of basic blocks in a top-level code block may be re-ordered.
 105 -- Fall-through is not allowed: there must be an explicit jump at the
 106 -- end of each basic block, but the code generator might rearrange basic
 107 -- blocks in order to turn some jumps into fallthroughs.
 108
 109 data GenBasicBlock i = BasicBlock BlockId [i]
 110 type CmmBasicBlock   = GenBasicBlock CmmStmt
 111
 112 instance UserOfLocalRegs i => UserOfLocalRegs (GenBasicBlock i) where
 113     foldRegsUsed f set (BasicBlock _ l) = foldRegsUsed f set l
 114
 115 blockId :: GenBasicBlock i -> BlockId
 116 -- The branch block id is that of the first block in
 117 -- the branch, which is that branch's entry point
 118 blockId (BasicBlock blk_id _ ) = blk_id
 119
 120 blockStmts :: GenBasicBlock i -> [i]
 121 blockStmts (BasicBlock _ stmts) = stmts
 122
 123
 124 mapBlockStmts :: (i -> i') -> GenBasicBlock i -> GenBasicBlock i'
 125 mapBlockStmts f (BasicBlock id bs) = BasicBlock id (map f bs)
 126 ----------------------------------------------------------------
 127 --   graph maps
 128 ----------------------------------------------------------------
 129
 130 cmmMapGraph    :: (g -> g') -> GenCmm    d h g -> GenCmm    d h g'
 131 cmmTopMapGraph :: (g -> g') -> GenCmmTop d h g -> GenCmmTop d h g'
 132
 133 cmmMapGraphM    :: Monad m => (String -> g -> m g') -> GenCmm    d h g -> m (GenCmm    d h g')
 134 cmmTopMapGraphM :: Monad m => (String -> g -> m g') -> GenCmmTop d h g -> m (GenCmmTop d h g')
 135
 136 cmmMapGraph f (Cmm tops) = Cmm $ map (cmmTopMapGraph f) tops
 137 cmmTopMapGraph f (CmmProc h l args g) = CmmProc h l args (f g)
 138 cmmTopMapGraph _ (CmmData s ds)             = CmmData s ds
 139
 140 cmmMapGraphM f (Cmm tops) = mapM (cmmTopMapGraphM f) tops >>= return . Cmm
 141 cmmTopMapGraphM f (CmmProc h l args g) =
 142   f (showSDoc $ ppr l) g >>= return . CmmProc h l args
 143 cmmTopMapGraphM _ (CmmData s ds)       = return $ CmmData s ds
 144
 145 -----------------------------------------------------------------------------
 146 --     Info Tables
 147 -----------------------------------------------------------------------------
 148
 149 data CmmInfo
 150   = CmmInfo
 151       (Maybe BlockId)     -- GC target. Nothing <=> CPS won't do stack check
 152                           -- JD: NOT USED BY NEW CODE GEN
 153       (Maybe UpdateFrame) -- Update frame
 154       CmmInfoTable        -- Info table
 155
 156 -- Info table as a haskell data type
 157 data CmmInfoTable
 158   = CmmInfoTable
 159       HasStaticClosure
 160       ProfilingInfo
 161       ClosureTypeTag -- Int
 162       ClosureTypeInfo
 163   | CmmNonInfoTable   -- Procedure doesn't need an info table
 164
 165 type HasStaticClosure = Bool
 166
 167 -- TODO: The GC target shouldn't really be part of CmmInfo
 168 -- as it doesn't appear in the resulting info table.
 169 -- It should be factored out.
 170
 171 data ClosureTypeInfo
 172   = ConstrInfo ClosureLayout ConstrTag ConstrDescription
 173   | FunInfo    ClosureLayout C_SRT FunArity ArgDescr SlowEntry
 174   | ThunkInfo  ClosureLayout C_SRT
 175   | ThunkSelectorInfo SelectorOffset C_SRT
 176   | ContInfo
 177       [Maybe LocalReg]  -- Stack layout: Just x, an item x
 178                         --               Nothing: a 1-word gap
 179                         -- Start of list is the *young* end
 180       C_SRT
 181
 182 data CmmReturnInfo = CmmMayReturn
 183                    | CmmNeverReturns
 184     deriving ( Eq )
 185
 186 -- TODO: These types may need refinement
 187 data ProfilingInfo = ProfilingInfo CmmLit CmmLit -- closure_type, closure_desc
 188 type ClosureTypeTag = StgHalfWord
 189 type ClosureLayout = (StgHalfWord, StgHalfWord) -- ptrs, nptrs
 190 type ConstrTag = StgHalfWord
 191 type ConstrDescription = CmmLit
 192 type FunArity = StgHalfWord
 193 type SlowEntry = CmmLit
 194   -- We would like this to be a CLabel but
 195   -- for now the parser sets this to zero on an INFO_TABLE_FUN.
 196 type SelectorOffset = StgWord
 197
 198 -- | A frame that is to be pushed before entry to the function.
 199 -- Used to handle 'update' frames.
 200 data UpdateFrame =
 201     UpdateFrame
 202       CmmExpr    -- Frame header.  Behaves like the target of a 'jump'.
 203       [CmmExpr]  -- Frame remainder.  Behaves like the arguments of a 'jump'.
 204
 205 -----------------------------------------------------------------------------
 206 --              CmmStmt
 207 -- A "statement".  Note that all branches are explicit: there are no
 208 -- control transfers to computed addresses, except when transfering
 209 -- control to a new function.
 210 -----------------------------------------------------------------------------
 211
 212 data CmmStmt    -- Old-style
 213   = CmmNop
 214   | CmmComment FastString
 215
 216   | CmmAssign CmmReg CmmExpr     -- Assign to register
 217
 218   | CmmStore CmmExpr CmmExpr     -- Assign to memory location.  Size is
 219                                  -- given by cmmExprType of the rhs.
 220
 221   | CmmCall                      -- A call (forign, native or primitive), with
 222      CmmCallTarget
 223      HintedCmmFormals            -- zero or more results
 224      HintedCmmActuals            -- zero or more arguments
 225      CmmSafety                   -- whether to build a continuation
 226      CmmReturnInfo
 227
 228   | CmmBranch BlockId             -- branch to another BB in this fn
 229
 230   | CmmCondBranch CmmExpr BlockId -- conditional branch
 231
 232   | CmmSwitch CmmExpr [Maybe BlockId]   -- Table branch
 233         -- The scrutinee is zero-based;
 234         --      zero -> first block
 235         --      one  -> second block etc
 236         -- Undefined outside range, and when there's a Nothing
 237
 238   | CmmJump CmmExpr      -- Jump to another C-- function,
 239       HintedCmmActuals         -- with these parameters.  (parameters never used)
 240
 241   | CmmReturn            -- Return from a native C-- function,
 242       HintedCmmActuals         -- with these return values. (parameters never used)
 243
 244 type CmmActual = CmmExpr
 245 type CmmFormal = LocalReg
 246 type CmmActuals = [CmmActual]
 247 type CmmFormals = [CmmFormal]
 248
 249 data CmmHinted a = CmmHinted { hintlessCmm :: a, cmmHint :: ForeignHint }
 250                  deriving( Eq )
 251
 252 type HintedCmmActuals = [HintedCmmActual]
 253 type HintedCmmFormals = [HintedCmmFormal]
 254 type HintedCmmFormal  = CmmHinted CmmFormal
 255 type HintedCmmActual  = CmmHinted CmmActual
 256
 257 data CmmSafety      = CmmUnsafe | CmmSafe C_SRT
 258
 259 -- | enable us to fold used registers over 'CmmActuals' and 'CmmFormals'
 260 instance UserOfLocalRegs CmmStmt where
 261   foldRegsUsed f (set::b) s = stmt s set
 262     where
 263       stmt :: CmmStmt -> b -> b
 264       stmt (CmmNop)                  = id
 265       stmt (CmmComment {})           = id
 266       stmt (CmmAssign _ e)           = gen e
 267       stmt (CmmStore e1 e2)          = gen e1 . gen e2
 268       stmt (CmmCall target _ es _ _) = gen target . gen es
 269       stmt (CmmBranch _)             = id
 270       stmt (CmmCondBranch e _)       = gen e
 271       stmt (CmmSwitch e _)           = gen e
 272       stmt (CmmJump e es)            = gen e . gen es
 273       stmt (CmmReturn es)            = gen es
 274
 275       gen :: UserOfLocalRegs a => a -> b -> b
 276       gen a set = foldRegsUsed f set a
 277
 278 instance UserOfLocalRegs CmmCallTarget where
 279     foldRegsUsed f set (CmmCallee e _) = foldRegsUsed f set e
 280     foldRegsUsed _ set (CmmPrim {})    = set
 281
 282 instance UserOfSlots CmmCallTarget where
 283     foldSlotsUsed f set (CmmCallee e _) = foldSlotsUsed f set e
 284     foldSlotsUsed _ set (CmmPrim {})    = set
 285
 286 instance UserOfLocalRegs a => UserOfLocalRegs (CmmHinted a) where
 287   foldRegsUsed f set a = foldRegsUsed f set (hintlessCmm a)
 288
 289 instance UserOfSlots a => UserOfSlots (CmmHinted a) where
 290   foldSlotsUsed f set a = foldSlotsUsed f set (hintlessCmm a)
 291
 292 instance DefinerOfLocalRegs a => DefinerOfLocalRegs (CmmHinted a) where
 293   foldRegsDefd f set a = foldRegsDefd f set (hintlessCmm a)
 294
 295 {-
 296 Discussion
 297 ~~~~~~~~~~
 298
 299 One possible problem with the above type is that the only way to do a
 300 non-local conditional jump is to encode it as a branch to a block that
 301 contains a single jump.  This leads to inefficient code in the back end.
 302
 303 [N.B. This problem will go away when we make the transition to the
 304 'zipper' form of control-flow graph, in which both targets of a
 305 conditional jump are explicit. ---NR]
 306
 307 One possible way to fix this would be:
 308
 309 data CmmStat =
 310   ...
 311   | CmmJump CmmBranchDest
 312   | CmmCondJump CmmExpr CmmBranchDest
 313   ...
 314
 315 data CmmBranchDest
 316   = Local BlockId
 317   | NonLocal CmmExpr [LocalReg]
 318
 319 In favour:
 320
 321 + one fewer constructors in CmmStmt
 322 + allows both cond branch and switch to jump to non-local destinations
 323
 324 Against:
 325
 326 - not strictly necessary: can already encode as branch+jump
 327 - not always possible to implement any better in the back end
 328 - could do the optimisation in the back end (but then plat-specific?)
 329 - C-- doesn't have it
 330 - back-end optimisation might be more general (jump shortcutting)
 331
 332 So we'll stick with the way it is, and add the optimisation to the NCG.
 333 -}
 334
 335 -----------------------------------------------------------------------------
 336 --              CmmCallTarget
 337 --
 338 -- The target of a CmmCall.
 339 -----------------------------------------------------------------------------
 340
 341 data CmmCallTarget
 342   = CmmCallee           -- Call a function (foreign or native)
 343         CmmExpr                 -- literal label <=> static call
 344                                 -- other expression <=> dynamic call
 345         CCallConv               -- The calling convention
 346
 347   | CmmPrim             -- Call a "primitive" (eg. sin, cos)
 348         CallishMachOp           -- These might be implemented as inline
 349                                 -- code by the backend.
 350   deriving Eq
 351
 352
 353 data ForeignHint
 354   = NoHint | AddrHint | SignedHint
 355   deriving( Eq )
 356         -- Used to give extra per-argument or per-result
 357         -- information needed by foreign calling conventions
 358
 359
 360 -- CallishMachOps tend to be implemented by foreign calls in some backends,
 361 -- so we separate them out.  In Cmm, these can only occur in a
 362 -- statement position, in contrast to an ordinary MachOp which can occur
 363 -- anywhere in an expression.
 364 data CallishMachOp
 365   = MO_F64_Pwr
 366   | MO_F64_Sin
 367   | MO_F64_Cos
 368   | MO_F64_Tan
 369   | MO_F64_Sinh
 370   | MO_F64_Cosh
 371   | MO_F64_Tanh
 372   | MO_F64_Asin
 373   | MO_F64_Acos
 374   | MO_F64_Atan
 375   | MO_F64_Log
 376   | MO_F64_Exp
 377   | MO_F64_Sqrt
 378   | MO_F32_Pwr
 379   | MO_F32_Sin
 380   | MO_F32_Cos
 381   | MO_F32_Tan
 382   | MO_F32_Sinh
 383   | MO_F32_Cosh
 384   | MO_F32_Tanh
 385   | MO_F32_Asin
 386   | MO_F32_Acos
 387   | MO_F32_Atan
 388   | MO_F32_Log
 389   | MO_F32_Exp
 390   | MO_F32_Sqrt
 391   | MO_WriteBarrier
 392   | MO_Touch         -- Keep variables live (when using interior pointers)
 393   deriving (Eq, Show)
 394
 395 pprCallishMachOp :: CallishMachOp -> SDoc
 396 pprCallishMachOp mo = text (show mo)
 397
 398 -----------------------------------------------------------------------------
 399 --              Static Data
 400 -----------------------------------------------------------------------------
 401
 402 data Section
 403   = Text
 404   | Data
 405   | ReadOnlyData
 406   | RelocatableReadOnlyData
 407   | UninitialisedData
 408   | ReadOnlyData16      -- .rodata.cst16 on x86_64, 16-byte aligned
 409   | OtherSection String
 410
 411 data CmmStatic
 412   = CmmStaticLit CmmLit
 413         -- a literal value, size given by cmmLitRep of the literal.
 414   | CmmUninitialised Int
 415         -- uninitialised data, N bytes long
 416   | CmmAlign Int
 417         -- align to next N-byte boundary (N must be a power of 2).
 418   | CmmDataLabel CLabel
 419         -- label the current position in this section.
 420   | CmmString [Word8]
 421         -- string of 8-bit values only, not zero terminated.
 422