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(..), CmmActual, CmmActuals, CmmFormal, CmmFormals, CmmKind,
24 CmmFormalsWithoutKinds, CmmFormalWithoutKind,
27 CmmStatic(..), Section(..),
29 BlockId(..), freshBlockId,
30 BlockEnv, emptyBlockEnv, lookupBlockEnv, extendBlockEnv, mkBlockEnv,
31 BlockSet, emptyBlockSet, elemBlockSet, extendBlockSet,
34 #include "HsVersions.h"
47 import ZipCfg ( BlockId(..), freshBlockId
48 , BlockEnv, emptyBlockEnv, lookupBlockEnv, extendBlockEnv, mkBlockEnv
49 , BlockSet, emptyBlockSet, elemBlockSet, extendBlockSet
52 -- A [[BlockId]] is a local label.
53 -- Local labels must be unique within an entire compilation unit, not
54 -- just a single top-level item, because local labels map one-to-one
55 -- with assembly-language labels.
57 -----------------------------------------------------------------------------
58 -- Cmm, CmmTop, CmmBasicBlock
59 -----------------------------------------------------------------------------
61 -- A file is a list of top-level chunks. These may be arbitrarily
62 -- re-orderd during code generation.
64 -- GenCmm is abstracted over
65 -- d, the type of static data elements in CmmData
66 -- h, the static info preceding the code of a CmmProc
67 -- g, the control-flow graph of a CmmProc
69 -- We expect there to be two main instances of this type:
70 -- (a) C--, i.e. populated with various C-- constructs
71 -- (Cmm and RawCmm below)
72 -- (b) Native code, populated with data/instructions
74 -- A second family of instances based on ZipCfg is work in progress.
76 newtype GenCmm d h g = Cmm [GenCmmTop d h g]
78 -- | A top-level chunk, abstracted over the type of the contents of
79 -- the basic blocks (Cmm or instructions are the likely instantiations).
81 = CmmProc -- A procedure
82 h -- Extra header such as the info table
83 CLabel -- Used to generate both info & entry labels
84 CmmFormalsWithoutKinds -- Argument locals live on entry (C-- procedure params)
85 -- XXX Odd that there are no kinds, but there you are ---NR
86 g -- Control-flow graph for the procedure's code
88 | CmmData -- Static data
92 -- | A control-flow graph represented as a list of extended basic blocks.
93 newtype ListGraph i = ListGraph [GenBasicBlock i]
94 -- ^ Code, may be empty. The first block is the entry point. The
95 -- order is otherwise initially unimportant, but at some point the
96 -- code gen will fix the order.
98 -- BlockIds must be unique across an entire compilation unit, since
99 -- they are translated to assembly-language labels, which scope
100 -- across a whole compilation unit.
102 -- | Cmm with the info table as a data type
103 type Cmm = GenCmm CmmStatic CmmInfo (ListGraph CmmStmt)
104 type CmmTop = GenCmmTop CmmStatic CmmInfo (ListGraph CmmStmt)
106 -- | Cmm with the info tables converted to a list of 'CmmStatic'
107 type RawCmm = GenCmm CmmStatic [CmmStatic] (ListGraph CmmStmt)
108 type RawCmmTop = GenCmmTop CmmStatic [CmmStatic] (ListGraph CmmStmt)
111 -- A basic block containing a single label, at the beginning.
112 -- The list of basic blocks in a top-level code block may be re-ordered.
113 -- Fall-through is not allowed: there must be an explicit jump at the
114 -- end of each basic block, but the code generator might rearrange basic
115 -- blocks in order to turn some jumps into fallthroughs.
117 data GenBasicBlock i = BasicBlock BlockId [i]
118 type CmmBasicBlock = GenBasicBlock CmmStmt
120 instance UserOfLocalRegs i => UserOfLocalRegs (GenBasicBlock i) where
121 foldRegsUsed f set (BasicBlock _ l) = foldRegsUsed f set l
123 blockId :: GenBasicBlock i -> BlockId
124 -- The branch block id is that of the first block in
125 -- the branch, which is that branch's entry point
126 blockId (BasicBlock blk_id _ ) = blk_id
128 blockStmts :: GenBasicBlock i -> [i]
129 blockStmts (BasicBlock _ stmts) = stmts
132 mapBlockStmts :: (i -> i') -> GenBasicBlock i -> GenBasicBlock i'
133 mapBlockStmts f (BasicBlock id bs) = BasicBlock id (map f bs)
134 ----------------------------------------------------------------
136 ----------------------------------------------------------------
138 cmmMapGraph :: (g -> g') -> GenCmm d h g -> GenCmm d h g'
139 cmmTopMapGraph :: (g -> g') -> GenCmmTop d h g -> GenCmmTop d h g'
141 cmmMapGraphM :: Monad m => (String -> g -> m g') -> GenCmm d h g -> m (GenCmm d h g')
142 cmmTopMapGraphM :: Monad m => (String -> g -> m g') -> GenCmmTop d h g -> m (GenCmmTop d h g')
144 cmmMapGraph f (Cmm tops) = Cmm $ map (cmmTopMapGraph f) tops
145 cmmTopMapGraph f (CmmProc h l args g) = CmmProc h l args (f g)
146 cmmTopMapGraph _ (CmmData s ds) = CmmData s ds
148 cmmMapGraphM f (Cmm tops) = mapM (cmmTopMapGraphM f) tops >>= return . Cmm
149 cmmTopMapGraphM f (CmmProc h l args g) = f (showSDoc $ ppr l) g >>= return . CmmProc h l args
150 cmmTopMapGraphM _ (CmmData s ds) = return $ CmmData s ds
152 -----------------------------------------------------------------------------
154 -----------------------------------------------------------------------------
158 (Maybe BlockId) -- GC target. Nothing <=> CPS won't do stack check
159 (Maybe UpdateFrame) -- Update frame
160 CmmInfoTable -- Info table
162 -- Info table as a haskell data type
166 ClosureTypeTag -- Int
168 | CmmNonInfoTable -- Procedure doesn't need an info table
170 -- TODO: The GC target shouldn't really be part of CmmInfo
171 -- as it doesn't appear in the resulting info table.
172 -- It should be factored out.
175 = ConstrInfo ClosureLayout ConstrTag ConstrDescription
176 | FunInfo ClosureLayout C_SRT FunType FunArity ArgDescr SlowEntry
177 | ThunkInfo ClosureLayout C_SRT
178 | ThunkSelectorInfo SelectorOffset C_SRT
180 [Maybe LocalReg] -- Forced stack parameters
183 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 FunType = StgHalfWord
193 type FunArity = StgHalfWord
194 type SlowEntry = CmmLit
195 -- ^We would like this to be a CLabel but
196 -- for now the parser sets this to zero on an INFO_TABLE_FUN.
197 type SelectorOffset = StgWord
199 -- | A frame that is to be pushed before entry to the function.
200 -- Used to handle 'update' frames.
203 CmmExpr -- Frame header. Behaves like the target of a 'jump'.
204 [CmmExpr] -- Frame remainder. Behaves like the arguments of a 'jump'.
206 -----------------------------------------------------------------------------
208 -- A "statement". Note that all branches are explicit: there are no
209 -- control transfers to computed addresses, except when transfering
210 -- control to a new function.
211 -----------------------------------------------------------------------------
215 | CmmComment FastString
217 | CmmAssign CmmReg CmmExpr -- Assign to register
219 | CmmStore CmmExpr CmmExpr -- Assign to memory location. Size is
220 -- given by cmmExprRep of the rhs.
222 | CmmCall -- A call (forign, native or primitive), with
224 CmmFormals -- zero or more results
225 CmmActuals -- zero or more arguments
226 CmmSafety -- whether to build a continuation
229 | CmmBranch BlockId -- branch to another BB in this fn
231 | CmmCondBranch CmmExpr BlockId -- conditional branch
233 | CmmSwitch CmmExpr [Maybe BlockId] -- Table branch
234 -- The scrutinee is zero-based;
235 -- zero -> first block
236 -- one -> second block etc
237 -- Undefined outside range, and when there's a Nothing
239 | CmmJump CmmExpr -- Jump to another C-- function,
240 CmmActuals -- with these parameters.
242 | CmmReturn -- Return from a native C-- function,
243 CmmActuals -- with these return values.
245 type CmmKind = MachHint
246 type CmmActual = (CmmExpr, CmmKind)
247 type CmmFormal = (LocalReg,CmmKind)
248 type CmmActuals = [CmmActual]
249 type CmmFormals = [CmmFormal]
250 type CmmFormalWithoutKind = LocalReg
251 type CmmFormalsWithoutKinds = [CmmFormalWithoutKind]
253 data CmmSafety = CmmUnsafe | CmmSafe C_SRT
255 -- | enable us to fold used registers over 'CmmActuals' and 'CmmFormals'
256 instance UserOfLocalRegs a => UserOfLocalRegs (a, CmmKind) where
257 foldRegsUsed f set (a, _) = foldRegsUsed f set a
259 instance UserOfLocalRegs CmmStmt where
260 foldRegsUsed f set s = stmt s set
261 where stmt (CmmNop) = id
262 stmt (CmmComment {}) = id
263 stmt (CmmAssign _ e) = gen e
264 stmt (CmmStore e1 e2) = gen e1 . gen e2
265 stmt (CmmCall target _ es _ _) = gen target . gen es
266 stmt (CmmBranch _) = id
267 stmt (CmmCondBranch e _) = gen e
268 stmt (CmmSwitch e _) = gen e
269 stmt (CmmJump e es) = gen e . gen es
270 stmt (CmmReturn es) = gen es
271 gen a set = foldRegsUsed f set a
273 instance UserOfLocalRegs CmmCallTarget where
274 foldRegsUsed f set (CmmCallee e _) = foldRegsUsed f set e
275 foldRegsUsed _ set (CmmPrim {}) = set
281 One possible problem with the above type is that the only way to do a
282 non-local conditional jump is to encode it as a branch to a block that
283 contains a single jump. This leads to inefficient code in the back end.
285 [N.B. This problem will go away when we make the transition to the
286 'zipper' form of control-flow graph, in which both targets of a
287 conditional jump are explicit. ---NR]
289 One possible way to fix this would be:
293 | CmmJump CmmBranchDest
294 | CmmCondJump CmmExpr CmmBranchDest
299 | NonLocal CmmExpr [LocalReg]
303 + one fewer constructors in CmmStmt
304 + allows both cond branch and switch to jump to non-local destinations
308 - not strictly necessary: can already encode as branch+jump
309 - not always possible to implement any better in the back end
310 - could do the optimisation in the back end (but then plat-specific?)
311 - C-- doesn't have it
312 - back-end optimisation might be more general (jump shortcutting)
314 So we'll stick with the way it is, and add the optimisation to the NCG.
317 -----------------------------------------------------------------------------
320 -- The target of a CmmCall.
321 -----------------------------------------------------------------------------
324 = CmmCallee -- Call a function (foreign or native)
325 CmmExpr -- literal label <=> static call
326 -- other expression <=> dynamic call
327 CCallConv -- The calling convention
329 | CmmPrim -- Call a "primitive" (eg. sin, cos)
330 CallishMachOp -- These might be implemented as inline
331 -- code by the backend.
333 -----------------------------------------------------------------------------
335 -----------------------------------------------------------------------------
341 | RelocatableReadOnlyData
343 | ReadOnlyData16 -- .rodata.cst16 on x86_64, 16-byte aligned
344 | OtherSection String
347 = CmmStaticLit CmmLit
348 -- a literal value, size given by cmmLitRep of the literal.
349 | CmmUninitialised Int
350 -- uninitialised data, N bytes long
352 -- align to next N-byte boundary (N must be a power of 2).
353 | CmmDataLabel CLabel
354 -- label the current position in this section.
356 -- string of 8-bit values only, not zero terminated.