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 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 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 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 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 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 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 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 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