Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

How is integer comparison implemented in GHC?

Tags:

haskell

ghc

At first, I wanted to look into how Integer was deriving from the classOrd

I got that definition in GHC.Classes

instance Ord Integer where
    (<=) = leInteger
    (>)  = gtInteger
    (<)  = ltInteger
    (>=) = geInteger
    compare = compareInteger

compareInteger is pointing to another source file, GHC.Integer.Type. it is defined like this :

compareInteger :: Integer -> Integer -> Ordering
compareInteger (Jn# x)  (Jn# y) = compareBigNat y x
compareInteger (S#  x)  (S#  y) = compareInt#   x y
compareInteger (Jp# x)  (Jp# y) = compareBigNat x y
compareInteger (Jn# _)  _       = LT
compareInteger (S#  _)  (Jp# _) = LT
compareInteger (S#  _)  (Jn# _) = GT
compareInteger (Jp# _)  _       = GT

S# is for fixed-size integers, Jn# and Jp# for arbitrary size integers.

In GHC.Classes (from the package ghc-prim) I was able to find a definition for compareInt#. The occurence of unusual types like Int# signaled me I was getting closer.

compareInt# :: Int# -> Int# -> Ordering
compareInt# x# y#
    | isTrue# (x# <#  y#) = LT
    | isTrue# (x# ==# y#) = EQ
    | True                = GT

Still going deeper, I got this definition for the operator (GHC.Prim module)

infix 4 <#
(<#) :: Int# -> Int# -> Int#
(<#) = (<#)

But this is a deep I was able to get. <# is refering to itself. We don’t know what it’s doing.

(isTrue# is simply a function that “Returns True if its parameter is 1# and False if 0#”)

Where can I find the source, the actual place where the job is getting done ? Is there some assembly at the very bottom ? Where do I find this sacred place ?

like image 954
Albizia Avatar asked Nov 06 '21 13:11

Albizia


People also ask

How to compare two integers in Befunge?

Befunge only has the greater-than operator (backtick `). The branch commands (underline _ and pipe |) test for zero. The function Comp compares two integers and returns the appropriate string result. blsq ) "5 6"ps^pcm+. {"The first one is less than the second one""They are both equal""The second one is less than the first one"}\/!!sh

How to compare two integer values in Java?

The Integer compare () method of Java accepts two integer values as input parameters. These two input parameters are required. It then compares those two parameters and gives us the result. NOTE: Input parameters for the Integer compare () method cannot be float or long. It has to be of int type.

What is the use of compare() method in Java?

The compare () method of the Integer class of the java.lang package compares two integer values (a, b) given as parameters and returns a value larger than zero (or 1) if (a > b). From Java version 11, you may or may not include the java.lang.Integer class for using the Integer compare () method of Java. Importing isn’t mandatory.

How many integers are passed as parameters to the command line?

Two integers are passed as parameters. Because the command line casts numeric literals as packed (15,5), calling from the command line requires the user to specify the 8 nybbles in hexadecimal form: CALL rc_intcmp (x'00000000' x'00000001')


1 Answers

First of all, technically when you enter the GHC.Integer.Type module you leave the realm of Haskell and enter the realm of the current implementation that GHC uses, so this question is about GHC Haskell specifically.

All the primitive operations like (<#) are implemented as a recursive loop which you have found in the GHC.Prim module. From there the documentation tells us the next place to look is the primops.txt.pp file where it is listed under the name IntLtOp.

Then the documentation mentioned earlier says there are two groups of primops: in-line and out-of-line. In-line primops are resolved during the translation from STG to Cmm (which are two internal representations that GHC uses) and can be found in the GHC.StgToCmm.Prim module. And indeed the IntLtOp case is listed there and it is transformed in-line using mainly the mo_wordSLt function which depends on the platform.

This mo_wordSLt function is defined in the GHC.Cmm.MachOp module which contains to quote:

Machine-level primops; ones which we can reasonably delegate to the native code generators to handle.

The mo_wordSLt function produces the MO_S_Lt constructor of the MachOp data type. So we can look further into a native code generator to see how that is translated into low-level instructions. There is quite a bit of choice in platforms: SPARC, AArch64, LLVM, C, PPC, and X86 (I found all these with the search function on GitLab).

X86 is the most popular platform, so I will continue there. The implementation uses a condIntReg helper function, which is defined as follows:

condIntReg :: Cond -> CmmExpr -> CmmExpr -> NatM Register

condIntReg cond x y = do
  CondCode _ cond cond_code <- condIntCode cond x y
  tmp <- getNewRegNat II8
  let
        code dst = cond_code `appOL` toOL [
                    SETCC cond (OpReg tmp),
                    MOVZxL II8 (OpReg tmp) (OpReg dst)
                  ]
  return (Any II32 code)

Also interesting is the definition of condIntCode, which depends on the operands of the condition. It is a large function, so I will not reproduce the full code here, but the general case produces a CMP instruction:

-- anything vs anything
condIntCode' _ cond x y = do
  platform <- getPlatform
  (y_reg, y_code) <- getNonClobberedReg y
  (x_op, x_code) <- getRegOrMem x
  let
        code = y_code `appOL`
               x_code `snocOL`
                  CMP (cmmTypeFormat (cmmExprType platform x)) (OpReg y_reg) x_op
  return (CondCode False cond code)
like image 106
Noughtmare Avatar answered Oct 15 '22 10:10

Noughtmare