nsz Git - libfirm/blob - ir/adt/bitset_ia32.h

   1 /*
   2  * Copyright (C) 1995-2007 University of Karlsruhe.  All right reserved.
   3  *
   4  * This file is part of libFirm.
   5  *
   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.
  10  *
  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.
  14  *
  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
  17  * PURPOSE.
  18  */
  19
  20 /**
  21  * @file
  22  * @brief    intel 80x86 implementation of bitsets
  23  * @version  $Id$
  24  */
  25 #ifndef _BITSET_IA32_H
  26 #define _BITSET_IA32_H
  27
  28 typedef unsigned int bitset_unit_t;
  29 #define BITSET_UNIT_FMT "%0x"
  30
  31 #undef _bitset_inside_clear
  32 #undef _bitset_inside_set
  33 #undef _bitset_inside_flip
  34 #undef _bitset_inside_is_set
  35
  36 #undef _bitset_inside_nlz
  37 #undef _bitset_inside_ntz
  38 #undef _bitset_inside_ntz_value
  39
  40 #define _bitset_inside_set(unit,bit) \
  41         __asm__( "btsl %1,%0" :"=m" (unit) :"Ir" (bit))
  42
  43 #define _bitset_inside_clear(unit,bit) \
  44         __asm__( "btrl %1,%0" :"=m" (unit) :"Ir" (bit))
  45
  46 #define _bitset_inside_flip(unit,bit) \
  47         __asm__( "btcl %1,%0" :"=m" (unit) :"Ir" (bit))
  48
  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)
  53
  54 static INLINE int _bitset_ia32_inside_is_set(bitset_unit_t *unit, unsigned bit)
  55 {
  56         int res = 0;
  57         __asm__("mov $0,%0\n\tbtl %1,%2\n\tadc $0,%0"
  58                         : "=r" (res)
  59                         : "Ir" (bit), "m" (unit)
  60                         : "cc");
  61         return res;
  62 }
  63
  64 static INLINE unsigned _bitset_ia32_inside_nlz(bitset_unit_t *unit)
  65 {
  66         unsigned res = 0;
  67         __asm__("bsrl %1,%0" :"=r" (res) :"m" (unit));
  68         return *unit == 0 ? 32 : res;
  69 }
  70
  71 static INLINE unsigned _bitset_ia32_inside_ntz(bitset_unit_t *unit) {
  72         unsigned res = 0;
  73         __asm__("bsfl %1,%0" :"=r" (res) :"m" (unit));
  74         return *unit == 0 ? 32 : res;
  75 }
  76
  77 static INLINE unsigned _bitset_ia32_inside_ntz_value(bitset_unit_t unit) {
  78         unsigned res = 0;
  79         __asm__("bsfl %1,%0" :"=r" (res) :"rm" (unit));
  80         return unit == 0 ? 32 : res;
  81 }
  82
  83 #if defined(__GNUC__) && defined(__SSE2__)
  84
  85 #include <stddef.h>
  86 #include <xmmintrin.h>
  87
  88 #undef _bitset_units
  89 #undef _bitset_overall_size
  90 #undef _bitset_data_ptr
  91
  92 #undef _BITSET_BINOP_UNITS_INC
  93
  94 #undef _bitset_inside_binop_and
  95 #undef _bitset_inside_binop_andnot
  96 #undef _bitset_inside_binop_or
  97 #undef _bitset_inside_binop_xor
  98
  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
 103
 104 #define _bitset_units(highest_bit) (round_up2(highest_bit, 128) / BS_UNIT_SIZE_BITS)
 105
 106 #define _bitset_overall_size(bitset_base_size,highest_bit) \
 107         ((bitset_base_size) + 16 + _bitset_units(highest_bit) * BS_UNIT_SIZE)
 108
 109 #define _bitset_data_ptr(data,bitset_base_size,highest_bit) \
 110   _bitset_sse_data_ptr(data, bitset_base_size, highest_bit)
 111
 112 static INLINE bitset_unit_t *_bitset_sse_data_ptr(void *data, size_t bitset_base_size,
 113                 bitset_pos_t highest_bit)
 114 {
 115         ptrdiff_t diff;
 116         char *units = data;
 117
 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;
 122 }
 123
 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)
 129
 130 #define _BITSET_SSE_BINOP(name) \
 131 static INLINE void _bitset_sse_inside_binop_ ## name(bitset_unit_t *tgt, bitset_unit_t *src) \
 132 { \
 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); \
 137 }
 138
 139
 140 static INLINE void _bitset_sse_inside_binop_with_zero_and(bitset_unit_t *tgt)
 141 {
 142         tgt[0] = 0;
 143         tgt[1] = 0;
 144         tgt[2] = 0;
 145         tgt[3] = 0;
 146 }
 147
 148 static INLINE void _bitset_sse_inside_binop_andnot(bitset_unit_t *tgt, bitset_unit_t *src)
 149 {
 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);
 154 }
 155
 156 _BITSET_SSE_BINOP(and)
 157 _BITSET_SSE_BINOP(or)
 158 _BITSET_SSE_BINOP(xor)
 159
 160
 161 #endif
 162 #endif