Bug Summary

File:tools/polly/lib/External/isl/isl_hash.c
Warning:line 167, column 13
The result of the left shift is undefined due to shifting by '33', which is greater or equal to the width of type 'uint32_t'

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-eagerly-assume -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-7/lib/clang/7.0.0 -D _DEBUG -D _GNU_SOURCE -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -I /build/llvm-toolchain-snapshot-7~svn337204/build-llvm/tools/polly/lib/External -I /build/llvm-toolchain-snapshot-7~svn337204/tools/polly/lib/External -I /build/llvm-toolchain-snapshot-7~svn337204/tools/polly/lib/External/pet/include -I /build/llvm-toolchain-snapshot-7~svn337204/tools/polly/lib/External/ppcg/include -I /build/llvm-toolchain-snapshot-7~svn337204/tools/polly/lib/External/ppcg/imath -I /build/llvm-toolchain-snapshot-7~svn337204/build-llvm/tools/polly/lib/External/ppcg -I /build/llvm-toolchain-snapshot-7~svn337204/tools/polly/lib/External/isl -I /build/llvm-toolchain-snapshot-7~svn337204/tools/polly/lib/External/isl/include -I /build/llvm-toolchain-snapshot-7~svn337204/tools/polly/lib/External/isl/imath -I /build/llvm-toolchain-snapshot-7~svn337204/build-llvm/tools/polly/lib/External/isl -I /build/llvm-toolchain-snapshot-7~svn337204/build-llvm/tools/polly/include -I /usr/include/jsoncpp -I /build/llvm-toolchain-snapshot-7~svn337204/build-llvm/tools/polly/lib/External/isl/include -I /build/llvm-toolchain-snapshot-7~svn337204/tools/polly/include -I /build/llvm-toolchain-snapshot-7~svn337204/build-llvm/include -I /build/llvm-toolchain-snapshot-7~svn337204/include -U NDEBUG -internal-isystem /usr/local/include -internal-isystem /usr/lib/llvm-7/lib/clang/7.0.0/include -internal-externc-isystem /usr/lib/gcc/x86_64-linux-gnu/7.3.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-7~svn337204/build-llvm/tools/polly/lib/External -fdebug-prefix-map=/build/llvm-toolchain-snapshot-7~svn337204=. -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-07-17-043059-5239-1 -x c /build/llvm-toolchain-snapshot-7~svn337204/tools/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 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
13
Assuming the condition is false
14
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
15
Assuming 'h' is < 'old_size'
16
Loop condition is true. Entering loop body
100 struct isl_hash_table_entry *entry;
101
102 if (!entries[h].data)
5
Assuming the condition is false
6
Taking false branch
17
Assuming the condition is false
18
Taking false branch
103 continue;
104
105 entry = isl_hash_table_find(ctx, table, entries[h].hash,
7
Calling 'isl_hash_table_find'
19
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)
;
20
Within the expansion of the macro 'isl_hash_bits':
a
The result of the left shift is undefined due to shifting by '33', which is greater or equal to the width of type 'uint32_t'
168 size = 1 << table->bits;
169 for (h = key_bits; table->entries[h].data; h = (h+1) % size)
8
Loop condition is false. Execution continues on line 174
170 if (table->entries[h].hash == key_hash &&
171 eq(table->entries[h].data, val))
172 return &table->entries[h];
173
174 if (!reserve)
9
Taking false branch
175 return NULL((void*)0);
176
177 if (4 * table->n >= 3 * size) {
10
Assuming the condition is true
11
Taking true branch
178 if (grow_table(ctx, table) < 0)
12
Calling 'grow_table'
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-7~svn337204/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}