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