Changes between Version 2 and Version 3 of Commentary/Compiler/OptOrdering


Ignore:
Timestamp:
Oct 20, 2011 4:50:40 PM (4 years ago)
Author:
simonpj
Comment:

--

Legend:

Unmodified
Added
Removed
Modified
  • Commentary/Compiler/OptOrdering

    v2 v3  
    11= Ordering the compiler's passes =
    22
     3This page has notes about the ordering of optimisation phases.
     4
    35'''NOTE:''' This is old documentation and may not be very relevant any more!
    4 
    5 
    6 == Change notes ==
    7  * '''1  Nov 94:''' if float-out is done after strictness, remember to switch off demandedness flags on floated bindings!
    8  * '''13 Oct 94:''' Run Float Inwards once more after strictness-simplify [andre]
    9  * '''4 Oct 94:''' Do simplification between float-in and strictness [andre], Ignore-inline-pragmas flag for final simplification [andre]
    10  * '''Aug 94:'''        Original: Simon, Andy, Andre
    116
    127== This ordering obeys all the constraints except (5) ==
     
    2419== Constraints ==
    2520
    26 1. float-in before strictness.
     21=== 1. float-in before strictness ===
    2722Reason: floating inwards moves definitions inwards to a site at which
    2823the binding might well be strict.
    29 
     24{{{
    3025Example         let x = ... in
    3126                    y = x+1
     
    3530                let y = let x = ... in x+1
    3631                in ...
    37 
     32}}}
    3833The strictness analyser will do a better job of the latter
    3934than the former.
    4035
    41 2. Don't simplify between float-in and strictness,
    42 unless you disable float-let-out-of-let, otherwise
     36=== 2. Don't simplify between float-in and strictness ===
     37
     38...unless you disable float-let-out-of-let, otherwise
    4339the simiplifier's local floating might undo some
    4440useful floating-in.
    45 
     41{{{
    4642Example         let f = let y = .. in \x-> x+y
    4743                in ...
     
    5046                    f = \x -> x+y
    5147                in ...
    52 
     48}}}
    5349This is a bad move, because now y isn't strict.
    5450In the pre-float case, the binding for y is strict.
     
    5652it's easy to disable float-let-from-let.
    5753
    58 3. Want full-laziness before foldr/build. 
     54=== 3. Want full-laziness before foldr/build ===
     55
    5956Reason: Give priority to sharing rather than deforestation.
    60 
     57{{{
    6158Example         \z -> let xs = build g
    6259                      in foldr k z xs
     
    6461                let xs = build g
    6562                in \x -> foldr k z xs
    66 
     63}}}
    6764In the post-full-laziness case, xs is shared between all
    6865applications of the function.   If we did foldr/build
    6966first, we'd have got
    70 
     67{{{
    7168                \z -> g k z
    72 
     69}}}
    7370and now we can't share xs.
    7471
    7572
    76 4.  Want strictness after foldr/build.
     73=== 4.  Want strictness after foldr/build ===
    7774Reason: foldr/build makes new function definitions which
    7875can benefit from strictness analysis.
    79 
     76{{{
    8077Example:        sum [1..10]
    8178===> (f/b)
    8279                let g x a | x > 10    = a
    8380                          | otherwise = g (x+1) (a+x)
    84 
     81}}}
    8582Here we clearly want to get strictness analysis on g.
    8683
    8784
    88 5.  Want full laziness after strictness
     85=== 5.  Want full laziness after strictness ===
    8986Reason: absence may allow something to be floated out
    9087which would not otherwise be.
    91 
     88{{{
    9289Example         \z -> let x = f (a,z) in ...
    9390===> (absence anal + inline wrapper of f)
     
    9592===> (full laziness)
    9693                let x= f.wrk a in  \z -> ...
    97 
     94}}}
    9895TOO BAD.  This doesn't look a common case to me.
    9996
    10097
    101 6. Want float-in after foldr/build.
     98=== 6. Want float-in after foldr/build  ===
     99
    102100Reason: Desugaring list comprehensions + foldr/build
    103101gives rise to new float-in opportunities.
    104 
     102{{{
    105103Example         ...some list comp...
    106104==> (foldr/build)
     
    114112                  [] -> h xs
    115113                  (y:ys) -> ...(t v)...
    116 
     114}}}
    117115Now v could usefully be floated into the second branch.
    118116
    119 7. Want simplify after float-inwards.
    120 [Occurred in the prelude, compiling ITup2.hs, function dfun.Ord.(*,*)]
     117=== 7. Want simplify after float-inwards ===
     118
     119(Occurred in the prelude, compiling `ITup2.hs`, function `dfun.Ord.(*,*)`)
    121120This is due to the following (that happens with dictionaries):
    122 
     121{{{
    123122let a1 = case v of (a,b) -> a
    124123in let m1 = \ c -> case c of I# c# -> case c# of 1 -> a1 5
     
    128127                                             in m1 cc
    129128   in (m1,m2)
    130 
     129}}}
    131130floating inwards will push the definition of a1 into m1 (supposing
    132131it is only used there):
    133 
     132{{{
    134133in let m1 = let a1 = case v of (a,b) -> a
    135134            in \ c -> case c of I# c# -> case c# of 1 -> a1 5
     
    139138                                             in m1 cc
    140139   in (m1,m2)
    141 
     140}}}
    142141if we do strictness analysis now we will not get a worker-wrapper
    143142for m1, because of the "let a1 ..." (notice that a1 is not strict in
     
    161160The only way of having the best of both is if we have the worker/wrapper
    162161pass explicitly called, and then we could do with
    163 
    164 float-in
    165 strictness analysis
    166 simplify
    167 strictness analysis
    168 worker-wrapper generation
    169 
     162 * float-in
     163 * strictness analysis
     164 * simplify
     165 * strictness analysis
     166 * worker-wrapper generation
    170167as we would
    171 a) be able to detect the strictness of m1 after the
    172    first call to the strictness analyser, and exploit it with the simplifier
    173    (in case it was strict).
    174 b) after the call to the simplifier (if m1 was not demanded)
    175    it would be floated out just like we currently do, before stricness
    176    analysis II and worker/wrapperisation.
     168 * 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).
     169 * 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.
    177170
    178171The reason to not do worker/wrapperisation twice is to avoid
     
    180173
    181174
    182 8.  If full laziness is ever done after strictness, remember to switch off
     175=== 8.  If full laziness is ever done after strictness ===
     176
     177...remember to switch off
    183178demandedness flags on floated bindings!  This isn't done at the moment.
    184179
    185 
    186 == Ignore-inline-pragmas flag for final simplification ==
     180=== 9. Ignore-inline-pragmas flag for final simplification ===
    187181
    188182[Occurred in the prelude, compiling ITup2.hs, function dfun.Ord.(*,*)]
     
    190184worker/wrappers for functions but the wrappers are never
    191185inlined. In dictionaries we often have
    192 
     186{{{
    193187dict = let f1 = ...
    194188           f2 = ...
    195189           ...
    196190       in (f1,f2,...)
    197 
     191}}}
    198192and if we create worker/wrappers for f1,...,fn the wrappers will not
    199193be inlined anywhere, and we will have ended up with extra
     
    211205the only occurrence of the worker etc.).
    212206
    213 == Run Float Inwards once more after strictness-simplify ==
    214 
    215 [Occurred in the prelude, compiling IInt.hs, function const.Int.index.wrk]
     207=== 10. Run Float Inwards once more after strictness-simplify ===
     208
     209[Occurred in the prelude, compiling `IInt.hs`, function `const.Int.index.wrk`]
    216210When workers are generated after strictness analysis (worker/wrapper),
    217211we generate them with "reboxing" lets, that simply reboxes the unboxed
    218212arguments, as it may be the case that the worker will need the
    219213original boxed value:
    220 
     214{{{
    221215f x y = case x of
    222216          (a,b) -> case y of
     
    236230                        True -> (x,x)
    237231                        False -> ((1,1),(2,2))
    238 
     232}}}
    239233in this case the simplifier will remove the binding for y as it is not
    240234used (we expected this to happen very often, but we do not know how