Compilation time/space regression in GHC 8.0/8.1 (search in type-level lists and -O)

After upgrading to GHC 8.0.1 I've noticed that compilation time of one of my libraries got unacceptably long. Please find the attached test case. Here are some numbers from my machine:

$ time ~/Prefixes/ghc-7.10.3/bin/ghc -O -c -Rghc-timing TypeList.hs Regression.hs 
<<ghc: 19103924976 bytes, 1441 GCs, 73048470/256579104 avg/max bytes residency (18 samples), 542M in use, 0.000 INIT (0.002 elapsed), 14.163 MUT (14.257 elapsed), 5.707 GC (5.830 elapsed) :ghc>>

real	0m20.160s
user	0m19.937s
sys	0m0.197s
$ time ~/Prefixes/ghc-8.0.1/bin/ghc -O -c -Rghc-timing TypeList.hs Regression.hs 
<<ghc: 147662211104 bytes, 9635 GCs, 190336418/433097448 avg/max bytes residency (38 samples), 1210M in use, 0.000 INIT (0.001 elapsed), 101.707 MUT (101.840 elapsed), 27.907 GC (28.259 elapsed) :ghc>>

real	2m10.195s
user	2m9.773s
sys	0m0.400s

Both versions are the official Debian 8 x86_64 binaries from haskell.org. I also compiled the git master and unfortunately it is affected as well.

It is worth mentioning that turning off optimization makes the problem disappear:

$ time ~/Prefixes/ghc-8.0.1/bin/ghc -O0 -c -Rghc-timing TypeList.hs Regression.hs 
<<ghc: 3779057184 bytes, 225 GCs, 17923355/81566792 avg/max bytes residency (8 samples), 164M in use, 0.000 INIT (0.001 elapsed), 2.847 MUT (2.941 elapsed), 0.553 GC (0.572 elapsed) :ghc>>

real	0m3.593s
user	0m3.507s
sys	0m0.073s

Trac metadata

Trac field	Value
Version	8.0.1
Type	Bug
TypeOfFailure	OtherFailure
Priority	normal
Resolution	Unresolved
Component	Compiler
Test case
Differential revisions
BlockedBy
Related
Blocking
CC
Operating system
Architecture