Opened 9 years ago

Closed 8 years ago

Last modified 8 years ago

#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)

Test1.hs (1.5 KB) - added by dreixel 9 years ago.
Test2.hs (233 bytes) - added by dreixel 9 years ago.
Test3.hs (923 bytes) - added by dreixel 9 years ago.
Test4.hs (252 bytes) - added by dreixel 9 years ago.

Download all attachments as: .zip

Change History (17)

Changed 9 years ago by dreixel

Attachment: Test1.hs added

Changed 9 years ago by dreixel

Attachment: Test2.hs added

comment:1 Changed 9 years ago by simonpj

This is a serious bug. Thank you for isolating it. I know what is going on; patch coming.

comment:2 Changed 9 years ago by simonpj

Status: newmerge
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:3 Changed 9 years ago by igloo

Resolution: fixed
Status: mergeclosed

Merged

comment:4 Changed 9 years ago by dreixel

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 simonpj

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 dreixel

Resolution: fixed
Status: closednew

Marking it as open, as it is not really fixed yet.

comment:7 Changed 9 years ago by igloo

Milestone: 7.2.1
Owner: set to simonpj

comment:8 Changed 9 years ago by dreixel

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 dreixel

Attachment: Test3.hs added

Changed 9 years ago by dreixel

Attachment: Test4.hs added

comment:9 Changed 9 years ago by simonpj

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 simonpj@…

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 simonpj

Status: newmerge

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

comment:12 Changed 8 years ago by igloo

Resolution: fixed
Status: mergeclosed

Merged

comment:13 Changed 8 years ago by dreixel

Yes, it now seems to work fine, thanks!

Note: See TracTickets for help on using tickets.