compiler/cmm/Cmm.hs

   1 {-# OPTIONS -fno-warn-name-shadowing -w #-}
   2 -- We'd like to use -fno-warn-orphans rather than -w, but old compilers
   3 -- don't understand it so building stage1 fails.
   4
   5 -----------------------------------------------------------------------------
   6 --
   7 -- Cmm data types
   8 --
   9 -- (c) The University of Glasgow 2004-2006
  10 --
  11 -----------------------------------------------------------------------------
  12
  13 module Cmm (
  14         GenCmm(..), Cmm, RawCmm,
  15         GenCmmTop(..), CmmTop, RawCmmTop,
  16         ListGraph(..),
  17         cmmMapGraph, cmmTopMapGraph,
  18         cmmMapGraphM, cmmTopMapGraphM,
  19         CmmInfo(..), UpdateFrame(..),
  20         CmmInfoTable(..), ClosureTypeInfo(..), ProfilingInfo(..), ClosureTypeTag,
  21         GenBasicBlock(..), CmmBasicBlock, blockId, blockStmts, mapBlockStmts,
  22         CmmReturnInfo(..),
  23         CmmStmt(..), CmmActuals, CmmFormal, CmmFormals, CmmHintFormals,
  24         CmmSafety(..),
  25         CmmCallTarget(..),
  26         CmmStatic(..), Section(..),
  27         CmmExpr(..), cmmExprRep, maybeInvertCmmExpr,
  28         CmmReg(..), cmmRegRep,
  29         CmmLit(..), cmmLitRep,
  30         LocalReg(..), localRegRep, localRegGCFollow, Kind(..),
  31         BlockId(..), freshBlockId,
  32         BlockEnv, emptyBlockEnv, lookupBlockEnv, extendBlockEnv, mkBlockEnv,
  33         BlockSet, emptyBlockSet, elemBlockSet, extendBlockSet,
  34         GlobalReg(..), globalRegRep,
  35
  36         node, nodeReg, spReg, hpReg, spLimReg
  37   ) where
  38
  39 -- ^ In order not to do violence to the import structure of the rest
  40 -- of the compiler, module Cmm re-exports a number of identifiers
  41 -- defined in 'CmmExpr'
  42
  43 #include "HsVersions.h"
  44
  45 import CmmExpr
  46 import MachOp
  47 import CLabel
  48 import ForeignCall
  49 import SMRep
  50 import ClosureInfo
  51 import Outputable
  52 import FastString
  53
  54 import Data.Word
  55
  56 import ZipCfg ( BlockId(..), freshBlockId
  57               , BlockEnv, emptyBlockEnv, lookupBlockEnv, extendBlockEnv, mkBlockEnv
  58               , BlockSet, emptyBlockSet, elemBlockSet, extendBlockSet
  59               )
  60
  61 -- A [[BlockId]] is a local label.
  62 -- Local labels must be unique within an entire compilation unit, not
  63 -- just a single top-level item, because local labels map one-to-one
  64 -- with assembly-language labels.
  65
  66 -----------------------------------------------------------------------------
  67 --              Cmm, CmmTop, CmmBasicBlock
  68 -----------------------------------------------------------------------------
  69
  70 -- A file is a list of top-level chunks.  These may be arbitrarily
  71 -- re-orderd during code generation.
  72
  73 -- GenCmm is abstracted over
  74 --   d, the type of static data elements in CmmData
  75 --   h, the static info preceding the code of a CmmProc
  76 --   g, the control-flow graph of a CmmProc
  77 --
  78 -- We expect there to be two main instances of this type:
  79 --   (a) C--, i.e. populated with various C-- constructs
  80 --              (Cmm and RawCmm below)
  81 --   (b) Native code, populated with data/instructions
  82 --
  83 -- A second family of instances based on ZipCfg is work in progress.
  84 --
  85 newtype GenCmm d h g = Cmm [GenCmmTop d h g]
  86
  87 -- | A top-level chunk, abstracted over the type of the contents of
  88 -- the basic blocks (Cmm or instructions are the likely instantiations).
  89 data GenCmmTop d h g
  90   = CmmProc     -- A procedure
  91      h                 -- Extra header such as the info table
  92      CLabel            -- Used to generate both info & entry labels
  93      CmmFormals        -- Argument locals live on entry (C-- procedure params)
  94      g                 -- Control-flow graph for the procedure's code
  95
  96   | CmmData     -- Static data
  97         Section
  98         [d]
  99
 100 -- | A control-flow graph represented as a list of extended basic blocks.
 101 newtype ListGraph i = ListGraph [GenBasicBlock i]
 102    -- ^ Code, may be empty.  The first block is the entry point.  The
 103    -- order is otherwise initially unimportant, but at some point the
 104    -- code gen will fix the order.
 105
 106    -- BlockIds must be unique across an entire compilation unit, since
 107    -- they are translated to assembly-language labels, which scope
 108    -- across a whole compilation unit.
 109
 110 -- | Cmm with the info table as a data type
 111 type Cmm    = GenCmm    CmmStatic CmmInfo (ListGraph CmmStmt)
 112 type CmmTop = GenCmmTop CmmStatic CmmInfo (ListGraph CmmStmt)
 113
 114 -- | Cmm with the info tables converted to a list of 'CmmStatic'
 115 type RawCmm    = GenCmm    CmmStatic [CmmStatic] (ListGraph CmmStmt)
 116 type RawCmmTop = GenCmmTop CmmStatic [CmmStatic] (ListGraph CmmStmt)
 117
 118
 119 -- A basic block containing a single label, at the beginning.
 120 -- The list of basic blocks in a top-level code block may be re-ordered.
 121 -- Fall-through is not allowed: there must be an explicit jump at the
 122 -- end of each basic block, but the code generator might rearrange basic
 123 -- blocks in order to turn some jumps into fallthroughs.
 124
 125 data GenBasicBlock i = BasicBlock BlockId [i]
 126 type CmmBasicBlock   = GenBasicBlock CmmStmt
 127
 128 instance UserOfLocalRegs i => UserOfLocalRegs (GenBasicBlock i) where
 129     foldRegsUsed f set (BasicBlock _ l) = foldRegsUsed f set l
 130
 131 blockId :: GenBasicBlock i -> BlockId
 132 -- The branch block id is that of the first block in
 133 -- the branch, which is that branch's entry point
 134 blockId (BasicBlock blk_id _ ) = blk_id
 135
 136 blockStmts :: GenBasicBlock i -> [i]
 137 blockStmts (BasicBlock _ stmts) = stmts
 138
 139
 140 mapBlockStmts :: (i -> i') -> GenBasicBlock i -> GenBasicBlock i'
 141 mapBlockStmts f (BasicBlock id bs) = BasicBlock id (map f bs)
 142 ----------------------------------------------------------------
 143 --   graph maps
 144 ----------------------------------------------------------------
 145
 146 cmmMapGraph    :: (g -> g') -> GenCmm    d h g -> GenCmm    d h g'
 147 cmmTopMapGraph :: (g -> g') -> GenCmmTop d h g -> GenCmmTop d h g'
 148
 149 cmmMapGraphM    :: Monad m => (String -> g -> m g') -> GenCmm    d h g -> m (GenCmm    d h g')
 150 cmmTopMapGraphM :: Monad m => (String -> g -> m g') -> GenCmmTop d h g -> m (GenCmmTop d h g')
 151
 152 cmmMapGraph f (Cmm tops) = Cmm $ map (cmmTopMapGraph f) tops
 153 cmmTopMapGraph f (CmmProc h l args g) = CmmProc h l args (f g)
 154 cmmTopMapGraph _ (CmmData s ds)       = CmmData s ds
 155
 156 cmmMapGraphM f (Cmm tops) = mapM (cmmTopMapGraphM f) tops >>= return . Cmm
 157 cmmTopMapGraphM f (CmmProc h l args g) = f (showSDoc $ ppr l) g >>= return . CmmProc h l args
 158 cmmTopMapGraphM _ (CmmData s ds)       = return $ CmmData s ds
 159
 160 -----------------------------------------------------------------------------
 161 --     Info Tables
 162 -----------------------------------------------------------------------------
 163
 164 data CmmInfo
 165   = CmmInfo
 166       (Maybe BlockId)     -- GC target. Nothing <=> CPS won't do stack check
 167       (Maybe UpdateFrame) -- Update frame
 168       CmmInfoTable        -- Info table
 169
 170 -- Info table as a haskell data type
 171 data CmmInfoTable
 172   = CmmInfoTable
 173       ProfilingInfo
 174       ClosureTypeTag -- Int
 175       ClosureTypeInfo
 176   | CmmNonInfoTable   -- Procedure doesn't need an info table
 177
 178 -- TODO: The GC target shouldn't really be part of CmmInfo
 179 -- as it doesn't appear in the resulting info table.
 180 -- It should be factored out.
 181
 182 data ClosureTypeInfo
 183   = ConstrInfo ClosureLayout ConstrTag ConstrDescription
 184   | FunInfo ClosureLayout C_SRT FunType FunArity ArgDescr SlowEntry
 185   | ThunkInfo ClosureLayout C_SRT
 186   | ThunkSelectorInfo SelectorOffset C_SRT
 187   | ContInfo
 188       [Maybe LocalReg]  -- Forced stack parameters
 189       C_SRT
 190
 191 data CmmReturnInfo = CmmMayReturn
 192                    | CmmNeverReturns
 193
 194 -- TODO: These types may need refinement
 195 data ProfilingInfo = ProfilingInfo CmmLit CmmLit -- closure_type, closure_desc
 196 type ClosureTypeTag = StgHalfWord
 197 type ClosureLayout = (StgHalfWord, StgHalfWord) -- ptrs, nptrs
 198 type ConstrTag = StgHalfWord
 199 type ConstrDescription = CmmLit
 200 type FunType = StgHalfWord
 201 type FunArity = StgHalfWord
 202 type SlowEntry = CmmLit
 203   -- ^We would like this to be a CLabel but
 204   -- for now the parser sets this to zero on an INFO_TABLE_FUN.
 205 type SelectorOffset = StgWord
 206
 207 -- | A frame that is to be pushed before entry to the function.
 208 -- Used to handle 'update' frames.
 209 data UpdateFrame =
 210     UpdateFrame
 211       CmmExpr    -- Frame header.  Behaves like the target of a 'jump'.
 212       [CmmExpr]  -- Frame remainder.  Behaves like the arguments of a 'jump'.
 213
 214 -----------------------------------------------------------------------------
 215 --              CmmStmt
 216 -- A "statement".  Note that all branches are explicit: there are no
 217 -- control transfers to computed addresses, except when transfering
 218 -- control to a new function.
 219 -----------------------------------------------------------------------------
 220
 221 data CmmStmt
 222   = CmmNop
 223   | CmmComment FastString
 224
 225   | CmmAssign CmmReg CmmExpr     -- Assign to register
 226
 227   | CmmStore CmmExpr CmmExpr     -- Assign to memory location.  Size is
 228                                  -- given by cmmExprRep of the rhs.
 229
 230   | CmmCall                      -- A call (forign, native or primitive), with
 231      CmmCallTarget
 232      CmmHintFormals              -- zero or more results
 233      CmmActuals                  -- zero or more arguments
 234      CmmSafety                   -- whether to build a continuation
 235      CmmReturnInfo
 236
 237   | CmmBranch BlockId             -- branch to another BB in this fn
 238
 239   | CmmCondBranch CmmExpr BlockId -- conditional branch
 240
 241   | CmmSwitch CmmExpr [Maybe BlockId]   -- Table branch
 242         -- The scrutinee is zero-based;
 243         --      zero -> first block
 244         --      one  -> second block etc
 245         -- Undefined outside range, and when there's a Nothing
 246
 247   | CmmJump CmmExpr      -- Jump to another C-- function,
 248       CmmActuals         -- with these parameters.
 249
 250   | CmmReturn            -- Return from a native C-- function,
 251       CmmActuals         -- with these return values.
 252
 253 type CmmActual      = CmmExpr
 254 type CmmActuals     = [(CmmActual,MachHint)]
 255 type CmmFormal      = LocalReg
 256 type CmmHintFormals = [(CmmFormal,MachHint)]
 257 type CmmFormals     = [CmmFormal]
 258 data CmmSafety      = CmmUnsafe | CmmSafe C_SRT
 259
 260 -- | enable us to fold used registers over 'CmmActuals' and 'CmmHintFormals'
 261 instance UserOfLocalRegs a => UserOfLocalRegs (a, MachHint) where
 262   foldRegsUsed f set (a, _) = foldRegsUsed f set a
 263
 264 instance UserOfLocalRegs CmmStmt where
 265   foldRegsUsed f set s = stmt s set
 266     where stmt (CmmNop)                  = id
 267           stmt (CmmComment {})           = id
 268           stmt (CmmAssign _ e)           = gen e
 269           stmt (CmmStore e1 e2)          = gen e1 . gen e2
 270           stmt (CmmCall target _ es _ _) = gen target . gen es
 271           stmt (CmmBranch _)             = id
 272           stmt (CmmCondBranch e _)       = gen e
 273           stmt (CmmSwitch e _)           = gen e
 274           stmt (CmmJump e es)            = gen e . gen es
 275           stmt (CmmReturn es)            = gen es
 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 {-
 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
 338 -----------------------------------------------------------------------------
 339 --              Static Data
 340 -----------------------------------------------------------------------------
 341
 342 data Section
 343   = Text
 344   | Data
 345   | ReadOnlyData
 346   | RelocatableReadOnlyData
 347   | UninitialisedData
 348   | ReadOnlyData16      -- .rodata.cst16 on x86_64, 16-byte aligned
 349   | OtherSection String
 350
 351 data CmmStatic
 352   = CmmStaticLit CmmLit
 353         -- a literal value, size given by cmmLitRep of the literal.
 354   | CmmUninitialised Int
 355         -- uninitialised data, N bytes long
 356   | CmmAlign Int
 357         -- align to next N-byte boundary (N must be a power of 2).
 358   | CmmDataLabel CLabel
 359         -- label the current position in this section.
 360   | CmmString [Word8]
 361         -- string of 8-bit values only, not zero terminated.
 362