#include "config.h"
#include "system.h"
#include "rtl.h"
#include "flags.h"
#include "obstack.h"
#include "regs.h"
#include "basic-block.h"
static struct obstack bitmap_obstack;
static int bitmap_obstack_init = FALSE;
#ifndef INLINE
#ifndef __GNUC__
#define INLINE
#else
#define INLINE __inline__
#endif
#endif
bitmap_element bitmap_zero;
bitmap_element *bitmap_free;
static void bitmap_element_free PROTO((bitmap, bitmap_element *));
static bitmap_element *bitmap_element_allocate PROTO((void));
static int bitmap_element_zerop PROTO((bitmap_element *));
static void bitmap_element_link PROTO((bitmap, bitmap_element *));
static bitmap_element *bitmap_find_bit PROTO((bitmap, unsigned int));
static INLINE void
bitmap_element_free (head, elt)
bitmap head;
bitmap_element *elt;
{
bitmap_element *next = elt->next;
bitmap_element *prev = elt->prev;
if (prev)
prev->next = next;
if (next)
next->prev = prev;
if (head->first == elt)
head->first = next;
if (head->current == elt)
head->current = next != 0 ? next : prev;
elt->next = bitmap_free;
bitmap_free = elt;
}
static INLINE bitmap_element *
bitmap_element_allocate ()
{
bitmap_element *element;
#if BITMAP_ELEMENT_WORDS != 2
int i;
#endif
if (bitmap_free != 0)
{
element = bitmap_free;
bitmap_free = element->next;
}
else
{
if (!bitmap_obstack_init)
{
bitmap_obstack_init = TRUE;
#ifndef OBSTACK_CHUNK_SIZE
#define OBSTACK_CHUNK_SIZE 0
#endif
#ifndef OBSTACK_CHUNK_ALLOC
#define OBSTACK_CHUNK_ALLOC xmalloc
#endif
#ifndef OBSTACK_CHUNK_FREE
#define OBSTACK_CHUNK_FREE free
#endif
#if !defined(__GNUC__) || (__GNUC__ < 2)
#define __alignof__(type) 0
#endif
obstack_specify_allocation (&bitmap_obstack, OBSTACK_CHUNK_SIZE,
__alignof__ (bitmap_element),
(void *(*) ()) OBSTACK_CHUNK_ALLOC,
(void (*) ()) OBSTACK_CHUNK_FREE);
}
element = (bitmap_element *) obstack_alloc (&bitmap_obstack,
sizeof (bitmap_element));
}
#if BITMAP_ELEMENT_WORDS == 2
element->bits[0] = element->bits[1] = 0;
#else
for (i = 0; i < BITMAP_ELEMENT_WORDS; i++)
element->bits[i] = 0;
#endif
return element;
}
static INLINE int
bitmap_element_zerop (element)
bitmap_element *element;
{
#if BITMAP_ELEMENT_WORDS == 2
return (element->bits[0] | element->bits[1]) == 0;
#else
int i;
for (i = 0; i < BITMAP_ELEMENT_WORDS; i++)
if (element->bits[i] != 0)
return 0;
return 1;
#endif
}
static INLINE void
bitmap_element_link (head, element)
bitmap head;
bitmap_element *element;
{
unsigned int indx = element->indx;
bitmap_element *ptr;
if (head->first == 0)
{
element->next = element->prev = 0;
head->first = element;
}
else if (indx < head->indx)
{
for (ptr = head->current;
ptr->prev != 0 && ptr->prev->indx > indx;
ptr = ptr->prev)
;
if (ptr->prev)
ptr->prev->next = element;
else
head->first = element;
element->prev = ptr->prev;
element->next = ptr;
ptr->prev = element;
}
else
{
for (ptr = head->current;
ptr->next != 0 && ptr->next->indx < indx;
ptr = ptr->next)
;
if (ptr->next)
ptr->next->prev = element;
element->next = ptr->next;
element->prev = ptr;
ptr->next = element;
}
head->current = element;
head->indx = indx;
}
INLINE void
bitmap_clear (head)
bitmap head;
{
bitmap_element *element, *next;
for (element = head->first; element != 0; element = next)
{
next = element->next;
element->next = bitmap_free;
bitmap_free = element;
}
head->first = head->current = 0;
}
void
bitmap_copy (to, from)
bitmap to;
bitmap from;
{
bitmap_element *from_ptr, *to_ptr = 0;
#if BITMAP_ELEMENT_WORDS != 2
int i;
#endif
bitmap_clear (to);
for (from_ptr = from->first; from_ptr; from_ptr = from_ptr->next)
{
bitmap_element *to_elt = bitmap_element_allocate ();
to_elt->indx = from_ptr->indx;
#if BITMAP_ELEMENT_WORDS == 2
to_elt->bits[0] = from_ptr->bits[0];
to_elt->bits[1] = from_ptr->bits[1];
#else
for (i = 0; i < BITMAP_ELEMENT_WORDS; i++)
to_elt->bits[i] = from_ptr->bits[i];
#endif
if (to_ptr == 0)
{
to->first = to->current = to_elt;
to->indx = from_ptr->indx;
to_elt->next = to_elt->prev = 0;
}
else
{
to_elt->prev = to_ptr;
to_elt->next = 0;
to_ptr->next = to_elt;
}
to_ptr = to_elt;
}
}
static INLINE bitmap_element *
bitmap_find_bit (head, bit)
bitmap head;
unsigned int bit;
{
bitmap_element *element;
unsigned HOST_WIDE_INT indx = bit / BITMAP_ELEMENT_ALL_BITS;
if (head->current == 0)
return 0;
if (head->indx > indx)
for (element = head->current;
element->prev != 0 && element->indx > indx;
element = element->prev)
;
else
for (element = head->current;
element->next != 0 && element->indx < indx;
element = element->next)
;
head->current = element;
head->indx = element->indx;
if (element != 0 && element->indx != indx)
element = 0;
return element;
}
void
bitmap_clear_bit (head, bit)
bitmap head;
int bit;
{
bitmap_element *ptr = bitmap_find_bit (head, bit);
if (ptr != 0)
{
unsigned bit_num = bit % (unsigned) HOST_BITS_PER_WIDE_INT;
unsigned word_num = ((bit / (unsigned) HOST_BITS_PER_WIDE_INT)
% BITMAP_ELEMENT_WORDS);
ptr->bits[word_num] &= ~ (((unsigned HOST_WIDE_INT) 1) << bit_num);
if (bitmap_element_zerop (ptr))
bitmap_element_free (head, ptr);
}
}
void
bitmap_set_bit (head, bit)
bitmap head;
int bit;
{
bitmap_element *ptr = bitmap_find_bit (head, bit);
unsigned word_num
= ((bit / (unsigned) HOST_BITS_PER_WIDE_INT) % BITMAP_ELEMENT_WORDS);
unsigned bit_num = bit % (unsigned) HOST_BITS_PER_WIDE_INT;
unsigned HOST_WIDE_INT bit_val = ((unsigned HOST_WIDE_INT) 1) << bit_num;
if (ptr == 0)
{
ptr = bitmap_element_allocate ();
ptr->indx = bit / BITMAP_ELEMENT_ALL_BITS;
ptr->bits[word_num] = bit_val;
bitmap_element_link (head, ptr);
}
else
ptr->bits[word_num] |= bit_val;
}
int
bitmap_bit_p (head, bit)
bitmap head;
int bit;
{
bitmap_element *ptr;
unsigned bit_num;
unsigned word_num;
ptr = bitmap_find_bit (head, bit);
if (ptr == 0)
return 0;
bit_num = bit % (unsigned) HOST_BITS_PER_WIDE_INT;
word_num
= ((bit / (unsigned) HOST_BITS_PER_WIDE_INT) % BITMAP_ELEMENT_WORDS);
return
(ptr->bits[word_num] & (((unsigned HOST_WIDE_INT) 1) << bit_num)) != 0;
}
void
bitmap_operation (to, from1, from2, operation)
bitmap to;
bitmap from1;
bitmap from2;
enum bitmap_bits operation;
{
bitmap_element *delete_list = 0;
bitmap_element *from1_ptr = from1->first;
bitmap_element *from2_ptr = from2->first;
unsigned int indx1
= (from1_ptr) ? from1_ptr->indx : ~ (unsigned HOST_WIDE_INT) 0;
unsigned int indx2
= (from2_ptr) ? from2_ptr->indx : ~ (unsigned HOST_WIDE_INT) 0;
bitmap_element *to_ptr = 0;
bitmap_element *from1_tmp;
bitmap_element *from2_tmp;
unsigned int indx;
#if BITMAP_ELEMENT_WORDS != 2
int i;
#endif
if (to == from1 || to == from2)
{
delete_list = to->first;
to->first = to->current = 0;
}
else
bitmap_clear (to);
while (from1_ptr != 0 || from2_ptr != 0)
{
if (indx1 == indx2)
{
indx = indx1;
from1_tmp = from1_ptr;
from2_tmp = from2_ptr;
from1_ptr = from1_ptr->next;
indx1 = (from1_ptr) ? from1_ptr->indx : ~ (unsigned HOST_WIDE_INT) 0;
from2_ptr = from2_ptr->next;
indx2 = (from2_ptr) ? from2_ptr->indx : ~ (unsigned HOST_WIDE_INT) 0;
}
else if (indx1 < indx2)
{
indx = indx1;
from1_tmp = from1_ptr;
from2_tmp = &bitmap_zero;
from1_ptr = from1_ptr->next;
indx1 = (from1_ptr) ? from1_ptr->indx : ~ (unsigned HOST_WIDE_INT) 0;
}
else
{
indx = indx2;
from1_tmp = &bitmap_zero;
from2_tmp = from2_ptr;
from2_ptr = from2_ptr->next;
indx2 = (from2_ptr) ? from2_ptr->indx : ~ (unsigned HOST_WIDE_INT) 0;
}
if (to_ptr == 0)
to_ptr = bitmap_element_allocate ();
switch (operation)
{
default:
abort ();
case BITMAP_AND:
#if BITMAP_ELEMENT_WORDS == 2
to_ptr->bits[0] = from1_tmp->bits[0] & from2_tmp->bits[0];
to_ptr->bits[1] = from1_tmp->bits[1] & from2_tmp->bits[1];
#else
for (i = BITMAP_ELEMENT_WORDS - 1; i >= 0; i--)
to_ptr->bits[i] = from1_tmp->bits[i] & from2_tmp->bits[i];
#endif
break;
case BITMAP_AND_COMPL:
#if BITMAP_ELEMENT_WORDS == 2
to_ptr->bits[0] = from1_tmp->bits[0] & ~ from2_tmp->bits[0];
to_ptr->bits[1] = from1_tmp->bits[1] & ~ from2_tmp->bits[1];
#else
for (i = BITMAP_ELEMENT_WORDS - 1; i >= 0; i--)
to_ptr->bits[i] = from1_tmp->bits[i] & ~ from2_tmp->bits[i];
#endif
break;
case BITMAP_IOR:
#if BITMAP_ELEMENT_WORDS == 2
to_ptr->bits[0] = from1_tmp->bits[0] | from2_tmp->bits[0];
to_ptr->bits[1] = from1_tmp->bits[1] | from2_tmp->bits[1];
#else
for (i = BITMAP_ELEMENT_WORDS - 1; i >= 0; i--)
to_ptr->bits[i] = from1_tmp->bits[i] | from2_tmp->bits[i];
#endif
break;
}
if (! bitmap_element_zerop (to_ptr))
{
to_ptr->indx = indx;
bitmap_element_link (to, to_ptr);
to_ptr = 0;
}
}
if (to_ptr != 0)
{
to_ptr->next = bitmap_free;
bitmap_free = to_ptr;
}
for (; delete_list != 0; delete_list = to_ptr)
{
to_ptr = delete_list->next;
delete_list->next = bitmap_free;
bitmap_free = delete_list;
}
}
void
bitmap_ior_and_compl (to, from1, from2)
bitmap to;
bitmap from1;
bitmap from2;
{
bitmap_head tmp;
tmp.first = tmp.current = 0;
bitmap_operation (&tmp, from1, from2, BITMAP_AND_COMPL);
bitmap_operation (to, to, &tmp, BITMAP_IOR);
bitmap_clear (&tmp);
}
bitmap
bitmap_initialize (head)
bitmap head;
{
head->first = head->current = 0;
return head;
}
void
bitmap_debug_file (file, head)
FILE *file;
bitmap head;
{
bitmap_element *ptr;
fprintf (file, "\nfirst = ");
fprintf (file, HOST_PTR_PRINTF, head->first);
fprintf (file, " current = ");
fprintf (file, HOST_PTR_PRINTF, head->current);
fprintf (file, " indx = %u\n", head->indx);
for (ptr = head->first; ptr; ptr = ptr->next)
{
int i, j, col = 26;
fprintf (file, "\t");
fprintf (file, HOST_PTR_PRINTF, ptr);
fprintf (file, " next = ");
fprintf (file, HOST_PTR_PRINTF, ptr->next);
fprintf (file, " prev = ");
fprintf (file, HOST_PTR_PRINTF, ptr->prev);
fprintf (file, " indx = %u\n\t\tbits = {", ptr->indx);
for (i = 0; i < BITMAP_ELEMENT_WORDS; i++)
for (j = 0; j < HOST_BITS_PER_WIDE_INT; j++)
if ((ptr->bits[i] & (((unsigned HOST_WIDE_INT) 1) << j)) != 0)
{
if (col > 70)
{
fprintf (file, "\n\t\t\t");
col = 24;
}
fprintf (file, " %u", (ptr->indx * BITMAP_ELEMENT_ALL_BITS
+ i * HOST_BITS_PER_WIDE_INT + j));
col += 4;
}
fprintf (file, " }\n");
}
}
void
debug_bitmap (head)
bitmap head;
{
bitmap_debug_file (stdout, head);
}
void
bitmap_print (file, head, prefix, suffix)
FILE *file;
bitmap head;
const char *prefix;
const char *suffix;
{
const char *comma = "";
int i;
fputs (prefix, file);
EXECUTE_IF_SET_IN_BITMAP (head, 0, i,
{
fprintf (file, "%s%d", comma, i);
comma = ", ";
});
fputs (suffix, file);
}
void
bitmap_release_memory ()
{
bitmap_free = 0;
if (bitmap_obstack_init)
{
bitmap_obstack_init = FALSE;
obstack_free (&bitmap_obstack, NULL_PTR);
}
}