Skip to content

Improve code for `divInt#`

I see this code for ghc-prim:GHC.Classes.divInt#:

divInt# :: Int# -> Int# -> Int#
x# `divInt#` y#
    =      if isTrue# (x# ># 0#) && isTrue# (y# <# 0#) then ((x# -# 1#) `quotInt#` y#) -# 1#
      else if isTrue# (x# <# 0#) && isTrue# (y# ># 0#) then ((x# +# 1#) `quotInt#` y#) -# 1#
      else x# `quotInt#` y#

This requires quite a lot of tests:

divInt# = \ (x#_aSk :: GHC.Prim.Int#)
            (y#_aSl :: GHC.Prim.Int#) ->
            case GHC.Prim.># x#_aSk 0# of {
              __DEFAULT ->
                case GHC.Prim.<# x#_aSk 0# of {
                  __DEFAULT -> GHC.Prim.quotInt# x#_aSk y#_aSl;
                  1# ->
                    case GHC.Prim.># y#_aSl 0# of {
                      __DEFAULT -> GHC.Prim.quotInt# x#_aSk y#_aSl;
                      1# ->
                        case GHC.Prim.quotInt# (GHC.Prim.+# x#_aSk 1#) y#_aSl
                        of wild_aSp [Occ=Once1]
                        { __DEFAULT ->
                        GHC.Prim.-# wild_aSp 1#
                        }
                    }
                };
              1# ->
                case GHC.Prim.<# y#_aSl 0# of {
                  __DEFAULT ->
                    case GHC.Prim.<# x#_aSk 0# of {
                      __DEFAULT -> GHC.Prim.quotInt# x#_aSk y#_aSl;
                      1# ->
                        case GHC.Prim.># y#_aSl 0# of {
                          __DEFAULT -> GHC.Prim.quotInt# x#_aSk y#_aSl;
                          1# ->
                            case GHC.Prim.quotInt# (GHC.Prim.+# x#_aSk 1#) y#_aSl
                            of wild_aSt [Occ=Once1]
                            { __DEFAULT ->
                            GHC.Prim.-# wild_aSt 1#
                            }
                        }
                    };
                  1# ->
                    case GHC.Prim.quotInt# (GHC.Prim.-# x#_aSk 1#) y#_aSl
                    of wild_aSu [Occ=Once1]
                    { __DEFAULT ->
                    GHC.Prim.-# wild_aSu 1#
                    }
                }
            }

(Recall that (>#) etc returns 0# for False, and 1# for True.)

We see

  • There is a test GHC.Prim.<# x#_aSk 0# inside the True branch of GHC.Prim.># x#_aSk 0#. The inner test will always return False, but we don't spot that. Surely we ought to? I'm sure there are tickets about this.

  • But even then we'd end up with

              case GHC.Prim.># x#_aSk 0# of {
                __DEFAULT ->
                  case GHC.Prim.<# x#_aSk 0# of {
                    __DEFAULT -> GHC.Prim.quotInt# x#_aSk y#_aSl;
                    1# ->
                      case GHC.Prim.># y#_aSl 0# of {
                        __DEFAULT -> GHC.Prim.quotInt# x#_aSk y#_aSl;
                        1# ->
                          case GHC.Prim.quotInt# (GHC.Prim.+# x#_aSk 1#) y#_aSl
                          of wild_aSp [Occ=Once1]
                          { __DEFAULT ->
                          GHC.Prim.-# wild_aSp 1#
                          }
                      }
                  };
                1# ->
                  case GHC.Prim.<# y#_aSl 0# of {
                    __DEFAULT -> GHC.Prim.quotInt# x#_aSk y#_aSl;
                    1# ->
                      case GHC.Prim.quotInt# (GHC.Prim.-# x#_aSk 1#) y#_aSl
                      of wild_aSu [Occ=Once1]
                      { __DEFAULT ->
                      GHC.Prim.-# wild_aSu 1#
                      }
                  }
              }

    We still make two tests on x.

  • But I think we can do better, by writing the function like this, testing y first:

    x# `divInt#` y#
      = case isTrue# (y# >=# 0#) of
           True  -> case isTrue (x# >=# 0#) of
                       True  -> -- y positive or zero, x positive or zero
                                x# `quotInt#` y#
                       False -> -- y positive or zero, x strictly negative
                                ((x# +# 1#) `quotInt#` y#) -# 1#
           False -> case isTrue (x# ># 0#) of
                      True  -> -- y strictly negative, x strictly positive
                               ((x# -# 1#) `quotInt#` y#) -# 1#
                      False -> -- Both negative or zero
                               x# `quotInt#` y#

    It actually makes the code a bit easier to grok too.

To upload designs, you'll need to enable LFS and have an admin enable hashed storage. More information