Simon Jakobi pushed to branch wip/sjakobi/T27115 at Glasgow Haskell Compiler / GHC

Commits:

2 changed files:

Changes:

  • compiler/GHC/Types/Demand.hs
    ... ... @@ -510,7 +510,7 @@ type CardNonOnce = Card
    510 510
     -- | Absent, {0}. Pretty-printed as A.
    
    511 511
     pattern C_00 :: Card
    
    512 512
     pattern C_00 = Card 0b001
    
    513
    --- | Bottom, {}. Pretty-printed as A.
    
    513
    +-- | Bottom, {}. Pretty-printed as B.
    
    514 514
     pattern C_10 :: Card
    
    515 515
     pattern C_10 = Card 0b000
    
    516 516
     -- | Strict and used once, {1}. Pretty-printed as 1.
    
    ... ... @@ -2046,7 +2046,7 @@ gets reached. For example, we don't want to be strict in the strict free
    2046 2046
     variables of 'rhs'.
    
    2047 2047
     
    
    2048 2048
     So we have the simple definition
    
    2049
    -  deferAfterPreciseException = lubDmdType (DmdType emptyDmdEnv [] exnDiv)
    
    2049
    +  deferAfterPreciseException = lubDmdType (DmdType (DE emptyVarEnv exnDiv) [])
    
    2050 2050
     
    
    2051 2051
     Historically, when we had `lubBoxity = _unboxedWins` (see Note [unboxedWins]),
    
    2052 2052
     we had a more complicated definition for deferAfterPreciseException to make sure
    
    ... ... @@ -2054,7 +2054,7 @@ it preserved boxity in its argument. That was needed for code like
    2054 2054
        case <I/O operation> of
    
    2055 2055
           (# s', r) -> f x
    
    2056 2056
     
    
    2057
    -which uses `x` *boxed*. If we `lub`bed it with `(DmdType emptyDmdEnv [] exnDiv)`
    
    2057
    +which uses `x` *boxed*. If we `lub`bed it with `(DmdType (DE emptyVarEnv exnDiv) [])`
    
    2058 2058
     we'd get an *unboxed* demand on `x` (because we let Unboxed win),
    
    2059 2059
     which led to #20746.  Nowadays with `lubBoxity = boxedWins` we don't need
    
    2060 2060
     the complicated definition.
    
    ... ... @@ -2191,12 +2191,12 @@ transformer, namely
    2191 2191
             a single DmdType
    
    2192 2192
     (Nevertheless we dignify DmdSig as a distinct type.)
    
    2193 2193
     
    
    2194
    -The DmdSig for an Id is a semantic thing.  Suppose a function `f` has a DmdSig of
    
    2195
    -  DmdSig (DmdType (fv_dmds,res) [d1..dn])
    
    2194
    +The DmdSig for an Id is a semantic thing. Suppose a function `f` has a DmdSig of
    
    2195
    +  DmdSig (DmdType (DmdEnv fv_dmds div) [d1..dn])
    
    2196 2196
     Here `n` is called the "demand-sig arity" of the DmdSig.  The signature means:
    
    2197 2197
       * If you apply `f` to n arguments (the demand-sig-arity)
    
    2198 2198
       * then you can unleash demands d1..dn on the arguments
    
    2199
    -  * and demands fv_dmds on the free variables.
    
    2199
    +  * and the demands fv_dmds on the free variables.
    
    2200 2200
     Also see Note [Demand type Divergence] for the meaning of a Divergence in a
    
    2201 2201
     demand signature.
    
    2202 2202
     
    
    ... ... @@ -2206,10 +2206,10 @@ demand, used for signature inference. Therefore we place a top demand on all
    2206 2206
     arguments.
    
    2207 2207
     
    
    2208 2208
     For example, the demand transformer described by the demand signature
    
    2209
    -        DmdSig (DmdType {x -> <1L>} <A><1P(L,L)>)
    
    2209
    +        <A><1P(L,L)>{x->1L}
    
    2210 2210
     says that when the function is applied to two arguments, it
    
    2211
    -unleashes demand 1L on the free var x, A on the first arg,
    
    2212
    -and 1P(L,L) on the second.
    
    2211
    +unleashes demand A on the first arg, 1P(L,L) on the second,
    
    2212
    +and 1L on the free var x.
    
    2213 2213
     
    
    2214 2214
     If this same function is applied to one arg, all we can say is that it
    
    2215 2215
     uses x with 1L, and its arg with demand 1P(L,L).
    
    ... ... @@ -2229,10 +2229,10 @@ was evaluated. Here's an example:
    2229 2229
     
    
    2230 2230
     The abstract transformer (let's call it F_e) of the if expression (let's
    
    2231 2231
     call it e) would transform an incoming (undersaturated!) head sub-demand A
    
    2232
    -into a demand type like {x-><1L>,y-><L>}<L>. In pictures:
    
    2232
    +into a demand type like <L>{x->1L,y->L}. In pictures:
    
    2233 2233
     
    
    2234 2234
          SubDemand ---F_e---> DmdType
    
    2235
    -     <A>                  {x-><1L>,y-><L>}<L>
    
    2235
    +     <A>                  <L>{x->1L,y->L}
    
    2236 2236
     
    
    2237 2237
     Let's assume that the demand transformers we compute for an expression are
    
    2238 2238
     correct wrt. to some concrete semantics for Core. How do demand signatures fit
    
    ... ... @@ -2240,7 +2240,7 @@ in? They are strange beasts, given that they come with strict rules when to
    2240 2240
     it's sound to unleash them.
    
    2241 2241
     
    
    2242 2242
     Fortunately, we can formalise the rules with Galois connections. Consider
    
    2243
    -f's strictness signature, {}<1L><L>. It's a single-point approximation of
    
    2243
    +f's strictness signature, <1L><L>. It's a single-point approximation of
    
    2244 2244
     the actual abstract transformer of f's RHS for arity 2. So, what happens is that
    
    2245 2245
     we abstract *once more* from the abstract domain we already are in, replacing
    
    2246 2246
     the incoming Demand by a simple lattice with two elements denoting incoming
    
    ... ... @@ -2260,8 +2260,8 @@ With
    2260 2260
     and F_f being the abstract transformer of f's RHS and f_f being the abstracted
    
    2261 2261
     abstract transformer computable from our demand signature simply by
    
    2262 2262
     
    
    2263
    -  f_f(>=2) = {}<1L><L>
    
    2264
    -  f_f(<2)  = multDmdType C_0N {}<1L><L>
    
    2263
    +  f_f(>=2) = <1L><L>
    
    2264
    +  f_f(<2)  = multDmdType C_0N <1L><L>
    
    2265 2265
     
    
    2266 2266
     where multDmdType makes a proper top element out of the given demand type.
    
    2267 2267
     
    
    ... ... @@ -2283,9 +2283,9 @@ yields a more precise demand type:
    2283 2283
     
    
    2284 2284
         incoming sub-demand   |  demand type
    
    2285 2285
         --------------------------------
    
    2286
    -    P(A)                  |  <L><L>{}
    
    2287
    -    C(1,C(1,P(L)))        |  <1P(L)><L>{}
    
    2288
    -    C(1,C(1,1P(1P(L),A))) |  <1P(A)><A>{}
    
    2286
    +    P(A)                  |  <L><L>
    
    2287
    +    C(1,C(1,P(L)))        |  <1P(L)><L>
    
    2288
    +    C(1,C(1,1P(1P(L),A))) |  <1P(A)><A>
    
    2289 2289
     
    
    2290 2290
     Note that in the first example, the depth of the demand type was *higher* than
    
    2291 2291
     the arity of the incoming call demand due to the anonymous lambda.
    

  • docs/users_guide/using-optimisation.rst
    ... ... @@ -1614,7 +1614,7 @@ as such you shouldn't need to set any of them explicitly. A flag
    1614 1614
         a polymorphic sub-demand of the same letter: E.g. ``L`` is equivalent to
    
    1615 1615
         ``LL`` by expansion of the single letter demand, which is equivalent to
    
    1616 1616
         ``LP(LP(..))``, so ``L``\s all the way down. It is always clear from
    
    1617
    -    context whether we talk about about a cardinality, sub-demand or demand.
    
    1617
    +    context whether we talk about a cardinality, sub-demand or demand.
    
    1618 1618
     
    
    1619 1619
         **Demand signatures**
    
    1620 1620
     
    
    ... ... @@ -1653,8 +1653,8 @@ as such you shouldn't need to set any of them explicitly. A flag
    1653 1653
             maybe n _ Nothing  = n
    
    1654 1654
             maybe _ s (Just a) = s a
    
    1655 1655
     
    
    1656
    -    We give it demand signature ``<L><MC(M,L)><1L>``.  The ``C(M,L)`` is a *call
    
    1657
    -    sub-demand* that says "Called at most once, where the result is used
    
    1656
    +    We give it demand signature ``<ML><MC(1,L)><1L>``.  The ``C(1,L)`` is a *call
    
    1657
    +    sub-demand* that says "Called exactly once, where the result is used
    
    1658 1658
         according to ``L``". The expression ``f `seq` f 1`` puts ``f`` under
    
    1659 1659
         demand ``SC(1,L)`` and serves as an example where the upper bound on
    
    1660 1660
         evaluation cardinality doesn't coincide with that of the call cardinality.