1 -----------------------------------------------------------------------------
3 -- Old-style Cmm data types
5 -- (c) The University of Glasgow 2004-2006
7 -----------------------------------------------------------------------------
10 Cmm, RawCmm, CmmTop, RawCmmTop,
12 CmmInfo(..), UpdateFrame(..),
13 cmmMapGraph, cmmTopMapGraph,
14 cmmMapGraphM, cmmTopMapGraphM,
15 GenBasicBlock(..), CmmBasicBlock, blockId, blockStmts, mapBlockStmts,
16 CmmStmt(..), CmmReturnInfo(..), CmmHinted(..),
17 HintedCmmFormal, HintedCmmFormals, HintedCmmActual, HintedCmmActuals,
18 CmmSafety(..), CmmCallTarget(..),
23 #include "HsVersions.h"
35 -- A [[BlockId]] is a local label.
36 -- Local labels must be unique within an entire compilation unit, not
37 -- just a single top-level item, because local labels map one-to-one
38 -- with assembly-language labels.
40 -----------------------------------------------------------------------------
42 -----------------------------------------------------------------------------
46 (Maybe BlockId) -- GC target. Nothing <=> CPS won't do stack check
47 -- JD: NOT USED BY NEW CODE GEN
48 (Maybe UpdateFrame) -- Update frame
49 CmmInfoTable -- Info table
51 -- | A frame that is to be pushed before entry to the function.
52 -- Used to handle 'update' frames.
55 CmmExpr -- Frame header. Behaves like the target of a 'jump'.
56 [CmmExpr] -- Frame remainder. Behaves like the arguments of a 'jump'.
58 -----------------------------------------------------------------------------
59 -- Cmm, CmmTop, CmmBasicBlock
60 -----------------------------------------------------------------------------
62 -- A file is a list of top-level chunks. These may be arbitrarily
63 -- re-orderd during code generation.
65 -- | A control-flow graph represented as a list of extended basic blocks.
66 newtype ListGraph i = ListGraph [GenBasicBlock i]
67 -- ^ Code, may be empty. The first block is the entry point. The
68 -- order is otherwise initially unimportant, but at some point the
69 -- code gen will fix the order.
71 -- BlockIds must be unique across an entire compilation unit, since
72 -- they are translated to assembly-language labels, which scope
73 -- across a whole compilation unit.
75 -- | Cmm with the info table as a data type
76 type Cmm = GenCmm CmmStatic CmmInfo (ListGraph CmmStmt)
77 type CmmTop = GenCmmTop CmmStatic CmmInfo (ListGraph CmmStmt)
79 -- | Cmm with the info tables converted to a list of 'CmmStatic'
80 type RawCmm = GenCmm CmmStatic [CmmStatic] (ListGraph CmmStmt)
81 type RawCmmTop = GenCmmTop CmmStatic [CmmStatic] (ListGraph CmmStmt)
84 -- A basic block containing a single label, at the beginning.
85 -- The list of basic blocks in a top-level code block may be re-ordered.
86 -- Fall-through is not allowed: there must be an explicit jump at the
87 -- end of each basic block, but the code generator might rearrange basic
88 -- blocks in order to turn some jumps into fallthroughs.
90 data GenBasicBlock i = BasicBlock BlockId [i]
91 type CmmBasicBlock = GenBasicBlock CmmStmt
93 instance UserOfLocalRegs i => UserOfLocalRegs (GenBasicBlock i) where
94 foldRegsUsed f set (BasicBlock _ l) = foldRegsUsed f set l
96 blockId :: GenBasicBlock i -> BlockId
97 -- The branch block id is that of the first block in
98 -- the branch, which is that branch's entry point
99 blockId (BasicBlock blk_id _ ) = blk_id
101 blockStmts :: GenBasicBlock i -> [i]
102 blockStmts (BasicBlock _ stmts) = stmts
105 mapBlockStmts :: (i -> i') -> GenBasicBlock i -> GenBasicBlock i'
106 mapBlockStmts f (BasicBlock id bs) = BasicBlock id (map f bs)
107 ----------------------------------------------------------------
109 ----------------------------------------------------------------
111 cmmMapGraph :: (g -> g') -> GenCmm d h g -> GenCmm d h g'
112 cmmTopMapGraph :: (g -> g') -> GenCmmTop d h g -> GenCmmTop d h g'
114 cmmMapGraphM :: Monad m => (String -> g -> m g') -> GenCmm d h g -> m (GenCmm d h g')
115 cmmTopMapGraphM :: Monad m => (String -> g -> m g') -> GenCmmTop d h g -> m (GenCmmTop d h g')
117 cmmMapGraph f (Cmm tops) = Cmm $ map (cmmTopMapGraph f) tops
118 cmmTopMapGraph f (CmmProc h l g) = CmmProc h l (f g)
119 cmmTopMapGraph _ (CmmData s ds) = CmmData s ds
121 cmmMapGraphM f (Cmm tops) = mapM (cmmTopMapGraphM f) tops >>= return . Cmm
122 cmmTopMapGraphM f (CmmProc h l g) =
123 f (showSDoc $ ppr l) g >>= return . CmmProc h l
124 cmmTopMapGraphM _ (CmmData s ds) = return $ CmmData s ds
127 data CmmReturnInfo = CmmMayReturn
131 -----------------------------------------------------------------------------
133 -- A "statement". Note that all branches are explicit: there are no
134 -- control transfers to computed addresses, except when transfering
135 -- control to a new function.
136 -----------------------------------------------------------------------------
138 data CmmStmt -- Old-style
140 | CmmComment FastString
142 | CmmAssign CmmReg CmmExpr -- Assign to register
144 | CmmStore CmmExpr CmmExpr -- Assign to memory location. Size is
145 -- given by cmmExprType of the rhs.
147 | CmmCall -- A call (forign, native or primitive), with
149 HintedCmmFormals -- zero or more results
150 HintedCmmActuals -- zero or more arguments
151 CmmSafety -- whether to build a continuation
154 | CmmBranch BlockId -- branch to another BB in this fn
156 | CmmCondBranch CmmExpr BlockId -- conditional branch
158 | CmmSwitch CmmExpr [Maybe BlockId] -- Table branch
159 -- The scrutinee is zero-based;
160 -- zero -> first block
161 -- one -> second block etc
162 -- Undefined outside range, and when there's a Nothing
164 | CmmJump CmmExpr -- Jump to another C-- function,
165 HintedCmmActuals -- with these parameters. (parameters never used)
167 | CmmReturn -- Return from a native C-- function,
168 HintedCmmActuals -- with these return values. (parameters never used)
170 data CmmHinted a = CmmHinted { hintlessCmm :: a, cmmHint :: ForeignHint }
173 type HintedCmmActuals = [HintedCmmActual]
174 type HintedCmmFormals = [HintedCmmFormal]
175 type HintedCmmFormal = CmmHinted CmmFormal
176 type HintedCmmActual = CmmHinted CmmActual
178 data CmmSafety = CmmUnsafe | CmmSafe C_SRT | CmmInterruptible
180 -- | enable us to fold used registers over 'CmmActuals' and 'CmmFormals'
181 instance UserOfLocalRegs CmmStmt where
182 foldRegsUsed f (set::b) s = stmt s set
184 stmt :: CmmStmt -> b -> b
186 stmt (CmmComment {}) = id
187 stmt (CmmAssign _ e) = gen e
188 stmt (CmmStore e1 e2) = gen e1 . gen e2
189 stmt (CmmCall target _ es _ _) = gen target . gen es
190 stmt (CmmBranch _) = id
191 stmt (CmmCondBranch e _) = gen e
192 stmt (CmmSwitch e _) = gen e
193 stmt (CmmJump e es) = gen e . gen es
194 stmt (CmmReturn es) = gen es
196 gen :: UserOfLocalRegs a => a -> b -> b
197 gen a set = foldRegsUsed f set a
199 instance UserOfLocalRegs CmmCallTarget where
200 foldRegsUsed f set (CmmCallee e _) = foldRegsUsed f set e
201 foldRegsUsed _ set (CmmPrim {}) = set
203 instance UserOfSlots CmmCallTarget where
204 foldSlotsUsed f set (CmmCallee e _) = foldSlotsUsed f set e
205 foldSlotsUsed _ set (CmmPrim {}) = set
207 instance UserOfLocalRegs a => UserOfLocalRegs (CmmHinted a) where
208 foldRegsUsed f set a = foldRegsUsed f set (hintlessCmm a)
210 instance UserOfSlots a => UserOfSlots (CmmHinted a) where
211 foldSlotsUsed f set a = foldSlotsUsed f set (hintlessCmm a)
213 instance DefinerOfLocalRegs a => DefinerOfLocalRegs (CmmHinted a) where
214 foldRegsDefd f set a = foldRegsDefd f set (hintlessCmm a)
220 One possible problem with the above type is that the only way to do a
221 non-local conditional jump is to encode it as a branch to a block that
222 contains a single jump. This leads to inefficient code in the back end.
224 [N.B. This problem will go away when we make the transition to the
225 'zipper' form of control-flow graph, in which both targets of a
226 conditional jump are explicit. ---NR]
228 One possible way to fix this would be:
232 | CmmJump CmmBranchDest
233 | CmmCondJump CmmExpr CmmBranchDest
238 | NonLocal CmmExpr [LocalReg]
242 + one fewer constructors in CmmStmt
243 + allows both cond branch and switch to jump to non-local destinations
247 - not strictly necessary: can already encode as branch+jump
248 - not always possible to implement any better in the back end
249 - could do the optimisation in the back end (but then plat-specific?)
250 - C-- doesn't have it
251 - back-end optimisation might be more general (jump shortcutting)
253 So we'll stick with the way it is, and add the optimisation to the NCG.
256 -----------------------------------------------------------------------------
259 -- The target of a CmmCall.
260 -----------------------------------------------------------------------------
263 = CmmCallee -- Call a function (foreign or native)
264 CmmExpr -- literal label <=> static call
265 -- other expression <=> dynamic call
266 CCallConv -- The calling convention
268 | CmmPrim -- Call a "primitive" (eg. sin, cos)
269 CallishMachOp -- These might be implemented as inline
270 -- code by the backend.