gcc/df-core.c

   1 /* Allocation for dataflow support routines.
   2    Copyright (C) 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006
   3    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 2, 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 COPYING.  If not, write to the Free
  23 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
  24 02110-1301, USA.
  25 */
  26
  27 /*
  28 OVERVIEW:
  29
  30 The files in this collection (df*.c,df.h) provide a general framework
  31 for solving dataflow problems.  The global dataflow is performed using
  32 a good implementation of iterative dataflow analysis.
  33
  34 The file df-problems.c provides problem instance for the most common
  35 dataflow problems: reaching defs, upward exposed uses, live variables,
  36 uninitialized variables, def-use chains, and use-def chains.  However,
  37 the interface allows other dataflow problems to be defined as well.
  38
  39
  40 USAGE:
  41
  42 Here is an example of using the dataflow routines.
  43
  44       struct df *df;
  45
  46       df = df_init (init_flags);
  47
  48       df_add_problem (df, problem);
  49
  50       df_set_blocks (df, blocks);
  51
  52       df_rescan_blocks (df, blocks);
  53
  54       df_analyze (df);
  55
  56       df_dump (df, stderr);
  57
  58       df_finish (df);
  59
  60
  61
  62 DF_INIT simply creates a poor man's object (df) that needs to be
  63 passed to all the dataflow routines.  df_finish destroys this object
  64 and frees up any allocated memory.
  65
  66 There are two flags that can be passed to df_init:
  67
  68 DF_NO_SCAN means that no scanning of the rtl code is performed.  This
  69 is used if the problem instance is to do it's own scanning.
  70
  71 DF_HARD_REGS means that the scanning is to build information about
  72 both pseudo registers and hardware registers.  Without this
  73 information, the problems will be solved only on pseudo registers.
  74
  75
  76
  77 DF_ADD_PROBLEM adds a problem, defined by an instance to struct
  78 df_problem, to the set of problems solved in this instance of df.  All
  79 calls to add a problem for a given instance of df must occur before
  80 the first call to DF_RESCAN_BLOCKS or DF_ANALYZE.
  81
  82 For all of the problems defined in df-problems.c, there are
  83 convienence functions named DF_*_ADD_PROBLEM.
  84
  85
  86 Problems can be dependent on other problems.  For instance, solving
  87 def-use or use-def chains is dependant on solving reaching
  88 definitions. As long as these dependancies are listed in the problem
  89 definition, the order of adding the problems is not material.
  90 Otherwise, the problems will be solved in the order of calls to
  91 df_add_problem.  Note that it is not necessary to have a problem.  In
  92 that case, df will just be used to do the scanning.
  93
  94
  95
  96 DF_SET_BLOCKS is an optional call used to define a region of the
  97 function on which the analysis will be performed.  The normal case is
  98 to analyze the entire function and no call to df_set_blocks is made.
  99
 100 When a subset is given, the analysis behaves as if the function only
 101 contains those blocks and any edges that occur directly between the
 102 blocks in the set.  Care should be taken to call df_set_blocks right
 103 before the call to analyze in order to eliminate the possiblity that
 104 optimizations that reorder blocks invalidate the bitvector.
 105
 106
 107
 108 DF_RESCAN_BLOCKS is an optional call that causes the scanner to be
 109  (re)run over the set of blocks passed in.  If blocks is NULL, the entire
 110 function (or all of the blocks defined in df_set_blocks) is rescanned.
 111 If blocks contains blocks that were not defined in the call to
 112 df_set_blocks, these blocks are added to the set of blocks.
 113
 114
 115 DF_ANALYZE causes all of the defined problems to be (re)solved.  It
 116 does not cause blocks to be (re)scanned at the rtl level unless no
 117 prior call is made to df_rescan_blocks.
 118
 119
 120 DF_DUMP can then be called to dump the information produce to some
 121 file.
 122
 123
 124
 125 DF_FINISH causes all of the datastructures to be cleaned up and freed.
 126 The df_instance is also freed and its pointer should be NULLed.
 127
 128
 129
 130
 131 Scanning produces a `struct df_ref' data structure (ref) is allocated
 132 for every register reference (def or use) and this records the insn
 133 and bb the ref is found within.  The refs are linked together in
 134 chains of uses and defs for each insn and for each register.  Each ref
 135 also has a chain field that links all the use refs for a def or all
 136 the def refs for a use.  This is used to create use-def or def-use
 137 chains.
 138
 139 Different optimizations have different needs.  Ultimately, only
 140 register allocation and schedulers should be using the bitmaps
 141 produced for the live register and uninitialized register problems.
 142 The rest of the backend should be upgraded to using and maintaining
 143 the linked information such as def use or use def chains.
 144
 145
 146
 147 PHILOSOPHY:
 148
 149 While incremental bitmaps are not worthwhile to maintain, incremental
 150 chains may be perfectly reasonable.  The fastest way to build chains
 151 from scratch or after significant modifications is to build reaching
 152 definitions (RD) and build the chains from this.
 153
 154 However, general algorithms for maintaining use-def or def-use chains
 155 are not practical.  The amount of work to recompute the chain any
 156 chain after an arbitrary change is large.  However, with a modest
 157 amount of work it is generally possible to have the application that
 158 uses the chains keep them up to date.  The high level knowledge of
 159 what is really happening is essential to crafting efficient
 160 incremental algorithms.
 161
 162 As for the bit vector problems, there is no interface to give a set of
 163 blocks over with to resolve the iteration.  In general, restarting a
 164 dataflow iteration is difficult and expensive.  Again, the best way to
 165 keep the dataflow infomation up to data (if this is really what is
 166 needed) it to formulate a problem specific solution.
 167
 168 There are fine grained calls for creating and deleting references from
 169 instructions in df-scan.c.  However, these are not currently connected
 170 to the engine that resolves the dataflow equations.
 171
 172
 173 DATA STRUCTURES:
 174
 175 The basic object is a DF_REF (reference) and this may either be a
 176 DEF (definition) or a USE of a register.
 177
 178 These are linked into a variety of lists; namely reg-def, reg-use,
 179 insn-def, insn-use, def-use, and use-def lists.  For example, the
 180 reg-def lists contain all the locations that define a given register
 181 while the insn-use lists contain all the locations that use a
 182 register.
 183
 184 Note that the reg-def and reg-use chains are generally short for
 185 pseudos and long for the hard registers.
 186
 187 ACCESSING REFS:
 188
 189 There are 4 ways to obtain access to refs:
 190
 191 1) References are divided into two categories, REAL and ARTIFICIAL.
 192
 193    REAL refs are associated with instructions.  They are linked into
 194    either in the insn's defs list (accessed by the DF_INSN_DEFS or
 195    DF_INSN_UID_DEFS macros) or the insn's uses list (accessed by the
 196    DF_INSN_USES or DF_INSN_UID_USES macros).  These macros produce a
 197    ref (or NULL), the rest of the list can be obtained by traversal of
 198    the NEXT_REF field (accessed by the DF_REF_NEXT_REF macro.)  There
 199    is no significance to the ordering of the uses or refs in an
 200    instruction.
 201
 202    ARTIFICIAL refs are associated with basic blocks.  The heads of
 203    these lists can be accessed by calling get_artificial_defs or
 204    get_artificial_uses for the particular basic block.  Artificial
 205    defs and uses are only there if DF_HARD_REGS was specified when the
 206    df instance was created.
 207
 208    Artificial defs and uses occur at the beginning blocks that are the
 209    destination of eh edges.  The defs come from the registers
 210    specified in EH_RETURN_DATA_REGNO and the uses come from the
 211    registers specified in ED_USES.  Logically these defs and uses
 212    should really occur along the eh edge, but there is no convienent
 213    way to do this.  Artificial edges that occur at the beginning of
 214    the block have the DF_REF_AT_TOP flag set.
 215
 216    Artificial uses also occur at the end of all blocks.  These arise
 217    from the hard registers that are always live, such as the stack
 218    register and are put there to keep the code from forgetting about
 219    them.
 220
 221 2) All of the uses and defs associated with each pseudo or hard
 222    register are linked in a bidirectional chain.  These are called
 223    reg-use or reg_def chains.
 224
 225    The first use (or def) for a register can be obtained using the
 226    DF_REG_USE_GET macro (or DF_REG_DEF_GET macro).  Subsequent uses
 227    for the same regno can be obtained by following the next_reg field
 228    of the ref.
 229
 230    In previous versions of this code, these chains were ordered.  It
 231    has not been practical to continue this practice.
 232
 233 3) If def-use or use-def chains are built, these can be traversed to
 234    get to other refs.
 235
 236 4) An array of all of the uses (and an array of all of the defs) can
 237    be built.  These arrays are indexed by the value in the id
 238    structure.  These arrays are only lazily kept up to date, and that
 239    process can be expensive.  To have these arrays built, call
 240    df_reorganize_refs.   Note that the values in the id field of a ref
 241    may change across calls to df_analyze or df_reorganize refs.
 242
 243    If the only use of this array is to find all of the refs, it is
 244    better to traverse all of the registers and then traverse all of
 245    reg-use or reg-def chains.
 246
 247
 248
 249 NOTES:
 250
 251 Embedded addressing side-effects, such as POST_INC or PRE_INC, generate
 252 both a use and a def.  These are both marked read/write to show that they
 253 are dependent. For example, (set (reg 40) (mem (post_inc (reg 42))))
 254 will generate a use of reg 42 followed by a def of reg 42 (both marked
 255 read/write).  Similarly, (set (reg 40) (mem (pre_dec (reg 41))))
 256 generates a use of reg 41 then a def of reg 41 (both marked read/write),
 257 even though reg 41 is decremented before it is used for the memory
 258 address in this second example.
 259
 260 A set to a REG inside a ZERO_EXTRACT, or a set to a non-paradoxical SUBREG
 261 for which the number of word_mode units covered by the outer mode is
 262 smaller than that covered by the inner mode, invokes a read-modify-write.
 263 operation.  We generate both a use and a def and again mark them
 264 read/write.
 265
 266 Paradoxical subreg writes do not leave a trace of the old content, so they
 267 are write-only operations.
 268 */
 269
 270
 271 #include "config.h"
 272 #include "system.h"
 273 #include "coretypes.h"
 274 #include "tm.h"
 275 #include "rtl.h"
 276 #include "tm_p.h"
 277 #include "insn-config.h"
 278 #include "recog.h"
 279 #include "function.h"
 280 #include "regs.h"
 281 #include "output.h"
 282 #include "alloc-pool.h"
 283 #include "flags.h"
 284 #include "hard-reg-set.h"
 285 #include "basic-block.h"
 286 #include "sbitmap.h"
 287 #include "bitmap.h"
 288 #include "timevar.h"
 289 #include "df.h"
 290 #include "tree-pass.h"
 291
 292 static struct df *ddf = NULL;
 293 struct df *shared_df = NULL;
 294
 295 /*----------------------------------------------------------------------------
 296   Functions to create, destroy and manipulate an instance of df.
 297 ----------------------------------------------------------------------------*/
 298
 299
 300 /* Initialize dataflow analysis and allocate and initialize dataflow
 301    memory.  */
 302
 303 struct df *
 304 df_init (int flags)
 305 {
 306   struct df *df = xcalloc (1, sizeof (struct df));
 307   df->flags = flags;
 308
 309   /* This is executed once per compilation to initialize platform
 310      specific data structures. */
 311   df_hard_reg_init ();
 312
 313   /* All df instance must define the scanning problem.  */
 314   df_scan_add_problem (df);
 315   ddf = df;
 316   return df;
 317 }
 318
 319 /* Add PROBLEM to the DF instance.  */
 320
 321 struct dataflow *
 322 df_add_problem (struct df *df, struct df_problem *problem)
 323 {
 324   struct dataflow *dflow;
 325
 326   /* First try to add the dependent problem. */
 327   if (problem->dependent_problem)
 328     df_add_problem (df, problem->dependent_problem);
 329
 330   /* Check to see if this problem has already been defined.  If it
 331      has, just return that instance, if not, add it to the end of the
 332      vector.  */
 333   dflow = df->problems_by_index[problem->id];
 334   if (dflow)
 335     return dflow;
 336
 337   /* Make a new one and add it to the end.  */
 338   dflow = xcalloc (1, sizeof (struct dataflow));
 339   dflow->df = df;
 340   dflow->problem = problem;
 341   df->problems_in_order[df->num_problems_defined++] = dflow;
 342   df->problems_by_index[dflow->problem->id] = dflow;
 343
 344   return dflow;
 345 }
 346
 347
 348 /* Set the blocks that are to be considered for analysis.  If this is
 349    not called or is called with null, the entire function in
 350    analyzed.  */
 351
 352 void
 353 df_set_blocks (struct df *df, bitmap blocks)
 354 {
 355   if (blocks)
 356     {
 357       if (!df->blocks_to_analyze)
 358         df->blocks_to_analyze = BITMAP_ALLOC (NULL);
 359       bitmap_copy (df->blocks_to_analyze, blocks);
 360     }
 361   else
 362     {
 363       if (df->blocks_to_analyze)
 364         {
 365           BITMAP_FREE (df->blocks_to_analyze);
 366           df->blocks_to_analyze = NULL;
 367         }
 368     }
 369 }
 370
 371
 372 /* Free all the dataflow info and the DF structure.  This should be
 373    called from the df_finish macro which also NULLs the parm.  */
 374
 375 void
 376 df_finish1 (struct df *df)
 377 {
 378   int i;
 379
 380   for (i = 0; i < df->num_problems_defined; i++)
 381     (*df->problems_in_order[i]->problem->free_fun) (df->problems_in_order[i]);
 382
 383   free (df);
 384 }
 385
 386 \f
 387 /*----------------------------------------------------------------------------
 388    The general data flow analysis engine.
 389 ----------------------------------------------------------------------------*/
 390
 391
 392 /* Hybrid search algorithm from "Implementation Techniques for
 393    Efficient Data-Flow Analysis of Large Programs".  */
 394
 395 static void
 396 df_hybrid_search_forward (basic_block bb,
 397                           struct dataflow *dataflow,
 398                           bool single_pass)
 399 {
 400   int result_changed;
 401   int i = bb->index;
 402   edge e;
 403   edge_iterator ei;
 404
 405   SET_BIT (dataflow->visited, bb->index);
 406   gcc_assert (TEST_BIT (dataflow->pending, bb->index));
 407   RESET_BIT (dataflow->pending, i);
 408
 409   /*  Calculate <conf_op> of predecessor_outs.  */
 410   if (EDGE_COUNT (bb->preds) > 0)
 411     FOR_EACH_EDGE (e, ei, bb->preds)
 412       {
 413         if (!TEST_BIT (dataflow->considered, e->src->index))
 414           continue;
 415
 416         (*dataflow->problem->con_fun_n) (dataflow, e);
 417       }
 418   else if (*dataflow->problem->con_fun_0)
 419     (*dataflow->problem->con_fun_0) (dataflow, bb);
 420
 421   result_changed = (*dataflow->problem->trans_fun) (dataflow, i);
 422
 423   if (!result_changed || single_pass)
 424     return;
 425
 426   FOR_EACH_EDGE (e, ei, bb->succs)
 427     {
 428       if (e->dest->index == i)
 429         continue;
 430       if (!TEST_BIT (dataflow->considered, e->dest->index))
 431         continue;
 432       SET_BIT (dataflow->pending, e->dest->index);
 433     }
 434
 435   FOR_EACH_EDGE (e, ei, bb->succs)
 436     {
 437       if (e->dest->index == i)
 438         continue;
 439
 440       if (!TEST_BIT (dataflow->considered, e->dest->index))
 441         continue;
 442       if (!TEST_BIT (dataflow->visited, e->dest->index))
 443         df_hybrid_search_forward (e->dest, dataflow, single_pass);
 444     }
 445 }
 446
 447 static void
 448 df_hybrid_search_backward (basic_block bb,
 449                            struct dataflow *dataflow,
 450                            bool single_pass)
 451 {
 452   int result_changed;
 453   int i = bb->index;
 454   edge e;
 455   edge_iterator ei;
 456
 457   SET_BIT (dataflow->visited, bb->index);
 458   gcc_assert (TEST_BIT (dataflow->pending, bb->index));
 459   RESET_BIT (dataflow->pending, i);
 460
 461   /*  Calculate <conf_op> of predecessor_outs.  */
 462   if (EDGE_COUNT (bb->succs) > 0)
 463     FOR_EACH_EDGE (e, ei, bb->succs)
 464       {
 465         if (!TEST_BIT (dataflow->considered, e->dest->index))
 466           continue;
 467
 468         (*dataflow->problem->con_fun_n) (dataflow, e);
 469       }
 470   else if (*dataflow->problem->con_fun_0)
 471     (*dataflow->problem->con_fun_0) (dataflow, bb);
 472
 473   result_changed = (*dataflow->problem->trans_fun) (dataflow, i);
 474
 475   if (!result_changed || single_pass)
 476     return;
 477
 478   FOR_EACH_EDGE (e, ei, bb->preds)
 479     {
 480       if (e->src->index == i)
 481         continue;
 482
 483       if (!TEST_BIT (dataflow->considered, e->src->index))
 484         continue;
 485
 486       SET_BIT (dataflow->pending, e->src->index);
 487     }
 488
 489   FOR_EACH_EDGE (e, ei, bb->preds)
 490     {
 491       if (e->src->index == i)
 492         continue;
 493
 494       if (!TEST_BIT (dataflow->considered, e->src->index))
 495         continue;
 496
 497       if (!TEST_BIT (dataflow->visited, e->src->index))
 498         df_hybrid_search_backward (e->src, dataflow, single_pass);
 499     }
 500 }
 501
 502
 503 /* This function will perform iterative bitvector dataflow described
 504    by DATAFLOW, producing the in and out sets.  Only the part of the
 505    cfg induced by blocks in DATAFLOW->order is taken into account.
 506
 507    SINGLE_PASS is true if you just want to make one pass over the
 508    blocks.  */
 509
 510 void
 511 df_iterative_dataflow (struct dataflow *dataflow,
 512                        bitmap blocks_to_consider, bitmap blocks_to_init,
 513                        int *blocks_in_postorder, int n_blocks,
 514                        bool single_pass)
 515 {
 516   unsigned int idx;
 517   int i;
 518   sbitmap visited = sbitmap_alloc (last_basic_block);
 519   sbitmap pending = sbitmap_alloc (last_basic_block);
 520   sbitmap considered = sbitmap_alloc (last_basic_block);
 521   bitmap_iterator bi;
 522
 523   dataflow->visited = visited;
 524   dataflow->pending = pending;
 525   dataflow->considered = considered;
 526
 527   sbitmap_zero (visited);
 528   sbitmap_zero (pending);
 529   sbitmap_zero (considered);
 530
 531   EXECUTE_IF_SET_IN_BITMAP (blocks_to_consider, 0, idx, bi)
 532     {
 533       SET_BIT (considered, idx);
 534     }
 535
 536   for (i = 0; i < n_blocks; i++)
 537     {
 538       idx = blocks_in_postorder[i];
 539       SET_BIT (pending, idx);
 540     };
 541
 542   (*dataflow->problem->init_fun) (dataflow, blocks_to_init);
 543
 544   while (1)
 545     {
 546
 547       /* For forward problems, you want to pass in reverse postorder
 548          and for backward problems you want postorder.  This has been
 549          shown to be as good as you can do by several people, the
 550          first being Mathew Hecht in his phd dissertation.
 551
 552          The nodes are passed into this function in postorder.  */
 553
 554       if (dataflow->problem->dir == DF_FORWARD)
 555         {
 556           for (i = n_blocks - 1 ; i >= 0 ; i--)
 557             {
 558               idx = blocks_in_postorder[i];
 559
 560               if (TEST_BIT (pending, idx) && !TEST_BIT (visited, idx))
 561                 df_hybrid_search_forward (BASIC_BLOCK (idx), dataflow, single_pass);
 562             }
 563         }
 564       else
 565         {
 566           for (i = 0; i < n_blocks; i++)
 567             {
 568               idx = blocks_in_postorder[i];
 569
 570               if (TEST_BIT (pending, idx) && !TEST_BIT (visited, idx))
 571                 df_hybrid_search_backward (BASIC_BLOCK (idx), dataflow, single_pass);
 572             }
 573         }
 574
 575       if (sbitmap_first_set_bit (pending) == -1)
 576         break;
 577
 578       sbitmap_zero (visited);
 579     }
 580
 581   sbitmap_free (pending);
 582   sbitmap_free (visited);
 583   sbitmap_free (considered);
 584 }
 585
 586
 587 /* Remove the entries not in BLOCKS from the LIST of length LEN, preserving
 588    the order of the remaining entries.  Returns the length of the resulting
 589    list.  */
 590
 591 static unsigned
 592 df_prune_to_subcfg (int list[], unsigned len, bitmap blocks)
 593 {
 594   unsigned act, last;
 595
 596   for (act = 0, last = 0; act < len; act++)
 597     if (bitmap_bit_p (blocks, list[act]))
 598       list[last++] = list[act];
 599
 600   return last;
 601 }
 602
 603
 604 /* Execute dataflow analysis on a single dataflow problem.
 605
 606    There are three sets of blocks passed in:
 607
 608    BLOCKS_TO_CONSIDER are the blocks whose solution can either be
 609    examined or will be computed.  For calls from DF_ANALYZE, this is
 610    the set of blocks that has been passed to DF_SET_BLOCKS.  For calls
 611    from DF_ANALYZE_SIMPLE_CHANGE_SOME_BLOCKS, this is the set of
 612    blocks in the fringe (the set of blocks passed in plus the set of
 613    immed preds and succs of those blocks).
 614
 615    BLOCKS_TO_INIT are the blocks whose solution will be changed by
 616    this iteration.  For calls from DF_ANALYZE, this is the set of
 617    blocks that has been passed to DF_SET_BLOCKS.  For calls from
 618    DF_ANALYZE_SIMPLE_CHANGE_SOME_BLOCKS, this is the set of blocks
 619    passed in.
 620
 621    BLOCKS_TO_SCAN are the set of blocks that need to be rescanned.
 622    For calls from DF_ANALYZE, this is the accumulated set of blocks
 623    that has been passed to DF_RESCAN_BLOCKS since the last call to
 624    DF_ANALYZE.  For calls from DF_ANALYZE_SIMPLE_CHANGE_SOME_BLOCKS,
 625    this is the set of blocks passed in.
 626
 627                    blocks_to_consider    blocks_to_init    blocks_to_scan
 628    full redo       all                   all               all
 629    partial redo    all                   all               sub
 630    small fixup     fringe                sub               sub
 631 */
 632
 633 static void
 634 df_analyze_problem (struct dataflow *dflow,
 635                     bitmap blocks_to_consider,
 636                     bitmap blocks_to_init,
 637                     bitmap blocks_to_scan,
 638                     int *postorder, int n_blocks, bool single_pass)
 639 {
 640   /* (Re)Allocate the datastructures necessary to solve the problem.  */
 641   if (*dflow->problem->alloc_fun)
 642     (*dflow->problem->alloc_fun) (dflow, blocks_to_scan);
 643
 644   /* Set up the problem and compute the local information.  This
 645      function is passed both the blocks_to_consider and the
 646      blocks_to_scan because the RD and RU problems require the entire
 647      function to be rescanned if they are going to be updated.  */
 648   if (*dflow->problem->local_compute_fun)
 649     (*dflow->problem->local_compute_fun) (dflow, blocks_to_consider, blocks_to_scan);
 650
 651   /* Solve the equations.  */
 652   if (*dflow->problem->dataflow_fun)
 653     (*dflow->problem->dataflow_fun) (dflow, blocks_to_consider, blocks_to_init,
 654                                     postorder, n_blocks, single_pass);
 655
 656   /* Massage the solution.  */
 657   if (*dflow->problem->finalize_fun)
 658     (*dflow->problem->finalize_fun) (dflow, blocks_to_consider);
 659 }
 660
 661
 662 /* Analyze dataflow info for the basic blocks specified by the bitmap
 663    BLOCKS, or for the whole CFG if BLOCKS is zero.  */
 664
 665 void
 666 df_analyze (struct df *df)
 667 {
 668   int *postorder = xmalloc (sizeof (int) *last_basic_block);
 669   bitmap current_all_blocks = BITMAP_ALLOC (NULL);
 670   int n_blocks;
 671   int i;
 672   bool everything;
 673
 674   n_blocks = post_order_compute (postorder, true);
 675
 676   if (n_blocks != n_basic_blocks)
 677     delete_unreachable_blocks ();
 678
 679   for (i = 0; i < n_blocks; i++)
 680     bitmap_set_bit (current_all_blocks, postorder[i]);
 681
 682   /* No one called df_rescan_blocks, so do it.  */
 683   if (!df->blocks_to_scan)
 684     df_rescan_blocks (df, NULL);
 685
 686   /* Make sure that we have pruned any unreachable blocks from these
 687      sets.  */
 688   bitmap_and_into (df->blocks_to_scan, current_all_blocks);
 689
 690   if (df->blocks_to_analyze)
 691     {
 692       everything = false;
 693       bitmap_and_into (df->blocks_to_analyze, current_all_blocks);
 694       n_blocks = df_prune_to_subcfg (postorder, n_blocks, df->blocks_to_analyze);
 695       BITMAP_FREE (current_all_blocks);
 696     }
 697   else
 698     {
 699       everything = true;
 700       df->blocks_to_analyze = current_all_blocks;
 701       current_all_blocks = NULL;
 702     }
 703
 704   /* Skip over the DF_SCAN problem. */
 705   for (i = 1; i < df->num_problems_defined; i++)
 706     df_analyze_problem (df->problems_in_order[i],
 707                         df->blocks_to_analyze, df->blocks_to_analyze,
 708                         df->blocks_to_scan,
 709                         postorder, n_blocks, false);
 710
 711   if (everything)
 712     {
 713       BITMAP_FREE (df->blocks_to_analyze);
 714       df->blocks_to_analyze = NULL;
 715     }
 716
 717   BITMAP_FREE (df->blocks_to_scan);
 718   df->blocks_to_scan = NULL;
 719 }
 720
 721
 722 \f
 723 /*----------------------------------------------------------------------------
 724    Functions to support limited incremental change.
 725 ----------------------------------------------------------------------------*/
 726
 727
 728 /* Get basic block info.  */
 729
 730 static void *
 731 df_get_bb_info (struct dataflow *dflow, unsigned int index)
 732 {
 733   return (struct df_scan_bb_info *) dflow->block_info[index];
 734 }
 735
 736
 737 /* Set basic block info.  */
 738
 739 static void
 740 df_set_bb_info (struct dataflow *dflow, unsigned int index,
 741                 void *bb_info)
 742 {
 743   dflow->block_info[index] = bb_info;
 744 }
 745
 746
 747 /* Called from the rtl_compact_blocks to reorganize the problems basic
 748    block info.  */
 749
 750 void
 751 df_compact_blocks (struct df *df)
 752 {
 753   int i, p;
 754   basic_block bb;
 755   void **problem_temps;
 756   int size = last_basic_block *sizeof (void *);
 757   problem_temps = xmalloc (size);
 758
 759   for (p = 0; p < df->num_problems_defined; p++)
 760     {
 761       struct dataflow *dflow = df->problems_in_order[p];
 762       if (*dflow->problem->free_bb_fun)
 763         {
 764           df_grow_bb_info (dflow);
 765           memcpy (problem_temps, dflow->block_info, size);
 766
 767           /* Copy the bb info from the problem tmps to the proper
 768              place in the block_info vector.  Null out the copied
 769              item.  */
 770           i = NUM_FIXED_BLOCKS;
 771           FOR_EACH_BB (bb)
 772             {
 773               df_set_bb_info (dflow, i, problem_temps[bb->index]);
 774               problem_temps[bb->index] = NULL;
 775               i++;
 776             }
 777           memset (dflow->block_info + i, 0,
 778                   (last_basic_block - i) *sizeof (void *));
 779
 780           /* Free any block infos that were not copied (and NULLed).
 781              These are from orphaned blocks.  */
 782           for (i = NUM_FIXED_BLOCKS; i < last_basic_block; i++)
 783             {
 784               if (problem_temps[i])
 785                 (*dflow->problem->free_bb_fun) (dflow, problem_temps[i]);
 786             }
 787         }
 788     }
 789
 790   free (problem_temps);
 791
 792   i = NUM_FIXED_BLOCKS;
 793   FOR_EACH_BB (bb)
 794     {
 795       SET_BASIC_BLOCK (i, bb);
 796       bb->index = i;
 797       i++;
 798     }
 799
 800   gcc_assert (i == n_basic_blocks);
 801
 802   for (; i < last_basic_block; i++)
 803     SET_BASIC_BLOCK (i, NULL);
 804 }
 805
 806
 807 /* Shove NEW_BLOCK in at OLD_INDEX.  Called from if-cvt to hack a
 808    block.  There is no excuse for people to do this kind of thing.  */
 809
 810 void
 811 df_bb_replace (struct df *df, int old_index, basic_block new_block)
 812 {
 813   int p;
 814
 815   for (p = 0; p < df->num_problems_defined; p++)
 816     {
 817       struct dataflow *dflow = df->problems_in_order[p];
 818       if (dflow->block_info)
 819         {
 820           void *temp;
 821
 822           df_grow_bb_info (dflow);
 823
 824           /* The old switcheroo.  */
 825
 826           temp = df_get_bb_info (dflow, old_index);
 827           df_set_bb_info (dflow, old_index,
 828                           df_get_bb_info (dflow, new_block->index));
 829           df_set_bb_info (dflow, new_block->index, temp);
 830         }
 831     }
 832
 833   SET_BASIC_BLOCK (old_index, new_block);
 834   new_block->index = old_index;
 835 }
 836
 837 /*----------------------------------------------------------------------------
 838    PUBLIC INTERFACES TO QUERY INFORMATION.
 839 ----------------------------------------------------------------------------*/
 840
 841
 842 /* Return last use of REGNO within BB.  */
 843
 844 struct df_ref *
 845 df_bb_regno_last_use_find (struct df *df, basic_block bb, unsigned int regno)
 846 {
 847   rtx insn;
 848   struct df_ref *use;
 849
 850   FOR_BB_INSNS_REVERSE (bb, insn)
 851     {
 852       unsigned int uid = INSN_UID (insn);
 853       for (use = DF_INSN_UID_GET (df, uid)->uses; use; use = use->next_ref)
 854         if (DF_REF_REGNO (use) == regno)
 855           return use;
 856     }
 857   return NULL;
 858 }
 859
 860
 861 /* Return first def of REGNO within BB.  */
 862
 863 struct df_ref *
 864 df_bb_regno_first_def_find (struct df *df, basic_block bb, unsigned int regno)
 865 {
 866   rtx insn;
 867   struct df_ref *def;
 868
 869   FOR_BB_INSNS (bb, insn)
 870     {
 871       unsigned int uid = INSN_UID (insn);
 872       for (def = DF_INSN_UID_GET (df, uid)->defs; def; def = def->next_ref)
 873         if (DF_REF_REGNO (def) == regno)
 874           return def;
 875     }
 876   return NULL;
 877 }
 878
 879
 880 /* Return last def of REGNO within BB.  */
 881
 882 struct df_ref *
 883 df_bb_regno_last_def_find (struct df *df, basic_block bb, unsigned int regno)
 884 {
 885   rtx insn;
 886   struct df_ref *def;
 887
 888   FOR_BB_INSNS_REVERSE (bb, insn)
 889     {
 890       unsigned int uid = INSN_UID (insn);
 891
 892       for (def = DF_INSN_UID_GET (df, uid)->defs; def; def = def->next_ref)
 893         if (DF_REF_REGNO (def) == regno)
 894           return def;
 895     }
 896
 897   return NULL;
 898 }
 899
 900 /* Return true if INSN defines REGNO.  */
 901
 902 bool
 903 df_insn_regno_def_p (struct df *df, rtx insn, unsigned int regno)
 904 {
 905   unsigned int uid;
 906   struct df_ref *def;
 907
 908   uid = INSN_UID (insn);
 909   for (def = DF_INSN_UID_GET (df, uid)->defs; def; def = def->next_ref)
 910     if (DF_REF_REGNO (def) == regno)
 911       return true;
 912
 913   return false;
 914 }
 915
 916
 917 /* Finds the reference corresponding to the definition of REG in INSN.
 918    DF is the dataflow object.  */
 919
 920 struct df_ref *
 921 df_find_def (struct df *df, rtx insn, rtx reg)
 922 {
 923   unsigned int uid;
 924   struct df_ref *def;
 925
 926   if (GET_CODE (reg) == SUBREG)
 927     reg = SUBREG_REG (reg);
 928   gcc_assert (REG_P (reg));
 929
 930   uid = INSN_UID (insn);
 931   for (def = DF_INSN_UID_GET (df, uid)->defs; def; def = def->next_ref)
 932     if (rtx_equal_p (DF_REF_REAL_REG (def), reg))
 933       return def;
 934
 935   return NULL;
 936 }
 937
 938
 939 /* Return true if REG is defined in INSN, zero otherwise.  */
 940
 941 bool
 942 df_reg_defined (struct df *df, rtx insn, rtx reg)
 943 {
 944   return df_find_def (df, insn, reg) != NULL;
 945 }
 946
 947
 948 /* Finds the reference corresponding to the use of REG in INSN.
 949    DF is the dataflow object.  */
 950
 951 struct df_ref *
 952 df_find_use (struct df *df, rtx insn, rtx reg)
 953 {
 954   unsigned int uid;
 955   struct df_ref *use;
 956
 957   if (GET_CODE (reg) == SUBREG)
 958     reg = SUBREG_REG (reg);
 959   gcc_assert (REG_P (reg));
 960
 961   uid = INSN_UID (insn);
 962   for (use = DF_INSN_UID_GET (df, uid)->uses; use; use = use->next_ref)
 963     if (rtx_equal_p (DF_REF_REAL_REG (use), reg))
 964       return use;
 965
 966   return NULL;
 967 }
 968
 969
 970 /* Return true if REG is referenced in INSN, zero otherwise.  */
 971
 972 bool
 973 df_reg_used (struct df *df, rtx insn, rtx reg)
 974 {
 975   return df_find_use (df, insn, reg) != NULL;
 976 }
 977
 978 \f
 979 /*----------------------------------------------------------------------------
 980    Debugging and printing functions.
 981 ----------------------------------------------------------------------------*/
 982
 983 /* Dump dataflow info.  */
 984 void
 985 df_dump (struct df *df, FILE *file)
 986 {
 987   int i;
 988
 989   if (! df || ! file)
 990     return;
 991
 992   fprintf (file, "\n\n%s\n", current_function_name ());
 993   fprintf (file, "\nDataflow summary:\n");
 994   fprintf (file, "def_info->bitmap_size = %d, use_info->bitmap_size = %d\n",
 995            df->def_info.bitmap_size, df->use_info.bitmap_size);
 996
 997   for (i = 0; i < df->num_problems_defined; i++)
 998     (*df->problems_in_order[i]->problem->dump_fun) (df->problems_in_order[i], file);
 999
1000   fprintf (file, "\n");
1001 }
1002
1003
1004 void
1005 df_refs_chain_dump (struct df *df, struct df_ref *ref,
1006                    bool follow_chain, FILE *file)
1007 {
1008   fprintf (file, "{ ");
1009   while (ref)
1010     {
1011       fprintf (file, "%c%d(%d) ",
1012                DF_REF_REG_DEF_P (ref) ? 'd' : 'u',
1013                DF_REF_ID (ref),
1014                DF_REF_REGNO (ref));
1015       if (follow_chain)
1016         df_chain_dump (df, DF_REF_CHAIN (ref), file);
1017       ref = ref->next_ref;
1018     }
1019   fprintf (file, "}");
1020 }
1021
1022
1023 /* Dump either a ref-def or reg-use chain.  */
1024
1025 void
1026 df_regs_chain_dump (struct df *df ATTRIBUTE_UNUSED, struct df_ref *ref,  FILE *file)
1027 {
1028   fprintf (file, "{ ");
1029   while (ref)
1030     {
1031       fprintf (file, "%c%d(%d) ",
1032                DF_REF_REG_DEF_P (ref) ? 'd' : 'u',
1033                DF_REF_ID (ref),
1034                DF_REF_REGNO (ref));
1035       ref = ref->next_reg;
1036     }
1037   fprintf (file, "}");
1038 }
1039
1040
1041 void
1042 df_insn_debug (struct df *df, rtx insn, bool follow_chain, FILE *file)
1043 {
1044   unsigned int uid;
1045   int bbi;
1046
1047   uid = INSN_UID (insn);
1048
1049   if (DF_INSN_UID_DEFS (df, uid))
1050     bbi = DF_REF_BBNO (DF_INSN_UID_DEFS (df, uid));
1051   else if (DF_INSN_UID_USES(df, uid))
1052     bbi = DF_REF_BBNO (DF_INSN_UID_USES (df, uid));
1053   else
1054     bbi = -1;
1055
1056   fprintf (file, "insn %d bb %d luid %d defs ",
1057            uid, bbi, DF_INSN_LUID (df, insn));
1058
1059   df_refs_chain_dump (df, DF_INSN_UID_DEFS (df, uid), follow_chain, file);
1060   fprintf (file, " defs ");
1061   df_refs_chain_dump (df, DF_INSN_UID_USES (df, uid), follow_chain, file);
1062   fprintf (file, "\n");
1063 }
1064
1065 void
1066 df_insn_debug_regno (struct df *df, rtx insn, FILE *file)
1067 {
1068   unsigned int uid;
1069   int bbi;
1070
1071   uid = INSN_UID (insn);
1072   if (DF_INSN_UID_DEFS (df, uid))
1073     bbi = DF_REF_BBNO (DF_INSN_UID_DEFS (df, uid));
1074   else if (DF_INSN_UID_USES(df, uid))
1075     bbi = DF_REF_BBNO (DF_INSN_UID_USES (df, uid));
1076   else
1077     bbi = -1;
1078
1079   fprintf (file, "insn %d bb %d luid %d defs ",
1080            uid, bbi, DF_INSN_LUID (df, insn));
1081   df_regs_chain_dump (df, DF_INSN_UID_DEFS (df, uid), file);
1082
1083   fprintf (file, " uses ");
1084   df_regs_chain_dump (df, DF_INSN_UID_USES (df, uid), file);
1085   fprintf (file, "\n");
1086 }
1087
1088 void
1089 df_regno_debug (struct df *df, unsigned int regno, FILE *file)
1090 {
1091   fprintf (file, "reg %d defs ", regno);
1092   df_regs_chain_dump (df, DF_REG_DEF_GET (df, regno)->reg_chain, file);
1093   fprintf (file, " uses ");
1094   df_regs_chain_dump (df, DF_REG_USE_GET (df, regno)->reg_chain, file);
1095   fprintf (file, "\n");
1096 }
1097
1098
1099 void
1100 df_ref_debug (struct df *df, struct df_ref *ref, FILE *file)
1101 {
1102   fprintf (file, "%c%d ",
1103            DF_REF_REG_DEF_P (ref) ? 'd' : 'u',
1104            DF_REF_ID (ref));
1105   fprintf (file, "reg %d bb %d luid %d insn %d chain ",
1106            DF_REF_REGNO (ref),
1107            DF_REF_BBNO (ref),
1108            DF_REF_INSN (ref) ? DF_INSN_LUID (df, DF_REF_INSN (ref)) : -1,
1109            DF_REF_INSN (ref) ? INSN_UID (DF_REF_INSN (ref)) : -1);
1110   df_chain_dump (df, DF_REF_CHAIN (ref), file);
1111   fprintf (file, "\n");
1112 }
1113 \f
1114 /* Functions for debugging from GDB.  */
1115
1116 void
1117 debug_df_insn (rtx insn)
1118 {
1119   df_insn_debug (ddf, insn, true, stderr);
1120   debug_rtx (insn);
1121 }
1122
1123
1124 void
1125 debug_df_reg (rtx reg)
1126 {
1127   df_regno_debug (ddf, REGNO (reg), stderr);
1128 }
1129
1130
1131 void
1132 debug_df_regno (unsigned int regno)
1133 {
1134   df_regno_debug (ddf, regno, stderr);
1135 }
1136
1137
1138 void
1139 debug_df_ref (struct df_ref *ref)
1140 {
1141   df_ref_debug (ddf, ref, stderr);
1142 }
1143
1144
1145 void
1146 debug_df_defno (unsigned int defno)
1147 {
1148   df_ref_debug (ddf, DF_DEFS_GET (ddf, defno), stderr);
1149 }
1150
1151
1152 void
1153 debug_df_useno (unsigned int defno)
1154 {
1155   df_ref_debug (ddf, DF_USES_GET (ddf, defno), stderr);
1156 }
1157
1158
1159 void
1160 debug_df_chain (struct df_link *link)
1161 {
1162   df_chain_dump (ddf, link, stderr);
1163   fputc ('\n', stderr);
1164 }