Opened 4 years ago

Last modified 4 months ago

#10346 new bug

Cross-module SpecConstr

Reported by: simonpj Owned by:
Priority: normal Milestone:
Component: Compiler Version: 7.10.1
Keywords: SpecConstr, newcomer Cc:
Operating System: Unknown/Multiple Architecture: Unknown/Multiple
Type of failure: Runtime performance bug Test Case:
Blocked By: Blocking:
Related Tickets: #13016 Differential Rev(s):
Wiki Page:

Description (last modified by simonpj)

Type-class specialisation now happens flawlessly across modules. That is, if I define

module DefineF where
   f :: Num a => a -> a
   {-# INLINEABLE f #-}
   f x = ...f x'....

then modules that import DefineF and call f at some particular type (say Int) will generate a specialised copy of f's code.

But this does not happen for SpecConstr; we only specialise a function for calls made in the same module. For example:

module M where
  {-# INLINABLE foo #-}
  foo True  y     = y
  foo False (a,b) = foo True (a+b,b)

module X where
  import M
  bar = ...(foo (x,y))...

Here foo is called with an explicit (x,y) argument in module X, and we'd like to SpecConstr it, as it would be if the call was in module M.

All the infrastructure is in place to allow cross-module SpecConstr; it just hasn't been done yet. This ticket is to record the idea.

Change History (21)

comment:1 Changed 4 years ago by Simon Peyton Jones <simonpj@…>

In b61562feb87689a202118ca08ef270422c69dcc2/ghc:

Seed SpecConstr from local calls

Seed SpecConstr based on *local* calls as well as *RHS* calls.
See Note [Seeding top-level recursive groups].  The change here
is mentioned here:

   NB: before Apr 15 we used (a) only, but Dimitrios had an example
       where (b) was  crucial, so I added that.

This is a pretty small change, requested by Dimitrios, that adds
SpecConstr call patterns from the rest of the module, as well as ones
from the RHS.

Still to come: #10346.

comment:2 Changed 3 years ago by thomie

Type of failure: None/UnknownRuntime performance bug

comment:3 Changed 22 months ago by simonpj

Keywords: SpecConstr added

comment:4 Changed 21 months ago by mpickering

Keywords: newcomer added

comment:5 Changed 19 months ago by dfeuer

Milestone: 8.4.1

comment:6 Changed 17 months ago by ak3n

Owner: set to ak3n

comment:7 Changed 17 months ago by mpickering

ak3n:I have a mostly complete patch already on phab which you might want to fi nish off and refine.

https://phabricator.haskell.org/D3566

comment:8 Changed 16 months ago by ak3n

I am sorry, but what is the desired behaviour? I made a simple test with modules. The first module contains the drop function, while the second one calls it. At the current moment, both versions (ghc with the patch (D3566) and ghc 8.2.1) with enabled -O2 flag optimize the function with SpecConstr pass in the first module, and substitute the call to the optimized version into the second module.

comment:9 Changed 16 months ago by ak3n

Owner: ak3n deleted

comment:10 Changed 11 months ago by bgamari

Milestone: 8.4.18.6.1

This ticket won't be resolved in 8.4; remilestoning for 8.6. Do holler if you are affected by this or would otherwise like to work on it.

comment:11 Changed 9 months ago by bgamari

Milestone: 8.6.1

Removing milestone as there is no one actively working on this at the moment.

comment:12 Changed 8 months ago by simonpj

Description: modified (diff)

comment:13 Changed 7 months ago by ckoparkar

Owner: set to ckoparkar

I'd like to work on this. The updated example is what helped me understand what the expected Core output should be. Thanks for that! (I'm relatively new to GHC hacking.) So far, I've read the SpecConstr paper, and am reading the source code now. My hunch is that we need to change the Propagation phase somehow to include the proper rewrite rules across modules. Is this correct ? Other than that, I don't have any specific questions at the moment.

comment:14 Changed 7 months ago by mpickering

Are you starting from my patch https://phabricator.haskell.org/D3566 ?

I understand how this is meant to work better now so can help you if you have any questions.

comment:15 Changed 7 months ago by ckoparkar

I did use that patch. However, I couldn't get it to do what we want. Not sure if I did something wrong. I'm using the example given in the description:

module M where

{-# INLINABLE foo #-}
foo True  y     = y
foo False (a,b) = foo True (a+b,b)

baz = foo False (1,2)

-----------------------------------

module X where

import M

bar = foo False (3,4)

and compiling it with ghc-stage2 -O2 -fforce-recomp -ddump-spec X.hs.

Relevant Core output:

baz :: (Integer, Integer)
[LclIdX,
 Unf=Unf{Src=<vanilla>, TopLvl=True, Value=False, ConLike=False,
         WorkFree=False, Expandable=False, Guidance=IF_ARGS [] 240 0}]
baz = foo_aZc GHC.Types.False (1, 2)

where foo_aZc is the specialized version of foo. On the other hand, bar still uses the regular foo.

bar :: (Integer, Integer)
[LclIdX,
 Unf=Unf{Src=<vanilla>, TopLvl=True, Value=False, ConLike=False,
         WorkFree=False, Expandable=False, Guidance=IF_ARGS [] 250 0}]
bar = foo @ Integer GHC.Num.$fNumInteger GHC.Types.False (3, 4)

I'm going to use that patch as a starting point though.

Last edited 7 months ago by ckoparkar (previous) (diff)

comment:16 Changed 7 months ago by ckoparkar

I understand how this is meant to work better now so can help you if you have any questions.

Thanks! I'll keep posting any updates or questions as I make some progress on this.

comment:17 Changed 7 months ago by mpickering

I never claimed that it worked but that it was at least somewhere to start!

comment:18 Changed 7 months ago by ckoparkar

It turns out that I was comparing the Core output of the regular Specializer instead of SpecConstr. Now that I'm looking at the proper thing, I'm a bit confused and have the same question as ak3n did. Even if I just use GHC HEAD, it seems that the call to foo in a different module is specialized. Using the same example with modules M and X, and compiling it with: ghc-stage2 -O2 -fforce-recomp -ddump-spec -fspec-constr -fno-specialize X.hs, this is what bar looks like after SpecConstr runs:

bar :: (Integer, Integer)
[LclIdX]
bar
  = case $wfoo1_s1h9 GHC.Types.False ww_s1h3 ww_s1h4 of
    { (# ww_s1ha, ww_s1hb #) ->
    (ww_s1ha, ww_s1hb)
    }

(This is exactly what the last paragraph in the Note [Seeding top-level recursive groups] says should happen. There's a specialized copy of foo in the importing module. Or that's what I think it is.)

I feel like I'm making a dumb mistake and I'm trying to track this down. mpickering: Do you remember if you were using some specific example while working on that patch ?

comment:19 in reply to:  18 Changed 7 months ago by sgraf

Replying to ckoparkar:

Now that I'm looking at the proper thing, I'm a bit confused and have the same question as ak3n did.

I blame the example.

  1. After SpecConstr runs on M, the call isn't really recursive anymore: There will be a specialisation for the call pattern [x, y] |> [True, (x, y)]. The resulting function is non-recursive, inlined, and suddenly foo itself isn't recursive anymore and simply gets inlined in X.
  2. The baz binding in M will make it so that there is a specialisation for the call pattern [x,y] |> [False, (x,y)] anyway. The call in X matches this pattern, so will be specialised appropriately.

Try this instead:

module M where

{-# INLINABLE foo #-}
foo 0 y = y
foo n y = foo (n-1) y

--baz = foo 14 (2,2)

---------------------

module X where

import M

bar = foo 2 (3,4)

This works better, because integer literals are not currently considered values (probably to avoid code bloat through endless loop unrolling). Notice that the call in X specialises iff you comment in baz in M which has the same call pattern.

comment:20 Changed 7 months ago by ckoparkar

Thanks for the explanation sgraf!

I did not realize that having exactly same call patterns would trigger this. I'll try out this example later today.

Last edited 7 months ago by ckoparkar (previous) (diff)

comment:21 Changed 4 months ago by ckoparkar

Owner: ckoparkar deleted
Note: See TracTickets for help on using tickets.