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 static void * df_get_bb_info (struct dataflow *, unsigned int);
 296 static void df_set_bb_info (struct dataflow *, unsigned int, void *);
 297 /*----------------------------------------------------------------------------
 298   Functions to create, destroy and manipulate an instance of df.
 299 ----------------------------------------------------------------------------*/
 300
 301
 302 /* Initialize dataflow analysis and allocate and initialize dataflow
 303    memory.  */
 304
 305 struct df *
 306 df_init (int flags)
 307 {
 308   struct df *df = xcalloc (1, sizeof (struct df));
 309   df->flags = flags;
 310
 311   /* This is executed once per compilation to initialize platform
 312      specific data structures. */
 313   df_hard_reg_init ();
 314
 315   /* All df instance must define the scanning problem.  */
 316   df_scan_add_problem (df);
 317   ddf = df;
 318   return df;
 319 }
 320
 321 /* Add PROBLEM to the DF instance.  */
 322
 323 struct dataflow *
 324 df_add_problem (struct df *df, struct df_problem *problem)
 325 {
 326   struct dataflow *dflow;
 327
 328   /* First try to add the dependent problem. */
 329   if (problem->dependent_problem)
 330     df_add_problem (df, problem->dependent_problem);
 331
 332   /* Check to see if this problem has already been defined.  If it
 333      has, just return that instance, if not, add it to the end of the
 334      vector.  */
 335   dflow = df->problems_by_index[problem->id];
 336   if (dflow)
 337     return dflow;
 338
 339   /* Make a new one and add it to the end.  */
 340   dflow = xcalloc (1, sizeof (struct dataflow));
 341   dflow->df = df;
 342   dflow->problem = problem;
 343   df->problems_in_order[df->num_problems_defined++] = dflow;
 344   df->problems_by_index[dflow->problem->id] = dflow;
 345
 346   return dflow;
 347 }
 348
 349
 350 /* Set the blocks that are to be considered for analysis.  If this is
 351    not called or is called with null, the entire function in
 352    analyzed.  */
 353
 354 void
 355 df_set_blocks (struct df *df, bitmap blocks)
 356 {
 357   if (blocks)
 358     {
 359       if (df->blocks_to_analyze)
 360         {
 361           int p;
 362           bitmap diff = BITMAP_ALLOC (NULL);
 363           bitmap all = BITMAP_ALLOC (NULL);
 364           bitmap_and_compl (diff, df->blocks_to_analyze, blocks);
 365           for (p = df->num_problems_defined - 1; p >= 0 ;p--)
 366             {
 367               struct dataflow *dflow = df->problems_in_order[p];
 368               if (*dflow->problem->reset_fun)
 369                 (*dflow->problem->reset_fun) (dflow, df->blocks_to_analyze);
 370               else if (*dflow->problem->free_bb_fun)
 371                 {
 372                   bitmap_iterator bi;
 373                   unsigned int bb_index;
 374
 375                   EXECUTE_IF_SET_IN_BITMAP (diff, 0, bb_index, bi)
 376                     {
 377                       basic_block bb = BASIC_BLOCK (bb_index);
 378                       if (bb)
 379                         {
 380                           (*dflow->problem->free_bb_fun)
 381                             (dflow, bb, df_get_bb_info (dflow, bb_index));
 382                           df_set_bb_info (dflow, bb_index, NULL);
 383                         }
 384                     }
 385                 }
 386             }
 387
 388           BITMAP_FREE (all);
 389           BITMAP_FREE (diff);
 390         }
 391       else
 392         {
 393           /* If we have not actually run scanning before, do not try
 394              to clear anything.  */
 395           struct dataflow *scan_dflow = df->problems_by_index [DF_SCAN];
 396           if (scan_dflow->problem_data)
 397             {
 398               bitmap blocks_to_reset = NULL;
 399               int p;
 400               for (p = df->num_problems_defined - 1; p >= 0 ;p--)
 401                 {
 402                   struct dataflow *dflow = df->problems_in_order[p];
 403                   if (*dflow->problem->reset_fun)
 404                     {
 405                       if (!blocks_to_reset)
 406                         {
 407                           basic_block bb;
 408                           blocks_to_reset = BITMAP_ALLOC (NULL);
 409                           FOR_ALL_BB(bb)
 410                             {
 411                               bitmap_set_bit (blocks_to_reset, bb->index);
 412                             }
 413                         }
 414                       (*dflow->problem->reset_fun) (dflow, blocks_to_reset);
 415                     }
 416                 }
 417               if (blocks_to_reset)
 418                 BITMAP_FREE (blocks_to_reset);
 419             }
 420           df->blocks_to_analyze = BITMAP_ALLOC (NULL);
 421         }
 422       bitmap_copy (df->blocks_to_analyze, blocks);
 423     }
 424   else
 425     {
 426       if (df->blocks_to_analyze)
 427         {
 428           BITMAP_FREE (df->blocks_to_analyze);
 429           df->blocks_to_analyze = NULL;
 430         }
 431     }
 432 }
 433
 434
 435 /* Free all the dataflow info and the DF structure.  This should be
 436    called from the df_finish macro which also NULLs the parm.  */
 437
 438 void
 439 df_finish1 (struct df *df)
 440 {
 441   int i;
 442
 443   for (i = 0; i < df->num_problems_defined; i++)
 444     (*df->problems_in_order[i]->problem->free_fun) (df->problems_in_order[i]);
 445
 446   free (df);
 447 }
 448
 449 \f
 450 /*----------------------------------------------------------------------------
 451    The general data flow analysis engine.
 452 ----------------------------------------------------------------------------*/
 453
 454
 455 /* Hybrid search algorithm from "Implementation Techniques for
 456    Efficient Data-Flow Analysis of Large Programs".  */
 457
 458 static void
 459 df_hybrid_search_forward (basic_block bb,
 460                           struct dataflow *dataflow,
 461                           bool single_pass)
 462 {
 463   int result_changed;
 464   int i = bb->index;
 465   edge e;
 466   edge_iterator ei;
 467
 468   SET_BIT (dataflow->visited, bb->index);
 469   gcc_assert (TEST_BIT (dataflow->pending, bb->index));
 470   RESET_BIT (dataflow->pending, i);
 471
 472   /*  Calculate <conf_op> of predecessor_outs.  */
 473   if (EDGE_COUNT (bb->preds) > 0)
 474     FOR_EACH_EDGE (e, ei, bb->preds)
 475       {
 476         if (!TEST_BIT (dataflow->considered, e->src->index))
 477           continue;
 478
 479         (*dataflow->problem->con_fun_n) (dataflow, e);
 480       }
 481   else if (*dataflow->problem->con_fun_0)
 482     (*dataflow->problem->con_fun_0) (dataflow, bb);
 483
 484   result_changed = (*dataflow->problem->trans_fun) (dataflow, i);
 485
 486   if (!result_changed || single_pass)
 487     return;
 488
 489   FOR_EACH_EDGE (e, ei, bb->succs)
 490     {
 491       if (e->dest->index == i)
 492         continue;
 493       if (!TEST_BIT (dataflow->considered, e->dest->index))
 494         continue;
 495       SET_BIT (dataflow->pending, e->dest->index);
 496     }
 497
 498   FOR_EACH_EDGE (e, ei, bb->succs)
 499     {
 500       if (e->dest->index == i)
 501         continue;
 502
 503       if (!TEST_BIT (dataflow->considered, e->dest->index))
 504         continue;
 505       if (!TEST_BIT (dataflow->visited, e->dest->index))
 506         df_hybrid_search_forward (e->dest, dataflow, single_pass);
 507     }
 508 }
 509
 510 static void
 511 df_hybrid_search_backward (basic_block bb,
 512                            struct dataflow *dataflow,
 513                            bool single_pass)
 514 {
 515   int result_changed;
 516   int i = bb->index;
 517   edge e;
 518   edge_iterator ei;
 519
 520   SET_BIT (dataflow->visited, bb->index);
 521   gcc_assert (TEST_BIT (dataflow->pending, bb->index));
 522   RESET_BIT (dataflow->pending, i);
 523
 524   /*  Calculate <conf_op> of predecessor_outs.  */
 525   if (EDGE_COUNT (bb->succs) > 0)
 526     FOR_EACH_EDGE (e, ei, bb->succs)
 527       {
 528         if (!TEST_BIT (dataflow->considered, e->dest->index))
 529           continue;
 530
 531         (*dataflow->problem->con_fun_n) (dataflow, e);
 532       }
 533   else if (*dataflow->problem->con_fun_0)
 534     (*dataflow->problem->con_fun_0) (dataflow, bb);
 535
 536   result_changed = (*dataflow->problem->trans_fun) (dataflow, i);
 537
 538   if (!result_changed || single_pass)
 539     return;
 540
 541   FOR_EACH_EDGE (e, ei, bb->preds)
 542     {
 543       if (e->src->index == i)
 544         continue;
 545
 546       if (!TEST_BIT (dataflow->considered, e->src->index))
 547         continue;
 548
 549       SET_BIT (dataflow->pending, e->src->index);
 550     }
 551
 552   FOR_EACH_EDGE (e, ei, bb->preds)
 553     {
 554       if (e->src->index == i)
 555         continue;
 556
 557       if (!TEST_BIT (dataflow->considered, e->src->index))
 558         continue;
 559
 560       if (!TEST_BIT (dataflow->visited, e->src->index))
 561         df_hybrid_search_backward (e->src, dataflow, single_pass);
 562     }
 563 }
 564
 565
 566 /* This function will perform iterative bitvector dataflow described
 567    by DATAFLOW, producing the in and out sets.  Only the part of the
 568    cfg induced by blocks in DATAFLOW->order is taken into account.
 569
 570    SINGLE_PASS is true if you just want to make one pass over the
 571    blocks.  */
 572
 573 void
 574 df_iterative_dataflow (struct dataflow *dataflow,
 575                        bitmap blocks_to_consider, bitmap blocks_to_init,
 576                        int *blocks_in_postorder, int n_blocks,
 577                        bool single_pass)
 578 {
 579   unsigned int idx;
 580   int i;
 581   sbitmap visited = sbitmap_alloc (last_basic_block);
 582   sbitmap pending = sbitmap_alloc (last_basic_block);
 583   sbitmap considered = sbitmap_alloc (last_basic_block);
 584   bitmap_iterator bi;
 585
 586   dataflow->visited = visited;
 587   dataflow->pending = pending;
 588   dataflow->considered = considered;
 589
 590   sbitmap_zero (visited);
 591   sbitmap_zero (pending);
 592   sbitmap_zero (considered);
 593
 594   EXECUTE_IF_SET_IN_BITMAP (blocks_to_consider, 0, idx, bi)
 595     {
 596       SET_BIT (considered, idx);
 597     }
 598
 599   for (i = 0; i < n_blocks; i++)
 600     {
 601       idx = blocks_in_postorder[i];
 602       SET_BIT (pending, idx);
 603     };
 604
 605   (*dataflow->problem->init_fun) (dataflow, blocks_to_init);
 606
 607   while (1)
 608     {
 609
 610       /* For forward problems, you want to pass in reverse postorder
 611          and for backward problems you want postorder.  This has been
 612          shown to be as good as you can do by several people, the
 613          first being Mathew Hecht in his phd dissertation.
 614
 615          The nodes are passed into this function in postorder.  */
 616
 617       if (dataflow->problem->dir == DF_FORWARD)
 618         {
 619           for (i = n_blocks - 1 ; i >= 0 ; i--)
 620             {
 621               idx = blocks_in_postorder[i];
 622
 623               if (TEST_BIT (pending, idx) && !TEST_BIT (visited, idx))
 624                 df_hybrid_search_forward (BASIC_BLOCK (idx), dataflow, single_pass);
 625             }
 626         }
 627       else
 628         {
 629           for (i = 0; i < n_blocks; i++)
 630             {
 631               idx = blocks_in_postorder[i];
 632
 633               if (TEST_BIT (pending, idx) && !TEST_BIT (visited, idx))
 634                 df_hybrid_search_backward (BASIC_BLOCK (idx), dataflow, single_pass);
 635             }
 636         }
 637
 638       if (sbitmap_first_set_bit (pending) == -1)
 639         break;
 640
 641       sbitmap_zero (visited);
 642     }
 643
 644   sbitmap_free (pending);
 645   sbitmap_free (visited);
 646   sbitmap_free (considered);
 647 }
 648
 649
 650 /* Remove the entries not in BLOCKS from the LIST of length LEN, preserving
 651    the order of the remaining entries.  Returns the length of the resulting
 652    list.  */
 653
 654 static unsigned
 655 df_prune_to_subcfg (int list[], unsigned len, bitmap blocks)
 656 {
 657   unsigned act, last;
 658
 659   for (act = 0, last = 0; act < len; act++)
 660     if (bitmap_bit_p (blocks, list[act]))
 661       list[last++] = list[act];
 662
 663   return last;
 664 }
 665
 666
 667 /* Execute dataflow analysis on a single dataflow problem.
 668
 669    There are three sets of blocks passed in:
 670
 671    BLOCKS_TO_CONSIDER are the blocks whose solution can either be
 672    examined or will be computed.  For calls from DF_ANALYZE, this is
 673    the set of blocks that has been passed to DF_SET_BLOCKS.  For calls
 674    from DF_ANALYZE_SIMPLE_CHANGE_SOME_BLOCKS, this is the set of
 675    blocks in the fringe (the set of blocks passed in plus the set of
 676    immed preds and succs of those blocks).
 677
 678    BLOCKS_TO_INIT are the blocks whose solution will be changed by
 679    this iteration.  For calls from DF_ANALYZE, this is the set of
 680    blocks that has been passed to DF_SET_BLOCKS.  For calls from
 681    DF_ANALYZE_SIMPLE_CHANGE_SOME_BLOCKS, this is the set of blocks
 682    passed in.
 683
 684    BLOCKS_TO_SCAN are the set of blocks that need to be rescanned.
 685    For calls from DF_ANALYZE, this is the accumulated set of blocks
 686    that has been passed to DF_RESCAN_BLOCKS since the last call to
 687    DF_ANALYZE.  For calls from DF_ANALYZE_SIMPLE_CHANGE_SOME_BLOCKS,
 688    this is the set of blocks passed in.
 689
 690                    blocks_to_consider    blocks_to_init    blocks_to_scan
 691    full redo       all                   all               all
 692    partial redo    all                   all               sub
 693    small fixup     fringe                sub               sub
 694 */
 695
 696 static void
 697 df_analyze_problem (struct dataflow *dflow,
 698                     bitmap blocks_to_consider,
 699                     bitmap blocks_to_init,
 700                     bitmap blocks_to_scan,
 701                     int *postorder, int n_blocks, bool single_pass)
 702 {
 703   /* (Re)Allocate the datastructures necessary to solve the problem.  */
 704   if (*dflow->problem->alloc_fun)
 705     (*dflow->problem->alloc_fun) (dflow, blocks_to_scan);
 706
 707   /* Set up the problem and compute the local information.  This
 708      function is passed both the blocks_to_consider and the
 709      blocks_to_scan because the RD and RU problems require the entire
 710      function to be rescanned if they are going to be updated.  */
 711   if (*dflow->problem->local_compute_fun)
 712     (*dflow->problem->local_compute_fun) (dflow, blocks_to_consider, blocks_to_scan);
 713
 714   /* Solve the equations.  */
 715   if (*dflow->problem->dataflow_fun)
 716     (*dflow->problem->dataflow_fun) (dflow, blocks_to_consider, blocks_to_init,
 717                                     postorder, n_blocks, single_pass);
 718
 719   /* Massage the solution.  */
 720   if (*dflow->problem->finalize_fun)
 721     (*dflow->problem->finalize_fun) (dflow, blocks_to_consider);
 722 }
 723
 724
 725 /* Analyze dataflow info for the basic blocks specified by the bitmap
 726    BLOCKS, or for the whole CFG if BLOCKS is zero.  */
 727
 728 void
 729 df_analyze (struct df *df)
 730 {
 731   int *postorder = xmalloc (sizeof (int) *last_basic_block);
 732   bitmap current_all_blocks = BITMAP_ALLOC (NULL);
 733   int n_blocks;
 734   int i;
 735   bool everything;
 736
 737   n_blocks = post_order_compute (postorder, true);
 738
 739   if (n_blocks != n_basic_blocks)
 740     delete_unreachable_blocks ();
 741
 742   for (i = 0; i < n_blocks; i++)
 743     bitmap_set_bit (current_all_blocks, postorder[i]);
 744
 745   /* No one called df_rescan_blocks, so do it.  */
 746   if (!df->blocks_to_scan)
 747     df_rescan_blocks (df, NULL);
 748
 749   /* Make sure that we have pruned any unreachable blocks from these
 750      sets.  */
 751   bitmap_and_into (df->blocks_to_scan, current_all_blocks);
 752
 753   if (df->blocks_to_analyze)
 754     {
 755       everything = false;
 756       bitmap_and_into (df->blocks_to_analyze, current_all_blocks);
 757       n_blocks = df_prune_to_subcfg (postorder, n_blocks, df->blocks_to_analyze);
 758       BITMAP_FREE (current_all_blocks);
 759     }
 760   else
 761     {
 762       everything = true;
 763       df->blocks_to_analyze = current_all_blocks;
 764       current_all_blocks = NULL;
 765     }
 766
 767   /* Skip over the DF_SCAN problem. */
 768   for (i = 1; i < df->num_problems_defined; i++)
 769     df_analyze_problem (df->problems_in_order[i],
 770                         df->blocks_to_analyze, df->blocks_to_analyze,
 771                         df->blocks_to_scan,
 772                         postorder, n_blocks, false);
 773
 774   if (everything)
 775     {
 776       BITMAP_FREE (df->blocks_to_analyze);
 777       df->blocks_to_analyze = NULL;
 778     }
 779
 780   BITMAP_FREE (df->blocks_to_scan);
 781   df->blocks_to_scan = NULL;
 782 }
 783
 784
 785 \f
 786 /*----------------------------------------------------------------------------
 787    Functions to support limited incremental change.
 788 ----------------------------------------------------------------------------*/
 789
 790
 791 /* Get basic block info.  */
 792
 793 static void *
 794 df_get_bb_info (struct dataflow *dflow, unsigned int index)
 795 {
 796   return (struct df_scan_bb_info *) dflow->block_info[index];
 797 }
 798
 799
 800 /* Set basic block info.  */
 801
 802 static void
 803 df_set_bb_info (struct dataflow *dflow, unsigned int index,
 804                 void *bb_info)
 805 {
 806   dflow->block_info[index] = bb_info;
 807 }
 808
 809
 810 /* Called from the rtl_compact_blocks to reorganize the problems basic
 811    block info.  */
 812
 813 void
 814 df_compact_blocks (struct df *df)
 815 {
 816   int i, p;
 817   basic_block bb;
 818   void **problem_temps;
 819   int size = last_basic_block *sizeof (void *);
 820   problem_temps = xmalloc (size);
 821
 822   for (p = 0; p < df->num_problems_defined; p++)
 823     {
 824       struct dataflow *dflow = df->problems_in_order[p];
 825       if (*dflow->problem->free_bb_fun)
 826         {
 827           df_grow_bb_info (dflow);
 828           memcpy (problem_temps, dflow->block_info, size);
 829
 830           /* Copy the bb info from the problem tmps to the proper
 831              place in the block_info vector.  Null out the copied
 832              item.  */
 833           i = NUM_FIXED_BLOCKS;
 834           FOR_EACH_BB (bb)
 835             {
 836               df_set_bb_info (dflow, i, problem_temps[bb->index]);
 837               problem_temps[bb->index] = NULL;
 838               i++;
 839             }
 840           memset (dflow->block_info + i, 0,
 841                   (last_basic_block - i) *sizeof (void *));
 842
 843           /* Free any block infos that were not copied (and NULLed).
 844              These are from orphaned blocks.  */
 845           for (i = NUM_FIXED_BLOCKS; i < last_basic_block; i++)
 846             {
 847               basic_block bb = BASIC_BLOCK (i);
 848               if (problem_temps[i] && bb)
 849                 (*dflow->problem->free_bb_fun)
 850                   (dflow, bb, problem_temps[i]);
 851             }
 852         }
 853     }
 854
 855   free (problem_temps);
 856
 857   i = NUM_FIXED_BLOCKS;
 858   FOR_EACH_BB (bb)
 859     {
 860       SET_BASIC_BLOCK (i, bb);
 861       bb->index = i;
 862       i++;
 863     }
 864
 865   gcc_assert (i == n_basic_blocks);
 866
 867   for (; i < last_basic_block; i++)
 868     SET_BASIC_BLOCK (i, NULL);
 869 }
 870
 871
 872 /* Shove NEW_BLOCK in at OLD_INDEX.  Called from if-cvt to hack a
 873    block.  There is no excuse for people to do this kind of thing.  */
 874
 875 void
 876 df_bb_replace (struct df *df, int old_index, basic_block new_block)
 877 {
 878   int p;
 879
 880   for (p = 0; p < df->num_problems_defined; p++)
 881     {
 882       struct dataflow *dflow = df->problems_in_order[p];
 883       if (dflow->block_info)
 884         {
 885           void *temp;
 886
 887           df_grow_bb_info (dflow);
 888
 889           /* The old switcheroo.  */
 890
 891           temp = df_get_bb_info (dflow, old_index);
 892           df_set_bb_info (dflow, old_index,
 893                           df_get_bb_info (dflow, new_block->index));
 894           df_set_bb_info (dflow, new_block->index, temp);
 895         }
 896     }
 897
 898   SET_BASIC_BLOCK (old_index, new_block);
 899   new_block->index = old_index;
 900 }
 901
 902 /*----------------------------------------------------------------------------
 903    PUBLIC INTERFACES TO QUERY INFORMATION.
 904 ----------------------------------------------------------------------------*/
 905
 906
 907 /* Return last use of REGNO within BB.  */
 908
 909 struct df_ref *
 910 df_bb_regno_last_use_find (struct df *df, basic_block bb, unsigned int regno)
 911 {
 912   rtx insn;
 913   struct df_ref *use;
 914
 915   FOR_BB_INSNS_REVERSE (bb, insn)
 916     {
 917       unsigned int uid = INSN_UID (insn);
 918       for (use = DF_INSN_UID_GET (df, uid)->uses; use; use = use->next_ref)
 919         if (DF_REF_REGNO (use) == regno)
 920           return use;
 921     }
 922   return NULL;
 923 }
 924
 925
 926 /* Return first def of REGNO within BB.  */
 927
 928 struct df_ref *
 929 df_bb_regno_first_def_find (struct df *df, basic_block bb, unsigned int regno)
 930 {
 931   rtx insn;
 932   struct df_ref *def;
 933
 934   FOR_BB_INSNS (bb, insn)
 935     {
 936       unsigned int uid = INSN_UID (insn);
 937       for (def = DF_INSN_UID_GET (df, uid)->defs; def; def = def->next_ref)
 938         if (DF_REF_REGNO (def) == regno)
 939           return def;
 940     }
 941   return NULL;
 942 }
 943
 944
 945 /* Return last def of REGNO within BB.  */
 946
 947 struct df_ref *
 948 df_bb_regno_last_def_find (struct df *df, basic_block bb, unsigned int regno)
 949 {
 950   rtx insn;
 951   struct df_ref *def;
 952
 953   FOR_BB_INSNS_REVERSE (bb, insn)
 954     {
 955       unsigned int uid = INSN_UID (insn);
 956
 957       for (def = DF_INSN_UID_GET (df, uid)->defs; def; def = def->next_ref)
 958         if (DF_REF_REGNO (def) == regno)
 959           return def;
 960     }
 961
 962   return NULL;
 963 }
 964
 965 /* Return true if INSN defines REGNO.  */
 966
 967 bool
 968 df_insn_regno_def_p (struct df *df, rtx insn, unsigned int regno)
 969 {
 970   unsigned int uid;
 971   struct df_ref *def;
 972
 973   uid = INSN_UID (insn);
 974   for (def = DF_INSN_UID_GET (df, uid)->defs; def; def = def->next_ref)
 975     if (DF_REF_REGNO (def) == regno)
 976       return true;
 977
 978   return false;
 979 }
 980
 981
 982 /* Finds the reference corresponding to the definition of REG in INSN.
 983    DF is the dataflow object.  */
 984
 985 struct df_ref *
 986 df_find_def (struct df *df, rtx insn, rtx reg)
 987 {
 988   unsigned int uid;
 989   struct df_ref *def;
 990
 991   if (GET_CODE (reg) == SUBREG)
 992     reg = SUBREG_REG (reg);
 993   gcc_assert (REG_P (reg));
 994
 995   uid = INSN_UID (insn);
 996   for (def = DF_INSN_UID_GET (df, uid)->defs; def; def = def->next_ref)
 997     if (rtx_equal_p (DF_REF_REAL_REG (def), reg))
 998       return def;
 999
1000   return NULL;
1001 }
1002
1003
1004 /* Return true if REG is defined in INSN, zero otherwise.  */
1005
1006 bool
1007 df_reg_defined (struct df *df, rtx insn, rtx reg)
1008 {
1009   return df_find_def (df, insn, reg) != NULL;
1010 }
1011
1012
1013 /* Finds the reference corresponding to the use of REG in INSN.
1014    DF is the dataflow object.  */
1015
1016 struct df_ref *
1017 df_find_use (struct df *df, rtx insn, rtx reg)
1018 {
1019   unsigned int uid;
1020   struct df_ref *use;
1021
1022   if (GET_CODE (reg) == SUBREG)
1023     reg = SUBREG_REG (reg);
1024   gcc_assert (REG_P (reg));
1025
1026   uid = INSN_UID (insn);
1027   for (use = DF_INSN_UID_GET (df, uid)->uses; use; use = use->next_ref)
1028     if (rtx_equal_p (DF_REF_REAL_REG (use), reg))
1029       return use;
1030
1031   return NULL;
1032 }
1033
1034
1035 /* Return true if REG is referenced in INSN, zero otherwise.  */
1036
1037 bool
1038 df_reg_used (struct df *df, rtx insn, rtx reg)
1039 {
1040   return df_find_use (df, insn, reg) != NULL;
1041 }
1042
1043 \f
1044 /*----------------------------------------------------------------------------
1045    Debugging and printing functions.
1046 ----------------------------------------------------------------------------*/
1047
1048 /* Dump dataflow info.  */
1049 void
1050 df_dump (struct df *df, FILE *file)
1051 {
1052   int i;
1053
1054   if (! df || ! file)
1055     return;
1056
1057   fprintf (file, "\n\n%s\n", current_function_name ());
1058   fprintf (file, "\nDataflow summary:\n");
1059   fprintf (file, "def_info->bitmap_size = %d, use_info->bitmap_size = %d\n",
1060            df->def_info.bitmap_size, df->use_info.bitmap_size);
1061
1062   for (i = 0; i < df->num_problems_defined; i++)
1063     (*df->problems_in_order[i]->problem->dump_fun) (df->problems_in_order[i], file);
1064
1065   fprintf (file, "\n");
1066 }
1067
1068
1069 void
1070 df_refs_chain_dump (struct df *df, struct df_ref *ref,
1071                    bool follow_chain, FILE *file)
1072 {
1073   fprintf (file, "{ ");
1074   while (ref)
1075     {
1076       fprintf (file, "%c%d(%d) ",
1077                DF_REF_REG_DEF_P (ref) ? 'd' : 'u',
1078                DF_REF_ID (ref),
1079                DF_REF_REGNO (ref));
1080       if (follow_chain)
1081         df_chain_dump (df, DF_REF_CHAIN (ref), file);
1082       ref = ref->next_ref;
1083     }
1084   fprintf (file, "}");
1085 }
1086
1087
1088 /* Dump either a ref-def or reg-use chain.  */
1089
1090 void
1091 df_regs_chain_dump (struct df *df ATTRIBUTE_UNUSED, struct df_ref *ref,  FILE *file)
1092 {
1093   fprintf (file, "{ ");
1094   while (ref)
1095     {
1096       fprintf (file, "%c%d(%d) ",
1097                DF_REF_REG_DEF_P (ref) ? 'd' : 'u',
1098                DF_REF_ID (ref),
1099                DF_REF_REGNO (ref));
1100       ref = ref->next_reg;
1101     }
1102   fprintf (file, "}");
1103 }
1104
1105
1106 void
1107 df_insn_debug (struct df *df, rtx insn, bool follow_chain, FILE *file)
1108 {
1109   unsigned int uid;
1110   int bbi;
1111
1112   uid = INSN_UID (insn);
1113
1114   if (DF_INSN_UID_DEFS (df, uid))
1115     bbi = DF_REF_BBNO (DF_INSN_UID_DEFS (df, uid));
1116   else if (DF_INSN_UID_USES(df, uid))
1117     bbi = DF_REF_BBNO (DF_INSN_UID_USES (df, uid));
1118   else
1119     bbi = -1;
1120
1121   fprintf (file, "insn %d bb %d luid %d defs ",
1122            uid, bbi, DF_INSN_LUID (df, insn));
1123
1124   df_refs_chain_dump (df, DF_INSN_UID_DEFS (df, uid), follow_chain, file);
1125   fprintf (file, " defs ");
1126   df_refs_chain_dump (df, DF_INSN_UID_USES (df, uid), follow_chain, file);
1127   fprintf (file, "\n");
1128 }
1129
1130 void
1131 df_insn_debug_regno (struct df *df, rtx insn, FILE *file)
1132 {
1133   unsigned int uid;
1134   int bbi;
1135
1136   uid = INSN_UID (insn);
1137   if (DF_INSN_UID_DEFS (df, uid))
1138     bbi = DF_REF_BBNO (DF_INSN_UID_DEFS (df, uid));
1139   else if (DF_INSN_UID_USES(df, uid))
1140     bbi = DF_REF_BBNO (DF_INSN_UID_USES (df, uid));
1141   else
1142     bbi = -1;
1143
1144   fprintf (file, "insn %d bb %d luid %d defs ",
1145            uid, bbi, DF_INSN_LUID (df, insn));
1146   df_regs_chain_dump (df, DF_INSN_UID_DEFS (df, uid), file);
1147
1148   fprintf (file, " uses ");
1149   df_regs_chain_dump (df, DF_INSN_UID_USES (df, uid), file);
1150   fprintf (file, "\n");
1151 }
1152
1153 void
1154 df_regno_debug (struct df *df, unsigned int regno, FILE *file)
1155 {
1156   fprintf (file, "reg %d defs ", regno);
1157   df_regs_chain_dump (df, DF_REG_DEF_GET (df, regno)->reg_chain, file);
1158   fprintf (file, " uses ");
1159   df_regs_chain_dump (df, DF_REG_USE_GET (df, regno)->reg_chain, file);
1160   fprintf (file, "\n");
1161 }
1162
1163
1164 void
1165 df_ref_debug (struct df *df, struct df_ref *ref, FILE *file)
1166 {
1167   fprintf (file, "%c%d ",
1168            DF_REF_REG_DEF_P (ref) ? 'd' : 'u',
1169            DF_REF_ID (ref));
1170   fprintf (file, "reg %d bb %d luid %d insn %d chain ",
1171            DF_REF_REGNO (ref),
1172            DF_REF_BBNO (ref),
1173            DF_REF_INSN (ref) ? DF_INSN_LUID (df, DF_REF_INSN (ref)) : -1,
1174            DF_REF_INSN (ref) ? INSN_UID (DF_REF_INSN (ref)) : -1);
1175   df_chain_dump (df, DF_REF_CHAIN (ref), file);
1176   fprintf (file, "\n");
1177 }
1178 \f
1179 /* Functions for debugging from GDB.  */
1180
1181 void
1182 debug_df_insn (rtx insn)
1183 {
1184   df_insn_debug (ddf, insn, true, stderr);
1185   debug_rtx (insn);
1186 }
1187
1188
1189 void
1190 debug_df_reg (rtx reg)
1191 {
1192   df_regno_debug (ddf, REGNO (reg), stderr);
1193 }
1194
1195
1196 void
1197 debug_df_regno (unsigned int regno)
1198 {
1199   df_regno_debug (ddf, regno, stderr);
1200 }
1201
1202
1203 void
1204 debug_df_ref (struct df_ref *ref)
1205 {
1206   df_ref_debug (ddf, ref, stderr);
1207 }
1208
1209
1210 void
1211 debug_df_defno (unsigned int defno)
1212 {
1213   df_ref_debug (ddf, DF_DEFS_GET (ddf, defno), stderr);
1214 }
1215
1216
1217 void
1218 debug_df_useno (unsigned int defno)
1219 {
1220   df_ref_debug (ddf, DF_USES_GET (ddf, defno), stderr);
1221 }
1222
1223
1224 void
1225 debug_df_chain (struct df_link *link)
1226 {
1227   df_chain_dump (ddf, link, stderr);
1228   fputc ('\n', stderr);
1229 }