• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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