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