Opened 10 years ago

Last modified 20 months ago

#3831 new bug

SpecConstr should exploit cases where there is exactly one call pattern

Reported by: igloo Owned by: simonpj
Priority: normal Milestone:
Component: Compiler Version: 6.13
Keywords: SpecConstr Cc:
Operating System: Unknown/Multiple Architecture: Unknown/Multiple
Type of failure: Compile-time performance bug Test Case: simplCore/should_compile/T3831
Blocked By: Blocking:
Related Tickets: Differential Rev(s):
Wiki Page:


On x86/Linux, with this mk/

GhcLibWays = v p dyn
SRC_HC_OPTS     = -O -H64m -Rghc-timing
GhcStage1HcOpts = -O -fasm
GhcStage2HcOpts = -O2 -fasm
GhcHcOpts       = -Rghc-timing
GhcLibHcOpts    = -O2 -XGenerics

#SplitObjs          = YES
SplitObjs          = NO

# -----------------------------------------------------------------------------
# Other settings that might be useful

# profiled RTS
#GhcRtsCcOpts =  -pg -g

# Optimised/profiled RTS
#GhcRtsCcOpts = -O2 -pg

#GhcRtsWithFrontPanel = YES
#SRC_HC_OPTS += `gtk-config --libs`

# NoFib settings
NoFibWays =

and these commands:

$ sh boot
$ ./configure --prefix=/opt/ghc-6.13
$ make

and a 1GB memory limit (ulimit -v 1024000), the build fails with:

"inplace/bin/ghc-stage1"   -O -H64m -Rghc-timing    -package-name terminfo- -hide-all-packages -i -ilibraries/terminfo/. -ilibraries/terminfo/dist-install/build -ilibraries/terminfo/dist-install/build/autogen -Ilibraries/terminfo/dist-install/build -Ilibraries/terminfo/dist-install/build/autogen -Ilibraries/terminfo/.    -optP-include -optPlibraries/terminfo/dist-install/build/autogen/cabal_macros.h -package base- -package extensible-exceptions-  -Wall -XForeignFunctionInterface -XDeriveDataTypeable -XEmptyDataDecls -XScopedTypeVariables -XFlexibleInstances -O2 -XGenerics -fno-warn-deprecated-flags     -odir libraries/terminfo/dist-install/build -hidir libraries/terminfo/dist-install/build -stubdir libraries/terminfo/dist-install/build -hisuf hi -osuf  o -hcsuf hc -c libraries/terminfo/./System/Console/Terminfo/Effects.hs -o libraries/terminfo/dist-install/build/System/Console/Terminfo/Effects.o
ghc-stage1: out of memory (requested 1048576 bytes)
make[1]: *** [libraries/terminfo/dist-install/build/System/Console/Terminfo/Effects.o] Error 1
make: *** [all] Error 2

With -v:

Glasgow Haskell Compiler, Version 6.13.20100120, for Haskell 98, stage 1 booted 
by GHC version 6.8.2
Using binary package database: /home/ian/qq/ghc/inplace/lib/package.conf.d/packa
wired-in package ghc-prim mapped to ghc-prim-
wired-in package integer-gmp mapped to integer-gmp-
wired-in package base mapped to base-
wired-in package rts mapped to builtin_rts
wired-in package haskell98 mapped to haskell98-
wired-in package template-haskell mapped to template-haskell-
wired-in package dph-seq mapped to dph-seq-0.4.0-inplace
wired-in package dph-par mapped to dph-par-0.4.0-inplace
Hsc static flags: -static
Created temporary directory: /tmp/ghc1791_0
*** Checking old interface for terminfo-
*** Parser:
*** Renamer/typechecker:
*** Desugar:
    Result size = 1076
*** Simplifier gentle[rules,no inline] max-iterations=4:
    Result size = 802
    Result size = 758
    Result size = 758
*** Specialise:
    Result size = 758
*** Float out(not lambdas, constants):
    Result size = 826
*** Float inwards:
    Result size = 826
*** Simplifier Phase 2 [main] max-iterations=4:
    Result size = 1499
    Result size = 2190
    Result size = 2994
    Result size = 2380
    Result size = 2380
*** Simplifier Phase 1 [main] max-iterations=4:
    Result size = 2145
    Result size = 2115
*** Simplifier Phase 0 [main] max-iterations=4:
    Result size = 2115
*** Demand analysis:
    Result size = 2115
*** Worker Wrapper binds:
    Result size = 2115
*** Glom binds:
*** GlomBinds:
    Result size = 2115
*** Simplifier Phase 0 [post-worker-wrapper] max-iterations=4:
    Result size = 2115
*** Float out(not lambdas, constants):
    Result size = 2121
*** Common sub-expression:
    Result size = 2102
*** Float inwards:
    Result size = 2102
*** Liberate case:
    Result size = 2102
*** Simplifier Phase 0 [post-liberate-case] max-iterations=4:
    Result size = 2082
    Result size = 2082
*** SpecConstr:
ghc-stage1: out of memory (requested 1048576 bytes)

Change History (18)

comment:1 Changed 10 years ago by igloo


This was compiling the HEAD; 6.12 not tested.

comment:2 Changed 10 years ago by simonpj

Summary: GHC uses too much memory compiling terminfoSpecConstr should exploit cases where there is exactly one call pattern
Test Case: simplCore/should_compile/T3831

I've fixed the blowup with

Mon Feb  1 00:24:20 GMT Standard Time 2010
  * Fix Trac #3831: blowup in SpecConstr
  It turned out that there were two bugs.  First, we were getting an
  exponential number of specialisations when we had a deep nest of
  join points.  See Note [Avoiding exponential blowup]. I fixed this
  by dividing sc_count (in ScEnv) by the number of specialisations
  when recursing.  Crude but effective.
  Second, when making specialisations I was looking at the result of
  applying specExpr to the RHS of the function, whereas I should have
  been looking at the original RHS.  See Note [Specialise original
  There's a tantalising missed opportunity here, though.  In this
  example (recorded as a test simplCore/should_compile/T3831), each join
  point has *exactly one* call pattern, so we should really just
  specialise for that alone, in which case there's zero code-blow-up.
  In particular, we don't need the *original* RHS at all.  I need to think
  more about how to exploit this.
  But the blowup is now limited, so compiling terminfo with -O2 works again.

I'm going to leave the ticket open because of the "tantalising opportunity", but I'll retitle it.


comment:3 Changed 10 years ago by simonmar

Does the bug need fixing in the 6.12 branch, or should it be re-milestoned?

comment:4 Changed 10 years ago by simonmar

Milestone: branch

Simon says it doesn't need fixing in 6.12, so moving the ticket to the 6.14 branch.

comment:5 Changed 9 years ago by igloo

Milestone: 6.14 branch6.14.1

comment:6 Changed 9 years ago by igloo

Owner: set to simonpj

comment:7 Changed 9 years ago by simonpj


Bumping this to 7.2.


comment:8 Changed 8 years ago by simonpj

difficulty: Unknown

Punting to 7.6

comment:9 Changed 7 years ago by igloo


comment:10 Changed 7 years ago by igloo


comment:11 Changed 5 years ago by thoughtpolice


Bumping priority down (these tickets haven't been closely followed or fixed in 7.4), and moving out to 7.10 and out of 7.8.3.

comment:12 Changed 5 years ago by thoughtpolice

Priority: highnormal

Actually dropping priority. :)

comment:13 Changed 5 years ago by thoughtpolice


Moving to 7.12.1 milestone; if you feel this is an error and should be addressed sooner, please move it back to the 7.10.1 milestone.

comment:14 Changed 4 years ago by thoughtpolice


Milestone renamed

comment:15 Changed 4 years ago by thomie

Milestone: 8.0.1

comment:16 Changed 3 years ago by simonpj

Keywords: SpecConstr added

comment:17 Changed 20 months ago by sgraf

I'm trying to reproduce what the missed opportunity was here. I ran T3831 and realized that the test is ineffective for detecting a regression of this ticket: The compiler invocation misses a -O2.

Re: missed tantalising opportunity: I think you are referring to setAttributes, specifically to this nesting of join points:

join {
  $j1 x1 m1
    = case m1 of {
        Nothing -> (# x1, Nothing #);
        Just x1 -> case ... x1 of { 
          (# y1, n1 #) ->
            join {
              $j2 x2 m2
                = ... -- many more
                  join {
                    $j12 x12 m12
                      = case m12
                        of {
                          Nothing ->
                            (# x12, Nothing #);
                          Just f ->
                            (# x12, Just (\a -> ...) #)
                        } } in
                  case m2
                  of {
                    Nothing -> jump $j12 x2 Nothing;
                    Just f -> case ... x2 of { 
                      (# x12', m12' #) ->
                      case m12'
                      of {
                        Nothing -> jump $j12 x12' (Just (x6 lvl7));
                        Just _ -> jump $j12 x12' (Just ...)
                  } } in
            case n1
            of {
              Nothing -> jump $j2 y1 Nothing;
              Just _ -> jump $j2 y1 (Just ...)
            } } in

I probably have made some errors while simplifying, but the idea is that these join points aren't specialised at all.

  1. These are all non-recursive. I was under the impression that we have the inliner for non-recursive bindings to decide if inlining is worthwhile.
  2. I don't see how there's only one call-pattern for each join point. There are 3: one Nothing, two Justs. Specialising (branching factor 2) or even inlining (3) these would mean exponential blow-up in code size.

So either I'm referring to the wrong fragment of the code (I found no other join points, let alone recursive ones) or things have changed since then.

comment:18 Changed 20 months ago by simonpj

Huh. Indeed those join points have more than one call pattern. (And are non-rec to boot.)

It looks as if something must have changed since I wrote that. Short of reverting to that version of GHC and trying it, I'm not sure what to suggest. Mysterious, but not actually a problem, I guess.

Note: See TracTickets for help on using tickets.