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