[patch][RFC] bitmaps as lists *or* trees

[Richard Biener]

On Thu, Mar 7, 2013 at 9:18 PM Steven Bosscher <stevenb.gcc@gmail.com> wrote:
>
> > Attached is a version that passes bootstrap&testing on
> > x86_64-unknown-linux-gnu. and with a ChangeLog.
>
> Hello,
>
> Testing with some bitmap view changes revealed a few bugs:
>
> - Listifying a tree was broken, the prev pointer was never set. Oops!
> - As a result of the above, clearing bitmaps was broken, the whole
> bitmap would be leaked instead of released.
> - Likewise, changing view from tree to list would only retain
> head->first and lose the rest of the set...
> - bitmap_last_set_bit has to search from the root, as head->current
> may be in the left branch of another node.

I have updated the patch to trunk and fixed another bug (the patch applied
OK to gcc 4.8 where the same bug exists - not sure what you developed it
ontop of).  We have a premature optimization in bitmap_find_bit:

@@ -506,7 +858,9 @@ bitmap_find_bit (bitmap head, unsigned i
   if (head->current == NULL
       || head->indx == indx)
     return head->current;
-  if (head->current == head->first
+  /* ???  Premature optimization?  */
+  if (!head->tree_form
+      && head->current == head->first
       && head->first->next == NULL)
     return NULL;

the reginfo.c use-case seems to be gone so I put the use in the SSA
propagator instead where it is supposed to help PR63155.

Meanwhile bitmap_head->descriptor_id is dead so I made tree_form a bool.

Richard.

> Ciao!
> Steven
-------------- next part --------------
A non-text attachment was scrubbed...
Name: tree-bitmap
Type: application/octet-stream
Size: 55144 bytes
Desc: not available
URL: <http://gcc.gnu.org/pipermail/gcc-patches/attachments/20181017/460b408c/attachment.obj>