#2132: Optimise nested comparisons
---------------------------------+------------------------------------------
Reporter: simonpj | Owner:
Type: bug | Status: patch
Priority: low | Milestone: 7.4.1
Component: Compiler | Version: 6.8.2
Keywords: | Testcase:
Blockedby: | Difficulty: Unknown
Os: Unknown/Multiple | Blocking:
Architecture: Unknown/Multiple | Failure: Runtime performance bug
---------------------------------+------------------------------------------
Changes (by michalt):
* status: new => patch
Comment:
Attached is my initial implementation of a core-to-core pass that tries to
optimize away unnecessary comparisons. Right now it is able to handle code
like:
{{{
case x < y of
True -> .. case y <= z of
True -> .. x == z .. -- always false
}}}
or
{{{
case x < 10 of
True -> .. case y > 20 of
True -> .. x == y .. -- always false
.. x > 15 .. -- always false
}}}
It basically stores the relations between variables and their intervals
and uses
both to determine if a result of some comparison is known. So far it does
not
handle complex expressions (like anything that includes arithmetic), so:
{{{
case x + 10 < y - 3 of
True -> .. x < y .. -- always false but not handled
}}}
It also doesn't handle the second example in the ticket description.
The patch validates (i.e. I've compiled stage2 and libraries with the new
optimization and it validates). I've also run nofib but I haven't noticed
anything that really stands out (it does find some more than 60
unnecessary
comparisons in nofib and in case of GHC/libraries more than 100).
So what do you think about it? Let me know what should be fixed/changed
etc.
Also I didn't write any tests yet, since I'm not sure how to actually test
it
--- would it be enough to simply write a few cases where the optimization
should
fire and some where it shouldn't and then just make sure that the result
is
as expected?
--
Ticket URL: <http://hackage.haskell.org/trac/ghc/ticket/2132#comment:13>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler
_______________________________________________
Glasgow-haskell-bugs mailing list
Glasgow-haskell-bugs@haskell.org
http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs
