[project @ 1996-04-05 08:26:04 by partain]
[ghc-hetmet.git] / ghc / compiler / coreSyn / CoreSyn.lhs
1 %
2 % (c) The GRASP/AQUA Project, Glasgow University, 1992-1996
3 %
4 \section[CoreSyn]{A data type for the Haskell compiler midsection}
5
6 \begin{code}
7 #include "HsVersions.h"
8
9 module CoreSyn (
10         GenCoreBinding(..), GenCoreExpr(..),
11         GenCoreArg(..), GenCoreBinder(..), GenCoreCaseAlts(..),
12         GenCoreCaseDefault(..),
13
14         bindersOf, pairsFromCoreBinds, rhssOfBind,
15
16         mkGenApp, mkValApp, mkTyApp, mkUseApp,
17         mkApp, mkCon, mkPrim,
18         mkValLam, mkTyLam, mkUseLam,
19         mkLam,
20         collectBinders, isValBinder, notValBinder,
21         
22         collectArgs, isValArg, notValArg, numValArgs,
23
24         mkCoLetAny, mkCoLetNoUnboxed, mkCoLetUnboxedToCase,
25         mkCoLetsAny, mkCoLetsNoUnboxed, mkCoLetsUnboxedToCase,
26         mkCoLetrecAny, mkCoLetrecNoUnboxed,
27
28         rhssOfAlts,
29
30         -- Common type instantiation...
31         CoreBinding(..),
32         CoreExpr(..),
33         CoreBinder(..),
34         CoreArg(..),
35         CoreCaseAlts(..),
36         CoreCaseDefault(..),
37
38         -- And not-so-common type instantiations...
39         TaggedCoreBinding(..),
40         TaggedCoreExpr(..),
41         TaggedCoreBinder(..),
42         TaggedCoreArg(..),
43         TaggedCoreCaseAlts(..),
44         TaggedCoreCaseDefault(..),
45
46         SimplifiableCoreBinding(..),
47         SimplifiableCoreExpr(..),
48         SimplifiableCoreBinder(..),
49         SimplifiableCoreArg(..),
50         SimplifiableCoreCaseAlts(..),
51         SimplifiableCoreCaseDefault(..)
52
53         -- and to make the interface self-sufficient ...
54
55     ) where
56
57 import Ubiq{-uitous-}
58
59 import CostCentre       ( showCostCentre, CostCentre )
60 import Id               ( idType, GenId{-instance Eq-} )
61 import Type             ( isUnboxedType )
62 import Usage            ( UVar(..) )
63 import Util             ( panic, assertPanic )
64 \end{code}
65
66 %************************************************************************
67 %*                                                                      *
68 \subsection[CoreTopBinding_and_CoreBinding]{@CoreTopBinding@ and @GenCoreBinding@}
69 %*                                                                      *
70 %************************************************************************
71
72 Core programs, bindings, expressions, etc., are parameterised with
73 respect to the information kept about binding and bound occurrences of
74 variables, called {\em binders} and {\em val_occ tyvar uvars}, respectively.  [I
75 don't really like the pair of names; I prefer {\em binder} and {\em
76 bounder}.  Or {\em binder} and {\em var}.]
77
78 A @GenCoreBinding@ is either a single non-recursive binding of a
79 ``binder'' to an expression, or a mutually-recursive blob of same.
80 \begin{code}
81 data GenCoreBinding val_bdr val_occ tyvar uvar
82   = NonRec      val_bdr (GenCoreExpr val_bdr val_occ tyvar uvar)
83   | Rec         [(val_bdr, GenCoreExpr val_bdr val_occ tyvar uvar)]
84 \end{code}
85
86 \begin{code}
87 bindersOf :: GenCoreBinding val_bdr val_occ tyvar uvar -> [val_bdr]
88
89 pairsFromCoreBinds ::
90   [GenCoreBinding val_bdr val_occ tyvar uvar] ->
91   [(val_bdr, GenCoreExpr val_bdr val_occ tyvar uvar)]
92
93 rhssOfBind :: GenCoreBinding val_bdr val_occ tyvar uvar -> [GenCoreExpr val_bdr val_occ tyvar uvar]
94
95 bindersOf (NonRec binder _) = [binder]
96 bindersOf (Rec pairs)       = [binder | (binder, _) <- pairs]
97
98 pairsFromCoreBinds []                  = []
99 pairsFromCoreBinds ((NonRec b e) : bs) = (b,e) :  pairsFromCoreBinds bs
100 pairsFromCoreBinds ((Rec  pairs) : bs) = pairs ++ pairsFromCoreBinds bs
101
102 rhssOfBind (NonRec _ rhs) = [rhs]
103 rhssOfBind (Rec pairs)    = [rhs | (_,rhs) <- pairs]
104 \end{code}
105
106 %************************************************************************
107 %*                                                                      *
108 \subsection[GenCoreExpr]{Core expressions: @GenCoreExpr@}
109 %*                                                                      *
110 %************************************************************************
111
112 @GenCoreExpr@ is the heart of the ``core'' data types; it is
113 (more-or-less) boiled-down second-order polymorphic lambda calculus.
114 For types in the core world, we just keep using @Types@.
115 \begin{code}
116 data GenCoreExpr val_bdr val_occ tyvar uvar
117      = Var    val_occ
118      | Lit    Literal   -- literal constants
119 \end{code}
120
121 @Cons@ and @Prims@ are saturated constructor and primitive-op
122 applications (see the comment).  Note: @Con@s are only set up by the
123 simplifier (and by the desugarer when it knows what it's doing).  The
124 desugarer sets up constructors as applications of global @Vars@s.
125
126 \begin{code}
127      | Con      Id [GenCoreArg val_occ tyvar uvar]
128                 -- Saturated constructor application:
129                 -- The constructor is a function of the form:
130                 --      /\ a1 -> ... /\ am -> \ b1 -> ... \ bn ->
131                 -- <expr> where "/\" is a type lambda and "\" the
132                 -- regular kind; there will be "m" Types and
133                 -- "n" bindees in the Con args.
134
135      | Prim     PrimOp [GenCoreArg val_occ tyvar uvar]
136                 -- saturated primitive operation;
137                 -- comment on Cons applies here, too.
138 \end{code}
139
140 Ye olde abstraction and application operators.
141 \begin{code}
142      | Lam      (GenCoreBinder val_bdr tyvar uvar)
143                 (GenCoreExpr   val_bdr val_occ tyvar uvar)
144
145      | App      (GenCoreExpr val_bdr val_occ tyvar uvar)
146                 (GenCoreArg  val_occ tyvar uvar)
147 \end{code}
148
149 Case expressions (\tr{case <expr> of <List of alternatives>}): there
150 are really two flavours masquerading here---those for scrutinising
151 {\em algebraic} types and those for {\em primitive} types.  Please see
152 under @GenCoreCaseAlts@.
153 \begin{code}
154      | Case     (GenCoreExpr val_bdr val_occ tyvar uvar)
155                 (GenCoreCaseAlts val_bdr val_occ tyvar uvar)
156 \end{code}
157
158 A Core case expression \tr{case e of v -> ...} implies evaluation of
159 \tr{e}; it is not equivalent to \tr{let v = in ...} (as with a Haskell
160 \tr{case}).
161
162 Non-recursive @Lets@ only have one binding; having more than one
163 doesn't buy you much, and it is an easy way to mess up variable
164 scoping.
165 \begin{code}
166      | Let      (GenCoreBinding val_bdr val_occ tyvar uvar)
167                 (GenCoreExpr val_bdr val_occ tyvar uvar)
168                 -- both recursive and non-.
169                 -- The "GenCoreBinding" records that information
170 \end{code}
171
172 For cost centre scc expressions we introduce a new core construct
173 @SCC@ so transforming passes have to deal with it explicitly. The
174 alternative of using a new PrimativeOp may result in a bad
175 transformations of which we are unaware.
176 \begin{code}
177      | SCC      CostCentre                                  -- label of scc
178                 (GenCoreExpr val_bdr val_occ tyvar uvar)    -- scc expression
179 \end{code}
180
181
182 %************************************************************************
183 %*                                                                      *
184 \subsection{Core-constructing functions with checking}
185 %*                                                                      *
186 %************************************************************************
187
188 When making @Lets@, we may want to take evasive action if the thing
189 being bound has unboxed type. We have different variants ...
190
191 @mkCoLet(s|rec)Any@             let-binds any binding, regardless of type
192 @mkCoLet(s|rec)NoUnboxed@       prohibits unboxed bindings
193 @mkCoLet(s)UnboxedToCase@       converts an unboxed binding to a case
194                                 (unboxed bindings in a letrec are still prohibited)
195
196 \begin{code}
197 mkCoLetAny :: GenCoreBinding Id Id tyvar uvar
198            -> GenCoreExpr    Id Id tyvar uvar
199            -> GenCoreExpr    Id Id tyvar uvar
200 mkCoLetsAny :: [GenCoreBinding Id Id tyvar uvar] ->
201                 GenCoreExpr Id Id tyvar uvar ->
202                 GenCoreExpr Id Id tyvar uvar
203
204 mkCoLetrecAny :: [(val_bdr, GenCoreExpr val_bdr val_occ tyvar uvar)]
205               -> GenCoreExpr val_bdr val_occ tyvar uvar
206               -> GenCoreExpr val_bdr val_occ tyvar uvar
207
208 mkCoLetrecAny []    body = body
209 mkCoLetrecAny binds body = Let (Rec binds) body
210
211 mkCoLetsAny []    expr = expr
212 mkCoLetsAny binds expr = foldr mkCoLetAny expr binds
213
214 mkCoLetAny bind@(Rec binds) body = mkCoLetrecAny binds body
215 mkCoLetAny bind@(NonRec binder rhs) body
216   = case body of
217       Var binder2 | binder == binder2
218          -> rhs   -- hey, I have the rhs
219       other
220          -> Let bind body
221 \end{code}
222
223 \begin{code}
224 --mkCoLetNoUnboxed ::
225 --  GenCoreBinding val_bdr val_occ tyvar uvar ->
226 --  GenCoreExpr val_bdr val_occ tyvar uvar ->
227 --  GenCoreExpr val_bdr val_occ tyvar uvar
228
229 mkCoLetNoUnboxed bind@(Rec binds) body
230   = mkCoLetrecNoUnboxed binds body
231 mkCoLetNoUnboxed bind@(NonRec binder rhs) body
232   = --ASSERT (not (isUnboxedType (idType binder)))
233     case body of
234       Var binder2 | binder == binder2
235          -> rhs   -- hey, I have the rhs
236       other
237          -> Let bind body
238
239 mkCoLetsNoUnboxed []    expr = expr
240 mkCoLetsNoUnboxed binds expr = foldr mkCoLetNoUnboxed expr binds
241
242 --mkCoLetrecNoUnboxed :: [(Id, CoreExpr)]       -- bindings
243 --                  -> CoreExpr         -- body
244 --                  -> CoreExpr                 -- result
245
246 mkCoLetrecNoUnboxed []    body = body
247 mkCoLetrecNoUnboxed binds body
248   = ASSERT (all is_boxed_bind binds)
249     Let (Rec binds) body
250   where
251     is_boxed_bind (binder, rhs)
252       = (not . isUnboxedType . idType) binder
253 \end{code}
254
255 \begin{code}
256 --mkCoLetUnboxedToCase ::
257 --  GenCoreBinding val_bdr val_occ tyvar uvar ->
258 --  GenCoreExpr val_bdr val_occ tyvar uvar ->
259 --  GenCoreExpr val_bdr val_occ tyvar uvar
260
261 mkCoLetUnboxedToCase bind@(Rec binds) body
262   = mkCoLetrecNoUnboxed binds body
263 mkCoLetUnboxedToCase bind@(NonRec binder rhs) body
264   = case body of
265       Var binder2 | binder == binder2
266          -> rhs   -- hey, I have the rhs
267       other
268          -> if (not (isUnboxedType (idType binder))) then
269                 Let bind body            -- boxed...
270             else
271                 Case rhs                  -- unboxed...
272                   (PrimAlts []
273                     (BindDefault binder body))
274
275 mkCoLetsUnboxedToCase []    expr = expr
276 mkCoLetsUnboxedToCase binds expr = foldr mkCoLetUnboxedToCase expr binds
277 \end{code}
278
279 %************************************************************************
280 %*                                                                      *
281 \subsection{Case alternatives in @GenCoreExpr@}
282 %*                                                                      *
283 %************************************************************************
284
285 We have different kinds of @case@s, the differences being reflected in
286 the kinds of alternatives a case has.  We maintain a distinction
287 between cases for scrutinising algebraic datatypes, as opposed to
288 primitive types.  In both cases, we carry around a @TyCon@, as a
289 handle with which we can get info about the case (e.g., total number
290 of data constructors for this type).
291
292 For example:
293 \begin{verbatim}
294 let# x=e in b
295 \end{verbatim}
296 becomes
297 \begin{verbatim}
298 Case e [ BindDefaultAlt x -> b ]
299 \end{verbatim}
300
301 \begin{code}
302 data GenCoreCaseAlts val_bdr val_occ tyvar uvar
303   = AlgAlts     [(Id,                           -- alts: data constructor,
304                   [val_bdr],                    -- constructor's parameters,
305                   GenCoreExpr val_bdr val_occ tyvar uvar)]      -- rhs.
306                 (GenCoreCaseDefault val_bdr val_occ tyvar uvar)
307
308   | PrimAlts    [(Literal,                      -- alts: unboxed literal,
309                   GenCoreExpr val_bdr val_occ tyvar uvar)]      -- rhs.
310                 (GenCoreCaseDefault val_bdr val_occ tyvar uvar)
311
312 -- obvious things: if there are no alts in the list, then the default
313 -- can't be NoDefault.
314
315 data GenCoreCaseDefault val_bdr val_occ tyvar uvar
316   = NoDefault                                   -- small con family: all
317                                                 -- constructor accounted for
318   | BindDefault val_bdr                         -- form: var -> expr;
319                 (GenCoreExpr val_bdr val_occ tyvar uvar)        -- "val_bdr" may or may not
320                                                 -- be used in RHS.
321 \end{code}
322
323 \begin{code}
324 rhssOfAlts (AlgAlts alts deflt)  = rhssOfDeflt deflt ++ [rhs | (_,_,rhs) <- alts]
325 rhssOfAlts (PrimAlts alts deflt) = rhssOfDeflt deflt ++ [rhs | (_,rhs)   <- alts]
326
327 rhssOfDeflt NoDefault           = []
328 rhssOfDeflt (BindDefault _ rhs) = [rhs]
329 \end{code}
330
331 %************************************************************************
332 %*                                                                      *
333 \subsection{Core binders}
334 %*                                                                      *
335 %************************************************************************
336
337 \begin{code}
338 data GenCoreBinder val_bdr tyvar uvar
339   = ValBinder   val_bdr
340   | TyBinder    tyvar
341   | UsageBinder uvar
342
343 isValBinder (ValBinder _) = True
344 isValBinder _             = False
345
346 notValBinder = not . isValBinder
347 \end{code}
348
349 Clump Lams together if possible.
350
351 \begin{code}
352 mkValLam :: [val_bdr]
353          -> GenCoreExpr val_bdr val_occ tyvar uvar
354          -> GenCoreExpr val_bdr val_occ tyvar uvar
355 mkTyLam  :: [tyvar]
356          -> GenCoreExpr val_bdr val_occ tyvar uvar
357          -> GenCoreExpr val_bdr val_occ tyvar uvar
358 mkUseLam :: [uvar]
359          -> GenCoreExpr val_bdr val_occ tyvar uvar
360          -> GenCoreExpr val_bdr val_occ tyvar uvar
361
362 mkValLam binders body = foldr (Lam . ValBinder)   body binders
363 mkTyLam  binders body = foldr (Lam . TyBinder)    body binders
364 mkUseLam binders body = foldr (Lam . UsageBinder) body binders
365
366 mkLam :: [tyvar] -> [val_bdr] -- ToDo: could add a [uvar] arg...
367          -> GenCoreExpr val_bdr val_occ tyvar uvar
368          -> GenCoreExpr val_bdr val_occ tyvar uvar
369
370 mkLam tyvars valvars body
371   = mkTyLam tyvars (mkValLam valvars body)
372 \end{code}
373
374 We often want to strip off leading lambdas before getting down to
375 business.  @collectBinders@ is your friend.
376
377 We expect (by convention) usage-, type-, and value- lambdas in that
378 order.
379
380 \begin{code}
381 collectBinders ::
382   GenCoreExpr val_bdr val_occ tyvar uvar ->
383   ([uvar], [tyvar], [val_bdr], GenCoreExpr val_bdr val_occ tyvar uvar)
384
385 collectBinders expr
386   = usages expr []
387   where
388     usages (Lam (UsageBinder u) body) uacc = usages body (u:uacc)
389     usages other uacc
390       = case (tyvars other []) of { (tacc, vacc, expr) ->
391         (reverse uacc, tacc, vacc, expr) }
392
393     tyvars (Lam (TyBinder t)    body) tacc = tyvars body (t:tacc)
394     tyvars other tacc
395       = ASSERT(not (usage_lambda other))
396         case (valvars other []) of { (vacc, expr) ->
397         (reverse tacc, vacc, expr) }
398
399     valvars (Lam (ValBinder v)  body) vacc = valvars body (v:vacc)
400     valvars other vacc
401       = ASSERT(not (usage_lambda other))
402         ASSERT(not (tyvar_lambda other))
403         (reverse vacc, other)
404
405     ---------------------------------------
406     usage_lambda (Lam (UsageBinder _) _) = True
407     usage_lambda _                       = False
408
409     tyvar_lambda (Lam (TyBinder _) _)    = True
410     tyvar_lambda _                       = False
411 \end{code}
412
413 %************************************************************************
414 %*                                                                      *
415 \subsection{Core arguments (atoms)}
416 %*                                                                      *
417 %************************************************************************
418
419 \begin{code}
420 data GenCoreArg val_occ tyvar uvar
421   = LitArg      Literal
422   | VarArg      val_occ
423   | TyArg       (GenType tyvar uvar)
424   | UsageArg    (GenUsage uvar)
425 \end{code}
426
427 General and specific forms:
428 \begin{code}
429 mkGenApp :: GenCoreExpr val_bdr val_occ tyvar uvar
430          -> [GenCoreArg val_occ tyvar uvar]
431          -> GenCoreExpr val_bdr val_occ tyvar uvar
432 mkTyApp  :: GenCoreExpr val_bdr val_occ tyvar uvar
433          -> [GenType tyvar uvar]
434          -> GenCoreExpr val_bdr val_occ tyvar uvar
435 mkUseApp :: GenCoreExpr val_bdr val_occ tyvar uvar
436          -> [GenUsage uvar]
437          -> GenCoreExpr val_bdr val_occ tyvar uvar
438 mkValApp :: GenCoreExpr val_bdr val_occ tyvar uvar
439          -> [GenCoreArg val_occ tyvar uvar] -- but we ASSERT they are LitArg or VarArg
440          -> GenCoreExpr val_bdr val_occ tyvar uvar
441
442 mkGenApp f args = foldl App                                f args
443 mkTyApp  f args = foldl (\ e a -> App e (TyArg a))         f args
444 mkUseApp f args = foldl (\ e a -> App e (UsageArg a))      f args
445 mkValApp f args = foldl (\ e a -> App e (is_Lit_or_Var a)) f args
446
447 #ifndef DEBUG
448 is_Lit_or_Var a = a
449 #else
450 is_Lit_or_Var a
451   = if isValArg a then a else panic "CoreSyn.mkValApps:not LitArg or VarArg"
452 #endif
453
454 isValArg (LitArg _) = True  -- often used for sanity-checking
455 isValArg (VarArg _) = True
456 isValArg _          = False
457
458 notValArg = not . isValArg -- exists only because it's a common use of isValArg
459
460 numValArgs as = length [ a | a <- as, isValArg a ] -- again, convenience
461 \end{code}
462
463 \begin{code}
464 mkApp  fun = mk_thing (mkGenApp fun)
465 mkCon  con = mk_thing (Con      con)
466 mkPrim op  = mk_thing (Prim     op)
467
468 mk_thing thing uses tys vals
469   = thing (map UsageArg uses ++ map TyArg tys ++ map is_Lit_or_Var vals)
470 \end{code}
471
472 @collectArgs@ takes an application expression, returning the function
473 and the arguments to which it is applied.
474
475 \begin{code}
476 collectArgs :: GenCoreExpr val_bdr val_occ tyvar uvar
477             -> (GenCoreExpr val_bdr val_occ tyvar uvar,
478                 [GenUsage uvar],
479                 [GenType tyvar uvar],
480                 [GenCoreArg val_occ tyvar uvar]{-ValArgs-})
481
482 collectArgs expr
483   = usages expr []
484   where
485     usages (App fun (UsageArg u)) uacc = usages fun (u:uacc)
486     usages fun uacc
487       = case (tyvars fun []) of { (expr, tacc, vacc) ->
488         (expr, uacc, tacc, vacc) }
489
490     tyvars (App fun (TyArg t))    tacc = tyvars fun (t:tacc)
491     tyvars fun tacc
492       = ASSERT(not (usage_app fun))
493         case (valvars fun []) of { (expr, vacc) ->
494         (expr, tacc, vacc) }
495
496     valvars (App fun v) vacc | isValArg v = valvars fun (v:vacc)
497     valvars fun vacc
498       = ASSERT(not (usage_app fun))
499         ASSERT(not (ty_app    fun))
500         (fun, vacc)
501
502     ---------------------------------------
503     usage_app (App _ (UsageArg _)) = True
504     usage_app _                    = False
505
506     ty_app    (App _ (TyArg _))    = True
507     ty_app    _                    = False
508 \end{code}
509
510 %************************************************************************
511 %*                                                                      *
512 \subsection{The main @Core*@ instantiation of the @GenCore*@ types}
513 %*                                                                      *
514 %************************************************************************
515
516 \begin{code}
517 type CoreBinding = GenCoreBinding  Id Id TyVar UVar
518 type CoreExpr    = GenCoreExpr     Id Id TyVar UVar
519 type CoreBinder  = GenCoreBinder   Id    TyVar UVar
520 type CoreArg     = GenCoreArg         Id TyVar UVar
521
522 type CoreCaseAlts    = GenCoreCaseAlts    Id Id TyVar UVar
523 type CoreCaseDefault = GenCoreCaseDefault Id Id TyVar UVar
524 \end{code}
525
526 %************************************************************************
527 %*                                                                      *
528 \subsection{The @TaggedCore*@ instantiation of the @GenCore*@ types}
529 %*                                                                      *
530 %************************************************************************
531
532 Binders are ``tagged'' with a \tr{t}:
533 \begin{code}
534 type Tagged t = (Id, t)
535
536 type TaggedCoreBinding t = GenCoreBinding (Tagged t) Id TyVar UVar
537 type TaggedCoreExpr    t = GenCoreExpr    (Tagged t) Id TyVar UVar
538 type TaggedCoreBinder  t = GenCoreBinder  (Tagged t)    TyVar UVar
539 type TaggedCoreArg     t = GenCoreArg                Id TyVar UVar
540
541 type TaggedCoreCaseAlts    t = GenCoreCaseAlts    (Tagged t) Id TyVar UVar
542 type TaggedCoreCaseDefault t = GenCoreCaseDefault (Tagged t) Id TyVar UVar
543 \end{code}
544
545 %************************************************************************
546 %*                                                                      *
547 \subsection{The @SimplifiableCore*@ instantiation of the @GenCore*@ types}
548 %*                                                                      *
549 %************************************************************************
550
551 Binders are tagged with @BinderInfo@:
552 \begin{code}
553 type Simplifiable = (Id, BinderInfo)
554
555 type SimplifiableCoreBinding = GenCoreBinding Simplifiable Id TyVar UVar
556 type SimplifiableCoreExpr    = GenCoreExpr    Simplifiable Id TyVar UVar
557 type SimplifiableCoreBinder  = GenCoreBinder  Simplifiable    TyVar UVar
558 type SimplifiableCoreArg     = GenCoreArg                  Id TyVar UVar
559
560 type SimplifiableCoreCaseAlts    = GenCoreCaseAlts    Simplifiable Id TyVar UVar
561 type SimplifiableCoreCaseDefault = GenCoreCaseDefault Simplifiable Id TyVar UVar
562 \end{code}