Skip to content

SpecConstr needs two runs when one should suffice

This is a spin-off of #14844, which is a spin-off of #14068, but applies on its own.

Consider this code:

module T14844Example (topLvl) where

topLvl large = (bar1, bar2, foo)
  where
    foo :: Integer -> (a -> b -> Bool) -> (a,b) -> Bool
    foo 0 _ _ = False
    foo s f t = l s' t
       where
         l 0 t = False
         l 1 t = case t of (x,y) -> f x y
         l n (x,y) = l (n-1) (x,y)
         s' = large s

    bar1 :: Integer -> (a -> b -> Bool) -> a -> b -> Bool
    bar1 s f x y = foo s f (x,y)

    bar2 :: Integer ->  (a -> b -> Bool) -> a -> b -> Bool
    bar2 s f x y = foo (s + 1) f (x,y)

Status quo: l gets specialized, because of the two call patterns

  • l s' t and
  • l (n-1) (x,y)

The second one is interesting *and* its second argument gets scrutinized (the scu_occs field reports ScrutOcc for t). But foo does not get specialized: It does have an interesting call pattern, but scu_occs reports UnkOcc, because foo’s parameters are just passed to t.

When we decide to !SpecConstr l, we know that one of the calls to l is of the shape s' t0. This is a boring call, and we do not create a specialization for it. But we create a specialization for l using the the other call pattern. This means we know that it would be beneficial if t0 were a constructor. So can we, at this point, decide to include t0 ↦ ScrutOcc in scu_occs?

First experiments look good, so I am working on this.

Edited by Simon Jakobi
To upload designs, you'll need to enable LFS and have an admin enable hashed storage. More information