Simon Peyton Jones pushed to branch wip/T27737 at Glasgow Haskell Compiler / GHC

Commits:

2 changed files:

Changes:

  • compiler/GHC/Core/Opt/Simplify/Iteration.hs
    ... ... @@ -1283,6 +1283,12 @@ simplExprF1 env expr@(Lam {}) cont
    1283 1283
             -- and likewise drop counts all binders (incl type lambdas)
    
    1284 1284
     
    
    1285 1285
     simplExprF1 env (Case scrut bndr _ alts) cont
    
    1286
    +  | not (seCaseCase env)  -- See (COC-INV) in Note [sm_case_case: switching off case continuations]
    
    1287
    +  = do { let scrut_out_ty = substTy env (idType bndr)
    
    1288
    +       ; scrut' <- simplExprC env scrut (mkBoringStop scrut_out_ty)
    
    1289
    +       ; rebuildCase (SAF_In, env) scrut' bndr alts cont }
    
    1290
    +
    
    1291
    +  | otherwise
    
    1286 1292
       = {-#SCC "simplExprF1-Case" #-}
    
    1287 1293
         simplExprF env scrut (Select { sc_bndr = bndr, sc_alts = alts
    
    1288 1294
                                      , sc_env = UnSimplified env, sc_cont = cont })
    
    ... ... @@ -1304,15 +1310,6 @@ simplExprF1 env (Let (NonRec bndr rhs) body) cont
    1304 1310
              tick (PreInlineUnconditionally bndr)
    
    1305 1311
            ; simplExprF env' body cont }
    
    1306 1312
     
    
    1307
    --- If -fno-case-of-case, push /only applications/ inside a 'let', lest we
    
    1308
    --- lose a join point.  See Note [Join points with -fno-case-of-case]
    
    1309
    -simplExprF1 env let_expr@(Let {}) cont
    
    1310
    -  | not (seCaseCase env)
    
    1311
    -  , (inner, outer) <- splitContArgs cont
    
    1312
    -  , not (contIsStop outer)
    
    1313
    -  = do { let_expr' <- simplExprC env let_expr inner
    
    1314
    -       ; rebuild env let_expr' outer }
    
    1315
    -
    
    1316 1313
     -- Now check for a join point.  It's better to do the preInlineUnconditionally
    
    1317 1314
     -- test first, because joinPointBinding_maybe has to eta-expand, so a trivial
    
    1318 1315
     -- binding like { j = j2 |> co } would first be eta-expanded and then inlined
    
    ... ... @@ -2026,9 +2023,10 @@ simplNonRecE env from_what bndr (rhs, rhs_se) body cont
    2026 2023
            -- If not, the invariant holds already, and it's optional.
    
    2027 2024
     
    
    2028 2025
            -- (FromBeta Lifted) or FromLet: look at the demand info
    
    2026
    +       -- seCaseCase: see (COC-INV)
    
    2027
    +       -- in Note [sm_case_case: switching off case continuations]
    
    2029 2028
            _ -> seCaseCase env && isStrUsedDmd (idDemandInfo bndr)
    
    2030 2029
     
    
    2031
    -
    
    2032 2030
     ------------------
    
    2033 2031
     simplRecE :: SimplEnv
    
    2034 2032
               -> [(InId, InExpr)]
    
    ... ... @@ -2131,15 +2129,14 @@ wrapJoinCont :: SimplEnv -> SimplCont
    2131 2129
     -- Deal with making the continuation duplicable if necessary,
    
    2132 2130
     -- and with the no-case-of-case situation.
    
    2133 2131
     wrapJoinCont env cont thing_inside
    
    2134
    -  | contIsStop cont        -- Common case; no need for fancy footwork
    
    2132
    +  | contIsStop cont        -- Fast path: no need for fancy footwork
    
    2135 2133
       = thing_inside env cont
    
    2136 2134
     
    
    2137 2135
       | otherwise
    
    2138 2136
         -- Normal case; see Note [Join points and case-of-case]
    
    2139 2137
         -- Case-of-case should be /on/ here, else we should not
    
    2140 2138
         -- be in wrapJoinCont in the first place
    
    2141
    -  = assertPpr (seCaseCase env) (ppr cont) $
    
    2142
    -    do { (floats1, cont')  <- mkDupableCont env cont
    
    2139
    +  = do { (floats1, cont')  <- mkDupableCont env cont
    
    2143 2140
            ; (floats2, result) <- thing_inside (env `setInScopeFromF` floats1) cont'
    
    2144 2141
            ; return (floats1 `addFloats` floats2, result) }
    
    2145 2142
     
    
    ... ... @@ -2168,8 +2165,84 @@ trimJoinCont var (JoinPoint arity) cont
    2168 2165
           = pprPanic "completeCall" $ ppr var $$ ppr cont
    
    2169 2166
     
    
    2170 2167
     
    
    2171
    -{- Note [Join points and case-of-case]
    
    2172
    -~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    
    2168
    +{- Note [sm_case_case: switching off case continuations]
    
    2169
    +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    
    2170
    +Normally when we come across a `case` expression, we just push a `Select`
    
    2171
    +continuation onto the continuation, roughly like this.
    
    2172
    +   simplExprF (Case scrut alts) cont
    
    2173
    +     = simplExprF scrut (Select alts cont)
    
    2174
    +
    
    2175
    +There are two reasons that we might NOT want to do this
    
    2176
    +
    
    2177
    +1. Loss of full laziness.  The case-of-case transformation can hide
    
    2178
    +   opportunities for let-floating (aka full laziness). For example
    
    2179
    +       rec { f = \y. case (expensive x) of (a,b) -> blah }
    
    2180
    +   We might hope to float the (expensive x) out of the \y-loop.
    
    2181
    +   But if we inline `expensive` we might get
    
    2182
    +      \y. case (case x of I# x' -> body) of (a,b) -> blah
    
    2183
    +   Now if we do case-of-case we get
    
    2184
    +       \y. case x if I# x2 ->
    
    2185
    +           case body of (a,b) -> blah
    
    2186
    +
    
    2187
    +   Sadly, at this point `body` mentions `x2`, so we can't float it out of the \y-loop.
    
    2188
    +
    
    2189
    +2. Pushing a `case` inside a `let` can prevent a join point from being
    
    2190
    +   discovered (#27737).  For example
    
    2191
    +      case (letrec j x y = ... in id (j p q)) of blah
    
    2192
    +   Here `j` is not /yet/ a join point, because it is not tail called, but it
    
    2193
    +   well become one after we inline `id`.  But if we push that `case` inwards
    
    2194
    +   at the same time as inlinine `id` we'll get
    
    2195
    +      letrec j x y = ... in case (j p q) of blah
    
    2196
    +   and now `j` /still/ isn't a join point, and will never become one.  This
    
    2197
    +   matters in practice: #27737
    
    2198
    +
    
    2199
    +Solution in both cases: in the "gentle" simplification phase that precedes the
    
    2200
    +first float-out transformation, never push a `Select` continuation.  So we
    
    2201
    +do not push the `case` inwards.  This behaiour is controlled by the `sm_case_case`
    
    2202
    +field of `SimplMode`, interrogated via `seCaseCase`.
    
    2203
    +
    
    2204
    +Some specifics, for when `sm_case_case` is False:
    
    2205
    +
    
    2206
    +(COC-INV) When `sm_case_case` is False we obey the following invariant:
    
    2207
    +             The SimplCont never contains
    
    2208
    +                - Select
    
    2209
    +                - StrictBind
    
    2210
    +                - StrictArg
    
    2211
    +    This is achieved by testing `seCaseCase` just before pushing any of
    
    2212
    +    those three constructors. Why StrictBind and StrictArg?  Because
    
    2213
    +    they mess with evaluation order in the same way that Select does.
    
    2214
    +
    
    2215
    +(COC1) The (COC-INV) also solves #25055, where we pushed a `case` inside `runRW`:
    
    2216
    +           case (runRW# (\s. body)) of (a,b) -> blah
    
    2217
    +         --->
    
    2218
    +           runRW# (\s. case body of (a,b) -> blah)
    
    2219
    +  Again, we don't want to this when `sm_case_case` is False, but that falls
    
    2220
    +  out as a simple consequence of (COC-INV)
    
    2221
    +
    
    2222
    +(COC2) Supose `sm_case_case` is False, and we are simplifying
    
    2223
    +
    
    2224
    +    case (join j x = <j-rhs> in
    
    2225
    +          case y of
    
    2226
    +             A -> j 1
    
    2227
    +             B -> j 2
    
    2228
    +             C -> e) of <outer-alts>
    
    2229
    +
    
    2230
    +  Usually, we'd push the outer continuation (case . of <outer-alts>) into
    
    2231
    +  both the RHS and the body of the join point j.  But since we aren't doing
    
    2232
    +  case-of-case we could end up with this totally bogus result
    
    2233
    +
    
    2234
    +      join x = case <j-rhs> of <outer-alts> in
    
    2235
    +      case (case y of
    
    2236
    +               A -> j 1
    
    2237
    +               B -> j 2
    
    2238
    +               C -> e) of <outer-alts>
    
    2239
    +
    
    2240
    +   Again, (COC-INV) neatly avoid this bogosity: we never push a Select
    
    2241
    +   onto the continuation.  This is much nicer than switching off case-of-case
    
    2242
    +   specifically (which we used to do).
    
    2243
    +
    
    2244
    +Note [Join points and case-of-case]
    
    2245
    +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    
    2173 2246
     When we perform the case-of-case transform (or otherwise push continuations
    
    2174 2247
     inward), we want to treat join points specially. Since they're always
    
    2175 2248
     tail-called and we want to maintain this invariant, we can do this (for any
    
    ... ... @@ -2317,7 +2390,7 @@ simplOutId :: SimplEnvIS -> OutId -> SimplCont -> SimplM (SimplFloats, OutExpr)
    2317 2390
     simplOutId env fun cont
    
    2318 2391
       | fun `hasKey` runRWKey
    
    2319 2392
       , ApplyToTy  { sc_cont = cont1 } <- cont
    
    2320
    -  , ApplyToTy  { sc_cont = cont2, sc_arg_ty = hole_ty } <- cont1
    
    2393
    +  , ApplyToTy  { sc_cont = cont2 } <- cont1
    
    2321 2394
       , ApplyToVal { sc_cont = cont3, sc_arg = arg, sc_cast = arg_mco
    
    2322 2395
                    , sc_env = arg_se, sc_hole_ty = fun_ty } <- cont2
    
    2323 2396
       -- Do this even if (contIsStop cont), or if seCaseCase is off.
    
    ... ... @@ -2326,11 +2399,6 @@ simplOutId env fun cont
    2326 2399
     
    
    2327 2400
                  overall_res_ty = contResultType cont3
    
    2328 2401
                  -- hole_ty is the type of the current runRW# application
    
    2329
    -             (outer_cont, new_runrw_res_ty, inner_cont)
    
    2330
    -                | seCaseCase env = (mkBoringStop overall_res_ty, overall_res_ty, cont3)
    
    2331
    -                | otherwise      = (cont3, hole_ty, mkBoringStop hole_ty)
    
    2332
    -                -- Only when case-of-case is on. See GHC.Driver.Config.Core.Opt.Simplify
    
    2333
    -                -- See (COC1) in Note [Case-of-case and full laziness]
    
    2334 2402
     
    
    2335 2403
            -- If the argument is a literal lambda already, take a short cut
    
    2336 2404
            -- This isn't just efficiency:
    
    ... ... @@ -2339,27 +2407,27 @@ simplOutId env fun cont
    2339 2407
            --    * Even more important: see Note [No eta-expansion in runRW#]
    
    2340 2408
            ; arg' <- case arg of
    
    2341 2409
                Lam s body -> do { (env', s') <- simplBinder arg_env s
    
    2342
    -                            ; body' <- simplExprC env' body inner_cont
    
    2410
    +                            ; body' <- simplExprC env' body cont3
    
    2343 2411
                                 ; return (Lam s' body') }
    
    2344 2412
                                 -- Important: do not try to eta-expand this lambda
    
    2345 2413
                                 -- See Note [No eta-expansion in runRW#]
    
    2346 2414
     
    
    2347 2415
                _ -> do { s' <- newId (fsLit "s") ManyTy realWorldStatePrimTy
    
    2348 2416
                        ; let (m,_,_) = splitFunTy fun_ty
    
    2349
    -                         env'  = arg_env `addNewInScopeIds` [s']
    
    2350
    -                         hole_ty = mkVisFunTy m realWorldStatePrimTy new_runrw_res_ty
    
    2417
    +                         env'    = arg_env `addNewInScopeIds` [s']
    
    2418
    +                         hole_ty = mkVisFunTy m realWorldStatePrimTy overall_res_ty
    
    2351 2419
                        ; cont' <- pushCastMCo env' arg_mco $
    
    2352
    -                              ApplyToVal { sc_arg = Var s', sc_cast = MRefl
    
    2353
    -                                         , sc_env = Simplified OkDup
    
    2354
    -                                         , sc_cont = inner_cont
    
    2420
    +                              ApplyToVal { sc_arg     = Var s', sc_cast = MRefl
    
    2421
    +                                         , sc_env     = Simplified OkDup
    
    2422
    +                                         , sc_cont    = cont3
    
    2355 2423
                                              , sc_hole_ty = hole_ty }
    
    2356 2424
                                     -- cont' applies to s', then K
    
    2357 2425
                        ; body' <- simplExprC env' arg cont'
    
    2358 2426
                        ; return (Lam s' body') }
    
    2359 2427
     
    
    2360
    -       ; let rr'   = getRuntimeRep new_runrw_res_ty
    
    2361
    -             call' = mkApps (Var fun) [mkTyArg rr', mkTyArg new_runrw_res_ty, arg']
    
    2362
    -       ; rebuild_go env call' outer_cont }
    
    2428
    +       ; let rr'   = getRuntimeRep overall_res_ty
    
    2429
    +             call' = mkApps (Var fun) [mkTyArg rr', mkTyArg overall_res_ty, arg']
    
    2430
    +       ; return (emptyFloats env, call') }
    
    2363 2431
     
    
    2364 2432
     -- Normal case for (f e1 .. en)
    
    2365 2433
     simplOutId env fun cont
    
    ... ... @@ -2424,8 +2492,8 @@ rebuildCall env fun_info
    2424 2492
                             , sc_hole_ty = fun_ty, sc_cont = cont })
    
    2425 2493
       | UnSimplified arg_env <- arg_se
    
    2426 2494
       , isStrictArgInfo fun_info  -- Strict arguments
    
    2427
    -  , seCaseCase env            -- But only when case-of-case is on.
    
    2428
    -                              -- See Note [Case-of-case and full laziness]
    
    2495
    +  , seCaseCase env            -- But only when case-of-case is on; see (COC-INV)
    
    2496
    +                              -- in Note [sm_case_case: switching off case continuations]
    
    2429 2497
       = simplExprF (arg_env `setInScopeFromE` env) arg $
    
    2430 2498
         addCastMCo arg_mco $
    
    2431 2499
         StrictArg { sc_fun = fun_info, sc_fun_ty = fun_ty
    
    ... ... @@ -3312,14 +3380,6 @@ doCaseToLet scrut case_bndr
    3312 3380
     --------------------------------------------------
    
    3313 3381
     
    
    3314 3382
     reallyRebuildCase (saf,env) scrut case_bndr alts cont
    
    3315
    -  | not (seCaseCase env)    -- Only when case-of-case is on.
    
    3316
    -                            -- See GHC.Driver.Config.Core.Opt.Simplify
    
    3317
    -                            --    Note [Case-of-case and full laziness]
    
    3318
    -  = do { case_expr <- simplAlts (saf,env) scrut case_bndr alts
    
    3319
    -                                (mkBoringStop (contHoleType cont))
    
    3320
    -       ; rebuild env case_expr cont }
    
    3321
    -
    
    3322
    -  | otherwise
    
    3323 3383
       = do { (floats, env', cont') <- mkDupableCaseCont env alts cont
    
    3324 3384
            ; case_expr <- simplAlts (saf,env') scrut
    
    3325 3385
                                     (scaleIdBy holeScaling case_bndr)
    

  • compiler/GHC/Driver/Config/Core/Opt/Simplify.hs
    ... ... @@ -80,7 +80,7 @@ initGentleSimplMode :: DynFlags -> SimplMode
    80 80
     initGentleSimplMode dflags = (initSimplMode dflags InitialPhase "Gentle")
    
    81 81
       { -- Don't do case-of-case transformations.
    
    82 82
         -- This makes full laziness work better
    
    83
    -    -- See Note [Case-of-case and full laziness]
    
    83
    +    -- See Note [sm_case_case: switching off case continuations]
    
    84 84
         sm_case_case = False
    
    85 85
       }
    
    86 86
     
    
    ... ... @@ -90,80 +90,3 @@ floatEnable dflags =
    90 90
         (True, True) -> FloatEnabled
    
    91 91
         (True, False)-> FloatNestedOnly
    
    92 92
         (False, _)   -> FloatDisabled
    93
    -
    
    94
    -
    
    95
    -{- Note [Case-of-case and full laziness]
    
    96
    -~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    
    97
    -Case-of-case can hide opportunities for let-floating (full laziness).
    
    98
    -For example
    
    99
    -   rec { f = \y. case (expensive x) of (a,b) -> blah }
    
    100
    -We might hope to float the (expensive x) out of the \y-loop.
    
    101
    -But if we inline `expensive` we might get
    
    102
    -   \y. case (case x of I# x' -> body) of (a,b) -> blah
    
    103
    -Now if we do case-of-case we get
    
    104
    -   \y. case x if I# x2 ->
    
    105
    -       case body of (a,b) -> blah
    
    106
    -
    
    107
    -Sadly, at this point `body` mentions `x2`, so we can't float it out of the
    
    108
    -\y-loop.
    
    109
    -
    
    110
    -Solution: don't do case-of-case in the "gentle" simplification phase that
    
    111
    -precedes the first float-out transformation.  Implementation:
    
    112
    -
    
    113
    -  * `sm_case_case` field in SimplMode
    
    114
    -
    
    115
    -  * If `sm_case_case` is False (tested via `seCaseCase`), then:
    
    116
    -    (COC1) When simplifying (case scrut of alts), do not make a Select continuation.
    
    117
    -           This happens in the `Case` case of `simplExprF`.
    
    118
    -    (COC2) When simplifying (f arg), where `f` is strict, do not make a StrictArg
    
    119
    -           continuation.  See the `ApplyToVal` case of `rebuildArg`.
    
    120
    -
    
    121
    -    ...more to come...
    
    122
    -           in GHC.Core.Opt.Simplify.Iteration.rebuildCall.
    
    123
    -
    
    124
    -    (COC3) This applies equally to the case-of-runRW# transformation:
    
    125
    -           case (runRW# (\s. body)) of (a,b) -> blah
    
    126
    -           --->
    
    127
    -           runRW# (\s. case body of (a,b) -> blah)
    
    128
    -           Again, don't do this when `sm_case_case` is off.
    
    129
    -           See #25055 for a motivating example.
    
    130
    -
    
    131
    -Note [Join points with -fno-case-of-case]   FIX ME
    
    132
    -~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    
    133
    -Supose case-of-case is switched off, and we are simplifying
    
    134
    -
    
    135
    -    case (join j x = <j-rhs> in
    
    136
    -          case y of
    
    137
    -             A -> j 1
    
    138
    -             B -> j 2
    
    139
    -             C -> e) of <outer-alts>
    
    140
    -
    
    141
    -Usually, we'd push the outer continuation (case . of <outer-alts>) into
    
    142
    -both the RHS and the body of the join point j.  But since we aren't doing
    
    143
    -case-of-case we may then end up with this totally bogus result
    
    144
    -
    
    145
    -    join x = case <j-rhs> of <outer-alts> in
    
    146
    -    case (case y of
    
    147
    -             A -> j 1
    
    148
    -             B -> j 2
    
    149
    -             C -> e) of <outer-alts>
    
    150
    -
    
    151
    -This would be OK in the language of the paper, but not in GHC: j is no longer
    
    152
    -a join point.  We can only do the "push continuation into the RHS of the
    
    153
    -join point j" if we also push the continuation right down to the /jumps/ to
    
    154
    -j, so that it can evaporate there (trimJoinCont). Then, if we are doing
    
    155
    -case-of-case, we'll get to:
    
    156
    -
    
    157
    -    join x = case <j-rhs> of <outer-alts> in
    
    158
    -    case y of
    
    159
    -      A -> j 1
    
    160
    -      B -> j 2
    
    161
    -      C -> case e of <outer-alts>
    
    162
    -
    
    163
    -which is great.
    
    164
    -
    
    165
    -Bottom line: if case-of-case is off, we must stop pushing the continuation
    
    166
    -inwards altogether at any join point.  Instead simplify the (join ... in ...)
    
    167
    -with a Stop continuation, and wrap the original continuation around the
    
    168
    -outside.  Surprisingly tricky!
    
    169
    --}