Sebastian Graf pushed to branch wip/T27383 at Glasgow Haskell Compiler / GHC Commits: 0e7c8aca by Sebastian Graf at 2026-06-16T23:47:03+02:00 Desugar a `case` scrutinee only once (#27383, #20251) In `dsExpr` for `HsCase` we desugared the scrutinee /twice/: once to build the Core `case` itself, and again inside `matchWrapper`, which re-desugared the source scrutinee (via `addHsScrutTmCs`) purely to record long-distance information for the pattern-match checker. For a single `case` that is merely wasteful. But for nested cases it is catastrophic. Consider case (case (case e of ... ) of ... ) of ... Desugaring the outer scrutinee desugars the middle `case` twice, each of which desugars the inner `case` twice, and so on. The work doubles at every level, so desugaring takes O(2^n) time in the nesting depth. That is the blowup reported in #27383; it is also what makes the machine-generated program in #20251 take an age to compile. The fix is simple. `matchWrapper` is handed the scrutinee anyway, so we give it the Core expression we have /already/ desugared, and record the long-distance term constraint with `addCoreScrutTmCs` instead of re-desugaring from source. This is just what `matchSinglePatVar` already does for single-pattern matches. So: * `matchWrapper` now takes `Maybe [CoreExpr]` rather than `Maybe [LHsExpr GhcTc]`. * The `HsCase` equation of `dsExpr` passes the already-desugared `core_discrim`; the arrow desugarer passes its match variables. * `addHsScrutTmCs` had no other use, so it is gone. Desugaring is now linear in the nesting depth. (The coverage checker still runs `simpleOptExpr` over each scrutinee, which leaves the total at O(n^2); that is ample.) The long-distance information itself is unchanged: the checker sees precisely the Core that backs the generated code. Test: deSugar/should_compile/T27383 - - - - - 8 changed files: - + changelog.d/fix-exponential-case-desugar-27383 - compiler/GHC/HsToCore/Arrows.hs - compiler/GHC/HsToCore/Expr.hs - compiler/GHC/HsToCore/Match.hs - compiler/GHC/HsToCore/Match.hs-boot - compiler/GHC/HsToCore/Pmc.hs - + testsuite/tests/deSugar/should_compile/T27383.hs - testsuite/tests/deSugar/should_compile/all.T Changes: ===================================== changelog.d/fix-exponential-case-desugar-27383 ===================================== @@ -0,0 +1,6 @@ +section: compiler +synopsis: Fix exponential-time desugaring of nested ``case`` expressions. + The scrutinee is no longer desugared a second time when recording + long-distance information for the pattern-match checker. +issues: #27383 #20251 +mrs: !16203 ===================================== compiler/GHC/HsToCore/Arrows.hs ===================================== @@ -553,7 +553,7 @@ dsCmd ids local_vars stack_ty res_ty in_ty = envStackType env_ids stack_ty' discrims = map nlHsVar arg_ids (discrim_vars, matching_code) - <- matchWrapper (ArrowMatchCtxt match_ctxt) (Just discrims) match' + <- matchWrapper (ArrowMatchCtxt match_ctxt) (Just (map Var arg_ids)) match' core_body <- flip (bind_vars discrim_vars) matching_code <$> traverse dsLExpr discrims ===================================== compiler/GHC/HsToCore/Expr.hs ===================================== @@ -421,7 +421,7 @@ dsExpr (HsPragE _ (HsPragSCC _ cc) expr) dsExpr (HsCase ctxt discrim matches) = do { core_discrim <- dsLExpr discrim - ; ([discrim_var], matching_code) <- matchWrapper ctxt (Just [discrim]) matches + ; ([discrim_var], matching_code) <- matchWrapper ctxt (Just [core_discrim]) matches ; return (bindNonRec discrim_var core_discrim matching_code) } -- Pepe: The binds are in scope in the body but NOT in the binding group ===================================== compiler/GHC/HsToCore/Match.hs ===================================== @@ -761,7 +761,7 @@ Call @match@ with all of this information! matchWrapper :: HsMatchContextRn -- ^ For shadowing warning messages - -> Maybe [LHsExpr GhcTc] -- ^ Scrutinee(s) + -> Maybe [CoreExpr] -- ^ Already-desugared scrutinee(s) -- see Note [matchWrapper scrutinees] -> MatchGroup GhcTc (LHsExpr GhcTc) -- ^ Matches being desugared -> DsM ([Id], CoreExpr) -- ^ Results (usually passed to 'match') @@ -818,7 +818,7 @@ matchWrapper ctxt scrs (MG { mg_alts = L _ matches -- pmc for pattern synonyms -- See Note [Long-distance information] in GHC.HsToCore.Pmc - then addHsScrutTmCs (concat scrs) new_vars $ + then addCoreScrutTmCs (concat scrs) new_vars $ pmcMatches origin (DsMatchContext ctxt locn) new_vars matches -- When we're not doing PM checks on the match group, ===================================== compiler/GHC/HsToCore/Match.hs-boot ===================================== @@ -16,7 +16,7 @@ match :: [Id] matchWrapper :: HsMatchContextRn - -> Maybe [LHsExpr GhcTc] + -> Maybe [CoreExpr] -> MatchGroup GhcTc (LHsExpr GhcTc) -> DsM ([Id], CoreExpr) ===================================== compiler/GHC/HsToCore/Pmc.hs ===================================== @@ -34,7 +34,7 @@ module GHC.HsToCore.Pmc ( isMatchContextPmChecked, isMatchContextPmChecked_SinglePat, -- See Note [Long-distance information] - addTyCs, addCoreScrutTmCs, addHsScrutTmCs, getLdiNablas, + addTyCs, addCoreScrutTmCs, getLdiNablas, getNFirstUncovered ) where @@ -59,7 +59,6 @@ import GHC.Utils.Panic import GHC.Types.Var (EvVar, Var (..)) import GHC.Types.Id.Info import GHC.Tc.Utils.TcType (evVarPred) -import {-# SOURCE #-} GHC.HsToCore.Expr (dsLExpr) import GHC.HsToCore.Monad import GHC.Data.Bag import GHC.Data.OrdList @@ -684,12 +683,6 @@ addCoreScrutTmCs (scr:scrs) (x:xs) k addPhiCtsNablas nablas (unitBag (PhiCoreCt x scr)) addCoreScrutTmCs _ _ _ = panic "addCoreScrutTmCs: numbers of scrutinees and match ids differ" --- | 'addCoreScrutTmCs', but desugars the 'LHsExpr's first. -addHsScrutTmCs :: [LHsExpr GhcTc] -> [Id] -> DsM a -> DsM a -addHsScrutTmCs scrs vars k = do - scr_es <- traverse dsLExpr scrs - addCoreScrutTmCs scr_es vars k - {- Note [Long-distance information] ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Consider @@ -716,8 +709,8 @@ To achieve similar reasoning in the coverage checker: which the call sites put into place with 'GHC.HsToCore.Monad.updPmNablas'. * Call sites also extend this set with facts from type-constraint dictionaries, - case scrutinees, etc. with the exported functions 'addTyCs', 'addCoreScrutTmCs' - and 'addHsScrutTmCs'. + case scrutinees, etc. with the exported functions 'addTyCs' and + 'addCoreScrutTmCs'. Note [Recovering from unsatisfiable pattern-matching constraints] ===================================== testsuite/tests/deSugar/should_compile/T27383.hs ===================================== @@ -0,0 +1,9 @@ +-- Regression test for #27383 (and #20251): deeply nested cases whose +-- scrutinees are themselves cases must desugar in polynomial (not +-- exponential) time. With the bug the scrutinee is desugared twice at +-- every level, so compiler allocation (tracked by this performance test) +-- grows as O(2^n) in the nesting depth. +module T27383 where + +zero :: Int +zero = (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case 0 of x500 -> x500) of x499 -> x499) of x498 -> x498) of x497 -> x497) of x496 -> x496) of x495 -> x495) of x494 -> x494) of x493 -> x493) of x492 -> x492) of x491 -> x491) of x490 -> x490) of x489 -> x489) of x488 -> x488) of x487 -> x487) of x486 -> x486) of x485 -> x485) of x484 -> x484) of x483 -> x483) of x482 -> x482) of x481 -> x481) of x480 -> x480) of x479 -> x479) of x478 -> x478) of x477 -> x477) of x476 -> x476) of x475 -> x475) of x474 -> x474) of x473 -> x473) of x472 -> x472) of x471 -> x471) of x470 -> x470) of x469 -> x469) of x468 -> x468) of x467 -> x467) of x466 -> x466) of x465 -> x465) of x464 -> x464) of x463 -> x463) of x462 -> x462) of x461 -> x461) of x460 -> x460) of x459 -> x459) of x458 -> x458) of x457 -> x457) of x456 -> x456) of x455 -> x455) of x454 -> x454) of x453 -> x453) of x452 -> x452) of x451 -> x451) of x450 -> x450) of x449 -> x449) of x448 -> x448) of x447 -> x447) of x446 -> x446) of x445 -> x445) of x444 -> x444) of x443 -> x443) of x442 -> x442) of x441 -> x441) of x440 -> x440) of x439 -> x439) of x438 -> x438) of x437 -> x437) of x436 -> x436) of x435 -> x435) of x434 -> x434) of x433 -> x433) of x432 -> x432) of x431 -> x431) of x430 -> x430) of x429 -> x429) of x428 -> x428) of x427 -> x427) of x426 -> x426) of x425 -> x425) of x424 -> x424) of x423 -> x423) of x422 -> x422) of x421 -> x421) of x420 -> x420) of x419 -> x419) of x418 -> x418) of x417 -> x417) of x416 -> x416) of x415 -> x415) of x414 -> x414) of x413 -> x413) of x412 -> x412) of x411 -> x411) of x410 -> x410) of x409 -> x409) of x408 -> x408) of x407 -> x407) of x406 -> x406) of x405 -> x405) of x404 -> x404) of x403 -> x403) of x402 -> x402) of x401 -> x401) of x400 -> x400) of x399 -> x399) of x398 -> x398) of x397 -> x397) of x396 -> x396) of x395 -> x395) of x394 -> x394) of x393 -> x393) of x392 -> x392) of x391 -> x391) of x390 -> x390) of x389 -> x389) of x388 -> x388) of x387 -> x387) of x386 -> x386) of x385 -> x385) of x384 -> x384) of x383 -> x383) of x382 -> x382) of x381 -> x381) of x380 -> x380) of x379 -> x379) of x378 -> x378) of x377 -> x377) of x376 -> x376) of x375 -> x375) of x374 -> x374) of x373 -> x373) of x372 -> x372) of x371 -> x371) of x370 -> x370) of x369 -> x369) of x368 -> x368) of x367 -> x367) of x366 -> x366) of x365 -> x365) of x364 -> x364) of x363 -> x363) of x362 -> x362) of x361 -> x361) of x360 -> x360) of x359 -> x359) of x358 -> x358) of x357 -> x357) of x356 -> x356) of x355 -> x355) of x354 -> x354) of x353 -> x353) of x352 -> x352) of x351 -> x351) of x350 -> x350) of x349 -> x349) of x348 -> x348) of x347 -> x347) of x346 -> x346) of x345 -> x345) of x344 -> x344) of x343 -> x343) of x342 -> x342) of x341 -> x341) of x340 -> x340) of x339 -> x339) of x338 -> x338) of x337 -> x337) of x336 -> x336) of x335 -> x335) of x334 -> x334) of x333 -> x333) of x332 -> x332) of x331 -> x331) of x330 -> x330) of x329 -> x329) of x328 -> x328) of x327 -> x327) of x326 -> x326) of x325 -> x325) of x324 -> x324) of x323 -> x323) of x322 -> x322) of x321 -> x321) of x320 -> x320) of x319 -> x319) of x318 -> x318) of x317 -> x317) of x316 -> x316) of x315 -> x315) of x314 -> x314) of x313 -> x313) of x312 -> x312) of x311 -> x311) of x310 -> x310) of x309 -> x309) of x308 -> x308) of x307 -> x307) of x306 -> x306) of x305 -> x305) of x304 -> x304) of x303 -> x303) of x302 -> x302) of x301 -> x301) of x300 -> x300) of x299 -> x299) of x298 -> x298) of x297 -> x297) of x296 -> x296) of x295 -> x295) of x294 -> x294) of x293 -> x293) of x292 -> x292) of x291 -> x291) of x290 -> x290) of x289 -> x289) of x288 -> x288) of x287 -> x287) of x286 -> x286) of x285 -> x285) of x284 -> x284) of x283 -> x283) of x282 -> x282) of x281 -> x281) of x280 -> x280) of x279 -> x279) of x278 -> x278) of x277 -> x277) of x276 -> x276) of x275 -> x275) of x274 -> x274) of x273 -> x273) of x272 -> x272) of x271 -> x271) of x270 -> x270) of x269 -> x269) of x268 -> x268) of x267 -> x267) of x266 -> x266) of x265 -> x265) of x264 -> x264) of x263 -> x263) of x262 -> x262) of x261 -> x261) of x260 -> x260) of x259 -> x259) of x258 -> x258) of x257 -> x257) of x256 -> x256) of x255 -> x255) of x254 -> x254) of x253 -> x253) of x252 -> x252) of x251 -> x251) of x250 -> x250) of x249 -> x249) of x248 -> x248) of x247 -> x247) of x246 -> x246) of x245 -> x245) of x244 -> x244) of x243 -> x243) of x242 -> x242) of x241 -> x241) of x240 -> x240) of x239 -> x239) of x238 -> x238) of x237 -> x237) of x236 -> x236) of x235 -> x235) of x234 -> x234) of x233 -> x233) of x232 -> x232) of x231 -> x231) of x230 -> x230) of x229 -> x229) of x228 -> x228) of x227 -> x227) of x226 -> x226) of x225 -> x225) of x224 -> x224) of x223 -> x223) of x222 -> x222) of x221 -> x221) of x220 -> x220) of x219 -> x219) of x218 -> x218) of x217 -> x217) of x216 -> x216) of x215 -> x215) of x214 -> x214) of x213 -> x213) of x212 -> x212) of x211 -> x211) of x210 -> x210) of x209 -> x209) of x208 -> x208) of x207 -> x207) of x206 -> x206) of x205 -> x205) of x204 -> x204) of x203 -> x203) of x202 -> x202) of x201 -> x201) of x200 -> x200) of x199 -> x199) of x198 -> x198) of x197 -> x197) of x196 -> x196) of x195 -> x195) of x194 -> x194) of x193 -> x193) of x192 -> x192) of x191 -> x191) of x190 -> x190) of x189 -> x189) of x188 -> x188) of x187 -> x187) of x186 -> x186) of x185 -> x185) of x184 -> x184) of x183 -> x183) of x182 -> x182) of x181 -> x181) of x180 -> x180) of x179 -> x179) of x178 -> x178) of x177 -> x177) of x176 -> x176) of x175 -> x175) of x174 -> x174) of x173 -> x173) of x172 -> x172) of x171 -> x171) of x170 -> x170) of x169 -> x169) of x168 -> x168) of x167 -> x167) of x166 -> x166) of x165 -> x165) of x164 -> x164) of x163 -> x163) of x162 -> x162) of x161 -> x161) of x160 -> x160) of x159 -> x159) of x158 -> x158) of x157 -> x157) of x156 -> x156) of x155 -> x155) of x154 -> x154) of x153 -> x153) of x152 -> x152) of x151 -> x151) of x150 -> x150) of x149 -> x149) of x148 -> x148) of x147 -> x147) of x146 -> x146) of x145 -> x145) of x144 -> x144) of x143 -> x143) of x142 -> x142) of x141 -> x141) of x140 -> x140) of x139 -> x139) of x138 -> x138) of x137 -> x137) of x136 -> x136) of x135 -> x135) of x134 -> x134) of x133 -> x133) of x132 -> x132) of x131 -> x131) of x130 -> x130) of x129 -> x129) of x128 -> x128) of x127 -> x127) of x126 -> x126) of x125 -> x125) of x124 -> x124) of x123 -> x123) of x122 -> x122) of x121 -> x121) of x120 -> x120) of x119 -> x119) of x118 -> x118) of x117 -> x117) of x116 -> x116) of x115 -> x115) of x114 -> x114) of x113 -> x113) of x112 -> x112) of x111 -> x111) of x110 -> x110) of x109 -> x109) of x108 -> x108) of x107 -> x107) of x106 -> x106) of x105 -> x105) of x104 -> x104) of x103 -> x103) of x102 -> x102) of x101 -> x101) of x100 -> x100) of x99 -> x99) of x98 -> x98) of x97 -> x97) of x96 -> x96) of x95 -> x95) of x94 -> x94) of x93 -> x93) of x92 -> x92) of x91 -> x91) of x90 -> x90) of x89 -> x89) of x88 -> x88) of x87 -> x87) of x86 -> x86) of x85 -> x85) of x84 -> x84) of x83 -> x83) of x82 -> x82) of x81 -> x81) of x80 -> x80) of x79 -> x79) of x78 -> x78) of x77 -> x77) of x76 -> x76) of x75 -> x75) of x74 -> x74) of x73 -> x73) of x72 -> x72) of x71 -> x71) of x70 -> x70) of x69 -> x69) of x68 -> x68) of x67 -> x67) of x66 -> x66) of x65 -> x65) of x64 -> x64) of x63 -> x63) of x62 -> x62) of x61 -> x61) of x60 -> x60) of x59 -> x59) of x58 -> x58) of x57 -> x57) of x56 -> x56) of x55 -> x55) of x54 -> x54) of x53 -> x53) of x52 -> x52) of x51 -> x51) of x50 -> x50) of x49 -> x49) of x48 -> x48) of x47 -> x47) of x46 -> x46) of x45 -> x45) of x44 -> x44) of x43 -> x43) of x42 -> x42) of x41 -> x41) of x40 -> x40) of x39 -> x39) of x38 -> x38) of x37 -> x37) of x36 -> x36) of x35 -> x35) of x34 -> x34) of x33 -> x33) of x32 -> x32) of x31 -> x31) of x30 -> x30) of x29 -> x29) of x28 -> x28) of x27 -> x27) of x26 -> x26) of x25 -> x25) of x24 -> x24) of x23 -> x23) of x22 -> x22) of x21 -> x21) of x20 -> x20) of x19 -> x19) of x18 -> x18) of x17 -> x17) of x16 -> x16) of x15 -> x15) of x14 -> x14) of x13 -> x13) of x12 -> x12) of x11 -> x11) of x10 -> x10) of x9 -> x9) of x8 -> x8) of x7 -> x7) of x6 -> x6) of x5 -> x5) of x4 -> x4) of x3 -> x3) of x2 -> x2) of x1 -> x1) ===================================== testsuite/tests/deSugar/should_compile/all.T ===================================== @@ -116,3 +116,7 @@ test('T22719', normal, compile, ['-ddump-simpl -dsuppress-uniques -dno-typeable- test('T23550', normal, compile, ['']) test('T24489', normal, compile, ['-O']) test('T25996', normal, compile, ['']) +test('T27383', + [collect_compiler_stats('bytes allocated', 10)], + compile, + ['-Wincomplete-patterns']) View it on GitLab: https://gitlab.haskell.org/ghc/ghc/-/commit/0e7c8acaba5f930f5dffc96606367446... -- View it on GitLab: https://gitlab.haskell.org/ghc/ghc/-/commit/0e7c8acaba5f930f5dffc96606367446... You're receiving this email because of your account on gitlab.haskell.org.