/* -*- mode: C; c-basic-offset: 3; -*- */ /* This file is part of MemCheck, a heavyweight Valgrind tool for detecting memory errors. Copyright (C) 2012-2015 Florian Krohm This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with this program; if not, write to the Free Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307, USA. The GNU General Public License is contained in the file COPYING. */ #include <assert.h> #include <string.h> // memset #include "vtest.h" /* A convenience function to compute either v1 & ~v2 & val2 or v1 & ~v2 & ~val2 depending on INVERT_VAL2. */ static vbits_t and_combine(vbits_t v1, vbits_t v2, value_t val2, int invert_val2) { assert(v1.num_bits == v2.num_bits); vbits_t new = { .num_bits = v2.num_bits }; if (invert_val2) { switch (v2.num_bits) { case 8: val2.u8 = ~val2.u8 & 0xff; break; case 16: val2.u16 = ~val2.u16 & 0xffff; break; case 32: val2.u32 = ~val2.u32; break; case 64: val2.u64 = ~val2.u64; break; default: panic(__func__); } } switch (v2.num_bits) { case 8: new.bits.u8 = (v1.bits.u8 & ~v2.bits.u8 & val2.u8) & 0xff; break; case 16: new.bits.u16 = (v1.bits.u16 & ~v2.bits.u16 & val2.u16) & 0xffff; break; case 32: new.bits.u32 = (v1.bits.u32 & ~v2.bits.u32 & val2.u32); break; case 64: new.bits.u64 = (v1.bits.u64 & ~v2.bits.u64 & val2.u64); break; default: panic(__func__); } return new; } /* Check the result of a binary operation. */ static void check_result_for_binary(const irop_t *op, const test_data_t *data) { const opnd_t *result = &data->result; const opnd_t *opnd1 = &data->opnds[0]; const opnd_t *opnd2 = &data->opnds[1]; vbits_t expected_vbits; /* Only handle those undef-kinds that actually occur. */ switch (op->undef_kind) { case UNDEF_NONE: expected_vbits = defined_vbits(result->vbits.num_bits); break; case UNDEF_ALL: expected_vbits = undefined_vbits(result->vbits.num_bits); break; case UNDEF_LEFT: // LEFT with respect to the leftmost 1-bit in both operands expected_vbits = left_vbits(or_vbits(opnd1->vbits, opnd2->vbits), result->vbits.num_bits); break; case UNDEF_SAME: assert(opnd1->vbits.num_bits == opnd2->vbits.num_bits); assert(opnd1->vbits.num_bits == result->vbits.num_bits); // SAME with respect to the 1-bits in both operands expected_vbits = or_vbits(opnd1->vbits, opnd2->vbits); break; case UNDEF_CONCAT: assert(opnd1->vbits.num_bits == opnd2->vbits.num_bits); assert(result->vbits.num_bits == 2 * opnd1->vbits.num_bits); expected_vbits = concat_vbits(opnd1->vbits, opnd2->vbits); break; case UNDEF_SHL: /* If any bit in the 2nd operand is undefined, so are all bits of the result. */ if (! completely_defined_vbits(opnd2->vbits)) { expected_vbits = undefined_vbits(result->vbits.num_bits); } else { assert(opnd2->vbits.num_bits == 8); unsigned shift_amount = opnd2->value.u8; expected_vbits = shl_vbits(opnd1->vbits, shift_amount); } break; case UNDEF_SHR: /* If any bit in the 2nd operand is undefined, so are all bits of the result. */ if (! completely_defined_vbits(opnd2->vbits)) { expected_vbits = undefined_vbits(result->vbits.num_bits); } else { assert(opnd2->vbits.num_bits == 8); unsigned shift_amount = opnd2->value.u8; expected_vbits = shr_vbits(opnd1->vbits, shift_amount); } break; case UNDEF_SAR: /* If any bit in the 2nd operand is undefined, so are all bits of the result. */ if (! completely_defined_vbits(opnd2->vbits)) { expected_vbits = undefined_vbits(result->vbits.num_bits); } else { assert(opnd2->vbits.num_bits == 8); unsigned shift_amount = opnd2->value.u8; expected_vbits = sar_vbits(opnd1->vbits, shift_amount); } break; case UNDEF_AND: { /* Let v1, v2 be the V-bits of the 1st and 2nd operand, respectively Let b1, b2 be the actual value of the 1st and 2nd operand, respect. And output bit is undefined (i.e. its V-bit == 1), iff (1) (v1 == 1) && (v2 == 1) OR (2) (v1 == 1) && (v2 == 0 && b2 == 1) OR (3) (v2 == 1) && (v1 == 0 && b1 == 1) */ vbits_t term1, term2, term3; term1 = and_vbits(opnd1->vbits, opnd2->vbits); term2 = and_combine(opnd1->vbits, opnd2->vbits, opnd2->value, 0); term3 = and_combine(opnd2->vbits, opnd1->vbits, opnd1->value, 0); expected_vbits = or_vbits(term1, or_vbits(term2, term3)); break; } case UNDEF_OR: { /* Let v1, v2 be the V-bits of the 1st and 2nd operand, respectively Let b1, b2 be the actual value of the 1st and 2nd operand, respect. And output bit is undefined (i.e. its V-bit == 1), iff (1) (v1 == 1) && (v2 == 1) OR (2) (v1 == 1) && (v2 == 0 && b2 == 0) OR (3) (v2 == 1) && (v1 == 0 && b1 == 0) */ vbits_t term1, term2, term3; term1 = and_vbits(opnd1->vbits, opnd2->vbits); term2 = and_combine(opnd1->vbits, opnd2->vbits, opnd2->value, 1); term3 = and_combine(opnd2->vbits, opnd1->vbits, opnd1->value, 1); expected_vbits = or_vbits(term1, or_vbits(term2, term3)); break; } case UNDEF_ORD: /* Set expected_vbits for the Iop_CmpORD category of iops. * If any of the input bits is undefined the least significant * three bits in the result will be set, i.e. 0xe. */ expected_vbits = cmpord_vbits(opnd1->vbits.num_bits, opnd2->vbits.num_bits); break; default: panic(__func__); } if (! equal_vbits(result->vbits, expected_vbits)) complain(op, data, expected_vbits); } static int test_shift(const irop_t *op, test_data_t *data) { unsigned num_input_bits, i; opnd_t *opnds = data->opnds; int tests_done = 0; /* When testing the 1st operand's undefinedness propagation, do so with all possible shift amnounts */ for (unsigned amount = 0; amount < bitsof_irtype(opnds[0].type); ++amount) { opnds[1].value.u8 = amount; // 1st (left) operand num_input_bits = bitsof_irtype(opnds[0].type); for (i = 0; i < num_input_bits; ++i) { opnds[0].vbits = onehot_vbits(i, bitsof_irtype(opnds[0].type)); opnds[1].vbits = defined_vbits(bitsof_irtype(opnds[1].type)); valgrind_execute_test(op, data); check_result_for_binary(op, data); tests_done++; } } // 2nd (right) operand /* If the operand is an immediate value, there are no v-bits to set. */ if (op->shift_amount_is_immediate) return tests_done; num_input_bits = bitsof_irtype(opnds[1].type); for (i = 0; i < num_input_bits; ++i) { opnds[0].vbits = defined_vbits(bitsof_irtype(opnds[0].type)); opnds[1].vbits = onehot_vbits(i, bitsof_irtype(opnds[1].type)); valgrind_execute_test(op, data); check_result_for_binary(op, data); tests_done++; } return tests_done; } static value_t all_bits_zero_value(unsigned num_bits) { value_t val; switch (num_bits) { case 8: val.u8 = 0; break; case 16: val.u16 = 0; break; case 32: val.u32 = 0; break; case 64: val.u64 = 0; break; default: panic(__func__); } return val; } static value_t all_bits_one_value(unsigned num_bits) { value_t val; switch (num_bits) { case 8: val.u8 = 0xff; break; case 16: val.u16 = 0xffff; break; case 32: val.u32 = ~0u; break; case 64: val.u64 = ~0ull; break; default: panic(__func__); } return val; } static int test_and(const irop_t *op, test_data_t *data) { unsigned num_input_bits, bitpos; opnd_t *opnds = data->opnds; int tests_done = 0; /* Undefinedness does not propagate if the other operand is 0. Use an all-bits-zero operand and test the other operand in the usual way (one bit undefined at a time). */ // 1st (left) operand variable, 2nd operand all-bits-zero num_input_bits = bitsof_irtype(opnds[0].type); for (bitpos = 0; bitpos < num_input_bits; ++bitpos) { opnds[0].vbits = onehot_vbits(bitpos, bitsof_irtype(opnds[0].type)); opnds[1].vbits = defined_vbits(bitsof_irtype(opnds[1].type)); opnds[1].value = all_bits_zero_value(bitsof_irtype(opnds[1].type)); valgrind_execute_test(op, data); check_result_for_binary(op, data); tests_done++; } // 2nd (right) operand variable, 1st operand all-bits-zero num_input_bits = bitsof_irtype(opnds[1].type); for (bitpos = 0; bitpos < num_input_bits; ++bitpos) { opnds[1].vbits = onehot_vbits(bitpos, bitsof_irtype(opnds[1].type)); opnds[0].vbits = defined_vbits(bitsof_irtype(opnds[0].type)); opnds[0].value = all_bits_zero_value(bitsof_irtype(opnds[0].type)); valgrind_execute_test(op, data); check_result_for_binary(op, data); tests_done++; } /* Undefinedness propagates if the other operand is 1. Use an all-bits-one operand and test the other operand in the usual way (one bit undefined at a time). */ // 1st (left) operand variable, 2nd operand all-bits-one num_input_bits = bitsof_irtype(opnds[0].type); for (bitpos = 0; bitpos < num_input_bits; ++bitpos) { opnds[0].vbits = onehot_vbits(bitpos, bitsof_irtype(opnds[0].type)); opnds[1].vbits = defined_vbits(bitsof_irtype(opnds[1].type)); opnds[1].value = all_bits_one_value(bitsof_irtype(opnds[1].type)); valgrind_execute_test(op, data); check_result_for_binary(op, data); tests_done++; } // 2nd (right) operand variable, 1st operand all-bits-one num_input_bits = bitsof_irtype(opnds[1].type); for (bitpos = 0; bitpos < num_input_bits; ++bitpos) { opnds[1].vbits = onehot_vbits(bitpos, bitsof_irtype(opnds[1].type)); opnds[0].vbits = defined_vbits(bitsof_irtype(opnds[0].type)); opnds[0].value = all_bits_one_value(bitsof_irtype(opnds[0].type)); valgrind_execute_test(op, data); check_result_for_binary(op, data); tests_done++; } return tests_done; } static int test_or(const irop_t *op, test_data_t *data) { unsigned num_input_bits, bitpos; opnd_t *opnds = data->opnds; int tests_done = 0; /* Undefinedness does not propagate if the other operand is 1. Use an all-bits-one operand and test the other operand in the usual way (one bit undefined at a time). */ // 1st (left) operand variable, 2nd operand all-bits-one num_input_bits = bitsof_irtype(opnds[0].type); opnds[0].vbits = defined_vbits(bitsof_irtype(opnds[0].type)); opnds[1].vbits = defined_vbits(bitsof_irtype(opnds[1].type)); opnds[1].value = all_bits_one_value(bitsof_irtype(opnds[1].type)); for (bitpos = 0; bitpos < num_input_bits; ++bitpos) { opnds[0].vbits = onehot_vbits(bitpos, bitsof_irtype(opnds[0].type)); valgrind_execute_test(op, data); check_result_for_binary(op, data); tests_done++; } // 2nd (right) operand variable, 1st operand all-bits-one num_input_bits = bitsof_irtype(opnds[1].type); opnds[0].vbits = defined_vbits(bitsof_irtype(opnds[0].type)); opnds[1].vbits = defined_vbits(bitsof_irtype(opnds[1].type)); opnds[0].value = all_bits_one_value(bitsof_irtype(opnds[0].type)); for (bitpos = 0; bitpos < num_input_bits; ++bitpos) { opnds[1].vbits = onehot_vbits(bitpos, bitsof_irtype(opnds[1].type)); valgrind_execute_test(op, data); check_result_for_binary(op, data); tests_done++; } /* Undefinedness propagates if the other operand is 0. Use an all-bits-zero operand and test the other operand in the usual way (one bit undefined at a time). */ // 1st (left) operand variable, 2nd operand all-bits-zero num_input_bits = bitsof_irtype(opnds[0].type); opnds[0].vbits = defined_vbits(bitsof_irtype(opnds[0].type)); opnds[1].vbits = defined_vbits(bitsof_irtype(opnds[1].type)); opnds[1].value = all_bits_zero_value(bitsof_irtype(opnds[1].type)); for (bitpos = 0; bitpos < num_input_bits; ++bitpos) { opnds[0].vbits = onehot_vbits(bitpos, bitsof_irtype(opnds[0].type)); valgrind_execute_test(op, data); check_result_for_binary(op, data); tests_done++; } // 2nd (right) operand variable, 1st operand all-bits-zero num_input_bits = bitsof_irtype(opnds[1].type); opnds[0].vbits = defined_vbits(bitsof_irtype(opnds[0].type)); opnds[1].vbits = defined_vbits(bitsof_irtype(opnds[1].type)); opnds[0].value = all_bits_zero_value(bitsof_irtype(opnds[0].type)); for (bitpos = 0; bitpos < num_input_bits; ++bitpos) { opnds[1].vbits = onehot_vbits(bitpos, bitsof_irtype(opnds[1].type)); valgrind_execute_test(op, data); check_result_for_binary(op, data); tests_done++; } return tests_done; } int test_binary_op(const irop_t *op, test_data_t *data) { unsigned num_input_bits, i, bitpos; opnd_t *opnds = data->opnds; int tests_done = 0; /* Handle special cases upfront */ switch (op->undef_kind) { case UNDEF_SHL: case UNDEF_SHR: case UNDEF_SAR: return test_shift(op, data); case UNDEF_AND: return test_and(op, data); case UNDEF_OR: return test_or(op, data); default: break; } /* For each operand, set a single bit to undefined and observe how that propagates to the output. Do this for all bits in each operand. */ for (i = 0; i < 2; ++i) { /* If this is a shift op that requires an immediate shift amount, do not iterate the v-bits of the 2nd operand */ if (i == 1 && op->shift_amount_is_immediate) break; num_input_bits = bitsof_irtype(opnds[i].type); opnds[0].vbits = defined_vbits(bitsof_irtype(opnds[0].type)); opnds[1].vbits = defined_vbits(bitsof_irtype(opnds[1].type)); /* Set the value of the 2nd operand to something != 0. So division won't crash. */ memset(&opnds[1].value, 0xff, sizeof opnds[1].value); /* For immediate shift amounts choose a value of '1'. That value should not cause a problem. Note: we always assign to the u64 member here. The reason is that in ir_inject.c the value_t type is not visible. The value is picked up there by interpreting the memory as an ULong value. So, we rely on union { ULong v1; // value picked up in ir_inject.c value_t v2; // value assigned here } xx; assert(sizeof xx.v1 == sizeof xx.v2.u64); assert(xx.v1 == xx.v2.u64); */ if (op->shift_amount_is_immediate) opnds[1].value.u64 = 1; for (bitpos = 0; bitpos < num_input_bits; ++bitpos) { opnds[i].vbits = onehot_vbits(bitpos, bitsof_irtype(opnds[i].type)); valgrind_execute_test(op, data); check_result_for_binary(op, data); tests_done++; } } return tests_done; }