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. */
10static vbits_t
11and_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. */
48static void
49check_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
175static int
176test_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
222static value_t
223all_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
239static value_t
240all_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
256static int
257test_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
330static int
331test_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
412int
413test_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