Skip to content
GitLab
Projects Groups Snippets
  • /
  • Help
    • Help
    • Support
    • Community forum
    • Submit feedback
  • Sign in / Register
  • GHC GHC
  • Project information
    • Project information
    • Activity
    • Labels
    • Members
  • Repository
    • Repository
    • Files
    • Commits
    • Branches
    • Tags
    • Contributors
    • Graph
    • Compare
    • Locked Files
  • Issues 5,247
    • Issues 5,247
    • List
    • Boards
    • Service Desk
    • Milestones
    • Iterations
  • Merge requests 577
    • Merge requests 577
  • CI/CD
    • CI/CD
    • Pipelines
    • Jobs
    • Schedules
    • Test Cases
  • Deployments
    • Deployments
    • Releases
  • Analytics
    • Analytics
    • Value stream
    • CI/CD
    • Code review
    • Insights
    • Issue
    • Repository
  • Wiki
    • Wiki
  • Snippets
    • Snippets
  • Activity
  • Graph
  • Create a new issue
  • Jobs
  • Commits
  • Issue Boards
Collapse sidebar
  • Glasgow Haskell CompilerGlasgow Haskell Compiler
  • GHCGHC
  • Issues
  • #19636
Closed
Open
Issue created Apr 02, 2021 by Simon Peyton Jones@simonpjDeveloper

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
Assignee
Assign to
Time tracking