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