Cmm.hs 12.6 KB
Newer Older
1
2
3
4
{-# OPTIONS -fno-warn-name-shadowing -w #-}
-- We'd like to use -fno-warn-orphans rather than -w, but old compilers
-- don't understand it so building stage1 fails.

5
6
7
8
-----------------------------------------------------------------------------
--
-- Cmm data types
--
Simon Marlow's avatar
Simon Marlow committed
9
-- (c) The University of Glasgow 2004-2006
10
11
12
13
--
-----------------------------------------------------------------------------

module Cmm ( 
14
15
	GenCmm(..), Cmm, RawCmm,
	GenCmmTop(..), CmmTop, RawCmmTop,
16
17
18
	ListGraph(..),
        cmmMapGraph, cmmTopMapGraph,
        cmmMapGraphM, cmmTopMapGraphM,
19
20
	CmmInfo(..), UpdateFrame(..),
        CmmInfoTable(..), ClosureTypeInfo(..), ProfilingInfo(..), ClosureTypeTag,
21
        GenBasicBlock(..), CmmBasicBlock, blockId, blockStmts, mapBlockStmts,
22
        CmmReturnInfo(..),
23
	CmmStmt(..), CmmActuals, CmmFormal, CmmFormals, CmmHintFormals,
24
        CmmSafety(..),
25
26
	CmmCallTarget(..),
	CmmStatic(..), Section(..),
27
	CmmExpr(..), cmmExprRep, maybeInvertCmmExpr,
28
29
	CmmReg(..), cmmRegRep,
	CmmLit(..), cmmLitRep,
30
	LocalReg(..), localRegRep, localRegGCFollow, Kind(..),
31
32
33
        BlockId(..), freshBlockId,
        BlockEnv, emptyBlockEnv, lookupBlockEnv, extendBlockEnv, mkBlockEnv,
        BlockSet, emptyBlockSet, elemBlockSet, extendBlockSet,
34
35
	GlobalReg(..), globalRegRep,

36
	node, nodeReg, spReg, hpReg, spLimReg
37
38
  ) where

39
40
41
42
-- ^ In order not to do violence to the import structure of the rest
-- of the compiler, module Cmm re-exports a number of identifiers
-- defined in 'CmmExpr'

43
44
#include "HsVersions.h"

45
import CmmExpr
46
import MachOp
Simon Marlow's avatar
Simon Marlow committed
47
48
import CLabel
import ForeignCall
49
import SMRep
50
import ClosureInfo
51
import Outputable
Simon Marlow's avatar
Simon Marlow committed
52
53
54
import FastString

import Data.Word
55

56
57
58
59
60
61
62
63
64
65
import ZipCfg (	BlockId(..), freshBlockId
              , BlockEnv, emptyBlockEnv, lookupBlockEnv, extendBlockEnv, mkBlockEnv
              , BlockSet, emptyBlockSet, elemBlockSet, extendBlockSet
              )

-- A [[BlockId]] is a local label.
-- Local labels must be unique within an entire compilation unit, not
-- just a single top-level item, because local labels map one-to-one
-- with assembly-language labels.

66
67
68
69
70
71
72
73
-----------------------------------------------------------------------------
--		Cmm, CmmTop, CmmBasicBlock
-----------------------------------------------------------------------------

-- A file is a list of top-level chunks.  These may be arbitrarily
-- re-orderd during code generation.

-- GenCmm is abstracted over
74
75
--   d, the type of static data elements in CmmData
--   h, the static info preceding the code of a CmmProc
76
--   g, the control-flow graph of a CmmProc
77
--
78
-- We expect there to be two main instances of this type:
79
80
81
--   (a) C--, i.e. populated with various C-- constructs
--		(Cmm and RawCmm below)
--   (b) Native code, populated with data/instructions
82
--
83
84
-- A second family of instances based on ZipCfg is work in progress.
--
85
newtype GenCmm d h g = Cmm [GenCmmTop d h g]
86

87
-- | A top-level chunk, abstracted over the type of the contents of
88
-- the basic blocks (Cmm or instructions are the likely instantiations).
89
data GenCmmTop d h g
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
95
96
97
98

  | CmmData 	-- Static data
	Section 
	[d]
99

100
101
102
103
104
105
106
107
108
109
-- | A control-flow graph represented as a list of extended basic blocks.
newtype ListGraph i = ListGraph [GenBasicBlock i] 
   -- ^ Code, may be empty.  The first block is the entry point.  The
   -- order is otherwise initially unimportant, but at some point the
   -- code gen will fix the order.

   -- BlockIds must be unique across an entire compilation unit, since
   -- they are translated to assembly-language labels, which scope
   -- across a whole compilation unit.

110
-- | Cmm with the info table as a data type
111
112
type Cmm    = GenCmm    CmmStatic CmmInfo (ListGraph CmmStmt)
type CmmTop = GenCmmTop CmmStatic CmmInfo (ListGraph CmmStmt)
113
114

-- | Cmm with the info tables converted to a list of 'CmmStatic'
115
116
type RawCmm    = GenCmm    CmmStatic [CmmStatic] (ListGraph CmmStmt)
type RawCmmTop = GenCmmTop CmmStatic [CmmStatic] (ListGraph CmmStmt)
117

118

119
120
121
122
123
124
125
-- A basic block containing a single label, at the beginning.
-- The list of basic blocks in a top-level code block may be re-ordered.
-- Fall-through is not allowed: there must be an explicit jump at the
-- end of each basic block, but the code generator might rearrange basic
-- blocks in order to turn some jumps into fallthroughs.

data GenBasicBlock i = BasicBlock BlockId [i]
126
type CmmBasicBlock   = GenBasicBlock CmmStmt
127

128
129
130
instance UserOfLocalRegs i => UserOfLocalRegs (GenBasicBlock i) where
    foldRegsUsed f set (BasicBlock _ l) = foldRegsUsed f set l

131
132
133
134
135
136
137
138
blockId :: GenBasicBlock i -> BlockId
-- The branch block id is that of the first block in 
-- the branch, which is that branch's entry point
blockId (BasicBlock blk_id _ ) = blk_id

blockStmts :: GenBasicBlock i -> [i]
blockStmts (BasicBlock _ stmts) = stmts

139

140
mapBlockStmts :: (i -> i') -> GenBasicBlock i -> GenBasicBlock i'
141
mapBlockStmts f (BasicBlock id bs) = BasicBlock id (map f bs)
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
----------------------------------------------------------------
--   graph maps
----------------------------------------------------------------

cmmMapGraph    :: (g -> g') -> GenCmm    d h g -> GenCmm    d h g'
cmmTopMapGraph :: (g -> g') -> GenCmmTop d h g -> GenCmmTop d h g'

cmmMapGraphM    :: Monad m => (String -> g -> m g') -> GenCmm    d h g -> m (GenCmm    d h g')
cmmTopMapGraphM :: Monad m => (String -> g -> m g') -> GenCmmTop d h g -> m (GenCmmTop d h g')

cmmMapGraph f (Cmm tops) = Cmm $ map (cmmTopMapGraph f) tops
cmmTopMapGraph f (CmmProc h l args g) = CmmProc h l args (f g)
cmmTopMapGraph _ (CmmData s ds)       = CmmData s ds

cmmMapGraphM f (Cmm tops) = mapM (cmmTopMapGraphM f) tops >>= return . Cmm
cmmTopMapGraphM f (CmmProc h l args g) = f (showSDoc $ ppr l) g >>= return . CmmProc h l args
cmmTopMapGraphM _ (CmmData s ds)       = return $ CmmData s ds
159

160
161
162
163
164
165
-----------------------------------------------------------------------------
--     Info Tables
-----------------------------------------------------------------------------

data CmmInfo
  = CmmInfo
166
      (Maybe BlockId)     -- GC target. Nothing <=> CPS won't do stack check
167
      (Maybe UpdateFrame) -- Update frame
168
      CmmInfoTable        -- Info table
169
170
171
172
173

-- Info table as a haskell data type
data CmmInfoTable
  = CmmInfoTable
      ProfilingInfo
174
175
      ClosureTypeTag -- Int
      ClosureTypeInfo
176
  | CmmNonInfoTable   -- Procedure doesn't need an info table
177
178
179
180

-- TODO: The GC target shouldn't really be part of CmmInfo
-- as it doesn't appear in the resulting info table.
-- It should be factored out.
181
182
183
184
185

data ClosureTypeInfo
  = ConstrInfo ClosureLayout ConstrTag ConstrDescription
  | FunInfo ClosureLayout C_SRT FunType FunArity ArgDescr SlowEntry
  | ThunkInfo ClosureLayout C_SRT
186
  | ThunkSelectorInfo SelectorOffset C_SRT
187
188
189
190
  | ContInfo
      [Maybe LocalReg]  -- Forced stack parameters
      C_SRT

191
192
data CmmReturnInfo = CmmMayReturn
                   | CmmNeverReturns
193

194
195
196
-- TODO: These types may need refinement
data ProfilingInfo = ProfilingInfo CmmLit CmmLit -- closure_type, closure_desc
type ClosureTypeTag = StgHalfWord
197
type ClosureLayout = (StgHalfWord, StgHalfWord) -- ptrs, nptrs
198
type ConstrTag = StgHalfWord
199
type ConstrDescription = CmmLit
200
201
type FunType = StgHalfWord
type FunArity = StgHalfWord
202
203
204
type SlowEntry = CmmLit
  -- ^We would like this to be a CLabel but
  -- for now the parser sets this to zero on an INFO_TABLE_FUN.
205
type SelectorOffset = StgWord
206

207
208
209
210
211
212
213
-- | A frame that is to be pushed before entry to the function.
-- Used to handle 'update' frames.
data UpdateFrame =
    UpdateFrame
      CmmExpr    -- Frame header.  Behaves like the target of a 'jump'.
      [CmmExpr]  -- Frame remainder.  Behaves like the arguments of a 'jump'.

214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
-----------------------------------------------------------------------------
--		CmmStmt
-- A "statement".  Note that all branches are explicit: there are no
-- control transfers to computed addresses, except when transfering
-- control to a new function.
-----------------------------------------------------------------------------

data CmmStmt
  = CmmNop
  | CmmComment FastString

  | CmmAssign CmmReg CmmExpr	 -- Assign to register

  | CmmStore CmmExpr CmmExpr     -- Assign to memory location.  Size is
                                 -- given by cmmExprRep of the rhs.

230
  | CmmCall	 		 -- A call (forign, native or primitive), with 
231
     CmmCallTarget
232
     CmmHintFormals		 -- zero or more results
233
     CmmActuals			 -- zero or more arguments
234
     CmmSafety			 -- whether to build a continuation
235
     CmmReturnInfo
236
237
238
239
240
241
242
243
244
245
246

  | CmmBranch BlockId             -- branch to another BB in this fn

  | CmmCondBranch CmmExpr BlockId -- conditional branch

  | CmmSwitch CmmExpr [Maybe BlockId]   -- Table branch
	-- The scrutinee is zero-based; 
	--	zero -> first block
	--	one  -> second block etc
	-- Undefined outside range, and when there's a Nothing

247
248
  | CmmJump CmmExpr      -- Jump to another C-- function,
      CmmActuals         -- with these parameters.
249

250
251
  | CmmReturn            -- Return from a native C-- function,
      CmmActuals         -- with these return values.
252

253
254
255
type CmmActual      = CmmExpr
type CmmActuals     = [(CmmActual,MachHint)]
type CmmFormal      = LocalReg
256
type CmmHintFormals = [(CmmFormal,MachHint)]
257
258
type CmmFormals     = [CmmFormal]
data CmmSafety      = CmmUnsafe | CmmSafe C_SRT
259

260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
-- | enable us to fold used registers over 'CmmActuals' and 'CmmHintFormals'
instance UserOfLocalRegs a => UserOfLocalRegs (a, MachHint) where
  foldRegsUsed f set (a, _) = foldRegsUsed f set a

instance UserOfLocalRegs CmmStmt where
  foldRegsUsed f set s = stmt s set
    where stmt (CmmNop)                  = id
          stmt (CmmComment {})           = id
          stmt (CmmAssign _ e)           = gen e
          stmt (CmmStore e1 e2)          = gen e1 . gen e2
          stmt (CmmCall target _ es _ _) = gen target . gen es
          stmt (CmmBranch _)             = id
          stmt (CmmCondBranch e _)       = gen e
          stmt (CmmSwitch e _)           = gen e
          stmt (CmmJump e es)            = gen e . gen es
          stmt (CmmReturn es)            = gen es
          gen a set = foldRegsUsed f set a

instance UserOfLocalRegs CmmCallTarget where
    foldRegsUsed f set (CmmCallee e _) = foldRegsUsed f set e
    foldRegsUsed _ set (CmmPrim {})    = set

282
283
284
285
286
287
288
289
{-
Discussion
~~~~~~~~~~

One possible problem with the above type is that the only way to do a
non-local conditional jump is to encode it as a branch to a block that
contains a single jump.  This leads to inefficient code in the back end.

290
291
292
293
[N.B. This problem will go away when we make the transition to the
'zipper' form of control-flow graph, in which both targets of a
conditional jump are explicit. ---NR]

294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
One possible way to fix this would be:

data CmmStat = 
  ...
  | CmmJump CmmBranchDest
  | CmmCondJump CmmExpr CmmBranchDest
  ...

data CmmBranchDest
  = Local BlockId
  | NonLocal CmmExpr [LocalReg]

In favour:

+ one fewer constructors in CmmStmt
+ allows both cond branch and switch to jump to non-local destinations

Against:

- not strictly necessary: can already encode as branch+jump
- not always possible to implement any better in the back end
- could do the optimisation in the back end (but then plat-specific?)
- C-- doesn't have it
- back-end optimisation might be more general (jump shortcutting)

So we'll stick with the way it is, and add the optimisation to the NCG.
-}

322
323
324
325
326
327
328
-----------------------------------------------------------------------------
--		CmmCallTarget
--
-- The target of a CmmCall.
-----------------------------------------------------------------------------

data CmmCallTarget
329
  = CmmCallee		-- Call a function (foreign or native)
330
331
332
333
	CmmExpr 		-- literal label <=> static call
				-- other expression <=> dynamic call
	CCallConv		-- The calling convention

334
  | CmmPrim		-- Call a "primitive" (eg. sin, cos)
335
336
337
338
339
340
341
342
343
344
345
	CallishMachOp		-- These might be implemented as inline
				-- code by the backend.

-----------------------------------------------------------------------------
--		Static Data
-----------------------------------------------------------------------------

data Section
  = Text
  | Data
  | ReadOnlyData
346
  | RelocatableReadOnlyData
347
  | UninitialisedData
348
  | ReadOnlyData16	-- .rodata.cst16 on x86_64, 16-byte aligned
349
350
351
352
353
354
355
356
357
358
359
  | OtherSection String

data CmmStatic
  = CmmStaticLit CmmLit	
	-- a literal value, size given by cmmLitRep of the literal.
  | CmmUninitialised Int
	-- uninitialised data, N bytes long
  | CmmAlign Int
	-- align to next N-byte boundary (N must be a power of 2).
  | CmmDataLabel CLabel
	-- label the current position in this section.
360
  | CmmString [Word8]
361
362
	-- string of 8-bit values only, not zero terminated.