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(..), HasStaticClosure, ClosureTypeInfo(..), ConstrDescription,
17 ProfilingInfo(..), ClosureTypeTag,
18 GenBasicBlock(..), CmmBasicBlock, blockId, blockStmts, mapBlockStmts,
20 CmmStmt(..), CmmActual, CmmActuals, CmmFormal, CmmFormals,
21 HintedCmmFormal, HintedCmmFormals, HintedCmmActual, HintedCmmActuals,
23 CmmCallTarget(..), CallishMachOp(..), pprCallishMachOp,
24 ForeignHint(..), CmmHinted(..),
25 CmmStatic(..), Section(..),
29 #include "HsVersions.h"
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.
49 -----------------------------------------------------------------------------
50 -- Cmm, CmmTop, CmmBasicBlock
51 -----------------------------------------------------------------------------
53 -- A file is a list of top-level chunks. These may be arbitrarily
54 -- re-orderd during code generation.
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
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
66 -- A second family of instances based on ZipCfg is work in progress.
68 newtype GenCmm d h g = Cmm [GenCmmTop d h g]
70 -- | A top-level chunk, abstracted over the type of the contents of
71 -- the basic blocks (Cmm or instructions are the likely instantiations).
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
80 | CmmData -- Static data
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.
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.
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)
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)
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.
109 data GenBasicBlock i = BasicBlock BlockId [i]
110 type CmmBasicBlock = GenBasicBlock CmmStmt
112 instance UserOfLocalRegs i => UserOfLocalRegs (GenBasicBlock i) where
113 foldRegsUsed f set (BasicBlock _ l) = foldRegsUsed f set l
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
120 blockStmts :: GenBasicBlock i -> [i]
121 blockStmts (BasicBlock _ stmts) = stmts
124 mapBlockStmts :: (i -> i') -> GenBasicBlock i -> GenBasicBlock i'
125 mapBlockStmts f (BasicBlock id bs) = BasicBlock id (map f bs)
126 ----------------------------------------------------------------
128 ----------------------------------------------------------------
130 cmmMapGraph :: (g -> g') -> GenCmm d h g -> GenCmm d h g'
131 cmmTopMapGraph :: (g -> g') -> GenCmmTop d h g -> GenCmmTop d h g'
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')
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
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
145 -----------------------------------------------------------------------------
147 -----------------------------------------------------------------------------
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
156 -- Info table as a haskell data type
161 ClosureTypeTag -- Int
163 | CmmNonInfoTable -- Procedure doesn't need an info table
165 type HasStaticClosure = Bool
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.
172 = ConstrInfo ClosureLayout ConstrTag ConstrDescription
173 | FunInfo ClosureLayout C_SRT FunArity ArgDescr SlowEntry
174 | ThunkInfo ClosureLayout C_SRT
175 | ThunkSelectorInfo SelectorOffset C_SRT
177 [Maybe LocalReg] -- Stack layout: Just x, an item x
178 -- Nothing: a 1-word gap
179 -- Start of list is the *young* end
182 data CmmReturnInfo = CmmMayReturn
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
198 -- | A frame that is to be pushed before entry to the function.
199 -- Used to handle 'update' frames.
202 CmmExpr -- Frame header. Behaves like the target of a 'jump'.
203 [CmmExpr] -- Frame remainder. Behaves like the arguments of a 'jump'.
205 -----------------------------------------------------------------------------
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 -----------------------------------------------------------------------------
212 data CmmStmt -- Old-style
214 | CmmComment FastString
216 | CmmAssign CmmReg CmmExpr -- Assign to register
218 | CmmStore CmmExpr CmmExpr -- Assign to memory location. Size is
219 -- given by cmmExprType of the rhs.
221 | CmmCall -- A call (forign, native or primitive), with
223 HintedCmmFormals -- zero or more results
224 HintedCmmActuals -- zero or more arguments
225 CmmSafety -- whether to build a continuation
228 | CmmBranch BlockId -- branch to another BB in this fn
230 | CmmCondBranch CmmExpr BlockId -- conditional branch
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
238 | CmmJump CmmExpr -- Jump to another C-- function,
239 HintedCmmActuals -- with these parameters. (parameters never used)
241 | CmmReturn -- Return from a native C-- function,
242 HintedCmmActuals -- with these return values. (parameters never used)
244 type CmmActual = CmmExpr
245 type CmmFormal = LocalReg
246 type CmmActuals = [CmmActual]
247 type CmmFormals = [CmmFormal]
249 data CmmHinted a = CmmHinted { hintlessCmm :: a, cmmHint :: ForeignHint }
252 type HintedCmmActuals = [HintedCmmActual]
253 type HintedCmmFormals = [HintedCmmFormal]
254 type HintedCmmFormal = CmmHinted CmmFormal
255 type HintedCmmActual = CmmHinted CmmActual
257 data CmmSafety = CmmUnsafe | CmmSafe C_SRT
259 -- | enable us to fold used registers over 'CmmActuals' and 'CmmFormals'
260 instance UserOfLocalRegs CmmStmt where
261 foldRegsUsed f set s = stmt s set
262 where stmt (CmmNop) = id
263 stmt (CmmComment {}) = id
264 stmt (CmmAssign _ e) = gen e
265 stmt (CmmStore e1 e2) = gen e1 . gen e2
266 stmt (CmmCall target _ es _ _) = gen target . gen es
267 stmt (CmmBranch _) = id
268 stmt (CmmCondBranch e _) = gen e
269 stmt (CmmSwitch e _) = gen e
270 stmt (CmmJump e es) = gen e . gen es
271 stmt (CmmReturn es) = gen es
272 gen a set = foldRegsUsed f set a
274 instance UserOfLocalRegs CmmCallTarget where
275 foldRegsUsed f set (CmmCallee e _) = foldRegsUsed f set e
276 foldRegsUsed _ set (CmmPrim {}) = set
278 instance UserOfSlots CmmCallTarget where
279 foldSlotsUsed f set (CmmCallee e _) = foldSlotsUsed f set e
280 foldSlotsUsed _ set (CmmPrim {}) = set
282 instance UserOfLocalRegs a => UserOfLocalRegs (CmmHinted a) where
283 foldRegsUsed f set a = foldRegsUsed f set (hintlessCmm a)
285 instance UserOfSlots a => UserOfSlots (CmmHinted a) where
286 foldSlotsUsed f set a = foldSlotsUsed f set (hintlessCmm a)
288 instance DefinerOfLocalRegs a => DefinerOfLocalRegs (CmmHinted a) where
289 foldRegsDefd f set a = foldRegsDefd f set (hintlessCmm a)
295 One possible problem with the above type is that the only way to do a
296 non-local conditional jump is to encode it as a branch to a block that
297 contains a single jump. This leads to inefficient code in the back end.
299 [N.B. This problem will go away when we make the transition to the
300 'zipper' form of control-flow graph, in which both targets of a
301 conditional jump are explicit. ---NR]
303 One possible way to fix this would be:
307 | CmmJump CmmBranchDest
308 | CmmCondJump CmmExpr CmmBranchDest
313 | NonLocal CmmExpr [LocalReg]
317 + one fewer constructors in CmmStmt
318 + allows both cond branch and switch to jump to non-local destinations
322 - not strictly necessary: can already encode as branch+jump
323 - not always possible to implement any better in the back end
324 - could do the optimisation in the back end (but then plat-specific?)
325 - C-- doesn't have it
326 - back-end optimisation might be more general (jump shortcutting)
328 So we'll stick with the way it is, and add the optimisation to the NCG.
331 -----------------------------------------------------------------------------
334 -- The target of a CmmCall.
335 -----------------------------------------------------------------------------
338 = CmmCallee -- Call a function (foreign or native)
339 CmmExpr -- literal label <=> static call
340 -- other expression <=> dynamic call
341 CCallConv -- The calling convention
343 | CmmPrim -- Call a "primitive" (eg. sin, cos)
344 CallishMachOp -- These might be implemented as inline
345 -- code by the backend.
350 = NoHint | AddrHint | SignedHint
352 -- Used to give extra per-argument or per-result
353 -- information needed by foreign calling conventions
356 -- CallishMachOps tend to be implemented by foreign calls in some backends,
357 -- so we separate them out. In Cmm, these can only occur in a
358 -- statement position, in contrast to an ordinary MachOp which can occur
359 -- anywhere in an expression.
388 | MO_Touch -- Keep variables live (when using interior pointers)
391 pprCallishMachOp :: CallishMachOp -> SDoc
392 pprCallishMachOp mo = text (show mo)
394 -----------------------------------------------------------------------------
396 -----------------------------------------------------------------------------
402 | RelocatableReadOnlyData
404 | ReadOnlyData16 -- .rodata.cst16 on x86_64, 16-byte aligned
405 | OtherSection String
408 = CmmStaticLit CmmLit
409 -- a literal value, size given by cmmLitRep of the literal.
410 | CmmUninitialised Int
411 -- uninitialised data, N bytes long
413 -- align to next N-byte boundary (N must be a power of 2).
414 | CmmDataLabel CLabel
415 -- label the current position in this section.
417 -- string of 8-bit values only, not zero terminated.