Comparisons against minBound/maxBound not optimised for (Int|Word)(8|16|32)

foo :: Int -> Bool
foo n = n < minBound || n > maxBound

GHC retains both comparisons even though they are guaranteed to be False. This also happens for other integral types. The optimisation is fairly easy to implement for Int and Word (only requires some plumbing in !PrelRules) but it's not clear what to do about smaller integral types. For Int64 and Word64, GHC doesn't even inline minBound and maxBound:

T.$wfoo :: GHC.Prim.Int64# -> GHC.Bool.Bool
T.$wfoo =
  \ (ww_ss5 :: GHC.Prim.Int64#) ->
    case GHC.Int.$fBoundedInt64_$cminBound
    of _ { GHC.Int.I64# y#_are ->
    case {__ccall hs_ltInt64 GHC.Prim.Int64#
                    -> GHC.Prim.Int64#
                    -> GHC.Prim.State# GHC.Prim.RealWorld
                    -> (# GHC.Prim.State# GHC.Prim.RealWorld, GHC.Prim.Int# #)}_arD
           ww_ss5 y#_are GHC.Prim.realWorld#
    of _ { (# _, ds3_arH #) ->
    case ds3_arH of _ {
      __DEFAULT -> GHC.Bool.True;
      0 ->
        case GHC.Int.$fBoundedInt64_$cmaxBound
        of _ { GHC.Int.I64# y#1_ar4 ->
        GHC.IntWord64.gtInt64# ww_ss5 y#1_ar4
        }
    }
    }
    }

T.foo :: GHC.Int.Int64 -> GHC.Bool.Bool
T.foo =
  \ (w_ss3 :: GHC.Int.Int64) ->
    case w_ss3 of _ { GHC.Int.I64# ww_ss5 -> T.$wfoo ww_ss5 }

Trac metadata

Trac field	Value
Version	6.13
Type	Bug
TypeOfFailure	OtherFailure
Priority	normal
Resolution	Unresolved
Component	Compiler
Test case
Differential revisions
BlockedBy
Related
Blocking
CC
Operating system
Architecture

changed weight to 5

added Tbug Trac import labels

changed milestone to %6.14 branch

mentioned in issue #4019 (closed)

removed milestone

A global

{-# RULES
"(<)/minBound"  forall x. x < minBound = False
"(>)/minBound"  forall x. minBound > x = False
etc.
  #-}

would eliminate those checks in many (almost all, hopefully) cases. However, it would break user code relying on incompatible Ord and Enum instances (it should not break local bindings for minBound/maxBound since the rule refers to GHC.Enum.minBound).

Alternatively, one could add those rules for every pertinent type, but I'd prefer a more general solution.

I don't think these rules would work reliably because the comparison operators could (and would) be inlined before the rules have had a chance to fire. Rules for specific primitive types wouldn't have this problem but IIRC, matching against the actual bounds literals can be problematic.

mentioned in commit d4781f3e

I've created a patch with rules for PrelRules.lhs that detect comparisons with minBound and maxBound that are always true or always false (like in the above examples). And it seems to work just fine:

foo1, foo2, foo3, foo4 :: Int -> Bool

foo1 n = n < minBound

foo2 n = n > maxBound

foo3 n = n >= minBound

foo4 n = n <= maxBound

gives now

Test.foo1 =
  \ (n_aaD :: GHC.Types.Int) ->
    case n_aaD of _ { GHC.Types.I# _ -> GHC.Bool.False }

Test.foo2 =
  \ (n_ag0 :: GHC.Types.Int) ->
    case n_ag0 of _ { GHC.Types.I# _ -> GHC.Bool.False }

Test.foo3 =
  \ (n_ag1 :: GHC.Types.Int) ->
    case n_ag1 of _ { GHC.Types.I# _ -> GHC.Bool.True }

Test.foo4 =
  \ (n_ag2 :: GHC.Types.Int) ->
    case n_ag2 of _ { GHC.Types.I# _ -> GHC.Bool.True }

This works fine also for Char, and Word, but interestingly in case of Int64 only maxBound is inlined, but not minBound (and so foo2 and foo4 are optimised but not foo1 and foo3), whereas in case of Word64 the opposite happens. For example by changing the type to Int64 in the above code we have:

Test.foo1 =
  \ (n_aaF :: GHC.Int.Int64) ->
    case n_aaF of _ { GHC.Int.I64# a1_ar3 ->
    case GHC.Int.$fBoundedInt64_$cminBound
    of _ { GHC.Int.I64# b1_ar7 ->
    GHC.Prim.<# a1_ar3 b1_ar7
    }
    }

Test.foo2 =
  \ (n_ag2 :: GHC.Int.Int64) ->
    case n_ag2 of _ { GHC.Int.I64# _ -> GHC.Bool.False }

Test.foo3 =
  \ (n_ag3 :: GHC.Int.Int64) ->
    case n_ag3 of _ { GHC.Int.I64# a1_arn ->
    case GHC.Int.$fBoundedInt64_$cminBound
    of _ { GHC.Int.I64# b1_arr ->
    GHC.Prim.>=# a1_arn b1_arr
    }
    }

Test.foo4 =
  \ (n_ag4 :: GHC.Int.Int64) ->
    case n_ag4 of _ { GHC.Int.I64# _ -> GHC.Bool.True }

Anyway, I'll attach the patch in a second. And please let me know what do you think about it (especially since I don't really know a lot about GHC internals).

Attached file minmaxbound.dpatch (download).

changed milestone to %7.0.2

changed milestone to %7.2.1

closed

Sorry for the delay. Now applied, thanks.

Trac metadata

Trac field	Value
Resolution	Unresolved → ResolvedFixed

The optimisation seems ok, but does this situation ever arise in practice? Who asks x < minBound?

Simon

Replying to [ticket:3744#comment:49615 simonpj]:

The optimisation seems ok, but does this situation ever arise in practice? Who asks x < minBound?

Simon

Well, I'm pretty sure I've never wrote something like that. ;)

On the other hand the ticket has been around for a while with a comment or two, so I thought that the optimization might be useful for someone. But I don't really feel strongly about it.

reopened

Replying to [ticket:3744#comment:49615 simonpj]:

The optimisation seems ok, but does this situation ever arise in practice? Who asks x < minBound?

Me! I jump through some hoops in vector to avoid the following problem.

foo :: Num a => a -> a
{-# INLINE foo #-}
foo x | x < 0 = error "Negative argument"
      | otherwise = e

bar :: Word -> Word
bar x = foo x + 1

I completely missed the patch, thanks a lot for this! Unfortunately, it doesn't handle Int8/Int16/Word8/Word16 and Int32/Word32 on 64 bit systems. It isn't very clear how to do this because we only have Int# and Word# in Core. Also, the inlining of minBound/maxBound for 64 bit types on 32 bit systems which this patch depends on doesn't work reliably. So this ticket isn't quite fixed yet but this is good progress!

Trac metadata

Trac field	Value
Resolution	ResolvedFixed → Unresolved

changed milestone to %7.4.1

changed milestone to %7.6.1

changed weight to 3

Trac metadata

Trac field	Value
Priority	normal → low

changed milestone to %7.6.2

changed milestone to %7.10.1

Moving to 7.10.1.

changed title from Comparisons against minBound/maxBound not optimised to Comparisons against minBound/maxBound not optimised for (Int|Word)(8|16|32)

Status: see ticket:3744#comment:49665. Use program from ticket:3744#comment:45613 to test, and replace Int by Int8 (Int64 works since 7.4).

For reference: commit d4781f3e

Author: Michal Terepeta <>
Date:   Wed Oct 27 18:40:54 2010 +0000

    Optimise comparisons against min/maxBound (ticket #3744).
    
    This optimises away comparisons with minBound or maxBound
    that are always false or always true.

commit fe582123

Author: Ian Lynagh <>
Date:   Wed Sep 19 22:37:01 2012 +0100

    Make some uses of minBound/maxBound use the target Int/Word sizes

Trac metadata

Trac field	Value
Type	Bug → FeatureRequest

added Tfeature request label and removed Tbug label

removed milestone

Moving to 7.12.1 milestone; if you feel this is an error and should be addressed sooner, please move it back to the 7.10.1 milestone.

I just ran into this too. Perhaps the thing to do is to generate rules in PrelRules like

    narrow8IntOp x <= 127 = True

etc.

changed milestone to %8.0.1

Milestone renamed

added Tbug runtime perf labels

added Plow label

mentioned in issue #19641 (closed)

As of GHC %9.2.1 the program:

import Data.Int

int :: Int -> Bool
int n = n < minBound || n > maxBound

int8 :: Int8 -> Bool
int8 n = n < minBound || n > maxBound

Generates:

int :: Int -> Bool
int
  = \ (n_aBj :: Int) ->
      case n_aBj of { GHC.Types.I# x_aSP -> GHC.Types.False }

int8 :: Int8 -> Bool
int8
  = \ (n_aRE :: Int8) ->
      case n_aRE of { GHC.Int.I8# x_aT5 ->
      case GHC.Prim.ltInt8# x_aT5 -128#8 of {
        __DEFAULT ->
          GHC.Prim.tagToEnum# @Bool (GHC.Prim.gtInt8# x_aT5 127#8);
        1# -> GHC.Types.True
      }
      }

In short, the Int case works as expected but more work in still needed in the sub-word case. This appears to just be a matter of missing constant-folding rules.

Ahh, but the the necessary constant-folding has been introduced in master (see c363108e):

int :: Int -> Bool
int
  = \ (n_aC6 :: Int) ->
      case n_aC6 of { GHC.Types.I# x_aUf -> GHC.Types.False }

int8 :: Int8 -> Bool
int8
  = \ (n_aT0 :: Int8) ->
      case n_aT0 of { GHC.Int.I8# x_aUv -> GHC.Types.False }

Closing.

closed