Bug 38282 - Bit intrinsics: ILEN and IBCHNG
Summary: Bit intrinsics: ILEN and IBCHNG
Status: RESOLVED FIXED
Alias: None
Product: gcc
Classification: Unclassified
Component: fortran (show other bugs)
Version: 4.4.0
: P3 enhancement
Target Milestone: 4.6.0
Assignee: Not yet assigned to anyone
URL:
Keywords:
Depends on: 40019
Blocks: 39627
  Show dependency treegraph
 
Reported: 2008-11-27 00:43 UTC by Walter Spector
Modified: 2011-11-09 09:58 UTC (History)
3 users (show)

See Also:
Host:
Target:
Build:
Known to work:
Known to fail:
Last reconfirmed: 2010-08-29 17:41:11


Attachments

Note You need to log in before you can comment on or make changes to this bug.
Description Walter Spector 2008-11-27 00:43:03 UTC
In 4.4, the LEADZ and TRAILZ intrinsics were added.  LEADZ is one of the HPF intrinsics.  However the other HPF bit intrinsics, POPCNT and POPPAR, were not included.

POPCNT and POPPAR are present in many other compilers, and have usually been implemented along with LEADZ.  This is because historically, POPCNT, POPPAR, and LEADZ were present in the Cray compilers to allow access to hardware instructions.  So it is a little strange to see LEADZ without the others.

Both POPCNT and POPPAR are also present in the F2008 draft.
Comment 1 Tobias Burnus 2008-11-27 11:14:12 UTC
(In reply to comment #0)
> POPCNT and POPPAR are present in many other compilers

And (even) more interestingly they are part of the Fortran 2008 Candidate Release (as you also mentioned):

  13.7.128 POPCNT (I)
  Description. Number of one bits.
  Class. Elemental function.
  Argument. I shall be of type integer.
  Result Characteristics. Default integer.
  Result Value. The result value is equal to the number of one bits in the 
    sequence of bits of I. The model for the interpretation of an integer value
    as a sequence of bits is in 13.3.

  13.7.129 POPPAR (I)
  Description. Parity expressed as 0 or 1.
  Class. Elemental function.
  Argument. I shall be of type integer.
  Result Characteristics. Default integer.
  Result Value. POPPAR (I) has the value 1 if POPCNT (I) is odd, and 0 if
    POPCNT (I) is even.

 * * *

For completeness:

Fortran 2008 and also the HPF standard also list the following "Array Reduction Functions" (HPF):

- IALL - Bitwise AND of all the elements of ARRAY along dimension DIM
         corresponding to the true elements of the mask
- IANY - Bitwise OR of all the elements of ARRAY along dimension DIM 
         corresponding to the true elements of MASK.
- IPARITY - Bitwise exclusive OR of all the elements of ARRAY along dimension
         DIM corresponding to the true elements of MASK.
- PARITY - True if and only if an odd number of values are true in MASK
         along dimension DIM.

And Fortran 2008 also the following elemental procedures for bits:
- DSHIFTL(I,J,SHIFT) - Combined left shift
- DSHIFTR(I,J,SHIFT) - Combined right shift
- SHIFTA - Right shift with fill.
- SHIFTL - Left shift
- SHIFTR - Right shift
- MASKL  Left justified mask
- MASKR - Right justified mask
- BGE - True if and only if I is bitwise greater than or equal to J
- BGT - True if and only if I is bitwise greater than J.
- BLE - True if and only if I is bitwise less than or equal to J
- BLT - True if and only if I is bitwise less than J.
- MERGE_BITS - Merge of bits under mask
Comment 2 Walter Spector 2008-11-27 19:32:00 UTC
Tobias, Steven,

If you would like to usurp this request and use it to implement the complete set
of F2008 bit intrinsics, please feel free to do so.

For completeness, one other HPF bit intrinsic is ILEN - which counts the
number of bits needed to represent an integer.  This is not in the F2008
draft, but is occasionally useful.

A few comments on the draft F2008 intrinsics:

DSHIFTL/DSHIFTR - Cray-1 intrinsics.  Occasionally handy.  Represented the
hardware vector "snake" instruction.
SHIFTA - Lots of systems have this instruction in hardware, but not the Cray-1.
So it went into the Cray compilers somewhat later.
SHIFTL/SHIFTR - Cray-1 intrinsics.  Better than ISHFT because the compiler
always knows which shift instruction to generate.
MASKL/MASKR - Shades of the MASK intrinsic on 60-bit CDC systems, which
represented a hardware instruction.
MERGE_BITS - On the Cray-1, it was called CSMG.  Hardware instruction.

One final instrinsic: IBCHNG.  This was part of the old "Industrial Real-Time
Fortran" Standard.  IBCHNG allows the caller to 'flip' a specific bit to its
complement.  The IRTF bit intrinsics were the basis for the Milspec-1753 bit
intrinsics, and then F90.  But somehow IBCHNG got lost along the way.
Nonetheless, a number of compilers (ifort, cray, sun, sgi, probably ibm, etc)
also implement IBCHNG.

(We could talk about the IRTF ISHL (logical shift), ISHA (arithmetic shift),
and ISHC (circular shift) which are also implemented in some compilers.  But
since the F90 ISHFT and ISHFTC, and F2008 SHIFTA cover these cases in a
Standard-conforming way, I would not recommend implementing them in gfortran.)
Comment 3 Francois-Xavier Coudert 2009-05-04 19:37:43 UTC
About POPCNT and POPPAR, beware! Implementations are much harder than simply using the GCC __builtin_popcount{,l,ll}: see PR40019 for similar issue with LEADZ and TRAILZ.
Comment 4 Steven Bosscher 2010-02-12 21:37:00 UTC
I'm not working on this => unassign.
Comment 5 Tobias Burnus 2010-08-25 14:26:45 UTC
(In reply to comment #3)
> About POPCNT and POPPAR, beware! Implementations are much harder than simply
> using the GCC __builtin_popcount{,l,ll}

Well, the difference is that one should be able to easily handle 128 bit values at TREE level using
  __builtin_popcount ((unsigned long) X) + __builtin_popcount((unsigned long) X << 64)
and
  __builtin_parity ((unsigned long) X) != __builtin_parity ((unsigned long) X << 64)

The proper solution is too add them as new builtins to gcc/libgcc2.{c,h}; cf. libgcc/Makefile.in - and update the docs.

At the same time, one could move CTZ/CLZ also to libgcc2.c, cf.
 http://gcc.gnu.org/viewcvs/trunk/libgfortran/intrinsics/bit_intrinsics.c?view=markup
Comment 6 Francois-Xavier Coudert 2010-08-29 17:41:11 UTC
I did LEADZ and TRAILZ, I guess I should do these. Assigning to me.
Comment 7 Tobias Burnus 2010-08-30 05:57:30 UTC
(In reply to comment #6)
> I did LEADZ and TRAILZ, I guess I should do these. Assigning to me.

Do you plan to do it via libgcc/Makefile.in + gcc/libgcc2.c - and then use the ME builtin?

Comment 8 Francois-Xavier Coudert 2010-08-30 08:27:33 UTC
(In reply to comment #7)
> Do you plan to do it via libgcc/Makefile.in + gcc/libgcc2.c - and then use the
> ME builtin?

That could be fun to try :)
Comment 9 Francois-Xavier Coudert 2010-08-31 11:26:18 UTC
Patch submitted at http://gcc.gnu.org/ml/fortran/2010-08/msg00476.html
Comment 10 Francois-Xavier Coudert 2010-08-31 18:57:01 UTC
Subject: Bug 38282

Author: fxcoudert
Date: Tue Aug 31 18:56:46 2010
New Revision: 163691

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=163691
Log:
	PR fortran/38282

	* f95-lang.c (gfc_init_builtin_functions): Define popcount{,l,ll}
	and parity{,l,ll} builtins.
	* trans-intrinsic.c (gfc_conv_intrinsic_popcnt_poppar): New function.
	(gfc_conv_intrinsic_function): Call above new functions.
	* simplify.c (gfc_simplify_popcnt, gfc_simplify_poppar): New
	functions.
	* intrinsic.texi: Document POPCNT and POPPAR.

	* gfortran.dg/popcnt_poppar_1.F90: New test.
	* gfortran.dg/popcnt_poppar_2.F90: New test.

Added:
    trunk/gcc/testsuite/gfortran.dg/popcnt_poppar_1.F90
    trunk/gcc/testsuite/gfortran.dg/popcnt_poppar_2.F90
Modified:
    trunk/gcc/fortran/ChangeLog
    trunk/gcc/fortran/f95-lang.c
    trunk/gcc/fortran/gfortran.h
    trunk/gcc/fortran/intrinsic.c
    trunk/gcc/fortran/intrinsic.h
    trunk/gcc/fortran/intrinsic.texi
    trunk/gcc/fortran/simplify.c
    trunk/gcc/fortran/trans-intrinsic.c
    trunk/gcc/testsuite/ChangeLog

Comment 11 Tobias Burnus 2010-09-06 05:55:27 UTC
Subject: Bug 38282

Author: burnus
Date: Mon Sep  6 05:55:10 2010
New Revision: 163898

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=163898
Log:
2010-09-06  Tobias Burnus  <burnus@net-b.de>

        PR fortran/38282
        * intrinsic.c (add_functions): Support IALL, IANY, IPARITY.
        (check_specific): Special case for those intrinsics.
        * gfortran.h (gfc_isym_id): Add new intrinsics
        * intrinsic.h (gfc_check_transf_bit_intrins,
        gfc_simplify_iall, gfc_simplify_iany, gfc_simplify_iparity,
        gfc_resolve_iall, gfc_resolve_iany, gfc_resolve_iparity):
        New prototypes.
        * iresolve.c (gfc_resolve_iall, gfc_resolve_iany,
        gfc_resolve_iparity, resolve_transformational): New functions.
        (gfc_resolve_product, gfc_resolve_sum,
        gfc_resolve_parity): Use resolve_transformational.
        * check.c (gfc_check_transf_bit_intrins): New function.
        * simplify.c (gfc_simplify_iall, gfc_simplify_iany,
        gfc_simplify_iparity, do_bit_any, do_bit_ior,
        do_bit_xor, simplify_transformation): New functions.
        (gfc_simplify_all, gfc_simplify_any, gfc_simplify_parity,
        gfc_simplify_sum, gfc_simplify_product): Use simplify_transformation.
        * trans-intrinsic.c (gfc_conv_intrinsic_arith,
        gfc_conv_intrinsic_function, gfc_is_intrinsic_libcall):
        Handle IALL, IANY and IPARITY intrinsics.       
        * intrinsic.texi (IMAGE_INDEX): Move up to fix alphabetic
        order.
        (IALL, IANY, IPARITY): Document new intrinsics.

2010-09-06  Tobias Burnus  <burnus@net-b.de>

        PR fortran/38282
        * gfortran.dg/iall_iany_iparity_1.f90: New.
        * gfortran.dg/iall_iany_iparity_2.f90: New.

2010-09-06  Tobias Burnus  <burnus@net-b.de>

        PR fortran/38282
        * gfortran.map: Add new iany, iall and iparity intrinsics.
        * Makefile.am: Ditto.
        * m4/iany.m4: New.
        * m4/iall.m4: New.
        * m4/iparity.m4: New.
        * Makefile.in: Regenerate.
        * generated/iall_i1.c: Generate.
        * generated/iall_i2.c: Generate.
        * generated/iall_i4.c: Generate.
        * generated/iall_i8.c: Generate.
        * generated/iall_i16.c: Generate.
        * generated/iany_i1.c: Generate.
        * generated/iany_i2.c: Generate.
        * generated/iany_i4.c: Generate.
        * generated/iany_i8.c: Generate.
        * generated/iany_i16.c: Generate.
        * generated/iparity_i1.c: Generate.
        * generated/iparity_i2.c: Generate.
        * generated/iparity_i4.c: Generate.
        * generated/iparity_i8.c: Generate.
        * generated/iparity_i16.c: Generate.


Added:
    trunk/gcc/testsuite/gfortran.dg/iall_iany_iparity_1.f90
    trunk/gcc/testsuite/gfortran.dg/iall_iany_iparity_2.f90
    trunk/libgfortran/generated/iall_i1.c
    trunk/libgfortran/generated/iall_i16.c
    trunk/libgfortran/generated/iall_i2.c
    trunk/libgfortran/generated/iall_i4.c
    trunk/libgfortran/generated/iall_i8.c
    trunk/libgfortran/generated/iany_i1.c
    trunk/libgfortran/generated/iany_i16.c
    trunk/libgfortran/generated/iany_i2.c
    trunk/libgfortran/generated/iany_i4.c
    trunk/libgfortran/generated/iany_i8.c
    trunk/libgfortran/generated/iparity_i1.c
    trunk/libgfortran/generated/iparity_i16.c
    trunk/libgfortran/generated/iparity_i2.c
    trunk/libgfortran/generated/iparity_i4.c
    trunk/libgfortran/generated/iparity_i8.c
    trunk/libgfortran/m4/iall.m4
    trunk/libgfortran/m4/iany.m4
    trunk/libgfortran/m4/iparity.m4
Modified:
    trunk/gcc/fortran/ChangeLog
    trunk/gcc/fortran/check.c
    trunk/gcc/fortran/gfortran.h
    trunk/gcc/fortran/intrinsic.c
    trunk/gcc/fortran/intrinsic.h
    trunk/gcc/fortran/intrinsic.texi
    trunk/gcc/fortran/iresolve.c
    trunk/gcc/fortran/simplify.c
    trunk/gcc/fortran/trans-intrinsic.c
    trunk/gcc/testsuite/ChangeLog
    trunk/libgfortran/ChangeLog
    trunk/libgfortran/Makefile.am
    trunk/libgfortran/Makefile.in
    trunk/libgfortran/gfortran.map

Comment 12 Tobias Burnus 2010-09-06 13:35:08 UTC
DONE:
- POPPAR, POPCNT [and LEADZ/TAILZ already in GCC 4.4]
- IALL, IANY, IPARITY

TODO (cf. comment 2)

a) F2008's bit intrinsics: DSHIFTL, DSHIFTR, SHIFTA, SHIFTL, SHIFTR, MASKL, MASKR, BGE, BGT, BLE, BLT, MERGE_BITS

c) HPF only: ILEN(I)
   Cf. http://wotug.org/parallel/standards/hpf/, HPF 2.0, Section 7.6

d) IBCHNG(POS, I)
   Industrial Real-Time Fortran Standard (ISO 7846:1985; withdrawn) and common
   vendor extension
Comment 13 Francois-Xavier Coudert 2010-09-08 19:35:56 UTC
Subject: Bug 38282

Author: fxcoudert
Date: Wed Sep  8 19:35:35 2010
New Revision: 164021

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=164021
Log:
	PR fortran/38282

	* intrinsic.c (add_functions): Add B{G,L}{E,T}, DSHIFT{L,R},
	MASK{L,R}, MERGE_BITS and SHIFT{A,L,R}.
	* gfortran.h: Define ISYM values for above intrinsics.
	* intrinsic.h (gfc_check_bge_bgt_ble_blt, gfc_check_dshift,
	gfc_check_mask, gfc_check_merge_bits, gfc_check_shift,
	gfc_simplify_bge, gfc_simplify_bgt, gfc_simplify_ble,
	gfc_simplify_blt, gfc_simplify_dshiftl, gfc_simplify_dshiftr,
	gfc_simplify_lshift, gfc_simplify_maskl, gfc_simplify_maskr,
	gfc_simplify_merge_bits, gfc_simplify_rshift,
	gfc_simplify_shifta, gfc_simplify_shiftl, gfc_simplify_shiftr,
	gfc_resolve_dshift, gfc_resolve_mask, gfc_resolve_merge_bits,
	gfc_resolve_shift): New prototypes.
	* iresolve.c (gfc_resolve_dshift, gfc_resolve_mask,
	gfc_resolve_merge_bits, gfc_resolve_shift): New functions.
	* check.c (gfc_check_bge_bgt_ble_blt, gfc_check_dshift,
	gfc_check_mask, gfc_check_merge_bits, gfc_check_shift): New
	functions.
	* trans-intrinsic.c (gfc_conv_intrinsic_dshift,
	gfc_conv_intrinsic_bitcomp, gfc_conv_intrinsic_shift,
	gfc_conv_intrinsic_merge_bits, gfc_conv_intrinsic_mask): New
	functions.
	(gfc_conv_intrinsic_function): Call above static functions.
	* intrinsic.texi: Document new intrinsics.
	* simplify.c (gfc_simplify_bge, gfc_simplify_bgt, gfc_simplify_ble,
        gfc_simplify_blt, gfc_simplify_dshiftl, gfc_simplify_dshiftr,
        gfc_simplify_lshift, gfc_simplify_maskl, gfc_simplify_maskr,
        gfc_simplify_merge_bits, gfc_simplify_rshift, 
        gfc_simplify_shifta, gfc_simplify_shiftl, gfc_simplify_shiftr):
	New functions.

	* gfortran.dg/bit_comparison_1.F90: New test.
	* gfortran.dg/leadz_trailz_3.f90: New test.
	* gfortran.dg/masklr_2.F90: New test.
	* gfortran.dg/shiftalr_1.F90: New test.
	* gfortran.dg/merge_bits_2.F90: New test.
	* gfortran.dg/dshift_2.F90: New test.
	* gfortran.dg/bit_comparison_2.F90: New test.
	* gfortran.dg/masklr_1.F90: New test.
	* gfortran.dg/merge_bits_1.F90: New test.
	* gfortran.dg/dshift_1.F90: New test.
	* gfortran.dg/shiftalr_2.F90: New test.

Added:
    trunk/gcc/testsuite/gfortran.dg/bit_comparison_1.F90
    trunk/gcc/testsuite/gfortran.dg/bit_comparison_2.F90
    trunk/gcc/testsuite/gfortran.dg/dshift_1.F90
    trunk/gcc/testsuite/gfortran.dg/dshift_2.F90
    trunk/gcc/testsuite/gfortran.dg/leadz_trailz_3.f90
    trunk/gcc/testsuite/gfortran.dg/masklr_1.F90
    trunk/gcc/testsuite/gfortran.dg/masklr_2.F90
    trunk/gcc/testsuite/gfortran.dg/merge_bits_1.F90
    trunk/gcc/testsuite/gfortran.dg/merge_bits_2.F90
    trunk/gcc/testsuite/gfortran.dg/shiftalr_1.F90
    trunk/gcc/testsuite/gfortran.dg/shiftalr_2.F90
Modified:
    trunk/gcc/fortran/ChangeLog
    trunk/gcc/fortran/check.c
    trunk/gcc/fortran/gfortran.h
    trunk/gcc/fortran/intrinsic.c
    trunk/gcc/fortran/intrinsic.h
    trunk/gcc/fortran/intrinsic.texi
    trunk/gcc/fortran/iresolve.c
    trunk/gcc/fortran/simplify.c
    trunk/gcc/fortran/trans-intrinsic.c
    trunk/gcc/testsuite/ChangeLog

Comment 14 Francois-Xavier Coudert 2010-09-08 19:52:09 UTC
Possible remaining are only old extensions, not sure they're useful: ILEN and IBCHNG.

Closing?
Comment 15 Walter Spector 2010-09-08 21:32:21 UTC
Subject: Re:  Bit intrinsics: ILEN and IBCHNG

FX wrote:
>------- Comment #14 from fxcoudert at gcc dot gnu dot org  2010-09-08 19:52 -------
>Possible remaining are only old extensions, not sure they're useful: ILEN and
>IBCHNG.
>
>Closing?

It is easy to write ones own IBCHNG.  So at this point, especially given
its rarity in actual codes, it is probably not worth implementing.

ILEN is pretty easy to write too.  If there is ever a move to implement
more of HPFs intrinsics, you could add it then.  (Speaking of which, I
think some kind of intrinsic sorting/grading routines, like maybe
simplified 1-D versions of HPFs SORT_{UP,DOWN} and GRADE_{UP,DOWN}
functions would be incredibly useful to a lot of programmers.  But that
is something which should be covered under a different ticket.)



Comment 16 Francois-Xavier Coudert 2011-11-09 09:58:52 UTC
Fixed on 4.6 branch a while back.