[GHC] #9645: Optimize range checks for primitive types

[GHC]

#9645: Optimize range checks for primitive types
-------------------------------------+-------------------------------------
       Reporter:  dfeuer             |                   Owner:
           Type:  feature request    |                  Status:  new
       Priority:  normal             |               Milestone:
      Component:  Compiler           |                 Version:  7.9
       Keywords:                     |        Operating System:
   Architecture:  Unknown/Multiple   |  Unknown/Multiple
     Difficulty:  Unknown            |         Type of failure:
     Blocked By:                     |  None/Unknown
Related Tickets:                     |               Test Case:
                                     |                Blocking:
                                     |  Differential Revisions:
-------------------------------------+-------------------------------------
 This came up in the context of #9638.

 A special case of Carter's recent suggestion that we try to find ways to
 automatically use branchless operators in some cases is to optimize the
 test

 {{{#!hs
 a <= x && x <= b
 }}}

 when `a` and `b` are statically known, along with minor variations that
 use strict comparisons.

 The general pattern is that when `a` and `b` are statically known values
 that look sufficiently like machine integers (including primitive `Enum`
 values), `a <= x && x <= b` can be optimized either to `seq x False` (if
 `b < a`) or to `(fromIntegral (x - a) :: Word) <= (fromIntegral (b - a))`
 (if `a <= b`). This would almost always be a good thing, because at its
 worst, `x < a`, it's slower than the original expression by a single
 addition, but it avoids a potentially expensive conditional jump.

 Of course, by the time it gets to the point where any such optimizations
 might take place, everything will have been converted to case expressions
 nested in some arbitrary fashion; if we're lucky, we'll get something we
 can recognize, like

 {{{#!hs
 case a <= x of
   True -> case x <= b of
             True -> e1
             False -> e2
   False -> e2
 }}}

 or

 {{{#!hs
 case x <= b of
   True -> a <= x
   False -> False
 }}}

 I don't know if we'll always be so lucky, but I think it may make sense to
 at least try to recognize these and similar forms.

--
Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/9645>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler