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