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