#4903 closed bug (fixed)
Inliner looping when specialising across modules (with GADTs and other extensions)
Reported by: | dreixel | Owned by: | simonpj |
---|---|---|---|
Priority: | normal | Milestone: | 7.2.1 |
Component: | Compiler | Version: | 7.1 |
Keywords: | Cc: | ||
Operating System: | Unknown/Multiple | Architecture: | Unknown/Multiple |
Type of failure: | Compile-time crash | Test Case: | simplCore/should_compile/T4903 |
Blocked By: | Blocking: | ||
Related Tickets: | Differential Rev(s): | ||
Wiki Page: |
Description
While #4870 is fixed, the original code that caused that problem is still not working. Now I can SPECIALISE imported functions, but I think the inliner is looping.
Unfortunately I cannot give a very small example, so I give a bigger example with comments explaining why the complexity is necessary.
{-# LANGUAGE FlexibleContexts #-} {-# LANGUAGE RankNTypes #-} {-# LANGUAGE TypeOperators #-} {-# LANGUAGE MultiParamTypeClasses #-} {-# LANGUAGE FlexibleInstances #-} {-# LANGUAGE GADTs #-} {-# LANGUAGE TypeFamilies #-} module Test1 where class El phi ix where proof :: phi ix class Fam phi where from :: phi ix -> ix -> PF phi I0 ix type family PF phi :: (* -> *) -> * -> * data I0 a = I0 a data I xi (r :: * -> *) ix = I (r xi) data (f :*: g) (r :: * -> *) ix = f r ix :*: g r ix class HEq phi f where heq :: (forall ix. phi ix -> r ix -> Bool) -> phi ix -> f r ix -> Bool instance El phi xi => HEq phi (I xi) where -- Replacing proof by undefined solves the problem heq eq _ (I x) = eq proof x instance (HEq phi f, HEq phi g) => HEq phi (f :*: g) where -- The problem only arises when there are two calls to heq here heq eq p (x :*: y) = heq eq p x && heq eq p y {-# INLINE eq #-} eq :: (Fam phi, HEq phi (PF phi)) => phi ix -> ix -> Bool eq p x = heq (\p (I0 x) -> eq p x) p (from p x) data Tree = Bin Tree Tree tree :: Tree -- The problem only occurs on an inifite (or very large) structure tree = Bin tree tree data TreeF :: * -> * where Tree :: TreeF Tree type instance PF TreeF = I Tree :*: I Tree -- If the representation is only |I Tree| then there is no problem instance Fam TreeF where from Tree (Bin l r) = I (I0 l) :*: I (I0 r) instance El TreeF Tree where proof = Tree
module Test2 where import Test1 {-# SPECIALIZE eq :: TreeF Tree -> Tree -> Bool #-} -- The pragma is only problematic if it is in a separate module f :: Bool -- If we don't use eq, there is no problem f = eq Tree tree
Compiling Test2 with ghc-7.1.20110116 -O -v gives:
... compile: input file Test2.hs ... *** Float inwards: Result size = 51 *** Simplifier SimplMode {Phase = 2 [main], inline, rules, eta-expand, case-of-case} max-iterations=4: Result size = 149 Result size = 229 Result size = 345 Result size = 627 Result size = 627 *** Simplifier SimplMode {Phase = 1 [main], inline, rules, eta-expand, case-of-case} max-iterations=4: Result size = 1191 Result size = 2319 Result size = 4575 Result size = 9087 Result size = 9087 *** Simplifier SimplMode {Phase = 0 [main], inline, rules, eta-expand, case-of-case} max-iterations=4: Result size = 18111 Result size = 36159 Result size = 72255 Result size = 144447 Result size = 144447 *** Demand analysis: Result size = 144447 *** Worker Wrapper binds: Result size = 150634 *** Glom binds: *** GlomBinds: Result size = 150634 *** Simplifier SimplMode {Phase = 0 [post-worker-wrapper], inline, rules, eta-expand, case-of-case} max-iterations=4: Result size = 113738 Result size = 53327 Result size = 53327 *** Float out(FOS {Lam = Just 0, Consts = True, PAPs = True}): Result size = 53329 *** Common sub-expression: Result size = 53329 *** Float inwards: Result size = 53329 *** Simplifier SimplMode {Phase = 0 [final], inline, rules, eta-expand, case-of-case} max-iterations=4: Result size = 53329 *** Tidy Core: Result size = 53329
...and eventually I run out of patience and kill the compiler. Some variations cause the compiler to run out of memory altogether. Note that all goes well if the code is all together in one module (and, looking at the generated core code, the compiler specialises nicely). But this is library and user code, which in normal use are in separate modules/packages.
Attachments (4)
Change History (17)
Changed 9 years ago by
Changed 9 years ago by
comment:1 Changed 9 years ago by
comment:2 Changed 9 years ago by
Status: | new → merge |
---|---|
Test Case: | → simplCore/should_compile/T4903 |
Fixed by
Wed Jan 26 17:21:12 GMT 2011 simonpj@microsoft.com * Fix dependencies among specialisations for imported Ids This was a subtle one (Trac #4903). See Note [Glom the bindings if imported functions are specialised] in Speclialise. Fundamentally, a specialised binding for an imported Id was being declared non-recursive, whereas in fact it can become recursive via a RULE. Once it's specified non-recurive the OccAnal pass treats that as gospel -- and that in turn led to infinite inlining. Easily fixed by glomming all the specialised bindings in a Rec; now the OccAnal will sort them out correctly. M ./compiler/specialise/Specialise.lhs -13 +57
Can you push this to the stable branch, please Ian?
comment:4 Changed 9 years ago by
If the INLINABLE pragma on line 37 of simplCore/should_compile/T4903a.hs is replaced by an INLINE pragma, the compiler loops. This should not happen, right?...
comment:5 Changed 9 years ago by
It's a bug, thank you! My previous fix was inadequate I now see. Sigh. Will work on it.
comment:6 Changed 9 years ago by
Resolution: | fixed |
---|---|
Status: | closed → new |
Marking it as open, as it is not really fixed yet.
comment:7 Changed 9 years ago by
Milestone: | → 7.2.1 |
---|---|
Owner: | set to simonpj |
comment:8 Changed 9 years ago by
I now have an example which is simpler and shows a regression from 7.0. This fragment in particular illustrates how compilation can fail both on 7.0 and 7.1, or only on 7.1:
tree :: Tree -- |tree = undefined| compiles both with 7.0 and 7.1 tree = treeN 0 where treeN 0 = undefined treeN n = Bin (treeN 0) (treeN 0) -- Replacing the line above with the line below makes 7.0 loop -- treeN n = Bin (treeN (n-1)) (treeN (n-1))
Note that 7.0 is not behaving correctly for all cases, either, so this is not "just" a regression. Attaching test files.
Changed 9 years ago by
Changed 9 years ago by
comment:9 Changed 9 years ago by
Very helpful, thank you. I think I see what is going on, but it'll have to wait till I get back form holiday.
comment:10 Changed 9 years ago by
commit 98e9096cdcfe7501109b66e3a22e7a41eee4521b
Author: Simon Peyton Jones <simonpj@microsoft.com> Date: Thu Jul 21 12:45:51 2011 +0100 When specialising recursive functions, mark the specialised function NOINLINE This fixes Trac #4903. See Note [Specialising imported functions] in OccurAnal. compiler/deSugar/DsBinds.lhs | 7 +++++-- compiler/specialise/Specialise.lhs | 3 +++ 2 files changed, 8 insertions(+), 2 deletions(-)
comment:11 Changed 9 years ago by
Status: | new → merge |
---|
I believe that this is now fixed. Finally. Can you try?
Ian can you merge this and the patches it depends on (also committed today)
Simon
This is a serious bug. Thank you for isolating it. I know what is going on; patch coming.