Add two local type signatures
[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 ListGraph(..),
13 cmmMapGraph, cmmTopMapGraph,
14 cmmMapGraphM, cmmTopMapGraphM,
15 CmmInfo(..), UpdateFrame(..),
16 CmmInfoTable(..), HasStaticClosure, ClosureTypeInfo(..), ConstrDescription,
17 ProfilingInfo(..), ClosureTypeTag,
18 GenBasicBlock(..), CmmBasicBlock, blockId, blockStmts, mapBlockStmts,
19 CmmReturnInfo(..),
20 CmmStmt(..), CmmActual, CmmActuals, CmmFormal, CmmFormals,
21 HintedCmmFormal, HintedCmmFormals, HintedCmmActual, HintedCmmActuals,
22 CmmSafety(..),
23 CmmCallTarget(..), CallishMachOp(..), pprCallishMachOp,
24 ForeignHint(..), CmmHinted(..),
25 CmmStatic(..), Section(..),
26 module CmmExpr,
27 ) where
28
29 #include "HsVersions.h"
30
31 import BlockId
32 import CmmExpr
33 import CLabel
34 import ForeignCall
35 import SMRep
36
37 import ClosureInfo
38 import Outputable
39 import FastString
40
41 import Data.Word
42
43
44 -- A [[BlockId]] is a local label.
45 -- Local labels must be unique within an entire compilation unit, not
46 -- just a single top-level item, because local labels map one-to-one
47 -- with assembly-language labels.
48
49 -----------------------------------------------------------------------------
50 -- Cmm, CmmTop, CmmBasicBlock
51 -----------------------------------------------------------------------------
52
53 -- A file is a list of top-level chunks. These may be arbitrarily
54 -- re-orderd during code generation.
55
56 -- GenCmm is abstracted over
57 -- d, the type of static data elements in CmmData
58 -- h, the static info preceding the code of a CmmProc
59 -- g, the control-flow graph of a CmmProc
60 --
61 -- We expect there to be two main instances of this type:
62 -- (a) C--, i.e. populated with various C-- constructs
63 -- (Cmm and RawCmm below)
64 -- (b) Native code, populated with data/instructions
65 --
66 -- A second family of instances based on ZipCfg is work in progress.
67 --
68 newtype GenCmm d h g = Cmm [GenCmmTop d h g]
69
70 -- | A top-level chunk, abstracted over the type of the contents of
71 -- the basic blocks (Cmm or instructions are the likely instantiations).
72 data GenCmmTop d h g
73 = CmmProc -- A procedure
74 h -- Extra header such as the info table
75 CLabel -- Used to generate both info & entry labels
76 CmmFormals -- Argument locals live on entry (C-- procedure params)
77 -- XXX Odd that there are no kinds, but there you are ---NR
78 g -- Control-flow graph for the procedure's code
79
80 | CmmData -- Static data
81 Section
82 [d]
83
84 -- | A control-flow graph represented as a list of extended basic blocks.
85 newtype ListGraph i = ListGraph [GenBasicBlock i]
86 -- ^ Code, may be empty. The first block is the entry point. The
87 -- order is otherwise initially unimportant, but at some point the
88 -- code gen will fix the order.
89
90 -- BlockIds must be unique across an entire compilation unit, since
91 -- they are translated to assembly-language labels, which scope
92 -- across a whole compilation unit.
93
94 -- | Cmm with the info table as a data type
95 type Cmm = GenCmm CmmStatic CmmInfo (ListGraph CmmStmt)
96 type CmmTop = GenCmmTop CmmStatic CmmInfo (ListGraph CmmStmt)
97
98 -- | Cmm with the info tables converted to a list of 'CmmStatic'
99 type RawCmm = GenCmm CmmStatic [CmmStatic] (ListGraph CmmStmt)
100 type RawCmmTop = GenCmmTop CmmStatic [CmmStatic] (ListGraph CmmStmt)
101
102
103 -- A basic block containing a single label, at the beginning.
104 -- The list of basic blocks in a top-level code block may be re-ordered.
105 -- Fall-through is not allowed: there must be an explicit jump at the
106 -- end of each basic block, but the code generator might rearrange basic
107 -- blocks in order to turn some jumps into fallthroughs.
108
109 data GenBasicBlock i = BasicBlock BlockId [i]
110 type CmmBasicBlock = GenBasicBlock CmmStmt
111
112 instance UserOfLocalRegs i => UserOfLocalRegs (GenBasicBlock i) where
113 foldRegsUsed f set (BasicBlock _ l) = foldRegsUsed f set l
114
115 blockId :: GenBasicBlock i -> BlockId
116 -- The branch block id is that of the first block in
117 -- the branch, which is that branch's entry point
118 blockId (BasicBlock blk_id _ ) = blk_id
119
120 blockStmts :: GenBasicBlock i -> [i]
121 blockStmts (BasicBlock _ stmts) = stmts
122
123
124 mapBlockStmts :: (i -> i') -> GenBasicBlock i -> GenBasicBlock i'
125 mapBlockStmts f (BasicBlock id bs) = BasicBlock id (map f bs)
126 ----------------------------------------------------------------
127 -- graph maps
128 ----------------------------------------------------------------
129
130 cmmMapGraph :: (g -> g') -> GenCmm d h g -> GenCmm d h g'
131 cmmTopMapGraph :: (g -> g') -> GenCmmTop d h g -> GenCmmTop d h g'
132
133 cmmMapGraphM :: Monad m => (String -> g -> m g') -> GenCmm d h g -> m (GenCmm d h g')
134 cmmTopMapGraphM :: Monad m => (String -> g -> m g') -> GenCmmTop d h g -> m (GenCmmTop d h g')
135
136 cmmMapGraph f (Cmm tops) = Cmm $ map (cmmTopMapGraph f) tops
137 cmmTopMapGraph f (CmmProc h l args g) = CmmProc h l args (f g)
138 cmmTopMapGraph _ (CmmData s ds) = CmmData s ds
139
140 cmmMapGraphM f (Cmm tops) = mapM (cmmTopMapGraphM f) tops >>= return . Cmm
141 cmmTopMapGraphM f (CmmProc h l args g) =
142 f (showSDoc $ ppr l) g >>= return . CmmProc h l args
143 cmmTopMapGraphM _ (CmmData s ds) = return $ CmmData s ds
144
145 -----------------------------------------------------------------------------
146 -- Info Tables
147 -----------------------------------------------------------------------------
148
149 data CmmInfo
150 = CmmInfo
151 (Maybe BlockId) -- GC target. Nothing <=> CPS won't do stack check
152 -- JD: NOT USED BY NEW CODE GEN
153 (Maybe UpdateFrame) -- Update frame
154 CmmInfoTable -- Info table
155
156 -- Info table as a haskell data type
157 data CmmInfoTable
158 = CmmInfoTable
159 HasStaticClosure
160 ProfilingInfo
161 ClosureTypeTag -- Int
162 ClosureTypeInfo
163 | CmmNonInfoTable -- Procedure doesn't need an info table
164
165 type HasStaticClosure = Bool
166
167 -- TODO: The GC target shouldn't really be part of CmmInfo
168 -- as it doesn't appear in the resulting info table.
169 -- It should be factored out.
170
171 data ClosureTypeInfo
172 = ConstrInfo ClosureLayout ConstrTag ConstrDescription
173 | FunInfo ClosureLayout C_SRT FunArity ArgDescr SlowEntry
174 | ThunkInfo ClosureLayout C_SRT
175 | ThunkSelectorInfo SelectorOffset C_SRT
176 | ContInfo
177 [Maybe LocalReg] -- Stack layout: Just x, an item x
178 -- Nothing: a 1-word gap
179 -- Start of list is the *young* end
180 C_SRT
181
182 data CmmReturnInfo = CmmMayReturn
183 | CmmNeverReturns
184 deriving ( Eq )
185
186 -- TODO: These types may need refinement
187 data ProfilingInfo = ProfilingInfo CmmLit CmmLit -- closure_type, closure_desc
188 type ClosureTypeTag = StgHalfWord
189 type ClosureLayout = (StgHalfWord, StgHalfWord) -- ptrs, nptrs
190 type ConstrTag = StgHalfWord
191 type ConstrDescription = CmmLit
192 type FunArity = StgHalfWord
193 type SlowEntry = CmmLit
194 -- We would like this to be a CLabel but
195 -- for now the parser sets this to zero on an INFO_TABLE_FUN.
196 type SelectorOffset = StgWord
197
198 -- | A frame that is to be pushed before entry to the function.
199 -- Used to handle 'update' frames.
200 data UpdateFrame =
201 UpdateFrame
202 CmmExpr -- Frame header. Behaves like the target of a 'jump'.
203 [CmmExpr] -- Frame remainder. Behaves like the arguments of a 'jump'.
204
205 -----------------------------------------------------------------------------
206 -- CmmStmt
207 -- A "statement". Note that all branches are explicit: there are no
208 -- control transfers to computed addresses, except when transfering
209 -- control to a new function.
210 -----------------------------------------------------------------------------
211
212 data CmmStmt -- Old-style
213 = CmmNop
214 | CmmComment FastString
215
216 | CmmAssign CmmReg CmmExpr -- Assign to register
217
218 | CmmStore CmmExpr CmmExpr -- Assign to memory location. Size is
219 -- given by cmmExprType of the rhs.
220
221 | CmmCall -- A call (forign, native or primitive), with
222 CmmCallTarget
223 HintedCmmFormals -- zero or more results
224 HintedCmmActuals -- zero or more arguments
225 CmmSafety -- whether to build a continuation
226 CmmReturnInfo
227
228 | CmmBranch BlockId -- branch to another BB in this fn
229
230 | CmmCondBranch CmmExpr BlockId -- conditional branch
231
232 | CmmSwitch CmmExpr [Maybe BlockId] -- Table branch
233 -- The scrutinee is zero-based;
234 -- zero -> first block
235 -- one -> second block etc
236 -- Undefined outside range, and when there's a Nothing
237
238 | CmmJump CmmExpr -- Jump to another C-- function,
239 HintedCmmActuals -- with these parameters. (parameters never used)
240
241 | CmmReturn -- Return from a native C-- function,
242 HintedCmmActuals -- with these return values. (parameters never used)
243
244 type CmmActual = CmmExpr
245 type CmmFormal = LocalReg
246 type CmmActuals = [CmmActual]
247 type CmmFormals = [CmmFormal]
248
249 data CmmHinted a = CmmHinted { hintlessCmm :: a, cmmHint :: ForeignHint }
250 deriving( Eq )
251
252 type HintedCmmActuals = [HintedCmmActual]
253 type HintedCmmFormals = [HintedCmmFormal]
254 type HintedCmmFormal = CmmHinted CmmFormal
255 type HintedCmmActual = CmmHinted CmmActual
256
257 data CmmSafety = CmmUnsafe | CmmSafe C_SRT
258
259 -- | enable us to fold used registers over 'CmmActuals' and 'CmmFormals'
260 instance UserOfLocalRegs CmmStmt where
261 foldRegsUsed f (set::b) s = stmt s set
262 where
263 stmt :: CmmStmt -> b -> b
264 stmt (CmmNop) = id
265 stmt (CmmComment {}) = id
266 stmt (CmmAssign _ e) = gen e
267 stmt (CmmStore e1 e2) = gen e1 . gen e2
268 stmt (CmmCall target _ es _ _) = gen target . gen es
269 stmt (CmmBranch _) = id
270 stmt (CmmCondBranch e _) = gen e
271 stmt (CmmSwitch e _) = gen e
272 stmt (CmmJump e es) = gen e . gen es
273 stmt (CmmReturn es) = gen es
274
275 gen :: UserOfLocalRegs a => a -> b -> b
276 gen a set = foldRegsUsed f set a
277
278 instance UserOfLocalRegs CmmCallTarget where
279 foldRegsUsed f set (CmmCallee e _) = foldRegsUsed f set e
280 foldRegsUsed _ set (CmmPrim {}) = set
281
282 instance UserOfSlots CmmCallTarget where
283 foldSlotsUsed f set (CmmCallee e _) = foldSlotsUsed f set e
284 foldSlotsUsed _ set (CmmPrim {}) = set
285
286 instance UserOfLocalRegs a => UserOfLocalRegs (CmmHinted a) where
287 foldRegsUsed f set a = foldRegsUsed f set (hintlessCmm a)
288
289 instance UserOfSlots a => UserOfSlots (CmmHinted a) where
290 foldSlotsUsed f set a = foldSlotsUsed f set (hintlessCmm a)
291
292 instance DefinerOfLocalRegs a => DefinerOfLocalRegs (CmmHinted a) where
293 foldRegsDefd f set a = foldRegsDefd f set (hintlessCmm a)
294
295 {-
296 Discussion
297 ~~~~~~~~~~
298
299 One possible problem with the above type is that the only way to do a
300 non-local conditional jump is to encode it as a branch to a block that
301 contains a single jump. This leads to inefficient code in the back end.
302
303 [N.B. This problem will go away when we make the transition to the
304 'zipper' form of control-flow graph, in which both targets of a
305 conditional jump are explicit. ---NR]
306
307 One possible way to fix this would be:
308
309 data CmmStat =
310 ...
311 | CmmJump CmmBranchDest
312 | CmmCondJump CmmExpr CmmBranchDest
313 ...
314
315 data CmmBranchDest
316 = Local BlockId
317 | NonLocal CmmExpr [LocalReg]
318
319 In favour:
320
321 + one fewer constructors in CmmStmt
322 + allows both cond branch and switch to jump to non-local destinations
323
324 Against:
325
326 - not strictly necessary: can already encode as branch+jump
327 - not always possible to implement any better in the back end
328 - could do the optimisation in the back end (but then plat-specific?)
329 - C-- doesn't have it
330 - back-end optimisation might be more general (jump shortcutting)
331
332 So we'll stick with the way it is, and add the optimisation to the NCG.
333 -}
334
335 -----------------------------------------------------------------------------
336 -- CmmCallTarget
337 --
338 -- The target of a CmmCall.
339 -----------------------------------------------------------------------------
340
341 data CmmCallTarget
342 = CmmCallee -- Call a function (foreign or native)
343 CmmExpr -- literal label <=> static call
344 -- other expression <=> dynamic call
345 CCallConv -- The calling convention
346
347 | CmmPrim -- Call a "primitive" (eg. sin, cos)
348 CallishMachOp -- These might be implemented as inline
349 -- code by the backend.
350 deriving Eq
351
352
353 data ForeignHint
354 = NoHint | AddrHint | SignedHint
355 deriving( Eq )
356 -- Used to give extra per-argument or per-result
357 -- information needed by foreign calling conventions
358
359
360 -- CallishMachOps tend to be implemented by foreign calls in some backends,
361 -- so we separate them out. In Cmm, these can only occur in a
362 -- statement position, in contrast to an ordinary MachOp which can occur
363 -- anywhere in an expression.
364 data CallishMachOp
365 = MO_F64_Pwr
366 | MO_F64_Sin
367 | MO_F64_Cos
368 | MO_F64_Tan
369 | MO_F64_Sinh
370 | MO_F64_Cosh
371 | MO_F64_Tanh
372 | MO_F64_Asin
373 | MO_F64_Acos
374 | MO_F64_Atan
375 | MO_F64_Log
376 | MO_F64_Exp
377 | MO_F64_Sqrt
378 | MO_F32_Pwr
379 | MO_F32_Sin
380 | MO_F32_Cos
381 | MO_F32_Tan
382 | MO_F32_Sinh
383 | MO_F32_Cosh
384 | MO_F32_Tanh
385 | MO_F32_Asin
386 | MO_F32_Acos
387 | MO_F32_Atan
388 | MO_F32_Log
389 | MO_F32_Exp
390 | MO_F32_Sqrt
391 | MO_WriteBarrier
392 | MO_Touch -- Keep variables live (when using interior pointers)
393 deriving (Eq, Show)
394
395 pprCallishMachOp :: CallishMachOp -> SDoc
396 pprCallishMachOp mo = text (show mo)
397
398 -----------------------------------------------------------------------------
399 -- Static Data
400 -----------------------------------------------------------------------------
401
402 data Section
403 = Text
404 | Data
405 | ReadOnlyData
406 | RelocatableReadOnlyData
407 | UninitialisedData
408 | ReadOnlyData16 -- .rodata.cst16 on x86_64, 16-byte aligned
409 | OtherSection String
410
411 data CmmStatic
412 = CmmStaticLit CmmLit
413 -- a literal value, size given by cmmLitRep of the literal.
414 | CmmUninitialised Int
415 -- uninitialised data, N bytes long
416 | CmmAlign Int
417 -- align to next N-byte boundary (N must be a power of 2).
418 | CmmDataLabel CLabel
419 -- label the current position in this section.
420 | CmmString [Word8]
421 -- string of 8-bit values only, not zero terminated.
422