LCOV - code coverage report
Current view: top level - gcc - double-int.h (source / functions) Hit Total Coverage
Test: gcc.info Lines: 14 32 43.8 %
Date: 2020-04-04 11:58:09 Functions: 2 2 100.0 %
Legend: Lines: hit not hit | Branches: + taken - not taken # not executed Branches: 0 0 -

           Branch data     Line data    Source code
       1                 :            : /* Operations with long integers.
       2                 :            :    Copyright (C) 2006-2020 Free Software Foundation, Inc.
       3                 :            : 
       4                 :            : This file is part of GCC.
       5                 :            : 
       6                 :            : GCC is free software; you can redistribute it and/or modify it
       7                 :            : under the terms of the GNU General Public License as published by the
       8                 :            : Free Software Foundation; either version 3, or (at your option) any
       9                 :            : later version.
      10                 :            : 
      11                 :            : GCC is distributed in the hope that it will be useful, but WITHOUT
      12                 :            : ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
      13                 :            : FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
      14                 :            : for more details.
      15                 :            : 
      16                 :            : You should have received a copy of the GNU General Public License
      17                 :            : along with GCC; see the file COPYING3.  If not see
      18                 :            : <http://www.gnu.org/licenses/>.  */
      19                 :            : 
      20                 :            : #ifndef DOUBLE_INT_H
      21                 :            : #define DOUBLE_INT_H
      22                 :            : 
      23                 :            : /* A large integer is currently represented as a pair of HOST_WIDE_INTs.
      24                 :            :    It therefore represents a number with precision of
      25                 :            :    2 * HOST_BITS_PER_WIDE_INT bits (it is however possible that the
      26                 :            :    internal representation will change, if numbers with greater precision
      27                 :            :    are needed, so the users should not rely on it).  The representation does
      28                 :            :    not contain any information about signedness of the represented value, so
      29                 :            :    it can be used to represent both signed and unsigned numbers.  For
      30                 :            :    operations where the results depend on signedness (division, comparisons),
      31                 :            :    it must be specified separately.  For each such operation, there are three
      32                 :            :    versions of the function -- double_int_op, that takes an extra UNS argument
      33                 :            :    giving the signedness of the values, and double_int_sop and double_int_uop
      34                 :            :    that stand for its specializations for signed and unsigned values.
      35                 :            : 
      36                 :            :    You may also represent with numbers in smaller precision using double_int.
      37                 :            :    You however need to use double_int_ext (that fills in the bits of the
      38                 :            :    number over the prescribed precision with zeros or with the sign bit) before
      39                 :            :    operations that do not perform arithmetics modulo 2^precision (comparisons,
      40                 :            :    division), and possibly before storing the results, if you want to keep
      41                 :            :    them in some canonical form).  In general, the signedness of double_int_ext
      42                 :            :    should match the signedness of the operation.
      43                 :            : 
      44                 :            :    ??? The components of double_int differ in signedness mostly for
      45                 :            :    historical reasons (they replace an older structure used to represent
      46                 :            :    numbers with precision higher than HOST_WIDE_INT).  It might be less
      47                 :            :    confusing to have them both signed or both unsigned.  */
      48                 :            : 
      49                 :            : struct double_int
      50                 :            : {
      51                 :            :   /* Normally, we would define constructors to create instances.
      52                 :            :      Two things prevent us from doing so.
      53                 :            :      First, defining a constructor makes the class non-POD in C++03,
      54                 :            :      and we certainly want double_int to be a POD.
      55                 :            :      Second, the GCC conding conventions prefer explicit conversion,
      56                 :            :      and explicit conversion operators are not available until C++11.  */
      57                 :            : 
      58                 :            :   static double_int from_uhwi (unsigned HOST_WIDE_INT cst);
      59                 :            :   static double_int from_shwi (HOST_WIDE_INT cst);
      60                 :            :   static double_int from_pair (HOST_WIDE_INT high, unsigned HOST_WIDE_INT low);
      61                 :            : 
      62                 :            :   /* Construct from a fuffer of length LEN.  BUFFER will be read according
      63                 :            :      to byte endianness and word endianness.  */
      64                 :            :   static double_int from_buffer (const unsigned char *buffer, int len);
      65                 :            : 
      66                 :            :   /* No copy assignment operator or destructor to keep the type a POD.  */
      67                 :            : 
      68                 :            :   /* There are some special value-creation static member functions.  */
      69                 :            : 
      70                 :            :   static double_int mask (unsigned prec);
      71                 :            :   static double_int max_value (unsigned int prec, bool uns);
      72                 :            :   static double_int min_value (unsigned int prec, bool uns);
      73                 :            : 
      74                 :            :   /* The following functions are mutating operations.  */
      75                 :            : 
      76                 :            :   double_int &operator ++ (); // prefix
      77                 :            :   double_int &operator -- (); // prefix
      78                 :            :   double_int &operator *= (double_int);
      79                 :            :   double_int &operator += (double_int);
      80                 :            :   double_int &operator -= (double_int);
      81                 :            :   double_int &operator &= (double_int);
      82                 :            :   double_int &operator ^= (double_int);
      83                 :            :   double_int &operator |= (double_int);
      84                 :            : 
      85                 :            :   /* The following functions are non-mutating operations.  */
      86                 :            : 
      87                 :            :   /* Conversion functions.  */
      88                 :            : 
      89                 :            :   HOST_WIDE_INT to_shwi () const;
      90                 :            :   unsigned HOST_WIDE_INT to_uhwi () const;
      91                 :            : 
      92                 :            :   /* Conversion query functions.  */
      93                 :            : 
      94                 :            :   bool fits_uhwi () const;
      95                 :            :   bool fits_shwi () const;
      96                 :            :   bool fits_hwi (bool uns) const;
      97                 :            : 
      98                 :            :   /* Attribute query functions.  */
      99                 :            : 
     100                 :            :   int trailing_zeros () const;
     101                 :            :   int popcount () const;
     102                 :            : 
     103                 :            :   /* Arithmetic query operations.  */
     104                 :            : 
     105                 :            :   bool multiple_of (double_int, bool, double_int *) const;
     106                 :            : 
     107                 :            :   /* Arithmetic operation functions.  */
     108                 :            : 
     109                 :            :   /* The following operations perform arithmetics modulo 2^precision, so you
     110                 :            :      do not need to call .ext between them, even if you are representing
     111                 :            :      numbers with precision less than HOST_BITS_PER_DOUBLE_INT bits.  */
     112                 :            : 
     113                 :            :   double_int set_bit (unsigned) const;
     114                 :            :   double_int mul_with_sign (double_int, bool unsigned_p, bool *overflow) const;
     115                 :            :   double_int wide_mul_with_sign (double_int, bool unsigned_p,
     116                 :            :                                  double_int *higher, bool *overflow) const;
     117                 :            :   double_int add_with_sign (double_int, bool unsigned_p, bool *overflow) const;
     118                 :            :   double_int sub_with_overflow (double_int, bool *overflow) const;
     119                 :            :   double_int neg_with_overflow (bool *overflow) const;
     120                 :            : 
     121                 :            :   double_int operator * (double_int) const;
     122                 :            :   double_int operator + (double_int) const;
     123                 :            :   double_int operator - (double_int) const;
     124                 :            :   double_int operator - () const;
     125                 :            :   double_int operator ~ () const;
     126                 :            :   double_int operator & (double_int) const;
     127                 :            :   double_int operator | (double_int) const;
     128                 :            :   double_int operator ^ (double_int) const;
     129                 :            :   double_int and_not (double_int) const;
     130                 :            : 
     131                 :            :   double_int lshift (HOST_WIDE_INT count) const;
     132                 :            :   double_int lshift (HOST_WIDE_INT count, unsigned int prec, bool arith) const;
     133                 :            :   double_int rshift (HOST_WIDE_INT count) const;
     134                 :            :   double_int rshift (HOST_WIDE_INT count, unsigned int prec, bool arith) const;
     135                 :            :   double_int alshift (HOST_WIDE_INT count, unsigned int prec) const;
     136                 :            :   double_int arshift (HOST_WIDE_INT count, unsigned int prec) const;
     137                 :            :   double_int llshift (HOST_WIDE_INT count, unsigned int prec) const;
     138                 :            :   double_int lrshift (HOST_WIDE_INT count, unsigned int prec) const;
     139                 :            :   double_int lrotate (HOST_WIDE_INT count, unsigned int prec) const;
     140                 :            :   double_int rrotate (HOST_WIDE_INT count, unsigned int prec) const;
     141                 :            : 
     142                 :            :   /* You must ensure that double_int::ext is called on the operands
     143                 :            :      of the following operations, if the precision of the numbers
     144                 :            :      is less than HOST_BITS_PER_DOUBLE_INT bits.  */
     145                 :            : 
     146                 :            :   double_int div (double_int, bool, unsigned) const;
     147                 :            :   double_int sdiv (double_int, unsigned) const;
     148                 :            :   double_int udiv (double_int, unsigned) const;
     149                 :            :   double_int mod (double_int, bool, unsigned) const;
     150                 :            :   double_int smod (double_int, unsigned) const;
     151                 :            :   double_int umod (double_int, unsigned) const;
     152                 :            :   double_int divmod_with_overflow (double_int, bool, unsigned,
     153                 :            :                                    double_int *, bool *) const;
     154                 :            :   double_int divmod (double_int, bool, unsigned, double_int *) const;
     155                 :            :   double_int sdivmod (double_int, unsigned, double_int *) const;
     156                 :            :   double_int udivmod (double_int, unsigned, double_int *) const;
     157                 :            : 
     158                 :            :   /* Precision control functions.  */
     159                 :            : 
     160                 :            :   double_int ext (unsigned prec, bool uns) const;
     161                 :            :   double_int zext (unsigned prec) const;
     162                 :            :   double_int sext (unsigned prec) const;
     163                 :            : 
     164                 :            :   /* Comparative functions.  */
     165                 :            : 
     166                 :            :   bool is_zero () const;
     167                 :            :   bool is_one () const;
     168                 :            :   bool is_minus_one () const;
     169                 :            :   bool is_negative () const;
     170                 :            : 
     171                 :            :   int cmp (double_int b, bool uns) const;
     172                 :            :   int ucmp (double_int b) const;
     173                 :            :   int scmp (double_int b) const;
     174                 :            : 
     175                 :            :   bool ult (double_int b) const;
     176                 :            :   bool ule (double_int b) const;
     177                 :            :   bool ugt (double_int b) const;
     178                 :            :   bool slt (double_int b) const;
     179                 :            :   bool sle (double_int b) const;
     180                 :            :   bool sgt (double_int b) const;
     181                 :            : 
     182                 :            :   double_int max (double_int b, bool uns);
     183                 :            :   double_int smax (double_int b);
     184                 :            :   double_int umax (double_int b);
     185                 :            : 
     186                 :            :   double_int min (double_int b, bool uns);
     187                 :            :   double_int smin (double_int b);
     188                 :            :   double_int umin (double_int b);
     189                 :            : 
     190                 :            :   bool operator == (double_int cst2) const;
     191                 :            :   bool operator != (double_int cst2) const;
     192                 :            : 
     193                 :            :   /* Please migrate away from using these member variables publicly.  */
     194                 :            : 
     195                 :            :   unsigned HOST_WIDE_INT low;
     196                 :            :   HOST_WIDE_INT high;
     197                 :            : 
     198                 :            : };
     199                 :            : 
     200                 :            : #define HOST_BITS_PER_DOUBLE_INT (2 * HOST_BITS_PER_WIDE_INT)
     201                 :            : 
     202                 :            : /* Constructors and conversions.  */
     203                 :            : 
     204                 :            : /* Constructs double_int from integer CST.  The bits over the precision of
     205                 :            :    HOST_WIDE_INT are filled with the sign bit.  */
     206                 :            : 
     207                 :            : inline double_int
     208                 :    1588876 : double_int::from_shwi (HOST_WIDE_INT cst)
     209                 :            : {
     210                 :    1588876 :   double_int r;
     211                 :    1588876 :   r.low = (unsigned HOST_WIDE_INT) cst;
     212                 :    1588876 :   r.high = cst < 0 ? -1 : 0;
     213                 :    1588876 :   return r;
     214                 :            : }
     215                 :            : 
     216                 :            : /* Some useful constants.  */
     217                 :            : /* FIXME(crowl): Maybe remove after converting callers?
     218                 :            :    The problem is that a named constant would not be as optimizable,
     219                 :            :    while the functional syntax is more verbose.  */
     220                 :            : 
     221                 :            : #define double_int_minus_one (double_int::from_shwi (-1))
     222                 :            : #define double_int_zero (double_int::from_shwi (0))
     223                 :            : #define double_int_one (double_int::from_shwi (1))
     224                 :            : #define double_int_two (double_int::from_shwi (2))
     225                 :            : #define double_int_ten (double_int::from_shwi (10))
     226                 :            : 
     227                 :            : /* Constructs double_int from unsigned integer CST.  The bits over the
     228                 :            :    precision of HOST_WIDE_INT are filled with zeros.  */
     229                 :            : 
     230                 :            : inline double_int
     231                 :            : double_int::from_uhwi (unsigned HOST_WIDE_INT cst)
     232                 :            : {
     233                 :            :   double_int r;
     234                 :            :   r.low = cst;
     235                 :            :   r.high = 0;
     236                 :            :   return r;
     237                 :            : }
     238                 :            : 
     239                 :            : inline double_int
     240                 :            : double_int::from_pair (HOST_WIDE_INT high, unsigned HOST_WIDE_INT low)
     241                 :            : {
     242                 :            :   double_int r;
     243                 :            :   r.low = low;
     244                 :            :   r.high = high;
     245                 :            :   return r;
     246                 :            : }
     247                 :            : 
     248                 :            : inline double_int &
     249                 :            : double_int::operator ++ ()
     250                 :            : {
     251                 :            :   *this += double_int_one;
     252                 :            :   return *this;
     253                 :            : }
     254                 :            : 
     255                 :            : inline double_int &
     256                 :          0 : double_int::operator -- ()
     257                 :            : {
     258                 :          0 :   *this -= double_int_one;
     259                 :          0 :   return *this;
     260                 :            : }
     261                 :            : 
     262                 :            : inline double_int &
     263                 :            : double_int::operator &= (double_int b)
     264                 :            : {
     265                 :            :   *this = *this & b;
     266                 :            :   return *this;
     267                 :            : }
     268                 :            : 
     269                 :            : inline double_int &
     270                 :            : double_int::operator ^= (double_int b)
     271                 :            : {
     272                 :            :   *this = *this ^ b;
     273                 :            :   return *this;
     274                 :            : }
     275                 :            : 
     276                 :            : inline double_int &
     277                 :            : double_int::operator |= (double_int b)
     278                 :            : {
     279                 :            :   *this = *this | b;
     280                 :            :   return *this;
     281                 :            : }
     282                 :            : 
     283                 :            : /* Returns value of CST as a signed number.  CST must satisfy
     284                 :            :    double_int::fits_signed.  */
     285                 :            : 
     286                 :            : inline HOST_WIDE_INT
     287                 :            : double_int::to_shwi () const
     288                 :            : {
     289                 :            :   return (HOST_WIDE_INT) low;
     290                 :            : }
     291                 :            : 
     292                 :            : /* Returns value of CST as an unsigned number.  CST must satisfy
     293                 :            :    double_int::fits_unsigned.  */
     294                 :            : 
     295                 :            : inline unsigned HOST_WIDE_INT
     296                 :            : double_int::to_uhwi () const
     297                 :            : {
     298                 :            :   return low;
     299                 :            : }
     300                 :            : 
     301                 :            : /* Returns true if CST fits in unsigned HOST_WIDE_INT.  */
     302                 :            : 
     303                 :            : inline bool
     304                 :          0 : double_int::fits_uhwi () const
     305                 :            : {
     306                 :          0 :   return high == 0;
     307                 :            : }
     308                 :            : 
     309                 :            : /* Logical operations.  */
     310                 :            : 
     311                 :            : /* Returns ~A.  */
     312                 :            : 
     313                 :            : inline double_int
     314                 :            : double_int::operator ~ () const
     315                 :            : {
     316                 :            :   double_int result;
     317                 :            :   result.low = ~low;
     318                 :            :   result.high = ~high;
     319                 :            :   return result;
     320                 :            : }
     321                 :            : 
     322                 :            : /* Returns A | B.  */
     323                 :            : 
     324                 :            : inline double_int
     325                 :          0 : double_int::operator | (double_int b) const
     326                 :            : {
     327                 :          0 :   double_int result;
     328                 :          0 :   result.low = low | b.low;
     329                 :          0 :   result.high = high | b.high;
     330                 :          0 :   return result;
     331                 :            : }
     332                 :            : 
     333                 :            : /* Returns A & B.  */
     334                 :            : 
     335                 :            : inline double_int
     336                 :            : double_int::operator & (double_int b) const
     337                 :            : {
     338                 :            :   double_int result;
     339                 :            :   result.low = low & b.low;
     340                 :            :   result.high = high & b.high;
     341                 :            :   return result;
     342                 :            : }
     343                 :            : 
     344                 :            : /* Returns A & ~B.  */
     345                 :            : 
     346                 :            : inline double_int
     347                 :            : double_int::and_not (double_int b) const
     348                 :            : {
     349                 :            :   double_int result;
     350                 :            :   result.low = low & ~b.low;
     351                 :            :   result.high = high & ~b.high;
     352                 :            :   return result;
     353                 :            : }
     354                 :            : 
     355                 :            : /* Returns A ^ B.  */
     356                 :            : 
     357                 :            : inline double_int
     358                 :            : double_int::operator ^ (double_int b) const
     359                 :            : {
     360                 :            :   double_int result;
     361                 :            :   result.low = low ^ b.low;
     362                 :            :   result.high = high ^ b.high;
     363                 :            :   return result;
     364                 :            : }
     365                 :            : 
     366                 :            : void dump_double_int (FILE *, double_int, bool);
     367                 :            : 
     368                 :            : #define ALL_ONES HOST_WIDE_INT_M1U
     369                 :            : 
     370                 :            : /* The operands of the following comparison functions must be processed
     371                 :            :    with double_int_ext, if their precision is less than
     372                 :            :    HOST_BITS_PER_DOUBLE_INT bits.  */
     373                 :            : 
     374                 :            : /* Returns true if CST is zero.  */
     375                 :            : 
     376                 :            : inline bool
     377                 :          0 : double_int::is_zero () const
     378                 :            : {
     379                 :          0 :   return low == 0 && high == 0;
     380                 :            : }
     381                 :            : 
     382                 :            : /* Returns true if CST is one.  */
     383                 :            : 
     384                 :            : inline bool
     385                 :            : double_int::is_one () const
     386                 :            : {
     387                 :            :   return low == 1 && high == 0;
     388                 :            : }
     389                 :            : 
     390                 :            : /* Returns true if CST is minus one.  */
     391                 :            : 
     392                 :            : inline bool
     393                 :            : double_int::is_minus_one () const
     394                 :            : {
     395                 :            :   return low == ALL_ONES && high == -1;
     396                 :            : }
     397                 :            : 
     398                 :            : /* Returns true if CST is negative.  */
     399                 :            : 
     400                 :            : inline bool
     401                 :          0 : double_int::is_negative () const
     402                 :            : {
     403                 :          0 :   return high < 0;
     404                 :            : }
     405                 :            : 
     406                 :            : /* Returns true if CST1 == CST2.  */
     407                 :            : 
     408                 :            : inline bool
     409                 :          0 : double_int::operator == (double_int cst2) const
     410                 :            : {
     411                 :          0 :   return low == cst2.low && high == cst2.high;
     412                 :            : }
     413                 :            : 
     414                 :            : /* Returns true if CST1 != CST2.  */
     415                 :            : 
     416                 :            : inline bool
     417                 :          0 : double_int::operator != (double_int cst2) const
     418                 :            : {
     419                 :          0 :   return low != cst2.low || high != cst2.high;
     420                 :            : }
     421                 :            : 
     422                 :            : /* Return number of set bits of CST.  */
     423                 :            : 
     424                 :            : inline int
     425                 :            : double_int::popcount () const
     426                 :            : {
     427                 :            :   return popcount_hwi (high) + popcount_hwi (low);
     428                 :            : }
     429                 :            : 
     430                 :            : 
     431                 :            : #ifndef GENERATOR_FILE
     432                 :            : /* Conversion to and from GMP integer representations.  */
     433                 :            : 
     434                 :            : void mpz_set_double_int (mpz_t, double_int, bool);
     435                 :            : double_int mpz_get_double_int (const_tree, mpz_t, bool);
     436                 :            : #endif
     437                 :            : 
     438                 :            : namespace wi
     439                 :            : {
     440                 :            :   template <>
     441                 :            :   struct int_traits <double_int>
     442                 :            :   {
     443                 :            :     static const enum precision_type precision_type = CONST_PRECISION;
     444                 :            :     static const bool host_dependent_precision = true;
     445                 :            :     static const unsigned int precision = HOST_BITS_PER_DOUBLE_INT;
     446                 :            :     static unsigned int get_precision (const double_int &);
     447                 :            :     static wi::storage_ref decompose (HOST_WIDE_INT *, unsigned int,
     448                 :            :                                       const double_int &);
     449                 :            :   };
     450                 :            : }
     451                 :            : 
     452                 :            : inline unsigned int
     453                 :    6521150 : wi::int_traits <double_int>::get_precision (const double_int &)
     454                 :            : {
     455                 :    6521150 :   return precision;
     456                 :            : }
     457                 :            : 
     458                 :            : inline wi::storage_ref
     459                 :    6521150 : wi::int_traits <double_int>::decompose (HOST_WIDE_INT *scratch, unsigned int p,
     460                 :            :                                         const double_int &x)
     461                 :            : {
     462                 :    6521150 :   gcc_checking_assert (precision == p);
     463                 :    6521150 :   scratch[0] = x.low;
     464                 :    6521150 :   if ((x.high == 0 && scratch[0] >= 0) || (x.high == -1 && scratch[0] < 0))
     465                 :    6512550 :     return wi::storage_ref (scratch, 1, precision);
     466                 :       8607 :   scratch[1] = x.high;
     467                 :       8607 :   return wi::storage_ref (scratch, 2, precision);
     468                 :            : }
     469                 :            : 
     470                 :            : #endif /* DOUBLE_INT_H */

Generated by: LCOV version 1.0

LCOV profile is generated on x86_64 machine using following configure options: configure --disable-bootstrap --enable-coverage=opt --enable-languages=c,c++,fortran,go,jit,lto --enable-host-shared. GCC test suite is run with the built compiler.