[GHC] #5550: GHC infinite loop when compiling vector

[GHC]

#5550: GHC infinite loop when compiling vector
---------------------------------+------------------------------------------
    Reporter:  simonpj           |       Owner:                  
        Type:  bug               |      Status:  merge           
    Priority:  low               |   Milestone:  7.6.2           
   Component:  Compiler          |     Version:  7.2.1           
    Keywords:                    |          Os:  Unknown/Multiple
Architecture:  Unknown/Multiple  |     Failure:  None/Unknown    
  Difficulty:  Unknown           |    Testcase:                  
   Blockedby:                    |    Blocking:                  
     Related:                    |  
---------------------------------+------------------------------------------
Changes (by amosrobinson):

  * status:  new => merge


Comment:

 I have implemented Roman's suggestion of having an upper bound for
 recursive types.
 So in this example:

 {{{
 loop :: SPEC -> [Int] -> [Int] -> [Int]
 loop SPEC z [] = z
 loop SPEC z (x:xs) = loop SPEC (x:z) xs
 }}}

 The only good call pattern is
 {{{loop SPEC (_:_) _}}}
 but once that is specialised, there's another call pattern
 {{{loop SPEC (_:(_:_)) _}}}
 and so on.

 So we just find the maximum number of recursive constructors in the
 arguments, and if it's greater than the limit (default 3) we discard the
 pattern.

 I only check the recursive count if ForceSpecConstr is on for the current
 function. This doesn't really matter, but if ForceSpecConstr isn't on it
 should terminate anyway because of the max count.

 Does this look OK to you, Roman?

 https://github.com/ghc/ghc/commit/81d55a9ec28d9d7c8b1492516ebd58c5ff90c0e8

 On Fri, Mar 8, 2013 at 7:20 PM, Roman Leshchinskiy <rl at cse.unsw.edu.au>
 wrote:
 > If you want to prevent infinite specialisation, then IMO the way
 > to do it would be by not specialising more than a few times on
 > recursive types but still specialising on tuples, Maybe, Either
 > and friends as much as possible. That would guarantee termination
 > without imposing an artificial bound.

-- 
Ticket URL: <http://hackage.haskell.org/trac/ghc/ticket/5550#comment:28>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler