Opened 5 years ago

Last modified 4 years ago

#9645 new feature request

Optimize range checks for primitive types

Reported by: dfeuer Owned by:
Priority: normal Milestone:
Component: Compiler Version: 7.9
Keywords: Cc: carter.schonwald@…
Operating System: Unknown/Multiple Architecture: Unknown/Multiple
Type of failure: Runtime performance bug Test Case:
Blocked By: Blocking:
Related Tickets: Differential Rev(s):
Wiki Page:

Description

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

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

case a <= x of
  True -> case x <= b of
            True -> e1
            False -> e2
  False -> e2

or

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.

Change History (1)

comment:1 Changed 4 years ago by thomie

Type of failure: None/UnknownRuntime performance bug
Note: See TracTickets for help on using tickets.