1	/* Scanning of rtl for dataflow analysis.
2	Copyright (C) 1999-2023 Free Software Foundation, Inc.
3	Originally contributed by Michael P. Hayes
4	(m.hayes@elec.canterbury.ac.nz, mhayes@redhat.com)
5	Major rewrite contributed by Danny Berlin (dberlin@dberlin.org)
6	and Kenneth Zadeck (zadeck@naturalbridge.com).
7
8	This file is part of GCC.
9
10	GCC is free software; you can redistribute it and/or modify it under
11	the terms of the GNU General Public License as published by the Free
12	Software Foundation; either version 3, or (at your option) any later
13	version.
14
15	GCC is distributed in the hope that it will be useful, but WITHOUT ANY
16	WARRANTY; without even the implied warranty of MERCHANTABILITY or
17	FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
18	for more details.
19
20	You should have received a copy of the GNU General Public License
21	along with GCC; see the file COPYING3. If not see
22	<http://www.gnu.org/licenses/>. */
23
24	#include "config.h"
25	#include "system.h"
26	#include "coretypes.h"
27	#include "backend.h"
28	#include "target.h"
29	#include "rtl.h"
30	#include "tree.h"
31	#include "df.h"
32	#include "memmodel.h"
33	#include "tm_p.h"
34	#include "regs.h"
35	#include "emit-rtl.h" /* FIXME: Can go away once crtl is moved to rtl.h. */
36	#include "dumpfile.h"
37	#include "calls.h"
38	#include "function-abi.h"
39
40	/* The set of hard registers in eliminables[i].from. */
41
42	static HARD_REG_SET elim_reg_set;
43
44	/* Initialize ur_in and ur_out as if all hard registers were partially
45	available. */
46
47	class df_collection_rec
48	{
49	public:
50	auto_vec<df_ref, 128> def_vec;
51	auto_vec<df_ref, 32> use_vec;
52	auto_vec<df_ref, 32> eq_use_vec;
53	auto_vec<df_mw_hardreg *, 32> mw_vec;
54	};
55
56	static void df_ref_record (enum df_ref_class, class df_collection_rec *,
57	rtx, rtx *,
58	basic_block, struct df_insn_info *,
59	enum df_ref_type, int ref_flags);
60	static void df_def_record_1 (class df_collection_rec *, rtx *,
61	basic_block, struct df_insn_info *,
62	int ref_flags);
63	static void df_defs_record (class df_collection_rec *, rtx,
64	basic_block, struct df_insn_info *,
65	int ref_flags);
66	static void df_uses_record (class df_collection_rec *,
67	rtx *, enum df_ref_type,
68	basic_block, struct df_insn_info *,
69	int ref_flags);
70
71	static void df_install_ref_incremental (df_ref);
72	static void df_insn_refs_collect (class df_collection_rec*,
73	basic_block, struct df_insn_info *);
74	static void df_canonize_collection_rec (class df_collection_rec *);
75
76	static void df_get_regular_block_artificial_uses (bitmap);
77	static void df_get_eh_block_artificial_uses (bitmap);
78
79	static void df_record_entry_block_defs (bitmap);
80	static void df_record_exit_block_uses (bitmap);
81	static void df_get_exit_block_use_set (bitmap);
82	static void df_get_entry_block_def_set (bitmap);
83	static void df_grow_ref_info (struct df_ref_info *, unsigned int);
84	static void df_ref_chain_delete_du_chain (df_ref);
85	static void df_ref_chain_delete (df_ref);
86
87	static void df_refs_add_to_chains (class df_collection_rec *,
88	basic_block, rtx_insn *, unsigned int);
89
90	static bool df_insn_refs_verify (class df_collection_rec *, basic_block,
91	rtx_insn *, bool);
92	static void df_entry_block_defs_collect (class df_collection_rec *, bitmap);
93	static void df_exit_block_uses_collect (class df_collection_rec *, bitmap);
94	static void df_install_ref (df_ref, struct df_reg_info *,
95	struct df_ref_info *, bool);
96
97	static int df_ref_compare (df_ref, df_ref);
98	static int df_ref_ptr_compare (const void *, const void *);
99	static int df_mw_compare (const df_mw_hardreg *, const df_mw_hardreg *);
100	static int df_mw_ptr_compare (const void *, const void *);
101
102	static void df_insn_info_delete (unsigned int);
103
104	/* Indexed by hardware reg number, is true if that register is ever
105	used in the current function.
106
107	In df-scan.cc, this is set up to record the hard regs used
108	explicitly. Reload adds in the hard regs used for holding pseudo
109	regs. Final uses it to generate the code in the function prologue
110	and epilogue to save and restore registers as needed. */
111
112	static bool regs_ever_live[FIRST_PSEUDO_REGISTER];
113
114	/* Flags used to tell df_refs_add_to_chains() which vectors it should copy. */
115	static const unsigned int copy_defs = 0x1;
116	static const unsigned int copy_uses = 0x2;
117	static const unsigned int copy_eq_uses = 0x4;
118	static const unsigned int copy_mw = 0x8;
119	static const unsigned int copy_all = copy_defs | copy_uses | copy_eq_uses
120	| copy_mw;
121
122	/*----------------------------------------------------------------------------
123	SCANNING DATAFLOW PROBLEM
124
125	There are several ways in which scanning looks just like the other
126	dataflow problems. It shares the all the mechanisms for local info
127	as well as basic block info. Where it differs is when and how often
128	it gets run. It also has no need for the iterative solver.
129	----------------------------------------------------------------------------*/
130
131	/* Problem data for the scanning dataflow function. */
132	struct df_scan_problem_data
133	{
134	object_allocator<df_base_ref> *ref_base_pool;
135	object_allocator<df_artificial_ref> *ref_artificial_pool;
136	object_allocator<df_regular_ref> *ref_regular_pool;
137	object_allocator<df_insn_info> *insn_pool;
138	object_allocator<df_reg_info> *reg_pool;
139	object_allocator<df_mw_hardreg> *mw_reg_pool;
140
141	bitmap_obstack reg_bitmaps;
142	bitmap_obstack insn_bitmaps;
143	};
144
145	/* Internal function to shut down the scanning problem. */
146	static void
147	df_scan_free_internal (void)
148	{
149	struct df_scan_problem_data *problem_data
150	= (struct df_scan_problem_data *) df_scan->problem_data;
151
152	free (ptr: df->def_info.refs);
153	free (ptr: df->def_info.begin);
154	free (ptr: df->def_info.count);
155	memset (s: &df->def_info, c: 0, n: (sizeof (struct df_ref_info)));
156
157	free (ptr: df->use_info.refs);
158	free (ptr: df->use_info.begin);
159	free (ptr: df->use_info.count);
160	memset (s: &df->use_info, c: 0, n: (sizeof (struct df_ref_info)));
161
162	free (ptr: df->def_regs);
163	df->def_regs = NULL;
164	free (ptr: df->use_regs);
165	df->use_regs = NULL;
166	free (ptr: df->eq_use_regs);
167	df->eq_use_regs = NULL;
168	df->regs_size = 0;
169	DF_REG_SIZE (df) = 0;
170
171	free (ptr: df->insns);
172	df->insns = NULL;
173	DF_INSN_SIZE () = 0;
174
175	free (df_scan->block_info);
176	df_scan->block_info = NULL;
177	df_scan->block_info_size = 0;
178
179	bitmap_clear (&df->hardware_regs_used);
180	bitmap_clear (&df->regular_block_artificial_uses);
181	bitmap_clear (&df->eh_block_artificial_uses);
182	BITMAP_FREE (df->entry_block_defs);
183	BITMAP_FREE (df->exit_block_uses);
184	bitmap_clear (&df->insns_to_delete);
185	bitmap_clear (&df->insns_to_rescan);
186	bitmap_clear (&df->insns_to_notes_rescan);
187
188	delete problem_data->ref_base_pool;
189	delete problem_data->ref_artificial_pool;
190	delete problem_data->ref_regular_pool;
191	delete problem_data->insn_pool;
192	delete problem_data->reg_pool;
193	delete problem_data->mw_reg_pool;
194	bitmap_obstack_release (&problem_data->reg_bitmaps);
195	bitmap_obstack_release (&problem_data->insn_bitmaps);
196	free (df_scan->problem_data);
197	}
198
199
200	/* Free basic block info. */
201
202	static void
203	df_scan_free_bb_info (basic_block bb, void *vbb_info)
204	{
205	struct df_scan_bb_info *bb_info = (struct df_scan_bb_info *) vbb_info;
206	unsigned int bb_index = bb->index;
207	rtx_insn *insn;
208
209	FOR_BB_INSNS (bb, insn)
210	if (INSN_P (insn))
211	df_insn_info_delete (INSN_UID (insn));
212
213	if (bb_index < df_scan->block_info_size)
214	bb_info = df_scan_get_bb_info (index: bb_index);
215
216	/* Get rid of any artificial uses or defs. */
217	df_ref_chain_delete_du_chain (bb_info->artificial_defs);
218	df_ref_chain_delete_du_chain (bb_info->artificial_uses);
219	df_ref_chain_delete (bb_info->artificial_defs);
220	df_ref_chain_delete (bb_info->artificial_uses);
221	bb_info->artificial_defs = NULL;
222	bb_info->artificial_uses = NULL;
223	}
224
225
226	/* Allocate the problem data for the scanning problem. This should be
227	called when the problem is created or when the entire function is to
228	be rescanned. */
229	void
230	df_scan_alloc (bitmap all_blocks ATTRIBUTE_UNUSED)
231	{
232	struct df_scan_problem_data *problem_data;
233	basic_block bb;
234
235	/* Given the number of pools, this is really faster than tearing
236	everything apart. */
237	if (df_scan->problem_data)
238	df_scan_free_internal ();
239
240	problem_data = XNEW (struct df_scan_problem_data);
241	df_scan->problem_data = problem_data;
242	df_scan->computed = true;
243
244	problem_data->ref_base_pool = new object_allocator<df_base_ref>
245	("df_scan ref base");
246	problem_data->ref_artificial_pool = new object_allocator<df_artificial_ref>
247	("df_scan ref artificial");
248	problem_data->ref_regular_pool = new object_allocator<df_regular_ref>
249	("df_scan ref regular");
250	problem_data->insn_pool = new object_allocator<df_insn_info>
251	("df_scan insn");
252	problem_data->reg_pool = new object_allocator<df_reg_info>
253	("df_scan reg");
254	problem_data->mw_reg_pool = new object_allocator<df_mw_hardreg>
255	("df_scan mw_reg");
256
257	bitmap_obstack_initialize (&problem_data->reg_bitmaps);
258	bitmap_obstack_initialize (&problem_data->insn_bitmaps);
259
260	df_grow_reg_info ();
261
262	df_grow_insn_info ();
263	df_grow_bb_info (df_scan);
264
265	FOR_ALL_BB_FN (bb, cfun)
266	{
267	unsigned int bb_index = bb->index;
268	struct df_scan_bb_info *bb_info = df_scan_get_bb_info (index: bb_index);
269	bb_info->artificial_defs = NULL;
270	bb_info->artificial_uses = NULL;
271	}
272
273	bitmap_initialize (head: &df->hardware_regs_used, obstack: &problem_data->reg_bitmaps);
274	bitmap_initialize (head: &df->regular_block_artificial_uses, obstack: &problem_data->reg_bitmaps);
275	bitmap_initialize (head: &df->eh_block_artificial_uses, obstack: &problem_data->reg_bitmaps);
276	df->entry_block_defs = BITMAP_ALLOC (obstack: &problem_data->reg_bitmaps);
277	df->exit_block_uses = BITMAP_ALLOC (obstack: &problem_data->reg_bitmaps);
278	bitmap_initialize (head: &df->insns_to_delete, obstack: &problem_data->insn_bitmaps);
279	bitmap_initialize (head: &df->insns_to_rescan, obstack: &problem_data->insn_bitmaps);
280	bitmap_initialize (head: &df->insns_to_notes_rescan, obstack: &problem_data->insn_bitmaps);
281	df_scan->optional_p = false;
282	}
283
284
285	/* Free all of the data associated with the scan problem. */
286
287	static void
288	df_scan_free (void)
289	{
290	if (df_scan->problem_data)
291	df_scan_free_internal ();
292
293	if (df->blocks_to_analyze)
294	{
295	BITMAP_FREE (df->blocks_to_analyze);
296	df->blocks_to_analyze = NULL;
297	}
298
299	free (df_scan);
300	}
301
302	/* Dump the preamble for DF_SCAN dump. */
303	static void
304	df_scan_start_dump (FILE *file ATTRIBUTE_UNUSED)
305	{
306	int i;
307	int dcount = 0;
308	int ucount = 0;
309	int ecount = 0;
310	int icount = 0;
311	int ccount = 0;
312	basic_block bb;
313	rtx_insn *insn;
314
315	fprintf (stream: file, format: ";; fully invalidated by EH \t");
316	df_print_regset
317	(file, r: bitmap_view<HARD_REG_SET> (eh_edge_abi.full_reg_clobbers ()));
318	fprintf (stream: file, format: ";; hardware regs used \t");
319	df_print_regset (file, r: &df->hardware_regs_used);
320	fprintf (stream: file, format: ";; regular block artificial uses \t");
321	df_print_regset (file, r: &df->regular_block_artificial_uses);
322	fprintf (stream: file, format: ";; eh block artificial uses \t");
323	df_print_regset (file, r: &df->eh_block_artificial_uses);
324	fprintf (stream: file, format: ";; entry block defs \t");
325	df_print_regset (file, r: df->entry_block_defs);
326	fprintf (stream: file, format: ";; exit block uses \t");
327	df_print_regset (file, r: df->exit_block_uses);
328	fprintf (stream: file, format: ";; regs ever live \t");
329	for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
330	if (df_regs_ever_live_p (i))
331	fprintf (stream: file, format: " %d [%s]", i, reg_names[i]);
332	fprintf (stream: file, format: "\n;; ref usage \t");
333
334	for (i = 0; i < (int)df->regs_inited; i++)
335	if (DF_REG_DEF_COUNT (i) || DF_REG_USE_COUNT (i) || DF_REG_EQ_USE_COUNT (i))
336	{
337	const char * sep = "";
338
339	fprintf (stream: file, format: "r%d={", i);
340	if (DF_REG_DEF_COUNT (i))
341	{
342	fprintf (stream: file, format: "%dd", DF_REG_DEF_COUNT (i));
343	sep = ",";
344	dcount += DF_REG_DEF_COUNT (i);
345	}
346	if (DF_REG_USE_COUNT (i))
347	{
348	fprintf (stream: file, format: "%s%du", sep, DF_REG_USE_COUNT (i));
349	sep = ",";
350	ucount += DF_REG_USE_COUNT (i);
351	}
352	if (DF_REG_EQ_USE_COUNT (i))
353	{
354	fprintf (stream: file, format: "%s%de", sep, DF_REG_EQ_USE_COUNT (i));
355	ecount += DF_REG_EQ_USE_COUNT (i);
356	}
357	fprintf (stream: file, format: "} ");
358	}
359
360	FOR_EACH_BB_FN (bb, cfun)
361	FOR_BB_INSNS (bb, insn)
362	if (INSN_P (insn))
363	{
364	if (CALL_P (insn))
365	ccount++;
366	else
367	icount++;
368	}
369
370	fprintf (stream: file, format: "\n;; total ref usage %d{%dd,%du,%de}"
371	" in %d{%d regular + %d call} insns.\n",
372	dcount + ucount + ecount, dcount, ucount, ecount,
373	icount + ccount, icount, ccount);
374	}
375
376	/* Dump the bb_info for a given basic block. */
377	static void
378	df_scan_start_block (basic_block bb, FILE *file)
379	{
380	struct df_scan_bb_info *bb_info
381	= df_scan_get_bb_info (index: bb->index);
382
383	if (bb_info)
384	{
385	fprintf (stream: file, format: ";; bb %d artificial_defs: ", bb->index);
386	df_refs_chain_dump (bb_info->artificial_defs, true, file);
387	fprintf (stream: file, format: "\n;; bb %d artificial_uses: ", bb->index);
388	df_refs_chain_dump (bb_info->artificial_uses, true, file);
389	fprintf (stream: file, format: "\n");
390	}
391	#if 0
392	{
393	rtx_insn *insn;
394	FOR_BB_INSNS (bb, insn)
395	if (INSN_P (insn))
396	df_insn_debug (insn, false, file);
397	}
398	#endif
399	}
400
401	static const struct df_problem problem_SCAN =
402	{
403	.id: DF_SCAN, /* Problem id. */
404	.dir: DF_NONE, /* Direction. */
405	.alloc_fun: df_scan_alloc, /* Allocate the problem specific data. */
406	NULL, /* Reset global information. */
407	.free_bb_fun: df_scan_free_bb_info, /* Free basic block info. */
408	NULL, /* Local compute function. */
409	NULL, /* Init the solution specific data. */
410	NULL, /* Iterative solver. */
411	NULL, /* Confluence operator 0. */
412	NULL, /* Confluence operator n. */
413	NULL, /* Transfer function. */
414	NULL, /* Finalize function. */
415	.free_fun: df_scan_free, /* Free all of the problem information. */
416	NULL, /* Remove this problem from the stack of dataflow problems. */
417	.dump_start_fun: df_scan_start_dump, /* Debugging. */
418	.dump_top_fun: df_scan_start_block, /* Debugging start block. */
419	NULL, /* Debugging end block. */
420	NULL, /* Debugging start insn. */
421	NULL, /* Debugging end insn. */
422	NULL, /* Incremental solution verify start. */
423	NULL, /* Incremental solution verify end. */
424	NULL, /* Dependent problem. */
425	.block_info_elt_size: sizeof (struct df_scan_bb_info),/* Size of entry of block_info array. */
426	.tv_id: TV_DF_SCAN, /* Timing variable. */
427	.free_blocks_on_set_blocks: false /* Reset blocks on dropping out of blocks_to_analyze. */
428	};
429
430
431	/* Create a new DATAFLOW instance and add it to an existing instance
432	of DF. The returned structure is what is used to get at the
433	solution. */
434
435	void
436	df_scan_add_problem (void)
437	{
438	df_add_problem (&problem_SCAN);
439	}
440
441
442	/*----------------------------------------------------------------------------
443	Storage Allocation Utilities
444	----------------------------------------------------------------------------*/
445
446
447	/* First, grow the reg_info information. If the current size is less than
448	the number of pseudos, grow to 25% more than the number of
449	pseudos.
450
451	Second, assure that all of the slots up to max_reg_num have been
452	filled with reg_info structures. */
453
454	void
455	df_grow_reg_info (void)
456	{
457	unsigned int max_reg = max_reg_num ();
458	unsigned int new_size = max_reg;
459	struct df_scan_problem_data *problem_data
460	= (struct df_scan_problem_data *) df_scan->problem_data;
461	unsigned int i;
462
463	if (df->regs_size < new_size)
464	{
465	new_size += new_size / 4;
466	df->def_regs = XRESIZEVEC (struct df_reg_info *, df->def_regs, new_size);
467	df->use_regs = XRESIZEVEC (struct df_reg_info *, df->use_regs, new_size);
468	df->eq_use_regs = XRESIZEVEC (struct df_reg_info *, df->eq_use_regs,
469	new_size);
470	df->def_info.begin = XRESIZEVEC (unsigned, df->def_info.begin, new_size);
471	df->def_info.count = XRESIZEVEC (unsigned, df->def_info.count, new_size);
472	df->use_info.begin = XRESIZEVEC (unsigned, df->use_info.begin, new_size);
473	df->use_info.count = XRESIZEVEC (unsigned, df->use_info.count, new_size);
474	df->regs_size = new_size;
475	}
476
477	for (i = df->regs_inited; i < max_reg; i++)
478	{
479	struct df_reg_info *reg_info;
480
481	// TODO
482	reg_info = problem_data->reg_pool->allocate ();
483	memset (s: reg_info, c: 0, n: sizeof (struct df_reg_info));
484	df->def_regs[i] = reg_info;
485	reg_info = problem_data->reg_pool->allocate ();
486	memset (s: reg_info, c: 0, n: sizeof (struct df_reg_info));
487	df->use_regs[i] = reg_info;
488	reg_info = problem_data->reg_pool->allocate ();
489	memset (s: reg_info, c: 0, n: sizeof (struct df_reg_info));
490	df->eq_use_regs[i] = reg_info;
491	df->def_info.begin[i] = 0;
492	df->def_info.count[i] = 0;
493	df->use_info.begin[i] = 0;
494	df->use_info.count[i] = 0;
495	}
496
497	df->regs_inited = max_reg;
498	}
499
500
501	/* Grow the ref information. */
502
503	static void
504	df_grow_ref_info (struct df_ref_info *ref_info, unsigned int new_size)
505	{
506	if (ref_info->refs_size < new_size)
507	{
508	ref_info->refs = XRESIZEVEC (df_ref, ref_info->refs, new_size);
509	memset (s: ref_info->refs + ref_info->refs_size, c: 0,
510	n: (new_size - ref_info->refs_size) *sizeof (df_ref));
511	ref_info->refs_size = new_size;
512	}
513	}
514
515
516	/* Check and grow the ref information if necessary. This routine
517	guarantees total_size + BITMAP_ADDEND amount of entries in refs
518	array. It updates ref_info->refs_size only and does not change
519	ref_info->total_size. */
520
521	static void
522	df_check_and_grow_ref_info (struct df_ref_info *ref_info,
523	unsigned bitmap_addend)
524	{
525	if (ref_info->refs_size < ref_info->total_size + bitmap_addend)
526	{
527	int new_size = ref_info->total_size + bitmap_addend;
528	new_size += ref_info->total_size / 4;
529	df_grow_ref_info (ref_info, new_size);
530	}
531	}
532
533
534	/* Grow the ref information. If the current size is less than the
535	number of instructions, grow to 25% more than the number of
536	instructions. */
537
538	void
539	df_grow_insn_info (void)
540	{
541	unsigned int new_size = get_max_uid () + 1;
542	if (DF_INSN_SIZE () < new_size)
543	{
544	new_size += new_size / 4;
545	df->insns = XRESIZEVEC (struct df_insn_info *, df->insns, new_size);
546	memset (s: df->insns + df->insns_size, c: 0,
547	n: (new_size - DF_INSN_SIZE ()) *sizeof (struct df_insn_info *));
548	DF_INSN_SIZE () = new_size;
549	}
550	}
551
552
553
554
555	/*----------------------------------------------------------------------------
556	PUBLIC INTERFACES FOR SMALL GRAIN CHANGES TO SCANNING.
557	----------------------------------------------------------------------------*/
558
559	/* Rescan all of the block_to_analyze or all of the blocks in the
560	function if df_set_blocks if blocks_to_analyze is NULL; */
561
562	void
563	df_scan_blocks (void)
564	{
565	basic_block bb;
566
567	df->def_info.ref_order = DF_REF_ORDER_NO_TABLE;
568	df->use_info.ref_order = DF_REF_ORDER_NO_TABLE;
569
570	df_get_regular_block_artificial_uses (&df->regular_block_artificial_uses);
571	df_get_eh_block_artificial_uses (&df->eh_block_artificial_uses);
572
573	bitmap_ior_into (&df->eh_block_artificial_uses,
574	&df->regular_block_artificial_uses);
575
576	/* ENTRY and EXIT blocks have special defs/uses. */
577	df_get_entry_block_def_set (df->entry_block_defs);
578	df_record_entry_block_defs (df->entry_block_defs);
579	df_get_exit_block_use_set (df->exit_block_uses);
580	df_record_exit_block_uses (df->exit_block_uses);
581	df_set_bb_dirty (BASIC_BLOCK_FOR_FN (cfun, ENTRY_BLOCK));
582	df_set_bb_dirty (BASIC_BLOCK_FOR_FN (cfun, EXIT_BLOCK));
583
584	/* Regular blocks */
585	FOR_EACH_BB_FN (bb, cfun)
586	{
587	unsigned int bb_index = bb->index;
588	df_bb_refs_record (bb_index, true);
589	}
590	}
591
592	/* Create new refs under address LOC within INSN. This function is
593	only used externally. REF_FLAGS must be either 0 or DF_REF_IN_NOTE,
594	depending on whether LOC is inside PATTERN (INSN) or a note. */
595
596	void
597	df_uses_create (rtx *loc, rtx_insn *insn, int ref_flags)
598	{
599	gcc_assert (!(ref_flags & ~DF_REF_IN_NOTE));
600	df_uses_record (NULL, loc, DF_REF_REG_USE,
601	BLOCK_FOR_INSN (insn),
602	DF_INSN_INFO_GET (insn),
603	ref_flags);
604	}
605
606	static void
607	df_install_ref_incremental (df_ref ref)
608	{
609	struct df_reg_info **reg_info;
610	struct df_ref_info *ref_info;
611	df_ref *ref_ptr;
612	bool add_to_table;
613
614	rtx_insn *insn = DF_REF_INSN (ref);
615	basic_block bb = BLOCK_FOR_INSN (insn);
616
617	if (DF_REF_REG_DEF_P (ref))
618	{
619	reg_info = df->def_regs;
620	ref_info = &df->def_info;
621	ref_ptr = &DF_INSN_DEFS (insn);
622	add_to_table = ref_info->ref_order != DF_REF_ORDER_NO_TABLE;
623	}
624	else if (DF_REF_FLAGS (ref) & DF_REF_IN_NOTE)
625	{
626	reg_info = df->eq_use_regs;
627	ref_info = &df->use_info;
628	ref_ptr = &DF_INSN_EQ_USES (insn);
629	switch (ref_info->ref_order)
630	{
631	case DF_REF_ORDER_UNORDERED_WITH_NOTES:
632	case DF_REF_ORDER_BY_REG_WITH_NOTES:
633	case DF_REF_ORDER_BY_INSN_WITH_NOTES:
634	add_to_table = true;
635	break;
636	default:
637	add_to_table = false;
638	break;
639	}
640	}
641	else
642	{
643	reg_info = df->use_regs;
644	ref_info = &df->use_info;
645	ref_ptr = &DF_INSN_USES (insn);
646	add_to_table = ref_info->ref_order != DF_REF_ORDER_NO_TABLE;
647	}
648
649	/* Do not add if ref is not in the right blocks. */
650	if (add_to_table && df->analyze_subset)
651	add_to_table = bitmap_bit_p (df->blocks_to_analyze, bb->index);
652
653	df_install_ref (ref, reg_info[DF_REF_REGNO (ref)], ref_info, add_to_table);
654
655	if (add_to_table)
656	switch (ref_info->ref_order)
657	{
658	case DF_REF_ORDER_UNORDERED_WITH_NOTES:
659	case DF_REF_ORDER_BY_REG_WITH_NOTES:
660	case DF_REF_ORDER_BY_INSN_WITH_NOTES:
661	ref_info->ref_order = DF_REF_ORDER_UNORDERED_WITH_NOTES;
662	break;
663	default:
664	ref_info->ref_order = DF_REF_ORDER_UNORDERED;
665	break;
666	}
667
668	while (*ref_ptr && df_ref_compare (*ref_ptr, ref) < 0)
669	ref_ptr = &DF_REF_NEXT_LOC (*ref_ptr);
670
671	DF_REF_NEXT_LOC (ref) = *ref_ptr;
672	*ref_ptr = ref;
673
674	#if 0
675	if (dump_file)
676	{
677	fprintf (dump_file, "adding ref ");
678	df_ref_debug (ref, dump_file);
679	}
680	#endif
681	/* By adding the ref directly, df_insn_rescan my not find any
682	differences even though the block will have changed. So we need
683	to mark the block dirty ourselves. */
684	if (!DEBUG_INSN_P (DF_REF_INSN (ref)))
685	df_set_bb_dirty (bb);
686	}
687
688
689
690	/*----------------------------------------------------------------------------
691	UTILITIES TO CREATE AND DESTROY REFS AND CHAINS.
692	----------------------------------------------------------------------------*/
693
694	static void
695	df_free_ref (df_ref ref)
696	{
697	struct df_scan_problem_data *problem_data
698	= (struct df_scan_problem_data *) df_scan->problem_data;
699
700	switch (DF_REF_CLASS (ref))
701	{
702	case DF_REF_BASE:
703	problem_data->ref_base_pool->remove (object: (df_base_ref *) (ref));
704	break;
705
706	case DF_REF_ARTIFICIAL:
707	problem_data->ref_artificial_pool->remove
708	(object: (df_artificial_ref *) (ref));
709	break;
710
711	case DF_REF_REGULAR:
712	problem_data->ref_regular_pool->remove
713	(object: (df_regular_ref *) (ref));
714	break;
715	}
716	}
717
718
719	/* Unlink and delete REF at the reg_use, reg_eq_use or reg_def chain.
720	Also delete the def-use or use-def chain if it exists. */
721
722	static void
723	df_reg_chain_unlink (df_ref ref)
724	{
725	df_ref next = DF_REF_NEXT_REG (ref);
726	df_ref prev = DF_REF_PREV_REG (ref);
727	int id = DF_REF_ID (ref);
728	struct df_reg_info *reg_info;
729	df_ref *refs = NULL;
730
731	if (DF_REF_REG_DEF_P (ref))
732	{
733	int regno = DF_REF_REGNO (ref);
734	reg_info = DF_REG_DEF_GET (regno);
735	refs = df->def_info.refs;
736	}
737	else
738	{
739	if (DF_REF_FLAGS (ref) & DF_REF_IN_NOTE)
740	{
741	reg_info = DF_REG_EQ_USE_GET (DF_REF_REGNO (ref));
742	switch (df->use_info.ref_order)
743	{
744	case DF_REF_ORDER_UNORDERED_WITH_NOTES:
745	case DF_REF_ORDER_BY_REG_WITH_NOTES:
746	case DF_REF_ORDER_BY_INSN_WITH_NOTES:
747	refs = df->use_info.refs;
748	break;
749	default:
750	break;
751	}
752	}
753	else
754	{
755	reg_info = DF_REG_USE_GET (DF_REF_REGNO (ref));
756	refs = df->use_info.refs;
757	}
758	}
759
760	if (refs)
761	{
762	if (df->analyze_subset)
763	{
764	if (bitmap_bit_p (df->blocks_to_analyze, DF_REF_BBNO (ref)))
765	refs[id] = NULL;
766	}
767	else
768	refs[id] = NULL;
769	}
770
771	/* Delete any def-use or use-def chains that start here. It is
772	possible that there is trash in this field. This happens for
773	insns that have been deleted when rescanning has been deferred
774	and the chain problem has also been deleted. The chain tear down
775	code skips deleted insns. */
776	if (df_chain && DF_REF_CHAIN (ref))
777	df_chain_unlink (ref);
778
779	reg_info->n_refs--;
780	if (DF_REF_FLAGS_IS_SET (ref, DF_HARD_REG_LIVE))
781	{
782	gcc_assert (DF_REF_REGNO (ref) < FIRST_PSEUDO_REGISTER);
783	df->hard_regs_live_count[DF_REF_REGNO (ref)]--;
784	}
785
786	/* Unlink from the reg chain. If there is no prev, this is the
787	first of the list. If not, just join the next and prev. */
788	if (prev)
789	DF_REF_NEXT_REG (prev) = next;
790	else
791	{
792	gcc_assert (reg_info->reg_chain == ref);
793	reg_info->reg_chain = next;
794	}
795	if (next)
796	DF_REF_PREV_REG (next) = prev;
797
798	df_free_ref (ref);
799	}
800
801	/* Initialize INSN_INFO to describe INSN. */
802
803	static void
804	df_insn_info_init_fields (df_insn_info *insn_info, rtx_insn *insn)
805	{
806	memset (s: insn_info, c: 0, n: sizeof (struct df_insn_info));
807	insn_info->insn = insn;
808	}
809
810	/* Create the insn record for INSN. If there was one there, zero it
811	out. */
812
813	struct df_insn_info *
814	df_insn_create_insn_record (rtx_insn *insn)
815	{
816	struct df_scan_problem_data *problem_data
817	= (struct df_scan_problem_data *) df_scan->problem_data;
818	struct df_insn_info *insn_rec;
819
820	df_grow_insn_info ();
821	insn_rec = DF_INSN_INFO_GET (insn);
822	if (!insn_rec)
823	{
824	insn_rec = problem_data->insn_pool->allocate ();
825	DF_INSN_INFO_SET (insn, insn_rec);
826	}
827	df_insn_info_init_fields (insn_info: insn_rec, insn);
828	return insn_rec;
829	}
830
831
832	/* Delete all du chain (DF_REF_CHAIN()) of all refs in the ref chain. */
833
834	static void
835	df_ref_chain_delete_du_chain (df_ref ref)
836	{
837	for (; ref; ref = DF_REF_NEXT_LOC (ref))
838	/* CHAIN is allocated by DF_CHAIN. So make sure to
839	pass df_scan instance for the problem. */
840	if (DF_REF_CHAIN (ref))
841	df_chain_unlink (ref);
842	}
843
844
845	/* Delete all refs in the ref chain. */
846
847	static void
848	df_ref_chain_delete (df_ref ref)
849	{
850	df_ref next;
851	for (; ref; ref = next)
852	{
853	next = DF_REF_NEXT_LOC (ref);
854	df_reg_chain_unlink (ref);
855	}
856	}
857
858
859	/* Delete the hardreg chain. */
860
861	static void
862	df_mw_hardreg_chain_delete (struct df_mw_hardreg *hardregs)
863	{
864	struct df_scan_problem_data *problem_data
865	= (struct df_scan_problem_data *) df_scan->problem_data;
866	df_mw_hardreg *next;
867
868	for (; hardregs; hardregs = next)
869	{
870	next = DF_MWS_NEXT (hardregs);
871	problem_data->mw_reg_pool->remove (object: hardregs);
872	}
873	}
874
875	/* Remove the contents of INSN_INFO (but don't free INSN_INFO itself). */
876
877	static void
878	df_insn_info_free_fields (df_insn_info *insn_info)
879	{
880	/* In general, notes do not have the insn_info fields
881	initialized. However, combine deletes insns by changing them
882	to notes. How clever. So we cannot just check if it is a
883	valid insn before short circuiting this code, we need to see
884	if we actually initialized it. */
885	df_mw_hardreg_chain_delete (hardregs: insn_info->mw_hardregs);
886
887	if (df_chain)
888	{
889	df_ref_chain_delete_du_chain (ref: insn_info->defs);
890	df_ref_chain_delete_du_chain (ref: insn_info->uses);
891	df_ref_chain_delete_du_chain (ref: insn_info->eq_uses);
892	}
893
894	df_ref_chain_delete (ref: insn_info->defs);
895	df_ref_chain_delete (ref: insn_info->uses);
896	df_ref_chain_delete (ref: insn_info->eq_uses);
897	}
898
899	/* Delete all of the refs information from the insn with UID.
900	Internal helper for df_insn_delete, df_insn_rescan, and other
901	df-scan routines that don't have to work in deferred mode
902	and do not have to mark basic blocks for re-processing. */
903
904	static void
905	df_insn_info_delete (unsigned int uid)
906	{
907	struct df_insn_info *insn_info = DF_INSN_UID_SAFE_GET (uid);
908
909	bitmap_clear_bit (&df->insns_to_delete, uid);
910	bitmap_clear_bit (&df->insns_to_rescan, uid);
911	bitmap_clear_bit (&df->insns_to_notes_rescan, uid);
912	if (insn_info)
913	{
914	struct df_scan_problem_data *problem_data
915	= (struct df_scan_problem_data *) df_scan->problem_data;
916
917	df_insn_info_free_fields (insn_info);
918	problem_data->insn_pool->remove (object: insn_info);
919	DF_INSN_UID_SET (uid, NULL);
920	}
921	}
922
923	/* Delete all of the refs information from INSN, either right now
924	or marked for later in deferred mode. */
925
926	void
927	df_insn_delete (rtx_insn *insn)
928	{
929	unsigned int uid;
930	basic_block bb;
931
932	gcc_checking_assert (INSN_P (insn));
933
934	if (!df)
935	return;
936
937	uid = INSN_UID (insn);
938	bb = BLOCK_FOR_INSN (insn);
939
940	/* ??? bb can be NULL after pass_free_cfg. At that point, DF should
941	not exist anymore (as mentioned in df-core.cc: "The only requirement
942	[for DF] is that there be a correct control flow graph." Clearly
943	that isn't the case after pass_free_cfg. But DF is freed much later
944	because some back-ends want to use DF info even though the CFG is
945	already gone. It's not clear to me whether that is safe, actually.
946	In any case, we expect BB to be non-NULL at least up to register
947	allocation, so disallow a non-NULL BB up to there. Not perfect
948	but better than nothing... */
949	gcc_checking_assert (bb != NULL || reload_completed);
950
951	df_grow_bb_info (df_scan);
952	df_grow_reg_info ();
953
954	/* The block must be marked as dirty now, rather than later as in
955	df_insn_rescan and df_notes_rescan because it may not be there at
956	rescanning time and the mark would blow up.
957	DEBUG_INSNs do not make a block's data flow solution dirty (at
958	worst the LUIDs are no longer contiguous). */
959	if (bb != NULL && NONDEBUG_INSN_P (insn))
960	df_set_bb_dirty (bb);
961
962	/* The client has deferred rescanning. */
963	if (df->changeable_flags & DF_DEFER_INSN_RESCAN)
964	{
965	struct df_insn_info *insn_info = DF_INSN_UID_SAFE_GET (uid);
966	if (insn_info)
967	{
968	bitmap_clear_bit (&df->insns_to_rescan, uid);
969	bitmap_clear_bit (&df->insns_to_notes_rescan, uid);
970	bitmap_set_bit (&df->insns_to_delete, uid);
971	}
972	if (dump_file)
973	fprintf (stream: dump_file, format: "deferring deletion of insn with uid = %d.\n", uid);
974	return;
975	}
976
977	if (dump_file)
978	fprintf (stream: dump_file, format: "deleting insn with uid = %d.\n", uid);
979
980	df_insn_info_delete (uid);
981	}
982
983
984	/* Free all of the refs and the mw_hardregs in COLLECTION_REC. */
985
986	static void
987	df_free_collection_rec (class df_collection_rec *collection_rec)
988	{
989	unsigned int ix;
990	struct df_scan_problem_data *problem_data
991	= (struct df_scan_problem_data *) df_scan->problem_data;
992	df_ref ref;
993	struct df_mw_hardreg *mw;
994
995	FOR_EACH_VEC_ELT (collection_rec->def_vec, ix, ref)
996	df_free_ref (ref);
997	FOR_EACH_VEC_ELT (collection_rec->use_vec, ix, ref)
998	df_free_ref (ref);
999	FOR_EACH_VEC_ELT (collection_rec->eq_use_vec, ix, ref)
1000	df_free_ref (ref);
1001	FOR_EACH_VEC_ELT (collection_rec->mw_vec, ix, mw)
1002	problem_data->mw_reg_pool->remove (object: mw);
1003
1004	collection_rec->def_vec.release ();
1005	collection_rec->use_vec.release ();
1006	collection_rec->eq_use_vec.release ();
1007	collection_rec->mw_vec.release ();
1008	}
1009
1010	/* Rescan INSN. Return TRUE if the rescanning produced any changes. */
1011
1012	bool
1013	df_insn_rescan (rtx_insn *insn)
1014	{
1015	unsigned int uid = INSN_UID (insn);
1016	struct df_insn_info *insn_info = NULL;
1017	basic_block bb = BLOCK_FOR_INSN (insn);
1018	class df_collection_rec collection_rec;
1019
1020	if ((!df) || (!INSN_P (insn)))
1021	return false;
1022
1023	if (!bb)
1024	{
1025	if (dump_file)
1026	fprintf (stream: dump_file, format: "no bb for insn with uid = %d.\n", uid);
1027	return false;
1028	}
1029
1030	/* The client has disabled rescanning and plans to do it itself. */
1031	if (df->changeable_flags & DF_NO_INSN_RESCAN)
1032	return false;
1033
1034	df_grow_bb_info (df_scan);
1035	df_grow_reg_info ();
1036
1037	insn_info = DF_INSN_UID_SAFE_GET (uid);
1038
1039	/* The client has deferred rescanning. */
1040	if (df->changeable_flags & DF_DEFER_INSN_RESCAN)
1041	{
1042	if (!insn_info)
1043	{
1044	insn_info = df_insn_create_insn_record (insn);
1045	insn_info->defs = 0;
1046	insn_info->uses = 0;
1047	insn_info->eq_uses = 0;
1048	insn_info->mw_hardregs = 0;
1049	}
1050	if (dump_file)
1051	fprintf (stream: dump_file, format: "deferring rescan insn with uid = %d.\n", uid);
1052
1053	bitmap_clear_bit (&df->insns_to_delete, uid);
1054	bitmap_clear_bit (&df->insns_to_notes_rescan, uid);
1055	bitmap_set_bit (&df->insns_to_rescan, INSN_UID (insn));
1056	return false;
1057	}
1058
1059	bitmap_clear_bit (&df->insns_to_delete, uid);
1060	bitmap_clear_bit (&df->insns_to_rescan, uid);
1061	bitmap_clear_bit (&df->insns_to_notes_rescan, uid);
1062	if (insn_info)
1063	{
1064	int luid;
1065	bool the_same = df_insn_refs_verify (&collection_rec, bb, insn, false);
1066	/* If there's no change, return false. */
1067	if (the_same)
1068	{
1069	df_free_collection_rec (collection_rec: &collection_rec);
1070	if (dump_file)
1071	fprintf (stream: dump_file, format: "verify found no changes in insn with uid = %d.\n", uid);
1072	return false;
1073	}
1074	if (dump_file)
1075	fprintf (stream: dump_file, format: "rescanning insn with uid = %d.\n", uid);
1076
1077	/* There's change - we need to delete the existing info.
1078	Since the insn isn't moved, we can salvage its LUID. */
1079	luid = DF_INSN_LUID (insn);
1080	df_insn_info_free_fields (insn_info);
1081	df_insn_info_init_fields (insn_info, insn);
1082	DF_INSN_LUID (insn) = luid;
1083	}
1084	else
1085	{
1086	struct df_insn_info *insn_info = df_insn_create_insn_record (insn);
1087	df_insn_refs_collect (&collection_rec, bb, insn_info);
1088	if (dump_file)
1089	fprintf (stream: dump_file, format: "scanning new insn with uid = %d.\n", uid);
1090	}
1091
1092	df_refs_add_to_chains (&collection_rec, bb, insn, copy_all);
1093	if (!DEBUG_INSN_P (insn))
1094	df_set_bb_dirty (bb);
1095
1096	return true;
1097	}
1098
1099	/* Same as df_insn_rescan, but don't mark the basic block as
1100	dirty. */
1101
1102	bool
1103	df_insn_rescan_debug_internal (rtx_insn *insn)
1104	{
1105	unsigned int uid = INSN_UID (insn);
1106	struct df_insn_info *insn_info;
1107
1108	gcc_assert (DEBUG_INSN_P (insn)
1109	&& VAR_LOC_UNKNOWN_P (INSN_VAR_LOCATION_LOC (insn)));
1110
1111	if (!df)
1112	return false;
1113
1114	insn_info = DF_INSN_UID_SAFE_GET (INSN_UID (insn));
1115	if (!insn_info)
1116	return false;
1117
1118	if (dump_file)
1119	fprintf (stream: dump_file, format: "deleting debug_insn with uid = %d.\n", uid);
1120
1121	bitmap_clear_bit (&df->insns_to_delete, uid);
1122	bitmap_clear_bit (&df->insns_to_rescan, uid);
1123	bitmap_clear_bit (&df->insns_to_notes_rescan, uid);
1124
1125	if (insn_info->defs == 0
1126	&& insn_info->uses == 0
1127	&& insn_info->eq_uses == 0
1128	&& insn_info->mw_hardregs == 0)
1129	return false;
1130
1131	df_mw_hardreg_chain_delete (hardregs: insn_info->mw_hardregs);
1132
1133	if (df_chain)
1134	{
1135	df_ref_chain_delete_du_chain (ref: insn_info->defs);
1136	df_ref_chain_delete_du_chain (ref: insn_info->uses);
1137	df_ref_chain_delete_du_chain (ref: insn_info->eq_uses);
1138	}
1139
1140	df_ref_chain_delete (ref: insn_info->defs);
1141	df_ref_chain_delete (ref: insn_info->uses);
1142	df_ref_chain_delete (ref: insn_info->eq_uses);
1143
1144	insn_info->defs = 0;
1145	insn_info->uses = 0;
1146	insn_info->eq_uses = 0;
1147	insn_info->mw_hardregs = 0;
1148
1149	return true;
1150	}
1151
1152
1153	/* Rescan all of the insns in the function. Note that the artificial
1154	uses and defs are not touched. This function will destroy def-use
1155	or use-def chains. */
1156
1157	void
1158	df_insn_rescan_all (void)
1159	{
1160	bool no_insn_rescan = false;
1161	bool defer_insn_rescan = false;
1162	basic_block bb;
1163	bitmap_iterator bi;
1164	unsigned int uid;
1165
1166	if (df->changeable_flags & DF_NO_INSN_RESCAN)
1167	{
1168	df_clear_flags (DF_NO_INSN_RESCAN);
1169	no_insn_rescan = true;
1170	}
1171
1172	if (df->changeable_flags & DF_DEFER_INSN_RESCAN)
1173	{
1174	df_clear_flags (DF_DEFER_INSN_RESCAN);
1175	defer_insn_rescan = true;
1176	}
1177
1178	auto_bitmap tmp (&df_bitmap_obstack);
1179	bitmap_copy (tmp, &df->insns_to_delete);
1180	EXECUTE_IF_SET_IN_BITMAP (tmp, 0, uid, bi)
1181	{
1182	struct df_insn_info *insn_info = DF_INSN_UID_SAFE_GET (uid);
1183	if (insn_info)
1184	df_insn_info_delete (uid);
1185	}
1186
1187	bitmap_clear (&df->insns_to_delete);
1188	bitmap_clear (&df->insns_to_rescan);
1189	bitmap_clear (&df->insns_to_notes_rescan);
1190
1191	FOR_EACH_BB_FN (bb, cfun)
1192	{
1193	rtx_insn *insn;
1194	FOR_BB_INSNS (bb, insn)
1195	{
1196	df_insn_rescan (insn);
1197	}
1198	}
1199
1200	if (no_insn_rescan)
1201	df_set_flags (DF_NO_INSN_RESCAN);
1202	if (defer_insn_rescan)
1203	df_set_flags (DF_DEFER_INSN_RESCAN);
1204	}
1205
1206
1207	/* Process all of the deferred rescans or deletions. */
1208
1209	void
1210	df_process_deferred_rescans (void)
1211	{
1212	bool no_insn_rescan = false;
1213	bool defer_insn_rescan = false;
1214	bitmap_iterator bi;
1215	unsigned int uid;
1216
1217	if (df->changeable_flags & DF_NO_INSN_RESCAN)
1218	{
1219	df_clear_flags (DF_NO_INSN_RESCAN);
1220	no_insn_rescan = true;
1221	}
1222
1223	if (df->changeable_flags & DF_DEFER_INSN_RESCAN)
1224	{
1225	df_clear_flags (DF_DEFER_INSN_RESCAN);
1226	defer_insn_rescan = true;
1227	}
1228
1229	if (dump_file)
1230	fprintf (stream: dump_file, format: "starting the processing of deferred insns\n");
1231
1232	auto_bitmap tmp (&df_bitmap_obstack);
1233	bitmap_copy (tmp, &df->insns_to_delete);
1234	EXECUTE_IF_SET_IN_BITMAP (tmp, 0, uid, bi)
1235	{
1236	struct df_insn_info *insn_info = DF_INSN_UID_SAFE_GET (uid);
1237	if (insn_info)
1238	df_insn_info_delete (uid);
1239	}
1240
1241	bitmap_copy (tmp, &df->insns_to_rescan);
1242	EXECUTE_IF_SET_IN_BITMAP (tmp, 0, uid, bi)
1243	{
1244	struct df_insn_info *insn_info = DF_INSN_UID_SAFE_GET (uid);
1245	if (insn_info)
1246	df_insn_rescan (insn: insn_info->insn);
1247	}
1248
1249	bitmap_copy (tmp, &df->insns_to_notes_rescan);
1250	EXECUTE_IF_SET_IN_BITMAP (tmp, 0, uid, bi)
1251	{
1252	struct df_insn_info *insn_info = DF_INSN_UID_SAFE_GET (uid);
1253	if (insn_info)
1254	df_notes_rescan (insn_info->insn);
1255	}
1256
1257	if (dump_file)
1258	fprintf (stream: dump_file, format: "ending the processing of deferred insns\n");
1259
1260	bitmap_clear (&df->insns_to_delete);
1261	bitmap_clear (&df->insns_to_rescan);
1262	bitmap_clear (&df->insns_to_notes_rescan);
1263
1264	if (no_insn_rescan)
1265	df_set_flags (DF_NO_INSN_RESCAN);
1266	if (defer_insn_rescan)
1267	df_set_flags (DF_DEFER_INSN_RESCAN);
1268
1269	/* If someone changed regs_ever_live during this pass, fix up the
1270	entry and exit blocks. */
1271	if (df->redo_entry_and_exit)
1272	{
1273	df_update_entry_exit_and_calls ();
1274	df->redo_entry_and_exit = false;
1275	}
1276	}
1277
1278
1279	/* Count the number of refs. Include the defs if INCLUDE_DEFS. Include
1280	the uses if INCLUDE_USES. Include the eq_uses if
1281	INCLUDE_EQ_USES. */
1282
1283	static unsigned int
1284	df_count_refs (bool include_defs, bool include_uses,
1285	bool include_eq_uses)
1286	{
1287	unsigned int regno;
1288	int size = 0;
1289	unsigned int m = df->regs_inited;
1290
1291	for (regno = 0; regno < m; regno++)
1292	{
1293	if (include_defs)
1294	size += DF_REG_DEF_COUNT (regno);
1295	if (include_uses)
1296	size += DF_REG_USE_COUNT (regno);
1297	if (include_eq_uses)
1298	size += DF_REG_EQ_USE_COUNT (regno);
1299	}
1300	return size;
1301	}
1302
1303
1304	/* Take build ref table for either the uses or defs from the reg-use
1305	or reg-def chains. This version processes the refs in reg order
1306	which is likely to be best if processing the whole function. */
1307
1308	static void
1309	df_reorganize_refs_by_reg_by_reg (struct df_ref_info *ref_info,
1310	bool include_defs,
1311	bool include_uses,
1312	bool include_eq_uses)
1313	{
1314	unsigned int m = df->regs_inited;
1315	unsigned int regno;
1316	unsigned int offset = 0;
1317	unsigned int start;
1318
1319	if (df->changeable_flags & DF_NO_HARD_REGS)
1320	{
1321	start = FIRST_PSEUDO_REGISTER;
1322	memset (s: ref_info->begin, c: 0, n: sizeof (int) * FIRST_PSEUDO_REGISTER);
1323	memset (s: ref_info->count, c: 0, n: sizeof (int) * FIRST_PSEUDO_REGISTER);
1324	}
1325	else
1326	start = 0;
1327
1328	ref_info->total_size
1329	= df_count_refs (include_defs, include_uses, include_eq_uses);
1330
1331	df_check_and_grow_ref_info (ref_info, bitmap_addend: 1);
1332
1333	for (regno = start; regno < m; regno++)
1334	{
1335	int count = 0;
1336	ref_info->begin[regno] = offset;
1337	if (include_defs)
1338	{
1339	df_ref ref = DF_REG_DEF_CHAIN (regno);
1340	while (ref)
1341	{
1342	ref_info->refs[offset] = ref;
1343	DF_REF_ID (ref) = offset++;
1344	count++;
1345	ref = DF_REF_NEXT_REG (ref);
1346	gcc_checking_assert (offset < ref_info->refs_size);
1347	}
1348	}
1349	if (include_uses)
1350	{
1351	df_ref ref = DF_REG_USE_CHAIN (regno);
1352	while (ref)
1353	{
1354	ref_info->refs[offset] = ref;
1355	DF_REF_ID (ref) = offset++;
1356	count++;
1357	ref = DF_REF_NEXT_REG (ref);
1358	gcc_checking_assert (offset < ref_info->refs_size);
1359	}
1360	}
1361	if (include_eq_uses)
1362	{
1363	df_ref ref = DF_REG_EQ_USE_CHAIN (regno);
1364	while (ref)
1365	{
1366	ref_info->refs[offset] = ref;
1367	DF_REF_ID (ref) = offset++;
1368	count++;
1369	ref = DF_REF_NEXT_REG (ref);
1370	gcc_checking_assert (offset < ref_info->refs_size);
1371	}
1372	}
1373	ref_info->count[regno] = count;
1374	}
1375
1376	/* The bitmap size is not decremented when refs are deleted. So
1377	reset it now that we have squished out all of the empty
1378	slots. */
1379	ref_info->table_size = offset;
1380	}
1381
1382
1383	/* Take build ref table for either the uses or defs from the reg-use
1384	or reg-def chains. This version processes the refs in insn order
1385	which is likely to be best if processing some segment of the
1386	function. */
1387
1388	static void
1389	df_reorganize_refs_by_reg_by_insn (struct df_ref_info *ref_info,
1390	bool include_defs,
1391	bool include_uses,
1392	bool include_eq_uses)
1393	{
1394	bitmap_iterator bi;
1395	unsigned int bb_index;
1396	unsigned int m = df->regs_inited;
1397	unsigned int offset = 0;
1398	unsigned int r;
1399	unsigned int start
1400	= (df->changeable_flags & DF_NO_HARD_REGS) ? FIRST_PSEUDO_REGISTER : 0;
1401
1402	memset (s: ref_info->begin, c: 0, n: sizeof (int) * df->regs_inited);
1403	memset (s: ref_info->count, c: 0, n: sizeof (int) * df->regs_inited);
1404
1405	ref_info->total_size = df_count_refs (include_defs, include_uses, include_eq_uses);
1406	df_check_and_grow_ref_info (ref_info, bitmap_addend: 1);
1407
1408	EXECUTE_IF_SET_IN_BITMAP (df->blocks_to_analyze, 0, bb_index, bi)
1409	{
1410	basic_block bb = BASIC_BLOCK_FOR_FN (cfun, bb_index);
1411	rtx_insn *insn;
1412	df_ref def, use;
1413
1414	if (include_defs)
1415	FOR_EACH_ARTIFICIAL_DEF (def, bb_index)
1416	{
1417	unsigned int regno = DF_REF_REGNO (def);
1418	ref_info->count[regno]++;
1419	}
1420	if (include_uses)
1421	FOR_EACH_ARTIFICIAL_USE (use, bb_index)
1422	{
1423	unsigned int regno = DF_REF_REGNO (use);
1424	ref_info->count[regno]++;
1425	}
1426
1427	FOR_BB_INSNS (bb, insn)
1428	{
1429	if (INSN_P (insn))
1430	{
1431	struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
1432
1433	if (include_defs)
1434	FOR_EACH_INSN_INFO_DEF (def, insn_info)
1435	{
1436	unsigned int regno = DF_REF_REGNO (def);
1437	ref_info->count[regno]++;
1438	}
1439	if (include_uses)
1440	FOR_EACH_INSN_INFO_USE (use, insn_info)
1441	{
1442	unsigned int regno = DF_REF_REGNO (use);
1443	ref_info->count[regno]++;
1444	}
1445	if (include_eq_uses)
1446	FOR_EACH_INSN_INFO_EQ_USE (use, insn_info)
1447	{
1448	unsigned int regno = DF_REF_REGNO (use);
1449	ref_info->count[regno]++;
1450	}
1451	}
1452	}
1453	}
1454
1455	for (r = start; r < m; r++)
1456	{
1457	ref_info->begin[r] = offset;
1458	offset += ref_info->count[r];
1459	ref_info->count[r] = 0;
1460	}
1461
1462	EXECUTE_IF_SET_IN_BITMAP (df->blocks_to_analyze, 0, bb_index, bi)
1463	{
1464	basic_block bb = BASIC_BLOCK_FOR_FN (cfun, bb_index);
1465	rtx_insn *insn;
1466	df_ref def, use;
1467
1468	if (include_defs)
1469	FOR_EACH_ARTIFICIAL_DEF (def, bb_index)
1470	{
1471	unsigned int regno = DF_REF_REGNO (def);
1472	if (regno >= start)
1473	{
1474	unsigned int id
1475	= ref_info->begin[regno] + ref_info->count[regno]++;
1476	DF_REF_ID (def) = id;
1477	ref_info->refs[id] = def;
1478	}
1479	}
1480	if (include_uses)
1481	FOR_EACH_ARTIFICIAL_USE (use, bb_index)
1482	{
1483	unsigned int regno = DF_REF_REGNO (def);
1484	if (regno >= start)
1485	{
1486	unsigned int id
1487	= ref_info->begin[regno] + ref_info->count[regno]++;
1488	DF_REF_ID (use) = id;
1489	ref_info->refs[id] = use;
1490	}
1491	}
1492
1493	FOR_BB_INSNS (bb, insn)
1494	{
1495	if (INSN_P (insn))
1496	{
1497	struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
1498
1499	if (include_defs)
1500	FOR_EACH_INSN_INFO_DEF (def, insn_info)
1501	{
1502	unsigned int regno = DF_REF_REGNO (def);
1503	if (regno >= start)
1504	{
1505	unsigned int id
1506	= ref_info->begin[regno] + ref_info->count[regno]++;
1507	DF_REF_ID (def) = id;
1508	ref_info->refs[id] = def;
1509	}
1510	}
1511	if (include_uses)
1512	FOR_EACH_INSN_INFO_USE (use, insn_info)
1513	{
1514	unsigned int regno = DF_REF_REGNO (use);
1515	if (regno >= start)
1516	{
1517	unsigned int id
1518	= ref_info->begin[regno] + ref_info->count[regno]++;
1519	DF_REF_ID (use) = id;
1520	ref_info->refs[id] = use;
1521	}
1522	}
1523	if (include_eq_uses)
1524	FOR_EACH_INSN_INFO_EQ_USE (use, insn_info)
1525	{
1526	unsigned int regno = DF_REF_REGNO (use);
1527	if (regno >= start)
1528	{
1529	unsigned int id
1530	= ref_info->begin[regno] + ref_info->count[regno]++;
1531	DF_REF_ID (use) = id;
1532	ref_info->refs[id] = use;
1533	}
1534	}
1535	}
1536	}
1537	}
1538
1539	/* The bitmap size is not decremented when refs are deleted. So
1540	reset it now that we have squished out all of the empty
1541	slots. */
1542
1543	ref_info->table_size = offset;
1544	}
1545
1546	/* Take build ref table for either the uses or defs from the reg-use
1547	or reg-def chains. */
1548
1549	static void
1550	df_reorganize_refs_by_reg (struct df_ref_info *ref_info,
1551	bool include_defs,
1552	bool include_uses,
1553	bool include_eq_uses)
1554	{
1555	if (df->analyze_subset)
1556	df_reorganize_refs_by_reg_by_insn (ref_info, include_defs,
1557	include_uses, include_eq_uses);
1558	else
1559	df_reorganize_refs_by_reg_by_reg (ref_info, include_defs,
1560	include_uses, include_eq_uses);
1561	}
1562
1563
1564	/* Add the refs in REF_VEC to the table in REF_INFO starting at OFFSET. */
1565	static unsigned int
1566	df_add_refs_to_table (unsigned int offset,
1567	struct df_ref_info *ref_info,
1568	df_ref ref)
1569	{
1570	for (; ref; ref = DF_REF_NEXT_LOC (ref))
1571	if (!(df->changeable_flags & DF_NO_HARD_REGS)
1572	|| (DF_REF_REGNO (ref) >= FIRST_PSEUDO_REGISTER))
1573	{
1574	ref_info->refs[offset] = ref;
1575	DF_REF_ID (ref) = offset++;
1576	}
1577	return offset;
1578	}
1579
1580
1581	/* Count the number of refs in all of the insns of BB. Include the
1582	defs if INCLUDE_DEFS. Include the uses if INCLUDE_USES. Include the
1583	eq_uses if INCLUDE_EQ_USES. */
1584
1585	static unsigned int
1586	df_reorganize_refs_by_insn_bb (basic_block bb, unsigned int offset,
1587	struct df_ref_info *ref_info,
1588	bool include_defs, bool include_uses,
1589	bool include_eq_uses)
1590	{
1591	rtx_insn *insn;
1592
1593	if (include_defs)
1594	offset = df_add_refs_to_table (offset, ref_info,
1595	ref: df_get_artificial_defs (bb_index: bb->index));
1596	if (include_uses)
1597	offset = df_add_refs_to_table (offset, ref_info,
1598	ref: df_get_artificial_uses (bb_index: bb->index));
1599
1600	FOR_BB_INSNS (bb, insn)
1601	if (INSN_P (insn))
1602	{
1603	unsigned int uid = INSN_UID (insn);
1604	if (include_defs)
1605	offset = df_add_refs_to_table (offset, ref_info,
1606	DF_INSN_UID_DEFS (uid));
1607	if (include_uses)
1608	offset = df_add_refs_to_table (offset, ref_info,
1609	DF_INSN_UID_USES (uid));
1610	if (include_eq_uses)
1611	offset = df_add_refs_to_table (offset, ref_info,
1612	DF_INSN_UID_EQ_USES (uid));
1613	}
1614	return offset;
1615	}
1616
1617
1618	/* Organize the refs by insn into the table in REF_INFO. If
1619	blocks_to_analyze is defined, use that set, otherwise the entire
1620	program. Include the defs if INCLUDE_DEFS. Include the uses if
1621	INCLUDE_USES. Include the eq_uses if INCLUDE_EQ_USES. */
1622
1623	static void
1624	df_reorganize_refs_by_insn (struct df_ref_info *ref_info,
1625	bool include_defs, bool include_uses,
1626	bool include_eq_uses)
1627	{
1628	basic_block bb;
1629	unsigned int offset = 0;
1630
1631	ref_info->total_size = df_count_refs (include_defs, include_uses, include_eq_uses);
1632	df_check_and_grow_ref_info (ref_info, bitmap_addend: 1);
1633	if (df->blocks_to_analyze)
1634	{
1635	bitmap_iterator bi;
1636	unsigned int index;
1637
1638	EXECUTE_IF_SET_IN_BITMAP (df->blocks_to_analyze, 0, index, bi)
1639	{
1640	offset = df_reorganize_refs_by_insn_bb (BASIC_BLOCK_FOR_FN (cfun,
1641	index),
1642	offset, ref_info,
1643	include_defs, include_uses,
1644	include_eq_uses);
1645	}
1646
1647	ref_info->table_size = offset;
1648	}
1649	else
1650	{
1651	FOR_ALL_BB_FN (bb, cfun)
1652	offset = df_reorganize_refs_by_insn_bb (bb, offset, ref_info,
1653	include_defs, include_uses,
1654	include_eq_uses);
1655	ref_info->table_size = offset;
1656	}
1657	}
1658
1659
1660	/* If the use refs in DF are not organized, reorganize them. */
1661
1662	void
1663	df_maybe_reorganize_use_refs (enum df_ref_order order)
1664	{
1665	if (order == df->use_info.ref_order)
1666	return;
1667
1668	switch (order)
1669	{
1670	case DF_REF_ORDER_BY_REG:
1671	df_reorganize_refs_by_reg (ref_info: &df->use_info, include_defs: false, include_uses: true, include_eq_uses: false);
1672	break;
1673
1674	case DF_REF_ORDER_BY_REG_WITH_NOTES:
1675	df_reorganize_refs_by_reg (ref_info: &df->use_info, include_defs: false, include_uses: true, include_eq_uses: true);
1676	break;
1677
1678	case DF_REF_ORDER_BY_INSN:
1679	df_reorganize_refs_by_insn (ref_info: &df->use_info, include_defs: false, include_uses: true, include_eq_uses: false);
1680	break;
1681
1682	case DF_REF_ORDER_BY_INSN_WITH_NOTES:
1683	df_reorganize_refs_by_insn (ref_info: &df->use_info, include_defs: false, include_uses: true, include_eq_uses: true);
1684	break;
1685
1686	case DF_REF_ORDER_NO_TABLE:
1687	free (ptr: df->use_info.refs);
1688	df->use_info.refs = NULL;
1689	df->use_info.refs_size = 0;
1690	break;
1691
1692	case DF_REF_ORDER_UNORDERED:
1693	case DF_REF_ORDER_UNORDERED_WITH_NOTES:
1694	gcc_unreachable ();
1695	break;
1696	}
1697
1698	df->use_info.ref_order = order;
1699	}
1700
1701
1702	/* If the def refs in DF are not organized, reorganize them. */
1703
1704	void
1705	df_maybe_reorganize_def_refs (enum df_ref_order order)
1706	{
1707	if (order == df->def_info.ref_order)
1708	return;
1709
1710	switch (order)
1711	{
1712	case DF_REF_ORDER_BY_REG:
1713	df_reorganize_refs_by_reg (ref_info: &df->def_info, include_defs: true, include_uses: false, include_eq_uses: false);
1714	break;
1715
1716	case DF_REF_ORDER_BY_INSN:
1717	df_reorganize_refs_by_insn (ref_info: &df->def_info, include_defs: true, include_uses: false, include_eq_uses: false);
1718	break;
1719
1720	case DF_REF_ORDER_NO_TABLE:
1721	free (ptr: df->def_info.refs);
1722	df->def_info.refs = NULL;
1723	df->def_info.refs_size = 0;
1724	break;
1725
1726	case DF_REF_ORDER_BY_INSN_WITH_NOTES:
1727	case DF_REF_ORDER_BY_REG_WITH_NOTES:
1728	case DF_REF_ORDER_UNORDERED:
1729	case DF_REF_ORDER_UNORDERED_WITH_NOTES:
1730	gcc_unreachable ();
1731	break;
1732	}
1733
1734	df->def_info.ref_order = order;
1735	}
1736
1737
1738	/* Change all of the basic block references in INSN to use the insn's
1739	current basic block. This function is called from routines that move
1740	instructions from one block to another. */
1741
1742	void
1743	df_insn_change_bb (rtx_insn *insn, basic_block new_bb)
1744	{
1745	basic_block old_bb = BLOCK_FOR_INSN (insn);
1746	struct df_insn_info *insn_info;
1747	unsigned int uid = INSN_UID (insn);
1748
1749	if (old_bb == new_bb)
1750	return;
1751
1752	set_block_for_insn (insn, bb: new_bb);
1753
1754	if (!df)
1755	return;
1756
1757	if (dump_file)
1758	fprintf (stream: dump_file, format: "changing bb of uid %d\n", uid);
1759
1760	insn_info = DF_INSN_UID_SAFE_GET (uid);
1761	if (insn_info == NULL)
1762	{
1763	if (dump_file)
1764	fprintf (stream: dump_file, format: " unscanned insn\n");
1765	df_insn_rescan (insn);
1766	return;
1767	}
1768
1769	if (!INSN_P (insn))
1770	return;
1771
1772	if (!DEBUG_INSN_P (insn))
1773	df_set_bb_dirty (new_bb);
1774	if (old_bb)
1775	{
1776	if (dump_file)
1777	fprintf (stream: dump_file, format: " from %d to %d\n",
1778	old_bb->index, new_bb->index);
1779	if (!DEBUG_INSN_P (insn))
1780	df_set_bb_dirty (old_bb);
1781	}
1782	else
1783	if (dump_file)
1784	fprintf (stream: dump_file, format: " to %d\n", new_bb->index);
1785	}
1786
1787
1788	/* Helper function for df_ref_change_reg_with_loc. */
1789
1790	static void
1791	df_ref_change_reg_with_loc_1 (struct df_reg_info *old_df,
1792	struct df_reg_info *new_df,
1793	unsigned int new_regno, rtx loc)
1794	{
1795	df_ref the_ref = old_df->reg_chain;
1796
1797	while (the_ref)
1798	{
1799	if ((!DF_REF_IS_ARTIFICIAL (the_ref))
1800	&& DF_REF_LOC (the_ref)
1801	&& (*DF_REF_LOC (the_ref) == loc))
1802	{
1803	df_ref next_ref = DF_REF_NEXT_REG (the_ref);
1804	df_ref prev_ref = DF_REF_PREV_REG (the_ref);
1805	df_ref *ref_ptr;
1806	struct df_insn_info *insn_info = DF_REF_INSN_INFO (the_ref);
1807
1808	DF_REF_REGNO (the_ref) = new_regno;
1809	DF_REF_REG (the_ref) = regno_reg_rtx[new_regno];
1810
1811	/* Pull the_ref out of the old regno chain. */
1812	if (prev_ref)
1813	DF_REF_NEXT_REG (prev_ref) = next_ref;
1814	else
1815	old_df->reg_chain = next_ref;
1816	if (next_ref)
1817	DF_REF_PREV_REG (next_ref) = prev_ref;
1818	old_df->n_refs--;
1819
1820	/* Put the ref into the new regno chain. */
1821	DF_REF_PREV_REG (the_ref) = NULL;
1822	DF_REF_NEXT_REG (the_ref) = new_df->reg_chain;
1823	if (new_df->reg_chain)
1824	DF_REF_PREV_REG (new_df->reg_chain) = the_ref;
1825	new_df->reg_chain = the_ref;
1826	new_df->n_refs++;
1827	if (DF_REF_BB (the_ref))
1828	df_set_bb_dirty (DF_REF_BB (the_ref));
1829
1830	/* Need to sort the record again that the ref was in because
1831	the regno is a sorting key. First, find the right
1832	record. */
1833	if (DF_REF_REG_DEF_P (the_ref))
1834	ref_ptr = &insn_info->defs;
1835	else if (DF_REF_FLAGS (the_ref) & DF_REF_IN_NOTE)
1836	ref_ptr = &insn_info->eq_uses;
1837	else
1838	ref_ptr = &insn_info->uses;
1839	if (dump_file)
1840	fprintf (stream: dump_file, format: "changing reg in insn %d\n",
1841	DF_REF_INSN_UID (the_ref));
1842
1843	/* Stop if we find the current reference or where the reference
1844	needs to be. */
1845	while (*ref_ptr != the_ref && df_ref_compare (*ref_ptr, the_ref) < 0)
1846	ref_ptr = &DF_REF_NEXT_LOC (*ref_ptr);
1847	if (*ref_ptr != the_ref)
1848	{
1849	/* The reference needs to be promoted up the list. */
1850	df_ref next = DF_REF_NEXT_LOC (the_ref);
1851	DF_REF_NEXT_LOC (the_ref) = *ref_ptr;
1852	*ref_ptr = the_ref;
1853	do
1854	ref_ptr = &DF_REF_NEXT_LOC (*ref_ptr);
1855	while (*ref_ptr != the_ref);
1856	*ref_ptr = next;
1857	}
1858	else if (DF_REF_NEXT_LOC (the_ref)
1859	&& df_ref_compare (the_ref, DF_REF_NEXT_LOC (the_ref)) > 0)
1860	{
1861	/* The reference needs to be demoted down the list. */
1862	*ref_ptr = DF_REF_NEXT_LOC (the_ref);
1863	do
1864	ref_ptr = &DF_REF_NEXT_LOC (*ref_ptr);
1865	while (*ref_ptr && df_ref_compare (the_ref, *ref_ptr) > 0);
1866	DF_REF_NEXT_LOC (the_ref) = *ref_ptr;
1867	*ref_ptr = the_ref;
1868	}
1869
1870	the_ref = next_ref;
1871	}
1872	else
1873	the_ref = DF_REF_NEXT_REG (the_ref);
1874	}
1875	}
1876
1877
1878	/* Change the regno of register LOC to NEW_REGNO and update the df
1879	information accordingly. Refs that do not match LOC are not changed
1880	which means that artificial refs are not changed since they have no loc.
1881	This call is to support the SET_REGNO macro. */
1882
1883	void
1884	df_ref_change_reg_with_loc (rtx loc, unsigned int new_regno)
1885	{
1886	unsigned int old_regno = REGNO (loc);
1887	if (old_regno == new_regno)
1888	return;
1889
1890	if (df)
1891	{
1892	df_grow_reg_info ();
1893
1894	df_ref_change_reg_with_loc_1 (DF_REG_DEF_GET (old_regno),
1895	DF_REG_DEF_GET (new_regno),
1896	new_regno, loc);
1897	df_ref_change_reg_with_loc_1 (DF_REG_USE_GET (old_regno),
1898	DF_REG_USE_GET (new_regno),
1899	new_regno, loc);
1900	df_ref_change_reg_with_loc_1 (DF_REG_EQ_USE_GET (old_regno),
1901	DF_REG_EQ_USE_GET (new_regno),
1902	new_regno, loc);
1903	}
1904	set_mode_and_regno (loc, GET_MODE (loc), new_regno);
1905	}
1906
1907
1908	/* Delete the mw_hardregs that point into the eq_notes. */
1909
1910	static void
1911	df_mw_hardreg_chain_delete_eq_uses (struct df_insn_info *insn_info)
1912	{
1913	struct df_mw_hardreg **mw_ptr = &insn_info->mw_hardregs;
1914	struct df_scan_problem_data *problem_data
1915	= (struct df_scan_problem_data *) df_scan->problem_data;
1916
1917	while (*mw_ptr)
1918	{
1919	df_mw_hardreg *mw = *mw_ptr;
1920	if (mw->flags & DF_REF_IN_NOTE)
1921	{
1922	*mw_ptr = DF_MWS_NEXT (mw);
1923	problem_data->mw_reg_pool->remove (object: mw);
1924	}
1925	else
1926	mw_ptr = &DF_MWS_NEXT (mw);
1927	}
1928	}
1929
1930
1931	/* Rescan only the REG_EQUIV/REG_EQUAL notes part of INSN. */
1932
1933	void
1934	df_notes_rescan (rtx_insn *insn)
1935	{
1936	struct df_insn_info *insn_info;
1937	unsigned int uid = INSN_UID (insn);
1938
1939	if (!df)
1940	return;
1941
1942	/* The client has disabled rescanning and plans to do it itself. */
1943	if (df->changeable_flags & DF_NO_INSN_RESCAN)
1944	return;
1945
1946	/* Do nothing if the insn hasn't been emitted yet. */
1947	if (!BLOCK_FOR_INSN (insn))
1948	return;
1949
1950	df_grow_bb_info (df_scan);
1951	df_grow_reg_info ();
1952
1953	insn_info = DF_INSN_UID_SAFE_GET (INSN_UID (insn));
1954
1955	/* The client has deferred rescanning. */
1956	if (df->changeable_flags & DF_DEFER_INSN_RESCAN)
1957	{
1958	if (!insn_info)
1959	{
1960	insn_info = df_insn_create_insn_record (insn);
1961	insn_info->defs = 0;
1962	insn_info->uses = 0;
1963	insn_info->eq_uses = 0;
1964	insn_info->mw_hardregs = 0;
1965	}
1966
1967	bitmap_clear_bit (&df->insns_to_delete, uid);
1968	/* If the insn is set to be rescanned, it does not need to also
1969	be notes rescanned. */
1970	if (!bitmap_bit_p (&df->insns_to_rescan, uid))
1971	bitmap_set_bit (&df->insns_to_notes_rescan, INSN_UID (insn));
1972	return;
1973	}
1974
1975	bitmap_clear_bit (&df->insns_to_delete, uid);
1976	bitmap_clear_bit (&df->insns_to_notes_rescan, uid);
1977
1978	if (insn_info)
1979	{
1980	basic_block bb = BLOCK_FOR_INSN (insn);
1981	rtx note;
1982	class df_collection_rec collection_rec;
1983	unsigned int i;
1984
1985	df_mw_hardreg_chain_delete_eq_uses (insn_info);
1986	df_ref_chain_delete (ref: insn_info->eq_uses);
1987	insn_info->eq_uses = NULL;
1988
1989	/* Process REG_EQUIV/REG_EQUAL notes */
1990	for (note = REG_NOTES (insn); note;
1991	note = XEXP (note, 1))
1992	{
1993	switch (REG_NOTE_KIND (note))
1994	{
1995	case REG_EQUIV:
1996	case REG_EQUAL:
1997	df_uses_record (&collection_rec,
1998	&XEXP (note, 0), DF_REF_REG_USE,
1999	bb, insn_info, ref_flags: DF_REF_IN_NOTE);
2000	default:
2001	break;
2002	}
2003	}
2004
2005	/* Find some place to put any new mw_hardregs. */
2006	df_canonize_collection_rec (&collection_rec);
2007	struct df_mw_hardreg **mw_ptr = &insn_info->mw_hardregs, *mw;
2008	FOR_EACH_VEC_ELT (collection_rec.mw_vec, i, mw)
2009	{
2010	while (*mw_ptr && df_mw_compare (*mw_ptr, mw) < 0)
2011	mw_ptr = &DF_MWS_NEXT (*mw_ptr);
2012	DF_MWS_NEXT (mw) = *mw_ptr;
2013	*mw_ptr = mw;
2014	mw_ptr = &DF_MWS_NEXT (mw);
2015	}
2016	df_refs_add_to_chains (&collection_rec, bb, insn, copy_eq_uses);
2017	}
2018	else
2019	df_insn_rescan (insn);
2020
2021	}
2022
2023
2024	/*----------------------------------------------------------------------------
2025	Hard core instruction scanning code. No external interfaces here,
2026	just a lot of routines that look inside insns.
2027	----------------------------------------------------------------------------*/
2028
2029
2030	/* Return true if the contents of two df_ref's are identical.
2031	It ignores DF_REF_MARKER. */
2032
2033	static bool
2034	df_ref_equal_p (df_ref ref1, df_ref ref2)
2035	{
2036	if (!ref2)
2037	return false;
2038
2039	if (ref1 == ref2)
2040	return true;
2041
2042	if (DF_REF_CLASS (ref1) != DF_REF_CLASS (ref2)
2043	|| DF_REF_REGNO (ref1) != DF_REF_REGNO (ref2)
2044	|| DF_REF_REG (ref1) != DF_REF_REG (ref2)
2045	|| DF_REF_TYPE (ref1) != DF_REF_TYPE (ref2)
2046	|| ((DF_REF_FLAGS (ref1) & ~(DF_REF_REG_MARKER + DF_REF_MW_HARDREG))
2047	!= (DF_REF_FLAGS (ref2) & ~(DF_REF_REG_MARKER + DF_REF_MW_HARDREG)))
2048	|| DF_REF_BB (ref1) != DF_REF_BB (ref2)
2049	|| DF_REF_INSN_INFO (ref1) != DF_REF_INSN_INFO (ref2))
2050	return false;
2051
2052	switch (DF_REF_CLASS (ref1))
2053	{
2054	case DF_REF_ARTIFICIAL:
2055	case DF_REF_BASE:
2056	return true;
2057
2058	case DF_REF_REGULAR:
2059	return DF_REF_LOC (ref1) == DF_REF_LOC (ref2);
2060
2061	default:
2062	gcc_unreachable ();
2063	}
2064	}
2065
2066
2067	/* Compare REF1 and REF2 for sorting. This is only called from places
2068	where all of the refs are of the same type, in the same insn, and
2069	have the same bb. So these fields are not checked. */
2070
2071	static int
2072	df_ref_compare (df_ref ref1, df_ref ref2)
2073	{
2074	if (DF_REF_CLASS (ref1) != DF_REF_CLASS (ref2))
2075	return (int)DF_REF_CLASS (ref1) - (int)DF_REF_CLASS (ref2);
2076
2077	if (DF_REF_REGNO (ref1) != DF_REF_REGNO (ref2))
2078	return (int)DF_REF_REGNO (ref1) - (int)DF_REF_REGNO (ref2);
2079
2080	if (DF_REF_TYPE (ref1) != DF_REF_TYPE (ref2))
2081	return (int)DF_REF_TYPE (ref1) - (int)DF_REF_TYPE (ref2);
2082
2083	if (DF_REF_REG (ref1) != DF_REF_REG (ref2))
2084	return (int)DF_REF_ORDER (ref1) - (int)DF_REF_ORDER (ref2);
2085
2086	/* Cannot look at the LOC field on artificial refs. */
2087	if (DF_REF_CLASS (ref1) != DF_REF_ARTIFICIAL
2088	&& DF_REF_LOC (ref1) != DF_REF_LOC (ref2))
2089	return (int)DF_REF_ORDER (ref1) - (int)DF_REF_ORDER (ref2);
2090
2091	if (DF_REF_FLAGS (ref1) != DF_REF_FLAGS (ref2))
2092	{
2093	/* If two refs are identical except that one of them has is from
2094	a mw and one is not, we need to have the one with the mw
2095	first. */
2096	if (DF_REF_FLAGS_IS_SET (ref1, DF_REF_MW_HARDREG) ==
2097	DF_REF_FLAGS_IS_SET (ref2, DF_REF_MW_HARDREG))
2098	return DF_REF_FLAGS (ref1) - DF_REF_FLAGS (ref2);
2099	else if (DF_REF_FLAGS_IS_SET (ref1, DF_REF_MW_HARDREG))
2100	return -1;
2101	else
2102	return 1;
2103	}
2104
2105	return (int)DF_REF_ORDER (ref1) - (int)DF_REF_ORDER (ref2);
2106	}
2107
2108	/* Like df_ref_compare, but compare two df_ref* pointers R1 and R2. */
2109
2110	static int
2111	df_ref_ptr_compare (const void *r1, const void *r2)
2112	{
2113	return df_ref_compare (ref1: *(const df_ref *) r1, ref2: *(const df_ref *) r2);
2114	}
2115
2116	/* Sort and compress a set of refs. */
2117
2118	static void
2119	df_sort_and_compress_refs (vec<df_ref, va_heap> *ref_vec)
2120	{
2121	unsigned int count;
2122	unsigned int i;
2123	unsigned int dist = 0;
2124
2125	count = ref_vec->length ();
2126
2127	/* If there are 1 or 0 elements, there is nothing to do. */
2128	if (count < 2)
2129	return;
2130	else if (count == 2)
2131	{
2132	df_ref r0 = (*ref_vec)[0];
2133	df_ref r1 = (*ref_vec)[1];
2134	if (df_ref_compare (ref1: r0, ref2: r1) > 0)
2135	std::swap (a&: (*ref_vec)[0], b&: (*ref_vec)[1]);
2136	}
2137	else
2138	{
2139	for (i = 0; i < count - 1; i++)
2140	{
2141	df_ref r0 = (*ref_vec)[i];
2142	df_ref r1 = (*ref_vec)[i + 1];
2143	if (df_ref_compare (ref1: r0, ref2: r1) >= 0)
2144	break;
2145	}
2146	/* If the array is already strictly ordered,
2147	which is the most common case for large COUNT case
2148	(which happens for CALL INSNs),
2149	no need to sort and filter out duplicate.
2150	Simply return the count.
2151	Make sure DF_GET_ADD_REFS adds refs in the increasing order
2152	of DF_REF_COMPARE. */
2153	if (i == count - 1)
2154	return;
2155	ref_vec->qsort (df_ref_ptr_compare);
2156	}
2157
2158	for (i=0; i<count-dist; i++)
2159	{
2160	/* Find the next ref that is not equal to the current ref. */
2161	while (i + dist + 1 < count
2162	&& df_ref_equal_p (ref1: (*ref_vec)[i],
2163	ref2: (*ref_vec)[i + dist + 1]))
2164	{
2165	df_free_ref (ref: (*ref_vec)[i + dist + 1]);
2166	dist++;
2167	}
2168	/* Copy it down to the next position. */
2169	if (dist && i + dist + 1 < count)
2170	(*ref_vec)[i + 1] = (*ref_vec)[i + dist + 1];
2171	}
2172
2173	count -= dist;
2174	ref_vec->truncate (size: count);
2175	}
2176
2177
2178	/* Return true if the contents of two df_ref's are identical.
2179	It ignores DF_REF_MARKER. */
2180
2181	static bool
2182	df_mw_equal_p (struct df_mw_hardreg *mw1, struct df_mw_hardreg *mw2)
2183	{
2184	if (!mw2)
2185	return false;
2186	return (mw1 == mw2) ||
2187	(mw1->mw_reg == mw2->mw_reg
2188	&& mw1->type == mw2->type
2189	&& mw1->flags == mw2->flags
2190	&& mw1->start_regno == mw2->start_regno
2191	&& mw1->end_regno == mw2->end_regno);
2192	}
2193
2194
2195	/* Compare MW1 and MW2 for sorting. */
2196
2197	static int
2198	df_mw_compare (const df_mw_hardreg *mw1, const df_mw_hardreg *mw2)
2199	{
2200	if (mw1->type != mw2->type)
2201	return mw1->type - mw2->type;
2202
2203	if (mw1->flags != mw2->flags)
2204	return mw1->flags - mw2->flags;
2205
2206	if (mw1->start_regno != mw2->start_regno)
2207	return mw1->start_regno - mw2->start_regno;
2208
2209	if (mw1->end_regno != mw2->end_regno)
2210	return mw1->end_regno - mw2->end_regno;
2211
2212	return mw1->mw_order - mw2->mw_order;
2213	}
2214
2215	/* Like df_mw_compare, but compare two df_mw_hardreg** pointers R1 and R2. */
2216
2217	static int
2218	df_mw_ptr_compare (const void *m1, const void *m2)
2219	{
2220	return df_mw_compare (mw1: *(const df_mw_hardreg *const *) m1,
2221	mw2: *(const df_mw_hardreg *const *) m2);
2222	}
2223
2224	/* Sort and compress a set of refs. */
2225
2226	static void
2227	df_sort_and_compress_mws (vec<df_mw_hardreg *, va_heap> *mw_vec)
2228	{
2229	unsigned int count;
2230	struct df_scan_problem_data *problem_data
2231	= (struct df_scan_problem_data *) df_scan->problem_data;
2232	unsigned int i;
2233	unsigned int dist = 0;
2234
2235	count = mw_vec->length ();
2236	if (count < 2)
2237	return;
2238	else if (count == 2)
2239	{
2240	struct df_mw_hardreg *m0 = (*mw_vec)[0];
2241	struct df_mw_hardreg *m1 = (*mw_vec)[1];
2242	if (df_mw_compare (mw1: m0, mw2: m1) > 0)
2243	{
2244	struct df_mw_hardreg *tmp = (*mw_vec)[0];
2245	(*mw_vec)[0] = (*mw_vec)[1];
2246	(*mw_vec)[1] = tmp;
2247	}
2248	}
2249	else
2250	mw_vec->qsort (df_mw_ptr_compare);
2251
2252	for (i=0; i<count-dist; i++)
2253	{
2254	/* Find the next ref that is not equal to the current ref. */
2255	while (i + dist + 1 < count
2256	&& df_mw_equal_p (mw1: (*mw_vec)[i], mw2: (*mw_vec)[i + dist + 1]))
2257	{
2258	problem_data->mw_reg_pool->remove (object: (*mw_vec)[i + dist + 1]);
2259	dist++;
2260	}
2261	/* Copy it down to the next position. */
2262	if (dist && i + dist + 1 < count)
2263	(*mw_vec)[i + 1] = (*mw_vec)[i + dist + 1];
2264	}
2265
2266	count -= dist;
2267	mw_vec->truncate (size: count);
2268	}
2269
2270
2271	/* Sort and remove duplicates from the COLLECTION_REC. */
2272
2273	static void
2274	df_canonize_collection_rec (class df_collection_rec *collection_rec)
2275	{
2276	df_sort_and_compress_refs (ref_vec: &collection_rec->def_vec);
2277	df_sort_and_compress_refs (ref_vec: &collection_rec->use_vec);
2278	df_sort_and_compress_refs (ref_vec: &collection_rec->eq_use_vec);
2279	df_sort_and_compress_mws (mw_vec: &collection_rec->mw_vec);
2280	}
2281
2282
2283	/* Add the new df_ref to appropriate reg_info/ref_info chains. */
2284
2285	static void
2286	df_install_ref (df_ref this_ref,
2287	struct df_reg_info *reg_info,
2288	struct df_ref_info *ref_info,
2289	bool add_to_table)
2290	{
2291	unsigned int regno = DF_REF_REGNO (this_ref);
2292	/* Add the ref to the reg_{def,use,eq_use} chain. */
2293	df_ref head = reg_info->reg_chain;
2294
2295	reg_info->reg_chain = this_ref;
2296	reg_info->n_refs++;
2297
2298	if (DF_REF_FLAGS_IS_SET (this_ref, DF_HARD_REG_LIVE))
2299	{
2300	gcc_assert (regno < FIRST_PSEUDO_REGISTER);
2301	df->hard_regs_live_count[regno]++;
2302	}
2303
2304	gcc_checking_assert (DF_REF_NEXT_REG (this_ref) == NULL
2305	&& DF_REF_PREV_REG (this_ref) == NULL);
2306
2307	DF_REF_NEXT_REG (this_ref) = head;
2308
2309	/* We cannot actually link to the head of the chain. */
2310	DF_REF_PREV_REG (this_ref) = NULL;
2311
2312	if (head)
2313	DF_REF_PREV_REG (head) = this_ref;
2314
2315	if (add_to_table)
2316	{
2317	gcc_assert (ref_info->ref_order != DF_REF_ORDER_NO_TABLE);
2318	df_check_and_grow_ref_info (ref_info, bitmap_addend: 1);
2319	DF_REF_ID (this_ref) = ref_info->table_size;
2320	/* Add the ref to the big array of defs. */
2321	ref_info->refs[ref_info->table_size] = this_ref;
2322	ref_info->table_size++;
2323	}
2324	else
2325	DF_REF_ID (this_ref) = -1;
2326
2327	ref_info->total_size++;
2328	}
2329
2330
2331	/* This function takes one of the groups of refs (defs, uses or
2332	eq_uses) and installs the entire group into the insn. It also adds
2333	each of these refs into the appropriate chains. */
2334
2335	static df_ref
2336	df_install_refs (basic_block bb,
2337	const vec<df_ref, va_heap> *old_vec,
2338	struct df_reg_info **reg_info,
2339	struct df_ref_info *ref_info,
2340	bool is_notes)
2341	{
2342	unsigned int count = old_vec->length ();
2343	if (count)
2344	{
2345	bool add_to_table;
2346	df_ref this_ref;
2347	unsigned int ix;
2348
2349	switch (ref_info->ref_order)
2350	{
2351	case DF_REF_ORDER_UNORDERED_WITH_NOTES:
2352	case DF_REF_ORDER_BY_REG_WITH_NOTES:
2353	case DF_REF_ORDER_BY_INSN_WITH_NOTES:
2354	ref_info->ref_order = DF_REF_ORDER_UNORDERED_WITH_NOTES;
2355	add_to_table = true;
2356	break;
2357	case DF_REF_ORDER_UNORDERED:
2358	case DF_REF_ORDER_BY_REG:
2359	case DF_REF_ORDER_BY_INSN:
2360	ref_info->ref_order = DF_REF_ORDER_UNORDERED;
2361	add_to_table = !is_notes;
2362	break;
2363	default:
2364	add_to_table = false;
2365	break;
2366	}
2367
2368	/* Do not add if ref is not in the right blocks. */
2369	if (add_to_table && df->analyze_subset)
2370	add_to_table = bitmap_bit_p (df->blocks_to_analyze, bb->index);
2371
2372	FOR_EACH_VEC_ELT (*old_vec, ix, this_ref)
2373	{
2374	DF_REF_NEXT_LOC (this_ref) = (ix + 1 < old_vec->length ()
2375	? (*old_vec)[ix + 1]
2376	: NULL);
2377	df_install_ref (this_ref, reg_info: reg_info[DF_REF_REGNO (this_ref)],
2378	ref_info, add_to_table);
2379	}
2380	return (*old_vec)[0];
2381	}
2382	else
2383	return 0;
2384	}
2385
2386
2387	/* This function takes the mws installs the entire group into the
2388	insn. */
2389
2390	static struct df_mw_hardreg *
2391	df_install_mws (const vec<df_mw_hardreg *, va_heap> *old_vec)
2392	{
2393	unsigned int count = old_vec->length ();
2394	if (count)
2395	{
2396	for (unsigned int i = 0; i < count - 1; i++)
2397	DF_MWS_NEXT ((*old_vec)[i]) = (*old_vec)[i + 1];
2398	DF_MWS_NEXT ((*old_vec)[count - 1]) = 0;
2399	return (*old_vec)[0];
2400	}
2401	else
2402	return 0;
2403	}
2404
2405
2406	/* Add a chain of df_refs to appropriate ref chain/reg_info/ref_info
2407	chains and update other necessary information. */
2408
2409	static void
2410	df_refs_add_to_chains (class df_collection_rec *collection_rec,
2411	basic_block bb, rtx_insn *insn, unsigned int flags)
2412	{
2413	if (insn)
2414	{
2415	struct df_insn_info *insn_rec = DF_INSN_INFO_GET (insn);
2416	/* If there is a vector in the collection rec, add it to the
2417	insn. A null rec is a signal that the caller will handle the
2418	chain specially. */
2419	if (flags & copy_defs)
2420	{
2421	gcc_checking_assert (!insn_rec->defs);
2422	insn_rec->defs
2423	= df_install_refs (bb, old_vec: &collection_rec->def_vec,
2424	reg_info: df->def_regs,
2425	ref_info: &df->def_info, is_notes: false);
2426	}
2427	if (flags & copy_uses)
2428	{
2429	gcc_checking_assert (!insn_rec->uses);
2430	insn_rec->uses
2431	= df_install_refs (bb, old_vec: &collection_rec->use_vec,
2432	reg_info: df->use_regs,
2433	ref_info: &df->use_info, is_notes: false);
2434	}
2435	if (flags & copy_eq_uses)
2436	{
2437	gcc_checking_assert (!insn_rec->eq_uses);
2438	insn_rec->eq_uses
2439	= df_install_refs (bb, old_vec: &collection_rec->eq_use_vec,
2440	reg_info: df->eq_use_regs,
2441	ref_info: &df->use_info, is_notes: true);
2442	}
2443	if (flags & copy_mw)
2444	{
2445	gcc_checking_assert (!insn_rec->mw_hardregs);
2446	insn_rec->mw_hardregs
2447	= df_install_mws (old_vec: &collection_rec->mw_vec);
2448	}
2449	}
2450	else
2451	{
2452	struct df_scan_bb_info *bb_info = df_scan_get_bb_info (index: bb->index);
2453
2454	gcc_checking_assert (!bb_info->artificial_defs);
2455	bb_info->artificial_defs
2456	= df_install_refs (bb, old_vec: &collection_rec->def_vec,
2457	reg_info: df->def_regs,
2458	ref_info: &df->def_info, is_notes: false);
2459	gcc_checking_assert (!bb_info->artificial_uses);
2460	bb_info->artificial_uses
2461	= df_install_refs (bb, old_vec: &collection_rec->use_vec,
2462	reg_info: df->use_regs,
2463	ref_info: &df->use_info, is_notes: false);
2464	}
2465	}
2466
2467
2468	/* Allocate a ref and initialize its fields. */
2469
2470	static df_ref
2471	df_ref_create_structure (enum df_ref_class cl,
2472	class df_collection_rec *collection_rec,
2473	rtx reg, rtx *loc,
2474	basic_block bb, struct df_insn_info *info,
2475	enum df_ref_type ref_type,
2476	int ref_flags)
2477	{
2478	const unsigned int regno
2479	= REGNO (GET_CODE (reg) == SUBREG ? SUBREG_REG (reg) : reg);
2480	struct df_scan_problem_data *problem_data
2481	= (struct df_scan_problem_data *) df_scan->problem_data;
2482	df_ref this_ref;
2483
2484	switch (cl)
2485	{
2486	case DF_REF_BASE:
2487	this_ref = (df_ref) (problem_data->ref_base_pool->allocate ());
2488	gcc_checking_assert (loc == NULL);
2489	break;
2490
2491	case DF_REF_ARTIFICIAL:
2492	this_ref = (df_ref) (problem_data->ref_artificial_pool->allocate ());
2493	this_ref->artificial_ref.bb = bb;
2494	gcc_checking_assert (loc == NULL);
2495	break;
2496
2497	case DF_REF_REGULAR:
2498	this_ref = (df_ref) (problem_data->ref_regular_pool->allocate ());
2499	this_ref->regular_ref.loc = loc;
2500	gcc_checking_assert (loc);
2501	break;
2502
2503	default:
2504	gcc_unreachable ();
2505	}
2506
2507	DF_REF_CLASS (this_ref) = cl;
2508	DF_REF_ID (this_ref) = -1;
2509	DF_REF_REG (this_ref) = reg;
2510	DF_REF_REGNO (this_ref) = regno;
2511	DF_REF_TYPE (this_ref) = ref_type;
2512	DF_REF_INSN_INFO (this_ref) = info;
2513	DF_REF_CHAIN (this_ref) = NULL;
2514	DF_REF_FLAGS (this_ref) = ref_flags;
2515	DF_REF_NEXT_REG (this_ref) = NULL;
2516	DF_REF_PREV_REG (this_ref) = NULL;
2517	DF_REF_ORDER (this_ref) = df->ref_order++;
2518
2519	/* We need to clear the DF_HARD_REG_LIVE bit because fwprop, and in the
2520	future possibly other optimizations, sometimes create new refs using
2521	live refs as the model. */
2522	DF_REF_FLAGS_CLEAR (this_ref, DF_HARD_REG_LIVE);
2523
2524	/* Now see if this ref really needs to have the bit set. */
2525	if (regno < FIRST_PSEUDO_REGISTER
2526	&& cl != DF_REF_ARTIFICIAL
2527	&& !DEBUG_INSN_P (info->insn))
2528	{
2529	if (ref_type == DF_REF_REG_DEF)
2530	{
2531	if (!DF_REF_FLAGS_IS_SET (this_ref, DF_REF_MAY_CLOBBER))
2532	DF_REF_FLAGS_SET (this_ref, DF_HARD_REG_LIVE);
2533	}
2534	else if (!(TEST_HARD_REG_BIT (set: elim_reg_set, bit: regno)
2535	&& (regno == FRAME_POINTER_REGNUM
2536	|| regno == ARG_POINTER_REGNUM)))
2537	DF_REF_FLAGS_SET (this_ref, DF_HARD_REG_LIVE);
2538	}
2539
2540	if (collection_rec)
2541	{
2542	if (DF_REF_REG_DEF_P (this_ref))
2543	collection_rec->def_vec.safe_push (obj: this_ref);
2544	else if (DF_REF_FLAGS (this_ref) & DF_REF_IN_NOTE)
2545	collection_rec->eq_use_vec.safe_push (obj: this_ref);
2546	else
2547	collection_rec->use_vec.safe_push (obj: this_ref);
2548	}
2549	else
2550	df_install_ref_incremental (ref: this_ref);
2551
2552	return this_ref;
2553	}
2554
2555
2556	/* Create new references of type DF_REF_TYPE for each part of register REG
2557	at address LOC within INSN of BB. */
2558
2559
2560	static void
2561	df_ref_record (enum df_ref_class cl,
2562	class df_collection_rec *collection_rec,
2563	rtx reg, rtx *loc,
2564	basic_block bb, struct df_insn_info *insn_info,
2565	enum df_ref_type ref_type,
2566	int ref_flags)
2567	{
2568	unsigned int regno;
2569
2570	gcc_checking_assert (REG_P (reg) || GET_CODE (reg) == SUBREG);
2571
2572	regno = REGNO (GET_CODE (reg) == SUBREG ? SUBREG_REG (reg) : reg);
2573	if (regno < FIRST_PSEUDO_REGISTER)
2574	{
2575	struct df_mw_hardreg *hardreg = NULL;
2576	struct df_scan_problem_data *problem_data
2577	= (struct df_scan_problem_data *) df_scan->problem_data;
2578	unsigned int i;
2579	unsigned int endregno;
2580	df_ref ref;
2581
2582	if (GET_CODE (reg) == SUBREG)
2583	{
2584	int off = subreg_regno_offset (regno, GET_MODE (SUBREG_REG (reg)),
2585	SUBREG_BYTE (reg), GET_MODE (reg));
2586	unsigned int nregno = regno + off;
2587	endregno = nregno + subreg_nregs (reg);
2588	if (off < 0 && regno < (unsigned) -off)
2589	/* Deal with paradoxical SUBREGs on big endian where
2590	in debug insns the hard reg number might be smaller
2591	than -off, such as (subreg:DI (reg:SI 0 [+4 ]) 0));
2592	RA decisions shouldn't be affected by debug insns
2593	and so RA can decide to put pseudo into a hard reg
2594	with small REGNO, even when it is referenced in
2595	a paradoxical SUBREG in a debug insn. */
2596	regno = 0;
2597	else
2598	regno = nregno;
2599	}
2600	else
2601	endregno = END_REGNO (x: reg);
2602
2603	/* If this is a multiword hardreg, we create some extra
2604	datastructures that will enable us to easily build REG_DEAD
2605	and REG_UNUSED notes. */
2606	if (collection_rec
2607	&& (endregno != regno + 1) && insn_info)
2608	{
2609	/* Sets to a subreg of a multiword register are partial.
2610	Sets to a non-subreg of a multiword register are not. */
2611	if (GET_CODE (reg) == SUBREG)
2612	ref_flags |= DF_REF_PARTIAL;
2613	ref_flags |= DF_REF_MW_HARDREG;
2614
2615	gcc_assert (regno < endregno);
2616
2617	hardreg = problem_data->mw_reg_pool->allocate ();
2618	hardreg->type = ref_type;
2619	hardreg->flags = ref_flags;
2620	hardreg->mw_reg = reg;
2621	hardreg->start_regno = regno;
2622	hardreg->end_regno = endregno - 1;
2623	hardreg->mw_order = df->ref_order++;
2624	collection_rec->mw_vec.safe_push (obj: hardreg);
2625	}
2626
2627	for (i = regno; i < endregno; i++)
2628	{
2629	ref = df_ref_create_structure (cl, collection_rec, reg: regno_reg_rtx[i], loc,
2630	bb, info: insn_info, ref_type, ref_flags);
2631
2632	gcc_assert (ORIGINAL_REGNO (DF_REF_REG (ref)) == i);
2633	}
2634	}
2635	else
2636	{
2637	df_ref_create_structure (cl, collection_rec, reg, loc, bb, info: insn_info,
2638	ref_type, ref_flags);
2639	}
2640	}
2641
2642
2643	/* Process all the registers defined in the rtx pointed by LOC.
2644	Autoincrement/decrement definitions will be picked up by df_uses_record.
2645	Any change here has to be matched in df_find_hard_reg_defs_1. */
2646
2647	static void
2648	df_def_record_1 (class df_collection_rec *collection_rec,
2649	rtx *loc, basic_block bb, struct df_insn_info *insn_info,
2650	int flags)
2651	{
2652	rtx dst = *loc;
2653
2654	/* It is legal to have a set destination be a parallel. */
2655	if (GET_CODE (dst) == PARALLEL)
2656	{
2657	int i;
2658	for (i = XVECLEN (dst, 0) - 1; i >= 0; i--)
2659	{
2660	rtx temp = XVECEXP (dst, 0, i);
2661	gcc_assert (GET_CODE (temp) == EXPR_LIST);
2662	df_def_record_1 (collection_rec, loc: &XEXP (temp, 0),
2663	bb, insn_info, flags);
2664	}
2665	return;
2666	}
2667
2668	if (GET_CODE (dst) == STRICT_LOW_PART)
2669	{
2670	flags |= DF_REF_READ_WRITE | DF_REF_PARTIAL | DF_REF_STRICT_LOW_PART;
2671
2672	loc = &XEXP (dst, 0);
2673	dst = *loc;
2674	}
2675
2676	if (GET_CODE (dst) == ZERO_EXTRACT)
2677	{
2678	flags |= DF_REF_READ_WRITE | DF_REF_PARTIAL | DF_REF_ZERO_EXTRACT;
2679
2680	loc = &XEXP (dst, 0);
2681	dst = *loc;
2682	}
2683
2684	/* At this point if we do not have a reg or a subreg, just return. */
2685	if (REG_P (dst))
2686	{
2687	df_ref_record (cl: DF_REF_REGULAR, collection_rec,
2688	reg: dst, loc, bb, insn_info, ref_type: DF_REF_REG_DEF, ref_flags: flags);
2689
2690	/* We want to keep sp alive everywhere - by making all
2691	writes to sp also use of sp. */
2692	if (REGNO (dst) == STACK_POINTER_REGNUM)
2693	df_ref_record (cl: DF_REF_BASE, collection_rec,
2694	reg: dst, NULL, bb, insn_info, ref_type: DF_REF_REG_USE, ref_flags: flags);
2695	}
2696	else if (GET_CODE (dst) == SUBREG && REG_P (SUBREG_REG (dst)))
2697	{
2698	if (read_modify_subreg_p (dst))
2699	flags |= DF_REF_READ_WRITE | DF_REF_PARTIAL;
2700
2701	flags |= DF_REF_SUBREG;
2702
2703	df_ref_record (cl: DF_REF_REGULAR, collection_rec,
2704	reg: dst, loc, bb, insn_info, ref_type: DF_REF_REG_DEF, ref_flags: flags);
2705	}
2706	}
2707
2708
2709	/* Process all the registers defined in the pattern rtx, X. Any change
2710	here has to be matched in df_find_hard_reg_defs. */
2711
2712	static void
2713	df_defs_record (class df_collection_rec *collection_rec,
2714	rtx x, basic_block bb, struct df_insn_info *insn_info,
2715	int flags)
2716	{
2717	RTX_CODE code = GET_CODE (x);
2718	int i;
2719
2720	switch (code)
2721	{
2722	case SET:
2723	df_def_record_1 (collection_rec, loc: &SET_DEST (x), bb, insn_info, flags);
2724	break;
2725
2726	case CLOBBER:
2727	flags |= DF_REF_MUST_CLOBBER;
2728	df_def_record_1 (collection_rec, loc: &XEXP (x, 0), bb, insn_info, flags);
2729	break;
2730
2731	case COND_EXEC:
2732	df_defs_record (collection_rec, COND_EXEC_CODE (x),
2733	bb, insn_info, flags: DF_REF_CONDITIONAL);
2734	break;
2735
2736	case PARALLEL:
2737	for (i = 0; i < XVECLEN (x, 0); i++)
2738	df_defs_record (collection_rec, XVECEXP (x, 0, i),
2739	bb, insn_info, flags);
2740	break;
2741	default:
2742	/* No DEFs to record in other cases */
2743	break;
2744	}
2745	}
2746
2747	/* Set bits in *DEFS for hard registers found in the rtx DST, which is the
2748	destination of a set or clobber. This has to match the logic in
2749	df_defs_record_1. */
2750
2751	static void
2752	df_find_hard_reg_defs_1 (rtx dst, HARD_REG_SET *defs)
2753	{
2754	/* It is legal to have a set destination be a parallel. */
2755	if (GET_CODE (dst) == PARALLEL)
2756	{
2757	int i;
2758	for (i = XVECLEN (dst, 0) - 1; i >= 0; i--)
2759	{
2760	rtx temp = XVECEXP (dst, 0, i);
2761	gcc_assert (GET_CODE (temp) == EXPR_LIST);
2762	df_find_hard_reg_defs_1 (XEXP (temp, 0), defs);
2763	}
2764	return;
2765	}
2766
2767	if (GET_CODE (dst) == STRICT_LOW_PART)
2768	dst = XEXP (dst, 0);
2769
2770	if (GET_CODE (dst) == ZERO_EXTRACT)
2771	dst = XEXP (dst, 0);
2772
2773	/* At this point if we do not have a reg or a subreg, just return. */
2774	if (REG_P (dst) && HARD_REGISTER_P (dst))
2775	SET_HARD_REG_BIT (set&: *defs, REGNO (dst));
2776	else if (GET_CODE (dst) == SUBREG
2777	&& REG_P (SUBREG_REG (dst)) && HARD_REGISTER_P (dst))
2778	SET_HARD_REG_BIT (set&: *defs, REGNO (SUBREG_REG (dst)));
2779	}
2780
2781	/* Set bits in *DEFS for hard registers defined in the pattern X. This
2782	has to match the logic in df_defs_record. */
2783
2784	static void
2785	df_find_hard_reg_defs (rtx x, HARD_REG_SET *defs)
2786	{
2787	RTX_CODE code = GET_CODE (x);
2788	int i;
2789
2790	switch (code)
2791	{
2792	case SET:
2793	df_find_hard_reg_defs_1 (SET_DEST (x), defs);
2794	break;
2795
2796	case CLOBBER:
2797	df_find_hard_reg_defs_1 (XEXP (x, 0), defs);
2798	break;
2799
2800	case COND_EXEC:
2801	df_find_hard_reg_defs (COND_EXEC_CODE (x), defs);
2802	break;
2803
2804	case PARALLEL:
2805	for (i = 0; i < XVECLEN (x, 0); i++)
2806	df_find_hard_reg_defs (XVECEXP (x, 0, i), defs);
2807	break;
2808	default:
2809	/* No DEFs to record in other cases */
2810	break;
2811	}
2812	}
2813
2814
2815	/* Process all the registers used in the rtx at address LOC. */
2816
2817	static void
2818	df_uses_record (class df_collection_rec *collection_rec,
2819	rtx *loc, enum df_ref_type ref_type,
2820	basic_block bb, struct df_insn_info *insn_info,
2821	int flags)
2822	{
2823	RTX_CODE code;
2824	rtx x;
2825
2826	retry:
2827	x = *loc;
2828	if (!x)
2829	return;
2830	code = GET_CODE (x);
2831	switch (code)
2832	{
2833	case LABEL_REF:
2834	case SYMBOL_REF:
2835	case CONST:
2836	CASE_CONST_ANY:
2837	case PC:
2838	case ADDR_VEC:
2839	case ADDR_DIFF_VEC:
2840	return;
2841
2842	case CLOBBER:
2843	/* If we are clobbering a MEM, mark any registers inside the address
2844	as being used. */
2845	if (MEM_P (XEXP (x, 0)))
2846	df_uses_record (collection_rec,
2847	loc: &XEXP (XEXP (x, 0), 0),
2848	ref_type: DF_REF_REG_MEM_STORE,
2849	bb, insn_info,
2850	flags);
2851
2852	/* If we're clobbering a REG then we have a def so ignore. */
2853	return;
2854
2855	case MEM:
2856	df_uses_record (collection_rec,
2857	loc: &XEXP (x, 0), ref_type: DF_REF_REG_MEM_LOAD,
2858	bb, insn_info, flags: flags & DF_REF_IN_NOTE);
2859	return;
2860
2861	case SUBREG:
2862	/* While we're here, optimize this case. */
2863	flags |= DF_REF_PARTIAL;
2864	/* In case the SUBREG is not of a REG, do not optimize. */
2865	if (!REG_P (SUBREG_REG (x)))
2866	{
2867	loc = &SUBREG_REG (x);
2868	df_uses_record (collection_rec, loc, ref_type, bb, insn_info, flags);
2869	return;
2870	}
2871	/* Fall through */
2872
2873	case REG:
2874	df_ref_record (cl: DF_REF_REGULAR, collection_rec,
2875	reg: x, loc, bb, insn_info,
2876	ref_type, ref_flags: flags);
2877	return;
2878
2879	case SIGN_EXTRACT:
2880	case ZERO_EXTRACT:
2881	{
2882	df_uses_record (collection_rec,
2883	loc: &XEXP (x, 1), ref_type, bb, insn_info, flags);
2884	df_uses_record (collection_rec,
2885	loc: &XEXP (x, 2), ref_type, bb, insn_info, flags);
2886
2887	/* If the parameters to the zero or sign extract are
2888	constants, strip them off and recurse, otherwise there is
2889	no information that we can gain from this operation. */
2890	if (code == ZERO_EXTRACT)
2891	flags |= DF_REF_ZERO_EXTRACT;
2892	else
2893	flags |= DF_REF_SIGN_EXTRACT;
2894
2895	df_uses_record (collection_rec,
2896	loc: &XEXP (x, 0), ref_type, bb, insn_info, flags);
2897	return;
2898	}
2899	break;
2900
2901	case SET:
2902	{
2903	rtx dst = SET_DEST (x);
2904	gcc_assert (!(flags & DF_REF_IN_NOTE));
2905	df_uses_record (collection_rec,
2906	loc: &SET_SRC (x), ref_type: DF_REF_REG_USE, bb, insn_info, flags);
2907
2908	switch (GET_CODE (dst))
2909	{
2910	case SUBREG:
2911	if (read_modify_subreg_p (dst))
2912	{
2913	df_uses_record (collection_rec, loc: &SUBREG_REG (dst),
2914	ref_type: DF_REF_REG_USE, bb, insn_info,
2915	flags: flags | DF_REF_READ_WRITE | DF_REF_SUBREG);
2916	break;
2917	}
2918	/* Fall through. */
2919	case REG:
2920	case PARALLEL:
2921	case SCRATCH:
2922	case PC:
2923	break;
2924	case MEM:
2925	df_uses_record (collection_rec, loc: &XEXP (dst, 0),
2926	ref_type: DF_REF_REG_MEM_STORE, bb, insn_info, flags);
2927	break;
2928	case STRICT_LOW_PART:
2929	{
2930	rtx *temp = &XEXP (dst, 0);
2931	/* A strict_low_part uses the whole REG and not just the
2932	SUBREG. */
2933	dst = XEXP (dst, 0);
2934	df_uses_record (collection_rec,
2935	loc: (GET_CODE (dst) == SUBREG) ? &SUBREG_REG (dst) : temp,
2936	ref_type: DF_REF_REG_USE, bb, insn_info,
2937	flags: DF_REF_READ_WRITE | DF_REF_STRICT_LOW_PART);
2938	}
2939	break;
2940	case ZERO_EXTRACT:
2941	{
2942	df_uses_record (collection_rec, loc: &XEXP (dst, 1),
2943	ref_type: DF_REF_REG_USE, bb, insn_info, flags);
2944	df_uses_record (collection_rec, loc: &XEXP (dst, 2),
2945	ref_type: DF_REF_REG_USE, bb, insn_info, flags);
2946	if (GET_CODE (XEXP (dst,0)) == MEM)
2947	df_uses_record (collection_rec, loc: &XEXP (dst, 0),
2948	ref_type: DF_REF_REG_USE, bb, insn_info,
2949	flags);
2950	else
2951	df_uses_record (collection_rec, loc: &XEXP (dst, 0),
2952	ref_type: DF_REF_REG_USE, bb, insn_info,
2953	flags: DF_REF_READ_WRITE | DF_REF_ZERO_EXTRACT);
2954	}
2955	break;
2956
2957	default:
2958	gcc_unreachable ();
2959	}
2960	return;
2961	}
2962
2963	case RETURN:
2964	case SIMPLE_RETURN:
2965	break;
2966
2967	case ASM_OPERANDS:
2968	case UNSPEC_VOLATILE:
2969	case TRAP_IF:
2970	case ASM_INPUT:
2971	{
2972	/* Traditional and volatile asm instructions must be
2973	considered to use and clobber all hard registers, all
2974	pseudo-registers and all of memory. So must TRAP_IF and
2975	UNSPEC_VOLATILE operations.
2976
2977	Consider for instance a volatile asm that changes the fpu
2978	rounding mode. An insn should not be moved across this
2979	even if it only uses pseudo-regs because it might give an
2980	incorrectly rounded result.
2981
2982	However, flow.c's liveness computation did *not* do this,
2983	giving the reasoning as " ?!? Unfortunately, marking all
2984	hard registers as live causes massive problems for the
2985	register allocator and marking all pseudos as live creates
2986	mountains of uninitialized variable warnings."
2987
2988	In order to maintain the status quo with regard to liveness
2989	and uses, we do what flow.c did and just mark any regs we
2990	can find in ASM_OPERANDS as used. In global asm insns are
2991	scanned and regs_asm_clobbered is filled out.
2992
2993	For all ASM_OPERANDS, we must traverse the vector of input
2994	operands. We cannot just fall through here since then we
2995	would be confused by the ASM_INPUT rtx inside ASM_OPERANDS,
2996	which do not indicate traditional asms unlike their normal
2997	usage. */
2998	if (code == ASM_OPERANDS)
2999	{
3000	int j;
3001
3002	for (j = 0; j < ASM_OPERANDS_INPUT_LENGTH (x); j++)
3003	df_uses_record (collection_rec, loc: &ASM_OPERANDS_INPUT (x, j),
3004	ref_type: DF_REF_REG_USE, bb, insn_info, flags);
3005	return;
3006	}
3007	break;
3008	}
3009
3010	case VAR_LOCATION:
3011	df_uses_record (collection_rec,
3012	loc: &PAT_VAR_LOCATION_LOC (x),
3013	ref_type: DF_REF_REG_USE, bb, insn_info, flags);
3014	return;
3015
3016	case PRE_DEC:
3017	case POST_DEC:
3018	case PRE_INC:
3019	case POST_INC:
3020	case PRE_MODIFY:
3021	case POST_MODIFY:
3022	gcc_assert (!DEBUG_INSN_P (insn_info->insn));
3023	/* Catch the def of the register being modified. */
3024	df_ref_record (cl: DF_REF_REGULAR, collection_rec, XEXP (x, 0), loc: &XEXP (x, 0),
3025	bb, insn_info,
3026	ref_type: DF_REF_REG_DEF,
3027	ref_flags: flags | DF_REF_READ_WRITE | DF_REF_PRE_POST_MODIFY);
3028
3029	/* ... Fall through to handle uses ... */
3030
3031	default:
3032	break;
3033	}
3034
3035	/* Recursively scan the operands of this expression. */
3036	{
3037	const char *fmt = GET_RTX_FORMAT (code);
3038	int i;
3039
3040	for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
3041	{
3042	if (fmt[i] == 'e')
3043	{
3044	/* Tail recursive case: save a function call level. */
3045	if (i == 0)
3046	{
3047	loc = &XEXP (x, 0);
3048	goto retry;
3049	}
3050	df_uses_record (collection_rec, loc: &XEXP (x, i), ref_type,
3051	bb, insn_info, flags);
3052	}
3053	else if (fmt[i] == 'E')
3054	{
3055	int j;
3056	for (j = 0; j < XVECLEN (x, i); j++)
3057	df_uses_record (collection_rec,
3058	loc: &XVECEXP (x, i, j), ref_type,
3059	bb, insn_info, flags);
3060	}
3061	}
3062	}
3063
3064	return;
3065	}
3066
3067
3068	/* For all DF_REF_CONDITIONAL defs, add a corresponding uses. */
3069
3070	static void
3071	df_get_conditional_uses (class df_collection_rec *collection_rec)
3072	{
3073	unsigned int ix;
3074	df_ref ref;
3075
3076	FOR_EACH_VEC_ELT (collection_rec->def_vec, ix, ref)
3077	{
3078	if (DF_REF_FLAGS_IS_SET (ref, DF_REF_CONDITIONAL))
3079	{
3080	df_ref use;
3081
3082	use = df_ref_create_structure (DF_REF_CLASS (ref), collection_rec, DF_REF_REG (ref),
3083	DF_REF_LOC (ref), DF_REF_BB (ref),
3084	DF_REF_INSN_INFO (ref), ref_type: DF_REF_REG_USE,
3085	DF_REF_FLAGS (ref) & ~DF_REF_CONDITIONAL);
3086	DF_REF_REGNO (use) = DF_REF_REGNO (ref);
3087	}
3088	}
3089	}
3090
3091
3092	/* Get call's extra defs and uses (track caller-saved registers). */
3093
3094	static void
3095	df_get_call_refs (class df_collection_rec *collection_rec,
3096	basic_block bb,
3097	struct df_insn_info *insn_info,
3098	int flags)
3099	{
3100	rtx note;
3101	bool is_sibling_call;
3102	unsigned int i;
3103	HARD_REG_SET defs_generated;
3104
3105	CLEAR_HARD_REG_SET (set&: defs_generated);
3106	df_find_hard_reg_defs (x: PATTERN (insn: insn_info->insn), defs: &defs_generated);
3107	is_sibling_call = SIBLING_CALL_P (insn_info->insn);
3108	function_abi callee_abi = insn_callee_abi (insn_info->insn);
3109
3110	for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3111	{
3112	if (i == STACK_POINTER_REGNUM
3113	&& !FAKE_CALL_P (insn_info->insn))
3114	/* The stack ptr is used (honorarily) by a CALL insn. */
3115	df_ref_record (cl: DF_REF_BASE, collection_rec, reg: regno_reg_rtx[i],
3116	NULL, bb, insn_info, ref_type: DF_REF_REG_USE,
3117	ref_flags: DF_REF_CALL_STACK_USAGE | flags);
3118	else if (global_regs[i])
3119	{
3120	/* Calls to const functions cannot access any global registers and
3121	calls to pure functions cannot set them. All other calls may
3122	reference any of the global registers, so they are recorded as
3123	used. */
3124	if (!RTL_CONST_CALL_P (insn_info->insn))
3125	{
3126	df_ref_record (cl: DF_REF_BASE, collection_rec, reg: regno_reg_rtx[i],
3127	NULL, bb, insn_info, ref_type: DF_REF_REG_USE, ref_flags: flags);
3128	if (!RTL_PURE_CALL_P (insn_info->insn))
3129	df_ref_record (cl: DF_REF_BASE, collection_rec, reg: regno_reg_rtx[i],
3130	NULL, bb, insn_info, ref_type: DF_REF_REG_DEF, ref_flags: flags);
3131	}
3132	}
3133	else if (callee_abi.clobbers_full_reg_p (regno: i)
3134	/* no clobbers for regs that are the result of the call */
3135	&& !TEST_HARD_REG_BIT (set: defs_generated, bit: i)
3136	&& (!is_sibling_call
3137	|| !bitmap_bit_p (df->exit_block_uses, i)
3138	|| refers_to_regno_p (regnum: i, crtl->return_rtx)))
3139	df_ref_record (cl: DF_REF_BASE, collection_rec, reg: regno_reg_rtx[i],
3140	NULL, bb, insn_info, ref_type: DF_REF_REG_DEF,
3141	ref_flags: DF_REF_MAY_CLOBBER | flags);
3142	}
3143
3144	/* Record the registers used to pass arguments, and explicitly
3145	noted as clobbered. */
3146	for (note = CALL_INSN_FUNCTION_USAGE (insn_info->insn); note;
3147	note = XEXP (note, 1))
3148	{
3149	if (GET_CODE (XEXP (note, 0)) == USE)
3150	df_uses_record (collection_rec, loc: &XEXP (XEXP (note, 0), 0),
3151	ref_type: DF_REF_REG_USE, bb, insn_info, flags);
3152	else if (GET_CODE (XEXP (note, 0)) == CLOBBER)
3153	{
3154	if (REG_P (XEXP (XEXP (note, 0), 0)))
3155	{
3156	unsigned int regno = REGNO (XEXP (XEXP (note, 0), 0));
3157	if (!TEST_HARD_REG_BIT (set: defs_generated, bit: regno))
3158	df_defs_record (collection_rec, XEXP (note, 0), bb,
3159	insn_info, flags);
3160	}
3161	else
3162	df_uses_record (collection_rec, loc: &XEXP (note, 0),
3163	ref_type: DF_REF_REG_USE, bb, insn_info, flags);
3164	}
3165	}
3166
3167	return;
3168	}
3169
3170	/* Collect all refs in the INSN. This function is free of any
3171	side-effect - it will create and return a lists of df_ref's in the
3172	COLLECTION_REC without putting those refs into existing ref chains
3173	and reg chains. */
3174
3175	static void
3176	df_insn_refs_collect (class df_collection_rec *collection_rec,
3177	basic_block bb, struct df_insn_info *insn_info)
3178	{
3179	rtx note;
3180	bool is_cond_exec = (GET_CODE (PATTERN (insn_info->insn)) == COND_EXEC);
3181
3182	/* Clear out the collection record. */
3183	collection_rec->def_vec.truncate (size: 0);
3184	collection_rec->use_vec.truncate (size: 0);
3185	collection_rec->eq_use_vec.truncate (size: 0);
3186	collection_rec->mw_vec.truncate (size: 0);
3187
3188	/* Process REG_EQUIV/REG_EQUAL notes. */
3189	for (note = REG_NOTES (insn_info->insn); note;
3190	note = XEXP (note, 1))
3191	{
3192	switch (REG_NOTE_KIND (note))
3193	{
3194	case REG_EQUIV:
3195	case REG_EQUAL:
3196	df_uses_record (collection_rec,
3197	loc: &XEXP (note, 0), ref_type: DF_REF_REG_USE,
3198	bb, insn_info, flags: DF_REF_IN_NOTE);
3199	break;
3200	case REG_NON_LOCAL_GOTO:
3201	/* The frame ptr is used by a non-local goto. */
3202	df_ref_record (cl: DF_REF_BASE, collection_rec,
3203	reg: regno_reg_rtx[FRAME_POINTER_REGNUM],
3204	NULL, bb, insn_info,
3205	ref_type: DF_REF_REG_USE, ref_flags: 0);
3206	if (!HARD_FRAME_POINTER_IS_FRAME_POINTER)
3207	df_ref_record (cl: DF_REF_BASE, collection_rec,
3208	reg: regno_reg_rtx[HARD_FRAME_POINTER_REGNUM],
3209	NULL, bb, insn_info,
3210	ref_type: DF_REF_REG_USE, ref_flags: 0);
3211	break;
3212	default:
3213	break;
3214	}
3215	}
3216
3217	int flags = (is_cond_exec) ? DF_REF_CONDITIONAL : 0;
3218	/* For CALL_INSNs, first record DF_REF_BASE register defs, as well as
3219	uses from CALL_INSN_FUNCTION_USAGE. */
3220	if (CALL_P (insn_info->insn))
3221	df_get_call_refs (collection_rec, bb, insn_info, flags);
3222
3223	/* Record other defs. These should be mostly for DF_REF_REGULAR, so
3224	that a qsort on the defs is unnecessary in most cases. */
3225	df_defs_record (collection_rec,
3226	x: PATTERN (insn: insn_info->insn), bb, insn_info, flags: 0);
3227
3228	/* Record the register uses. */
3229	df_uses_record (collection_rec,
3230	loc: &PATTERN (insn: insn_info->insn), ref_type: DF_REF_REG_USE, bb, insn_info, flags: 0);
3231
3232	/* DF_REF_CONDITIONAL needs corresponding USES. */
3233	if (is_cond_exec)
3234	df_get_conditional_uses (collection_rec);
3235
3236	df_canonize_collection_rec (collection_rec);
3237	}
3238
3239	/* Recompute the luids for the insns in BB. */
3240
3241	void
3242	df_recompute_luids (basic_block bb)
3243	{
3244	rtx_insn *insn;
3245	int luid = 0;
3246
3247	df_grow_insn_info ();
3248
3249	/* Scan the block an insn at a time from beginning to end. */
3250	FOR_BB_INSNS (bb, insn)
3251	{
3252	struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
3253	/* Inserting labels does not always trigger the incremental
3254	rescanning. */
3255	if (!insn_info)
3256	{
3257	gcc_assert (!INSN_P (insn));
3258	insn_info = df_insn_create_insn_record (insn);
3259	}
3260
3261	DF_INSN_INFO_LUID (insn_info) = luid;
3262	if (INSN_P (insn))
3263	luid++;
3264	}
3265	}
3266
3267
3268	/* Collect all artificial refs at the block level for BB and add them
3269	to COLLECTION_REC. */
3270
3271	static void
3272	df_bb_refs_collect (class df_collection_rec *collection_rec, basic_block bb)
3273	{
3274	collection_rec->def_vec.truncate (size: 0);
3275	collection_rec->use_vec.truncate (size: 0);
3276	collection_rec->eq_use_vec.truncate (size: 0);
3277	collection_rec->mw_vec.truncate (size: 0);
3278
3279	if (bb->index == ENTRY_BLOCK)
3280	{
3281	df_entry_block_defs_collect (collection_rec, df->entry_block_defs);
3282	return;
3283	}
3284	else if (bb->index == EXIT_BLOCK)
3285	{
3286	df_exit_block_uses_collect (collection_rec, df->exit_block_uses);
3287	return;
3288	}
3289
3290	if (bb_has_eh_pred (bb))
3291	{
3292	unsigned int i;
3293	/* Mark the registers that will contain data for the handler. */
3294	for (i = 0; ; ++i)
3295	{
3296	unsigned regno = EH_RETURN_DATA_REGNO (i);
3297	if (regno == INVALID_REGNUM)
3298	break;
3299	df_ref_record (cl: DF_REF_ARTIFICIAL, collection_rec, reg: regno_reg_rtx[regno], NULL,
3300	bb, NULL, ref_type: DF_REF_REG_DEF, ref_flags: DF_REF_AT_TOP);
3301	}
3302	}
3303
3304	/* Add the hard_frame_pointer if this block is the target of a
3305	non-local goto. */
3306	if (bb->flags & BB_NON_LOCAL_GOTO_TARGET)
3307	df_ref_record (cl: DF_REF_ARTIFICIAL, collection_rec, hard_frame_pointer_rtx, NULL,
3308	bb, NULL, ref_type: DF_REF_REG_DEF, ref_flags: DF_REF_AT_TOP);
3309
3310	/* Add the artificial uses. */
3311	if (bb->index >= NUM_FIXED_BLOCKS)
3312	{
3313	bitmap_iterator bi;
3314	unsigned int regno;
3315	bitmap au = bb_has_eh_pred (bb)
3316	? &df->eh_block_artificial_uses
3317	: &df->regular_block_artificial_uses;
3318
3319	EXECUTE_IF_SET_IN_BITMAP (au, 0, regno, bi)
3320	{
3321	df_ref_record (cl: DF_REF_ARTIFICIAL, collection_rec, reg: regno_reg_rtx[regno], NULL,
3322	bb, NULL, ref_type: DF_REF_REG_USE, ref_flags: 0);
3323	}
3324	}
3325
3326	df_canonize_collection_rec (collection_rec);
3327	}
3328
3329
3330	/* Record all the refs within the basic block BB_INDEX and scan the instructions if SCAN_INSNS. */
3331
3332	void
3333	df_bb_refs_record (int bb_index, bool scan_insns)
3334	{
3335	basic_block bb = BASIC_BLOCK_FOR_FN (cfun, bb_index);
3336	rtx_insn *insn;
3337	int luid = 0;
3338
3339	if (!df)
3340	return;
3341
3342	df_collection_rec collection_rec;
3343	df_grow_bb_info (df_scan);
3344	if (scan_insns)
3345	/* Scan the block an insn at a time from beginning to end. */
3346	FOR_BB_INSNS (bb, insn)
3347	{
3348	struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
3349	gcc_assert (!insn_info);
3350
3351	insn_info = df_insn_create_insn_record (insn);
3352	if (INSN_P (insn))
3353	{
3354	/* Record refs within INSN. */
3355	DF_INSN_INFO_LUID (insn_info) = luid++;
3356	df_insn_refs_collect (collection_rec: &collection_rec, bb, DF_INSN_INFO_GET (insn));
3357	df_refs_add_to_chains (collection_rec: &collection_rec, bb, insn, flags: copy_all);
3358	}
3359	DF_INSN_INFO_LUID (insn_info) = luid;
3360	}
3361
3362	/* Other block level artificial refs */
3363	df_bb_refs_collect (collection_rec: &collection_rec, bb);
3364	df_refs_add_to_chains (collection_rec: &collection_rec, bb, NULL, flags: copy_all);
3365
3366	/* Now that the block has been processed, set the block as dirty so
3367	LR and LIVE will get it processed. */
3368	df_set_bb_dirty (bb);
3369	}
3370
3371
3372	/* Get the artificial use set for a regular (i.e. non-exit/non-entry)
3373	block. */
3374
3375	static void
3376	df_get_regular_block_artificial_uses (bitmap regular_block_artificial_uses)
3377	{
3378	#ifdef EH_USES
3379	unsigned int i;
3380	#endif
3381
3382	bitmap_clear (regular_block_artificial_uses);
3383
3384	if (reload_completed)
3385	{
3386	if (frame_pointer_needed)
3387	bitmap_set_bit (regular_block_artificial_uses, HARD_FRAME_POINTER_REGNUM);
3388	}
3389	else
3390	/* Before reload, there are a few registers that must be forced
3391	live everywhere -- which might not already be the case for
3392	blocks within infinite loops. */
3393	{
3394	unsigned int picreg = PIC_OFFSET_TABLE_REGNUM;
3395
3396	/* Any reference to any pseudo before reload is a potential
3397	reference of the frame pointer. */
3398	bitmap_set_bit (regular_block_artificial_uses, FRAME_POINTER_REGNUM);
3399
3400	if (!HARD_FRAME_POINTER_IS_FRAME_POINTER)
3401	bitmap_set_bit (regular_block_artificial_uses,
3402	HARD_FRAME_POINTER_REGNUM);
3403
3404	/* Pseudos with argument area equivalences may require
3405	reloading via the argument pointer. */
3406	if (FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
3407	&& fixed_regs[ARG_POINTER_REGNUM])
3408	bitmap_set_bit (regular_block_artificial_uses, ARG_POINTER_REGNUM);
3409
3410	/* Any constant, or pseudo with constant equivalences, may
3411	require reloading from memory using the pic register. */
3412	if (picreg != INVALID_REGNUM
3413	&& fixed_regs[picreg])
3414	bitmap_set_bit (regular_block_artificial_uses, picreg);
3415	}
3416	/* The all-important stack pointer must always be live. */
3417	bitmap_set_bit (regular_block_artificial_uses, STACK_POINTER_REGNUM);
3418
3419	#ifdef EH_USES
3420	/* EH_USES registers are used:
3421	1) at all insns that might throw (calls or with -fnon-call-exceptions
3422	trapping insns)
3423	2) in all EH edges
3424	3) to support backtraces and/or debugging, anywhere between their
3425	initialization and where they the saved registers are restored
3426	from them, including the cases where we don't reach the epilogue
3427	(noreturn call or infinite loop). */
3428	for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3429	if (EH_USES (i))
3430	bitmap_set_bit (regular_block_artificial_uses, i);
3431	#endif
3432	}
3433
3434
3435	/* Get the artificial use set for an eh block. */
3436
3437	static void
3438	df_get_eh_block_artificial_uses (bitmap eh_block_artificial_uses)
3439	{
3440	bitmap_clear (eh_block_artificial_uses);
3441
3442	/* The following code (down through the arg_pointer setting APPEARS
3443	to be necessary because there is nothing that actually
3444	describes what the exception handling code may actually need
3445	to keep alive. */
3446	if (reload_completed)
3447	{
3448	if (frame_pointer_needed)
3449	{
3450	bitmap_set_bit (eh_block_artificial_uses, FRAME_POINTER_REGNUM);
3451	if (!HARD_FRAME_POINTER_IS_FRAME_POINTER)
3452	bitmap_set_bit (eh_block_artificial_uses,
3453	HARD_FRAME_POINTER_REGNUM);
3454	}
3455	if (FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
3456	&& fixed_regs[ARG_POINTER_REGNUM])
3457	bitmap_set_bit (eh_block_artificial_uses, ARG_POINTER_REGNUM);
3458	}
3459	}
3460
3461
3462
3463	/*----------------------------------------------------------------------------
3464	Specialized hard register scanning functions.
3465	----------------------------------------------------------------------------*/
3466
3467
3468	/* Mark a register in SET. Hard registers in large modes get all
3469	of their component registers set as well. */
3470
3471	static void
3472	df_mark_reg (rtx reg, void *vset)
3473	{
3474	bitmap_set_range ((bitmap) vset, REGNO (reg), REG_NREGS (reg));
3475	}
3476
3477
3478	/* Set the bit for regs that are considered being defined at the entry. */
3479
3480	static void
3481	df_get_entry_block_def_set (bitmap entry_block_defs)
3482	{
3483	rtx r;
3484	int i;
3485
3486	bitmap_clear (entry_block_defs);
3487
3488	/* For separate shrink-wrapping we use LIVE to analyze which basic blocks
3489	need a prologue for some component to be executed before that block,
3490	and we do not care about any other registers. Hence, we do not want
3491	any register for any component defined in the entry block, and we can
3492	just leave all registers undefined. */
3493	if (df_scan->local_flags & DF_SCAN_EMPTY_ENTRY_EXIT)
3494	return;
3495
3496	for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3497	{
3498	if (global_regs[i])
3499	bitmap_set_bit (entry_block_defs, i);
3500	if (FUNCTION_ARG_REGNO_P (i))
3501	bitmap_set_bit (entry_block_defs, INCOMING_REGNO (i));
3502	}
3503
3504	/* The always important stack pointer. */
3505	bitmap_set_bit (entry_block_defs, STACK_POINTER_REGNUM);
3506
3507	/* Once the prologue has been generated, all of these registers
3508	should just show up in the first regular block. */
3509	if (targetm.have_prologue () && epilogue_completed)
3510	{
3511	/* Defs for the callee saved registers are inserted so that the
3512	pushes have some defining location. */
3513	for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3514	if (!crtl->abi->clobbers_full_reg_p (regno: i)
3515	&& !fixed_regs[i]
3516	&& df_regs_ever_live_p (i))
3517	bitmap_set_bit (entry_block_defs, i);
3518	}
3519
3520	r = targetm.calls.struct_value_rtx (current_function_decl, true);
3521	if (r && REG_P (r))
3522	bitmap_set_bit (entry_block_defs, REGNO (r));
3523
3524	/* If the function has an incoming STATIC_CHAIN, it has to show up
3525	in the entry def set. */
3526	r = rtx_for_static_chain (current_function_decl, true);
3527	if (r && REG_P (r))
3528	bitmap_set_bit (entry_block_defs, REGNO (r));
3529
3530	if ((!reload_completed) || frame_pointer_needed)
3531	{
3532	/* Any reference to any pseudo before reload is a potential
3533	reference of the frame pointer. */
3534	bitmap_set_bit (entry_block_defs, FRAME_POINTER_REGNUM);
3535
3536	/* If they are different, also mark the hard frame pointer as live. */
3537	if (!HARD_FRAME_POINTER_IS_FRAME_POINTER
3538	&& !LOCAL_REGNO (HARD_FRAME_POINTER_REGNUM))
3539	bitmap_set_bit (entry_block_defs, HARD_FRAME_POINTER_REGNUM);
3540	}
3541
3542	/* These registers are live everywhere. */
3543	if (!reload_completed)
3544	{
3545	/* Pseudos with argument area equivalences may require
3546	reloading via the argument pointer. */
3547	if (FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
3548	&& fixed_regs[ARG_POINTER_REGNUM])
3549	bitmap_set_bit (entry_block_defs, ARG_POINTER_REGNUM);
3550
3551	/* Any constant, or pseudo with constant equivalences, may
3552	require reloading from memory using the pic register. */
3553	unsigned int picreg = PIC_OFFSET_TABLE_REGNUM;
3554	if (picreg != INVALID_REGNUM
3555	&& fixed_regs[picreg])
3556	bitmap_set_bit (entry_block_defs, picreg);
3557	}
3558
3559	#ifdef INCOMING_RETURN_ADDR_RTX
3560	if (REG_P (INCOMING_RETURN_ADDR_RTX))
3561	bitmap_set_bit (entry_block_defs, REGNO (INCOMING_RETURN_ADDR_RTX));
3562	#endif
3563
3564	targetm.extra_live_on_entry (entry_block_defs);
3565	}
3566
3567
3568	/* Return the (conservative) set of hard registers that are defined on
3569	entry to the function.
3570	It uses df->entry_block_defs to determine which register
3571	reference to include. */
3572
3573	static void
3574	df_entry_block_defs_collect (class df_collection_rec *collection_rec,
3575	bitmap entry_block_defs)
3576	{
3577	unsigned int i;
3578	bitmap_iterator bi;
3579
3580	EXECUTE_IF_SET_IN_BITMAP (entry_block_defs, 0, i, bi)
3581	{
3582	df_ref_record (cl: DF_REF_ARTIFICIAL, collection_rec, reg: regno_reg_rtx[i], NULL,
3583	ENTRY_BLOCK_PTR_FOR_FN (cfun), NULL, ref_type: DF_REF_REG_DEF, ref_flags: 0);
3584	}
3585
3586	df_canonize_collection_rec (collection_rec);
3587	}
3588
3589
3590	/* Record the (conservative) set of hard registers that are defined on
3591	entry to the function. */
3592
3593	static void
3594	df_record_entry_block_defs (bitmap entry_block_defs)
3595	{
3596	class df_collection_rec collection_rec;
3597	df_entry_block_defs_collect (collection_rec: &collection_rec, entry_block_defs);
3598
3599	/* Process bb_refs chain */
3600	df_refs_add_to_chains (collection_rec: &collection_rec,
3601	BASIC_BLOCK_FOR_FN (cfun, ENTRY_BLOCK),
3602	NULL,
3603	flags: copy_defs);
3604	}
3605
3606
3607	/* Update the defs in the entry block. */
3608
3609	void
3610	df_update_entry_block_defs (void)
3611	{
3612	bool changed = false;
3613
3614	auto_bitmap refs (&df_bitmap_obstack);
3615	df_get_entry_block_def_set (entry_block_defs: refs);
3616	gcc_assert (df->entry_block_defs);
3617	if (!bitmap_equal_p (df->entry_block_defs, refs))
3618	{
3619	struct df_scan_bb_info *bb_info = df_scan_get_bb_info (ENTRY_BLOCK);
3620	df_ref_chain_delete_du_chain (ref: bb_info->artificial_defs);
3621	df_ref_chain_delete (ref: bb_info->artificial_defs);
3622	bb_info->artificial_defs = NULL;
3623	changed = true;
3624	}
3625
3626	if (changed)
3627	{
3628	df_record_entry_block_defs (entry_block_defs: refs);
3629	bitmap_copy (df->entry_block_defs, refs);
3630	df_set_bb_dirty (BASIC_BLOCK_FOR_FN (cfun, ENTRY_BLOCK));
3631	}
3632	}
3633
3634
3635	/* Return true if REGNO is used by the epilogue. */
3636	bool
3637	df_epilogue_uses_p (unsigned int regno)
3638	{
3639	return (EPILOGUE_USES (regno)
3640	|| TEST_HARD_REG_BIT (crtl->must_be_zero_on_return, bit: regno));
3641	}
3642
3643	/* Set the bit for regs that are considered being used at the exit. */
3644
3645	static void
3646	df_get_exit_block_use_set (bitmap exit_block_uses)
3647	{
3648	unsigned int i;
3649	unsigned int picreg = PIC_OFFSET_TABLE_REGNUM;
3650
3651	bitmap_clear (exit_block_uses);
3652
3653	/* For separate shrink-wrapping we use LIVE to analyze which basic blocks
3654	need an epilogue for some component to be executed after that block,
3655	and we do not care about any other registers. Hence, we do not want
3656	any register for any component seen as used in the exit block, and we
3657	can just say no registers at all are used. */
3658	if (df_scan->local_flags & DF_SCAN_EMPTY_ENTRY_EXIT)
3659	return;
3660
3661	/* Stack pointer is always live at the exit. */
3662	bitmap_set_bit (exit_block_uses, STACK_POINTER_REGNUM);
3663
3664	/* Mark the frame pointer if needed at the end of the function.
3665	If we end up eliminating it, it will be removed from the live
3666	list of each basic block by reload. */
3667
3668	if ((!reload_completed) || frame_pointer_needed)
3669	{
3670	bitmap_set_bit (exit_block_uses, FRAME_POINTER_REGNUM);
3671
3672	/* If they are different, also mark the hard frame pointer as live. */
3673	if (!HARD_FRAME_POINTER_IS_FRAME_POINTER
3674	&& !LOCAL_REGNO (HARD_FRAME_POINTER_REGNUM))
3675	bitmap_set_bit (exit_block_uses, HARD_FRAME_POINTER_REGNUM);
3676	}
3677
3678	/* Many architectures have a GP register even without flag_pic.
3679	Assume the pic register is not in use, or will be handled by
3680	other means, if it is not fixed. */
3681	if (!PIC_OFFSET_TABLE_REG_CALL_CLOBBERED
3682	&& picreg != INVALID_REGNUM
3683	&& fixed_regs[picreg])
3684	bitmap_set_bit (exit_block_uses, picreg);
3685
3686	/* Mark all global registers, and all registers used by the
3687	epilogue as being live at the end of the function since they
3688	may be referenced by our caller. */
3689	for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3690	if (global_regs[i] || df_epilogue_uses_p (regno: i))
3691	bitmap_set_bit (exit_block_uses, i);
3692
3693	if (targetm.have_epilogue () && epilogue_completed)
3694	{
3695	/* Mark all call-saved registers that we actually used. */
3696	for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3697	if (df_regs_ever_live_p (i)
3698	&& !LOCAL_REGNO (i)
3699	&& !crtl->abi->clobbers_full_reg_p (regno: i))
3700	bitmap_set_bit (exit_block_uses, i);
3701	}
3702
3703	/* Mark the registers that will contain data for the handler. */
3704	if (reload_completed && crtl->calls_eh_return)
3705	for (i = 0; ; ++i)
3706	{
3707	unsigned regno = EH_RETURN_DATA_REGNO (i);
3708	if (regno == INVALID_REGNUM)
3709	break;
3710	bitmap_set_bit (exit_block_uses, regno);
3711	}
3712
3713	#ifdef EH_RETURN_STACKADJ_RTX
3714	if ((!targetm.have_epilogue () || ! epilogue_completed)
3715	&& crtl->calls_eh_return)
3716	{
3717	rtx tmp = EH_RETURN_STACKADJ_RTX;
3718	if (tmp && REG_P (tmp))
3719	df_mark_reg (reg: tmp, vset: exit_block_uses);
3720	}
3721	#endif
3722
3723	if ((!targetm.have_epilogue () || ! epilogue_completed)
3724	&& crtl->calls_eh_return)
3725	{
3726	rtx tmp = EH_RETURN_HANDLER_RTX;
3727	if (tmp && REG_P (tmp))
3728	df_mark_reg (reg: tmp, vset: exit_block_uses);
3729	}
3730
3731	/* Mark function return value. */
3732	diddle_return_value (df_mark_reg, (void*) exit_block_uses);
3733	}
3734
3735
3736	/* Return the refs of hard registers that are used in the exit block.
3737	It uses df->exit_block_uses to determine register to include. */
3738
3739	static void
3740	df_exit_block_uses_collect (class df_collection_rec *collection_rec, bitmap exit_block_uses)
3741	{
3742	unsigned int i;
3743	bitmap_iterator bi;
3744
3745	EXECUTE_IF_SET_IN_BITMAP (exit_block_uses, 0, i, bi)
3746	df_ref_record (cl: DF_REF_ARTIFICIAL, collection_rec, reg: regno_reg_rtx[i], NULL,
3747	EXIT_BLOCK_PTR_FOR_FN (cfun), NULL, ref_type: DF_REF_REG_USE, ref_flags: 0);
3748
3749	/* It is deliberate that this is not put in the exit block uses but
3750	I do not know why. */
3751	if (FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
3752	&& reload_completed
3753	&& !bitmap_bit_p (exit_block_uses, ARG_POINTER_REGNUM)
3754	&& bb_has_eh_pred (EXIT_BLOCK_PTR_FOR_FN (cfun))
3755	&& fixed_regs[ARG_POINTER_REGNUM])
3756	df_ref_record (cl: DF_REF_ARTIFICIAL, collection_rec, reg: regno_reg_rtx[ARG_POINTER_REGNUM], NULL,
3757	EXIT_BLOCK_PTR_FOR_FN (cfun), NULL, ref_type: DF_REF_REG_USE, ref_flags: 0);
3758
3759	df_canonize_collection_rec (collection_rec);
3760	}
3761
3762
3763	/* Record the set of hard registers that are used in the exit block.
3764	It uses df->exit_block_uses to determine which bit to include. */
3765
3766	static void
3767	df_record_exit_block_uses (bitmap exit_block_uses)
3768	{
3769	class df_collection_rec collection_rec;
3770	df_exit_block_uses_collect (collection_rec: &collection_rec, exit_block_uses);
3771
3772	/* Process bb_refs chain */
3773	df_refs_add_to_chains (collection_rec: &collection_rec,
3774	BASIC_BLOCK_FOR_FN (cfun, EXIT_BLOCK),
3775	NULL,
3776	flags: copy_uses);
3777	}
3778
3779
3780	/* Update the uses in the exit block. */
3781
3782	void
3783	df_update_exit_block_uses (void)
3784	{
3785	bool changed = false;
3786
3787	auto_bitmap refs (&df_bitmap_obstack);
3788	df_get_exit_block_use_set (exit_block_uses: refs);
3789	gcc_assert (df->exit_block_uses);
3790	if (!bitmap_equal_p (df->exit_block_uses, refs))
3791	{
3792	struct df_scan_bb_info *bb_info = df_scan_get_bb_info (EXIT_BLOCK);
3793	df_ref_chain_delete_du_chain (ref: bb_info->artificial_uses);
3794	df_ref_chain_delete (ref: bb_info->artificial_uses);
3795	bb_info->artificial_uses = NULL;
3796	changed = true;
3797	}
3798
3799	if (changed)
3800	{
3801	df_record_exit_block_uses (exit_block_uses: refs);
3802	bitmap_copy (df->exit_block_uses, refs);
3803	df_set_bb_dirty (BASIC_BLOCK_FOR_FN (cfun, EXIT_BLOCK));
3804	}
3805	}
3806
3807	static bool initialized = false;
3808
3809
3810	/* Initialize some platform specific structures. */
3811
3812	void
3813	df_hard_reg_init (void)
3814	{
3815	int i;
3816	static const struct {const int from, to; } eliminables[] = ELIMINABLE_REGS;
3817
3818	if (initialized)
3819	return;
3820
3821	/* Record which registers will be eliminated. We use this in
3822	mark_used_regs. */
3823	CLEAR_HARD_REG_SET (set&: elim_reg_set);
3824
3825	for (i = 0; i < (int) ARRAY_SIZE (eliminables); i++)
3826	SET_HARD_REG_BIT (set&: elim_reg_set, bit: eliminables[i].from);
3827
3828	initialized = true;
3829	}
3830
3831	/* Recompute the parts of scanning that are based on regs_ever_live
3832	because something changed in that array. */
3833
3834	void
3835	df_update_entry_exit_and_calls (void)
3836	{
3837	basic_block bb;
3838
3839	df_update_entry_block_defs ();
3840	df_update_exit_block_uses ();
3841
3842	/* The call insns need to be rescanned because there may be changes
3843	in the set of registers clobbered across the call. */
3844	FOR_EACH_BB_FN (bb, cfun)
3845	{
3846	rtx_insn *insn;
3847	FOR_BB_INSNS (bb, insn)
3848	{
3849	if (INSN_P (insn) && CALL_P (insn))
3850	df_insn_rescan (insn);
3851	}
3852	}
3853	}
3854
3855
3856	/* Return true if hard REG is actually used in the some instruction.
3857	There are a fair number of conditions that affect the setting of
3858	this array. See the comment in df.h for df->hard_regs_live_count
3859	for the conditions that this array is set. */
3860
3861	bool
3862	df_hard_reg_used_p (unsigned int reg)
3863	{
3864	return df->hard_regs_live_count[reg] != 0;
3865	}
3866
3867
3868	/* A count of the number of times REG is actually used in the some
3869	instruction. There are a fair number of conditions that affect the
3870	setting of this array. See the comment in df.h for
3871	df->hard_regs_live_count for the conditions that this array is
3872	set. */
3873
3874
3875	unsigned int
3876	df_hard_reg_used_count (unsigned int reg)
3877	{
3878	return df->hard_regs_live_count[reg];
3879	}
3880
3881
3882	/* Get the value of regs_ever_live[REGNO]. */
3883
3884	bool
3885	df_regs_ever_live_p (unsigned int regno)
3886	{
3887	return regs_ever_live[regno];
3888	}
3889
3890	/* Set regs_ever_live[REGNO] to VALUE. If this cause regs_ever_live
3891	to change, schedule that change for the next update. */
3892
3893	void
3894	df_set_regs_ever_live (unsigned int regno, bool value)
3895	{
3896	if (regs_ever_live[regno] == value)
3897	return;
3898
3899	regs_ever_live[regno] = value;
3900	if (df)
3901	df->redo_entry_and_exit = true;
3902	}
3903
3904
3905	/* Compute "regs_ever_live" information from the underlying df
3906	information. Set the vector to all false if RESET. */
3907
3908	void
3909	df_compute_regs_ever_live (bool reset)
3910	{
3911	unsigned int i;
3912	bool changed = df->redo_entry_and_exit;
3913
3914	if (reset)
3915	memset (s: regs_ever_live, c: 0, n: sizeof (regs_ever_live));
3916
3917	for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3918	if ((!regs_ever_live[i]) && df_hard_reg_used_p (reg: i))
3919	{
3920	regs_ever_live[i] = true;
3921	changed = true;
3922	}
3923	if (changed)
3924	df_update_entry_exit_and_calls ();
3925	df->redo_entry_and_exit = false;
3926	}
3927
3928
3929	/*----------------------------------------------------------------------------
3930	Dataflow ref information verification functions.
3931
3932	df_reg_chain_mark (refs, regno, is_def, is_eq_use)
3933	df_reg_chain_verify_unmarked (refs)
3934	df_refs_verify (vec<stack, va_df_ref>, ref*, bool)
3935	df_mws_verify (mw*, mw*, bool)
3936	df_insn_refs_verify (collection_rec, bb, insn, bool)
3937	df_bb_refs_verify (bb, refs, bool)
3938	df_bb_verify (bb)
3939	df_exit_block_bitmap_verify (bool)
3940	df_entry_block_bitmap_verify (bool)
3941	df_scan_verify ()
3942	----------------------------------------------------------------------------*/
3943
3944
3945	/* Mark all refs in the reg chain. Verify that all of the registers
3946	are in the correct chain. */
3947
3948	static unsigned int
3949	df_reg_chain_mark (df_ref refs, unsigned int regno,
3950	bool is_def, bool is_eq_use)
3951	{
3952	unsigned int count = 0;
3953	df_ref ref;
3954	for (ref = refs; ref; ref = DF_REF_NEXT_REG (ref))
3955	{
3956	gcc_assert (!DF_REF_IS_REG_MARKED (ref));
3957
3958	/* If there are no def-use or use-def chains, make sure that all
3959	of the chains are clear. */
3960	if (!df_chain)
3961	gcc_assert (!DF_REF_CHAIN (ref));
3962
3963	/* Check to make sure the ref is in the correct chain. */
3964	gcc_assert (DF_REF_REGNO (ref) == regno);
3965	if (is_def)
3966	gcc_assert (DF_REF_REG_DEF_P (ref));
3967	else
3968	gcc_assert (!DF_REF_REG_DEF_P (ref));
3969
3970	if (is_eq_use)
3971	gcc_assert ((DF_REF_FLAGS (ref) & DF_REF_IN_NOTE));
3972	else
3973	gcc_assert ((DF_REF_FLAGS (ref) & DF_REF_IN_NOTE) == 0);
3974
3975	if (DF_REF_NEXT_REG (ref))
3976	gcc_assert (DF_REF_PREV_REG (DF_REF_NEXT_REG (ref)) == ref);
3977	count++;
3978	DF_REF_REG_MARK (ref);
3979	}
3980	return count;
3981	}
3982
3983
3984	/* Verify that all of the registers in the chain are unmarked. */
3985
3986	static void
3987	df_reg_chain_verify_unmarked (df_ref refs)
3988	{
3989	df_ref ref;
3990	for (ref = refs; ref; ref = DF_REF_NEXT_REG (ref))
3991	gcc_assert (!DF_REF_IS_REG_MARKED (ref));
3992	}
3993
3994
3995	/* Verify that NEW_REC and OLD_REC have exactly the same members. */
3996
3997	static bool
3998	df_refs_verify (const vec<df_ref, va_heap> *new_rec, df_ref old_rec,
3999	bool abort_if_fail)
4000	{
4001	unsigned int ix;
4002	df_ref new_ref;
4003
4004	FOR_EACH_VEC_ELT (*new_rec, ix, new_ref)
4005	{
4006	if (old_rec == NULL || !df_ref_equal_p (ref1: new_ref, ref2: old_rec))
4007	{
4008	if (abort_if_fail)
4009	gcc_assert (0);
4010	else
4011	return false;
4012	}
4013
4014	/* Abort if fail is called from the function level verifier. If
4015	that is the context, mark this reg as being seem. */
4016	if (abort_if_fail)
4017	{
4018	gcc_assert (DF_REF_IS_REG_MARKED (old_rec));
4019	DF_REF_REG_UNMARK (old_rec);
4020	}
4021
4022	old_rec = DF_REF_NEXT_LOC (old_rec);
4023	}
4024
4025	if (abort_if_fail)
4026	gcc_assert (old_rec == NULL);
4027	else
4028	return old_rec == NULL;
4029	return false;
4030	}
4031
4032
4033	/* Verify that NEW_REC and OLD_REC have exactly the same members. */
4034
4035	static bool
4036	df_mws_verify (const vec<df_mw_hardreg *, va_heap> *new_rec,
4037	struct df_mw_hardreg *old_rec,
4038	bool abort_if_fail)
4039	{
4040	unsigned int ix;
4041	struct df_mw_hardreg *new_reg;
4042
4043	FOR_EACH_VEC_ELT (*new_rec, ix, new_reg)
4044	{
4045	if (old_rec == NULL || !df_mw_equal_p (mw1: new_reg, mw2: old_rec))
4046	{
4047	if (abort_if_fail)
4048	gcc_assert (0);
4049	else
4050	return false;
4051	}
4052	old_rec = DF_MWS_NEXT (old_rec);
4053	}
4054
4055	if (abort_if_fail)
4056	gcc_assert (old_rec == NULL);
4057	else
4058	return old_rec == NULL;
4059	return false;
4060	}
4061
4062
4063	/* Return true if the existing insn refs information is complete and
4064	correct. Otherwise (i.e. if there's any missing or extra refs),
4065	return the correct df_ref chain in REFS_RETURN.
4066
4067	If ABORT_IF_FAIL, leave the refs that are verified (already in the
4068	ref chain) as DF_REF_MARKED(). If it's false, then it's a per-insn
4069	verification mode instead of the whole function, so unmark
4070	everything.
4071
4072	If ABORT_IF_FAIL is set, this function never returns false. */
4073
4074	static bool
4075	df_insn_refs_verify (class df_collection_rec *collection_rec,
4076	basic_block bb,
4077	rtx_insn *insn,
4078	bool abort_if_fail)
4079	{
4080	bool ret1, ret2, ret3;
4081	unsigned int uid = INSN_UID (insn);
4082	struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
4083
4084	df_insn_refs_collect (collection_rec, bb, insn_info);
4085
4086	/* Unfortunately we cannot opt out early if one of these is not
4087	right and abort_if_fail is set because the marks will not get cleared. */
4088	ret1 = df_refs_verify (new_rec: &collection_rec->def_vec, DF_INSN_UID_DEFS (uid),
4089	abort_if_fail);
4090	if (!ret1 && !abort_if_fail)
4091	return false;
4092	ret2 = df_refs_verify (new_rec: &collection_rec->use_vec, DF_INSN_UID_USES (uid),
4093	abort_if_fail);
4094	if (!ret2 && !abort_if_fail)
4095	return false;
4096	ret3 = df_refs_verify (new_rec: &collection_rec->eq_use_vec, DF_INSN_UID_EQ_USES (uid),
4097	abort_if_fail);
4098	if (!ret3 && !abort_if_fail)
4099	return false;
4100	if (! df_mws_verify (new_rec: &collection_rec->mw_vec, DF_INSN_UID_MWS (uid),
4101	abort_if_fail))
4102	return false;
4103	return (ret1 && ret2 && ret3);
4104	}
4105
4106
4107	/* Return true if all refs in the basic block are correct and complete.
4108	Due to df_ref_chain_verify, it will cause all refs
4109	that are verified to have DF_REF_MARK bit set. */
4110
4111	static bool
4112	df_bb_verify (basic_block bb)
4113	{
4114	rtx_insn *insn;
4115	struct df_scan_bb_info *bb_info = df_scan_get_bb_info (index: bb->index);
4116	class df_collection_rec collection_rec;
4117
4118	gcc_assert (bb_info);
4119
4120	/* Scan the block, one insn at a time, from beginning to end. */
4121	FOR_BB_INSNS_REVERSE (bb, insn)
4122	{
4123	if (!INSN_P (insn))
4124	continue;
4125	df_insn_refs_verify (collection_rec: &collection_rec, bb, insn, abort_if_fail: true);
4126	df_free_collection_rec (collection_rec: &collection_rec);
4127	}
4128
4129	/* Do the artificial defs and uses. */
4130	df_bb_refs_collect (collection_rec: &collection_rec, bb);
4131	df_refs_verify (new_rec: &collection_rec.def_vec, old_rec: df_get_artificial_defs (bb_index: bb->index), abort_if_fail: true);
4132	df_refs_verify (new_rec: &collection_rec.use_vec, old_rec: df_get_artificial_uses (bb_index: bb->index), abort_if_fail: true);
4133	df_free_collection_rec (collection_rec: &collection_rec);
4134
4135	return true;
4136	}
4137
4138
4139	/* Returns true if the entry block has correct and complete df_ref set.
4140	If not it either aborts if ABORT_IF_FAIL is true or returns false. */
4141
4142	static bool
4143	df_entry_block_bitmap_verify (bool abort_if_fail)
4144	{
4145	bool is_eq;
4146
4147	auto_bitmap entry_block_defs (&df_bitmap_obstack);
4148	df_get_entry_block_def_set (entry_block_defs);
4149
4150	is_eq = bitmap_equal_p (entry_block_defs, df->entry_block_defs);
4151
4152	if (!is_eq && abort_if_fail)
4153	{
4154	fprintf (stderr, format: "entry_block_defs = ");
4155	df_print_regset (stderr, r: entry_block_defs);
4156	fprintf (stderr, format: "df->entry_block_defs = ");
4157	df_print_regset (stderr, r: df->entry_block_defs);
4158	gcc_assert (0);
4159	}
4160
4161	return is_eq;
4162	}
4163
4164
4165	/* Returns true if the exit block has correct and complete df_ref set.
4166	If not it either aborts if ABORT_IF_FAIL is true or returns false. */
4167
4168	static bool
4169	df_exit_block_bitmap_verify (bool abort_if_fail)
4170	{
4171	bool is_eq;
4172
4173	auto_bitmap exit_block_uses (&df_bitmap_obstack);
4174	df_get_exit_block_use_set (exit_block_uses);
4175
4176	is_eq = bitmap_equal_p (exit_block_uses, df->exit_block_uses);
4177
4178	if (!is_eq && abort_if_fail)
4179	{
4180	fprintf (stderr, format: "exit_block_uses = ");
4181	df_print_regset (stderr, r: exit_block_uses);
4182	fprintf (stderr, format: "df->exit_block_uses = ");
4183	df_print_regset (stderr, r: df->exit_block_uses);
4184	gcc_assert (0);
4185	}
4186
4187	return is_eq;
4188	}
4189
4190
4191	/* Return true if df_ref information for all insns in all blocks are
4192	correct and complete. */
4193
4194	void
4195	df_scan_verify (void)
4196	{
4197	unsigned int i;
4198	basic_block bb;
4199
4200	if (!df)
4201	return;
4202
4203	/* Verification is a 4 step process. */
4204
4205	/* (1) All of the refs are marked by going through the reg chains. */
4206	for (i = 0; i < DF_REG_SIZE (df); i++)
4207	{
4208	gcc_assert (df_reg_chain_mark (DF_REG_DEF_CHAIN (i), i, true, false)
4209	== DF_REG_DEF_COUNT (i));
4210	gcc_assert (df_reg_chain_mark (DF_REG_USE_CHAIN (i), i, false, false)
4211	== DF_REG_USE_COUNT (i));
4212	gcc_assert (df_reg_chain_mark (DF_REG_EQ_USE_CHAIN (i), i, false, true)
4213	== DF_REG_EQ_USE_COUNT (i));
4214	}
4215
4216	/* (2) There are various bitmaps whose value may change over the
4217	course of the compilation. This step recomputes them to make
4218	sure that they have not slipped out of date. */
4219	auto_bitmap regular_block_artificial_uses (&df_bitmap_obstack);
4220	auto_bitmap eh_block_artificial_uses (&df_bitmap_obstack);
4221
4222	df_get_regular_block_artificial_uses (regular_block_artificial_uses);
4223	df_get_eh_block_artificial_uses (eh_block_artificial_uses);
4224
4225	bitmap_ior_into (eh_block_artificial_uses,
4226	regular_block_artificial_uses);
4227
4228	/* Check artificial_uses bitmaps didn't change. */
4229	gcc_assert (bitmap_equal_p (regular_block_artificial_uses,
4230	&df->regular_block_artificial_uses));
4231	gcc_assert (bitmap_equal_p (eh_block_artificial_uses,
4232	&df->eh_block_artificial_uses));
4233
4234	/* Verify entry block and exit block. These only verify the bitmaps,
4235	the refs are verified in df_bb_verify. */
4236	df_entry_block_bitmap_verify (abort_if_fail: true);
4237	df_exit_block_bitmap_verify (abort_if_fail: true);
4238
4239	/* (3) All of the insns in all of the blocks are traversed and the
4240	marks are cleared both in the artificial refs attached to the
4241	blocks and the real refs inside the insns. It is a failure to
4242	clear a mark that has not been set as this means that the ref in
4243	the block or insn was not in the reg chain. */
4244
4245	FOR_ALL_BB_FN (bb, cfun)
4246	df_bb_verify (bb);
4247
4248	/* (4) See if all reg chains are traversed a second time. This time
4249	a check is made that the marks are clear. A set mark would be a
4250	from a reg that is not in any insn or basic block. */
4251
4252	for (i = 0; i < DF_REG_SIZE (df); i++)
4253	{
4254	df_reg_chain_verify_unmarked (DF_REG_DEF_CHAIN (i));
4255	df_reg_chain_verify_unmarked (DF_REG_USE_CHAIN (i));
4256	df_reg_chain_verify_unmarked (DF_REG_EQ_USE_CHAIN (i));
4257	}
4258	}
4259