1 {-# OPTIONS -Wall -fno-warn-name-shadowing -fno-warn-orphans #-}
2 -----------------------------------------------------------------------------
6 -- (c) The University of Glasgow 2004-2006
8 -----------------------------------------------------------------------------
11 -- The above warning supression flag is a temporary kludge.
12 -- While working on this module you are encouraged to remove it and fix
13 -- any warnings in the module. See
14 -- http://hackage.haskell.org/trac/ghc/wiki/CodingStyle#Warnings
18 GenCmm(..), Cmm, RawCmm,
19 GenCmmTop(..), CmmTop, RawCmmTop,
21 cmmMapGraph, cmmTopMapGraph,
22 cmmMapGraphM, cmmTopMapGraphM,
23 CmmInfo(..), UpdateFrame(..),
24 CmmInfoTable(..), ClosureTypeInfo(..), ProfilingInfo(..), ClosureTypeTag,
25 GenBasicBlock(..), CmmBasicBlock, blockId, blockStmts, mapBlockStmts,
27 CmmStmt(..), CmmActuals, CmmFormal, CmmFormals, CmmHintFormals,
30 CmmStatic(..), Section(..),
31 CmmExpr(..), cmmExprRep, maybeInvertCmmExpr,
32 CmmReg(..), cmmRegRep,
33 CmmLit(..), cmmLitRep,
34 LocalReg(..), localRegRep, localRegGCFollow, Kind(..),
35 BlockId(..), freshBlockId,
36 BlockEnv, emptyBlockEnv, lookupBlockEnv, extendBlockEnv, mkBlockEnv,
37 BlockSet, emptyBlockSet, elemBlockSet, extendBlockSet,
38 GlobalReg(..), globalRegRep,
40 node, nodeReg, spReg, hpReg, spLimReg
43 -- ^ In order not to do violence to the import structure of the rest
44 -- of the compiler, module Cmm re-exports a number of identifiers
45 -- defined in 'CmmExpr'
47 #include "HsVersions.h"
60 import ZipCfg ( BlockId(..), freshBlockId
61 , BlockEnv, emptyBlockEnv, lookupBlockEnv, extendBlockEnv, mkBlockEnv
62 , BlockSet, emptyBlockSet, elemBlockSet, extendBlockSet
65 -- A [[BlockId]] is a local label.
66 -- Local labels must be unique within an entire compilation unit, not
67 -- just a single top-level item, because local labels map one-to-one
68 -- with assembly-language labels.
70 -----------------------------------------------------------------------------
71 -- Cmm, CmmTop, CmmBasicBlock
72 -----------------------------------------------------------------------------
74 -- A file is a list of top-level chunks. These may be arbitrarily
75 -- re-orderd during code generation.
77 -- GenCmm is abstracted over
78 -- d, the type of static data elements in CmmData
79 -- h, the static info preceding the code of a CmmProc
80 -- g, the control-flow graph of a CmmProc
82 -- We expect there to be two main instances of this type:
83 -- (a) C--, i.e. populated with various C-- constructs
84 -- (Cmm and RawCmm below)
85 -- (b) Native code, populated with data/instructions
87 -- A second family of instances based on ZipCfg is work in progress.
89 newtype GenCmm d h g = Cmm [GenCmmTop d h g]
91 -- | A top-level chunk, abstracted over the type of the contents of
92 -- the basic blocks (Cmm or instructions are the likely instantiations).
94 = CmmProc -- A procedure
95 h -- Extra header such as the info table
96 CLabel -- Used to generate both info & entry labels
97 CmmFormals -- Argument locals live on entry (C-- procedure params)
98 g -- Control-flow graph for the procedure's code
100 | CmmData -- Static data
104 -- | A control-flow graph represented as a list of extended basic blocks.
105 newtype ListGraph i = ListGraph [GenBasicBlock i]
106 -- ^ Code, may be empty. The first block is the entry point. The
107 -- order is otherwise initially unimportant, but at some point the
108 -- code gen will fix the order.
110 -- BlockIds must be unique across an entire compilation unit, since
111 -- they are translated to assembly-language labels, which scope
112 -- across a whole compilation unit.
114 -- | Cmm with the info table as a data type
115 type Cmm = GenCmm CmmStatic CmmInfo (ListGraph CmmStmt)
116 type CmmTop = GenCmmTop CmmStatic CmmInfo (ListGraph CmmStmt)
118 -- | Cmm with the info tables converted to a list of 'CmmStatic'
119 type RawCmm = GenCmm CmmStatic [CmmStatic] (ListGraph CmmStmt)
120 type RawCmmTop = GenCmmTop CmmStatic [CmmStatic] (ListGraph CmmStmt)
123 -- A basic block containing a single label, at the beginning.
124 -- The list of basic blocks in a top-level code block may be re-ordered.
125 -- Fall-through is not allowed: there must be an explicit jump at the
126 -- end of each basic block, but the code generator might rearrange basic
127 -- blocks in order to turn some jumps into fallthroughs.
129 data GenBasicBlock i = BasicBlock BlockId [i]
130 type CmmBasicBlock = GenBasicBlock CmmStmt
132 instance UserOfLocalRegs i => UserOfLocalRegs (GenBasicBlock i) where
133 foldRegsUsed f set (BasicBlock _ l) = foldRegsUsed f set l
135 blockId :: GenBasicBlock i -> BlockId
136 -- The branch block id is that of the first block in
137 -- the branch, which is that branch's entry point
138 blockId (BasicBlock blk_id _ ) = blk_id
140 blockStmts :: GenBasicBlock i -> [i]
141 blockStmts (BasicBlock _ stmts) = stmts
144 mapBlockStmts :: (i -> i') -> GenBasicBlock i -> GenBasicBlock i'
145 mapBlockStmts f (BasicBlock id bs) = BasicBlock id (map f bs)
146 ----------------------------------------------------------------
148 ----------------------------------------------------------------
150 cmmMapGraph :: (g -> g') -> GenCmm d h g -> GenCmm d h g'
151 cmmTopMapGraph :: (g -> g') -> GenCmmTop d h g -> GenCmmTop d h g'
153 cmmMapGraphM :: Monad m => (String -> g -> m g') -> GenCmm d h g -> m (GenCmm d h g')
154 cmmTopMapGraphM :: Monad m => (String -> g -> m g') -> GenCmmTop d h g -> m (GenCmmTop d h g')
156 cmmMapGraph f (Cmm tops) = Cmm $ map (cmmTopMapGraph f) tops
157 cmmTopMapGraph f (CmmProc h l args g) = CmmProc h l args (f g)
158 cmmTopMapGraph _ (CmmData s ds) = CmmData s ds
160 cmmMapGraphM f (Cmm tops) = mapM (cmmTopMapGraphM f) tops >>= return . Cmm
161 cmmTopMapGraphM f (CmmProc h l args g) = f (showSDoc $ ppr l) g >>= return . CmmProc h l args
162 cmmTopMapGraphM _ (CmmData s ds) = return $ CmmData s ds
164 -----------------------------------------------------------------------------
166 -----------------------------------------------------------------------------
170 (Maybe BlockId) -- GC target. Nothing <=> CPS won't do stack check
171 (Maybe UpdateFrame) -- Update frame
172 CmmInfoTable -- Info table
174 -- Info table as a haskell data type
178 ClosureTypeTag -- Int
180 | CmmNonInfoTable -- Procedure doesn't need an info table
182 -- TODO: The GC target shouldn't really be part of CmmInfo
183 -- as it doesn't appear in the resulting info table.
184 -- It should be factored out.
187 = ConstrInfo ClosureLayout ConstrTag ConstrDescription
188 | FunInfo ClosureLayout C_SRT FunType FunArity ArgDescr SlowEntry
189 | ThunkInfo ClosureLayout C_SRT
190 | ThunkSelectorInfo SelectorOffset C_SRT
192 [Maybe LocalReg] -- Forced stack parameters
195 data CmmReturnInfo = CmmMayReturn
198 -- TODO: These types may need refinement
199 data ProfilingInfo = ProfilingInfo CmmLit CmmLit -- closure_type, closure_desc
200 type ClosureTypeTag = StgHalfWord
201 type ClosureLayout = (StgHalfWord, StgHalfWord) -- ptrs, nptrs
202 type ConstrTag = StgHalfWord
203 type ConstrDescription = CmmLit
204 type FunType = StgHalfWord
205 type FunArity = StgHalfWord
206 type SlowEntry = CmmLit
207 -- ^We would like this to be a CLabel but
208 -- for now the parser sets this to zero on an INFO_TABLE_FUN.
209 type SelectorOffset = StgWord
211 -- | A frame that is to be pushed before entry to the function.
212 -- Used to handle 'update' frames.
215 CmmExpr -- Frame header. Behaves like the target of a 'jump'.
216 [CmmExpr] -- Frame remainder. Behaves like the arguments of a 'jump'.
218 -----------------------------------------------------------------------------
220 -- A "statement". Note that all branches are explicit: there are no
221 -- control transfers to computed addresses, except when transfering
222 -- control to a new function.
223 -----------------------------------------------------------------------------
227 | CmmComment FastString
229 | CmmAssign CmmReg CmmExpr -- Assign to register
231 | CmmStore CmmExpr CmmExpr -- Assign to memory location. Size is
232 -- given by cmmExprRep of the rhs.
234 | CmmCall -- A call (forign, native or primitive), with
236 CmmHintFormals -- zero or more results
237 CmmActuals -- zero or more arguments
238 CmmSafety -- whether to build a continuation
241 | CmmBranch BlockId -- branch to another BB in this fn
243 | CmmCondBranch CmmExpr BlockId -- conditional branch
245 | CmmSwitch CmmExpr [Maybe BlockId] -- Table branch
246 -- The scrutinee is zero-based;
247 -- zero -> first block
248 -- one -> second block etc
249 -- Undefined outside range, and when there's a Nothing
251 | CmmJump CmmExpr -- Jump to another C-- function,
252 CmmActuals -- with these parameters.
254 | CmmReturn -- Return from a native C-- function,
255 CmmActuals -- with these return values.
257 type CmmActual = CmmExpr
258 type CmmActuals = [(CmmActual,MachHint)]
259 type CmmFormal = LocalReg
260 type CmmHintFormals = [(CmmFormal,MachHint)]
261 type CmmFormals = [CmmFormal]
262 data CmmSafety = CmmUnsafe | CmmSafe C_SRT
264 -- | enable us to fold used registers over 'CmmActuals' and 'CmmHintFormals'
265 instance UserOfLocalRegs a => UserOfLocalRegs (a, MachHint) where
266 foldRegsUsed f set (a, _) = foldRegsUsed f set a
268 instance UserOfLocalRegs CmmStmt where
269 foldRegsUsed f set s = stmt s set
270 where stmt (CmmNop) = id
271 stmt (CmmComment {}) = id
272 stmt (CmmAssign _ e) = gen e
273 stmt (CmmStore e1 e2) = gen e1 . gen e2
274 stmt (CmmCall target _ es _ _) = gen target . gen es
275 stmt (CmmBranch _) = id
276 stmt (CmmCondBranch e _) = gen e
277 stmt (CmmSwitch e _) = gen e
278 stmt (CmmJump e es) = gen e . gen es
279 stmt (CmmReturn es) = gen es
280 gen a set = foldRegsUsed f set a
282 instance UserOfLocalRegs CmmCallTarget where
283 foldRegsUsed f set (CmmCallee e _) = foldRegsUsed f set e
284 foldRegsUsed _ set (CmmPrim {}) = set
290 One possible problem with the above type is that the only way to do a
291 non-local conditional jump is to encode it as a branch to a block that
292 contains a single jump. This leads to inefficient code in the back end.
294 [N.B. This problem will go away when we make the transition to the
295 'zipper' form of control-flow graph, in which both targets of a
296 conditional jump are explicit. ---NR]
298 One possible way to fix this would be:
302 | CmmJump CmmBranchDest
303 | CmmCondJump CmmExpr CmmBranchDest
308 | NonLocal CmmExpr [LocalReg]
312 + one fewer constructors in CmmStmt
313 + allows both cond branch and switch to jump to non-local destinations
317 - not strictly necessary: can already encode as branch+jump
318 - not always possible to implement any better in the back end
319 - could do the optimisation in the back end (but then plat-specific?)
320 - C-- doesn't have it
321 - back-end optimisation might be more general (jump shortcutting)
323 So we'll stick with the way it is, and add the optimisation to the NCG.
326 -----------------------------------------------------------------------------
329 -- The target of a CmmCall.
330 -----------------------------------------------------------------------------
333 = CmmCallee -- Call a function (foreign or native)
334 CmmExpr -- literal label <=> static call
335 -- other expression <=> dynamic call
336 CCallConv -- The calling convention
338 | CmmPrim -- Call a "primitive" (eg. sin, cos)
339 CallishMachOp -- These might be implemented as inline
340 -- code by the backend.
342 -----------------------------------------------------------------------------
344 -----------------------------------------------------------------------------
350 | RelocatableReadOnlyData
352 | ReadOnlyData16 -- .rodata.cst16 on x86_64, 16-byte aligned
353 | OtherSection String
356 = CmmStaticLit CmmLit
357 -- a literal value, size given by cmmLitRep of the literal.
358 | CmmUninitialised Int
359 -- uninitialised data, N bytes long
361 -- align to next N-byte boundary (N must be a power of 2).
362 | CmmDataLabel CLabel
363 -- label the current position in this section.
365 -- string of 8-bit values only, not zero terminated.