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