Safe Haskell | None |
---|---|
Language | Haskell2010 |
Note [CSE for Stg] ~~~~~~~~~~~~~~~~~~ This module implements a simple common subexpression elimination pass for STG. This is useful because there are expressions that we want to common up (because they are operationally equivalent), but that we cannot common up in Core, because their types differ. This was originally reported as #9291.
There are two types of common code occurrences that we aim for, see note [Case 1: CSEing allocated closures] and note [Case 2: CSEing case binders] below.
Note [Case 1: CSEing allocated closures] ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ The first kind of CSE opportunity we aim for is generated by this Haskell code:
bar :: a -> (Either Int a, Either Bool a) bar x = (Right x, Right x)
which produces this Core:
bar :: forall a. a -> (Either Int a, Either Bool a)
bar a x = (Right
Int a x, Right
Bool @a x)
where the two components of the tuple are different terms, and cannot be commoned up (easily). On the STG level we have
bar [x] = let c1 = Right [x] c2 = Right [x] in (c1,c2)
and now it is obvious that we can write
bar [x] = let c1 = Right [x] in (c1,c1)
instead.
Note [Case 2: CSEing case binders] ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ The second kind of CSE opportunity we aim for is more interesting, and came up in 5344: The Haskell code
foo :: Either Int a -> Either Bool a foo (Right x) = Right x foo _ = Left False
produces this Core
foo :: forall a. Either Int a -> Either Bool a
foo a e = case e of b { Left n -> …
, Right x -> Right
Bool @a x }
where we cannot CSE `Right Bool
a x` with the case binder b
as they have
different types. But in STG we have
foo [e] = case e of b { Left [n] -> … , Right [x] -> Right [x] }
and nothing stops us from transforming that to
foo [e] = case e of b { Left [n] -> … , Right [x] -> b}
Documentation
stgCse :: [InStgTopBinding] -> [OutStgTopBinding] Source #