1 /* -*- mode: C; c-basic-offset: 3; -*- */
2
3 /*
4 This file is part of MemCheck, a heavyweight Valgrind tool for
5 detecting memory errors.
6
7 Copyright (C) 2012-2015 Florian Krohm
8
9 This program is free software; you can redistribute it and/or
10 modify it under the terms of the GNU General Public License as
11 published by the Free Software Foundation; either version 2 of the
12 License, or (at your option) any later version.
13
14 This program is distributed in the hope that it will be useful, but
15 WITHOUT ANY WARRANTY; without even the implied warranty of
16 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
17 General Public License for more details.
18
19 You should have received a copy of the GNU General Public License
20 along with this program; if not, write to the Free Software
21 Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
22 02111-1307, USA.
23
24 The GNU General Public License is contained in the file COPYING.
25 */
26
27 #include <assert.h>
28 #include <string.h> // memset
29 #include "vtest.h"
30
31
32 /* A convenience function to compute either v1 & ~v2 & val2 or
33 v1 & ~v2 & ~val2 depending on INVERT_VAL2. */
34 static vbits_t
and_combine(vbits_t v1,vbits_t v2,value_t val2,int invert_val2)35 and_combine(vbits_t v1, vbits_t v2, value_t val2, int invert_val2)
36 {
37 assert(v1.num_bits == v2.num_bits);
38
39 vbits_t new = { .num_bits = v2.num_bits };
40
41 if (invert_val2) {
42 switch (v2.num_bits) {
43 case 8: val2.u8 = ~val2.u8 & 0xff; break;
44 case 16: val2.u16 = ~val2.u16 & 0xffff; break;
45 case 32: val2.u32 = ~val2.u32; break;
46 case 64: val2.u64 = ~val2.u64; break;
47 default:
48 panic(__func__);
49 }
50 }
51
52 switch (v2.num_bits) {
53 case 8:
54 new.bits.u8 = (v1.bits.u8 & ~v2.bits.u8 & val2.u8) & 0xff;
55 break;
56 case 16:
57 new.bits.u16 = (v1.bits.u16 & ~v2.bits.u16 & val2.u16) & 0xffff;
58 break;
59 case 32:
60 new.bits.u32 = (v1.bits.u32 & ~v2.bits.u32 & val2.u32);
61 break;
62 case 64:
63 new.bits.u64 = (v1.bits.u64 & ~v2.bits.u64 & val2.u64);
64 break;
65 default:
66 panic(__func__);
67 }
68 return new;
69 }
70
71 /* Check the result of a binary operation. */
72 static void
check_result_for_binary(const irop_t * op,const test_data_t * data)73 check_result_for_binary(const irop_t *op, const test_data_t *data)
74 {
75 const opnd_t *result = &data->result;
76 const opnd_t *opnd1 = &data->opnds[0];
77 const opnd_t *opnd2 = &data->opnds[1];
78 vbits_t expected_vbits;
79
80 /* Only handle those undef-kinds that actually occur. */
81 switch (op->undef_kind) {
82 case UNDEF_NONE:
83 expected_vbits = defined_vbits(result->vbits.num_bits);
84 break;
85
86 case UNDEF_ALL:
87 expected_vbits = undefined_vbits(result->vbits.num_bits);
88 break;
89
90 case UNDEF_LEFT:
91 // LEFT with respect to the leftmost 1-bit in both operands
92 expected_vbits = left_vbits(or_vbits(opnd1->vbits, opnd2->vbits),
93 result->vbits.num_bits);
94 break;
95
96 case UNDEF_SAME:
97 assert(opnd1->vbits.num_bits == opnd2->vbits.num_bits);
98 assert(opnd1->vbits.num_bits == result->vbits.num_bits);
99
100 // SAME with respect to the 1-bits in both operands
101 expected_vbits = or_vbits(opnd1->vbits, opnd2->vbits);
102 break;
103
104 case UNDEF_CONCAT:
105 assert(opnd1->vbits.num_bits == opnd2->vbits.num_bits);
106 assert(result->vbits.num_bits == 2 * opnd1->vbits.num_bits);
107 expected_vbits = concat_vbits(opnd1->vbits, opnd2->vbits);
108 break;
109
110 case UNDEF_SHL:
111 /* If any bit in the 2nd operand is undefined, so are all bits
112 of the result. */
113 if (! completely_defined_vbits(opnd2->vbits)) {
114 expected_vbits = undefined_vbits(result->vbits.num_bits);
115 } else {
116 assert(opnd2->vbits.num_bits == 8);
117 unsigned shift_amount = opnd2->value.u8;
118
119 expected_vbits = shl_vbits(opnd1->vbits, shift_amount);
120 }
121 break;
122
123 case UNDEF_SHR:
124 /* If any bit in the 2nd operand is undefined, so are all bits
125 of the result. */
126 if (! completely_defined_vbits(opnd2->vbits)) {
127 expected_vbits = undefined_vbits(result->vbits.num_bits);
128 } else {
129 assert(opnd2->vbits.num_bits == 8);
130 unsigned shift_amount = opnd2->value.u8;
131
132 expected_vbits = shr_vbits(opnd1->vbits, shift_amount);
133 }
134 break;
135
136 case UNDEF_SAR:
137 /* If any bit in the 2nd operand is undefined, so are all bits
138 of the result. */
139 if (! completely_defined_vbits(opnd2->vbits)) {
140 expected_vbits = undefined_vbits(result->vbits.num_bits);
141 } else {
142 assert(opnd2->vbits.num_bits == 8);
143 unsigned shift_amount = opnd2->value.u8;
144
145 expected_vbits = sar_vbits(opnd1->vbits, shift_amount);
146 }
147 break;
148
149 case UNDEF_AND: {
150 /* Let v1, v2 be the V-bits of the 1st and 2nd operand, respectively
151 Let b1, b2 be the actual value of the 1st and 2nd operand, respect.
152 And output bit is undefined (i.e. its V-bit == 1), iff
153 (1) (v1 == 1) && (v2 == 1) OR
154 (2) (v1 == 1) && (v2 == 0 && b2 == 1) OR
155 (3) (v2 == 1) && (v1 == 0 && b1 == 1)
156 */
157 vbits_t term1, term2, term3;
158 term1 = and_vbits(opnd1->vbits, opnd2->vbits);
159 term2 = and_combine(opnd1->vbits, opnd2->vbits, opnd2->value, 0);
160 term3 = and_combine(opnd2->vbits, opnd1->vbits, opnd1->value, 0);
161 expected_vbits = or_vbits(term1, or_vbits(term2, term3));
162 break;
163 }
164
165 case UNDEF_OR: {
166 /* Let v1, v2 be the V-bits of the 1st and 2nd operand, respectively
167 Let b1, b2 be the actual value of the 1st and 2nd operand, respect.
168 And output bit is undefined (i.e. its V-bit == 1), iff
169 (1) (v1 == 1) && (v2 == 1) OR
170 (2) (v1 == 1) && (v2 == 0 && b2 == 0) OR
171 (3) (v2 == 1) && (v1 == 0 && b1 == 0)
172 */
173 vbits_t term1, term2, term3;
174 term1 = and_vbits(opnd1->vbits, opnd2->vbits);
175 term2 = and_combine(opnd1->vbits, opnd2->vbits, opnd2->value, 1);
176 term3 = and_combine(opnd2->vbits, opnd1->vbits, opnd1->value, 1);
177 expected_vbits = or_vbits(term1, or_vbits(term2, term3));
178 break;
179 }
180
181 case UNDEF_ORD:
182 /* Set expected_vbits for the Iop_CmpORD category of iops.
183 * If any of the input bits is undefined the least significant
184 * three bits in the result will be set, i.e. 0xe.
185 */
186 expected_vbits = cmpord_vbits(opnd1->vbits.num_bits,
187 opnd2->vbits.num_bits);
188 break;
189
190 default:
191 panic(__func__);
192 }
193
194 if (! equal_vbits(result->vbits, expected_vbits))
195 complain(op, data, expected_vbits);
196 }
197
198
199 static int
test_shift(const irop_t * op,test_data_t * data)200 test_shift(const irop_t *op, test_data_t *data)
201 {
202 unsigned num_input_bits, i;
203 opnd_t *opnds = data->opnds;
204 int tests_done = 0;
205
206 /* When testing the 1st operand's undefinedness propagation,
207 do so with all possible shift amnounts */
208 for (unsigned amount = 0; amount < bitsof_irtype(opnds[0].type); ++amount) {
209 opnds[1].value.u8 = amount;
210
211 // 1st (left) operand
212 num_input_bits = bitsof_irtype(opnds[0].type);
213
214 for (i = 0; i < num_input_bits; ++i) {
215 opnds[0].vbits = onehot_vbits(i, bitsof_irtype(opnds[0].type));
216 opnds[1].vbits = defined_vbits(bitsof_irtype(opnds[1].type));
217
218 valgrind_execute_test(op, data);
219
220 check_result_for_binary(op, data);
221 tests_done++;
222 }
223 }
224
225 // 2nd (right) operand
226
227 /* If the operand is an immediate value, there are no v-bits to set. */
228 if (op->shift_amount_is_immediate) return tests_done;
229
230 num_input_bits = bitsof_irtype(opnds[1].type);
231
232 for (i = 0; i < num_input_bits; ++i) {
233 opnds[0].vbits = defined_vbits(bitsof_irtype(opnds[0].type));
234 opnds[1].vbits = onehot_vbits(i, bitsof_irtype(opnds[1].type));
235
236 valgrind_execute_test(op, data);
237
238 check_result_for_binary(op, data);
239
240 tests_done++;
241 }
242 return tests_done;
243 }
244
245
246 static value_t
all_bits_zero_value(unsigned num_bits)247 all_bits_zero_value(unsigned num_bits)
248 {
249 value_t val;
250
251 switch (num_bits) {
252 case 8: val.u8 = 0; break;
253 case 16: val.u16 = 0; break;
254 case 32: val.u32 = 0; break;
255 case 64: val.u64 = 0; break;
256 default:
257 panic(__func__);
258 }
259 return val;
260 }
261
262
263 static value_t
all_bits_one_value(unsigned num_bits)264 all_bits_one_value(unsigned num_bits)
265 {
266 value_t val;
267
268 switch (num_bits) {
269 case 8: val.u8 = 0xff; break;
270 case 16: val.u16 = 0xffff; break;
271 case 32: val.u32 = ~0u; break;
272 case 64: val.u64 = ~0ull; break;
273 default:
274 panic(__func__);
275 }
276 return val;
277 }
278
279
280 static int
test_and(const irop_t * op,test_data_t * data)281 test_and(const irop_t *op, test_data_t *data)
282 {
283 unsigned num_input_bits, bitpos;
284 opnd_t *opnds = data->opnds;
285 int tests_done = 0;
286
287 /* Undefinedness does not propagate if the other operand is 0.
288 Use an all-bits-zero operand and test the other operand in
289 the usual way (one bit undefined at a time). */
290
291 // 1st (left) operand variable, 2nd operand all-bits-zero
292 num_input_bits = bitsof_irtype(opnds[0].type);
293
294 for (bitpos = 0; bitpos < num_input_bits; ++bitpos) {
295 opnds[0].vbits = onehot_vbits(bitpos, bitsof_irtype(opnds[0].type));
296 opnds[1].vbits = defined_vbits(bitsof_irtype(opnds[1].type));
297 opnds[1].value = all_bits_zero_value(bitsof_irtype(opnds[1].type));
298
299 valgrind_execute_test(op, data);
300
301 check_result_for_binary(op, data);
302 tests_done++;
303 }
304
305 // 2nd (right) operand variable, 1st operand all-bits-zero
306 num_input_bits = bitsof_irtype(opnds[1].type);
307
308 for (bitpos = 0; bitpos < num_input_bits; ++bitpos) {
309 opnds[1].vbits = onehot_vbits(bitpos, bitsof_irtype(opnds[1].type));
310 opnds[0].vbits = defined_vbits(bitsof_irtype(opnds[0].type));
311 opnds[0].value = all_bits_zero_value(bitsof_irtype(opnds[0].type));
312
313 valgrind_execute_test(op, data);
314
315 check_result_for_binary(op, data);
316 tests_done++;
317 }
318
319 /* Undefinedness propagates if the other operand is 1.
320 Use an all-bits-one operand and test the other operand in
321 the usual way (one bit undefined at a time). */
322
323 // 1st (left) operand variable, 2nd operand all-bits-one
324 num_input_bits = bitsof_irtype(opnds[0].type);
325
326 for (bitpos = 0; bitpos < num_input_bits; ++bitpos) {
327 opnds[0].vbits = onehot_vbits(bitpos, bitsof_irtype(opnds[0].type));
328 opnds[1].vbits = defined_vbits(bitsof_irtype(opnds[1].type));
329 opnds[1].value = all_bits_one_value(bitsof_irtype(opnds[1].type));
330
331 valgrind_execute_test(op, data);
332
333 check_result_for_binary(op, data);
334 tests_done++;
335 }
336
337 // 2nd (right) operand variable, 1st operand all-bits-one
338 num_input_bits = bitsof_irtype(opnds[1].type);
339
340 for (bitpos = 0; bitpos < num_input_bits; ++bitpos) {
341 opnds[1].vbits = onehot_vbits(bitpos, bitsof_irtype(opnds[1].type));
342 opnds[0].vbits = defined_vbits(bitsof_irtype(opnds[0].type));
343 opnds[0].value = all_bits_one_value(bitsof_irtype(opnds[0].type));
344
345 valgrind_execute_test(op, data);
346
347 check_result_for_binary(op, data);
348 tests_done++;
349 }
350 return tests_done;
351 }
352
353
354 static int
test_or(const irop_t * op,test_data_t * data)355 test_or(const irop_t *op, test_data_t *data)
356 {
357 unsigned num_input_bits, bitpos;
358 opnd_t *opnds = data->opnds;
359 int tests_done = 0;
360
361 /* Undefinedness does not propagate if the other operand is 1.
362 Use an all-bits-one operand and test the other operand in
363 the usual way (one bit undefined at a time). */
364
365 // 1st (left) operand variable, 2nd operand all-bits-one
366 num_input_bits = bitsof_irtype(opnds[0].type);
367
368 opnds[0].vbits = defined_vbits(bitsof_irtype(opnds[0].type));
369 opnds[1].vbits = defined_vbits(bitsof_irtype(opnds[1].type));
370 opnds[1].value = all_bits_one_value(bitsof_irtype(opnds[1].type));
371
372 for (bitpos = 0; bitpos < num_input_bits; ++bitpos) {
373 opnds[0].vbits = onehot_vbits(bitpos, bitsof_irtype(opnds[0].type));
374
375 valgrind_execute_test(op, data);
376
377 check_result_for_binary(op, data);
378 tests_done++;
379 }
380
381 // 2nd (right) operand variable, 1st operand all-bits-one
382 num_input_bits = bitsof_irtype(opnds[1].type);
383
384 opnds[0].vbits = defined_vbits(bitsof_irtype(opnds[0].type));
385 opnds[1].vbits = defined_vbits(bitsof_irtype(opnds[1].type));
386 opnds[0].value = all_bits_one_value(bitsof_irtype(opnds[0].type));
387
388 for (bitpos = 0; bitpos < num_input_bits; ++bitpos) {
389 opnds[1].vbits = onehot_vbits(bitpos, bitsof_irtype(opnds[1].type));
390
391 valgrind_execute_test(op, data);
392
393 check_result_for_binary(op, data);
394 tests_done++;
395 }
396
397 /* Undefinedness propagates if the other operand is 0.
398 Use an all-bits-zero operand and test the other operand in
399 the usual way (one bit undefined at a time). */
400
401 // 1st (left) operand variable, 2nd operand all-bits-zero
402 num_input_bits = bitsof_irtype(opnds[0].type);
403
404 opnds[0].vbits = defined_vbits(bitsof_irtype(opnds[0].type));
405 opnds[1].vbits = defined_vbits(bitsof_irtype(opnds[1].type));
406 opnds[1].value = all_bits_zero_value(bitsof_irtype(opnds[1].type));
407
408 for (bitpos = 0; bitpos < num_input_bits; ++bitpos) {
409 opnds[0].vbits = onehot_vbits(bitpos, bitsof_irtype(opnds[0].type));
410
411 valgrind_execute_test(op, data);
412
413 check_result_for_binary(op, data);
414 tests_done++;
415 }
416
417 // 2nd (right) operand variable, 1st operand all-bits-zero
418 num_input_bits = bitsof_irtype(opnds[1].type);
419
420 opnds[0].vbits = defined_vbits(bitsof_irtype(opnds[0].type));
421 opnds[1].vbits = defined_vbits(bitsof_irtype(opnds[1].type));
422 opnds[0].value = all_bits_zero_value(bitsof_irtype(opnds[0].type));
423
424 for (bitpos = 0; bitpos < num_input_bits; ++bitpos) {
425 opnds[1].vbits = onehot_vbits(bitpos, bitsof_irtype(opnds[1].type));
426
427 valgrind_execute_test(op, data);
428
429 check_result_for_binary(op, data);
430 tests_done++;
431 }
432 return tests_done;
433 }
434
435
436 int
test_binary_op(const irop_t * op,test_data_t * data)437 test_binary_op(const irop_t *op, test_data_t *data)
438 {
439 unsigned num_input_bits, i, bitpos;
440 opnd_t *opnds = data->opnds;
441 int tests_done = 0;
442
443 /* Handle special cases upfront */
444 switch (op->undef_kind) {
445 case UNDEF_SHL:
446 case UNDEF_SHR:
447 case UNDEF_SAR:
448 return test_shift(op, data);
449
450 case UNDEF_AND:
451 return test_and(op, data);
452
453 case UNDEF_OR:
454 return test_or(op, data);
455
456 default:
457 break;
458 }
459
460 /* For each operand, set a single bit to undefined and observe how
461 that propagates to the output. Do this for all bits in each
462 operand. */
463 for (i = 0; i < 2; ++i) {
464
465 /* If this is a shift op that requires an immediate shift amount,
466 do not iterate the v-bits of the 2nd operand */
467 if (i == 1 && op->shift_amount_is_immediate) break;
468
469 num_input_bits = bitsof_irtype(opnds[i].type);
470 opnds[0].vbits = defined_vbits(bitsof_irtype(opnds[0].type));
471 opnds[1].vbits = defined_vbits(bitsof_irtype(opnds[1].type));
472
473 /* Set the value of the 2nd operand to something != 0. So division
474 won't crash. */
475 memset(&opnds[1].value, 0xff, sizeof opnds[1].value);
476
477 /* For immediate shift amounts choose a value of '1'. That value should
478 not cause a problem. Note: we always assign to the u64 member here.
479 The reason is that in ir_inject.c the value_t type is not visible.
480 The value is picked up there by interpreting the memory as an
481 ULong value. So, we rely on
482 union {
483 ULong v1; // value picked up in ir_inject.c
484 value_t v2; // value assigned here
485 } xx;
486 assert(sizeof xx.v1 == sizeof xx.v2.u64);
487 assert(xx.v1 == xx.v2.u64);
488 */
489 if (op->shift_amount_is_immediate)
490 opnds[1].value.u64 = 1;
491
492 for (bitpos = 0; bitpos < num_input_bits; ++bitpos) {
493 opnds[i].vbits = onehot_vbits(bitpos, bitsof_irtype(opnds[i].type));
494
495 valgrind_execute_test(op, data);
496
497 check_result_for_binary(op, data);
498
499 tests_done++;
500 }
501 }
502 return tests_done;
503 }
504