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