From 0e5b369ef15294d10ee8efa432bbb3d6822d065b Mon Sep 17 00:00:00 2001 From: Richard Biener Date: Tue, 30 Jul 2019 14:16:24 +0000 Subject: [PATCH] re PR tree-optimization/91257 (Compile-time and memory-hog hog) 2019-07-30 Richard Biener PR tree-optimization/91257 * bitmap.c (bitmap_ior_and_compl_into): Open-code. From-SVN: r273909 --- gcc/ChangeLog | 5 ++++ gcc/bitmap.c | 71 ++++++++++++++++++++++++++++++++++++++++++++++----- 2 files changed, 70 insertions(+), 6 deletions(-) diff --git a/gcc/ChangeLog b/gcc/ChangeLog index b921f1e2671..05258644174 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,8 @@ +2019-07-30 Richard Biener + + PR tree-optimization/91257 + * bitmap.c (bitmap_ior_and_compl_into): Open-code. + 2019-07-30 Martin Liska * doc/invoke.texi: Document new behavior. diff --git a/gcc/bitmap.c b/gcc/bitmap.c index 838a31da238..ce68a628358 100644 --- a/gcc/bitmap.c +++ b/gcc/bitmap.c @@ -2421,16 +2421,75 @@ bitmap_ior_and_compl (bitmap dst, const_bitmap a, const_bitmap b, const_bitmap k bool bitmap_ior_and_compl_into (bitmap a, const_bitmap b, const_bitmap c) { - bitmap_head tmp; - bool changed; + bitmap_element *a_elt = a->first; + const bitmap_element *b_elt = b->first; + const bitmap_element *c_elt = c->first; + bitmap_element and_elt; + bitmap_element *a_prev = NULL; + bitmap_element **a_prev_pnext = &a->first; + bool changed = false; + unsigned ix; gcc_checking_assert (!a->tree_form && !b->tree_form && !c->tree_form); - bitmap_initialize (&tmp, &bitmap_default_obstack); - bitmap_and_compl (&tmp, b, c); - changed = bitmap_ior_into (a, &tmp); - bitmap_clear (&tmp); + if (a == b) + return false; + if (bitmap_empty_p (c)) + return bitmap_ior_into (a, b); + else if (bitmap_empty_p (a)) + return bitmap_and_compl (a, b, c); + + and_elt.indx = -1; + while (b_elt) + { + /* Advance C. */ + while (c_elt && c_elt->indx < b_elt->indx) + c_elt = c_elt->next; + + const bitmap_element *and_elt_ptr; + if (c_elt && c_elt->indx == b_elt->indx) + { + BITMAP_WORD overall = 0; + and_elt_ptr = &and_elt; + and_elt.indx = b_elt->indx; + for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++) + { + and_elt.bits[ix] = b_elt->bits[ix] & ~c_elt->bits[ix]; + overall |= and_elt.bits[ix]; + } + if (!overall) + { + b_elt = b_elt->next; + continue; + } + } + else + and_elt_ptr = b_elt; + + b_elt = b_elt->next; + /* Now find a place to insert AND_ELT. */ + do + { + ix = a_elt ? a_elt->indx : and_elt_ptr->indx; + if (ix == and_elt_ptr->indx) + changed = bitmap_elt_ior (a, a_elt, a_prev, a_elt, + and_elt_ptr, changed); + else if (ix > and_elt_ptr->indx) + changed = bitmap_elt_copy (a, NULL, a_prev, and_elt_ptr, changed); + + a_prev = *a_prev_pnext; + a_prev_pnext = &a_prev->next; + a_elt = *a_prev_pnext; + + /* If A lagged behind B/C, we advanced it so loop once more. */ + } + while (ix < and_elt_ptr->indx); + } + + gcc_checking_assert (!a->current == !a->first); + if (a->current) + a->indx = a->current->indx; return changed; } -- 2.30.2