/* -*- 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;
}