2 * Copyright (C) 1995-2007 University of Karlsruhe. All right reserved.
4 * This file is part of libFirm.
6 * This file may be distributed and/or modified under the terms of the
7 * GNU General Public License version 2 as published by the Free Software
8 * Foundation and appearing in the file LICENSE.GPL included in the
9 * packaging of this file.
11 * Licensees holding valid libFirm Professional Edition licenses may use
12 * this file in accordance with the libFirm Commercial License.
13 * Agreement provided with the Software.
15 * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
16 * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
22 * @brief intel 80x86 implementation of bitsets
25 #ifndef _BITSET_IA32_H
26 #define _BITSET_IA32_H
28 typedef unsigned int bitset_unit_t;
29 #define BITSET_UNIT_FMT "%0x"
31 #undef _bitset_inside_clear
32 #undef _bitset_inside_set
33 #undef _bitset_inside_flip
34 #undef _bitset_inside_is_set
36 #undef _bitset_inside_nlz
37 #undef _bitset_inside_ntz
38 #undef _bitset_inside_ntz_value
40 #define _bitset_inside_set(unit,bit) \
41 __asm__( "btsl %1,%0" :"=m" (unit) :"Ir" (bit))
43 #define _bitset_inside_clear(unit,bit) \
44 __asm__( "btrl %1,%0" :"=m" (unit) :"Ir" (bit))
46 #define _bitset_inside_flip(unit,bit) \
47 __asm__( "btcl %1,%0" :"=m" (unit) :"Ir" (bit))
49 #define _bitset_inside_is_set(unit,bit) _bitset_ia32_inside_is_set(unit, bit)
50 #define _bitset_inside_nlz(unit) _bitset_ia32_inside_nlz(unit)
51 #define _bitset_inside_ntz(unit) _bitset_ia32_inside_ntz(unit)
52 #define _bitset_inside_ntz_value(unit) _bitset_ia32_inside_ntz_value(unit)
54 static INLINE int _bitset_ia32_inside_is_set(bitset_unit_t *unit, unsigned bit)
57 __asm__("mov $0,%0\n\tbtl %1,%2\n\tadc $0,%0"
59 : "Ir" (bit), "m" (unit)
64 static INLINE unsigned _bitset_ia32_inside_nlz(bitset_unit_t *unit)
67 __asm__("bsrl %1,%0" :"=r" (res) :"m" (unit));
68 return *unit == 0 ? 32 : res;
71 static INLINE unsigned _bitset_ia32_inside_ntz(bitset_unit_t *unit) {
73 __asm__("bsfl %1,%0" :"=r" (res) :"m" (unit));
74 return *unit == 0 ? 32 : res;
77 static INLINE unsigned _bitset_ia32_inside_ntz_value(bitset_unit_t unit) {
79 __asm__("bsfl %1,%0" :"=r" (res) :"rm" (unit));
80 return unit == 0 ? 32 : res;
83 #if defined(__GNUC__) && defined(__SSE2__)
86 #include <xmmintrin.h>
89 #undef _bitset_overall_size
90 #undef _bitset_data_ptr
92 #undef _BITSET_BINOP_UNITS_INC
94 #undef _bitset_inside_binop_and
95 #undef _bitset_inside_binop_andnot
96 #undef _bitset_inside_binop_or
97 #undef _bitset_inside_binop_xor
99 #undef _bitset_inside_binop_with_zero_and
100 #undef _bitset_inside_binop_with_zero_andnot
101 #undef _bitset_inside_binop_with_zero_or
102 #undef _bitset_inside_binop_with_zero_xor
104 #define _bitset_units(highest_bit) (round_up2(highest_bit, 128) / BS_UNIT_SIZE_BITS)
106 #define _bitset_overall_size(bitset_base_size,highest_bit) \
107 ((bitset_base_size) + 16 + _bitset_units(highest_bit) * BS_UNIT_SIZE)
109 #define _bitset_data_ptr(data,bitset_base_size,highest_bit) \
110 _bitset_sse_data_ptr(data, bitset_base_size, highest_bit)
112 static INLINE bitset_unit_t *_bitset_sse_data_ptr(void *data, size_t bitset_base_size,
113 bitset_pos_t highest_bit)
118 diff = (units - (char *) 0) + bitset_base_size;
119 diff = round_up2(diff, 16);
120 units = (char *) 0 + diff;
121 return (bitset_unit_t *) units;
124 #define _BITSET_BINOP_UNITS_INC 4
125 #define _bitset_inside_binop_and(tgt,src) _bitset_sse_inside_binop_and(tgt,src)
126 #define _bitset_inside_binop_andnot(tgt,src) _bitset_sse_inside_binop_andnot(tgt,src)
127 #define _bitset_inside_binop_or(tgt,src) _bitset_sse_inside_binop_or(tgt,src)
128 #define _bitset_inside_binop_xor(tgt,src) _bitset_sse_inside_binop_xor(tgt,src)
130 #define _BITSET_SSE_BINOP(name) \
131 static INLINE void _bitset_sse_inside_binop_ ## name(bitset_unit_t *tgt, bitset_unit_t *src) \
133 __m128i src_op = _mm_load_si128((__m128i *) src); \
134 __m128i tgt_op = _mm_load_si128((__m128i *) tgt); \
135 __m128i res = _mm_ ## name ## _si128(tgt_op, src_op); \
136 _mm_store_si128((void *) tgt, res); \
140 static INLINE void _bitset_sse_inside_binop_with_zero_and(bitset_unit_t *tgt)
148 static INLINE void _bitset_sse_inside_binop_andnot(bitset_unit_t *tgt, bitset_unit_t *src)
150 __m128i src_op = _mm_load_si128((void *) src);
151 __m128i tgt_op = _mm_load_si128((void *) tgt);
152 __m128i res = _mm_andnot_si128(src_op, tgt_op);
153 _mm_store_si128((__m128i *) tgt, res);
156 _BITSET_SSE_BINOP(and)
157 _BITSET_SSE_BINOP(or)
158 _BITSET_SSE_BINOP(xor)