df-problems.cc source code [gcc/df-problems.cc]

1	/ Standard problems for dataflow support routines.*
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 "df.h"
31	#include "memmodel.h"
32	#include "tm_p.h"
33	#include "insn-config.h"
34	#include "cfganal.h"
35	#include "dce.h"
36	#include "valtrack.h"
37	#include "dumpfile.h"
38	#include "rtl-iter.h"
39	#include "regs.h"
40	#include "function-abi.h"
41
42	/ Note that turning REG_DEAD_DEBUGGING on will cause*
43	gcc.c-torture/unsorted/dump-noaddr.c to fail because it prints
44	addresses in the dumps. /*
45	#define REG_DEAD_DEBUGGING 0
46
47	#define DF_SPARSE_THRESHOLD 32
48
49	static bitmap_head seen_in_block;
50	static bitmap_head seen_in_insn;
51
52	/----------------------------------------------------------------------------*
53	Utility functions.
54	----------------------------------------------------------------------------/*
55
56	/ Generic versions to get the void* version of the block info. Only*
57	used inside the problem instance vectors. /*
58
59	/ Dump a def-use or use-def chain for REF to FILE. /
60
61	void
62	df_chain_dump (struct df_link link, FILE file)
63	{
64	fprintf (stream: file, format: "{ ");
65	for (; link; link = link->next)
66	{
67	fprintf (stream: file, format: "%c%d(bb %d insn %d) ",
68	DF_REF_REG_DEF_P (link->ref)
69	? `'d'`
70	: (DF_REF_FLAGS (link->ref) & DF_REF_IN_NOTE) ? `'e'` : `'u'`,
71	DF_REF_ID (link->ref),
72	DF_REF_BBNO (link->ref),
73	DF_REF_IS_ARTIFICIAL (link->ref)
74	? -`1` : DF_REF_INSN_UID (link->ref));
75	}
76	fprintf (stream: file, format: "}");
77	}
78
79
80	/ Print some basic block info as part of df_dump. /
81
82	void
83	df_print_bb_index (basic_block bb, FILE *file)
84	{
85	edge e;
86	edge_iterator ei;
87
88	fprintf (stream: file, format: "\n( ");
89	FOR_EACH_EDGE (e, ei, bb->preds)
90	{
91	basic_block pred = e->src;
92	fprintf (stream: file, format: "%d%s ", pred->index, e->flags & EDGE_EH ? "(EH)" : "");
93	}
94	fprintf (stream: file, format: ")->[%d]->( ", bb->index);
95	FOR_EACH_EDGE (e, ei, bb->succs)
96	{
97	basic_block succ = e->dest;
98	fprintf (stream: file, format: "%d%s ", succ->index, e->flags & EDGE_EH ? "(EH)" : "");
99	}
100	fprintf (stream: file, format: ")\n");
101	}
102
103
104	/----------------------------------------------------------------------------*
105	REACHING DEFINITIONS
106
107	Find the locations in the function where each definition site for a
108	pseudo reaches. In and out bitvectors are built for each basic
109	block. The id field in the ref is used to index into these sets.
110	See df.h for details.
111
112	If the DF_RD_PRUNE_DEAD_DEFS changeable flag is set, only DEFs reaching
113	existing uses are included in the global reaching DEFs set, or in other
114	words only DEFs that are still live. This is a kind of pruned version
115	of the traditional reaching definitions problem that is much less
116	complex to compute and produces enough information to compute UD-chains.
117	In this context, live must be interpreted in the DF_LR sense: Uses that
118	are upward exposed but maybe not initialized on all paths through the
119	CFG. For a USE that is not reached by a DEF on all paths, we still want
120	to make those DEFs that do reach the USE visible, and pruning based on
121	DF_LIVE would make that impossible.
122	----------------------------------------------------------------------------/*
123
124	/ This problem plays a large number of games for the sake of*
125	efficiency.
126
127	1) The order of the bits in the bitvectors. After the scanning
128	phase, all of the defs are sorted. All of the defs for the reg 0
129	are first, followed by all defs for reg 1 and so on.
130
131	2) There are two kill sets, one if the number of defs is less or
132	equal to DF_SPARSE_THRESHOLD and another if the number of defs is
133	greater.
134
135	<= : Data is built directly in the kill set.
136
137	> : One level of indirection is used to keep from generating long
138	strings of 1 bits in the kill sets. Bitvectors that are indexed
139	by the regnum are used to represent that there is a killing def
140	for the register. The confluence and transfer functions use
141	these along with the bitmap_clear_range call to remove ranges of
142	bits without actually generating a knockout vector.
143
144	The kill and sparse_kill and the dense_invalidated_by_eh and
145	sparse_invalidated_by_eh both play this game. /*
146
147	/ Private data used to compute the solution for this problem. These*
148	data structures are not accessible outside of this module. /*
149	class df_rd_problem_data
150	{
151	public:
152	/ The set of defs to regs invalidated by EH edges. /
153	bitmap_head sparse_invalidated_by_eh;
154	bitmap_head dense_invalidated_by_eh;
155	/ An obstack for the bitmaps we need for this problem. /
156	bitmap_obstack rd_bitmaps;
157	};
158
159
160	/ Free basic block info. /
161
162	static void
163	df_rd_free_bb_info (basic_block bb ATTRIBUTE_UNUSED,
164	void *vbb_info)
165	{
166	class df_rd_bb_info bb_info = (class* df_rd_bb_info *) vbb_info;
167	if (bb_info)
168	{
169	bitmap_clear (&bb_info->kill);
170	bitmap_clear (&bb_info->sparse_kill);
171	bitmap_clear (&bb_info->gen);
172	bitmap_clear (&bb_info->in);
173	bitmap_clear (&bb_info->out);
174	}
175	}
176
177
178	/ Allocate or reset bitmaps for DF_RD blocks. The solution bits are*
179	not touched unless the block is new. /*
180
181	static void
182	df_rd_alloc (bitmap all_blocks)
183	{
184	unsigned int bb_index;
185	bitmap_iterator bi;
186	class df_rd_problem_data *problem_data;
187
188	if (df_rd->problem_data)
189	{
190	problem_data = (class df_rd_problem_data *) df_rd->problem_data;
191	bitmap_clear (&problem_data->sparse_invalidated_by_eh);
192	bitmap_clear (&problem_data->dense_invalidated_by_eh);
193	}
194	else
195	{
196	problem_data = XNEW (class df_rd_problem_data);
197	df_rd->problem_data = problem_data;
198
199	bitmap_obstack_initialize (&problem_data->rd_bitmaps);
200	bitmap_initialize (head: &problem_data->sparse_invalidated_by_eh,
201	obstack: &problem_data->rd_bitmaps);
202	bitmap_initialize (head: &problem_data->dense_invalidated_by_eh,
203	obstack: &problem_data->rd_bitmaps);
204	}
205
206	df_grow_bb_info (df_rd);
207
208	/ Because of the clustering of all use sites for the same pseudo,*
209	we have to process all of the blocks before doing the analysis. /*
210
211	EXECUTE_IF_SET_IN_BITMAP (all_blocks, `0`, bb_index, bi)
212	{
213	class df_rd_bb_info *bb_info = df_rd_get_bb_info (index: bb_index);
214
215	/ When bitmaps are already initialized, just clear them. /
216	if (bb_info->kill.obstack)
217	{
218	bitmap_clear (&bb_info->kill);
219	bitmap_clear (&bb_info->sparse_kill);
220	bitmap_clear (&bb_info->gen);
221	}
222	else
223	{
224	bitmap_initialize (head: &bb_info->kill, obstack: &problem_data->rd_bitmaps);
225	bitmap_initialize (head: &bb_info->sparse_kill, obstack: &problem_data->rd_bitmaps);
226	bitmap_initialize (head: &bb_info->gen, obstack: &problem_data->rd_bitmaps);
227	bitmap_initialize (head: &bb_info->in, obstack: &problem_data->rd_bitmaps);
228	bitmap_initialize (head: &bb_info->out, obstack: &problem_data->rd_bitmaps);
229	}
230	}
231	df_rd->optional_p = true;
232	}
233
234
235	/ Add the effect of the top artificial defs of BB to the reaching definitions*
236	bitmap LOCAL_RD. /*
237
238	void
239	df_rd_simulate_artificial_defs_at_top (basic_block bb, bitmap local_rd)
240	{
241	int bb_index = bb->index;
242	df_ref def;
243	FOR_EACH_ARTIFICIAL_DEF (def, bb_index)
244	if (DF_REF_FLAGS (def) & DF_REF_AT_TOP)
245	{
246	unsigned int dregno = DF_REF_REGNO (def);
247	if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL \| DF_REF_CONDITIONAL)))
248	bitmap_clear_range (local_rd,
249	DF_DEFS_BEGIN (dregno),
250	DF_DEFS_COUNT (dregno));
251	bitmap_set_bit (local_rd, DF_REF_ID (def));
252	}
253	}
254
255	/ Add the effect of the defs of INSN to the reaching definitions bitmap*
256	LOCAL_RD. /*
257
258	void
259	df_rd_simulate_one_insn (basic_block bb ATTRIBUTE_UNUSED, rtx_insn *insn,
260	bitmap local_rd)
261	{
262	df_ref def;
263
264	FOR_EACH_INSN_DEF (def, insn)
265	{
266	unsigned int dregno = DF_REF_REGNO (def);
267	if ((!(df->changeable_flags & DF_NO_HARD_REGS))
268	\|\| (dregno >= FIRST_PSEUDO_REGISTER))
269	{
270	if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL \| DF_REF_CONDITIONAL)))
271	bitmap_clear_range (local_rd,
272	DF_DEFS_BEGIN (dregno),
273	DF_DEFS_COUNT (dregno));
274	if (!(DF_REF_FLAGS (def)
275	& (DF_REF_MUST_CLOBBER \| DF_REF_MAY_CLOBBER)))
276	bitmap_set_bit (local_rd, DF_REF_ID (def));
277	}
278	}
279	}
280
281	/ Process a list of DEFs for df_rd_bb_local_compute. This is a bit*
282	more complicated than just simulating, because we must produce the
283	gen and kill sets and hence deal with the two possible representations
284	of kill sets. /*
285
286	static void
287	df_rd_bb_local_compute_process_def (class df_rd_bb_info *bb_info,
288	df_ref def,
289	int top_flag)
290	{
291	for (; def; def = DF_REF_NEXT_LOC (def))
292	{
293	if (top_flag == (DF_REF_FLAGS (def) & DF_REF_AT_TOP))
294	{
295	unsigned int regno = DF_REF_REGNO (def);
296	unsigned int begin = DF_DEFS_BEGIN (regno);
297	unsigned int n_defs = DF_DEFS_COUNT (regno);
298
299	if ((!(df->changeable_flags & DF_NO_HARD_REGS))
300	\|\| (regno >= FIRST_PSEUDO_REGISTER))
301	{
302	/ Only the last def(s) for a regno in the block has any*
303	effect. /*
304	if (!bitmap_bit_p (&seen_in_block, regno))
305	{
306	/ The first def for regno in insn gets to knock out the*
307	defs from other instructions. /*
308	if ((!bitmap_bit_p (&seen_in_insn, regno))
309	/ If the def is to only part of the reg, it does*
310	not kill the other defs that reach here. /*
311	&& (!(DF_REF_FLAGS (def) &
312	(DF_REF_PARTIAL \| DF_REF_CONDITIONAL \| DF_REF_MAY_CLOBBER))))
313	{
314	if (n_defs > DF_SPARSE_THRESHOLD)
315	{
316	bitmap_set_bit (&bb_info->sparse_kill, regno);
317	bitmap_clear_range (&bb_info->gen, begin, n_defs);
318	}
319	else
320	{
321	bitmap_set_range (&bb_info->kill, begin, n_defs);
322	bitmap_clear_range (&bb_info->gen, begin, n_defs);
323	}
324	}
325
326	bitmap_set_bit (&seen_in_insn, regno);
327	/ All defs for regno in the instruction may be put into*
328	the gen set. /*
329	if (!(DF_REF_FLAGS (def)
330	& (DF_REF_MUST_CLOBBER \| DF_REF_MAY_CLOBBER)))
331	bitmap_set_bit (&bb_info->gen, DF_REF_ID (def));
332	}
333	}
334	}
335	}
336	}
337
338	/ Compute local reaching def info for basic block BB. /
339
340	static void
341	df_rd_bb_local_compute (unsigned int bb_index)
342	{
343	basic_block bb = BASIC_BLOCK_FOR_FN (cfun, bb_index);
344	class df_rd_bb_info *bb_info = df_rd_get_bb_info (index: bb_index);
345	rtx_insn *insn;
346
347	bitmap_clear (&seen_in_block);
348	bitmap_clear (&seen_in_insn);
349
350	/ Artificials are only hard regs. /
351	if (!(df->changeable_flags & DF_NO_HARD_REGS))
352	df_rd_bb_local_compute_process_def (bb_info,
353	def: df_get_artificial_defs (bb_index),
354	top_flag: `0`);
355
356	FOR_BB_INSNS_REVERSE (bb, insn)
357	{
358	unsigned int uid = INSN_UID (insn);
359
360	if (!INSN_P (insn))
361	continue;
362
363	df_rd_bb_local_compute_process_def (bb_info,
364	DF_INSN_UID_DEFS (uid), top_flag: `0`);
365
366	/ This complex dance with the two bitmaps is required because*
367	instructions can assign twice to the same pseudo. This
368	generally happens with calls that will have one def for the
369	result and another def for the clobber. If only one vector
370	is used and the clobber goes first, the result will be
371	lost. /*
372	bitmap_ior_into (&seen_in_block, &seen_in_insn);
373	bitmap_clear (&seen_in_insn);
374	}
375
376	/ Process the artificial defs at the top of the block last since we*
377	are going backwards through the block and these are logically at
378	the start. /*
379	if (!(df->changeable_flags & DF_NO_HARD_REGS))
380	df_rd_bb_local_compute_process_def (bb_info,
381	def: df_get_artificial_defs (bb_index),
382	top_flag: DF_REF_AT_TOP);
383	}
384
385
386	/ Compute local reaching def info for each basic block within BLOCKS. /
387
388	static void
389	df_rd_local_compute (bitmap all_blocks)
390	{
391	unsigned int bb_index;
392	bitmap_iterator bi;
393	class df_rd_problem_data *problem_data
394	= (class df_rd_problem_data *) df_rd->problem_data;
395	bitmap sparse_invalidated = &problem_data->sparse_invalidated_by_eh;
396	bitmap dense_invalidated = &problem_data->dense_invalidated_by_eh;
397
398	bitmap_initialize (head: &seen_in_block, obstack: &df_bitmap_obstack);
399	bitmap_initialize (head: &seen_in_insn, obstack: &df_bitmap_obstack);
400
401	df_maybe_reorganize_def_refs (DF_REF_ORDER_BY_REG);
402
403	EXECUTE_IF_SET_IN_BITMAP (all_blocks, `0`, bb_index, bi)
404	{
405	df_rd_bb_local_compute (bb_index);
406	}
407
408	/ Set up the knockout bit vectors to be applied across EH_EDGES.*
409	Conservatively treat partially-clobbered registers as surviving
410	across the EH edge, i.e. assume that definitions before the edge
411	is taken might* reach uses after it has been taken. /
412	if (!(df->changeable_flags & DF_NO_HARD_REGS))
413	for (unsigned int regno = `0`; regno < FIRST_PSEUDO_REGISTER; ++regno)
414	if (eh_edge_abi.clobbers_full_reg_p (regno))
415	{
416	if (DF_DEFS_COUNT (regno) > DF_SPARSE_THRESHOLD)
417	bitmap_set_bit (sparse_invalidated, regno);
418	else
419	bitmap_set_range (dense_invalidated,
420	DF_DEFS_BEGIN (regno),
421	DF_DEFS_COUNT (regno));
422	}
423
424	bitmap_release (head: &seen_in_block);
425	bitmap_release (head: &seen_in_insn);
426	}
427
428
429	/ Initialize the solution bit vectors for problem. /
430
431	static void
432	df_rd_init_solution (bitmap all_blocks)
433	{
434	unsigned int bb_index;
435	bitmap_iterator bi;
436
437	EXECUTE_IF_SET_IN_BITMAP (all_blocks, `0`, bb_index, bi)
438	{
439	class df_rd_bb_info *bb_info = df_rd_get_bb_info (index: bb_index);
440
441	bitmap_copy (&bb_info->out, &bb_info->gen);
442	bitmap_clear (&bb_info->in);
443	}
444	}
445
446	/ In of target gets or of out of source. /
447
448	static bool
449	df_rd_confluence_n (edge e)
450	{
451	bitmap op1 = &df_rd_get_bb_info (index: e->dest->index)->in;
452	bitmap op2 = &df_rd_get_bb_info (index: e->src->index)->out;
453	bool changed = false;
454
455	if (e->flags & EDGE_FAKE)
456	return false;
457
458	if (e->flags & EDGE_EH)
459	{
460	class df_rd_problem_data *problem_data
461	= (class df_rd_problem_data *) df_rd->problem_data;
462	bitmap sparse_invalidated = &problem_data->sparse_invalidated_by_eh;
463	bitmap dense_invalidated = &problem_data->dense_invalidated_by_eh;
464	bitmap_iterator bi;
465	unsigned int regno;
466
467	auto_bitmap tmp (&df_bitmap_obstack);
468	bitmap_and_compl (tmp, op2, dense_invalidated);
469
470	EXECUTE_IF_SET_IN_BITMAP (sparse_invalidated, `0`, regno, bi)
471	{
472	bitmap_clear_range (tmp,
473	DF_DEFS_BEGIN (regno),
474	DF_DEFS_COUNT (regno));
475	}
476	changed \|= bitmap_ior_into (op1, tmp);
477	return changed;
478	}
479	else
480	return bitmap_ior_into (op1, op2);
481	}
482
483
484	/ Transfer function. /
485
486	static bool
487	df_rd_transfer_function (int bb_index)
488	{
489	class df_rd_bb_info *bb_info = df_rd_get_bb_info (index: bb_index);
490	unsigned int regno;
491	bitmap_iterator bi;
492	bitmap in = &bb_info->in;
493	bitmap out = &bb_info->out;
494	bitmap gen = &bb_info->gen;
495	bitmap kill = &bb_info->kill;
496	bitmap sparse_kill = &bb_info->sparse_kill;
497	bool changed = false;
498
499	if (bitmap_empty_p (map: sparse_kill))
500	changed = bitmap_ior_and_compl (DST: out, A: gen, B: in, C: kill);
501	else
502	{
503	class df_rd_problem_data *problem_data;
504	bitmap_head tmp;
505
506	/ Note that TMP is _not_ a temporary bitmap if we end up replacing*
507	OUT with TMP. Therefore, allocate TMP in the RD bitmaps obstack. /*
508	problem_data = (class df_rd_problem_data *) df_rd->problem_data;
509	bitmap_initialize (head: &tmp, obstack: &problem_data->rd_bitmaps);
510
511	bitmap_and_compl (&tmp, in, kill);
512	EXECUTE_IF_SET_IN_BITMAP (sparse_kill, `0`, regno, bi)
513	{
514	bitmap_clear_range (&tmp,
515	DF_DEFS_BEGIN (regno),
516	DF_DEFS_COUNT (regno));
517	}
518	bitmap_ior_into (&tmp, gen);
519	changed = !bitmap_equal_p (&tmp, out);
520	if (changed)
521	bitmap_move (out, &tmp);
522	else
523	bitmap_clear (&tmp);
524	}
525
526	if (df->changeable_flags & DF_RD_PRUNE_DEAD_DEFS)
527	{
528	/ Create a mask of DEFs for all registers live at the end of this*
529	basic block, and mask out DEFs of registers that are not live.
530	Computing the mask looks costly, but the benefit of the pruning
531	outweighs the cost. /*
532	class df_rd_bb_info *bb_info = df_rd_get_bb_info (index: bb_index);
533	bitmap regs_live_out = &df_lr_get_bb_info (index: bb_index)->out;
534	bitmap live_defs = BITMAP_ALLOC (obstack: &df_bitmap_obstack);
535	unsigned int regno;
536	bitmap_iterator bi;
537
538	EXECUTE_IF_SET_IN_BITMAP (regs_live_out, `0`, regno, bi)
539	bitmap_set_range (live_defs,
540	DF_DEFS_BEGIN (regno),
541	DF_DEFS_COUNT (regno));
542	changed \|= bitmap_and_into (&bb_info->out, live_defs);
543	BITMAP_FREE (live_defs);
544	}
545
546	return changed;
547	}
548
549	/ Free all storage associated with the problem. /
550
551	static void
552	df_rd_free (void)
553	{
554	class df_rd_problem_data *problem_data
555	= (class df_rd_problem_data *) df_rd->problem_data;
556
557	if (problem_data)
558	{
559	bitmap_obstack_release (&problem_data->rd_bitmaps);
560
561	df_rd->block_info_size = `0`;
562	free (df_rd->block_info);
563	df_rd->block_info = NULL;
564	free (df_rd->problem_data);
565	}
566	free (df_rd);
567	}
568
569
570	/ Debugging info. /
571
572	static void
573	df_rd_start_dump (FILE *file)
574	{
575	class df_rd_problem_data *problem_data
576	= (class df_rd_problem_data *) df_rd->problem_data;
577	unsigned int m = DF_REG_SIZE (df);
578	unsigned int regno;
579
580	if (!df_rd->block_info)
581	return;
582
583	fprintf (stream: file, format: ";; Reaching defs:\n");
584
585	fprintf (stream: file, format: ";; sparse invalidated \t");
586	dump_bitmap (file, map: &problem_data->sparse_invalidated_by_eh);
587	fprintf (stream: file, format: ";; dense invalidated \t");
588	dump_bitmap (file, map: &problem_data->dense_invalidated_by_eh);
589
590	fprintf (stream: file, format: ";; reg->defs[] map:\t");
591	for (regno = `0`; regno < m; regno++)
592	if (DF_DEFS_COUNT (regno))
593	fprintf (stream: file, format: "%d[%d,%d] ", regno,
594	DF_DEFS_BEGIN (regno),
595	DF_DEFS_BEGIN (regno) + DF_DEFS_COUNT (regno) - `1`);
596	fprintf (stream: file, format: "\n");
597	}
598
599
600	static void
601	df_rd_dump_defs_set (bitmap defs_set, const char prefix, FILE file)
602	{
603	bitmap_head tmp;
604	unsigned int regno;
605	unsigned int m = DF_REG_SIZE (df);
606	bool first_reg = true;
607
608	fprintf (stream: file, format: "%s\t(%d) ", prefix, (int) bitmap_count_bits (defs_set));
609
610	bitmap_initialize (head: &tmp, obstack: &df_bitmap_obstack);
611	for (regno = `0`; regno < m; regno++)
612	{
613	if (HARD_REGISTER_NUM_P (regno)
614	&& (df->changeable_flags & DF_NO_HARD_REGS))
615	continue;
616	bitmap_set_range (&tmp, DF_DEFS_BEGIN (regno), DF_DEFS_COUNT (regno));
617	bitmap_and_into (&tmp, defs_set);
618	if (! bitmap_empty_p (map: &tmp))
619	{
620	bitmap_iterator bi;
621	unsigned int ix;
622	bool first_def = true;
623
624	if (! first_reg)
625	fprintf (stream: file, format: ",");
626	first_reg = false;
627
628	fprintf (stream: file, format: "%u[", regno);
629	EXECUTE_IF_SET_IN_BITMAP (&tmp, `0`, ix, bi)
630	{
631	fprintf (stream: file, format: "%s%u", first_def ? "" : ",", ix);
632	first_def = false;
633	}
634	fprintf (stream: file, format: "]");
635	}
636	bitmap_clear (&tmp);
637	}
638
639	fprintf (stream: file, format: "\n");
640	bitmap_clear (&tmp);
641	}
642
643	/ Debugging info at top of bb. /
644
645	static void
646	df_rd_top_dump (basic_block bb, FILE *file)
647	{
648	class df_rd_bb_info *bb_info = df_rd_get_bb_info (index: bb->index);
649	if (!bb_info)
650	return;
651
652	df_rd_dump_defs_set (defs_set: &bb_info->in, prefix: ";; rd in ", file);
653	df_rd_dump_defs_set (defs_set: &bb_info->gen, prefix: ";; rd gen ", file);
654	df_rd_dump_defs_set (defs_set: &bb_info->kill, prefix: ";; rd kill", file);
655	}
656
657
658	/ Debugging info at bottom of bb. /
659
660	static void
661	df_rd_bottom_dump (basic_block bb, FILE *file)
662	{
663	class df_rd_bb_info *bb_info = df_rd_get_bb_info (index: bb->index);
664	if (!bb_info)
665	return;
666
667	df_rd_dump_defs_set (defs_set: &bb_info->out, prefix: ";; rd out ", file);
668	}
669
670	/ All of the information associated with every instance of the problem. /
671
672	static const struct df_problem problem_RD =
673	{
674	.id: DF_RD, / Problem id. /
675	.dir: DF_FORWARD, / Direction. /
676	.alloc_fun: df_rd_alloc, / Allocate the problem specific data. /
677	NULL, / Reset global information. /
678	.free_bb_fun: df_rd_free_bb_info, / Free basic block info. /
679	.local_compute_fun: df_rd_local_compute, / Local compute function. /
680	.init_fun: df_rd_init_solution, / Init the solution specific data. /
681	.dataflow_fun: df_worklist_dataflow, / Worklist solver. /
682	NULL, / Confluence operator 0. /
683	.con_fun_n: df_rd_confluence_n, / Confluence operator n. /
684	.trans_fun: df_rd_transfer_function, / Transfer function. /
685	NULL, / Finalize function. /
686	.free_fun: df_rd_free, / Free all of the problem information. /
687	.remove_problem_fun: df_rd_free, / Remove this problem from the stack of dataflow problems. /
688	.dump_start_fun: df_rd_start_dump, / Debugging. /
689	.dump_top_fun: df_rd_top_dump, / Debugging start block. /
690	.dump_bottom_fun: df_rd_bottom_dump, / Debugging end block. /
691	NULL, / Debugging start insn. /
692	NULL, / Debugging end insn. /
693	NULL, / Incremental solution verify start. /
694	NULL, / Incremental solution verify end. /
695	NULL, / Dependent problem. /
696	.block_info_elt_size: sizeof (class df_rd_bb_info),/ Size of entry of block_info array. /
697	.tv_id: TV_DF_RD, / Timing variable. /
698	.free_blocks_on_set_blocks: true / Reset blocks on dropping out of blocks_to_analyze. /
699	};
700
701
702
703	/ Create a new RD instance and add it to the existing instance*
704	of DF. /*
705
706	void
707	df_rd_add_problem (void)
708	{
709	df_add_problem (&problem_RD);
710	}
711
712
713
714	/----------------------------------------------------------------------------*
715	LIVE REGISTERS
716
717	Find the locations in the function where any use of a pseudo can
718	reach in the backwards direction. In and out bitvectors are built
719	for each basic block. The regno is used to index into these sets.
720	See df.h for details.
721	----------------------------------------------------------------------------/*
722
723	/ Private data used to verify the solution for this problem. /
724	struct df_lr_problem_data
725	{
726	bitmap_head *in;
727	bitmap_head *out;
728	/ An obstack for the bitmaps we need for this problem. /
729	bitmap_obstack lr_bitmaps;
730	};
731
732	/ Free basic block info. /
733
734	static void
735	df_lr_free_bb_info (basic_block bb ATTRIBUTE_UNUSED,
736	void *vbb_info)
737	{
738	class df_lr_bb_info bb_info = (class* df_lr_bb_info *) vbb_info;
739	if (bb_info)
740	{
741	bitmap_clear (&bb_info->use);
742	bitmap_clear (&bb_info->def);
743	bitmap_clear (&bb_info->in);
744	bitmap_clear (&bb_info->out);
745	}
746	}
747
748
749	/ Allocate or reset bitmaps for DF_LR blocks. The solution bits are*
750	not touched unless the block is new. /*
751
752	static void
753	df_lr_alloc (bitmap all_blocks ATTRIBUTE_UNUSED)
754	{
755	unsigned int bb_index;
756	bitmap_iterator bi;
757	struct df_lr_problem_data *problem_data;
758
759	df_grow_bb_info (df_lr);
760	if (df_lr->problem_data)
761	problem_data = (struct df_lr_problem_data *) df_lr->problem_data;
762	else
763	{
764	problem_data = XNEW (struct df_lr_problem_data);
765	df_lr->problem_data = problem_data;
766
767	problem_data->out = NULL;
768	problem_data->in = NULL;
769	bitmap_obstack_initialize (&problem_data->lr_bitmaps);
770	}
771
772	EXECUTE_IF_SET_IN_BITMAP (df_lr->out_of_date_transfer_functions, `0`, bb_index, bi)
773	{
774	class df_lr_bb_info *bb_info = df_lr_get_bb_info (index: bb_index);
775
776	/ When bitmaps are already initialized, just clear them. /
777	if (bb_info->use.obstack)
778	{
779	bitmap_clear (&bb_info->def);
780	bitmap_clear (&bb_info->use);
781	}
782	else
783	{
784	bitmap_initialize (head: &bb_info->use, obstack: &problem_data->lr_bitmaps);
785	bitmap_initialize (head: &bb_info->def, obstack: &problem_data->lr_bitmaps);
786	bitmap_initialize (head: &bb_info->in, obstack: &problem_data->lr_bitmaps);
787	bitmap_initialize (head: &bb_info->out, obstack: &problem_data->lr_bitmaps);
788	}
789	}
790
791	df_lr->optional_p = false;
792	}
793
794
795	/ Reset the global solution for recalculation. /
796
797	static void
798	df_lr_reset (bitmap all_blocks)
799	{
800	unsigned int bb_index;
801	bitmap_iterator bi;
802
803	EXECUTE_IF_SET_IN_BITMAP (all_blocks, `0`, bb_index, bi)
804	{
805	class df_lr_bb_info *bb_info = df_lr_get_bb_info (index: bb_index);
806	gcc_assert (bb_info);
807	bitmap_clear (&bb_info->in);
808	bitmap_clear (&bb_info->out);
809	}
810	}
811
812
813	/ Compute local live register info for basic block BB. /
814
815	static void
816	df_lr_bb_local_compute (unsigned int bb_index)
817	{
818	basic_block bb = BASIC_BLOCK_FOR_FN (cfun, bb_index);
819	class df_lr_bb_info *bb_info = df_lr_get_bb_info (index: bb_index);
820	rtx_insn *insn;
821	df_ref def, use;
822
823	/ Process the registers set in an exception handler. /
824	FOR_EACH_ARTIFICIAL_DEF (def, bb_index)
825	if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) == `0`)
826	{
827	unsigned int dregno = DF_REF_REGNO (def);
828	bitmap_set_bit (&bb_info->def, dregno);
829	bitmap_clear_bit (&bb_info->use, dregno);
830	}
831
832	/ Process the hardware registers that are always live. /
833	FOR_EACH_ARTIFICIAL_USE (use, bb_index)
834	/ Add use to set of uses in this BB. /
835	if ((DF_REF_FLAGS (use) & DF_REF_AT_TOP) == `0`)
836	bitmap_set_bit (&bb_info->use, DF_REF_REGNO (use));
837
838	FOR_BB_INSNS_REVERSE (bb, insn)
839	{
840	if (!NONDEBUG_INSN_P (insn))
841	continue;
842
843	df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
844	FOR_EACH_INSN_INFO_DEF (def, insn_info)
845	{
846	/ If the definition is to only part of the register, it will*
847	usually have a corresponding use. For example, stores to one
848	word of a multiword register R have both a use and a partial
849	definition of R.
850
851	In those cases, the LR confluence function:
852
853	IN = (OUT & ~DEF) \| USE
854
855	is unaffected by whether we count the partial definition or not.
856	However, it's more convenient for consumers if DEF contains
857	all the registers defined in a block.
858
859	The only current case in which we record a partial definition
860	without a corresponding use is if the destination is the
861	multi-register subreg of a hard register. An artificial
862	example of this is:
863
864	(set (subreg:TI (reg:V8HI x0) 0) (const_int -1))
865
866	on AArch64. This is described as a DF_REF_PARTIAL
867	definition of x0 and x1 with no corresponding uses.
868	In previous versions of GCC, the instruction had no
869	effect on LR (that is, LR acted as though the instruction
870	didn't exist).
871
872	It seems suspect that this case is treated differently.
873	Either the instruction should be a full definition of x0 and x1,
874	or the definition should be treated in the same way as other
875	partial definitions, such as strict_lowparts or subregs that
876	satisfy read_modify_subreg_p.
877
878	Fortunately, multi-register subregs of hard registers should
879	be rare. They should be folded into a plain REG if the target
880	allows that (as AArch64 does for example above).
881
882	Here we treat the cases alike by forcing a use even in the rare
883	case that no DF_REF_REG_USE is recorded. That is, we model all
884	partial definitions as both a use and a definition of the
885	register. /*
886	unsigned int dregno = DF_REF_REGNO (def);
887	bitmap_set_bit (&bb_info->def, dregno);
888	if (DF_REF_FLAGS (def) & (DF_REF_PARTIAL \| DF_REF_CONDITIONAL))
889	bitmap_set_bit (&bb_info->use, dregno);
890	else
891	bitmap_clear_bit (&bb_info->use, dregno);
892	}
893
894	FOR_EACH_INSN_INFO_USE (use, insn_info)
895	/ Add use to set of uses in this BB. /
896	bitmap_set_bit (&bb_info->use, DF_REF_REGNO (use));
897	}
898
899	/ Process the registers set in an exception handler or the hard*
900	frame pointer if this block is the target of a non local
901	goto. /*
902	FOR_EACH_ARTIFICIAL_DEF (def, bb_index)
903	if (DF_REF_FLAGS (def) & DF_REF_AT_TOP)
904	{
905	unsigned int dregno = DF_REF_REGNO (def);
906	bitmap_set_bit (&bb_info->def, dregno);
907	bitmap_clear_bit (&bb_info->use, dregno);
908	}
909
910	#ifdef EH_USES
911	/ Process the uses that are live into an exception handler. /
912	FOR_EACH_ARTIFICIAL_USE (use, bb_index)
913	/ Add use to set of uses in this BB. /
914	if (DF_REF_FLAGS (use) & DF_REF_AT_TOP)
915	bitmap_set_bit (&bb_info->use, DF_REF_REGNO (use));
916	#endif
917
918	/ If the df_live problem is not defined, such as at -O0 and -O1, we*
919	still need to keep the luids up to date. This is normally done
920	in the df_live problem since this problem has a forwards
921	scan. /*
922	if (!df_live)
923	df_recompute_luids (bb);
924	}
925
926
927	/ Compute local live register info for each basic block within BLOCKS. /
928
929	static void
930	df_lr_local_compute (bitmap all_blocks ATTRIBUTE_UNUSED)
931	{
932	unsigned int bb_index, i;
933	bitmap_iterator bi;
934
935	bitmap_clear (&df->hardware_regs_used);
936
937	/ The all-important stack pointer must always be live. /
938	bitmap_set_bit (&df->hardware_regs_used, STACK_POINTER_REGNUM);
939
940	/ Global regs are always live, too. /
941	for (i = `0`; i < FIRST_PSEUDO_REGISTER; i++)
942	if (global_regs[i])
943	bitmap_set_bit (&df->hardware_regs_used, i);
944
945	/ Before reload, there are a few registers that must be forced*
946	live everywhere -- which might not already be the case for
947	blocks within infinite loops. /*
948	if (!reload_completed)
949	{
950	unsigned int pic_offset_table_regnum = PIC_OFFSET_TABLE_REGNUM;
951	/ Any reference to any pseudo before reload is a potential*
952	reference of the frame pointer. /*
953	bitmap_set_bit (&df->hardware_regs_used, FRAME_POINTER_REGNUM);
954
955	/ Pseudos with argument area equivalences may require*
956	reloading via the argument pointer. /*
957	if (FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
958	&& fixed_regs[ARG_POINTER_REGNUM])
959	bitmap_set_bit (&df->hardware_regs_used, ARG_POINTER_REGNUM);
960
961	/ Any constant, or pseudo with constant equivalences, may*
962	require reloading from memory using the pic register. /*
963	if (pic_offset_table_regnum != INVALID_REGNUM
964	&& fixed_regs[pic_offset_table_regnum])
965	bitmap_set_bit (&df->hardware_regs_used, pic_offset_table_regnum);
966	}
967
968	EXECUTE_IF_SET_IN_BITMAP (df_lr->out_of_date_transfer_functions, `0`, bb_index, bi)
969	{
970	if (bb_index == EXIT_BLOCK)
971	{
972	/ The exit block is special for this problem and its bits are*
973	computed from thin air. /*
974	class df_lr_bb_info *bb_info = df_lr_get_bb_info (EXIT_BLOCK);
975	bitmap_copy (&bb_info->use, df->exit_block_uses);
976	}
977	else
978	df_lr_bb_local_compute (bb_index);
979	}
980
981	bitmap_clear (df_lr->out_of_date_transfer_functions);
982	}
983
984
985	/ Initialize the solution vectors. /
986
987	static void
988	df_lr_init (bitmap all_blocks)
989	{
990	unsigned int bb_index;
991	bitmap_iterator bi;
992
993	EXECUTE_IF_SET_IN_BITMAP (all_blocks, `0`, bb_index, bi)
994	{
995	class df_lr_bb_info *bb_info = df_lr_get_bb_info (index: bb_index);
996	bitmap_copy (&bb_info->in, &bb_info->use);
997	bitmap_clear (&bb_info->out);
998	}
999	}
1000
1001
1002	/ Confluence function that processes infinite loops. This might be a*
1003	noreturn function that throws. And even if it isn't, getting the
1004	unwind info right helps debugging. /*
1005	static void
1006	df_lr_confluence_0 (basic_block bb)
1007	{
1008	bitmap op1 = &df_lr_get_bb_info (index: bb->index)->out;
1009	if (bb != EXIT_BLOCK_PTR_FOR_FN (cfun))
1010	bitmap_copy (op1, &df->hardware_regs_used);
1011	}
1012
1013
1014	/ Confluence function that ignores fake edges. /
1015
1016	static bool
1017	df_lr_confluence_n (edge e)
1018	{
1019	bitmap op1 = &df_lr_get_bb_info (index: e->src->index)->out;
1020	bitmap op2 = &df_lr_get_bb_info (index: e->dest->index)->in;
1021	bool changed = false;
1022
1023	/ Call-clobbered registers die across exception and call edges.*
1024	Conservatively treat partially-clobbered registers as surviving
1025	across the edges; they might or might not, depending on what
1026	mode they have. /*
1027	/ ??? Abnormal call edges ignored for the moment, as this gets*
1028	confused by sibling call edges, which crashes reg-stack. /*
1029	if (e->flags & EDGE_EH)
1030	{
1031	bitmap_view<HARD_REG_SET> eh_kills (eh_edge_abi.full_reg_clobbers ());
1032	changed = bitmap_ior_and_compl_into (A: op1, B: op2, C: eh_kills);
1033	}
1034	else
1035	changed = bitmap_ior_into (op1, op2);
1036
1037	changed \|= bitmap_ior_into (op1, &df->hardware_regs_used);
1038	return changed;
1039	}
1040
1041
1042	/ Transfer function. /
1043
1044	static bool
1045	df_lr_transfer_function (int bb_index)
1046	{
1047	class df_lr_bb_info *bb_info = df_lr_get_bb_info (index: bb_index);
1048	bitmap in = &bb_info->in;
1049	bitmap out = &bb_info->out;
1050	bitmap use = &bb_info->use;
1051	bitmap def = &bb_info->def;
1052
1053	return bitmap_ior_and_compl (DST: in, A: use, B: out, C: def);
1054	}
1055
1056
1057	/ Run the fast dce as a side effect of building LR. /
1058
1059	static void
1060	df_lr_finalize (bitmap all_blocks)
1061	{
1062	df_lr->solutions_dirty = false;
1063	if (df->changeable_flags & DF_LR_RUN_DCE)
1064	{
1065	run_fast_df_dce ();
1066
1067	/ If dce deletes some instructions, we need to recompute the lr*
1068	solution before proceeding further. The problem is that fast
1069	dce is a pessimestic dataflow algorithm. In the case where
1070	it deletes a statement S inside of a loop, the uses inside of
1071	S may not be deleted from the dataflow solution because they
1072	were carried around the loop. While it is conservatively
1073	correct to leave these extra bits, the standards of df
1074	require that we maintain the best possible (least fixed
1075	point) solution. The only way to do that is to redo the
1076	iteration from the beginning. See PR35805 for an
1077	example. /*
1078	if (df_lr->solutions_dirty)
1079	{
1080	df_clear_flags (DF_LR_RUN_DCE);
1081	df_lr_alloc (all_blocks);
1082	df_lr_local_compute (all_blocks);
1083	df_worklist_dataflow (df_lr, all_blocks, df->postorder, df->n_blocks);
1084	df_lr_finalize (all_blocks);
1085	df_set_flags (DF_LR_RUN_DCE);
1086	}
1087	}
1088	}
1089
1090
1091	/ Free all storage associated with the problem. /
1092
1093	static void
1094	df_lr_free (void)
1095	{
1096	struct df_lr_problem_data *problem_data
1097	= (struct df_lr_problem_data *) df_lr->problem_data;
1098	if (df_lr->block_info)
1099	{
1100
1101	df_lr->block_info_size = `0`;
1102	free (df_lr->block_info);
1103	df_lr->block_info = NULL;
1104	bitmap_obstack_release (&problem_data->lr_bitmaps);
1105	free (df_lr->problem_data);
1106	df_lr->problem_data = NULL;
1107	}
1108
1109	BITMAP_FREE (df_lr->out_of_date_transfer_functions);
1110	free (df_lr);
1111	}
1112
1113
1114	/ Debugging info at top of bb. /
1115
1116	static void
1117	df_lr_top_dump (basic_block bb, FILE *file)
1118	{
1119	class df_lr_bb_info *bb_info = df_lr_get_bb_info (index: bb->index);
1120	struct df_lr_problem_data *problem_data;
1121	if (!bb_info)
1122	return;
1123
1124	fprintf (stream: file, format: ";; lr in \t");
1125	df_print_regset (file, r: &bb_info->in);
1126	if (df_lr->problem_data)
1127	{
1128	problem_data = (struct df_lr_problem_data *)df_lr->problem_data;
1129	if (problem_data->in)
1130	{
1131	fprintf (stream: file, format: ";; old in \t");
1132	df_print_regset (file, r: &problem_data->in[bb->index]);
1133	}
1134	}
1135	fprintf (stream: file, format: ";; lr use \t");
1136	df_print_regset (file, r: &bb_info->use);
1137	fprintf (stream: file, format: ";; lr def \t");
1138	df_print_regset (file, r: &bb_info->def);
1139	}
1140
1141
1142	/ Debugging info at bottom of bb. /
1143
1144	static void
1145	df_lr_bottom_dump (basic_block bb, FILE *file)
1146	{
1147	class df_lr_bb_info *bb_info = df_lr_get_bb_info (index: bb->index);
1148	struct df_lr_problem_data *problem_data;
1149	if (!bb_info)
1150	return;
1151
1152	fprintf (stream: file, format: ";; lr out \t");
1153	df_print_regset (file, r: &bb_info->out);
1154	if (df_lr->problem_data)
1155	{
1156	problem_data = (struct df_lr_problem_data *)df_lr->problem_data;
1157	if (problem_data->out)
1158	{
1159	fprintf (stream: file, format: ";; old out \t");
1160	df_print_regset (file, r: &problem_data->out[bb->index]);
1161	}
1162	}
1163	}
1164
1165
1166	/ Build the datastructure to verify that the solution to the dataflow*
1167	equations is not dirty. /*
1168
1169	static void
1170	df_lr_verify_solution_start (void)
1171	{
1172	basic_block bb;
1173	struct df_lr_problem_data *problem_data;
1174	if (df_lr->solutions_dirty)
1175	return;
1176
1177	/ Set it true so that the solution is recomputed. /
1178	df_lr->solutions_dirty = true;
1179
1180	problem_data = (struct df_lr_problem_data *)df_lr->problem_data;
1181	problem_data->in = XNEWVEC (bitmap_head, last_basic_block_for_fn (cfun));
1182	problem_data->out = XNEWVEC (bitmap_head, last_basic_block_for_fn (cfun));
1183
1184	FOR_ALL_BB_FN (bb, cfun)
1185	{
1186	bitmap_initialize (head: &problem_data->in[bb->index], obstack: &problem_data->lr_bitmaps);
1187	bitmap_initialize (head: &problem_data->out[bb->index], obstack: &problem_data->lr_bitmaps);
1188	bitmap_copy (&problem_data->in[bb->index], DF_LR_IN (bb));
1189	bitmap_copy (&problem_data->out[bb->index], DF_LR_OUT (bb));
1190	}
1191	}
1192
1193
1194	/ Compare the saved datastructure and the new solution to the dataflow*
1195	equations. /*
1196
1197	static void
1198	df_lr_verify_solution_end (void)
1199	{
1200	struct df_lr_problem_data *problem_data;
1201	basic_block bb;
1202
1203	problem_data = (struct df_lr_problem_data *)df_lr->problem_data;
1204
1205	if (!problem_data->out)
1206	return;
1207
1208	if (df_lr->solutions_dirty)
1209	/ Do not check if the solution is still dirty. See the comment*
1210	in df_lr_finalize for details. /*
1211	df_lr->solutions_dirty = false;
1212	else
1213	FOR_ALL_BB_FN (bb, cfun)
1214	{
1215	if ((!bitmap_equal_p (&problem_data->in[bb->index], DF_LR_IN (bb)))
1216	\|\| (!bitmap_equal_p (&problem_data->out[bb->index], DF_LR_OUT (bb))))
1217	{
1218	/df_dump (stderr);/
1219	gcc_unreachable ();
1220	}
1221	}
1222
1223	/ Cannot delete them immediately because you may want to dump them*
1224	if the comparison fails. /*
1225	FOR_ALL_BB_FN (bb, cfun)
1226	{
1227	bitmap_clear (&problem_data->in[bb->index]);
1228	bitmap_clear (&problem_data->out[bb->index]);
1229	}
1230
1231	free (ptr: problem_data->in);
1232	free (ptr: problem_data->out);
1233	problem_data->in = NULL;
1234	problem_data->out = NULL;
1235	}
1236
1237
1238	/ All of the information associated with every instance of the problem. /
1239
1240	static const struct df_problem problem_LR =
1241	{
1242	.id: DF_LR, / Problem id. /
1243	.dir: DF_BACKWARD, / Direction. /
1244	.alloc_fun: df_lr_alloc, / Allocate the problem specific data. /
1245	.reset_fun: df_lr_reset, / Reset global information. /
1246	.free_bb_fun: df_lr_free_bb_info, / Free basic block info. /
1247	.local_compute_fun: df_lr_local_compute, / Local compute function. /
1248	.init_fun: df_lr_init, / Init the solution specific data. /
1249	.dataflow_fun: df_worklist_dataflow, / Worklist solver. /
1250	.con_fun_0: df_lr_confluence_0, / Confluence operator 0. /
1251	.con_fun_n: df_lr_confluence_n, / Confluence operator n. /
1252	.trans_fun: df_lr_transfer_function, / Transfer function. /
1253	.finalize_fun: df_lr_finalize, / Finalize function. /
1254	.free_fun: df_lr_free, / Free all of the problem information. /
1255	NULL, / Remove this problem from the stack of dataflow problems. /
1256	NULL, / Debugging. /
1257	.dump_top_fun: df_lr_top_dump, / Debugging start block. /
1258	.dump_bottom_fun: df_lr_bottom_dump, / Debugging end block. /
1259	NULL, / Debugging start insn. /
1260	NULL, / Debugging end insn. /
1261	.verify_start_fun: df_lr_verify_solution_start,/ Incremental solution verify start. /
1262	.verify_end_fun: df_lr_verify_solution_end, / Incremental solution verify end. /
1263	NULL, / Dependent problem. /
1264	.block_info_elt_size: sizeof (class df_lr_bb_info),/ Size of entry of block_info array. /
1265	.tv_id: TV_DF_LR, / Timing variable. /
1266	.free_blocks_on_set_blocks: false / Reset blocks on dropping out of blocks_to_analyze. /
1267	};
1268
1269
1270	/ Create a new DATAFLOW instance and add it to an existing instance*
1271	of DF. The returned structure is what is used to get at the
1272	solution. /*
1273
1274	void
1275	df_lr_add_problem (void)
1276	{
1277	df_add_problem (&problem_LR);
1278	/ These will be initialized when df_scan_blocks processes each*
1279	block. /*
1280	df_lr->out_of_date_transfer_functions = BITMAP_ALLOC (obstack: &df_bitmap_obstack);
1281	}
1282
1283
1284	/ Verify that all of the lr related info is consistent and*
1285	correct. /*
1286
1287	void
1288	df_lr_verify_transfer_functions (void)
1289	{
1290	basic_block bb;
1291	bitmap_head saved_def;
1292	bitmap_head saved_use;
1293	bitmap_head all_blocks;
1294
1295	if (!df)
1296	return;
1297
1298	bitmap_initialize (head: &saved_def, obstack: &bitmap_default_obstack);
1299	bitmap_initialize (head: &saved_use, obstack: &bitmap_default_obstack);
1300	bitmap_initialize (head: &all_blocks, obstack: &bitmap_default_obstack);
1301
1302	FOR_ALL_BB_FN (bb, cfun)
1303	{
1304	class df_lr_bb_info *bb_info = df_lr_get_bb_info (index: bb->index);
1305	bitmap_set_bit (&all_blocks, bb->index);
1306
1307	if (bb_info)
1308	{
1309	/ Make a copy of the transfer functions and then compute*
1310	new ones to see if the transfer functions have
1311	changed. /*
1312	if (!bitmap_bit_p (df_lr->out_of_date_transfer_functions,
1313	bb->index))
1314	{
1315	bitmap_copy (&saved_def, &bb_info->def);
1316	bitmap_copy (&saved_use, &bb_info->use);
1317	bitmap_clear (&bb_info->def);
1318	bitmap_clear (&bb_info->use);
1319
1320	df_lr_bb_local_compute (bb_index: bb->index);
1321	gcc_assert (bitmap_equal_p (&saved_def, &bb_info->def));
1322	gcc_assert (bitmap_equal_p (&saved_use, &bb_info->use));
1323	}
1324	}
1325	else
1326	{
1327	/ If we do not have basic block info, the block must be in*
1328	the list of dirty blocks or else some one has added a
1329	block behind our backs. /*
1330	gcc_assert (bitmap_bit_p (df_lr->out_of_date_transfer_functions,
1331	bb->index));
1332	}
1333	/ Make sure no one created a block without following*
1334	procedures. /*
1335	gcc_assert (df_scan_get_bb_info (bb->index));
1336	}
1337
1338	/ Make sure there are no dirty bits in blocks that have been deleted. /
1339	gcc_assert (!bitmap_intersect_compl_p (df_lr->out_of_date_transfer_functions,
1340	&all_blocks));
1341
1342	bitmap_clear (&saved_def);
1343	bitmap_clear (&saved_use);
1344	bitmap_clear (&all_blocks);
1345	}
1346
1347
1348
1349	/----------------------------------------------------------------------------*
1350	LIVE AND MAY-INITIALIZED REGISTERS.
1351
1352	This problem first computes the IN and OUT bitvectors for the
1353	may-initialized registers problems, which is a forward problem.
1354	It gives the set of registers for which we MAY have an available
1355	definition, i.e. for which there is an available definition on
1356	at least one path from the entry block to the entry/exit of a
1357	basic block. Sets generate a definition, while clobbers kill
1358	a definition.
1359
1360	In and out bitvectors are built for each basic block and are indexed by
1361	regnum (see df.h for details). In and out bitvectors in struct
1362	df_live_bb_info actually refers to the may-initialized problem;
1363
1364	Then, the in and out sets for the LIVE problem itself are computed.
1365	These are the logical AND of the IN and OUT sets from the LR problem
1366	and the may-initialized problem.
1367	----------------------------------------------------------------------------/*
1368
1369	/ Private data used to verify the solution for this problem. /
1370	struct df_live_problem_data
1371	{
1372	bitmap_head *in;
1373	bitmap_head *out;
1374	/ An obstack for the bitmaps we need for this problem. /
1375	bitmap_obstack live_bitmaps;
1376	};
1377
1378	/ Scratch var used by transfer functions. This is used to implement*
1379	an optimization to reduce the amount of space used to compute the
1380	combined lr and live analysis. /*
1381	static bitmap_head df_live_scratch;
1382
1383
1384	/ Free basic block info. /
1385
1386	static void
1387	df_live_free_bb_info (basic_block bb ATTRIBUTE_UNUSED,
1388	void *vbb_info)
1389	{
1390	class df_live_bb_info bb_info = (class* df_live_bb_info *) vbb_info;
1391	if (bb_info)
1392	{
1393	bitmap_clear (&bb_info->gen);
1394	bitmap_clear (&bb_info->kill);
1395	bitmap_clear (&bb_info->in);
1396	bitmap_clear (&bb_info->out);
1397	}
1398	}
1399
1400
1401	/ Allocate or reset bitmaps for DF_LIVE blocks. The solution bits are*
1402	not touched unless the block is new. /*
1403
1404	static void
1405	df_live_alloc (bitmap all_blocks ATTRIBUTE_UNUSED)
1406	{
1407	unsigned int bb_index;
1408	bitmap_iterator bi;
1409	struct df_live_problem_data *problem_data;
1410
1411	if (df_live->problem_data)
1412	problem_data = (struct df_live_problem_data *) df_live->problem_data;
1413	else
1414	{
1415	problem_data = XNEW (struct df_live_problem_data);
1416	df_live->problem_data = problem_data;
1417
1418	problem_data->out = NULL;
1419	problem_data->in = NULL;
1420	bitmap_obstack_initialize (&problem_data->live_bitmaps);
1421	bitmap_initialize (head: &df_live_scratch, obstack: &problem_data->live_bitmaps);
1422	}
1423
1424	df_grow_bb_info (df_live);
1425
1426	EXECUTE_IF_SET_IN_BITMAP (df_live->out_of_date_transfer_functions, `0`, bb_index, bi)
1427	{
1428	class df_live_bb_info *bb_info = df_live_get_bb_info (index: bb_index);
1429
1430	/ When bitmaps are already initialized, just clear them. /
1431	if (bb_info->kill.obstack)
1432	{
1433	bitmap_clear (&bb_info->kill);
1434	bitmap_clear (&bb_info->gen);
1435	}
1436	else
1437	{
1438	bitmap_initialize (head: &bb_info->kill, obstack: &problem_data->live_bitmaps);
1439	bitmap_initialize (head: &bb_info->gen, obstack: &problem_data->live_bitmaps);
1440	bitmap_initialize (head: &bb_info->in, obstack: &problem_data->live_bitmaps);
1441	bitmap_initialize (head: &bb_info->out, obstack: &problem_data->live_bitmaps);
1442	}
1443	}
1444	df_live->optional_p = (optimize <= `1`);
1445	}
1446
1447
1448	/ Reset the global solution for recalculation. /
1449
1450	static void
1451	df_live_reset (bitmap all_blocks)
1452	{
1453	unsigned int bb_index;
1454	bitmap_iterator bi;
1455
1456	EXECUTE_IF_SET_IN_BITMAP (all_blocks, `0`, bb_index, bi)
1457	{
1458	class df_live_bb_info *bb_info = df_live_get_bb_info (index: bb_index);
1459	gcc_assert (bb_info);
1460	bitmap_clear (&bb_info->in);
1461	bitmap_clear (&bb_info->out);
1462	}
1463	}
1464
1465
1466	/ Compute local uninitialized register info for basic block BB. /
1467
1468	static void
1469	df_live_bb_local_compute (unsigned int bb_index)
1470	{
1471	basic_block bb = BASIC_BLOCK_FOR_FN (cfun, bb_index);
1472	class df_live_bb_info *bb_info = df_live_get_bb_info (index: bb_index);
1473	rtx_insn *insn;
1474	df_ref def;
1475	int luid = `0`;
1476
1477	FOR_BB_INSNS (bb, insn)
1478	{
1479	unsigned int uid = INSN_UID (insn);
1480	struct df_insn_info *insn_info = DF_INSN_UID_GET (uid);
1481
1482	/ Inserting labels does not always trigger the incremental*
1483	rescanning. /*
1484	if (!insn_info)
1485	{
1486	gcc_assert (!INSN_P (insn));
1487	insn_info = df_insn_create_insn_record (insn);
1488	}
1489
1490	DF_INSN_INFO_LUID (insn_info) = luid;
1491	if (!INSN_P (insn))
1492	continue;
1493
1494	luid++;
1495	FOR_EACH_INSN_INFO_DEF (def, insn_info)
1496	{
1497	unsigned int regno = DF_REF_REGNO (def);
1498
1499	if (DF_REF_FLAGS_IS_SET (def,
1500	DF_REF_PARTIAL \| DF_REF_CONDITIONAL))
1501	/ All partial or conditional def*
1502	seen are included in the gen set. /*
1503	bitmap_set_bit (&bb_info->gen, regno);
1504	else if (DF_REF_FLAGS_IS_SET (def, DF_REF_MUST_CLOBBER))
1505	/ Only must clobbers for the entire reg destroy the*
1506	value. /*
1507	bitmap_set_bit (&bb_info->kill, regno);
1508	else if (! DF_REF_FLAGS_IS_SET (def, DF_REF_MAY_CLOBBER))
1509	bitmap_set_bit (&bb_info->gen, regno);
1510	}
1511	}
1512
1513	FOR_EACH_ARTIFICIAL_DEF (def, bb_index)
1514	bitmap_set_bit (&bb_info->gen, DF_REF_REGNO (def));
1515	}
1516
1517
1518	/ Compute local uninitialized register info. /
1519
1520	static void
1521	df_live_local_compute (bitmap all_blocks ATTRIBUTE_UNUSED)
1522	{
1523	unsigned int bb_index;
1524	bitmap_iterator bi;
1525
1526	df_grow_insn_info ();
1527
1528	EXECUTE_IF_SET_IN_BITMAP (df_live->out_of_date_transfer_functions,
1529	`0`, bb_index, bi)
1530	{
1531	df_live_bb_local_compute (bb_index);
1532	}
1533
1534	bitmap_clear (df_live->out_of_date_transfer_functions);
1535	}
1536
1537
1538	/ Initialize the solution vectors. /
1539
1540	static void
1541	df_live_init (bitmap all_blocks)
1542	{
1543	unsigned int bb_index;
1544	bitmap_iterator bi;
1545
1546	EXECUTE_IF_SET_IN_BITMAP (all_blocks, `0`, bb_index, bi)
1547	{
1548	class df_live_bb_info *bb_info = df_live_get_bb_info (index: bb_index);
1549	class df_lr_bb_info *bb_lr_info = df_lr_get_bb_info (index: bb_index);
1550
1551	/ No register may reach a location where it is not used. Thus*
1552	we trim the rr result to the places where it is used. /*
1553	bitmap_and (&bb_info->out, &bb_info->gen, &bb_lr_info->out);
1554	bitmap_clear (&bb_info->in);
1555	}
1556	}
1557
1558	/ Forward confluence function that ignores fake edges. /
1559
1560	static bool
1561	df_live_confluence_n (edge e)
1562	{
1563	bitmap op1 = &df_live_get_bb_info (index: e->dest->index)->in;
1564	bitmap op2 = &df_live_get_bb_info (index: e->src->index)->out;
1565
1566	if (e->flags & EDGE_FAKE)
1567	return false;
1568
1569	return bitmap_ior_into (op1, op2);
1570	}
1571
1572
1573	/ Transfer function for the forwards may-initialized problem. /
1574
1575	static bool
1576	df_live_transfer_function (int bb_index)
1577	{
1578	class df_live_bb_info *bb_info = df_live_get_bb_info (index: bb_index);
1579	class df_lr_bb_info *bb_lr_info = df_lr_get_bb_info (index: bb_index);
1580	bitmap in = &bb_info->in;
1581	bitmap out = &bb_info->out;
1582	bitmap gen = &bb_info->gen;
1583	bitmap kill = &bb_info->kill;
1584
1585	/ We need to use a scratch set here so that the value returned from this*
1586	function invocation properly reflects whether the sets changed in a
1587	significant way; i.e. not just because the lr set was anded in. /*
1588	bitmap_and (&df_live_scratch, gen, &bb_lr_info->out);
1589	/ No register may reach a location where it is not used. Thus*
1590	we trim the rr result to the places where it is used. /*
1591	bitmap_and_into (in, &bb_lr_info->in);
1592
1593	return bitmap_ior_and_compl (DST: out, A: &df_live_scratch, B: in, C: kill);
1594	}
1595
1596
1597	/ And the LR info with the may-initialized registers to produce the LIVE info. /
1598
1599	static void
1600	df_live_finalize (bitmap all_blocks)
1601	{
1602
1603	if (df_live->solutions_dirty)
1604	{
1605	bitmap_iterator bi;
1606	unsigned int bb_index;
1607
1608	EXECUTE_IF_SET_IN_BITMAP (all_blocks, `0`, bb_index, bi)
1609	{
1610	class df_lr_bb_info *bb_lr_info = df_lr_get_bb_info (index: bb_index);
1611	class df_live_bb_info *bb_live_info = df_live_get_bb_info (index: bb_index);
1612
1613	/ No register may reach a location where it is not used. Thus*
1614	we trim the rr result to the places where it is used. /*
1615	bitmap_and_into (&bb_live_info->in, &bb_lr_info->in);
1616	bitmap_and_into (&bb_live_info->out, &bb_lr_info->out);
1617	}
1618
1619	df_live->solutions_dirty = false;
1620	}
1621	}
1622
1623
1624	/ Free all storage associated with the problem. /
1625
1626	static void
1627	df_live_free (void)
1628	{
1629	struct df_live_problem_data *problem_data
1630	= (struct df_live_problem_data *) df_live->problem_data;
1631	if (df_live->block_info)
1632	{
1633	df_live->block_info_size = `0`;
1634	free (df_live->block_info);
1635	df_live->block_info = NULL;
1636	bitmap_release (head: &df_live_scratch);
1637	bitmap_obstack_release (&problem_data->live_bitmaps);
1638	free (ptr: problem_data);
1639	df_live->problem_data = NULL;
1640	}
1641	BITMAP_FREE (df_live->out_of_date_transfer_functions);
1642	free (df_live);
1643	}
1644
1645
1646	/ Debugging info at top of bb. /
1647
1648	static void
1649	df_live_top_dump (basic_block bb, FILE *file)
1650	{
1651	class df_live_bb_info *bb_info = df_live_get_bb_info (index: bb->index);
1652	struct df_live_problem_data *problem_data;
1653
1654	if (!bb_info)
1655	return;
1656
1657	fprintf (stream: file, format: ";; live in \t");
1658	df_print_regset (file, r: &bb_info->in);
1659	if (df_live->problem_data)
1660	{
1661	problem_data = (struct df_live_problem_data *)df_live->problem_data;
1662	if (problem_data->in)
1663	{
1664	fprintf (stream: file, format: ";; old in \t");
1665	df_print_regset (file, r: &problem_data->in[bb->index]);
1666	}
1667	}
1668	fprintf (stream: file, format: ";; live gen \t");
1669	df_print_regset (file, r: &bb_info->gen);
1670	fprintf (stream: file, format: ";; live kill\t");
1671	df_print_regset (file, r: &bb_info->kill);
1672	}
1673
1674
1675	/ Debugging info at bottom of bb. /
1676
1677	static void
1678	df_live_bottom_dump (basic_block bb, FILE *file)
1679	{
1680	class df_live_bb_info *bb_info = df_live_get_bb_info (index: bb->index);
1681	struct df_live_problem_data *problem_data;
1682
1683	if (!bb_info)
1684	return;
1685
1686	fprintf (stream: file, format: ";; live out \t");
1687	df_print_regset (file, r: &bb_info->out);
1688	if (df_live->problem_data)
1689	{
1690	problem_data = (struct df_live_problem_data *)df_live->problem_data;
1691	if (problem_data->out)
1692	{
1693	fprintf (stream: file, format: ";; old out \t");
1694	df_print_regset (file, r: &problem_data->out[bb->index]);
1695	}
1696	}
1697	}
1698
1699
1700	/ Build the datastructure to verify that the solution to the dataflow*
1701	equations is not dirty. /*
1702
1703	static void
1704	df_live_verify_solution_start (void)
1705	{
1706	basic_block bb;
1707	struct df_live_problem_data *problem_data;
1708	if (df_live->solutions_dirty)
1709	return;
1710
1711	/ Set it true so that the solution is recomputed. /
1712	df_live->solutions_dirty = true;
1713
1714	problem_data = (struct df_live_problem_data *)df_live->problem_data;
1715	problem_data->in = XNEWVEC (bitmap_head, last_basic_block_for_fn (cfun));
1716	problem_data->out = XNEWVEC (bitmap_head, last_basic_block_for_fn (cfun));
1717
1718	FOR_ALL_BB_FN (bb, cfun)
1719	{
1720	bitmap_initialize (head: &problem_data->in[bb->index], obstack: &problem_data->live_bitmaps);
1721	bitmap_initialize (head: &problem_data->out[bb->index], obstack: &problem_data->live_bitmaps);
1722	bitmap_copy (&problem_data->in[bb->index], DF_LIVE_IN (bb));
1723	bitmap_copy (&problem_data->out[bb->index], DF_LIVE_OUT (bb));
1724	}
1725	}
1726
1727
1728	/ Compare the saved datastructure and the new solution to the dataflow*
1729	equations. /*
1730
1731	static void
1732	df_live_verify_solution_end (void)
1733	{
1734	struct df_live_problem_data *problem_data;
1735	basic_block bb;
1736
1737	problem_data = (struct df_live_problem_data *)df_live->problem_data;
1738	if (!problem_data->out)
1739	return;
1740
1741	FOR_ALL_BB_FN (bb, cfun)
1742	{
1743	if ((!bitmap_equal_p (&problem_data->in[bb->index], DF_LIVE_IN (bb)))
1744	\|\| (!bitmap_equal_p (&problem_data->out[bb->index], DF_LIVE_OUT (bb))))
1745	{
1746	/df_dump (stderr);/
1747	gcc_unreachable ();
1748	}
1749	}
1750
1751	/ Cannot delete them immediately because you may want to dump them*
1752	if the comparison fails. /*
1753	FOR_ALL_BB_FN (bb, cfun)
1754	{
1755	bitmap_clear (&problem_data->in[bb->index]);
1756	bitmap_clear (&problem_data->out[bb->index]);
1757	}
1758
1759	free (ptr: problem_data->in);
1760	free (ptr: problem_data->out);
1761	free (ptr: problem_data);
1762	df_live->problem_data = NULL;
1763	}
1764
1765
1766	/ All of the information associated with every instance of the problem. /
1767
1768	static const struct df_problem problem_LIVE =
1769	{
1770	.id: DF_LIVE, / Problem id. /
1771	.dir: DF_FORWARD, / Direction. /
1772	.alloc_fun: df_live_alloc, / Allocate the problem specific data. /
1773	.reset_fun: df_live_reset, / Reset global information. /
1774	.free_bb_fun: df_live_free_bb_info, / Free basic block info. /
1775	.local_compute_fun: df_live_local_compute, / Local compute function. /
1776	.init_fun: df_live_init, / Init the solution specific data. /
1777	.dataflow_fun: df_worklist_dataflow, / Worklist solver. /
1778	NULL, / Confluence operator 0. /
1779	.con_fun_n: df_live_confluence_n, / Confluence operator n. /
1780	.trans_fun: df_live_transfer_function, / Transfer function. /
1781	.finalize_fun: df_live_finalize, / Finalize function. /
1782	.free_fun: df_live_free, / Free all of the problem information. /
1783	.remove_problem_fun: df_live_free, / Remove this problem from the stack of dataflow problems. /
1784	NULL, / Debugging. /
1785	.dump_top_fun: df_live_top_dump, / Debugging start block. /
1786	.dump_bottom_fun: df_live_bottom_dump, / Debugging end block. /
1787	NULL, / Debugging start insn. /
1788	NULL, / Debugging end insn. /
1789	.verify_start_fun: df_live_verify_solution_start,/ Incremental solution verify start. /
1790	.verify_end_fun: df_live_verify_solution_end, / Incremental solution verify end. /
1791	.dependent_problem: &problem_LR, / Dependent problem. /
1792	.block_info_elt_size: sizeof (class df_live_bb_info),/ Size of entry of block_info array. /
1793	.tv_id: TV_DF_LIVE, / Timing variable. /
1794	.free_blocks_on_set_blocks: false / Reset blocks on dropping out of blocks_to_analyze. /
1795	};
1796
1797
1798	/ Create a new DATAFLOW instance and add it to an existing instance*
1799	of DF. The returned structure is what is used to get at the
1800	solution. /*
1801
1802	void
1803	df_live_add_problem (void)
1804	{
1805	df_add_problem (&problem_LIVE);
1806	/ These will be initialized when df_scan_blocks processes each*
1807	block. /*
1808	df_live->out_of_date_transfer_functions = BITMAP_ALLOC (obstack: &df_bitmap_obstack);
1809	}
1810
1811
1812	/ Set all of the blocks as dirty. This needs to be done if this*
1813	problem is added after all of the insns have been scanned. /*
1814
1815	void
1816	df_live_set_all_dirty (void)
1817	{
1818	basic_block bb;
1819	FOR_ALL_BB_FN (bb, cfun)
1820	bitmap_set_bit (df_live->out_of_date_transfer_functions,
1821	bb->index);
1822	}
1823
1824
1825	/ Verify that all of the lr related info is consistent and*
1826	correct. /*
1827
1828	void
1829	df_live_verify_transfer_functions (void)
1830	{
1831	basic_block bb;
1832	bitmap_head saved_gen;
1833	bitmap_head saved_kill;
1834	bitmap_head all_blocks;
1835
1836	if (!df)
1837	return;
1838
1839	bitmap_initialize (head: &saved_gen, obstack: &bitmap_default_obstack);
1840	bitmap_initialize (head: &saved_kill, obstack: &bitmap_default_obstack);
1841	bitmap_initialize (head: &all_blocks, obstack: &bitmap_default_obstack);
1842
1843	df_grow_insn_info ();
1844
1845	FOR_ALL_BB_FN (bb, cfun)
1846	{
1847	class df_live_bb_info *bb_info = df_live_get_bb_info (index: bb->index);
1848	bitmap_set_bit (&all_blocks, bb->index);
1849
1850	if (bb_info)
1851	{
1852	/ Make a copy of the transfer functions and then compute*
1853	new ones to see if the transfer functions have
1854	changed. /*
1855	if (!bitmap_bit_p (df_live->out_of_date_transfer_functions,
1856	bb->index))
1857	{
1858	bitmap_copy (&saved_gen, &bb_info->gen);
1859	bitmap_copy (&saved_kill, &bb_info->kill);
1860	bitmap_clear (&bb_info->gen);
1861	bitmap_clear (&bb_info->kill);
1862
1863	df_live_bb_local_compute (bb_index: bb->index);
1864	gcc_assert (bitmap_equal_p (&saved_gen, &bb_info->gen));
1865	gcc_assert (bitmap_equal_p (&saved_kill, &bb_info->kill));
1866	}
1867	}
1868	else
1869	{
1870	/ If we do not have basic block info, the block must be in*
1871	the list of dirty blocks or else some one has added a
1872	block behind our backs. /*
1873	gcc_assert (bitmap_bit_p (df_live->out_of_date_transfer_functions,
1874	bb->index));
1875	}
1876	/ Make sure no one created a block without following*
1877	procedures. /*
1878	gcc_assert (df_scan_get_bb_info (bb->index));
1879	}
1880
1881	/ Make sure there are no dirty bits in blocks that have been deleted. /
1882	gcc_assert (!bitmap_intersect_compl_p (df_live->out_of_date_transfer_functions,
1883	&all_blocks));
1884	bitmap_clear (&saved_gen);
1885	bitmap_clear (&saved_kill);
1886	bitmap_clear (&all_blocks);
1887	}
1888
1889	/----------------------------------------------------------------------------*
1890	MUST-INITIALIZED REGISTERS.
1891	----------------------------------------------------------------------------/*
1892
1893	/ Private data used to verify the solution for this problem. /
1894	struct df_mir_problem_data
1895	{
1896	bitmap_head *in;
1897	bitmap_head *out;
1898	/ An obstack for the bitmaps we need for this problem. /
1899	bitmap_obstack mir_bitmaps;
1900	};
1901
1902
1903	/ Free basic block info. /
1904
1905	static void
1906	df_mir_free_bb_info (basic_block bb ATTRIBUTE_UNUSED,
1907	void *vbb_info)
1908	{
1909	class df_mir_bb_info bb_info = (class* df_mir_bb_info *) vbb_info;
1910	if (bb_info)
1911	{
1912	bitmap_clear (&bb_info->gen);
1913	bitmap_clear (&bb_info->kill);
1914	bitmap_clear (&bb_info->in);
1915	bitmap_clear (&bb_info->out);
1916	}
1917	}
1918
1919
1920	/ Allocate or reset bitmaps for DF_MIR blocks. The solution bits are*
1921	not touched unless the block is new. /*
1922
1923	static void
1924	df_mir_alloc (bitmap all_blocks)
1925	{
1926	unsigned int bb_index;
1927	bitmap_iterator bi;
1928	struct df_mir_problem_data *problem_data;
1929
1930	if (df_mir->problem_data)
1931	problem_data = (struct df_mir_problem_data *) df_mir->problem_data;
1932	else
1933	{
1934	problem_data = XNEW (struct df_mir_problem_data);
1935	df_mir->problem_data = problem_data;
1936
1937	problem_data->out = NULL;
1938	problem_data->in = NULL;
1939	bitmap_obstack_initialize (&problem_data->mir_bitmaps);
1940	}
1941
1942	df_grow_bb_info (df_mir);
1943
1944	EXECUTE_IF_SET_IN_BITMAP (all_blocks, `0`, bb_index, bi)
1945	{
1946	class df_mir_bb_info *bb_info = df_mir_get_bb_info (index: bb_index);
1947
1948	/ When bitmaps are already initialized, just clear them. /
1949	if (bb_info->kill.obstack)
1950	{
1951	bitmap_clear (&bb_info->kill);
1952	bitmap_clear (&bb_info->gen);
1953	}
1954	else
1955	{
1956	bitmap_initialize (head: &bb_info->kill, obstack: &problem_data->mir_bitmaps);
1957	bitmap_initialize (head: &bb_info->gen, obstack: &problem_data->mir_bitmaps);
1958	bitmap_initialize (head: &bb_info->in, obstack: &problem_data->mir_bitmaps);
1959	bitmap_initialize (head: &bb_info->out, obstack: &problem_data->mir_bitmaps);
1960	bb_info->con_visited = false;
1961	}
1962	}
1963
1964	df_mir->optional_p = `1`;
1965	}
1966
1967
1968	/ Reset the global solution for recalculation. /
1969
1970	static void
1971	df_mir_reset (bitmap all_blocks)
1972	{
1973	unsigned int bb_index;
1974	bitmap_iterator bi;
1975
1976	EXECUTE_IF_SET_IN_BITMAP (all_blocks, `0`, bb_index, bi)
1977	{
1978	class df_mir_bb_info *bb_info = df_mir_get_bb_info (index: bb_index);
1979
1980	gcc_assert (bb_info);
1981
1982	bitmap_clear (&bb_info->in);
1983	bitmap_clear (&bb_info->out);
1984	bb_info->con_visited = false;
1985	}
1986	}
1987
1988
1989	/ Compute local uninitialized register info for basic block BB. /
1990
1991	static void
1992	df_mir_bb_local_compute (unsigned int bb_index)
1993	{
1994	basic_block bb = BASIC_BLOCK_FOR_FN (cfun, bb_index);
1995	class df_mir_bb_info *bb_info = df_mir_get_bb_info (index: bb_index);
1996	rtx_insn *insn;
1997	int luid = `0`;
1998
1999	/ Ignoring artificial defs is intentional: these often pretend that some*
2000	registers carry incoming arguments (when they are FUNCTION_ARG_REGNO) even
2001	though they are not used for that. As a result, conservatively assume
2002	they may be uninitialized. /*
2003
2004	FOR_BB_INSNS (bb, insn)
2005	{
2006	unsigned int uid = INSN_UID (insn);
2007	struct df_insn_info *insn_info = DF_INSN_UID_GET (uid);
2008
2009	/ Inserting labels does not always trigger the incremental*
2010	rescanning. /*
2011	if (!insn_info)
2012	{
2013	gcc_assert (!INSN_P (insn));
2014	insn_info = df_insn_create_insn_record (insn);
2015	}
2016
2017	DF_INSN_INFO_LUID (insn_info) = luid;
2018	if (!INSN_P (insn))
2019	continue;
2020
2021	luid++;
2022	df_mir_simulate_one_insn (bb, insn, &bb_info->kill, &bb_info->gen);
2023	}
2024	}
2025
2026
2027	/ Compute local uninitialized register info. /
2028
2029	static void
2030	df_mir_local_compute (bitmap all_blocks)
2031	{
2032	unsigned int bb_index;
2033	bitmap_iterator bi;
2034
2035	df_grow_insn_info ();
2036
2037	EXECUTE_IF_SET_IN_BITMAP (all_blocks, `0`, bb_index, bi)
2038	{
2039	df_mir_bb_local_compute (bb_index);
2040	}
2041	}
2042
2043
2044	/ Initialize the solution vectors. /
2045
2046	static void
2047	df_mir_init (bitmap all_blocks)
2048	{
2049	df_mir_reset (all_blocks);
2050	}
2051
2052
2053	/ Initialize IN sets for blocks with no predecessors: when landing on such*
2054	blocks, assume all registers are uninitialized. /*
2055
2056	static void
2057	df_mir_confluence_0 (basic_block bb)
2058	{
2059	class df_mir_bb_info *bb_info = df_mir_get_bb_info (index: bb->index);
2060
2061	bitmap_clear (&bb_info->in);
2062	bb_info->con_visited = true;
2063	}
2064
2065
2066	/ Forward confluence function that ignores fake edges. /
2067
2068	static bool
2069	df_mir_confluence_n (edge e)
2070	{
2071	if (e->flags & EDGE_FAKE)
2072	return false;
2073
2074	df_mir_bb_info *src_info = df_mir_get_bb_info (index: e->src->index);
2075	/ If SRC was not visited yet then we'll and with all-ones which*
2076	means no changes. Do not consider DST con_visited by this
2077	operation alone either. /*
2078	if (!src_info->con_visited)
2079	return false;
2080
2081	df_mir_bb_info *dst_info = df_mir_get_bb_info (index: e->dest->index);
2082	bitmap op1 = &dst_info->in;
2083	bitmap op2 = &src_info->out;
2084	/ If DEST was not visited yet just copy the SRC bitmap. /
2085	if (!dst_info->con_visited)
2086	{
2087	dst_info->con_visited = true;
2088	bitmap_copy (op1, op2);
2089	return true;
2090	}
2091
2092	/ A register is must-initialized at the entry of a basic block iff it is*
2093	must-initialized at the exit of all the predecessors. /*
2094	return bitmap_and_into (op1, op2);
2095	}
2096
2097
2098	/ Transfer function for the forwards must-initialized problem. /
2099
2100	static bool
2101	df_mir_transfer_function (int bb_index)
2102	{
2103	class df_mir_bb_info *bb_info = df_mir_get_bb_info (index: bb_index);
2104	bitmap in = &bb_info->in;
2105	bitmap out = &bb_info->out;
2106	bitmap gen = &bb_info->gen;
2107	bitmap kill = &bb_info->kill;
2108
2109	return bitmap_ior_and_compl (DST: out, A: gen, B: in, C: kill);
2110	}
2111
2112
2113	/ Free all storage associated with the problem. /
2114
2115	static void
2116	df_mir_free (void)
2117	{
2118	struct df_mir_problem_data *problem_data
2119	= (struct df_mir_problem_data *) df_mir->problem_data;
2120	if (df_mir->block_info)
2121	{
2122	df_mir->block_info_size = `0`;
2123	free (df_mir->block_info);
2124	df_mir->block_info = NULL;
2125	bitmap_obstack_release (&problem_data->mir_bitmaps);
2126	free (ptr: problem_data);
2127	df_mir->problem_data = NULL;
2128	}
2129	free (df_mir);
2130	}
2131
2132
2133	/ Debugging info at top of bb. /
2134
2135	static void
2136	df_mir_top_dump (basic_block bb, FILE *file)
2137	{
2138	class df_mir_bb_info *bb_info = df_mir_get_bb_info (index: bb->index);
2139
2140	if (!bb_info)
2141	return;
2142
2143	fprintf (stream: file, format: ";; mir in \t");
2144	df_print_regset (file, r: &bb_info->in);
2145	fprintf (stream: file, format: ";; mir kill\t");
2146	df_print_regset (file, r: &bb_info->kill);
2147	fprintf (stream: file, format: ";; mir gen \t");
2148	df_print_regset (file, r: &bb_info->gen);
2149	}
2150
2151	/ Debugging info at bottom of bb. /
2152
2153	static void
2154	df_mir_bottom_dump (basic_block bb, FILE *file)
2155	{
2156	class df_mir_bb_info *bb_info = df_mir_get_bb_info (index: bb->index);
2157
2158	if (!bb_info)
2159	return;
2160
2161	fprintf (stream: file, format: ";; mir out \t");
2162	df_print_regset (file, r: &bb_info->out);
2163	}
2164
2165
2166	/ Build the datastructure to verify that the solution to the dataflow*
2167	equations is not dirty. /*
2168
2169	static void
2170	df_mir_verify_solution_start (void)
2171	{
2172	basic_block bb;
2173	struct df_mir_problem_data *problem_data;
2174	if (df_mir->solutions_dirty)
2175	return;
2176
2177	/ Set it true so that the solution is recomputed. /
2178	df_mir->solutions_dirty = true;
2179
2180	problem_data = (struct df_mir_problem_data *) df_mir->problem_data;
2181	problem_data->in = XNEWVEC (bitmap_head, last_basic_block_for_fn (cfun));
2182	problem_data->out = XNEWVEC (bitmap_head, last_basic_block_for_fn (cfun));
2183	bitmap_obstack_initialize (&problem_data->mir_bitmaps);
2184
2185	FOR_ALL_BB_FN (bb, cfun)
2186	{
2187	bitmap_initialize (head: &problem_data->in[bb->index], obstack: &problem_data->mir_bitmaps);
2188	bitmap_initialize (head: &problem_data->out[bb->index], obstack: &problem_data->mir_bitmaps);
2189	bitmap_copy (&problem_data->in[bb->index], DF_MIR_IN (bb));
2190	bitmap_copy (&problem_data->out[bb->index], DF_MIR_OUT (bb));
2191	}
2192	}
2193
2194
2195	/ Compare the saved datastructure and the new solution to the dataflow*
2196	equations. /*
2197
2198	static void
2199	df_mir_verify_solution_end (void)
2200	{
2201	struct df_mir_problem_data *problem_data;
2202	basic_block bb;
2203
2204	problem_data = (struct df_mir_problem_data *) df_mir->problem_data;
2205	if (!problem_data->out)
2206	return;
2207
2208	FOR_ALL_BB_FN (bb, cfun)
2209	{
2210	if ((!bitmap_equal_p (&problem_data->in[bb->index], DF_MIR_IN (bb)))
2211	\|\| (!bitmap_equal_p (&problem_data->out[bb->index], DF_MIR_OUT (bb))))
2212	gcc_unreachable ();
2213	}
2214
2215	/ Cannot delete them immediately because you may want to dump them*
2216	if the comparison fails. /*
2217	FOR_ALL_BB_FN (bb, cfun)
2218	{
2219	bitmap_clear (&problem_data->in[bb->index]);
2220	bitmap_clear (&problem_data->out[bb->index]);
2221	}
2222
2223	free (ptr: problem_data->in);
2224	free (ptr: problem_data->out);
2225	bitmap_obstack_release (&problem_data->mir_bitmaps);
2226	free (ptr: problem_data);
2227	df_mir->problem_data = NULL;
2228	}
2229
2230
2231	/ All of the information associated with every instance of the problem. /
2232
2233	static const struct df_problem problem_MIR =
2234	{
2235	.id: DF_MIR, / Problem id. /
2236	.dir: DF_FORWARD, / Direction. /
2237	.alloc_fun: df_mir_alloc, / Allocate the problem specific data. /
2238	.reset_fun: df_mir_reset, / Reset global information. /
2239	.free_bb_fun: df_mir_free_bb_info, / Free basic block info. /
2240	.local_compute_fun: df_mir_local_compute, / Local compute function. /
2241	.init_fun: df_mir_init, / Init the solution specific data. /
2242	.dataflow_fun: df_worklist_dataflow, / Worklist solver. /
2243	.con_fun_0: df_mir_confluence_0, / Confluence operator 0. /
2244	.con_fun_n: df_mir_confluence_n, / Confluence operator n. /
2245	.trans_fun: df_mir_transfer_function, / Transfer function. /
2246	NULL, / Finalize function. /
2247	.free_fun: df_mir_free, / Free all of the problem information. /
2248	.remove_problem_fun: df_mir_free, / Remove this problem from the stack of dataflow problems. /
2249	NULL, / Debugging. /
2250	.dump_top_fun: df_mir_top_dump, / Debugging start block. /
2251	.dump_bottom_fun: df_mir_bottom_dump, / Debugging end block. /
2252	NULL, / Debugging start insn. /
2253	NULL, / Debugging end insn. /
2254	.verify_start_fun: df_mir_verify_solution_start, / Incremental solution verify start. /
2255	.verify_end_fun: df_mir_verify_solution_end, / Incremental solution verify end. /
2256	NULL, / Dependent problem. /
2257	.block_info_elt_size: sizeof (class df_mir_bb_info),/ Size of entry of block_info array. /
2258	.tv_id: TV_DF_MIR, / Timing variable. /
2259	.free_blocks_on_set_blocks: false / Reset blocks on dropping out of blocks_to_analyze. /
2260	};
2261
2262
2263	/ Create a new DATAFLOW instance and add it to an existing instance*
2264	of DF. /*
2265
2266	void
2267	df_mir_add_problem (void)
2268	{
2269	df_add_problem (&problem_MIR);
2270	/ These will be initialized when df_scan_blocks processes each*
2271	block. /*
2272	df_mir->out_of_date_transfer_functions = BITMAP_ALLOC (obstack: &df_bitmap_obstack);
2273	}
2274
2275
2276	/ Apply the effects of the gen/kills in INSN to the corresponding bitmaps. /
2277
2278	void
2279	df_mir_simulate_one_insn (basic_block bb ATTRIBUTE_UNUSED, rtx_insn *insn,
2280	bitmap kill, bitmap gen)
2281	{
2282	df_ref def;
2283
2284	FOR_EACH_INSN_DEF (def, insn)
2285	{
2286	unsigned int regno = DF_REF_REGNO (def);
2287
2288	/ The order of GENs/KILLs matters, so if this def clobbers a reg, any*
2289	previous gen is irrelevant (and reciprocally). Also, claim that a
2290	register is GEN only if it is in all cases. /*
2291	if (DF_REF_FLAGS_IS_SET (def, DF_REF_MUST_CLOBBER \| DF_REF_MAY_CLOBBER))
2292	{
2293	bitmap_set_bit (kill, regno);
2294	bitmap_clear_bit (gen, regno);
2295	}
2296	/ In the worst case, partial and conditional defs can leave bits*
2297	uninitialized, so assume they do not change anything. /*
2298	else if (!DF_REF_FLAGS_IS_SET (def, DF_REF_PARTIAL \| DF_REF_CONDITIONAL))
2299	{
2300	bitmap_set_bit (gen, regno);
2301	bitmap_clear_bit (kill, regno);
2302	}
2303	}
2304	}
2305
2306	/----------------------------------------------------------------------------*
2307	CREATE DEF_USE (DU) and / or USE_DEF (UD) CHAINS
2308
2309	Link either the defs to the uses and / or the uses to the defs.
2310
2311	These problems are set up like the other dataflow problems so that
2312	they nicely fit into the framework. They are much simpler and only
2313	involve a single traversal of instructions and an examination of
2314	the reaching defs information (the dependent problem).
2315	----------------------------------------------------------------------------/*
2316
2317	#define df_chain_problem_p(FLAG) (((enum df_chain_flags)df_chain->local_flags)&(FLAG))
2318
2319	/ Create a du or ud chain from SRC to DST and link it into SRC. /
2320
2321	struct df_link *
2322	df_chain_create (df_ref src, df_ref dst)
2323	{
2324	struct df_link *head = DF_REF_CHAIN (src);
2325	struct df_link *link = df_chain->block_pool->allocate ();
2326
2327	DF_REF_CHAIN (src) = link;
2328	link->next = head;
2329	link->ref = dst;
2330	return link;
2331	}
2332
2333
2334	/ Delete any du or ud chains that start at REF and point to*
2335	TARGET. /*
2336	static void
2337	df_chain_unlink_1 (df_ref ref, df_ref target)
2338	{
2339	struct df_link *chain = DF_REF_CHAIN (ref);
2340	struct df_link *prev = NULL;
2341
2342	while (chain)
2343	{
2344	if (chain->ref == target)
2345	{
2346	if (prev)
2347	prev->next = chain->next;
2348	else
2349	DF_REF_CHAIN (ref) = chain->next;
2350	df_chain->block_pool->remove (object: chain);
2351	return;
2352	}
2353	prev = chain;
2354	chain = chain->next;
2355	}
2356	}
2357
2358
2359	/ Delete a du or ud chain that leave or point to REF. /
2360
2361	void
2362	df_chain_unlink (df_ref ref)
2363	{
2364	struct df_link *chain = DF_REF_CHAIN (ref);
2365	while (chain)
2366	{
2367	struct df_link *next = chain->next;
2368	/ Delete the other side if it exists. /
2369	df_chain_unlink_1 (ref: chain->ref, target: ref);
2370	df_chain->block_pool->remove (object: chain);
2371	chain = next;
2372	}
2373	DF_REF_CHAIN (ref) = NULL;
2374	}
2375
2376
2377	/ Copy the du or ud chain starting at FROM_REF and attach it to*
2378	TO_REF. /*
2379
2380	void
2381	df_chain_copy (df_ref to_ref,
2382	struct df_link *from_ref)
2383	{
2384	while (from_ref)
2385	{
2386	df_chain_create (src: to_ref, dst: from_ref->ref);
2387	from_ref = from_ref->next;
2388	}
2389	}
2390
2391
2392	/ Remove this problem from the stack of dataflow problems. /
2393
2394	static void
2395	df_chain_remove_problem (void)
2396	{
2397	bitmap_iterator bi;
2398	unsigned int bb_index;
2399
2400	/ Wholesale destruction of the old chains. /
2401	if (df_chain->block_pool)
2402	delete df_chain->block_pool;
2403
2404	EXECUTE_IF_SET_IN_BITMAP (df_chain->out_of_date_transfer_functions, `0`, bb_index, bi)
2405	{
2406	rtx_insn *insn;
2407	df_ref def, use;
2408	basic_block bb = BASIC_BLOCK_FOR_FN (cfun, bb_index);
2409
2410	if (df_chain_problem_p (DF_DU_CHAIN))
2411	FOR_EACH_ARTIFICIAL_DEF (def, bb_index)
2412	DF_REF_CHAIN (def) = NULL;
2413	if (df_chain_problem_p (DF_UD_CHAIN))
2414	FOR_EACH_ARTIFICIAL_USE (use, bb_index)
2415	DF_REF_CHAIN (use) = NULL;
2416
2417	FOR_BB_INSNS (bb, insn)
2418	if (INSN_P (insn))
2419	{
2420	df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
2421	if (df_chain_problem_p (DF_DU_CHAIN))
2422	FOR_EACH_INSN_INFO_DEF (def, insn_info)
2423	DF_REF_CHAIN (def) = NULL;
2424	if (df_chain_problem_p (DF_UD_CHAIN))
2425	{
2426	FOR_EACH_INSN_INFO_USE (use, insn_info)
2427	DF_REF_CHAIN (use) = NULL;
2428	FOR_EACH_INSN_INFO_EQ_USE (use, insn_info)
2429	DF_REF_CHAIN (use) = NULL;
2430	}
2431	}
2432	}
2433
2434	bitmap_clear (df_chain->out_of_date_transfer_functions);
2435	df_chain->block_pool = NULL;
2436	}
2437
2438
2439	/ Remove the chain problem completely. /
2440
2441	static void
2442	df_chain_fully_remove_problem (void)
2443	{
2444	df_chain_remove_problem ();
2445	BITMAP_FREE (df_chain->out_of_date_transfer_functions);
2446	free (df_chain);
2447	}
2448
2449
2450	/ Create def-use or use-def chains. /
2451
2452	static void
2453	df_chain_alloc (bitmap all_blocks ATTRIBUTE_UNUSED)
2454	{
2455	df_chain_remove_problem ();
2456	df_chain->block_pool = new object_allocator<df_link> ("df_chain_block pool");
2457	df_chain->optional_p = true;
2458	}
2459
2460
2461	/ Reset all of the chains when the set of basic blocks changes. /
2462
2463	static void
2464	df_chain_reset (bitmap blocks_to_clear ATTRIBUTE_UNUSED)
2465	{
2466	df_chain_remove_problem ();
2467	}
2468
2469
2470	/ Create the chains for a list of USEs. /
2471
2472	static void
2473	df_chain_create_bb_process_use (bitmap local_rd,
2474	df_ref use,
2475	int top_flag)
2476	{
2477	bitmap_iterator bi;
2478	unsigned int def_index;
2479
2480	for (; use; use = DF_REF_NEXT_LOC (use))
2481	{
2482	unsigned int uregno = DF_REF_REGNO (use);
2483	if ((!(df->changeable_flags & DF_NO_HARD_REGS))
2484	\|\| (uregno >= FIRST_PSEUDO_REGISTER))
2485	{
2486	/ Do not want to go through this for an uninitialized var. /
2487	int count = DF_DEFS_COUNT (uregno);
2488	if (count)
2489	{
2490	if (top_flag == (DF_REF_FLAGS (use) & DF_REF_AT_TOP))
2491	{
2492	unsigned int first_index = DF_DEFS_BEGIN (uregno);
2493	unsigned int last_index = first_index + count - `1`;
2494
2495	EXECUTE_IF_SET_IN_BITMAP (local_rd, first_index, def_index, bi)
2496	{
2497	df_ref def;
2498	if (def_index > last_index)
2499	break;
2500
2501	def = DF_DEFS_GET (def_index);
2502	if (df_chain_problem_p (DF_DU_CHAIN))
2503	df_chain_create (src: def, dst: use);
2504	if (df_chain_problem_p (DF_UD_CHAIN))
2505	df_chain_create (src: use, dst: def);
2506	}
2507	}
2508	}
2509	}
2510	}
2511	}
2512
2513
2514	/ Create chains from reaching defs bitmaps for basic block BB. /
2515
2516	static void
2517	df_chain_create_bb (unsigned int bb_index)
2518	{
2519	basic_block bb = BASIC_BLOCK_FOR_FN (cfun, bb_index);
2520	class df_rd_bb_info *bb_info = df_rd_get_bb_info (index: bb_index);
2521	rtx_insn *insn;
2522	bitmap_head cpy;
2523
2524	bitmap_initialize (head: &cpy, obstack: &bitmap_default_obstack);
2525	bitmap_copy (&cpy, &bb_info->in);
2526	bitmap_set_bit (df_chain->out_of_date_transfer_functions, bb_index);
2527
2528	/ Since we are going forwards, process the artificial uses first*
2529	then the artificial defs second. /*
2530
2531	#ifdef EH_USES
2532	/ Create the chains for the artificial uses from the EH_USES at the*
2533	beginning of the block. /*
2534
2535	/ Artificials are only hard regs. /
2536	if (!(df->changeable_flags & DF_NO_HARD_REGS))
2537	df_chain_create_bb_process_use (&cpy,
2538	df_get_artificial_uses (bb->index),
2539	DF_REF_AT_TOP);
2540	#endif
2541
2542	df_rd_simulate_artificial_defs_at_top (bb, local_rd: &cpy);
2543
2544	/ Process the regular instructions next. /
2545	FOR_BB_INSNS (bb, insn)
2546	if (INSN_P (insn))
2547	{
2548	unsigned int uid = INSN_UID (insn);
2549
2550	/ First scan the uses and link them up with the defs that remain*
2551	in the cpy vector. /*
2552	df_chain_create_bb_process_use (local_rd: &cpy, DF_INSN_UID_USES (uid), top_flag: `0`);
2553	if (df->changeable_flags & DF_EQ_NOTES)
2554	df_chain_create_bb_process_use (local_rd: &cpy, DF_INSN_UID_EQ_USES (uid), top_flag: `0`);
2555
2556	/ Since we are going forwards, process the defs second. /
2557	df_rd_simulate_one_insn (bb, insn, local_rd: &cpy);
2558	}
2559
2560	/ Create the chains for the artificial uses of the hard registers*
2561	at the end of the block. /*
2562	if (!(df->changeable_flags & DF_NO_HARD_REGS))
2563	df_chain_create_bb_process_use (local_rd: &cpy,
2564	use: df_get_artificial_uses (bb_index: bb->index),
2565	top_flag: `0`);
2566
2567	bitmap_clear (&cpy);
2568	}
2569
2570	/ Create def-use chains from reaching use bitmaps for basic blocks*
2571	in BLOCKS. /*
2572
2573	static void
2574	df_chain_finalize (bitmap all_blocks)
2575	{
2576	unsigned int bb_index;
2577	bitmap_iterator bi;
2578
2579	EXECUTE_IF_SET_IN_BITMAP (all_blocks, `0`, bb_index, bi)
2580	{
2581	df_chain_create_bb (bb_index);
2582	}
2583	}
2584
2585
2586	/ Free all storage associated with the problem. /
2587
2588	static void
2589	df_chain_free (void)
2590	{
2591	delete df_chain->block_pool;
2592	BITMAP_FREE (df_chain->out_of_date_transfer_functions);
2593	free (df_chain);
2594	}
2595
2596
2597	/ Debugging info. /
2598
2599	static void
2600	df_chain_bb_dump (basic_block bb, FILE file, bool* top)
2601	{
2602	/ Artificials are only hard regs. /
2603	if (df->changeable_flags & DF_NO_HARD_REGS)
2604	return;
2605	if (df_chain_problem_p (DF_UD_CHAIN))
2606	{
2607	df_ref use;
2608
2609	fprintf (stream: file,
2610	format: ";; UD chains for artificial uses at %s\n",
2611	top ? "top" : "bottom");
2612	FOR_EACH_ARTIFICIAL_USE (use, bb->index)
2613	if ((top && (DF_REF_FLAGS (use) & DF_REF_AT_TOP))
2614	\|\| (!top && !(DF_REF_FLAGS (use) & DF_REF_AT_TOP)))
2615	{
2616	fprintf (stream: file, format: ";; reg %d ", DF_REF_REGNO (use));
2617	df_chain_dump (DF_REF_CHAIN (use), file);
2618	fprintf (stream: file, format: "\n");
2619	}
2620	}
2621	if (df_chain_problem_p (DF_DU_CHAIN))
2622	{
2623	df_ref def;
2624
2625	fprintf (stream: file,
2626	format: ";; DU chains for artificial defs at %s\n",
2627	top ? "top" : "bottom");
2628	FOR_EACH_ARTIFICIAL_DEF (def, bb->index)
2629	if ((top && (DF_REF_FLAGS (def) & DF_REF_AT_TOP))
2630	\|\| (!top && !(DF_REF_FLAGS (def) & DF_REF_AT_TOP)))
2631	{
2632	fprintf (stream: file, format: ";; reg %d ", DF_REF_REGNO (def));
2633	df_chain_dump (DF_REF_CHAIN (def), file);
2634	fprintf (stream: file, format: "\n");
2635	}
2636	}
2637	}
2638
2639	static void
2640	df_chain_top_dump (basic_block bb, FILE *file)
2641	{
2642	df_chain_bb_dump (bb, file, /top=/true);
2643	}
2644
2645	static void
2646	df_chain_bottom_dump (basic_block bb, FILE *file)
2647	{
2648	df_chain_bb_dump (bb, file, /top=/false);
2649	}
2650
2651	static void
2652	df_chain_insn_top_dump (const rtx_insn insn, FILE file)
2653	{
2654	if (df_chain_problem_p (DF_UD_CHAIN) && INSN_P (insn))
2655	{
2656	struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
2657	df_ref use;
2658
2659	fprintf (stream: file, format: ";; UD chains for insn luid %d uid %d\n",
2660	DF_INSN_INFO_LUID (insn_info), INSN_UID (insn));
2661	FOR_EACH_INSN_INFO_USE (use, insn_info)
2662	if (!HARD_REGISTER_NUM_P (DF_REF_REGNO (use))
2663	\|\| !(df->changeable_flags & DF_NO_HARD_REGS))
2664	{
2665	fprintf (stream: file, format: ";; reg %d ", DF_REF_REGNO (use));
2666	if (DF_REF_FLAGS (use) & DF_REF_READ_WRITE)
2667	fprintf (stream: file, format: "read/write ");
2668	df_chain_dump (DF_REF_CHAIN (use), file);
2669	fprintf (stream: file, format: "\n");
2670	}
2671	FOR_EACH_INSN_INFO_EQ_USE (use, insn_info)
2672	if (!HARD_REGISTER_NUM_P (DF_REF_REGNO (use))
2673	\|\| !(df->changeable_flags & DF_NO_HARD_REGS))
2674	{
2675	fprintf (stream: file, format: ";; eq_note reg %d ", DF_REF_REGNO (use));
2676	df_chain_dump (DF_REF_CHAIN (use), file);
2677	fprintf (stream: file, format: "\n");
2678	}
2679	}
2680	}
2681
2682	static void
2683	df_chain_insn_bottom_dump (const rtx_insn insn, FILE file)
2684	{
2685	if (df_chain_problem_p (DF_DU_CHAIN) && INSN_P (insn))
2686	{
2687	struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
2688	df_ref def;
2689	fprintf (stream: file, format: ";; DU chains for insn luid %d uid %d\n",
2690	DF_INSN_INFO_LUID (insn_info), INSN_UID (insn));
2691	FOR_EACH_INSN_INFO_DEF (def, insn_info)
2692	if (!HARD_REGISTER_NUM_P (DF_REF_REGNO (def))
2693	\|\| !(df->changeable_flags & DF_NO_HARD_REGS))
2694	{
2695	fprintf (stream: file, format: ";; reg %d ", DF_REF_REGNO (def));
2696	if (DF_REF_FLAGS (def) & DF_REF_READ_WRITE)
2697	fprintf (stream: file, format: "read/write ");
2698	df_chain_dump (DF_REF_CHAIN (def), file);
2699	fprintf (stream: file, format: "\n");
2700	}
2701	fprintf (stream: file, format: "\n");
2702	}
2703	}
2704
2705	static const struct df_problem problem_CHAIN =
2706	{
2707	.id: DF_CHAIN, / Problem id. /
2708	.dir: DF_NONE, / Direction. /
2709	.alloc_fun: df_chain_alloc, / Allocate the problem specific data. /
2710	.reset_fun: df_chain_reset, / Reset global information. /
2711	NULL, / Free basic block info. /
2712	NULL, / Local compute function. /
2713	NULL, / Init the solution specific data. /
2714	NULL, / Iterative solver. /
2715	NULL, / Confluence operator 0. /
2716	NULL, / Confluence operator n. /
2717	NULL, / Transfer function. /
2718	.finalize_fun: df_chain_finalize, / Finalize function. /
2719	.free_fun: df_chain_free, / Free all of the problem information. /
2720	.remove_problem_fun: df_chain_fully_remove_problem,/ Remove this problem from the stack of dataflow problems. /
2721	NULL, / Debugging. /
2722	.dump_top_fun: df_chain_top_dump, / Debugging start block. /
2723	.dump_bottom_fun: df_chain_bottom_dump, / Debugging end block. /
2724	.dump_insn_top_fun: df_chain_insn_top_dump, / Debugging start insn. /
2725	.dump_insn_bottom_fun: df_chain_insn_bottom_dump, / Debugging end insn. /
2726	NULL, / Incremental solution verify start. /
2727	NULL, / Incremental solution verify end. /
2728	.dependent_problem: &problem_RD, / Dependent problem. /
2729	.block_info_elt_size: sizeof (struct df_scan_bb_info),/ Size of entry of block_info array. /
2730	.tv_id: TV_DF_CHAIN, / Timing variable. /
2731	.free_blocks_on_set_blocks: false / Reset blocks on dropping out of blocks_to_analyze. /
2732	};
2733
2734
2735	/ Create a new DATAFLOW instance and add it to an existing instance*
2736	of DF. The returned structure is what is used to get at the
2737	solution. /*
2738
2739	void
2740	df_chain_add_problem (unsigned int chain_flags)
2741	{
2742	df_add_problem (&problem_CHAIN);
2743	df_chain->local_flags = chain_flags;
2744	df_chain->out_of_date_transfer_functions = BITMAP_ALLOC (obstack: &df_bitmap_obstack);
2745	}
2746
2747	#undef df_chain_problem_p
2748
2749
2750	/----------------------------------------------------------------------------*
2751	WORD LEVEL LIVE REGISTERS
2752
2753	Find the locations in the function where any use of a pseudo can
2754	reach in the backwards direction. In and out bitvectors are built
2755	for each basic block. We only track pseudo registers that have a
2756	size of 2 UNITS_PER_WORD; bitmaps are indexed by 2 * regno and*
2757	contain two bits corresponding to each of the subwords.
2758
2759	----------------------------------------------------------------------------/*
2760
2761	/ Private data used to verify the solution for this problem. /
2762	struct df_word_lr_problem_data
2763	{
2764	/ An obstack for the bitmaps we need for this problem. /
2765	bitmap_obstack word_lr_bitmaps;
2766	};
2767
2768
2769	/ Free basic block info. /
2770
2771	static void
2772	df_word_lr_free_bb_info (basic_block bb ATTRIBUTE_UNUSED,
2773	void *vbb_info)
2774	{
2775	class df_word_lr_bb_info bb_info = (class* df_word_lr_bb_info *) vbb_info;
2776	if (bb_info)
2777	{
2778	bitmap_clear (&bb_info->use);
2779	bitmap_clear (&bb_info->def);
2780	bitmap_clear (&bb_info->in);
2781	bitmap_clear (&bb_info->out);
2782	}
2783	}
2784
2785
2786	/ Allocate or reset bitmaps for DF_WORD_LR blocks. The solution bits are*
2787	not touched unless the block is new. /*
2788
2789	static void
2790	df_word_lr_alloc (bitmap all_blocks ATTRIBUTE_UNUSED)
2791	{
2792	unsigned int bb_index;
2793	bitmap_iterator bi;
2794	basic_block bb;
2795	struct df_word_lr_problem_data *problem_data
2796	= XNEW (struct df_word_lr_problem_data);
2797
2798	df_word_lr->problem_data = problem_data;
2799
2800	df_grow_bb_info (df_word_lr);
2801
2802	/ Create the mapping from regnos to slots. This does not change*
2803	unless the problem is destroyed and recreated. In particular, if
2804	we end up deleting the only insn that used a subreg, we do not
2805	want to redo the mapping because this would invalidate everything
2806	else. /*
2807
2808	bitmap_obstack_initialize (&problem_data->word_lr_bitmaps);
2809
2810	FOR_EACH_BB_FN (bb, cfun)
2811	bitmap_set_bit (df_word_lr->out_of_date_transfer_functions, bb->index);
2812
2813	bitmap_set_bit (df_word_lr->out_of_date_transfer_functions, ENTRY_BLOCK);
2814	bitmap_set_bit (df_word_lr->out_of_date_transfer_functions, EXIT_BLOCK);
2815
2816	EXECUTE_IF_SET_IN_BITMAP (df_word_lr->out_of_date_transfer_functions, `0`, bb_index, bi)
2817	{
2818	class df_word_lr_bb_info *bb_info = df_word_lr_get_bb_info (index: bb_index);
2819
2820	/ When bitmaps are already initialized, just clear them. /
2821	if (bb_info->use.obstack)
2822	{
2823	bitmap_clear (&bb_info->def);
2824	bitmap_clear (&bb_info->use);
2825	}
2826	else
2827	{
2828	bitmap_initialize (head: &bb_info->use, obstack: &problem_data->word_lr_bitmaps);
2829	bitmap_initialize (head: &bb_info->def, obstack: &problem_data->word_lr_bitmaps);
2830	bitmap_initialize (head: &bb_info->in, obstack: &problem_data->word_lr_bitmaps);
2831	bitmap_initialize (head: &bb_info->out, obstack: &problem_data->word_lr_bitmaps);
2832	}
2833	}
2834
2835	df_word_lr->optional_p = true;
2836	}
2837
2838
2839	/ Reset the global solution for recalculation. /
2840
2841	static void
2842	df_word_lr_reset (bitmap all_blocks)
2843	{
2844	unsigned int bb_index;
2845	bitmap_iterator bi;
2846
2847	EXECUTE_IF_SET_IN_BITMAP (all_blocks, `0`, bb_index, bi)
2848	{
2849	class df_word_lr_bb_info *bb_info = df_word_lr_get_bb_info (index: bb_index);
2850	gcc_assert (bb_info);
2851	bitmap_clear (&bb_info->in);
2852	bitmap_clear (&bb_info->out);
2853	}
2854	}
2855
2856	/ Examine REF, and if it is for a reg we're interested in, set or*
2857	clear the bits corresponding to its subwords from the bitmap
2858	according to IS_SET. LIVE is the bitmap we should update. We do
2859	not track hard regs or pseudos of any size other than 2 *
2860	UNITS_PER_WORD.
2861	We return true if we changed the bitmap, or if we encountered a register
2862	we're not tracking. /*
2863
2864	bool
2865	df_word_lr_mark_ref (df_ref ref, bool is_set, regset live)
2866	{
2867	rtx orig_reg = DF_REF_REG (ref);
2868	rtx reg = orig_reg;
2869	machine_mode reg_mode;
2870	unsigned regno;
2871	/ Left at -1 for whole accesses. /
2872	int which_subword = -`1`;
2873	bool changed = false;
2874
2875	if (GET_CODE (reg) == SUBREG)
2876	reg = SUBREG_REG (orig_reg);
2877	regno = REGNO (reg);
2878	reg_mode = GET_MODE (reg);
2879	if (regno < FIRST_PSEUDO_REGISTER
2880	\|\| maybe_ne (a: GET_MODE_SIZE (mode: reg_mode), b: `2` * UNITS_PER_WORD))
2881	return true;
2882
2883	if (GET_CODE (orig_reg) == SUBREG
2884	&& read_modify_subreg_p (orig_reg))
2885	{
2886	gcc_assert (DF_REF_FLAGS_IS_SET (ref, DF_REF_PARTIAL));
2887	if (subreg_lowpart_p (orig_reg))
2888	which_subword = `0`;
2889	else
2890	which_subword = `1`;
2891	}
2892	if (is_set)
2893	{
2894	if (which_subword != `1`)
2895	changed \|= bitmap_set_bit (live, regno * `2`);
2896	if (which_subword != `0`)
2897	changed \|= bitmap_set_bit (live, regno * `2` + `1`);
2898	}
2899	else
2900	{
2901	if (which_subword != `1`)
2902	changed \|= bitmap_clear_bit (live, regno * `2`);
2903	if (which_subword != `0`)
2904	changed \|= bitmap_clear_bit (live, regno * `2` + `1`);
2905	}
2906	return changed;
2907	}
2908
2909	/ Compute local live register info for basic block BB. /
2910
2911	static void
2912	df_word_lr_bb_local_compute (unsigned int bb_index)
2913	{
2914	basic_block bb = BASIC_BLOCK_FOR_FN (cfun, bb_index);
2915	class df_word_lr_bb_info *bb_info = df_word_lr_get_bb_info (index: bb_index);
2916	rtx_insn *insn;
2917	df_ref def, use;
2918
2919	/ Ensure that artificial refs don't contain references to pseudos. /
2920	FOR_EACH_ARTIFICIAL_DEF (def, bb_index)
2921	gcc_assert (DF_REF_REGNO (def) < FIRST_PSEUDO_REGISTER);
2922
2923	FOR_EACH_ARTIFICIAL_USE (use, bb_index)
2924	gcc_assert (DF_REF_REGNO (use) < FIRST_PSEUDO_REGISTER);
2925
2926	FOR_BB_INSNS_REVERSE (bb, insn)
2927	{
2928	if (!NONDEBUG_INSN_P (insn))
2929	continue;
2930
2931	df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
2932	FOR_EACH_INSN_INFO_DEF (def, insn_info)
2933	/ If the def is to only part of the reg, it does*
2934	not kill the other defs that reach here. /*
2935	if (!(DF_REF_FLAGS (def) & (DF_REF_CONDITIONAL)))
2936	{
2937	df_word_lr_mark_ref (ref: def, is_set: true, live: &bb_info->def);
2938	df_word_lr_mark_ref (ref: def, is_set: false, live: &bb_info->use);
2939	}
2940	FOR_EACH_INSN_INFO_USE (use, insn_info)
2941	df_word_lr_mark_ref (ref: use, is_set: true, live: &bb_info->use);
2942	}
2943	}
2944
2945
2946	/ Compute local live register info for each basic block within BLOCKS. /
2947
2948	static void
2949	df_word_lr_local_compute (bitmap all_blocks ATTRIBUTE_UNUSED)
2950	{
2951	unsigned int bb_index;
2952	bitmap_iterator bi;
2953
2954	EXECUTE_IF_SET_IN_BITMAP (df_word_lr->out_of_date_transfer_functions, `0`, bb_index, bi)
2955	{
2956	if (bb_index == EXIT_BLOCK)
2957	{
2958	unsigned regno;
2959	bitmap_iterator bi;
2960	EXECUTE_IF_SET_IN_BITMAP (df->exit_block_uses, FIRST_PSEUDO_REGISTER,
2961	regno, bi)
2962	gcc_unreachable ();
2963	}
2964	else
2965	df_word_lr_bb_local_compute (bb_index);
2966	}
2967
2968	bitmap_clear (df_word_lr->out_of_date_transfer_functions);
2969	}
2970
2971
2972	/ Initialize the solution vectors. /
2973
2974	static void
2975	df_word_lr_init (bitmap all_blocks)
2976	{
2977	unsigned int bb_index;
2978	bitmap_iterator bi;
2979
2980	EXECUTE_IF_SET_IN_BITMAP (all_blocks, `0`, bb_index, bi)
2981	{
2982	class df_word_lr_bb_info *bb_info = df_word_lr_get_bb_info (index: bb_index);
2983	bitmap_copy (&bb_info->in, &bb_info->use);
2984	bitmap_clear (&bb_info->out);
2985	}
2986	}
2987
2988
2989	/ Confluence function that ignores fake edges. /
2990
2991	static bool
2992	df_word_lr_confluence_n (edge e)
2993	{
2994	bitmap op1 = &df_word_lr_get_bb_info (index: e->src->index)->out;
2995	bitmap op2 = &df_word_lr_get_bb_info (index: e->dest->index)->in;
2996
2997	return bitmap_ior_into (op1, op2);
2998	}
2999
3000
3001	/ Transfer function. /
3002
3003	static bool
3004	df_word_lr_transfer_function (int bb_index)
3005	{
3006	class df_word_lr_bb_info *bb_info = df_word_lr_get_bb_info (index: bb_index);
3007	bitmap in = &bb_info->in;
3008	bitmap out = &bb_info->out;
3009	bitmap use = &bb_info->use;
3010	bitmap def = &bb_info->def;
3011
3012	return bitmap_ior_and_compl (DST: in, A: use, B: out, C: def);
3013	}
3014
3015
3016	/ Free all storage associated with the problem. /
3017
3018	static void
3019	df_word_lr_free (void)
3020	{
3021	struct df_word_lr_problem_data *problem_data
3022	= (struct df_word_lr_problem_data *)df_word_lr->problem_data;
3023
3024	if (df_word_lr->block_info)
3025	{
3026	df_word_lr->block_info_size = `0`;
3027	free (df_word_lr->block_info);
3028	df_word_lr->block_info = NULL;
3029	}
3030
3031	BITMAP_FREE (df_word_lr->out_of_date_transfer_functions);
3032	bitmap_obstack_release (&problem_data->word_lr_bitmaps);
3033	free (ptr: problem_data);
3034	free (df_word_lr);
3035	}
3036
3037
3038	/ Debugging info at top of bb. /
3039
3040	static void
3041	df_word_lr_top_dump (basic_block bb, FILE *file)
3042	{
3043	class df_word_lr_bb_info *bb_info = df_word_lr_get_bb_info (index: bb->index);
3044	if (!bb_info)
3045	return;
3046
3047	fprintf (stream: file, format: ";; blr in \t");
3048	df_print_word_regset (file, r: &bb_info->in);
3049	fprintf (stream: file, format: ";; blr use \t");
3050	df_print_word_regset (file, r: &bb_info->use);
3051	fprintf (stream: file, format: ";; blr def \t");
3052	df_print_word_regset (file, r: &bb_info->def);
3053	}
3054
3055
3056	/ Debugging info at bottom of bb. /
3057
3058	static void
3059	df_word_lr_bottom_dump (basic_block bb, FILE *file)
3060	{
3061	class df_word_lr_bb_info *bb_info = df_word_lr_get_bb_info (index: bb->index);
3062	if (!bb_info)
3063	return;
3064
3065	fprintf (stream: file, format: ";; blr out \t");
3066	df_print_word_regset (file, r: &bb_info->out);
3067	}
3068
3069
3070	/ All of the information associated with every instance of the problem. /
3071
3072	static const struct df_problem problem_WORD_LR =
3073	{
3074	.id: DF_WORD_LR, / Problem id. /
3075	.dir: DF_BACKWARD, / Direction. /
3076	.alloc_fun: df_word_lr_alloc, / Allocate the problem specific data. /
3077	.reset_fun: df_word_lr_reset, / Reset global information. /
3078	.free_bb_fun: df_word_lr_free_bb_info, / Free basic block info. /
3079	.local_compute_fun: df_word_lr_local_compute, / Local compute function. /
3080	.init_fun: df_word_lr_init, / Init the solution specific data. /
3081	.dataflow_fun: df_worklist_dataflow, / Worklist solver. /
3082	NULL, / Confluence operator 0. /
3083	.con_fun_n: df_word_lr_confluence_n, / Confluence operator n. /
3084	.trans_fun: df_word_lr_transfer_function, / Transfer function. /
3085	NULL, / Finalize function. /
3086	.free_fun: df_word_lr_free, / Free all of the problem information. /
3087	.remove_problem_fun: df_word_lr_free, / Remove this problem from the stack of dataflow problems. /
3088	NULL, / Debugging. /
3089	.dump_top_fun: df_word_lr_top_dump, / Debugging start block. /
3090	.dump_bottom_fun: df_word_lr_bottom_dump, / Debugging end block. /
3091	NULL, / Debugging start insn. /
3092	NULL, / Debugging end insn. /
3093	NULL, / Incremental solution verify start. /
3094	NULL, / Incremental solution verify end. /
3095	NULL, / Dependent problem. /
3096	.block_info_elt_size: sizeof (class df_word_lr_bb_info),/ Size of entry of block_info array. /
3097	.tv_id: TV_DF_WORD_LR, / Timing variable. /
3098	.free_blocks_on_set_blocks: false / Reset blocks on dropping out of blocks_to_analyze. /
3099	};
3100
3101
3102	/ Create a new DATAFLOW instance and add it to an existing instance*
3103	of DF. The returned structure is what is used to get at the
3104	solution. /*
3105
3106	void
3107	df_word_lr_add_problem (void)
3108	{
3109	df_add_problem (&problem_WORD_LR);
3110	/ These will be initialized when df_scan_blocks processes each*
3111	block. /*
3112	df_word_lr->out_of_date_transfer_functions = BITMAP_ALLOC (obstack: &df_bitmap_obstack);
3113	}
3114
3115
3116	/ Simulate the effects of the defs of INSN on LIVE. Return true if we changed*
3117	any bits, which is used by the caller to determine whether a set is
3118	necessary. We also return true if there are other reasons not to delete
3119	an insn. /*
3120
3121	bool
3122	df_word_lr_simulate_defs (rtx_insn *insn, bitmap live)
3123	{
3124	bool changed = false;
3125	df_ref def;
3126
3127	FOR_EACH_INSN_DEF (def, insn)
3128	if (DF_REF_FLAGS (def) & DF_REF_CONDITIONAL)
3129	changed = true;
3130	else
3131	changed \|= df_word_lr_mark_ref (ref: def, is_set: false, live);
3132	return changed;
3133	}
3134
3135
3136	/ Simulate the effects of the uses of INSN on LIVE. /
3137
3138	void
3139	df_word_lr_simulate_uses (rtx_insn *insn, bitmap live)
3140	{
3141	df_ref use;
3142
3143	FOR_EACH_INSN_USE (use, insn)
3144	df_word_lr_mark_ref (ref: use, is_set: true, live);
3145	}
3146
3147	/----------------------------------------------------------------------------*
3148	This problem computes REG_DEAD and REG_UNUSED notes.
3149	----------------------------------------------------------------------------/*
3150
3151	static void
3152	df_note_alloc (bitmap all_blocks ATTRIBUTE_UNUSED)
3153	{
3154	df_note->optional_p = true;
3155	}
3156
3157	/ This is only used if REG_DEAD_DEBUGGING is in effect. /
3158	static void
3159	df_print_note (const char prefix, rtx_insn insn, rtx note)
3160	{
3161	if (dump_file)
3162	{
3163	fprintf (stream: dump_file, format: "%s %d ", prefix, INSN_UID (insn));
3164	print_rtl (dump_file, note);
3165	fprintf (stream: dump_file, format: "\n");
3166	}
3167	}
3168
3169
3170	/ After reg-stack, the x86 floating point stack regs are difficult to*
3171	analyze because of all of the pushes, pops and rotations. Thus, we
3172	just leave the notes alone. /*
3173
3174	#ifdef STACK_REGS
3175	static inline bool
3176	df_ignore_stack_reg (int regno)
3177	{
3178	return regstack_completed
3179	&& IN_RANGE (regno, FIRST_STACK_REG, LAST_STACK_REG);
3180	}
3181	#else
3182	static inline bool
3183	df_ignore_stack_reg (int regno ATTRIBUTE_UNUSED)
3184	{
3185	return false;
3186	}
3187	#endif
3188
3189
3190	/ Remove all of the REG_DEAD or REG_UNUSED notes from INSN. /
3191
3192	static void
3193	df_remove_dead_and_unused_notes (rtx_insn *insn)
3194	{
3195	rtx *pprev = &REG_NOTES (insn);
3196	rtx link = *pprev;
3197
3198	while (link)
3199	{
3200	switch (REG_NOTE_KIND (link))
3201	{
3202	case REG_DEAD:
3203	/ After reg-stack, we need to ignore any unused notes*
3204	for the stack registers. /*
3205	if (df_ignore_stack_reg (REGNO (XEXP (link, `0`))))
3206	{
3207	pprev = &XEXP (link, `1`);
3208	link = *pprev;
3209	}
3210	else
3211	{
3212	rtx next = XEXP (link, `1`);
3213	if (REG_DEAD_DEBUGGING)
3214	df_print_note (prefix: "deleting: ", insn, note: link);
3215	free_EXPR_LIST_node (link);
3216	*pprev = link = next;
3217	}
3218	break;
3219
3220	case REG_UNUSED:
3221	/ After reg-stack, we need to ignore any unused notes*
3222	for the stack registers. /*
3223	if (df_ignore_stack_reg (REGNO (XEXP (link, `0`))))
3224	{
3225	pprev = &XEXP (link, `1`);
3226	link = *pprev;
3227	}
3228	else
3229	{
3230	rtx next = XEXP (link, `1`);
3231	if (REG_DEAD_DEBUGGING)
3232	df_print_note (prefix: "deleting: ", insn, note: link);
3233	free_EXPR_LIST_node (link);
3234	*pprev = link = next;
3235	}
3236	break;
3237
3238	default:
3239	pprev = &XEXP (link, `1`);
3240	link = *pprev;
3241	break;
3242	}
3243	}
3244	}
3245
3246	/ Remove REG_EQUAL/REG_EQUIV notes referring to dead pseudos using LIVE*
3247	as the bitmap of currently live registers. /*
3248
3249	static void
3250	df_remove_dead_eq_notes (rtx_insn *insn, bitmap live)
3251	{
3252	rtx *pprev = &REG_NOTES (insn);
3253	rtx link = *pprev;
3254
3255	while (link)
3256	{
3257	switch (REG_NOTE_KIND (link))
3258	{
3259	case REG_EQUAL:
3260	case REG_EQUIV:
3261	{
3262	/ Remove the notes that refer to dead registers. As we have at most*
3263	one REG_EQUAL/EQUIV note, all of EQ_USES will refer to this note
3264	so we need to purge the complete EQ_USES vector when removing
3265	the note using df_notes_rescan. /*
3266	df_ref use;
3267	bool deleted = false;
3268
3269	FOR_EACH_INSN_EQ_USE (use, insn)
3270	if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER
3271	&& DF_REF_LOC (use)
3272	&& (DF_REF_FLAGS (use) & DF_REF_IN_NOTE)
3273	&& !bitmap_bit_p (live, DF_REF_REGNO (use))
3274	&& loc_mentioned_in_p (DF_REF_LOC (use), XEXP (link, `0`)))
3275	{
3276	deleted = true;
3277	break;
3278	}
3279	if (deleted)
3280	{
3281	rtx next;
3282	if (REG_DEAD_DEBUGGING)
3283	df_print_note (prefix: "deleting: ", insn, note: link);
3284	next = XEXP (link, `1`);
3285	free_EXPR_LIST_node (link);
3286	*pprev = link = next;
3287	df_notes_rescan (insn);
3288	}
3289	else
3290	{
3291	pprev = &XEXP (link, `1`);
3292	link = *pprev;
3293	}
3294	break;
3295	}
3296
3297	default:
3298	pprev = &XEXP (link, `1`);
3299	link = *pprev;
3300	break;
3301	}
3302	}
3303	}
3304
3305	/ Set a NOTE_TYPE note for REG in INSN. /
3306
3307	static inline void
3308	df_set_note (enum reg_note note_type, rtx_insn *insn, rtx reg)
3309	{
3310	gcc_checking_assert (!DEBUG_INSN_P (insn));
3311	add_reg_note (insn, note_type, reg);
3312	}
3313
3314	/ A subroutine of df_set_unused_notes_for_mw, with a selection of its*
3315	arguments. Return true if the register value described by MWS's
3316	mw_reg is known to be completely unused, and if mw_reg can therefore
3317	be used in a REG_UNUSED note. /*
3318
3319	static bool
3320	df_whole_mw_reg_unused_p (struct df_mw_hardreg *mws,
3321	bitmap live, bitmap artificial_uses)
3322	{
3323	unsigned int r;
3324
3325	/ If MWS describes a partial reference, create REG_UNUSED notes for*
3326	individual hard registers. /*
3327	if (mws->flags & DF_REF_PARTIAL)
3328	return false;
3329
3330	/ Likewise if some part of the register is used. /
3331	for (r = mws->start_regno; r <= mws->end_regno; r++)
3332	if (bitmap_bit_p (live, r)
3333	\|\| bitmap_bit_p (artificial_uses, r))
3334	return false;
3335
3336	gcc_assert (REG_P (mws->mw_reg));
3337	return true;
3338	}
3339
3340
3341	/ Set the REG_UNUSED notes for the multiword hardreg defs in INSN*
3342	based on the bits in LIVE. Do not generate notes for registers in
3343	artificial uses. DO_NOT_GEN is updated so that REG_DEAD notes are
3344	not generated if the reg is both read and written by the
3345	instruction.
3346	*/
3347
3348	static void
3349	df_set_unused_notes_for_mw (rtx_insn insn, struct* df_mw_hardreg *mws,
3350	bitmap live, bitmap do_not_gen,
3351	bitmap artificial_uses,
3352	struct dead_debug_local *debug)
3353	{
3354	unsigned int r;
3355
3356	if (REG_DEAD_DEBUGGING && dump_file)
3357	fprintf (stream: dump_file, format: "mw_set_unused looking at mws[%d..%d]\n",
3358	mws->start_regno, mws->end_regno);
3359
3360	if (df_whole_mw_reg_unused_p (mws, live, artificial_uses))
3361	{
3362	unsigned int regno = mws->start_regno;
3363	df_set_note (note_type: REG_UNUSED, insn, reg: mws->mw_reg);
3364	dead_debug_insert_temp (debug, uregno: regno, insn, DEBUG_TEMP_AFTER_WITH_REG);
3365
3366	if (REG_DEAD_DEBUGGING)
3367	df_print_note (prefix: "adding 1: ", insn, REG_NOTES (insn));
3368
3369	bitmap_set_bit (do_not_gen, regno);
3370	/ Only do this if the value is totally dead. /
3371	}
3372	else
3373	for (r = mws->start_regno; r <= mws->end_regno; r++)
3374	{
3375	if (!bitmap_bit_p (live, r)
3376	&& !bitmap_bit_p (artificial_uses, r))
3377	{
3378	df_set_note (note_type: REG_UNUSED, insn, reg: regno_reg_rtx[r]);
3379	dead_debug_insert_temp (debug, uregno: r, insn, DEBUG_TEMP_AFTER_WITH_REG);
3380	if (REG_DEAD_DEBUGGING)
3381	df_print_note (prefix: "adding 2: ", insn, REG_NOTES (insn));
3382	}
3383	bitmap_set_bit (do_not_gen, r);
3384	}
3385	}
3386
3387
3388	/ A subroutine of df_set_dead_notes_for_mw, with a selection of its*
3389	arguments. Return true if the register value described by MWS's
3390	mw_reg is known to be completely dead, and if mw_reg can therefore
3391	be used in a REG_DEAD note. /*
3392
3393	static bool
3394	df_whole_mw_reg_dead_p (struct df_mw_hardreg *mws,
3395	bitmap live, bitmap artificial_uses,
3396	bitmap do_not_gen)
3397	{
3398	unsigned int r;
3399
3400	/ If MWS describes a partial reference, create REG_DEAD notes for*
3401	individual hard registers. /*
3402	if (mws->flags & DF_REF_PARTIAL)
3403	return false;
3404
3405	/ Likewise if some part of the register is not dead. /
3406	for (r = mws->start_regno; r <= mws->end_regno; r++)
3407	if (bitmap_bit_p (live, r)
3408	\|\| bitmap_bit_p (artificial_uses, r)
3409	\|\| bitmap_bit_p (do_not_gen, r))
3410	return false;
3411
3412	gcc_assert (REG_P (mws->mw_reg));
3413	return true;
3414	}
3415
3416	/ Set the REG_DEAD notes for the multiword hardreg use in INSN based*
3417	on the bits in LIVE. DO_NOT_GEN is used to keep REG_DEAD notes
3418	from being set if the instruction both reads and writes the
3419	register. /*
3420
3421	static void
3422	df_set_dead_notes_for_mw (rtx_insn insn, struct* df_mw_hardreg *mws,
3423	bitmap live, bitmap do_not_gen,
3424	bitmap artificial_uses, bool *added_notes_p)
3425	{
3426	unsigned int r;
3427	bool is_debug = *added_notes_p;
3428
3429	added_notes_p = false*;
3430
3431	if (REG_DEAD_DEBUGGING && dump_file)
3432	{
3433	fprintf (stream: dump_file, format: "mw_set_dead looking at mws[%d..%d]\n do_not_gen =",
3434	mws->start_regno, mws->end_regno);
3435	df_print_regset (file: dump_file, r: do_not_gen);
3436	fprintf (stream: dump_file, format: " live =");
3437	df_print_regset (file: dump_file, r: live);
3438	fprintf (stream: dump_file, format: " artificial uses =");
3439	df_print_regset (file: dump_file, r: artificial_uses);
3440	}
3441
3442	if (df_whole_mw_reg_dead_p (mws, live, artificial_uses, do_not_gen))
3443	{
3444	if (is_debug)
3445	{
3446	added_notes_p = true*;
3447	return;
3448	}
3449	/ Add a dead note for the entire multi word register. /
3450	df_set_note (note_type: REG_DEAD, insn, reg: mws->mw_reg);
3451	if (REG_DEAD_DEBUGGING)
3452	df_print_note (prefix: "adding 1: ", insn, REG_NOTES (insn));
3453	}
3454	else
3455	{
3456	for (r = mws->start_regno; r <= mws->end_regno; r++)
3457	if (!bitmap_bit_p (live, r)
3458	&& !bitmap_bit_p (artificial_uses, r)
3459	&& !bitmap_bit_p (do_not_gen, r))
3460	{
3461	if (is_debug)
3462	{
3463	added_notes_p = true*;
3464	return;
3465	}
3466	df_set_note (note_type: REG_DEAD, insn, reg: regno_reg_rtx[r]);
3467	if (REG_DEAD_DEBUGGING)
3468	df_print_note (prefix: "adding 2: ", insn, REG_NOTES (insn));
3469	}
3470	}
3471	return;
3472	}
3473
3474
3475	/ Create a REG_UNUSED note if necessary for DEF in INSN updating*
3476	LIVE. Do not generate notes for registers in ARTIFICIAL_USES. /*
3477
3478	static void
3479	df_create_unused_note (rtx_insn *insn, df_ref def,
3480	bitmap live, bitmap artificial_uses,
3481	struct dead_debug_local *debug)
3482	{
3483	unsigned int dregno = DF_REF_REGNO (def);
3484
3485	if (REG_DEAD_DEBUGGING && dump_file)
3486	{
3487	fprintf (stream: dump_file, format: " regular looking at def ");
3488	df_ref_debug (def, dump_file);
3489	}
3490
3491	if (!((DF_REF_FLAGS (def) & DF_REF_MW_HARDREG)
3492	\|\| bitmap_bit_p (live, dregno)
3493	\|\| bitmap_bit_p (artificial_uses, dregno)
3494	\|\| df_ignore_stack_reg (regno: dregno)))
3495	{
3496	rtx reg = (DF_REF_LOC (def))
3497	? *DF_REF_REAL_LOC (def): DF_REF_REG (def);
3498	df_set_note (note_type: REG_UNUSED, insn, reg);
3499	dead_debug_insert_temp (debug, uregno: dregno, insn, DEBUG_TEMP_AFTER_WITH_REG);
3500	if (REG_DEAD_DEBUGGING)
3501	df_print_note (prefix: "adding 3: ", insn, REG_NOTES (insn));
3502	}
3503
3504	return;
3505	}
3506
3507
3508	/ Recompute the REG_DEAD and REG_UNUSED notes and compute register*
3509	info: lifetime, bb, and number of defs and uses for basic block
3510	BB. The three bitvectors are scratch regs used here. /*
3511
3512	static void
3513	df_note_bb_compute (unsigned int bb_index,
3514	bitmap live, bitmap do_not_gen, bitmap artificial_uses)
3515	{
3516	basic_block bb = BASIC_BLOCK_FOR_FN (cfun, bb_index);
3517	rtx_insn *insn;
3518	df_ref def, use;
3519	struct dead_debug_local debug;
3520
3521	dead_debug_local_init (&debug, NULL, NULL);
3522
3523	bitmap_copy (live, df_get_live_out (bb));
3524	bitmap_clear (artificial_uses);
3525
3526	if (REG_DEAD_DEBUGGING && dump_file)
3527	{
3528	fprintf (stream: dump_file, format: "live at bottom ");
3529	df_print_regset (file: dump_file, r: live);
3530	}
3531
3532	/ Process the artificial defs and uses at the bottom of the block*
3533	to begin processing. /*
3534	FOR_EACH_ARTIFICIAL_DEF (def, bb_index)
3535	{
3536	if (REG_DEAD_DEBUGGING && dump_file)
3537	fprintf (stream: dump_file, format: "artificial def %d\n", DF_REF_REGNO (def));
3538
3539	if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) == `0`)
3540	bitmap_clear_bit (live, DF_REF_REGNO (def));
3541	}
3542
3543	FOR_EACH_ARTIFICIAL_USE (use, bb_index)
3544	if ((DF_REF_FLAGS (use) & DF_REF_AT_TOP) == `0`)
3545	{
3546	unsigned int regno = DF_REF_REGNO (use);
3547	bitmap_set_bit (live, regno);
3548
3549	/ Notes are not generated for any of the artificial registers*
3550	at the bottom of the block. /*
3551	bitmap_set_bit (artificial_uses, regno);
3552	}
3553
3554	if (REG_DEAD_DEBUGGING && dump_file)
3555	{
3556	fprintf (stream: dump_file, format: "live before artificials out ");
3557	df_print_regset (file: dump_file, r: live);
3558	}
3559
3560	FOR_BB_INSNS_REVERSE (bb, insn)
3561	{
3562	if (!INSN_P (insn))
3563	continue;
3564
3565	df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
3566	df_mw_hardreg *mw;
3567	int debug_insn;
3568
3569	debug_insn = DEBUG_INSN_P (insn);
3570
3571	bitmap_clear (do_not_gen);
3572	df_remove_dead_and_unused_notes (insn);
3573
3574	/ Process the defs. /
3575	if (CALL_P (insn))
3576	{
3577	if (REG_DEAD_DEBUGGING && dump_file)
3578	{
3579	fprintf (stream: dump_file, format: "processing call %d\n live =",
3580	INSN_UID (insn));
3581	df_print_regset (file: dump_file, r: live);
3582	}
3583
3584	/ We only care about real sets for calls. Clobbers cannot*
3585	be depended on to really die. /*
3586	FOR_EACH_INSN_INFO_MW (mw, insn_info)
3587	if ((DF_MWS_REG_DEF_P (mw))
3588	&& !df_ignore_stack_reg (regno: mw->start_regno))
3589	df_set_unused_notes_for_mw (insn, mws: mw, live, do_not_gen,
3590	artificial_uses, debug: &debug);
3591
3592	/ All of the defs except the return value are some sort of*
3593	clobber. This code is for the return. /*
3594	FOR_EACH_INSN_INFO_DEF (def, insn_info)
3595	{
3596	unsigned int dregno = DF_REF_REGNO (def);
3597	if (!DF_REF_FLAGS_IS_SET (def, DF_REF_MUST_CLOBBER \| DF_REF_MAY_CLOBBER))
3598	{
3599	df_create_unused_note (insn,
3600	def, live, artificial_uses, debug: &debug);
3601	bitmap_set_bit (do_not_gen, dregno);
3602	}
3603
3604	if (!DF_REF_FLAGS_IS_SET (def, DF_REF_PARTIAL \| DF_REF_CONDITIONAL))
3605	bitmap_clear_bit (live, dregno);
3606	}
3607	}
3608	else
3609	{
3610	/ Regular insn. /
3611	FOR_EACH_INSN_INFO_MW (mw, insn_info)
3612	if (DF_MWS_REG_DEF_P (mw))
3613	df_set_unused_notes_for_mw (insn, mws: mw, live, do_not_gen,
3614	artificial_uses, debug: &debug);
3615
3616	FOR_EACH_INSN_INFO_DEF (def, insn_info)
3617	{
3618	unsigned int dregno = DF_REF_REGNO (def);
3619	df_create_unused_note (insn,
3620	def, live, artificial_uses, debug: &debug);
3621
3622	if (!DF_REF_FLAGS_IS_SET (def, DF_REF_MUST_CLOBBER \| DF_REF_MAY_CLOBBER))
3623	bitmap_set_bit (do_not_gen, dregno);
3624
3625	if (!DF_REF_FLAGS_IS_SET (def, DF_REF_PARTIAL \| DF_REF_CONDITIONAL))
3626	bitmap_clear_bit (live, dregno);
3627	}
3628	}
3629
3630	/ Process the uses. /
3631	FOR_EACH_INSN_INFO_MW (mw, insn_info)
3632	if (DF_MWS_REG_USE_P (mw)
3633	&& !df_ignore_stack_reg (regno: mw->start_regno))
3634	{
3635	bool really_add_notes = debug_insn != `0`;
3636
3637	df_set_dead_notes_for_mw (insn, mws: mw, live, do_not_gen,
3638	artificial_uses,
3639	added_notes_p: &really_add_notes);
3640
3641	if (really_add_notes)
3642	debug_insn = -`1`;
3643	}
3644
3645	FOR_EACH_INSN_INFO_USE (use, insn_info)
3646	{
3647	unsigned int uregno = DF_REF_REGNO (use);
3648
3649	if (REG_DEAD_DEBUGGING && dump_file && !debug_insn)
3650	{
3651	fprintf (stream: dump_file, format: " regular looking at use ");
3652	df_ref_debug (use, dump_file);
3653	}
3654
3655	if (!bitmap_bit_p (live, uregno))
3656	{
3657	if (debug_insn)
3658	{
3659	if (debug_insn > `0`)
3660	{
3661	/ We won't add REG_UNUSED or REG_DEAD notes for*
3662	these, so we don't have to mess with them in
3663	debug insns either. /*
3664	if (!bitmap_bit_p (artificial_uses, uregno)
3665	&& !df_ignore_stack_reg (regno: uregno))
3666	dead_debug_add (&debug, use, uregno);
3667	continue;
3668	}
3669	break;
3670	}
3671	else
3672	dead_debug_insert_temp (&debug, uregno, insn,
3673	DEBUG_TEMP_BEFORE_WITH_REG);
3674
3675	if ( (!(DF_REF_FLAGS (use)
3676	& (DF_REF_MW_HARDREG \| DF_REF_READ_WRITE)))
3677	&& (!bitmap_bit_p (do_not_gen, uregno))
3678	&& (!bitmap_bit_p (artificial_uses, uregno))
3679	&& (!df_ignore_stack_reg (regno: uregno)))
3680	{
3681	rtx reg = (DF_REF_LOC (use))
3682	? *DF_REF_REAL_LOC (use) : DF_REF_REG (use);
3683	df_set_note (note_type: REG_DEAD, insn, reg);
3684
3685	if (REG_DEAD_DEBUGGING)
3686	df_print_note (prefix: "adding 4: ", insn, REG_NOTES (insn));
3687	}
3688	/ This register is now live. /
3689	bitmap_set_bit (live, uregno);
3690	}
3691	}
3692
3693	df_remove_dead_eq_notes (insn, live);
3694
3695	if (debug_insn == -`1`)
3696	{
3697	/ ??? We could probably do better here, replacing dead*
3698	registers with their definitions. /*
3699	INSN_VAR_LOCATION_LOC (insn) = gen_rtx_UNKNOWN_VAR_LOC ();
3700	df_insn_rescan_debug_internal (insn);
3701	}
3702	}
3703
3704	dead_debug_local_finish (&debug, NULL);
3705	}
3706
3707
3708	/ Compute register info: lifetime, bb, and number of defs and uses. /
3709	static void
3710	df_note_compute (bitmap all_blocks)
3711	{
3712	unsigned int bb_index;
3713	bitmap_iterator bi;
3714	bitmap_head live, do_not_gen, artificial_uses;
3715
3716	bitmap_initialize (head: &live, obstack: &df_bitmap_obstack);
3717	bitmap_initialize (head: &do_not_gen, obstack: &df_bitmap_obstack);
3718	bitmap_initialize (head: &artificial_uses, obstack: &df_bitmap_obstack);
3719
3720	EXECUTE_IF_SET_IN_BITMAP (all_blocks, `0`, bb_index, bi)
3721	{
3722	/ ??? Unlike fast DCE, we don't use global_debug for uses of dead*
3723	pseudos in debug insns because we don't always (re)visit blocks
3724	with death points after visiting dead uses. Even changing this
3725	loop to postorder would still leave room for visiting a death
3726	point before visiting a subsequent debug use. /*
3727	df_note_bb_compute (bb_index, live: &live, do_not_gen: &do_not_gen, artificial_uses: &artificial_uses);
3728	}
3729
3730	bitmap_clear (&live);
3731	bitmap_clear (&do_not_gen);
3732	bitmap_clear (&artificial_uses);
3733	}
3734
3735
3736	/ Free all storage associated with the problem. /
3737
3738	static void
3739	df_note_free (void)
3740	{
3741	free (df_note);
3742	}
3743
3744
3745	/ All of the information associated every instance of the problem. /
3746
3747	static const struct df_problem problem_NOTE =
3748	{
3749	.id: DF_NOTE, / Problem id. /
3750	.dir: DF_NONE, / Direction. /
3751	.alloc_fun: df_note_alloc, / Allocate the problem specific data. /
3752	NULL, / Reset global information. /
3753	NULL, / Free basic block info. /
3754	.local_compute_fun: df_note_compute, / Local compute function. /
3755	NULL, / Init the solution specific data. /
3756	NULL, / Iterative solver. /
3757	NULL, / Confluence operator 0. /
3758	NULL, / Confluence operator n. /
3759	NULL, / Transfer function. /
3760	NULL, / Finalize function. /
3761	.free_fun: df_note_free, / Free all of the problem information. /
3762	.remove_problem_fun: df_note_free, / Remove this problem from the stack of dataflow problems. /
3763	NULL, / Debugging. /
3764	NULL, / Debugging start block. /
3765	NULL, / Debugging end block. /
3766	NULL, / Debugging start insn. /
3767	NULL, / Debugging end insn. /
3768	NULL, / Incremental solution verify start. /
3769	NULL, / Incremental solution verify end. /
3770	.dependent_problem: &problem_LR, / Dependent problem. /
3771	.block_info_elt_size: sizeof (struct df_scan_bb_info),/ Size of entry of block_info array. /
3772	.tv_id: TV_DF_NOTE, / Timing variable. /
3773	.free_blocks_on_set_blocks: false / Reset blocks on dropping out of blocks_to_analyze. /
3774	};
3775
3776
3777	/ Create a new DATAFLOW instance and add it to an existing instance*
3778	of DF. The returned structure is what is used to get at the
3779	solution. /*
3780
3781	void
3782	df_note_add_problem (void)
3783	{
3784	df_add_problem (&problem_NOTE);
3785	}
3786
3787
3788
3789
3790	/----------------------------------------------------------------------------*
3791	Functions for simulating the effects of single insns.
3792
3793	You can either simulate in the forwards direction, starting from
3794	the top of a block or the backwards direction from the end of the
3795	block. If you go backwards, defs are examined first to clear bits,
3796	then uses are examined to set bits. If you go forwards, defs are
3797	examined first to set bits, then REG_DEAD and REG_UNUSED notes
3798	are examined to clear bits. In either case, the result of examining
3799	a def can be undone (respectively by a use or a REG_UNUSED note).
3800
3801	If you start at the top of the block, use one of DF_LIVE_IN or
3802	DF_LR_IN. If you start at the bottom of the block use one of
3803	DF_LIVE_OUT or DF_LR_OUT. BE SURE TO PASS A COPY OF THESE SETS,
3804	THEY WILL BE DESTROYED.
3805	----------------------------------------------------------------------------/*
3806
3807
3808	/ Find the set of DEFs for INSN. /
3809
3810	void
3811	df_simulate_find_defs (rtx_insn *insn, bitmap defs)
3812	{
3813	df_ref def;
3814
3815	FOR_EACH_INSN_DEF (def, insn)
3816	bitmap_set_bit (defs, DF_REF_REGNO (def));
3817	}
3818
3819	/ Find the set of uses for INSN. This includes partial defs. /
3820
3821	static void
3822	df_simulate_find_uses (rtx_insn *insn, bitmap uses)
3823	{
3824	df_ref def, use;
3825	struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
3826
3827	FOR_EACH_INSN_INFO_DEF (def, insn_info)
3828	if (DF_REF_FLAGS (def) & (DF_REF_PARTIAL \| DF_REF_CONDITIONAL))
3829	bitmap_set_bit (uses, DF_REF_REGNO (def));
3830	FOR_EACH_INSN_INFO_USE (use, insn_info)
3831	bitmap_set_bit (uses, DF_REF_REGNO (use));
3832	}
3833
3834	/ Find the set of real DEFs, which are not clobbers, for INSN. /
3835
3836	void
3837	df_simulate_find_noclobber_defs (rtx_insn *insn, bitmap defs)
3838	{
3839	df_ref def;
3840
3841	FOR_EACH_INSN_DEF (def, insn)
3842	if (!(DF_REF_FLAGS (def) & (DF_REF_MUST_CLOBBER \| DF_REF_MAY_CLOBBER)))
3843	bitmap_set_bit (defs, DF_REF_REGNO (def));
3844	}
3845
3846
3847	/ Simulate the effects of the defs of INSN on LIVE. /
3848
3849	void
3850	df_simulate_defs (rtx_insn *insn, bitmap live)
3851	{
3852	df_ref def;
3853
3854	FOR_EACH_INSN_DEF (def, insn)
3855	{
3856	unsigned int dregno = DF_REF_REGNO (def);
3857
3858	/ If the def is to only part of the reg, it does*
3859	not kill the other defs that reach here. /*
3860	if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL \| DF_REF_CONDITIONAL)))
3861	bitmap_clear_bit (live, dregno);
3862	}
3863	}
3864
3865
3866	/ Simulate the effects of the uses of INSN on LIVE. /
3867
3868	void
3869	df_simulate_uses (rtx_insn *insn, bitmap live)
3870	{
3871	df_ref use;
3872
3873	if (DEBUG_INSN_P (insn))
3874	return;
3875
3876	FOR_EACH_INSN_USE (use, insn)
3877	/ Add use to set of uses in this BB. /
3878	bitmap_set_bit (live, DF_REF_REGNO (use));
3879	}
3880
3881
3882	/ Add back the always live regs in BB to LIVE. /
3883
3884	static inline void
3885	df_simulate_fixup_sets (basic_block bb, bitmap live)
3886	{
3887	/ These regs are considered always live so if they end up dying*
3888	because of some def, we need to bring the back again. /*
3889	if (bb_has_eh_pred (bb))
3890	bitmap_ior_into (live, &df->eh_block_artificial_uses);
3891	else
3892	bitmap_ior_into (live, &df->regular_block_artificial_uses);
3893	}
3894
3895
3896	/----------------------------------------------------------------------------*
3897	The following three functions are used only for BACKWARDS scanning:
3898	i.e. they process the defs before the uses.
3899
3900	df_simulate_initialize_backwards should be called first with a
3901	bitvector copyied from the DF_LIVE_OUT or DF_LR_OUT. Then
3902	df_simulate_one_insn_backwards should be called for each insn in
3903	the block, starting with the last one. Finally,
3904	df_simulate_finalize_backwards can be called to get a new value
3905	of the sets at the top of the block (this is rarely used).
3906	----------------------------------------------------------------------------/*
3907
3908	/ Apply the artificial uses and defs at the end of BB in a backwards*
3909	direction. /*
3910
3911	void
3912	df_simulate_initialize_backwards (basic_block bb, bitmap live)
3913	{
3914	df_ref def, use;
3915	int bb_index = bb->index;
3916
3917	FOR_EACH_ARTIFICIAL_DEF (def, bb_index)
3918	if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) == `0`)
3919	bitmap_clear_bit (live, DF_REF_REGNO (def));
3920
3921	FOR_EACH_ARTIFICIAL_USE (use, bb_index)
3922	if ((DF_REF_FLAGS (use) & DF_REF_AT_TOP) == `0`)
3923	bitmap_set_bit (live, DF_REF_REGNO (use));
3924	}
3925
3926
3927	/ Simulate the backwards effects of INSN on the bitmap LIVE. /
3928
3929	void
3930	df_simulate_one_insn_backwards (basic_block bb, rtx_insn *insn, bitmap live)
3931	{
3932	if (!NONDEBUG_INSN_P (insn))
3933	return;
3934
3935	df_simulate_defs (insn, live);
3936	df_simulate_uses (insn, live);
3937	df_simulate_fixup_sets (bb, live);
3938	}
3939
3940
3941	/ Apply the artificial uses and defs at the top of BB in a backwards*
3942	direction. /*
3943
3944	void
3945	df_simulate_finalize_backwards (basic_block bb, bitmap live)
3946	{
3947	df_ref def;
3948	#ifdef EH_USES
3949	df_ref use;
3950	#endif
3951	int bb_index = bb->index;
3952
3953	FOR_EACH_ARTIFICIAL_DEF (def, bb_index)
3954	if (DF_REF_FLAGS (def) & DF_REF_AT_TOP)
3955	bitmap_clear_bit (live, DF_REF_REGNO (def));
3956
3957	#ifdef EH_USES
3958	FOR_EACH_ARTIFICIAL_USE (use, bb_index)
3959	if (DF_REF_FLAGS (use) & DF_REF_AT_TOP)
3960	bitmap_set_bit (live, DF_REF_REGNO (use));
3961	#endif
3962	}
3963	/----------------------------------------------------------------------------*
3964	The following three functions are used only for FORWARDS scanning:
3965	i.e. they process the defs and the REG_DEAD and REG_UNUSED notes.
3966	Thus it is important to add the DF_NOTES problem to the stack of
3967	problems computed before using these functions.
3968
3969	df_simulate_initialize_forwards should be called first with a
3970	bitvector copyied from the DF_LIVE_IN or DF_LR_IN. Then
3971	df_simulate_one_insn_forwards should be called for each insn in
3972	the block, starting with the first one.
3973	----------------------------------------------------------------------------/*
3974
3975	/ Initialize the LIVE bitmap, which should be copied from DF_LIVE_IN or*
3976	DF_LR_IN for basic block BB, for forward scanning by marking artificial
3977	defs live. /*
3978
3979	void
3980	df_simulate_initialize_forwards (basic_block bb, bitmap live)
3981	{
3982	df_ref def;
3983	int bb_index = bb->index;
3984
3985	FOR_EACH_ARTIFICIAL_DEF (def, bb_index)
3986	if (DF_REF_FLAGS (def) & DF_REF_AT_TOP)
3987	bitmap_set_bit (live, DF_REF_REGNO (def));
3988	}
3989
3990	/ Simulate the forwards effects of INSN on the bitmap LIVE. /
3991
3992	void
3993	df_simulate_one_insn_forwards (basic_block bb, rtx_insn *insn, bitmap live)
3994	{
3995	rtx link;
3996	if (! INSN_P (insn))
3997	return;
3998
3999	/ Make sure that DF_NOTE really is an active df problem. /
4000	gcc_assert (df_note);
4001
4002	/ Note that this is the opposite as how the problem is defined, because*
4003	in the LR problem defs _kill_ liveness. However, they do so backwards,
4004	while here the scan is performed forwards! So, first assume that the
4005	def is live, and if this is not true REG_UNUSED notes will rectify the
4006	situation. /*
4007	df_simulate_find_noclobber_defs (insn, defs: live);
4008
4009	/ Clear all of the registers that go dead. /
4010	for (link = REG_NOTES (insn); link; link = XEXP (link, `1`))
4011	{
4012	switch (REG_NOTE_KIND (link))
4013	{
4014	case REG_DEAD:
4015	case REG_UNUSED:
4016	{
4017	rtx reg = XEXP (link, `0`);
4018	bitmap_clear_range (live, REGNO (reg), REG_NREGS (reg));
4019	}
4020	break;
4021	default:
4022	break;
4023	}
4024	}
4025	df_simulate_fixup_sets (bb, live);
4026	}
4027
4028	/ Used by the next two functions to encode information about the*
4029	memory references we found. /*
4030	#define MEMREF_NORMAL 1
4031	#define MEMREF_VOLATILE 2
4032
4033	/ Return an OR of MEMREF_NORMAL or MEMREF_VOLATILE for the MEMs in X. /
4034
4035	static int
4036	find_memory (rtx_insn *insn)
4037	{
4038	int flags = `0`;
4039	subrtx_iterator::array_type array;
4040	FOR_EACH_SUBRTX (iter, array, PATTERN (insn), NONCONST)
4041	{
4042	const_rtx x = *iter;
4043	if (GET_CODE (x) == ASM_OPERANDS && MEM_VOLATILE_P (x))
4044	flags \|= MEMREF_VOLATILE;
4045	else if (MEM_P (x))
4046	{
4047	if (MEM_VOLATILE_P (x))
4048	flags \|= MEMREF_VOLATILE;
4049	else if (!MEM_READONLY_P (x))
4050	flags \|= MEMREF_NORMAL;
4051	}
4052	}
4053	return flags;
4054	}
4055
4056	/ A subroutine of can_move_insns_across_p called through note_stores.*
4057	DATA points to an integer in which we set either the bit for
4058	MEMREF_NORMAL or the bit for MEMREF_VOLATILE if we find a MEM
4059	of either kind. /*
4060
4061	static void
4062	find_memory_stores (rtx x, const_rtx pat ATTRIBUTE_UNUSED,
4063	void *data ATTRIBUTE_UNUSED)
4064	{
4065	int pflags = (int* *)data;
4066	if (GET_CODE (x) == SUBREG)
4067	x = XEXP (x, `0`);
4068	/ Treat stores to SP as stores to memory, this will prevent problems*
4069	when there are references to the stack frame. /*
4070	if (x == stack_pointer_rtx)
4071	*pflags \|= MEMREF_VOLATILE;
4072	if (!MEM_P (x))
4073	return;
4074	*pflags \|= MEM_VOLATILE_P (x) ? MEMREF_VOLATILE : MEMREF_NORMAL;
4075	}
4076
4077	/ Scan BB backwards, using df_simulate functions to keep track of*
4078	lifetimes, up to insn POINT. The result is stored in LIVE. /*
4079
4080	void
4081	simulate_backwards_to_point (basic_block bb, regset live, rtx point)
4082	{
4083	rtx_insn *insn;
4084	bitmap_copy (live, df_get_live_out (bb));
4085	df_simulate_initialize_backwards (bb, live);
4086
4087	/ Scan and update life information until we reach the point we're*
4088	interested in. /*
4089	for (insn = BB_END (bb); insn != point; insn = PREV_INSN (insn))
4090	df_simulate_one_insn_backwards (bb, insn, live);
4091	}
4092
4093	/ Return true if it is safe to move a group of insns, described by*
4094	the range FROM to TO, backwards across another group of insns,
4095	described by ACROSS_FROM to ACROSS_TO. It is assumed that there
4096	are no insns between ACROSS_TO and FROM, but they may be in
4097	different basic blocks; MERGE_BB is the block from which the
4098	insns will be moved. The caller must pass in a regset MERGE_LIVE
4099	which specifies the registers live after TO.
4100
4101	This function may be called in one of two cases: either we try to
4102	move identical instructions from all successor blocks into their
4103	predecessor, or we try to move from only one successor block. If
4104	OTHER_BRANCH_LIVE is nonnull, it indicates that we're dealing with
4105	the second case. It should contain a set of registers live at the
4106	end of ACROSS_TO which must not be clobbered by moving the insns.
4107	In that case, we're also more careful about moving memory references
4108	and trapping insns.
4109
4110	We return false if it is not safe to move the entire group, but it
4111	may still be possible to move a subgroup. PMOVE_UPTO, if nonnull,
4112	is set to point at the last moveable insn in such a case. /*
4113
4114	bool
4115	can_move_insns_across (rtx_insn from, rtx_insn to,
4116	rtx_insn across_from, rtx_insn across_to,
4117	basic_block merge_bb, regset merge_live,
4118	regset other_branch_live, rtx_insn **pmove_upto)
4119	{
4120	rtx_insn insn, next, *max_to;
4121	bitmap merge_set, merge_use, local_merge_live;
4122	bitmap test_set, test_use;
4123	unsigned i, fail = `0`;
4124	bitmap_iterator bi;
4125	int memrefs_in_across = `0`;
4126	int mem_sets_in_across = `0`;
4127	bool trapping_insns_in_across = false;
4128
4129	if (pmove_upto != NULL)
4130	*pmove_upto = NULL;
4131
4132	/ Find real bounds, ignoring debug insns. /
4133	while (!NONDEBUG_INSN_P (from) && from != to)
4134	from = NEXT_INSN (insn: from);
4135	while (!NONDEBUG_INSN_P (to) && from != to)
4136	to = PREV_INSN (insn: to);
4137
4138	for (insn = across_to; ; insn = next)
4139	{
4140	if (CALL_P (insn))
4141	{
4142	if (RTL_CONST_OR_PURE_CALL_P (insn))
4143	/ Pure functions can read from memory. Const functions can*
4144	read from arguments that the ABI has forced onto the stack.
4145	Neither sort of read can be volatile. /*
4146	memrefs_in_across \|= MEMREF_NORMAL;
4147	else
4148	{
4149	memrefs_in_across \|= MEMREF_VOLATILE;
4150	mem_sets_in_across \|= MEMREF_VOLATILE;
4151	}
4152	}
4153	if (NONDEBUG_INSN_P (insn))
4154	{
4155	if (volatile_insn_p (PATTERN (insn)))
4156	return false;
4157	memrefs_in_across \|= find_memory (insn);
4158	note_stores (insn, find_memory_stores, &mem_sets_in_across);
4159	/ This is used just to find sets of the stack pointer. /
4160	memrefs_in_across \|= mem_sets_in_across;
4161	trapping_insns_in_across \|= may_trap_p (PATTERN (insn));
4162	}
4163	next = PREV_INSN (insn);
4164	if (insn == across_from)
4165	break;
4166	}
4167
4168	/ Collect:*
4169	MERGE_SET = set of registers set in MERGE_BB
4170	MERGE_USE = set of registers used in MERGE_BB and live at its top
4171	MERGE_LIVE = set of registers live at the point inside the MERGE
4172	range that we've reached during scanning
4173	TEST_SET = set of registers set between ACROSS_FROM and ACROSS_END.
4174	TEST_USE = set of registers used between ACROSS_FROM and ACROSS_END,
4175	and live before ACROSS_FROM. /*
4176
4177	merge_set = BITMAP_ALLOC (obstack: &reg_obstack);
4178	merge_use = BITMAP_ALLOC (obstack: &reg_obstack);
4179	local_merge_live = BITMAP_ALLOC (obstack: &reg_obstack);
4180	test_set = BITMAP_ALLOC (obstack: &reg_obstack);
4181	test_use = BITMAP_ALLOC (obstack: &reg_obstack);
4182
4183	/ Compute the set of registers set and used in the ACROSS range. /
4184	if (other_branch_live != NULL)
4185	bitmap_copy (test_use, other_branch_live);
4186	df_simulate_initialize_backwards (bb: merge_bb, live: test_use);
4187	for (insn = across_to; ; insn = next)
4188	{
4189	if (NONDEBUG_INSN_P (insn))
4190	{
4191	df_simulate_find_defs (insn, defs: test_set);
4192	df_simulate_defs (insn, live: test_use);
4193	df_simulate_uses (insn, live: test_use);
4194	}
4195	next = PREV_INSN (insn);
4196	if (insn == across_from)
4197	break;
4198	}
4199
4200	/ Compute an upper bound for the amount of insns moved, by finding*
4201	the first insn in MERGE that sets a register in TEST_USE, or uses
4202	a register in TEST_SET. We also check for calls, trapping operations,
4203	and memory references. /*
4204	max_to = NULL;
4205	for (insn = from; ; insn = next)
4206	{
4207	if (CALL_P (insn))
4208	break;
4209	if (NOTE_P (insn) && NOTE_KIND (insn) == NOTE_INSN_EPILOGUE_BEG)
4210	break;
4211	if (NONDEBUG_INSN_P (insn))
4212	{
4213	if (may_trap_or_fault_p (PATTERN (insn))
4214	&& (trapping_insns_in_across
4215	\|\| other_branch_live != NULL
4216	\|\| volatile_insn_p (PATTERN (insn))))
4217	break;
4218
4219	/ We cannot move memory stores past each other, or move memory*
4220	reads past stores, at least not without tracking them and
4221	calling true_dependence on every pair.
4222
4223	If there is no other branch and no memory references or
4224	sets in the ACROSS range, we can move memory references
4225	freely, even volatile ones.
4226
4227	Otherwise, the rules are as follows: volatile memory
4228	references and stores can't be moved at all, and any type
4229	of memory reference can't be moved if there are volatile
4230	accesses or stores in the ACROSS range. That leaves
4231	normal reads, which can be moved, as the trapping case is
4232	dealt with elsewhere. /*
4233	if (other_branch_live != NULL \|\| memrefs_in_across != `0`)
4234	{
4235	int mem_ref_flags = `0`;
4236	int mem_set_flags = `0`;
4237	note_stores (insn, find_memory_stores, &mem_set_flags);
4238	mem_ref_flags = find_memory (insn);
4239	/ Catch sets of the stack pointer. /
4240	mem_ref_flags \|= mem_set_flags;
4241
4242	if ((mem_ref_flags \| mem_set_flags) & MEMREF_VOLATILE)
4243	break;
4244	if ((memrefs_in_across & MEMREF_VOLATILE) && mem_ref_flags != `0`)
4245	break;
4246	if (mem_set_flags != `0`
4247	\|\| (mem_sets_in_across != `0` && mem_ref_flags != `0`))
4248	break;
4249	}
4250	df_simulate_find_uses (insn, uses: merge_use);
4251	/ We're only interested in uses which use a value live at*
4252	the top, not one previously set in this block. /*
4253	bitmap_and_compl_into (merge_use, merge_set);
4254	df_simulate_find_defs (insn, defs: merge_set);
4255	if (bitmap_intersect_p (merge_set, test_use)
4256	\|\| bitmap_intersect_p (merge_use, test_set))
4257	break;
4258	max_to = insn;
4259	}
4260	next = NEXT_INSN (insn);
4261	if (insn == to)
4262	break;
4263	}
4264	if (max_to != to)
4265	fail = `1`;
4266
4267	if (max_to == NULL_RTX \|\| (fail && pmove_upto == NULL))
4268	goto out;
4269
4270	/ Now, lower this upper bound by also taking into account that*
4271	a range of insns moved across ACROSS must not leave a register
4272	live at the end that will be clobbered in ACROSS. We need to
4273	find a point where TEST_SET & LIVE == 0.
4274
4275	Insns in the MERGE range that set registers which are also set
4276	in the ACROSS range may still be moved as long as we also move
4277	later insns which use the results of the set, and make the
4278	register dead again. This is verified by the condition stated
4279	above. We only need to test it for registers that are set in
4280	the moved region.
4281
4282	MERGE_LIVE is provided by the caller and holds live registers after
4283	TO. /*
4284	bitmap_copy (local_merge_live, merge_live);
4285	for (insn = to; insn != max_to; insn = PREV_INSN (insn))
4286	df_simulate_one_insn_backwards (bb: merge_bb, insn, live: local_merge_live);
4287
4288	/ We're not interested in registers that aren't set in the moved*
4289	region at all. /*
4290	bitmap_and_into (local_merge_live, merge_set);
4291	for (;;)
4292	{
4293	if (NONDEBUG_INSN_P (insn))
4294	{
4295	if (!bitmap_intersect_p (test_set, local_merge_live))
4296	{
4297	max_to = insn;
4298	break;
4299	}
4300
4301	df_simulate_one_insn_backwards (bb: merge_bb, insn,
4302	live: local_merge_live);
4303	}
4304	if (insn == from)
4305	{
4306	fail = `1`;
4307	goto out;
4308	}
4309	insn = PREV_INSN (insn);
4310	}
4311
4312	if (max_to != to)
4313	fail = `1`;
4314
4315	if (pmove_upto)
4316	*pmove_upto = max_to;
4317
4318	/ For small register class machines, don't lengthen lifetimes of*
4319	hard registers before reload. /*
4320	if (! reload_completed
4321	&& targetm.small_register_classes_for_mode_p (VOIDmode))
4322	{
4323	EXECUTE_IF_SET_IN_BITMAP (merge_set, `0`, i, bi)
4324	{
4325	if (i < FIRST_PSEUDO_REGISTER
4326	&& ! fixed_regs[i]
4327	&& ! global_regs[i])
4328	{
4329	fail = `1`;
4330	break;
4331	}
4332	}
4333	}
4334
4335	out:
4336	BITMAP_FREE (merge_set);
4337	BITMAP_FREE (merge_use);
4338	BITMAP_FREE (local_merge_live);
4339	BITMAP_FREE (test_set);
4340	BITMAP_FREE (test_use);
4341
4342	return !fail;
4343	}
4344
4345
4346	/----------------------------------------------------------------------------*
4347	MULTIPLE DEFINITIONS
4348
4349	Find the locations in the function reached by multiple definition sites
4350	for a live pseudo. In and out bitvectors are built for each basic
4351	block. They are restricted for efficiency to live registers.
4352
4353	The gen and kill sets for the problem are obvious. Together they
4354	include all defined registers in a basic block; the gen set includes
4355	registers where a partial or conditional or may-clobber definition is
4356	last in the BB, while the kill set includes registers with a complete
4357	definition coming last. However, the computation of the dataflow
4358	itself is interesting.
4359
4360	The idea behind it comes from SSA form's iterated dominance frontier
4361	criterion for inserting PHI functions. Just like in that case, we can use
4362	the dominance frontier to find places where multiple definitions meet;
4363	a register X defined in a basic block BB1 has multiple definitions in
4364	basic blocks in BB1's dominance frontier.
4365
4366	So, the in-set of a basic block BB2 is not just the union of the
4367	out-sets of BB2's predecessors, but includes some more bits that come
4368	from the basic blocks of whose dominance frontier BB2 is part (BB1 in
4369	the previous paragraph). I called this set the init-set of BB2.
4370
4371	(Note: I actually use the kill-set only to build the init-set.
4372	gen bits are anyway propagated from BB1 to BB2 by dataflow).
4373
4374	For example, if you have
4375
4376	BB1 : r10 = 0
4377	r11 = 0
4378	if <...> goto BB2 else goto BB3;
4379
4380	BB2 : r10 = 1
4381	r12 = 1
4382	goto BB3;
4383
4384	BB3 :
4385
4386	you have BB3 in BB2's dominance frontier but not in BB1's, so that the
4387	init-set of BB3 includes r10 and r12, but not r11. Note that we do
4388	not need to iterate the dominance frontier, because we do not insert
4389	anything like PHI functions there! Instead, dataflow will take care of
4390	propagating the information to BB3's successors.
4391	---------------------------------------------------------------------------/*
4392
4393	/ Private data used to verify the solution for this problem. /
4394	struct df_md_problem_data
4395	{
4396	/ An obstack for the bitmaps we need for this problem. /
4397	bitmap_obstack md_bitmaps;
4398	};
4399
4400	/ Scratch var used by transfer functions. This is used to do md analysis*
4401	only for live registers. /*
4402	static bitmap_head df_md_scratch;
4403
4404
4405	static void
4406	df_md_free_bb_info (basic_block bb ATTRIBUTE_UNUSED,
4407	void *vbb_info)
4408	{
4409	class df_md_bb_info bb_info = (class* df_md_bb_info *) vbb_info;
4410	if (bb_info)
4411	{
4412	bitmap_clear (&bb_info->kill);
4413	bitmap_clear (&bb_info->gen);
4414	bitmap_clear (&bb_info->init);
4415	bitmap_clear (&bb_info->in);
4416	bitmap_clear (&bb_info->out);
4417	}
4418	}
4419
4420
4421	/ Allocate or reset bitmaps for DF_MD. The solution bits are*
4422	not touched unless the block is new. /*
4423
4424	static void
4425	df_md_alloc (bitmap all_blocks)
4426	{
4427	unsigned int bb_index;
4428	bitmap_iterator bi;
4429	struct df_md_problem_data *problem_data;
4430
4431	df_grow_bb_info (df_md);
4432	if (df_md->problem_data)
4433	problem_data = (struct df_md_problem_data *) df_md->problem_data;
4434	else
4435	{
4436	problem_data = XNEW (struct df_md_problem_data);
4437	df_md->problem_data = problem_data;
4438	bitmap_obstack_initialize (&problem_data->md_bitmaps);
4439	}
4440	bitmap_initialize (head: &df_md_scratch, obstack: &problem_data->md_bitmaps);
4441
4442	EXECUTE_IF_SET_IN_BITMAP (all_blocks, `0`, bb_index, bi)
4443	{
4444	class df_md_bb_info *bb_info = df_md_get_bb_info (index: bb_index);
4445	/ When bitmaps are already initialized, just clear them. /
4446	if (bb_info->init.obstack)
4447	{
4448	bitmap_clear (&bb_info->init);
4449	bitmap_clear (&bb_info->gen);
4450	bitmap_clear (&bb_info->kill);
4451	bitmap_clear (&bb_info->in);
4452	bitmap_clear (&bb_info->out);
4453	}
4454	else
4455	{
4456	bitmap_initialize (head: &bb_info->init, obstack: &problem_data->md_bitmaps);
4457	bitmap_initialize (head: &bb_info->gen, obstack: &problem_data->md_bitmaps);
4458	bitmap_initialize (head: &bb_info->kill, obstack: &problem_data->md_bitmaps);
4459	bitmap_initialize (head: &bb_info->in, obstack: &problem_data->md_bitmaps);
4460	bitmap_initialize (head: &bb_info->out, obstack: &problem_data->md_bitmaps);
4461	}
4462	}
4463
4464	df_md->optional_p = true;
4465	}
4466
4467	/ Add the effect of the top artificial defs of BB to the multiple definitions*
4468	bitmap LOCAL_MD. /*
4469
4470	void
4471	df_md_simulate_artificial_defs_at_top (basic_block bb, bitmap local_md)
4472	{
4473	int bb_index = bb->index;
4474	df_ref def;
4475	FOR_EACH_ARTIFICIAL_DEF (def, bb_index)
4476	if (DF_REF_FLAGS (def) & DF_REF_AT_TOP)
4477	{
4478	unsigned int dregno = DF_REF_REGNO (def);
4479	if (DF_REF_FLAGS (def)
4480	& (DF_REF_PARTIAL \| DF_REF_CONDITIONAL \| DF_REF_MAY_CLOBBER))
4481	bitmap_set_bit (local_md, dregno);
4482	else
4483	bitmap_clear_bit (local_md, dregno);
4484	}
4485	}
4486
4487
4488	/ Add the effect of the defs of INSN to the reaching definitions bitmap*
4489	LOCAL_MD. /*
4490
4491	void
4492	df_md_simulate_one_insn (basic_block bb ATTRIBUTE_UNUSED, rtx_insn *insn,
4493	bitmap local_md)
4494	{
4495	df_ref def;
4496
4497	FOR_EACH_INSN_DEF (def, insn)
4498	{
4499	unsigned int dregno = DF_REF_REGNO (def);
4500	if ((!(df->changeable_flags & DF_NO_HARD_REGS))
4501	\|\| (dregno >= FIRST_PSEUDO_REGISTER))
4502	{
4503	if (DF_REF_FLAGS (def)
4504	& (DF_REF_PARTIAL \| DF_REF_CONDITIONAL \| DF_REF_MAY_CLOBBER))
4505	bitmap_set_bit (local_md, DF_REF_ID (def));
4506	else
4507	bitmap_clear_bit (local_md, DF_REF_ID (def));
4508	}
4509	}
4510	}
4511
4512	static void
4513	df_md_bb_local_compute_process_def (class df_md_bb_info *bb_info,
4514	df_ref def,
4515	int top_flag)
4516	{
4517	bitmap_clear (&seen_in_insn);
4518
4519	for (; def; def = DF_REF_NEXT_LOC (def))
4520	{
4521	unsigned int dregno = DF_REF_REGNO (def);
4522	if (((!(df->changeable_flags & DF_NO_HARD_REGS))
4523	\|\| (dregno >= FIRST_PSEUDO_REGISTER))
4524	&& top_flag == (DF_REF_FLAGS (def) & DF_REF_AT_TOP))
4525	{
4526	if (!bitmap_bit_p (&seen_in_insn, dregno))
4527	{
4528	if (DF_REF_FLAGS (def)
4529	& (DF_REF_PARTIAL \| DF_REF_CONDITIONAL \| DF_REF_MAY_CLOBBER))
4530	{
4531	bitmap_set_bit (&bb_info->gen, dregno);
4532	bitmap_clear_bit (&bb_info->kill, dregno);
4533	}
4534	else
4535	{
4536	/ When we find a clobber and a regular def,*
4537	make sure the regular def wins. /*
4538	bitmap_set_bit (&seen_in_insn, dregno);
4539	bitmap_set_bit (&bb_info->kill, dregno);
4540	bitmap_clear_bit (&bb_info->gen, dregno);
4541	}
4542	}
4543	}
4544	}
4545	}
4546
4547
4548	/ Compute local multiple def info for basic block BB. /
4549
4550	static void
4551	df_md_bb_local_compute (unsigned int bb_index)
4552	{
4553	basic_block bb = BASIC_BLOCK_FOR_FN (cfun, bb_index);
4554	class df_md_bb_info *bb_info = df_md_get_bb_info (index: bb_index);
4555	rtx_insn *insn;
4556
4557	/ Artificials are only hard regs. /
4558	if (!(df->changeable_flags & DF_NO_HARD_REGS))
4559	df_md_bb_local_compute_process_def (bb_info,
4560	def: df_get_artificial_defs (bb_index),
4561	top_flag: DF_REF_AT_TOP);
4562
4563	FOR_BB_INSNS (bb, insn)
4564	{
4565	unsigned int uid = INSN_UID (insn);
4566	if (!INSN_P (insn))
4567	continue;
4568
4569	df_md_bb_local_compute_process_def (bb_info, DF_INSN_UID_DEFS (uid), top_flag: `0`);
4570	}
4571
4572	if (!(df->changeable_flags & DF_NO_HARD_REGS))
4573	df_md_bb_local_compute_process_def (bb_info,
4574	def: df_get_artificial_defs (bb_index),
4575	top_flag: `0`);
4576	}
4577
4578	/ Compute local reaching def info for each basic block within BLOCKS. /
4579
4580	static void
4581	df_md_local_compute (bitmap all_blocks)
4582	{
4583	unsigned int bb_index, df_bb_index;
4584	bitmap_iterator bi1, bi2;
4585	basic_block bb;
4586	bitmap_head *frontiers;
4587
4588	bitmap_initialize (head: &seen_in_insn, obstack: &bitmap_default_obstack);
4589
4590	EXECUTE_IF_SET_IN_BITMAP (all_blocks, `0`, bb_index, bi1)
4591	{
4592	df_md_bb_local_compute (bb_index);
4593	}
4594
4595	bitmap_release (head: &seen_in_insn);
4596
4597	frontiers = XNEWVEC (bitmap_head, last_basic_block_for_fn (cfun));
4598	FOR_ALL_BB_FN (bb, cfun)
4599	bitmap_initialize (head: &frontiers[bb->index], obstack: &bitmap_default_obstack);
4600
4601	compute_dominance_frontiers (frontiers);
4602
4603	/ Add each basic block's kills to the nodes in the frontier of the BB. /
4604	EXECUTE_IF_SET_IN_BITMAP (all_blocks, `0`, bb_index, bi1)
4605	{
4606	bitmap kill = &df_md_get_bb_info (index: bb_index)->kill;
4607	EXECUTE_IF_SET_IN_BITMAP (&frontiers[bb_index], `0`, df_bb_index, bi2)
4608	{
4609	basic_block bb = BASIC_BLOCK_FOR_FN (cfun, df_bb_index);
4610	if (bitmap_bit_p (all_blocks, df_bb_index))
4611	bitmap_ior_and_into (DST: &df_md_get_bb_info (index: df_bb_index)->init, B: kill,
4612	C: df_get_live_in (bb));
4613	}
4614	}
4615
4616	FOR_ALL_BB_FN (bb, cfun)
4617	bitmap_clear (&frontiers[bb->index]);
4618	free (ptr: frontiers);
4619	}
4620
4621
4622	/ Reset the global solution for recalculation. /
4623
4624	static void
4625	df_md_reset (bitmap all_blocks)
4626	{
4627	unsigned int bb_index;
4628	bitmap_iterator bi;
4629
4630	EXECUTE_IF_SET_IN_BITMAP (all_blocks, `0`, bb_index, bi)
4631	{
4632	class df_md_bb_info *bb_info = df_md_get_bb_info (index: bb_index);
4633	gcc_assert (bb_info);
4634	bitmap_clear (&bb_info->in);
4635	bitmap_clear (&bb_info->out);
4636	}
4637	}
4638
4639	static bool
4640	df_md_transfer_function (int bb_index)
4641	{
4642	basic_block bb = BASIC_BLOCK_FOR_FN (cfun, bb_index);
4643	class df_md_bb_info *bb_info = df_md_get_bb_info (index: bb_index);
4644	bitmap in = &bb_info->in;
4645	bitmap out = &bb_info->out;
4646	bitmap gen = &bb_info->gen;
4647	bitmap kill = &bb_info->kill;
4648
4649	/ We need to use a scratch set here so that the value returned from this*
4650	function invocation properly reflects whether the sets changed in a
4651	significant way; i.e. not just because the live set was anded in. /*
4652	bitmap_and (&df_md_scratch, gen, df_get_live_out (bb));
4653
4654	/ Multiple definitions of a register are not relevant if it is not*
4655	live. Thus we trim the result to the places where it is live. /*
4656	bitmap_and_into (in, df_get_live_in (bb));
4657
4658	return bitmap_ior_and_compl (DST: out, A: &df_md_scratch, B: in, C: kill);
4659	}
4660
4661	/ Initialize the solution bit vectors for problem. /
4662
4663	static void
4664	df_md_init (bitmap all_blocks)
4665	{
4666	unsigned int bb_index;
4667	bitmap_iterator bi;
4668
4669	EXECUTE_IF_SET_IN_BITMAP (all_blocks, `0`, bb_index, bi)
4670	{
4671	class df_md_bb_info *bb_info = df_md_get_bb_info (index: bb_index);
4672
4673	bitmap_copy (&bb_info->in, &bb_info->init);
4674	df_md_transfer_function (bb_index);
4675	}
4676	}
4677
4678	static void
4679	df_md_confluence_0 (basic_block bb)
4680	{
4681	class df_md_bb_info *bb_info = df_md_get_bb_info (index: bb->index);
4682	bitmap_copy (&bb_info->in, &bb_info->init);
4683	}
4684
4685	/ In of target gets or of out of source. /
4686
4687	static bool
4688	df_md_confluence_n (edge e)
4689	{
4690	bitmap op1 = &df_md_get_bb_info (index: e->dest->index)->in;
4691	bitmap op2 = &df_md_get_bb_info (index: e->src->index)->out;
4692
4693	if (e->flags & EDGE_FAKE)
4694	return false;
4695
4696	if (e->flags & EDGE_EH)
4697	{
4698	/ Conservatively treat partially-clobbered registers as surviving*
4699	across the edge; they might or might not, depending on what mode
4700	they have. /*
4701	bitmap_view<HARD_REG_SET> eh_kills (eh_edge_abi.full_reg_clobbers ());
4702	return bitmap_ior_and_compl_into (A: op1, B: op2, C: eh_kills);
4703	}
4704	else
4705	return bitmap_ior_into (op1, op2);
4706	}
4707
4708	/ Free all storage associated with the problem. /
4709
4710	static void
4711	df_md_free (void)
4712	{
4713	struct df_md_problem_data *problem_data
4714	= (struct df_md_problem_data *) df_md->problem_data;
4715
4716	bitmap_release (head: &df_md_scratch);
4717	bitmap_obstack_release (&problem_data->md_bitmaps);
4718	free (ptr: problem_data);
4719	df_md->problem_data = NULL;
4720
4721	df_md->block_info_size = `0`;
4722	free (df_md->block_info);
4723	df_md->block_info = NULL;
4724	free (df_md);
4725	}
4726
4727
4728	/ Debugging info at top of bb. /
4729
4730	static void
4731	df_md_top_dump (basic_block bb, FILE *file)
4732	{
4733	class df_md_bb_info *bb_info = df_md_get_bb_info (index: bb->index);
4734	if (!bb_info)
4735	return;
4736
4737	fprintf (stream: file, format: ";; md in \t");
4738	df_print_regset (file, r: &bb_info->in);
4739	fprintf (stream: file, format: ";; md init \t");
4740	df_print_regset (file, r: &bb_info->init);
4741	fprintf (stream: file, format: ";; md gen \t");
4742	df_print_regset (file, r: &bb_info->gen);
4743	fprintf (stream: file, format: ";; md kill \t");
4744	df_print_regset (file, r: &bb_info->kill);
4745	}
4746
4747	/ Debugging info at bottom of bb. /
4748
4749	static void
4750	df_md_bottom_dump (basic_block bb, FILE *file)
4751	{
4752	class df_md_bb_info *bb_info = df_md_get_bb_info (index: bb->index);
4753	if (!bb_info)
4754	return;
4755
4756	fprintf (stream: file, format: ";; md out \t");
4757	df_print_regset (file, r: &bb_info->out);
4758	}
4759
4760	static const struct df_problem problem_MD =
4761	{
4762	.id: DF_MD, / Problem id. /
4763	.dir: DF_FORWARD, / Direction. /
4764	.alloc_fun: df_md_alloc, / Allocate the problem specific data. /
4765	.reset_fun: df_md_reset, / Reset global information. /
4766	.free_bb_fun: df_md_free_bb_info, / Free basic block info. /
4767	.local_compute_fun: df_md_local_compute, / Local compute function. /
4768	.init_fun: df_md_init, / Init the solution specific data. /
4769	.dataflow_fun: df_worklist_dataflow, / Worklist solver. /
4770	.con_fun_0: df_md_confluence_0, / Confluence operator 0. /
4771	.con_fun_n: df_md_confluence_n, / Confluence operator n. /
4772	.trans_fun: df_md_transfer_function, / Transfer function. /
4773	NULL, / Finalize function. /
4774	.free_fun: df_md_free, / Free all of the problem information. /
4775	.remove_problem_fun: df_md_free, / Remove this problem from the stack of dataflow problems. /
4776	NULL, / Debugging. /
4777	.dump_top_fun: df_md_top_dump, / Debugging start block. /
4778	.dump_bottom_fun: df_md_bottom_dump, / Debugging end block. /
4779	NULL, / Debugging start insn. /
4780	NULL, / Debugging end insn. /
4781	NULL, / Incremental solution verify start. /
4782	NULL, / Incremental solution verify end. /
4783	NULL, / Dependent problem. /
4784	.block_info_elt_size: sizeof (class df_md_bb_info),/ Size of entry of block_info array. /
4785	.tv_id: TV_DF_MD, / Timing variable. /
4786	.free_blocks_on_set_blocks: false / Reset blocks on dropping out of blocks_to_analyze. /
4787	};
4788
4789	/ Create a new MD instance and add it to the existing instance*
4790	of DF. /*
4791
4792	void
4793	df_md_add_problem (void)
4794	{
4795	df_add_problem (&problem_MD);
4796	}
4797
4798
4799
4800

source code of gcc/df-problems.cc