2 % (c) The AQUA Project, Glasgow University, 1993-1996
4 \section[Simplify]{The main module of the simplifier}
7 #include "HsVersions.h"
9 module Simplify ( simplTopBinds, simplExpr, simplBind ) where
12 IMPORT_DELOOPER(SmplLoop) -- paranoia checking
13 IMPORT_1_3(List(partition))
16 import CmdLineOpts ( SimplifierSwitch(..) )
17 import ConFold ( completePrim )
18 import CoreUnfold ( Unfolding, SimpleUnfolding, mkFormSummary, exprIsTrivial, whnfOrBottom, FormSummary(..) )
19 import CostCentre ( isSccCountCostCentre, cmpCostCentre )
21 import CoreUtils ( coreExprType, nonErrorRHSs, maybeErrorApp,
22 unTagBinders, squashableDictishCcExpr
24 import Id ( idType, idWantsToBeINLINEd, idMustNotBeINLINEd, addIdArity, getIdArity,
25 getIdDemandInfo, addIdDemandInfo,
26 GenId{-instance NamedThing-}
28 import Name ( isExported )
29 import IdInfo ( willBeDemanded, noDemandInfo, DemandInfo, ArityInfo(..),
30 atLeastArity, unknownArity )
31 import Literal ( isNoRepLit )
32 import Maybes ( maybeToBool )
33 --import Name ( isExported )
34 import PprStyle ( PprStyle(..) )
35 import PprType ( GenType{-instance Outputable-}, GenTyVar{- instance Outputable -} )
36 #if __GLASGOW_HASKELL__ <= 30
37 import PprCore ( GenCoreArg, GenCoreExpr )
39 import TyVar ( GenTyVar {- instance Eq -} )
40 import Pretty --( ($$) )
41 import PrimOp ( primOpOkForSpeculation, PrimOp(..) )
42 import SimplCase ( simplCase, bindLargeRhs )
45 import SimplVar ( completeVar )
46 import Unique ( Unique )
48 import Type ( mkTyVarTy, mkTyVarTys, mkAppTy, applyTy, mkFunTys,
49 splitFunTy, splitFunTyExpandingDicts, getFunTy_maybe, eqTy
51 import TysWiredIn ( realWorldStateTy )
52 import Outputable ( Outputable(..) )
53 import Util ( SYN_IE(Eager), appEager, returnEager, runEager, mapEager,
54 isSingleton, zipEqual, zipWithEqual, mapAndUnzip, panic, pprPanic, assertPanic, pprTrace )
57 The controlling flags, and what they do
58 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
62 -fsimplify = run the simplifier
63 -ffloat-inwards = runs the float lets inwards pass
64 -ffloat = runs the full laziness pass
65 (ToDo: rename to -ffull-laziness)
66 -fupdate-analysis = runs update analyser
67 -fstrictness = runs strictness analyser
68 -fsaturate-apps = saturates applications (eta expansion)
72 -ffloat-past-lambda = OK to do full laziness.
73 (ToDo: remove, as the full laziness pass is
74 useless without this flag, therefore
75 it is unnecessary. Just -ffull-laziness
78 -ffloat-lets-ok = OK to float lets out of lets if the enclosing
79 let is strict or if the floating will expose
82 -ffloat-primops-ok = OK to float out of lets cases whose scrutinee
83 is a primop that cannot fail [simplifier].
85 -fcode-duplication-ok = allows the previous option to work on cases with
86 multiple branches [simplifier].
88 -flet-to-case = does let-to-case transformation [simplifier].
90 -fcase-of-case = does case of case transformation [simplifier].
92 -fpedantic-bottoms = does not allow:
93 case x of y -> e ===> e[x/y]
94 (which may turn bottom into non-bottom)
100 Inlining is one of the delicate aspects of the simplifier. By
101 ``inlining'' we mean replacing an occurrence of a variable ``x'' by
102 the RHS of x's definition. Thus
104 let x = e in ...x... ===> let x = e in ...e...
106 We have two mechanisms for inlining:
108 1. Unconditional. The occurrence analyser has pinned an (OneOcc
109 FunOcc NoDupDanger NotInsideSCC n) flag on the variable, saying ``it's
110 certainly safe to inline this variable, and to drop its binding''.
111 (...Umm... if n <= 1; if n > 1, it is still safe, provided you are
112 happy to be duplicating code...) When it encounters such a beast, the
113 simplifer binds the variable to its RHS (in the id_env) and continues.
114 It doesn't even look at the RHS at that stage. It also drops the
117 2. Conditional. In all other situations, the simplifer simplifies
118 the RHS anyway, and keeps the new binding. It also binds the new
119 (cloned) variable to a ``suitable'' Unfolding in the UnfoldEnv.
121 Here, ``suitable'' might mean NoUnfolding (if the occurrence
122 info is ManyOcc and the RHS is not a manifest HNF, or UnfoldAlways (if
123 the variable has an INLINE pragma on it). The idea is that anything
124 in the UnfoldEnv is safe to use, but also has an enclosing binding if
125 you decide not to use it.
129 We *never* put a non-HNF unfolding in the UnfoldEnv except in the
132 At one time I thought it would be OK to put non-HNF unfoldings in for
133 variables which occur only once [if they got inlined at that
134 occurrence the RHS of the binding would become dead, so no duplication
135 would occur]. But consider:
138 f = \y -> ...y...y...y...
141 Now, it seems that @x@ appears only once, but even so it is NOT safe
142 to put @x@ in the UnfoldEnv, because @f@ will be inlined, and will
143 duplicate the references to @x@.
145 Because of this, the "unconditional-inline" mechanism above is the
146 only way in which non-HNFs can get inlined.
151 When a variable has an INLINE pragma on it --- which includes wrappers
152 produced by the strictness analyser --- we treat it rather carefully.
154 For a start, we are careful not to substitute into its RHS, because
155 that might make it BIG, and the user said "inline exactly this", not
156 "inline whatever you get after inlining other stuff inside me". For
160 in {-# INLINE y #-} y = f 3
163 Here we don't want to substitute BIG for the (single) occurrence of f,
164 because then we'd duplicate BIG when we inline'd y. (Exception:
165 things in the UnfoldEnv with UnfoldAlways flags, which originated in
166 other INLINE pragmas.)
168 So, we clean out the UnfoldEnv of all SimpleUnfolding inlinings before
169 going into such an RHS.
171 What about imports? They don't really matter much because we only
172 inline relatively small things via imports.
174 We augment the the UnfoldEnv with UnfoldAlways guidance if there's an
175 INLINE pragma. We also do this for the RHSs of recursive decls,
176 before looking at the recursive decls. That way we achieve the effect
177 of inlining a wrapper in the body of its worker, in the case of a
178 mutually-recursive worker/wrapper split.
181 %************************************************************************
183 \subsection[Simplify-simplExpr]{The main function: simplExpr}
185 %************************************************************************
187 At the top level things are a little different.
189 * No cloning (not allowed for exported Ids, unnecessary for the others)
190 * Floating is done a bit differently (no case floating; check for leaks; handle letrec)
193 simplTopBinds :: SimplEnv -> [InBinding] -> SmplM [OutBinding]
195 -- Dead code is now discarded by the occurrence analyser,
197 simplTopBinds env binds
198 = mapSmpl (floatBind env True) binds `thenSmpl` \ binds_s ->
199 simpl_top_binds env (concat binds_s)
201 simpl_top_binds env [] = returnSmpl []
203 simpl_top_binds env (NonRec binder@(in_id,occ_info) rhs : binds)
204 = --- No cloning necessary at top level
205 simplRhsExpr env binder rhs in_id `thenSmpl` \ (rhs',arity) ->
206 completeNonRec env binder (in_id `withArity` arity) rhs' `thenSmpl` \ (new_env, binds1') ->
207 simpl_top_binds new_env binds `thenSmpl` \ binds2' ->
208 returnSmpl (binds1' ++ binds2')
210 simpl_top_binds env (Rec pairs : binds)
211 = -- No cloning necessary at top level, but we nevertheless
212 -- add the Ids to the environment. This makes sure that
213 -- info carried on the Id (such as arity info) gets propagated
216 -- This may seem optional, but I found an occasion when it Really matters.
217 -- Consider foo{n} = ...foo...
220 -- where baz* is exported and foo isn't. Then when we do "indirection-shorting"
221 -- in tidyCore, we need the {no-inline} pragma from foo to attached to the final
222 -- thing: baz*{n} = ...baz...
224 -- Sure we could have made the indirection-shorting a bit cleverer, but
225 -- propagating pragma info is a Good Idea anyway.
227 env1 = extendIdEnvWithClones env binders ids
229 simplRecursiveGroup env1 ids pairs `thenSmpl` \ (bind', new_env) ->
230 simpl_top_binds new_env binds `thenSmpl` \ binds' ->
231 returnSmpl (Rec bind' : binds')
233 binders = map fst pairs
234 ids = map fst binders
237 %************************************************************************
239 \subsection[Simplify-simplExpr]{The main function: simplExpr}
241 %************************************************************************
245 simplExpr :: SimplEnv
246 -> InExpr -> [OutArg]
247 -> OutType -- Type of (e args); i.e. type of overall result
251 The expression returned has the same meaning as the input expression
252 applied to the specified arguments.
257 Check if there's a macro-expansion, and if so rattle on. Otherwise do
258 the more sophisticated stuff.
261 simplExpr env (Var v) args result_ty
262 = case (runEager $ lookupId env v) of
263 LitArg lit -- A boring old literal
264 -> ASSERT( null args )
267 VarArg var -- More interesting! An id!
268 -> completeVar env var args result_ty
269 -- Either Id is in the local envt, or it's a global.
270 -- In either case we don't need to apply the type
271 -- environment to it.
278 simplExpr env (Lit l) [] result_ty = returnSmpl (Lit l)
280 simplExpr env (Lit l) _ _ = panic "simplExpr:Lit with argument"
284 Primitive applications are simple.
285 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
287 NB: Prim expects an empty argument list! (Because it should be
288 saturated and not higher-order. ADR)
291 simplExpr env (Prim op prim_args) args result_ty
293 mapEager (simplArg env) prim_args `appEager` \ prim_args' ->
294 simpl_op op `appEager` \ op' ->
295 completePrim env op' prim_args'
297 -- PrimOps just need any types in them renamed.
299 simpl_op (CCallOp label is_asm may_gc arg_tys result_ty)
300 = mapEager (simplTy env) arg_tys `appEager` \ arg_tys' ->
301 simplTy env result_ty `appEager` \ result_ty' ->
302 returnEager (CCallOp label is_asm may_gc arg_tys' result_ty')
304 simpl_op other_op = returnEager other_op
307 Constructor applications
308 ~~~~~~~~~~~~~~~~~~~~~~~~
309 Nothing to try here. We only reuse constructors when they appear as the
310 rhs of a let binding (see completeLetBinding).
313 simplExpr env (Con con con_args) args result_ty
314 = ASSERT( null args )
315 mapEager (simplArg env) con_args `appEager` \ con_args' ->
316 returnSmpl (Con con con_args')
320 Applications are easy too:
321 ~~~~~~~~~~~~~~~~~~~~~~~~~~
322 Just stuff 'em in the arg stack
325 simplExpr env (App fun arg) args result_ty
326 = simplArg env arg `appEager` \ arg' ->
327 simplExpr env fun (arg' : args) result_ty
333 First the case when it's applied to an argument.
336 simplExpr env (Lam (TyBinder tyvar) body) (TyArg ty : args) result_ty
337 = -- ASSERT(not (isPrimType ty))
338 tick TyBetaReduction `thenSmpl_`
339 simplExpr (extendTyEnv env tyvar ty) body args result_ty
343 simplExpr env tylam@(Lam (TyBinder tyvar) body) [] result_ty
344 = cloneTyVarSmpl tyvar `thenSmpl` \ tyvar' ->
346 new_ty = mkTyVarTy tyvar'
347 new_env = extendTyEnv env tyvar new_ty
348 new_result_ty = applyTy result_ty new_ty
350 simplExpr new_env body [] new_result_ty `thenSmpl` \ body' ->
351 returnSmpl (Lam (TyBinder tyvar') body')
354 simplExpr env (Lam (TyBinder _) _) (_ : _) result_ty
355 = panic "simplExpr:TyLam with non-TyArg"
363 There's a complication with lambdas that aren't saturated.
368 If we did nothing, x is used inside the \y, so would be marked
369 as dangerous to dup. But in the common case where the abstraction
370 is applied to two arguments this is over-pessimistic.
371 So instead we don't take account of the \y when dealing with x's usage;
372 instead, the simplifier is careful when partially applying lambdas.
375 simplExpr env expr@(Lam (ValBinder binder) body) orig_args result_ty
376 = go 0 env expr orig_args
378 go n env (Lam (ValBinder binder) body) (val_arg : args)
379 | isValArg val_arg -- The lambda has an argument
380 = tick BetaReduction `thenSmpl_`
381 go (n+1) (extendIdEnvWithAtom env binder val_arg) body args
383 go n env expr@(Lam (ValBinder binder) body) args
384 -- The lambda is un-saturated, so we must zap the occurrence info
385 -- on the arguments we've already beta-reduced into the body of the lambda
386 = ASSERT( null args ) -- Value lambda must match value argument!
388 new_env = markDangerousOccs env (take n orig_args)
390 simplValLam new_env expr 0 {- Guaranteed applied to at least 0 args! -} result_ty
391 `thenSmpl` \ (expr', arity) ->
394 go n env non_val_lam_expr args -- The lambda had enough arguments
395 = simplExpr env non_val_lam_expr args result_ty
403 simplExpr env (Let bind body) args result_ty
404 = simplBind env bind (\env -> simplExpr env body args result_ty) result_ty
411 simplExpr env expr@(Case scrut alts) args result_ty
412 = simplCase env scrut alts (\env rhs -> simplExpr env rhs args result_ty) result_ty
419 simplExpr env (Coerce coercion ty body) args result_ty
420 = simplCoerce env coercion ty body args result_ty
427 1) Eliminating nested sccs ...
428 We must be careful to maintain the scc counts ...
431 simplExpr env (SCC cc1 (SCC cc2 expr)) args result_ty
432 | not (isSccCountCostCentre cc2) && case cmpCostCentre cc1 cc2 of { EQ_ -> True; _ -> False }
433 -- eliminate inner scc if no call counts and same cc as outer
434 = simplExpr env (SCC cc1 expr) args result_ty
436 | not (isSccCountCostCentre cc2) && not (isSccCountCostCentre cc1)
437 -- eliminate outer scc if no call counts associated with either ccs
438 = simplExpr env (SCC cc2 expr) args result_ty
441 2) Moving sccs inside lambdas ...
444 simplExpr env (SCC cc (Lam binder@(ValBinder _) body)) args result_ty
445 | not (isSccCountCostCentre cc)
446 -- move scc inside lambda only if no call counts
447 = simplExpr env (Lam binder (SCC cc body)) args result_ty
449 simplExpr env (SCC cc (Lam binder body)) args result_ty
450 -- always ok to move scc inside type/usage lambda
451 = simplExpr env (Lam binder (SCC cc body)) args result_ty
454 3) Eliminating dict sccs ...
457 simplExpr env (SCC cc expr) args result_ty
458 | squashableDictishCcExpr cc expr
459 -- eliminate dict cc if trivial dict expression
460 = simplExpr env expr args result_ty
463 4) Moving arguments inside the body of an scc ...
464 This moves the cost of doing the application inside the scc
465 (which may include the cost of extracting methods etc)
468 simplExpr env (SCC cost_centre body) args result_ty
470 new_env = setEnclosingCC env cost_centre
472 simplExpr new_env body args result_ty `thenSmpl` \ body' ->
473 returnSmpl (SCC cost_centre body')
476 %************************************************************************
478 \subsection{Simplify RHS of a Let/Letrec}
480 %************************************************************************
482 simplRhsExpr does arity-expansion. That is, given:
484 * a right hand side /\ tyvars -> \a1 ... an -> e
485 * the information (stored in BinderInfo) that the function will always
486 be applied to at least k arguments
488 it transforms the rhs to
490 /\tyvars -> \a1 ... an b(n+1) ... bk -> (e b(n+1) ... bk)
492 This is a Very Good Thing!
499 -> OutId -- The new binder (used only for its type)
500 -> SmplM (OutExpr, ArityInfo)
502 -- First a special case for variable right-hand sides
504 -- It's OK to simplify the RHS, but it's often a waste of time. Often
505 -- these v = w things persist because v is exported, and w is used
506 -- elsewhere. So if we're not careful we'll eta expand the rhs, only
507 -- to eta reduce it in competeNonRec.
509 -- If we leave the binding unchanged, we will certainly replace v by w at
510 -- every occurrence of v, which is good enough.
512 -- In fact, it's better to replace v by w than to inline w in v's rhs,
513 -- even if this is the only occurrence of w. Why? Because w might have
514 -- IdInfo (like strictness) that v doesn't.
516 simplRhsExpr env binder@(id,occ_info) (Var v) new_id
517 = case (runEager $ lookupId env v) of
518 LitArg lit -> returnSmpl (Lit lit, ArityExactly 0)
519 VarArg v' -> returnSmpl (Var v', getIdArity v')
521 simplRhsExpr env binder@(id,occ_info) rhs new_id
522 = -- Deal with the big lambda part
523 ASSERT( null uvars ) -- For now
525 mapSmpl cloneTyVarSmpl tyvars `thenSmpl` \ tyvars' ->
527 rhs_ty = idType new_id
528 new_tys = mkTyVarTys tyvars'
529 body_ty = foldl applyTy rhs_ty new_tys
530 lam_env = extendTyEnvList rhs_env (zipEqual "simplRhsExpr" tyvars new_tys)
532 -- Deal with the little lambda part
533 -- Note that we call simplLam even if there are no binders,
534 -- in case it can do arity expansion.
535 simplValLam lam_env body (getBinderInfoArity occ_info) body_ty `thenSmpl` \ (lambda', arity) ->
537 -- Put on the big lambdas, trying to float out any bindings caught inside
538 mkRhsTyLam tyvars' lambda' `thenSmpl` \ rhs' ->
540 returnSmpl (rhs', arity)
542 rhs_env | -- Don't ever inline in a INLINE thing's rhs, because
543 -- doing so will inline a worker straight back into its wrapper!
544 idWantsToBeINLINEd id
545 = switchOffInlining env
549 -- Switch off all inlining in the RHS of things that have an INLINE pragma.
550 -- They are going to be inlined wherever they are used, and then all the
551 -- inlining will take effect. Meanwhile, there isn't
552 -- much point in doing anything to the as-yet-un-INLINEd rhs.
553 -- It's very important to switch off inlining! Consider:
555 -- let f = \pq -> BIG
557 -- let g = \y -> f y y
559 -- in ...g...g...g...g...g...
561 -- Now, if that's the ONLY occurrence of f, it will be inlined inside g,
562 -- and thence copied multiple times when g is inlined.
564 -- Andy disagrees! Example:
565 -- all xs = foldr (&&) True xs
566 -- any p = all . map p {-# INLINE any #-}
568 -- Problem: any won't get deforested, and so if it's exported and
569 -- the importer doesn't use the inlining, (eg passes it as an arg)
570 -- then we won't get deforestation at all.
571 -- We havn't solved this problem yet!
573 (uvars, tyvars, body) = collectUsageAndTyBinders rhs
577 %************************************************************************
579 \subsection{Simplify a lambda abstraction}
581 %************************************************************************
583 Simplify (\binders -> body) trying eta expansion and reduction, given that
584 the abstraction will always be applied to at least min_no_of_args.
587 simplValLam env expr min_no_of_args expr_ty
588 | not (switchIsSet env SimplDoLambdaEtaExpansion) || -- Bale out if eta expansion off
590 exprIsTrivial expr || -- or it's a trivial RHS
591 -- No eta expansion for trivial RHSs
592 -- It's rather a Bad Thing to expand
595 -- g = \a b c -> f alpha beta a b c
597 -- The original RHS is "trivial" (exprIsTrivial), because it generates
598 -- no code (renames f to g). But the new RHS isn't.
600 null potential_extra_binder_tys || -- or ain't a function
601 no_of_extra_binders <= 0 -- or no extra binders needed
602 = cloneIds env binders `thenSmpl` \ binders' ->
604 new_env = extendIdEnvWithClones env binders binders'
606 simplExpr new_env body [] body_ty `thenSmpl` \ body' ->
607 returnSmpl (mkValLam binders' body', final_arity)
609 | otherwise -- Eta expansion possible
610 = -- A SSERT( no_of_extra_binders <= length potential_extra_binder_tys )
611 (if not ( no_of_extra_binders <= length potential_extra_binder_tys ) then
612 pprTrace "simplValLam" (vcat [ppr PprDebug expr,
613 ppr PprDebug expr_ty,
614 ppr PprDebug binders,
615 int no_of_extra_binders,
616 ppr PprDebug potential_extra_binder_tys])
619 tick EtaExpansion `thenSmpl_`
620 cloneIds env binders `thenSmpl` \ binders' ->
622 new_env = extendIdEnvWithClones env binders binders'
624 newIds extra_binder_tys `thenSmpl` \ extra_binders' ->
625 simplExpr new_env body (map VarArg extra_binders') etad_body_ty `thenSmpl` \ body' ->
627 mkValLam (binders' ++ extra_binders') body',
632 (binders,body) = collectValBinders expr
633 no_of_binders = length binders
634 (arg_tys, res_ty) = splitFunTyExpandingDicts expr_ty
635 potential_extra_binder_tys = (if not (no_of_binders <= length arg_tys) then
636 pprTrace "simplValLam" (vcat [ppr PprDebug expr,
637 ppr PprDebug expr_ty,
638 ppr PprDebug binders])
640 drop no_of_binders arg_tys
641 body_ty = mkFunTys potential_extra_binder_tys res_ty
643 -- Note: it's possible that simplValLam will be applied to something
644 -- with a forall type. Eg when being applied to the rhs of
646 -- where wurble has a forall-type, but no big lambdas at the top.
647 -- We could be clever an insert new big lambdas, but we don't bother.
649 etad_body_ty = mkFunTys (drop no_of_extra_binders potential_extra_binder_tys) res_ty
650 extra_binder_tys = take no_of_extra_binders potential_extra_binder_tys
651 final_arity = atLeastArity (no_of_binders + no_of_extra_binders)
653 no_of_extra_binders = -- First, use the info about how many args it's
654 -- always applied to in its scope; but ignore this
655 -- info for thunks. To see why we ignore it for thunks,
656 -- consider let f = lookup env key in (f 1, f 2)
657 -- We'd better not eta expand f just because it is
659 (min_no_of_args - no_of_binders)
661 -- Next, try seeing if there's a lambda hidden inside
663 -- etaExpandCount can reuturn a huge number (like 10000!) if
664 -- it finds that the body is a call to "error"; hence
665 -- the use of "min" here.
667 (etaExpandCount body `min` length potential_extra_binder_tys)
669 -- Finally, see if it's a state transformer, in which
670 -- case we eta-expand on principle! This can waste work,
671 -- but usually doesn't
673 case potential_extra_binder_tys of
674 [ty] | ty `eqTy` realWorldStateTy -> 1
680 %************************************************************************
682 \subsection[Simplify-coerce]{Coerce expressions}
684 %************************************************************************
687 -- (coerce (case s of p -> r)) args ==> case s of p -> (coerce r) args
688 simplCoerce env coercion ty expr@(Case scrut alts) args result_ty
689 = simplCase env scrut alts (\env rhs -> simplCoerce env coercion ty rhs args result_ty) result_ty
691 -- (coerce (let defns in b)) args ==> let defns' in (coerce b) args
692 simplCoerce env coercion ty (Let bind body) args result_ty
693 = simplBind env bind (\env -> simplCoerce env coercion ty body args result_ty) result_ty
696 simplCoerce env coercion ty expr args result_ty
697 = simplTy env ty `appEager` \ ty' ->
698 simplTy env expr_ty `appEager` \ expr_ty' ->
699 simplExpr env expr [] expr_ty' `thenSmpl` \ expr' ->
700 returnSmpl (mkGenApp (mkCoerce coercion ty' expr') args)
702 expr_ty = coreExprType (unTagBinders expr) -- Rather like simplCase other_scrut
704 -- Try cancellation; we do this "on the way up" because
705 -- I think that's where it'll bite best
706 mkCoerce (CoerceOut con1) ty1 (Coerce (CoerceIn con2) ty2 body) | con1 == con2 = body
707 mkCoerce coercion ty body = Coerce coercion ty body
711 %************************************************************************
713 \subsection[Simplify-let]{Let-expressions}
715 %************************************************************************
718 simplBind :: SimplEnv
720 -> (SimplEnv -> SmplM OutExpr)
725 When floating cases out of lets, remember this:
727 let x* = case e of alts
730 where x* is sure to be demanded or e is a cheap operation that cannot
731 fail, e.g. unboxed addition. Here we should be prepared to duplicate
732 <small expr>. A good example:
741 p1 -> foldr c n (build e1)
742 p2 -> foldr c n (build e2)
744 NEW: We use the same machinery that we use for case-of-case to
745 *always* do case floating from let, that is we let bind and abstract
746 the original let body, and let the occurrence analyser later decide
747 whether the new let should be inlined or not. The example above
751 let join_body x' = foldr c n x'
753 p1 -> let x* = build e1
755 p2 -> let x* = build e2
758 note that join_body is a let-no-escape.
759 In this particular example join_body will later be inlined,
760 achieving the same effect.
761 ToDo: check this is OK with andy
766 -- Dead code is now discarded by the occurrence analyser,
768 simplBind env (NonRec binder@(id,occ_info) rhs) body_c body_ty
769 | idWantsToBeINLINEd id
770 = complete_bind env rhs -- Don't mess about with floating or let-to-case on
775 -- Try for strict let of error
776 simpl_bind env rhs | will_be_demanded && maybeToBool maybe_error_app
777 = returnSmpl retyped_error_app
779 maybe_error_app = maybeErrorApp rhs (Just body_ty)
780 Just retyped_error_app = maybe_error_app
782 -- Try let-to-case; see notes below about let-to-case
783 simpl_bind env rhs | will_be_demanded &&
785 singleConstructorType rhs_ty &&
786 -- Only do let-to-case for single constructor types.
787 -- For other types we defer doing it until the tidy-up phase at
788 -- the end of simplification.
789 not rhs_is_whnf -- note: WHNF, but not bottom, (comment below)
790 = tick Let2Case `thenSmpl_`
791 mkIdentityAlts rhs_ty demand_info `thenSmpl` \ id_alts ->
792 simplCase env rhs id_alts (\env rhs -> complete_bind env rhs) body_ty
793 -- NB: it's tidier to call complete_bind not simpl_bind, else
794 -- we nearly end up in a loop. Consider:
796 -- ==> case rhs of (p,q) -> let x=(p,q) in b
797 -- This effectively what the above simplCase call does.
798 -- Now, the inner let is a let-to-case target again! Actually, since
799 -- the RHS is in WHNF it won't happen, but it's a close thing!
802 simpl_bind env (Let bind rhs) | let_floating_ok
803 = tick LetFloatFromLet `thenSmpl_`
804 simplBind env (fix_up_demandedness will_be_demanded bind)
805 (\env -> simpl_bind env rhs) body_ty
807 -- Try case-from-let; this deals with a strict let of error too
808 simpl_bind env (Case scrut alts) | case_floating_ok scrut
809 = tick CaseFloatFromLet `thenSmpl_`
811 -- First, bind large let-body if necessary
812 if ok_to_dup || isSingleton (nonErrorRHSs alts)
814 simplCase env scrut alts (\env rhs -> simpl_bind env rhs) body_ty
816 bindLargeRhs env [binder] body_ty body_c `thenSmpl` \ (extra_binding, new_body) ->
818 body_c' = \env -> simplExpr env new_body [] body_ty
819 case_c = \env rhs -> simplBind env (NonRec binder rhs) body_c' body_ty
821 simplCase env scrut alts case_c body_ty `thenSmpl` \ case_expr ->
822 returnSmpl (Let extra_binding case_expr)
824 -- None of the above; simplify rhs and tidy up
825 simpl_bind env rhs = complete_bind env rhs
827 complete_bind env rhs
828 = cloneId env binder `thenSmpl` \ new_id ->
829 simplRhsExpr env binder rhs new_id `thenSmpl` \ (rhs',arity) ->
830 completeNonRec env binder
831 (new_id `withArity` arity) rhs' `thenSmpl` \ (new_env, binds) ->
832 body_c new_env `thenSmpl` \ body' ->
833 returnSmpl (mkCoLetsAny binds body')
836 -- All this stuff is computed at the start of the simpl_bind loop
837 float_lets = switchIsSet env SimplFloatLetsExposingWHNF
838 float_primops = switchIsSet env SimplOkToFloatPrimOps
839 ok_to_dup = switchIsSet env SimplOkToDupCode
840 always_float_let_from_let = switchIsSet env SimplAlwaysFloatLetsFromLets
841 try_let_to_case = switchIsSet env SimplLetToCase
842 no_float = switchIsSet env SimplNoLetFromStrictLet
844 demand_info = getIdDemandInfo id
845 will_be_demanded = willBeDemanded demand_info
848 form = mkFormSummary rhs
849 rhs_is_bot = case form of
852 rhs_is_whnf = case form of
857 float_exposes_hnf = floatExposesHNF float_lets float_primops ok_to_dup rhs
859 let_floating_ok = (will_be_demanded && not no_float) ||
860 always_float_let_from_let ||
863 case_floating_ok scrut = (will_be_demanded && not no_float) ||
864 (float_exposes_hnf && is_cheap_prim_app scrut && float_primops)
870 The booleans controlling floating have to be set with a little care.
871 Here's one performance bug I found:
873 let x = let y = let z = case a# +# 1 of {b# -> E1}
878 Now, if E2, E3 aren't HNFs we won't float the y-binding or the z-binding.
879 Before case_floating_ok included float_exposes_hnf, the case expression was floated
880 *one level per simplifier iteration* outwards. So it made th s
882 Let to case: two points
885 Point 1. We defer let-to-case for all data types except single-constructor
886 ones. Suppose we change
892 It can be the case that we find that b ultimately contains ...(case x of ..)....
893 and this is the only occurrence of x. Then if we've done let-to-case
894 we can't inline x, which is a real pain. On the other hand, we lose no
895 transformations by not doing this transformation, because the relevant
896 case-of-X transformations are also implemented by simpl_bind.
898 If x is a single-constructor type, then we go ahead anyway, giving
900 case e of (y,z) -> let x = (y,z) in b
902 because now we can squash case-on-x wherever they occur in b.
904 We do let-to-case on multi-constructor types in the tidy-up phase
905 (tidyCoreExpr) mainly so that the code generator doesn't need to
906 spot the demand-flag.
909 Point 2. It's important to try let-to-case before doing the
910 strict-let-of-case transformation, which happens in the next equation
913 let a*::Int = case v of {p1->e1; p2->e2}
916 (The * means that a is sure to be demanded.)
917 If we do case-floating first we get this:
921 p1-> let a*=e1 in k a
922 p2-> let a*=e2 in k a
924 Now watch what happens if we do let-to-case first:
926 case (case v of {p1->e1; p2->e2}) of
927 Int a# -> let a*=I# a# in b
929 let k = \a# -> let a*=I# a# in b
931 p1 -> case e1 of I# a# -> k a#
932 p1 -> case e2 of I# a# -> k a#
934 The latter is clearly better. (Remember the reboxing let-decl for a
935 is likely to go away, because after all b is strict in a.)
937 We do not do let to case for WHNFs, e.g.
943 as this is less efficient. but we don't mind doing let-to-case for
944 "bottom", as that will allow us to remove more dead code, if anything:
948 case error of x -> ...
952 Notice that let to case occurs only if x is used strictly in its body
959 Simplify each RHS, float any let(recs) from the RHSs (if let-floating is
960 on and it'll expose a HNF), and bang the whole resulting mess together
963 1. Any "macros" should be expanded. The main application of this
972 Here we would like the single call to g to be inlined.
974 We can spot this easily, because g will be tagged as having just one
975 occurrence. The "inlineUnconditionally" predicate is just what we want.
977 A worry: could this lead to non-termination? For example:
986 Here, f and g call each other (just once) and neither is used elsewhere.
989 * the occurrence analyser will drop any (sub)-group that isn't used at
992 * If the group is used outside itself (ie in the "in" part), then there
995 ** IMPORTANT: check that NewOccAnal has the property that a group of
996 bindings like the above has f&g dropped.! ***
999 2. We'd also like to pull out any top-level let(rec)s from the
1003 f = let h = ... in \x -> ....h...f...h...
1009 f = \x -> ....h...f...h...
1013 But floating cases is less easy? (Don't for now; ToDo?)
1016 3. We'd like to arrange that the RHSs "know" about members of the
1017 group that are bound to constructors. For example:
1021 f a b c d = case d.Eq of (h,_) -> let x = (a,b); y = (c,d) in not (h x y)
1022 /= a b = unpack tuple a, unpack tuple b, call f
1025 here, by knowing about d.Eq in f's rhs, one could get rid of
1026 the case (and break out the recursion completely).
1027 [This occurred with more aggressive inlining threshold (4),
1028 nofib/spectral/knights]
1031 1: we simplify constructor rhss first.
1032 2: we record the "known constructors" in the environment
1033 3: we simplify the other rhss, with the knowledge about the constructors
1038 simplBind env (Rec pairs) body_c body_ty
1039 = -- Do floating, if necessary
1040 floatBind env False (Rec pairs) `thenSmpl` \ [Rec pairs'] ->
1042 binders = map fst pairs'
1044 cloneIds env binders `thenSmpl` \ ids' ->
1046 env_w_clones = extendIdEnvWithClones env binders ids'
1048 simplRecursiveGroup env_w_clones ids' pairs' `thenSmpl` \ (pairs', new_env) ->
1050 body_c new_env `thenSmpl` \ body' ->
1052 returnSmpl (Let (Rec pairs') body')
1056 -- The env passed to simplRecursiveGroup already has
1057 -- bindings that clone the variables of the group.
1058 simplRecursiveGroup env new_ids []
1059 = returnSmpl ([], env)
1061 simplRecursiveGroup env (new_id : new_ids) ((binder@(_, occ_info), rhs) : pairs)
1062 = simplRhsExpr env binder rhs new_id `thenSmpl` \ (new_rhs, arity) ->
1064 new_id' = new_id `withArity` arity
1066 -- ToDo: this next bit could usefully share code with completeNonRec
1069 | idMustNotBeINLINEd new_id -- Occurrence analyser says "don't inline"
1072 | is_atomic eta'd_rhs -- If rhs (after eta reduction) is atomic
1073 = extendIdEnvWithAtom env binder the_arg
1075 | otherwise -- Non-atomic
1076 = extendEnvGivenBinding env occ_info new_id new_rhs
1077 -- Don't eta if it doesn't eliminate the binding
1079 eta'd_rhs = etaCoreExpr new_rhs
1080 the_arg = case eta'd_rhs of
1084 simplRecursiveGroup new_env new_ids pairs `thenSmpl` \ (new_pairs, final_env) ->
1085 returnSmpl ((new_id', new_rhs) : new_pairs, final_env)
1089 @completeLet@ looks at the simplified post-floating RHS of the
1090 let-expression, and decides what to do. There's one interesting
1091 aspect to this, namely constructor reuse. Consider
1097 Is it a good idea to replace the rhs @y:ys@ with @x@? This depends a
1098 bit on the compiler technology, but in general I believe not. For
1099 example, here's some code from a real program:
1101 const.Int.max.wrk{-s2516-} =
1102 \ upk.s3297# upk.s3298# ->
1106 a.s3299 = I#! upk.s3297#
1108 case (const.Int._tagCmp.wrk{-s2513-} upk.s3297# upk.s3298#) of {
1109 _LT -> I#! upk.s3298#
1114 The a.s3299 really isn't doing much good. We'd be better off inlining
1115 it. (Actually, let-no-escapery means it isn't as bad as it looks.)
1117 So the current strategy is to inline all known-form constructors, and
1118 only do the reverse (turn a constructor application back into a
1119 variable) when we find a let-expression:
1123 ... (let y = C a1 .. an in ...) ...
1125 where it is always good to ditch the binding for y, and replace y by
1126 x. That's just what completeLetBinding does.
1130 -- We want to ensure that all let-bound Coerces have
1131 -- atomic bodies, so they can freely be inlined.
1132 completeNonRec env binder new_id (Coerce coercion ty rhs)
1133 | not (is_atomic rhs)
1134 = newId (coreExprType rhs) `thenSmpl` \ inner_id ->
1136 (inner_id, dangerousArgOcc) inner_id rhs `thenSmpl` \ (env1, binds1) ->
1137 -- Dangerous occ because, like constructor args,
1138 -- it can be duplicated easily
1140 atomic_rhs = case runEager $ lookupId env1 inner_id of
1144 completeNonRec env1 binder new_id
1145 (Coerce coercion ty atomic_rhs) `thenSmpl` \ (env2, binds2) ->
1147 returnSmpl (env2, binds1 ++ binds2)
1149 -- Right hand sides that are constructors
1152 --- ...(let w = C same-args in ...)...
1153 -- Then use v instead of w. This may save
1154 -- re-constructing an existing constructor.
1155 completeNonRec env binder new_id rhs@(Con con con_args)
1156 | switchIsSet env SimplReuseCon &&
1157 maybeToBool maybe_existing_con &&
1158 not (isExported new_id) -- Don't bother for exported things
1159 -- because we won't be able to drop
1161 = tick ConReused `thenSmpl_`
1162 returnSmpl (extendIdEnvWithAtom env binder (VarArg it), [NonRec new_id rhs])
1164 maybe_existing_con = lookForConstructor env con con_args
1165 Just it = maybe_existing_con
1169 -- Check for atomic right-hand sides.
1170 -- We used to have a "tick AtomicRhs" in here, but it causes more trouble
1171 -- than it's worth. For a top-level binding a = b, where a is exported,
1172 -- we can't drop the binding, so we get repeated AtomicRhs ticks
1173 completeNonRec env binder@(id,occ_info) new_id new_rhs
1174 | is_atomic eta'd_rhs -- If rhs (after eta reduction) is atomic
1175 = returnSmpl (atomic_env , [NonRec new_id eta'd_rhs])
1177 | otherwise -- Non atomic rhs (don't eta after all)
1178 = returnSmpl (non_atomic_env , [NonRec new_id new_rhs])
1180 atomic_env = extendIdEnvWithAtom env binder the_arg
1182 non_atomic_env = extendEnvGivenBinding (extendIdEnvWithClone env binder new_id)
1183 occ_info new_id new_rhs
1185 eta'd_rhs = etaCoreExpr new_rhs
1186 the_arg = case eta'd_rhs of
1193 floatBind :: SimplEnv
1194 -> Bool -- True <=> Top level
1196 -> SmplM [InBinding]
1198 floatBind env top_level bind
1204 = tickN LetFloatFromLet n_extras `thenSmpl_`
1205 -- It's important to increment the tick counts if we
1206 -- do any floating. A situation where this turns out
1207 -- to be important is this:
1208 -- Float in produces:
1209 -- letrec x = let y = Ey in Ex
1211 -- Now floating gives this:
1215 --- We now want to iterate once more in case Ey doesn't
1216 -- mention x, in which case the y binding can be pulled
1217 -- out as an enclosing let(rec), which in turn gives
1218 -- the strictness analyser more chance.
1222 (binds', _, n_extras) = fltBind bind
1224 float_lets = switchIsSet env SimplFloatLetsExposingWHNF
1225 always_float_let_from_let = switchIsSet env SimplAlwaysFloatLetsFromLets
1227 -- fltBind guarantees not to return leaky floats
1228 -- and all the binders of the floats have had their demand-info zapped
1229 fltBind (NonRec bndr rhs)
1230 = (binds ++ [NonRec (un_demandify bndr) rhs'],
1234 (binds, rhs') = fltRhs rhs
1239 binders `zip` rhss')],
1240 and (zipWith leakFree binders rhss'),
1245 (binders, rhss) = unzip pairs
1246 (binds_s, rhss') = mapAndUnzip fltRhs rhss
1247 extras = concat (map get_pairs (concat binds_s))
1249 get_pairs (NonRec bndr rhs) = [(bndr,rhs)]
1250 get_pairs (Rec pairs) = pairs
1252 -- fltRhs has same invariant as fltBind
1254 | (always_float_let_from_let ||
1255 floatExposesHNF True False False rhs)
1262 -- fltExpr has same invariant as fltBind
1263 fltExpr (Let bind body)
1264 | not top_level || binds_wont_leak
1265 -- fltExpr guarantees not to return leaky floats
1266 = (binds' ++ body_binds, body')
1268 (body_binds, body') = fltExpr body
1269 (binds', binds_wont_leak, _) = fltBind bind
1271 fltExpr expr = ([], expr)
1273 -- Crude but effective
1274 leakFree (id,_) rhs = case getIdArity id of
1275 ArityAtLeast n | n > 0 -> True
1276 ArityExactly n | n > 0 -> True
1277 other -> whnfOrBottom rhs
1281 %************************************************************************
1283 \subsection[Simplify-atoms]{Simplifying atoms}
1285 %************************************************************************
1288 simplArg :: SimplEnv -> InArg -> Eager ans OutArg
1290 simplArg env (LitArg lit) = returnEager (LitArg lit)
1291 simplArg env (TyArg ty) = simplTy env ty `appEager` \ ty' ->
1292 returnEager (TyArg ty')
1293 simplArg env (VarArg id) = lookupId env id
1296 %************************************************************************
1298 \subsection[Simplify-quickies]{Some local help functions}
1300 %************************************************************************
1304 -- fix_up_demandedness switches off the willBeDemanded Info field
1305 -- for bindings floated out of a non-demanded let
1306 fix_up_demandedness True {- Will be demanded -} bind
1307 = bind -- Simple; no change to demand info needed
1308 fix_up_demandedness False {- May not be demanded -} (NonRec binder rhs)
1309 = NonRec (un_demandify binder) rhs
1310 fix_up_demandedness False {- May not be demanded -} (Rec pairs)
1311 = Rec [(un_demandify binder, rhs) | (binder,rhs) <- pairs]
1313 un_demandify (id, occ_info) = (id `addIdDemandInfo` noDemandInfo, occ_info)
1315 is_cheap_prim_app (Prim op _) = primOpOkForSpeculation op
1316 is_cheap_prim_app other = False
1318 computeResultType :: SimplEnv -> InType -> [OutArg] -> OutType
1319 computeResultType env expr_ty orig_args
1320 = simplTy env expr_ty `appEager` \ expr_ty' ->
1323 go ty (TyArg ty_arg : args) = go (mkAppTy ty ty_arg) args
1324 go ty (a:args) | isValArg a = case (getFunTy_maybe ty) of
1325 Just (_, res_ty) -> go res_ty args
1327 pprPanic "computeResultType" (vcat [
1328 ppr PprDebug (a:args),
1329 ppr PprDebug orig_args,
1330 ppr PprDebug expr_ty',
1333 go expr_ty' orig_args
1336 var `withArity` UnknownArity = var
1337 var `withArity` arity = var `addIdArity` arity
1339 is_atomic (Var v) = True
1340 is_atomic (Lit l) = not (isNoRepLit l)
1341 is_atomic other = False