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         CmmInfo(..), ClosureTypeInfo(..), ProfilingInfo(..),
  13         GenBasicBlock(..), CmmBasicBlock, blockId, blockStmts,
  14         CmmStmt(..), CmmActuals, CmmFormal, CmmFormals, CmmHintFormals,
  15         CmmCallTarget(..),
  16         CmmStatic(..), Section(..),
  17         CmmExpr(..), cmmExprRep,
  18         CmmReg(..), cmmRegRep,
  19         CmmLit(..), cmmLitRep,
  20         LocalReg(..), localRegRep, localRegGCFollow, Kind(..),
  21         BlockId(..), BlockEnv,
  22         GlobalReg(..), globalRegRep,
  23
  24         node, nodeReg, spReg, hpReg, spLimReg
  25   ) where
  26
  27 #include "HsVersions.h"
  28
  29 import MachOp
  30 import CLabel
  31 import ForeignCall
  32 import SMRep
  33 import ClosureInfo
  34 import Unique
  35 import UniqFM
  36 import FastString
  37
  38 import Data.Word
  39
  40 -----------------------------------------------------------------------------
  41 --              Cmm, CmmTop, CmmBasicBlock
  42 -----------------------------------------------------------------------------
  43
  44 -- A file is a list of top-level chunks.  These may be arbitrarily
  45 -- re-orderd during code generation.
  46
  47 -- GenCmm is abstracted over
  48 --   (a) the type of static data elements
  49 --   (b) the contents of a basic block.
  50 -- We expect there to be two main instances of this type:
  51 --   (a) Plain C--, i.e. populated with CmmLit and CmmExpr respectively,
  52 --   (b) Native code, populated with instructions
  53 --
  54 newtype GenCmm d h i = Cmm [GenCmmTop d h i]
  55
  56 -- | Cmm with the info table as a data type
  57 type Cmm = GenCmm CmmStatic CmmInfo CmmStmt
  58
  59 -- | Cmm with the info tables converted to a list of 'CmmStatic'
  60 type RawCmm = GenCmm CmmStatic [CmmStatic] CmmStmt
  61
  62 -- A top-level chunk, abstracted over the type of the contents of
  63 -- the basic blocks (Cmm or instructions are the likely instantiations).
  64 data GenCmmTop d h i
  65   = CmmProc
  66      h                 -- Extra header such as the info table
  67      CLabel            -- Used to generate both info & entry labels
  68      CmmFormals        -- Argument locals live on entry (C-- procedure params)
  69      [GenBasicBlock i] -- Code, may be empty.  The first block is
  70                        -- the entry point.  The order is otherwise initially
  71                        -- unimportant, but at some point the code gen will
  72                        -- fix the order.
  73
  74                        -- the BlockId of the first block does not give rise
  75                        -- to a label.  To jump to the first block in a Proc,
  76                        -- use the appropriate CLabel.
  77
  78   -- some static data.
  79   | CmmData Section [d] -- constant values only
  80
  81 type CmmTop = GenCmmTop CmmStatic CmmInfo CmmStmt
  82 type RawCmmTop = GenCmmTop CmmStatic [CmmStatic] CmmStmt
  83
  84 -- A basic block containing a single label, at the beginning.
  85 -- The list of basic blocks in a top-level code block may be re-ordered.
  86 -- Fall-through is not allowed: there must be an explicit jump at the
  87 -- end of each basic block, but the code generator might rearrange basic
  88 -- blocks in order to turn some jumps into fallthroughs.
  89
  90 data GenBasicBlock i = BasicBlock BlockId [i]
  91   -- ToDo: Julian suggests that we might need to annotate this type
  92   -- with the out & in edges in the graph, i.e. two * [BlockId].  This
  93   -- information can be derived from the contents, but it might be
  94   -- helpful to cache it here.
  95
  96 type CmmBasicBlock = GenBasicBlock CmmStmt
  97
  98 blockId :: GenBasicBlock i -> BlockId
  99 -- The branch block id is that of the first block in
 100 -- the branch, which is that branch's entry point
 101 blockId (BasicBlock blk_id _ ) = blk_id
 102
 103 blockStmts :: GenBasicBlock i -> [i]
 104 blockStmts (BasicBlock _ stmts) = stmts
 105
 106 -----------------------------------------------------------------------------
 107 --     Info Tables
 108 -----------------------------------------------------------------------------
 109
 110 -- Info table as a haskell data type
 111 data CmmInfo
 112   = CmmInfo
 113       ProfilingInfo
 114       (Maybe BlockId) -- GC target
 115       ClosureTypeTag -- Int
 116       ClosureTypeInfo
 117   | CmmNonInfo   -- Procedure doesn't need an info table
 118       (Maybe BlockId) -- But we still need a GC target for it
 119
 120 -- TODO: The GC target shouldn't really be part of CmmInfo
 121 -- as it doesn't appear in the resulting info table.
 122 -- It should be factored out.
 123
 124 data ClosureTypeInfo
 125   = ConstrInfo ClosureLayout ConstrTag ConstrDescription
 126   | FunInfo ClosureLayout C_SRT FunType FunArity ArgDescr SlowEntry
 127   | ThunkInfo ClosureLayout C_SRT
 128   | ThunkSelectorInfo SelectorOffset C_SRT
 129   | ContInfo
 130       [Maybe LocalReg]  -- Forced stack parameters
 131       C_SRT
 132
 133 -- TODO: These types may need refinement
 134 data ProfilingInfo = ProfilingInfo CmmLit CmmLit -- closure_type, closure_desc
 135 type ClosureTypeTag = StgHalfWord
 136 type ClosureLayout = (StgHalfWord, StgHalfWord) -- pts, nptrs
 137 type ConstrTag = StgHalfWord
 138 type ConstrDescription = CmmLit
 139 type FunType = StgHalfWord
 140 type FunArity = StgHalfWord
 141 type SlowEntry = CLabel
 142 type SelectorOffset = StgWord
 143
 144 -----------------------------------------------------------------------------
 145 --              CmmStmt
 146 -- A "statement".  Note that all branches are explicit: there are no
 147 -- control transfers to computed addresses, except when transfering
 148 -- control to a new function.
 149 -----------------------------------------------------------------------------
 150
 151 data CmmStmt
 152   = CmmNop
 153   | CmmComment FastString
 154
 155   | CmmAssign CmmReg CmmExpr     -- Assign to register
 156
 157   | CmmStore CmmExpr CmmExpr     -- Assign to memory location.  Size is
 158                                  -- given by cmmExprRep of the rhs.
 159
 160   | CmmCall                      -- A foreign call, with
 161      CmmCallTarget
 162      CmmHintFormals              -- zero or more results
 163      CmmActuals                  -- zero or more arguments
 164      C_SRT                       -- SRT for the continuation of the call
 165
 166   | CmmBranch BlockId             -- branch to another BB in this fn
 167
 168   | CmmCondBranch CmmExpr BlockId -- conditional branch
 169
 170   | CmmSwitch CmmExpr [Maybe BlockId]   -- Table branch
 171         -- The scrutinee is zero-based;
 172         --      zero -> first block
 173         --      one  -> second block etc
 174         -- Undefined outside range, and when there's a Nothing
 175
 176   | CmmJump CmmExpr               -- Jump to another function,
 177       CmmActuals                  -- with these parameters.
 178
 179   | CmmReturn                     -- Return from a function,
 180       CmmActuals                  -- with these return values.
 181
 182 type CmmActual = CmmExpr
 183 type CmmActuals = [(CmmActual,MachHint)]
 184 type CmmFormal = LocalReg
 185 type CmmHintFormals = [(CmmFormal,MachHint)]
 186 type CmmFormals = [CmmFormal]
 187
 188 {-
 189 Discussion
 190 ~~~~~~~~~~
 191
 192 One possible problem with the above type is that the only way to do a
 193 non-local conditional jump is to encode it as a branch to a block that
 194 contains a single jump.  This leads to inefficient code in the back end.
 195
 196 One possible way to fix this would be:
 197
 198 data CmmStat =
 199   ...
 200   | CmmJump CmmBranchDest
 201   | CmmCondJump CmmExpr CmmBranchDest
 202   ...
 203
 204 data CmmBranchDest
 205   = Local BlockId
 206   | NonLocal CmmExpr [LocalReg]
 207
 208 In favour:
 209
 210 + one fewer constructors in CmmStmt
 211 + allows both cond branch and switch to jump to non-local destinations
 212
 213 Against:
 214
 215 - not strictly necessary: can already encode as branch+jump
 216 - not always possible to implement any better in the back end
 217 - could do the optimisation in the back end (but then plat-specific?)
 218 - C-- doesn't have it
 219 - back-end optimisation might be more general (jump shortcutting)
 220
 221 So we'll stick with the way it is, and add the optimisation to the NCG.
 222 -}
 223
 224 -----------------------------------------------------------------------------
 225 --              CmmCallTarget
 226 --
 227 -- The target of a CmmCall.
 228 -----------------------------------------------------------------------------
 229
 230 data CmmCallTarget
 231   = CmmForeignCall              -- Call to a foreign function
 232         CmmExpr                 -- literal label <=> static call
 233                                 -- other expression <=> dynamic call
 234         CCallConv               -- The calling convention
 235
 236   | CmmPrim                     -- Call to a "primitive" (eg. sin, cos)
 237         CallishMachOp           -- These might be implemented as inline
 238                                 -- code by the backend.
 239
 240 -----------------------------------------------------------------------------
 241 --              CmmExpr
 242 -- An expression.  Expressions have no side effects.
 243 -----------------------------------------------------------------------------
 244
 245 data CmmExpr
 246   = CmmLit CmmLit               -- Literal
 247   | CmmLoad CmmExpr MachRep     -- Read memory location
 248   | CmmReg CmmReg               -- Contents of register
 249   | CmmMachOp MachOp [CmmExpr]  -- Machine operation (+, -, *, etc.)
 250   | CmmRegOff CmmReg Int
 251         -- CmmRegOff reg i
 252         --        ** is shorthand only, meaning **
 253         -- CmmMachOp (MO_S_Add rep (CmmReg reg) (CmmLit (CmmInt i rep)))
 254         --      where rep = cmmRegRep reg
 255   deriving Eq
 256
 257 cmmExprRep :: CmmExpr -> MachRep
 258 cmmExprRep (CmmLit lit)      = cmmLitRep lit
 259 cmmExprRep (CmmLoad _ rep)   = rep
 260 cmmExprRep (CmmReg reg)      = cmmRegRep reg
 261 cmmExprRep (CmmMachOp op _)  = resultRepOfMachOp op
 262 cmmExprRep (CmmRegOff reg _) = cmmRegRep reg
 263
 264 data CmmReg
 265   = CmmLocal  LocalReg
 266   | CmmGlobal GlobalReg
 267   deriving( Eq )
 268
 269 cmmRegRep :: CmmReg -> MachRep
 270 cmmRegRep (CmmLocal  reg)       = localRegRep reg
 271 cmmRegRep (CmmGlobal reg)       = globalRegRep reg
 272
 273 -- | Whether a 'LocalReg' is a GC followable pointer
 274 data Kind = KindPtr | KindNonPtr deriving (Eq)
 275
 276 data LocalReg
 277   = LocalReg
 278       !Unique   -- ^ Identifier
 279       MachRep   -- ^ Type
 280       Kind      -- ^ Should the GC follow as a pointer
 281
 282 instance Eq LocalReg where
 283   (LocalReg u1 _ _) == (LocalReg u2 _ _) = u1 == u2
 284
 285 instance Uniquable LocalReg where
 286   getUnique (LocalReg uniq _ _) = uniq
 287
 288 localRegRep :: LocalReg -> MachRep
 289 localRegRep (LocalReg _ rep _) = rep
 290
 291 localRegGCFollow (LocalReg _ _ p) = p
 292
 293 data CmmLit
 294   = CmmInt Integer  MachRep
 295         -- Interpretation: the 2's complement representation of the value
 296         -- is truncated to the specified size.  This is easier than trying
 297         -- to keep the value within range, because we don't know whether
 298         -- it will be used as a signed or unsigned value (the MachRep doesn't
 299         -- distinguish between signed & unsigned).
 300   | CmmFloat  Rational MachRep
 301   | CmmLabel    CLabel                  -- Address of label
 302   | CmmLabelOff CLabel Int              -- Address of label + byte offset
 303
 304         -- Due to limitations in the C backend, the following
 305         -- MUST ONLY be used inside the info table indicated by label2
 306         -- (label2 must be the info label), and label1 must be an
 307         -- SRT, a slow entrypoint or a large bitmap (see the Mangler)
 308         -- Don't use it at all unless tablesNextToCode.
 309         -- It is also used inside the NCG during when generating
 310         -- position-independent code.
 311   | CmmLabelDiffOff CLabel CLabel Int   -- label1 - label2 + offset
 312   deriving Eq
 313
 314 cmmLitRep :: CmmLit -> MachRep
 315 cmmLitRep (CmmInt _ rep)    = rep
 316 cmmLitRep (CmmFloat _ rep)  = rep
 317 cmmLitRep (CmmLabel _)      = wordRep
 318 cmmLitRep (CmmLabelOff _ _) = wordRep
 319 cmmLitRep (CmmLabelDiffOff _ _ _) = wordRep
 320
 321 -----------------------------------------------------------------------------
 322 -- A local label.
 323
 324 -- Local labels must be unique within a single compilation unit.
 325
 326 newtype BlockId = BlockId Unique
 327   deriving (Eq,Ord)
 328
 329 instance Uniquable BlockId where
 330   getUnique (BlockId u) = u
 331
 332 type BlockEnv a = UniqFM {- BlockId -} a
 333
 334 -----------------------------------------------------------------------------
 335 --              Static Data
 336 -----------------------------------------------------------------------------
 337
 338 data Section
 339   = Text
 340   | Data
 341   | ReadOnlyData
 342   | RelocatableReadOnlyData
 343   | UninitialisedData
 344   | ReadOnlyData16      -- .rodata.cst16 on x86_64, 16-byte aligned
 345   | OtherSection String
 346
 347 data CmmStatic
 348   = CmmStaticLit CmmLit
 349         -- a literal value, size given by cmmLitRep of the literal.
 350   | CmmUninitialised Int
 351         -- uninitialised data, N bytes long
 352   | CmmAlign Int
 353         -- align to next N-byte boundary (N must be a power of 2).
 354   | CmmDataLabel CLabel
 355         -- label the current position in this section.
 356   | CmmString [Word8]
 357         -- string of 8-bit values only, not zero terminated.
 358
 359 -----------------------------------------------------------------------------
 360 --              Global STG registers
 361 -----------------------------------------------------------------------------
 362
 363 data GlobalReg
 364   -- Argument and return registers
 365   = VanillaReg                  -- pointers, unboxed ints and chars
 366         {-# UNPACK #-} !Int     -- its number
 367
 368   | FloatReg            -- single-precision floating-point registers
 369         {-# UNPACK #-} !Int     -- its number
 370
 371   | DoubleReg           -- double-precision floating-point registers
 372         {-# UNPACK #-} !Int     -- its number
 373
 374   | LongReg             -- long int registers (64-bit, really)
 375         {-# UNPACK #-} !Int     -- its number
 376
 377   -- STG registers
 378   | Sp                  -- Stack ptr; points to last occupied stack location.
 379   | SpLim               -- Stack limit
 380   | Hp                  -- Heap ptr; points to last occupied heap location.
 381   | HpLim               -- Heap limit register
 382   | CurrentTSO          -- pointer to current thread's TSO
 383   | CurrentNursery      -- pointer to allocation area
 384   | HpAlloc             -- allocation count for heap check failure
 385
 386                 -- We keep the address of some commonly-called
 387                 -- functions in the register table, to keep code
 388                 -- size down:
 389   | GCEnter1            -- stg_gc_enter_1
 390   | GCFun               -- stg_gc_fun
 391
 392   -- Base offset for the register table, used for accessing registers
 393   -- which do not have real registers assigned to them.  This register
 394   -- will only appear after we have expanded GlobalReg into memory accesses
 395   -- (where necessary) in the native code generator.
 396   | BaseReg
 397
 398   -- Base Register for PIC (position-independent code) calculations
 399   -- Only used inside the native code generator. It's exact meaning differs
 400   -- from platform to platform (see module PositionIndependentCode).
 401   | PicBaseReg
 402
 403   deriving( Eq
 404 #ifdef DEBUG
 405         , Show
 406 #endif
 407          )
 408
 409 -- convenient aliases
 410 spReg, hpReg, spLimReg, nodeReg :: CmmReg
 411 spReg = CmmGlobal Sp
 412 hpReg = CmmGlobal Hp
 413 spLimReg = CmmGlobal SpLim
 414 nodeReg = CmmGlobal node
 415
 416 node :: GlobalReg
 417 node = VanillaReg 1
 418
 419 globalRegRep :: GlobalReg -> MachRep
 420 globalRegRep (VanillaReg _)     = wordRep
 421 globalRegRep (FloatReg _)       = F32
 422 globalRegRep (DoubleReg _)      = F64
 423 globalRegRep (LongReg _)        = I64
 424 globalRegRep _                  = wordRep