[GHC] #5615: ghc produces poor code for `div` with constant powers of 2.
GHC
ghc-devs at haskell.org
Sat Jun 28 13:43:57 UTC 2014
#5615: ghc produces poor code for `div` with constant powers of 2.
-------------------------------------+-------------------------------------
Reporter: Lennart | Owner: daniel.is.fischer
Type: bug | Status: new
Priority: normal | Milestone: 7.6.2
Component: Compiler | Version: 7.4.1-rc1
Resolution: | Keywords:
Operating System: Unknown/Multiple | Architecture: x86
Type of failure: None/Unknown | Difficulty: Unknown
Test Case: | Blocked By:
Blocking: | Related Tickets:
-------------------------------------+-------------------------------------
Comment (by thomie):
How about implementing Euclidean division?
[http://legacy.cs.uu.nl/daan/download/papers/divmodnote.pdf Division and
Modulus for Computer Scientists] (6 pages pdf) by
[http://research.microsoft.com/en-us/people/daan/ Daan Leijen].
"Boute argues that Euclidean division is superior to the other ones in
terms of regularity and useful mathematical properties, allthough floored
division, promoted by Knuth, is also a good definition. Despite its
widespread use, truncated division is shown to be inferior to the other
definitions.
An interesting mathematical property that is only satisfied by Euclidean
division is the shift-rule. A compiler can use this to optimize divisions
by a power of two into an arithmetical shift or a bitwise-and operation."
D '''div''',,E,, (2^n^) = D '''asr''' n
D '''mod''',,E,, (2^n^) = D '''and''' (2^n - 1^)
Note: [https://api.dartlang.org/apidocs/channels/stable/dartdoc-viewer
/dart-core.num Dart]'s modulo operator (%) uses Euclidean division.
--
Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/5615#comment:17>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler
More information about the ghc-tickets
mailing list