PrimOp.lhs 20.4 KB
Newer Older
1 2 3 4 5 6 7
%
% (c) The GRASP/AQUA Project, Glasgow University, 1992-1998
%
\section[PrimOp]{Primitive operations (machine-level)}

\begin{code}
module PrimOp (
8 9 10
        PrimOp(..), allThePrimOps,
        primOpType, primOpSig,
        primOpTag, maxPrimOpTag, primOpOcc,
11

12
        tagToEnumKey,
13

14
        primOpOutOfLine, primOpCodeSize,
15
        primOpOkForSpeculation, primOpOkForSideEffects,
16
        primOpIsCheap, primOpFixity,
17

18
        getPrimOpResultInfo,  PrimOpResultInfo(..),
19 20

        PrimCall(..)
21 22 23 24 25 26 27
    ) where

#include "HsVersions.h"

import TysPrim
import TysWiredIn

28
import Demand
29 30 31 32 33
import Var              ( TyVar )
import OccName          ( OccName, pprOccName, mkVarOccFS )
import TyCon            ( TyCon, isPrimTyCon, tyConPrimRep, PrimRep(..) )
import Type             ( Type, mkForAllTys, mkFunTy, mkFunTys, tyConAppTyCon,
                          typePrimRep )
34
import BasicTypes       ( Arity, Fixity(..), FixityDirection(..), TupleSort(..) )
35 36
import ForeignCall      ( CLabelString )
import Unique           ( Unique, mkPrimOpIdUnique )
37
import Outputable
38
import FastTypes
39
import FastString
40
import Module           ( PackageId )
41 42 43
\end{code}

%************************************************************************
44
%*                                                                      *
45
\subsection[PrimOp-datatype]{Datatype for @PrimOp@ (an enumeration)}
46
%*                                                                      *
47 48 49 50 51
%************************************************************************

These are in \tr{state-interface.verb} order.

\begin{code}
52

53
-- supplies:
54
-- data PrimOp = ...
55
#include "primop-data-decl.hs-incl"
56 57 58 59 60
\end{code}

Used for the Ord instance

\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 74 75 76
    op1 <  op2 =  tagOf_PrimOp op1 <# tagOf_PrimOp op2
    op1 <= op2 =  tagOf_PrimOp op1 <=# tagOf_PrimOp op2
    op1 >= op2 =  tagOf_PrimOp op1 >=# tagOf_PrimOp op2
    op1 >  op2 =  tagOf_PrimOp op1 ># tagOf_PrimOp op2
77
    op1 `compare` op2 | op1 < op2  = LT
78 79
                      | op1 == op2 = EQ
                      | otherwise  = GT
80 81 82 83 84 85

instance Outputable PrimOp where
    ppr op = pprPrimOp op
\end{code}

An @Enum@-derived list would be better; meanwhile... (ToDo)
86

87
\begin{code}
88 89
allThePrimOps :: [PrimOp]
allThePrimOps =
90
#include "primop-list.hs-incl"
91 92
\end{code}

93 94 95 96 97 98 99
\begin{code}
tagToEnumKey :: Unique
tagToEnumKey = mkPrimOpIdUnique (primOpTag TagToEnumOp)
\end{code}



100
%************************************************************************
101
%*                                                                      *
102
\subsection[PrimOp-info]{The essential info about each @PrimOp@}
103
%*                                                                      *
104 105 106 107 108 109 110 111 112 113 114 115 116
%************************************************************************

The @String@ in the @PrimOpInfos@ is the ``base name'' by which the user may
refer to the primitive operation.  The conventional \tr{#}-for-
unboxed ops is added on later.

The reason for the funny characters in the names is so we do not
interfere with the programmer's Haskell name spaces.

We use @PrimKinds@ for the ``type'' information, because they're
(slightly) more convenient to use than @TyCons@.
\begin{code}
data PrimOpInfo
117 118 119 120 121 122 123 124 125 126 127
  = Dyadic      OccName         -- string :: T -> T -> T
                Type
  | Monadic     OccName         -- string :: T -> T
                Type
  | Compare     OccName         -- string :: T -> T -> Bool
                Type

  | GenPrimOp   OccName         -- string :: \/a1..an . T1 -> .. -> Tk -> T
                [TyVar]
                [Type]
                Type
128

129
mkDyadic, mkMonadic, mkCompare :: FastString -> Type -> PrimOpInfo
130 131 132
mkDyadic str  ty = Dyadic  (mkVarOccFS str) ty
mkMonadic str ty = Monadic (mkVarOccFS str) ty
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 137 138
\end{code}

%************************************************************************
139
%*                                                                      *
140
\subsubsection{Strictness}
141
%*                                                                      *
142 143 144 145 146
%************************************************************************

Not all primops are strict!

\begin{code}
147
primOpStrictness :: PrimOp -> Arity -> StrictSig
148 149 150
        -- See Demand.StrictnessInfo for discussion of what the results
        -- The arity should be the arity of the primop; that's why
        -- this function isn't exported.
151
#include "primop-strictness.hs-incl"
152 153
\end{code}

154 155 156 157 158 159 160 161 162 163 164
%************************************************************************
%*                                                                      *
\subsubsection{Fixity}
%*                                                                      *
%************************************************************************

\begin{code}
primOpFixity :: PrimOp -> Maybe Fixity
#include "primop-fixity.hs-incl"
\end{code}

165
%************************************************************************
166
%*                                                                      *
167
\subsubsection[PrimOp-comparison]{PrimOpInfo basic comparison ops}
168
%*                                                                      *
169 170 171 172 173 174 175
%************************************************************************

@primOpInfo@ gives all essential information (from which everything
else, notably a type, can be constructed) for each @PrimOp@.

\begin{code}
primOpInfo :: PrimOp -> PrimOpInfo
176
#include "primop-primop-info.hs-incl"
177 178
\end{code}

179
Here are a load of comments from the old primOp info:
180 181 182 183 184 185 186 187 188 189 190 191

A @Word#@ is an unsigned @Int#@.

@decodeFloat#@ is given w/ Integer-stuff (it's similar).

@decodeDouble#@ is given w/ Integer-stuff (it's similar).

Decoding of floating-point numbers is sorta Integer-related.  Encoding
is done with plain ccalls now (see PrelNumExtra.lhs).

A @Weak@ Pointer is created by the @mkWeak#@ primitive:

192 193
        mkWeak# :: k -> v -> f -> State# RealWorld
                        -> (# State# RealWorld, Weak# v #)
194 195 196

In practice, you'll use the higher-level

197 198
        data Weak v = Weak# v
        mkWeak :: k -> v -> IO () -> IO (Weak v)
199 200 201 202 203

The following operation dereferences a weak pointer.  The weak pointer
may have been finalized, so the operation returns a result code which
must be inspected before looking at the dereferenced value.

204 205
        deRefWeak# :: Weak# v -> State# RealWorld ->
                        (# State# RealWorld, v, Int# #)
206 207 208 209 210

Only look at v if the Int# returned is /= 0 !!

The higher-level op is

211
        deRefWeak :: Weak v -> IO (Maybe v)
212 213

Weak pointers can be finalized early by using the finalize# operation:
214 215 216

        finalizeWeak# :: Weak# v -> State# RealWorld ->
                           (# State# RealWorld, Int#, IO () #)
217 218 219

The Int# returned is either

220 221
        0 if the weak pointer has already been finalized, or it has no
          finalizer (the third component is then invalid).
222

223 224
        1 if the weak pointer is still alive, with the finalizer returned
          as the third component.
225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261

A {\em stable name/pointer} is an index into a table of stable name
entries.  Since the garbage collector is told about stable pointers,
it is safe to pass a stable pointer to external systems such as C
routines.

\begin{verbatim}
makeStablePtr#  :: a -> State# RealWorld -> (# State# RealWorld, StablePtr# a #)
freeStablePtr   :: StablePtr# a -> State# RealWorld -> State# RealWorld
deRefStablePtr# :: StablePtr# a -> State# RealWorld -> (# State# RealWorld, a #)
eqStablePtr#    :: StablePtr# a -> StablePtr# a -> Int#
\end{verbatim}

It may seem a bit surprising that @makeStablePtr#@ is a @IO@
operation since it doesn't (directly) involve IO operations.  The
reason is that if some optimisation pass decided to duplicate calls to
@makeStablePtr#@ and we only pass one of the stable pointers over, a
massive space leak can result.  Putting it into the IO monad
prevents this.  (Another reason for putting them in a monad is to
ensure correct sequencing wrt the side-effecting @freeStablePtr@
operation.)

An important property of stable pointers is that if you call
makeStablePtr# twice on the same object you get the same stable
pointer back.

Note that we can implement @freeStablePtr#@ using @_ccall_@ (and,
besides, it's not likely to be used from Haskell) so it's not a
primop.

Question: Why @RealWorld@ - won't any instance of @_ST@ do the job? [ADR]

Stable Names
~~~~~~~~~~~~

A stable name is like a stable pointer, but with three important differences:

262 263 264
        (a) You can't deRef one to get back to the original object.
        (b) You can convert one to an Int.
        (c) You don't need to 'freeStableName'
265 266 267 268 269 270

The existence of a stable name doesn't guarantee to keep the object it
points to alive (unlike a stable pointer), hence (a).

Invariants:

271 272 273 274 275
        (a) makeStableName always returns the same value for a given
            object (same as stable pointers).

        (b) if two stable names are equal, it implies that the objects
            from which they were created were the same.
276

277 278
        (c) stableNameToInt always returns the same Int for a given
            stable name.
279 280 281 282 283 284 285 286 287 288


-- HWL: The first 4 Int# in all par... annotations denote:
--   name, granularity info, size of result, degree of parallelism
--      Same  structure as _seq_ i.e. returns Int#
-- KSW: v, the second arg in parAt# and parAtForNow#, is used only to determine
--   `the processor containing the expression v'; it is not evaluated

These primops are pretty wierd.

289 290
        dataToTag# :: a -> Int    (arg must be an evaluated data type)
        tagToEnum# :: Int -> a    (result type must be an enumerated type)
291 292 293 294 295

The constraints aren't currently checked by the front end, but the
code generator will fall over if they aren't satisfied.

%************************************************************************
296
%*                                                                      *
297
            Which PrimOps are out-of-line
298
%*                                                                      *
299 300 301 302 303
%************************************************************************

Some PrimOps need to be called out-of-line because they either need to
perform a heap check or they block.

apt's avatar
apt committed
304

305
\begin{code}
apt's avatar
apt committed
306
primOpOutOfLine :: PrimOp -> Bool
307
#include "primop-out-of-line.hs-incl"
308 309
\end{code}

310

311 312 313 314 315 316 317 318
%************************************************************************
%*                                                                      *
            Failure and side effects
%*                                                                      *
%************************************************************************

Note [PrimOp can_fail and has_side_effects]
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390
Both can_fail and has_side_effects mean that the primop has
some effect that is not captured entirely by its result value.

   ----------  has_side_effects ---------------------
   Has some imperative side effect, perhaps on the world (I/O),
   or perhaps on some mutable data structure (writeIORef).
   Generally speaking all such primops have a type like
      State -> input -> (State, output)
   so the state token guarantees ordering, and also ensures
   that the primop is executed even if 'output' is discarded.

   ----------  can_fail ----------------------------
   Can fail with a seg-fault or divide-by-zero error on some elements
   of its input domain.  Main examples:
      division (fails on zero demoninator
      array indexing (fails if the index is out of bounds)
   However (ASSUMPTION), these can_fail primops are ALWAYS surrounded
   with a test that checks for the bad cases.  

Consequences:

* You can discard a can_fail primop, or float it _inwards_.
  But you cannot float it _outwards_, lest you escape the
  dynamic scope of the test.  Example:
      case d ># 0# of
        True  -> case x /# d of r -> r +# 1
        False -> 0
  Here we must not float the case outwards to give
      case x/# d of r ->
      case d ># 0# of
        True  -> r +# 1
        False -> 0

* I believe that exactly the same rules apply to a has_side_effects
  primop; you can discard it (remember, the state token will keep
  it alive if necessary), or float it in, but not float it out.

  Example of the latter
       if blah then let! s1 = writeMutVar s0 v True in s1
               else s0
  Notice that s0 is mentioned in both branches of the 'if', but 
  only one of these two will actually be consumed.  But if we
  float out to
      let! s1 = writeMutVar s0 v True
      in if blah then s1 else s0
  the writeMutVar will be performed in both branches, which is
  utterly wrong.

* You cannot duplicate a has_side_effect primop.  You might wonder
  how this can occur given the state token threading, but just look
  at Control.Monad.ST.Lazy.Imp.strictToLazy!  We get something like
  this
        p = case readMutVar# s v of
              (# s', r #) -> (S# s', r)
        s' = case p of (s', r) -> s'
        r  = case p of (s', r) -> r

  (All these bindings are boxed.)  If we inline p at its two call
  sites, we get a catastrophe: because the read is performed once when
  s' is demanded, and once when 'r' is demanded, which may be much 
  later.  Utterly wrong.  Trac #3207 is real example of this happening.

  However, it's fine to duplicate a can_fail primop.  That is
  the difference between can_fail and has_side_effects.

            can_fail     has_side_effects
Discard        YES           YES
Float in       YES           YES
Float out      NO            NO
Duplicate      YES           NO

How do we achieve these effects?
391

392 393 394 395 396 397
Note [primOpOkForSpeculation]
  * The "no-float-out" thing is achieved by ensuring that we never
    let-bind a can_fail or has_side_effects primop.  The RHS of a
    let-binding (which can float in and out freely) satisfies
    exprOkForSpeculation.  And exprOkForSpeculation is false of
    can_fail and no_side_effect.
398

399 400 401
  * So can_fail and no_side_effect primops will appear only as the
    scrutinees of cases, and that's why the FloatIn pass is capable
    of floating case bindings inwards.
402

403 404
  * The no-duplicate thing is done via primOpIsCheap, by making
    has_side_effects things (very very very) not-cheap!
405

406 407

\begin{code}
408 409 410 411 412 413
primOpHasSideEffects :: PrimOp -> Bool
#include "primop-has-side-effects.hs-incl"

primOpCanFail :: PrimOp -> Bool
#include "primop-can-fail.hs-incl"

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 421 422

primOpOkForSideEffects :: PrimOp -> Bool
primOpOkForSideEffects op
  = not (primOpHasSideEffects op)
423
\end{code}
424

425

426 427 428 429 430 431 432 433 434 435 436
Note [primOpIsCheap]
~~~~~~~~~~~~~~~~~~~~
@primOpIsCheap@, as used in \tr{SimplUtils.lhs}.  For now (HACK
WARNING), we just borrow some other predicates for a
what-should-be-good-enough test.  "Cheap" means willing to call it more
than once, and/or push it inside a lambda.  The latter could change the
behaviour of 'seq' for primops that can fail, so we don't treat them as cheap.

\begin{code}
primOpIsCheap :: PrimOp -> Bool
primOpIsCheap op = primOpOkForSpeculation op
437 438
-- In March 2001, we changed this to
--      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 444 445 446
--     where
--         loop i | i == n    = return ()
--                | otherwise = bar i >> loop (i+1)
-- 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 451 452
-- were we don't want to inline x. But primopIsCheap doesn't control
-- that (it's exprIsDupable that does) so the problem doesn't occur
-- even if primOpIsCheap sometimes says 'True'.
453 454
\end{code}

455 456 457 458 459 460 461

%************************************************************************
%*                                                                      *
               PrimOp code size
%*                                                                      *
%************************************************************************

462 463 464 465
primOpCodeSize
~~~~~~~~~~~~~~
Gives an indication of the code size of a primop, for the purposes of
calculating unfolding sizes; see CoreUnfold.sizeExpr.
466 467

\begin{code}
468 469 470 471 472 473 474
primOpCodeSize :: PrimOp -> Int
#include "primop-code-size.hs-incl"

primOpCodeSizeDefault :: Int
primOpCodeSizeDefault = 1
  -- CoreUnfold.primOpSize already takes into account primOpOutOfLine
  -- and adds some further costs for the args in that case.
475

476 477 478
primOpCodeSizeForeignCall :: Int
primOpCodeSizeForeignCall = 4
\end{code}
479

480

481 482 483 484 485
%************************************************************************
%*                                                                      *
               PrimOp types
%*                                                                      *
%************************************************************************
486 487 488 489

\begin{code}
primOpType :: PrimOp -> Type  -- you may want to use primOpSig instead
primOpType op
Ian Lynagh's avatar
Ian Lynagh committed
490 491 492 493
  = case primOpInfo op of
    Dyadic  _occ ty -> dyadic_fun_ty ty
    Monadic _occ ty -> monadic_fun_ty ty
    Compare _occ ty -> compare_fun_ty ty
494

495
    GenPrimOp _occ tyvars arg_tys res_ty ->
Ian Lynagh's avatar
Ian Lynagh committed
496
        mkForAllTys tyvars (mkFunTys arg_tys res_ty)
497 498

primOpOcc :: PrimOp -> OccName
Ian Lynagh's avatar
Ian Lynagh committed
499 500 501 502 503
primOpOcc op = case primOpInfo op of
               Dyadic    occ _     -> occ
               Monadic   occ _     -> occ
               Compare   occ _     -> occ
               GenPrimOp occ _ _ _ -> occ
504 505 506

-- primOpSig is like primOpType but gives the result split apart:
-- (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 513 514 515
  where
    arity = length arg_tys
    (tyvars, arg_tys, res_ty)
      = case (primOpInfo op) of
Ian Lynagh's avatar
Ian Lynagh committed
516 517 518 519
        Monadic   _occ ty                    -> ([],     [ty],    ty    )
        Dyadic    _occ ty                    -> ([],     [ty,ty], ty    )
        Compare   _occ ty                    -> ([],     [ty,ty], boolTy)
        GenPrimOp _occ tyvars arg_tys res_ty -> (tyvars, arg_tys, res_ty)
520 521 522 523
\end{code}

\begin{code}
data PrimOpResultInfo
524 525
  = ReturnsPrim     PrimRep
  | ReturnsAlg      TyCon
526 527 528 529 530 531 532 533

-- Some PrimOps need not return a manifest primitive or algebraic value
-- (i.e. they might return a polymorphic value).  These PrimOps *must*
-- be out of line, or the code generator won't work.

getPrimOpResultInfo :: PrimOp -> PrimOpResultInfo
getPrimOpResultInfo op
  = case (primOpInfo op) of
534 535 536
      Dyadic  _ ty                        -> ReturnsPrim (typePrimRep ty)
      Monadic _ ty                        -> ReturnsPrim (typePrimRep ty)
      Compare _ _                         -> ReturnsAlg boolTyCon
537
      GenPrimOp _ _ _ ty | isPrimTyCon tc -> ReturnsPrim (tyConPrimRep tc)
538 539 540 541 542 543
                         | otherwise      -> ReturnsAlg tc
                         where
                           tc = tyConAppTyCon ty
                        -- All primops return a tycon-app result
                        -- The tycon can be an unboxed tuple, though, which
                        -- gives rise to a ReturnAlg
544 545
\end{code}

546 547 548 549
We do not currently make use of whether primops are commutable.

We used to try to move constants to the right hand side for strength
reduction.
550 551

\begin{code}
552
{-
553
commutableOp :: PrimOp -> Bool
554
#include "primop-commutable.hs-incl"
555
-}
556 557 558 559
\end{code}

Utils:
\begin{code}
560
dyadic_fun_ty, monadic_fun_ty, compare_fun_ty :: Type -> Type
561 562 563 564 565 566 567 568
dyadic_fun_ty  ty = mkFunTys [ty, ty] ty
monadic_fun_ty ty = mkFunTy  ty ty
compare_fun_ty ty = mkFunTys [ty, ty] boolTy
\end{code}

Output stuff:
\begin{code}
pprPrimOp  :: PrimOp -> SDoc
569
pprPrimOp other_op = pprOccName (primOpOcc other_op)
570 571
\end{code}

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 584
  ppr (PrimCall lbl pkgId)
        = text "__primcall" <+> ppr pkgId <+> ppr lbl
585 586

\end{code}