Bug Summary

File:tools/polly/lib/External/isl/isl_hash.c
Warning:line 168, 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 -mrelocation-model pic -pic-level 2 -mthread-model posix -fmath-errno -masm-verbose -mconstructor-aliases -munwind-tables -fuse-init-array -target-cpu x86-64 -dwarf-column-info -debugger-tuning=gdb -momit-leaf-frame-pointer -ffunction-sections -fdata-sections -resource-dir /usr/lib/llvm-8/lib/clang/8.0.0 -D _DEBUG -D _GNU_SOURCE -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -I /build/llvm-toolchain-snapshot-8~svn345461/build-llvm/tools/polly/lib/External -I /build/llvm-toolchain-snapshot-8~svn345461/tools/polly/lib/External -I /build/llvm-toolchain-snapshot-8~svn345461/tools/polly/lib/External/pet/include -I /build/llvm-toolchain-snapshot-8~svn345461/tools/polly/lib/External/ppcg/include -I /build/llvm-toolchain-snapshot-8~svn345461/tools/polly/lib/External/ppcg/imath -I /build/llvm-toolchain-snapshot-8~svn345461/build-llvm/tools/polly/lib/External/ppcg -I /build/llvm-toolchain-snapshot-8~svn345461/tools/polly/lib/External/isl -I /build/llvm-toolchain-snapshot-8~svn345461/tools/polly/lib/External/isl/include -I /build/llvm-toolchain-snapshot-8~svn345461/tools/polly/lib/External/isl/imath -I /build/llvm-toolchain-snapshot-8~svn345461/build-llvm/tools/polly/lib/External/isl -I /build/llvm-toolchain-snapshot-8~svn345461/build-llvm/tools/polly/include -I /build/llvm-toolchain-snapshot-8~svn345461/build-llvm/tools/polly/lib/External/isl/include -I /build/llvm-toolchain-snapshot-8~svn345461/tools/polly/include -I /build/llvm-toolchain-snapshot-8~svn345461/build-llvm/include -I /build/llvm-toolchain-snapshot-8~svn345461/include -U NDEBUG -internal-isystem /usr/local/include -internal-isystem /usr/lib/llvm-8/lib/clang/8.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-8~svn345461/build-llvm/tools/polly/lib/External -fdebug-prefix-map=/build/llvm-toolchain-snapshot-8~svn345461=. -ferror-limit 19 -fmessage-length 0 -stack-protector 2 -fobjc-runtime=gcc -fdiagnostics-show-option -vectorize-loops -vectorize-slp -analyzer-output=html -analyzer-config stable-report-filename=true -o /tmp/scan-build-2018-10-27-211344-32123-1 -x c /build/llvm-toolchain-snapshot-8~svn345461/tools/polly/lib/External/isl/isl_hash.c -faddrsig
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 int no(const void *entry, const void *val)
67{
68 return 0;
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 the condition is false
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 the condition is false
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 can be used to make a distinction between
152 * a missing entry and an error condition.
153 * It is used by isl_union_*_find_part_entry.
154 */
155static struct isl_hash_table_entry none = { 0, NULL((void*)0) };
156struct isl_hash_table_entry *isl_hash_table_entry_none = &none;
157
158struct isl_hash_table_entry *isl_hash_table_find(struct isl_ctx *ctx,
159 struct isl_hash_table *table,
160 uint32_t key_hash,
161 int (*eq)(const void *entry, const void *val),
162 const void *val, int reserve)
163{
164 size_t size;
165 uint32_t h, key_bits;
166
167 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)
;
168 size = 1 << table->bits;
9
The result of the left shift is undefined due to shifting by '32', which is greater or equal to the width of type 'int'
169 for (h = key_bits; table->entries[h].data; h = (h+1) % size)
170 if (table->entries[h].hash == key_hash &&
171 eq(table->entries[h].data, val))
172 return &table->entries[h];
173
174 if (!reserve)
175 return NULL((void*)0);
176
177 if (4 * table->n >= 3 * size) {
178 if (grow_table(ctx, table) < 0)
179 return NULL((void*)0);
180 return isl_hash_table_find(ctx, table, key_hash, eq, val, 1);
181 }
182
183 table->n++;
184 table->entries[h].hash = key_hash;
185
186 return &table->entries[h];
187}
188
189isl_stat isl_hash_table_foreach(isl_ctx *ctx, struct isl_hash_table *table,
190 isl_stat (*fn)(void **entry, void *user), void *user)
191{
192 size_t size;
193 uint32_t h;
194
195 if (!table->entries)
196 return isl_stat_error;
197
198 size = 1 << table->bits;
199 for (h = 0; h < size; ++ h)
200 if (table->entries[h].data &&
201 fn(&table->entries[h].data, user) < 0)
202 return isl_stat_error;
203
204 return isl_stat_ok;
205}
206
207void isl_hash_table_remove(struct isl_ctx *ctx,
208 struct isl_hash_table *table,
209 struct isl_hash_table_entry *entry)
210{
211 int h, h2;
212 size_t size;
213
214 if (!table || !entry)
215 return;
216
217 size = 1 << table->bits;
218 h = entry - table->entries;
219 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-8~svn345461/tools/polly/lib/External/isl/isl_hash.c"
, 219); return; } while (0); } while (0)
;
220
221 for (h2 = h+1; table->entries[h2 % size].data; h2++) {
222 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)
223 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)
;
224 uint32_t offset = (size + bits - (h+1)) % size;
225 if (offset <= h2 - (h+1))
226 continue;
227 *entry = table->entries[h2 % size];
228 h = h2;
229 entry = &table->entries[h % size];
230 }
231
232 entry->hash = 0;
233 entry->data = NULL((void*)0);
234 table->n--;
235}