Bug Summary

File: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-store=region -analyzer-opt-analyze-nested-blocks -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/llvm-toolchain-snapshot-14~++20220119111520+da61cb019eb2/build-llvm -resource-dir /usr/lib/llvm-14/lib/clang/14.0.0 -D _DEBUG -D _GNU_SOURCE -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -I tools/polly/lib/External -I /build/llvm-toolchain-snapshot-14~++20220119111520+da61cb019eb2/polly/lib/External -I /build/llvm-toolchain-snapshot-14~++20220119111520+da61cb019eb2/polly/lib/External/isl -I /build/llvm-toolchain-snapshot-14~++20220119111520+da61cb019eb2/polly/lib/External/isl/include -I /build/llvm-toolchain-snapshot-14~++20220119111520+da61cb019eb2/polly/lib/External/isl/imath -I tools/polly/lib/External/isl -I tools/polly/include -I /build/llvm-toolchain-snapshot-14~++20220119111520+da61cb019eb2/polly/lib/External/pet/include -I tools/polly/lib/External/isl/include -I /build/llvm-toolchain-snapshot-14~++20220119111520+da61cb019eb2/polly/include -I include -I /build/llvm-toolchain-snapshot-14~++20220119111520+da61cb019eb2/llvm/include -D _FORTIFY_SOURCE=2 -D NDEBUG -U NDEBUG -internal-isystem /usr/lib/llvm-14/lib/clang/14.0.0/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/llvm-toolchain-snapshot-14~++20220119111520+da61cb019eb2/build-llvm=build-llvm -fmacro-prefix-map=/build/llvm-toolchain-snapshot-14~++20220119111520+da61cb019eb2/= -fcoverage-prefix-map=/build/llvm-toolchain-snapshot-14~++20220119111520+da61cb019eb2/build-llvm=build-llvm -fcoverage-prefix-map=/build/llvm-toolchain-snapshot-14~++20220119111520+da61cb019eb2/= -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/llvm-toolchain-snapshot-14~++20220119111520+da61cb019eb2/build-llvm -fdebug-prefix-map=/build/llvm-toolchain-snapshot-14~++20220119111520+da61cb019eb2/build-llvm=build-llvm -fdebug-prefix-map=/build/llvm-toolchain-snapshot-14~++20220119111520+da61cb019eb2/= -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-2022-01-19-134126-35450-1 -x c /build/llvm-toolchain-snapshot-14~++20220119111520+da61cb019eb2/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.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
16
Assuming field 'entries' is non-null
17
Taking false branch
43
Assuming field 'entries' is non-null
44
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
31.1
'h' is < 'old_size'
< old_size
; ++h) {
3
Assuming 'h' is < 'old_size'
4
Loop condition is true. Entering loop body
18
Assuming 'h' is < 'old_size'
19
Loop condition is true. Entering loop body
32
Loop condition is true. Entering loop body
45
Assuming 'h' is < 'old_size'
46
Loop condition is true. Entering loop body
52
Assuming 'h' is >= 'old_size'
53
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
20
Assuming field 'data' is non-null
21
Taking false branch
33
Assuming field 'data' is non-null
34
Taking false branch
47
Assuming field 'data' is non-null
48
Taking false branch
103 continue;
104
105 entry = isl_hash_table_find(ctx, table, entries[h].hash,
7
Calling 'isl_hash_table_find'
22
Calling 'isl_hash_table_find'
30
Returning from 'isl_hash_table_find'
35
Calling 'isl_hash_table_find'
49
Value assigned to field 'bits'
106 &no, NULL((void*)0), 1);
107 if (!entry
30.1
'entry' is non-null
) {
31
Taking false branch
50
Assuming 'entry' is non-null
51
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
'?' condition is false
9
Assuming field 'bits' is < 16
10
'?' condition is false
23
'?' condition is false
24
'?' condition is false
36
'?' condition is false
37
'?' condition is false
57
Assuming field 'bits' is equal to 32
58
'?' condition is true
167 size = 1 << table->bits;
59
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) {
11
Loop condition is false. Execution continues on line 180
25
Loop condition is false. Execution continues on line 180
38
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
11.1
'reserve' is 1
25.1
'reserve' is 1
38.1
'reserve' is 1
)
12
Taking false branch
26
Taking false branch
39
Taking false branch
181 return isl_hash_table_entry_none;
182
183 if (4 * table->n >= 3 * size) {
13
Assuming the condition is true
14
Taking true branch
27
Assuming the condition is false
28
Taking false branch
40
Assuming the condition is true
41
Taking true branch
184 if (grow_table(ctx, table) < 0)
15
Calling 'grow_table'
42
Calling 'grow_table'
54
Returning from 'grow_table'
55
Taking false branch
185 return NULL((void*)0);
186 return isl_hash_table_find(ctx, table, key_hash, eq, val, 1);
56
Calling 'isl_hash_table_find'
187 }
188
189 table->n++;
190 table->entries[h].hash = key_hash;
191
192 return &table->entries[h];
29
Returning without writing to 'table->bits'
193}
194
195isl_stat isl_hash_table_foreach(isl_ctx *ctx, struct isl_hash_table *table,
196 isl_stat (*fn)(void **entry, void *user), void *user)
197{
198 size_t size;
199 uint32_t h;
200
201 if (!table->entries)
202 return isl_stat_error;
203
204 size = 1 << table->bits;
205 for (h = 0; h < size; ++ h)
206 if (table->entries[h].data &&
207 fn(&table->entries[h].data, user) < 0)
208 return isl_stat_error;
209
210 return isl_stat_ok;
211}
212
213void isl_hash_table_remove(struct isl_ctx *ctx,
214 struct isl_hash_table *table,
215 struct isl_hash_table_entry *entry)
216{
217 int h, h2;
218 size_t size;
219
220 if (!table || !entry)
221 return;
222
223 size = 1 << table->bits;
224 h = entry - table->entries;
225 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", 225); return
; } while (0); } while (0)
;
226
227 for (h2 = h+1; table->entries[h2 % size].data; h2++) {
228 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)
229 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)
;
230 uint32_t offset = (size + bits - (h+1)) % size;
231 if (offset <= h2 - (h+1))
232 continue;
233 *entry = table->entries[h2 % size];
234 h = h2;
235 entry = &table->entries[h % size];
236 }
237
238 entry->hash = 0;
239 entry->data = NULL((void*)0);
240 table->n--;
241}