bitmap.c

GCC编译器源代码

/* Functions to support general ended bitmaps.
   Copyright (C) 1997 Free Software Foundation, Inc.

This file is part of GNU CC.

GNU CC 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, or (at your option)
any later version.

GNU CC 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 GNU CC; see the file COPYING.  If not, write to
the Free Software Foundation, 59 Temple Place - Suite 330,
Boston, MA 02111-1307, USA.  */

#include "config.h"
#include <stdio.h>
#include "rtl.h"
#include "flags.h"
#include "obstack.h"
#include "regs.h"
#include "basic-block.h"

#ifdef HAVE_STDLIB_H
#include <stdlib.h>
#endif

#ifdef NEED_DECLARATION_FREE
extern void free PROTO((void *));
#endif

/* Obstack to allocate bitmap elements from.  */
static struct obstack bitmap_obstack;
static int bitmap_obstack_init = FALSE;


#ifndef INLINE
#ifndef __GNUC__
#define INLINE
#else
#define INLINE __inline__
#endif
#endif

/* Global data */
bitmap_element bitmap_zero;		/* An element of all zero bits. */
bitmap_element *bitmap_free;		/* Freelist of bitmap elements. */

static void bitmap_element_free		PROTO((bitmap, bitmap_element *));
static bitmap_element *bitmap_element_allocate PROTO((bitmap));
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));

/* Free a bitmap element */

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;

  /* Since the first thing we try is to insert before current,
     make current the next entry in preference to the previous.  */
  if (head->current == elt)
    head->current = next != 0 ? next : prev;

  elt->next = bitmap_free;
  bitmap_free = elt;
}

/* Allocate a bitmap element.  The bits are cleared, but nothing else is.  */

static INLINE bitmap_element *
bitmap_element_allocate (head)
     bitmap head;
{
  bitmap_element *element;
  int i;

  if (bitmap_free != 0)
    {
      element = bitmap_free;
      bitmap_free = element->next;
    }
  else
    {
      /* We can't use gcc_obstack_init to initialize the obstack since
	 print-rtl.c now calls bitmap functions, and bitmap is linked
	 into the gen* functions.  */
      if (!bitmap_obstack_init)
	{
	  bitmap_obstack_init = TRUE;

	  /* Let particular systems override the size of a chunk.  */
#ifndef OBSTACK_CHUNK_SIZE
#define OBSTACK_CHUNK_SIZE 0
#endif
	  /* Let them override the alloc and free routines too.  */
#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;
}

/* Return nonzero if all bits in an element are zero.  */

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
}

/* Link the bitmap element into the current bitmap linked list.  */

static INLINE void
bitmap_element_link (head, element)
     bitmap head;
     bitmap_element *element;
{
  unsigned int indx = element->indx;
  bitmap_element *ptr;

  /* If this is the first and only element, set it in.  */
  if (head->first == 0)
    {
      element->next = element->prev = 0;
      head->first = element;
    }

  /* If this index is less than that of the current element, it goes someplace
     before the current 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;
    }

  /* Otherwise, it must go someplace after the current 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;
    }

  /* Set up so this is the first element searched.  */
  head->current = element;
  head->indx = indx;
}

/* Clear a bitmap by freeing the linked list.  */

void INLINE
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;
}

/* Copy a bitmap to another bitmap */

void
bitmap_copy (to, from)
     bitmap to;
     bitmap from;
{
  bitmap_element *from_ptr, *to_ptr = 0;
  int i;

  bitmap_clear (to);

  /* Copy elements in forward direction one at a time */
  for (from_ptr = from->first; from_ptr; from_ptr = from_ptr->next)
    {
      bitmap_element *to_elt = bitmap_element_allocate (to);

      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

      /* Here we have a special case of bitmap_element_link, for the case
	 where we know the links are being entered in sequence.  */
      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;
    }
}

/* Find a bitmap element that would hold a bitmap's bit.
   Update the `current' field even if we can't find an element that
   would hold the bitmap's bit to make eventual allocation
   faster.  */

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

  /* `element' is the nearest to the one we want.  If it's not the one we
     want, the one we want doesn't exist.  */
  head->current = element;
  head->indx = element->indx;
  if (element != 0 && element->indx != indx)
    element = 0;

  return element;
}