1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
|
/* { dg-additional-options "-O3" } */
/* { dg-additional-options "-march=skylake-avx512" { target avx512f } } */
#include "tree-vect.h"
#include<stdbool.h>
#include<stdlib.h>
#include<stddef.h>
#include<string.h>
#define SBITMAP_ELT_BITS ((unsigned) 64)
#define SBITMAP_ELT_TYPE unsigned long long
#define SBITMAP_SIZE_BYTES(BITMAP) ((BITMAP)->size * sizeof (SBITMAP_ELT_TYPE))
#define do_popcount(x) __builtin_popcountll(x)
typedef struct simple_bitmap_def
{
unsigned char *popcount; /* Population count. */
unsigned int n_bits; /* Number of bits. */
unsigned int size; /* Size in elements. */
SBITMAP_ELT_TYPE elms[1]; /* The elements. */
} *sbitmap;
typedef const struct simple_bitmap_def *const_sbitmap;
/* The iterator for sbitmap. */
typedef struct {
/* The pointer to the first word of the bitmap. */
const SBITMAP_ELT_TYPE *ptr;
/* The size of the bitmap. */
unsigned int size;
/* The current word index. */
unsigned int word_num;
/* The current bit index (not modulo SBITMAP_ELT_BITS). */
unsigned int bit_num;
/* The words currently visited. */
SBITMAP_ELT_TYPE word;
} sbitmap_iterator;
static inline void
sbitmap_iter_init (sbitmap_iterator *i, const_sbitmap bmp, unsigned int min)
{
i->word_num = min / (unsigned int) SBITMAP_ELT_BITS;
i->bit_num = min;
i->size = bmp->size;
i->ptr = bmp->elms;
if (i->word_num >= i->size)
i->word = 0;
else
i->word = (i->ptr[i->word_num]
>> (i->bit_num % (unsigned int) SBITMAP_ELT_BITS));
}
/* Return true if we have more bits to visit, in which case *N is set
to the index of the bit to be visited. Otherwise, return
false. */
static inline bool
sbitmap_iter_cond (sbitmap_iterator *i, unsigned int *n)
{
/* Skip words that are zeros. */
for (; i->word == 0; i->word = i->ptr[i->word_num])
{
i->word_num++;
/* If we have reached the end, break. */
if (i->word_num >= i->size)
return false;
i->bit_num = i->word_num * SBITMAP_ELT_BITS;
}
/* Skip bits that are zero. */
for (; (i->word & 1) == 0; i->word >>= 1)
i->bit_num++;
*n = i->bit_num;
return true;
}
/* Advance to the next bit. */
static inline void
sbitmap_iter_next (sbitmap_iterator *i)
{
i->word >>= 1;
i->bit_num++;
}
#define SBITMAP_SET_SIZE(N) (((N) + SBITMAP_ELT_BITS - 1) / SBITMAP_ELT_BITS)
/* Allocate a simple bitmap of N_ELMS bits. */
sbitmap
sbitmap_alloc (unsigned int n_elms)
{
unsigned int bytes, size, amt;
sbitmap bmap;
size = SBITMAP_SET_SIZE (n_elms);
bytes = size * sizeof (SBITMAP_ELT_TYPE);
amt = (sizeof (struct simple_bitmap_def)
+ bytes - sizeof (SBITMAP_ELT_TYPE));
bmap = (sbitmap) malloc (amt);
bmap->n_bits = n_elms;
bmap->size = size;
bmap->popcount = NULL;
return bmap;
}
#define sbitmap_free(MAP) (free((MAP)->popcount), free((MAP)))
/* Loop over all elements of SBITMAP, starting with MIN. In each
iteration, N is set to the index of the bit being visited. ITER is
an instance of sbitmap_iterator used to iterate the bitmap. */
#define EXECUTE_IF_SET_IN_SBITMAP(SBITMAP, MIN, N, ITER) \
for (sbitmap_iter_init (&(ITER), (SBITMAP), (MIN)); \
sbitmap_iter_cond (&(ITER), &(N)); \
sbitmap_iter_next (&(ITER)))
int
__attribute__((noinline))
sbitmap_first_set_bit (const_sbitmap bmap)
{
unsigned int n = 0;
sbitmap_iterator sbi;
EXECUTE_IF_SET_IN_SBITMAP (bmap, 0, n, sbi)
return n;
return -1;
}
void
sbitmap_zero (sbitmap bmap)
{
memset (bmap->elms, 0, SBITMAP_SIZE_BYTES (bmap));
if (bmap->popcount)
memset (bmap->popcount, 0, bmap->size * sizeof (unsigned char));
}
int main ()
{
check_vect ();
sbitmap tmp = sbitmap_alloc(1856);
sbitmap_zero (tmp);
int res = sbitmap_first_set_bit (tmp);
if (res != -1)
abort ();
sbitmap_free (tmp);
return 0;
}
|
