adamj%WEB.Berkeley.EDU@LILAC.BERKELEY.EDU (03/26/89)
/***************************************************************************
void GarbageCollect (void)
void SetBitMark (Bit *bit, bool mark_value)
Bit *GenPrimitiveBit (void)
Bit *GenCompositeBit (Bit *left, Bit *right)
Bit *GenNand (Bit *left, Bit *right)
Bit *GenNot (Bit *bit)
Bit *GenAnd (Bit *bit1, Bit *bit2)
Bit *GenOr (Bit *bit1, Bit *bit2)
Bit *GenNor (Bit *bit1, Bit *bit2)
Bit *GenXor (Bit *bit1, Bit *bit2)
Bit *GenConstantBit (bool value)
Bit *Build_Mask_Table_Expr (int *mask_table,
Bit **input_vector,
int input_vector_size,
int output_bit)
void Initialize_Bits (void)
bool Get_Constant_Bit_Value (Bit *bit)
void InvalidateAllBits (void)
void EvaluateBit (Bit *bit)
***************************************************************************/
#include "bits.h"
#include "utils.h"
#define max(x,y) (((x) > (y)) ? (x) : (y))
static Bit *chain_start = (Bit*) 0;
static Bit *TrueBit, *FalseBit;
static unsigned int num_bits_generated = 0;
static unsigned int num_bits_matched = 0;
/* static unsigned int num_patterns_recognized = 0; */
void
GarbageCollect (void)
{
Bit **pBit = &chain_start;
unsigned int count = 0;
unsigned int kill_count = 0;
FalseBit->mark = TRUE;
TrueBit->mark = TRUE;
while (*pBit) {
Bit *bit = *pBit;
count++;
if (bit->mark) {
pBit = &bit->chain;
bit->mark = FALSE;
}
else
{
*pBit = bit->chain;
if (bit->left) {
/* Remove this node from the doubly linked
"parents with the same left child" list.
Also, if we're at the head of the list, then
the child should point to the next node along
the line (which might be NULL).
*/
if (bit->same_left_node_forward)
bit->same_left_node_forward->
same_left_node_back =
bit->same_left_node_back;
if (bit->same_left_node_back)
bit->same_left_node_back->
same_left_node_forward =
bit->same_left_node_forward;
else
bit->left->parent =
bit->same_left_node_forward;
}
free (bit);
kill_count++;
}
}
printf ("Garbage collection freed %d of %d bits (%d remain).\n",
kill_count, count, count - kill_count);
printf ("%d bits matched.\n", num_bits_matched);
num_bits_matched = 0;
/* printf ("%d patterns recognized.\n", num_patterns_recognized); */
}
void
SetBitMark (Bit *bit, bool mark_value)
{
if (!bit || bit->mark == mark_value) return;
bit->mark = mark_value;
SetBitMark (bit->left, mark_value);
SetBitMark (bit->right, mark_value);
}
Bit *
GenPrimitiveBit (void)
{
Bit *result = (Bit*) malloc (sizeof (Bit));
if (!result) FatalError ("GenBit: malloc failed");
/* Used for garbage collection. */
result->mark = FALSE;
result->chain = chain_start;
chain_start = result;
/* Since this is a new bit, it doesn't have a parent yet. */
result->parent = (Bit*) 0;
result->left = (Bit*) 0;
result->right = (Bit*) 0;
result->height = 0;
#ifdef notdef
if (++num_bits_generated % 1000 == 0)
printf ("%d bits generated.\n", num_bits_generated);
#endif
return result;
}
static inline bool
IsInversion (Bit *bit)
{
return bit->left == bit->right && bit->left;
}
Bit *
GenCompositeBit (Bit *left, Bit *right)
{
Bit *result;
if (left == FalseBit || right == FalseBit) return TrueBit;
if (left == TrueBit)
left = right;
else if (right == TrueBit)
right = left;
/* Force ((x.x).(x.x)) to return x. I.e., if the left and right
sides are identical, and both sides of these identical children
are identical and non-null, then return the child's child. */
if (left == right && left->left == left->right && left->left)
return left->left;
/* We rotate the tree so that we can gaurantee that at least
one of the children will not be an inversion. Hopefully,
this will produce more lopsided trees.
The identity involved is:
x AND (y AND z) == (x AND y) AND z
AND(x,AND(y,z)) == AND(AND(x,y),z)
~AND(x,AND(y,z)) == ~AND(AND(x,y),z)
NAND(x,AND(y,z)) == NAND(AND(x,y),z)
NAND(x,NOT(NAND(y,z))) == NAND(NOT(NAND(x,y),z))
*/
while (IsInversion(right)) {
Bit *not_an_inversion, *maybe_an_inversion;
if (IsInversion(right->right)) {
not_an_inversion = right->left;
maybe_an_inversion = right->right;
}
else {
not_an_inversion = right->right;
maybe_an_inversion = right->left;
}
left = GenNot(GenNand(left,not_an_inversion));
right = maybe_an_inversion;
}
/* Put the deeper subtree on the left. If both subtrees are of equal
depth, then make the one with the lower numerical address the one
on the left. */
if (left->height < right->height ||
(left->height == right->height &&
(unsigned long) left < (unsigned long) right)) {
Bit *temp = left;
left = right;
right = temp;
}
/* Recognize NAND(NOT(x),x) --> TRUE. */
if (left->left == left->right && left->left == right) {
/* num_patterns_recognized++; */
printf ("foo\n");
return TrueBit;
}
/* Find out if we've already created a bit with the same children. */
result = left->parent;
while (result) {
if (result->left != left)
FatalError ("GenComposite: Left child doesn't match");
if (result->right == right) {
num_bits_matched++;
return result; /* Found a match! */
}
result = result->same_left_node_forward;
}
/* Now, we know we've got to create a new bit. Allocate the
storage for it. */
result = GenPrimitiveBit ();
/* Fill in the children. */
result->left = left;
result->right = right;
/* Calculate the height of the current tree. Since the left
side is at least as tall as the right side, we know that:
max(left->height,right->height) == left->height.
*/
result->height = left->height + 1;
result->computed = FALSE;
/* Put ourselves at the head of a doubly-linked list of nodes
with the same left child. */
result->same_left_node_forward = left->parent;
result->same_left_node_back = (Bit*) 0;
if (left->parent) left->parent->same_left_node_back = result;
left->parent = result;
return result;
}
Bit *
GenNand (Bit *left, Bit *right)
{
return GenCompositeBit( left, right );
}
Bit *
GenNot (Bit *bit)
{
return GenNand ( bit, bit );
}
Bit *
GenAnd (Bit *bit1, Bit *bit2)
{
if (!bit1) return bit2;
if (!bit2) return bit1;
return GenNot(GenNand( bit1, bit2));
}
Bit *
GenOr (Bit *bit1, Bit *bit2)
{
if (!bit1) return bit2;
if (!bit2) return bit1;
return GenNand(GenNot(bit1), GenNot(bit2));
}
Bit *
GenNor (Bit *bit1, Bit *bit2)
{
return GenNot(GenOr(bit1, bit2));
}
Bit *
GenXor (Bit *bit1, Bit *bit2)
{
#ifdef notdef
bool inverted = FALSE;
if (bit1->left == bit1->right && bit1->left) {
inverted = !inverted;
bit1 = bit1->left;
}
if (bit2->left == bit2->right && bit2->left) {
inverted = !inverted;
bit2 = bit2->left;
}
if (inverted)
return GenNand(GenNand(bit1, bit2),GenOr(bit1, bit2));
else
return GenAnd(GenNand(bit1, bit2),GenOr(bit1, bit2));
return GenOr(GenAnd(GenNot(bit1),bit2),
GenAnd(GenNot(bit2),bit1));
#endif
return GenNand(GenNand(GenNot(bit1),bit2),
GenNand(GenNot(bit2),bit1));
}
Bit *GenConstantBit (bool value)
{
if (value)
return TrueBit;
else
return FalseBit;
}
/**********************************************************************
Build an expression describing the given bit configuration.
Bit mask is little-endian, i.e.,
input_vector[0] is for bit mask 0x1.
input_vector[1] is for bit mask 0x2.
input_vector[2] is for bit mask 0x4.
input_vector[3] is for bit mask 0x8.
etc., etc.
E.g.,
10010 --> x4~x3~x2x1~x0
**********************************************************************/
static Bit *
Build_Mask_Expr (int mask, int relevant_bits,
Bit **input_vector,
int vector_size)
{
int i;
Bit *result = (Bit*) 0;
unsigned int num_factors = 0;
Bit *factors[vector_size];
for (i = 0 ; i < vector_size; i++) {
const int bit_mask = 1 << i;
if (relevant_bits & bit_mask)
factors[num_factors++] = (mask & bit_mask) ?
input_vector[i] : GenNot (input_vector[i]);
}
/* Sort the factors so that the tallest ones will be at the
bottom of the tree. This, hopefully, should produce more
lopsided trees. */
while (num_factors) {
unsigned int tallest_factor = 0;
for (i = 1; i < num_factors; i++) {
if (factors[i]->height > factors[tallest_factor]->height)
tallest_factor = i;
}
result = GenAnd (result, factors[tallest_factor]);
factors[tallest_factor] = factors[--num_factors];
}
return result;
}
/**********************************************************************
TestCombinations: returns TRUE if for every i which matches the
relevant_bits of input, that input turns on the corresponding bit
in output_mask, according to the input/output mask_table. Use_table
is also updated.
**********************************************************************/
static inline bool
TestCombinations (int input, int relevant_bits,
int *mask_table, bool *use_table, int table_size,
int output_mask)
{
unsigned int i;
input &= relevant_bits;
for (i = 0; i < table_size; i++)
if (((i & relevant_bits) == input) && !(mask_table[i] & output_mask))
return FALSE;
for (i = 0; i < table_size; i++)
if ((i & relevant_bits) == input)
use_table[i] = TRUE;
return TRUE;
}
/**********************************************************************
Given an integer vector of masks, generate a sum-of-products
bit representation for each the output bit given in "output_bit."
**********************************************************************/
Bit *
Build_Mask_Table_Expr (int *mask_table,
Bit **input_vector,
int input_vector_size,
int output_bit)
{
int cur_input;
int num_ones = 0;
int output_mask = 1 << output_bit;
int above_max_input = 1<<input_vector_size;
Bit *result = (Bit*) 0;
int cur_output_bit = 0;
bool use_table[above_max_input];
unsigned int i;
unsigned int num_terms = 0;
Bit *terms[above_max_input];
for (cur_input = 0; cur_input < above_max_input; cur_input++) {
use_table[cur_input] = FALSE;
if (mask_table[cur_input] & output_mask) num_ones++;
}
for (cur_input = 0; cur_input < above_max_input; cur_input++) {
/* Now build the factor corresponding to the relevant_bits
of cur_input. */
if ((mask_table[cur_input] & output_mask) &&
!use_table[cur_input]) {
int relevant_bits = above_max_input - 1;
/* Attempt to minimize the factor. E.g., Ax + A~x --> A. */
for (i = 0; i < input_vector_size; i++) {
if (TestCombinations (cur_input, relevant_bits & ~(1<<i),
mask_table, use_table,
above_max_input, output_mask))
relevant_bits &= ~(1 << i);
}
terms[num_terms++] =
Build_Mask_Expr (cur_input, relevant_bits,
input_vector,
input_vector_size);
} /* if mask_table... && !use_table... */
} /* for cur_input = 0..above_max_input-1 */
while (num_terms) {
unsigned int tallest_term = 0;
for (i = 1; i < num_terms; i++) {
if (terms[i]->height > terms[tallest_term]->height)
tallest_term = i;
}
result = GenOr (result, terms[tallest_term]);
terms[tallest_term] = terms[--num_terms];
}
return result;
}
void
Initialize_Bits (void)
{
Bit *temp_FalseBit = GenPrimitiveBit ();
FalseBit = TrueBit = (Bit*) 0;
TrueBit = GenNot (temp_FalseBit);
SetBitValue (TrueBit, TRUE);
FalseBit = temp_FalseBit;
SetBitValue (FalseBit, FALSE);
}
bool
Get_Constant_Bit_Value (Bit *bit)
{
if (bit == FalseBit)
return FALSE;
else if (bit == TrueBit)
return TRUE;
else
FatalError ("Constant bit is neither TRUE nor FALSE.\n");
}
/*********************************************************************
void EvaluateBit (Bit *bit)
a b
TRUE 0 1
FALSE 1 x
UNKNOWN 0 0
**********************************************************************/
void
EvaluateBit (Bit *bit)
{
if (bit->computed) return;
if (!bit->left || !bit->right)
FatalError ("Uncalculated primitive bit");
EvaluateBit (bit->left);
EvaluateBit (bit->right);
bit->a = bit->left->b & bit->right->b &
~(bit->b = bit->left->a | bit->right->a);
if (!bit->a && !bit->b)
FatalError ("Lost information in calculating bit value");
bit->computed = TRUE;
}
void
InvalidateAllBits (void)
{
Bit *bit = chain_start;
while (bit) {
bit->computed = FALSE;
bit = bit->chain;
}
SetBitValue (TrueBit, TRUE);
SetBitValue (FalseBit, FALSE);
}
void
SetBitValue (Bit *bit, bool value)
{
if (value) {
bit->a = 0;
bit->b = ~0;
}
else
bit->a = ~0;
bit->computed = TRUE;
}
bool
GetBitValue (Bit *bit)
{
if (!bit->a && !bit->b)
FatalError ("Unknown bit value");
return ! bit->a;
}