+ ProxyEnv
+%* *
+%************************************************************************
+
+\begin{code}
+data ProxyEnv
+ = PE (IdEnv (Id, [(Id,CoercionI)])) VarSet
+ -- Main env, and its free variables (of both range and domain)
+\end{code}
+
+Note [ProxyEnv]
+~~~~~~~~~~~~~~~
+The ProxyEnv keeps track of the connection between case binders and
+scrutinee. Specifically, if
+ sc |-> (sc, [...(cb, co)...])
+is a binding in the ProxyEnv, then
+ cb = sc |> coi
+Typically we add such a binding when encountering the case expression
+ case (sc |> coi) of cb { ... }
+
+Things to note:
+ * The domain of the ProxyEnv is the variable (or casted variable)
+ scrutinees of enclosing cases. This is additionally used
+ to ensure we gather occurrence info even for GlobalId scrutinees;
+ see Note [Binder swap for GlobalId scrutinee]
+
+ * The ProxyEnv is just an optimisation; you can throw away any
+ element without losing correctness. And we do so when pushing
+ it inside a binding (see trimProxyEnv).
+
+ * Once scrutinee might map to many case binders: Eg
+ case sc of cb1 { DEFAULT -> ....case sc of cb2 { ... } .. }
+
+INVARIANTS
+ * If sc1 |-> (sc2, [...(cb, co)...]), then sc1==sc2
+ It's a UniqFM and we sometimes need the domain Id
+
+ * Any particular case binder 'cb' occurs only once in entire range
+
+ * No loops
+
+The Main Reason for having a ProxyEnv is so that when we encounter
+ case e of cb { pi -> ri }
+we can find all the in-scope variables derivable from 'cb',
+and effectively add let-bindings for them thus:
+ case e of cb { pi -> let { x = ..cb..; y = ...cb.. }
+ in ri }
+The function getProxies finds these bindings; then we
+add just the necessary ones, using wrapProxy.
+
+More info under Note [Binder swap]
+
+Note [Binder swap]
+~~~~~~~~~~~~~~~~~~
+We do these two transformations right here:
+
+ (1) case x of b { pi -> ri }
+ ==>
+ case x of b { pi -> let x=b in ri }
+
+ (2) case (x |> co) of b { pi -> ri }
+ ==>
+ case (x |> co) of b { pi -> let x = b |> sym co in ri }
+
+ Why (2)? See Note [Case of cast]
+
+In both cases, in a particular alternative (pi -> ri), we only
+add the binding if
+ (a) x occurs free in (pi -> ri)
+ (ie it occurs in ri, but is not bound in pi)
+ (b) the pi does not bind b (or the free vars of co)
+We need (a) and (b) for the inserted binding to be correct.
+
+For the alternatives where we inject the binding, we can transfer
+all x's OccInfo to b. And that is the point.
+
+Notice that
+ * The deliberate shadowing of 'x'.
+ * That (a) rapidly becomes false, so no bindings are injected.
+
+The reason for doing these transformations here is because it allows
+us to adjust the OccInfo for 'x' and 'b' as we go.
+
+ * Suppose the only occurrences of 'x' are the scrutinee and in the
+ ri; then this transformation makes it occur just once, and hence
+ get inlined right away.
+
+ * If we do this in the Simplifier, we don't know whether 'x' is used
+ in ri, so we are forced to pessimistically zap b's OccInfo even
+ though it is typically dead (ie neither it nor x appear in the
+ ri). There's nothing actually wrong with zapping it, except that
+ it's kind of nice to know which variables are dead. My nose
+ tells me to keep this information as robustly as possible.
+
+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 [Case of cast]
+~~~~~~~~~~~~~~~~~~~
+Consider case (x `cast` co) of b { I# ->
+ ... (case (x `cast` co) of {...}) ...
+We'd like to eliminate the inner case. That is the motivation for
+equation (2) in Note [Binder swap]. When we get to the inner case, we
+inline x, cancel the casts, and away we go.
+
+Note [Binder swap on GlobalId scrutinees]
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+When the scrutinee is a GlobalId we must take care in two ways
+
+ i) In order to *know* whether 'x' occurs free in the RHS, we need its
+ occurrence info. BUT, we don't gather occurrence info for
+ GlobalIds. That's one use for the (small) occ_proxy env in OccEnv is
+ for: it says "gather occurrence info for these.
+
+ ii) We must call localiseId on 'x' first, in case it's a GlobalId, or
+ has an External Name. See, for example, SimplEnv Note [Global Ids in
+ the substitution].
+
+Note [getProxies is subtle]
+~~~~~~~~~~~~~~~~~~~~~~~~~~~
+The code for getProxies isn't all that obvious. Consider
+
+ case v |> cov of x { DEFAULT ->
+ case x |> cox1 of y { DEFAULT ->
+ case x |> cox2 of z { DEFAULT -> r
+
+These will give us a ProxyEnv looking like:
+ x |-> (x, [(y, cox1), (z, cox2)])
+ v |-> (v, [(x, cov)])
+
+From this we want to extract the bindings
+ x = z |> sym cox2
+ v = x |> sym cov
+ y = x |> cox1
+
+Notice that later bindings may mention earlier ones, and that
+we need to go "both ways".
+
+Historical note [no-case-of-case]
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+We *used* to suppress the binder-swap in case expressions 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.
+
+\begin{code}
+extendProxyEnv :: ProxyEnv -> Id -> CoercionI -> Id -> ProxyEnv
+-- (extendPE x co y) typically arises from
+-- case (x |> co) of y { ... }
+-- It extends the proxy env with the binding
+-- y = x |> co
+extendProxyEnv pe scrut co case_bndr
+ | scrut == case_bndr = PE env1 fvs1 -- If case_bndr shadows scrut,
+ | otherwise = PE env2 fvs2 -- don't extend
+ where
+ PE env1 fvs1 = trimProxyEnv pe [case_bndr]
+ env2 = extendVarEnv_Acc add single env1 scrut1 (case_bndr,co)
+ single cb_co = (scrut1, [cb_co])
+ add cb_co (x, cb_cos) = (x, cb_co:cb_cos)
+ fvs2 = fvs1 `unionVarSet` freeVarsCoI co
+ `extendVarSet` case_bndr
+ `extendVarSet` scrut1
+
+ scrut1 = mkLocalId (localiseName (idName scrut)) (idType scrut)
+ -- Localise the scrut_var before shadowing it; we're making a
+ -- new binding for it, and it might have an External Name, or
+ -- even be a GlobalId; Note [Binder swap on GlobalId scrutinees]
+ -- Also we don't want any INLILNE or NOINLINE pragmas!
+
+-----------
+type ProxyBind = (Id, Id, CoercionI)
+
+getProxies :: OccEnv -> Id -> Bag ProxyBind
+-- Return a bunch of bindings [...(xi,ei)...]
+-- such that let { ...; xi=ei; ... } binds the xi using y alone
+-- See Note [getProxies is subtle]
+getProxies (OccEnv { occ_proxy = PE pe _ }) case_bndr
+ = -- pprTrace "wrapProxies" (ppr case_bndr) $
+ go_fwd case_bndr
+ where
+ fwd_pe :: IdEnv (Id, CoercionI)
+ fwd_pe = foldVarEnv add1 emptyVarEnv pe
+ where
+ add1 (x,ycos) env = foldr (add2 x) env ycos
+ add2 x (y,co) env = extendVarEnv env y (x,co)
+
+ go_fwd :: Id -> Bag ProxyBind
+ -- Return bindings derivable from case_bndr
+ go_fwd case_bndr = -- pprTrace "go_fwd" (vcat [ppr case_bndr, text "fwd_pe =" <+> ppr fwd_pe,
+ -- text "pe =" <+> ppr pe]) $
+ go_fwd' case_bndr
+
+ go_fwd' case_bndr
+ | Just (scrut, co) <- lookupVarEnv fwd_pe case_bndr
+ = unitBag (scrut, case_bndr, mkSymCoI co)
+ `unionBags` go_fwd scrut
+ `unionBags` go_bwd scrut [pr | pr@(cb,_) <- lookup_bwd scrut
+ , cb /= case_bndr]
+ | otherwise
+ = emptyBag
+
+ lookup_bwd :: Id -> [(Id, CoercionI)]
+ -- Return case_bndrs that are connected to scrut
+ lookup_bwd scrut = case lookupVarEnv pe scrut of
+ Nothing -> []
+ Just (_, cb_cos) -> cb_cos
+
+ go_bwd :: Id -> [(Id, CoercionI)] -> Bag ProxyBind
+ go_bwd scrut cb_cos = foldr (unionBags . go_bwd1 scrut) emptyBag cb_cos
+
+ go_bwd1 :: Id -> (Id, CoercionI) -> Bag ProxyBind
+ go_bwd1 scrut (case_bndr, co)
+ = -- pprTrace "go_bwd1" (ppr case_bndr) $
+ unitBag (case_bndr, scrut, co)
+ `unionBags` go_bwd case_bndr (lookup_bwd case_bndr)
+
+-----------
+mkAltEnv :: OccEnv -> CoreExpr -> Id -> OccEnv
+-- Does two things: a) makes the occ_ctxt = OccVanilla
+-- b) extends the ProxyEnv if possible
+mkAltEnv env scrut cb
+ = env { occ_encl = OccVanilla, occ_proxy = pe' }
+ where
+ pe = occ_proxy env
+ pe' = case scrut of
+ Var v -> extendProxyEnv pe v (IdCo (idType v)) cb
+ Cast (Var v) co -> extendProxyEnv pe v (ACo co) cb
+ _other -> trimProxyEnv pe [cb]
+
+-----------
+trimOccEnv :: OccEnv -> [CoreBndr] -> OccEnv
+trimOccEnv env bndrs = env { occ_proxy = trimProxyEnv (occ_proxy env) bndrs }
+
+-----------
+trimProxyEnv :: ProxyEnv -> [CoreBndr] -> ProxyEnv
+-- We are about to push this ProxyEnv inside a binding for 'bndrs'
+-- So dump any ProxyEnv bindings which mention any of the bndrs
+trimProxyEnv (PE pe fvs) bndrs
+ | not (bndr_set `intersectsVarSet` fvs)
+ = PE pe fvs
+ | otherwise
+ = PE pe' (fvs `minusVarSet` bndr_set)
+ where
+ pe' = mapVarEnv trim pe
+ bndr_set = mkVarSet bndrs
+ trim (scrut, cb_cos) | scrut `elemVarSet` bndr_set = (scrut, [])
+ | otherwise = (scrut, filterOut discard cb_cos)
+ discard (cb,co) = bndr_set `intersectsVarSet`
+ extendVarSet (freeVarsCoI co) cb
+
+-----------
+freeVarsCoI :: CoercionI -> VarSet
+freeVarsCoI (IdCo t) = tyVarsOfType t
+freeVarsCoI (ACo co) = tyVarsOfType co
+\end{code}
+
+
+%************************************************************************
+%* *
projects / ghc-hetmet.git / blobdiff