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