gcc/df-core.c

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