X-Git-Url: http://git.megacz.com/?a=blobdiff_plain;ds=sidebyside;f=compiler%2FsimplCore%2FOccurAnal.lhs;h=c5f323ed779c829c1bfca6ec6699527646a7c583;hb=4bc25e8c30559b7a6a87b39afcc79340ae778788;hp=b92239e5e4b26e03393ce550f50f2f5c8ff9b377;hpb=ac7db825a40d6b4e582a9b33969a1b0d5de9b3f6;p=ghc-hetmet.git diff --git a/compiler/simplCore/OccurAnal.lhs b/compiler/simplCore/OccurAnal.lhs index b92239e..c5f323e 100644 --- a/compiler/simplCore/OccurAnal.lhs +++ b/compiler/simplCore/OccurAnal.lhs @@ -171,8 +171,8 @@ However things are made quite a bit more complicated by RULES. Remember ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ We avoid infinite inlinings by choosing loop breakers, and ensuring that a loop breaker cuts each loop. But what is a - "loop"? In particular, a RULES is like an equation for 'f' that - is *always* inlined if it are applicable. We do *not* disable + "loop"? In particular, a RULE is like an equation for 'f' that + is *always* inlined if it is applicable. We do *not* disable rules for loop-breakers. It's up to whoever makes the rules to make sure that the rules themselves alwasys terminate. See Note [Rules for recursive functions] in Simplify.lhs @@ -237,8 +237,9 @@ However things are made quite a bit more complicated by RULES. Remember * Note [Rule dependency info] ~~~~~~~~~~~~~~~~~~~~~~~~~~~ The VarSet in a SpecInfo is used for dependency analysis in the - occurrence analyser. We must track free vars in *both* lhs and rhs. Why both? - Consider + occurrence analyser. We must track free vars in *both* lhs and rhs. + Hence use of idRuleVars, rather than idRuleRhsVars in addRuleUsage. + Why both? Consider x = y RULE f x = 4 Then if we substitute y for x, we'd better do so in the @@ -509,7 +510,7 @@ reOrderCycle (bind : binds) -- bad choice for loop breaker | is_con_app rhs = 3 -- Data types help with cases - -- Note [conapp] + -- Note [Constructor applictions] -- If an Id is marked "never inline" then it makes a great loop breaker -- The only reason for not checking that here is that it is rare @@ -560,22 +561,24 @@ reOrderCycle (bind : binds) is_con_app _ = False makeLoopBreaker :: Bool -> Id -> Id --- Set the loop-breaker flag --- See Note [Weak loop breakers] +-- Set the loop-breaker flag: see Note [Weak loop breakers] makeLoopBreaker weak bndr = setIdOccInfo bndr (IAmALoopBreaker weak) \end{code} -Note [Worker inline loop] -~~~~~~~~~~~~~~~~~~~~~~~~ -Never choose a wrapper as the loop breaker! Because -wrappers get auto-generated inlinings when importing, and -that can lead to an infinite inlining loop. For example: +Note [INLINE pragmas] +~~~~~~~~~~~~~~~~~~~~~ +Never choose a function with an INLINE pramga as the loop breaker! +If such a function is mutually-recursive with a non-INLINE thing, +then the latter should be the loop-breaker. + +A particular case is wrappers generated by the demand analyser. +If you make then into a loop breaker you may get an infinite +inlining loop. For example: rec { $wfoo x = ....foo x.... {-loop brk-} foo x = ...$wfoo x... } - The interface file sees the unfolding for $wfoo, and sees that foo is strict (and hence it gets an auto-generated wrapper). Result: an infinite inlining in the importing scope. So be a bit careful if you @@ -584,6 +587,22 @@ nofib/spectral/minimax. If the repTree wrapper is chosen as the loop breaker then compiling Game.hs goes into an infinite loop (this happened when we gave is_con_app a lower score than inline candidates). +Note [Constructor applications] +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ +It's really really important to inline dictionaries. Real +example (the Enum Ordering instance from GHC.Base): + + rec f = \ x -> case d of (p,q,r) -> p x + g = \ x -> case d of (p,q,r) -> q x + d = (v, f, g) + +Here, f and g occur just once; but we can't inline them into d. +On the other hand we *could* simplify those case expressions if +we didn't stupidly choose d as the loop breaker. +But we won't because constructor args are marked "Many". +Inlining dictionaries is really essential to unravelling +the loops in static numeric dictionaries, see GHC.Float. + Note [Closure conversion] ~~~~~~~~~~~~~~~~~~~~~~~~~ We treat (\x. C p q) as a high-score candidate in the letrec scoring algorithm. @@ -657,10 +676,14 @@ addRuleUsage :: UsageDetails -> Id -> UsageDetails -- Add the usage from RULES in Id to the usage addRuleUsage usage id = foldVarSet add usage (idRuleVars id) + -- idRuleVars here: see Note [Rule dependency info] where - add v u = addOneOcc u v NoOccInfo -- Give a non-committal binder info - -- (i.e manyOcc) because many copies - -- of the specialised thing can appear + add v u = addOneOcc u v NoOccInfo + -- Give a non-committal binder info (i.e manyOcc) because + -- a) Many copies of the specialised thing can appear + -- b) We don't want to substitute a BIG expression inside a RULE + -- even if that's the only occurrence of the thing + -- (Same goes for INLINE.) \end{code} Expressions @@ -841,7 +864,7 @@ occAnalApp env (Var fun, args) where fun_uniq = idUnique fun fun_uds = mkOneOcc env fun (valArgCount args > 0) - is_pap = isDataConWorkId fun || valArgCount args < idArity fun + is_pap = isConLikeId fun || valArgCount args < idArity fun -- Hack for build, fold, runST args_stuff | fun_uniq == buildIdKey = appSpecial env 2 [True,True] args @@ -957,6 +980,16 @@ us to adjust the OccInfo for 'x' and 'b' as we go. The Maybe (Id,CoreExpr) passed to occAnalAlt is the extra let-binding {x=b}; it's Nothing if the binder-swap doesn't happen. +There is a danger though. Consider + let v = x +# y + in case (f v) of w -> ...v...v... +And suppose that (f v) expands to just v. Then we'd like to +use 'w' instead of 'v' in the alternative. But it may be too +late; we may have substituted the (cheap) x+#y for v in the +same simplifier pass that reduced (f v) to v. + +I think this is just too bad. CSE will recover some of it. + Note [Binder swap on GlobalId scrutinees] ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ When the scrutinee is a GlobalId we must take care in two ways @@ -970,6 +1003,67 @@ When the scrutinee is a GlobalId we must take care in two ways has an External Name. See, for example, SimplEnv Note [Global Ids in the substitution]. +Historical note [no-case-of-case] +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ +We *used* to suppress the binder-swap in case expressoins when +-fno-case-of-case is on. Old remarks: + "This happens in the first simplifier pass, + and enhances full laziness. Here's the bad case: + f = \ y -> ...(case x of I# v -> ...(case x of ...) ... ) + If we eliminate the inner case, we trap it inside the I# v -> arm, + which might prevent some full laziness happening. I've seen this + in action in spectral/cichelli/Prog.hs: + [(m,n) | m <- [1..max], n <- [1..max]] + Hence the check for NoCaseOfCase." +However, now the full-laziness pass itself reverses the binder-swap, so this +check is no longer necessary. + +Historical note [Suppressing the case binder-swap] +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ +This old note describes a problem that is also fixed by doing the +binder-swap in OccAnal: + + There is another situation when it might make sense to suppress the + case-expression binde-swap. If we have + + case x of w1 { DEFAULT -> case x of w2 { A -> e1; B -> e2 } + ...other cases .... } + + We'll perform the binder-swap for the outer case, giving + + case x of w1 { DEFAULT -> case w1 of w2 { A -> e1; B -> e2 } + ...other cases .... } + + But there is no point in doing it for the inner case, because w1 can't + be inlined anyway. Furthermore, doing the case-swapping involves + zapping w2's occurrence info (see paragraphs that follow), and that + forces us to bind w2 when doing case merging. So we get + + case x of w1 { A -> let w2 = w1 in e1 + B -> let w2 = w1 in e2 + ...other cases .... } + + This is plain silly in the common case where w2 is dead. + + Even so, I can't see a good way to implement this idea. I tried + not doing the binder-swap if the scrutinee was already evaluated + but that failed big-time: + + data T = MkT !Int + + case v of w { MkT x -> + case x of x1 { I# y1 -> + case x of x2 { I# y2 -> ... + + Notice that because MkT is strict, x is marked "evaluated". But to + eliminate the last case, we must either make sure that x (as well as + x1) has unfolding MkT y1. THe straightforward thing to do is to do + the binder-swap. So this whole note is a no-op. + +It's fixed by doing the binder-swap in OccAnal because we can do the +binder-swap unconditionally and still get occurrence analysis +information right. + Note [Case of cast] ~~~~~~~~~~~~~~~~~~~ Consider case (x `cast` co) of b { I# ->