ghc/compiler/absCSyn/AbsCSyn.lhs

   1 %
   2 % (c) The GRASP/AQUA Project, Glasgow University, 1992-1996
   3 %
   4 \section[AbstractC]{Abstract C: the last stop before machine code}
   5
   6 This ``Abstract C'' data type describes the raw Spineless Tagless
   7 machine model at a C-ish level; it is ``abstract'' in that it only
   8 includes C-like structures that we happen to need.  The conversion of
   9 programs from @StgSyntax@ (basically a functional language) to
  10 @AbstractC@ (basically imperative C) is the heart of code generation.
  11 From @AbstractC@, one may convert to real C (for portability) or to
  12 raw assembler/machine code.
  13
  14 \begin{code}
  15 module AbsCSyn {- (
  16         -- export everything
  17         AbstractC(..),
  18         CStmtMacro(..),
  19         CExprMacro(..),
  20         CAddrMode(..),
  21         ReturnInfo(..),
  22         mkAbstractCs, mkAbsCStmts, mkAlgAltsCSwitch,
  23         mkIntCLit,
  24         mkAbsCStmtList,
  25         mkCCostCentre,
  26
  27         -- RegRelatives
  28         RegRelative(..),
  29
  30         -- registers
  31         MagicId(..), node, infoptr,
  32         isVolatileReg, noLiveRegsMask, mkLiveRegsMask,
  33         CostRes(Cost)
  34     )-} where
  35
  36 #include "HsVersions.h"
  37
  38 import {-# SOURCE #-} ClosureInfo ( ClosureInfo )
  39 import {-# SOURCE #-} CLabel      ( CLabel )
  40
  41 #if  ! OMIT_NATIVE_CODEGEN
  42 import {-# SOURCE #-} MachMisc
  43 #endif
  44
  45 import Constants        ( mAX_Vanilla_REG, mAX_Float_REG,
  46                           mAX_Double_REG, lIVENESS_R1, lIVENESS_R2,
  47                           lIVENESS_R3, lIVENESS_R4, lIVENESS_R5,
  48                           lIVENESS_R6, lIVENESS_R7, lIVENESS_R8
  49                         )
  50 import HeapOffs         ( VirtualSpAOffset, VirtualSpBOffset,
  51                           VirtualHeapOffset, HeapOffset
  52                         )
  53 import CostCentre       ( CostCentre )
  54 import Literal          ( mkMachInt, Literal )
  55 import PrimRep          ( isFollowableRep, PrimRep(..) )
  56 import PrimOp           ( PrimOp )
  57 import Unique           ( Unique )
  58
  59 \end{code}
  60
  61 @AbstractC@ is a list of Abstract~C statements, but the data structure
  62 is tree-ish, for easier and more efficient putting-together.
  63 \begin{code}
  64 absCNop = AbsCNop
  65
  66 data AbstractC
  67   = AbsCNop
  68   | AbsCStmts           AbstractC AbstractC
  69
  70   -- and the individual stmts...
  71 \end{code}
  72
  73 A note on @CAssign@: In general, the type associated with an assignment
  74 is the type of the lhs.  However, when the lhs is a pointer to mixed
  75 types (e.g. SpB relative), the type of the assignment is the type of
  76 the rhs for float types, or the generic StgWord for all other types.
  77 (In particular, a CharRep on the rhs is promoted to IntRep when
  78 stored in a mixed type location.)
  79
  80 \begin{code}
  81   | CAssign
  82         CAddrMode       -- target
  83         CAddrMode       -- source
  84
  85   | CJump
  86         CAddrMode       -- Put this in the program counter
  87                         -- eg `CJump (CReg (VanillaReg PtrRep 1))' puts Ret1 in PC
  88                         -- Enter can be done by:
  89                         --        CJump (CVal NodeRel zeroOff)
  90
  91   | CFallThrough
  92         CAddrMode       -- Fall through into this routine
  93                         -- (for the benefit of the native code generators)
  94                         -- Equivalent to CJump in C land
  95
  96   | CReturn             -- This used to be RetVecRegRel
  97         CAddrMode       -- Any base address mode
  98         ReturnInfo      -- How to get the return address from the base address
  99
 100   | CSwitch CAddrMode
 101         [(Literal, AbstractC)]  -- alternatives
 102         AbstractC               -- default; if there is no real Abstract C in here
 103                                 -- (e.g., all comments; see function "nonemptyAbsC"),
 104                                 -- then that means the default _cannot_ occur.
 105                                 -- If there is only one alternative & no default code,
 106                                 -- then there is no need to check the tag.
 107                                 -- Therefore, e.g.:
 108                                 --  CSwitch m [(tag,code)] AbsCNop == code
 109
 110   | CCodeBlock CLabel AbstractC
 111                         -- [amode analog: CLabelledCode]
 112                         -- A labelled block of code; this "statement" is not
 113                         -- executed; rather, the labelled code will be hoisted
 114                         -- out to the top level (out of line) & it can be
 115                         -- jumped to.
 116
 117   | CInitHdr            -- to initialise the header of a closure (both fixed/var parts)
 118         ClosureInfo
 119         RegRelative     -- address of the info ptr
 120         CAddrMode       -- cost centre to place in closure
 121                         --   CReg CurCostCentre or CC_HDR(R1.p{-Node-})
 122         Bool            -- inplace update or allocate
 123
 124   | COpStmt
 125         [CAddrMode]     -- Results
 126         PrimOp
 127         [CAddrMode]     -- Arguments
 128         Int             -- Live registers (may be obtainable from volatility? ADR)
 129         [MagicId]       -- Potentially volatile/live registers
 130                         -- (to save/restore around the call/op)
 131
 132         -- INVARIANT: When a PrimOp which can cause GC is used, the
 133         -- only live data is tidily on the STG stacks or in the STG
 134         -- registers (the code generator ensures this).
 135         --
 136         -- Why this?  Because if the arguments were arbitrary
 137         -- addressing modes, they might be things like (Hp+6) which
 138         -- will get utterly spongled by GC.
 139
 140   | CSimultaneous       -- Perform simultaneously all the statements
 141         AbstractC       -- in the nested AbstractC.  They are only
 142                         -- allowed to be CAssigns, COpStmts and AbsCNops, so the
 143                         -- "simultaneous" part just concerns making
 144                         -- sure that permutations work.
 145                         -- For example { a := b, b := a }
 146                         --      needs to go via (at least one) temporary
 147
 148   -- see the notes about these next few; they follow below...
 149   | CMacroStmt          CStmtMacro      [CAddrMode]
 150   | CCallProfCtrMacro   FAST_STRING     [CAddrMode]
 151   | CCallProfCCMacro    FAST_STRING     [CAddrMode]
 152
 153   -- *** the next three [or so...] are DATA (those above are CODE) ***
 154
 155   | CStaticClosure
 156         CLabel  -- The (full, not base) label to use for labelling the closure.
 157         ClosureInfo
 158         CAddrMode       -- cost centre identifier to place in closure
 159         [CAddrMode]     -- free vars; ptrs, then non-ptrs
 160
 161
 162   | CClosureInfoAndCode
 163         ClosureInfo     -- Explains placement and layout of closure
 164         AbstractC       -- Slow entry point code
 165         (Maybe AbstractC)
 166                         -- Fast entry point code, if any
 167         CAddrMode       -- Address of update code; Nothing => should never be used
 168                         -- (which is the case for all except constructors)
 169         String          -- Closure description; NB we can't get this from
 170                         -- ClosureInfo, because the latter refers to the *right* hand
 171                         -- side of a defn, whereas the "description" refers to *left*
 172                         -- hand side
 173         Int             -- Liveness info; this is here because it is
 174                         -- easy to produce w/in the CgMonad; hard
 175                         -- thereafter.  (WDP 95/11)
 176
 177   | CRetVector                  -- Return vector with "holes"
 178                                 -- (Nothings) for the default
 179         CLabel                  -- vector-table label
 180         [Maybe CAddrMode]
 181         AbstractC               -- (and what to put in a "hole" [when Nothing])
 182
 183   | CRetUnVector        -- Direct return
 184         CLabel          -- unvector-table label
 185         CAddrMode       -- return code
 186
 187   | CFlatRetVector      -- A labelled block of static data
 188         CLabel          -- This is the flattened version of CRetVector
 189         [CAddrMode]
 190
 191   | CCostCentreDecl     -- A cost centre *declaration*
 192         Bool            -- True  <=> local => full declaration
 193                         -- False <=> extern; just say so
 194         CostCentre
 195
 196   | CClosureUpdInfo
 197         AbstractC       -- InRegs Info Table (CClosureInfoTable)
 198                         --                    ^^^^^^^^^^^^^^^^^
 199                         --                                out of date -- HWL
 200
 201   | CSplitMarker        -- Split into separate object modules here
 202 \end{code}
 203
 204 About @CMacroStmt@, etc.: notionally, they all just call some
 205 arbitrary C~macro or routine, passing the @CAddrModes@ as arguments.
 206 However, we distinguish between various flavours of these things,
 207 mostly just to keep things somewhat less wild and wooly.
 208
 209 \begin{description}
 210 \item[@CMacroStmt@:]
 211 Some {\em essential} bits of the STG execution model are done with C
 212 macros.  An example is @STK_CHK@, which checks for stack-space
 213 overflow.  This enumeration type lists all such macros:
 214 \begin{code}
 215 data CStmtMacro
 216   = ARGS_CHK_A_LOAD_NODE
 217   | ARGS_CHK_A
 218   | ARGS_CHK_B_LOAD_NODE
 219   | ARGS_CHK_B
 220   | HEAP_CHK
 221   | STK_CHK
 222   | UPD_CAF
 223   | UPD_IND
 224   | UPD_INPLACE_NOPTRS
 225   | UPD_INPLACE_PTRS
 226   | UPD_BH_UPDATABLE
 227   | UPD_BH_SINGLE_ENTRY
 228   | PUSH_STD_UPD_FRAME
 229   | POP_STD_UPD_FRAME
 230   | SET_TAG
 231   | GRAN_FETCH                  -- for GrAnSim only  -- HWL
 232   | GRAN_RESCHEDULE             -- for GrAnSim only  -- HWL
 233   | GRAN_FETCH_AND_RESCHEDULE   -- for GrAnSim only  -- HWL
 234   | THREAD_CONTEXT_SWITCH       -- for GrAnSim only  -- HWL
 235   | GRAN_YIELD                  -- for GrAnSim only  -- HWL
 236   deriving Text
 237 \end{code}
 238
 239 \item[@CCallProfCtrMacro@:]
 240 The @String@ names a macro that, if \tr{#define}d, will bump one/some
 241 of the STG-event profiling counters.
 242
 243 \item[@CCallProfCCMacro@:]
 244 The @String@ names a macro that, if \tr{#define}d, will perform some
 245 cost-centre-profiling-related action.
 246 \end{description}
 247
 248 HERE ARE SOME OLD NOTES ABOUT HEAP-CHK ENTRY POINTS:
 249
 250 \item[@CCallStgC@:]
 251 Some parts of the system, {\em notably the storage manager}, are
 252 implemented by C~routines that must know something about the internals
 253 of the STG world, e.g., where the heap-pointer is.  (The
 254 ``C-as-assembler'' documents describes this stuff in detail.)
 255
 256 This is quite a tricky business, especially with ``optimised~C,'' so
 257 we keep close tabs on these fellows.  This enumeration type lists all
 258 such ``STG~C'' routines:
 259
 260 HERE ARE SOME *OLD* NOTES ABOUT HEAP-CHK ENTRY POINTS:
 261
 262 Heap overflow invokes the garbage collector (of your choice :-), and
 263 we have different entry points, to tell the GC the exact configuration
 264 before it.
 265 \begin{description}
 266 \item[Branch of a boxed case:]
 267 The @Node@ register points off to somewhere legitimate, the @TagReg@
 268 holds the tag, and the @RetReg@ points to the code for the
 269 alterative which should be resumed. (ToDo: update)
 270
 271 \item[Branch of an unboxed case:]
 272 The @Node@ register points nowhere of any particular interest, a
 273 kind-specific register (@IntReg@, @FloatReg@, etc.) holds the unboxed
 274 value, and the @RetReg@ points to the code for the alternative
 275 which should be resumed. (ToDo: update)
 276
 277 \item[Closure entry:]
 278 The @Node@ register points to the closure, and the @RetReg@ points
 279 to the code to be resumed. (ToDo: update)
 280 \end{description}
 281
 282 %************************************************************************
 283 %*                                                                      *
 284 \subsection[CAddrMode]{C addressing modes}
 285 %*                                                                      *
 286 %************************************************************************
 287
 288 Addressing modes: these have @PrimitiveKinds@ pinned on them.
 289 \begin{code}
 290 data CAddrMode
 291   = CVal  RegRelative PrimRep
 292                         -- On RHS of assign: Contents of Magic[n]
 293                         -- On LHS of assign: location Magic[n]
 294                         -- (ie at addr Magic+n)
 295
 296   | CAddr RegRelative
 297                         -- On RHS of assign: Address of Magic[n]; ie Magic+n
 298                         --      n=0 gets the Magic location itself
 299                         --      (NB: n=0 case superceded by CReg)
 300                         -- On LHS of assign: only sensible if n=0,
 301                         --      which gives the magic location itself
 302                         --      (NB: superceded by CReg)
 303
 304   | CReg MagicId        -- To replace (CAddr MagicId 0)
 305
 306   | CTableEntry             -- CVal should be generalized to allow this
 307                 CAddrMode   -- Base
 308                 CAddrMode   -- Offset
 309                 PrimRep    -- For casting
 310
 311   | CTemp Unique PrimRep        -- Temporary locations
 312         -- ``Temporaries'' correspond to local variables in C, and registers in
 313         -- native code.
 314
 315   | CLbl    CLabel      -- Labels in the runtime system, etc.
 316                         -- See comment under CLabelledData about (String,Name)
 317             PrimRep     -- the kind is so we can generate accurate C decls
 318
 319   | CUnVecLbl           -- A choice of labels left up to the back end
 320               CLabel    -- direct
 321               CLabel    -- vectored
 322
 323   | CCharLike CAddrMode -- The address of a static char-like closure for
 324                         -- the specified character.  It is guaranteed to be in
 325                         -- the range 0..255.
 326
 327   | CIntLike CAddrMode  -- The address of a static int-like closure for the
 328                         -- specified small integer.  It is guaranteed to be in the
 329                         -- range mIN_INTLIKE..mAX_INTLIKE
 330
 331   | CString FAST_STRING -- The address of the null-terminated string
 332   | CLit    Literal
 333   | CLitLit FAST_STRING -- completely literal literal: just spit this String
 334                         -- into the C output
 335             PrimRep
 336
 337   | COffset HeapOffset  -- A literal constant, not an offset *from* anything!
 338                         -- ToDo: this should really be CLitOffset
 339
 340   | CCode AbstractC     -- Some code.  Used mainly for return addresses.
 341
 342   | CLabelledCode CLabel AbstractC  -- Almost defunct? (ToDo?) --JSM
 343                         -- Some code that must have a particular label
 344                         -- (which is jumpable to)
 345
 346   | CJoinPoint          -- This is used as the amode of a let-no-escape-bound variable
 347         VirtualSpAOffset        -- SpA and SpB values after any volatile free vars
 348         VirtualSpBOffset        -- of the rhs have been saved on stack.
 349                                 -- Just before the code for the thing is jumped to,
 350                                 -- SpA/B will be set to these values,
 351                                 -- and then any stack-passed args pushed,
 352                                 -- then the code for this thing will be entered
 353
 354   | CMacroExpr
 355         PrimRep         -- the kind of the result
 356         CExprMacro      -- the macro to generate a value
 357         [CAddrMode]     -- and its arguments
 358
 359   | CCostCentre         -- If Bool is True ==> it to be printed as a String,
 360         CostCentre      -- (*not* as a C identifier or some such).
 361         Bool            -- (It's not just the double-quotes on either side;
 362                         -- spaces and other funny characters will have been
 363                         -- fiddled in the non-String variant.)
 364
 365 mkCCostCentre cc
 366   = --ASSERT(not (currentOrSubsumedCosts cc))
 367     --FALSE: We do put subsumedCC in static closures
 368     CCostCentre cc False
 369 \end{code}
 370
 371 Various C macros for values which are dependent on the back-end layout.
 372
 373 \begin{code}
 374
 375 data CExprMacro
 376   = INFO_PTR
 377   | ENTRY_CODE
 378   | INFO_TAG
 379   | EVAL_TAG
 380   deriving(Text)
 381
 382 \end{code}
 383
 384 A tiny convenience:
 385 \begin{code}
 386 mkIntCLit :: Int -> CAddrMode
 387 mkIntCLit i = CLit (mkMachInt (toInteger i))
 388 \end{code}
 389
 390 %************************************************************************
 391 %*                                                                      *
 392 \subsection[RegRelative]{@RegRelatives@: ???}
 393 %*                                                                      *
 394 %************************************************************************
 395
 396 \begin{code}
 397 data RegRelative
 398   = HpRel        VirtualHeapOffset      -- virtual offset of Hp
 399                  VirtualHeapOffset      -- virtual offset of The Thing
 400   | SpARel       VirtualSpAOffset       -- virtual offset of SpA
 401                  VirtualSpAOffset       -- virtual offset of The Thing
 402   | SpBRel       VirtualSpBOffset       -- virtual offset of SpB
 403                  VirtualSpBOffset       -- virtual offset of The Thing
 404   | NodeRel      VirtualHeapOffset
 405
 406 data ReturnInfo
 407   = DirectReturn                        -- Jump directly, if possible
 408   | StaticVectoredReturn Int            -- Fixed tag, starting at zero
 409   | DynamicVectoredReturn CAddrMode     -- Dynamic tag given by amode, starting at zero
 410 \end{code}
 411
 412 %************************************************************************
 413 %*                                                                      *
 414 \subsection[MagicId]{@MagicIds@: registers and such}
 415 %*                                                                      *
 416 %************************************************************************
 417
 418 Much of what happens in Abstract-C is in terms of ``magic'' locations,
 419 such as the stack pointer, heap pointer, etc.  If possible, these will
 420 be held in registers.
 421
 422 Here are some notes about what's active when:
 423 \begin{description}
 424 \item[Always active:]
 425         Hp, HpLim, SpA, SpB, SuA, SuB
 426
 427 \item[Entry set:]
 428         ArgPtr1 (= Node)...
 429
 430 \item[Return set:]
 431 Ptr regs: RetPtr1 (= Node), RetPtr2...
 432 Int/char regs:  RetData1 (= TagReg = IntReg), RetData2...
 433 Float regs: RetFloat1, ...
 434 Double regs: RetDouble1, ...
 435 \end{description}
 436
 437 \begin{code}
 438 data MagicId
 439   = BaseReg     -- mentioned only in nativeGen
 440
 441   | StkOReg     -- mentioned only in nativeGen
 442
 443   -- Argument and return registers
 444   | VanillaReg          -- pointers, unboxed ints and chars
 445         PrimRep         -- PtrRep, IntRep, CharRep, StablePtrRep or ForeignObjRep
 446                         --      (in case we need to distinguish)
 447         FAST_INT        -- its number (1 .. mAX_Vanilla_REG)
 448
 449   | FloatReg    -- single-precision floating-point registers
 450         FAST_INT        -- its number (1 .. mAX_Float_REG)
 451
 452   | DoubleReg   -- double-precision floating-point registers
 453         FAST_INT        -- its number (1 .. mAX_Double_REG)
 454
 455   | TagReg      -- to return constructor tags; as almost all returns are vectored,
 456                 -- this is rarely used.
 457
 458   | RetReg      -- topmost return address from the B stack
 459
 460   | SpA         -- Stack ptr; points to last occupied stack location.
 461                 -- Stack grows downward.
 462   | SuA         -- mentioned only in nativeGen
 463
 464   | SpB         -- Basic values, return addresses and update frames.
 465                 -- Grows upward.
 466   | SuB         -- mentioned only in nativeGen
 467
 468   | Hp          -- Heap ptr; points to last occupied heap location.
 469                 -- Free space at lower addresses.
 470
 471   | HpLim       -- Heap limit register: mentioned only in nativeGen
 472
 473   | LivenessReg -- (parallel only) used when we need to record explicitly
 474                 -- what registers are live
 475
 476   | StdUpdRetVecReg     -- mentioned only in nativeGen
 477   | StkStubReg          -- register holding STK_STUB_closure (for stubbing dead stack slots)
 478
 479   | CurCostCentre -- current cost centre register.
 480
 481   | VoidReg -- see "VoidPrim" type; just a placeholder; no actual register
 482
 483 node    = VanillaReg PtrRep     ILIT(1) -- A convenient alias for Node
 484 infoptr = VanillaReg DataPtrRep ILIT(2) -- An alias for InfoPtr
 485
 486 --------------------
 487 noLiveRegsMask :: Int   -- Mask indicating nothing live
 488 noLiveRegsMask = 0
 489
 490 mkLiveRegsMask
 491         :: [MagicId]    -- Candidate live regs; depends what they have in them
 492         -> Int
 493
 494 mkLiveRegsMask regs
 495   = foldl do_reg noLiveRegsMask regs
 496   where
 497     do_reg acc (VanillaReg kind reg_no)
 498       | isFollowableRep kind
 499       = acc + (reg_tbl !! IBOX(reg_no _SUB_ ILIT(1)))
 500
 501     do_reg acc anything_else = acc
 502
 503     reg_tbl -- ToDo: mk Array!
 504       = [lIVENESS_R1, lIVENESS_R2, lIVENESS_R3, lIVENESS_R4,
 505          lIVENESS_R5, lIVENESS_R6, lIVENESS_R7, lIVENESS_R8]
 506 \end{code}
 507
 508 We need magical @Eq@ because @VanillaReg@s come in multiple flavors.
 509
 510 \begin{code}
 511 instance Eq MagicId where
 512     reg1 == reg2 = tag reg1 _EQ_ tag reg2
 513      where
 514         tag BaseReg          = (ILIT(0) :: FAST_INT)
 515         tag StkOReg          = ILIT(1)
 516         tag TagReg           = ILIT(2)
 517         tag RetReg           = ILIT(3)
 518         tag SpA              = ILIT(4)
 519         tag SuA              = ILIT(5)
 520         tag SpB              = ILIT(6)
 521         tag SuB              = ILIT(7)
 522         tag Hp               = ILIT(8)
 523         tag HpLim            = ILIT(9)
 524         tag LivenessReg      = ILIT(10)
 525         tag StdUpdRetVecReg  = ILIT(12)
 526         tag StkStubReg       = ILIT(13)
 527         tag CurCostCentre    = ILIT(14)
 528         tag VoidReg          = ILIT(15)
 529
 530         tag (VanillaReg _ i) = ILIT(15) _ADD_ i
 531
 532         tag (FloatReg i) = ILIT(15) _ADD_ maxv _ADD_ i
 533           where
 534             maxv = case mAX_Vanilla_REG of { IBOX(x) -> x }
 535
 536         tag (DoubleReg i) = ILIT(15) _ADD_ maxv _ADD_ maxf _ADD_ i
 537           where
 538             maxv = case mAX_Vanilla_REG of { IBOX(x) -> x }
 539             maxf = case mAX_Float_REG   of { IBOX(x) -> x }
 540 \end{code}
 541
 542 Returns True for any register that {\em potentially} dies across
 543 C calls (or anything near equivalent).  We just say @True@ and
 544 let the (machine-specific) registering macros sort things out...
 545 \begin{code}
 546 isVolatileReg :: MagicId -> Bool
 547
 548 isVolatileReg any = True
 549 --isVolatileReg (FloatReg _)    = True
 550 --isVolatileReg (DoubleReg _)   = True
 551 \end{code}
 552
 553 %************************************************************************
 554 %*                                                                      *
 555 \subsection[AbsCSyn-printing]{Pretty-printing Abstract~C}
 556 %*                                                                      *
 557 %************************************************************************
 558
 559 It's in \tr{PprAbsC.lhs}.