1/* Allocation 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
8This file is part of GCC.
9
10GCC is free software; you can redistribute it and/or modify it under
11the terms of the GNU General Public License as published by the Free
12Software Foundation; either version 3, or (at your option) any later
13version.
14
15GCC is distributed in the hope that it will be useful, but WITHOUT ANY
16WARRANTY; without even the implied warranty of MERCHANTABILITY or
17FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
18for more details.
19
20You should have received a copy of the GNU General Public License
21along with GCC; see the file COPYING3. If not see
22<http://www.gnu.org/licenses/>. */
23
24/*
25OVERVIEW:
26
27The files in this collection (df*.c,df.h) provide a general framework
28for solving dataflow problems. The global dataflow is performed using
29a good implementation of iterative dataflow analysis.
30
31The file df-problems.cc provides problem instance for the most common
32dataflow problems: reaching defs, upward exposed uses, live variables,
33uninitialized variables, def-use chains, and use-def chains. However,
34the interface allows other dataflow problems to be defined as well.
35
36Dataflow analysis is available in most of the rtl backend (the parts
37between pass_df_initialize and pass_df_finish). It is quite likely
38that these boundaries will be expanded in the future. The only
39requirement is that there be a correct control flow graph.
40
41There are three variations of the live variable problem that are
42available whenever dataflow is available. The LR problem finds the
43areas that can reach a use of a variable, the UR problems finds the
44areas that can be reached from a definition of a variable. The LIVE
45problem finds the intersection of these two areas.
46
47There are several optional problems. These can be enabled when they
48are needed and disabled when they are not needed.
49
50Dataflow problems are generally solved in three layers. The bottom
51layer is called scanning where a data structure is built for each rtl
52insn that describes the set of defs and uses of that insn. Scanning
53is generally kept up to date, i.e. as the insns changes, the scanned
54version of that insn changes also. There are various mechanisms for
55making this happen and are described in the INCREMENTAL SCANNING
56section.
57
58In the middle layer, basic blocks are scanned to produce transfer
59functions which describe the effects of that block on the global
60dataflow solution. The transfer functions are only rebuilt if the
61some instruction within the block has changed.
62
63The top layer is the dataflow solution itself. The dataflow solution
64is computed by using an efficient iterative solver and the transfer
65functions. The dataflow solution must be recomputed whenever the
66control changes or if one of the transfer function changes.
67
68
69USAGE:
70
71Here is an example of using the dataflow routines.
72
73 df_[chain,live,note,rd]_add_problem (flags);
74
75 df_set_blocks (blocks);
76
77 df_analyze ();
78
79 df_dump (stderr);
80
81 df_finish_pass (false);
82
83DF_[chain,live,note,rd]_ADD_PROBLEM adds a problem, defined by an
84instance to struct df_problem, to the set of problems solved in this
85instance of df. All calls to add a problem for a given instance of df
86must occur before the first call to DF_ANALYZE.
87
88Problems can be dependent on other problems. For instance, solving
89def-use or use-def chains is dependent on solving reaching
90definitions. As long as these dependencies are listed in the problem
91definition, the order of adding the problems is not material.
92Otherwise, the problems will be solved in the order of calls to
93df_add_problem. Note that it is not necessary to have a problem. In
94that case, df will just be used to do the scanning.
95
96
97
98DF_SET_BLOCKS is an optional call used to define a region of the
99function on which the analysis will be performed. The normal case is
100to analyze the entire function and no call to df_set_blocks is made.
101DF_SET_BLOCKS only effects the blocks that are effected when computing
102the transfer functions and final solution. The insn level information
103is always kept up to date.
104
105When a subset is given, the analysis behaves as if the function only
106contains those blocks and any edges that occur directly between the
107blocks in the set. Care should be taken to call df_set_blocks right
108before the call to analyze in order to eliminate the possibility that
109optimizations that reorder blocks invalidate the bitvector.
110
111DF_ANALYZE causes all of the defined problems to be (re)solved. When
112DF_ANALYZE is completes, the IN and OUT sets for each basic block
113contain the computer information. The DF_*_BB_INFO macros can be used
114to access these bitvectors. All deferred rescannings are down before
115the transfer functions are recomputed.
116
117DF_DUMP can then be called to dump the information produce to some
118file. This calls DF_DUMP_START, to print the information that is not
119basic block specific, and then calls DF_DUMP_TOP and DF_DUMP_BOTTOM
120for each block to print the basic specific information. These parts
121can all be called separately as part of a larger dump function.
122
123
124DF_FINISH_PASS causes df_remove_problem to be called on all of the
125optional problems. It also causes any insns whose scanning has been
126deferred to be rescanned as well as clears all of the changeable flags.
127Setting the pass manager TODO_df_finish flag causes this function to
128be run. However, the pass manager will call df_finish_pass AFTER the
129pass dumping has been done, so if you want to see the results of the
130optional problems in the pass dumps, use the TODO flag rather than
131calling the function yourself.
132
133INCREMENTAL SCANNING
134
135There are four ways of doing the incremental scanning:
136
1371) Immediate rescanning - Calls to df_insn_rescan, df_notes_rescan,
138 df_bb_delete, df_insn_change_bb have been added to most of
139 the low level service functions that maintain the cfg and change
140 rtl. Calling and of these routines many cause some number of insns
141 to be rescanned.
142
143 For most modern rtl passes, this is certainly the easiest way to
144 manage rescanning the insns. This technique also has the advantage
145 that the scanning information is always correct and can be relied
146 upon even after changes have been made to the instructions. This
147 technique is contra indicated in several cases:
148
149 a) If def-use chains OR use-def chains (but not both) are built,
150 using this is SIMPLY WRONG. The problem is that when a ref is
151 deleted that is the target of an edge, there is not enough
152 information to efficiently find the source of the edge and
153 delete the edge. This leaves a dangling reference that may
154 cause problems.
155
156 b) If def-use chains AND use-def chains are built, this may
157 produce unexpected results. The problem is that the incremental
158 scanning of an insn does not know how to repair the chains that
159 point into an insn when the insn changes. So the incremental
160 scanning just deletes the chains that enter and exit the insn
161 being changed. The dangling reference issue in (a) is not a
162 problem here, but if the pass is depending on the chains being
163 maintained after insns have been modified, this technique will
164 not do the correct thing.
165
166 c) If the pass modifies insns several times, this incremental
167 updating may be expensive.
168
169 d) If the pass modifies all of the insns, as does register
170 allocation, it is simply better to rescan the entire function.
171
1722) Deferred rescanning - Calls to df_insn_rescan, df_notes_rescan, and
173 df_insn_delete do not immediately change the insn but instead make
174 a note that the insn needs to be rescanned. The next call to
175 df_analyze, df_finish_pass, or df_process_deferred_rescans will
176 cause all of the pending rescans to be processed.
177
178 This is the technique of choice if either 1a, 1b, or 1c are issues
179 in the pass. In the case of 1a or 1b, a call to df_finish_pass
180 (either manually or via TODO_df_finish) should be made before the
181 next call to df_analyze or df_process_deferred_rescans.
182
183 This mode is also used by a few passes that still rely on note_uses,
184 note_stores and rtx iterators instead of using the DF data. This
185 can be said to fall under case 1c.
186
187 To enable this mode, call df_set_flags (DF_DEFER_INSN_RESCAN).
188 (This mode can be cleared by calling df_clear_flags
189 (DF_DEFER_INSN_RESCAN) but this does not cause the deferred insns to
190 be rescanned.
191
1923) Total rescanning - In this mode the rescanning is disabled.
193 Only when insns are deleted is the df information associated with
194 it also deleted. At the end of the pass, a call must be made to
195 df_insn_rescan_all. This method is used by the register allocator
196 since it generally changes each insn multiple times (once for each ref)
197 and does not need to make use of the updated scanning information.
198
1994) Do it yourself - In this mechanism, the pass updates the insns
200 itself using the low level df primitives. Currently no pass does
201 this, but it has the advantage that it is quite efficient given
202 that the pass generally has exact knowledge of what it is changing.
203
204DATA STRUCTURES
205
206Scanning produces a `struct df_ref' data structure (ref) is allocated
207for every register reference (def or use) and this records the insn
208and bb the ref is found within. The refs are linked together in
209chains of uses and defs for each insn and for each register. Each ref
210also has a chain field that links all the use refs for a def or all
211the def refs for a use. This is used to create use-def or def-use
212chains.
213
214Different optimizations have different needs. Ultimately, only
215register allocation and schedulers should be using the bitmaps
216produced for the live register and uninitialized register problems.
217The rest of the backend should be upgraded to using and maintaining
218the linked information such as def use or use def chains.
219
220
221PHILOSOPHY:
222
223While incremental bitmaps are not worthwhile to maintain, incremental
224chains may be perfectly reasonable. The fastest way to build chains
225from scratch or after significant modifications is to build reaching
226definitions (RD) and build the chains from this.
227
228However, general algorithms for maintaining use-def or def-use chains
229are not practical. The amount of work to recompute the chain any
230chain after an arbitrary change is large. However, with a modest
231amount of work it is generally possible to have the application that
232uses the chains keep them up to date. The high level knowledge of
233what is really happening is essential to crafting efficient
234incremental algorithms.
235
236As for the bit vector problems, there is no interface to give a set of
237blocks over with to resolve the iteration. In general, restarting a
238dataflow iteration is difficult and expensive. Again, the best way to
239keep the dataflow information up to data (if this is really what is
240needed) it to formulate a problem specific solution.
241
242There are fine grained calls for creating and deleting references from
243instructions in df-scan.cc. However, these are not currently connected
244to the engine that resolves the dataflow equations.
245
246
247DATA STRUCTURES:
248
249The basic object is a DF_REF (reference) and this may either be a
250DEF (definition) or a USE of a register.
251
252These are linked into a variety of lists; namely reg-def, reg-use,
253insn-def, insn-use, def-use, and use-def lists. For example, the
254reg-def lists contain all the locations that define a given register
255while the insn-use lists contain all the locations that use a
256register.
257
258Note that the reg-def and reg-use chains are generally short for
259pseudos and long for the hard registers.
260
261ACCESSING INSNS:
262
2631) The df insn information is kept in an array of DF_INSN_INFO objects.
264 The array is indexed by insn uid, and every DF_REF points to the
265 DF_INSN_INFO object of the insn that contains the reference.
266
2672) Each insn has three sets of refs, which are linked into one of three
268 lists: The insn's defs list (accessed by the DF_INSN_INFO_DEFS,
269 DF_INSN_DEFS, or DF_INSN_UID_DEFS macros), the insn's uses list
270 (accessed by the DF_INSN_INFO_USES, DF_INSN_USES, or
271 DF_INSN_UID_USES macros) or the insn's eq_uses list (accessed by the
272 DF_INSN_INFO_EQ_USES, DF_INSN_EQ_USES or DF_INSN_UID_EQ_USES macros).
273 The latter list are the list of references in REG_EQUAL or REG_EQUIV
274 notes. These macros produce a ref (or NULL), the rest of the list
275 can be obtained by traversal of the NEXT_REF field (accessed by the
276 DF_REF_NEXT_REF macro.) There is no significance to the ordering of
277 the uses or refs in an instruction.
278
2793) Each insn has a logical uid field (LUID) which is stored in the
280 DF_INSN_INFO object for the insn. The LUID field is accessed by
281 the DF_INSN_INFO_LUID, DF_INSN_LUID, and DF_INSN_UID_LUID macros.
282 When properly set, the LUID is an integer that numbers each insn in
283 the basic block, in order from the start of the block.
284 The numbers are only correct after a call to df_analyze. They will
285 rot after insns are added deleted or moved round.
286
287ACCESSING REFS:
288
289There are 4 ways to obtain access to refs:
290
2911) References are divided into two categories, REAL and ARTIFICIAL.
292
293 REAL refs are associated with instructions.
294
295 ARTIFICIAL refs are associated with basic blocks. The heads of
296 these lists can be accessed by calling df_get_artificial_defs or
297 df_get_artificial_uses for the particular basic block.
298
299 Artificial defs and uses occur both at the beginning and ends of blocks.
300
301 For blocks that are at the destination of eh edges, the
302 artificial uses and defs occur at the beginning. The defs relate
303 to the registers specified in EH_RETURN_DATA_REGNO and the uses
304 relate to the registers specified in EH_USES. Logically these
305 defs and uses should really occur along the eh edge, but there is
306 no convenient way to do this. Artificial defs that occur at the
307 beginning of the block have the DF_REF_AT_TOP flag set.
308
309 Artificial uses occur at the end of all blocks. These arise from
310 the hard registers that are always live, such as the stack
311 register and are put there to keep the code from forgetting about
312 them.
313
314 Artificial defs occur at the end of the entry block. These arise
315 from registers that are live at entry to the function.
316
3172) There are three types of refs: defs, uses and eq_uses. (Eq_uses are
318 uses that appear inside a REG_EQUAL or REG_EQUIV note.)
319
320 All of the eq_uses, uses and defs associated with each pseudo or
321 hard register may be linked in a bidirectional chain. These are
322 called reg-use or reg_def chains. If the changeable flag
323 DF_EQ_NOTES is set when the chains are built, the eq_uses will be
324 treated like uses. If it is not set they are ignored.
325
326 The first use, eq_use or def for a register can be obtained using
327 the DF_REG_USE_CHAIN, DF_REG_EQ_USE_CHAIN or DF_REG_DEF_CHAIN
328 macros. Subsequent uses for the same regno can be obtained by
329 following the next_reg field of the ref. The number of elements in
330 each of the chains can be found by using the DF_REG_USE_COUNT,
331 DF_REG_EQ_USE_COUNT or DF_REG_DEF_COUNT macros.
332
333 In previous versions of this code, these chains were ordered. It
334 has not been practical to continue this practice.
335
3363) If def-use or use-def chains are built, these can be traversed to
337 get to other refs. If the flag DF_EQ_NOTES has been set, the chains
338 include the eq_uses. Otherwise these are ignored when building the
339 chains.
340
3414) An array of all of the uses (and an array of all of the defs) can
342 be built. These arrays are indexed by the value in the id
343 structure. These arrays are only lazily kept up to date, and that
344 process can be expensive. To have these arrays built, call
345 df_reorganize_defs or df_reorganize_uses. If the flag DF_EQ_NOTES
346 has been set the array will contain the eq_uses. Otherwise these
347 are ignored when building the array and assigning the ids. Note
348 that the values in the id field of a ref may change across calls to
349 df_analyze or df_reorganize_defs or df_reorganize_uses.
350
351 If the only use of this array is to find all of the refs, it is
352 better to traverse all of the registers and then traverse all of
353 reg-use or reg-def chains.
354
355NOTES:
356
357Embedded addressing side-effects, such as POST_INC or PRE_INC, generate
358both a use and a def. These are both marked read/write to show that they
359are dependent. For example, (set (reg 40) (mem (post_inc (reg 42))))
360will generate a use of reg 42 followed by a def of reg 42 (both marked
361read/write). Similarly, (set (reg 40) (mem (pre_dec (reg 41))))
362generates a use of reg 41 then a def of reg 41 (both marked read/write),
363even though reg 41 is decremented before it is used for the memory
364address in this second example.
365
366A set to a REG inside a ZERO_EXTRACT, or a set to a non-paradoxical SUBREG
367for which the number of word_mode units covered by the outer mode is
368smaller than that covered by the inner mode, invokes a read-modify-write
369operation. We generate both a use and a def and again mark them
370read/write.
371
372Paradoxical subreg writes do not leave a trace of the old content, so they
373are write-only operations.
374*/
375
376
377#include "config.h"
378#include "system.h"
379#include "coretypes.h"
380#include "backend.h"
381#include "rtl.h"
382#include "df.h"
383#include "memmodel.h"
384#include "emit-rtl.h"
385#include "cfganal.h"
386#include "tree-pass.h"
387#include "cfgloop.h"
388
389static void *df_get_bb_info (struct dataflow *, unsigned int);
390static void df_set_bb_info (struct dataflow *, unsigned int, void *);
391static void df_clear_bb_info (struct dataflow *, unsigned int);
392#ifdef DF_DEBUG_CFG
393static void df_set_clean_cfg (void);
394#endif
395
396/* The obstack on which regsets are allocated. */
397struct bitmap_obstack reg_obstack;
398
399/* An obstack for bitmap not related to specific dataflow problems.
400 This obstack should e.g. be used for bitmaps with a short life time
401 such as temporary bitmaps. */
402
403bitmap_obstack df_bitmap_obstack;
404
405
406/*----------------------------------------------------------------------------
407 Functions to create, destroy and manipulate an instance of df.
408----------------------------------------------------------------------------*/
409
410class df_d *df;
411
412/* Add PROBLEM (and any dependent problems) to the DF instance. */
413
414void
415df_add_problem (const struct df_problem *problem)
416{
417 struct dataflow *dflow;
418 int i;
419
420 /* First try to add the dependent problem. */
421 if (problem->dependent_problem)
422 df_add_problem (problem: problem->dependent_problem);
423
424 /* Check to see if this problem has already been defined. If it
425 has, just return that instance, if not, add it to the end of the
426 vector. */
427 dflow = df->problems_by_index[problem->id];
428 if (dflow)
429 return;
430
431 /* Make a new one and add it to the end. */
432 dflow = XCNEW (struct dataflow);
433 dflow->problem = problem;
434 dflow->computed = false;
435 dflow->solutions_dirty = true;
436 df->problems_by_index[dflow->problem->id] = dflow;
437
438 /* Keep the defined problems ordered by index. This solves the
439 problem that RI will use the information from UREC if UREC has
440 been defined, or from LIVE if LIVE is defined and otherwise LR.
441 However for this to work, the computation of RI must be pushed
442 after which ever of those problems is defined, but we do not
443 require any of those except for LR to have actually been
444 defined. */
445 df->num_problems_defined++;
446 for (i = df->num_problems_defined - 2; i >= 0; i--)
447 {
448 if (problem->id < df->problems_in_order[i]->problem->id)
449 df->problems_in_order[i+1] = df->problems_in_order[i];
450 else
451 {
452 df->problems_in_order[i+1] = dflow;
453 return;
454 }
455 }
456 df->problems_in_order[0] = dflow;
457}
458
459
460/* Set the MASK flags in the DFLOW problem. The old flags are
461 returned. If a flag is not allowed to be changed this will fail if
462 checking is enabled. */
463int
464df_set_flags (int changeable_flags)
465{
466 int old_flags = df->changeable_flags;
467 df->changeable_flags |= changeable_flags;
468 return old_flags;
469}
470
471
472/* Clear the MASK flags in the DFLOW problem. The old flags are
473 returned. If a flag is not allowed to be changed this will fail if
474 checking is enabled. */
475int
476df_clear_flags (int changeable_flags)
477{
478 int old_flags = df->changeable_flags;
479 df->changeable_flags &= ~changeable_flags;
480 return old_flags;
481}
482
483
484/* Set the blocks that are to be considered for analysis. If this is
485 not called or is called with null, the entire function in
486 analyzed. */
487
488void
489df_set_blocks (bitmap blocks)
490{
491 if (blocks)
492 {
493 if (dump_file)
494 bitmap_print (dump_file, blocks, "setting blocks to analyze ", "\n");
495 if (df->blocks_to_analyze)
496 {
497 /* This block is called to change the focus from one subset
498 to another. */
499 int p;
500 auto_bitmap diff (&df_bitmap_obstack);
501 bitmap_and_compl (diff, df->blocks_to_analyze, blocks);
502 for (p = 0; p < df->num_problems_defined; p++)
503 {
504 struct dataflow *dflow = df->problems_in_order[p];
505 if (dflow->optional_p && dflow->problem->reset_fun)
506 dflow->problem->reset_fun (df->blocks_to_analyze);
507 else if (dflow->problem->free_blocks_on_set_blocks)
508 {
509 bitmap_iterator bi;
510 unsigned int bb_index;
511
512 EXECUTE_IF_SET_IN_BITMAP (diff, 0, bb_index, bi)
513 {
514 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, bb_index);
515 if (bb)
516 {
517 void *bb_info = df_get_bb_info (dflow, bb_index);
518 dflow->problem->free_bb_fun (bb, bb_info);
519 df_clear_bb_info (dflow, bb_index);
520 }
521 }
522 }
523 }
524 }
525 else
526 {
527 /* This block of code is executed to change the focus from
528 the entire function to a subset. */
529 bitmap_head blocks_to_reset;
530 bool initialized = false;
531 int p;
532 for (p = 0; p < df->num_problems_defined; p++)
533 {
534 struct dataflow *dflow = df->problems_in_order[p];
535 if (dflow->optional_p && dflow->problem->reset_fun)
536 {
537 if (!initialized)
538 {
539 basic_block bb;
540 bitmap_initialize (head: &blocks_to_reset, obstack: &df_bitmap_obstack);
541 FOR_ALL_BB_FN (bb, cfun)
542 {
543 bitmap_set_bit (&blocks_to_reset, bb->index);
544 }
545 }
546 dflow->problem->reset_fun (&blocks_to_reset);
547 }
548 }
549 if (initialized)
550 bitmap_clear (&blocks_to_reset);
551
552 df->blocks_to_analyze = BITMAP_ALLOC (obstack: &df_bitmap_obstack);
553 }
554 bitmap_copy (df->blocks_to_analyze, blocks);
555 df->analyze_subset = true;
556 }
557 else
558 {
559 /* This block is executed to reset the focus to the entire
560 function. */
561 if (dump_file)
562 fprintf (stream: dump_file, format: "clearing blocks_to_analyze\n");
563 if (df->blocks_to_analyze)
564 {
565 BITMAP_FREE (df->blocks_to_analyze);
566 df->blocks_to_analyze = NULL;
567 }
568 df->analyze_subset = false;
569 }
570
571 /* Setting the blocks causes the refs to be unorganized since only
572 the refs in the blocks are seen. */
573 df_maybe_reorganize_def_refs (DF_REF_ORDER_NO_TABLE);
574 df_maybe_reorganize_use_refs (DF_REF_ORDER_NO_TABLE);
575 df_mark_solutions_dirty ();
576}
577
578
579/* Delete a DFLOW problem (and any problems that depend on this
580 problem). */
581
582void
583df_remove_problem (struct dataflow *dflow)
584{
585 const struct df_problem *problem;
586 int i;
587
588 if (!dflow)
589 return;
590
591 problem = dflow->problem;
592 gcc_assert (problem->remove_problem_fun);
593
594 /* Delete any problems that depended on this problem first. */
595 for (i = 0; i < df->num_problems_defined; i++)
596 if (df->problems_in_order[i]->problem->dependent_problem == problem)
597 df_remove_problem (dflow: df->problems_in_order[i]);
598
599 /* Now remove this problem. */
600 for (i = 0; i < df->num_problems_defined; i++)
601 if (df->problems_in_order[i] == dflow)
602 {
603 int j;
604 for (j = i + 1; j < df->num_problems_defined; j++)
605 df->problems_in_order[j-1] = df->problems_in_order[j];
606 df->problems_in_order[j-1] = NULL;
607 df->num_problems_defined--;
608 break;
609 }
610
611 (problem->remove_problem_fun) ();
612 df->problems_by_index[problem->id] = NULL;
613}
614
615
616/* Remove all of the problems that are not permanent. Scanning, LR
617 and (at -O2 or higher) LIVE are permanent, the rest are removable.
618 Also clear all of the changeable_flags. */
619
620void
621df_finish_pass (bool verify ATTRIBUTE_UNUSED)
622{
623 int i;
624
625#ifdef ENABLE_DF_CHECKING
626 int saved_flags;
627#endif
628
629 if (!df)
630 return;
631
632 df_maybe_reorganize_def_refs (DF_REF_ORDER_NO_TABLE);
633 df_maybe_reorganize_use_refs (DF_REF_ORDER_NO_TABLE);
634
635#ifdef ENABLE_DF_CHECKING
636 saved_flags = df->changeable_flags;
637#endif
638
639 /* We iterate over problems by index as each problem removed will
640 lead to problems_in_order to be reordered. */
641 for (i = 0; i < DF_LAST_PROBLEM_PLUS1; i++)
642 {
643 struct dataflow *dflow = df->problems_by_index[i];
644
645 if (dflow && dflow->optional_p)
646 df_remove_problem (dflow);
647 }
648
649 /* Clear all of the flags. */
650 df->changeable_flags = 0;
651 df_process_deferred_rescans ();
652
653 /* Set the focus back to the whole function. */
654 if (df->blocks_to_analyze)
655 {
656 BITMAP_FREE (df->blocks_to_analyze);
657 df->blocks_to_analyze = NULL;
658 df_mark_solutions_dirty ();
659 df->analyze_subset = false;
660 }
661
662#ifdef ENABLE_DF_CHECKING
663 /* Verification will fail in DF_NO_INSN_RESCAN. */
664 if (!(saved_flags & DF_NO_INSN_RESCAN))
665 {
666 df_lr_verify_transfer_functions ();
667 if (df_live)
668 df_live_verify_transfer_functions ();
669 }
670
671#ifdef DF_DEBUG_CFG
672 df_set_clean_cfg ();
673#endif
674#endif
675
676 if (flag_checking && verify)
677 df->changeable_flags |= DF_VERIFY_SCHEDULED;
678}
679
680
681/* Set up the dataflow instance for the entire back end. */
682
683static unsigned int
684rest_of_handle_df_initialize (void)
685{
686 gcc_assert (!df);
687 df = XCNEW (class df_d);
688 df->changeable_flags = 0;
689
690 bitmap_obstack_initialize (&df_bitmap_obstack);
691
692 /* Set this to a conservative value. Stack_ptr_mod will compute it
693 correctly later. */
694 crtl->sp_is_unchanging = 0;
695
696 df_scan_add_problem ();
697 df_scan_alloc (NULL);
698
699 /* These three problems are permanent. */
700 df_lr_add_problem ();
701 if (optimize > 1)
702 df_live_add_problem ();
703
704 df->hard_regs_live_count = XCNEWVEC (unsigned int, FIRST_PSEUDO_REGISTER);
705
706 df_hard_reg_init ();
707 /* After reload, some ports add certain bits to regs_ever_live so
708 this cannot be reset. */
709 df_compute_regs_ever_live (true);
710 df_scan_blocks ();
711 df_compute_regs_ever_live (false);
712 return 0;
713}
714
715
716namespace {
717
718const pass_data pass_data_df_initialize_opt =
719{
720 .type: RTL_PASS, /* type */
721 .name: "dfinit", /* name */
722 .optinfo_flags: OPTGROUP_NONE, /* optinfo_flags */
723 .tv_id: TV_DF_SCAN, /* tv_id */
724 .properties_required: 0, /* properties_required */
725 .properties_provided: 0, /* properties_provided */
726 .properties_destroyed: 0, /* properties_destroyed */
727 .todo_flags_start: 0, /* todo_flags_start */
728 .todo_flags_finish: 0, /* todo_flags_finish */
729};
730
731class pass_df_initialize_opt : public rtl_opt_pass
732{
733public:
734 pass_df_initialize_opt (gcc::context *ctxt)
735 : rtl_opt_pass (pass_data_df_initialize_opt, ctxt)
736 {}
737
738 /* opt_pass methods: */
739 bool gate (function *) final override { return optimize > 0; }
740 unsigned int execute (function *) final override
741 {
742 return rest_of_handle_df_initialize ();
743 }
744
745}; // class pass_df_initialize_opt
746
747} // anon namespace
748
749rtl_opt_pass *
750make_pass_df_initialize_opt (gcc::context *ctxt)
751{
752 return new pass_df_initialize_opt (ctxt);
753}
754
755
756namespace {
757
758const pass_data pass_data_df_initialize_no_opt =
759{
760 .type: RTL_PASS, /* type */
761 .name: "no-opt dfinit", /* name */
762 .optinfo_flags: OPTGROUP_NONE, /* optinfo_flags */
763 .tv_id: TV_DF_SCAN, /* tv_id */
764 .properties_required: 0, /* properties_required */
765 .properties_provided: 0, /* properties_provided */
766 .properties_destroyed: 0, /* properties_destroyed */
767 .todo_flags_start: 0, /* todo_flags_start */
768 .todo_flags_finish: 0, /* todo_flags_finish */
769};
770
771class pass_df_initialize_no_opt : public rtl_opt_pass
772{
773public:
774 pass_df_initialize_no_opt (gcc::context *ctxt)
775 : rtl_opt_pass (pass_data_df_initialize_no_opt, ctxt)
776 {}
777
778 /* opt_pass methods: */
779 bool gate (function *) final override { return optimize == 0; }
780 unsigned int execute (function *) final override
781 {
782 return rest_of_handle_df_initialize ();
783 }
784
785}; // class pass_df_initialize_no_opt
786
787} // anon namespace
788
789rtl_opt_pass *
790make_pass_df_initialize_no_opt (gcc::context *ctxt)
791{
792 return new pass_df_initialize_no_opt (ctxt);
793}
794
795
796/* Free all the dataflow info and the DF structure. This should be
797 called from the df_finish macro which also NULLs the parm. */
798
799static unsigned int
800rest_of_handle_df_finish (void)
801{
802 int i;
803
804 gcc_assert (df);
805
806 for (i = 0; i < df->num_problems_defined; i++)
807 {
808 struct dataflow *dflow = df->problems_in_order[i];
809 dflow->problem->free_fun ();
810 }
811
812 free (ptr: df->postorder);
813 free (ptr: df->postorder_inverted);
814 free (ptr: df->hard_regs_live_count);
815 free (ptr: df);
816 df = NULL;
817
818 bitmap_obstack_release (&df_bitmap_obstack);
819 return 0;
820}
821
822
823namespace {
824
825const pass_data pass_data_df_finish =
826{
827 .type: RTL_PASS, /* type */
828 .name: "dfinish", /* name */
829 .optinfo_flags: OPTGROUP_NONE, /* optinfo_flags */
830 .tv_id: TV_NONE, /* tv_id */
831 .properties_required: 0, /* properties_required */
832 .properties_provided: 0, /* properties_provided */
833 .properties_destroyed: 0, /* properties_destroyed */
834 .todo_flags_start: 0, /* todo_flags_start */
835 .todo_flags_finish: 0, /* todo_flags_finish */
836};
837
838class pass_df_finish : public rtl_opt_pass
839{
840public:
841 pass_df_finish (gcc::context *ctxt)
842 : rtl_opt_pass (pass_data_df_finish, ctxt)
843 {}
844
845 /* opt_pass methods: */
846 unsigned int execute (function *) final override
847 {
848 return rest_of_handle_df_finish ();
849 }
850
851}; // class pass_df_finish
852
853} // anon namespace
854
855rtl_opt_pass *
856make_pass_df_finish (gcc::context *ctxt)
857{
858 return new pass_df_finish (ctxt);
859}
860
861
862
863
864
865/*----------------------------------------------------------------------------
866 The general data flow analysis engine.
867----------------------------------------------------------------------------*/
868
869/* Helper function for df_worklist_dataflow.
870 Propagate the dataflow forward.
871 Given a BB_INDEX, do the dataflow propagation
872 and set bits on for successors in PENDING for earlier
873 and WORKLIST for later in bbindex_to_postorder
874 if the out set of the dataflow has changed.
875
876 AGE specify time when BB was visited last time.
877 AGE of 0 means we are visiting for first time and need to
878 compute transfer function to initialize datastructures.
879 Otherwise we re-do transfer function only if something change
880 while computing confluence functions.
881 We need to compute confluence only of basic block that are younger
882 then last visit of the BB.
883
884 Return true if BB info has changed. This is always the case
885 in the first visit. */
886
887static bool
888df_worklist_propagate_forward (struct dataflow *dataflow,
889 unsigned bb_index,
890 unsigned *bbindex_to_postorder,
891 bitmap worklist,
892 bitmap pending,
893 sbitmap considered,
894 vec<int> &last_change_age,
895 int age)
896{
897 edge e;
898 edge_iterator ei;
899 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, bb_index);
900 bool changed = !age;
901
902 /* Calculate <conf_op> of incoming edges. */
903 if (EDGE_COUNT (bb->preds) > 0)
904 FOR_EACH_EDGE (e, ei, bb->preds)
905 {
906 if (bbindex_to_postorder[e->src->index] < last_change_age.length ()
907 && age <= last_change_age[bbindex_to_postorder[e->src->index]]
908 && bitmap_bit_p (map: considered, bitno: e->src->index))
909 changed |= dataflow->problem->con_fun_n (e);
910 }
911 else if (dataflow->problem->con_fun_0)
912 dataflow->problem->con_fun_0 (bb);
913
914 if (changed
915 && dataflow->problem->trans_fun (bb_index))
916 {
917 /* The out set of this block has changed.
918 Propagate to the outgoing blocks. */
919 FOR_EACH_EDGE (e, ei, bb->succs)
920 {
921 unsigned ob_index = e->dest->index;
922
923 if (bitmap_bit_p (map: considered, bitno: ob_index))
924 {
925 if (bbindex_to_postorder[bb_index]
926 < bbindex_to_postorder[ob_index])
927 bitmap_set_bit (worklist, bbindex_to_postorder[ob_index]);
928 else
929 bitmap_set_bit (pending, bbindex_to_postorder[ob_index]);
930 }
931 }
932 return true;
933 }
934 return false;
935}
936
937
938/* Helper function for df_worklist_dataflow.
939 Propagate the dataflow backward. */
940
941static bool
942df_worklist_propagate_backward (struct dataflow *dataflow,
943 unsigned bb_index,
944 unsigned *bbindex_to_postorder,
945 bitmap worklist,
946 bitmap pending,
947 sbitmap considered,
948 vec<int> &last_change_age,
949 int age)
950{
951 edge e;
952 edge_iterator ei;
953 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, bb_index);
954 bool changed = !age;
955
956 /* Calculate <conf_op> of incoming edges. */
957 if (EDGE_COUNT (bb->succs) > 0)
958 FOR_EACH_EDGE (e, ei, bb->succs)
959 {
960 if (bbindex_to_postorder[e->dest->index] < last_change_age.length ()
961 && age <= last_change_age[bbindex_to_postorder[e->dest->index]]
962 && bitmap_bit_p (map: considered, bitno: e->dest->index))
963 changed |= dataflow->problem->con_fun_n (e);
964 }
965 else if (dataflow->problem->con_fun_0)
966 dataflow->problem->con_fun_0 (bb);
967
968 if (changed
969 && dataflow->problem->trans_fun (bb_index))
970 {
971 /* The out set of this block has changed.
972 Propagate to the outgoing blocks. */
973 FOR_EACH_EDGE (e, ei, bb->preds)
974 {
975 unsigned ob_index = e->src->index;
976
977 if (bitmap_bit_p (map: considered, bitno: ob_index))
978 {
979 if (bbindex_to_postorder[bb_index]
980 < bbindex_to_postorder[ob_index])
981 bitmap_set_bit (worklist, bbindex_to_postorder[ob_index]);
982 else
983 bitmap_set_bit (pending, bbindex_to_postorder[ob_index]);
984 }
985 }
986 return true;
987 }
988 return false;
989}
990
991/* Main dataflow solver loop.
992
993 DATAFLOW is problem we are solving, PENDING is worklist of basic blocks we
994 need to visit.
995 BLOCK_IN_POSTORDER is array of size N_BLOCKS specifying postorder in BBs and
996 BBINDEX_TO_POSTORDER is array mapping back BB->index to postorder position.
997 PENDING will be freed.
998
999 The worklists are bitmaps indexed by postorder positions.
1000
1001 The function implements standard algorithm for dataflow solving with two
1002 worklists (we are processing WORKLIST and storing new BBs to visit in
1003 PENDING).
1004
1005 As an optimization we maintain ages when BB was changed (stored in
1006 last_change_age) and when it was last visited (stored in last_visit_age).
1007 This avoids need to re-do confluence function for edges to basic blocks
1008 whose source did not change since destination was visited last time. */
1009
1010static void
1011df_worklist_dataflow_doublequeue (struct dataflow *dataflow,
1012 bitmap pending,
1013 sbitmap considered,
1014 int *blocks_in_postorder,
1015 unsigned *bbindex_to_postorder,
1016 int n_blocks)
1017{
1018 enum df_flow_dir dir = dataflow->problem->dir;
1019 int dcount = 0;
1020 bitmap worklist = BITMAP_ALLOC (obstack: &df_bitmap_obstack);
1021 int age = 0;
1022 bool changed;
1023 vec<int> last_visit_age = vNULL;
1024 vec<int> last_change_age = vNULL;
1025 int prev_age;
1026
1027 last_visit_age.safe_grow_cleared (len: n_blocks, exact: true);
1028 last_change_age.safe_grow_cleared (len: n_blocks, exact: true);
1029
1030 /* Double-queueing. Worklist is for the current iteration,
1031 and pending is for the next. */
1032 while (!bitmap_empty_p (map: pending))
1033 {
1034 std::swap (a&: pending, b&: worklist);
1035
1036 do
1037 {
1038 unsigned index = bitmap_clear_first_set_bit (worklist);
1039
1040 unsigned bb_index;
1041 dcount++;
1042
1043 bb_index = blocks_in_postorder[index];
1044 prev_age = last_visit_age[index];
1045 if (dir == DF_FORWARD)
1046 changed = df_worklist_propagate_forward (dataflow, bb_index,
1047 bbindex_to_postorder,
1048 worklist, pending,
1049 considered,
1050 last_change_age,
1051 age: prev_age);
1052 else
1053 changed = df_worklist_propagate_backward (dataflow, bb_index,
1054 bbindex_to_postorder,
1055 worklist, pending,
1056 considered,
1057 last_change_age,
1058 age: prev_age);
1059 last_visit_age[index] = ++age;
1060 if (changed)
1061 last_change_age[index] = age;
1062 }
1063 while (!bitmap_empty_p (map: worklist));
1064 }
1065
1066 BITMAP_FREE (worklist);
1067 BITMAP_FREE (pending);
1068 last_visit_age.release ();
1069 last_change_age.release ();
1070
1071 /* Dump statistics. */
1072 if (dump_file)
1073 fprintf (stream: dump_file, format: "df_worklist_dataflow_doublequeue:"
1074 " n_basic_blocks %d n_edges %d"
1075 " count %d (%5.2g)\n",
1076 n_basic_blocks_for_fn (cfun), n_edges_for_fn (cfun),
1077 dcount, dcount / (double)n_basic_blocks_for_fn (cfun));
1078}
1079
1080/* Worklist-based dataflow solver. It uses sbitmap as a worklist,
1081 with "n"-th bit representing the n-th block in the reverse-postorder order.
1082 The solver is a double-queue algorithm similar to the "double stack" solver
1083 from Cooper, Harvey and Kennedy, "Iterative data-flow analysis, Revisited".
1084 The only significant difference is that the worklist in this implementation
1085 is always sorted in RPO of the CFG visiting direction. */
1086
1087void
1088df_worklist_dataflow (struct dataflow *dataflow,
1089 bitmap blocks_to_consider,
1090 int *blocks_in_postorder,
1091 int n_blocks)
1092{
1093 bitmap pending = BITMAP_ALLOC (obstack: &df_bitmap_obstack);
1094 bitmap_iterator bi;
1095 unsigned int *bbindex_to_postorder;
1096 int i;
1097 unsigned int index;
1098 enum df_flow_dir dir = dataflow->problem->dir;
1099
1100 gcc_assert (dir != DF_NONE);
1101
1102 /* BBINDEX_TO_POSTORDER maps the bb->index to the reverse postorder. */
1103 bbindex_to_postorder = XNEWVEC (unsigned int,
1104 last_basic_block_for_fn (cfun));
1105
1106 /* Initialize the array to an out-of-bound value. */
1107 for (i = 0; i < last_basic_block_for_fn (cfun); i++)
1108 bbindex_to_postorder[i] = last_basic_block_for_fn (cfun);
1109
1110 /* Initialize the considered map. */
1111 auto_sbitmap considered (last_basic_block_for_fn (cfun));
1112 bitmap_clear (considered);
1113 EXECUTE_IF_SET_IN_BITMAP (blocks_to_consider, 0, index, bi)
1114 {
1115 bitmap_set_bit (map: considered, bitno: index);
1116 }
1117
1118 /* Initialize the mapping of block index to postorder. */
1119 for (i = 0; i < n_blocks; i++)
1120 {
1121 bbindex_to_postorder[blocks_in_postorder[i]] = i;
1122 /* Add all blocks to the worklist. */
1123 bitmap_set_bit (pending, i);
1124 }
1125
1126 /* Initialize the problem. */
1127 if (dataflow->problem->init_fun)
1128 dataflow->problem->init_fun (blocks_to_consider);
1129
1130 /* Solve it. */
1131 df_worklist_dataflow_doublequeue (dataflow, pending, considered,
1132 blocks_in_postorder,
1133 bbindex_to_postorder,
1134 n_blocks);
1135 free (ptr: bbindex_to_postorder);
1136}
1137
1138
1139/* Remove the entries not in BLOCKS from the LIST of length LEN, preserving
1140 the order of the remaining entries. Returns the length of the resulting
1141 list. */
1142
1143static unsigned
1144df_prune_to_subcfg (int list[], unsigned len, bitmap blocks)
1145{
1146 unsigned act, last;
1147
1148 for (act = 0, last = 0; act < len; act++)
1149 if (bitmap_bit_p (blocks, list[act]))
1150 list[last++] = list[act];
1151
1152 return last;
1153}
1154
1155
1156/* Execute dataflow analysis on a single dataflow problem.
1157
1158 BLOCKS_TO_CONSIDER are the blocks whose solution can either be
1159 examined or will be computed. For calls from DF_ANALYZE, this is
1160 the set of blocks that has been passed to DF_SET_BLOCKS.
1161*/
1162
1163void
1164df_analyze_problem (struct dataflow *dflow,
1165 bitmap blocks_to_consider,
1166 int *postorder, int n_blocks)
1167{
1168 timevar_push (tv: dflow->problem->tv_id);
1169
1170 /* (Re)Allocate the datastructures necessary to solve the problem. */
1171 if (dflow->problem->alloc_fun)
1172 dflow->problem->alloc_fun (blocks_to_consider);
1173
1174#ifdef ENABLE_DF_CHECKING
1175 if (dflow->problem->verify_start_fun)
1176 dflow->problem->verify_start_fun ();
1177#endif
1178
1179 /* Set up the problem and compute the local information. */
1180 if (dflow->problem->local_compute_fun)
1181 dflow->problem->local_compute_fun (blocks_to_consider);
1182
1183 /* Solve the equations. */
1184 if (dflow->problem->dataflow_fun)
1185 dflow->problem->dataflow_fun (dflow, blocks_to_consider,
1186 postorder, n_blocks);
1187
1188 /* Massage the solution. */
1189 if (dflow->problem->finalize_fun)
1190 dflow->problem->finalize_fun (blocks_to_consider);
1191
1192#ifdef ENABLE_DF_CHECKING
1193 if (dflow->problem->verify_end_fun)
1194 dflow->problem->verify_end_fun ();
1195#endif
1196
1197 timevar_pop (tv: dflow->problem->tv_id);
1198
1199 dflow->computed = true;
1200}
1201
1202
1203/* Analyze dataflow info. */
1204
1205static void
1206df_analyze_1 (void)
1207{
1208 int i;
1209
1210 /* We need to do this before the df_verify_all because this is
1211 not kept incrementally up to date. */
1212 df_compute_regs_ever_live (false);
1213 df_process_deferred_rescans ();
1214
1215 if (dump_file)
1216 fprintf (stream: dump_file, format: "df_analyze called\n");
1217
1218#ifndef ENABLE_DF_CHECKING
1219 if (df->changeable_flags & DF_VERIFY_SCHEDULED)
1220#endif
1221 df_verify ();
1222
1223 /* Skip over the DF_SCAN problem. */
1224 for (i = 1; i < df->num_problems_defined; i++)
1225 {
1226 struct dataflow *dflow = df->problems_in_order[i];
1227 if (dflow->solutions_dirty)
1228 {
1229 if (dflow->problem->dir == DF_FORWARD)
1230 df_analyze_problem (dflow,
1231 blocks_to_consider: df->blocks_to_analyze,
1232 postorder: df->postorder_inverted,
1233 n_blocks: df->n_blocks);
1234 else
1235 df_analyze_problem (dflow,
1236 blocks_to_consider: df->blocks_to_analyze,
1237 postorder: df->postorder,
1238 n_blocks: df->n_blocks);
1239 }
1240 }
1241
1242 if (!df->analyze_subset)
1243 {
1244 BITMAP_FREE (df->blocks_to_analyze);
1245 df->blocks_to_analyze = NULL;
1246 }
1247
1248#ifdef DF_DEBUG_CFG
1249 df_set_clean_cfg ();
1250#endif
1251}
1252
1253/* Analyze dataflow info. */
1254
1255void
1256df_analyze (void)
1257{
1258 bitmap current_all_blocks = BITMAP_ALLOC (obstack: &df_bitmap_obstack);
1259
1260 free (ptr: df->postorder);
1261 free (ptr: df->postorder_inverted);
1262 /* For DF_FORWARD use a RPO on the forward graph. Since we want to
1263 have unreachable blocks deleted use post_order_compute and reverse
1264 the order. */
1265 df->postorder_inverted = XNEWVEC (int, n_basic_blocks_for_fn (cfun));
1266 df->n_blocks = post_order_compute (df->postorder_inverted, true, true);
1267 for (int i = 0; i < df->n_blocks / 2; ++i)
1268 std::swap (a&: df->postorder_inverted[i],
1269 b&: df->postorder_inverted[df->n_blocks - 1 - i]);
1270 /* For DF_BACKWARD use a RPO on the reverse graph. */
1271 df->postorder = XNEWVEC (int, n_basic_blocks_for_fn (cfun));
1272 int n = inverted_rev_post_order_compute (cfun, df->postorder);
1273 gcc_assert (n == df->n_blocks);
1274
1275 for (int i = 0; i < df->n_blocks; i++)
1276 bitmap_set_bit (current_all_blocks, df->postorder[i]);
1277
1278 if (flag_checking)
1279 {
1280 /* Verify that POSTORDER_INVERTED only contains blocks reachable from
1281 the ENTRY block. */
1282 for (int i = 0; i < df->n_blocks; i++)
1283 gcc_assert (bitmap_bit_p (current_all_blocks,
1284 df->postorder_inverted[i]));
1285 }
1286
1287 /* Make sure that we have pruned any unreachable blocks from these
1288 sets. */
1289 if (df->analyze_subset)
1290 {
1291 bitmap_and_into (df->blocks_to_analyze, current_all_blocks);
1292 unsigned int newlen = df_prune_to_subcfg (list: df->postorder, len: df->n_blocks,
1293 blocks: df->blocks_to_analyze);
1294 df_prune_to_subcfg (list: df->postorder_inverted, len: df->n_blocks,
1295 blocks: df->blocks_to_analyze);
1296 df->n_blocks = newlen;
1297 BITMAP_FREE (current_all_blocks);
1298 }
1299 else
1300 {
1301 df->blocks_to_analyze = current_all_blocks;
1302 current_all_blocks = NULL;
1303 }
1304
1305 df_analyze_1 ();
1306}
1307
1308/* Compute the reverse top sort order of the sub-CFG specified by LOOP.
1309 Returns the number of blocks which is always loop->num_nodes. */
1310
1311static int
1312loop_rev_post_order_compute (int *post_order, class loop *loop)
1313{
1314 edge_iterator *stack;
1315 int sp;
1316 int post_order_num = loop->num_nodes - 1;
1317
1318 /* Allocate stack for back-tracking up CFG. */
1319 stack = XNEWVEC (edge_iterator, loop->num_nodes + 1);
1320 sp = 0;
1321
1322 /* Allocate bitmap to track nodes that have been visited. */
1323 auto_bitmap visited;
1324
1325 /* Push the first edge on to the stack. */
1326 stack[sp++] = ei_start (loop_preheader_edge (loop)->src->succs);
1327
1328 while (sp)
1329 {
1330 edge_iterator ei;
1331 basic_block src;
1332 basic_block dest;
1333
1334 /* Look at the edge on the top of the stack. */
1335 ei = stack[sp - 1];
1336 src = ei_edge (i: ei)->src;
1337 dest = ei_edge (i: ei)->dest;
1338
1339 /* Check if the edge destination has been visited yet and mark it
1340 if not so. */
1341 if (flow_bb_inside_loop_p (loop, dest)
1342 && bitmap_set_bit (visited, dest->index))
1343 {
1344 if (EDGE_COUNT (dest->succs) > 0)
1345 /* Since the DEST node has been visited for the first
1346 time, check its successors. */
1347 stack[sp++] = ei_start (dest->succs);
1348 else
1349 post_order[post_order_num--] = dest->index;
1350 }
1351 else
1352 {
1353 if (ei_one_before_end_p (i: ei)
1354 && src != loop_preheader_edge (loop)->src)
1355 post_order[post_order_num--] = src->index;
1356
1357 if (!ei_one_before_end_p (i: ei))
1358 ei_next (i: &stack[sp - 1]);
1359 else
1360 sp--;
1361 }
1362 }
1363
1364 free (ptr: stack);
1365
1366 return loop->num_nodes;
1367}
1368
1369/* Compute the reverse top sort order of the inverted sub-CFG specified
1370 by LOOP. Returns the number of blocks which is always loop->num_nodes. */
1371
1372static int
1373loop_inverted_rev_post_order_compute (int *post_order, class loop *loop)
1374{
1375 basic_block bb;
1376 edge_iterator *stack;
1377 int sp;
1378 int post_order_num = loop->num_nodes - 1;
1379
1380 /* Allocate stack for back-tracking up CFG. */
1381 stack = XNEWVEC (edge_iterator, loop->num_nodes + 1);
1382 sp = 0;
1383
1384 /* Allocate bitmap to track nodes that have been visited. */
1385 auto_bitmap visited;
1386
1387 /* Put all latches into the initial work list. In theory we'd want
1388 to start from loop exits but then we'd have the special case of
1389 endless loops. It doesn't really matter for DF iteration order and
1390 handling latches last is probably even better. */
1391 stack[sp++] = ei_start (loop->header->preds);
1392 bitmap_set_bit (visited, loop->header->index);
1393
1394 /* The inverted traversal loop. */
1395 while (sp)
1396 {
1397 edge_iterator ei;
1398 basic_block pred;
1399
1400 /* Look at the edge on the top of the stack. */
1401 ei = stack[sp - 1];
1402 bb = ei_edge (i: ei)->dest;
1403 pred = ei_edge (i: ei)->src;
1404
1405 /* Check if the predecessor has been visited yet and mark it
1406 if not so. */
1407 if (flow_bb_inside_loop_p (loop, pred)
1408 && bitmap_set_bit (visited, pred->index))
1409 {
1410 if (EDGE_COUNT (pred->preds) > 0)
1411 /* Since the predecessor node has been visited for the first
1412 time, check its predecessors. */
1413 stack[sp++] = ei_start (pred->preds);
1414 else
1415 post_order[post_order_num--] = pred->index;
1416 }
1417 else
1418 {
1419 if (flow_bb_inside_loop_p (loop, bb)
1420 && ei_one_before_end_p (i: ei))
1421 post_order[post_order_num--] = bb->index;
1422
1423 if (!ei_one_before_end_p (i: ei))
1424 ei_next (i: &stack[sp - 1]);
1425 else
1426 sp--;
1427 }
1428 }
1429
1430 free (ptr: stack);
1431 return loop->num_nodes;
1432}
1433
1434
1435/* Analyze dataflow info for the basic blocks contained in LOOP. */
1436
1437void
1438df_analyze_loop (class loop *loop)
1439{
1440 free (ptr: df->postorder);
1441 free (ptr: df->postorder_inverted);
1442
1443 df->postorder = XNEWVEC (int, loop->num_nodes);
1444 df->postorder_inverted = XNEWVEC (int, loop->num_nodes);
1445 df->n_blocks = loop_rev_post_order_compute (post_order: df->postorder_inverted, loop);
1446 int n = loop_inverted_rev_post_order_compute (post_order: df->postorder, loop);
1447 gcc_assert ((unsigned) df->n_blocks == loop->num_nodes);
1448 gcc_assert ((unsigned) n == loop->num_nodes);
1449
1450 bitmap blocks = BITMAP_ALLOC (obstack: &df_bitmap_obstack);
1451 for (int i = 0; i < df->n_blocks; ++i)
1452 bitmap_set_bit (blocks, df->postorder[i]);
1453 df_set_blocks (blocks);
1454 BITMAP_FREE (blocks);
1455
1456 df_analyze_1 ();
1457}
1458
1459
1460/* Return the number of basic blocks from the last call to df_analyze. */
1461
1462int
1463df_get_n_blocks (enum df_flow_dir dir)
1464{
1465 gcc_assert (dir != DF_NONE);
1466
1467 if (dir == DF_FORWARD)
1468 {
1469 gcc_assert (df->postorder_inverted);
1470 return df->n_blocks;
1471 }
1472
1473 gcc_assert (df->postorder);
1474 return df->n_blocks;
1475}
1476
1477
1478/* Return a pointer to the array of basic blocks in the reverse postorder.
1479 Depending on the direction of the dataflow problem,
1480 it returns either the usual reverse postorder array
1481 or the reverse postorder of inverted traversal. */
1482int *
1483df_get_postorder (enum df_flow_dir dir)
1484{
1485 gcc_assert (dir != DF_NONE);
1486
1487 if (dir == DF_FORWARD)
1488 {
1489 gcc_assert (df->postorder_inverted);
1490 return df->postorder_inverted;
1491 }
1492 gcc_assert (df->postorder);
1493 return df->postorder;
1494}
1495
1496static struct df_problem user_problem;
1497static struct dataflow user_dflow;
1498
1499/* Interface for calling iterative dataflow with user defined
1500 confluence and transfer functions. All that is necessary is to
1501 supply DIR, a direction, CONF_FUN_0, a confluence function for
1502 blocks with no logical preds (or NULL), CONF_FUN_N, the normal
1503 confluence function, TRANS_FUN, the basic block transfer function,
1504 and BLOCKS, the set of blocks to examine, POSTORDER the blocks in
1505 postorder, and N_BLOCKS, the number of blocks in POSTORDER. */
1506
1507void
1508df_simple_dataflow (enum df_flow_dir dir,
1509 df_init_function init_fun,
1510 df_confluence_function_0 con_fun_0,
1511 df_confluence_function_n con_fun_n,
1512 df_transfer_function trans_fun,
1513 bitmap blocks, int * postorder, int n_blocks)
1514{
1515 memset (s: &user_problem, c: 0, n: sizeof (struct df_problem));
1516 user_problem.dir = dir;
1517 user_problem.init_fun = init_fun;
1518 user_problem.con_fun_0 = con_fun_0;
1519 user_problem.con_fun_n = con_fun_n;
1520 user_problem.trans_fun = trans_fun;
1521 user_dflow.problem = &user_problem;
1522 df_worklist_dataflow (dataflow: &user_dflow, blocks_to_consider: blocks, blocks_in_postorder: postorder, n_blocks);
1523}
1524
1525
1526
1527/*----------------------------------------------------------------------------
1528 Functions to support limited incremental change.
1529----------------------------------------------------------------------------*/
1530
1531
1532/* Get basic block info. */
1533
1534static void *
1535df_get_bb_info (struct dataflow *dflow, unsigned int index)
1536{
1537 if (dflow->block_info == NULL)
1538 return NULL;
1539 if (index >= dflow->block_info_size)
1540 return NULL;
1541 return (void *)((char *)dflow->block_info
1542 + index * dflow->problem->block_info_elt_size);
1543}
1544
1545
1546/* Set basic block info. */
1547
1548static void
1549df_set_bb_info (struct dataflow *dflow, unsigned int index,
1550 void *bb_info)
1551{
1552 gcc_assert (dflow->block_info);
1553 memcpy (dest: (char *)dflow->block_info
1554 + index * dflow->problem->block_info_elt_size,
1555 src: bb_info, n: dflow->problem->block_info_elt_size);
1556}
1557
1558
1559/* Clear basic block info. */
1560
1561static void
1562df_clear_bb_info (struct dataflow *dflow, unsigned int index)
1563{
1564 gcc_assert (dflow->block_info);
1565 gcc_assert (dflow->block_info_size > index);
1566 memset (s: (char *)dflow->block_info
1567 + index * dflow->problem->block_info_elt_size,
1568 c: 0, n: dflow->problem->block_info_elt_size);
1569}
1570
1571
1572/* Mark the solutions as being out of date. */
1573
1574void
1575df_mark_solutions_dirty (void)
1576{
1577 if (df)
1578 {
1579 int p;
1580 for (p = 1; p < df->num_problems_defined; p++)
1581 df->problems_in_order[p]->solutions_dirty = true;
1582 }
1583}
1584
1585
1586/* Return true if BB needs it's transfer functions recomputed. */
1587
1588bool
1589df_get_bb_dirty (basic_block bb)
1590{
1591 return bitmap_bit_p ((df_live
1592 ? df_live : df_lr)->out_of_date_transfer_functions,
1593 bb->index);
1594}
1595
1596
1597/* Mark BB as needing it's transfer functions as being out of
1598 date. */
1599
1600void
1601df_set_bb_dirty (basic_block bb)
1602{
1603 bb->flags |= BB_MODIFIED;
1604 if (df)
1605 {
1606 int p;
1607 for (p = 1; p < df->num_problems_defined; p++)
1608 {
1609 struct dataflow *dflow = df->problems_in_order[p];
1610 if (dflow->out_of_date_transfer_functions)
1611 bitmap_set_bit (dflow->out_of_date_transfer_functions, bb->index);
1612 }
1613 df_mark_solutions_dirty ();
1614 }
1615}
1616
1617
1618/* Grow the bb_info array. */
1619
1620void
1621df_grow_bb_info (struct dataflow *dflow)
1622{
1623 unsigned int new_size = last_basic_block_for_fn (cfun) + 1;
1624 if (dflow->block_info_size < new_size)
1625 {
1626 new_size += new_size / 4;
1627 dflow->block_info
1628 = (void *)XRESIZEVEC (char, (char *)dflow->block_info,
1629 new_size
1630 * dflow->problem->block_info_elt_size);
1631 memset (s: (char *)dflow->block_info
1632 + dflow->block_info_size
1633 * dflow->problem->block_info_elt_size,
1634 c: 0,
1635 n: (new_size - dflow->block_info_size)
1636 * dflow->problem->block_info_elt_size);
1637 dflow->block_info_size = new_size;
1638 }
1639}
1640
1641
1642/* Clear the dirty bits. This is called from places that delete
1643 blocks. */
1644static void
1645df_clear_bb_dirty (basic_block bb)
1646{
1647 int p;
1648 for (p = 1; p < df->num_problems_defined; p++)
1649 {
1650 struct dataflow *dflow = df->problems_in_order[p];
1651 if (dflow->out_of_date_transfer_functions)
1652 bitmap_clear_bit (dflow->out_of_date_transfer_functions, bb->index);
1653 }
1654}
1655
1656/* Called from the rtl_compact_blocks to reorganize the problems basic
1657 block info. */
1658
1659void
1660df_compact_blocks (void)
1661{
1662 int i, p;
1663 basic_block bb;
1664 void *problem_temps;
1665
1666 auto_bitmap tmp (&df_bitmap_obstack);
1667 for (p = 0; p < df->num_problems_defined; p++)
1668 {
1669 struct dataflow *dflow = df->problems_in_order[p];
1670
1671 /* Need to reorganize the out_of_date_transfer_functions for the
1672 dflow problem. */
1673 if (dflow->out_of_date_transfer_functions)
1674 {
1675 bitmap_copy (tmp, dflow->out_of_date_transfer_functions);
1676 bitmap_clear (dflow->out_of_date_transfer_functions);
1677 if (bitmap_bit_p (tmp, ENTRY_BLOCK))
1678 bitmap_set_bit (dflow->out_of_date_transfer_functions, ENTRY_BLOCK);
1679 if (bitmap_bit_p (tmp, EXIT_BLOCK))
1680 bitmap_set_bit (dflow->out_of_date_transfer_functions, EXIT_BLOCK);
1681
1682 i = NUM_FIXED_BLOCKS;
1683 FOR_EACH_BB_FN (bb, cfun)
1684 {
1685 if (bitmap_bit_p (tmp, bb->index))
1686 bitmap_set_bit (dflow->out_of_date_transfer_functions, i);
1687 i++;
1688 }
1689 }
1690
1691 /* Now shuffle the block info for the problem. */
1692 if (dflow->problem->free_bb_fun)
1693 {
1694 int size = (last_basic_block_for_fn (cfun)
1695 * dflow->problem->block_info_elt_size);
1696 problem_temps = XNEWVAR (char, size);
1697 df_grow_bb_info (dflow);
1698 memcpy (dest: problem_temps, src: dflow->block_info, n: size);
1699
1700 /* Copy the bb info from the problem tmps to the proper
1701 place in the block_info vector. Null out the copied
1702 item. The entry and exit blocks never move. */
1703 i = NUM_FIXED_BLOCKS;
1704 FOR_EACH_BB_FN (bb, cfun)
1705 {
1706 df_set_bb_info (dflow, index: i,
1707 bb_info: (char *)problem_temps
1708 + bb->index * dflow->problem->block_info_elt_size);
1709 i++;
1710 }
1711 memset (s: (char *)dflow->block_info
1712 + i * dflow->problem->block_info_elt_size, c: 0,
1713 n: (last_basic_block_for_fn (cfun) - i)
1714 * dflow->problem->block_info_elt_size);
1715 free (ptr: problem_temps);
1716 }
1717 }
1718
1719 /* Shuffle the bits in the basic_block indexed arrays. */
1720
1721 if (df->blocks_to_analyze)
1722 {
1723 if (bitmap_bit_p (tmp, ENTRY_BLOCK))
1724 bitmap_set_bit (df->blocks_to_analyze, ENTRY_BLOCK);
1725 if (bitmap_bit_p (tmp, EXIT_BLOCK))
1726 bitmap_set_bit (df->blocks_to_analyze, EXIT_BLOCK);
1727 bitmap_copy (tmp, df->blocks_to_analyze);
1728 bitmap_clear (df->blocks_to_analyze);
1729 i = NUM_FIXED_BLOCKS;
1730 FOR_EACH_BB_FN (bb, cfun)
1731 {
1732 if (bitmap_bit_p (tmp, bb->index))
1733 bitmap_set_bit (df->blocks_to_analyze, i);
1734 i++;
1735 }
1736 }
1737
1738 i = NUM_FIXED_BLOCKS;
1739 FOR_EACH_BB_FN (bb, cfun)
1740 {
1741 SET_BASIC_BLOCK_FOR_FN (cfun, i, bb);
1742 bb->index = i;
1743 i++;
1744 }
1745
1746 gcc_assert (i == n_basic_blocks_for_fn (cfun));
1747
1748 for (; i < last_basic_block_for_fn (cfun); i++)
1749 SET_BASIC_BLOCK_FOR_FN (cfun, i, NULL);
1750
1751#ifdef DF_DEBUG_CFG
1752 if (!df_lr->solutions_dirty)
1753 df_set_clean_cfg ();
1754#endif
1755}
1756
1757
1758/* Shove NEW_BLOCK in at OLD_INDEX. Called from ifcvt to hack a
1759 block. There is no excuse for people to do this kind of thing. */
1760
1761void
1762df_bb_replace (int old_index, basic_block new_block)
1763{
1764 int new_block_index = new_block->index;
1765 int p;
1766
1767 if (dump_file)
1768 fprintf (stream: dump_file, format: "shoving block %d into %d\n", new_block_index, old_index);
1769
1770 gcc_assert (df);
1771 gcc_assert (BASIC_BLOCK_FOR_FN (cfun, old_index) == NULL);
1772
1773 for (p = 0; p < df->num_problems_defined; p++)
1774 {
1775 struct dataflow *dflow = df->problems_in_order[p];
1776 if (dflow->block_info)
1777 {
1778 df_grow_bb_info (dflow);
1779 df_set_bb_info (dflow, index: old_index,
1780 bb_info: df_get_bb_info (dflow, index: new_block_index));
1781 }
1782 }
1783
1784 df_clear_bb_dirty (bb: new_block);
1785 SET_BASIC_BLOCK_FOR_FN (cfun, old_index, new_block);
1786 new_block->index = old_index;
1787 df_set_bb_dirty (BASIC_BLOCK_FOR_FN (cfun, old_index));
1788 SET_BASIC_BLOCK_FOR_FN (cfun, new_block_index, NULL);
1789}
1790
1791
1792/* Free all of the per basic block dataflow from all of the problems.
1793 This is typically called before a basic block is deleted and the
1794 problem will be reanalyzed. */
1795
1796void
1797df_bb_delete (int bb_index)
1798{
1799 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, bb_index);
1800 int i;
1801
1802 if (!df)
1803 return;
1804
1805 for (i = 0; i < df->num_problems_defined; i++)
1806 {
1807 struct dataflow *dflow = df->problems_in_order[i];
1808 if (dflow->problem->free_bb_fun)
1809 {
1810 void *bb_info = df_get_bb_info (dflow, index: bb_index);
1811 if (bb_info)
1812 {
1813 dflow->problem->free_bb_fun (bb, bb_info);
1814 df_clear_bb_info (dflow, index: bb_index);
1815 }
1816 }
1817 }
1818 df_clear_bb_dirty (bb);
1819 df_mark_solutions_dirty ();
1820}
1821
1822
1823/* Verify that there is a place for everything and everything is in
1824 its place. This is too expensive to run after every pass in the
1825 mainline. However this is an excellent debugging tool if the
1826 dataflow information is not being updated properly. You can just
1827 sprinkle calls in until you find the place that is changing an
1828 underlying structure without calling the proper updating
1829 routine. */
1830
1831void
1832df_verify (void)
1833{
1834 df_scan_verify ();
1835#ifdef ENABLE_DF_CHECKING
1836 df_lr_verify_transfer_functions ();
1837 if (df_live)
1838 df_live_verify_transfer_functions ();
1839#endif
1840 df->changeable_flags &= ~DF_VERIFY_SCHEDULED;
1841}
1842
1843#ifdef DF_DEBUG_CFG
1844
1845/* Compute an array of ints that describes the cfg. This can be used
1846 to discover places where the cfg is modified by the appropriate
1847 calls have not been made to the keep df informed. The internals of
1848 this are unexciting, the key is that two instances of this can be
1849 compared to see if any changes have been made to the cfg. */
1850
1851static int *
1852df_compute_cfg_image (void)
1853{
1854 basic_block bb;
1855 int size = 2 + (2 * n_basic_blocks_for_fn (cfun));
1856 int i;
1857 int * map;
1858
1859 FOR_ALL_BB_FN (bb, cfun)
1860 {
1861 size += EDGE_COUNT (bb->succs);
1862 }
1863
1864 map = XNEWVEC (int, size);
1865 map[0] = size;
1866 i = 1;
1867 FOR_ALL_BB_FN (bb, cfun)
1868 {
1869 edge_iterator ei;
1870 edge e;
1871
1872 map[i++] = bb->index;
1873 FOR_EACH_EDGE (e, ei, bb->succs)
1874 map[i++] = e->dest->index;
1875 map[i++] = -1;
1876 }
1877 map[i] = -1;
1878 return map;
1879}
1880
1881static int *saved_cfg = NULL;
1882
1883
1884/* This function compares the saved version of the cfg with the
1885 current cfg and aborts if the two are identical. The function
1886 silently returns if the cfg has been marked as dirty or the two are
1887 the same. */
1888
1889void
1890df_check_cfg_clean (void)
1891{
1892 int *new_map;
1893
1894 if (!df)
1895 return;
1896
1897 if (df_lr->solutions_dirty)
1898 return;
1899
1900 if (saved_cfg == NULL)
1901 return;
1902
1903 new_map = df_compute_cfg_image ();
1904 gcc_assert (memcmp (saved_cfg, new_map, saved_cfg[0] * sizeof (int)) == 0);
1905 free (new_map);
1906}
1907
1908
1909/* This function builds a cfg fingerprint and squirrels it away in
1910 saved_cfg. */
1911
1912static void
1913df_set_clean_cfg (void)
1914{
1915 free (saved_cfg);
1916 saved_cfg = df_compute_cfg_image ();
1917}
1918
1919#endif /* DF_DEBUG_CFG */
1920/*----------------------------------------------------------------------------
1921 PUBLIC INTERFACES TO QUERY INFORMATION.
1922----------------------------------------------------------------------------*/
1923
1924
1925/* Return first def of REGNO within BB. */
1926
1927df_ref
1928df_bb_regno_first_def_find (basic_block bb, unsigned int regno)
1929{
1930 rtx_insn *insn;
1931 df_ref def;
1932
1933 FOR_BB_INSNS (bb, insn)
1934 {
1935 if (!INSN_P (insn))
1936 continue;
1937
1938 FOR_EACH_INSN_DEF (def, insn)
1939 if (DF_REF_REGNO (def) == regno)
1940 return def;
1941 }
1942 return NULL;
1943}
1944
1945
1946/* Return last def of REGNO within BB. */
1947
1948df_ref
1949df_bb_regno_last_def_find (basic_block bb, unsigned int regno)
1950{
1951 rtx_insn *insn;
1952 df_ref def;
1953
1954 FOR_BB_INSNS_REVERSE (bb, insn)
1955 {
1956 if (!INSN_P (insn))
1957 continue;
1958
1959 FOR_EACH_INSN_DEF (def, insn)
1960 if (DF_REF_REGNO (def) == regno)
1961 return def;
1962 }
1963
1964 return NULL;
1965}
1966
1967/* Finds the reference corresponding to the definition of REG in INSN.
1968 DF is the dataflow object. */
1969
1970df_ref
1971df_find_def (rtx_insn *insn, rtx reg)
1972{
1973 df_ref def;
1974
1975 if (GET_CODE (reg) == SUBREG)
1976 reg = SUBREG_REG (reg);
1977 gcc_assert (REG_P (reg));
1978
1979 FOR_EACH_INSN_DEF (def, insn)
1980 if (DF_REF_REGNO (def) == REGNO (reg))
1981 return def;
1982
1983 return NULL;
1984}
1985
1986
1987/* Return true if REG is defined in INSN, zero otherwise. */
1988
1989bool
1990df_reg_defined (rtx_insn *insn, rtx reg)
1991{
1992 return df_find_def (insn, reg) != NULL;
1993}
1994
1995
1996/* Finds the reference corresponding to the use of REG in INSN.
1997 DF is the dataflow object. */
1998
1999df_ref
2000df_find_use (rtx_insn *insn, rtx reg)
2001{
2002 df_ref use;
2003
2004 if (GET_CODE (reg) == SUBREG)
2005 reg = SUBREG_REG (reg);
2006 gcc_assert (REG_P (reg));
2007
2008 df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
2009 FOR_EACH_INSN_INFO_USE (use, insn_info)
2010 if (DF_REF_REGNO (use) == REGNO (reg))
2011 return use;
2012 if (df->changeable_flags & DF_EQ_NOTES)
2013 FOR_EACH_INSN_INFO_EQ_USE (use, insn_info)
2014 if (DF_REF_REGNO (use) == REGNO (reg))
2015 return use;
2016 return NULL;
2017}
2018
2019
2020/* Return true if REG is referenced in INSN, zero otherwise. */
2021
2022bool
2023df_reg_used (rtx_insn *insn, rtx reg)
2024{
2025 return df_find_use (insn, reg) != NULL;
2026}
2027
2028/* If REG has a single definition, return its known value, otherwise return
2029 null. */
2030
2031rtx
2032df_find_single_def_src (rtx reg)
2033{
2034 rtx src = NULL_RTX;
2035
2036 /* Don't look through unbounded number of single definition REG copies,
2037 there might be loops for sources with uninitialized variables. */
2038 for (int cnt = 0; cnt < 128; cnt++)
2039 {
2040 df_ref adef = DF_REG_DEF_CHAIN (REGNO (reg));
2041 if (adef == NULL || DF_REF_NEXT_REG (adef) != NULL
2042 || DF_REF_IS_ARTIFICIAL (adef)
2043 || (DF_REF_FLAGS (adef)
2044 & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
2045 return NULL_RTX;
2046
2047 rtx set = single_set (DF_REF_INSN (adef));
2048 if (set == NULL || !rtx_equal_p (SET_DEST (set), reg))
2049 return NULL_RTX;
2050
2051 rtx note = find_reg_equal_equiv_note (DF_REF_INSN (adef));
2052 if (note && function_invariant_p (XEXP (note, 0)))
2053 return XEXP (note, 0);
2054 src = SET_SRC (set);
2055
2056 if (REG_P (src))
2057 {
2058 reg = src;
2059 continue;
2060 }
2061 break;
2062 }
2063 if (!function_invariant_p (src))
2064 return NULL_RTX;
2065
2066 return src;
2067}
2068
2069
2070/*----------------------------------------------------------------------------
2071 Debugging and printing functions.
2072----------------------------------------------------------------------------*/
2073
2074/* Write information about registers and basic blocks into FILE.
2075 This is part of making a debugging dump. */
2076
2077void
2078dump_regset (regset r, FILE *outf)
2079{
2080 unsigned i;
2081 reg_set_iterator rsi;
2082
2083 if (r == NULL)
2084 {
2085 fputs (s: " (nil)", stream: outf);
2086 return;
2087 }
2088
2089 EXECUTE_IF_SET_IN_REG_SET (r, 0, i, rsi)
2090 {
2091 fprintf (stream: outf, format: " %d", i);
2092 if (i < FIRST_PSEUDO_REGISTER)
2093 fprintf (stream: outf, format: " [%s]",
2094 reg_names[i]);
2095 }
2096}
2097
2098/* Print a human-readable representation of R on the standard error
2099 stream. This function is designed to be used from within the
2100 debugger. */
2101extern void debug_regset (regset);
2102DEBUG_FUNCTION void
2103debug_regset (regset r)
2104{
2105 dump_regset (r, stderr);
2106 putc (c: '\n', stderr);
2107}
2108
2109/* Write information about registers and basic blocks into FILE.
2110 This is part of making a debugging dump. */
2111
2112void
2113df_print_regset (FILE *file, const_bitmap r)
2114{
2115 unsigned int i;
2116 bitmap_iterator bi;
2117
2118 if (r == NULL)
2119 fputs (s: " (nil)", stream: file);
2120 else
2121 {
2122 EXECUTE_IF_SET_IN_BITMAP (r, 0, i, bi)
2123 {
2124 fprintf (stream: file, format: " %d", i);
2125 if (i < FIRST_PSEUDO_REGISTER)
2126 fprintf (stream: file, format: " [%s]", reg_names[i]);
2127 }
2128 }
2129 fprintf (stream: file, format: "\n");
2130}
2131
2132
2133/* Write information about registers and basic blocks into FILE. The
2134 bitmap is in the form used by df_byte_lr. This is part of making a
2135 debugging dump. */
2136
2137void
2138df_print_word_regset (FILE *file, const_bitmap r)
2139{
2140 unsigned int max_reg = max_reg_num ();
2141
2142 if (r == NULL)
2143 fputs (s: " (nil)", stream: file);
2144 else
2145 {
2146 unsigned int i;
2147 for (i = FIRST_PSEUDO_REGISTER; i < max_reg; i++)
2148 {
2149 bool found = (bitmap_bit_p (r, 2 * i)
2150 || bitmap_bit_p (r, 2 * i + 1));
2151 if (found)
2152 {
2153 int word;
2154 const char * sep = "";
2155 fprintf (stream: file, format: " %d", i);
2156 fprintf (stream: file, format: "(");
2157 for (word = 0; word < 2; word++)
2158 if (bitmap_bit_p (r, 2 * i + word))
2159 {
2160 fprintf (stream: file, format: "%s%d", sep, word);
2161 sep = ", ";
2162 }
2163 fprintf (stream: file, format: ")");
2164 }
2165 }
2166 }
2167 fprintf (stream: file, format: "\n");
2168}
2169
2170
2171/* Dump dataflow info. */
2172
2173void
2174df_dump (FILE *file)
2175{
2176 basic_block bb;
2177 df_dump_start (file);
2178
2179 FOR_ALL_BB_FN (bb, cfun)
2180 {
2181 df_print_bb_index (bb, file);
2182 df_dump_top (bb, file);
2183 df_dump_bottom (bb, file);
2184 }
2185
2186 fprintf (stream: file, format: "\n");
2187}
2188
2189
2190/* Dump dataflow info for df->blocks_to_analyze. */
2191
2192void
2193df_dump_region (FILE *file)
2194{
2195 if (df->blocks_to_analyze)
2196 {
2197 bitmap_iterator bi;
2198 unsigned int bb_index;
2199
2200 fprintf (stream: file, format: "\n\nstarting region dump\n");
2201 df_dump_start (file);
2202
2203 EXECUTE_IF_SET_IN_BITMAP (df->blocks_to_analyze, 0, bb_index, bi)
2204 {
2205 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, bb_index);
2206 dump_bb (file, bb, 0, TDF_DETAILS);
2207 }
2208 fprintf (stream: file, format: "\n");
2209 }
2210 else
2211 df_dump (file);
2212}
2213
2214
2215/* Dump the introductory information for each problem defined. */
2216
2217void
2218df_dump_start (FILE *file)
2219{
2220 int i;
2221
2222 if (!df || !file)
2223 return;
2224
2225 fprintf (stream: file, format: "\n\n%s\n", current_function_name ());
2226 fprintf (stream: file, format: "\nDataflow summary:\n");
2227 if (df->blocks_to_analyze)
2228 fprintf (stream: file, format: "def_info->table_size = %d, use_info->table_size = %d\n",
2229 DF_DEFS_TABLE_SIZE (), DF_USES_TABLE_SIZE ());
2230
2231 for (i = 0; i < df->num_problems_defined; i++)
2232 {
2233 struct dataflow *dflow = df->problems_in_order[i];
2234 if (dflow->computed)
2235 {
2236 df_dump_problem_function fun = dflow->problem->dump_start_fun;
2237 if (fun)
2238 fun (file);
2239 }
2240 }
2241}
2242
2243
2244/* Dump the top or bottom of the block information for BB. */
2245static void
2246df_dump_bb_problem_data (basic_block bb, FILE *file, bool top)
2247{
2248 int i;
2249
2250 if (!df || !file)
2251 return;
2252
2253 for (i = 0; i < df->num_problems_defined; i++)
2254 {
2255 struct dataflow *dflow = df->problems_in_order[i];
2256 if (dflow->computed)
2257 {
2258 df_dump_bb_problem_function bbfun;
2259
2260 if (top)
2261 bbfun = dflow->problem->dump_top_fun;
2262 else
2263 bbfun = dflow->problem->dump_bottom_fun;
2264
2265 if (bbfun)
2266 bbfun (bb, file);
2267 }
2268 }
2269}
2270
2271/* Dump the top of the block information for BB. */
2272
2273void
2274df_dump_top (basic_block bb, FILE *file)
2275{
2276 df_dump_bb_problem_data (bb, file, /*top=*/true);
2277}
2278
2279/* Dump the bottom of the block information for BB. */
2280
2281void
2282df_dump_bottom (basic_block bb, FILE *file)
2283{
2284 df_dump_bb_problem_data (bb, file, /*top=*/false);
2285}
2286
2287
2288/* Dump information about INSN just before or after dumping INSN itself. */
2289static void
2290df_dump_insn_problem_data (const rtx_insn *insn, FILE *file, bool top)
2291{
2292 int i;
2293
2294 if (!df || !file)
2295 return;
2296
2297 for (i = 0; i < df->num_problems_defined; i++)
2298 {
2299 struct dataflow *dflow = df->problems_in_order[i];
2300 if (dflow->computed)
2301 {
2302 df_dump_insn_problem_function insnfun;
2303
2304 if (top)
2305 insnfun = dflow->problem->dump_insn_top_fun;
2306 else
2307 insnfun = dflow->problem->dump_insn_bottom_fun;
2308
2309 if (insnfun)
2310 insnfun (insn, file);
2311 }
2312 }
2313}
2314
2315/* Dump information about INSN before dumping INSN itself. */
2316
2317void
2318df_dump_insn_top (const rtx_insn *insn, FILE *file)
2319{
2320 df_dump_insn_problem_data (insn, file, /*top=*/true);
2321}
2322
2323/* Dump information about INSN after dumping INSN itself. */
2324
2325void
2326df_dump_insn_bottom (const rtx_insn *insn, FILE *file)
2327{
2328 df_dump_insn_problem_data (insn, file, /*top=*/false);
2329}
2330
2331
2332static void
2333df_ref_dump (df_ref ref, FILE *file)
2334{
2335 fprintf (stream: file, format: "%c%d(%d)",
2336 DF_REF_REG_DEF_P (ref)
2337 ? 'd'
2338 : (DF_REF_FLAGS (ref) & DF_REF_IN_NOTE) ? 'e' : 'u',
2339 DF_REF_ID (ref),
2340 DF_REF_REGNO (ref));
2341}
2342
2343void
2344df_refs_chain_dump (df_ref ref, bool follow_chain, FILE *file)
2345{
2346 fprintf (stream: file, format: "{ ");
2347 for (; ref; ref = DF_REF_NEXT_LOC (ref))
2348 {
2349 df_ref_dump (ref, file);
2350 if (follow_chain)
2351 df_chain_dump (DF_REF_CHAIN (ref), file);
2352 }
2353 fprintf (stream: file, format: "}");
2354}
2355
2356
2357/* Dump either a ref-def or reg-use chain. */
2358
2359void
2360df_regs_chain_dump (df_ref ref, FILE *file)
2361{
2362 fprintf (stream: file, format: "{ ");
2363 while (ref)
2364 {
2365 df_ref_dump (ref, file);
2366 ref = DF_REF_NEXT_REG (ref);
2367 }
2368 fprintf (stream: file, format: "}");
2369}
2370
2371
2372static void
2373df_mws_dump (struct df_mw_hardreg *mws, FILE *file)
2374{
2375 for (; mws; mws = DF_MWS_NEXT (mws))
2376 fprintf (stream: file, format: "mw %c r[%d..%d]\n",
2377 DF_MWS_REG_DEF_P (mws) ? 'd' : 'u',
2378 mws->start_regno, mws->end_regno);
2379}
2380
2381
2382static void
2383df_insn_uid_debug (unsigned int uid,
2384 bool follow_chain, FILE *file)
2385{
2386 fprintf (stream: file, format: "insn %d luid %d",
2387 uid, DF_INSN_UID_LUID (uid));
2388
2389 if (DF_INSN_UID_DEFS (uid))
2390 {
2391 fprintf (stream: file, format: " defs ");
2392 df_refs_chain_dump (DF_INSN_UID_DEFS (uid), follow_chain, file);
2393 }
2394
2395 if (DF_INSN_UID_USES (uid))
2396 {
2397 fprintf (stream: file, format: " uses ");
2398 df_refs_chain_dump (DF_INSN_UID_USES (uid), follow_chain, file);
2399 }
2400
2401 if (DF_INSN_UID_EQ_USES (uid))
2402 {
2403 fprintf (stream: file, format: " eq uses ");
2404 df_refs_chain_dump (DF_INSN_UID_EQ_USES (uid), follow_chain, file);
2405 }
2406
2407 if (DF_INSN_UID_MWS (uid))
2408 {
2409 fprintf (stream: file, format: " mws ");
2410 df_mws_dump (DF_INSN_UID_MWS (uid), file);
2411 }
2412 fprintf (stream: file, format: "\n");
2413}
2414
2415
2416DEBUG_FUNCTION void
2417df_insn_debug (rtx_insn *insn, bool follow_chain, FILE *file)
2418{
2419 df_insn_uid_debug (uid: INSN_UID (insn), follow_chain, file);
2420}
2421
2422DEBUG_FUNCTION void
2423df_insn_debug_regno (rtx_insn *insn, FILE *file)
2424{
2425 struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
2426
2427 fprintf (stream: file, format: "insn %d bb %d luid %d defs ",
2428 INSN_UID (insn), BLOCK_FOR_INSN (insn)->index,
2429 DF_INSN_INFO_LUID (insn_info));
2430 df_refs_chain_dump (DF_INSN_INFO_DEFS (insn_info), follow_chain: false, file);
2431
2432 fprintf (stream: file, format: " uses ");
2433 df_refs_chain_dump (DF_INSN_INFO_USES (insn_info), follow_chain: false, file);
2434
2435 fprintf (stream: file, format: " eq_uses ");
2436 df_refs_chain_dump (DF_INSN_INFO_EQ_USES (insn_info), follow_chain: false, file);
2437 fprintf (stream: file, format: "\n");
2438}
2439
2440DEBUG_FUNCTION void
2441df_regno_debug (unsigned int regno, FILE *file)
2442{
2443 fprintf (stream: file, format: "reg %d defs ", regno);
2444 df_regs_chain_dump (DF_REG_DEF_CHAIN (regno), file);
2445 fprintf (stream: file, format: " uses ");
2446 df_regs_chain_dump (DF_REG_USE_CHAIN (regno), file);
2447 fprintf (stream: file, format: " eq_uses ");
2448 df_regs_chain_dump (DF_REG_EQ_USE_CHAIN (regno), file);
2449 fprintf (stream: file, format: "\n");
2450}
2451
2452
2453DEBUG_FUNCTION void
2454df_ref_debug (df_ref ref, FILE *file)
2455{
2456 fprintf (stream: file, format: "%c%d ",
2457 DF_REF_REG_DEF_P (ref) ? 'd' : 'u',
2458 DF_REF_ID (ref));
2459 fprintf (stream: file, format: "reg %d bb %d insn %d flag %#x type %#x ",
2460 DF_REF_REGNO (ref),
2461 DF_REF_BBNO (ref),
2462 DF_REF_IS_ARTIFICIAL (ref) ? -1 : DF_REF_INSN_UID (ref),
2463 DF_REF_FLAGS (ref),
2464 DF_REF_TYPE (ref));
2465 if (DF_REF_LOC (ref))
2466 {
2467 if (flag_dump_noaddr)
2468 fprintf (stream: file, format: "loc #(#) chain ");
2469 else
2470 fprintf (stream: file, format: "loc %p(%p) chain ", (void *)DF_REF_LOC (ref),
2471 (void *)*DF_REF_LOC (ref));
2472 }
2473 else
2474 fprintf (stream: file, format: "chain ");
2475 df_chain_dump (DF_REF_CHAIN (ref), file);
2476 fprintf (stream: file, format: "\n");
2477}
2478
2479/* Functions for debugging from GDB. */
2480
2481DEBUG_FUNCTION void
2482debug_df_insn (rtx_insn *insn)
2483{
2484 df_insn_debug (insn, follow_chain: true, stderr);
2485 debug_rtx (insn);
2486}
2487
2488
2489DEBUG_FUNCTION void
2490debug_df_reg (rtx reg)
2491{
2492 df_regno_debug (REGNO (reg), stderr);
2493}
2494
2495
2496DEBUG_FUNCTION void
2497debug_df_regno (unsigned int regno)
2498{
2499 df_regno_debug (regno, stderr);
2500}
2501
2502
2503DEBUG_FUNCTION void
2504debug_df_ref (df_ref ref)
2505{
2506 df_ref_debug (ref, stderr);
2507}
2508
2509
2510DEBUG_FUNCTION void
2511debug_df_defno (unsigned int defno)
2512{
2513 df_ref_debug (DF_DEFS_GET (defno), stderr);
2514}
2515
2516
2517DEBUG_FUNCTION void
2518debug_df_useno (unsigned int defno)
2519{
2520 df_ref_debug (DF_USES_GET (defno), stderr);
2521}
2522
2523
2524DEBUG_FUNCTION void
2525debug_df_chain (struct df_link *link)
2526{
2527 df_chain_dump (link, stderr);
2528 fputc (c: '\n', stderr);
2529}
2530

source code of gcc/df-core.cc