gcc/sbitmap.h

   1 /* Simple bitmaps.
   2    Copyright (C) 1999 Free Software Foundation, Inc.
   3
   4 This file is part of GNU CC.
   5
   6 GNU CC is free software; you can redistribute it and/or modify
   7 it under the terms of the GNU General Public License as published by
   8 the Free Software Foundation; either version 2, or (at your option)
   9 any later version.
  10
  11 GNU CC is distributed in the hope that it will be useful,
  12 but WITHOUT ANY WARRANTY; without even the implied warranty of
  13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14 GNU General Public License for more details.
  15
  16 You should have received a copy of the GNU General Public License
  17 along with GNU CC; see the file COPYING.  If not, write to
  18 the Free Software Foundation, 59 Temple Place - Suite 330,
  19 Boston, MA 02111-1307, USA.  */
  20
  21 #ifndef _SBITMAP_H
  22 #define _SBITMAP_H 1
  23
  24 /* It's not clear yet whether using bitmap.[ch] will be a win.
  25    It should be straightforward to convert so for now we keep things simple
  26    while more important issues are dealt with.  */
  27
  28 #define SBITMAP_ELT_BITS HOST_BITS_PER_WIDE_INT
  29 #define SBITMAP_ELT_TYPE unsigned HOST_WIDE_INT
  30
  31 typedef struct simple_bitmap_def {
  32   /* Number of bits.  */
  33   int n_bits;
  34   /* Size in elements.  */
  35   int size;
  36   /* Size in bytes.  */
  37   int bytes;
  38   /* The elements.  */
  39   SBITMAP_ELT_TYPE elms[1];
  40 } *sbitmap;
  41
  42 typedef SBITMAP_ELT_TYPE *sbitmap_ptr;
  43
  44 /* Return the set size needed for N elements.  */
  45 #define SBITMAP_SET_SIZE(n) (((n) + SBITMAP_ELT_BITS - 1) / SBITMAP_ELT_BITS)
  46
  47 /* set bit number bitno in the bitmap */
  48 #define SET_BIT(bitmap, bitno)                                  \
  49   ((bitmap)->elms [(bitno) / SBITMAP_ELT_BITS]                  \
  50    |= (SBITMAP_ELT_TYPE) 1 << (bitno) % SBITMAP_ELT_BITS)
  51
  52 /* test if bit number bitno in the bitmap is set */
  53 #define TEST_BIT(bitmap, bitno) \
  54 ((bitmap)->elms [(bitno) / SBITMAP_ELT_BITS] >> (bitno) % SBITMAP_ELT_BITS & 1)
  55
  56 /* reset bit number bitno in the bitmap  */
  57 #define RESET_BIT(bitmap, bitno)                                \
  58   ((bitmap)->elms [(bitno) / SBITMAP_ELT_BITS]                  \
  59    &= ~((SBITMAP_ELT_TYPE) 1 << (bitno) % SBITMAP_ELT_BITS))
  60
  61 /* Loop over all elements of SBITSET, starting with MIN.  */
  62 #define EXECUTE_IF_SET_IN_SBITMAP(SBITMAP, MIN, N, CODE)                \
  63 do {                                                                    \
  64   unsigned int bit_num_ = (MIN) % (unsigned) SBITMAP_ELT_BITS;          \
  65   unsigned int word_num_ = (MIN) / (unsigned) SBITMAP_ELT_BITS;         \
  66   unsigned int size_ = (SBITMAP)->size;                                 \
  67   SBITMAP_ELT_TYPE *ptr_ = (SBITMAP)->elms;                             \
  68                                                                         \
  69   while (word_num_ < size_)                                             \
  70     {                                                                   \
  71       SBITMAP_ELT_TYPE word_ = ptr_[word_num_];                         \
  72       if (word_ != 0)                                                   \
  73         {                                                               \
  74           for (; bit_num_ < SBITMAP_ELT_BITS; ++bit_num_)               \
  75             {                                                           \
  76               SBITMAP_ELT_TYPE mask_ = (SBITMAP_ELT_TYPE)1 << bit_num_; \
  77               if ((word_ & mask_) != 0)                                 \
  78                 {                                                       \
  79                   word_ &= ~mask_;                                      \
  80                   (N) = word_num_ * SBITMAP_ELT_BITS + bit_num_;        \
  81                   CODE;                                                 \
  82                   if (word_ == 0)                                       \
  83                     break;                                              \
  84                 }                                                       \
  85             }                                                           \
  86         }                                                               \
  87       bit_num_ = 0;                                                     \
  88       word_num_++;                                                      \
  89    }                                                                    \
  90 } while (0)
  91
  92 #define sbitmap_free(map)               free(map)
  93 #define sbitmap_vector_free(vec)        free(vec)
  94
  95 extern void dump_sbitmap PROTO ((FILE *, sbitmap));
  96 extern void dump_sbitmap_vector PROTO ((FILE *, const char *, const char *,
  97                                         sbitmap *, int));
  98
  99 extern sbitmap sbitmap_alloc PROTO ((int));
 100 extern sbitmap *sbitmap_vector_alloc PROTO ((int, int));
 101
 102 extern void sbitmap_copy PROTO ((sbitmap, sbitmap));
 103 extern void sbitmap_zero PROTO ((sbitmap));
 104 extern void sbitmap_ones PROTO ((sbitmap));
 105 extern void sbitmap_vector_zero PROTO ((sbitmap *, int));
 106 extern void sbitmap_vector_ones PROTO ((sbitmap *, int));
 107
 108 extern int sbitmap_union_of_diff PROTO ((sbitmap, sbitmap, sbitmap, sbitmap));
 109 extern void sbitmap_difference PROTO ((sbitmap, sbitmap, sbitmap));
 110 extern void sbitmap_not PROTO ((sbitmap, sbitmap));
 111 extern int sbitmap_a_or_b_and_c PROTO ((sbitmap, sbitmap, sbitmap, sbitmap));
 112 extern int sbitmap_a_and_b_or_c PROTO ((sbitmap, sbitmap, sbitmap, sbitmap));
 113 extern int sbitmap_a_and_b PROTO ((sbitmap, sbitmap, sbitmap));
 114 extern int sbitmap_a_or_b PROTO ((sbitmap, sbitmap, sbitmap));
 115 extern int sbitmap_a_subset_b_p PROTO ((sbitmap, sbitmap));
 116
 117 struct int_list;
 118 extern void sbitmap_intersect_of_predsucc PROTO ((sbitmap, sbitmap *,
 119                                                   int, struct int_list **));
 120 #define sbitmap_intersect_of_predecessors  sbitmap_intersect_of_predsucc
 121 #define sbitmap_intersect_of_successors    sbitmap_intersect_of_predsucc
 122
 123 extern void sbitmap_union_of_predsucc PROTO ((sbitmap, sbitmap *, int,
 124                                               struct int_list **));
 125 #define sbitmap_union_of_predecessors  sbitmap_union_of_predsucc
 126 #define sbitmap_union_of_successors    sbitmap_union_of_predsucc
 127
 128 /* Intersection and Union of preds/succs using the new flow graph
 129    structure instead of the pred/succ arrays.  */
 130
 131 extern void sbitmap_intersection_of_succs    PROTO ((sbitmap, sbitmap *, int));
 132 extern void sbitmap_intersection_of_preds    PROTO ((sbitmap, sbitmap *, int));
 133 extern void sbitmap_union_of_succs           PROTO ((sbitmap, sbitmap *, int));
 134 extern void sbitmap_union_of_preds           PROTO ((sbitmap, sbitmap *, int));
 135
 136 #endif /* _SBITMAP_H */