Snapshot of codegen refactoring to share with simonpj
[ghc.git] / compiler / cmm / OldCmm.hs
1 -----------------------------------------------------------------------------
2 --
3 -- Old-style Cmm data types
4 --
5 -- (c) The University of Glasgow 2004-2006
6 --
7 -----------------------------------------------------------------------------
8
9 module OldCmm (
10 CmmPgm, GenCmmPgm, RawCmmPgm, CmmTop, RawCmmTop,
11 ListGraph(..),
12 CmmInfo(..), UpdateFrame(..), CmmInfoTable(..), ClosureTypeInfo(..),
13 CmmStatic(..), CmmStatics(..), CmmFormal, CmmActual,
14 cmmMapGraph, cmmTopMapGraph,
15 cmmMapGraphM, cmmTopMapGraphM,
16 GenBasicBlock(..), CmmBasicBlock, blockId, blockStmts, mapBlockStmts,
17 CmmStmt(..), CmmReturnInfo(..), CmmHinted(..),
18 HintedCmmFormal, HintedCmmActual,
19 CmmSafety(..), CmmCallTarget(..),
20 New.GenCmmTop(..),
21 New.ForeignHint(..),
22 module CmmExpr,
23 Section(..),
24 ProfilingInfo(..), C_SRT(..)
25 ) where
26
27 #include "HsVersions.h"
28
29 import qualified Cmm as New
30 import Cmm ( CmmInfoTable(..), GenCmmPgm, CmmStatics(..), GenCmmTop(..),
31 CmmFormal, CmmActual, Section(..), CmmStatic(..),
32 ProfilingInfo(..), ClosureTypeInfo(..) )
33
34 import BlockId
35 import CmmExpr
36 import ForeignCall
37 import ClosureInfo
38 import Outputable
39 import FastString
40
41
42 -- A [[BlockId]] is a local label.
43 -- Local labels must be unique within an entire compilation unit, not
44 -- just a single top-level item, because local labels map one-to-one
45 -- with assembly-language labels.
46
47 -----------------------------------------------------------------------------
48 -- Info Tables
49 -----------------------------------------------------------------------------
50
51 data CmmInfo
52 = CmmInfo
53 (Maybe BlockId) -- GC target. Nothing <=> CPS won't do stack check
54 -- JD: NOT USED BY NEW CODE GEN
55 (Maybe UpdateFrame) -- Update frame
56 CmmInfoTable -- Info table
57
58 -- | A frame that is to be pushed before entry to the function.
59 -- Used to handle 'update' frames.
60 data UpdateFrame =
61 UpdateFrame
62 CmmExpr -- Frame header. Behaves like the target of a 'jump'.
63 [CmmExpr] -- Frame remainder. Behaves like the arguments of a 'jump'.
64
65 -----------------------------------------------------------------------------
66 -- Cmm, CmmTop, CmmBasicBlock
67 -----------------------------------------------------------------------------
68
69 -- A file is a list of top-level chunks. These may be arbitrarily
70 -- re-orderd during code generation.
71
72 -- | A control-flow graph represented as a list of extended basic blocks.
73 newtype ListGraph i = ListGraph [GenBasicBlock i]
74 -- ^ Code, may be empty. The first block is the entry point. The
75 -- order is otherwise initially unimportant, but at some point the
76 -- code gen will fix the order.
77
78 -- BlockIds must be unique across an entire compilation unit, since
79 -- they are translated to assembly-language labels, which scope
80 -- across a whole compilation unit.
81
82 -- | Cmm with the info table as a data type
83 type CmmPgm = GenCmmPgm CmmStatics CmmInfo (ListGraph CmmStmt)
84 type CmmTop = GenCmmTop CmmStatics CmmInfo (ListGraph CmmStmt)
85
86 -- | Cmm with the info tables converted to a list of 'CmmStatic' along with the info
87 -- table label. If we are building without tables-next-to-code there will be no statics
88 --
89 -- INVARIANT: if there is an info table, it has at least one CmmStatic
90 type RawCmmPgm = GenCmmPgm CmmStatics (Maybe CmmStatics) (ListGraph CmmStmt)
91 type RawCmmTop = GenCmmTop CmmStatics (Maybe CmmStatics) (ListGraph CmmStmt)
92
93
94 -- A basic block containing a single label, at the beginning.
95 -- The list of basic blocks in a top-level code block may be re-ordered.
96 -- Fall-through is not allowed: there must be an explicit jump at the
97 -- end of each basic block, but the code generator might rearrange basic
98 -- blocks in order to turn some jumps into fallthroughs.
99
100 data GenBasicBlock i = BasicBlock BlockId [i]
101 type CmmBasicBlock = GenBasicBlock CmmStmt
102
103 instance UserOfLocalRegs i => UserOfLocalRegs (GenBasicBlock i) where
104 foldRegsUsed f set (BasicBlock _ l) = foldRegsUsed f set l
105
106 blockId :: GenBasicBlock i -> BlockId
107 -- The branch block id is that of the first block in
108 -- the branch, which is that branch's entry point
109 blockId (BasicBlock blk_id _ ) = blk_id
110
111 blockStmts :: GenBasicBlock i -> [i]
112 blockStmts (BasicBlock _ stmts) = stmts
113
114
115 mapBlockStmts :: (i -> i') -> GenBasicBlock i -> GenBasicBlock i'
116 mapBlockStmts f (BasicBlock id bs) = BasicBlock id (map f bs)
117 ----------------------------------------------------------------
118 -- graph maps
119 ----------------------------------------------------------------
120
121 cmmMapGraph :: (g -> g') -> GenCmmPgm d h g -> GenCmmPgm d h g'
122 cmmTopMapGraph :: (g -> g') -> GenCmmTop d h g -> GenCmmTop d h g'
123
124 cmmMapGraphM :: Monad m => (String -> g -> m g') -> GenCmmPgm d h g -> m (GenCmmPgm d h g')
125 cmmTopMapGraphM :: Monad m => (String -> g -> m g') -> GenCmmTop d h g -> m (GenCmmTop d h g')
126
127 cmmMapGraph f tops = map (cmmTopMapGraph f) tops
128 cmmTopMapGraph f (CmmProc h l g) = CmmProc h l (f g)
129 cmmTopMapGraph _ (CmmData s ds) = CmmData s ds
130
131 cmmMapGraphM f tops = mapM (cmmTopMapGraphM f) tops
132 cmmTopMapGraphM f (CmmProc h l g) =
133 f (showSDoc $ ppr l) g >>= return . CmmProc h l
134 cmmTopMapGraphM _ (CmmData s ds) = return $ CmmData s ds
135
136
137 data CmmReturnInfo = CmmMayReturn
138 | CmmNeverReturns
139 deriving ( Eq )
140
141 -----------------------------------------------------------------------------
142 -- CmmStmt
143 -- A "statement". Note that all branches are explicit: there are no
144 -- control transfers to computed addresses, except when transfering
145 -- control to a new function.
146 -----------------------------------------------------------------------------
147
148 data CmmStmt -- Old-style
149 = CmmNop
150 | CmmComment FastString
151
152 | CmmAssign CmmReg CmmExpr -- Assign to register
153
154 | CmmStore CmmExpr CmmExpr -- Assign to memory location. Size is
155 -- given by cmmExprType of the rhs.
156
157 | CmmCall -- A call (foreign, native or primitive), with
158 CmmCallTarget
159 [HintedCmmFormal] -- zero or more results
160 [HintedCmmActual] -- zero or more arguments
161 CmmSafety -- whether to build a continuation
162 CmmReturnInfo
163 -- Some care is necessary when handling the arguments of these, see
164 -- [Register parameter passing] and the hack in cmm/CmmOpt.hs
165
166 | CmmBranch BlockId -- branch to another BB in this fn
167
168 | CmmCondBranch CmmExpr BlockId -- conditional branch
169
170 | CmmSwitch CmmExpr [Maybe BlockId] -- Table branch
171 -- The scrutinee is zero-based;
172 -- zero -> first block
173 -- one -> second block etc
174 -- Undefined outside range, and when there's a Nothing
175
176 | CmmJump CmmExpr -- Jump to another C-- function,
177 [HintedCmmActual] -- with these parameters. (parameters never used)
178
179 | CmmReturn -- Return from a native C-- function,
180 [HintedCmmActual] -- with these return values. (parameters never used)
181
182 data CmmHinted a = CmmHinted { hintlessCmm :: a, cmmHint :: New.ForeignHint }
183 deriving( Eq )
184
185 type HintedCmmFormal = CmmHinted CmmFormal
186 type HintedCmmActual = CmmHinted CmmActual
187
188 data CmmSafety = CmmUnsafe | CmmSafe C_SRT | CmmInterruptible
189
190 -- | enable us to fold used registers over '[CmmActual]' and '[CmmFormal]'
191 instance UserOfLocalRegs CmmStmt where
192 foldRegsUsed f (set::b) s = stmt s set
193 where
194 stmt :: CmmStmt -> b -> b
195 stmt (CmmNop) = id
196 stmt (CmmComment {}) = id
197 stmt (CmmAssign _ e) = gen e
198 stmt (CmmStore e1 e2) = gen e1 . gen e2
199 stmt (CmmCall target _ es _ _) = gen target . gen es
200 stmt (CmmBranch _) = id
201 stmt (CmmCondBranch e _) = gen e
202 stmt (CmmSwitch e _) = gen e
203 stmt (CmmJump e es) = gen e . gen es
204 stmt (CmmReturn es) = gen es
205
206 gen :: UserOfLocalRegs a => a -> b -> b
207 gen a set = foldRegsUsed f set a
208
209 instance UserOfLocalRegs CmmCallTarget where
210 foldRegsUsed f set (CmmCallee e _) = foldRegsUsed f set e
211 foldRegsUsed _ set (CmmPrim {}) = set
212
213 instance UserOfSlots CmmCallTarget where
214 foldSlotsUsed f set (CmmCallee e _) = foldSlotsUsed f set e
215 foldSlotsUsed _ set (CmmPrim {}) = set
216
217 instance UserOfLocalRegs a => UserOfLocalRegs (CmmHinted a) where
218 foldRegsUsed f set a = foldRegsUsed f set (hintlessCmm a)
219
220 instance UserOfSlots a => UserOfSlots (CmmHinted a) where
221 foldSlotsUsed f set a = foldSlotsUsed f set (hintlessCmm a)
222
223 instance DefinerOfLocalRegs a => DefinerOfLocalRegs (CmmHinted a) where
224 foldRegsDefd f set a = foldRegsDefd f set (hintlessCmm a)
225
226 {-
227 Discussion
228 ~~~~~~~~~~
229
230 One possible problem with the above type is that the only way to do a
231 non-local conditional jump is to encode it as a branch to a block that
232 contains a single jump. This leads to inefficient code in the back end.
233
234 [N.B. This problem will go away when we make the transition to the
235 'zipper' form of control-flow graph, in which both targets of a
236 conditional jump are explicit. ---NR]
237
238 One possible way to fix this would be:
239
240 data CmmStat =
241 ...
242 | CmmJump CmmBranchDest
243 | CmmCondJump CmmExpr CmmBranchDest
244 ...
245
246 data CmmBranchDest
247 = Local BlockId
248 | NonLocal CmmExpr [LocalReg]
249
250 In favour:
251
252 + one fewer constructors in CmmStmt
253 + allows both cond branch and switch to jump to non-local destinations
254
255 Against:
256
257 - not strictly necessary: can already encode as branch+jump
258 - not always possible to implement any better in the back end
259 - could do the optimisation in the back end (but then plat-specific?)
260 - C-- doesn't have it
261 - back-end optimisation might be more general (jump shortcutting)
262
263 So we'll stick with the way it is, and add the optimisation to the NCG.
264 -}
265
266 -----------------------------------------------------------------------------
267 -- CmmCallTarget
268 --
269 -- The target of a CmmCall.
270 -----------------------------------------------------------------------------
271
272 data CmmCallTarget
273 = CmmCallee -- Call a function (foreign or native)
274 CmmExpr -- literal label <=> static call
275 -- other expression <=> dynamic call
276 CCallConv -- The calling convention
277
278 | CmmPrim -- Call a "primitive" (eg. sin, cos)
279 CallishMachOp -- These might be implemented as inline
280 -- code by the backend.
281 deriving Eq