+++ /dev/null
- Ordering the compiler's passes
- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
-
-Change notes
-~~~~~~~~~~~~
-1 Nov 94 * NB: if float-out is done after strictness, remember to
- switch off demandedness flags on floated bindings!
-13 Oct 94 * Run Float Inwards once more after strictness-simplify [andre]
- 4 Oct 94 * Do simplification between float-in and strictness [andre]
- * Ignore-inline-pragmas flag for final simplification [andre]
-
-Aug 94 Original: Simon, Andy, Andre
-
-
-
-
-This ordering obeys all the constraints except (5)
-~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
-
- full laziness
- simplify with foldr/build
- float-in
- simplify
- strictness
- float-in
-
-[check FFT2 still gets benefits with this ordering]
-
-=================================
- Constraints
-=================================
-
-1. float-in before strictness.
-Reason: floating inwards moves definitions inwards to a site at which
-the binding might well be strict.
-
-Example let x = ... in
- y = x+1
- in
- ...
-===>
- let y = let x = ... in x+1
- in ...
-
-The strictness analyser will do a better job of the latter
-than the former.
-
-2. Don't simplify between float-in and strictness,
-unless you disable float-let-out-of-let, otherwise
-the simiplifier's local floating might undo some
-useful floating-in.
-
-Example let f = let y = .. in \x-> x+y
- in ...
-===>
- let y = ...
- f = \x -> x+y
- in ...
-
-This is a bad move, because now y isn't strict.
-In the pre-float case, the binding for y is strict.
-Mind you, this isn't a very common case, and
-it's easy to disable float-let-from-let.
-
-3. Want full-laziness before foldr/build.
-Reason: Give priority to sharing rather than deforestation.
-
-Example \z -> let xs = build g
- in foldr k z xs
-===>
- let xs = build g
- in \x -> foldr k z xs
-
-In the post-full-laziness case, xs is shared between all
-applications of the function. If we did foldr/build
-first, we'd have got
-
- \z -> g k z
-
-and now we can't share xs.
-
-
-4. Want strictness after foldr/build.
-Reason: foldr/build makes new function definitions which
-can benefit from strictness analysis.
-
-Example: sum [1..10]
-===> (f/b)
- let g x a | x > 10 = a
- | otherwise = g (x+1) (a+x)
-
-Here we clearly want to get strictness analysis on g.
-
-
-5. Want full laziness after strictness
-Reason: absence may allow something to be floated out
-which would not otherwise be.
-
-Example \z -> let x = f (a,z) in ...
-===> (absence anal + inline wrapper of f)
- \z -> let x = f.wrk a in ...
-===> (full laziness)
- let x= f.wrk a in \z -> ...
-
-TOO BAD. This doesn't look a common case to me.
-
-
-6. Want float-in after foldr/build.
-Reason: Desugaring list comprehensions + foldr/build
-gives rise to new float-in opportunities.
-
-Example ...some list comp...
-==> (foldr/build)
- let v = h xs in
- case ... of
- [] -> v
- (y:ys) -> ...(t v)...
-==> (simplifier)
- let v = h xs in
- case ... of
- [] -> h xs
- (y:ys) -> ...(t v)...
-
-Now v could usefully be floated into the second branch.
-
-7. Want simplify after float-inwards.
-[Occurred in the prelude, compiling ITup2.hs, function dfun.Ord.(*,*)]
-This is due to the following (that happens with dictionaries):
-
-let a1 = case v of (a,b) -> a
-in let m1 = \ c -> case c of I# c# -> case c# of 1 -> a1 5
- 2 -> 6
-in let m2 = \ c -> case c of I# c# ->
- case c# +# 1# of cc# -> let cc = I# cc#
- in m1 cc
- in (m1,m2)
-
-floating inwards will push the definition of a1 into m1 (supposing
-it is only used there):
-
-in let m1 = let a1 = case v of (a,b) -> a
- in \ c -> case c of I# c# -> case c# of 1 -> a1 5
- 2 -> 6
-in let m2 = \ c -> case c of I# c# ->
- case c# +# 1# of cc# -> let cc = I# cc#
- in m1 cc
- in (m1,m2)
-
-if we do strictness analysis now we will not get a worker-wrapper
-for m1, because of the "let a1 ..." (notice that a1 is not strict in
-its body).
-
-Not having this worker wrapper might be very bad, because it might
-mean that we will have to rebox arguments to m1 if they are
-already unboxed, generating extra allocations, as occurs with m2 (cc)
-above.
-
-To solve this problem we have decided to run the simplifier after
-float-inwards, so that lets whose body is a HNF are floated out,
-undoing the float-inwards transformation in these cases.
-We are then back to the original code, which would have a worker-wrapper
-for m1 after strictness analysis and would avoid the extra let in m2.
-
-What we lose in this case are the opportunities for case-floating
-that could be presented if, for example, a1 would indeed be demanded (strict)
-after the floating inwards.
-
-The only way of having the best of both is if we have the worker/wrapper
-pass explicitly called, and then we could do with
-
-float-in
-strictness analysis
-simplify
-strictness analysis
-worker-wrapper generation
-
-as we would
-a) be able to detect the strictness of m1 after the
- first call to the strictness analyser, and exploit it with the simplifier
- (in case it was strict).
-b) after the call to the simplifier (if m1 was not demanded)
- it would be floated out just like we currently do, before stricness
- analysis II and worker/wrapperisation.
-
-The reason to not do worker/wrapperisation twice is to avoid
-generating wrappers for wrappers which could happen.
-
-
-8. If full laziness is ever done after strictness, remember to switch off
-demandedness flags on floated bindings! This isn't done at the moment.
-
-
-Ignore-inline-pragmas flag for final simplification
-~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
-[Occurred in the prelude, compiling ITup2.hs, function dfun.Ord.(*,*)]
-Sometimes (e.g. in dictionary methods) we generate
-worker/wrappers for functions but the wrappers are never
-inlined. In dictionaries we often have
-
-dict = let f1 = ...
- f2 = ...
- ...
- in (f1,f2,...)
-
-and if we create worker/wrappers for f1,...,fn the wrappers will not
-be inlined anywhere, and we will have ended up with extra
-closures (one for the worker and one for the wrapper) and extra
-function calls, as when we access the dictionary we will be acessing
-the wrapper, which will call the worker.
-The simplifier never inlines workers into wrappers, as the wrappers
-themselves have INLINE pragmas attached to them (so that they are always
-inlined, and we do not know in advance how many times they will be inlined).
-
-To solve this problem, in the last call to the simplifier we will
-ignore these inline pragmas and handle the workers and the wrappers
-as normal definitions. This will allow a worker to be inlined into
-the wrapper if it satisfies all the criteria for inlining (e.g. it is
-the only occurrence of the worker etc.).
-
-Run Float Inwards once more after strictness-simplify
-~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
-[Occurred in the prelude, compiling IInt.hs, function const.Int.index.wrk]
-When workers are generated after strictness analysis (worker/wrapper),
-we generate them with "reboxing" lets, that simply reboxes the unboxed
-arguments, as it may be the case that the worker will need the
-original boxed value:
-
-f x y = case x of
- (a,b) -> case y of
- (c,d) -> case a == c of
- True -> (x,x)
- False -> ((1,1),(2,2))
-
-==> (worker/wrapper)
-
-f_wrapper x y = case x of
- (a,b) -> case y of
- (c,d) -> f_worker a b c d
-
-f_worker a b c d = let x = (a,b)
- y = (c,d)
- in case a == c of
- True -> (x,x)
- False -> ((1,1),(2,2))
-
-in this case the simplifier will remove the binding for y as it is not
-used (we expected this to happen very often, but we do not know how
-many "reboxers" are eventually removed and how many are kept), and
-will keep the binding for x. But notice that x is only used in *one*
-of the branches in the case, but is always being allocated! The
-floating inwards pass would push its definition into the True branch.
-A similar benefit occurs if it is only used inside a let definition.
-These are basically the advantages of floating inwards, but they are
-only exposed after the S.A./worker-wrapperisation of the code! As we
-also have reasons to float inwards before S.A. we have to run it
-twice.
-
projects / ghc-hetmet.git / blobdiff