Opened 6 years ago

Closed 3 years ago

#7944 closed bug (fixed)

GHC goes into an apparently infinite loop at -O2

Reported by: bos Owned by:
Priority: normal Milestone: 8.2.1
Component: Compiler Version: 7.9
Keywords: SpecConstr Cc: ezyang
Operating System: Unknown/Multiple Architecture: x86_64 (amd64)
Type of failure: Compile-time crash Test Case:
Blocked By: Blocking:
Related Tickets: #5550 #8852 Differential Rev(s): Phab:D3404
Wiki Page:

Description

I ran across a peculiar case this evening: a benchmark that I can't compile with -O2, because GHC goes into an infinite loop.

I have a very small repro at https://github.com/bos/inttable/blob/2d529c693f4c9a2903dae8f640759a05e7d20c69/Repro.hs

You can grab the necessary code and reproduce as follows:

git clone git://github.com/bos/inttable.git
cd inttable
ghc -O2 --make Repro

With GHC 7.6.3, this goes into an infinite loop. If I compile with -v3, I see that GHC freezes here:

*** SpecConstr:
Result size of SpecConstr

This never prints any output. Since the compiler isn't allocating more memory, I assume that it's stuck in a loop, rather than doing something productive.

Change History (16)

comment:1 Changed 6 years ago by bos

If I rebuild both modules with -fspec-constr-threshold=485, the build completes. If I bump that number to 486, it does not.

comment:2 Changed 6 years ago by amosrobinson

Resolution: duplicate
Status: newclosed

Hi, This looks like an instance of #5550: ForceSpecConstr was blowing up when specialising on recursive types (list, in this case). This is fixed in HEAD, but sadly there isn't a good fix until then (without modifying the vector library to remove ForceSpecConstr annotations).

Can you change the [Int] to a Vector? Otherwise, you might just need to compile with -fno-spec-constr (or the lower threshhold, as you mentioned) for now.

comment:3 Changed 5 years ago by simonpj

difficulty: Unknown
Resolution: duplicate
Status: closednew

I believe this is finally fixed; see #8852. Can you try now, with HEAD?

Simon

comment:4 Changed 5 years ago by simonpj

Status: newinfoneeded

comment:5 Changed 5 years ago by thomie

Status: infoneedednew

I don't think this is fixed yet.

Steps to reproduce (with a quick build of today's ghc master in directory ~/ghc-build, on Linux):

cabal install --with-ghc=ghc-build/inplace/bin/ghc-stage2 vector
git clone https://github.com/thomie/inttable
cd inttable
~/ghc-build/inplace/bin/ghc-stage2 -O2 -v3 --make T7944.hs

This last step freezes after about 1 second, with final output:

*** SpecConstr:
Result size of SpecConstr

CPU is at 100%, until I kill it after a few minutes. Contrary to Bryan's observation, I do see an increase in memory usage over time. I get the same results when using ghc-7.8.3 instead of current ghc master.

I had to make a small change to Bryan's inttable repository (hide some imports from base). See the mentioned github url.

Last edited 4 years ago by thomie (previous) (diff)

comment:6 Changed 5 years ago by MikolajKonarski

Operating System: MacOS XUnknown/Multiple
Version: 7.6.37.9

comment:7 Changed 4 years ago by thomie

-fno-spec-constr indeed fixes the problem.

I reduced the test code some more, but it still requires vector.

$ cabal install vector  # cabal gave me vector-0.10.12.3
$ ghc-7.10.2 -O2 --make T7944.hs  # also fails with ghc-7.11.20150711
module T7944 where

import qualified Data.Vector as V
import qualified IntMap as I

constructMap :: V.Vector (Int, [Int]) -> I.IntMap [Int]
constructMap = V.foldl' go I.empty
    where go m (k,v) = snd $ I.insertWith (++) k v m
module IntMap where

import Data.Bits ((.&.), complement, xor)
import GHC.Num (Num(..))
import GHC.Real (fromIntegral)

type Nat = Word

natFromInt :: Key -> Nat
natFromInt i = fromIntegral i

intFromNat :: Nat -> Key
intFromNat w = fromIntegral w

data IntMap a = Nil | Tip Key a | Bin Prefix Mask (IntMap a) (IntMap a)

type Prefix = Int
type Mask   = Int
type Key    = Int

empty :: IntMap a
empty = Nil

insertWith :: (a -> a -> a) -> Key -> a -> IntMap a -> (Maybe a, IntMap a)
insertWith f k x t = case t of
    Bin p m l r
        | nomatch k p m -> (Nothing, join k (Tip k x) p t)
        | zero k m      -> let (found, l') = insertWith f k x l
                           in (found, Bin p m l' r)
        | otherwise     -> let (found, r') = insertWith f k x r
                           in (found, Bin p m l r')
    Tip ky y
        | k == ky       -> (Just y, Tip k (f x y))
        | otherwise     -> (Nothing, join k (Tip k x) ky t)
    Nil                 -> (Nothing, Tip k x)

join :: Prefix -> IntMap a -> Prefix -> IntMap a -> IntMap a
join p1 t1 p2 t2
  | zero p1 m = Bin p m t1 t2
  | otherwise = Bin p m t2 t1
  where
    m = branchMask p1 p2
    p = mask p1 m

zero :: Key -> Mask -> Bool
zero i m = (natFromInt i) .&. (natFromInt m) == 0

nomatch :: Key -> Prefix -> Mask -> Bool
nomatch i p m = (mask i m) /= p

mask :: Key -> Mask -> Prefix
mask i m = maskW (natFromInt i) (natFromInt m)

maskW :: Nat -> Nat -> Prefix
maskW i m = intFromNat (i .&. (complement (m-1) `xor` m))

branchMask :: Prefix -> Prefix -> Mask
branchMask p1 p2 = intFromNat (highestBitMask (natFromInt p1))

highestBitMask :: Nat -> Nat
highestBitMask x1 = x1
Last edited 4 years ago by thomie (previous) (diff)

comment:8 Changed 4 years ago by amosrobinson

Hi, I had a go reducing this more. I only have ghc 7.8.3, so would someone be able to try this on head?

module T7944 where

import GHC.Exts

-- Force specialisation of "go"
data SPEC = SPEC | SPEC2
{-# ANN type SPEC ForceSpecConstr #-}

-- This is more or less just an ordinary fold
go :: SPEC -> [a] -> IntMap a -> IntMap a
go SPEC [] m = m
go SPEC (_:xs) m
 = go SPEC xs
 -- This would be the "worker function" of the fold
 $ Unary m


-- Both constructors are necessary, despite only one being used
data IntMap a = Nil | Unary (IntMap a)

comment:9 Changed 4 years ago by thomie

Yes, infinite loop with ghc-7.10.2 as well as ghc-7.11.20150711 (HEAD).

comment:10 Changed 4 years ago by amosrobinson

Hmm. So I thought in this case, the is_too_recursive check should stop specialisation after a few runs. The counting of recursive constructors is only going down through applications though: I wonder whether it needs to handle lets, cases, etc? https://github.com/ghc/ghc/blob/master/compiler/specialise/SpecConstr.hs#L1807

comment:11 Changed 3 years ago by mpickering

Keywords: SpecConstr added

comment:12 Changed 3 years ago by RyanGlScott

I just tried compiling the programs in comment:5 and comment:8 with GHC 8.2.1 and HEAD, and neither went into an infinite loop. I'm not sure OtToMH what commit fixed this (wild guess: 8674883c137401873fd53a6963acd33af651c2af ?), but we should find it and add a regression test for it so that this stays fixed.

comment:13 Changed 3 years ago by mpickering

Seems plausible that it was the join points patch. Nothing else in the file history looks like a big change.

comment:14 Changed 3 years ago by RyanGlScott

Cc: ezyang added
Differential Rev(s): Phab:D3404
Status: newpatch

Huh, the commit that fixed this turned out to be something quite different from what I was imagining. It's actually b8b3e30a6eedf9f213b8a718573c4827cfa230ba (Axe RecFlag on TyCons.) I don't know if this change directly fixes the issue or if it's just a happy coincidence (ezyang, any thoughts?), but either way, I've added a regression test in Phab:D3404.

comment:15 Changed 3 years ago by Ben Gamari <ben@…>

In af941a9/ghc:

Add regression test for #7944

Commit b8b3e30a6eedf9f213b8a718573c4827cfa230ba happened to fix the bug
reported in #7944. Let's add a regression test so that it stays that
way.

Fixes #7944.

Test Plan: make test TEST=T7944

Reviewers: austin, bgamari

Reviewed By: bgamari

Subscribers: rwbarton, thomie

Differential Revision: https://phabricator.haskell.org/D3404

comment:16 Changed 3 years ago by bgamari

Milestone: 8.2.1
Resolution: fixed
Status: patchclosed
Note: See TracTickets for help on using tickets.