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 -triple x86_64-pc-linux-gnu -analyze -disable-free -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 -mthread-model posix -mframe-pointer=none -fmath-errno -fno-rounding-math -masm-verbose -mconstructor-aliases -munwind-tables -target-cpu x86-64 -dwarf-column-info -fno-split-dwarf-inlining -debugger-tuning=gdb -ffunction-sections -fdata-sections -resource-dir /usr/lib/llvm-11/lib/clang/11.0.0 -D _DEBUG -D _GNU_SOURCE -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -I /build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/build-llvm/tools/polly/lib/External -I /build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/polly/lib/External -I /build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/polly/lib/External/pet/include -I /build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/polly/lib/External/ppcg/include -I /build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/polly/lib/External/ppcg/imath -I /build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/build-llvm/tools/polly/lib/External/ppcg -I /build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/polly/lib/External/isl -I /build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/polly/lib/External/isl/include -I /build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/polly/lib/External/isl/imath -I /build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/build-llvm/tools/polly/lib/External/isl -I /build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/build-llvm/tools/polly/include -I /build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/build-llvm/tools/polly/lib/External/isl/include -I /build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/polly/include -I /build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/build-llvm/include -I /build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/include -U NDEBUG -internal-isystem /usr/local/include -internal-isystem /usr/lib/llvm-11/lib/clang/11.0.0/include -internal-externc-isystem /usr/include/x86_64-linux-gnu -internal-externc-isystem /include -internal-externc-isystem /usr/include -O2 -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-11~++20200309111110+2c36c23f347/build-llvm/tools/polly/lib/External -fdebug-prefix-map=/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347=. -ferror-limit 19 -fmessage-length 0 -stack-protector 2 -fgnuc-version=4.2.1 -fobjc-runtime=gcc -fdiagnostics-show-option -vectorize-loops -vectorize-slp -analyzer-output=html -analyzer-config stable-report-filename=true -faddrsig -o /tmp/scan-build-2020-03-09-184146-41876-1 -x c /build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/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
91 table->entries = entries;
92 return -1;
93 }
94
95 n = table->n;
96 table->n = 0;
97 table->bits++;
3
Value assigned to field 'bits'
98
99 for (h = 0; h < old_size; ++h) {
4
Assuming 'h' is < 'old_size'
5
Loop condition is true. Entering loop body
100 struct isl_hash_table_entry *entry;
101
102 if (!entries[h].data)
6
Assuming field 'data' is non-null
7
Taking false branch
103 continue;
104
105 entry = isl_hash_table_find(ctx, table, entries[h].hash,
8
Calling 'isl_hash_table_find'
106 &no, NULL((void*)0), 1);
107 if (!entry) {
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)
;
9
Assuming field 'bits' is equal to 32
10
'?' condition is true
167 size = 1 << table->bits;
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'
168 for (h = key_bits; table->entries[h].data; h = (h+1) % size) {
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)
181 return isl_hash_table_entry_none;
182
183 if (4 * table->n >= 3 * size) {
184 if (grow_table(ctx, table) < 0)
185 return NULL((void*)0);
186 return isl_hash_table_find(ctx, table, key_hash, eq, val, 1);
187 }
188
189 table->n++;
190 table->entries[h].hash = key_hash;
191
192 return &table->entries[h];
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", "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/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}