[GHC] #5663: integer-gmp passes arguments to __gmpn_gcd_1() in contravention of the docs

[GHC]

#5663: integer-gmp passes arguments to __gmpn_gcd_1() in contravention of the docs
---------------------------------+------------------------------------------
    Reporter:  Irene             |       Owner:                             
        Type:  bug               |      Status:  new                        
    Priority:  normal            |   Component:  libraries (other)          
     Version:  7.3               |    Keywords:                             
    Testcase:                    |   Blockedby:                             
          Os:  Unknown/Multiple  |    Blocking:                             
Architecture:  x86_64 (amd64)    |     Failure:  Incorrect result at runtime
---------------------------------+------------------------------------------
 I have encountered this issue on GHC HEAD, but it looks like it's been the
 case for a long time:  The implementation of gcdInt#, which is used by gcd
 for Int#, some other integer types, and Integer when both parameters use
 the S# "small" constructor, is a wrapper around __gmpn_gcd_1().  The GMP
 documentation for mpn_gcd() states some input preconditions for its
 inputs, and the documentation for mpn_gcd_1() comes right after it and is
 very terse, implying that the same preconditions are assumed.  We do in
 fact guarantee most of those preconditions, in particular that the first
 input is the larger one, but it specifies that the second input must be
 odd, and we don't check that.  (I'm not quite clear on what we're supposed
 to do if it isn't, but presumably there's some simple algorithm ...)

 This is not just a theoretical problem.  GMP has multiple implementations
 of its algorithms, for multiple architectures, and no doubt each one has
 slightly different characteristics; I have tested on an x86-64 system,
 which uses the implementation of mpn_gcd_1() in the file libraries
 /integer-gmp/gmp/gmpbuild/mpn/x86_64/gcd_1.asm.  I don't really want to
 make sense of the assembly language and figure out why it misbehaves, but
 we're violating the documentation and the entire mpn_* suite of functions
 is considered "internal and difficult to use correctly", so we are the
 ones who need to change, not them.

 The problem can be seen as follows:

 GHCi, version 7.3.20111124: http://www.haskell.org/ghc/  :? for help
 Loading package ghc-prim ... linking ... done.
 Loading package integer-gmp ... linking ... done.
 Loading package base ... linking ... done.
 Prelude> import GHC.Integer.GMP.Internals
 Prelude GHC.Integer.GMP.Internals> import GHC.Types
 Prelude GHC.Integer.GMP.Internals GHC.Types GHC.Int> import
 GHC.Integer.GMP.Prim
 Prelude GHC.Integer.GMP.Internals GHC.Types GHC.Int GHC.Integer.GMP.Prim>
 I# (gcdInt# 0x2B992DDFA23249D6# 0xDE0B6B3A7640000#)
 0

 This should reproduce on any x86-64 system, although I don't have access
 to another one to test that.  In my setup, I'm using the in-tree GMP,
 which is GMP 5.0.2 as of this writing.

 To elicit this misbehavior without using an internal function is a little
 harder.  It comes up on my system when attempting to build the GHC
 haddocks, trying to compute a Rational approximation of pi (that process
 is where I discovered the above magic constants).  But it will not
 reproduce easily for other people.  I am still investigating why not, but
 I suspect that cross-module dictionary-function unfolding, which is
 implemented with built-in rewrite rules, one for each class, is broken and
 has not worked on any platform for at least a couple months.  This in turn
 prevents other rewrite rules from firing; constant folding of arithmetic
 operations can't happen because those rules are written against primops,
 not against the methods of Num.  On investigation, I have found that some
 compilation settings (profiling, dynamic linking) correctly include the
 definition, and not just the type, of dictionary functions in interface
 files, but vanilla compilation does not.  I note that a comment in
 compiler/main/TidyPgm.lhs claims that DFun unfoldings are communicated to
 the code in compiler/iface/MkIface.lhs by placing them in the binding; but
 the bindings are part of the CgGuts, which are not passed to mkIface at
 all (only the ModGuts are).  So there needs to be a new mechanism to pass
 this information, and I'm not sure what it should be, or why it does get
 included with some settings.  I'll file a separate ticket on this when I
 have more facts, and not just speculation; I mention it here only because
 it interacts with the gcd bug, both masking it and evoking it in different
 situations.

 The upshot: Anyone seeking to reproduce the behavior will find it does not
 arise if they invoke "gcd 3141592653589793238 1000000000000000000 ::
 Integer", because this gets folded at compile-time by a rule that DOES
 still work.  Invoking "gcdInteger 3141592653589793238 1000000000000000000"
 directly will trigger the bug from the interpreter, but not when compiled,
 because there is a non-builtin rewrite rule on gcdInteger (not, you will
 observe, a dictionary function, and hence not affected by the other
 problem) which folds it.  However, because of the aforementioned
 brokenness of constant folding on arithmetic, I expect that the behavior
 can be reproduced on all x86-64 platforms, both interpreted and compiled,
 by invoking "gcdInteger (3141592653589793238 * 1) (1 *
 1000000000000000000)".

 The code that needs changes for the gcd issue can be found in libraries
 /integer-gmp/cbits/gmp-wrappers.cmm.

-- 
Ticket URL: <http://hackage.haskell.org/trac/ghc/ticket/5663>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler