From 517d03e41b4f5c144d1ad684539340421be2be2a Mon Sep 17 00:00:00 2001 From: Simon Peyton Jones Date: Fri, 2 Dec 2016 13:59:11 +0000 Subject: Fix an asymptotic bug in the occurrence analyser Trac #12425 and #12234 showed up a major and long-standing bug in the occurrence analyser, whereby it could generate explonentially large program! There's a lot of commentary on #12425; and it's all described in Note [Loop breakers, node scoring, and stability] I did quite a lot of refactoring to make the code comprehensibe again (its structure had bit-rotted rather), so the patch looks bigger than it really is. Hurrah! I did a nofib run to check that I hadn't inadertently ruined anything: -------------------------------------------------------------------------------- Program Size Allocs Runtime Elapsed TotalMem -------------------------------------------------------------------------------- fluid -0.3% -1.5% 0.01 0.01 +0.0% parser -0.9% +0.6% 0.04 0.04 +0.0% prolog -0.1% +1.2% 0.00 0.00 +0.0% -------------------------------------------------------------------------------- Min -0.9% -1.5% -8.6% -8.7% +0.0% Max +0.1% +1.2% +7.7% +7.8% +2.4% Geometric Mean -0.2% -0.0% -0.2% -0.3% +0.0% I checked what happened in 'prolog'. It seems that we have a recursive data structure something like this f :: [blah] f x = build (\cn. ...g... ) g :: [blah2] g y = ....(foldr k z (f y)).... If we inline 'f' into 'g' we get better fusion than the other way round, but we don't have any way to spot that at the moment. (I wonder if we could do worker/wrapper for functions returning a 'build'?) It was happening before by a fluke. Anyway I decided to accept this; it's relatively rare I think. --- testsuite/tests/typecheck/should_compile/all.T | 1 + 1 file changed, 1 insertion(+) (limited to 'testsuite/tests/typecheck/should_compile') diff --git a/testsuite/tests/typecheck/should_compile/all.T b/testsuite/tests/typecheck/should_compile/all.T index 98e4ece08c..de7f147383 100644 --- a/testsuite/tests/typecheck/should_compile/all.T +++ b/testsuite/tests/typecheck/should_compile/all.T @@ -555,3 +555,4 @@ test('T12734', normal, compile, ['']) test('T12734a', normal, compile_fail, ['']) test('T12763', normal, compile, ['']) test('T12797', normal, compile, ['']) + -- cgit v1.2.1