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