1 -----------------------------------------------------------------------------
5 -- (c) The University of Glasgow 2004-2006
7 -----------------------------------------------------------------------------
10 GenCmm(..), Cmm, RawCmm,
11 GenCmmTop(..), CmmTop, RawCmmTop,
13 cmmMapGraph, cmmTopMapGraph,
14 cmmMapGraphM, cmmTopMapGraphM,
15 CmmInfo(..), UpdateFrame(..),
16 CmmInfoTable(..), ClosureTypeInfo(..), ProfilingInfo(..), ClosureTypeTag,
17 GenBasicBlock(..), CmmBasicBlock, blockId, blockStmts, mapBlockStmts,
19 CmmStmt(..), CmmActual, CmmActuals, CmmFormal, CmmFormals, CmmKind,
20 CmmFormalsWithoutKinds, CmmFormalWithoutKind,
24 CmmStatic(..), Section(..),
28 #include "HsVersions.h"
43 -- A [[BlockId]] is a local label.
44 -- Local labels must be unique within an entire compilation unit, not
45 -- just a single top-level item, because local labels map one-to-one
46 -- with assembly-language labels.
48 -----------------------------------------------------------------------------
49 -- Cmm, CmmTop, CmmBasicBlock
50 -----------------------------------------------------------------------------
52 -- A file is a list of top-level chunks. These may be arbitrarily
53 -- re-orderd during code generation.
55 -- GenCmm is abstracted over
56 -- d, the type of static data elements in CmmData
57 -- h, the static info preceding the code of a CmmProc
58 -- g, the control-flow graph of a CmmProc
60 -- We expect there to be two main instances of this type:
61 -- (a) C--, i.e. populated with various C-- constructs
62 -- (Cmm and RawCmm below)
63 -- (b) Native code, populated with data/instructions
65 -- A second family of instances based on ZipCfg is work in progress.
67 newtype GenCmm d h g = Cmm [GenCmmTop d h g]
69 -- | A top-level chunk, abstracted over the type of the contents of
70 -- the basic blocks (Cmm or instructions are the likely instantiations).
72 = CmmProc -- A procedure
73 h -- Extra header such as the info table
74 CLabel -- Used to generate both info & entry labels
75 CmmFormalsWithoutKinds -- Argument locals live on entry (C-- procedure params)
76 -- XXX Odd that there are no kinds, but there you are ---NR
77 g -- Control-flow graph for the procedure's code
79 | CmmData -- Static data
83 -- | A control-flow graph represented as a list of extended basic blocks.
84 newtype ListGraph i = ListGraph [GenBasicBlock i]
85 -- ^ Code, may be empty. The first block is the entry point. The
86 -- order is otherwise initially unimportant, but at some point the
87 -- code gen will fix the order.
89 -- BlockIds must be unique across an entire compilation unit, since
90 -- they are translated to assembly-language labels, which scope
91 -- across a whole compilation unit.
93 -- | Cmm with the info table as a data type
94 type Cmm = GenCmm CmmStatic CmmInfo (ListGraph CmmStmt)
95 type CmmTop = GenCmmTop CmmStatic CmmInfo (ListGraph CmmStmt)
97 -- | Cmm with the info tables converted to a list of 'CmmStatic'
98 type RawCmm = GenCmm CmmStatic [CmmStatic] (ListGraph CmmStmt)
99 type RawCmmTop = GenCmmTop CmmStatic [CmmStatic] (ListGraph CmmStmt)
102 -- A basic block containing a single label, at the beginning.
103 -- The list of basic blocks in a top-level code block may be re-ordered.
104 -- Fall-through is not allowed: there must be an explicit jump at the
105 -- end of each basic block, but the code generator might rearrange basic
106 -- blocks in order to turn some jumps into fallthroughs.
108 data GenBasicBlock i = BasicBlock BlockId [i]
109 type CmmBasicBlock = GenBasicBlock CmmStmt
111 instance UserOfLocalRegs i => UserOfLocalRegs (GenBasicBlock i) where
112 foldRegsUsed f set (BasicBlock _ l) = foldRegsUsed f set l
114 blockId :: GenBasicBlock i -> BlockId
115 -- The branch block id is that of the first block in
116 -- the branch, which is that branch's entry point
117 blockId (BasicBlock blk_id _ ) = blk_id
119 blockStmts :: GenBasicBlock i -> [i]
120 blockStmts (BasicBlock _ stmts) = stmts
123 mapBlockStmts :: (i -> i') -> GenBasicBlock i -> GenBasicBlock i'
124 mapBlockStmts f (BasicBlock id bs) = BasicBlock id (map f bs)
125 ----------------------------------------------------------------
127 ----------------------------------------------------------------
129 cmmMapGraph :: (g -> g') -> GenCmm d h g -> GenCmm d h g'
130 cmmTopMapGraph :: (g -> g') -> GenCmmTop d h g -> GenCmmTop d h g'
132 cmmMapGraphM :: Monad m => (String -> g -> m g') -> GenCmm d h g -> m (GenCmm d h g')
133 cmmTopMapGraphM :: Monad m => (String -> g -> m g') -> GenCmmTop d h g -> m (GenCmmTop d h g')
135 cmmMapGraph f (Cmm tops) = Cmm $ map (cmmTopMapGraph f) tops
136 cmmTopMapGraph f (CmmProc h l args g) = CmmProc h l args (f g)
137 cmmTopMapGraph _ (CmmData s ds) = CmmData s ds
139 cmmMapGraphM f (Cmm tops) = mapM (cmmTopMapGraphM f) tops >>= return . Cmm
140 cmmTopMapGraphM f (CmmProc h l args g) = f (showSDoc $ ppr l) g >>= return . CmmProc h l args
141 cmmTopMapGraphM _ (CmmData s ds) = return $ CmmData s ds
143 -----------------------------------------------------------------------------
145 -----------------------------------------------------------------------------
149 (Maybe BlockId) -- GC target. Nothing <=> CPS won't do stack check
150 (Maybe UpdateFrame) -- Update frame
151 CmmInfoTable -- Info table
153 -- Info table as a haskell data type
157 ClosureTypeTag -- Int
159 | CmmNonInfoTable -- Procedure doesn't need an info table
161 -- TODO: The GC target shouldn't really be part of CmmInfo
162 -- as it doesn't appear in the resulting info table.
163 -- It should be factored out.
166 = ConstrInfo ClosureLayout ConstrTag ConstrDescription
167 | FunInfo ClosureLayout C_SRT FunType FunArity ArgDescr SlowEntry
168 | ThunkInfo ClosureLayout C_SRT
169 | ThunkSelectorInfo SelectorOffset C_SRT
171 [Maybe LocalReg] -- Forced stack parameters
174 data CmmReturnInfo = CmmMayReturn
177 -- TODO: These types may need refinement
178 data ProfilingInfo = ProfilingInfo CmmLit CmmLit -- closure_type, closure_desc
179 type ClosureTypeTag = StgHalfWord
180 type ClosureLayout = (StgHalfWord, StgHalfWord) -- ptrs, nptrs
181 type ConstrTag = StgHalfWord
182 type ConstrDescription = CmmLit
183 type FunType = StgHalfWord
184 type FunArity = StgHalfWord
185 type SlowEntry = CmmLit
186 -- ^We would like this to be a CLabel but
187 -- for now the parser sets this to zero on an INFO_TABLE_FUN.
188 type SelectorOffset = StgWord
190 -- | A frame that is to be pushed before entry to the function.
191 -- Used to handle 'update' frames.
194 CmmExpr -- Frame header. Behaves like the target of a 'jump'.
195 [CmmExpr] -- Frame remainder. Behaves like the arguments of a 'jump'.
197 -----------------------------------------------------------------------------
199 -- A "statement". Note that all branches are explicit: there are no
200 -- control transfers to computed addresses, except when transfering
201 -- control to a new function.
202 -----------------------------------------------------------------------------
206 | CmmComment FastString
208 | CmmAssign CmmReg CmmExpr -- Assign to register
210 | CmmStore CmmExpr CmmExpr -- Assign to memory location. Size is
211 -- given by cmmExprRep of the rhs.
213 | CmmCall -- A call (forign, native or primitive), with
215 CmmFormals -- zero or more results
216 CmmActuals -- zero or more arguments
217 CmmSafety -- whether to build a continuation
220 | CmmBranch BlockId -- branch to another BB in this fn
222 | CmmCondBranch CmmExpr BlockId -- conditional branch
224 | CmmSwitch CmmExpr [Maybe BlockId] -- Table branch
225 -- The scrutinee is zero-based;
226 -- zero -> first block
227 -- one -> second block etc
228 -- Undefined outside range, and when there's a Nothing
230 | CmmJump CmmExpr -- Jump to another C-- function,
231 CmmActuals -- with these parameters.
233 | CmmReturn -- Return from a native C-- function,
234 CmmActuals -- with these return values.
236 type CmmKind = MachHint
237 data CmmKinded a = CmmKinded { kindlessCmm :: a, cmmKind :: CmmKind }
239 type CmmActual = CmmKinded CmmExpr
240 type CmmFormal = CmmKinded LocalReg
241 type CmmActuals = [CmmActual]
242 type CmmFormals = [CmmFormal]
243 type CmmFormalWithoutKind = LocalReg
244 type CmmFormalsWithoutKinds = [CmmFormalWithoutKind]
246 data CmmSafety = CmmUnsafe | CmmSafe C_SRT
248 -- | enable us to fold used registers over 'CmmActuals' and 'CmmFormals'
249 instance UserOfLocalRegs a => UserOfLocalRegs (CmmKinded a) where
250 foldRegsUsed f set (CmmKinded a _) = foldRegsUsed f set a
252 instance UserOfLocalRegs CmmStmt where
253 foldRegsUsed f set s = stmt s set
254 where stmt (CmmNop) = id
255 stmt (CmmComment {}) = id
256 stmt (CmmAssign _ e) = gen e
257 stmt (CmmStore e1 e2) = gen e1 . gen e2
258 stmt (CmmCall target _ es _ _) = gen target . gen es
259 stmt (CmmBranch _) = id
260 stmt (CmmCondBranch e _) = gen e
261 stmt (CmmSwitch e _) = gen e
262 stmt (CmmJump e es) = gen e . gen es
263 stmt (CmmReturn es) = gen es
264 gen a set = foldRegsUsed f set a
266 instance UserOfLocalRegs CmmCallTarget where
267 foldRegsUsed f set (CmmCallee e _) = foldRegsUsed f set e
268 foldRegsUsed _ set (CmmPrim {}) = set
270 instance DefinerOfLocalRegs a => DefinerOfLocalRegs (CmmKinded a) where
271 foldRegsDefd f z (CmmKinded x _) = foldRegsDefd f z x
273 --just look like a tuple, since it was a tuple before
274 -- ... is that a good idea? --Isaac Dupree
275 instance (Outputable a) => Outputable (CmmKinded a) where
276 ppr (CmmKinded a k) = ppr (a, k)
282 One possible problem with the above type is that the only way to do a
283 non-local conditional jump is to encode it as a branch to a block that
284 contains a single jump. This leads to inefficient code in the back end.
286 [N.B. This problem will go away when we make the transition to the
287 'zipper' form of control-flow graph, in which both targets of a
288 conditional jump are explicit. ---NR]
290 One possible way to fix this would be:
294 | CmmJump CmmBranchDest
295 | CmmCondJump CmmExpr CmmBranchDest
300 | NonLocal CmmExpr [LocalReg]
304 + one fewer constructors in CmmStmt
305 + allows both cond branch and switch to jump to non-local destinations
309 - not strictly necessary: can already encode as branch+jump
310 - not always possible to implement any better in the back end
311 - could do the optimisation in the back end (but then plat-specific?)
312 - C-- doesn't have it
313 - back-end optimisation might be more general (jump shortcutting)
315 So we'll stick with the way it is, and add the optimisation to the NCG.
318 -----------------------------------------------------------------------------
321 -- The target of a CmmCall.
322 -----------------------------------------------------------------------------
325 = CmmCallee -- Call a function (foreign or native)
326 CmmExpr -- literal label <=> static call
327 -- other expression <=> dynamic call
328 CCallConv -- The calling convention
330 | CmmPrim -- Call a "primitive" (eg. sin, cos)
331 CallishMachOp -- These might be implemented as inline
332 -- code by the backend.
335 -----------------------------------------------------------------------------
337 -----------------------------------------------------------------------------
343 | RelocatableReadOnlyData
345 | ReadOnlyData16 -- .rodata.cst16 on x86_64, 16-byte aligned
346 | OtherSection String
349 = CmmStaticLit CmmLit
350 -- a literal value, size given by cmmLitRep of the literal.
351 | CmmUninitialised Int
352 -- uninitialised data, N bytes long
354 -- align to next N-byte boundary (N must be a power of 2).
355 | CmmDataLabel CLabel
356 -- label the current position in this section.
358 -- string of 8-bit values only, not zero terminated.