Opened 9 years ago

Closed 9 years ago

Last modified 9 years ago

#4448 closed bug (fixed)

Another case of SpecConstr not specialising

Reported by: rl Owned by:
Priority: normal Milestone: 7.0.2
Component: Compiler Version: 7.1
Keywords: Cc:
Operating System: Unknown/Multiple Architecture: Unknown/Multiple
Type of failure: Runtime performance bug Test Case:
Blocked By: Blocking:
Related Tickets: Differential Rev(s):
Wiki Page:

Description

Compile with -O2 -fno-spec-constr-count -fno-spec-constr-threshold:

foo :: Int -> Int -> Int -> (Int,Int)
foo !a !b !c = loop (Left (a,b))
  where
    loop :: Either (Int,Int) (Int, (Int,Int)) -> (Int,Int)
    loop (Left (!x,!n))
      | n > 0     = loop (Right (x,(x+c,n-1)))
      | otherwise = (x,n)

    loop (Right (i,t))
      | i < c     = loop (Right (i+1,t))
      | otherwise = loop (Left t)

SpecConstr doesn't specialise for the (Int,Int) pair. Unless I'm mistaken, the SpecConstr loop should get this since the call in foo has the form Left (I# x, I# y) and the pair then gets threaded through the loop.

Change History (5)

comment:1 Changed 9 years ago by igloo

Milestone: 7.0.2

comment:2 Changed 9 years ago by simonpj

Nice example! The reason for this turns out to be simple. SpecConstr specialises a function f when

  • It sees a call to f (I# x, I# y)
  • AND it can see that f takes apart the pair, and takes apart the first Int, and takes apart the second Int.

The second condition is to avoid over-specialising (see the original paper). The "taking apart" analysis is fiarly simple-minded, and it fails in this example, because one of the arguments is passed on (un-take-apart) to a recursive call, and that takes it apart.

One solution is presumably to use ForceSpecConstr on this loop? (Another would be to use a more sophisticated analysis.)

comment:3 Changed 9 years ago by rl

ForceSpecConstr doesn't affect the "taking apart" requirement at the moment. It probably should, though. I'll send a patch.

comment:4 Changed 9 years ago by rl

Resolution: fixed
Status: newclosed

I pushed this:

Thu Nov 18 13:28:39 PST 2010  Roman Leshchinskiy <rl@cse.unsw.edu.au>
 * ForceSpecConstr now forces specialisation even for arguments which aren't scrutinised

I suppose we can close this since the problem can now be solved by using ForceSpecConstr.

comment:5 Changed 9 years ago by simonpj

Yes, close it once you've tested that it works. Ideally add a test, although it's always tricky to do that. (Maybe count the number of rules generated...)

Note: See TracTickets for help on using tickets.