903853489f14972a0b16d31f1223f85047946455
[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(..), 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