Bug Summary

File:build/source/polly/lib/External/isl/isl_hash.c
Warning:line 167, column 11
The result of the left shift is undefined due to shifting by '32', which is greater or equal to the width of type 'int'

Annotated Source Code

Press '?' to see keyboard shortcuts

clang -cc1 -cc1 -triple x86_64-pc-linux-gnu -analyze -disable-free -clear-ast-before-backend -disable-llvm-verifier -discard-value-names -main-file-name isl_hash.c -analyzer-checker=core -analyzer-checker=apiModeling -analyzer-checker=unix -analyzer-checker=deadcode -analyzer-checker=security.insecureAPI.UncheckedReturn -analyzer-checker=security.insecureAPI.getpw -analyzer-checker=security.insecureAPI.gets -analyzer-checker=security.insecureAPI.mktemp -analyzer-checker=security.insecureAPI.mkstemp -analyzer-checker=security.insecureAPI.vfork -analyzer-checker=nullability.NullPassedToNonnull -analyzer-checker=nullability.NullReturnedFromNonnull -analyzer-output plist -w -setup-static-analyzer -analyzer-config-compatibility-mode=true -mrelocation-model pic -pic-level 2 -mframe-pointer=none -fmath-errno -ffp-contract=on -fno-rounding-math -mconstructor-aliases -funwind-tables=2 -target-cpu x86-64 -tune-cpu generic -debugger-tuning=gdb -ffunction-sections -fdata-sections -fcoverage-compilation-dir=/build/source/build-llvm -resource-dir /usr/lib/llvm-17/lib/clang/17 -I tools/polly/lib/External -I /build/source/polly/lib/External -I /build/source/polly/lib/External/isl -I /build/source/polly/lib/External/isl/include -I /build/source/polly/lib/External/isl/imath -I tools/polly/lib/External/isl -I tools/polly/include -I /build/source/polly/lib/External/pet/include -I tools/polly/lib/External/isl/include -I /build/source/polly/include -I include -I /build/source/llvm/include -D _DEBUG -D _GLIBCXX_ASSERTIONS -D _GNU_SOURCE -D _LIBCPP_ENABLE_ASSERTIONS -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -D _FORTIFY_SOURCE=2 -D NDEBUG -U NDEBUG -internal-isystem /usr/lib/llvm-17/lib/clang/17/include -internal-isystem /usr/local/include -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../x86_64-linux-gnu/include -internal-externc-isystem /usr/include/x86_64-linux-gnu -internal-externc-isystem /include -internal-externc-isystem /usr/include -fmacro-prefix-map=/build/source/build-llvm=build-llvm -fmacro-prefix-map=/build/source/= -fcoverage-prefix-map=/build/source/build-llvm=build-llvm -fcoverage-prefix-map=/build/source/= -O3 -Wno-unused-command-line-argument -Wno-unused-parameter -Wwrite-strings -Wno-missing-field-initializers -Wno-long-long -Wno-comment -std=gnu99 -fconst-strings -fdebug-compilation-dir=/build/source/build-llvm -fdebug-prefix-map=/build/source/build-llvm=build-llvm -fdebug-prefix-map=/build/source/= -fdebug-prefix-map=/build/source/build-llvm=build-llvm -fdebug-prefix-map=/build/source/= -ferror-limit 19 -stack-protector 2 -fgnuc-version=4.2.1 -fcolor-diagnostics -vectorize-loops -vectorize-slp -analyzer-output=html -analyzer-config stable-report-filename=true -faddrsig -D__GCC_HAVE_DWARF2_CFI_ASM=1 -o /tmp/scan-build-2023-07-19-143856-16066-1 -x c /build/source/polly/lib/External/isl/isl_hash.c
1/*
2 * Copyright 2008-2009 Katholieke Universiteit Leuven
3 *
4 * Use of this software is governed by the MIT license
5 *
6 * Written by Sven Verdoolaege, K.U.Leuven, Departement
7 * Computerwetenschappen, Celestijnenlaan 200A, B-3001 Leuven, Belgium
8 */
9
10#include <stdlib.h>
11#include <isl_hash_private.h>
12#include <isl/ctx.h>
13#include "isl_config.h"
14
15uint32_t isl_hash_string(uint32_t hash, const char *s)
16{
17 for (; *s; s++)
18 isl_hash_byte(hash, *s)do { hash *= 16777619; hash ^= *s; } while(0);
19 return hash;
20}
21
22uint32_t isl_hash_mem(uint32_t hash, const void *p, size_t len)
23{
24 int i;
25 const char *s = p;
26 for (i = 0; i < len; ++i)
27 isl_hash_byte(hash, s[i])do { hash *= 16777619; hash ^= s[i]; } while(0);
28 return hash;
29}
30
31static unsigned int round_up(unsigned int v)
32{
33 int old_v = v;
34
35 while (v) {
36 old_v = v;
37 v ^= v & -v;
38 }
39 return old_v << 1;
40}
41
42int isl_hash_table_init(struct isl_ctx *ctx, struct isl_hash_table *table,
43 int min_size)
44{
45 size_t size;
46
47 if (!table)
48 return -1;
49
50 if (min_size < 2)
51 min_size = 2;
52 table->bits = ffs(round_up(4 * (min_size + 1) / 3 - 1)) - 1;
53 table->n = 0;
54
55 size = 1 << table->bits;
56 table->entries = isl_calloc_array(ctx, struct isl_hash_table_entry,((struct isl_hash_table_entry *)isl_calloc_or_die(ctx, size, sizeof
(struct isl_hash_table_entry)))
57 size)((struct isl_hash_table_entry *)isl_calloc_or_die(ctx, size, sizeof
(struct isl_hash_table_entry)));
58 if (!table->entries)
59 return -1;
60
61 return 0;
62}
63
64/* Dummy comparison function that always returns false.
65 */
66static isl_bool no(const void *entry, const void *val)
67{
68 return isl_bool_false;
69}
70
71/* Extend "table" to twice its size.
72 * Return 0 on success and -1 on error.
73 *
74 * We reuse isl_hash_table_find to create entries in the extended table.
75 * Since all entries in the original table are assumed to be different,
76 * there is no need to compare them against each other.
77 */
78static int grow_table(struct isl_ctx *ctx, struct isl_hash_table *table)
79{
80 int n;
81 size_t old_size, size;
82 struct isl_hash_table_entry *entries;
83 uint32_t h;
84
85 entries = table->entries;
86 old_size = 1 << table->bits;
87 size = 2 * old_size;
88 table->entries = isl_calloc_array(ctx, struct isl_hash_table_entry,((struct isl_hash_table_entry *)isl_calloc_or_die(ctx, size, sizeof
(struct isl_hash_table_entry)))
89 size)((struct isl_hash_table_entry *)isl_calloc_or_die(ctx, size, sizeof
(struct isl_hash_table_entry)));
90 if (!table->entries) {
1
Assuming field 'entries' is non-null
→
2
←
Taking false branch
→
17
←
Assuming field 'entries' is non-null
→
18
←
Taking false branch
→
36
←
Assuming field 'entries' is non-null
→
37
←
Taking false branch
→
91 table->entries = entries;
92 return -1;
93 }
94
95 n = table->n;
96 table->n = 0;
97 table->bits++;
98
99 for (h = 0; h < old_size; ++h) {
3
←
Assuming 'h' is < 'old_size'
→
4
←
Loop condition is true. Entering loop body
→
19
←
Assuming 'h' is < 'old_size'
→
20
←
Loop condition is true. Entering loop body
→
24
←
Assuming 'h' is < 'old_size'
→
25
←
Loop condition is true. Entering loop body
→
38
←
Assuming 'h' is < 'old_size'
→
39
←
Loop condition is true. Entering loop body
→
45
←
Assuming 'h' is >= 'old_size'
→
46
←
Loop condition is false. Execution continues on line 118
→
100 struct isl_hash_table_entry *entry;
101
102 if (!entries[h].data)
5
←
Assuming field 'data' is non-null
→
6
←
Taking false branch
→
21
←
Assuming field 'data' is non-null
→
22
←
Taking false branch
→
26
←
Assuming field 'data' is non-null
→
27
←
Taking false branch
→
40
←
Assuming field 'data' is non-null
→
41
←
Taking false branch
→
103 continue;
104
105 entry = isl_hash_table_find(ctx, table, entries[h].hash,
7
←
Calling 'isl_hash_table_find'
→
28
←
Calling 'isl_hash_table_find'
→
42
←
Value assigned to field 'bits'
→
106 &no, NULL((void*)0), 1);
107 if (!entry
22.1
'entry' is non-null
) {
23
←
Taking false branch
→
43
←
Assuming 'entry' is non-null
→
44
←
Taking false branch
→
108 table->bits--;
109 free(table->entries);
110 table->entries = entries;
111 table->n = n;
112 return -1;
113 }
114
115 *entry = entries[h];
116 }
117
118 free(entries);
119
120 return 0;
121}
122
123struct isl_hash_table *isl_hash_table_alloc(struct isl_ctx *ctx, int min_size)
124{
125 struct isl_hash_table *table = NULL((void*)0);
126
127 table = isl_alloc_type(ctx, struct isl_hash_table)((struct isl_hash_table *)isl_malloc_or_die(ctx, sizeof(struct
isl_hash_table)));
128 if (isl_hash_table_init(ctx, table, min_size))
129 goto error;
130 return table;
131error:
132 isl_hash_table_free(ctx, table);
133 return NULL((void*)0);
134}
135
136void isl_hash_table_clear(struct isl_hash_table *table)
137{
138 if (!table)
139 return;
140 free(table->entries);
141}
142
143void isl_hash_table_free(struct isl_ctx *ctx, struct isl_hash_table *table)
144{
145 if (!table)
146 return;
147 isl_hash_table_clear(table);
148 free(table);
149}
150
151/* A dummy entry that is used by isl_hash_table_find
152 * to make a distinction between a missing entry and an error condition.
153 */
154static struct isl_hash_table_entry none = { 0, NULL((void*)0) };
155struct isl_hash_table_entry *isl_hash_table_entry_none = &none;
156
157struct isl_hash_table_entry *isl_hash_table_find(struct isl_ctx *ctx,
158 struct isl_hash_table *table,
159 uint32_t key_hash,
160 isl_bool (*eq)(const void *entry, const void *val),
161 const void *val, int reserve)
162{
163 size_t size;
164 uint32_t h, key_bits;
165
166 key_bits = isl_hash_bits(key_hash, table->bits)((table->bits) == 32) ? (key_hash) : ((table->bits) >=
16) ? ((key_hash) >> (table->bits)) ^ ((key_hash) &
(((uint32_t)1 << (table->bits)) - 1)) : (((key_hash
) >> (table->bits)) ^ (key_hash)) & (((uint32_t)
1 << (table->bits)) - 1);
8
←
Assuming field 'bits' is not equal to 32
→
9
←
'?' condition is false
→
10
←
Assuming field 'bits' is < 16
→
11
←
'?' condition is false
→
29
←
'?' condition is false
→
30
←
'?' condition is false
→
50
←
Assuming field 'bits' is equal to 32
→
51
←
'?' condition is true
→
167 size = 1 << table->bits;
52
←
The result of the left shift is undefined due to shifting by '32', which is greater or equal to the width of type 'int'
168 for (h = key_bits; table->entries[h].data; h = (h+1) % size) {
12
←
Loop condition is false. Execution continues on line 180
→
31
←
Loop condition is false. Execution continues on line 180
→
169 isl_bool equal;
170
171 if (table->entries[h].hash != key_hash)
172 continue;
173 equal = eq(table->entries[h].data, val);
174 if (equal < 0)
175 return NULL((void*)0);
176 if (equal)
177 return &table->entries[h];
178 }
179
180 if (!reserve
12.1
'reserve' is 1
31.1
'reserve' is 1
)
13
←
Taking false branch
→
32
←
Taking false branch
→
181 return isl_hash_table_entry_none;
182
183 if (4 * table->n >= 3 * size) {
14
←
Assuming the condition is true
→
15
←
Taking true branch
→
33
←
Assuming the condition is true
→
34
←
Taking true branch
→
184 if (grow_table(ctx, table) < 0)
16
←
Calling 'grow_table'
→
35
←
Calling 'grow_table'
→
47
←
Returning from 'grow_table'
→
48
←
Taking false branch
→
185 return NULL((void*)0);
186 return isl_hash_table_find(ctx, table, key_hash, eq, val, 1);
49
←
Calling 'isl_hash_table_find'
→
187 }
188
189 table->n++;
190 table->entries[h].hash = key_hash;
191
192 return &table->entries[h];
193}
194
195/* Return the first entry containing data in "table".
196 * Return isl_hash_table_entry_none is there is no such entry and
197 * NULL on error.
198 */
199struct isl_hash_table_entry *isl_hash_table_first(struct isl_hash_table *table)
200{
201 size_t size;
202 uint32_t h;
203
204 if (!table->entries)
205 return NULL((void*)0);
206
207 size = 1 << table->bits;
208 for (h = 0; h < size; ++ h)
209 if (table->entries[h].data)
210 return &table->entries[h];
211
212 return isl_hash_table_entry_none;
213}
214
215isl_stat isl_hash_table_foreach(isl_ctx *ctx, struct isl_hash_table *table,
216 isl_stat (*fn)(void **entry, void *user), void *user)
217{
218 size_t size;
219 uint32_t h;
220
221 if (!table->entries)
222 return isl_stat_error;
223
224 size = 1 << table->bits;
225 for (h = 0; h < size; ++ h)
226 if (table->entries[h].data &&
227 fn(&table->entries[h].data, user) < 0)
228 return isl_stat_error;
229
230 return isl_stat_ok;
231}
232
233/* Does "test" succeed on every (non-empty) entry of "table"?
234 */
235isl_bool isl_hash_table_every(isl_ctx *ctx, struct isl_hash_table *table,
236 isl_bool (*test)(void **entry, void *user), void *user)
237{
238 size_t size;
239 uint32_t h;
240
241 if (!table->entries)
242 return isl_bool_error;
243
244 size = 1 << table->bits;
245 for (h = 0; h < size; ++ h) {
246 isl_bool r;
247
248 if (!table->entries[h].data)
249 continue;
250 r = test(&table->entries[h].data, user);
251 if (r < 0 || !r)
252 return r;
253 }
254
255 return isl_bool_true;
256}
257
258void isl_hash_table_remove(struct isl_ctx *ctx,
259 struct isl_hash_table *table,
260 struct isl_hash_table_entry *entry)
261{
262 int h, h2;
263 size_t size;
264
265 if (!table || !entry)
266 return;
267
268 size = 1 << table->bits;
269 h = entry - table->entries;
270 isl_assert(ctx, h >= 0 && h < size, return)do { if (h >= 0 && h < size) break; do { isl_handle_error
(ctx, isl_error_unknown, "Assertion \"" "h >= 0 && h < size"
"\" failed", "polly/lib/External/isl/isl_hash.c", 270); return
; } while (0); } while (0);
271
272 for (h2 = h+1; table->entries[h2 % size].data; h2++) {
273 uint32_t bits = isl_hash_bits(table->entries[h2 % size].hash,((table->bits) == 32) ? (table->entries[h2 % size].hash
) : ((table->bits) >= 16) ? ((table->entries[h2 % size
].hash) >> (table->bits)) ^ ((table->entries[h2 %
size].hash) & (((uint32_t)1 << (table->bits)) -
1)) : (((table->entries[h2 % size].hash) >> (table->
bits)) ^ (table->entries[h2 % size].hash)) & (((uint32_t
)1 << (table->bits)) - 1)
274 table->bits)((table->bits) == 32) ? (table->entries[h2 % size].hash
) : ((table->bits) >= 16) ? ((table->entries[h2 % size
].hash) >> (table->bits)) ^ ((table->entries[h2 %
size].hash) & (((uint32_t)1 << (table->bits)) -
1)) : (((table->entries[h2 % size].hash) >> (table->
bits)) ^ (table->entries[h2 % size].hash)) & (((uint32_t
)1 << (table->bits)) - 1);
275 uint32_t offset = (size + bits - (h+1)) % size;
276 if (offset <= h2 - (h+1))
277 continue;
278 *entry = table->entries[h2 % size];
279 h = h2;
280 entry = &table->entries[h % size];
281 }
282
283 entry->hash = 0;
284 entry->data = NULL((void*)0);
285 table->n--;
286}