1	/* Functions to support general ended bitmaps.
2	Copyright (C) 1997-2023 Free Software Foundation, Inc.
3
4	This file is part of GCC.
5
6	GCC is free software; you can redistribute it and/or modify it under
7	the terms of the GNU General Public License as published by the Free
8	Software Foundation; either version 3, or (at your option) any later
9	version.
10
11	GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12	WARRANTY; without even the implied warranty of MERCHANTABILITY or
13	FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14	for more details.
15
16	You should have received a copy of the GNU General Public License
17	along with GCC; see the file COPYING3. If not see
18	<http://www.gnu.org/licenses/>. */
19
20	#include "config.h"
21	#include "system.h"
22	#include "coretypes.h"
23	#include "bitmap.h"
24	#include "selftest.h"
25
26	/* Memory allocation statistics purpose instance. */
27	mem_alloc_description<bitmap_usage> bitmap_mem_desc;
28
29	/* Static zero-initialized bitmap obstack used for default initialization
30	of bitmap_head. */
31	bitmap_obstack bitmap_head::crashme;
32
33	static bitmap_element *bitmap_tree_listify_from (bitmap, bitmap_element *);
34
35	/* Register new bitmap. */
36	void
37	bitmap_register (bitmap b MEM_STAT_DECL)
38	{
39	static unsigned alloc_descriptor_max_uid = 1;
40	gcc_assert (b->alloc_descriptor == 0);
41	b->alloc_descriptor = alloc_descriptor_max_uid++;
42
43	bitmap_mem_desc.register_descriptor (ptr: b->get_descriptor (), origin: BITMAP_ORIGIN,
44	ggc: false FINAL_PASS_MEM_STAT);
45	}
46
47	/* Account the overhead. */
48	static void
49	register_overhead (bitmap b, size_t amount)
50	{
51	unsigned *d = b->get_descriptor ();
52	if (bitmap_mem_desc.contains_descriptor_for_instance (ptr: d))
53	bitmap_mem_desc.register_instance_overhead (size: amount, ptr: d);
54	}
55
56	/* Release the overhead. */
57	static void
58	release_overhead (bitmap b, size_t amount, bool remove_from_map)
59	{
60	unsigned *d = b->get_descriptor ();
61	if (bitmap_mem_desc.contains_descriptor_for_instance (ptr: d))
62	bitmap_mem_desc.release_instance_overhead (ptr: d, size: amount, remove_from_map);
63	}
64
65
66	/* Global data */
67	bitmap_element bitmap_zero_bits; /* An element of all zero bits. */
68	bitmap_obstack bitmap_default_obstack; /* The default bitmap obstack. */
69	static int bitmap_default_obstack_depth;
70	static GTY((deletable)) bitmap_element *bitmap_ggc_free; /* Freelist of
71	GC'd elements. */
72
73
74	/* Bitmap memory management. */
75
76	/* Add ELT to the appropriate freelist. */
77	static inline void
78	bitmap_elem_to_freelist (bitmap head, bitmap_element *elt)
79	{
80	bitmap_obstack *bit_obstack = head->obstack;
81
82	if (GATHER_STATISTICS)
83	release_overhead (b: head, amount: sizeof (bitmap_element), remove_from_map: false);
84
85	elt->next = NULL;
86	elt->indx = -1;
87	if (bit_obstack)
88	{
89	elt->prev = bit_obstack->elements;
90	bit_obstack->elements = elt;
91	}
92	else
93	{
94	elt->prev = bitmap_ggc_free;
95	bitmap_ggc_free = elt;
96	}
97	}
98
99	/* Allocate a bitmap element. The bits are cleared, but nothing else is. */
100
101	static inline bitmap_element *
102	bitmap_element_allocate (bitmap head)
103	{
104	bitmap_element *element;
105	bitmap_obstack *bit_obstack = head->obstack;
106
107	if (bit_obstack)
108	{
109	element = bit_obstack->elements;
110
111	if (element)
112	/* Use up the inner list first before looking at the next
113	element of the outer list. */
114	if (element->next)
115	{
116	bit_obstack->elements = element->next;
117	bit_obstack->elements->prev = element->prev;
118	}
119	else
120	/* Inner list was just a singleton. */
121	bit_obstack->elements = element->prev;
122	else
123	element = XOBNEW (&bit_obstack->obstack, bitmap_element);
124	}
125	else
126	{
127	element = bitmap_ggc_free;
128	if (element)
129	/* Use up the inner list first before looking at the next
130	element of the outer list. */
131	if (element->next)
132	{
133	bitmap_ggc_free = element->next;
134	bitmap_ggc_free->prev = element->prev;
135	}
136	else
137	/* Inner list was just a singleton. */
138	bitmap_ggc_free = element->prev;
139	else
140	element = ggc_alloc<bitmap_element> ();
141	}
142
143	if (GATHER_STATISTICS)
144	register_overhead (b: head, amount: sizeof (bitmap_element));
145
146	memset (s: element->bits, c: 0, n: sizeof (element->bits));
147
148	return element;
149	}
150
151	/* Remove ELT and all following elements from bitmap HEAD.
152	Put the released elements in the freelist for HEAD. */
153
154	void
155	bitmap_elt_clear_from (bitmap head, bitmap_element *elt)
156	{
157	bitmap_element *prev;
158	bitmap_obstack *bit_obstack = head->obstack;
159
160	if (!elt)
161	return;
162
163	if (head->tree_form)
164	elt = bitmap_tree_listify_from (head, elt);
165
166	if (GATHER_STATISTICS)
167	{
168	int n = 0;
169	for (prev = elt; prev; prev = prev->next)
170	n++;
171	release_overhead (b: head, amount: sizeof (bitmap_element) * n, remove_from_map: false);
172	}
173
174	prev = elt->prev;
175	if (prev)
176	{
177	prev->next = NULL;
178	if (head->current->indx > prev->indx)
179	{
180	head->current = prev;
181	head->indx = prev->indx;
182	}
183	}
184	else
185	{
186	head->first = NULL;
187	head->current = NULL;
188	head->indx = 0;
189	}
190
191	/* Put the entire list onto the freelist in one operation. */
192	if (bit_obstack)
193	{
194	elt->prev = bit_obstack->elements;
195	bit_obstack->elements = elt;
196	}
197	else
198	{
199	elt->prev = bitmap_ggc_free;
200	bitmap_ggc_free = elt;
201	}
202	}
203
204	/* Linked-list view of bitmaps.
205
206	In this representation, the bitmap elements form a double-linked list
207	with elements sorted by increasing index. */
208
209	/* Link the bitmap element into the current bitmap linked list. */
210
211	static inline void
212	bitmap_list_link_element (bitmap head, bitmap_element *element)
213	{
214	unsigned int indx = element->indx;
215	bitmap_element *ptr;
216
217	gcc_checking_assert (!head->tree_form);
218
219	/* If this is the first and only element, set it in. */
220	if (head->first == 0)
221	{
222	element->next = element->prev = 0;
223	head->first = element;
224	}
225
226	/* If this index is less than that of the current element, it goes someplace
227	before the current element. */
228	else if (indx < head->indx)
229	{
230	for (ptr = head->current;
231	ptr->prev != 0 && ptr->prev->indx > indx;
232	ptr = ptr->prev)
233	;
234
235	if (ptr->prev)
236	ptr->prev->next = element;
237	else
238	head->first = element;
239
240	element->prev = ptr->prev;
241	element->next = ptr;
242	ptr->prev = element;
243	}
244
245	/* Otherwise, it must go someplace after the current element. */
246	else
247	{
248	for (ptr = head->current;
249	ptr->next != 0 && ptr->next->indx < indx;
250	ptr = ptr->next)
251	;
252
253	if (ptr->next)
254	ptr->next->prev = element;
255
256	element->next = ptr->next;
257	element->prev = ptr;
258	ptr->next = element;
259	}
260
261	/* Set up so this is the first element searched. */
262	head->current = element;
263	head->indx = indx;
264	}
265
266	/* Unlink the bitmap element from the current bitmap linked list,
267	and return it to the freelist. */
268
269	static inline void
270	bitmap_list_unlink_element (bitmap head, bitmap_element *element,
271	bool to_freelist = true)
272	{
273	bitmap_element *next = element->next;
274	bitmap_element *prev = element->prev;
275
276	gcc_checking_assert (!head->tree_form);
277
278	if (prev)
279	prev->next = next;
280
281	if (next)
282	next->prev = prev;
283
284	if (head->first == element)
285	head->first = next;
286
287	/* Since the first thing we try is to insert before current,
288	make current the next entry in preference to the previous. */
289	if (head->current == element)
290	{
291	head->current = next != 0 ? next : prev;
292	if (head->current)
293	head->indx = head->current->indx;
294	else
295	head->indx = 0;
296	}
297
298	if (to_freelist)
299	bitmap_elem_to_freelist (head, elt: element);
300	}
301
302	/* Insert a new uninitialized element (or NODE if not NULL) into bitmap
303	HEAD after element ELT. If ELT is NULL, insert the element at the start.
304	Return the new element. */
305
306	static bitmap_element *
307	bitmap_list_insert_element_after (bitmap head,
308	bitmap_element *elt, unsigned int indx,
309	bitmap_element *node = NULL)
310	{
311	if (!node)
312	node = bitmap_element_allocate (head);
313	node->indx = indx;
314
315	gcc_checking_assert (!head->tree_form);
316
317	if (!elt)
318	{
319	if (!head->current)
320	{
321	head->current = node;
322	head->indx = indx;
323	}
324	node->next = head->first;
325	if (node->next)
326	node->next->prev = node;
327	head->first = node;
328	node->prev = NULL;
329	}
330	else
331	{
332	gcc_checking_assert (head->current);
333	node->next = elt->next;
334	if (node->next)
335	node->next->prev = node;
336	elt->next = node;
337	node->prev = elt;
338	}
339	return node;
340	}
341
342	/* Return the element for INDX, or NULL if the element doesn't exist.
343	Update the `current' field even if we can't find an element that
344	would hold the bitmap's bit to make eventual allocation
345	faster. */
346
347	static inline bitmap_element *
348	bitmap_list_find_element (bitmap head, unsigned int indx)
349	{
350	bitmap_element *element;
351
352	if (head->current == NULL
353	|| head->indx == indx)
354	return head->current;
355
356	if (head->current == head->first
357	&& head->first->next == NULL)
358	return NULL;
359
360	/* Usage can be NULL due to allocated bitmaps for which we do not
361	call initialize function. */
362	bitmap_usage *usage = NULL;
363	if (GATHER_STATISTICS)
364	usage = bitmap_mem_desc.get_descriptor_for_instance (ptr: head);
365
366	/* This bitmap has more than one element, and we're going to look
367	through the elements list. Count that as a search. */
368	if (GATHER_STATISTICS && usage)
369	usage->m_nsearches++;
370
371	if (head->indx < indx)
372	/* INDX is beyond head->indx. Search from head->current
373	forward. */
374	for (element = head->current;
375	element->next != 0 && element->indx < indx;
376	element = element->next)
377	{
378	if (GATHER_STATISTICS && usage)
379	usage->m_search_iter++;
380	}
381
382	else if (head->indx / 2 < indx)
383	/* INDX is less than head->indx and closer to head->indx than to
384	0. Search from head->current backward. */
385	for (element = head->current;
386	element->prev != 0 && element->indx > indx;
387	element = element->prev)
388	{
389	if (GATHER_STATISTICS && usage)
390	usage->m_search_iter++;
391	}
392
393	else
394	/* INDX is less than head->indx and closer to 0 than to
395	head->indx. Search from head->first forward. */
396	for (element = head->first;
397	element->next != 0 && element->indx < indx;
398	element = element->next)
399	{
400	if (GATHER_STATISTICS && usage)
401	usage->m_search_iter++;
402	}
403
404	/* `element' is the nearest to the one we want. If it's not the one we
405	want, the one we want doesn't exist. */
406	gcc_checking_assert (element != NULL);
407	head->current = element;
408	head->indx = element->indx;
409	if (element->indx != indx)
410	element = 0;
411	return element;
412	}
413
414
415	/* Splay-tree view of bitmaps.
416
417	This is an almost one-to-one the implementatin of the simple top-down
418	splay tree in Sleator and Tarjan's "Self-adjusting Binary Search Trees".
419	It is probably not the most efficient form of splay trees, but it should
420	be good enough to experiment with this idea of bitmaps-as-trees.
421
422	For all functions below, the variable or function argument "t" is a node
423	in the tree, and "e" is a temporary or new node in the tree. The rest
424	is sufficiently straigh-forward (and very well explained in the paper)
425	that comment would only clutter things. */
426
427	static inline void
428	bitmap_tree_link_left (bitmap_element * &t, bitmap_element * &l)
429	{
430	l->next = t;
431	l = t;
432	t = t->next;
433	}
434
435	static inline void
436	bitmap_tree_link_right (bitmap_element * &t, bitmap_element * &r)
437	{
438	r->prev = t;
439	r = t;
440	t = t->prev;
441	}
442
443	static inline void
444	bitmap_tree_rotate_left (bitmap_element * &t)
445	{
446	bitmap_element *e = t->next;
447	t->next = t->next->prev;
448	e->prev = t;
449	t = e;
450	}
451
452	static inline void
453	bitmap_tree_rotate_right (bitmap_element * &t)
454	{
455	bitmap_element *e = t->prev;
456	t->prev = t->prev->next;
457	e->next = t;
458	t = e;
459	}
460
461	static bitmap_element *
462	bitmap_tree_splay (bitmap head, bitmap_element *t, unsigned int indx)
463	{
464	bitmap_element N, *l, *r;
465
466	if (t == NULL)
467	return NULL;
468
469	bitmap_usage *usage = NULL;
470	if (GATHER_STATISTICS)
471	usage = bitmap_mem_desc.get_descriptor_for_instance (ptr: head);
472
473	N.prev = N.next = NULL;
474	l = r = &N;
475
476	while (indx != t->indx)
477	{
478	if (GATHER_STATISTICS && usage)
479	usage->m_search_iter++;
480
481	if (indx < t->indx)
482	{
483	if (t->prev != NULL && indx < t->prev->indx)
484	bitmap_tree_rotate_right (t);
485	if (t->prev == NULL)
486	break;
487	bitmap_tree_link_right (t, r);
488	}
489	else if (indx > t->indx)
490	{
491	if (t->next != NULL && indx > t->next->indx)
492	bitmap_tree_rotate_left (t);
493	if (t->next == NULL)
494	break;
495	bitmap_tree_link_left (t, l);
496	}
497	}
498
499	l->next = t->prev;
500	r->prev = t->next;
501	t->prev = N.next;
502	t->next = N.prev;
503	return t;
504	}
505
506	/* Link bitmap element E into the current bitmap splay tree. */
507
508	static inline void
509	bitmap_tree_link_element (bitmap head, bitmap_element *e)
510	{
511	if (head->first == NULL)
512	e->prev = e->next = NULL;
513	else
514	{
515	bitmap_element *t = bitmap_tree_splay (head, t: head->first, indx: e->indx);
516	if (e->indx < t->indx)
517	{
518	e->prev = t->prev;
519	e->next = t;
520	t->prev = NULL;
521	}
522	else if (e->indx > t->indx)
523	{
524	e->next = t->next;
525	e->prev = t;
526	t->next = NULL;
527	}
528	else
529	gcc_unreachable ();
530	}
531	head->first = e;
532	head->current = e;
533	head->indx = e->indx;
534	}
535
536	/* Unlink bitmap element E from the current bitmap splay tree,
537	and return it to the freelist. */
538
539	static void
540	bitmap_tree_unlink_element (bitmap head, bitmap_element *e)
541	{
542	bitmap_element *t = bitmap_tree_splay (head, t: head->first, indx: e->indx);
543
544	gcc_checking_assert (t == e);
545
546	if (e->prev == NULL)
547	t = e->next;
548	else
549	{
550	t = bitmap_tree_splay (head, t: e->prev, indx: e->indx);
551	t->next = e->next;
552	}
553	head->first = t;
554	head->current = t;
555	head->indx = (t != NULL) ? t->indx : 0;
556
557	bitmap_elem_to_freelist (head, elt: e);
558	}
559
560	/* Return the element for INDX, or NULL if the element doesn't exist. */
561
562	static inline bitmap_element *
563	bitmap_tree_find_element (bitmap head, unsigned int indx)
564	{
565	if (head->current == NULL
566	|| head->indx == indx)
567	return head->current;
568
569	/* Usage can be NULL due to allocated bitmaps for which we do not
570	call initialize function. */
571	bitmap_usage *usage = NULL;
572	if (GATHER_STATISTICS)
573	usage = bitmap_mem_desc.get_descriptor_for_instance (ptr: head);
574
575	/* This bitmap has more than one element, and we're going to look
576	through the elements list. Count that as a search. */
577	if (GATHER_STATISTICS && usage)
578	usage->m_nsearches++;
579
580	bitmap_element *element = bitmap_tree_splay (head, t: head->first, indx);
581	gcc_checking_assert (element != NULL);
582	head->first = element;
583	head->current = element;
584	head->indx = element->indx;
585	if (element->indx != indx)
586	element = 0;
587	return element;
588	}
589
590	/* Converting bitmap views from linked-list to tree and vice versa. */
591
592	/* Splice element E and all elements with a larger index from
593	bitmap HEAD, convert the spliced elements to the linked-list
594	view, and return the head of the list (which should be E again), */
595
596	static bitmap_element *
597	bitmap_tree_listify_from (bitmap head, bitmap_element *e)
598	{
599	bitmap_element *t, *erb;
600
601	/* Detach the right branch from E (all elements with indx > E->indx),
602	and splay E to the root. */
603	erb = e->next;
604	e->next = NULL;
605	t = bitmap_tree_splay (head, t: head->first, indx: e->indx);
606	gcc_checking_assert (t == e);
607
608	/* Because E has no right branch, and we rotated it to the root,
609	the left branch is the new root. */
610	t = e->prev;
611	head->first = t;
612	head->current = t;
613	head->indx = (t != NULL) ? t->indx : 0;
614
615	/* Detach the tree from E, and re-attach the right branch of E. */
616	e->prev = NULL;
617	e->next = erb;
618
619	/* The tree is now valid again. Now we need to "un-tree" E.
620	It is imperative that a non-recursive implementation is used
621	for this, because splay trees have a worst case depth of O(N)
622	for a tree with N nodes. A recursive implementation could
623	result in a stack overflow for a sufficiently large, unbalanced
624	bitmap tree. */
625
626	auto_vec<bitmap_element *, 32> stack;
627	auto_vec<bitmap_element *, 32> sorted_elements;
628	bitmap_element *n = e;
629
630	while (true)
631	{
632	while (n != NULL)
633	{
634	stack.safe_push (obj: n);
635	n = n->prev;
636	}
637
638	if (stack.is_empty ())
639	break;
640
641	n = stack.pop ();
642	sorted_elements.safe_push (obj: n);
643	n = n->next;
644	}
645
646	gcc_assert (sorted_elements[0] == e);
647
648	bitmap_element *prev = NULL;
649	unsigned ix;
650	FOR_EACH_VEC_ELT (sorted_elements, ix, n)
651	{
652	if (prev != NULL)
653	prev->next = n;
654	n->prev = prev;
655	n->next = NULL;
656	prev = n;
657	}
658
659	return e;
660	}
661
662	/* Convert bitmap HEAD from splay-tree view to linked-list view. */
663
664	void
665	bitmap_list_view (bitmap head)
666	{
667	bitmap_element *ptr;
668
669	gcc_assert (head->tree_form);
670
671	ptr = head->first;
672	if (ptr)
673	{
674	while (ptr->prev)
675	bitmap_tree_rotate_right (t&: ptr);
676	head->first = ptr;
677	head->first = bitmap_tree_listify_from (head, e: ptr);
678	}
679
680	head->tree_form = false;
681	if (!head->current)
682	{
683	head->current = head->first;
684	head->indx = head->current ? head->current->indx : 0;
685	}
686	}
687
688	/* Convert bitmap HEAD from linked-list view to splay-tree view.
689	This is simply a matter of dropping the prev or next pointers
690	and setting the tree_form flag. The tree will balance itself
691	if and when it is used. */
692
693	void
694	bitmap_tree_view (bitmap head)
695	{
696	bitmap_element *ptr;
697
698	gcc_assert (! head->tree_form);
699
700	ptr = head->first;
701	while (ptr)
702	{
703	ptr->prev = NULL;
704	ptr = ptr->next;
705	}
706
707	head->tree_form = true;
708	}
709
710	/* Clear a bitmap by freeing all its elements. */
711
712	void
713	bitmap_clear (bitmap head)
714	{
715	if (head->first == NULL)
716	return;
717	if (head->tree_form)
718	{
719	bitmap_element *e, *t;
720	for (e = head->first; e->prev; e = e->prev)
721	/* Loop to find the element with the smallest index. */ ;
722	t = bitmap_tree_splay (head, t: head->first, indx: e->indx);
723	gcc_checking_assert (t == e);
724	head->first = t;
725	}
726	bitmap_elt_clear_from (head, elt: head->first);
727	}
728
729	/* Initialize a bitmap obstack. If BIT_OBSTACK is NULL, initialize
730	the default bitmap obstack. */
731
732	void
733	bitmap_obstack_initialize (bitmap_obstack *bit_obstack)
734	{
735	if (!bit_obstack)
736	{
737	if (bitmap_default_obstack_depth++)
738	return;
739	bit_obstack = &bitmap_default_obstack;
740	}
741
742	#if !defined(__GNUC__) || (__GNUC__ < 2)
743	#define __alignof__(type) 0
744	#endif
745
746	bit_obstack->elements = NULL;
747	bit_obstack->heads = NULL;
748	obstack_specify_allocation (&bit_obstack->obstack, OBSTACK_CHUNK_SIZE,
749	__alignof__ (bitmap_element),
750	obstack_chunk_alloc,
751	obstack_chunk_free);
752	}
753
754	/* Release the memory from a bitmap obstack. If BIT_OBSTACK is NULL,
755	release the default bitmap obstack. */
756
757	void
758	bitmap_obstack_release (bitmap_obstack *bit_obstack)
759	{
760	if (!bit_obstack)
761	{
762	if (--bitmap_default_obstack_depth)
763	{
764	gcc_assert (bitmap_default_obstack_depth > 0);
765	return;
766	}
767	bit_obstack = &bitmap_default_obstack;
768	}
769
770	bit_obstack->elements = NULL;
771	bit_obstack->heads = NULL;
772	obstack_free (&bit_obstack->obstack, NULL);
773	}
774
775	/* Create a new bitmap on an obstack. If BIT_OBSTACK is NULL, create
776	it on the default bitmap obstack. */
777
778	bitmap
779	bitmap_alloc (bitmap_obstack *bit_obstack MEM_STAT_DECL)
780	{
781	bitmap map;
782
783	if (!bit_obstack)
784	bit_obstack = &bitmap_default_obstack;
785	map = bit_obstack->heads;
786	if (map)
787	bit_obstack->heads = (class bitmap_head *) map->first;
788	else
789	map = XOBNEW (&bit_obstack->obstack, bitmap_head);
790	bitmap_initialize (head: map, obstack: bit_obstack PASS_MEM_STAT);
791
792	if (GATHER_STATISTICS)
793	register_overhead (b: map, amount: sizeof (bitmap_head));
794
795	return map;
796	}
797
798	/* Create a new GCd bitmap. */
799
800	bitmap
801	bitmap_gc_alloc (ALONE_MEM_STAT_DECL)
802	{
803	bitmap map;
804
805	map = ggc_alloc<bitmap_head> ();
806	bitmap_initialize (head: map, NULL PASS_MEM_STAT);
807
808	if (GATHER_STATISTICS)
809	register_overhead (b: map, amount: sizeof (bitmap_head));
810
811	return map;
812	}
813
814	/* Release an obstack allocated bitmap. */
815
816	void
817	bitmap_obstack_free (bitmap map)
818	{
819	if (map)
820	{
821	bitmap_clear (head: map);
822	map->first = (bitmap_element *) map->obstack->heads;
823
824	if (GATHER_STATISTICS)
825	release_overhead (b: map, amount: sizeof (bitmap_head), remove_from_map: true);
826
827	map->obstack->heads = map;
828	}
829	}
830
831
832	/* Return nonzero if all bits in an element are zero. */
833
834	static inline int
835	bitmap_element_zerop (const bitmap_element *element)
836	{
837	#if BITMAP_ELEMENT_WORDS == 2
838	return (element->bits[0] | element->bits[1]) == 0;
839	#else
840	unsigned i;
841
842	for (i = 0; i < BITMAP_ELEMENT_WORDS; i++)
843	if (element->bits[i] != 0)
844	return 0;
845
846	return 1;
847	#endif
848	}
849
850	/* Copy a bitmap to another bitmap. */
851
852	void
853	bitmap_copy (bitmap to, const_bitmap from)
854	{
855	const bitmap_element *from_ptr;
856	bitmap_element *to_ptr = 0;
857
858	gcc_checking_assert (!to->tree_form && !from->tree_form);
859
860	bitmap_clear (head: to);
861
862	/* Copy elements in forward direction one at a time. */
863	for (from_ptr = from->first; from_ptr; from_ptr = from_ptr->next)
864	{
865	bitmap_element *to_elt = bitmap_element_allocate (head: to);
866
867	to_elt->indx = from_ptr->indx;
868	memcpy (dest: to_elt->bits, src: from_ptr->bits, n: sizeof (to_elt->bits));
869
870	/* Here we have a special case of bitmap_list_link_element,
871	for the case where we know the links are being entered
872	in sequence. */
873	if (to_ptr == 0)
874	{
875	to->first = to->current = to_elt;
876	to->indx = from_ptr->indx;
877	to_elt->next = to_elt->prev = 0;
878	}
879	else
880	{
881	to_elt->prev = to_ptr;
882	to_elt->next = 0;
883	to_ptr->next = to_elt;
884	}
885
886	to_ptr = to_elt;
887	}
888	}
889
890	/* Move a bitmap to another bitmap. */
891
892	void
893	bitmap_move (bitmap to, bitmap from)
894	{
895	gcc_assert (to->obstack == from->obstack);
896
897	bitmap_clear (head: to);
898
899	size_t sz = 0;
900	if (GATHER_STATISTICS)
901	{
902	for (bitmap_element *e = to->first; e; e = e->next)
903	sz += sizeof (bitmap_element);
904	register_overhead (b: to, amount: sz);
905	}
906
907	*to = *from;
908
909	if (GATHER_STATISTICS)
910	release_overhead (b: from, amount: sz, remove_from_map: false);
911	}
912
913	/* Clear a single bit in a bitmap. Return true if the bit changed. */
914
915	bool
916	bitmap_clear_bit (bitmap head, int bit)
917	{
918	unsigned int indx = bit / BITMAP_ELEMENT_ALL_BITS;
919	bitmap_element *ptr;
920
921	if (!head->tree_form)
922	ptr = bitmap_list_find_element (head, indx);
923	else
924	ptr = bitmap_tree_find_element (head, indx);
925	if (ptr != 0)
926	{
927	unsigned bit_num = bit % BITMAP_WORD_BITS;
928	unsigned word_num = bit / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS;
929	BITMAP_WORD bit_val = ((BITMAP_WORD) 1) << bit_num;
930	bool res = (ptr->bits[word_num] & bit_val) != 0;
931	if (res)
932	{
933	ptr->bits[word_num] &= ~bit_val;
934	/* If we cleared the entire word, free up the element. */
935	if (!ptr->bits[word_num]
936	&& bitmap_element_zerop (element: ptr))
937	{
938	if (!head->tree_form)
939	bitmap_list_unlink_element (head, element: ptr);
940	else
941	bitmap_tree_unlink_element (head, e: ptr);
942	}
943	}
944
945	return res;
946	}
947
948	return false;
949	}
950
951	/* Set a single bit in a bitmap. Return true if the bit changed. */
952
953	bool
954	bitmap_set_bit (bitmap head, int bit)
955	{
956	unsigned indx = bit / BITMAP_ELEMENT_ALL_BITS;
957	bitmap_element *ptr;
958	if (!head->tree_form)
959	ptr = bitmap_list_find_element (head, indx);
960	else
961	ptr = bitmap_tree_find_element (head, indx);
962	unsigned word_num = bit / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS;
963	unsigned bit_num = bit % BITMAP_WORD_BITS;
964	BITMAP_WORD bit_val = ((BITMAP_WORD) 1) << bit_num;
965
966	if (ptr != 0)
967	{
968	bool res = (ptr->bits[word_num] & bit_val) == 0;
969	if (res)
970	ptr->bits[word_num] |= bit_val;
971	return res;
972	}
973
974	ptr = bitmap_element_allocate (head);
975	ptr->indx = bit / BITMAP_ELEMENT_ALL_BITS;
976	ptr->bits[word_num] = bit_val;
977	if (!head->tree_form)
978	bitmap_list_link_element (head, element: ptr);
979	else
980	bitmap_tree_link_element (head, e: ptr);
981	return true;
982	}
983
984	/* Return whether a bit is set within a bitmap. */
985
986	bool
987	bitmap_bit_p (const_bitmap head, int bit)
988	{
989	unsigned int indx = bit / BITMAP_ELEMENT_ALL_BITS;
990	const bitmap_element *ptr;
991	unsigned bit_num;
992	unsigned word_num;
993
994	if (!head->tree_form)
995	ptr = bitmap_list_find_element (head: const_cast<bitmap> (head), indx);
996	else
997	ptr = bitmap_tree_find_element (head: const_cast<bitmap> (head), indx);
998	if (ptr == 0)
999	return 0;
1000
1001	bit_num = bit % BITMAP_WORD_BITS;
1002	word_num = bit / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS;
1003
1004	return (ptr->bits[word_num] >> bit_num) & 1;
1005	}
1006
1007	/* Set CHUNK_SIZE bits at a time in bitmap HEAD.
1008	Store CHUNK_VALUE starting at bits CHUNK * chunk_size.
1009	This is the set routine for viewing bitmap as a multi-bit sparse array. */
1010
1011	void
1012	bitmap_set_aligned_chunk (bitmap head, unsigned int chunk,
1013	unsigned int chunk_size, BITMAP_WORD chunk_value)
1014	{
1015	// Ensure chunk size is a power of 2 and fits in BITMAP_WORD.
1016	gcc_checking_assert (pow2p_hwi (chunk_size));
1017	gcc_checking_assert (chunk_size < (sizeof (BITMAP_WORD) * CHAR_BIT));
1018
1019	// Ensure chunk_value is within range of chunk_size bits.
1020	BITMAP_WORD max_value = (1 << chunk_size) - 1;
1021	gcc_checking_assert (chunk_value <= max_value);
1022
1023	unsigned bit = chunk * chunk_size;
1024	unsigned indx = bit / BITMAP_ELEMENT_ALL_BITS;
1025	bitmap_element *ptr;
1026	if (!head->tree_form)
1027	ptr = bitmap_list_find_element (head, indx);
1028	else
1029	ptr = bitmap_tree_find_element (head, indx);
1030	unsigned word_num = bit / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS;
1031	unsigned bit_num = bit % BITMAP_WORD_BITS;
1032	BITMAP_WORD bit_val = chunk_value << bit_num;
1033	BITMAP_WORD mask = ~(max_value << bit_num);
1034
1035	if (ptr != 0)
1036	{
1037	ptr->bits[word_num] &= mask;
1038	ptr->bits[word_num] |= bit_val;
1039	return;
1040	}
1041
1042	ptr = bitmap_element_allocate (head);
1043	ptr->indx = bit / BITMAP_ELEMENT_ALL_BITS;
1044	ptr->bits[word_num] = bit_val;
1045	if (!head->tree_form)
1046	bitmap_list_link_element (head, element: ptr);
1047	else
1048	bitmap_tree_link_element (head, e: ptr);
1049	}
1050
1051	/* This is the get routine for viewing bitmap as a multi-bit sparse array.
1052	Return a set of CHUNK_SIZE consecutive bits from HEAD, starting at bit
1053	CHUNK * chunk_size. */
1054
1055	BITMAP_WORD
1056	bitmap_get_aligned_chunk (const_bitmap head, unsigned int chunk,
1057	unsigned int chunk_size)
1058	{
1059	// Ensure chunk size is a power of 2, fits in BITMAP_WORD and is in range.
1060	gcc_checking_assert (pow2p_hwi (chunk_size));
1061	gcc_checking_assert (chunk_size < (sizeof (BITMAP_WORD) * CHAR_BIT));
1062
1063	BITMAP_WORD max_value = (1 << chunk_size) - 1;
1064	unsigned bit = chunk * chunk_size;
1065	unsigned int indx = bit / BITMAP_ELEMENT_ALL_BITS;
1066	const bitmap_element *ptr;
1067	unsigned bit_num;
1068	unsigned word_num;
1069
1070	if (!head->tree_form)
1071	ptr = bitmap_list_find_element (head: const_cast<bitmap> (head), indx);
1072	else
1073	ptr = bitmap_tree_find_element (head: const_cast<bitmap> (head), indx);
1074	if (ptr == 0)
1075	return 0;
1076
1077	bit_num = bit % BITMAP_WORD_BITS;
1078	word_num = bit / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS;
1079
1080	// Return 4 bits.
1081	return (ptr->bits[word_num] >> bit_num) & max_value;
1082	}
1083
1084	#if GCC_VERSION < 3400
1085	/* Table of number of set bits in a character, indexed by value of char. */
1086	static const unsigned char popcount_table[] =
1087	{
1088	0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4,1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,
1089	1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
1090	1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
1091	2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
1092	1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
1093	2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
1094	2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
1095	3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,
1096	};
1097
1098	static unsigned long
1099	bitmap_popcount (BITMAP_WORD a)
1100	{
1101	unsigned long ret = 0;
1102	unsigned i;
1103
1104	/* Just do this the table way for now */
1105	for (i = 0; i < BITMAP_WORD_BITS; i+= 8)
1106	ret += popcount_table[(a >> i) & 0xff];
1107	return ret;
1108	}
1109	#endif
1110
1111	/* Count and return the number of bits set in the bitmap word BITS. */
1112	static unsigned long
1113	bitmap_count_bits_in_word (const BITMAP_WORD *bits)
1114	{
1115	unsigned long count = 0;
1116
1117	for (unsigned ix = 0; ix != BITMAP_ELEMENT_WORDS; ix++)
1118	{
1119	#if GCC_VERSION >= 3400
1120	/* Note that popcountl matches BITMAP_WORD in type, so the actual size
1121	of BITMAP_WORD is not material. */
1122	count += __builtin_popcountl (bits[ix]);
1123	#else
1124	count += bitmap_popcount (bits[ix]);
1125	#endif
1126	}
1127	return count;
1128	}
1129
1130	/* Count the number of bits set in the bitmap, and return it. */
1131
1132	unsigned long
1133	bitmap_count_bits (const_bitmap a)
1134	{
1135	unsigned long count = 0;
1136	const bitmap_element *elt;
1137
1138	gcc_checking_assert (!a->tree_form);
1139	for (elt = a->first; elt; elt = elt->next)
1140	count += bitmap_count_bits_in_word (bits: elt->bits);
1141
1142	return count;
1143	}
1144
1145	/* Count the number of unique bits set in A and B and return it. */
1146
1147	unsigned long
1148	bitmap_count_unique_bits (const_bitmap a, const_bitmap b)
1149	{
1150	unsigned long count = 0;
1151	const bitmap_element *elt_a, *elt_b;
1152
1153	for (elt_a = a->first, elt_b = b->first; elt_a && elt_b; )
1154	{
1155	/* If we're at different indices, then count all the bits
1156	in the lower element. If we're at the same index, then
1157	count the bits in the IOR of the two elements. */
1158	if (elt_a->indx < elt_b->indx)
1159	{
1160	count += bitmap_count_bits_in_word (bits: elt_a->bits);
1161	elt_a = elt_a->next;
1162	}
1163	else if (elt_b->indx < elt_a->indx)
1164	{
1165	count += bitmap_count_bits_in_word (bits: elt_b->bits);
1166	elt_b = elt_b->next;
1167	}
1168	else
1169	{
1170	BITMAP_WORD bits[BITMAP_ELEMENT_WORDS];
1171	for (unsigned ix = 0; ix != BITMAP_ELEMENT_WORDS; ix++)
1172	bits[ix] = elt_a->bits[ix] | elt_b->bits[ix];
1173	count += bitmap_count_bits_in_word (bits);
1174	elt_a = elt_a->next;
1175	elt_b = elt_b->next;
1176	}
1177	}
1178	return count;
1179	}
1180
1181	/* Return true if the bitmap has a single bit set. Otherwise return
1182	false. */
1183
1184	bool
1185	bitmap_single_bit_set_p (const_bitmap a)
1186	{
1187	unsigned long count = 0;
1188	const bitmap_element *elt;
1189	unsigned ix;
1190
1191	if (bitmap_empty_p (map: a))
1192	return false;
1193
1194	elt = a->first;
1195
1196	/* As there are no completely empty bitmap elements, a second one
1197	means we have more than one bit set. */
1198	if (elt->next != NULL
1199	&& (!a->tree_form || elt->prev != NULL))
1200	return false;
1201
1202	for (ix = 0; ix != BITMAP_ELEMENT_WORDS; ix++)
1203	{
1204	#if GCC_VERSION >= 3400
1205	/* Note that popcountl matches BITMAP_WORD in type, so the actual size
1206	of BITMAP_WORD is not material. */
1207	count += __builtin_popcountl (elt->bits[ix]);
1208	#else
1209	count += bitmap_popcount (elt->bits[ix]);
1210	#endif
1211	if (count > 1)
1212	return false;
1213	}
1214
1215	return count == 1;
1216	}
1217
1218
1219	/* Return the bit number of the first set bit in the bitmap. The
1220	bitmap must be non-empty. When CLEAR is true it clears the bit. */
1221
1222	static unsigned
1223	bitmap_first_set_bit_worker (bitmap a, bool clear)
1224	{
1225	bitmap_element *elt = a->first;
1226	unsigned bit_no;
1227	BITMAP_WORD word;
1228	unsigned ix;
1229
1230	gcc_checking_assert (elt);
1231
1232	if (a->tree_form)
1233	while (elt->prev)
1234	elt = elt->prev;
1235
1236	bit_no = elt->indx * BITMAP_ELEMENT_ALL_BITS;
1237	for (ix = 0; ix != BITMAP_ELEMENT_WORDS; ix++)
1238	{
1239	word = elt->bits[ix];
1240	if (word)
1241	goto found_bit;
1242	}
1243	gcc_unreachable ();
1244	found_bit:
1245	bit_no += ix * BITMAP_WORD_BITS;
1246
1247	#if GCC_VERSION >= 3004
1248	gcc_assert (sizeof (long) == sizeof (word));
1249	bit_no += __builtin_ctzl (word);
1250	#else
1251	/* Binary search for the first set bit. */
1252	#if BITMAP_WORD_BITS > 64
1253	#error "Fill out the table."
1254	#endif
1255	#if BITMAP_WORD_BITS > 32
1256	if (!(word & 0xffffffff))
1257	word >>= 32, bit_no += 32;
1258	#endif
1259	if (!(word & 0xffff))
1260	word >>= 16, bit_no += 16;
1261	if (!(word & 0xff))
1262	word >>= 8, bit_no += 8;
1263	if (!(word & 0xf))
1264	word >>= 4, bit_no += 4;
1265	if (!(word & 0x3))
1266	word >>= 2, bit_no += 2;
1267	if (!(word & 0x1))
1268	word >>= 1, bit_no += 1;
1269
1270	gcc_checking_assert (word & 1);
1271	#endif
1272
1273	if (clear)
1274	{
1275	elt->bits[ix] &= ~((BITMAP_WORD) 1 << (bit_no % BITMAP_WORD_BITS));
1276	/* If we cleared the entire word, free up the element. */
1277	if (!elt->bits[ix]
1278	&& bitmap_element_zerop (element: elt))
1279	{
1280	if (!a->tree_form)
1281	bitmap_list_unlink_element (head: a, element: elt);
1282	else
1283	bitmap_tree_unlink_element (head: a, e: elt);
1284	}
1285	}
1286
1287	return bit_no;
1288	}
1289
1290	/* Return the bit number of the first set bit in the bitmap. The
1291	bitmap must be non-empty. */
1292
1293	unsigned
1294	bitmap_first_set_bit (const_bitmap a)
1295	{
1296	return bitmap_first_set_bit_worker (a: const_cast<bitmap> (a), clear: false);
1297	}
1298
1299	/* Return and clear the bit number of the first set bit in the bitmap. The
1300	bitmap must be non-empty. */
1301
1302	unsigned
1303	bitmap_clear_first_set_bit (bitmap a)
1304	{
1305	return bitmap_first_set_bit_worker (a, clear: true);
1306	}
1307
1308	/* Return the bit number of the first set bit in the bitmap. The
1309	bitmap must be non-empty. */
1310
1311	unsigned
1312	bitmap_last_set_bit (const_bitmap a)
1313	{
1314	const bitmap_element *elt;
1315	unsigned bit_no;
1316	BITMAP_WORD word;
1317	int ix;
1318
1319	if (a->tree_form)
1320	elt = a->first;
1321	else
1322	elt = a->current ? a->current : a->first;
1323	gcc_checking_assert (elt);
1324
1325	while (elt->next)
1326	elt = elt->next;
1327
1328	bit_no = elt->indx * BITMAP_ELEMENT_ALL_BITS;
1329	for (ix = BITMAP_ELEMENT_WORDS - 1; ix >= 1; ix--)
1330	{
1331	word = elt->bits[ix];
1332	if (word)
1333	goto found_bit;
1334	}
1335	gcc_assert (elt->bits[ix] != 0);
1336	found_bit:
1337	bit_no += ix * BITMAP_WORD_BITS;
1338	#if GCC_VERSION >= 3004
1339	gcc_assert (sizeof (long) == sizeof (word));
1340	bit_no += BITMAP_WORD_BITS - __builtin_clzl (word) - 1;
1341	#else
1342	/* Hopefully this is a twos-complement host... */
1343	BITMAP_WORD x = word;
1344	x |= (x >> 1);
1345	x |= (x >> 2);
1346	x |= (x >> 4);
1347	x |= (x >> 8);
1348	x |= (x >> 16);
1349	#if BITMAP_WORD_BITS > 32
1350	x |= (x >> 32);
1351	#endif
1352	bit_no += bitmap_popcount (x) - 1;
1353	#endif
1354
1355	return bit_no;
1356	}
1357
1358
1359	/* DST = A & B. */
1360
1361	void
1362	bitmap_and (bitmap dst, const_bitmap a, const_bitmap b)
1363	{
1364	bitmap_element *dst_elt = dst->first;
1365	const bitmap_element *a_elt = a->first;
1366	const bitmap_element *b_elt = b->first;
1367	bitmap_element *dst_prev = NULL;
1368
1369	gcc_checking_assert (!dst->tree_form && !a->tree_form && !b->tree_form);
1370	gcc_assert (dst != a && dst != b);
1371
1372	if (a == b)
1373	{
1374	bitmap_copy (to: dst, from: a);
1375	return;
1376	}
1377
1378	while (a_elt && b_elt)
1379	{
1380	if (a_elt->indx < b_elt->indx)
1381	a_elt = a_elt->next;
1382	else if (b_elt->indx < a_elt->indx)
1383	b_elt = b_elt->next;
1384	else
1385	{
1386	/* Matching elts, generate A & B. */
1387	unsigned ix;
1388	BITMAP_WORD ior = 0;
1389
1390	if (!dst_elt)
1391	dst_elt = bitmap_list_insert_element_after (head: dst, elt: dst_prev,
1392	indx: a_elt->indx);
1393	else
1394	dst_elt->indx = a_elt->indx;
1395	for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
1396	{
1397	BITMAP_WORD r = a_elt->bits[ix] & b_elt->bits[ix];
1398
1399	dst_elt->bits[ix] = r;
1400	ior |= r;
1401	}
1402	if (ior)
1403	{
1404	dst_prev = dst_elt;
1405	dst_elt = dst_elt->next;
1406	}
1407	a_elt = a_elt->next;
1408	b_elt = b_elt->next;
1409	}
1410	}
1411	/* Ensure that dst->current is valid. */
1412	dst->current = dst->first;
1413	bitmap_elt_clear_from (head: dst, elt: dst_elt);
1414	gcc_checking_assert (!dst->current == !dst->first);
1415	if (dst->current)
1416	dst->indx = dst->current->indx;
1417	}
1418
1419	/* A &= B. Return true if A changed. */
1420
1421	bool
1422	bitmap_and_into (bitmap a, const_bitmap b)
1423	{
1424	bitmap_element *a_elt = a->first;
1425	const bitmap_element *b_elt = b->first;
1426	bitmap_element *next;
1427	bool changed = false;
1428
1429	gcc_checking_assert (!a->tree_form && !b->tree_form);
1430
1431	if (a == b)
1432	return false;
1433
1434	while (a_elt && b_elt)
1435	{
1436	if (a_elt->indx < b_elt->indx)
1437	{
1438	next = a_elt->next;
1439	bitmap_list_unlink_element (head: a, element: a_elt);
1440	a_elt = next;
1441	changed = true;
1442	}
1443	else if (b_elt->indx < a_elt->indx)
1444	b_elt = b_elt->next;
1445	else
1446	{
1447	/* Matching elts, generate A &= B. */
1448	unsigned ix;
1449	BITMAP_WORD ior = 0;
1450
1451	for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
1452	{
1453	BITMAP_WORD r = a_elt->bits[ix] & b_elt->bits[ix];
1454	if (a_elt->bits[ix] != r)
1455	changed = true;
1456	a_elt->bits[ix] = r;
1457	ior |= r;
1458	}
1459	next = a_elt->next;
1460	if (!ior)
1461	bitmap_list_unlink_element (head: a, element: a_elt);
1462	a_elt = next;
1463	b_elt = b_elt->next;
1464	}
1465	}
1466
1467	if (a_elt)
1468	{
1469	changed = true;
1470	bitmap_elt_clear_from (head: a, elt: a_elt);
1471	}
1472
1473	gcc_checking_assert (!a->current == !a->first
1474	&& (!a->current || a->indx == a->current->indx));
1475
1476	return changed;
1477	}
1478
1479
1480	/* Insert an element equal to SRC_ELT after DST_PREV, overwriting DST_ELT
1481	if non-NULL. CHANGED is true if the destination bitmap had already been
1482	changed; the new value of CHANGED is returned. */
1483
1484	static inline bool
1485	bitmap_elt_copy (bitmap dst, bitmap_element *dst_elt, bitmap_element *dst_prev,
1486	const bitmap_element *src_elt, bool changed)
1487	{
1488	if (!changed && dst_elt && dst_elt->indx == src_elt->indx)
1489	{
1490	unsigned ix;
1491
1492	for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
1493	if (src_elt->bits[ix] != dst_elt->bits[ix])
1494	{
1495	dst_elt->bits[ix] = src_elt->bits[ix];
1496	changed = true;
1497	}
1498	}
1499	else
1500	{
1501	changed = true;
1502	if (!dst_elt)
1503	dst_elt = bitmap_list_insert_element_after (head: dst, elt: dst_prev,
1504	indx: src_elt->indx);
1505	else
1506	dst_elt->indx = src_elt->indx;
1507	memcpy (dest: dst_elt->bits, src: src_elt->bits, n: sizeof (dst_elt->bits));
1508	}
1509	return changed;
1510	}
1511
1512
1513
1514	/* DST = A & ~B */
1515
1516	bool
1517	bitmap_and_compl (bitmap dst, const_bitmap a, const_bitmap b)
1518	{
1519	bitmap_element *dst_elt = dst->first;
1520	const bitmap_element *a_elt = a->first;
1521	const bitmap_element *b_elt = b->first;
1522	bitmap_element *dst_prev = NULL;
1523	bitmap_element **dst_prev_pnext = &dst->first;
1524	bool changed = false;
1525
1526	gcc_checking_assert (!dst->tree_form && !a->tree_form && !b->tree_form);
1527	gcc_assert (dst != a && dst != b);
1528
1529	if (a == b)
1530	{
1531	changed = !bitmap_empty_p (map: dst);
1532	bitmap_clear (head: dst);
1533	return changed;
1534	}
1535
1536	while (a_elt)
1537	{
1538	while (b_elt && b_elt->indx < a_elt->indx)
1539	b_elt = b_elt->next;
1540
1541	if (!b_elt || b_elt->indx > a_elt->indx)
1542	{
1543	changed = bitmap_elt_copy (dst, dst_elt, dst_prev, src_elt: a_elt, changed);
1544	dst_prev = *dst_prev_pnext;
1545	dst_prev_pnext = &dst_prev->next;
1546	dst_elt = *dst_prev_pnext;
1547	a_elt = a_elt->next;
1548	}
1549
1550	else
1551	{
1552	/* Matching elts, generate A & ~B. */
1553	unsigned ix;
1554	BITMAP_WORD ior = 0;
1555
1556	if (!changed && dst_elt && dst_elt->indx == a_elt->indx)
1557	{
1558	for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
1559	{
1560	BITMAP_WORD r = a_elt->bits[ix] & ~b_elt->bits[ix];
1561
1562	if (dst_elt->bits[ix] != r)
1563	{
1564	changed = true;
1565	dst_elt->bits[ix] = r;
1566	}
1567	ior |= r;
1568	}
1569	}
1570	else
1571	{
1572	bool new_element;
1573	if (!dst_elt || dst_elt->indx > a_elt->indx)
1574	{
1575	dst_elt = bitmap_list_insert_element_after (head: dst, elt: dst_prev,
1576	indx: a_elt->indx);
1577	new_element = true;
1578	}
1579	else
1580	{
1581	dst_elt->indx = a_elt->indx;
1582	new_element = false;
1583	}
1584
1585	for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
1586	{
1587	BITMAP_WORD r = a_elt->bits[ix] & ~b_elt->bits[ix];
1588
1589	dst_elt->bits[ix] = r;
1590	ior |= r;
1591	}
1592
1593	if (ior)
1594	changed = true;
1595	else
1596	{
1597	changed |= !new_element;
1598	bitmap_list_unlink_element (head: dst, element: dst_elt);
1599	dst_elt = *dst_prev_pnext;
1600	}
1601	}
1602
1603	if (ior)
1604	{
1605	dst_prev = *dst_prev_pnext;
1606	dst_prev_pnext = &dst_prev->next;
1607	dst_elt = *dst_prev_pnext;
1608	}
1609	a_elt = a_elt->next;
1610	b_elt = b_elt->next;
1611	}
1612	}
1613
1614	/* Ensure that dst->current is valid. */
1615	dst->current = dst->first;
1616
1617	if (dst_elt)
1618	{
1619	changed = true;
1620	bitmap_elt_clear_from (head: dst, elt: dst_elt);
1621	}
1622	gcc_checking_assert (!dst->current == !dst->first);
1623	if (dst->current)
1624	dst->indx = dst->current->indx;
1625
1626	return changed;
1627	}
1628
1629	/* A &= ~B. Returns true if A changes */
1630
1631	bool
1632	bitmap_and_compl_into (bitmap a, const_bitmap b)
1633	{
1634	bitmap_element *a_elt = a->first;
1635	const bitmap_element *b_elt = b->first;
1636	bitmap_element *next;
1637	BITMAP_WORD changed = 0;
1638
1639	gcc_checking_assert (!a->tree_form && !b->tree_form);
1640
1641	if (a == b)
1642	{
1643	if (bitmap_empty_p (map: a))
1644	return false;
1645	else
1646	{
1647	bitmap_clear (head: a);
1648	return true;
1649	}
1650	}
1651
1652	while (a_elt && b_elt)
1653	{
1654	if (a_elt->indx < b_elt->indx)
1655	a_elt = a_elt->next;
1656	else if (b_elt->indx < a_elt->indx)
1657	b_elt = b_elt->next;
1658	else
1659	{
1660	/* Matching elts, generate A &= ~B. */
1661	unsigned ix;
1662	BITMAP_WORD ior = 0;
1663
1664	for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
1665	{
1666	BITMAP_WORD cleared = a_elt->bits[ix] & b_elt->bits[ix];
1667	BITMAP_WORD r = a_elt->bits[ix] ^ cleared;
1668
1669	a_elt->bits[ix] = r;
1670	changed |= cleared;
1671	ior |= r;
1672	}
1673	next = a_elt->next;
1674	if (!ior)
1675	bitmap_list_unlink_element (head: a, element: a_elt);
1676	a_elt = next;
1677	b_elt = b_elt->next;
1678	}
1679	}
1680	gcc_checking_assert (!a->current == !a->first
1681	&& (!a->current || a->indx == a->current->indx));
1682	return changed != 0;
1683	}
1684
1685	/* Set COUNT bits from START in HEAD. */
1686	void
1687	bitmap_set_range (bitmap head, unsigned int start, unsigned int count)
1688	{
1689	unsigned int first_index, end_bit_plus1, last_index;
1690	bitmap_element *elt, *elt_prev;
1691	unsigned int i;
1692
1693	gcc_checking_assert (!head->tree_form);
1694
1695	if (!count)
1696	return;
1697
1698	if (count == 1)
1699	{
1700	bitmap_set_bit (head, bit: start);
1701	return;
1702	}
1703
1704	first_index = start / BITMAP_ELEMENT_ALL_BITS;
1705	end_bit_plus1 = start + count;
1706	last_index = (end_bit_plus1 - 1) / BITMAP_ELEMENT_ALL_BITS;
1707	elt = bitmap_list_find_element (head, indx: first_index);
1708
1709	/* If bitmap_list_find_element returns zero, the current is the closest block
1710	to the result. Otherwise, just use bitmap_element_allocate to
1711	ensure ELT is set; in the loop below, ELT == NULL means "insert
1712	at the end of the bitmap". */
1713	if (!elt)
1714	{
1715	elt = bitmap_element_allocate (head);
1716	elt->indx = first_index;
1717	bitmap_list_link_element (head, element: elt);
1718	}
1719
1720	gcc_checking_assert (elt->indx == first_index);
1721	elt_prev = elt->prev;
1722	for (i = first_index; i <= last_index; i++)
1723	{
1724	unsigned elt_start_bit = i * BITMAP_ELEMENT_ALL_BITS;
1725	unsigned elt_end_bit_plus1 = elt_start_bit + BITMAP_ELEMENT_ALL_BITS;
1726
1727	unsigned int first_word_to_mod;
1728	BITMAP_WORD first_mask;
1729	unsigned int last_word_to_mod;
1730	BITMAP_WORD last_mask;
1731	unsigned int ix;
1732
1733	if (!elt || elt->indx != i)
1734	elt = bitmap_list_insert_element_after (head, elt: elt_prev, indx: i);
1735
1736	if (elt_start_bit <= start)
1737	{
1738	/* The first bit to turn on is somewhere inside this
1739	elt. */
1740	first_word_to_mod = (start - elt_start_bit) / BITMAP_WORD_BITS;
1741
1742	/* This mask should have 1s in all bits >= start position. */
1743	first_mask =
1744	(((BITMAP_WORD) 1) << ((start % BITMAP_WORD_BITS))) - 1;
1745	first_mask = ~first_mask;
1746	}
1747	else
1748	{
1749	/* The first bit to turn on is below this start of this elt. */
1750	first_word_to_mod = 0;
1751	first_mask = ~(BITMAP_WORD) 0;
1752	}
1753
1754	if (elt_end_bit_plus1 <= end_bit_plus1)
1755	{
1756	/* The last bit to turn on is beyond this elt. */
1757	last_word_to_mod = BITMAP_ELEMENT_WORDS - 1;
1758	last_mask = ~(BITMAP_WORD) 0;
1759	}
1760	else
1761	{
1762	/* The last bit to turn on is inside to this elt. */
1763	last_word_to_mod =
1764	(end_bit_plus1 - elt_start_bit) / BITMAP_WORD_BITS;
1765
1766	/* The last mask should have 1s below the end bit. */
1767	last_mask =
1768	(((BITMAP_WORD) 1) << ((end_bit_plus1 % BITMAP_WORD_BITS))) - 1;
1769	}
1770
1771	if (first_word_to_mod == last_word_to_mod)
1772	{
1773	BITMAP_WORD mask = first_mask & last_mask;
1774	elt->bits[first_word_to_mod] |= mask;
1775	}
1776	else
1777	{
1778	elt->bits[first_word_to_mod] |= first_mask;
1779	if (BITMAP_ELEMENT_WORDS > 2)
1780	for (ix = first_word_to_mod + 1; ix < last_word_to_mod; ix++)
1781	elt->bits[ix] = ~(BITMAP_WORD) 0;
1782	elt->bits[last_word_to_mod] |= last_mask;
1783	}
1784
1785	elt_prev = elt;
1786	elt = elt->next;
1787	}
1788
1789	head->current = elt ? elt : elt_prev;
1790	head->indx = head->current->indx;
1791	}
1792
1793	/* Clear COUNT bits from START in HEAD. */
1794	void
1795	bitmap_clear_range (bitmap head, unsigned int start, unsigned int count)
1796	{
1797	unsigned int first_index, end_bit_plus1, last_index;
1798	bitmap_element *elt;
1799
1800	gcc_checking_assert (!head->tree_form);
1801
1802	if (!count)
1803	return;
1804
1805	if (count == 1)
1806	{
1807	bitmap_clear_bit (head, bit: start);
1808	return;
1809	}
1810
1811	first_index = start / BITMAP_ELEMENT_ALL_BITS;
1812	end_bit_plus1 = start + count;
1813	last_index = (end_bit_plus1 - 1) / BITMAP_ELEMENT_ALL_BITS;
1814	elt = bitmap_list_find_element (head, indx: first_index);
1815
1816	/* If bitmap_list_find_element returns zero, the current is the closest block
1817	to the result. If the current is less than first index, find the
1818	next one. Otherwise, just set elt to be current. */
1819	if (!elt)
1820	{
1821	if (head->current)
1822	{
1823	if (head->indx < first_index)
1824	{
1825	elt = head->current->next;
1826	if (!elt)
1827	return;
1828	}
1829	else
1830	elt = head->current;
1831	}
1832	else
1833	return;
1834	}
1835
1836	while (elt && (elt->indx <= last_index))
1837	{
1838	bitmap_element * next_elt = elt->next;
1839	unsigned elt_start_bit = (elt->indx) * BITMAP_ELEMENT_ALL_BITS;
1840	unsigned elt_end_bit_plus1 = elt_start_bit + BITMAP_ELEMENT_ALL_BITS;
1841
1842
1843	if (elt_start_bit >= start && elt_end_bit_plus1 <= end_bit_plus1)
1844	/* Get rid of the entire elt and go to the next one. */
1845	bitmap_list_unlink_element (head, element: elt);
1846	else
1847	{
1848	/* Going to have to knock out some bits in this elt. */
1849	unsigned int first_word_to_mod;
1850	BITMAP_WORD first_mask;
1851	unsigned int last_word_to_mod;
1852	BITMAP_WORD last_mask;
1853	unsigned int i;
1854	bool clear = true;
1855
1856	if (elt_start_bit <= start)
1857	{
1858	/* The first bit to turn off is somewhere inside this
1859	elt. */
1860	first_word_to_mod = (start - elt_start_bit) / BITMAP_WORD_BITS;
1861
1862	/* This mask should have 1s in all bits >= start position. */
1863	first_mask =
1864	(((BITMAP_WORD) 1) << ((start % BITMAP_WORD_BITS))) - 1;
1865	first_mask = ~first_mask;
1866	}
1867	else
1868	{
1869	/* The first bit to turn off is below this start of this elt. */
1870	first_word_to_mod = 0;
1871	first_mask = 0;
1872	first_mask = ~first_mask;
1873	}
1874
1875	if (elt_end_bit_plus1 <= end_bit_plus1)
1876	{
1877	/* The last bit to turn off is beyond this elt. */
1878	last_word_to_mod = BITMAP_ELEMENT_WORDS - 1;
1879	last_mask = 0;
1880	last_mask = ~last_mask;
1881	}
1882	else
1883	{
1884	/* The last bit to turn off is inside to this elt. */
1885	last_word_to_mod =
1886	(end_bit_plus1 - elt_start_bit) / BITMAP_WORD_BITS;
1887
1888	/* The last mask should have 1s below the end bit. */
1889	last_mask =
1890	(((BITMAP_WORD) 1) << (((end_bit_plus1) % BITMAP_WORD_BITS))) - 1;
1891	}
1892
1893
1894	if (first_word_to_mod == last_word_to_mod)
1895	{
1896	BITMAP_WORD mask = first_mask & last_mask;
1897	elt->bits[first_word_to_mod] &= ~mask;
1898	}
1899	else
1900	{
1901	elt->bits[first_word_to_mod] &= ~first_mask;
1902	if (BITMAP_ELEMENT_WORDS > 2)
1903	for (i = first_word_to_mod + 1; i < last_word_to_mod; i++)
1904	elt->bits[i] = 0;
1905	elt->bits[last_word_to_mod] &= ~last_mask;
1906	}
1907	for (i = 0; i < BITMAP_ELEMENT_WORDS; i++)
1908	if (elt->bits[i])
1909	{
1910	clear = false;
1911	break;
1912	}
1913	/* Check to see if there are any bits left. */
1914	if (clear)
1915	bitmap_list_unlink_element (head, element: elt);
1916	}
1917	elt = next_elt;
1918	}
1919
1920	if (elt)
1921	{
1922	head->current = elt;
1923	head->indx = head->current->indx;
1924	}
1925	}
1926
1927	/* A = ~A & B. */
1928
1929	void
1930	bitmap_compl_and_into (bitmap a, const_bitmap b)
1931	{
1932	bitmap_element *a_elt = a->first;
1933	const bitmap_element *b_elt = b->first;
1934	bitmap_element *a_prev = NULL;
1935	bitmap_element *next;
1936
1937	gcc_checking_assert (!a->tree_form && !b->tree_form);
1938	gcc_assert (a != b);
1939
1940	if (bitmap_empty_p (map: a))
1941	{
1942	bitmap_copy (to: a, from: b);
1943	return;
1944	}
1945	if (bitmap_empty_p (map: b))
1946	{
1947	bitmap_clear (head: a);
1948	return;
1949	}
1950
1951	while (a_elt || b_elt)
1952	{
1953	if (!b_elt || (a_elt && a_elt->indx < b_elt->indx))
1954	{
1955	/* A is before B. Remove A */
1956	next = a_elt->next;
1957	a_prev = a_elt->prev;
1958	bitmap_list_unlink_element (head: a, element: a_elt);
1959	a_elt = next;
1960	}
1961	else if (!a_elt || b_elt->indx < a_elt->indx)
1962	{
1963	/* B is before A. Copy B. */
1964	next = bitmap_list_insert_element_after (head: a, elt: a_prev, indx: b_elt->indx);
1965	memcpy (dest: next->bits, src: b_elt->bits, n: sizeof (next->bits));
1966	a_prev = next;
1967	b_elt = b_elt->next;
1968	}
1969	else
1970	{
1971	/* Matching elts, generate A = ~A & B. */
1972	unsigned ix;
1973	BITMAP_WORD ior = 0;
1974
1975	for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
1976	{
1977	BITMAP_WORD cleared = a_elt->bits[ix] & b_elt->bits[ix];
1978	BITMAP_WORD r = b_elt->bits[ix] ^ cleared;
1979
1980	a_elt->bits[ix] = r;
1981	ior |= r;
1982	}
1983	next = a_elt->next;
1984	if (!ior)
1985	bitmap_list_unlink_element (head: a, element: a_elt);
1986	else
1987	a_prev = a_elt;
1988	a_elt = next;
1989	b_elt = b_elt->next;
1990	}
1991	}
1992	gcc_checking_assert (!a->current == !a->first
1993	&& (!a->current || a->indx == a->current->indx));
1994	return;
1995	}
1996
1997
1998	/* Insert an element corresponding to A_ELT | B_ELT after DST_PREV,
1999	overwriting DST_ELT if non-NULL. CHANGED is true if the destination bitmap
2000	had already been changed; the new value of CHANGED is returned. */
2001
2002	static inline bool
2003	bitmap_elt_ior (bitmap dst, bitmap_element *dst_elt, bitmap_element *dst_prev,
2004	const bitmap_element *a_elt, const bitmap_element *b_elt,
2005	bool changed)
2006	{
2007	gcc_assert (a_elt || b_elt);
2008
2009	if (a_elt && b_elt && a_elt->indx == b_elt->indx)
2010	{
2011	/* Matching elts, generate A | B. */
2012	unsigned ix;
2013
2014	if (!changed && dst_elt && dst_elt->indx == a_elt->indx)
2015	{
2016	for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
2017	{
2018	BITMAP_WORD r = a_elt->bits[ix] | b_elt->bits[ix];
2019	if (r != dst_elt->bits[ix])
2020	{
2021	dst_elt->bits[ix] = r;
2022	changed = true;
2023	}
2024	}
2025	}
2026	else
2027	{
2028	changed = true;
2029	if (!dst_elt)
2030	dst_elt = bitmap_list_insert_element_after (head: dst, elt: dst_prev,
2031	indx: a_elt->indx);
2032	else
2033	dst_elt->indx = a_elt->indx;
2034	for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
2035	{
2036	BITMAP_WORD r = a_elt->bits[ix] | b_elt->bits[ix];
2037	dst_elt->bits[ix] = r;
2038	}
2039	}
2040	}
2041	else
2042	{
2043	/* Copy a single element. */
2044	const bitmap_element *src;
2045
2046	if (!b_elt || (a_elt && a_elt->indx < b_elt->indx))
2047	src = a_elt;
2048	else
2049	src = b_elt;
2050
2051	gcc_checking_assert (src);
2052	changed = bitmap_elt_copy (dst, dst_elt, dst_prev, src_elt: src, changed);
2053	}
2054	return changed;
2055	}
2056
2057
2058	/* DST = A | B. Return true if DST changes. */
2059
2060	bool
2061	bitmap_ior (bitmap dst, const_bitmap a, const_bitmap b)
2062	{
2063	bitmap_element *dst_elt = dst->first;
2064	const bitmap_element *a_elt = a->first;
2065	const bitmap_element *b_elt = b->first;
2066	bitmap_element *dst_prev = NULL;
2067	bitmap_element **dst_prev_pnext = &dst->first;
2068	bool changed = false;
2069
2070	gcc_checking_assert (!dst->tree_form && !a->tree_form && !b->tree_form);
2071	gcc_assert (dst != a && dst != b);
2072
2073	while (a_elt || b_elt)
2074	{
2075	changed = bitmap_elt_ior (dst, dst_elt, dst_prev, a_elt, b_elt, changed);
2076
2077	if (a_elt && b_elt && a_elt->indx == b_elt->indx)
2078	{
2079	a_elt = a_elt->next;
2080	b_elt = b_elt->next;
2081	}
2082	else
2083	{
2084	if (a_elt && (!b_elt || a_elt->indx <= b_elt->indx))
2085	a_elt = a_elt->next;
2086	else if (b_elt && (!a_elt || b_elt->indx <= a_elt->indx))
2087	b_elt = b_elt->next;
2088	}
2089
2090	dst_prev = *dst_prev_pnext;
2091	dst_prev_pnext = &dst_prev->next;
2092	dst_elt = *dst_prev_pnext;
2093	}
2094
2095	if (dst_elt)
2096	{
2097	changed = true;
2098	/* Ensure that dst->current is valid. */
2099	dst->current = dst->first;
2100	bitmap_elt_clear_from (head: dst, elt: dst_elt);
2101	}
2102	gcc_checking_assert (!dst->current == !dst->first);
2103	if (dst->current)
2104	dst->indx = dst->current->indx;
2105	return changed;
2106	}
2107
2108	/* A |= B. Return true if A changes. */
2109
2110	bool
2111	bitmap_ior_into (bitmap a, const_bitmap b)
2112	{
2113	bitmap_element *a_elt = a->first;
2114	const bitmap_element *b_elt = b->first;
2115	bitmap_element *a_prev = NULL;
2116	bitmap_element **a_prev_pnext = &a->first;
2117	bool changed = false;
2118
2119	gcc_checking_assert (!a->tree_form && !b->tree_form);
2120	if (a == b)
2121	return false;
2122
2123	while (b_elt)
2124	{
2125	/* If A lags behind B, just advance it. */
2126	if (!a_elt || a_elt->indx == b_elt->indx)
2127	{
2128	changed = bitmap_elt_ior (dst: a, dst_elt: a_elt, dst_prev: a_prev, a_elt, b_elt, changed);
2129	b_elt = b_elt->next;
2130	}
2131	else if (a_elt->indx > b_elt->indx)
2132	{
2133	changed = bitmap_elt_copy (dst: a, NULL, dst_prev: a_prev, src_elt: b_elt, changed);
2134	b_elt = b_elt->next;
2135	}
2136
2137	a_prev = *a_prev_pnext;
2138	a_prev_pnext = &a_prev->next;
2139	a_elt = *a_prev_pnext;
2140	}
2141
2142	gcc_checking_assert (!a->current == !a->first);
2143	if (a->current)
2144	a->indx = a->current->indx;
2145	return changed;
2146	}
2147
2148	/* A |= B. Return true if A changes. Free B (re-using its storage
2149	for the result). */
2150
2151	bool
2152	bitmap_ior_into_and_free (bitmap a, bitmap *b_)
2153	{
2154	bitmap b = *b_;
2155	bitmap_element *a_elt = a->first;
2156	bitmap_element *b_elt = b->first;
2157	bitmap_element *a_prev = NULL;
2158	bitmap_element **a_prev_pnext = &a->first;
2159	bool changed = false;
2160
2161	gcc_checking_assert (!a->tree_form && !b->tree_form);
2162	gcc_assert (a->obstack == b->obstack);
2163	if (a == b)
2164	return false;
2165
2166	while (b_elt)
2167	{
2168	/* If A lags behind B, just advance it. */
2169	if (!a_elt || a_elt->indx == b_elt->indx)
2170	{
2171	changed = bitmap_elt_ior (dst: a, dst_elt: a_elt, dst_prev: a_prev, a_elt, b_elt, changed);
2172	b_elt = b_elt->next;
2173	}
2174	else if (a_elt->indx > b_elt->indx)
2175	{
2176	bitmap_element *b_elt_next = b_elt->next;
2177	bitmap_list_unlink_element (head: b, element: b_elt, to_freelist: false);
2178	bitmap_list_insert_element_after (head: a, elt: a_prev, indx: b_elt->indx, node: b_elt);
2179	b_elt = b_elt_next;
2180	}
2181
2182	a_prev = *a_prev_pnext;
2183	a_prev_pnext = &a_prev->next;
2184	a_elt = *a_prev_pnext;
2185	}
2186
2187	gcc_checking_assert (!a->current == !a->first);
2188	if (a->current)
2189	a->indx = a->current->indx;
2190
2191	if (b->obstack)
2192	BITMAP_FREE (*b_);
2193	else
2194	bitmap_clear (head: b);
2195	return changed;
2196	}
2197
2198	/* DST = A ^ B */
2199
2200	void
2201	bitmap_xor (bitmap dst, const_bitmap a, const_bitmap b)
2202	{
2203	bitmap_element *dst_elt = dst->first;
2204	const bitmap_element *a_elt = a->first;
2205	const bitmap_element *b_elt = b->first;
2206	bitmap_element *dst_prev = NULL;
2207
2208	gcc_checking_assert (!dst->tree_form && !a->tree_form && !b->tree_form);
2209	gcc_assert (dst != a && dst != b);
2210
2211	if (a == b)
2212	{
2213	bitmap_clear (head: dst);
2214	return;
2215	}
2216
2217	while (a_elt || b_elt)
2218	{
2219	if (a_elt && b_elt && a_elt->indx == b_elt->indx)
2220	{
2221	/* Matching elts, generate A ^ B. */
2222	unsigned ix;
2223	BITMAP_WORD ior = 0;
2224
2225	if (!dst_elt)
2226	dst_elt = bitmap_list_insert_element_after (head: dst, elt: dst_prev,
2227	indx: a_elt->indx);
2228	else
2229	dst_elt->indx = a_elt->indx;
2230	for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
2231	{
2232	BITMAP_WORD r = a_elt->bits[ix] ^ b_elt->bits[ix];
2233
2234	ior |= r;
2235	dst_elt->bits[ix] = r;
2236	}
2237	a_elt = a_elt->next;
2238	b_elt = b_elt->next;
2239	if (ior)
2240	{
2241	dst_prev = dst_elt;
2242	dst_elt = dst_elt->next;
2243	}
2244	}
2245	else
2246	{
2247	/* Copy a single element. */
2248	const bitmap_element *src;
2249
2250	if (!b_elt || (a_elt && a_elt->indx < b_elt->indx))
2251	{
2252	src = a_elt;
2253	a_elt = a_elt->next;
2254	}
2255	else
2256	{
2257	src = b_elt;
2258	b_elt = b_elt->next;
2259	}
2260
2261	if (!dst_elt)
2262	dst_elt = bitmap_list_insert_element_after (head: dst, elt: dst_prev,
2263	indx: src->indx);
2264	else
2265	dst_elt->indx = src->indx;
2266	memcpy (dest: dst_elt->bits, src: src->bits, n: sizeof (dst_elt->bits));
2267	dst_prev = dst_elt;
2268	dst_elt = dst_elt->next;
2269	}
2270	}
2271	/* Ensure that dst->current is valid. */
2272	dst->current = dst->first;
2273	bitmap_elt_clear_from (head: dst, elt: dst_elt);
2274	gcc_checking_assert (!dst->current == !dst->first);
2275	if (dst->current)
2276	dst->indx = dst->current->indx;
2277	}
2278
2279	/* A ^= B */
2280
2281	void
2282	bitmap_xor_into (bitmap a, const_bitmap b)
2283	{
2284	bitmap_element *a_elt = a->first;
2285	const bitmap_element *b_elt = b->first;
2286	bitmap_element *a_prev = NULL;
2287
2288	gcc_checking_assert (!a->tree_form && !b->tree_form);
2289
2290	if (a == b)
2291	{
2292	bitmap_clear (head: a);
2293	return;
2294	}
2295
2296	while (b_elt)
2297	{
2298	if (!a_elt || b_elt->indx < a_elt->indx)
2299	{
2300	/* Copy b_elt. */
2301	bitmap_element *dst = bitmap_list_insert_element_after (head: a, elt: a_prev,
2302	indx: b_elt->indx);
2303	memcpy (dest: dst->bits, src: b_elt->bits, n: sizeof (dst->bits));
2304	a_prev = dst;
2305	b_elt = b_elt->next;
2306	}
2307	else if (a_elt->indx < b_elt->indx)
2308	{
2309	a_prev = a_elt;
2310	a_elt = a_elt->next;
2311	}
2312	else
2313	{
2314	/* Matching elts, generate A ^= B. */
2315	unsigned ix;
2316	BITMAP_WORD ior = 0;
2317	bitmap_element *next = a_elt->next;
2318
2319	for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
2320	{
2321	BITMAP_WORD r = a_elt->bits[ix] ^ b_elt->bits[ix];
2322
2323	ior |= r;
2324	a_elt->bits[ix] = r;
2325	}
2326	b_elt = b_elt->next;
2327	if (ior)
2328	a_prev = a_elt;
2329	else
2330	bitmap_list_unlink_element (head: a, element: a_elt);
2331	a_elt = next;
2332	}
2333	}
2334	gcc_checking_assert (!a->current == !a->first);
2335	if (a->current)
2336	a->indx = a->current->indx;
2337	}
2338
2339	/* Return true if two bitmaps are identical.
2340	We do not bother with a check for pointer equality, as that never
2341	occurs in practice. */
2342
2343	bool
2344	bitmap_equal_p (const_bitmap a, const_bitmap b)
2345	{
2346	const bitmap_element *a_elt;
2347	const bitmap_element *b_elt;
2348	unsigned ix;
2349
2350	gcc_checking_assert (!a->tree_form && !b->tree_form);
2351
2352	for (a_elt = a->first, b_elt = b->first;
2353	a_elt && b_elt;
2354	a_elt = a_elt->next, b_elt = b_elt->next)
2355	{
2356	if (a_elt->indx != b_elt->indx)
2357	return false;
2358	for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
2359	if (a_elt->bits[ix] != b_elt->bits[ix])
2360	return false;
2361	}
2362	return !a_elt && !b_elt;
2363	}
2364
2365	/* Return true if A AND B is not empty. */
2366
2367	bool
2368	bitmap_intersect_p (const_bitmap a, const_bitmap b)
2369	{
2370	const bitmap_element *a_elt;
2371	const bitmap_element *b_elt;
2372	unsigned ix;
2373
2374	gcc_checking_assert (!a->tree_form && !b->tree_form);
2375
2376	for (a_elt = a->first, b_elt = b->first;
2377	a_elt && b_elt;)
2378	{
2379	if (a_elt->indx < b_elt->indx)
2380	a_elt = a_elt->next;
2381	else if (b_elt->indx < a_elt->indx)
2382	b_elt = b_elt->next;
2383	else
2384	{
2385	for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
2386	if (a_elt->bits[ix] & b_elt->bits[ix])
2387	return true;
2388	a_elt = a_elt->next;
2389	b_elt = b_elt->next;
2390	}
2391	}
2392	return false;
2393	}
2394
2395	/* Return true if A AND NOT B is not empty. */
2396
2397	bool
2398	bitmap_intersect_compl_p (const_bitmap a, const_bitmap b)
2399	{
2400	const bitmap_element *a_elt;
2401	const bitmap_element *b_elt;
2402	unsigned ix;
2403
2404	gcc_checking_assert (!a->tree_form && !b->tree_form);
2405
2406	for (a_elt = a->first, b_elt = b->first;
2407	a_elt && b_elt;)
2408	{
2409	if (a_elt->indx < b_elt->indx)
2410	return true;
2411	else if (b_elt->indx < a_elt->indx)
2412	b_elt = b_elt->next;
2413	else
2414	{
2415	for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
2416	if (a_elt->bits[ix] & ~b_elt->bits[ix])
2417	return true;
2418	a_elt = a_elt->next;
2419	b_elt = b_elt->next;
2420	}
2421	}
2422	return a_elt != NULL;
2423	}
2424
2425
2426	/* DST = A | (FROM1 & ~FROM2). Return true if DST changes. */
2427
2428	bool
2429	bitmap_ior_and_compl (bitmap dst, const_bitmap a, const_bitmap b, const_bitmap kill)
2430	{
2431	bool changed = false;
2432
2433	bitmap_element *dst_elt = dst->first;
2434	const bitmap_element *a_elt = a->first;
2435	const bitmap_element *b_elt = b->first;
2436	const bitmap_element *kill_elt = kill->first;
2437	bitmap_element *dst_prev = NULL;
2438	bitmap_element **dst_prev_pnext = &dst->first;
2439
2440	gcc_checking_assert (!dst->tree_form && !a->tree_form && !b->tree_form
2441	&& !kill->tree_form);
2442	gcc_assert (dst != a && dst != b && dst != kill);
2443
2444	/* Special cases. We don't bother checking for bitmap_equal_p (b, kill). */
2445	if (b == kill || bitmap_empty_p (map: b))
2446	{
2447	changed = !bitmap_equal_p (a: dst, b: a);
2448	if (changed)
2449	bitmap_copy (to: dst, from: a);
2450	return changed;
2451	}
2452	if (bitmap_empty_p (map: kill))
2453	return bitmap_ior (dst, a, b);
2454	if (bitmap_empty_p (map: a))
2455	return bitmap_and_compl (dst, a: b, b: kill);
2456
2457	while (a_elt || b_elt)
2458	{
2459	bool new_element = false;
2460
2461	if (b_elt)
2462	while (kill_elt && kill_elt->indx < b_elt->indx)
2463	kill_elt = kill_elt->next;
2464
2465	if (b_elt && kill_elt && kill_elt->indx == b_elt->indx
2466	&& (!a_elt || a_elt->indx >= b_elt->indx))
2467	{
2468	bitmap_element tmp_elt;
2469	unsigned ix;
2470
2471	BITMAP_WORD ior = 0;
2472	tmp_elt.indx = b_elt->indx;
2473	for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
2474	{
2475	BITMAP_WORD r = b_elt->bits[ix] & ~kill_elt->bits[ix];
2476	ior |= r;
2477	tmp_elt.bits[ix] = r;
2478	}
2479
2480	if (ior)
2481	{
2482	changed = bitmap_elt_ior (dst, dst_elt, dst_prev,
2483	a_elt, b_elt: &tmp_elt, changed);
2484	new_element = true;
2485	if (a_elt && a_elt->indx == b_elt->indx)
2486	a_elt = a_elt->next;
2487	}
2488
2489	b_elt = b_elt->next;
2490	kill_elt = kill_elt->next;
2491	}
2492	else
2493	{
2494	changed = bitmap_elt_ior (dst, dst_elt, dst_prev,
2495	a_elt, b_elt, changed);
2496	new_element = true;
2497
2498	if (a_elt && b_elt && a_elt->indx == b_elt->indx)
2499	{
2500	a_elt = a_elt->next;
2501	b_elt = b_elt->next;
2502	}
2503	else
2504	{
2505	if (a_elt && (!b_elt || a_elt->indx <= b_elt->indx))
2506	a_elt = a_elt->next;
2507	else if (b_elt && (!a_elt || b_elt->indx <= a_elt->indx))
2508	b_elt = b_elt->next;
2509	}
2510	}
2511
2512	if (new_element)
2513	{
2514	dst_prev = *dst_prev_pnext;
2515	dst_prev_pnext = &dst_prev->next;
2516	dst_elt = *dst_prev_pnext;
2517	}
2518	}
2519
2520	if (dst_elt)
2521	{
2522	changed = true;
2523	/* Ensure that dst->current is valid. */
2524	dst->current = dst->first;
2525	bitmap_elt_clear_from (head: dst, elt: dst_elt);
2526	}
2527	gcc_checking_assert (!dst->current == !dst->first);
2528	if (dst->current)
2529	dst->indx = dst->current->indx;
2530
2531	return changed;
2532	}
2533
2534	/* A |= (B & ~C). Return true if A changes. */
2535
2536	bool
2537	bitmap_ior_and_compl_into (bitmap a, const_bitmap b, const_bitmap c)
2538	{
2539	bitmap_element *a_elt = a->first;
2540	const bitmap_element *b_elt = b->first;
2541	const bitmap_element *c_elt = c->first;
2542	bitmap_element and_elt;
2543	bitmap_element *a_prev = NULL;
2544	bitmap_element **a_prev_pnext = &a->first;
2545	bool changed = false;
2546	unsigned ix;
2547
2548	gcc_checking_assert (!a->tree_form && !b->tree_form && !c->tree_form);
2549
2550	if (a == b)
2551	return false;
2552	if (bitmap_empty_p (map: c))
2553	return bitmap_ior_into (a, b);
2554	else if (bitmap_empty_p (map: a))
2555	return bitmap_and_compl (dst: a, a: b, b: c);
2556
2557	and_elt.indx = -1;
2558	while (b_elt)
2559	{
2560	/* Advance C. */
2561	while (c_elt && c_elt->indx < b_elt->indx)
2562	c_elt = c_elt->next;
2563
2564	const bitmap_element *and_elt_ptr;
2565	if (c_elt && c_elt->indx == b_elt->indx)
2566	{
2567	BITMAP_WORD overall = 0;
2568	and_elt_ptr = &and_elt;
2569	and_elt.indx = b_elt->indx;
2570	for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
2571	{
2572	and_elt.bits[ix] = b_elt->bits[ix] & ~c_elt->bits[ix];
2573	overall |= and_elt.bits[ix];
2574	}
2575	if (!overall)
2576	{
2577	b_elt = b_elt->next;
2578	continue;
2579	}
2580	}
2581	else
2582	and_elt_ptr = b_elt;
2583
2584	b_elt = b_elt->next;
2585
2586	/* Now find a place to insert AND_ELT. */
2587	do
2588	{
2589	ix = a_elt ? a_elt->indx : and_elt_ptr->indx;
2590	if (ix == and_elt_ptr->indx)
2591	changed = bitmap_elt_ior (dst: a, dst_elt: a_elt, dst_prev: a_prev, a_elt,
2592	b_elt: and_elt_ptr, changed);
2593	else if (ix > and_elt_ptr->indx)
2594	changed = bitmap_elt_copy (dst: a, NULL, dst_prev: a_prev, src_elt: and_elt_ptr, changed);
2595
2596	a_prev = *a_prev_pnext;
2597	a_prev_pnext = &a_prev->next;
2598	a_elt = *a_prev_pnext;
2599
2600	/* If A lagged behind B/C, we advanced it so loop once more. */
2601	}
2602	while (ix < and_elt_ptr->indx);
2603	}
2604
2605	gcc_checking_assert (!a->current == !a->first);
2606	if (a->current)
2607	a->indx = a->current->indx;
2608	return changed;
2609	}
2610
2611	/* A |= (B & C). Return true if A changes. */
2612
2613	bool
2614	bitmap_ior_and_into (bitmap a, const_bitmap b, const_bitmap c)
2615	{
2616	bitmap_element *a_elt = a->first;
2617	const bitmap_element *b_elt = b->first;
2618	const bitmap_element *c_elt = c->first;
2619	bitmap_element and_elt;
2620	bitmap_element *a_prev = NULL;
2621	bitmap_element **a_prev_pnext = &a->first;
2622	bool changed = false;
2623	unsigned ix;
2624
2625	gcc_checking_assert (!a->tree_form && !b->tree_form && !c->tree_form);
2626
2627	if (b == c)
2628	return bitmap_ior_into (a, b);
2629	if (bitmap_empty_p (map: b) || bitmap_empty_p (map: c))
2630	return false;
2631
2632	and_elt.indx = -1;
2633	while (b_elt && c_elt)
2634	{
2635	BITMAP_WORD overall;
2636
2637	/* Find a common item of B and C. */
2638	while (b_elt->indx != c_elt->indx)
2639	{
2640	if (b_elt->indx < c_elt->indx)
2641	{
2642	b_elt = b_elt->next;
2643	if (!b_elt)
2644	goto done;
2645	}
2646	else
2647	{
2648	c_elt = c_elt->next;
2649	if (!c_elt)
2650	goto done;
2651	}
2652	}
2653
2654	overall = 0;
2655	and_elt.indx = b_elt->indx;
2656	for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
2657	{
2658	and_elt.bits[ix] = b_elt->bits[ix] & c_elt->bits[ix];
2659	overall |= and_elt.bits[ix];
2660	}
2661
2662	b_elt = b_elt->next;
2663	c_elt = c_elt->next;
2664	if (!overall)
2665	continue;
2666
2667	/* Now find a place to insert AND_ELT. */
2668	do
2669	{
2670	ix = a_elt ? a_elt->indx : and_elt.indx;
2671	if (ix == and_elt.indx)
2672	changed = bitmap_elt_ior (dst: a, dst_elt: a_elt, dst_prev: a_prev, a_elt, b_elt: &and_elt, changed);
2673	else if (ix > and_elt.indx)
2674	changed = bitmap_elt_copy (dst: a, NULL, dst_prev: a_prev, src_elt: &and_elt, changed);
2675
2676	a_prev = *a_prev_pnext;
2677	a_prev_pnext = &a_prev->next;
2678	a_elt = *a_prev_pnext;
2679
2680	/* If A lagged behind B/C, we advanced it so loop once more. */
2681	}
2682	while (ix < and_elt.indx);
2683	}
2684
2685	done:
2686	gcc_checking_assert (!a->current == !a->first);
2687	if (a->current)
2688	a->indx = a->current->indx;
2689	return changed;
2690	}
2691
2692	/* Compute hash of bitmap (for purposes of hashing). */
2693
2694	hashval_t
2695	bitmap_hash (const_bitmap head)
2696	{
2697	const bitmap_element *ptr;
2698	BITMAP_WORD hash = 0;
2699	int ix;
2700
2701	gcc_checking_assert (!head->tree_form);
2702
2703	for (ptr = head->first; ptr; ptr = ptr->next)
2704	{
2705	hash ^= ptr->indx;
2706	for (ix = 0; ix != BITMAP_ELEMENT_WORDS; ix++)
2707	hash ^= ptr->bits[ix];
2708	}
2709	return (hashval_t)hash;
2710	}
2711
2712
2713	/* Function to obtain a vector of bitmap elements in bit order from
2714	HEAD in tree view. */
2715
2716	static void
2717	bitmap_tree_to_vec (vec<bitmap_element *> &elts, const_bitmap head)
2718	{
2719	gcc_checking_assert (head->tree_form);
2720	auto_vec<bitmap_element *, 32> stack;
2721	bitmap_element *e = head->first;
2722	while (true)
2723	{
2724	while (e != NULL)
2725	{
2726	stack.safe_push (obj: e);
2727	e = e->prev;
2728	}
2729	if (stack.is_empty ())
2730	break;
2731
2732	e = stack.pop ();
2733	elts.safe_push (obj: e);
2734	e = e->next;
2735	}
2736	}
2737
2738	/* Debugging function to print out the contents of a bitmap element. */
2739
2740	DEBUG_FUNCTION void
2741	debug_bitmap_elt_file (FILE *file, const bitmap_element *ptr)
2742	{
2743	unsigned int i, j, col = 26;
2744
2745	fprintf (stream: file, format: "\t" HOST_PTR_PRINTF " next = " HOST_PTR_PRINTF
2746	" prev = " HOST_PTR_PRINTF " indx = %u\n\t\tbits = {",
2747	(const void*) ptr, (const void*) ptr->next,
2748	(const void*) ptr->prev, ptr->indx);
2749
2750	for (i = 0; i < BITMAP_ELEMENT_WORDS; i++)
2751	for (j = 0; j < BITMAP_WORD_BITS; j++)
2752	if ((ptr->bits[i] >> j) & 1)
2753	{
2754	if (col > 70)
2755	{
2756	fprintf (stream: file, format: "\n\t\t\t");
2757	col = 24;
2758	}
2759
2760	fprintf (stream: file, format: " %u", (ptr->indx * BITMAP_ELEMENT_ALL_BITS
2761	+ i * BITMAP_WORD_BITS + j));
2762	col += 4;
2763	}
2764
2765	fprintf (stream: file, format: " }\n");
2766	}
2767
2768	/* Debugging function to print out the contents of a bitmap. */
2769
2770	DEBUG_FUNCTION void
2771	debug_bitmap_file (FILE *file, const_bitmap head)
2772	{
2773	const bitmap_element *ptr;
2774
2775	fprintf (stream: file, format: "\nfirst = " HOST_PTR_PRINTF
2776	" current = " HOST_PTR_PRINTF " indx = %u\n",
2777	(void *) head->first, (void *) head->current, head->indx);
2778
2779	if (head->tree_form)
2780	{
2781	auto_vec<bitmap_element *, 32> elts;
2782	bitmap_tree_to_vec (elts, head);
2783	for (unsigned i = 0; i < elts.length (); ++i)
2784	debug_bitmap_elt_file (file, ptr: elts[i]);
2785	}
2786	else
2787	for (ptr = head->first; ptr; ptr = ptr->next)
2788	debug_bitmap_elt_file (file, ptr);
2789	}
2790
2791	/* Function to be called from the debugger to print the contents
2792	of a bitmap. */
2793
2794	DEBUG_FUNCTION void
2795	debug_bitmap (const_bitmap head)
2796	{
2797	debug_bitmap_file (stderr, head);
2798	}
2799
2800	/* Function to print out the contents of a bitmap. Unlike debug_bitmap_file,
2801	it does not print anything but the bits. */
2802
2803	DEBUG_FUNCTION void
2804	bitmap_print (FILE *file, const_bitmap head, const char *prefix,
2805	const char *suffix)
2806	{
2807	const char *comma = "";
2808	unsigned i;
2809
2810	fputs (s: prefix, stream: file);
2811	if (head->tree_form)
2812	{
2813	auto_vec<bitmap_element *, 32> elts;
2814	bitmap_tree_to_vec (elts, head);
2815	for (i = 0; i < elts.length (); ++i)
2816	for (unsigned ix = 0; ix != BITMAP_ELEMENT_WORDS; ++ix)
2817	{
2818	BITMAP_WORD word = elts[i]->bits[ix];
2819	for (unsigned bit = 0; bit != BITMAP_WORD_BITS; ++bit)
2820	if (word & ((BITMAP_WORD)1 << bit))
2821	{
2822	fprintf (stream: file, format: "%s%d", comma,
2823	(bit + BITMAP_WORD_BITS * ix
2824	+ elts[i]->indx * BITMAP_ELEMENT_ALL_BITS));
2825	comma = ", ";
2826	}
2827	}
2828	}
2829	else
2830	{
2831	bitmap_iterator bi;
2832	EXECUTE_IF_SET_IN_BITMAP (head, 0, i, bi)
2833	{
2834	fprintf (stream: file, format: "%s%d", comma, i);
2835	comma = ", ";
2836	}
2837	}
2838	fputs (s: suffix, stream: file);
2839	}
2840
2841	/* Output per-bitmap memory usage statistics. */
2842	void
2843	dump_bitmap_statistics (void)
2844	{
2845	if (!GATHER_STATISTICS)
2846	return;
2847
2848	bitmap_mem_desc.dump (origin: BITMAP_ORIGIN);
2849	}
2850
2851	DEBUG_FUNCTION void
2852	debug (const bitmap_head &ref)
2853	{
2854	dump_bitmap (stderr, map: &ref);
2855	}
2856
2857	DEBUG_FUNCTION void
2858	debug (const bitmap_head *ptr)
2859	{
2860	if (ptr)
2861	debug (ref: *ptr);
2862	else
2863	fprintf (stderr, format: "<nil>\n");
2864	}
2865
2866	DEBUG_FUNCTION void
2867	debug (const auto_bitmap &ref)
2868	{
2869	debug (ref: (const bitmap_head &) ref);
2870	}
2871
2872	DEBUG_FUNCTION void
2873	debug (const auto_bitmap *ptr)
2874	{
2875	debug (ptr: (const bitmap_head *) ptr);
2876	}
2877
2878	void
2879	bitmap_head::dump ()
2880	{
2881	debug (ptr: this);
2882	}
2883
2884	#if CHECKING_P
2885
2886	namespace selftest {
2887
2888	/* Selftests for bitmaps. */
2889
2890	/* Freshly-created bitmaps ought to be empty. */
2891
2892	static void
2893	test_gc_alloc ()
2894	{
2895	bitmap b = bitmap_gc_alloc ();
2896	ASSERT_TRUE (bitmap_empty_p (b));
2897	}
2898
2899	/* Verify bitmap_set_range. */
2900
2901	static void
2902	test_set_range ()
2903	{
2904	bitmap b = bitmap_gc_alloc ();
2905	ASSERT_TRUE (bitmap_empty_p (b));
2906
2907	bitmap_set_range (head: b, start: 7, count: 5);
2908	ASSERT_FALSE (bitmap_empty_p (b));
2909	ASSERT_EQ (5, bitmap_count_bits (b));
2910
2911	/* Verify bitmap_bit_p at the boundaries. */
2912	ASSERT_FALSE (bitmap_bit_p (b, 6));
2913	ASSERT_TRUE (bitmap_bit_p (b, 7));
2914	ASSERT_TRUE (bitmap_bit_p (b, 11));
2915	ASSERT_FALSE (bitmap_bit_p (b, 12));
2916	}
2917
2918	/* Verify splitting a range into two pieces using bitmap_clear_bit. */
2919
2920	static void
2921	test_clear_bit_in_middle ()
2922	{
2923	bitmap b = bitmap_gc_alloc ();
2924
2925	/* Set b to [100..200]. */
2926	bitmap_set_range (head: b, start: 100, count: 100);
2927	ASSERT_EQ (100, bitmap_count_bits (b));
2928
2929	/* Clear a bit in the middle. */
2930	bool changed = bitmap_clear_bit (head: b, bit: 150);
2931	ASSERT_TRUE (changed);
2932	ASSERT_EQ (99, bitmap_count_bits (b));
2933	ASSERT_TRUE (bitmap_bit_p (b, 149));
2934	ASSERT_FALSE (bitmap_bit_p (b, 150));
2935	ASSERT_TRUE (bitmap_bit_p (b, 151));
2936	}
2937
2938	/* Verify bitmap_copy. */
2939
2940	static void
2941	test_copying ()
2942	{
2943	bitmap src = bitmap_gc_alloc ();
2944	bitmap_set_range (head: src, start: 40, count: 10);
2945
2946	bitmap dst = bitmap_gc_alloc ();
2947	ASSERT_FALSE (bitmap_equal_p (src, dst));
2948	bitmap_copy (to: dst, from: src);
2949	ASSERT_TRUE (bitmap_equal_p (src, dst));
2950
2951	/* Verify that we can make them unequal again... */
2952	bitmap_set_range (head: src, start: 70, count: 5);
2953	ASSERT_FALSE (bitmap_equal_p (src, dst));
2954
2955	/* ...and that changing src after the copy didn't affect
2956	the other: */
2957	ASSERT_FALSE (bitmap_bit_p (dst, 70));
2958	}
2959
2960	/* Verify bitmap_single_bit_set_p. */
2961
2962	static void
2963	test_bitmap_single_bit_set_p ()
2964	{
2965	bitmap b = bitmap_gc_alloc ();
2966
2967	ASSERT_FALSE (bitmap_single_bit_set_p (b));
2968
2969	bitmap_set_range (head: b, start: 42, count: 1);
2970	ASSERT_TRUE (bitmap_single_bit_set_p (b));
2971	ASSERT_EQ (42, bitmap_first_set_bit (b));
2972
2973	bitmap_set_range (head: b, start: 1066, count: 1);
2974	ASSERT_FALSE (bitmap_single_bit_set_p (b));
2975	ASSERT_EQ (42, bitmap_first_set_bit (b));
2976
2977	bitmap_clear_range (head: b, start: 0, count: 100);
2978	ASSERT_TRUE (bitmap_single_bit_set_p (b));
2979	ASSERT_EQ (1066, bitmap_first_set_bit (b));
2980	}
2981
2982	/* Verify accessing aligned bit chunks works as expected. */
2983
2984	static void
2985	test_aligned_chunk (unsigned num_bits)
2986	{
2987	bitmap b = bitmap_gc_alloc ();
2988	int limit = 2 ^ num_bits;
2989
2990	int index = 3;
2991	for (int x = 0; x < limit; x++)
2992	{
2993	bitmap_set_aligned_chunk (head: b, chunk: index, chunk_size: num_bits, chunk_value: (BITMAP_WORD) x);
2994	ASSERT_TRUE ((int) bitmap_get_aligned_chunk (b, index, num_bits) == x);
2995	ASSERT_TRUE ((int) bitmap_get_aligned_chunk (b, index + 1,
2996	num_bits) == 0);
2997	ASSERT_TRUE ((int) bitmap_get_aligned_chunk (b, index - 1,
2998	num_bits) == 0);
2999	index += 3;
3000	}
3001	index = 3;
3002	for (int x = 0; x < limit ; x++)
3003	{
3004	ASSERT_TRUE ((int) bitmap_get_aligned_chunk (b, index, num_bits) == x);
3005	index += 3;
3006	}
3007	}
3008
3009	/* Run all of the selftests within this file. */
3010
3011	void
3012	bitmap_cc_tests ()
3013	{
3014	test_gc_alloc ();
3015	test_set_range ();
3016	test_clear_bit_in_middle ();
3017	test_copying ();
3018	test_bitmap_single_bit_set_p ();
3019	/* Test 2, 4 and 8 bit aligned chunks. */
3020	test_aligned_chunk (num_bits: 2);
3021	test_aligned_chunk (num_bits: 4);
3022	test_aligned_chunk (num_bits: 8);
3023	}
3024
3025	} // namespace selftest
3026	#endif /* CHECKING_P */
3027
3028	#include "gt-bitmap.h"
3029