Do not repeatedly simplify an argument more than once
authorsimonpj@microsoft.com <unknown>
Thu, 10 Aug 2006 14:15:26 +0000 (14:15 +0000)
committersimonpj@microsoft.com <unknown>
Thu, 10 Aug 2006 14:15:26 +0000 (14:15 +0000)
commitc43e5edf13931d4532dc6062ebce312b66e17ba7
tree8b8e67d69ffce34d9eadc9cc458e9a7456977269
parent3df4d7ee5a9ba08583a7671b224f213e8ee4482b
Do not repeatedly simplify an argument more than once

A very important invariant of the simplifier is that we do not simplify
an arbitrarily large expression more than once in a single pass. If this
can happen, then we can get exponential behaviour, when the large expression
itself has a large sub-expression which is simplified twice, and so on.

GHC has a long-standing bug which allows this repeated simplification to
happen.  It shows up when we have a function like this

f d BIG
where f's unfolding looks like
\x -> case x of (a,b) -> a
Of course this is v common for overloaded functions.

Before this patch we simplified all the args (d and BIG) before
deciding to unfold f.  Then we push back the simplified BIG onto the
continuation stack, inline f, so now we have
(case d of (a,b) -> a) BIG
After we reduce the case a bit, we'll simplify BIG a second time.  And
that's the problem.

The quick-and-dirty solution is to keep a flag in the ApplyTo continuation
to say whather the arg has already been simplified.  An alternative would
be to simplify it when first encountered, but that's a bigger change.
compiler/simplCore/SimplUtils.lhs
compiler/simplCore/Simplify.lhs