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