1/* Simple bitmaps.
2   Copyright (C) 1999 Free Software Foundation, Inc.
3
4This file is part of GNU CC.
5
6GNU CC is free software; you can redistribute it and/or modify
7it under the terms of the GNU General Public License as published by
8the Free Software Foundation; either version 2, or (at your option)
9any later version.
10
11GNU CC is distributed in the hope that it will be useful,
12but WITHOUT ANY WARRANTY; without even the implied warranty of
13MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14GNU General Public License for more details.
15
16You should have received a copy of the GNU General Public License
17along with GNU CC; see the file COPYING.  If not, write to
18the Free Software Foundation, 59 Temple Place - Suite 330,
19Boston, MA 02111-1307, USA.  */
20
21#include "config.h"
22#include "system.h"
23#include "rtl.h"
24#include "flags.h"
25#include "basic-block.h"
26
27/* Bitmap manipulation routines.  */
28
29/* Allocate a simple bitmap of N_ELMS bits.  */
30
31sbitmap
32sbitmap_alloc (n_elms)
33     int n_elms;
34{
35  int bytes, size, amt;
36  sbitmap bmap;
37
38  size = SBITMAP_SET_SIZE (n_elms);
39  bytes = size * sizeof (SBITMAP_ELT_TYPE);
40  amt = (sizeof (struct simple_bitmap_def)
41	 + bytes - sizeof (SBITMAP_ELT_TYPE));
42  bmap = (sbitmap) xmalloc (amt);
43  bmap->n_bits = n_elms;
44  bmap->size = size;
45  bmap->bytes = bytes;
46  return bmap;
47}
48
49/* Allocate a vector of N_VECS bitmaps of N_ELMS bits.  */
50
51sbitmap *
52sbitmap_vector_alloc (n_vecs, n_elms)
53     int n_vecs, n_elms;
54{
55  int i, bytes, offset, elm_bytes, size, amt, vector_bytes;
56  sbitmap *bitmap_vector;
57
58  size = SBITMAP_SET_SIZE (n_elms);
59  bytes = size * sizeof (SBITMAP_ELT_TYPE);
60  elm_bytes = (sizeof (struct simple_bitmap_def)
61	       + bytes - sizeof (SBITMAP_ELT_TYPE));
62  vector_bytes = n_vecs * sizeof (sbitmap *);
63
64  /* Round up `vector_bytes' to account for the alignment requirements
65     of an sbitmap.  One could allocate the vector-table and set of sbitmaps
66     separately, but that requires maintaining two pointers or creating
67     a cover struct to hold both pointers (so our result is still just
68     one pointer).  Neither is a bad idea, but this is simpler for now.  */
69  {
70    /* Based on DEFAULT_ALIGNMENT computation in obstack.c.  */
71    struct { char x; SBITMAP_ELT_TYPE y; } align;
72    int alignment = (char *) & align.y - & align.x;
73    vector_bytes = (vector_bytes + alignment - 1) & ~ (alignment - 1);
74  }
75
76  amt = vector_bytes + (n_vecs * elm_bytes);
77  bitmap_vector = (sbitmap *) xmalloc (amt);
78
79  for (i = 0, offset = vector_bytes;
80       i < n_vecs;
81       i++, offset += elm_bytes)
82    {
83      sbitmap b = (sbitmap) ((char *) bitmap_vector + offset);
84      bitmap_vector[i] = b;
85      b->n_bits = n_elms;
86      b->size = size;
87      b->bytes = bytes;
88    }
89
90  return bitmap_vector;
91}
92
93/* Copy sbitmap SRC to DST.  */
94
95void
96sbitmap_copy (dst, src)
97     sbitmap dst, src;
98{
99  bcopy ((PTR) src->elms, (PTR) dst->elms,
100	 sizeof (SBITMAP_ELT_TYPE) * dst->size);
101}
102
103/* Zero all elements in a bitmap.  */
104
105void
106sbitmap_zero (bmap)
107     sbitmap bmap;
108{
109  bzero ((char *) bmap->elms, bmap->bytes);
110}
111
112/* Set to ones all elements in a bitmap.  */
113
114void
115sbitmap_ones (bmap)
116     sbitmap bmap;
117{
118  memset (bmap->elms, -1, bmap->bytes);
119}
120
121/* Zero a vector of N_VECS bitmaps.  */
122
123void
124sbitmap_vector_zero (bmap, n_vecs)
125     sbitmap *bmap;
126     int n_vecs;
127{
128  int i;
129
130  for (i = 0; i < n_vecs; i++)
131    sbitmap_zero (bmap[i]);
132}
133
134/* Set to ones a vector of N_VECS bitmaps.  */
135
136void
137sbitmap_vector_ones (bmap, n_vecs)
138     sbitmap *bmap;
139     int n_vecs;
140{
141  int i;
142
143  for (i = 0; i < n_vecs; i++)
144    sbitmap_ones (bmap[i]);
145}
146
147/* Set DST to be A union (B - C).
148   DST = A | (B & ~C).
149   Return non-zero if any change is made.  */
150
151int
152sbitmap_union_of_diff (dst, a, b, c)
153     sbitmap dst, a, b, c;
154{
155  int i,changed;
156  sbitmap_ptr dstp, ap, bp, cp;
157
158  changed = 0;
159  dstp = dst->elms;
160  ap = a->elms;
161  bp = b->elms;
162  cp = c->elms;
163  for (i = 0; i < dst->size; i++)
164    {
165      SBITMAP_ELT_TYPE tmp = *ap | (*bp & ~*cp);
166      if (*dstp != tmp)
167	changed = 1;
168      *dstp = tmp;
169      dstp++; ap++; bp++; cp++;
170    }
171  return changed;
172}
173
174/* Set bitmap DST to the bitwise negation of the bitmap SRC.  */
175
176void
177sbitmap_not (dst, src)
178     sbitmap dst, src;
179{
180  int i;
181  sbitmap_ptr dstp, ap;
182
183  dstp = dst->elms;
184  ap = src->elms;
185  for (i = 0; i < dst->size; i++)
186    {
187      SBITMAP_ELT_TYPE tmp = ~(*ap);
188      *dstp = tmp;
189      dstp++; ap++;
190    }
191}
192
193/* Set the bits in DST to be the difference between the bits
194   in A and the bits in B. i.e. dst = a - b.
195   The - operator is implemented as a & (~b).  */
196
197void
198sbitmap_difference (dst, a, b)
199     sbitmap dst, a, b;
200{
201  int i;
202  sbitmap_ptr dstp, ap, bp;
203
204  dstp = dst->elms;
205  ap = a->elms;
206  bp = b->elms;
207  for (i = 0; i < dst->size; i++)
208    *dstp++ = *ap++ & (~*bp++);
209}
210
211/* Set DST to be (A and B)).
212   Return non-zero if any change is made.  */
213
214int
215sbitmap_a_and_b (dst, a, b)
216     sbitmap dst, a, b;
217{
218  int i,changed;
219  sbitmap_ptr dstp, ap, bp;
220
221  changed = 0;
222  dstp = dst->elms;
223  ap = a->elms;
224  bp = b->elms;
225  for (i = 0; i < dst->size; i++)
226    {
227      SBITMAP_ELT_TYPE tmp = *ap & *bp;
228      if (*dstp != tmp)
229	changed = 1;
230      *dstp = tmp;
231      dstp++; ap++; bp++;
232    }
233  return changed;
234}
235/* Set DST to be (A or B)).
236   Return non-zero if any change is made.  */
237
238int
239sbitmap_a_or_b (dst, a, b)
240     sbitmap dst, a, b;
241{
242  int i,changed;
243  sbitmap_ptr dstp, ap, bp;
244
245  changed = 0;
246  dstp = dst->elms;
247  ap = a->elms;
248  bp = b->elms;
249  for (i = 0; i < dst->size; i++)
250    {
251      SBITMAP_ELT_TYPE tmp = *ap | *bp;
252      if (*dstp != tmp)
253	changed = 1;
254      *dstp = tmp;
255      dstp++; ap++; bp++;
256    }
257  return changed;
258}
259
260/* Set DST to be (A or (B and C)).
261   Return non-zero if any change is made.  */
262
263int
264sbitmap_a_or_b_and_c (dst, a, b, c)
265     sbitmap dst, a, b, c;
266{
267  int i,changed;
268  sbitmap_ptr dstp, ap, bp, cp;
269
270  changed = 0;
271  dstp = dst->elms;
272  ap = a->elms;
273  bp = b->elms;
274  cp = c->elms;
275  for (i = 0; i < dst->size; i++)
276    {
277      SBITMAP_ELT_TYPE tmp = *ap | (*bp & *cp);
278      if (*dstp != tmp)
279	changed = 1;
280      *dstp = tmp;
281      dstp++; ap++; bp++; cp++;
282    }
283  return changed;
284}
285
286/* Set DST to be (A ann (B or C)).
287   Return non-zero if any change is made.  */
288
289int
290sbitmap_a_and_b_or_c (dst, a, b, c)
291     sbitmap dst, a, b, c;
292{
293  int i,changed;
294  sbitmap_ptr dstp, ap, bp, cp;
295
296  changed = 0;
297  dstp = dst->elms;
298  ap = a->elms;
299  bp = b->elms;
300  cp = c->elms;
301  for (i = 0; i < dst->size; i++)
302    {
303      SBITMAP_ELT_TYPE tmp = *ap & (*bp | *cp);
304      if (*dstp != tmp)
305	changed = 1;
306      *dstp = tmp;
307      dstp++; ap++; bp++; cp++;
308    }
309  return changed;
310}
311
312/* Set the bitmap DST to the intersection of SRC of all predecessors or
313   successors of block number BB (PRED_SUCC says which).  */
314
315void
316sbitmap_intersect_of_predsucc (dst, src, bb, pred_succ)
317     sbitmap dst;
318     sbitmap *src;
319     int bb;
320     int_list_ptr *pred_succ;
321{
322  int_list_ptr ps;
323  int ps_bb;
324  int set_size = dst->size;
325
326  ps = pred_succ[bb];
327
328  /* It is possible that there are no predecessors(/successors).
329     This can happen for example in unreachable code.  */
330
331  if (ps == NULL)
332    {
333      /* In APL-speak this is the `and' reduction of the empty set and thus
334	 the result is the identity for `and'.  */
335      sbitmap_ones (dst);
336      return;
337    }
338
339  /* Set result to first predecessor/successor.  */
340
341  for ( ; ps != NULL; ps = ps->next)
342    {
343      ps_bb = INT_LIST_VAL (ps);
344      if (ps_bb == ENTRY_BLOCK || ps_bb == EXIT_BLOCK)
345	continue;
346      sbitmap_copy (dst, src[ps_bb]);
347      /* Break out since we're only doing first predecessor.  */
348      break;
349    }
350  if (ps == NULL)
351    return;
352
353  /* Now do the remaining predecessors/successors.  */
354
355  for (ps = ps->next; ps != NULL; ps = ps->next)
356    {
357      int i;
358      sbitmap_ptr p,r;
359
360      ps_bb = INT_LIST_VAL (ps);
361      if (ps_bb == ENTRY_BLOCK || ps_bb == EXIT_BLOCK)
362	continue;
363
364      p = src[ps_bb]->elms;
365      r = dst->elms;
366
367      for (i = 0; i < set_size; i++)
368	*r++ &= *p++;
369    }
370}
371
372/* Set the bitmap DST to the union of SRC of all predecessors/successors of
373   block number BB.  */
374
375void
376sbitmap_union_of_predsucc (dst, src, bb, pred_succ)
377     sbitmap dst;
378     sbitmap *src;
379     int bb;
380     int_list_ptr *pred_succ;
381{
382  int_list_ptr ps;
383  int ps_bb;
384  int set_size = dst->size;
385
386  ps = pred_succ[bb];
387
388  /* It is possible that there are no predecessors(/successors).
389     This can happen for example in unreachable code.  */
390
391  if (ps == NULL)
392    {
393      /* In APL-speak this is the `or' reduction of the empty set and thus
394	 the result is the identity for `or'.  */
395      sbitmap_zero (dst);
396      return;
397    }
398
399  /* Set result to first predecessor/successor.  */
400
401  for ( ; ps != NULL; ps = ps->next)
402    {
403      ps_bb = INT_LIST_VAL (ps);
404      if (ps_bb == ENTRY_BLOCK || ps_bb == EXIT_BLOCK)
405	continue;
406      sbitmap_copy (dst, src[ps_bb]);
407      /* Break out since we're only doing first predecessor.  */
408      break;
409    }
410  if (ps == NULL)
411    return;
412
413  /* Now do the remaining predecessors/successors.  */
414
415  for (ps = ps->next; ps != NULL; ps = ps->next)
416    {
417      int i;
418      sbitmap_ptr p,r;
419
420      ps_bb = INT_LIST_VAL (ps);
421      if (ps_bb == ENTRY_BLOCK || ps_bb == EXIT_BLOCK)
422	continue;
423
424      p = src[ps_bb]->elms;
425      r = dst->elms;
426
427      for (i = 0; i < set_size; i++)
428	*r++ |= *p++;
429    }
430}
431
432void
433dump_sbitmap (file, bmap)
434     FILE *file;
435     sbitmap bmap;
436{
437  int i,j,n;
438  int set_size = bmap->size;
439  int total_bits = bmap->n_bits;
440
441  fprintf (file, "  ");
442  for (i = n = 0; i < set_size && n < total_bits; i++)
443    {
444      for (j = 0; j < SBITMAP_ELT_BITS && n < total_bits; j++, n++)
445	{
446	  if (n != 0 && n % 10 == 0)
447	    fprintf (file, " ");
448	  fprintf (file, "%d", (bmap->elms[i] & (1L << j)) != 0);
449	}
450    }
451  fprintf (file, "\n");
452}
453
454void
455dump_sbitmap_vector (file, title, subtitle, bmaps, n_maps)
456     FILE *file;
457     const char *title, *subtitle;
458     sbitmap *bmaps;
459     int n_maps;
460{
461  int bb;
462
463  fprintf (file, "%s\n", title);
464  for (bb = 0; bb < n_maps; bb++)
465    {
466      fprintf (file, "%s %d\n", subtitle, bb);
467      dump_sbitmap (file, bmaps[bb]);
468    }
469  fprintf (file, "\n");
470}
471