1 {-# OPTIONS -fno-warn-name-shadowing -w #-}
2 -- We'd like to use -fno-warn-orphans rather than -w, but old compilers
3 -- don't understand it so building stage1 fails.
5 -----------------------------------------------------------------------------
9 -- (c) The University of Glasgow 2004-2006
11 -----------------------------------------------------------------------------
14 GenCmm(..), Cmm, RawCmm,
15 GenCmmTop(..), CmmTop, RawCmmTop,
17 cmmMapGraph, cmmTopMapGraph,
18 cmmMapGraphM, cmmTopMapGraphM,
19 CmmInfo(..), UpdateFrame(..),
20 CmmInfoTable(..), ClosureTypeInfo(..), ProfilingInfo(..), ClosureTypeTag,
21 GenBasicBlock(..), CmmBasicBlock, blockId, blockStmts, mapBlockStmts,
23 CmmStmt(..), CmmActuals, CmmFormal, CmmFormals, CmmHintFormals,
26 CmmStatic(..), Section(..),
27 CmmExpr(..), cmmExprRep, maybeInvertCmmExpr,
28 CmmReg(..), cmmRegRep,
29 CmmLit(..), cmmLitRep,
30 LocalReg(..), localRegRep, localRegGCFollow, Kind(..),
31 BlockId(..), freshBlockId,
32 BlockEnv, emptyBlockEnv, lookupBlockEnv, extendBlockEnv, mkBlockEnv,
33 BlockSet, emptyBlockSet, elemBlockSet, extendBlockSet,
34 GlobalReg(..), globalRegRep,
36 node, nodeReg, spReg, hpReg, spLimReg
39 -- ^ In order not to do violence to the import structure of the rest
40 -- of the compiler, module Cmm re-exports a number of identifiers
41 -- defined in 'CmmExpr'
43 #include "HsVersions.h"
56 import ZipCfg ( BlockId(..), freshBlockId
57 , BlockEnv, emptyBlockEnv, lookupBlockEnv, extendBlockEnv, mkBlockEnv
58 , BlockSet, emptyBlockSet, elemBlockSet, extendBlockSet
61 -- A [[BlockId]] is a local label.
62 -- Local labels must be unique within an entire compilation unit, not
63 -- just a single top-level item, because local labels map one-to-one
64 -- with assembly-language labels.
66 -----------------------------------------------------------------------------
67 -- Cmm, CmmTop, CmmBasicBlock
68 -----------------------------------------------------------------------------
70 -- A file is a list of top-level chunks. These may be arbitrarily
71 -- re-orderd during code generation.
73 -- GenCmm is abstracted over
74 -- d, the type of static data elements in CmmData
75 -- h, the static info preceding the code of a CmmProc
76 -- g, the control-flow graph of a CmmProc
78 -- We expect there to be two main instances of this type:
79 -- (a) C--, i.e. populated with various C-- constructs
80 -- (Cmm and RawCmm below)
81 -- (b) Native code, populated with data/instructions
83 -- A second family of instances based on ZipCfg is work in progress.
85 newtype GenCmm d h g = Cmm [GenCmmTop d h g]
87 -- | A top-level chunk, abstracted over the type of the contents of
88 -- the basic blocks (Cmm or instructions are the likely instantiations).
90 = CmmProc -- A procedure
91 h -- Extra header such as the info table
92 CLabel -- Used to generate both info & entry labels
93 CmmFormals -- Argument locals live on entry (C-- procedure params)
94 g -- Control-flow graph for the procedure's code
96 | CmmData -- Static data
100 -- | A control-flow graph represented as a list of extended basic blocks.
101 newtype ListGraph i = ListGraph [GenBasicBlock i]
102 -- ^ Code, may be empty. The first block is the entry point. The
103 -- order is otherwise initially unimportant, but at some point the
104 -- code gen will fix the order.
106 -- BlockIds must be unique across an entire compilation unit, since
107 -- they are translated to assembly-language labels, which scope
108 -- across a whole compilation unit.
110 -- | Cmm with the info table as a data type
111 type Cmm = GenCmm CmmStatic CmmInfo (ListGraph CmmStmt)
112 type CmmTop = GenCmmTop CmmStatic CmmInfo (ListGraph CmmStmt)
114 -- | Cmm with the info tables converted to a list of 'CmmStatic'
115 type RawCmm = GenCmm CmmStatic [CmmStatic] (ListGraph CmmStmt)
116 type RawCmmTop = GenCmmTop CmmStatic [CmmStatic] (ListGraph CmmStmt)
119 -- A basic block containing a single label, at the beginning.
120 -- The list of basic blocks in a top-level code block may be re-ordered.
121 -- Fall-through is not allowed: there must be an explicit jump at the
122 -- end of each basic block, but the code generator might rearrange basic
123 -- blocks in order to turn some jumps into fallthroughs.
125 data GenBasicBlock i = BasicBlock BlockId [i]
126 type CmmBasicBlock = GenBasicBlock CmmStmt
128 instance UserOfLocalRegs i => UserOfLocalRegs (GenBasicBlock i) where
129 foldRegsUsed f set (BasicBlock _ l) = foldRegsUsed f set l
131 blockId :: GenBasicBlock i -> BlockId
132 -- The branch block id is that of the first block in
133 -- the branch, which is that branch's entry point
134 blockId (BasicBlock blk_id _ ) = blk_id
136 blockStmts :: GenBasicBlock i -> [i]
137 blockStmts (BasicBlock _ stmts) = stmts
140 mapBlockStmts :: (i -> i') -> GenBasicBlock i -> GenBasicBlock i'
141 mapBlockStmts f (BasicBlock id bs) = BasicBlock id (map f bs)
142 ----------------------------------------------------------------
144 ----------------------------------------------------------------
146 cmmMapGraph :: (g -> g') -> GenCmm d h g -> GenCmm d h g'
147 cmmTopMapGraph :: (g -> g') -> GenCmmTop d h g -> GenCmmTop d h g'
149 cmmMapGraphM :: Monad m => (String -> g -> m g') -> GenCmm d h g -> m (GenCmm d h g')
150 cmmTopMapGraphM :: Monad m => (String -> g -> m g') -> GenCmmTop d h g -> m (GenCmmTop d h g')
152 cmmMapGraph f (Cmm tops) = Cmm $ map (cmmTopMapGraph f) tops
153 cmmTopMapGraph f (CmmProc h l args g) = CmmProc h l args (f g)
154 cmmTopMapGraph _ (CmmData s ds) = CmmData s ds
156 cmmMapGraphM f (Cmm tops) = mapM (cmmTopMapGraphM f) tops >>= return . Cmm
157 cmmTopMapGraphM f (CmmProc h l args g) = f (showSDoc $ ppr l) g >>= return . CmmProc h l args
158 cmmTopMapGraphM _ (CmmData s ds) = return $ CmmData s ds
160 -----------------------------------------------------------------------------
162 -----------------------------------------------------------------------------
166 (Maybe BlockId) -- GC target. Nothing <=> CPS won't do stack check
167 (Maybe UpdateFrame) -- Update frame
168 CmmInfoTable -- Info table
170 -- Info table as a haskell data type
174 ClosureTypeTag -- Int
176 | CmmNonInfoTable -- Procedure doesn't need an info table
178 -- TODO: The GC target shouldn't really be part of CmmInfo
179 -- as it doesn't appear in the resulting info table.
180 -- It should be factored out.
183 = ConstrInfo ClosureLayout ConstrTag ConstrDescription
184 | FunInfo ClosureLayout C_SRT FunType FunArity ArgDescr SlowEntry
185 | ThunkInfo ClosureLayout C_SRT
186 | ThunkSelectorInfo SelectorOffset C_SRT
188 [Maybe LocalReg] -- Forced stack parameters
191 data CmmReturnInfo = CmmMayReturn
194 -- TODO: These types may need refinement
195 data ProfilingInfo = ProfilingInfo CmmLit CmmLit -- closure_type, closure_desc
196 type ClosureTypeTag = StgHalfWord
197 type ClosureLayout = (StgHalfWord, StgHalfWord) -- ptrs, nptrs
198 type ConstrTag = StgHalfWord
199 type ConstrDescription = CmmLit
200 type FunType = StgHalfWord
201 type FunArity = StgHalfWord
202 type SlowEntry = CmmLit
203 -- ^We would like this to be a CLabel but
204 -- for now the parser sets this to zero on an INFO_TABLE_FUN.
205 type SelectorOffset = StgWord
207 -- | A frame that is to be pushed before entry to the function.
208 -- Used to handle 'update' frames.
211 CmmExpr -- Frame header. Behaves like the target of a 'jump'.
212 [CmmExpr] -- Frame remainder. Behaves like the arguments of a 'jump'.
214 -----------------------------------------------------------------------------
216 -- A "statement". Note that all branches are explicit: there are no
217 -- control transfers to computed addresses, except when transfering
218 -- control to a new function.
219 -----------------------------------------------------------------------------
223 | CmmComment FastString
225 | CmmAssign CmmReg CmmExpr -- Assign to register
227 | CmmStore CmmExpr CmmExpr -- Assign to memory location. Size is
228 -- given by cmmExprRep of the rhs.
230 | CmmCall -- A call (forign, native or primitive), with
232 CmmHintFormals -- zero or more results
233 CmmActuals -- zero or more arguments
234 CmmSafety -- whether to build a continuation
237 | CmmBranch BlockId -- branch to another BB in this fn
239 | CmmCondBranch CmmExpr BlockId -- conditional branch
241 | CmmSwitch CmmExpr [Maybe BlockId] -- Table branch
242 -- The scrutinee is zero-based;
243 -- zero -> first block
244 -- one -> second block etc
245 -- Undefined outside range, and when there's a Nothing
247 | CmmJump CmmExpr -- Jump to another C-- function,
248 CmmActuals -- with these parameters.
250 | CmmReturn -- Return from a native C-- function,
251 CmmActuals -- with these return values.
253 type CmmActual = CmmExpr
254 type CmmActuals = [(CmmActual,MachHint)]
255 type CmmFormal = LocalReg
256 type CmmHintFormals = [(CmmFormal,MachHint)]
257 type CmmFormals = [CmmFormal]
258 data CmmSafety = CmmUnsafe | CmmSafe C_SRT
260 -- | enable us to fold used registers over 'CmmActuals' and 'CmmHintFormals'
261 instance UserOfLocalRegs a => UserOfLocalRegs (a, MachHint) where
262 foldRegsUsed f set (a, _) = foldRegsUsed f set a
264 instance UserOfLocalRegs CmmStmt where
265 foldRegsUsed f set s = stmt s set
266 where stmt (CmmNop) = id
267 stmt (CmmComment {}) = id
268 stmt (CmmAssign _ e) = gen e
269 stmt (CmmStore e1 e2) = gen e1 . gen e2
270 stmt (CmmCall target _ es _ _) = gen target . gen es
271 stmt (CmmBranch _) = id
272 stmt (CmmCondBranch e _) = gen e
273 stmt (CmmSwitch e _) = gen e
274 stmt (CmmJump e es) = gen e . gen es
275 stmt (CmmReturn es) = gen es
276 gen a set = foldRegsUsed f set a
278 instance UserOfLocalRegs CmmCallTarget where
279 foldRegsUsed f set (CmmCallee e _) = foldRegsUsed f set e
280 foldRegsUsed _ set (CmmPrim {}) = set
286 One possible problem with the above type is that the only way to do a
287 non-local conditional jump is to encode it as a branch to a block that
288 contains a single jump. This leads to inefficient code in the back end.
290 [N.B. This problem will go away when we make the transition to the
291 'zipper' form of control-flow graph, in which both targets of a
292 conditional jump are explicit. ---NR]
294 One possible way to fix this would be:
298 | CmmJump CmmBranchDest
299 | CmmCondJump CmmExpr CmmBranchDest
304 | NonLocal CmmExpr [LocalReg]
308 + one fewer constructors in CmmStmt
309 + allows both cond branch and switch to jump to non-local destinations
313 - not strictly necessary: can already encode as branch+jump
314 - not always possible to implement any better in the back end
315 - could do the optimisation in the back end (but then plat-specific?)
316 - C-- doesn't have it
317 - back-end optimisation might be more general (jump shortcutting)
319 So we'll stick with the way it is, and add the optimisation to the NCG.
322 -----------------------------------------------------------------------------
325 -- The target of a CmmCall.
326 -----------------------------------------------------------------------------
329 = CmmCallee -- Call a function (foreign or native)
330 CmmExpr -- literal label <=> static call
331 -- other expression <=> dynamic call
332 CCallConv -- The calling convention
334 | CmmPrim -- Call a "primitive" (eg. sin, cos)
335 CallishMachOp -- These might be implemented as inline
336 -- code by the backend.
338 -----------------------------------------------------------------------------
340 -----------------------------------------------------------------------------
346 | RelocatableReadOnlyData
348 | ReadOnlyData16 -- .rodata.cst16 on x86_64, 16-byte aligned
349 | OtherSection String
352 = CmmStaticLit CmmLit
353 -- a literal value, size given by cmmLitRep of the literal.
354 | CmmUninitialised Int
355 -- uninitialised data, N bytes long
357 -- align to next N-byte boundary (N must be a power of 2).
358 | CmmDataLabel CLabel
359 -- label the current position in this section.
361 -- string of 8-bit values only, not zero terminated.