1aaca36274acf2fd3efadf6660444e0d1c216a84
[ghc.git] / compiler / prelude / PrimOp.lhs
1 %
2 % (c) The GRASP/AQUA Project, Glasgow University, 1992-1998
3 %
4 \section[PrimOp]{Primitive operations (machine-level)}
5
6 \begin{code}
7 module PrimOp (
8         PrimOp(..), allThePrimOps,
9         primOpType, primOpSig,
10         primOpTag, maxPrimOpTag, primOpOcc,
11
12         tagToEnumKey,
13
14         primOpOutOfLine, primOpCodeSize,
15         primOpOkForSpeculation, primOpOkForSideEffects,
16         primOpIsCheap, primOpFixity,
17
18         getPrimOpResultInfo,  PrimOpResultInfo(..),
19
20         PrimCall(..)
21     ) where
22
23 #include "HsVersions.h"
24
25 import TysPrim
26 import TysWiredIn
27
28 import Demand
29 import Var              ( TyVar )
30 import OccName          ( OccName, pprOccName, mkVarOccFS )
31 import TyCon            ( TyCon, isPrimTyCon, tyConPrimRep, PrimRep(..) )
32 import Type             ( Type, mkForAllTys, mkFunTy, mkFunTys, tyConAppTyCon,
33                           typePrimRep )
34 import BasicTypes       ( Arity, Fixity(..), FixityDirection(..), TupleSort(..) )
35 import ForeignCall      ( CLabelString )
36 import Unique           ( Unique, mkPrimOpIdUnique )
37 import Outputable
38 import FastTypes
39 import FastString
40 import Module           ( PackageId )
41 \end{code}
42
43 %************************************************************************
44 %*                                                                      *
45 \subsection[PrimOp-datatype]{Datatype for @PrimOp@ (an enumeration)}
46 %*                                                                      *
47 %************************************************************************
48
49 These are in \tr{state-interface.verb} order.
50
51 \begin{code}
52
53 -- supplies:
54 -- data PrimOp = ...
55 #include "primop-data-decl.hs-incl"
56 \end{code}
57
58 Used for the Ord instance
59
60 \begin{code}
61 primOpTag :: PrimOp -> Int
62 primOpTag op = iBox (tagOf_PrimOp op)
63
64 -- supplies
65 -- tagOf_PrimOp :: PrimOp -> FastInt
66 #include "primop-tag.hs-incl"
67
68
69 instance Eq PrimOp where
70     op1 == op2 = tagOf_PrimOp op1 ==# tagOf_PrimOp op2
71
72 instance Ord PrimOp where
73     op1 <  op2 =  tagOf_PrimOp op1 <# tagOf_PrimOp op2
74     op1 <= op2 =  tagOf_PrimOp op1 <=# tagOf_PrimOp op2
75     op1 >= op2 =  tagOf_PrimOp op1 >=# tagOf_PrimOp op2
76     op1 >  op2 =  tagOf_PrimOp op1 ># tagOf_PrimOp op2
77     op1 `compare` op2 | op1 < op2  = LT
78                       | op1 == op2 = EQ
79                       | otherwise  = GT
80
81 instance Outputable PrimOp where
82     ppr op = pprPrimOp op
83 \end{code}
84
85 An @Enum@-derived list would be better; meanwhile... (ToDo)
86
87 \begin{code}
88 allThePrimOps :: [PrimOp]
89 allThePrimOps =
90 #include "primop-list.hs-incl"
91 \end{code}
92
93 \begin{code}
94 tagToEnumKey :: Unique
95 tagToEnumKey = mkPrimOpIdUnique (primOpTag TagToEnumOp)
96 \end{code}
97
98
99
100 %************************************************************************
101 %*                                                                      *
102 \subsection[PrimOp-info]{The essential info about each @PrimOp@}
103 %*                                                                      *
104 %************************************************************************
105
106 The @String@ in the @PrimOpInfos@ is the ``base name'' by which the user may
107 refer to the primitive operation.  The conventional \tr{#}-for-
108 unboxed ops is added on later.
109
110 The reason for the funny characters in the names is so we do not
111 interfere with the programmer's Haskell name spaces.
112
113 We use @PrimKinds@ for the ``type'' information, because they're
114 (slightly) more convenient to use than @TyCons@.
115 \begin{code}
116 data PrimOpInfo
117   = Dyadic      OccName         -- string :: T -> T -> T
118                 Type
119   | Monadic     OccName         -- string :: T -> T
120                 Type
121   | Compare     OccName         -- string :: T -> T -> Bool
122                 Type
123
124   | GenPrimOp   OccName         -- string :: \/a1..an . T1 -> .. -> Tk -> T
125                 [TyVar]
126                 [Type]
127                 Type
128
129 mkDyadic, mkMonadic, mkCompare :: FastString -> Type -> PrimOpInfo
130 mkDyadic str  ty = Dyadic  (mkVarOccFS str) ty
131 mkMonadic str ty = Monadic (mkVarOccFS str) ty
132 mkCompare str ty = Compare (mkVarOccFS str) ty
133
134 mkGenPrimOp :: FastString -> [TyVar] -> [Type] -> Type -> PrimOpInfo
135 mkGenPrimOp str tvs tys ty = GenPrimOp (mkVarOccFS str) tvs tys ty
136 \end{code}
137
138 %************************************************************************
139 %*                                                                      *
140 \subsubsection{Strictness}
141 %*                                                                      *
142 %************************************************************************
143
144 Not all primops are strict!
145
146 \begin{code}
147 primOpStrictness :: PrimOp -> Arity -> StrictSig
148         -- See Demand.StrictnessInfo for discussion of what the results
149         -- The arity should be the arity of the primop; that's why
150         -- this function isn't exported.
151 #include "primop-strictness.hs-incl"
152 \end{code}
153
154 %************************************************************************
155 %*                                                                      *
156 \subsubsection{Fixity}
157 %*                                                                      *
158 %************************************************************************
159
160 \begin{code}
161 primOpFixity :: PrimOp -> Maybe Fixity
162 #include "primop-fixity.hs-incl"
163 \end{code}
164
165 %************************************************************************
166 %*                                                                      *
167 \subsubsection[PrimOp-comparison]{PrimOpInfo basic comparison ops}
168 %*                                                                      *
169 %************************************************************************
170
171 @primOpInfo@ gives all essential information (from which everything
172 else, notably a type, can be constructed) for each @PrimOp@.
173
174 \begin{code}
175 primOpInfo :: PrimOp -> PrimOpInfo
176 #include "primop-primop-info.hs-incl"
177 \end{code}
178
179 Here are a load of comments from the old primOp info:
180
181 A @Word#@ is an unsigned @Int#@.
182
183 @decodeFloat#@ is given w/ Integer-stuff (it's similar).
184
185 @decodeDouble#@ is given w/ Integer-stuff (it's similar).
186
187 Decoding of floating-point numbers is sorta Integer-related.  Encoding
188 is done with plain ccalls now (see PrelNumExtra.lhs).
189
190 A @Weak@ Pointer is created by the @mkWeak#@ primitive:
191
192         mkWeak# :: k -> v -> f -> State# RealWorld
193                         -> (# State# RealWorld, Weak# v #)
194
195 In practice, you'll use the higher-level
196
197         data Weak v = Weak# v
198         mkWeak :: k -> v -> IO () -> IO (Weak v)
199
200 The following operation dereferences a weak pointer.  The weak pointer
201 may have been finalized, so the operation returns a result code which
202 must be inspected before looking at the dereferenced value.
203
204         deRefWeak# :: Weak# v -> State# RealWorld ->
205                         (# State# RealWorld, v, Int# #)
206
207 Only look at v if the Int# returned is /= 0 !!
208
209 The higher-level op is
210
211         deRefWeak :: Weak v -> IO (Maybe v)
212
213 Weak pointers can be finalized early by using the finalize# operation:
214
215         finalizeWeak# :: Weak# v -> State# RealWorld ->
216                            (# State# RealWorld, Int#, IO () #)
217
218 The Int# returned is either
219
220         0 if the weak pointer has already been finalized, or it has no
221           finalizer (the third component is then invalid).
222
223         1 if the weak pointer is still alive, with the finalizer returned
224           as the third component.
225
226 A {\em stable name/pointer} is an index into a table of stable name
227 entries.  Since the garbage collector is told about stable pointers,
228 it is safe to pass a stable pointer to external systems such as C
229 routines.
230
231 \begin{verbatim}
232 makeStablePtr#  :: a -> State# RealWorld -> (# State# RealWorld, StablePtr# a #)
233 freeStablePtr   :: StablePtr# a -> State# RealWorld -> State# RealWorld
234 deRefStablePtr# :: StablePtr# a -> State# RealWorld -> (# State# RealWorld, a #)
235 eqStablePtr#    :: StablePtr# a -> StablePtr# a -> Int#
236 \end{verbatim}
237
238 It may seem a bit surprising that @makeStablePtr#@ is a @IO@
239 operation since it doesn't (directly) involve IO operations.  The
240 reason is that if some optimisation pass decided to duplicate calls to
241 @makeStablePtr#@ and we only pass one of the stable pointers over, a
242 massive space leak can result.  Putting it into the IO monad
243 prevents this.  (Another reason for putting them in a monad is to
244 ensure correct sequencing wrt the side-effecting @freeStablePtr@
245 operation.)
246
247 An important property of stable pointers is that if you call
248 makeStablePtr# twice on the same object you get the same stable
249 pointer back.
250
251 Note that we can implement @freeStablePtr#@ using @_ccall_@ (and,
252 besides, it's not likely to be used from Haskell) so it's not a
253 primop.
254
255 Question: Why @RealWorld@ - won't any instance of @_ST@ do the job? [ADR]
256
257 Stable Names
258 ~~~~~~~~~~~~
259
260 A stable name is like a stable pointer, but with three important differences:
261
262         (a) You can't deRef one to get back to the original object.
263         (b) You can convert one to an Int.
264         (c) You don't need to 'freeStableName'
265
266 The existence of a stable name doesn't guarantee to keep the object it
267 points to alive (unlike a stable pointer), hence (a).
268
269 Invariants:
270
271         (a) makeStableName always returns the same value for a given
272             object (same as stable pointers).
273
274         (b) if two stable names are equal, it implies that the objects
275             from which they were created were the same.
276
277         (c) stableNameToInt always returns the same Int for a given
278             stable name.
279
280
281 -- HWL: The first 4 Int# in all par... annotations denote:
282 --   name, granularity info, size of result, degree of parallelism
283 --      Same  structure as _seq_ i.e. returns Int#
284 -- KSW: v, the second arg in parAt# and parAtForNow#, is used only to determine
285 --   `the processor containing the expression v'; it is not evaluated
286
287 These primops are pretty wierd.
288
289         dataToTag# :: a -> Int    (arg must be an evaluated data type)
290         tagToEnum# :: Int -> a    (result type must be an enumerated type)
291
292 The constraints aren't currently checked by the front end, but the
293 code generator will fall over if they aren't satisfied.
294
295 %************************************************************************
296 %*                                                                      *
297             Which PrimOps are out-of-line
298 %*                                                                      *
299 %************************************************************************
300
301 Some PrimOps need to be called out-of-line because they either need to
302 perform a heap check or they block.
303
304
305 \begin{code}
306 primOpOutOfLine :: PrimOp -> Bool
307 #include "primop-out-of-line.hs-incl"
308 \end{code}
309
310
311 %************************************************************************
312 %*                                                                      *
313             Failure and side effects
314 %*                                                                      *
315 %************************************************************************
316
317 Note [PrimOp can_fail and has_side_effects]
318 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
319 Both can_fail and has_side_effects mean that the primop has
320 some effect that is not captured entirely by its result value.
321
322    ----------  has_side_effects ---------------------
323    Has some imperative side effect, perhaps on the world (I/O),
324    or perhaps on some mutable data structure (writeIORef).
325    Generally speaking all such primops have a type like
326       State -> input -> (State, output)
327    so the state token guarantees ordering, and also ensures
328    that the primop is executed even if 'output' is discarded.
329
330    ----------  can_fail ----------------------------
331    Can fail with a seg-fault or divide-by-zero error on some elements
332    of its input domain.  Main examples:
333       division (fails on zero demoninator
334       array indexing (fails if the index is out of bounds)
335    However (ASSUMPTION), these can_fail primops are ALWAYS surrounded
336    with a test that checks for the bad cases.  
337
338 Consequences:
339
340 * You can discard a can_fail primop, or float it _inwards_.
341   But you cannot float it _outwards_, lest you escape the
342   dynamic scope of the test.  Example:
343       case d ># 0# of
344         True  -> case x /# d of r -> r +# 1
345         False -> 0
346   Here we must not float the case outwards to give
347       case x/# d of r ->
348       case d ># 0# of
349         True  -> r +# 1
350         False -> 0
351
352 * I believe that exactly the same rules apply to a has_side_effects
353   primop; you can discard it (remember, the state token will keep
354   it alive if necessary), or float it in, but not float it out.
355
356   Example of the latter
357        if blah then let! s1 = writeMutVar s0 v True in s1
358                else s0
359   Notice that s0 is mentioned in both branches of the 'if', but 
360   only one of these two will actually be consumed.  But if we
361   float out to
362       let! s1 = writeMutVar s0 v True
363       in if blah then s1 else s0
364   the writeMutVar will be performed in both branches, which is
365   utterly wrong.
366
367 * You cannot duplicate a has_side_effect primop.  You might wonder
368   how this can occur given the state token threading, but just look
369   at Control.Monad.ST.Lazy.Imp.strictToLazy!  We get something like
370   this
371         p = case readMutVar# s v of
372               (# s', r #) -> (S# s', r)
373         s' = case p of (s', r) -> s'
374         r  = case p of (s', r) -> r
375
376   (All these bindings are boxed.)  If we inline p at its two call
377   sites, we get a catastrophe: because the read is performed once when
378   s' is demanded, and once when 'r' is demanded, which may be much 
379   later.  Utterly wrong.  Trac #3207 is real example of this happening.
380
381   However, it's fine to duplicate a can_fail primop.  That is
382   the difference between can_fail and has_side_effects.
383
384             can_fail     has_side_effects
385 Discard        YES           YES
386 Float in       YES           YES
387 Float out      NO            NO
388 Duplicate      YES           NO
389
390 How do we achieve these effects?
391
392 Note [primOpOkForSpeculation]
393   * The "no-float-out" thing is achieved by ensuring that we never
394     let-bind a can_fail or has_side_effects primop.  The RHS of a
395     let-binding (which can float in and out freely) satisfies
396     exprOkForSpeculation.  And exprOkForSpeculation is false of
397     can_fail and no_side_effect.
398
399   * So can_fail and no_side_effect primops will appear only as the
400     scrutinees of cases, and that's why the FloatIn pass is capable
401     of floating case bindings inwards.
402
403   * The no-duplicate thing is done via primOpIsCheap, by making
404     has_side_effects things (very very very) not-cheap!
405
406
407 \begin{code}
408 primOpHasSideEffects :: PrimOp -> Bool
409 #include "primop-has-side-effects.hs-incl"
410
411 primOpCanFail :: PrimOp -> Bool
412 #include "primop-can-fail.hs-incl"
413
414 primOpOkForSpeculation :: PrimOp -> Bool
415   -- See Note [primOpOkForSpeculation and primOpOkForFloatOut]
416   -- See comments with CoreUtils.exprOkForSpeculation
417 primOpOkForSpeculation op
418   = not (primOpHasSideEffects op || primOpOutOfLine op || primOpCanFail op)
419
420 primOpOkForSideEffects :: PrimOp -> Bool
421 primOpOkForSideEffects op
422   = not (primOpHasSideEffects op)
423 \end{code}
424
425
426 Note [primOpIsCheap]
427 ~~~~~~~~~~~~~~~~~~~~
428 @primOpIsCheap@, as used in \tr{SimplUtils.lhs}.  For now (HACK
429 WARNING), we just borrow some other predicates for a
430 what-should-be-good-enough test.  "Cheap" means willing to call it more
431 than once, and/or push it inside a lambda.  The latter could change the
432 behaviour of 'seq' for primops that can fail, so we don't treat them as cheap.
433
434 \begin{code}
435 primOpIsCheap :: PrimOp -> Bool
436 primOpIsCheap op = primOpOkForSpeculation op
437 -- In March 2001, we changed this to
438 --      primOpIsCheap op = False
439 -- thereby making *no* primops seem cheap.  But this killed eta
440 -- expansion on case (x ==# y) of True -> \s -> ...
441 -- which is bad.  In particular a loop like
442 --      doLoop n = loop 0
443 --     where
444 --         loop i | i == n    = return ()
445 --                | otherwise = bar i >> loop (i+1)
446 -- allocated a closure every time round because it doesn't eta expand.
447 --
448 -- The problem that originally gave rise to the change was
449 --      let x = a +# b *# c in x +# x
450 -- were we don't want to inline x. But primopIsCheap doesn't control
451 -- that (it's exprIsDupable that does) so the problem doesn't occur
452 -- even if primOpIsCheap sometimes says 'True'.
453 \end{code}
454
455
456 %************************************************************************
457 %*                                                                      *
458                PrimOp code size
459 %*                                                                      *
460 %************************************************************************
461
462 primOpCodeSize
463 ~~~~~~~~~~~~~~
464 Gives an indication of the code size of a primop, for the purposes of
465 calculating unfolding sizes; see CoreUnfold.sizeExpr.
466
467 \begin{code}
468 primOpCodeSize :: PrimOp -> Int
469 #include "primop-code-size.hs-incl"
470
471 primOpCodeSizeDefault :: Int
472 primOpCodeSizeDefault = 1
473   -- CoreUnfold.primOpSize already takes into account primOpOutOfLine
474   -- and adds some further costs for the args in that case.
475
476 primOpCodeSizeForeignCall :: Int
477 primOpCodeSizeForeignCall = 4
478 \end{code}
479
480
481 %************************************************************************
482 %*                                                                      *
483                PrimOp types
484 %*                                                                      *
485 %************************************************************************
486
487 \begin{code}
488 primOpType :: PrimOp -> Type  -- you may want to use primOpSig instead
489 primOpType op
490   = case primOpInfo op of
491     Dyadic  _occ ty -> dyadic_fun_ty ty
492     Monadic _occ ty -> monadic_fun_ty ty
493     Compare _occ ty -> compare_fun_ty ty
494
495     GenPrimOp _occ tyvars arg_tys res_ty ->
496         mkForAllTys tyvars (mkFunTys arg_tys res_ty)
497
498 primOpOcc :: PrimOp -> OccName
499 primOpOcc op = case primOpInfo op of
500                Dyadic    occ _     -> occ
501                Monadic   occ _     -> occ
502                Compare   occ _     -> occ
503                GenPrimOp occ _ _ _ -> occ
504
505 -- primOpSig is like primOpType but gives the result split apart:
506 -- (type variables, argument types, result type)
507 -- It also gives arity, strictness info
508
509 primOpSig :: PrimOp -> ([TyVar], [Type], Type, Arity, StrictSig)
510 primOpSig op
511   = (tyvars, arg_tys, res_ty, arity, primOpStrictness op arity)
512   where
513     arity = length arg_tys
514     (tyvars, arg_tys, res_ty)
515       = case (primOpInfo op) of
516         Monadic   _occ ty                    -> ([],     [ty],    ty    )
517         Dyadic    _occ ty                    -> ([],     [ty,ty], ty    )
518         Compare   _occ ty                    -> ([],     [ty,ty], boolTy)
519         GenPrimOp _occ tyvars arg_tys res_ty -> (tyvars, arg_tys, res_ty)
520 \end{code}
521
522 \begin{code}
523 data PrimOpResultInfo
524   = ReturnsPrim     PrimRep
525   | ReturnsAlg      TyCon
526
527 -- Some PrimOps need not return a manifest primitive or algebraic value
528 -- (i.e. they might return a polymorphic value).  These PrimOps *must*
529 -- be out of line, or the code generator won't work.
530
531 getPrimOpResultInfo :: PrimOp -> PrimOpResultInfo
532 getPrimOpResultInfo op
533   = case (primOpInfo op) of
534       Dyadic  _ ty                        -> ReturnsPrim (typePrimRep ty)
535       Monadic _ ty                        -> ReturnsPrim (typePrimRep ty)
536       Compare _ _                         -> ReturnsAlg boolTyCon
537       GenPrimOp _ _ _ ty | isPrimTyCon tc -> ReturnsPrim (tyConPrimRep tc)
538                          | otherwise      -> ReturnsAlg tc
539                          where
540                            tc = tyConAppTyCon ty
541                         -- All primops return a tycon-app result
542                         -- The tycon can be an unboxed tuple, though, which
543                         -- gives rise to a ReturnAlg
544 \end{code}
545
546 We do not currently make use of whether primops are commutable.
547
548 We used to try to move constants to the right hand side for strength
549 reduction.
550
551 \begin{code}
552 {-
553 commutableOp :: PrimOp -> Bool
554 #include "primop-commutable.hs-incl"
555 -}
556 \end{code}
557
558 Utils:
559 \begin{code}
560 dyadic_fun_ty, monadic_fun_ty, compare_fun_ty :: Type -> Type
561 dyadic_fun_ty  ty = mkFunTys [ty, ty] ty
562 monadic_fun_ty ty = mkFunTy  ty ty
563 compare_fun_ty ty = mkFunTys [ty, ty] boolTy
564 \end{code}
565
566 Output stuff:
567 \begin{code}
568 pprPrimOp  :: PrimOp -> SDoc
569 pprPrimOp other_op = pprOccName (primOpOcc other_op)
570 \end{code}
571
572
573 %************************************************************************
574 %*                                                                      *
575 \subsubsection[PrimCall]{User-imported primitive calls}
576 %*                                                                      *
577 %************************************************************************
578
579 \begin{code}
580 data PrimCall = PrimCall CLabelString PackageId
581
582 instance Outputable PrimCall where
583   ppr (PrimCall lbl pkgId)
584         = text "__primcall" <+> ppr pkgId <+> ppr lbl
585
586 \end{code}