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,
  20         HintedCmmFormal, HintedCmmFormals, HintedCmmActual, HintedCmmActuals,
  21         CmmSafety(..),
  22         CmmCallTarget(..), CallishMachOp(..), pprCallishMachOp,
  23         ForeignHint(..), CmmHinted(..),
  24         CmmStatic(..), Section(..),
  25         module CmmExpr,
  26   ) where
  27
  28 #include "HsVersions.h"
  29
  30 import BlockId
  31 import CmmExpr
  32 import CLabel
  33 import ForeignCall
  34 import SMRep
  35
  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      CmmFormals              -- 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 FunArity ArgDescr SlowEntry
 168   | ThunkInfo  ClosureLayout C_SRT
 169   | ThunkSelectorInfo SelectorOffset C_SRT
 170   | ContInfo
 171       [Maybe LocalReg]  -- stack layout
 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 FunArity = StgHalfWord
 184 type SlowEntry = CmmLit
 185   -- We would like this to be a CLabel but
 186   -- for now the parser sets this to zero on an INFO_TABLE_FUN.
 187 type SelectorOffset = StgWord
 188
 189 -- | A frame that is to be pushed before entry to the function.
 190 -- Used to handle 'update' frames.
 191 data UpdateFrame =
 192     UpdateFrame
 193       CmmExpr    -- Frame header.  Behaves like the target of a 'jump'.
 194       [CmmExpr]  -- Frame remainder.  Behaves like the arguments of a 'jump'.
 195
 196 -----------------------------------------------------------------------------
 197 --              CmmStmt
 198 -- A "statement".  Note that all branches are explicit: there are no
 199 -- control transfers to computed addresses, except when transfering
 200 -- control to a new function.
 201 -----------------------------------------------------------------------------
 202
 203 data CmmStmt    -- Old-style
 204   = CmmNop
 205   | CmmComment FastString
 206
 207   | CmmAssign CmmReg CmmExpr     -- Assign to register
 208
 209   | CmmStore CmmExpr CmmExpr     -- Assign to memory location.  Size is
 210                                  -- given by cmmExprType of the rhs.
 211
 212   | CmmCall                      -- A call (forign, native or primitive), with
 213      CmmCallTarget
 214      HintedCmmFormals            -- zero or more results
 215      HintedCmmActuals            -- zero or more arguments
 216      CmmSafety                   -- whether to build a continuation
 217      CmmReturnInfo
 218
 219   | CmmBranch BlockId             -- branch to another BB in this fn
 220
 221   | CmmCondBranch CmmExpr BlockId -- conditional branch
 222
 223   | CmmSwitch CmmExpr [Maybe BlockId]   -- Table branch
 224         -- The scrutinee is zero-based;
 225         --      zero -> first block
 226         --      one  -> second block etc
 227         -- Undefined outside range, and when there's a Nothing
 228
 229   | CmmJump CmmExpr      -- Jump to another C-- function,
 230       HintedCmmActuals         -- with these parameters.  (parameters never used)
 231
 232   | CmmReturn            -- Return from a native C-- function,
 233       HintedCmmActuals         -- with these return values. (parameters never used)
 234
 235 type CmmActual = CmmExpr
 236 type CmmFormal = LocalReg
 237 type CmmActuals = [CmmActual]
 238 type CmmFormals = [CmmFormal]
 239
 240 data CmmHinted a = CmmHinted { hintlessCmm :: a, cmmHint :: ForeignHint }
 241                  deriving( Eq )
 242
 243 type HintedCmmActuals = [HintedCmmActual]
 244 type HintedCmmFormals = [HintedCmmFormal]
 245 type HintedCmmFormal  = CmmHinted CmmFormal
 246 type HintedCmmActual  = CmmHinted CmmActual
 247
 248 data CmmSafety      = CmmUnsafe | CmmSafe C_SRT
 249
 250 -- | enable us to fold used registers over 'CmmActuals' and 'CmmFormals'
 251 instance UserOfLocalRegs CmmStmt where
 252   foldRegsUsed f set s = stmt s set
 253     where stmt (CmmNop)                  = id
 254           stmt (CmmComment {})           = id
 255           stmt (CmmAssign _ e)           = gen e
 256           stmt (CmmStore e1 e2)          = gen e1 . gen e2
 257           stmt (CmmCall target _ es _ _) = gen target . gen es
 258           stmt (CmmBranch _)             = id
 259           stmt (CmmCondBranch e _)       = gen e
 260           stmt (CmmSwitch e _)           = gen e
 261           stmt (CmmJump e es)            = gen e . gen es
 262           stmt (CmmReturn es)            = gen es
 263           gen a set = foldRegsUsed f set a
 264
 265 instance UserOfLocalRegs CmmCallTarget where
 266     foldRegsUsed f set (CmmCallee e _) = foldRegsUsed f set e
 267     foldRegsUsed _ set (CmmPrim {})    = set
 268
 269 instance UserOfSlots CmmCallTarget where
 270     foldSlotsUsed f set (CmmCallee e _) = foldSlotsUsed f set e
 271     foldSlotsUsed _ set (CmmPrim {})    = set
 272
 273 instance UserOfLocalRegs a => UserOfLocalRegs (CmmHinted a) where
 274   foldRegsUsed f set a = foldRegsUsed f set (hintlessCmm a)
 275
 276 instance UserOfSlots a => UserOfSlots (CmmHinted a) where
 277   foldSlotsUsed f set a = foldSlotsUsed f set (hintlessCmm a)
 278
 279 instance DefinerOfLocalRegs a => DefinerOfLocalRegs (CmmHinted a) where
 280   foldRegsDefd f set a = foldRegsDefd f set (hintlessCmm a)
 281
 282 {-
 283 Discussion
 284 ~~~~~~~~~~
 285
 286 One possible problem with the above type is that the only way to do a
 287 non-local conditional jump is to encode it as a branch to a block that
 288 contains a single jump.  This leads to inefficient code in the back end.
 289
 290 [N.B. This problem will go away when we make the transition to the
 291 'zipper' form of control-flow graph, in which both targets of a
 292 conditional jump are explicit. ---NR]
 293
 294 One possible way to fix this would be:
 295
 296 data CmmStat =
 297   ...
 298   | CmmJump CmmBranchDest
 299   | CmmCondJump CmmExpr CmmBranchDest
 300   ...
 301
 302 data CmmBranchDest
 303   = Local BlockId
 304   | NonLocal CmmExpr [LocalReg]
 305
 306 In favour:
 307
 308 + one fewer constructors in CmmStmt
 309 + allows both cond branch and switch to jump to non-local destinations
 310
 311 Against:
 312
 313 - not strictly necessary: can already encode as branch+jump
 314 - not always possible to implement any better in the back end
 315 - could do the optimisation in the back end (but then plat-specific?)
 316 - C-- doesn't have it
 317 - back-end optimisation might be more general (jump shortcutting)
 318
 319 So we'll stick with the way it is, and add the optimisation to the NCG.
 320 -}
 321
 322 -----------------------------------------------------------------------------
 323 --              CmmCallTarget
 324 --
 325 -- The target of a CmmCall.
 326 -----------------------------------------------------------------------------
 327
 328 data CmmCallTarget
 329   = CmmCallee           -- Call a function (foreign or native)
 330         CmmExpr                 -- literal label <=> static call
 331                                 -- other expression <=> dynamic call
 332         CCallConv               -- The calling convention
 333
 334   | CmmPrim             -- Call a "primitive" (eg. sin, cos)
 335         CallishMachOp           -- These might be implemented as inline
 336                                 -- code by the backend.
 337   deriving Eq
 338
 339
 340 data ForeignHint
 341   = NoHint | AddrHint | SignedHint
 342   deriving( Eq )
 343         -- Used to give extra per-argument or per-result
 344         -- information needed by foreign calling conventions
 345
 346
 347 -- CallishMachOps tend to be implemented by foreign calls in some backends,
 348 -- so we separate them out.  In Cmm, these can only occur in a
 349 -- statement position, in contrast to an ordinary MachOp which can occur
 350 -- anywhere in an expression.
 351 data CallishMachOp
 352   = MO_F64_Pwr
 353   | MO_F64_Sin
 354   | MO_F64_Cos
 355   | MO_F64_Tan
 356   | MO_F64_Sinh
 357   | MO_F64_Cosh
 358   | MO_F64_Tanh
 359   | MO_F64_Asin
 360   | MO_F64_Acos
 361   | MO_F64_Atan
 362   | MO_F64_Log
 363   | MO_F64_Exp
 364   | MO_F64_Sqrt
 365   | MO_F32_Pwr
 366   | MO_F32_Sin
 367   | MO_F32_Cos
 368   | MO_F32_Tan
 369   | MO_F32_Sinh
 370   | MO_F32_Cosh
 371   | MO_F32_Tanh
 372   | MO_F32_Asin
 373   | MO_F32_Acos
 374   | MO_F32_Atan
 375   | MO_F32_Log
 376   | MO_F32_Exp
 377   | MO_F32_Sqrt
 378   | MO_WriteBarrier
 379   deriving (Eq, Show)
 380
 381 pprCallishMachOp :: CallishMachOp -> SDoc
 382 pprCallishMachOp mo = text (show mo)
 383
 384 -----------------------------------------------------------------------------
 385 --              Static Data
 386 -----------------------------------------------------------------------------
 387
 388 data Section
 389   = Text
 390   | Data
 391   | ReadOnlyData
 392   | RelocatableReadOnlyData
 393   | UninitialisedData
 394   | ReadOnlyData16      -- .rodata.cst16 on x86_64, 16-byte aligned
 395   | OtherSection String
 396
 397 data CmmStatic
 398   = CmmStaticLit CmmLit
 399         -- a literal value, size given by cmmLitRep of the literal.
 400   | CmmUninitialised Int
 401         -- uninitialised data, N bytes long
 402   | CmmAlign Int
 403         -- align to next N-byte boundary (N must be a power of 2).
 404   | CmmDataLabel CLabel
 405         -- label the current position in this section.
 406   | CmmString [Word8]
 407         -- string of 8-bit values only, not zero terminated.
 408