1{- 2(c) The University of Glasgow 2006 3(c) The GRASP/AQUA Project, Glasgow University, 1992-1998 4 5 6 Arity and eta expansion 7-} 8 9{-# LANGUAGE CPP #-} 10 11{-# OPTIONS_GHC -Wno-incomplete-record-updates #-} 12 13-- | Arity and eta expansion 14module GHC.Core.Opt.Arity 15 ( manifestArity, joinRhsArity, exprArity, typeArity 16 , exprEtaExpandArity, findRhsArity 17 , etaExpand, etaExpandAT 18 , exprBotStrictness_maybe 19 20 -- ** ArityType 21 , ArityType(..), mkBotArityType, mkTopArityType, expandableArityType 22 , arityTypeArity, maxWithArity, idArityType 23 24 -- ** Join points 25 , etaExpandToJoinPoint, etaExpandToJoinPointRule 26 27 -- ** Coercions and casts 28 , pushCoArg, pushCoArgs, pushCoValArg, pushCoTyArg 29 , pushCoercionIntoLambda, pushCoDataCon, collectBindersPushingCo 30 ) 31where 32 33#include "GhclibHsVersions.h" 34 35import GHC.Prelude 36 37import GHC.Driver.Ppr 38 39import GHC.Core 40import GHC.Core.FVs 41import GHC.Core.Utils 42import GHC.Types.Demand 43import GHC.Types.Var 44import GHC.Types.Var.Env 45import GHC.Types.Id 46 47-- We have two sorts of substitution: 48-- GHC.Core.Subst.Subst, and GHC.Core.TyCo.TCvSubst 49-- Both have substTy, substCo Hence need for qualification 50import GHC.Core.Subst as Core 51import GHC.Core.Type as Type 52import GHC.Core.Coercion as Type 53 54import GHC.Core.DataCon 55import GHC.Core.TyCon ( tyConArity ) 56import GHC.Core.TyCon.RecWalk ( initRecTc, checkRecTc ) 57import GHC.Core.Predicate ( isDictTy ) 58import GHC.Core.Multiplicity 59import GHC.Types.Var.Set 60import GHC.Types.Basic 61import GHC.Types.Tickish 62import GHC.Builtin.Uniques 63import GHC.Driver.Session ( DynFlags, GeneralFlag(..), gopt ) 64import GHC.Utils.Outputable 65import GHC.Utils.Panic 66import GHC.Data.FastString 67import GHC.Data.Pair 68import GHC.Utils.Misc 69 70{- 71************************************************************************ 72* * 73 manifestArity and exprArity 74* * 75************************************************************************ 76 77exprArity is a cheap-and-cheerful version of exprEtaExpandArity. 78It tells how many things the expression can be applied to before doing 79any work. It doesn't look inside cases, lets, etc. The idea is that 80exprEtaExpandArity will do the hard work, leaving something that's easy 81for exprArity to grapple with. In particular, Simplify uses exprArity to 82compute the ArityInfo for the Id. 83 84Originally I thought that it was enough just to look for top-level lambdas, but 85it isn't. I've seen this 86 87 foo = PrelBase.timesInt 88 89We want foo to get arity 2 even though the eta-expander will leave it 90unchanged, in the expectation that it'll be inlined. But occasionally it 91isn't, because foo is blacklisted (used in a rule). 92 93Similarly, see the ok_note check in exprEtaExpandArity. So 94 f = __inline_me (\x -> e) 95won't be eta-expanded. 96 97And in any case it seems more robust to have exprArity be a bit more intelligent. 98But note that (\x y z -> f x y z) 99should have arity 3, regardless of f's arity. 100-} 101 102manifestArity :: CoreExpr -> Arity 103-- ^ manifestArity sees how many leading value lambdas there are, 104-- after looking through casts 105manifestArity (Lam v e) | isId v = 1 + manifestArity e 106 | otherwise = manifestArity e 107manifestArity (Tick t e) | not (tickishIsCode t) = manifestArity e 108manifestArity (Cast e _) = manifestArity e 109manifestArity _ = 0 110 111joinRhsArity :: CoreExpr -> JoinArity 112-- Join points are supposed to have manifestly-visible 113-- lambdas at the top: no ticks, no casts, nothing 114-- Moreover, type lambdas count in JoinArity 115joinRhsArity (Lam _ e) = 1 + joinRhsArity e 116joinRhsArity _ = 0 117 118 119--------------- 120exprArity :: CoreExpr -> Arity 121-- ^ An approximate, fast, version of 'exprEtaExpandArity' 122exprArity e = go e 123 where 124 go (Var v) = idArity v 125 go (Lam x e) | isId x = go e + 1 126 | otherwise = go e 127 go (Tick t e) | not (tickishIsCode t) = go e 128 go (Cast e co) = trim_arity (go e) (coercionRKind co) 129 -- Note [exprArity invariant] 130 go (App e (Type _)) = go e 131 go (App f a) | exprIsTrivial a = (go f - 1) `max` 0 132 -- See Note [exprArity for applications] 133 -- NB: coercions count as a value argument 134 135 go _ = 0 136 137 trim_arity :: Arity -> Type -> Arity 138 trim_arity arity ty = arity `min` length (typeArity ty) 139 140--------------- 141typeArity :: Type -> [OneShotInfo] 142-- How many value arrows are visible in the type? 143-- We look through foralls, and newtypes 144-- See Note [exprArity invariant] 145typeArity ty 146 = go initRecTc ty 147 where 148 go rec_nts ty 149 | Just (_, ty') <- splitForAllTyCoVar_maybe ty 150 = go rec_nts ty' 151 152 | Just (_,arg,res) <- splitFunTy_maybe ty 153 = typeOneShot arg : go rec_nts res 154 155 | Just (tc,tys) <- splitTyConApp_maybe ty 156 , Just (ty', _) <- instNewTyCon_maybe tc tys 157 , Just rec_nts' <- checkRecTc rec_nts tc -- See Note [Expanding newtypes] 158 -- in GHC.Core.TyCon 159-- , not (isClassTyCon tc) -- Do not eta-expand through newtype classes 160-- -- See Note [Newtype classes and eta expansion] 161-- (no longer required) 162 = go rec_nts' ty' 163 -- Important to look through non-recursive newtypes, so that, eg 164 -- (f x) where f has arity 2, f :: Int -> IO () 165 -- Here we want to get arity 1 for the result! 166 -- 167 -- AND through a layer of recursive newtypes 168 -- e.g. newtype Stream m a b = Stream (m (Either b (a, Stream m a b))) 169 170 | otherwise 171 = [] 172 173--------------- 174exprBotStrictness_maybe :: CoreExpr -> Maybe (Arity, StrictSig) 175-- A cheap and cheerful function that identifies bottoming functions 176-- and gives them a suitable strictness signatures. It's used during 177-- float-out 178exprBotStrictness_maybe e 179 = case getBotArity (arityType botStrictnessArityEnv e) of 180 Nothing -> Nothing 181 Just ar -> Just (ar, sig ar) 182 where 183 sig ar = mkClosedStrictSig (replicate ar topDmd) botDiv 184 185{- 186Note [exprArity invariant] 187~~~~~~~~~~~~~~~~~~~~~~~~~~ 188exprArity has the following invariants: 189 190 (1) If typeArity (exprType e) = n, 191 then manifestArity (etaExpand e n) = n 192 193 That is, etaExpand can always expand as much as typeArity says 194 So the case analysis in etaExpand and in typeArity must match 195 196 (2) exprArity e <= typeArity (exprType e) 197 198 (3) Hence if (exprArity e) = n, then manifestArity (etaExpand e n) = n 199 200 That is, if exprArity says "the arity is n" then etaExpand really 201 can get "n" manifest lambdas to the top. 202 203Why is this important? Because 204 - In GHC.Iface.Tidy we use exprArity to fix the *final arity* of 205 each top-level Id, and in 206 - In CorePrep we use etaExpand on each rhs, so that the visible lambdas 207 actually match that arity, which in turn means 208 that the StgRhs has the right number of lambdas 209 210An alternative would be to do the eta-expansion in GHC.Iface.Tidy, at least 211for top-level bindings, in which case we would not need the trim_arity 212in exprArity. That is a less local change, so I'm going to leave it for today! 213 214Note [Newtype classes and eta expansion] 215~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 216 NB: this nasty special case is no longer required, because 217 for newtype classes we don't use the class-op rule mechanism 218 at all. See Note [Single-method classes] in GHC.Tc.TyCl.Instance. SLPJ May 2013 219 220-------- Old out of date comments, just for interest ----------- 221We have to be careful when eta-expanding through newtypes. In general 222it's a good idea, but annoyingly it interacts badly with the class-op 223rule mechanism. Consider 224 225 class C a where { op :: a -> a } 226 instance C b => C [b] where 227 op x = ... 228 229These translate to 230 231 co :: forall a. (a->a) ~ C a 232 233 $copList :: C b -> [b] -> [b] 234 $copList d x = ... 235 236 $dfList :: C b -> C [b] 237 {-# DFunUnfolding = [$copList] #-} 238 $dfList d = $copList d |> co@[b] 239 240Now suppose we have: 241 242 dCInt :: C Int 243 244 blah :: [Int] -> [Int] 245 blah = op ($dfList dCInt) 246 247Now we want the built-in op/$dfList rule will fire to give 248 blah = $copList dCInt 249 250But with eta-expansion 'blah' might (and in #3772, which is 251slightly more complicated, does) turn into 252 253 blah = op (\eta. ($dfList dCInt |> sym co) eta) 254 255and now it is *much* harder for the op/$dfList rule to fire, because 256exprIsConApp_maybe won't hold of the argument to op. I considered 257trying to *make* it hold, but it's tricky and I gave up. 258 259The test simplCore/should_compile/T3722 is an excellent example. 260-------- End of old out of date comments, just for interest ----------- 261 262 263Note [exprArity for applications] 264~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 265When we come to an application we check that the arg is trivial. 266 eg f (fac x) does not have arity 2, 267 even if f has arity 3! 268 269* We require that is trivial rather merely cheap. Suppose f has arity 2. 270 Then f (Just y) 271 has arity 0, because if we gave it arity 1 and then inlined f we'd get 272 let v = Just y in \w. <f-body> 273 which has arity 0. And we try to maintain the invariant that we don't 274 have arity decreases. 275 276* The `max 0` is important! (\x y -> f x) has arity 2, even if f is 277 unknown, hence arity 0 278 279 280************************************************************************ 281* * 282 Computing the "arity" of an expression 283* * 284************************************************************************ 285 286Note [Definition of arity] 287~~~~~~~~~~~~~~~~~~~~~~~~~~ 288The "arity" of an expression 'e' is n if 289 applying 'e' to *fewer* than n *value* arguments 290 converges rapidly 291 292Or, to put it another way 293 294 there is no work lost in duplicating the partial 295 application (e x1 .. x(n-1)) 296 297In the divergent case, no work is lost by duplicating because if the thing 298is evaluated once, that's the end of the program. 299 300Or, to put it another way, in any context C 301 302 C[ (\x1 .. xn. e x1 .. xn) ] 303 is as efficient as 304 C[ e ] 305 306It's all a bit more subtle than it looks: 307 308Note [One-shot lambdas] 309~~~~~~~~~~~~~~~~~~~~~~~ 310Consider one-shot lambdas 311 let x = expensive in \y z -> E 312We want this to have arity 1 if the \y-abstraction is a 1-shot lambda. 313 314Note [Dealing with bottom] 315~~~~~~~~~~~~~~~~~~~~~~~~~~ 316A Big Deal with computing arities is expressions like 317 318 f = \x -> case x of 319 True -> \s -> e1 320 False -> \s -> e2 321 322This happens all the time when f :: Bool -> IO () 323In this case we do eta-expand, in order to get that \s to the 324top, and give f arity 2. 325 326This isn't really right in the presence of seq. Consider 327 (f bot) `seq` 1 328 329This should diverge! But if we eta-expand, it won't. We ignore this 330"problem" (unless -fpedantic-bottoms is on), because being scrupulous 331would lose an important transformation for many programs. (See 332#5587 for an example.) 333 334Consider also 335 f = \x -> error "foo" 336Here, arity 1 is fine. But if it is 337 f = \x -> case x of 338 True -> error "foo" 339 False -> \y -> x+y 340then we want to get arity 2. Technically, this isn't quite right, because 341 (f True) `seq` 1 342should diverge, but it'll converge if we eta-expand f. Nevertheless, we 343do so; it improves some programs significantly, and increasing convergence 344isn't a bad thing. Hence the ABot/ATop in ArityType. 345 346So these two transformations aren't always the Right Thing, and we 347have several tickets reporting unexpected behaviour resulting from 348this transformation. So we try to limit it as much as possible: 349 350 (1) Do NOT move a lambda outside a known-bottom case expression 351 case undefined of { (a,b) -> \y -> e } 352 This showed up in #5557 353 354 (2) Do NOT move a lambda outside a case unless 355 (a) The scrutinee is ok-for-speculation, or 356 (b) more liberally: the scrutinee is cheap (e.g. a variable), and 357 -fpedantic-bottoms is not enforced (see #2915 for an example) 358 359Of course both (1) and (2) are readily defeated by disguising the bottoms. 360 3614. Note [Newtype arity] 362~~~~~~~~~~~~~~~~~~~~~~~~ 363Non-recursive newtypes are transparent, and should not get in the way. 364We do (currently) eta-expand recursive newtypes too. So if we have, say 365 366 newtype T = MkT ([T] -> Int) 367 368Suppose we have 369 e = coerce T f 370where f has arity 1. Then: etaExpandArity e = 1; 371that is, etaExpandArity looks through the coerce. 372 373When we eta-expand e to arity 1: eta_expand 1 e T 374we want to get: coerce T (\x::[T] -> (coerce ([T]->Int) e) x) 375 376 HOWEVER, note that if you use coerce bogusly you can ge 377 coerce Int negate 378 And since negate has arity 2, you might try to eta expand. But you can't 379 decompose Int to a function type. Hence the final case in eta_expand. 380 381Note [The state-transformer hack] 382~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 383Suppose we have 384 f = e 385where e has arity n. Then, if we know from the context that f has 386a usage type like 387 t1 -> ... -> tn -1-> t(n+1) -1-> ... -1-> tm -> ... 388then we can expand the arity to m. This usage type says that 389any application (x e1 .. en) will be applied to uniquely to (m-n) more args 390Consider f = \x. let y = <expensive> 391 in case x of 392 True -> foo 393 False -> \(s:RealWorld) -> e 394where foo has arity 1. Then we want the state hack to 395apply to foo too, so we can eta expand the case. 396 397Then we expect that if f is applied to one arg, it'll be applied to two 398(that's the hack -- we don't really know, and sometimes it's false) 399See also Id.isOneShotBndr. 400 401Note [State hack and bottoming functions] 402~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 403It's a terrible idea to use the state hack on a bottoming function. 404Here's what happens (#2861): 405 406 f :: String -> IO T 407 f = \p. error "..." 408 409Eta-expand, using the state hack: 410 411 f = \p. (\s. ((error "...") |> g1) s) |> g2 412 g1 :: IO T ~ (S -> (S,T)) 413 g2 :: (S -> (S,T)) ~ IO T 414 415Extrude the g2 416 417 f' = \p. \s. ((error "...") |> g1) s 418 f = f' |> (String -> g2) 419 420Discard args for bottomming function 421 422 f' = \p. \s. ((error "...") |> g1 |> g3 423 g3 :: (S -> (S,T)) ~ (S,T) 424 425Extrude g1.g3 426 427 f'' = \p. \s. (error "...") 428 f' = f'' |> (String -> S -> g1.g3) 429 430And now we can repeat the whole loop. Aargh! The bug is in applying the 431state hack to a function which then swallows the argument. 432 433This arose in another guise in #3959. Here we had 434 435 catch# (throw exn >> return ()) 436 437Note that (throw :: forall a e. Exn e => e -> a) is called with [a = IO ()]. 438After inlining (>>) we get 439 440 catch# (\_. throw {IO ()} exn) 441 442We must *not* eta-expand to 443 444 catch# (\_ _. throw {...} exn) 445 446because 'catch#' expects to get a (# _,_ #) after applying its argument to 447a State#, not another function! 448 449In short, we use the state hack to allow us to push let inside a lambda, 450but not to introduce a new lambda. 451 452 453Note [ArityType] 454~~~~~~~~~~~~~~~~ 455ArityType is the result of a compositional analysis on expressions, 456from which we can decide the real arity of the expression (extracted 457with function exprEtaExpandArity). 458 459We use the following notation: 460 at ::= \o1..on.div 461 div ::= T | x | ⊥ 462 o ::= ? | 1 463And omit the \. if n = 0. Examples: 464 \?11.T stands for @AT [NoOneShotInfo,OneShotLam,OneShotLam] topDiv@ 465 ⊥ stands for @AT [] botDiv@ 466See the 'Outputable' instance for more information. It's pretty simple. 467 468Here is what the fields mean. If an arbitrary expression 'f' has 469ArityType 'at', then 470 471 * If @at = AT [o1,..,on] botDiv@ (notation: \o1..on.⊥), then @f x1..xn@ 472 definitely diverges. Partial applications to fewer than n args may *or 473 may not* diverge. 474 475 We allow ourselves to eta-expand bottoming functions, even 476 if doing so may lose some `seq` sharing, 477 let x = <expensive> in \y. error (g x y) 478 ==> \y. let x = <expensive> in error (g x y) 479 480 * If @at = AT [o1,..,on] topDiv@ (notation: \o1..on.T), then expanding 'f' 481 to @\x1..xn. f x1..xn@ loses no sharing, assuming the calls of f respect 482 the one-shot-ness o1..on of its definition. 483 484 NB 'f' is an arbitrary expression, eg @f = g e1 e2@. This 'f' can have 485 arity type @AT oss _@, with @length oss > 0@, only if e1 e2 are themselves 486 cheap. 487 488 * In both cases, @f@, @f x1@, ... @f x1 ... x(n-1)@ are definitely 489 really functions, or bottom, but *not* casts from a data type, in 490 at least one case branch. (If it's a function in one case branch but 491 an unsafe cast from a data type in another, the program is bogus.) 492 So eta expansion is dynamically ok; see Note [State hack and 493 bottoming functions], the part about catch# 494 495Example: 496 f = \x\y. let v = <expensive> in 497 \s(one-shot) \t(one-shot). blah 498 'f' has arity type \??11.T 499 The one-shot-ness means we can, in effect, push that 500 'let' inside the \st. 501 502 503Suppose f = \xy. x+y 504Then f :: \??.T 505 f v :: \?.T 506 f <expensive> :: T 507-} 508 509 510-- | The analysis lattice of arity analysis. It is isomorphic to 511-- 512-- @ 513-- data ArityType' 514-- = AEnd Divergence 515-- | ALam OneShotInfo ArityType' 516-- @ 517-- 518-- Which is easier to display the Hasse diagram for: 519-- 520-- @ 521-- ALam OneShotLam at 522-- | 523-- AEnd topDiv 524-- | 525-- ALam NoOneShotInfo at 526-- | 527-- AEnd exnDiv 528-- | 529-- AEnd botDiv 530-- @ 531-- 532-- where the @at@ fields of @ALam@ are inductively subject to the same order. 533-- That is, @ALam os at1 < ALam os at2@ iff @at1 < at2@. 534-- 535-- Why the strange Top element? See Note [Combining case branches]. 536-- 537-- We rely on this lattice structure for fixed-point iteration in 538-- 'findRhsArity'. For the semantics of 'ArityType', see Note [ArityType]. 539data ArityType 540 = AT ![OneShotInfo] !Divergence 541 -- ^ @AT oss div@ means this value can safely be eta-expanded @length oss@ 542 -- times, provided use sites respect the 'OneShotInfo's in @oss@. 543 -- A 'OneShotLam' annotation can come from two sources: 544 -- * The user annotated a lambda as one-shot with 'GHC.Exts.oneShot' 545 -- * It's from a lambda binder of a type affected by `-fstate-hack`. 546 -- See 'idStateHackOneShotInfo'. 547 -- In both cases, 'OneShotLam' should win over 'NoOneShotInfo', see 548 -- Note [Combining case branches]. 549 -- 550 -- If @div@ is dead-ending ('isDeadEndDiv'), then application to 551 -- @length os@ arguments will surely diverge, similar to the situation 552 -- with 'DmdType'. 553 deriving Eq 554 555-- | This is the BNF of the generated output: 556-- 557-- @ 558-- @ 559-- 560-- We format 561-- @AT [o1,..,on] topDiv@ as @\o1..on.T@ and 562-- @AT [o1,..,on] botDiv@ as @\o1..on.⊥@, respectively. 563-- More concretely, @AT [NOI,OS,OS] topDiv@ is formatted as @\?11.T@. 564-- If the one-shot info is empty, we omit the leading @\.@. 565instance Outputable ArityType where 566 ppr (AT oss div) 567 | null oss = pp_div div 568 | otherwise = char '\\' <> hcat (map pp_os oss) <> dot <> pp_div div 569 where 570 pp_div Diverges = char '⊥' 571 pp_div ExnOrDiv = char 'x' 572 pp_div Dunno = char 'T' 573 pp_os OneShotLam = char '1' 574 pp_os NoOneShotInfo = char '?' 575 576mkBotArityType :: [OneShotInfo] -> ArityType 577mkBotArityType oss = AT oss botDiv 578 579botArityType :: ArityType 580botArityType = mkBotArityType [] 581 582mkTopArityType :: [OneShotInfo] -> ArityType 583mkTopArityType oss = AT oss topDiv 584 585topArityType :: ArityType 586topArityType = mkTopArityType [] 587 588-- | The number of value args for the arity type 589arityTypeArity :: ArityType -> Arity 590arityTypeArity (AT oss _) = length oss 591 592-- | True <=> eta-expansion will add at least one lambda 593expandableArityType :: ArityType -> Bool 594expandableArityType at = arityTypeArity at /= 0 595 596-- | See Note [Dead ends] in "GHC.Types.Demand". 597-- Bottom implies a dead end. 598isDeadEndArityType :: ArityType -> Bool 599isDeadEndArityType (AT _ div) = isDeadEndDiv div 600 601-- | Expand a non-bottoming arity type so that it has at least the given arity. 602maxWithArity :: ArityType -> Arity -> ArityType 603maxWithArity at@(AT oss div) !ar 604 | isDeadEndArityType at = at 605 | oss `lengthAtLeast` ar = at 606 | otherwise = AT (take ar $ oss ++ repeat NoOneShotInfo) div 607 608-- | Trim an arity type so that it has at most the given arity. 609-- Any excess 'OneShotInfo's are truncated to 'topDiv', even if they end in 610-- 'ABot'. 611minWithArity :: ArityType -> Arity -> ArityType 612minWithArity at@(AT oss _) ar 613 | oss `lengthAtMost` ar = at 614 | otherwise = AT (take ar oss) topDiv 615 616takeWhileOneShot :: ArityType -> ArityType 617takeWhileOneShot (AT oss div) 618 | isDeadEndDiv div = AT (takeWhile isOneShotInfo oss) topDiv 619 | otherwise = AT (takeWhile isOneShotInfo oss) div 620 621-- | The Arity returned is the number of value args the 622-- expression can be applied to without doing much work 623exprEtaExpandArity :: DynFlags -> CoreExpr -> ArityType 624-- exprEtaExpandArity is used when eta expanding 625-- e ==> \xy -> e x y 626exprEtaExpandArity dflags e = arityType (etaExpandArityEnv dflags) e 627 628getBotArity :: ArityType -> Maybe Arity 629-- Arity of a divergent function 630getBotArity (AT oss div) 631 | isDeadEndDiv div = Just $ length oss 632 | otherwise = Nothing 633 634---------------------- 635findRhsArity :: DynFlags -> Id -> CoreExpr -> Arity -> ArityType 636-- This implements the fixpoint loop for arity analysis 637-- See Note [Arity analysis] 638-- If findRhsArity e = (n, is_bot) then 639-- (a) any application of e to <n arguments will not do much work, 640-- so it is safe to expand e ==> (\x1..xn. e x1 .. xn) 641-- (b) if is_bot=True, then e applied to n args is guaranteed bottom 642findRhsArity dflags bndr rhs old_arity 643 = go 0 botArityType 644 -- We always do one step, but usually that produces a result equal to 645 -- old_arity, and then we stop right away, because old_arity is assumed 646 -- to be sound. In other words, arities should never decrease. 647 -- Result: the common case is that there is just one iteration 648 where 649 go :: Int -> ArityType -> ArityType 650 go !n cur_at@(AT oss div) 651 | not (isDeadEndDiv div) -- the "stop right away" case 652 , length oss <= old_arity = cur_at -- from above 653 | next_at == cur_at = cur_at 654 | otherwise = 655 -- Warn if more than 2 iterations. Why 2? See Note [Exciting arity] 656 WARN( debugIsOn && n > 2, text "Exciting arity" 657 $$ nest 2 ( 658 ppr bndr <+> ppr cur_at <+> ppr next_at 659 $$ ppr rhs) ) 660 go (n+1) next_at 661 where 662 next_at = step cur_at 663 664 step :: ArityType -> ArityType 665 step at = -- pprTrace "step" (ppr bndr <+> ppr at <+> ppr (arityType env rhs)) $ 666 arityType env rhs 667 where 668 env = extendSigEnv (findRhsArityEnv dflags) bndr at 669 670{- 671Note [Arity analysis] 672~~~~~~~~~~~~~~~~~~~~~ 673The motivating example for arity analysis is this: 674 675 f = \x. let g = f (x+1) 676 in \y. ...g... 677 678What arity does f have? Really it should have arity 2, but a naive 679look at the RHS won't see that. You need a fixpoint analysis which 680says it has arity "infinity" the first time round. 681 682This example happens a lot; it first showed up in Andy Gill's thesis, 683fifteen years ago! It also shows up in the code for 'rnf' on lists 684in #4138. 685 686We do the necessary, quite simple fixed-point iteration in 'findRhsArity', 687which assumes for a single binding 'ABot' on the first run and iterates 688until it finds a stable arity type. Two wrinkles 689 690* We often have to ask (see the Case or Let case of 'arityType') whether some 691 expression is cheap. In the case of an application, that depends on the arity 692 of the application head! That's why we have our own version of 'exprIsCheap', 693 'myExprIsCheap', that will integrate the optimistic arity types we have on 694 f and g into the cheapness check. 695 696* Consider this (#18793) 697 698 go = \ds. case ds of 699 [] -> id 700 (x:ys) -> let acc = go ys in 701 case blah of 702 True -> acc 703 False -> \ x1 -> acc (negate x1) 704 705 We must propagate go's optimistically large arity to @acc@, so that the 706 tail call to @acc@ in the True branch has sufficient arity. This is done 707 by the 'am_sigs' field in 'FindRhsArity', and 'lookupSigEnv' in the Var case 708 of 'arityType'. 709 710Note [Exciting Arity] 711~~~~~~~~~~~~~~~~~~~~~ 712The fixed-point iteration in 'findRhsArity' stabilises very quickly in almost 713all cases. To get notified of cases where we need an usual number of iterations, 714we emit a warning in debug mode, so that we can investigate and make sure that 715we really can't do better. It's a gross hack, but catches real bugs (#18870). 716 717Now, which number is "unusual"? We pick n > 2. Here's a pretty common and 718expected example that takes two iterations and would ruin the specificity 719of the warning (from T18937): 720 721 f :: [Int] -> Int -> Int 722 f [] = id 723 f (x:xs) = let y = sum [0..x] 724 in \z -> f xs (y + z) 725 726Fixed-point iteration starts with arity type ⊥ for f. After the first 727iteration, we get arity type \??.T, e.g. arity 2, because we unconditionally 728'floatIn' the let-binding (see its bottom case). After the second iteration, 729we get arity type \?.T, e.g. arity 1, because now we are no longer allowed 730to floatIn the non-cheap let-binding. Which is all perfectly benign, but 731means we do two iterations (well, actually 3 'step's to detect we are stable) 732and don't want to emit the warning. 733 734Note [Eta expanding through dictionaries] 735~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 736If the experimental -fdicts-cheap flag is on, we eta-expand through 737dictionary bindings. This improves arities. Thereby, it also 738means that full laziness is less prone to floating out the 739application of a function to its dictionary arguments, which 740can thereby lose opportunities for fusion. Example: 741 foo :: Ord a => a -> ... 742 foo = /\a \(d:Ord a). let d' = ...d... in \(x:a). .... 743 -- So foo has arity 1 744 745 f = \x. foo dInt $ bar x 746 747The (foo DInt) is floated out, and makes ineffective a RULE 748 foo (bar x) = ... 749 750One could go further and make exprIsCheap reply True to any 751dictionary-typed expression, but that's more work. 752-} 753 754arityLam :: Id -> ArityType -> ArityType 755arityLam id (AT oss div) = AT (idStateHackOneShotInfo id : oss) div 756 757floatIn :: Bool -> ArityType -> ArityType 758-- We have something like (let x = E in b), 759-- where b has the given arity type. 760floatIn cheap at 761 | isDeadEndArityType at || cheap = at 762 -- If E is not cheap, keep arity only for one-shots 763 | otherwise = takeWhileOneShot at 764 765arityApp :: ArityType -> Bool -> ArityType 766-- Processing (fun arg) where at is the ArityType of fun, 767-- Knock off an argument and behave like 'let' 768arityApp (AT (_:oss) div) cheap = floatIn cheap (AT oss div) 769arityApp at _ = at 770 771-- | Least upper bound in the 'ArityType' lattice. 772-- See the haddocks on 'ArityType' for the lattice. 773-- 774-- Used for branches of a @case@. 775andArityType :: ArityType -> ArityType -> ArityType 776andArityType (AT (os1:oss1) div1) (AT (os2:oss2) div2) 777 | AT oss' div' <- andArityType (AT oss1 div1) (AT oss2 div2) 778 = AT ((os1 `bestOneShot` os2) : oss') div' -- See Note [Combining case branches] 779andArityType (AT [] div1) at2 780 | isDeadEndDiv div1 = at2 -- Note [ABot branches: max arity wins] 781 | otherwise = takeWhileOneShot at2 -- See Note [Combining case branches] 782andArityType at1 (AT [] div2) 783 | isDeadEndDiv div2 = at1 -- Note [ABot branches: max arity wins] 784 | otherwise = takeWhileOneShot at1 -- See Note [Combining case branches] 785 786{- Note [ABot branches: max arity wins] 787~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 788Consider case x of 789 True -> \x. error "urk" 790 False -> \xy. error "urk2" 791 792Remember: \o1..on.⊥ means "if you apply to n args, it'll definitely diverge". 793So we need \??.⊥ for the whole thing, the /max/ of both arities. 794 795Note [Combining case branches] 796~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 797Consider 798 go = \x. let z = go e0 799 go2 = \x. case x of 800 True -> z 801 False -> \s(one-shot). e1 802 in go2 x 803We *really* want to respect the one-shot annotation provided by the 804user and eta-expand go and go2. 805When combining the branches of the case we have 806 T `andAT` \1.T 807and we want to get \1.T. 808But if the inner lambda wasn't one-shot (\?.T) we don't want to do this. 809(We need a usage analysis to justify that.) 810 811So we combine the best of the two branches, on the (slightly dodgy) 812basis that if we know one branch is one-shot, then they all must be. 813Surprisingly, this means that the one-shot arity type is effectively the top 814element of the lattice. 815 816Note [Arity trimming] 817~~~~~~~~~~~~~~~~~~~~~ 818Consider ((\x y. blah) |> co), where co :: (Int->Int->Int) ~ (Int -> F a) , and 819F is some type family. 820 821Because of Note [exprArity invariant], item (2), we must return with arity at 822most 1, because typeArity (Int -> F a) = 1. So we have to trim the result of 823calling arityType on (\x y. blah). Failing to do so, and hence breaking the 824exprArity invariant, led to #5441. 825 826How to trim? If we end in topDiv, it's easy. But we must take great care with 827dead ends (i.e. botDiv). Suppose the expression was (\x y. error "urk"), 828we'll get \??.⊥. We absolutely must not trim that to \?.⊥, because that 829claims that ((\x y. error "urk") |> co) diverges when given one argument, 830which it absolutely does not. And Bad Things happen if we think something 831returns bottom when it doesn't (#16066). 832 833So, if we need to trim a dead-ending arity type, switch (conservatively) to 834topDiv. 835 836Historical note: long ago, we unconditionally switched to topDiv when we 837encountered a cast, but that is far too conservative: see #5475 838-} 839 840--------------------------- 841 842-- | Each of the entry-points of the analyser ('arityType') has different 843-- requirements. The entry-points are 844-- 845-- 1. 'exprBotStrictness_maybe' 846-- 2. 'exprEtaExpandArity' 847-- 3. 'findRhsArity' 848-- 849-- For each of the entry-points, there is a separate mode that governs 850-- 851-- 1. How pedantic we are wrt. ⊥, in 'pedanticBottoms'. 852-- 2. Whether we store arity signatures for non-recursive let-bindings, 853-- accessed in 'extendSigEnv'/'lookupSigEnv'. 854-- See Note [Arity analysis] why that's important. 855-- 3. Which expressions we consider cheap to float inside a lambda, 856-- in 'myExprIsCheap'. 857data AnalysisMode 858 = BotStrictness 859 -- ^ Used during 'exprBotStrictness_maybe'. 860 | EtaExpandArity { am_ped_bot :: !Bool 861 , am_dicts_cheap :: !Bool } 862 -- ^ Used for finding an expression's eta-expanding arity quickly, without 863 -- fixed-point iteration ('exprEtaExpandArity'). 864 | FindRhsArity { am_ped_bot :: !Bool 865 , am_dicts_cheap :: !Bool 866 , am_sigs :: !(IdEnv ArityType) } 867 -- ^ Used for regular, fixed-point arity analysis ('findRhsArity'). 868 -- See Note [Arity analysis] for details about fixed-point iteration. 869 -- INVARIANT: Disjoint with 'ae_joins'. 870 871data ArityEnv 872 = AE 873 { ae_mode :: !AnalysisMode 874 -- ^ The analysis mode. See 'AnalysisMode'. 875 , ae_joins :: !IdSet 876 -- ^ In-scope join points. See Note [Eta-expansion and join points] 877 -- INVARIANT: Disjoint with the domain of 'am_sigs' (if present). 878 } 879 880-- | The @ArityEnv@ used by 'exprBotStrictness_maybe'. Pedantic about bottoms 881-- and no application is ever considered cheap. 882botStrictnessArityEnv :: ArityEnv 883botStrictnessArityEnv = AE { ae_mode = BotStrictness, ae_joins = emptyVarSet } 884 885-- | The @ArityEnv@ used by 'exprEtaExpandArity'. 886etaExpandArityEnv :: DynFlags -> ArityEnv 887etaExpandArityEnv dflags 888 = AE { ae_mode = EtaExpandArity { am_ped_bot = gopt Opt_PedanticBottoms dflags 889 , am_dicts_cheap = gopt Opt_DictsCheap dflags } 890 , ae_joins = emptyVarSet } 891 892-- | The @ArityEnv@ used by 'findRhsArity'. 893findRhsArityEnv :: DynFlags -> ArityEnv 894findRhsArityEnv dflags 895 = AE { ae_mode = FindRhsArity { am_ped_bot = gopt Opt_PedanticBottoms dflags 896 , am_dicts_cheap = gopt Opt_DictsCheap dflags 897 , am_sigs = emptyVarEnv } 898 , ae_joins = emptyVarSet } 899 900-- First some internal functions in snake_case for deleting in certain VarEnvs 901-- of the ArityType. Don't call these; call delInScope* instead! 902 903modifySigEnv :: (IdEnv ArityType -> IdEnv ArityType) -> ArityEnv -> ArityEnv 904modifySigEnv f env@AE { ae_mode = am@FindRhsArity{am_sigs = sigs} } = 905 env { ae_mode = am { am_sigs = f sigs } } 906modifySigEnv _ env = env 907{-# INLINE modifySigEnv #-} 908 909del_sig_env :: Id -> ArityEnv -> ArityEnv -- internal! 910del_sig_env id = modifySigEnv (\sigs -> delVarEnv sigs id) 911{-# INLINE del_sig_env #-} 912 913del_sig_env_list :: [Id] -> ArityEnv -> ArityEnv -- internal! 914del_sig_env_list ids = modifySigEnv (\sigs -> delVarEnvList sigs ids) 915{-# INLINE del_sig_env_list #-} 916 917del_join_env :: JoinId -> ArityEnv -> ArityEnv -- internal! 918del_join_env id env@(AE { ae_joins = joins }) 919 = env { ae_joins = delVarSet joins id } 920{-# INLINE del_join_env #-} 921 922del_join_env_list :: [JoinId] -> ArityEnv -> ArityEnv -- internal! 923del_join_env_list ids env@(AE { ae_joins = joins }) 924 = env { ae_joins = delVarSetList joins ids } 925{-# INLINE del_join_env_list #-} 926 927-- end of internal deletion functions 928 929extendJoinEnv :: ArityEnv -> [JoinId] -> ArityEnv 930extendJoinEnv env@(AE { ae_joins = joins }) join_ids 931 = del_sig_env_list join_ids 932 $ env { ae_joins = joins `extendVarSetList` join_ids } 933 934extendSigEnv :: ArityEnv -> Id -> ArityType -> ArityEnv 935extendSigEnv env id ar_ty 936 = del_join_env id (modifySigEnv (\sigs -> extendVarEnv sigs id ar_ty) env) 937 938delInScope :: ArityEnv -> Id -> ArityEnv 939delInScope env id = del_join_env id $ del_sig_env id env 940 941delInScopeList :: ArityEnv -> [Id] -> ArityEnv 942delInScopeList env ids = del_join_env_list ids $ del_sig_env_list ids env 943 944lookupSigEnv :: ArityEnv -> Id -> Maybe ArityType 945lookupSigEnv AE{ ae_mode = mode } id = case mode of 946 BotStrictness -> Nothing 947 EtaExpandArity{} -> Nothing 948 FindRhsArity{ am_sigs = sigs } -> lookupVarEnv sigs id 949 950-- | Whether the analysis should be pedantic about bottoms. 951-- 'exprBotStrictness_maybe' always is. 952pedanticBottoms :: ArityEnv -> Bool 953pedanticBottoms AE{ ae_mode = mode } = case mode of 954 BotStrictness -> True 955 EtaExpandArity{ am_ped_bot = ped_bot } -> ped_bot 956 FindRhsArity{ am_ped_bot = ped_bot } -> ped_bot 957 958-- | A version of 'exprIsCheap' that considers results from arity analysis 959-- and optionally the expression's type. 960-- Under 'exprBotStrictness_maybe', no expressions are cheap. 961myExprIsCheap :: ArityEnv -> CoreExpr -> Maybe Type -> Bool 962myExprIsCheap AE{ae_mode = mode} e mb_ty = case mode of 963 BotStrictness -> False 964 _ -> cheap_dict || cheap_fun e 965 where 966 cheap_dict = am_dicts_cheap mode && fmap isDictTy mb_ty == Just True 967 cheap_fun e = case mode of 968#if __GLASGOW_HASKELL__ <= 900 969 BotStrictness -> panic "impossible" 970#endif 971 EtaExpandArity{} -> exprIsCheap e 972 FindRhsArity{am_sigs = sigs} -> exprIsCheapX (myIsCheapApp sigs) e 973 974-- | A version of 'isCheapApp' that considers results from arity analysis. 975-- See Note [Arity analysis] for what's in the signature environment and why 976-- it's important. 977myIsCheapApp :: IdEnv ArityType -> CheapAppFun 978myIsCheapApp sigs fn n_val_args = case lookupVarEnv sigs fn of 979 -- Nothing means not a local function, fall back to regular 980 -- 'GHC.Core.Utils.isCheapApp' 981 Nothing -> isCheapApp fn n_val_args 982 -- @Just at@ means local function with @at@ as current ArityType. 983 -- Roughly approximate what 'isCheapApp' is doing. 984 Just (AT oss div) 985 | isDeadEndDiv div -> True -- See Note [isCheapApp: bottoming functions] in GHC.Core.Utils 986 | n_val_args < length oss -> True -- Essentially isWorkFreeApp 987 | otherwise -> False 988 989---------------- 990arityType :: ArityEnv -> CoreExpr -> ArityType 991 992arityType env (Cast e co) 993 = minWithArity (arityType env e) co_arity -- See Note [Arity trimming] 994 where 995 co_arity = length (typeArity (coercionRKind co)) 996 -- See Note [exprArity invariant] (2); must be true of 997 -- arityType too, since that is how we compute the arity 998 -- of variables, and they in turn affect result of exprArity 999 -- #5441 is a nice demo 1000 1001arityType env (Var v) 1002 | v `elemVarSet` ae_joins env 1003 = botArityType -- See Note [Eta-expansion and join points] 1004 | Just at <- lookupSigEnv env v -- Local binding 1005 = at 1006 | otherwise 1007 = idArityType v 1008 1009 -- Lambdas; increase arity 1010arityType env (Lam x e) 1011 | isId x = arityLam x (arityType env' e) 1012 | otherwise = arityType env' e 1013 where 1014 env' = delInScope env x 1015 1016 -- Applications; decrease arity, except for types 1017arityType env (App fun (Type _)) 1018 = arityType env fun 1019arityType env (App fun arg ) 1020 = arityApp (arityType env fun) (myExprIsCheap env arg Nothing) 1021 1022 -- Case/Let; keep arity if either the expression is cheap 1023 -- or it's a 1-shot lambda 1024 -- The former is not really right for Haskell 1025 -- f x = case x of { (a,b) -> \y. e } 1026 -- ===> 1027 -- f x y = case x of { (a,b) -> e } 1028 -- The difference is observable using 'seq' 1029 -- 1030arityType env (Case scrut bndr _ alts) 1031 | exprIsDeadEnd scrut || null alts 1032 = botArityType -- Do not eta expand. See Note [Dealing with bottom (1)] 1033 | not (pedanticBottoms env) -- See Note [Dealing with bottom (2)] 1034 , myExprIsCheap env scrut (Just (idType bndr)) 1035 = alts_type 1036 | exprOkForSpeculation scrut 1037 = alts_type 1038 1039 | otherwise -- In the remaining cases we may not push 1040 = takeWhileOneShot alts_type -- evaluation of the scrutinee in 1041 where 1042 env' = delInScope env bndr 1043 arity_type_alt (Alt _con bndrs rhs) = arityType (delInScopeList env' bndrs) rhs 1044 alts_type = foldr1 andArityType (map arity_type_alt alts) 1045 1046arityType env (Let (NonRec j rhs) body) 1047 | Just join_arity <- isJoinId_maybe j 1048 , (_, rhs_body) <- collectNBinders join_arity rhs 1049 = -- See Note [Eta-expansion and join points] 1050 andArityType (arityType env rhs_body) 1051 (arityType env' body) 1052 where 1053 env' = extendJoinEnv env [j] 1054 1055arityType env (Let (Rec pairs) body) 1056 | ((j,_):_) <- pairs 1057 , isJoinId j 1058 = -- See Note [Eta-expansion and join points] 1059 foldr (andArityType . do_one) (arityType env' body) pairs 1060 where 1061 env' = extendJoinEnv env (map fst pairs) 1062 do_one (j,rhs) 1063 | Just arity <- isJoinId_maybe j 1064 = arityType env' $ snd $ collectNBinders arity rhs 1065 | otherwise 1066 = pprPanic "arityType:joinrec" (ppr pairs) 1067 1068arityType env (Let (NonRec b r) e) 1069 = floatIn cheap_rhs (arityType env' e) 1070 where 1071 cheap_rhs = myExprIsCheap env r (Just (idType b)) 1072 env' = extendSigEnv env b (arityType env r) 1073 1074arityType env (Let (Rec prs) e) 1075 = floatIn (all is_cheap prs) (arityType env' e) 1076 where 1077 env' = delInScopeList env (map fst prs) 1078 is_cheap (b,e) = myExprIsCheap env' e (Just (idType b)) 1079 1080arityType env (Tick t e) 1081 | not (tickishIsCode t) = arityType env e 1082 1083arityType _ _ = topArityType 1084 1085{- Note [Eta-expansion and join points] 1086~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 1087Consider this (#18328) 1088 1089 f x = join j y = case y of 1090 True -> \a. blah 1091 False -> \b. blah 1092 in case x of 1093 A -> j True 1094 B -> \c. blah 1095 C -> j False 1096 1097and suppose the join point is too big to inline. Now, what is the 1098arity of f? If we inlined the join point, we'd definitely say "arity 10992" because we are prepared to push case-scrutinisation inside a 1100lambda. But currently the join point totally messes all that up, 1101because (thought of as a vanilla let-binding) the arity pinned on 'j' 1102is just 1. 1103 1104Why don't we eta-expand j? Because of 1105Note [Do not eta-expand join points] in GHC.Core.Opt.Simplify.Utils 1106 1107Even if we don't eta-expand j, why is its arity only 1? 1108See invariant 2b in Note [Invariants on join points] in GHC.Core. 1109 1110So we do this: 1111 1112* Treat the RHS of a join-point binding, /after/ stripping off 1113 join-arity lambda-binders, as very like the body of the let. 1114 More precisely, do andArityType with the arityType from the 1115 body of the let. 1116 1117* Dually, when we come to a /call/ of a join point, just no-op 1118 by returning ABot, the bottom element of ArityType, 1119 which so that: bot `andArityType` x = x 1120 1121* This works if the join point is bound in the expression we are 1122 taking the arityType of. But if it's bound further out, it makes 1123 no sense to say that (say) the arityType of (j False) is ABot. 1124 Bad things happen. So we keep track of the in-scope join-point Ids 1125 in ae_join. 1126 1127This will make f, above, have arity 2. Then, we'll eta-expand it thus: 1128 1129 f x eta = (join j y = ... in case x of ...) eta 1130 1131and the Simplify will automatically push that application of eta into 1132the join points. 1133 1134An alternative (roughly equivalent) idea would be to carry an 1135environment mapping let-bound Ids to their ArityType. 1136-} 1137 1138idArityType :: Id -> ArityType 1139idArityType v 1140 | strict_sig <- idStrictness v 1141 , not $ isTopSig strict_sig 1142 , (ds, div) <- splitStrictSig strict_sig 1143 , let arity = length ds 1144 -- Every strictness signature admits an arity signature! 1145 = AT (take arity one_shots) div 1146 | otherwise 1147 = AT (take (idArity v) one_shots) topDiv 1148 where 1149 one_shots :: [OneShotInfo] -- One-shot-ness derived from the type 1150 one_shots = typeArity (idType v) 1151 1152{- 1153%************************************************************************ 1154%* * 1155 The main eta-expander 1156%* * 1157%************************************************************************ 1158 1159We go for: 1160 f = \x1..xn -> N ==> f = \x1..xn y1..ym -> N y1..ym 1161 (n >= 0) 1162 1163where (in both cases) 1164 1165 * The xi can include type variables 1166 1167 * The yi are all value variables 1168 1169 * N is a NORMAL FORM (i.e. no redexes anywhere) 1170 wanting a suitable number of extra args. 1171 1172The biggest reason for doing this is for cases like 1173 1174 f = \x -> case x of 1175 True -> \y -> e1 1176 False -> \y -> e2 1177 1178Here we want to get the lambdas together. A good example is the nofib 1179program fibheaps, which gets 25% more allocation if you don't do this 1180eta-expansion. 1181 1182We may have to sandwich some coerces between the lambdas 1183to make the types work. exprEtaExpandArity looks through coerces 1184when computing arity; and etaExpand adds the coerces as necessary when 1185actually computing the expansion. 1186 1187Note [No crap in eta-expanded code] 1188~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 1189The eta expander is careful not to introduce "crap". In particular, 1190given a CoreExpr satisfying the 'CpeRhs' invariant (in CorePrep), it 1191returns a CoreExpr satisfying the same invariant. See Note [Eta 1192expansion and the CorePrep invariants] in CorePrep. 1193 1194This means the eta-expander has to do a bit of on-the-fly 1195simplification but it's not too hard. The alternative, of relying on 1196a subsequent clean-up phase of the Simplifier to de-crapify the result, 1197means you can't really use it in CorePrep, which is painful. 1198 1199Note [Eta expansion for join points] 1200~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 1201The no-crap rule is very tiresome to guarantee when 1202we have join points. Consider eta-expanding 1203 let j :: Int -> Int -> Bool 1204 j x = e 1205 in b 1206 1207The simple way is 1208 \(y::Int). (let j x = e in b) y 1209 1210The no-crap way is 1211 \(y::Int). let j' :: Int -> Bool 1212 j' x = e y 1213 in b[j'/j] y 1214where I have written to stress that j's type has 1215changed. Note that (of course!) we have to push the application 1216inside the RHS of the join as well as into the body. AND if j 1217has an unfolding we have to push it into there too. AND j might 1218be recursive... 1219 1220So for now I'm abandoning the no-crap rule in this case. I think 1221that for the use in CorePrep it really doesn't matter; and if 1222it does, then CoreToStg.myCollectArgs will fall over. 1223 1224(Moreover, I think that casts can make the no-crap rule fail too.) 1225 1226Note [Eta expansion and SCCs] 1227~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 1228Note that SCCs are not treated specially by etaExpand. If we have 1229 etaExpand 2 (\x -> scc "foo" e) 1230 = (\xy -> (scc "foo" e) y) 1231So the costs of evaluating 'e' (not 'e y') are attributed to "foo" 1232 1233Note [Eta expansion and source notes] 1234~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 1235CorePrep puts floatable ticks outside of value applications, but not 1236type applications. As a result we might be trying to eta-expand an 1237expression like 1238 1239 (src<...> v) @a 1240 1241which we want to lead to code like 1242 1243 \x -> src<...> v @a x 1244 1245This means that we need to look through type applications and be ready 1246to re-add floats on the top. 1247 1248Note [Eta expansion with ArityType] 1249~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 1250The etaExpandAT function takes an ArityType (not just an Arity) to 1251guide eta-expansion. Why? Because we want to preserve one-shot info. 1252Consider 1253 foo = \x. case x of 1254 True -> (\s{os}. blah) |> co 1255 False -> wubble 1256We'll get an ArityType for foo of \?1.T. 1257 1258Then we want to eta-expand to 1259 foo = \x. (\eta{os}. (case x of ...as before...) eta) |> some_co 1260 1261That 'eta' binder is fresh, and we really want it to have the 1262one-shot flag from the inner \s{os}. By expanding with the 1263ArityType gotten from analysing the RHS, we achieve this neatly. 1264 1265This makes a big difference to the one-shot monad trick; 1266see Note [The one-shot state monad trick] in GHC.Utils.Monad. 1267-} 1268 1269-- | @etaExpand n e@ returns an expression with 1270-- the same meaning as @e@, but with arity @n@. 1271-- 1272-- Given: 1273-- 1274-- > e' = etaExpand n e 1275-- 1276-- We should have that: 1277-- 1278-- > ty = exprType e = exprType e' 1279etaExpand :: Arity -> CoreExpr -> CoreExpr 1280etaExpandAT :: ArityType -> CoreExpr -> CoreExpr 1281 1282etaExpand n orig_expr = eta_expand (replicate n NoOneShotInfo) orig_expr 1283etaExpandAT (AT oss _) orig_expr = eta_expand oss orig_expr 1284 -- See Note [Eta expansion with ArityType] 1285 1286-- etaExpand arity e = res 1287-- Then 'res' has at least 'arity' lambdas at the top 1288-- See Note [Eta expansion with ArityType] 1289-- 1290-- etaExpand deals with for-alls. For example: 1291-- etaExpand 1 E 1292-- where E :: forall a. a -> a 1293-- would return 1294-- (/\b. \y::a -> E b y) 1295-- 1296-- It deals with coerces too, though they are now rare 1297-- so perhaps the extra code isn't worth it 1298 1299eta_expand :: [OneShotInfo] -> CoreExpr -> CoreExpr 1300eta_expand one_shots orig_expr 1301 = go one_shots orig_expr 1302 where 1303 -- Strip off existing lambdas and casts before handing off to mkEtaWW 1304 -- Note [Eta expansion and SCCs] 1305 go [] expr = expr 1306 go oss@(_:oss1) (Lam v body) | isTyVar v = Lam v (go oss body) 1307 | otherwise = Lam v (go oss1 body) 1308 go oss (Cast expr co) = Cast (go oss expr) co 1309 1310 go oss expr 1311 = -- pprTrace "ee" (vcat [ppr orig_expr, ppr expr, pprEtaInfos etas]) $ 1312 retick $ etaInfoAbs etas (etaInfoApp in_scope' sexpr etas) 1313 where 1314 in_scope = mkInScopeSet (exprFreeVars expr) 1315 (in_scope', etas) = mkEtaWW oss (ppr orig_expr) in_scope (exprType expr) 1316 1317 -- Find ticks behind type apps. 1318 -- See Note [Eta expansion and source notes] 1319 (expr', args) = collectArgs expr 1320 (ticks, expr'') = stripTicksTop tickishFloatable expr' 1321 sexpr = foldl' App expr'' args 1322 retick expr = foldr mkTick expr ticks 1323 1324{- ********************************************************************* 1325* * 1326 The EtaInfo mechanism 1327 mkEtaWW, etaInfoAbs, etaInfoApp 1328* * 1329********************************************************************* -} 1330 1331{- Note [The EtaInfo mechanism] 1332~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 1333Suppose we have (e :: ty) and we want to eta-expand it to arity N. 1334This what eta_expand does. We do it in two steps: 1335 13361. mkEtaWW: from 'ty' and 'N' build a [EtaInfo] which describes 1337 the shape of the expansion necessary to expand to arity N. 1338 13392. Build the term 1340 \ v1..vn. e v1 .. vn 1341 where those abstractions and applications are described by 1342 the same [EtaInfo]. Specifically we build the term 1343 1344 etaInfoAbs etas (etaInfoApp in_scope e etas) 1345 1346 where etas :: [EtaInfo]# 1347 etaInfoAbs builds the lambdas 1348 etaInfoApp builds the applictions 1349 1350 Note that the /same/ [EtaInfo] drives both etaInfoAbs and etaInfoApp 1351 1352To a first approximation [EtaInfo] is just [Var]. But 1353casts complicate the question. If we have 1354 newtype N a = MkN (S -> a) 1355and 1356 ty = N (N Int) 1357then the eta-expansion must look like 1358 (\x (\y. ((e |> co1) x) |> co2) y) 1359 |> sym co2) 1360 |> sym co1 1361where 1362 co1 :: N (N Int) ~ S -> N Int 1363 co2 :: N Int ~ S -> Int 1364 1365Blimey! Look at all those casts. Moreover, if the type 1366is very deeply nested (as happens in #18223), the repetition 1367of types can make the overall term very large. So there is a big 1368payoff in cancelling out casts aggressively wherever possible. 1369(See also Note [No crap in eta-expanded code].) 1370 1371This matters a lot in etaEInfoApp, where we 1372* Do beta-reduction on the fly 1373* Use getARg_mabye to get a cast out of the way, 1374 so that we can do beta reduction 1375Together this makes a big difference. Consider when e is 1376 case x of 1377 True -> (\x -> e1) |> c1 1378 False -> (\p -> e2) |> c2 1379 1380When we eta-expand this to arity 1, say, etaInfoAbs will wrap 1381a (\eta) around the outside and use etaInfoApp to apply each 1382alternative to 'eta'. We want to beta-reduce all that junk 1383away. 1384 1385#18223 was a dramatic example in which the intermediate term was 1386grotesquely huge, even though the next Simplifier iteration squashed 1387it. Better to kill it at birth. 1388-} 1389 1390-------------- 1391data EtaInfo -- Abstraction Application 1392 = EtaVar Var -- /\a. [] [] a 1393 -- (\x. []) [] x 1394 | EtaCo CoercionR -- [] |> sym co [] |> co 1395 1396instance Outputable EtaInfo where 1397 ppr (EtaVar v) = text "EtaVar" <+> ppr v <+> dcolon <+> ppr (idType v) 1398 ppr (EtaCo co) = text "EtaCo" <+> hang (ppr co) 2 (dcolon <+> ppr (coercionType co)) 1399 1400-- Used in debug-printing 1401-- pprEtaInfos :: [EtaInfo] -> SDoc 1402-- pprEtaInfos eis = brackets $ vcat $ punctuate comma $ map ppr eis 1403 1404pushCoercion :: Coercion -> [EtaInfo] -> [EtaInfo] 1405-- Puts a EtaCo on the front of a [EtaInfo], but combining 1406-- with an existing EtaCo if possible 1407-- A minor improvement 1408pushCoercion co1 (EtaCo co2 : eis) 1409 | isReflCo co = eis 1410 | otherwise = EtaCo co : eis 1411 where 1412 co = co1 `mkTransCo` co2 1413 1414pushCoercion co eis 1415 = EtaCo co : eis 1416 1417getArg_maybe :: [EtaInfo] -> Maybe (CoreArg, [EtaInfo]) 1418-- Get an argument to the front of the [EtaInfo], if possible, 1419-- by pushing any EtaCo through the argument 1420getArg_maybe eis = go MRefl eis 1421 where 1422 go :: MCoercion -> [EtaInfo] -> Maybe (CoreArg, [EtaInfo]) 1423 go _ [] = Nothing 1424 go mco (EtaCo co2 : eis) = go (mkTransMCoL mco co2) eis 1425 go MRefl (EtaVar v : eis) = Just (varToCoreExpr v, eis) 1426 go (MCo co) (EtaVar v : eis) 1427 | Just (arg, mco) <- pushCoArg co (varToCoreExpr v) 1428 = case mco of 1429 MRefl -> Just (arg, eis) 1430 MCo co -> Just (arg, pushCoercion co eis) 1431 | otherwise 1432 = Nothing 1433 1434mkCastMCo :: CoreExpr -> MCoercionR -> CoreExpr 1435mkCastMCo e MRefl = e 1436mkCastMCo e (MCo co) = Cast e co 1437 -- We are careful to use (MCo co) only when co is not reflexive 1438 -- Hence (Cast e co) rather than (mkCast e co) 1439 1440mkPiMCo :: Var -> MCoercionR -> MCoercionR 1441mkPiMCo _ MRefl = MRefl 1442mkPiMCo v (MCo co) = MCo (mkPiCo Representational v co) 1443 1444-------------- 1445etaInfoAbs :: [EtaInfo] -> CoreExpr -> CoreExpr 1446-- See Note [The EtaInfo mechanism] 1447etaInfoAbs eis expr 1448 | null eis = expr 1449 | otherwise = case final_mco of 1450 MRefl -> expr' 1451 MCo co -> mkCast expr' co 1452 where 1453 (expr', final_mco) = foldr do_one (split_cast expr) eis 1454 1455 do_one :: EtaInfo -> (CoreExpr, MCoercion) -> (CoreExpr, MCoercion) 1456 -- Implements the "Abstraction" column in the comments for data EtaInfo 1457 -- In both argument and result the pair (e,mco) denotes (e |> mco) 1458 do_one (EtaVar v) (expr, mco) = (Lam v expr, mkPiMCo v mco) 1459 do_one (EtaCo co) (expr, mco) = (expr, mco `mkTransMCoL` mkSymCo co) 1460 1461 split_cast :: CoreExpr -> (CoreExpr, MCoercion) 1462 split_cast (Cast e co) = (e, MCo co) 1463 split_cast e = (e, MRefl) 1464 -- We could look in the body of lets, and the branches of a case 1465 -- But then we would have to worry about whether the cast mentioned 1466 -- any of the bound variables, which is tiresome. Later maybe. 1467 -- Result: we may end up with 1468 -- (\(x::Int). case x of { DEFAULT -> e1 |> co }) |> sym (<Int>->co) 1469 -- and fail to optimise it away 1470 1471-------------- 1472etaInfoApp :: InScopeSet -> CoreExpr -> [EtaInfo] -> CoreExpr 1473-- (etaInfoApp s e eis) returns something equivalent to 1474-- (substExpr s e `appliedto` eis) 1475-- See Note [The EtaInfo mechanism] 1476 1477etaInfoApp in_scope expr eis 1478 = go (mkEmptySubst in_scope) expr eis 1479 where 1480 go :: Subst -> CoreExpr -> [EtaInfo] -> CoreExpr 1481 -- 'go' pushed down the eta-infos into the branch of a case 1482 -- and the body of a let; and does beta-reduction if possible 1483 go subst (Tick t e) eis 1484 = Tick (substTickish subst t) (go subst e eis) 1485 go subst (Cast e co) eis 1486 = go subst e (pushCoercion (Core.substCo subst co) eis) 1487 go subst (Case e b ty alts) eis 1488 = Case (Core.substExprSC subst e) b1 ty' alts' 1489 where 1490 (subst1, b1) = Core.substBndr subst b 1491 alts' = map subst_alt alts 1492 ty' = etaInfoAppTy (Core.substTy subst ty) eis 1493 subst_alt (Alt con bs rhs) = Alt con bs' (go subst2 rhs eis) 1494 where 1495 (subst2,bs') = Core.substBndrs subst1 bs 1496 go subst (Let b e) eis 1497 | not (isJoinBind b) -- See Note [Eta expansion for join points] 1498 = Let b' (go subst' e eis) 1499 where 1500 (subst', b') = Core.substBindSC subst b 1501 1502 -- Beta-reduction if possible, using getArg_maybe to push 1503 -- any intervening casts past the argument 1504 -- See Note [The EtaInfo mechansim] 1505 go subst (Lam v e) eis 1506 | Just (arg, eis') <- getArg_maybe eis 1507 = go (Core.extendSubst subst v arg) e eis' 1508 1509 -- Stop pushing down; just wrap the expression up 1510 go subst e eis = wrap (Core.substExprSC subst e) eis 1511 1512 wrap e [] = e 1513 wrap e (EtaVar v : eis) = wrap (App e (varToCoreExpr v)) eis 1514 wrap e (EtaCo co : eis) = wrap (Cast e co) eis 1515 1516 1517-------------- 1518etaInfoAppTy :: Type -> [EtaInfo] -> Type 1519-- If e :: ty 1520-- then etaInfoApp e eis :: etaInfoApp ty eis 1521etaInfoAppTy ty [] = ty 1522etaInfoAppTy ty (EtaVar v : eis) = etaInfoAppTy (applyTypeToArg ty (varToCoreExpr v)) eis 1523etaInfoAppTy _ (EtaCo co : eis) = etaInfoAppTy (coercionRKind co) eis 1524 1525-------------- 1526-- | @mkEtaWW n _ fvs ty@ will compute the 'EtaInfo' necessary for eta-expanding 1527-- an expression @e :: ty@ to take @n@ value arguments, where @fvs@ are the 1528-- free variables of @e@. 1529-- 1530-- Note that this function is entirely unconcerned about cost centres and other 1531-- semantically-irrelevant source annotations, so call sites must take care to 1532-- preserve that info. See Note [Eta expansion and SCCs]. 1533mkEtaWW 1534 :: [OneShotInfo] 1535 -- ^ How many value arguments to eta-expand 1536 -> SDoc 1537 -- ^ The pretty-printed original expression, for warnings. 1538 -> InScopeSet 1539 -- ^ A super-set of the free vars of the expression to eta-expand. 1540 -> Type 1541 -> (InScopeSet, [EtaInfo]) 1542 -- ^ The variables in 'EtaInfo' are fresh wrt. to the incoming 'InScopeSet'. 1543 -- The outgoing 'InScopeSet' extends the incoming 'InScopeSet' with the 1544 -- fresh variables in 'EtaInfo'. 1545 1546mkEtaWW orig_oss ppr_orig_expr in_scope orig_ty 1547 = go 0 orig_oss empty_subst orig_ty [] 1548 where 1549 empty_subst = mkEmptyTCvSubst in_scope 1550 1551 go :: Int -- For fresh names 1552 -> [OneShotInfo] -- Number of value args to expand to 1553 -> TCvSubst -> Type -- We are really looking at subst(ty) 1554 -> [EtaInfo] -- Accumulating parameter 1555 -> (InScopeSet, [EtaInfo]) 1556 go _ [] subst _ eis -- See Note [exprArity invariant] 1557 ----------- Done! No more expansion needed 1558 = (getTCvInScope subst, reverse eis) 1559 1560 go n oss@(one_shot:oss1) subst ty eis -- See Note [exprArity invariant] 1561 ----------- Forall types (forall a. ty) 1562 | Just (tcv,ty') <- splitForAllTyCoVar_maybe ty 1563 , (subst', tcv') <- Type.substVarBndr subst tcv 1564 , let oss' | isTyVar tcv = oss 1565 | otherwise = oss1 1566 -- A forall can bind a CoVar, in which case 1567 -- we consume one of the [OneShotInfo] 1568 = go n oss' subst' ty' (EtaVar tcv' : eis) 1569 1570 ----------- Function types (t1 -> t2) 1571 | Just (mult, arg_ty, res_ty) <- splitFunTy_maybe ty 1572 , not (isTypeLevPoly arg_ty) 1573 -- See Note [Levity polymorphism invariants] in GHC.Core 1574 -- See also test case typecheck/should_run/EtaExpandLevPoly 1575 1576 , (subst', eta_id) <- freshEtaId n subst (Scaled mult arg_ty) 1577 -- Avoid free vars of the original expression 1578 1579 , let eta_id' = eta_id `setIdOneShotInfo` one_shot 1580 = go (n+1) oss1 subst' res_ty (EtaVar eta_id' : eis) 1581 1582 ----------- Newtypes 1583 -- Given this: 1584 -- newtype T = MkT ([T] -> Int) 1585 -- Consider eta-expanding this 1586 -- eta_expand 1 e T 1587 -- We want to get 1588 -- coerce T (\x::[T] -> (coerce ([T]->Int) e) x) 1589 | Just (co, ty') <- topNormaliseNewType_maybe ty 1590 , let co' = Type.substCo subst co 1591 -- Remember to apply the substitution to co (#16979) 1592 -- (or we could have applied to ty, but then 1593 -- we'd have had to zap it for the recursive call) 1594 = go n oss subst ty' (pushCoercion co' eis) 1595 1596 | otherwise -- We have an expression of arity > 0, 1597 -- but its type isn't a function, or a binder 1598 -- is levity-polymorphic 1599 = WARN( True, (ppr orig_oss <+> ppr orig_ty) $$ ppr_orig_expr ) 1600 (getTCvInScope subst, reverse eis) 1601 -- This *can* legitimately happen: 1602 -- e.g. coerce Int (\x. x) Essentially the programmer is 1603 -- playing fast and loose with types (Happy does this a lot). 1604 -- So we simply decline to eta-expand. Otherwise we'd end up 1605 -- with an explicit lambda having a non-function type 1606 1607 1608{- ********************************************************************* 1609* * 1610 The "push rules" 1611* * 1612************************************************************************ 1613 1614Here we implement the "push rules" from FC papers: 1615 1616* The push-argument rules, where we can move a coercion past an argument. 1617 We have 1618 (fun |> co) arg 1619 and we want to transform it to 1620 (fun arg') |> co' 1621 for some suitable co' and transformed arg'. 1622 1623* The PushK rule for data constructors. We have 1624 (K e1 .. en) |> co 1625 and we want to transform to 1626 (K e1' .. en') 1627 by pushing the coercion into the arguments 1628-} 1629 1630pushCoArgs :: CoercionR -> [CoreArg] -> Maybe ([CoreArg], MCoercion) 1631pushCoArgs co [] = return ([], MCo co) 1632pushCoArgs co (arg:args) = do { (arg', m_co1) <- pushCoArg co arg 1633 ; case m_co1 of 1634 MCo co1 -> do { (args', m_co2) <- pushCoArgs co1 args 1635 ; return (arg':args', m_co2) } 1636 MRefl -> return (arg':args, MRefl) } 1637 1638pushCoArg :: CoercionR -> CoreArg -> Maybe (CoreArg, MCoercion) 1639-- We have (fun |> co) arg, and we want to transform it to 1640-- (fun arg) |> co 1641-- This may fail, e.g. if (fun :: N) where N is a newtype 1642-- C.f. simplCast in GHC.Core.Opt.Simplify 1643-- 'co' is always Representational 1644-- If the returned coercion is Nothing, then it would have been reflexive 1645pushCoArg co (Type ty) = do { (ty', m_co') <- pushCoTyArg co ty 1646 ; return (Type ty', m_co') } 1647pushCoArg co val_arg = do { (arg_co, m_co') <- pushCoValArg co 1648 ; return (val_arg `mkCastMCo` arg_co, m_co') } 1649 1650pushCoTyArg :: CoercionR -> Type -> Maybe (Type, MCoercionR) 1651-- We have (fun |> co) @ty 1652-- Push the coercion through to return 1653-- (fun @ty') |> co' 1654-- 'co' is always Representational 1655-- If the returned coercion is Nothing, then it would have been reflexive; 1656-- it's faster not to compute it, though. 1657pushCoTyArg co ty 1658 -- The following is inefficient - don't do `eqType` here, the coercion 1659 -- optimizer will take care of it. See #14737. 1660 -- -- | tyL `eqType` tyR 1661 -- -- = Just (ty, Nothing) 1662 1663 | isReflCo co 1664 = Just (ty, MRefl) 1665 1666 | isForAllTy_ty tyL 1667 = ASSERT2( isForAllTy_ty tyR, ppr co $$ ppr ty ) 1668 Just (ty `mkCastTy` co1, MCo co2) 1669 1670 | otherwise 1671 = Nothing 1672 where 1673 Pair tyL tyR = coercionKind co 1674 -- co :: tyL ~ tyR 1675 -- tyL = forall (a1 :: k1). ty1 1676 -- tyR = forall (a2 :: k2). ty2 1677 1678 co1 = mkSymCo (mkNthCo Nominal 0 co) 1679 -- co1 :: k2 ~N k1 1680 -- Note that NthCo can extract a Nominal equality between the 1681 -- kinds of the types related by a coercion between forall-types. 1682 -- See the NthCo case in GHC.Core.Lint. 1683 1684 co2 = mkInstCo co (mkGReflLeftCo Nominal ty co1) 1685 -- co2 :: ty1[ (ty|>co1)/a1 ] ~ ty2[ ty/a2 ] 1686 -- Arg of mkInstCo is always nominal, hence mkNomReflCo 1687 1688pushCoValArg :: CoercionR -> Maybe (MCoercionR, MCoercionR) 1689-- We have (fun |> co) arg 1690-- Push the coercion through to return 1691-- (fun (arg |> co_arg)) |> co_res 1692-- 'co' is always Representational 1693-- If the second returned Coercion is actually Nothing, then no cast is necessary; 1694-- the returned coercion would have been reflexive. 1695pushCoValArg co 1696 -- The following is inefficient - don't do `eqType` here, the coercion 1697 -- optimizer will take care of it. See #14737. 1698 -- -- | tyL `eqType` tyR 1699 -- -- = Just (mkRepReflCo arg, Nothing) 1700 1701 | isReflCo co 1702 = Just (MRefl, MRefl) 1703 1704 | isFunTy tyL 1705 , (co_mult, co1, co2) <- decomposeFunCo Representational co 1706 , isReflexiveCo co_mult 1707 -- We can't push the coercion in the case where co_mult isn't reflexivity: 1708 -- it could be an unsafe axiom, and losing this information could yield 1709 -- ill-typed terms. For instance (fun x ::(1) Int -> (fun _ -> () |> co) x) 1710 -- with co :: (Int -> ()) ~ (Int %1 -> ()), would reduce to (fun x ::(1) Int 1711 -- -> (fun _ ::(Many) Int -> ()) x) which is ill-typed 1712 1713 -- If co :: (tyL1 -> tyL2) ~ (tyR1 -> tyR2) 1714 -- then co1 :: tyL1 ~ tyR1 1715 -- co2 :: tyL2 ~ tyR2 1716 = ASSERT2( isFunTy tyR, ppr co $$ ppr arg ) 1717 Just (coToMCo (mkSymCo co1), coToMCo co2) 1718 -- Critically, coToMCo to checks for ReflCo; the whole coercion may not 1719 -- be reflexive, but either of its components might be 1720 -- We could use isReflexiveCo, but it's not clear if the benefit 1721 -- is worth the cost, and it makes no difference in #18223 1722 1723 | otherwise 1724 = Nothing 1725 where 1726 arg = funArgTy tyR 1727 Pair tyL tyR = coercionKind co 1728 1729pushCoercionIntoLambda 1730 :: InScopeSet -> Var -> CoreExpr -> CoercionR -> Maybe (Var, CoreExpr) 1731-- This implements the Push rule from the paper on coercions 1732-- (\x. e) |> co 1733-- ===> 1734-- (\x'. e |> co') 1735pushCoercionIntoLambda in_scope x e co 1736 | ASSERT(not (isTyVar x) && not (isCoVar x)) True 1737 , Pair s1s2 t1t2 <- coercionKind co 1738 , Just (_, _s1,_s2) <- splitFunTy_maybe s1s2 1739 , Just (w1, t1,_t2) <- splitFunTy_maybe t1t2 1740 , (co_mult, co1, co2) <- decomposeFunCo Representational co 1741 , isReflexiveCo co_mult 1742 -- We can't push the coercion in the case where co_mult isn't 1743 -- reflexivity. See pushCoValArg for more details. 1744 = let 1745 -- Should we optimize the coercions here? 1746 -- Otherwise they might not match too well 1747 x' = x `setIdType` t1 `setIdMult` w1 1748 in_scope' = in_scope `extendInScopeSet` x' 1749 subst = extendIdSubst (mkEmptySubst in_scope') 1750 x 1751 (mkCast (Var x') co1) 1752 in Just (x', substExpr subst e `mkCast` co2) 1753 | otherwise 1754 = pprTrace "exprIsLambda_maybe: Unexpected lambda in case" (ppr (Lam x e)) 1755 Nothing 1756 1757pushCoDataCon :: DataCon -> [CoreExpr] -> Coercion 1758 -> Maybe (DataCon 1759 , [Type] -- Universal type args 1760 , [CoreExpr]) -- All other args incl existentials 1761-- Implement the KPush reduction rule as described in "Down with kinds" 1762-- The transformation applies iff we have 1763-- (C e1 ... en) `cast` co 1764-- where co :: (T t1 .. tn) ~ to_ty 1765-- The left-hand one must be a T, because exprIsConApp returned True 1766-- but the right-hand one might not be. (Though it usually will.) 1767pushCoDataCon dc dc_args co 1768 | isReflCo co || from_ty `eqType` to_ty -- try cheap test first 1769 , let (univ_ty_args, rest_args) = splitAtList (dataConUnivTyVars dc) dc_args 1770 = Just (dc, map exprToType univ_ty_args, rest_args) 1771 1772 | Just (to_tc, to_tc_arg_tys) <- splitTyConApp_maybe to_ty 1773 , to_tc == dataConTyCon dc 1774 -- These two tests can fail; we might see 1775 -- (C x y) `cast` (g :: T a ~ S [a]), 1776 -- where S is a type function. In fact, exprIsConApp 1777 -- will probably not be called in such circumstances, 1778 -- but there's nothing wrong with it 1779 1780 = let 1781 tc_arity = tyConArity to_tc 1782 dc_univ_tyvars = dataConUnivTyVars dc 1783 dc_ex_tcvars = dataConExTyCoVars dc 1784 arg_tys = dataConRepArgTys dc 1785 1786 non_univ_args = dropList dc_univ_tyvars dc_args 1787 (ex_args, val_args) = splitAtList dc_ex_tcvars non_univ_args 1788 1789 -- Make the "Psi" from the paper 1790 omegas = decomposeCo tc_arity co (tyConRolesRepresentational to_tc) 1791 (psi_subst, to_ex_arg_tys) 1792 = liftCoSubstWithEx Representational 1793 dc_univ_tyvars 1794 omegas 1795 dc_ex_tcvars 1796 (map exprToType ex_args) 1797 1798 -- Cast the value arguments (which include dictionaries) 1799 new_val_args = zipWith cast_arg (map scaledThing arg_tys) val_args 1800 cast_arg arg_ty arg = mkCast arg (psi_subst arg_ty) 1801 1802 to_ex_args = map Type to_ex_arg_tys 1803 1804 dump_doc = vcat [ppr dc, ppr dc_univ_tyvars, ppr dc_ex_tcvars, 1805 ppr arg_tys, ppr dc_args, 1806 ppr ex_args, ppr val_args, ppr co, ppr from_ty, ppr to_ty, ppr to_tc 1807 , ppr $ mkTyConApp to_tc (map exprToType $ takeList dc_univ_tyvars dc_args) ] 1808 in 1809 ASSERT2( eqType from_ty (mkTyConApp to_tc (map exprToType $ takeList dc_univ_tyvars dc_args)), dump_doc ) 1810 ASSERT2( equalLength val_args arg_tys, dump_doc ) 1811 Just (dc, to_tc_arg_tys, to_ex_args ++ new_val_args) 1812 1813 | otherwise 1814 = Nothing 1815 1816 where 1817 Pair from_ty to_ty = coercionKind co 1818 1819collectBindersPushingCo :: CoreExpr -> ([Var], CoreExpr) 1820-- Collect lambda binders, pushing coercions inside if possible 1821-- E.g. (\x.e) |> g g :: <Int> -> blah 1822-- = (\x. e |> Nth 1 g) 1823-- 1824-- That is, 1825-- 1826-- collectBindersPushingCo ((\x.e) |> g) === ([x], e |> Nth 1 g) 1827collectBindersPushingCo e 1828 = go [] e 1829 where 1830 -- Peel off lambdas until we hit a cast. 1831 go :: [Var] -> CoreExpr -> ([Var], CoreExpr) 1832 -- The accumulator is in reverse order 1833 go bs (Lam b e) = go (b:bs) e 1834 go bs (Cast e co) = go_c bs e co 1835 go bs e = (reverse bs, e) 1836 1837 -- We are in a cast; peel off casts until we hit a lambda. 1838 go_c :: [Var] -> CoreExpr -> CoercionR -> ([Var], CoreExpr) 1839 -- (go_c bs e c) is same as (go bs e (e |> c)) 1840 go_c bs (Cast e co1) co2 = go_c bs e (co1 `mkTransCo` co2) 1841 go_c bs (Lam b e) co = go_lam bs b e co 1842 go_c bs e co = (reverse bs, mkCast e co) 1843 1844 -- We are in a lambda under a cast; peel off lambdas and build a 1845 -- new coercion for the body. 1846 go_lam :: [Var] -> Var -> CoreExpr -> CoercionR -> ([Var], CoreExpr) 1847 -- (go_lam bs b e c) is same as (go_c bs (\b.e) c) 1848 go_lam bs b e co 1849 | isTyVar b 1850 , let Pair tyL tyR = coercionKind co 1851 , ASSERT( isForAllTy_ty tyL ) 1852 isForAllTy_ty tyR 1853 , isReflCo (mkNthCo Nominal 0 co) -- See Note [collectBindersPushingCo] 1854 = go_c (b:bs) e (mkInstCo co (mkNomReflCo (mkTyVarTy b))) 1855 1856 | isCoVar b 1857 , let Pair tyL tyR = coercionKind co 1858 , ASSERT( isForAllTy_co tyL ) 1859 isForAllTy_co tyR 1860 , isReflCo (mkNthCo Nominal 0 co) -- See Note [collectBindersPushingCo] 1861 , let cov = mkCoVarCo b 1862 = go_c (b:bs) e (mkInstCo co (mkNomReflCo (mkCoercionTy cov))) 1863 1864 | isId b 1865 , let Pair tyL tyR = coercionKind co 1866 , ASSERT( isFunTy tyL) isFunTy tyR 1867 , (co_mult, co_arg, co_res) <- decomposeFunCo Representational co 1868 , isReflCo co_mult -- See Note [collectBindersPushingCo] 1869 , isReflCo co_arg -- See Note [collectBindersPushingCo] 1870 = go_c (b:bs) e co_res 1871 1872 | otherwise = (reverse bs, mkCast (Lam b e) co) 1873 1874{- 1875 1876Note [collectBindersPushingCo] 1877~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 1878We just look for coercions of form 1879 <type> # w -> blah 1880(and similarly for foralls) to keep this function simple. We could do 1881more elaborate stuff, but it'd involve substitution etc. 1882 1883-} 1884 1885{- ********************************************************************* 1886* * 1887 Join points 1888* * 1889********************************************************************* -} 1890 1891------------------- 1892-- | Split an expression into the given number of binders and a body, 1893-- eta-expanding if necessary. Counts value *and* type binders. 1894etaExpandToJoinPoint :: JoinArity -> CoreExpr -> ([CoreBndr], CoreExpr) 1895etaExpandToJoinPoint join_arity expr 1896 = go join_arity [] expr 1897 where 1898 go 0 rev_bs e = (reverse rev_bs, e) 1899 go n rev_bs (Lam b e) = go (n-1) (b : rev_bs) e 1900 go n rev_bs e = case etaBodyForJoinPoint n e of 1901 (bs, e') -> (reverse rev_bs ++ bs, e') 1902 1903etaExpandToJoinPointRule :: JoinArity -> CoreRule -> CoreRule 1904etaExpandToJoinPointRule _ rule@(BuiltinRule {}) 1905 = WARN(True, (sep [text "Can't eta-expand built-in rule:", ppr rule])) 1906 -- How did a local binding get a built-in rule anyway? Probably a plugin. 1907 rule 1908etaExpandToJoinPointRule join_arity rule@(Rule { ru_bndrs = bndrs, ru_rhs = rhs 1909 , ru_args = args }) 1910 | need_args == 0 1911 = rule 1912 | need_args < 0 1913 = pprPanic "etaExpandToJoinPointRule" (ppr join_arity $$ ppr rule) 1914 | otherwise 1915 = rule { ru_bndrs = bndrs ++ new_bndrs, ru_args = args ++ new_args 1916 , ru_rhs = new_rhs } 1917 where 1918 need_args = join_arity - length args 1919 (new_bndrs, new_rhs) = etaBodyForJoinPoint need_args rhs 1920 new_args = varsToCoreExprs new_bndrs 1921 1922-- Adds as many binders as asked for; assumes expr is not a lambda 1923etaBodyForJoinPoint :: Int -> CoreExpr -> ([CoreBndr], CoreExpr) 1924etaBodyForJoinPoint need_args body 1925 = go need_args (exprType body) (init_subst body) [] body 1926 where 1927 go 0 _ _ rev_bs e 1928 = (reverse rev_bs, e) 1929 go n ty subst rev_bs e 1930 | Just (tv, res_ty) <- splitForAllTyCoVar_maybe ty 1931 , let (subst', tv') = substVarBndr subst tv 1932 = go (n-1) res_ty subst' (tv' : rev_bs) (e `App` varToCoreExpr tv') 1933 | Just (mult, arg_ty, res_ty) <- splitFunTy_maybe ty 1934 , let (subst', b) = freshEtaId n subst (Scaled mult arg_ty) 1935 = go (n-1) res_ty subst' (b : rev_bs) (e `App` Var b) 1936 | otherwise 1937 = pprPanic "etaBodyForJoinPoint" $ int need_args $$ 1938 ppr body $$ ppr (exprType body) 1939 1940 init_subst e = mkEmptyTCvSubst (mkInScopeSet (exprFreeVars e)) 1941 1942 1943 1944-------------- 1945freshEtaId :: Int -> TCvSubst -> Scaled Type -> (TCvSubst, Id) 1946-- Make a fresh Id, with specified type (after applying substitution) 1947-- It should be "fresh" in the sense that it's not in the in-scope set 1948-- of the TvSubstEnv; and it should itself then be added to the in-scope 1949-- set of the TvSubstEnv 1950-- 1951-- The Int is just a reasonable starting point for generating a unique; 1952-- it does not necessarily have to be unique itself. 1953freshEtaId n subst ty 1954 = (subst', eta_id') 1955 where 1956 Scaled mult' ty' = Type.substScaledTyUnchecked subst ty 1957 eta_id' = uniqAway (getTCvInScope subst) $ 1958 mkSysLocalOrCoVar (fsLit "eta") (mkBuiltinUnique n) mult' ty' 1959 -- "OrCoVar" since this can be used to eta-expand 1960 -- coercion abstractions 1961 subst' = extendTCvInScope subst eta_id' 1962