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