Opened 8 years ago

Last modified 21 months ago

#3744 new feature request

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

Reported by: rl Owned by:
Priority: low Milestone:
Component: Compiler Version: 6.13
Keywords: Cc: daniel.is.fischer@…, michal.terepeta@…, rwbarton
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

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 }

Attachments (1)

minmaxbound.dpatch (181.5 KB) - added by michalt 7 years ago.

Download all attachments as: .zip

Change History (22)

comment:1 Changed 8 years ago by igloo

Milestone: 6.14 branch

comment:2 Changed 7 years ago by igloo

Milestone: 6.14 branch6.14.1

comment:3 Changed 7 years ago by daniel.is.fischer

Cc: daniel.is.fischer@… added

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.

comment:4 Changed 7 years ago by rl

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.

comment:5 Changed 7 years ago by michalt

Cc: michal.terepeta@… added

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).

Changed 7 years ago by michalt

Attachment: minmaxbound.dpatch added

comment:6 Changed 7 years ago by michalt

Status: newpatch

comment:7 Changed 7 years ago by igloo

Milestone: 7.0.17.0.2

comment:8 Changed 7 years ago by igloo

Milestone: 7.0.27.2.1

comment:9 Changed 7 years ago by igloo

Resolution: fixed
Status: patchclosed

Sorry for the delay. Now applied, thanks.

comment:10 Changed 7 years ago by simonpj

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

Simon

comment:11 in reply to:  10 Changed 7 years ago by michalt

Replying to 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.

comment:12 in reply to:  10 Changed 7 years ago by rl

Resolution: fixed
Status: closednew

Replying to 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!

comment:13 Changed 6 years ago by igloo

Milestone: 7.2.17.4.1

comment:14 Changed 6 years ago by igloo

Milestone: 7.4.17.6.1
Priority: normallow

comment:15 Changed 5 years ago by igloo

Milestone: 7.6.17.6.2

comment:16 Changed 3 years ago by thoughtpolice

Milestone: 7.6.27.10.1

Moving to 7.10.1.

comment:17 Changed 3 years ago by thomie

difficulty: Unknown
Summary: Comparisons against minBound/maxBound not optimisedComparisons against minBound/maxBound not optimised for (Int|Word)(8|16|32)
Type: bugfeature request

Status: see comment:12. Use program from comment:5 to test, and replace Int by Int8 (Int64 works since 7.4).

For reference: commit d4781f3e6e8cead1cbeac5337f9f78440c8df8bc

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 fe5821233d439c35c441cfc6c9d2029e5fd01342

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

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

comment:18 Changed 3 years ago by thoughtpolice

Milestone: 7.10.17.12.1

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.

comment:19 Changed 2 years ago by rwbarton

Cc: rwbarton added

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

    narrow8IntOp x <= 127 = True

etc.

Last edited 2 years ago by rwbarton (previous) (diff)

comment:20 Changed 2 years ago by thoughtpolice

Milestone: 7.12.18.0.1

Milestone renamed

comment:21 Changed 21 months ago by thomie

Milestone: 8.0.1
Note: See TracTickets for help on using tickets.