Seemingly correct program causes compiler to hang

[cdsmith]

https://code.world/#POtNn6ESpU1Y3PtsRZ0aRfQ

This program causes GHCJS to hang until CodeWorld kills it. If you remove the *t from the definition of rRed, then it works fine. Not sure what's up here...

[cdsmith]

This command hangs:

ghcjs -O2 -hide-package base -package codeworld-base \
    -XRebindableSyntax -XImplicitPrelude \
    POt/POtNn6ESpU1Y3PtsRZ0aRfQ.hs

The same command without -O2 succeeds.

[cdsmith]

Actually, the program does compile... it just takes 6 minutes and 30 seconds to do so! Since CodeWorld gives up and terminates the compiler after 10 seconds, this generally won't work.

[wnghn]

Another occurrence: https://code.world/#PvmZL8tK6a8AdVPlxmV1Lww

[cdsmith]

Tried with GHC 8.0.1, and the program still hangs. :(

[cdsmith]

Something is causing the inlining to go crazy here!

Looking at the first example posted above with GHC 8 and -ddump-simpl-iterations, the simplifier makes a sequence of multiple passes over the source program, with apparently exponential size blowup per pass. After a few iterations, the land variable is inlined to the point that we have around 600K terms in its definition, and that's not even the end. Unlike GHC 7.10, GHC 8 ultimately just segfaults and dies on this program.

I am unsure, at this point, how to make any further progress.

[cdsmith]

$ ghcjs -O2 -v3 -hide-package base -package codeworld-base -XRebindableSyntax -XImplicitPrelude POt/POtNn6ESpU1Y3PtsRZ0aRfQ.hs
Glasgow Haskell Compiler for JavaScript, Version 8.0.1, stage 2 booted by GHC version 7.8.4
Using binary package database: /home/cdsmith/.ghcjs/x86_64-linux-0.2.1-8.0.1/ghcjs/package.conf.d/package.cache
Using binary package database: /home/cdsmith/.ghcjs/x86_64-linux-0.2.1-8.0.1/package.conf.d/package.cache
loading package database /home/cdsmith/.ghcjs/x86_64-linux-0.2.1-8.0.1/ghcjs/package.conf.d
loading package database /home/cdsmith/.ghcjs/x86_64-linux-0.2.1-8.0.1/package.conf.d
wired-in package ghc-prim mapped to ghc-prim-0.5.0.0-KRz6mJVsstU3CAY1cvHuRF
wired-in package integer-gmp mapped to integer-gmp-1.0.0.1-CrgYcijdRIIA7PG1zfL4Io
wired-in package base mapped to base-4.9.0.0-KJoxgaxCLaB5JRExU4r59H
wired-in package rts mapped to rts
wired-in package template-haskell mapped to template-haskell-2.11.0.0-IMyiHRjUreC4LCWEHj3pup
wired-in package ghc mapped to ghc-8.0.1-IyhNq6eFDr5GQr1tKzZt5j
wired-in package dph-seq not found.
wired-in package dph-par not found.
Hsc static flags: 
loading package database /home/cdsmith/.ghcjs/x86_64-linux-0.2.1-8.0.1/ghcjs/package.conf.d
loading package database /home/cdsmith/.ghcjs/x86_64-linux-0.2.1-8.0.1/package.conf.d
wired-in package ghc-prim mapped to ghc-prim-0.5.0.0-KRz6mJVsstU3CAY1cvHuRF
wired-in package integer-gmp mapped to integer-gmp-1.0.0.1-CrgYcijdRIIA7PG1zfL4Io
wired-in package base mapped to base-4.9.0.0-KJoxgaxCLaB5JRExU4r59H
wired-in package rts mapped to rts-1.0
wired-in package template-haskell mapped to template-haskell-2.11.0.0-IMyiHRjUreC4LCWEHj3pup
wired-in package ghc mapped to ghc-8.0.1-IyhNq6eFDr5GQr1tKzZt5j
wired-in package dph-seq not found.
wired-in package dph-par not found.
*** Chasing dependencies:
Chasing modules from: *POt/POtNn6ESpU1Y3PtsRZ0aRfQ.hs
!!! Chasing dependencies: finished in 4.00 milliseconds, allocated 0.248 megabytes
Stable obj: []
Stable BCO: []
Ready for upsweep
  [NONREC
      ModSummary {
         ms_hs_date = 2016-12-20 21:38:36.4472685 UTC
         ms_mod = Main,
         ms_textual_imps = [(Nothing, Prelude)]
         ms_srcimps = []
      }]
*** Deleting temp files:
Deleting: 
compile: input file POt/POtNn6ESpU1Y3PtsRZ0aRfQ.hs
*** Checking old interface for Main:
[1 of 1] Compiling Main             ( POt/POtNn6ESpU1Y3PtsRZ0aRfQ.hs, POt/POtNn6ESpU1Y3PtsRZ0aRfQ.js_o )
*** Parser [Main]:
!!! Parser [Main]: finished in 0.00 milliseconds, allocated 2.161 megabytes
*** Renamer/typechecker [Main]:
!!! Renamer/typechecker [Main]: finished in 176.00 milliseconds, allocated 94.362 megabytes
*** Desugar [Main]:
Result size of Desugar (after optimization)
  = {terms: 498, types: 234, coercions: 0}
!!! Desugar [Main]: finished in 8.00 milliseconds, allocated 5.237 megabytes
*** Simplifier [Main]:
Result size of Simplifier iteration=1
  = {terms: 469, types: 194, coercions: 0}
Result size of Simplifier = {terms: 469, types: 194, coercions: 0}
!!! Simplifier [Main]: finished in 24.00 milliseconds, allocated 32.673 megabytes
*** Specialise [Main]:
Result size of Specialise = {terms: 469, types: 194, coercions: 0}
!!! Specialise [Main]: finished in 0.00 milliseconds, allocated 0.493 megabytes
*** Float out(FOS {Lam = Just 0,
                   Consts = True,
                   OverSatApps = False}) [Main]:
Result size of Float out(FOS {Lam = Just 0,
                              Consts = True,
                              OverSatApps = False})
  = {terms: 1,193, types: 698, coercions: 0}
!!! Float out(FOS {Lam = Just 0,
                   Consts = True,
                   OverSatApps = False}) [Main]: finished in 4.00 milliseconds, allocated 2.809 megabytes
*** Simplifier [Main]:
Result size of Simplifier iteration=1
  = {terms: 1,124, types: 437, coercions: 354}
Result size of Simplifier iteration=2
  = {terms: 1,062, types: 417, coercions: 199}
Result size of Simplifier iteration=3
  = {terms: 1,190, types: 461, coercions: 203}
Result size of Simplifier iteration=4
  = {terms: 1,610, types: 585, coercions: 219}
Result size of Simplifier
  = {terms: 1,610, types: 585, coercions: 219}
!!! Simplifier [Main]: finished in 32.00 milliseconds, allocated 28.353 megabytes
*** Simplifier [Main]:
Result size of Simplifier iteration=1
  = {terms: 2,710, types: 935, coercions: 267}
Result size of Simplifier iteration=2
  = {terms: 5,734, types: 1,991, coercions: 411}
Result size of Simplifier iteration=3
  = {terms: 13,942, types: 5,159, coercions: 843}
Result size of Simplifier iteration=4
  = {terms: 35,974, types: 14,663, coercions: 2,139}
Result size of Simplifier
  = {terms: 35,974, types: 14,663, coercions: 2,139}
!!! Simplifier [Main]: finished in 280.00 milliseconds, allocated 168.588 megabytes
*** Simplifier [Main]:
Result size of Simplifier iteration=1
  = {terms: 94,824, types: 43,388, coercions: 2,124}
Result size of Simplifier iteration=2
  = {terms: 246,438, types: 128,910, coercions: 2,118}
Result size of Simplifier iteration=3
  = {terms: 631,350, types: 385,518, coercions: 2,118}
Result size of Simplifier iteration=4
  = {terms: 561,366, types: 350,526, coercions: 2,118}
Result size of Simplifier
  = {terms: 561,366, types: 350,526, coercions: 2,118}
!!! Simplifier [Main]: finished in 9780.00 milliseconds, allocated 5400.022 megabytes
*** Float inwards [Main]:
Result size of Float inwards
  = {terms: 561,366, types: 350,526, coercions: 2,118}
!!! Float inwards [Main]: finished in 1040.00 milliseconds, allocated 1078.397 megabytes
*** Called arity analysis [Main]:
Result size of Called arity analysis
  = {terms: 561,366, types: 350,526, coercions: 2,118}
!!! Called arity analysis [Main]: finished in 880.00 milliseconds, allocated 388.327 megabytes
*** Simplifier [Main]:
Result size of Simplifier iteration=1
  = {terms: 584,685, types: 350,520, coercions: 2,115}
Result size of Simplifier iteration=2
  = {terms: 639,117, types: 373,848, coercions: 2,115}
Result size of Simplifier iteration=3
  = {terms: 703,917, types: 404,952, coercions: 2,115}
Result size of Simplifier iteration=4
  = {terms: 772,173, types: 438,648, coercions: 2,115}
Result size of Simplifier
  = {terms: 772,173, types: 438,648, coercions: 2,115}
!!! Simplifier [Main]: finished in 15180.00 milliseconds, allocated 9094.544 megabytes
*** Demand analysis [Main]:
Result size of Demand analysisSegmentation fault

[cdsmith]

Problem can be reproduced with GHCJS and codeworld-api. This eliminates the possibility that there's something weird going on with codeworld-base, RebindableSyntax, the custom prelude, or one of the many language extensions used by default CodeWorld.

https://code.world/haskell#PqoIiILL47CjSRKrcEV6lRg

[cdsmith]

The culprit was 2176917246048e5d1dc11828a82c798f3d436a6e

It introduced a lot of extra pattern matching cases to CodeWorld's transformation functions, in an attempt to canonicalize the representation of pictures and, hopefully, avoid some redraws. But apparently this hits a bad combinatorial explosion in GHC's optimizer or something.

I'm reverting this part of the commit.