152284Sobrien/* Simple bitmaps. 2169689Skan Copyright (C) 1999, 2000, 2002, 2003, 2004 Free Software Foundation, Inc. 352284Sobrien 490075SobrienThis file is part of GCC. 552284Sobrien 690075SobrienGCC is free software; you can redistribute it and/or modify it under 790075Sobrienthe terms of the GNU General Public License as published by the Free 890075SobrienSoftware Foundation; either version 2, or (at your option) any later 990075Sobrienversion. 1052284Sobrien 1190075SobrienGCC is distributed in the hope that it will be useful, but WITHOUT ANY 1290075SobrienWARRANTY; without even the implied warranty of MERCHANTABILITY or 1390075SobrienFITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 1490075Sobrienfor more details. 1552284Sobrien 1652284SobrienYou should have received a copy of the GNU General Public License 1790075Sobrienalong with GCC; see the file COPYING. If not, write to the Free 18169689SkanSoftware Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 19169689Skan02110-1301, USA. */ 2052284Sobrien 2152284Sobrien#include "config.h" 2252284Sobrien#include "system.h" 23132718Skan#include "coretypes.h" 24132718Skan#include "tm.h" 2552284Sobrien#include "rtl.h" 2652284Sobrien#include "flags.h" 2790075Sobrien#include "hard-reg-set.h" 28169689Skan#include "obstack.h" 2952284Sobrien#include "basic-block.h" 3052284Sobrien 3152284Sobrien/* Bitmap manipulation routines. */ 3252284Sobrien 3352284Sobrien/* Allocate a simple bitmap of N_ELMS bits. */ 3452284Sobrien 3552284Sobriensbitmap 36132718Skansbitmap_alloc (unsigned int n_elms) 3752284Sobrien{ 3890075Sobrien unsigned int bytes, size, amt; 3952284Sobrien sbitmap bmap; 4052284Sobrien 4152284Sobrien size = SBITMAP_SET_SIZE (n_elms); 4252284Sobrien bytes = size * sizeof (SBITMAP_ELT_TYPE); 4352284Sobrien amt = (sizeof (struct simple_bitmap_def) 4452284Sobrien + bytes - sizeof (SBITMAP_ELT_TYPE)); 45132718Skan bmap = xmalloc (amt); 4652284Sobrien bmap->n_bits = n_elms; 4752284Sobrien bmap->size = size; 4852284Sobrien bmap->bytes = bytes; 4952284Sobrien return bmap; 5052284Sobrien} 5152284Sobrien 52117395Skan/* Resize a simple bitmap BMAP to N_ELMS bits. If increasing the 53117395Skan size of BMAP, clear the new bits to zero if the DEF argument 54117395Skan is zero, and set them to one otherwise. */ 55117395Skan 56117395Skansbitmap 57132718Skansbitmap_resize (sbitmap bmap, unsigned int n_elms, int def) 58117395Skan{ 59117395Skan unsigned int bytes, size, amt; 60117395Skan unsigned int last_bit; 61117395Skan 62117395Skan size = SBITMAP_SET_SIZE (n_elms); 63117395Skan bytes = size * sizeof (SBITMAP_ELT_TYPE); 64117395Skan if (bytes > bmap->bytes) 65117395Skan { 66117395Skan amt = (sizeof (struct simple_bitmap_def) 67117395Skan + bytes - sizeof (SBITMAP_ELT_TYPE)); 68132718Skan bmap = xrealloc (bmap, amt); 69117395Skan } 70117395Skan 71117395Skan if (n_elms > bmap->n_bits) 72117395Skan { 73117395Skan if (def) 74117395Skan { 75132718Skan memset (bmap->elms + bmap->size, -1, bytes - bmap->bytes); 76117395Skan 77117395Skan /* Set the new bits if the original last element. */ 78117395Skan last_bit = bmap->n_bits % SBITMAP_ELT_BITS; 79117395Skan if (last_bit) 80117395Skan bmap->elms[bmap->size - 1] 81117395Skan |= ~((SBITMAP_ELT_TYPE)-1 >> (SBITMAP_ELT_BITS - last_bit)); 82117395Skan 83117395Skan /* Clear the unused bit in the new last element. */ 84117395Skan last_bit = n_elms % SBITMAP_ELT_BITS; 85117395Skan if (last_bit) 86117395Skan bmap->elms[size - 1] 87117395Skan &= (SBITMAP_ELT_TYPE)-1 >> (SBITMAP_ELT_BITS - last_bit); 88117395Skan } 89117395Skan else 90132718Skan memset (bmap->elms + bmap->size, 0, bytes - bmap->bytes); 91117395Skan } 92117395Skan else if (n_elms < bmap->n_bits) 93117395Skan { 94132718Skan /* Clear the surplus bits in the last word. */ 95117395Skan last_bit = n_elms % SBITMAP_ELT_BITS; 96117395Skan if (last_bit) 97117395Skan bmap->elms[size - 1] 98117395Skan &= (SBITMAP_ELT_TYPE)-1 >> (SBITMAP_ELT_BITS - last_bit); 99117395Skan } 100117395Skan 101117395Skan bmap->n_bits = n_elms; 102117395Skan bmap->size = size; 103117395Skan bmap->bytes = bytes; 104117395Skan return bmap; 105117395Skan} 106117395Skan 107169689Skan/* Re-allocate a simple bitmap of N_ELMS bits. New storage is uninitialized. */ 108169689Skan 109169689Skansbitmap 110169689Skansbitmap_realloc (sbitmap src, unsigned int n_elms) 111169689Skan{ 112169689Skan unsigned int bytes, size, amt; 113169689Skan sbitmap bmap; 114169689Skan 115169689Skan size = SBITMAP_SET_SIZE (n_elms); 116169689Skan bytes = size * sizeof (SBITMAP_ELT_TYPE); 117169689Skan amt = (sizeof (struct simple_bitmap_def) 118169689Skan + bytes - sizeof (SBITMAP_ELT_TYPE)); 119169689Skan 120169689Skan if (src->bytes >= bytes) 121169689Skan { 122169689Skan src->n_bits = n_elms; 123169689Skan return src; 124169689Skan } 125169689Skan 126169689Skan bmap = (sbitmap) xrealloc (src, amt); 127169689Skan bmap->n_bits = n_elms; 128169689Skan bmap->size = size; 129169689Skan bmap->bytes = bytes; 130169689Skan return bmap; 131169689Skan} 132169689Skan 13352284Sobrien/* Allocate a vector of N_VECS bitmaps of N_ELMS bits. */ 13452284Sobrien 13552284Sobriensbitmap * 136132718Skansbitmap_vector_alloc (unsigned int n_vecs, unsigned int n_elms) 13752284Sobrien{ 13890075Sobrien unsigned int i, bytes, offset, elm_bytes, size, amt, vector_bytes; 13952284Sobrien sbitmap *bitmap_vector; 14052284Sobrien 14152284Sobrien size = SBITMAP_SET_SIZE (n_elms); 14252284Sobrien bytes = size * sizeof (SBITMAP_ELT_TYPE); 14352284Sobrien elm_bytes = (sizeof (struct simple_bitmap_def) 14452284Sobrien + bytes - sizeof (SBITMAP_ELT_TYPE)); 14552284Sobrien vector_bytes = n_vecs * sizeof (sbitmap *); 14652284Sobrien 14752284Sobrien /* Round up `vector_bytes' to account for the alignment requirements 14852284Sobrien of an sbitmap. One could allocate the vector-table and set of sbitmaps 14952284Sobrien separately, but that requires maintaining two pointers or creating 15052284Sobrien a cover struct to hold both pointers (so our result is still just 15152284Sobrien one pointer). Neither is a bad idea, but this is simpler for now. */ 15252284Sobrien { 15352284Sobrien /* Based on DEFAULT_ALIGNMENT computation in obstack.c. */ 15452284Sobrien struct { char x; SBITMAP_ELT_TYPE y; } align; 15552284Sobrien int alignment = (char *) & align.y - & align.x; 15652284Sobrien vector_bytes = (vector_bytes + alignment - 1) & ~ (alignment - 1); 15752284Sobrien } 15852284Sobrien 15952284Sobrien amt = vector_bytes + (n_vecs * elm_bytes); 160132718Skan bitmap_vector = xmalloc (amt); 16152284Sobrien 16290075Sobrien for (i = 0, offset = vector_bytes; i < n_vecs; i++, offset += elm_bytes) 16352284Sobrien { 16452284Sobrien sbitmap b = (sbitmap) ((char *) bitmap_vector + offset); 16590075Sobrien 16652284Sobrien bitmap_vector[i] = b; 16752284Sobrien b->n_bits = n_elms; 16852284Sobrien b->size = size; 16952284Sobrien b->bytes = bytes; 17052284Sobrien } 17152284Sobrien 17252284Sobrien return bitmap_vector; 17352284Sobrien} 17452284Sobrien 17552284Sobrien/* Copy sbitmap SRC to DST. */ 17652284Sobrien 17752284Sobrienvoid 178132718Skansbitmap_copy (sbitmap dst, sbitmap src) 17952284Sobrien{ 18090075Sobrien memcpy (dst->elms, src->elms, sizeof (SBITMAP_ELT_TYPE) * dst->size); 18152284Sobrien} 18252284Sobrien 18390075Sobrien/* Determine if a == b. */ 18490075Sobrienint 185132718Skansbitmap_equal (sbitmap a, sbitmap b) 18690075Sobrien{ 18790075Sobrien return !memcmp (a->elms, b->elms, sizeof (SBITMAP_ELT_TYPE) * a->size); 18890075Sobrien} 189117395Skan 19052284Sobrien/* Zero all elements in a bitmap. */ 19152284Sobrien 19252284Sobrienvoid 193132718Skansbitmap_zero (sbitmap bmap) 19452284Sobrien{ 195132718Skan memset (bmap->elms, 0, bmap->bytes); 19652284Sobrien} 19752284Sobrien 19890075Sobrien/* Set all elements in a bitmap to ones. */ 19952284Sobrien 20052284Sobrienvoid 201132718Skansbitmap_ones (sbitmap bmap) 20252284Sobrien{ 20390075Sobrien unsigned int last_bit; 20490075Sobrien 205132718Skan memset (bmap->elms, -1, bmap->bytes); 20690075Sobrien 20790075Sobrien last_bit = bmap->n_bits % SBITMAP_ELT_BITS; 20890075Sobrien if (last_bit) 20990075Sobrien bmap->elms[bmap->size - 1] 21090075Sobrien = (SBITMAP_ELT_TYPE)-1 >> (SBITMAP_ELT_BITS - last_bit); 21152284Sobrien} 21252284Sobrien 21352284Sobrien/* Zero a vector of N_VECS bitmaps. */ 21452284Sobrien 21552284Sobrienvoid 216132718Skansbitmap_vector_zero (sbitmap *bmap, unsigned int n_vecs) 21752284Sobrien{ 21890075Sobrien unsigned int i; 21952284Sobrien 22052284Sobrien for (i = 0; i < n_vecs; i++) 22152284Sobrien sbitmap_zero (bmap[i]); 22252284Sobrien} 22352284Sobrien 22490075Sobrien/* Set a vector of N_VECS bitmaps to ones. */ 22552284Sobrien 22652284Sobrienvoid 227132718Skansbitmap_vector_ones (sbitmap *bmap, unsigned int n_vecs) 22852284Sobrien{ 22990075Sobrien unsigned int i; 23052284Sobrien 23152284Sobrien for (i = 0; i < n_vecs; i++) 23252284Sobrien sbitmap_ones (bmap[i]); 23352284Sobrien} 23452284Sobrien 23552284Sobrien/* Set DST to be A union (B - C). 23652284Sobrien DST = A | (B & ~C). 237117395Skan Returns true if any change is made. */ 23852284Sobrien 239117395Skanbool 240132718Skansbitmap_union_of_diff_cg (sbitmap dst, sbitmap a, sbitmap b, sbitmap c) 24152284Sobrien{ 242117395Skan unsigned int i, n = dst->size; 243117395Skan sbitmap_ptr dstp = dst->elms; 244117395Skan sbitmap_ptr ap = a->elms; 245117395Skan sbitmap_ptr bp = b->elms; 246117395Skan sbitmap_ptr cp = c->elms; 247117395Skan SBITMAP_ELT_TYPE changed = 0; 24852284Sobrien 249117395Skan for (i = 0; i < n; i++) 25052284Sobrien { 25190075Sobrien SBITMAP_ELT_TYPE tmp = *ap++ | (*bp++ & ~*cp++); 252117395Skan changed |= *dstp ^ tmp; 253117395Skan *dstp++ = tmp; 25452284Sobrien } 25590075Sobrien 256117395Skan return changed != 0; 25752284Sobrien} 25852284Sobrien 259117395Skanvoid 260132718Skansbitmap_union_of_diff (sbitmap dst, sbitmap a, sbitmap b, sbitmap c) 261117395Skan{ 262117395Skan unsigned int i, n = dst->size; 263117395Skan sbitmap_ptr dstp = dst->elms; 264117395Skan sbitmap_ptr ap = a->elms; 265117395Skan sbitmap_ptr bp = b->elms; 266117395Skan sbitmap_ptr cp = c->elms; 267117395Skan 268117395Skan for (i = 0; i < n; i++) 269117395Skan *dstp++ = *ap++ | (*bp++ & ~*cp++); 270117395Skan} 271117395Skan 27252284Sobrien/* Set bitmap DST to the bitwise negation of the bitmap SRC. */ 27352284Sobrien 27452284Sobrienvoid 275132718Skansbitmap_not (sbitmap dst, sbitmap src) 27652284Sobrien{ 277117395Skan unsigned int i, n = dst->size; 278117395Skan sbitmap_ptr dstp = dst->elms; 279117395Skan sbitmap_ptr srcp = src->elms; 280132718Skan unsigned int last_bit; 28152284Sobrien 282117395Skan for (i = 0; i < n; i++) 283117395Skan *dstp++ = ~*srcp++; 284132718Skan 285132718Skan /* Zero all bits past n_bits, by ANDing dst with sbitmap_ones. */ 286132718Skan last_bit = src->n_bits % SBITMAP_ELT_BITS; 287132718Skan if (last_bit) 288132718Skan dst->elms[n-1] = dst->elms[n-1] 289132718Skan & ((SBITMAP_ELT_TYPE)-1 >> (SBITMAP_ELT_BITS - last_bit)); 29052284Sobrien} 29152284Sobrien 29252284Sobrien/* Set the bits in DST to be the difference between the bits 29390075Sobrien in A and the bits in B. i.e. dst = a & (~b). */ 29452284Sobrien 29552284Sobrienvoid 296132718Skansbitmap_difference (sbitmap dst, sbitmap a, sbitmap b) 29752284Sobrien{ 298117395Skan unsigned int i, dst_size = dst->size; 299117395Skan unsigned int min_size = dst->size; 300117395Skan sbitmap_ptr dstp = dst->elms; 301117395Skan sbitmap_ptr ap = a->elms; 302117395Skan sbitmap_ptr bp = b->elms; 303132718Skan 304117395Skan /* A should be at least as large as DEST, to have a defined source. */ 305169689Skan gcc_assert (a->size >= dst_size); 306117395Skan /* If minuend is smaller, we simply pretend it to be zero bits, i.e. 307117395Skan only copy the subtrahend into dest. */ 308117395Skan if (b->size < min_size) 309117395Skan min_size = b->size; 310117395Skan for (i = 0; i < min_size; i++) 31152284Sobrien *dstp++ = *ap++ & (~*bp++); 312117395Skan /* Now fill the rest of dest from A, if B was too short. 313117395Skan This makes sense only when destination and A differ. */ 314117395Skan if (dst != a && i != dst_size) 315117395Skan for (; i < dst_size; i++) 316117395Skan *dstp++ = *ap++; 31752284Sobrien} 31852284Sobrien 319169689Skan/* Return true if there are any bits set in A are also set in B. 320169689Skan Return false otherwise. */ 321169689Skan 322169689Skanbool 323169689Skansbitmap_any_common_bits (sbitmap a, sbitmap b) 324169689Skan{ 325169689Skan sbitmap_ptr ap = a->elms; 326169689Skan sbitmap_ptr bp = b->elms; 327169689Skan unsigned int i, n; 328169689Skan 329169689Skan n = MIN (a->size, b->size); 330169689Skan for (i = 0; i < n; i++) 331169689Skan if ((*ap++ & *bp++) != 0) 332169689Skan return true; 333169689Skan 334169689Skan return false; 335169689Skan} 336169689Skan 33790075Sobrien/* Set DST to be (A and B). 338117395Skan Return nonzero if any change is made. */ 33952284Sobrien 340117395Skanbool 341132718Skansbitmap_a_and_b_cg (sbitmap dst, sbitmap a, sbitmap b) 34252284Sobrien{ 343117395Skan unsigned int i, n = dst->size; 344117395Skan sbitmap_ptr dstp = dst->elms; 345117395Skan sbitmap_ptr ap = a->elms; 346117395Skan sbitmap_ptr bp = b->elms; 347117395Skan SBITMAP_ELT_TYPE changed = 0; 34852284Sobrien 349117395Skan for (i = 0; i < n; i++) 35052284Sobrien { 35190075Sobrien SBITMAP_ELT_TYPE tmp = *ap++ & *bp++; 352132718Skan changed |= *dstp ^ tmp; 353117395Skan *dstp++ = tmp; 35452284Sobrien } 35590075Sobrien 356117395Skan return changed != 0; 35752284Sobrien} 35890075Sobrien 359117395Skanvoid 360132718Skansbitmap_a_and_b (sbitmap dst, sbitmap a, sbitmap b) 361117395Skan{ 362117395Skan unsigned int i, n = dst->size; 363117395Skan sbitmap_ptr dstp = dst->elms; 364117395Skan sbitmap_ptr ap = a->elms; 365117395Skan sbitmap_ptr bp = b->elms; 366117395Skan 367117395Skan for (i = 0; i < n; i++) 368117395Skan *dstp++ = *ap++ & *bp++; 369117395Skan} 370117395Skan 37190075Sobrien/* Set DST to be (A xor B)). 372117395Skan Return nonzero if any change is made. */ 37390075Sobrien 374117395Skanbool 375132718Skansbitmap_a_xor_b_cg (sbitmap dst, sbitmap a, sbitmap b) 37690075Sobrien{ 377117395Skan unsigned int i, n = dst->size; 378117395Skan sbitmap_ptr dstp = dst->elms; 379117395Skan sbitmap_ptr ap = a->elms; 380117395Skan sbitmap_ptr bp = b->elms; 381117395Skan SBITMAP_ELT_TYPE changed = 0; 382117395Skan 383117395Skan for (i = 0; i < n; i++) 38490075Sobrien { 38590075Sobrien SBITMAP_ELT_TYPE tmp = *ap++ ^ *bp++; 386132718Skan changed |= *dstp ^ tmp; 387117395Skan *dstp++ = tmp; 38890075Sobrien } 389117395Skan 390117395Skan return changed != 0; 39190075Sobrien} 39290075Sobrien 393117395Skanvoid 394132718Skansbitmap_a_xor_b (sbitmap dst, sbitmap a, sbitmap b) 395117395Skan{ 396117395Skan unsigned int i, n = dst->size; 397117395Skan sbitmap_ptr dstp = dst->elms; 398117395Skan sbitmap_ptr ap = a->elms; 399117395Skan sbitmap_ptr bp = b->elms; 400117395Skan 401117395Skan for (i = 0; i < n; i++) 402117395Skan *dstp++ = *ap++ ^ *bp++; 403117395Skan} 404117395Skan 40552284Sobrien/* Set DST to be (A or B)). 406117395Skan Return nonzero if any change is made. */ 40752284Sobrien 408117395Skanbool 409132718Skansbitmap_a_or_b_cg (sbitmap dst, sbitmap a, sbitmap b) 41052284Sobrien{ 411117395Skan unsigned int i, n = dst->size; 412117395Skan sbitmap_ptr dstp = dst->elms; 413117395Skan sbitmap_ptr ap = a->elms; 414117395Skan sbitmap_ptr bp = b->elms; 415117395Skan SBITMAP_ELT_TYPE changed = 0; 41652284Sobrien 417117395Skan for (i = 0; i < n; i++) 41852284Sobrien { 41990075Sobrien SBITMAP_ELT_TYPE tmp = *ap++ | *bp++; 420132718Skan changed |= *dstp ^ tmp; 421117395Skan *dstp++ = tmp; 42252284Sobrien } 42390075Sobrien 424117395Skan return changed != 0; 42552284Sobrien} 42652284Sobrien 427117395Skanvoid 428132718Skansbitmap_a_or_b (sbitmap dst, sbitmap a, sbitmap b) 429117395Skan{ 430117395Skan unsigned int i, n = dst->size; 431117395Skan sbitmap_ptr dstp = dst->elms; 432117395Skan sbitmap_ptr ap = a->elms; 433117395Skan sbitmap_ptr bp = b->elms; 43490075Sobrien 435117395Skan for (i = 0; i < n; i++) 436117395Skan *dstp++ = *ap++ | *bp++; 437117395Skan} 438117395Skan 439117395Skan/* Return nonzero if A is a subset of B. */ 440117395Skan 441117395Skanbool 442132718Skansbitmap_a_subset_b_p (sbitmap a, sbitmap b) 44390075Sobrien{ 444117395Skan unsigned int i, n = a->size; 44590075Sobrien sbitmap_ptr ap, bp; 44690075Sobrien 447117395Skan for (ap = a->elms, bp = b->elms, i = 0; i < n; i++, ap++, bp++) 44890075Sobrien if ((*ap | *bp) != *bp) 449117395Skan return false; 45090075Sobrien 451117395Skan return true; 45290075Sobrien} 45390075Sobrien 45452284Sobrien/* Set DST to be (A or (B and C)). 455117395Skan Return nonzero if any change is made. */ 45652284Sobrien 457117395Skanbool 458132718Skansbitmap_a_or_b_and_c_cg (sbitmap dst, sbitmap a, sbitmap b, sbitmap c) 45952284Sobrien{ 460117395Skan unsigned int i, n = dst->size; 461117395Skan sbitmap_ptr dstp = dst->elms; 462117395Skan sbitmap_ptr ap = a->elms; 463117395Skan sbitmap_ptr bp = b->elms; 464117395Skan sbitmap_ptr cp = c->elms; 465117395Skan SBITMAP_ELT_TYPE changed = 0; 46652284Sobrien 467117395Skan for (i = 0; i < n; i++) 46852284Sobrien { 46990075Sobrien SBITMAP_ELT_TYPE tmp = *ap++ | (*bp++ & *cp++); 470117395Skan changed |= *dstp ^ tmp; 471117395Skan *dstp++ = tmp; 47252284Sobrien } 47390075Sobrien 474117395Skan return changed != 0; 47552284Sobrien} 47652284Sobrien 477117395Skanvoid 478132718Skansbitmap_a_or_b_and_c (sbitmap dst, sbitmap a, sbitmap b, sbitmap c) 479117395Skan{ 480117395Skan unsigned int i, n = dst->size; 481117395Skan sbitmap_ptr dstp = dst->elms; 482117395Skan sbitmap_ptr ap = a->elms; 483117395Skan sbitmap_ptr bp = b->elms; 484117395Skan sbitmap_ptr cp = c->elms; 485117395Skan 486117395Skan for (i = 0; i < n; i++) 487117395Skan *dstp++ = *ap++ | (*bp++ & *cp++); 488117395Skan} 489117395Skan 49090075Sobrien/* Set DST to be (A and (B or C)). 491117395Skan Return nonzero if any change is made. */ 49252284Sobrien 493117395Skanbool 494132718Skansbitmap_a_and_b_or_c_cg (sbitmap dst, sbitmap a, sbitmap b, sbitmap c) 49552284Sobrien{ 496117395Skan unsigned int i, n = dst->size; 497117395Skan sbitmap_ptr dstp = dst->elms; 498117395Skan sbitmap_ptr ap = a->elms; 499117395Skan sbitmap_ptr bp = b->elms; 500117395Skan sbitmap_ptr cp = c->elms; 501117395Skan SBITMAP_ELT_TYPE changed = 0; 50252284Sobrien 503117395Skan for (i = 0; i < n; i++) 50452284Sobrien { 50590075Sobrien SBITMAP_ELT_TYPE tmp = *ap++ & (*bp++ | *cp++); 506117395Skan changed |= *dstp ^ tmp; 507117395Skan *dstp++ = tmp; 50852284Sobrien } 50990075Sobrien 510117395Skan return changed != 0; 51152284Sobrien} 51252284Sobrien 513117395Skanvoid 514132718Skansbitmap_a_and_b_or_c (sbitmap dst, sbitmap a, sbitmap b, sbitmap c) 515117395Skan{ 516117395Skan unsigned int i, n = dst->size; 517117395Skan sbitmap_ptr dstp = dst->elms; 518117395Skan sbitmap_ptr ap = a->elms; 519117395Skan sbitmap_ptr bp = b->elms; 520117395Skan sbitmap_ptr cp = c->elms; 521117395Skan 522117395Skan for (i = 0; i < n; i++) 523117395Skan *dstp++ = *ap++ & (*bp++ | *cp++); 524117395Skan} 525117395Skan 52690075Sobrien#ifdef IN_GCC 52790075Sobrien/* Set the bitmap DST to the intersection of SRC of successors of 52890075Sobrien block number BB, using the new flow graph structures. */ 52952284Sobrien 53052284Sobrienvoid 531132718Skansbitmap_intersection_of_succs (sbitmap dst, sbitmap *src, int bb) 53252284Sobrien{ 53390075Sobrien basic_block b = BASIC_BLOCK (bb); 53490075Sobrien unsigned int set_size = dst->size; 53590075Sobrien edge e; 536169689Skan unsigned ix; 53752284Sobrien 538169689Skan for (e = NULL, ix = 0; ix < EDGE_COUNT (b->succs); ix++) 53990075Sobrien { 540169689Skan e = EDGE_SUCC (b, ix); 54190075Sobrien if (e->dest == EXIT_BLOCK_PTR) 542117395Skan continue; 543169689Skan 54490075Sobrien sbitmap_copy (dst, src[e->dest->index]); 54590075Sobrien break; 54652284Sobrien } 54752284Sobrien 54890075Sobrien if (e == 0) 54990075Sobrien sbitmap_ones (dst); 55090075Sobrien else 551169689Skan for (++ix; ix < EDGE_COUNT (b->succs); ix++) 55290075Sobrien { 55390075Sobrien unsigned int i; 55490075Sobrien sbitmap_ptr p, r; 55552284Sobrien 556169689Skan e = EDGE_SUCC (b, ix); 55790075Sobrien if (e->dest == EXIT_BLOCK_PTR) 55890075Sobrien continue; 55990075Sobrien 56090075Sobrien p = src[e->dest->index]->elms; 56190075Sobrien r = dst->elms; 56290075Sobrien for (i = 0; i < set_size; i++) 56390075Sobrien *r++ &= *p++; 56490075Sobrien } 56590075Sobrien} 56690075Sobrien 56790075Sobrien/* Set the bitmap DST to the intersection of SRC of predecessors of 56890075Sobrien block number BB, using the new flow graph structures. */ 56990075Sobrien 57090075Sobrienvoid 571132718Skansbitmap_intersection_of_preds (sbitmap dst, sbitmap *src, int bb) 57290075Sobrien{ 57390075Sobrien basic_block b = BASIC_BLOCK (bb); 57490075Sobrien unsigned int set_size = dst->size; 57590075Sobrien edge e; 576169689Skan unsigned ix; 57790075Sobrien 578169689Skan for (e = NULL, ix = 0; ix < EDGE_COUNT (b->preds); ix++) 57952284Sobrien { 580169689Skan e = EDGE_PRED (b, ix); 58190075Sobrien if (e->src == ENTRY_BLOCK_PTR) 582117395Skan continue; 58390075Sobrien 58490075Sobrien sbitmap_copy (dst, src[e->src->index]); 58552284Sobrien break; 58652284Sobrien } 58752284Sobrien 58890075Sobrien if (e == 0) 58990075Sobrien sbitmap_ones (dst); 59090075Sobrien else 591169689Skan for (++ix; ix < EDGE_COUNT (b->preds); ix++) 59290075Sobrien { 59390075Sobrien unsigned int i; 59490075Sobrien sbitmap_ptr p, r; 59552284Sobrien 596169689Skan e = EDGE_PRED (b, ix); 59790075Sobrien if (e->src == ENTRY_BLOCK_PTR) 59890075Sobrien continue; 59990075Sobrien 60090075Sobrien p = src[e->src->index]->elms; 60190075Sobrien r = dst->elms; 60290075Sobrien for (i = 0; i < set_size; i++) 60390075Sobrien *r++ &= *p++; 60490075Sobrien } 60590075Sobrien} 60690075Sobrien 60790075Sobrien/* Set the bitmap DST to the union of SRC of successors of 60890075Sobrien block number BB, using the new flow graph structures. */ 60990075Sobrien 61090075Sobrienvoid 611132718Skansbitmap_union_of_succs (sbitmap dst, sbitmap *src, int bb) 61290075Sobrien{ 61390075Sobrien basic_block b = BASIC_BLOCK (bb); 61490075Sobrien unsigned int set_size = dst->size; 61590075Sobrien edge e; 616169689Skan unsigned ix; 61790075Sobrien 618169689Skan for (ix = 0; ix < EDGE_COUNT (b->succs); ix++) 61952284Sobrien { 620169689Skan e = EDGE_SUCC (b, ix); 62190075Sobrien if (e->dest == EXIT_BLOCK_PTR) 622117395Skan continue; 62352284Sobrien 62490075Sobrien sbitmap_copy (dst, src[e->dest->index]); 62590075Sobrien break; 62690075Sobrien } 62752284Sobrien 628169689Skan if (ix == EDGE_COUNT (b->succs)) 62990075Sobrien sbitmap_zero (dst); 63090075Sobrien else 631169689Skan for (ix++; ix < EDGE_COUNT (b->succs); ix++) 63290075Sobrien { 63390075Sobrien unsigned int i; 63490075Sobrien sbitmap_ptr p, r; 63552284Sobrien 636169689Skan e = EDGE_SUCC (b, ix); 63790075Sobrien if (e->dest == EXIT_BLOCK_PTR) 63890075Sobrien continue; 63990075Sobrien 64090075Sobrien p = src[e->dest->index]->elms; 64190075Sobrien r = dst->elms; 64290075Sobrien for (i = 0; i < set_size; i++) 64390075Sobrien *r++ |= *p++; 64490075Sobrien } 64552284Sobrien} 64652284Sobrien 64790075Sobrien/* Set the bitmap DST to the union of SRC of predecessors of 64890075Sobrien block number BB, using the new flow graph structures. */ 64952284Sobrien 65052284Sobrienvoid 651132718Skansbitmap_union_of_preds (sbitmap dst, sbitmap *src, int bb) 65252284Sobrien{ 65390075Sobrien basic_block b = BASIC_BLOCK (bb); 65490075Sobrien unsigned int set_size = dst->size; 65590075Sobrien edge e; 656169689Skan unsigned ix; 65752284Sobrien 658169689Skan for (ix = 0; ix < EDGE_COUNT (b->preds); ix++) 65952284Sobrien { 660169689Skan e = EDGE_PRED (b, ix); 66190075Sobrien if (e->src== ENTRY_BLOCK_PTR) 662117395Skan continue; 66352284Sobrien 66490075Sobrien sbitmap_copy (dst, src[e->src->index]); 66552284Sobrien break; 66652284Sobrien } 66752284Sobrien 668169689Skan if (ix == EDGE_COUNT (b->preds)) 66990075Sobrien sbitmap_zero (dst); 67090075Sobrien else 671169689Skan for (ix++; ix < EDGE_COUNT (b->preds); ix++) 67290075Sobrien { 67390075Sobrien unsigned int i; 67490075Sobrien sbitmap_ptr p, r; 67552284Sobrien 676169689Skan e = EDGE_PRED (b, ix); 67790075Sobrien if (e->src == ENTRY_BLOCK_PTR) 67890075Sobrien continue; 679117395Skan 68090075Sobrien p = src[e->src->index]->elms; 68190075Sobrien r = dst->elms; 68290075Sobrien for (i = 0; i < set_size; i++) 68390075Sobrien *r++ |= *p++; 68490075Sobrien } 68590075Sobrien} 68690075Sobrien#endif 68790075Sobrien 68890075Sobrien/* Return number of first bit set in the bitmap, -1 if none. */ 68990075Sobrien 69090075Sobrienint 691132718Skansbitmap_first_set_bit (sbitmap bmap) 69290075Sobrien{ 693169689Skan unsigned int n = 0; 694169689Skan sbitmap_iterator sbi; 69590075Sobrien 696169689Skan EXECUTE_IF_SET_IN_SBITMAP (bmap, 0, n, sbi) 697169689Skan return n; 69890075Sobrien return -1; 69990075Sobrien} 70090075Sobrien 70190075Sobrien/* Return number of last bit set in the bitmap, -1 if none. */ 70290075Sobrien 70390075Sobrienint 704132718Skansbitmap_last_set_bit (sbitmap bmap) 70590075Sobrien{ 70690075Sobrien int i; 70790075Sobrien SBITMAP_ELT_TYPE *ptr = bmap->elms; 70890075Sobrien 70990075Sobrien for (i = bmap->size - 1; i >= 0; i--) 71052284Sobrien { 71190075Sobrien SBITMAP_ELT_TYPE word = ptr[i]; 71252284Sobrien 71390075Sobrien if (word != 0) 71490075Sobrien { 71590075Sobrien unsigned int index = (i + 1) * SBITMAP_ELT_BITS - 1; 71690075Sobrien SBITMAP_ELT_TYPE mask 71790075Sobrien = (SBITMAP_ELT_TYPE) 1 << (SBITMAP_ELT_BITS - 1); 71852284Sobrien 71990075Sobrien while (1) 72090075Sobrien { 72190075Sobrien if ((word & mask) != 0) 72290075Sobrien return index; 72352284Sobrien 72490075Sobrien mask >>= 1; 72590075Sobrien index--; 72690075Sobrien } 72790075Sobrien } 72852284Sobrien } 72990075Sobrien 73090075Sobrien return -1; 73152284Sobrien} 73252284Sobrien 73352284Sobrienvoid 734132718Skandump_sbitmap (FILE *file, sbitmap bmap) 73552284Sobrien{ 73690075Sobrien unsigned int i, n, j; 73790075Sobrien unsigned int set_size = bmap->size; 73890075Sobrien unsigned int total_bits = bmap->n_bits; 73952284Sobrien 74052284Sobrien fprintf (file, " "); 74152284Sobrien for (i = n = 0; i < set_size && n < total_bits; i++) 74290075Sobrien for (j = 0; j < SBITMAP_ELT_BITS && n < total_bits; j++, n++) 74390075Sobrien { 74490075Sobrien if (n != 0 && n % 10 == 0) 74590075Sobrien fprintf (file, " "); 74690075Sobrien 74790075Sobrien fprintf (file, "%d", 74890075Sobrien (bmap->elms[i] & ((SBITMAP_ELT_TYPE) 1 << j)) != 0); 74990075Sobrien } 75090075Sobrien 75152284Sobrien fprintf (file, "\n"); 75252284Sobrien} 75352284Sobrien 75452284Sobrienvoid 755132718Skandump_sbitmap_file (FILE *file, sbitmap bmap) 75690075Sobrien{ 75790075Sobrien unsigned int i, pos; 75890075Sobrien 759117395Skan fprintf (file, "n_bits = %d, set = {", bmap->n_bits); 76090075Sobrien 76190075Sobrien for (pos = 30, i = 0; i < bmap->n_bits; i++) 76290075Sobrien if (TEST_BIT (bmap, i)) 76390075Sobrien { 76490075Sobrien if (pos > 70) 76590075Sobrien { 766117395Skan fprintf (file, "\n "); 76790075Sobrien pos = 0; 76890075Sobrien } 76990075Sobrien 770117395Skan fprintf (file, "%d ", i); 771117395Skan pos += 2 + (i >= 10) + (i >= 100) + (i >= 1000); 77290075Sobrien } 77390075Sobrien 774117395Skan fprintf (file, "}\n"); 77590075Sobrien} 77690075Sobrien 77790075Sobrienvoid 778132718Skandebug_sbitmap (sbitmap bmap) 779117395Skan{ 780117395Skan dump_sbitmap_file (stderr, bmap); 781117395Skan} 782117395Skan 783117395Skanvoid 784132718Skandump_sbitmap_vector (FILE *file, const char *title, const char *subtitle, 785132718Skan sbitmap *bmaps, int n_maps) 78652284Sobrien{ 78752284Sobrien int bb; 78852284Sobrien 78952284Sobrien fprintf (file, "%s\n", title); 79052284Sobrien for (bb = 0; bb < n_maps; bb++) 79152284Sobrien { 79252284Sobrien fprintf (file, "%s %d\n", subtitle, bb); 79352284Sobrien dump_sbitmap (file, bmaps[bb]); 79452284Sobrien } 79590075Sobrien 79652284Sobrien fprintf (file, "\n"); 79752284Sobrien} 798