diff options
author | Richard Biener <rguenther@suse.de> | 2019-07-30 12:13:01 +0000 |
---|---|---|
committer | Richard Biener <rguenth@gcc.gnu.org> | 2019-07-30 12:13:01 +0000 |
commit | 029ca38849484689c7cea5757f6eb646404264ec (patch) | |
tree | 3c7bc0b1c1505b914d58c1536b246f7b13179c1d /gcc/bitmap.c | |
parent | 1da8ab97a129ded60471ffcc2595ddce67336cd8 (diff) | |
download | gcc-029ca38849484689c7cea5757f6eb646404264ec.zip gcc-029ca38849484689c7cea5757f6eb646404264ec.tar.gz gcc-029ca38849484689c7cea5757f6eb646404264ec.tar.bz2 |
re PR tree-optimization/91257 (Compile-time and memory-hog hog)
2019-07-30 Richard Biener <rguenther@suse.de>
PR tree-optimization/91257
* bitmap.h (bitmap_ior_into_and_free): Declare.
* bitmap.c (bitmap_list_unlink_element): Add defaulted param
whether to add the unliked element to the freelist.
(bitmap_list_insert_element_after): Add defaulted param for
an already allocated element.
(bitmap_ior_into_and_free): New function.
* tree-ssa-structalias.c (condense_visit): Reduce the
ponts-to and edge bitmaps of the SCC members in a
logarithmic fashion rather than all to one.
From-SVN: r273907
Diffstat (limited to 'gcc/bitmap.c')
-rw-r--r-- | gcc/bitmap.c | 68 |
1 files changed, 61 insertions, 7 deletions
diff --git a/gcc/bitmap.c b/gcc/bitmap.c index c99d646..838a31d 100644 --- a/gcc/bitmap.c +++ b/gcc/bitmap.c @@ -267,7 +267,8 @@ bitmap_list_link_element (bitmap head, bitmap_element *element) and return it to the freelist. */ static inline void -bitmap_list_unlink_element (bitmap head, bitmap_element *element) +bitmap_list_unlink_element (bitmap head, bitmap_element *element, + bool to_freelist = true) { bitmap_element *next = element->next; bitmap_element *prev = element->prev; @@ -294,18 +295,21 @@ bitmap_list_unlink_element (bitmap head, bitmap_element *element) head->indx = 0; } - bitmap_elem_to_freelist (head, element); + if (to_freelist) + bitmap_elem_to_freelist (head, element); } -/* Insert a new uninitialized element into bitmap HEAD after element - ELT. If ELT is NULL, insert the element at the start. Return the - new element. */ +/* Insert a new uninitialized element (or NODE if not NULL) into bitmap + HEAD after element ELT. If ELT is NULL, insert the element at the start. + Return the new element. */ static bitmap_element * bitmap_list_insert_element_after (bitmap head, - bitmap_element *elt, unsigned int indx) + bitmap_element *elt, unsigned int indx, + bitmap_element *node = NULL) { - bitmap_element *node = bitmap_element_allocate (head); + if (!node) + node = bitmap_element_allocate (head); node->indx = indx; gcc_checking_assert (!head->tree_form); @@ -2026,6 +2030,56 @@ bitmap_ior_into (bitmap a, const_bitmap b) return changed; } +/* A |= B. Return true if A changes. Free B (re-using its storage + for the result). */ + +bool +bitmap_ior_into_and_free (bitmap a, bitmap *b_) +{ + bitmap b = *b_; + bitmap_element *a_elt = a->first; + bitmap_element *b_elt = b->first; + bitmap_element *a_prev = NULL; + bitmap_element **a_prev_pnext = &a->first; + bool changed = false; + + gcc_checking_assert (!a->tree_form && !b->tree_form); + gcc_assert (a->obstack == b->obstack); + if (a == b) + return false; + + while (b_elt) + { + /* If A lags behind B, just advance it. */ + if (!a_elt || a_elt->indx == b_elt->indx) + { + changed = bitmap_elt_ior (a, a_elt, a_prev, a_elt, b_elt, changed); + b_elt = b_elt->next; + } + else if (a_elt->indx > b_elt->indx) + { + bitmap_element *b_elt_next = b_elt->next; + bitmap_list_unlink_element (b, b_elt, false); + bitmap_list_insert_element_after (a, a_prev, b_elt->indx, b_elt); + b_elt = b_elt_next; + } + + a_prev = *a_prev_pnext; + a_prev_pnext = &a_prev->next; + a_elt = *a_prev_pnext; + } + + gcc_checking_assert (!a->current == !a->first); + if (a->current) + a->indx = a->current->indx; + + if (b->obstack) + BITMAP_FREE (*b_); + else + bitmap_clear (b); + return changed; +} + /* DST = A ^ B */ void |